Simulating group-level user behavior enables scalable counterfactual evaluation of merchant strategies without costly online experiments. However, building a trustworthy simulator faces two structural challenges. First, information incompleteness causes reasoning-based simulators to over-rationalize when unobserved factors such as offline context and implicit habits are missing. Second, mechanism duality requires capturing both interpretable preferences and implicit statistical regularities, which no single paradigm achieves alone. We propose Policy-Guided Hybrid Simulation (PGHS), a dual-process framework that mines transferable decision policies from behavioral trajectories and uses them as a shared alignment layer. This layer anchors an LLM-based reasoning branch that prevents over-rationalization and an ML-based fitting branch that absorbs implicit regularities. Group-level predictions from both branches are fused for complementary correction. We deploy PGHS on Meituan with 101 merchants and over 26,000 trajectories. PGHS achieves a group simulation error of 8.80%, improving over the best reasoning-based and fitting-based baselines by 45.8% and 40.9% respectively.

Multimodal knowledge editing (MKE) aims to efficiently rectify outdated or incorrect knowledge in multimodal large language models (MLLMs) while preserving reliability, generality, and locality. Recently, in-context editing (ICE) has emerged as a prevalent paradigm for MKE, focusing on inference-time context manipulation. While ICE mitigates the side effects of intrinsic interventions on MLLMs, it still suffers from an out-of-control limitation. Specifically, previous methods rely excessively on the implicit contextualization of MLLMs and regard the MKE process as a matter of chance. Based on this observation, we further identify the corresponding challenges as localizing the responsible key units and defining the triggering conditions within MLLMs. To address these challenges, we pursue a controllable ICE approach and refer to the multimodal neurons. Consequently, we propose a neuron-level controllable ICE framework for MKE, namely NeuCon-ICE. It consists of (1) a multimodal contextual neuron identification module that aims to determine where to edit by identifying the tightly coupled multimodal contextual neurons, and (2) a context-aware neuron editing module that aims to determine how to edit by selectively injecting context-aware updates into the identified neurons. Experiments on three representative MLLMs (BLIP-2, MiniGPT-4, and LLaVA 1.5) on ComprehendEdit and E-VQA demonstrate that NeuCon-ICE consistently achieves state-of-the-art overall performance, delivering an overall gain of at least 10.79% across baselines and datasets. The code is available at https://github.com/jc4357/NeuCon-ICE.

Large language models (LLMs) excel when user goals are clearly specified, yet real-world queries are often vague and evolving, forcing LLMs to guess and leading to misaligned responses. Existing approaches attempt to clarify user intents through iterative questioning. While effective in alleviating disambiguation, this paradigm tends to merely provide standard and normal responses, which fails to meet the growing demand for diverse personalized expression of users. Based on the observation, we first identify its problem as the ignore of users' mental states, in which the complicated mental elements, unclear functional rules, and evolving mental states pose obstacles to approach the problem. Therefore, in this paper, we introduce the theory of the mentalizing network in the human brain and propose a neurobiologically inspired framework, i.e., NeurPIU, that endows LLMs with human-like mentalizing capabilities for personalized intent understanding. NeurPIU constructs an intent neural network that organizes users' long-term mental states into a three-layer graph; retrieves query-relevant states via spreading activation mechanism with temporal decay; and injects an encoded cognitive prefix into a frozen LLM through a lightweight LoRA-based cognitive model to guide response generation. The network is incrementally updated after each interaction to track evolving user cognition. Extensive experiments on four benchmarks show that NeurPIU consistently improves long-term dialogue quality, especially its plug-and-play feature, and generalizes to conversational recommendation and mental health counseling. A user study with physiological measurements further indicates that NeurPIU reduces interaction time by 53.95% while improving user experience ratings by 22.38%. All data and code are released.

Entity matching is a fundamental task in a wide range of retrieval and knowledge applications, aiming to identify whether two objects correspond to the same real-world entity across heterogeneous sources. Typical variants include entity resolution (ER), entity linking (EL), and entity alignment (EA). While recent unified matchers have made progress through multi-task training with comprehensive annotations, real-world pipelines often operate under scarce supervision, where labeled data is incomplete and fails to cover the full spectrum of matching scenarios. In this regime, supervised unified models degrade substantially, and deployable compact LLMs remain unreliable: lightweight fine-tuning and in-context learning yield inconsistent behavior and can even exhibit negative effects under scenario shifts. To fill in this gap, we propose øurs, a meta-rule induction and retrieval framework for unified entity matching under scarce supervision. Instead of relying on parametric adaptation, øurs converts limited supervision into explicit natural-language rules, abstracts them into reusable meta-rules via hierarchical clustering, and retrieves the most relevant meta-rules to guide the LLM's inference for each input instance. This design improves robustness by grounding decisions on explicit and reusable evidence, instead of relying solely on implicit adaptation or prompt demonstrations. Extensive experiments show that øurs achieves state-of-the-art performance on unified entity matching under scarce supervision.

Entity Matching (EM) is a fundamental task in data integration, traditionally studied over structured data such as tables and knowledge graphs. In modern repositories, real-world objects are often represented across multiple modalities, including structured entities with symbolic attributes and visual entities in image-centric collections. This motivates cross-modal entity matching, which aims to identify visual-structured entity pairs that refer to the same object. Existing methods typically rely on pretrained vision-language models to compute entity pair similarity and derive correspondence via local ranking, which, however, can be unreliable given noisy and ambiguous cross-modal data and may produce globally inconsistent correspondences across related entities. Multimodal large language models (MLLMs) offer richer cross-modal cues for matching, but exhaustive MLLM reasoning over large candidate spaces is prohibitively expensive. To address these limitations, in this work, we propose øurq, a blackboard-based multi-agent framework for zero-shot cross-modal entity matching that performs iterative, self-correcting refinement by fusing multiple matching signals, explicitly regulating global consistency, and selectively invoking an MLLM only for hard cases. We further construct two new benchmarks from real-world visual and structured data. Extensive experiments show that øurq consistently outperforms competitive baselines, providing an effective solution for zero-shot cross-modal entity matching. We release our data and code at https://github.com/Q-17/CoMCo.

The widespread use of social-media graphs has provided a convenient channel for rumor propagation. Rapid localization of rumor sources is therefore crucial for mitigating diffusion and enabling punitive countermeasures. Source Localization (SL) aims to identify the origin nodes given partial infection observations. Although deep-learning-based SL approaches outperform traditional estimators, three fundamental limitations remain: (i) Model Complexity —existing methods enrich node embeddings with cascades of auxiliary features, yielding high-capacity but excessively complex representations, leading to an exponential increase in the number of model parameters; (ii) Annotation gap —to overcome the scarcity of real-world misinformation cascades, current pipelines repeatedly simulate diffusion from a fixed seed, eroding robustness on true, few-shot outbreaks; and (iii) Computational bottleneck —full-model retraining or recurrent cascade simulation is required for every new task, which disqualifies the solutions from real-time deployment. Inspired by the success of prompt learning in NLP and graph learning, we propose LAPS, a Lightweight privilege-Allocation Prompting framework for Source localization. LAPS first trims parameter explosion and data scarcity by pre-training a graph-level source region classifier on adaptive subgraphs with source-prior diffusion data. It then enables few-shot SL via a privilege-allocation prompt module that updates <1% of all the parameters, avoiding model retraining to facilitate efficiency. Extensive experiments on five real-world networks demonstrate the effectiveness and efficiency of our prompt-based framework on few-shot source localization task.

For complex networks such as the Web, the Network Dismantling (ND) problem, which asks for the minimum-cost removal of nodes that destroys the giant connected component in the network, is significant in system robustness and misinformation containment. In this paper, we propose a heuristic algorithm, IG+, which is based on reverse dismantling and incorporates novel optimizations. Besides, we design two dynamic algorithms, CCRT-ins and CCRT-rem, employing tree-like indexes to update dismantling results efficiently. Experiments show that our methods outperform state-of-the-art approaches in both effectiveness and efficiency, and can dismantle 10-million-scale networks at arbitrary granularity in a few minutes.

Large Language Models are rapidly emerging as web-native interfaces to social platforms. On the social web, users frequently have ambiguous and dynamic goals, making complex intent understanding—rather than single-turn execution—the cornerstone of effective human-LLM collaboration. Existing approaches attempt to clarify user intents through sequential or parallel questioning, yet they fall short of addressing the core challenge: modeling the logical dependencies among clarification questions. Inspired by the Cognitive Load Theory, we propose Prism, a novel framework for complex intent understanding that enables logically coherent and efficient intent clarification. Prism comprises four tailored modules: a complex intent decomposition module, which decomposes user intents into smaller, well-structured elements and identifies logical dependencies among them; a logical clarification generation module, which organizes clarification questions based on these dependencies to ensure coherent, low-friction interactions; an intent-aware reward module, which evaluates the quality of clarification trajectories via an intent-aware reward function and leverages Monte Carlo Sample to simulate user-LLM interactions for large-scale, high-quality training data generation; and a self-evolved intent tuning module, which iteratively refines the LLM's logical clarification capability through data-driven feedback and optimization. Prism consistently outperforms existing approaches across clarification interactions, intent execution, and cognitive load benchmarks. It achieves state-of-the-art logical consistency, reduces logical conflicts to 11.5%, increases user satisfaction by 14.4%, and decreases task completion time by 34.8%. All data and code are released.

