Causal effect estimation from networked observational data encounters notable challenges, primarily hidden confounders arising from network structure, or spillover effects that influence unit's outcomes based on neighboring treatment assignments. Existing graph neural network (GNN)-based methods have endeavored to address these challenges, utilizing the GNN's message-passing mechanism to capture hidden confounders or model spillover effects. However, they mainly focus on transductive causal effect learning on a single networked data, limiting their efficacy in inductive settings for real-world applications where networked data often originates from multiple environments influenced by potentially varying time or geographical regions. In light of this, we introduce the principle of invariance to the task of causal effect estimation on networked data, culminating in our Invariant Graph Learning (IGL) framework. Specifically, it first generates multiple networked data to simulate diverse environments from a given observational data. Then it further encourages the model to learn environment-invariant representations for confounders and spillover effects. Such a design enables the model to extrapolate beyond a single observed environment, thereby improving the performance of causal effect estimation in potential new environments. Extensive experiments on two real-world datasets demonstrates the superiority of our approach.
论文检索
输入标题、作者或关键词，从 8,216 篇学术成果中精准定位
Link recommendation systems in online social networks (OSNs), such as Facebook's "People You May Know", Twitter's "Who to Follow", and Instagram's "Suggested Accounts", facilitate the formation of new connections among users. This paper addresses the challenge of link recommendation for the purpose of social influence maximization. In particular, given a graph G and the seed set S, our objective is to select k edges that connect seed nodes and ordinary nodes to optimize the influence dissemination of the seed set. This problem, referred to as influence maximization with augmentation (IMA), has been proven to be NP-hard. In this paper, we propose an algorithm, namely AIS, consisting of an efficient estimator for augmented influence estimation and an accelerated sampling approach. AIS provides a (1-1/e - ε)-approximate solution with a high probability of 1-δ, and runs in O(k2 (m+n) log (n / δ) / ε2 + k |EC|) time assuming that the influence of any singleton node is smaller than that of the seed set. To the best of our knowledge, this is the first algorithm that can be implemented on large graphs containing millions of nodes while preserving strong theoretical guarantees. We conduct extensive experiments to demonstrate the effectiveness and efficiency of our proposed algorithm.
What News Do People Get on Social Media? Analyzing Exposure and Consumption of News through Data Donations
PDF ↗Understanding how exposure to news on social media impacts public discourse and exacerbates political polarization is a significant endeavor in both computer and social sciences. Unfortunately, progress in this area is hampered by limited access to data due to the closed nature of social media platforms. Consequently, prior studies have been constrained to considering only fragments of users' news exposure and reactions. To overcome this obstacle, we present an innovative measurement approach centered on donating personal data for scientific purposes, facilitated through a privacy-preserving tool that captures users' interactions with news on Facebook. This approach offers a nuanced perspective on users' news exposure and consumption, encompassing different types of news exposure: selective, incidental, algorithmic, and targeted, driven by the diverse underlying mechanisms governing news appearance on users' feeds. Our analysis of data from 472 participants based in the U.S. reveals several interesting findings. For instance, users are more prone to encountering misinformation because of their active selection of low-quality news sources rather than being exposed solely due to friends or platform algorithms. Furthermore, our study uncovers that users are open to engaging with news sources with opposite political ideology as long as these interactions are not visible to their immediate social circles. Overall, our study showcases the viability of data donation as a means to provide clarity to longstanding questions in this field, offering new perspectives on the intricate dynamics of social media news consumption and its effects.
The flourishing of knowledge graph (KG) applications has driven the need for entity alignment (EA) across KGs. However, the heterogeneity of practical KGs, characterized by differing scales, structures, and limited overlapping entities, greatly surpasses that of existing EA datasets. This discrepancy highlights an oversimplified heterogeneity in current EA datasets, which obstructs the exploration of the EA application. In this paper, we study the performance of EA methods on the alignment of highly heterogeneous KGs (HHKGs). Firstly, we address the oversimplified heterogeneity settings of current datasets and propose two new HHKG datasets that closely mimic practical EA scenarios. Then, based on these datasets, we conduct extensive experiments to evaluate previous representative EA methods. Our findings reveal that, in aligning HHKGs, valuable structure information can hardly be exploited, which leads to inferior performance of existing EA methods, especially those based on GNNs. These findings shed light on the potential problems associated with the conventional application of GNN-based methods as a panacea for all EA datasets. Consequently, to elucidate what EA methodology is genuinely beneficial in practical scenarios, we undertake an in-depth analysis by implementing a simple but effective approach: Simple-HHEA. Our experiment results conclude that the key to the future EA model design in practice lies in their adaptability and efficiency to varying information quality conditions, as well as their capability to capture patterns across HHKGs. The datasets and source code are available at https://github.com/IDEA-FinAI/Simple-HHEA.
Query2GMM: Learning Representation with Gaussian Mixture Model for Reasoning over Knowledge Graphs
PDF ↗Logical query answering over Knowledge Graphs (KGs) is a fundamental yet complex task. A promising approach to achieve this is to embed queries and entities jointly into the same embedding space. Research along this line suggests that using multi-modal distribution to represent answer entities is more suitable than uni-modal distribution, as a single query may contain multiple disjoint answer subsets due to the compositional nature of multi-hop queries and the varying latent semantics of relations. However, existing methods based on multi-modal distribution roughly represent each subset without capturing its accurate cardinality, or even degenerate into uni-modal distribution learning during the reasoning process due to the lack of an effective similarity measure. To better model queries with diversified answers, we propose Query2GMM for answering logical queries over knowledge graphs. In Query2GMM, we present the GMM embedding to represent each query using a univariate Gaussian Mixture Model (GMM). Each subset of a query is encoded by its cardinality, semantic center and dispersion degree, allowing for precise representation of multiple subsets. Then we design specific neural networks for each operator to handle the inherent complexity that comes with multi-modal distribution while alleviating the cascading errors. Last, we design a new similarity measure to assess the relationships between an entity and a query's multi-answer subsets, enabling effective multi-modal distribution learning for reasoning. Comprehensive experimental results show that Query2GMM outperforms the best competitor by an absolute average of 6.35%.
Extreme Multi Label (XML) problems, and in particular XML completion -- the task of prediction the missing labels of an entity -- have attracted significant attention in the past few years. Most XML completion problems can organically leverage a label hierarchy, which can be represented as a tree that encodes the relations between the different labels. In this paper, we propose a new algorithm, HECTOR - Hierarchical Extreme Completion for Text based on TransfORmer, to solve XML Completion problems more effectively. HECTOR operates by directly predicting paths in the label tree rather than individual labels, thus taking advantage of information encoded in the hierarchy. Due to the sequential aspect of these paths, HECTOR can leverage the effectiveness and performance of the Transformer architecture to outperform state-of-the-art of XML completion methods. Extensive evaluations on three real-world datasets demonstrate the effectiveness of our approach for XML completion. We compare HECTOR with several state-of-the-art XML completion methods for various completion problems, and in particular for label refinement, i.e., the scenario where only the coarse labels (i.e. the first few top levels in a taxonomy) are observed. Empirical results on three different datasets show that our method significantly outperforms the state of the art, with HECTOR frequently outperforming previous techniques by more than 10% according to multiple metrics.
Link prediction models assign scores to predict new, plausible edges to complete knowledge graphs. In link prediction evaluation, the score of an existing edge (positive) is ranked w.r.t. the scores of its synthetically corrupted counterparts (negatives). An accurate model ranks positives higher than negatives, assuming ascending order. Since the number of negatives are typically large for a single positive, link prediction evaluation is computationally expensive. As far as we know, only one approach has proposed to replace rank aggregations by a distance between sample positives and negatives. Unfortunately, the distance does not consider individual ranks, so edges in isolation cannot be assessed. In this paper, we propose an alternative protocol based on posterior probabilities of positives rather than ranks. A calibration function assigns posterior probabilities to edges that measure their plausibility. We propose to assess our alternative protocol in various ways, including whether expected semantics are captured when using different strategies to synthetically generate negatives. Our experiments show that posterior probabilities and ranks are highly correlated. Also, the time reduction of our alternative protocol is quite significant: more than 77% compared to rank-based evaluation. We conclude that link prediction evaluation based on posterior probabilities is viable and significantly reduces computational costs.
Uniform Interpolation (UI) is an advanced reasoning service used to narrow down an ontology to a restricted view. This new ontology, known as a uniform interpolant, will only consist of the ''relevant names'', yet it will retain their original meanings. UI is immensely promising due to its applicability across various domains where custom views of ontologies are essential. Nonetheless, to unlock its full potential, we need optimized techniques to generate these tailored views. Previous studies suggest that creating uniform interpolants for EL-ontologies is notably challenging. In some instances, it is not even feasible to compute a uniform interpolant; when feasible, the size of the uniform interpolant can be up to triple exponentially larger than the source ontology. Despite these challenges, our paper introduces an improved ''forgetting'' technique specifically designed for computing uniform interpolants of ELI-ontologies. We demonstrate that, with good normalization and inference strategies, such uniform interpolants can be efficiently computed, just as quickly as computing ''modules''. A comprehensive evaluation with a prototypical implementation of the method shows superb success rates over two popular benchmark datasets, demonstrating a clear computational advantage over state-of-the-art approaches.
Tor hidden services (HSs) are used to provide anonymous services to users on the Internet without revealing the location of the servers. However, existing approaches have proven ineffective in mitigating the misuse of hidden services. Our investigation reveals that the latest iteration of Tor hidden services still exhibits vulnerabilities related to Hidden Service Directories (HSDirs). Building upon this identified weakness, we introduce the HSDirSniper attack, which leverages a substantial volume of descriptors to inundate the HSDir's descriptor cache. This results in the HSDir purging all stored descriptors, thereby blocking arbitrary hidden services. Notably, our attack represents the most practical means of blocking hidden services within the current high-adversarial context. The advantage of the HSDirSniper attack lies in its covert nature, as the targeted hidden service remains unaware of the attack. Additionally, the successful execution of this attack does not require the introduction of a colluding routing node within the Tor Network. We conducted comprehensive experiments in the real-world Tor Network, and the experimental results show that an attacker equipped with a certain quantity of hidden servers can render arbitrary hidden services inaccessible up to 90% of the time. To ascertain the potential scope of damage that the HSDirSniper attack can inflict upon hidden services, we provide a formal analytical framework for quantifying the cost of the HSDirSniper attack. Finally, we discuss the ethical concerns and countermeasures.
Malicious traffic detection has been a focal point in the field of network security, and deep learning-based approaches are emerging as a new paradigm. However, most of them are supervised methods, which highly depend on well-labeled data, and fail to handle unknown or continuously evolving attacks. Unsupervised methods alleviate the need for labeled data, but existing methods are often limited to detecting anomalies either in vertical perspective through historical comparisons or in horizontal perspective by comparing with concurrent entities. Relying on data from a single perspective is unreliable, and it limits the model's accuracy and generalizability. In this paper, we propose a novel method ContraMTD based on contrastive learning, which comprehensively considers both vertical and horizontal perspectives. ContraMTD extracts local behavior features and global interaction features from normal network traffic by proposed SEC and DE-GAT respectively, then employs contrastive learning to learn the relationship, especially consistency between them, and finally detects malicious traffic through a multi-round scoring approach. We conduct extensive experiments on three datasets, including a self-collected dataset, and the results demonstrate that our method outperforms many state-of-the-art methods in the domain of unsupervised malicious traffic detection.
This paper introduces a novel information retrieval (IR) task of Conversational Entity Retrieval from a Knowledge Graph (CER-KG), which extends non-conversational entity retrieval from a knowledge graph (KG) to the conversational scenario. The user queries in CER-KG dialog turns may rely on the results of the preceding turns, which are KG entities. Similar to the conversational document IR, CER-KG can be viewed as a sequence of interrelated ranking tasks. To enable future research on CER-KG, we created QBLink-KG, a publicly available benchmark that was adapted from QBLink, a benchmark for text-based conversational reading comprehension of Wikipedia. As an initial approach to CER-KG, we experimented with Transformer- and LSTM-based query encoders in combination with the Neural Architecture for Conversational Entity Retrieval (NACER), our proposed feature-based neural architecture for entity ranking in CER-KG. NACER computes the ranking score of a candidate KG entity by taking into account diverse lexical and semantic matching signals between various KG components in its neighborhood, such as entities, categories, and literals, as well as entities in the results of the preceding turns in dialog history. The reported experimental results reveal the key challenges of CER-KG along with the possible directions for new approaches to this task.
Cognitive Personalized Search Integrating Large Language Models with an Efficient Memory Mechanism
PDF ↗Traditional search engines usually provide identical search results for all users, overlooking individual preferences. To counter this limitation, personalized search has been developed to re-rank results based on user preferences derived from query logs. Deep learning-based personalized search methods have shown promise, but they rely heavily on abundant training data, making them susceptible to data sparsity challenges. This paper proposes a Cognitive Personalized Search (CoPS) model, which integrates Large Language Models (LLMs) with a cognitive memory mechanism inspired by human cognition. CoPS employs LLMs to enhance user modeling and user search experience. The cognitive memory mechanism comprises sensory memory for quick sensory responses, working memory for sophisticated cognitive responses, and long-term memory for storing historical interactions. CoPS handles new queries using a three-step approach: identifying re-finding behaviors, constructing user profiles with relevant historical information, and ranking documents based on personalized query intent. Experiments show that CoPS outperforms baseline models in zero-shot scenarios.
In the rapidly evolving landscape of information retrieval, search engines strive to provide more personalized and relevant results to users. Query suggestion systems play a crucial role in achieving this goal by assisting users in formulating effective queries. However, existing query suggestion systems mainly rely on textual inputs, potentially limiting user search experiences for querying images. In this paper, we introduce a novel Multimodal Query Suggestion (MMQS) task, which aims to generate query suggestions based on user query images to improve the intentionality and diversity of search results. We present the RL4Sugg framework, leveraging the power of Large Language Models (LLMs) with Multi-Agent Reinforcement Learning from Human Feedback to optimize the generation process. Through comprehensive experiments, we validate the effectiveness of RL4Sugg, demonstrating a 18% improvement compared to the best existing approach. Moreover, the MMQS has been transferred into real-world search engine products, which yield enhanced user engagement. Our research advances query suggestion systems and provides a new perspective on multimodal information retrieval.
Node embedding learns low-dimensional vectors for nodes in the graph. Recent state-of-the-art embedding approaches take Personalized PageRank (PPR) as the proximity measure and factorize the PPR matrix or its adaptation to generate embeddings. However, little previous work analyzes what information is encoded by these approaches, and how the information correlates with their superb performance in downstream tasks. In this work, we first show that state-of-the-art embedding approaches that factorize a PPR-related matrix can be unified into a closed-form framework. Then, we study whether the embeddings generated by this strategy can be inverted to better recover the graph topology information than random-walk based embeddings. To achieve this, we propose two methods for recovering graph topology via PPR-based embeddings, including the analytical method and the optimization method. Extensive experimental results demonstrate that the embeddings generated by factorizing a PPR-related matrix maintain more topological information, such as common edges and community structures, than that generated by random walks, paving a new way to systematically comprehend why PPR-based node embedding approaches outperform random walk-based alternatives in various downstream tasks. To the best of our knowledge, this is the first work that focuses on the interpretability of PPR-based node embedding approaches.
Out-of-distribution (OOD) generalization has gained increasing attentions for learning on graphs, as graph neural networks (GNNs) often exhibit performance degradation with distribution shifts. The challenge is that distribution shifts on graphs involve intricate interconnections between nodes, and the environment labels are often absent in data. In this paper, we adopt a bottom-up data-generative perspective and reveal a key observation through causal analysis: the crux of GNNs' failure in OOD generalization lies in the latent confounding bias from the environment. The latter misguides the model to leverage environment-sensitive correlations between ego-graph features and target nodes' labels, resulting in undesirable generalization on new unseen nodes. Built upon this analysis, we introduce a conceptually simple yet principled approach for training robust GNNs under node-level distribution shifts, without prior knowledge of environment labels. Our method resorts to a new learning objective derived from causal inference that coordinates an environment estimator and a mixture-of-expert GNN predictor. The new approach can counteract the confounding bias in training data and facilitate learning generalizable predictive relations. Extensive experiment demonstrates that our model can effectively enhance generalization with various types of distribution shifts and yield up to 27.4% accuracy improvement over state-of-the-arts on graph OOD generalization benchmarks.
Scalable graph neural networks (GNNs) have emerged as a promising technique, which exhibits superior predictive performance and high running efficiency across numerous large-scale graph-based web applications. However, (i) Most scalable GNNs tend to treat all nodes with the same propagation rules, neglecting their topological uniqueness; (ii) Existing node-wise propagation optimization strategies are insufficient on web-scale graphs with intricate topology, where a full portrayal of nodes' local properties is required. Intuitively, different nodes in web-scale graphs possess distinct topological roles, and therefore propagating them indiscriminately or neglecting local contexts may compromise the quality of node representations. To address the above issues, we propose Adaptive Topology-aware Propagation (ATP), which reduces potential high-bias propagation and extracts structural patterns of each node in a scalable manner to improve running efficiency and predictive performance. Remarkably, ATP is crafted to be a plug-and-play node-wise propagation optimization strategy, allowing for offline execution independent of the graph learning process in a new perspective. Therefore, this approach can be seamlessly integrated into most scalable GNNs while remaining orthogonal to existing node-wise propagation optimization strategies. Extensive experiments on 12 datasets have demonstrated the effectiveness of ATP.
User cold-start recommendation aims to provide accurate items for the newly joint users and is a hot and challenging problem. Nowadays as people participant in different domains, how to recommend items in the new domain for users in an old domain has become more urgent. In this paper, we focus on the Dual Cold-Start Cross Domain Recommendation (Dual-CSCDR) problem. That is, providing the most relevant items for new users on the source and target domains. The prime task in Dual-CSCDR is to properly model user-item rating interactions and map user expressive embeddings across domains. However, previous approaches cannot solve Dual-CSCDR well, since they separate the collaborative filtering and distribution mapping process, leading to the error superimposition issue. Moreover, most of these methods fail to fully exploit the cross-domain relationship among large number of non-overlapped users, which strongly limits their performance. To fill this gap, we propose User Distribution Mapping model with Collaborative Filtering (UDMCF), a novel end-to-end cold-start cross-domain recommendation framework for the Dual-CSCDR problem. UDMCF includes two main modules, i.e., rating prediction module and distribution alignment module. The former module adopts one-hot ID vectors and multi-hot historical ratings for collaborative filtering via a contrastive loss. The latter module contains overlapped user embedding alignment and general user subgroup distribution alignment. Specifically, we innovatively propose unbalance distribution optimal transport with typical subgroup discovering algorithm to map the whole user distributions. Our empirical study on several datasets demonstrates that UDMCF significantly outperforms the state-of-the-art models under the Dual-CSCDR setting.
In auction theory, a core is a stable outcome where no subgroup of participants can achieve better results for themselves. Core-competitive auctions aim to generate revenue that is achievable in a core. They are particularly important because they not only generate optimized revenue for the seller, but also provide an efficient and stable environment for participants. We generalize the design of core-competitive auctions to encompass partially observable networked markets (PONM). Unlike traditional auctions, which often deal with scenarios of limited trading activity, our approach to core-competitive auctions for PONM captures the nature of real-world transaction markets, which is a large linking world for the economic entities and commodities circulate among the entities in the market. Our generalizing the auction market to PONM can much improve the liquidity of the auction, and is especially meaningful for the web economics. Specifically, we quantify the upper and lower bounds of the minimum core revenue in PONM, and further prove that there does not exist any truthful auction for PONM which is efficient and core-competitive. Governed by this impossible result, we identify the criteria that the allocation rule for PONM should meet. Based on these criteria, we propose a new class of auction mechanisms for PONM that is individually rational, incentive-compatible, and core-competitive.
Recommendation algorithms play a pivotal role in shaping our media choices, which makes it crucial to comprehend their long-term impact on user behavior. These algorithms are often linked to two critical outcomes: homogenization, wherein users consume similar content despite disparate underlying preferences, and the filter bubble effect, wherein individuals with differing preferences only consume content aligned with their preferences (without much overlap with other users). Prior research assumes a trade-off between homogenization and filter bubble effects and then shows that personalized recommendations mitigate filter bubbles by fostering homogenization. However, because of this assumption of a tradeoff between these two effects, prior work cannot develop a more nuanced view of how recommendation systems may independently impact homogenization and filter bubble effects. We develop a more refined definition of homogenization and the filter bubble effect by decomposing them into two key metrics: how different the average consumption is between users (inter-user diversity) and how varied an individual's consumption is (intra-user diversity). We then use a novel agent-based simulation framework that enables a holistic view of the impact of recommendation systems on homogenization and filter bubble effects. Our simulations show that traditional recommendation algorithms (based on past behavior) mainly reduce filter bubbles by affecting inter-user diversity without significantly impacting intra-user diversity. Building on these findings, we introduce two new recommendation algorithms that take a more nuanced approach by accounting for both types of diversity.
Time series data has become ubiquitous across various fields such as healthcare, finance, entertainment, and transportation, driven by advancements in sensing technologies that enable continuous monitoring and recording. This growth in data size and complexity presents new challenges for traditional analysis techniques, necessitating the development of advanced, interdisciplinary temporal mining algorithms. The goals of this workshop are to: (1) highlight significant challenges in learning and mining from time series data, such as irregular sampling, spatiotemporal structures, and uncertainty quantification; (2) discuss recent developments in algorithmic, theoretical, statistical, and systems-based approaches for addressing these challenges, including both classical methods and large language models (LLMs); and (3) synergize research efforts by exploring both new and open problems in time series analysis and mining. This workshop will focus on both the theoretical and practical aspects of time series data analysis, providing a platform for researchers and practitioners from academia, government, and industry to discuss potential research directions, critical technical issues, and present solutions for practical applications. Contributions from related fields such as AI, machine learning, data science, and statistics are also included.