Timely detection of anomalous interactions between different entities is crucial for the security and stability of Web-related systems, which are often modeled as streaming graphs. A major issue in existing anomaly detection methods is the effectiveness and the corresponding interpretability. In this paper, we introduce a novel evaluation metric, namely Interaction Willingness, to measure the propensity for entity interactions. Based on this metric, we design two efficient anomaly detection algorithms, AnoD and AnoC, tailored for real-time detection of two prevalent types of anomalous interaction behaviors (dense-type and counter-type), respectively. Notably, we adopt and extend the High-Order Count-Min Sketch for the implicit storage of streaming graphs, and ensure that both the space cost and the time cost of AnoD and AnoC for processing each new streaming edge remain constant and user-controllable, with estimation guarantees. Experimental evaluations on 6 real-world datasets demonstrate that the proposed evaluation metric and the associated algorithms achieve superior detection performance with clear interpretability for detecting anomalous interactions.

Temporal heterogeneous network representation learning is a pivotal approach for encapsulating the diversity of nodes and edges along with their temporal evolution into concise, low‐dimensional node representations. This technique has demonstrated remarkable efficacy in various network analysis and inference tasks. However, existing approaches study network evolution mainly by analyzing snapshots of temporal networks, while neglecting the intrinsic formation mechanisms of temporal heterogeneous networks. Few dynamic models delve into the intrinsic factors propelling network evolution. To fill this research gap, we introduce a novel learning framework for temporal heterogeneous network representation learning with dynamic influence modeling, denoted as THNRD. THNRD pioneers the application of the Hawkes process to temporal heterogeneous networks, utilizing the linking process of dynamic events to emulate the network’s formation mechanism, capturing the intrinsic dynamic progression of temporal heterogeneous networks. Subsequently, THNRD introduces a multilayer spatiotemporal aggregation model under a unified spatiotemporal framework, which is designed to harmoniously integrate the semantic and dynamic attributes of the networks. We also take node influence into consideration to further describe the temporal emergent phenomena. We verify the effectiveness of our proposed method via extensive experimental evaluations on real‐world datasets. The results consistently demonstrate that THNRD outperforms current state‐of‐the‐art methods.

Dynamic graph representation learning has emerged as a pivotal paradigm for modeling time-varying relational patterns in complex systems ranging from social networks to urban mobility. While existing methods achieve notable progress in temporal modeling, one critical challenge remains insufficiently addressed: identifying dual temporal evolution, i,e., instantaneous states and evolutionary trajectories. To address the challenge, we propose HMGNN, a novel dynamic graph learning framework that harmoniously integrates temporal dynamics modeling with stable structural representation learning, allowing adaptive pattern discovery while preserving feature consistency in evolving environments. Firstly, we propose a dynamic model that integrates a historical information perception module and a temporal aggregation module. The module converts the historical information into the model and adaptively measures the impact of the instantaneous and historical information effectively through the aggregation function. Secondly, we devise a dual-component model learning framework comprising contrastive learning and multi-granular temporal curriculum learning to holistically capture evolutionary dynamics. The contrastive learning component employs continuous-view contrastive alignment to preserve stable node feature across temporal evolution. Complementarily, our multi-granular temporal curriculum learning introduces masking mechanism to explicitly learn different time interval evolution patterns. Extensive experiments demonstrate the significant superiority of HMGNN against state-of-the-art dynamic graph learning methods in terms of all evaluation metrics.

Retrieval-augmented generation (RAG) has demonstrated strong potential in enhancing large language models (LLMs) for complex, real-world question answering. However, existing RAG frameworks remain inadequate for temporal scenarios, primarily due to their inability to jointly model temporal constraints in both retrieval and reasoning. On the retrieval side, traditional approaches focus on semantic similarity, often returning outdated or temporally misaligned evidence. On the generation side, these systems frequently produce factually incorrect or hallucinated answers when confronted with incomplete or temporally inconsistent information. Motivated by the observed limitations, we propose ChronoReflect+, a temporal logic-aware RAG framework that incorporates hybrid temporal-aware retrieval and progressive multi-step reflection. Our method iteratively refines both retrieval and reasoning, identifying and bridging information gaps as context accumulates. Extensive experiments demonstrate that ChronoReflect+ significantly outperforms state-of-the-art RAG baselines-improving end-to-end accuracy by 15.2%-particularly on questions involving implicit time expressions and multi-hop reasoning.

Information diffusion prediction, the forecasting of propagation paths, provides critical insights into information spread mechanisms, directly enabling applications like misinformation spread forecasting and detection for malicious account. Prior research primarily focused on combining user social graphs and information cascades for prediction, often overlooking the distinct role characteristics users exhibit during interactions. Classifying users into different roles enables the construction of a multi-layered social graph, facilitating the extraction of deeper user features. This paper introduces a model that leverages multi-dimensional interactions between user features. Specifically, to account for users' dynamic preferences, we construct sequential hypergraphs from information cascades using timestamps and utilize a hypergraph neural network to extract users' dynamic features. Furthermore, to capture users' static features, we build multi-layer social networks from the social graph based on users' roles. We employ graph convolutional networks to separately extract static features from each layer and subsequently fuse them using an attention mechanism. Superior performance of our framework is evidenced by experimental validation on real-world datasets against cutting-edge benchmarks.

In the contemporary era, characterized by an accelerated development in the domain of social networks, the phenomenon of fake news has attained unprecedented levels of prevalence, exerting substantial detrimental influence on society. Identification of the sources of such information in a timely manner is of paramount importance in order to prevent further damage. Existing source localization methods can be categorized into two distinct approaches: the first involves the deployment of observers followed by localization, while the second employs traditional community partitioning for source localization without considering community structure in observer deployment, resulting in suboptimal information acquisition. To address this issue, we propose Community Partition-Based Source Localization with Adaptive Observers Deployment (CSOL), which consists of three stages: In the first stage, community partitioning is achieved using contrastive learning with optimization and a feature extraction module that is highly correlated with partition. In the second stage, we are the first work to adaptively deploy observer based on community importance, integrating community partitioning with observer placement. In the third stage, an early source estimation strategy is employed to enhance efficiency and accuracy. Experimental results in real-world networks demonstrate that CSOL outperforms other SOTA methods in both accuracy and efficiency.

Framing effect is a well-known cognitive bias in which individuals' responses to the same underlying question vary depending on how the question is phrased. Recent studies suggest that large language models (LLMs) also exhibit framing effects, but existing work has primarily replicated psychological experiments using hand-crafted prompts, leaving their impact on practical downstream tasks underexplored. To fill in the gap, in this paper, we conduct a systematic empirical investigation into framing effects in LLMs across multiple real-world downstream tasks. We construct semantically equivalent prompts with positive and negative framings and evaluate a wide range of LLMs under these conditions. We uncover several behavioral regularities of framing effects in LLMs, among which the most notable one is a consistent response asymmetry: LLMs find answering ''yes'' harder than ''no''. That is, LLMs tend to issue affirmative responses (i.e., ''yes'') only when they are highly confident, while they incline to answer negatively (i.e., ''no'') under uncertainty. We interpret this asymmetry through the lens of Error Management Theory (EMT), which posits that rational agents adopt risk-averse strategies to minimize the more costly error. We empirically show that this behavior is partially attributable to a statistical imbalance in the frequency of positive versus negative framing cues in pretraining corpora. Furthermore, we demonstrate that the framing-induced bias in LLMs can inform prompt engineering and active in-context learning, i.e., using framing-sensitive samples as demonstrations can improve model performance. Finally, we offer a preliminary strategy to mitigate the framing effect, i.e., injecting debiasing instructions, which shows promise. In all, our work uncovers a fundamental behavioral bias in LLMs and offers practical guidance for their reliable deployment across downstream tasks.

The graph has been widely used to model the entities and the relationships among them in real-world applications. Subgraph matching is a core operation in graph data analysis. However, existing exact matching methods may incur high cost as their searched branches are always unpromising. In recent years, several approximate matching solutions have been proposed by exploiting neural networks. Nevertheless, the accuracy of the returned approximate results could be improved significantly. Motivated by these observations, we proposed OptMatch, an efficient and generic neural network-assisted subgraph matching approach, in this work. In particular, OptMatch proposes a novel subgraph partial embedding network and implements carefully designed search strategies to optimize search processes during the subgraph matching process. First, it can be used to accelerate existing exact matching methods. Moreover, it is also an approximate matching solution, which offers better accuracy compared to existing approximate solutions. We conduct exten-sive experiments on seven real-world data graphs to demonstrate the superiority of OptMatch in both exact and approximate subgraph matching.

Knowledge Graph Alignment (KGA) identifies elements in different knowledge graphs (KGs) that refer to the same real-world object. It is a key step towards improving the coverage of KGs, which in turn can better facilitate downstream tasks. However, there is currently no interactive tool to support KGA research, particularly for visualizing alignment results, hence limiting the understanding of the procedure and also the development of more advanced solutions. To fill in this gap, in this paper, we introduce IKGA, an interactive visualization tool for KGA, which visualizes the alignment process by integrating various algorithms of representation learning and alignment inference-two key steps in KGA. The system allows users to observe KGA results, compare existing algorithms, and apply to domain-specific KGs at hand.

Although various graph contrastive learning (GCL) techniques have been employed to generate augmented views and maximize their mutual information, current solutions only consider the pairwise relationships based on edges, neglecting the high-order information that can help generate more informative augmented views and make better contrast. To fill in this gap, we propose to leverage hyperedge to facilitate GCL, as it connects two or more nodes and can model high-order relationships among multiple nodes. More specifically, hyperedges are constructed based on the original graph. Then, we conduct node-level Page Rank based on hyperedges and hyperedge-level PageRank based on nodes to generate augmented views. As to the contrasting stage, different from existing GCL methods that simply treat the corresponding nodes of the anchor in different views as positives and overlook certain nodes strongly associated with the anchor, we build the positives and negatives based on hyperedges, where whether a node is a positive is determined by the number of hyperedges it coexists with the anchor. We compare our hyperedge GCL with state-of-the-art methods on downstream tasks, and the empirical results validate the superiority of our proposal. Further experiments on graph augmentation and graph contrastive loss also demonstrate the effectiveness of the proposed modules.

Highly Heterogeneous Entity Alignment (HHEA) represents a more realistic application scenario of Entity Alignment (EA). This challenging task aims to align equivalent entities between highly heterogeneous knowledge graphs (HHKGs) with significant differences in structure, scale, and overlap. In practice, obtaining labeled data for HHEA is often difficult, necessitating research into unsupervised HHEA. This involves addressing several challenges, including the difficulty in capturing structural and semantic associations between HHKGs, the absence of explicit HHEA paradigms, and the high time and computational costs. Unfortunately, there is no solution for unsupervised HHEA. To bridge this gap, this paper formally investigates the unsupervised HHEA problem and proposes an effective unsupervised HHEA solution, AdaCoAgentEA, which addresses the challenges of unsupervised HHEA from the perspective of multi-agent collaboration. Specifically, we design an adaptive collaboration framework with three functional areas powered by multi-agent LLMs and small models, effectively eliminating dependence on labeled data while capturing structural and semantic correlations between HHKGs. Furthermore, we design a suite of optimization tools for AdaCoAgentEA, including meta-alignment mechanisms and communication protocols, which facilitate effective associations between HHKGs and provide explicit HHEA paradigms while reducing time and computational costs. Extensive experiments demonstrate that our proposed framework achieves state-of-the-art performance in both unsupervised HHEA and classic EA tasks across five datasets, rivaling fully supervised models while maintaining high efficiency and scalability.

The enhance of accuracy in reasoning results of LLMs arouses the community's interests, wherein pioneering studies investigate post-hoc strategies to rectify potential mistakes. Despite extensive efforts, they are all stuck in a state of resource competition demand ing significant time and computing expenses. The cause of the situation lies in the failure of identifying the fundamental feature of the solutions in this line, coined as the self-denial of LLMs. In other words, LLMs should confidently determine the potential existence of mistakes and carefully execute the targeted correction. As the whole procedure conducts within LLMs, supporting and persuasive references are hard to acquire, while the absence of specific steps towards refining hidden mistakes persists even when errors are acknowledged. In response to the challenges, we present PSSD, which refers to and implements the human psyche structure such that three distinct and interconnected roles contribute to human reasoning. Specifically, PSSD leverages the recent multi-agent paradigm, and is further enhanced with three innovatively conceived roles: (1) the intuition-based id role that provides initial attempts based on benign LLMs; (2) the rule-driven superego role that summarizes rules to regulate the above attempts, and returns specific key points as guidance; and (3) the script-centric ego role that absorbs all procedural information to generate executable script for the final answer prediction. Extensive experiments demonstrate that the proposed design not only better enhance reasoning capabilities, but also seamlessly integrate with current models, leading to superior performance.

Abstract Knowledge tracing (KT) refers to the problem of predicting a learner’s future performance based on their past performance in education. Recently, attention-based sequence modeling methods achieve impressive predictive performance. However, existing solutions merely consider one single sequence modeling method, which might fail to capture the comprehensive state of knowledge across long sequences. In this paper, we propose D ual S equence M odeling for K nowledge T racing (DSMKT). DSMKT aims to enhance the modeling of a learner’s long-term profile by collaborating two sequence modeling methods, i.e., the masked self-attention mechanism and the gated recurrent unit. To further exploit the synergy between two sequence models, we adopt the idea of online knowledge distillation and adaptively combine two branches to form a stronger teacher model, which in turn provides predictions as extra supervision for better modeling ability. Extensive experiments on four real-world benchmark datasets show that DSMKT performs excellently in predicting future learner responses.

With the increasing complexity of urban transportation systems and the growing demand for dynamic, real-time responsiveness, Time-Dependent Minimum Travel Time Queries (TD-MTTQs) in time-dependent road networks have become a core challenge in intelligent transportation system research. To address the trade-offs between preprocessing complexity and query efficiency in existing index-based methods for large-scale road network applications, this paper proposes a 4-hop index method, TD-TNR-CH. The core methodology involves establishing local indexes from each node to its nearest critical nodes (named transit nodes) through strategic critical node selection, while simultaneously constructing query tables associated with candidate sets between these critical nodes. This architecture enables rapid computation of medium-to-long distance queries through efficient index lookups, while ensuring high responsiveness for short-distance queries via TCH-based local searches. Extensive experimental results on large-scale real-world road networks demonstrate that our method exhibits superior scalability, achieving query efficiency of up to 103 times that of the fastest existing algorithms. Furthermore, it shows exceptional stability across queries of varying distances. Additionally, leveraging its parallelized architecture, TD-TNR-CH requires only approximately 30 minutes of preprocessing time for large-scale networks, significantly outperforming comparable methods in terms of preprocessing efficiency.

Information diffusion prediction is a crucial task for comprehending the dissemination process of information. Although this problem has received significant attention recently, most of the state-of-the-arts primarily focus on the modelling of information cascades, while neglecting the implicit social relations between users in the social network and failing to adequately model the interrelations between the user social network and information cascades. To tackle the aforementioned issues, in this work, we propose aDual-StateHypergraphContrastiveLearning model (DSHCL). Specifically, we first propose to construct a social hypergraph based on the social network to capture the implicit social relations. Then, for capturing the cascade level correlations among users, we generate the dual-state (i.e., static and dynamic) user representations from the user social hypergraph and information cascades. Finally, we exploit contrastive learning to model the interplay between the social network and information cascades by discriminating the dual-state representations generated from them. We conduct an empirical assessment of DSHCL across four publicly available datasets, and the findings underscore the DSHCL's superiority and the efficacy of its components.

Graph neural networks (GNNs) are effective machine learning models for many graph-related applications. Despite their empirical success, many research efforts focus on the theoretical limitations of GNNs, i.e., the GNNs expressive power. Early works in this domain mainly focus on studying the graph isomorphism recognition ability of GNNs, and recent works try to leverage the properties such as subgraph counting and connectivity learning to characterize the expressive power of GNNs, which are more practical and closer to real-world. However, no survey papers and open-source repositories comprehensively summarize and discuss models in this important direction. To fill the gap, we conduct a first survey for models for enhancing expressive power under different forms of definition. Concretely, the models are reviewed based on three categories, i.e., Graph feature enhancement, Graph topology enhancement, and GNNs architecture enhancement.

Large language models (LLMs) have shown impressive success in various applications. However, they encounter issues in accurately understanding user intentions, thereby impeding the successful accomplishment of tasks. The pioneering study tackles intention understanding through iteratively interacting with users to enhance response quality; however, it fails to identify the notorious challenges associated with the task, where efficiency and accuracy are paramount for ensuring optimal user experience. To address these challenges, we introduce a new interactive table based intention understanding (ITIU) framework, which refers to and implements non-linear thinking in psychology such that details of intention are parallelly generated. Specifically, in the table interacting design phase, ITIU first brainstorms a more concrete intention table relevant to user instructions and subsequently incorporates a rule-based supervision mechanism to enhance the accuracy of its content. In the specialized model training phase, we obtain the procedural records generated by ITIU to develop a specialized upstream interactive intention understanding model. The specialized model replaces internal steps within the original interaction design for further efficiency improvement. Comprehensive experimental results demonstrate that ITIU significantly outperforms existing intention understanding methods, particularly in terms of interaction efficiency and intention understanding accuracy. Furthermore, whether integrated into the open-source LLaMA or powerful LLMs like GPT-4 and Claude-3, ITIU shows significant performance improvements. All the data and codes are released.

Temporal knowledge graph alignment (TKGA) discovers the equivalent elements among heterogeneous temporal knowledge graphs (TKGs), and thus can increase the coverage of a given TKG. However, existing TKGA datasets fail to mirror the real-life challenges, and the oversimplified scenarios may even impede the fair comparison and development of the alignment solutions. To address the aforementioned issues, in this work, we propose to benchmark challenges for temporal knowledge graph alignment by establishing a new dataset, i.e., BETA, which features multi-granular temporal information, more realistic quadruple distribution, and new challenging alignment scenarios. Furthermore, we also offer a simple yet effective solution, MGTEA, to address the aforementioned challenges, which effectively models the complex structural and multi-granular temporal features to facilitate the alignment. Extensive experiments reveal that BETA indeed better mirrors the real-life challenges, and there is still room for developing more advanced solutions to address these difficulties, despite of the superior performance achieved by MGTEA.

Large language models (LLMs) possess powerful contextual comprehension capabilities and have demonstrated remarkable success in conversational tasks. However, existing works that apply LLMs to conversational text-to-SQL task have the problem of repetitive mistakes, which results in the failure to bring out the performance of LLMs. In this paper, we propose a novel approach that provides guidance through learning from mistakes. Specifically, the guidance offered by our approach includes tailored suggestions, corrective feedback, and personalized strategies aimed at improving learning outcomes. Furthermore, we employ chain-of-thought (CoT) to utilize guidance that is not suitable directly as prompts. Our method rigorously analyzes actual errors and strategizes on how to utilize the derived guidance effectively. Experimental results demonstrate that our approach improves the state-of-the-art (SOTA) performance metrics, increasing QEX performance from 66.3% to 70.9% (an absolute improvement of 4.6%) and IEX performance from 37.4% to 45.1% (an absolute improvement of 7.7%) on the CoSQL dataset.

Multi-modal Entity Alignment (MMEA) aims to identify equivalent entities across different multi-modal knowledge graphs (MMKGs), facilitating their integration and enhancing coverage. However, current MMEA datasets have limitations, including low entity coverage, a single image per entity, high inter-image correlation, and images sourced from the same search engine, which do not reflect real-world challenges. The fair comparison and development of alignment solutions may be hindered by these oversimplified scenarios. To address this problem, in this work, we first construct M3, an MMEA benchmark equipped with multiple images from different search engines in real-world scenarios. Additionally, we design a simple and universal multi-image processing module (AMIA), which assigns varying attention weights to images associated with entities to effectively model visual information. Experimental results validate the difficulty of M3, as well as the effectiveness of AMIA. Despite the superior performance of AMIA, there is still room for developing more advanced solutions to address these difficulties. Our dataset is publicly released.

Knowledge Graph Question Generation (KGQG) is the task of generating natural language questions based on the given knowledge graph (KG). Although extensively explored in recent years, prevailing models predominantly depend on labelled data for training deep learning models or employ large parametric frameworks, e.g., Large Language Models (LLMs), which can incur significant deployment costs and pose practical implementation challenges. To address these issues, in this work, we put forward a zero-shot, multi-agent KGQG framework. This framework integrates the capabilities of LLMs with small models to facilitate cost-effective, high-quality question generation. In specific, we develop a professional editorial team architecture accompanied by two workflow optimization tools to reduce unproductive collaboration among LLMs-based agents and enhance the robustness of the system. Extensive experiments demonstrate that our proposed framework derives the new state-of-the-art performance on the zero-shot KGQG tasks, with relative gains of 20.24% and 13.57% on two KGQG datasets, respectively, which rival fully supervised state-of-the-art models.

Dynamic graphs are ubiquitous in our lives, yet they are also susceptible to the risks imposed by malicious activities. However, identifying anomalies in these dynamic graphs presents a challenging task due to the complex graph structures. Existing methods for dynamic anomaly detection primarily focus on learning representations for each timestamp and using sequence modeling techniques to capture and model the temporal information. Despite extensive research, dynamic anomaly detection still faces two key challenges. First, existing methods are limited in effectively using fine-grained temporal information. Second, they have limited generalization capabilities under unsupervised settings. Overcoming these challenges is crucial for advances in dynamic anomaly detection. In this paper, we propose a novel unsupervised anomaly detection method for dynamic graphs. Our approach leverages complex temporal information through fine-grained sampling and embedding modules. Additionally, we introduce an attention alignment strategy to minimize discrepancies in contextual attention between source and target nodes. Through a comprehensive evaluation, we demonstrate that our strategy effectively mitigates overfitting and improves generalization. Experiments on ten dynamic graph datasets validate the effectiveness of our proposed method in detecting anomalies.

Instant delivery has become a fundamental service in people's daily lives. Different from the traditional express service, the instant delivery has a strict shipping time constraint after being ordered. However, the labor shortage makes it challenging to realize efficient instant delivery. To tackle the problem, researchers have studied to introduce vehicles (i.e., taxis) or Unmanned Aerial Vehicles (UAVs or drones) into instant delivery tasks. Unfortunately, the delivery detour of taxis and the limited battery of UAVs make it hard to meet the rapidly increasing instant delivery demands. Under this circumstance, this paper proposes an air-ground cooperative instant delivery paradigm to maximize the delivery performance and meanwhile minimize the negative effects on the taxi passengers. Specifically, a data-driven delivery potential-demands-aware cooperative strategy is designed to improve the overall delivery performance of both UAVs and taxis as well as the taxi passengers' experience. The experimental results show that the proposed method improves the delivery number by 30.1% and 114.5% compared to the taxi-based and UAV-based instant delivery respectively, and shortens the delivery time by 35.7% compared to the taxi-based instant delivery.

Graphs are valuable data structures used to represent complex relationships between entities in a wide range of applications, such as social networks and chemical reactions. Subgraph counting problem is a well-known hard problem, as its core subroutine, the subgraph matching, is NP-complete. In this work, we propose an efficient and unified deep learning-based solution framework LearnSC, which solves the subgraph counting problem approximately. This framework offers two key advantages: (i) it is a generic solution that is orthogonal to the existing techniques of learning-based solutions; and (ii) it is equipped with a suite of optimizations to significantly improve the accuracy of the estimated results. Our experimental results on 7 datasets demonstrate that our proposal is highly accurate, robust, and scalable, making it an excellent solution for subgraph counting problem among all statistics-based and learning-based competitors.

Entity alignment (EA) identifies equivalent entities that locate in different knowledge graphs (KGs), and has attracted growing research interests over the last few years with the advancement of KG embedding techniques. Although a pile of embedding-based EA frameworks have been developed, they mainly focus on improving the performance of entity representation learning, while largely overlook the subsequent stage that matches$KGs$in entity embedding spaces. Nevertheless, accurately matching entities based on learned entity representations is crucial to the overall alignment performance, as it coordinates individual alignment decisions and determines the global matching result. Hence, it is essential to understand how well existing solutions for matching KGs in entity embedding spaces perform on present benchmarks, as well as their strengths and weaknesses. To this end, in this article we provide a comprehensive survey and evaluation of matching algorithms for KGs in entity embedding spaces in terms of effectiveness and efficiency on both classic settings and new scenarios that better mirror real-life challenges. Based on in-depth analysis, we provide useful insights into the design trade-offs and good paradigms of existing works, and suggest promising directions for future development.

Network dismantling is a process of identifying influential nodes that can decompose a network into disconnected sub-networks. This provides a novel approach to understanding and analyzing complex networks abstracted from the real world. State-of-the-art solutions for this task exploit graph encoders to capture the structural features of the network, which are then sent to the multi-layer perceptron for predicting the node importance. This process, however, fails to exploit the interactions among the graph representations learned from different views and neglects the neighboring information when evaluating node importance. In this work, we address these issues with a graph contrastive learning framework with multi-hop aggregation, resulting in the identification of influential nodes. Firstly, we construct role graphs to provide a holistic view of the original graphs. Secondly, graph representations are obtained in the individual views, and enhanced expressiveness is achieved through contrastive learning. Finally, based on the representations, the multi-hop neighbor information of the nodes is aggregated to rank the node importance, and thus aid in the identification of important nodes. We evaluate our proposal on real and synthetic networks, and the results show that our method outperforms the baseline with fewer nodes required to disassemble a network.

Computing the reachability between two vertices in a graph is a fundamental problem in graph data analysis. Most of the existing works assume that the edges in the graph have no labels, but in many real application scenarios, edges naturally come with edge-labels, and label constraints may be placed on the edges appearing on a valid path between two query vertices. Therefore, we study the label-constrained reachability (LCR) queries in this paper, where we are given a source vertex s , a target vertex t , a label set Δ, and the goal is to check whether there exists any path from s to t such that all the labels of edges on the path belong to Δ. A plethora of methods have been proposed in the literature to support the LCR queries. All these methods take the assumption that the graph is resident in the main memory of a machine. Nevertheless, the graphs in many real application scenarios are generally big and may not reside in memory. In these cases, existing methods suffer from serious scalability problem, i.e., result in huge I/O costs. Motivated by this, in this paper, we study the I/O efficient LCR query problem and aim to efficiently answer the LCR queries when the graph cannot fit in the main memory. To achieve this goal, we propose a reduction-based indexing approach. We introduce two elegant graph reduction operators which aims to reduce the size of the graph loaded in memory while preserving the LCR information among the remaining vertices. With these two operators, we devise an index named LCR-Index and propose algorithms to adaptively construct the index based on the available memory. Equipped with LCR-Index, we can answer a LCR query by only scanning the LCR-Index sequentially. Experiments demonstrate our query processing algorithm can handle graphs with billions of edges.

Although various graph contrastive learning (GCL) techniques have been employed to generate augmented views and maximize their mutual information, current solutions only consider the pairwise relationships based on edges, neglecting the high-order information that can help generate more informative augmented views and make better contrast. To fill in this gap, we propose to leverage hyperedge to facilitate GCL, as it connects two or more nodes and can model high-order relationships among multiple nodes. More specifically, hyperedges are constructed based on the original graph. Then, we conduct node-level PageRank based on hyperedges and hyperedge-level PageRank based on nodes to generate augmented views. As to the contrasting stage, different from existing GCL methods that simply treat the corresponding nodes of the anchor in different views as positives and overlook certain nodes strongly associated with the anchor, we build the positives and negatives based on hyperedges, where whether a node is a positive is determined by the number of hyperedges it coexists with the anchor. We compare our hyperedge GCL with state-of-the-art methods on downstream tasks, and the empirical results validate the superiority of our proposal. Further experiments on graph augmentation and graph contrastive loss also demonstrate the effectiveness of the proposed modules.

Heterogeneous information networks (HINs) are a key resource in many domain-specific retrieval and recommendation scenarios and in conversational environments. Current approaches to mining graph data often rely on abundant supervised information. However, supervised signals for graph learning tend to be scarce for a new task and only a handful of labeled nodes may be available. Meta-learning mechanisms are able to harness prior knowledge that can be adapted to new tasks. In this article, we design meta-learning framework for heterogeneous information networks ( META-HIN ), for few-shot learning problems on HINs. To the best of our knowledge, we are among the first to design a unified framework to realize the few-shot learning of HINs and facilitate different downstream tasks across different domains of graphs. Unlike most previous models, which focus on a single task on a single graph, META-HIN is able to deal with different tasks (node classification, link prediction, and anomaly detection are used as examples) across multiple graphs. Subgraphs are sampled to build the support and query set. Before being processed by the meta-learning module, subgraphs are modeled via a structure module to capture structural features. Then, a heterogeneous Graph Neural Network module is used as the base model to express the features of subgraphs. We also design a Generative Adversarial Network-based contrastive learning module that is able to exploit unsupervised information of the subgraphs. In our experiments, we fuse several datasets from multiple domains to verify META-HIN ’s broad applicability in a multiple-graph scenario. META-HIN consistently and significantly outperforms state-of-the-art alternatives on every task and across all datasets that we consider.

Multimodal Named Entity Recognition (MNER) aims to combine data from different modalities (e.g. text, images, videos, etc.) for recognition and classification of named entities, which is crucial for constructing Multimodal Knowledge Graphs (MMKGs). However, existing researches suffer from two prominant issues: over-reliance on textual features while neglecting visual features, and the lack of effective reduction of the feature space discrepancy of multimodal data. To overcome these challenges, this paper proposes a Multi-Grained Interaction Contrastive Learning framework for MNER task, namely MGICL. MGICL slices data into different granularities, i.e., sentence level/word token level for text, and image level/object level for image. By utilizing multimodal features with different granularities, the framework enables cross-contrast and narrows down the feature space discrepancy between modalities. Moreover, it facilitates the acquisition of valuable visual features by the text. Additionally, a visual gate control mechanism is introduced to dynamically select relevant visual information, thereby reducing the impact of visual noise. Experimental results demonstrate that the proposed MGICL framework satisfactorily tackles the challenges of MNER through enhancing information interaction of multimodal data and reducing the effect of noise, and hence, effectively improves the performance of MNER.

Automatic detection of fake news has received widespread attentions over recent years. A pile of efforts has been put forward to address the problem with high accuracy, while most of them lack convincing explanations, making it difficult to curb the continued spread of false news in real-life cases. Although some models leverage external resources to provide preliminary interpretability, such external signals are not always available. To fill in this gap, in this work, we put forward an interpretable fake news detection model IKA by making use of the historical evidence in the form of graphs. Specifically, we establish both positive and negative evidence graphs by collecting the signals from the historical news, i.e., training data. Then, given a piece of news to be detected, in addition to the common features used for detecting false news, we compare the news and evidence graphs to generate both the matching vector and the related graph evidence for explaining the prediction. We conduct extensive experiments on both Chinese and English datasets. The experiment results show that the detection accuracy of IKA exceeds the state-of-the-art approaches and IKA can provide useful explanations for the prediction results. Besides, IKA is general and can be applied on other models to improve their interpretability.

A frequency bursting pattern (FBP) in temporal graphs represents some interaction behavior that accumulates its frequency at the fastest rate. Mining FBPs is essential to early warning of emergencies. However, existing studies on frequency-based pattern mining in graphs do not consider the temporal information and bursting features of a subgraph pattern. As a result, they may not provide effective and efficient mining algorithms for FBP discovery. In this paper, we study the problem of discovering top-k FBPs in temporal graphs. We present a novel model, referred to as maximal (m, θ)-bursting pattern, to describe FBPs in a temporal graph, which is a subgraph with a size larger than m that accumulates its frequency at the fastest rate during a time interval of length no less than θ. A naive solution for top-k FBPs discovery is to use the best-first search algorithm, where the burstiness threshold changes as more patterns are mined. However, this method will result in huge search space since we need to check every possible time interval for a candidate pattern in the temporal graph. To tackle this problem, we devise an online top-k framework in which k candidate results are maintained from the initial timestamp to the end in the temporal graph. Under the new framework, we further conceive two optimization strategies by exploiting incremental subgraph matching and Evolutionary Game Theory to boost the performance. Extensive experiment results on five real temporal graphs show that our algorithm has higher efficiency, effectiveness and scalability.

Relation classification detects the semantic relation between two annotated entities from a piece of text, which is a useful tool for structurization of knowledge. Recently, federated learning has been introduced to train relation classification models in decentralized settings. Current methods strive for a strong server model by decoupling the model training at server from direct access to texts at clients while taking advantage of them. Nevertheless, they overlook the fact that clients have heterogeneous texts (i.e., texts with diversely skewed distribution of relations), which renders existing methods less practical. In this paper, we propose to investigate personalized federated relation classification, in which strong client models adapted to their own data are desired. To further meet the challenges brought by heterogeneous texts, we present a novel framework, namely pf-RC, with several optimized designs. It features a knowledge aggregation method that exploits a relation-wise weighting mechanism, and a feature augmentation method that leverages prototypes to adaptively enhance the representations of instances of long-tail relations. We experimentally validate the superiority of pf-RC against competing baselines in various settings, and the results suggest that the tailored techniques mitigate the challenges.

Graph self-supervised learning aims to mine useful information from unlabeled graph data, and has been successfully applied to pre-train graph representations. Many existing approaches use contrastive learning to learn powerful embeddings by learning contrastively from two augmented graph views. However, none of these graph contrastive methods fully exploits the diversity of different augmentations, and hence is prone to overfitting and limited generalization ability of learned representations. In this paper, we propose a novel Graph Self-supervised Learning method with Augmentation-aware Contrastive Learning. Our method is based on the finding that the pre-trained model after adding augmentation diversity can achieve better generalization ability. To make full use of the information from the diverse augmentation method, this paper constructs new augmentation-aware prediction task which complementary with the contrastive learning task. Similar to how pre-training requires fast adaptation to different downstream tasks, we simulate train-test adaptation on the constructed tasks for further enhancing the learning ability; this strategy can be deemed as a form of meta-learning. Experimental results show that our method outperforms previous methods and learns better representations for a variety of downstream tasks.

Abstract In recent years, Coronavirus disease 2019 (COVID-19) has become a global epidemic, and some efforts have been devoted to tracking and controlling its spread. Extracting structured knowledge from involved epidemic case reports can inform the surveillance system, which is important for controlling the spread of outbreaks. Therefore, in this paper, we focus on the task of Chinese epidemic event extraction (EE), which is defined as the detection of epidemic-related events and corresponding arguments in the texts of epidemic case reports. To facilitate the research of this task, we first define the epidemic-related event types and argument roles. Then we manually annotate a Chinese COVID-19 epidemic dataset, named COVID-19 Case Report (CCR). We also propose a novel hierarchical EE architecture, named multi-model fusion-based hierarchical event extraction (MFHEE). In MFHEE, we introduce a multi-model fusion strategy to tackle the issue of recognition bias of previous EE models. The experimental results on CCR dataset show that our method can effectively extract epidemic events and outperforms other baselines on this dataset. The comparative experiments results on other generic datasets show that our method has good scalability and portability. The ablation studies also show that the proposed hierarchical structure and multi-model fusion strategy contribute to the precision of our model.

Node importance estimation is a fundamental task in graph analysis, which can be applied to various downstream applications such as recommendation and resource allocation. However, existing studies merely work under a single view, which neglects the rich information hidden in other aspects of the graph. Hence, in this work, we propose a Multiview Contrastive Representation Learning (MCRL) model to obtain representations of nodes from multiple perspectives and then infer the node importance. Specifically, we are the first to apply the contrastive learning technique to the node importance analysis task, which enhances the expressiveness of graph representations and lays the foundation for importance estimation. Moreover, based on the improved representations, we generate the entity importance score by attentively aggregating the scores from two different views, i.e., node view and node‐edge interaction view. We conduct extensive experiments on real‐world datasets, and the experimental results show that MCRL outperforms existing methods on all evaluation metrics.

Entity alignment aims to identify equivalent entity pairs from different knowledge graphs (KGs). Recently, aligning temporal knowledge graphs (TKGs) that contain time information has aroused increasingly more interest, as the time dimension is widely used in real-life applications. The matching between TKGs requires seed entity pairs, which are lacking in practice. Hence, it is of great significance to study TKG alignment under scarce supervision. In this work, the authors formally formulate the problem of TKG alignment with limited labeled data and propose to solve it under the active learning framework. As the core of active learning is to devise query strategies to select the most informative instances to label, the authors propose to make full use of time information and put forward novel time-aware strategies to meet the requirement of weakly supervised temporal entity alignment. Extensive experimental results on multiple real-world datasets show that it is important to study TKG alignment with scarce supervision, and the proposed time-aware strategy is effective.

Abstract With the rapid development of information technologies, multi-source heterogeneous data has become an open problem, and the data is usually modeled as graphs since the graph structure is able to encode complex relationships among entities. However, in practical applications, such as network security analysis and public opinion analysis over social networks, the structure and the content of graph data are constantly evolving. Therefore, the ability to continuously monitor and detect interesting patterns on massive and dynamic graphs in real-time is crucial for many applications. Recently, a large group of excellent research works has also emerged. Nevertheless, these studies focus on different updates of graphs and apply different subgraph matching algorithms; thus, it is desirable to review these works comprehensively and give a thorough overview. In this paper, we systematically investigate the existing continuous subgraph matching techniques from the aspects of key techniques, representative algorithms, and performance evaluation. Furthermore, the typical applications and challenges of continuous subgraph matching over dynamic graphs, as well as the future development trends, are summarized and prospected.

In network representation learning we learn how to represent heterogeneous information networks in a low-dimensional space so as to facilitate effective search, classification, and prediction solutions. Previous network representation learning methods typically require sufficient task-specific labeled data to address domain-specific problems. The trained model usually cannot be transferred to out-of-domain datasets. We propose a self-supervised pre-training and fine-tuning framework, PF-HIN, to capture the features of a heterogeneous information network. Unlike traditional network representation learning models that have to train the entire model all over again for every downstream task and dataset, PF-HIN only needs to fine-tune the model and a small number of extra task-specific parameters, thus improving model efficiency and effectiveness. During pre-training, we first transform the neighborhood of a given node into a sequence. PF-HIN is pre-trained based on two self-supervised tasks, masked node modeling and adjacent node prediction. We adopt deep bi-directional transformer encoders to train the model, and leverage factorized embedding parameterization and cross-layer parameter sharing to reduce the parameters. In the fine-tuning stage, we choose four benchmark downstream tasks, i.e., link prediction, similarity search, node classification, and node clustering. PF-HIN outperforms state-of-the-art alternatives on each of these tasks, on four datasets.

Entity alignment (EA) identifies equivalent entities that locate in different knowledge graphs (KGs), and has attracted growing research interests over the last few years with the advancement of KG embedding techniques. Although a pile of embedding-based EA frameworks have been developed, they mainly focus on improving the performance ofentity representation learning, while largely overlook the subsequent stage thatmatches KGs in entity embedding spaces. Nevertheless, accurately matching entities based on learned entity representations is crucial to the overall alignment performance, as it coordinates individual alignment decisions and determines the global matching result. Hence, it is essential to understand how well existing solutions for matching KGs in entity embedding spaces perform on present benchmarks, as well as their strengths and weaknesses. To this end, in this article we provide a comprehensive survey and evaluation of matching algorithms for KGs in entity embedding spaces in terms of effectiveness and efficiency on both classic settings and new scenarios that better mirror real-life challenges. Based on in-depth analysis, we provide useful insights into the design trade-offs and good paradigms of existing works, and suggest promising directions for future development.

Few-shot Relational Triple Extraction (RTE) aims at detecting emerging relation types along with their entity pairs from unstructured text with the support of a few labeled samples. Prior arts use conditional random field or nearest-neighbor matching strategy to extract entities and use prototypical networks for extracting relations from sentences. Nevertheless, they fail to utilize the triple-level information to verify the plausibility of extracted relational triples, and ignore the proper transfer among the perspectives of entity, relation and triple. To fill in these gaps, in this work, we put forward a novel perspective transfer network (PTN) to address few-shot RTE. Specifically, PTN starts from the relation perspective by checking the existence of a given relation. Then, it transfers to the entity perspective to locate entity spans with relation-specific support sets. Next, it transfers to the triple perspective to validate the plausibility of extracted relational triples. Finally, it transfers back to the relation perspective to check the next relation, and repeats the aforementioned procedure. By transferring among the perspectives of relation, entity, and triple, PTN not only validates the extracted elements at both local and global levels, but also effectively handles more realistic and difficult few-shot RTE scenarios such as multiple triple extraction and nonexistence of triples. Extensive experimental results on existing dataset and new datasets demonstrate that our approach can significantly improve performance over the state-of-the-arts.

The Neo4j query language Cypher enables efficient querying for graphs and has become the most popular graph database language. Due to its complexities, semantic parsing (similar to Text-to-SQL) that translates natural language queries to Cypher becomes highly desirable. We propose the first Text-to-CQL dataset, SpCQL, which contains one Neo4j graph database, 10,000 manually annotated natural language queries and the matching Cypher queries (CQL). Correspondingly, based on this dataset, we define a new semantic parsing task Text-to-CQL. The Text-to-CQL task differs from the traditional Text-to-SQL task due to CQL being more flexible and versatile, especially for schema queries, which brings precedented challenges for the translation process. Although current SOTA Text-to-SQL models utilize SQL schema and contents, they do not scale up to large-scale graph databases. Besides, due to the absence of the primary and foreign keys in Cypher, which are essential for the multi-table Text-to-SQL task, existing Text-to-SQL models are rendered ineffective in this new task and have to be adapted to work. We propose three baselines based on the Seq2Seq framework and conduct experiments on the SpCQL dataset. The experiments yield undesirable results for existing models, hence pressing for subsequent research that considers the characteristics of SQL. The dataset is available at https://github.com/Guoaibo/Text-to-CQL.

The existence of anomalies is quite common, but they are hidden within the complex structure and high-dimensional node attributes of the attributed networks. As a latent hazard in existing systems, anomalies can be transformed into important instruction information once we detect them, e.g., computer network admins can react to the leakage of sensitive data if network traffic anomalies are identified. Extensive research in anomaly detection on attributed networks has proposed various techniques, which do improve the quality of data in networks, while they rarely cope with the few-shot anomaly detection problem. Few-shot anomaly detection task with only a few dozen labeled anomalies is more practical since anomalies are rare in number for real-world systems.

RDF stream processing (RSP) has become a vibrant area of research in the Semantic Web community, which guarantees interoperability and opens up important applications. There have been efforts to extend RDF data and SPARQL query for representing streaming information and continuous querying functionalities. However, existing solutions will incur significant low throughput due to the recomputation of the results from scratch as the window slides. In this paper, we propose a novel graph-based framework, referred as IncTreeRDF, towards continuous SPARQL query evaluation over RDF data streams. Under the framework, the RDF data streams are modeled as streaming graphs; the SPARQL queries are translated into graph patterns and evaluated via continuous sub-graph pattern-matching over streaming RDF graphs. IncTreeRDF employs a query-centric auxiliary data structure called TStore to store some intermediate results, which supports fast incremental maintenance. Based on TStore, we can not only avoid re-computing matches of the query but also prune invalid updates. Besides, we define matching-free update, in which subgraph matching calculation can be avoided under this scenario. Extensive experimental results show that IncTreeRDF significantly outperforms existing competitors.

Current question answering systems are insufficient when confronting real-life scenarios, as they can hardly be aware of whether a question is answerable given its context. Hence, there is a recent pursuit of unanswerability of a question and its attribution. Attribution of unanswerability requires the system to choose an appropriate cause for an unanswerable question. As the task is sophisticated for even human beings, it is expensive to acquire labeled data, which makes it a low-data regime problem. Moreover, the causes themselves are semantically abstract and complex, and the process of attribution is heavily question- and context-dependent. Thus, a capable model has to carefully appreciate the causes, and then, judiciously contrast the question with its context, in order to cast it into the right cause. In response to the challenges, we present PTAU, which refers to and implements a high-level human reading strategy such that one reads with anticipation. In specific, PTAU leverages the recent prompt-tuning paradigm, and is further enhanced with two innovatively conceived modules: 1) a cause-oriented template module that constructs continuous templates towards certain attributing class in high dimensional vector space; and 2) a semantics-aware label module that exploits label semantics through contrastive learning to render the classes distinguishable. Extensive experiments demonstrate that the proposed design better enlightens not only the attribution model, but also current question answering models, leading to superior performance.

Abstract Entity alignment (EA) aims to discover the equivalent entities in different knowledge graphs (KGs). It is a pivotal step for integrating KGs to increase knowledge coverage and quality. Recent years have witnessed a rapid increase of EA frameworks. However, state-of-the-art solutions tend to rely on labeled data for model training. Additionally, they work under the closed-domain setting and cannot deal with entities that are unmatchable. To address these deficiencies, we offer an unsupervised framework that performs entity alignment in the open world. Specifically, we first mine useful features from the side information of KGs. Then, we devise an unmatchable entity prediction module to filter out unmatchable entities and produce preliminary alignment results. These preliminary results are regarded as the pseudo-labeled data and forwarded to the progressive learning framework to generate structural representations, which are integrated with the side information to provide a more comprehensive view for alignment. Finally, the progressive learning framework gradually improves the quality of structural embeddings and enhances the alignment performance. Furthermore, noticing that the pseudo-labeled data are of various qualities, we introduce the concept of confidence to measure the probability of an entity pair of being true and develop a confidence-based unsupervised EA framework . Our solutions do not require labeled data and can effectively filter out unmatchable entities. Comprehensive experimental evaluations validate the superiority of our proposals .

Entity alignment (EA) finds equivalent entities that are located in different knowledge graphs (KGs), which is an essential step to enhance the quality of KGs, and hence of significance to downstream applications (e.g., question answering and recommendation). Recent years have witnessed a rapid increase of EA approaches, yet the relative performance of them remains unclear, partly due to the incomplete empirical evaluations, as well as the fact that comparisons were carried out under different settings (i.e., datasets, information used as input, etc.). In this paper, we fill in the gap by conducting a comprehensive evaluation and detailed analysis of state-of-the-art EA approaches. We first propose a general EA framework that encompasses all the current methods, and then group existing methods into three major categories. Next, we judiciously evaluate these solutions on a wide range of use cases, based on their effectiveness, efficiency and robustness. Finally, we construct a new EA dataset to mirror the real-life challenges of alignment, which were largely overlooked by existing literature. This study strives to provide a clear picture of the strengths and weaknesses of current EA approaches, so as to inspire quality follow-up research.

Content representation is a fundamental task in information retrieval. Representation learning is aimed at capturing features of an information object in a low-dimensional space. Most research on representation learning for heterogeneous information networks (HINs) focuses on static HINs. In practice, however, networks are dynamic and subject to constant change. In this article, we propose a novel and scalable representation learning model, M-DHIN , to explore the evolution of a dynamic HIN. We regard a dynamic HIN as a series of snapshots with different time stamps. We first use a static embedding method to learn the initial embeddings of a dynamic HIN at the first time stamp. We describe the features of the initial HIN via metagraphs, which retains more structural and semantic information than traditional path-oriented static models. We also adopt a complex embedding scheme to better distinguish between symmetric and asymmetric metagraphs. Unlike traditional models that process an entire network at each time stamp, we build a so-called change dataset that only includes nodes involved in a triadic closure or opening process, as well as newly added or deleted nodes. Then, we utilize the above metagraph-based mechanism to train on the change dataset. As a result of this setup, M-DHIN is scalable to large dynamic HINs since it only needs to model the entire HIN once while only the changed parts need to be processed over time. Existing dynamic embedding models only express the existing snapshots and cannot predict the future network structure. To equip M-DHIN with this ability, we introduce an LSTM-based deep autoencoder model that processes the evolution of the graph via an LSTM encoder and outputs the predicted graph. Finally, we evaluate the proposed model, M-DHIN , on real-life datasets and demonstrate that it significantly and consistently outperforms state-of-the-art models.

Entity alignment (EA) is the task of detecting equivalent entities from different knowledge graphs (KGs). Although this problem has been intensively studied during the last few years, the majority of the state-of-the-arts heavily rely on the labeled data, which are difficult to obtain in practice. Therefore, it calls for the study of EA with scarce supervision. To resolve this issue, we put forward a reinforced active entity alignment framework to select the entities to be manually labeled with the aim of enhancing alignment performance with minimal labeling efforts. Under this framework, we further devise an unsupervised contrastive loss to contrast different views of entity representations and augment the limited supervision signals by exploiting the vast unlabeled data. We empirically evaluate our proposal on eight popular KG pairs, and the results demonstrate that our proposed model and its components consistently boost the alignment performance under scarce supervision.

Retrieving event instances from texts is pivotal to various natural language processing applications (e.g., automatic question answering and dialogue systems), and the first task to perform is event detection. There are two related sub-tasks therein-trigger identification and type classification, and the former is considered to play a dominant role. Nevertheless, it is notoriously challenging to predict event triggers right. To handle the task, existing work has made tremendous progress by incorporating manual features, data augmentation and neural networks, etc. Due to the scarcity of data and insufficient representation of trigger words, however, they still fail to precisely determine the spans of triggers (coined as trigger span detection problem). To address the challenge, we propose to learn discriminative neural representations (DNR) from texts. Specifically, our DNR model tackles the trigger span detection problem by exploiting two novel techniques: 1) a contrastive learning strategy, which enlarges the discrepancy between representations of words inside and outside triggers; and 2) a Mixspan strategy, which better trains the model to differentiate words nearby triggers' span boundaries. Extensive experiments on benchmarks-ACE2005 and TAC2015-demonstrate the superiority of our DNR model, leading to state-of-the-art performance.

Entity alignment (EA) is the task of identifying the entities that refer to the same real-world object but are located in different knowledge graphs (KGs). For entities to be aligned, existing EA solutions treat them separately and generate alignment results as ranked lists of entities on the other side. Nevertheless, this decision-making paradigm fails to take into account the interdependence among entities. Although some recent efforts mitigate this issue by imposing the 1-to-1 constraint on the alignment process, they still cannot adequately model the underlying interdependence and the results tend to be sub-optimal. To fill in this gap, in this work, we delve into the dynamics of the decision-making process, and offer a reinforcement learning (RL)–based model to align entities collectively. Under the RL framework, we devise the coherence and exclusiveness constraints to characterize the interdependence and restrict collective alignment. Additionally, to generate more precise inputs to the RL framework, we employ representative features to capture different aspects of the similarity between entities in heterogeneous KGs, which are integrated by an adaptive feature fusion strategy. Our proposal is evaluated on both cross-lingual and mono-lingual EA benchmarks and compared against state-of-the-art solutions. The empirical results verify its effectiveness and superiority.

\emphSeasonal periodicity is a frequent phenomenon for social interactions in temporal networks. A key property of this behavior is that it exhibits periodicity for multiple particular periods in temporal networks. Mining such seasonal-periodic patterns is significant since it can indicate interesting relationships between the individuals involved in the interactions. Unfortunately, most previous studies for periodic pattern mining ignore the seasonal feature. This motivates us to explore mining seasonal-periodic subgraphs, and the investigation presents a novel model, called maximal σ-periodic $ømega$-seasonal k-subgraph. It represents a subgraph with size larger than k and that appears at least σ times periodically in at least $ømega$ particular periods on the temporal graph. Since seasonal-periodic patterns do not satisfy the anti-monotonic property, we propose a weak version of support measure with an anti-monotonic property to reduce the search space efficiently. Then, we present an effective mining algorithm to seek all maximal σ-periodic $ømega$-seasonal k-subgraphs. Experimental results on real-life datasets show the effectiveness and efficiency of our approach.

Entity alignment (EA) identifies entities that refer to the same real-world object but locate in different knowledge graphs (KGs), and has been harnessed for KG construction and integration. When generating EA results, current solutions treat entities independently and fail to take into account the interdependence between entities. To fill this gap, we propose a collective EA framework. We first employ three representative features, i.e., structural, semantic and string signals, which are adapted to capture different aspects of the similarity between entities in heterogeneous KGs. In order to make collective EA decisions, we formulate EA as the classical stable matching problem, which is further effectively solved by deferred acceptance algorithm. Our proposal is evaluated on both cross-lingual and mono-lingual EA benchmarks against state-of-the-art solutions, and the empirical results verify its effectiveness and superiority.

Entity alignment (EA) is to discover equivalent entities in knowledge graphs (KGs), which bridges heterogeneous sources of information and facilitates the integration of knowledge. Existing EA solutions mainly rely on structural information to align entities, typically through KG embedding. Nonetheless, in real-life KGs, only a few entities are densely connected to others, and the rest majority possess rather sparse neighborhood structure. We refer to the latter as long-tail entities, and observe that such phenomenon arguably limits the use of structural information for EA.

The top- N recommendation problem has been studied extensively. Item-based collaborative filtering recommendation algorithms show promising results for the problem. They predict a user’s preferences by estimating similarities between a target and user-rated items. Top- N recommendation remains a challenging task in scenarios where there is a lack of preference history for new items. Feature-based Similarity Models (FSMs) address this particular problem by extending item-based collaborative filtering by estimating similarity functions of item features. The quality of the estimated similarity function determines the accuracy of the recommendation. However, existing FSMs only estimate global similarity functions; i.e., they estimate using preference information across all users. Moreover, the estimated similarity functions are linear ; hence, they may fail to capture the complex structure underlying item features. In this article, we propose to improve FSMs by estimating local similarity functions, where each function is estimated for a subset of like-minded users. To capture global preference patterns, we extend the global similarity function from linear to nonlinear, based on the effectiveness of variational autoencoders. We propose a Bayesian generative model, called the Local Variational Feature-based Similarity Model, to encapsulate local and global similarity functions. We present a variational Expectation Minimization algorithm for efficient approximate inference. Extensive experiments on a large number of real-world datasets demonstrate the effectiveness of our proposed model.

Top- N recommendations have been studied extensively. Promising results have been achieved by recent item-based collaborative filtering (ICF) methods. The key to ICF lies in the estimation of item similarities. Observing the block-diagonal structure of the item similarities in practice, we propose a block-diagonal regularization (BDR) over item similarities for ICF. The intuitions behind BDR are as follows: (1) with BDR, item clustering is embedded into the learning of ICF methods; (2) BDR induces sparsity of item similarities, which guarantees recommendation efficiency; and (3) BDR captures in-block transitivity to overcome rating sparsity. By regularizing the item similarity matrix of item similarity models with BDR, we obtain a block-aware item similarity model. Our experimental evaluations on a large number of datasets show that the block-diagonal structure is crucial to the performance of top- N recommendation.

An evolving pattern graph is defined by an initial pattern graph and a graph update stream consisting of edge insertions and deletions. Identifying and monitoring evolving graph patterns in the data graph is important in various application domains such as Cyberthreats surveillance. This motivates us to explore matching patterns with evolvement, and the investigation presents a novel algorithm \incepg for continuously matching of evolving patterns. Specially, we propose a concise representation \Index of partial matching solutions, and its execution model allows fast incremental maintenance. We also conceive an effective model for estimating step-wise cost of pattern evaluation to drive the matching process. Extensive experiments verify the superiority of \incepg.

The mission of set reconciliation (also called set synchronization) is to identify those elements which appear only in exactly one of two given sets. In this paper, we extend the set reconciliation problem into three design rationales: (i) multiset support; (ii) near 100% reconciliation accuracy; (iii) communication-friendly and time-saving. Prior reconciliation methods fail to realize the three rationales simultaneously. To this end, we redesign Trie and Fenwick Tree (FT), to near-accurately represent and reconcile two types of multisets that we refer to as unsorted and sorted multisets, respectively. Comprehensive evaluations are conducted to quantify the performance of our proposals. The trace-driven evaluations demonstrate that Trie and FT achieve near-accurate multiset reconciliation, with 4.31 and 2.96 times faster than the CBF-based method, respectively.

To represent a complex network, paths are often employed for capturing relationships among node: random walks for (homogeneous) networks and metapaths for heterogeneous information networks (HINs). However, there is structural (and possibly semantic) information loss when using paths to represent the subgraph between two nodes, since a path is a linear structure and a subgraph often is not. Can we find a better alternative for network embeddings? We offer a novel mechanism to capture the features of HIN nodes via metagraphs, which retains more structural and semantic information than path-oriented models. Inspired by developments in knowledge graph embedding, we propose to construct HIN triplets using nodes and metagraphs between them. Metagraphs are generated by harnessing the GRAMI algorithm, which enumerates frequent subgraph patterns in a HIN. Subsequently, the Hadamard function is applied to encode relationships between nodes and metagraphs, and the probability whether a HIN triplet can be evaluated. Further, to better distinguish between symmetric and asymmetric cases of metagraphs, we introduce a complex embedding scheme that is able to precisely express fine-grained features of HIN nodes. We evaluate the proposed model, M-HIN, on real-life datasets and demonstrate that it significantly and consistently outperforms state-of-the-art models.

Uncertainty is intrinsic to a wide spectrum of real-life applications, which inevitably applies to graph data. Representative uncertain graphs are seen in bio-informatics, social networks, etc. This paper motivates the problem of frequent subgraph mining on single uncertain graphs, and investigates two different - probabilistic and expected - semantics in terms of support definitions. First, we present an enumeration-evaluation algorithm to solve the problem under probabilistic semantics. By showing the support computation under probabilistic semantics is #P-complete, we develop an approximation algorithm with accuracy guarantee for efficient problem-solving. To enhance the solution, we devise computation sharing techniques to achieve better mining performance. Afterwards, the algorithm is extended in a similar flavor to handle the problem under expected semantics, where checkpoint-based pruning and validation techniques are integrated. Experiment results on real-life datasets confirm the practical usability of the mining algorithms.

The mission of set reconciliation (also called set synchronization) is to identify those elements which appear only in exactly one of two given sets. In this paper, we extend the set reconciliation problem into three design rationales: (i) multiset support; (ii) near 100 percent reconciliation accuracy; and (iii) communication-friendly and time-saving. These three rationales, if realized, will lead to unprecedented benefits for the set reconciliation paradigm. Generally, prior reconciliation methods are mainly designed for simple sets and thus remain inapplicable for multisets. Methods based on probabilistic data structures, e.g., the Counting Bloom Filter (CBF), support efficient representation, and multiplicity queries. Based on these probabilistic data structures, approximate multiset reconciliation can be enabled. However, they often cannot achieve a statisfying accuracy, due to potential hash collisions. The reconciliations enabled by logs or lists incur high time-complexity and communication overhead. Therefore, existing reconciliation methods, fail to realize the three rationales simultaneously. To this end, we redesign Trie and Fenwick Tree (FT), to near-accurately represent and reconcile two types of multisets that we refer to as unsorted and sorted multisets, respectively. Moreover, to further reduce the communication overhead during the reconciliation process, we design a partial transmission strategy when exchanging two Tries or FTs. Comprehensive evaluations are conducted to quantify the performance of our proposals. The trace-driven evaluations demonstrate that Trie and FT achieve near-accurate multiset reconciliation, with 4.31 and 2.96 times faster than the CBF-based method, respectively. The simulations based on synthetic datasets further indicate that our proposals outperform the CBF-based method in terms of accuracy and communication overhead at most time.

Knowledge graphs are typical large-scale multi-relational structures, which comprise a large amount of fact triplets. Nonetheless, existing knowledge graphs are still sparse and far from being complete. To refine the knowledge graphs, representation learning is widely used to embed fact triplets into low-dimensional spaces. Many existing knowledge graph embedding models either focus on learning rich features from entities but fail to extract good features of relations, or employ sophisticated models that have rather high time and memory-space complexities. In this paper, we propose a novel knowledge graph embedding model, CombinE. It exploits entity features from two complementary perspectives via the plus and minus combinations. We start with the plus combination, where we use shared features of entity pairs participating in a relation to convey its relation features. To also allow differences of each pairs of entities participating in a relation, we also use the minus combination, where we concentrate on individual entity features, and regard relations as a channel to offset the divergence and preserve the prominence between head and tail entities. Compared with the state-of-the-art models, our experimental results demonstrate that CombinE outperforms existing ones and has low time and memory-space complexities.

In this paper, we leverage high-dimensional side information to enhance top-N recommendations. To reduce the impact of the curse of high dimensionality, we incorporate a dimensionality reduction method, Locality Preserving Projection (LPP), into the recommendation model. A joint learning model is proposed to achieve the task of dimensionality reduction and recommendation simultaneously and iteratively. Specifically, item similarities generated by the recommendation model are used as the weights of the adjacency graph for LPP while the projections are used to bias the learning of item similarity. Employing LPP for recommendation not only preserves locality but also improves item similarity. Our experimental results illustrate that the proposed method is superior over state-of-the-art methods.

The development of cloud storage and computing has facilitated the rise of various big data applications. As a representative high performance computing (HPC) workload, graph processing is becoming a part of cloud computing. However, scalable computing on large graphs is still dominated by HPC solutions, which require high performance all-to-all collective operations over torus (or mesh) networking. Implementing those torus-based algorithms on commodity clusters, e.g., cloud computing infrastructures, can result in great latency due to inefficient communication. Moreover, designing a highly scalable system for large social graphs, is far from being trivial, as intrinsic features of social graphs, e.g., degree skewness and lacking of locality, often profoundly limit the extent of parallelism.

Uncertainty is intrinsic to a wide spectrum of real-life applications, which inevitably applies to graph data. Representative uncertain graphs are seen in bio-informatics, social networks, etc. This paper motivates the problem of frequent subgraph mining on single uncertain graphs. We present an enumeration-evaluation algorithm to solve the problem. By showing support computation on an uncertain graph is #P-hard, we develop an approximation algorithm with accuracy guarantee for this purpose. To enhance the solution, we devise optimization techniques to achieve better mining performance. Experiment results on real-life data confirm the usability of the algorithm.

Provenance is a record that describes entities and processes involved in producing, delivering and influencing a resource. Provenance management and reuse can enable interesting applications for knowledge discovery and analytics. One crucial component of a provenance management system is the comparison between provenances. In the era of big data, provenance management systems are in need of a scalable algorithmic solution for efficient comparison. Existing solutions to the problem have large memory footprint and require overlong system response time. In this paper, we present a new solution to threshold-based provenance comparison. We model provenance directly as graph, and propose to measure provenance similarity using provenance edit distance. Following the depth-first search paradigm, we design an algorithm PEDSim based on an encoding technique specific to provenance graphs and quantifiable heuristics. Extensive experiments on real data demonstrate the superiority of our method to other alternatives.

A process trace describes the processes taken in a workflow to generate a particular result. Given many process traces, each with a large amount of very low level information, it is a challenge to make process traces meaningful to different users. It is more challenging to compare two complex process traces generated by heterogenous systems and have different levels of granularity. We present CTrace, a system that (1) lets users explore the conceptual abstraction of large process traces with different levels of granularity, and (2) provides semantic comparison among traces in which both the structural and the semantic similarity are considered. The above functions are underpinned by a novel notion of multi-granularity process trace and efficient multi-granularity similarity comparison algorithms.

Graphs are widely used to model complex data in many applications, such as bioinformatics, chemistry, social networks, pattern recognition, etc. A fundamental and critical query primitive is to efficiently search similar structures in a large collection of graphs. This paper studies the graph similarity queries with edit distance constraints. Existing solutions to the problem utilize fixed-size overlapping substructures to generate candidates, and thus become susceptible to large vertex degrees or large distance thresholds. In this paper, we present a partition-based approach to tackle the problem. By dividing data graphs into variable-size non-overlapping partitions, the edit distance constraint is converted to a graph containment constraint for candidate generation. We develop efficient query processing algorithms based on the new paradigm. A candidate pruning technique and an improved graph edit distance algorithm are also developed to further boost the performance. In addition, a cost-aware graph partitioning technique is devised to optimize the index. Extensive experiments demonstrate our approach significantly outperforms existing approaches.

Graphs are widely used to model complicated data semantics in many applications in bioinformatics, chemistry, social networks, pattern recognition, etc. A recent trend is to tolerate noise arising from various sources, such as erroneous data entry, and find similarity matches. In this paper, we study the graph similarity join problem that returns pairs of graphs such that their edit distances are no larger than a threshold. Inspired by the q-gram idea for string similarity problem, our solution extracts paths from graphs as features for indexing. We establish a lower bound of common features to generate candidates. An efficient algorithm is proposed to exploit both matching and mismatching features to improve the filtering and verification on candidates. We demonstrate the proposed algorithm significantly outperforms existing approaches with extensive experiments on publicly available datasets.