Retrieval-Augmented Generation (RAG) enhances large language models (LLMs) with external knowledge retrieval, improving factual accuracy and knowledge coverage. However, existing RAG approaches face a fundamental trade-off when handling complex reasoning: while traditional iterative retrieval methods offer flexibility, their local perspective limits their ability to establish global knowledge connections. In contrast, structure-augmented RAG methods capture global relationships but incur significant construction costs. To fill in this gap, we propose MGranRAG, an innovative framework designed to integrate precise local retrieval with structured global reasoning. Our approach circumvents expensive semantic extraction by employing a lightweight contextual hierarchical graph, effectively combining the local adaptability of iterative retrieval with the global consistency of structured knowledge. The framework adopts a novel iterative optimization scheme: at the local level, the LLM identifies multi-granular contextual evidence, such as key sentences and phrases, within retrieved passages to refine retrieval. At the global level, these multi-granularity evidence nodes are then mapped and propagated within the structured hierarchical graph, enabling the diffusion of rich contextual information at different levels to introduce global semantic constraints and reorder retrieval results. This coordination between local and global iterative processes dynamically balances retrieval accuracy and contextual coherence. Experimental results on challenging multi-hop and open-domain question answering datasets show that our proposal achieves new state-of-the-art performance in both retrieval and answer accuracy.

Large Language Models (LLMs) have demonstrated remarkable performance across a wide range of natural language processing tasks. However, temporal reasoning, particularly under complex temporal constraints, remains a major challenge. To this end, existing approaches have explored symbolic methods, which encode temporal structure explicitly, and reflective mechanisms, which revise reasoning errors through multi-step inference. Nonetheless, symbolic approaches often underutilize the reasoning capabilities of LLMs, while reflective methods typically lack structured temporal representations, which can result in inconsistent or hallucinated reasoning. As a result, even when the correct temporal context is available, LLMs may still misinterpret or misapply time-related information, leading to incomplete or inaccurate answers. To address these limitations, in this work, we propose Neuro-Symbolic Temporal Reasoning (NeSTR), a novel framework that integrates structured symbolic representations with hybrid reflective reasoning to enhance the temporal sensitivity of LLM inference. NeSTR preserves explicit temporal relations through symbolic encoding, enforces logical consistency via verification, and corrects flawed inferences using abductive reflection. Extensive experiments on diverse temporal question answering benchmarks demonstrate that NeSTR achieves superior zero-shot performance and consistently improves temporal reasoning without any fine-tuning, showcasing the advantage of neuro-symbolic integration in enhancing temporal understanding in large language models.

The evolving worldly dynamics necessitate continuous revision and updating of knowledge within Large Language Models (LLMs), driving the development of Knowledge Editing (KE) techniques. Recently, a novel paradigm of Temporal Knowledge Editing (TKE) has been proposed, emphasizing that models deployed in dynamic environments should integrate new information while retaining historical knowledge. However, we observe that current definitions and methods for TKE are insufficient, as they do not effectively capture or adapt to the fine-grained temporal dynamics inherent in real-world knowledge evolution. In this paper, we introduce the notion of multi-granularity TKE, encompassing temporal knowledge across yearly, monthly, and daily granularities, and propose a corresponding dataset, named MTKE. We argue that comprehending and retaining knowledge across different temporal granularities is crucial for LLMs to accurately reflect real-world changes. The key challenge lies in integrating new temporal knowledge at various granularities while also preserving relevant historical knowledge, thus ensuring LLMs maintain a consistent and accurate understanding over time. To achieve this, we propose a Sparse Parameter-Injected Knowledge Editing method, dubbed SPIKE, which anchors both temporal knowledge and subject positions within the model. Experiments demonstrate that our method effectively preserves historical knowledge performance while accurately incorporating dynamic temporal knowledge across multi-granularity temporal scenarios.

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.

Instant delivery has become an essential service in daily life, requiring strict delivery timelines. However, traditional delivery methods that employ human couriers struggle to meet the soaring delivery demands due to labor shortages. While researchers have explored alternative solutions using ground vehicles (e.g., crowdsourced taxis) and Unmanned Aerial Vehicles (UAVs), their inherent limitations, such as constrained delivery detour for crowdsourced taxis and limited battery capacity of UAVs, greatly constrain their effectiveness. To address these challenges, this paper proposes a novel air-ground delivery paradigm that cooperatively integrates UAVs and crowdsourced taxis. First, UAV stations are strategically deployed based on delivery gaps between the delivery demands and taxis' delivery capacity, instead of delivery demands only; Then, a predictive UAV repositioning strategy is designed to bridge instantaneously dynamic delivery gaps. Thereafter, a transfer learning-based (TL-based) algorithm that mines the delivery knowledge of human couriers is designed to optimize the cooperative performance. This algorithm extracts behavioral insights from human couriers and transfers them to enhance the delivery capabilities of UAVs and taxis. Finally, parcel assignment is formulated as optimization problems aimed at maximizing total preferences of UAVs and taxis, and maximizing delivery number while minimizing cost, respectively. Evaluations on real-world datasets demonstrate that the proposed method delivers 27.4% more parcels, saves 19.2% delivery cost, and preserves 36.3% more of the travel experience of taxi passengers than the state-of-the-art (SOTA) air-ground cooperative approach for instant delivery.

The emergence of large language models (LLMs) has greatly advanced automated code generation, with multiagent systems comprising multiple LLMs gaining attention for their collaborative potential. However, most multi-agent systems still rely on large LLMs, leading to high computational costs and data privacy risks. Small LLMs provide a resource-efficient and privacy-preserving alternative; however, directly replacing them in conventional multi-agent frameworks leads to considerable performance degradation. This paper initially identifies two fundamental challenges in achieving effective collaboration among small LLMs: the difficulty in accurately interpreting complex role prompts and the fragility of inter-agent coordination. To overcome these, we propose MASDP, a multi-agent system for code generation withdynamic precaution tuning, inspired by the whistleblowing mechanism. MASDP introduces a fine-tuned Reminder agent that proactively anticipates potential errors, shifts the burden of code optimization from the Programmer to itself, and iteratively refines precautions based on execution feedback–thereby enhancing cooperation and reliability. Extensive experiments show that MASDP, built entirely on small LLMs, outperforms state-of-the-art baselines, including GPT-4, while substantially reducing computational overhead and safeguarding data privacy.

Multimedia event extraction aims to jointly extract event structural knowledge from multiple modalities, thus improving the comprehension and utilization of events in the growing multimedia content (e.g., multimedia news). A key challenge in multimedia event extraction is to establish cross-modal correlations during training without multimedia event annotations. Considering the complexity and cost of annotation across modalities, the multimedia event extraction task only provides parallel annotated data for evaluation. Previous works attempt to learn implicit correlations directly from unlabeled image-text pairs, but do not yield substantially better performance for event-centric tasks. To address this problem, we propose a cross-modal multi-task learning framework X-MTL to establish cross-modal correlations at the task level, which can simultaneously address four key tasks of multimedia event extraction: trigger detection, argument extraction, verb classification, and role classification. Specifically, to process inputs from different modalities and tasks, we utilize two separate modality-specific encoders and a modality-shared encoder to learn joint task representations, and introduce textual and visual prompt learning methods to enrich and unify task inputs. To resolve task conflict in cross-modal multi-task learning, we propose a pseudo label based knowledge distillation method, combined with dynamic weight adjustment method, which can effectively lift the performance to surpass the separately-trained models. On the Multimedia Event Extraction benchmark M2E2, experimental results show that X-MTL surpasses the current state-of-the-art (SOTA) methods by 4.1% for multimedia event mention and 8.2% for multimedia argument role.

Social platforms, while facilitating access to information, have also become saturated with a plethora of fake news, resulting in negative consequences. Automatic multimodal fake news detection is a worthwhile pursuit. Existing multimodal fake news datasets only provide binary labels of real or fake. However, real news is alike, while each fake news is fake in its own way. These datasets fail to reflect the mixed nature of various types of multimodal fake news. To bridge the gap, we construct an attributing multi-granularity multimodal fake news detection dataset AMG, revealing the inherent fake pattern. Furthermore, we propose a multi-granularity clue alignment model MGCA to achieve multimodal fake news detection and attribution. Experimental results demonstrate that AMG is a challenging dataset, and its attribution setting opens up new avenues for future research.

To understand a document with multiple events, event-event relation extraction (ERE) emerges as a crucial task, aiming to discern how natural events temporally or structurally associate with each other. To achieve this goal, our work addresses the problems of temporal event relation extraction (TRE) and subevent relation extraction (SRE). The latest methods for such problems have commonly built document-level event graphs for global reasoning across sentences. However, the edges between events are usually derived from external tools heuristically, which are not always reliable and may introduce noise. Moreover, they are not capable of preserving logical constraints among event relations, e.g., coreference constraint, symmetry constraint and conjunction constraint. These constraints guarantee coherence between different relation types, enabling the generation of a unified event evolution graph. In this work, we propose a novel method named LogicERE, which performs high-order event relation reasoning through modeling logic constraints. Specifically, different from conventional event graphs, we design a logic constraint induced graph (LCG) without any external tools. LCG involves event nodes where the interactions among them can model the coreference constraint, and event pairs nodes where the interactions among them can retain the symmetry constraint and conjunction constraint. Then we perform high-order reasoning on LCG with relational graph transformer to obtain enhanced event and event pair embeddings. Finally, we further incorporate logic constraint information via a joint logic learning module. Extensive experiments demonstrate the effectiveness of the proposed method with state-of-the-art performance on benchmark datasets.

Evidence-enhanced detectors present remarkable abilities in identifying malicious social text.However, the rise of large language models (LLMs) brings potential risks of evidence pollution to confuse detectors.This paper explores potential manipulation scenarios including basic pollution, and rephrasing or generating evidence by LLMs.To mitigate the negative impact, we propose three defense strategies from the data and model sides, including machine-generated text detection, a mixture of experts, and parameter updating.Extensive experiments on four malicious social text detection tasks with ten datasets illustrate that evidence pollution significantly compromises detectors, where the generating strategy causes up to a 14.4% performance drop.Meanwhile, the defense strategies could mitigate evidence pollution, but they faced limitations for practical employment.Further analysis illustrates that polluted evidence (i) is of high quality, evaluated by metrics and humans; (ii) would compromise the model calibration, increasing expected calibration error up to 21.6%; and (iii) could be integrated to amplify the negative impact, especially for encoder-based LMs, where the accuracy drops by 21.8%.

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.

Script Event Prediction (SEP) aims to forecast the next event in a sequence from a list of candidates. Traditional methods often use pre-trained language models to model event associations but struggle with semantic ambiguity and embedding bias. Semantic ambiguity arises from the multiple meanings of identical words and insufficient consideration of event arguments, while embedding bias results from assigning similar word embeddings to event pairs with similar lexical features, despite their different meanings. To address above issues, we propose a the Semantic and Sentiment Dual-enhanced Generative Model (SSD-GM). SSD-GM leverages two types of script event information to enhance the generative model. Specifically, it employs a GNN-based semantic structure aggregator to integrate the event-centric structure information, thereby mitigating the impact of semantic ambiguity. Furthermore, we find that local sentiment variability effectively reduces biases in event embeddings, while maintaining global sentiment consistency enhances predictive accuracy. As a result, SSD-GM adeptly captures both global and local sentiment of events through its sentiment information awareness mechanism. Extensive experiments on the Multi-Choice Narrative Cloze (MCNC) task demonstrate that our approach achieves better results than other state-of-the-art baselines.

Multi-modal entity alignment (MMEA) is a long-standing task that aims to discover identical entities between different multi-modal knowledge graphs (MMKGs). However, most of the existing MMEA datasets consider the multi-modal data as the attributes of textual entities, while neglecting the correlations among the multi-modal data and do not fit in the real-world scenarios well. In response, in this work, we establish a novel yet practical MMEA dataset, i.e. NMMEA, which models multi-modal data (e.g., images) equally as textual entities in the MMKG. Due to the introduction of multi-modal data, NMMEA poses new challenges to existing MMEA solutions, i.e., heterogeneous structural representation learning and cross-modal alignment inference. Hence, we put forward a simple yet effective solution, CrossEA, which can effectively learn the structural information of entities by considering both intra-modal and cross-modal relations, and further infer the similarity of different types of entity pairs. Extensive experiments validate the significance of NMMEA, where CrossEA can achieve superior performance in contrast to competitive methods on the proposed dataset.

Continual Few-shot Relation Extraction (CFRE) aims to continually learn new relations from limited labeled data while preserving knowledge about previously learned relations. Facing the inherent issue of catastrophic forgetting, previous approaches predominantly rely on memory replay strategies. However, they often overlook task interference in continual learning and the varying memory requirements for different relations. To address these shortcomings, we propose a novel framework, DPC-FT, which features: 1) a lightweight relation encoder for each task to mitigate negative knowledge transfer across tasks; 2) a dynamic prototype module to allocate less memory for easier relations and more memory for harder relations. Additionally, we introduce the None-Of-The-Above (NOTA) detection in CFRE and propose a threshold criterion to identify relations that have never been learned. Extensive experiments demonstrate the effectiveness and efficiency of our method in CFRE, making our approach more practical and comprehensive for real-world scenarios.

Social media platforms provide an ideal environment to spread misinformation, where social bots can accelerate the spread.This paper explores the interplay between social bots and misinformation on the Sina Weibo platform.We construct a large-scale dataset that includes annotations for both misinformation and social bots.From the misinformation perspective, the dataset is multimodal, containing 11,393 pieces of misinformation and 16,416 pieces of verified information.From the social bot perspective, this dataset contains 65,749 social bots and 345,886 genuine accounts, annotated using a weakly supervised annotator.Extensive experiments demonstrate the comprehensiveness of the dataset, the clear distinction between misinformation and real information, and the high quality of social bot annotations.Further analysis illustrates that: (i) social bots are deeply involved in information spread; (ii) misinformation with the same topics has similar content, providing the basis of echo chambers, and social bots would amplify this phenomenon; and (iii) social bots generate similar content aiming to manipulate public opinions.

Dynamic recommendation, focusing on modeling user preference from historical interactions and providing recommendations on current time, plays a key role in many personalized services. Recent works show that pre-trained dynamic graph neural networks (GNNs) can achieve excellent performance. However, existing methods by fine-tuning node representations at large scales demand significant computational resources. Additionally, the long-tail distribution of degrees leads to insufficient representations for nodes with sparse interactions, posing challenges for efficient fine-tuning. To address these issues, we introduce GraphSASA, a novel method for efficient fine-tuning in dynamic recommendation systems. GraphSASA employs test-time augmentation by leveraging the similarity of node representation distributions during hierarchical graph aggregation, which enhances node representations. Then it applies singular value decomposition, freezing the original vector matrix while focusing fine-tuning on the derived singular value matrices, which reduces the parameter burden of fine-tuning and improves the fine-tuning adaptability. Experimental results demonstrate that our method achieves state-of-the-art performance on three large-scale datasets.

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.

Efficient set representation and membership testing are important in high-speed network measurement. Fast insertions, space efficiency, fast query, and low false positive rate are the core requirements of traffic measurement, but existing solutions, such as hash tables and Bloom filters(BFs), cannot satisfy these requirements simultaneously. The state-of-the-art cuckoo filter and its variants(CFs) rely on the random eviction relocation strategy to resolve hash collisions, improving space utilization while reducing false positives and maintaining high query efficiency. However, CFs suffer a critical challenge in practical applications: insertion could trigger multiple evictions when all candidate buckets for an element are saturated, leading to insertion performance degradation, especially when space utilization exceeds 0.8. To solve the above problem, we propose a novel relocation strategy based on a random graph model, called the local minimum strategy. Our core idea is to use the implicit meaning of the number of evictions in each bucket as an indication to minimize the relocation of elements. We theoretically and experimentally prove that the eviction threshold for each bucket is$O(\log m)$, where$m$is the number of buckets. The threshold establishes the bounds for the probability of a successful insertion. The experimental results show that, the local minimum strategy significantly reduces the number of relocations by 67 %, as well as increasing the insertion throughput by more than 10 %.

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.

Relation classification plays a crucial role in detecting semantic relations between annotated entities within text data, serving as a fundamental tool for knowledge structurization. In recent years, federated learning has emerged as a promising approach for training relation classification models in decentralized settings. Existing methods have focused on developing a robust server model by decoupling model training at the server from direct access to client-side text data, while taking advantage of distributed data sources. However, a significant challenge arises from the heterogeneous nature of client texts, characterized by diverse and skewed distributions of relations, which has limited the practicality of current approaches. In response to this challenge, this study introduces the concept of personalized federated relation classification, aiming to tailor strong client models to adapt to their individual data distributions. To further address the issues stemming from heterogeneous texts, a novel framework, referred to as${\sf pFedRC}$, is proposed with several optimized designs. This framework incorporates a knowledge fusion method that leverages a relation-wise weighting mechanism, and a feature augmentation approach utilizing prototypes to adaptively enhance the representations of instances associated with long-tail relations. Although federated learning can safely ensure private data unexposed, it is important to recognize that, from an information theory standpoint, there still exists a possibility for a curious server to deduce private information by analyzing the shared knowledge uploaded by clients. To enhance the privacy guarantees of the personalized federated relation classification system, this work integrates client-level differential privacy mechanism into the federated training process. According to our theoretical analysis,${\sf pFedRC}$with client-level differential privacy can realize rigorous privacy guarantees. Experimental evaluations demonstrate the superiority of the proposed${\sf pFedRC}$framework over competing baselines in various settings, illustrating that the tailored techniques effectively mitigate the challenges posed by heterogeneous text data while preserving privacy guarantees. This research contributes to the advancement of learning privacy-preserving personalized relation classification models via taking advantages of data from multiple sources.

Fake news data, often sampled from the same communities, results in the veracity of news being highly correlated with certain textual and visual entities. This correlation leads fake news classification models to be prone to shortcut learning, quickly overfitting by capturing only shallow spurious correlations between labels and features. Consequently, neural networks trained on such data suffer from poor generalization and potential misclassification under distribution shifts. To address these critical challenges and enhance the robustness of fake news detection, in this paper, we propose a DIsentanglement-based Causality-awarE fake news detection method (DICE). DICE introduces a novel paradigm that moves beyond merely mitigating known correlations or relying on predefined bias categories. Specifically, DICE dynamically constructs multimodal news into a graph neural network, employing learnable node and edge mask disentanglers to effectively model and separate genuine causal relationships from spurious correlations between multimodal features and veracity labels. To reinforce this disentanglement process, we design a novel optimization framework that minimizes extrapolation risk and enforces representation orthogonality, leading to robust disentangled causal and biased representations. Extensive experiments demonstrate that DICE achieves superior performance on five large-scale fake news detection benchmarks. Additionally, our evaluation on a heavily biased fake news dataset demonstrates DICE’s strong generalization, suggesting its potential to inform a new paradigm in causal fake news detection. The code repo is available: https://github.com/mazihan880/DICE Code/.

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.

Relation classification (RC) aims to detect the semantic relation between two annotated entities in a piece of sentence, serving as an essential task in automatic knowledge graph construction. Due to the emergence of new relations, there is a recent trend to train RC models in continual settings. To overcome the catastrophic forgetting problem in continual learning, existing research is devoted in a two-stage training paradigm, fast adaptation to novel relations, and memory replay for all historical relations. These memory-replay-based methods explore different techniques to mitigate the forgetting problem of continual RC (CRC) models during the memory replay stage. However, we find that the representation space undergoes distortion due to the incoming of fresh relations in the fast adaptation phase. To address this issue, we propose using a knowledge distillation strategy and designing a margin loss, aiming to maintain the stability of the RC model during adaptation to new relations. In addition, in the second stage, with a limited number of typical memory instances available, we introduce a self-contrastive learning objective to facilitate learning a balanced decision boundary for RC. Through training in two stages, our objective is to acquire a stable representation space to encode instances for CRC. We experimentally demonstrate the superiority of our model over competing methods in various settings, and the results suggest that our tailored designs can achieve better performance in CRC.

Conventional federated learning (FL) assumes the homogeneity of models, necessitating clients to expose their model parameters to enhance the performance of the server model. However, this assumption cannot reflect real-world scenarios. Sharing models and parameters raises security concerns for users, and solely focusing on the server-side model neglects clients' personalization requirements, potentially impeding expected performance improvements of users. On the other hand, prioritizing personalization may compromise the generalization of the server model, thereby hindering extensive knowledge migration. To address these challenges, we put forth an important problem: How can FL ensure both generalization and personalization when clients' models are heterogeneous? In this work, we introduce FedTED, which leverages a twin-branch structure and data-free knowledge distillation (DFKD) to address the challenges posed by model heterogeneity and diverse objectives in FL. The employed techniques in FedTED yield significant improvements in both personalization and generalization, while effectively coordinating the updating process of clients' heterogeneous models and successfully reconstructing a satisfactory global model. Our empirical evaluation demonstrates that FedTED outperforms many representative algorithms, particularly in scenarios where clients' models are heterogeneous, achieving a remarkable 19.37% enhancement in generalization performance and up to 9.76% improvement in personalization performance.

Structural clustering is one of the most popular graph clustering methods, which has achieved great performance improvement by utilizing GPUs. Even though, the state-of-the-art GPU-based structural clustering algorithm, GPUSCAN, still suffers from efficiency issues since lots of extra costs are introduced for parallelization. Moreover, GPUSCAN assumes that the graph is resident in the GPU memory. However, the GPU memory capacity is limited currently while many real-world graphs are big and cannot fit in the GPU memory, which makes GPUSCAN unable to handle large graphs. Motivated by this, we present a new GPU-based structural clustering algorithm, GPUSCAN++, in this paper. To address the efficiency issue, we propose a new progressive clustering method tailored for GPUs that not only avoid high parallelization costs but also fully exploits the computing resources of GPUs. To address the GPU memory limitation issue, we propose a partition-based algorithm for structural clustering that can process large graphs with limited GPU memory. We conduct experiments on real graphs, and the experimental results demonstrate that our algorithm can achieve up to 168 times speedup compared with the state-of-the-art GPU-based algorithm when the graph can be resident in the GPU memory. Moreover, our algorithm is scalable to handle large graphs. As an example, our algorithm can finish the structural clustering on a graph with 1.8 billion edges using less than 2 GB GPU memory.

In this study, we address the challenge of enhancing temporal knowledge reasoning in Large Language Models (LLMs).LLMs often struggle with this task, leading to the generation of inaccurate or misleading responses.This issue mainly arises from their limited ability to handle evolving factual knowledge and complex temporal logic.To overcome these limitations, we propose Abstract Reasoning Induction (ARI) framework, which divides temporal reasoning into two distinct phases: Knowledgeagnostic and Knowledge-based.This framework offers factual knowledge support to LLMs while minimizing the incorporation of extraneous noisy data.Concurrently, informed by the principles of constructivism, ARI provides LLMs the capability to engage in proactive, self-directed learning from both correct and incorrect historical reasoning samples.By teaching LLMs to actively construct knowledge and methods, it can significantly boosting their temporal reasoning abilities.Our approach achieves significant improvements, with relative gains of 29.7% and 9.27% on two temporal QA datasets, underscoring its efficacy in advancing temporal reasoning in LLMs.The code can be found at https: //github.com/czy1999/ARI-QA.

The swift detection of multimedia fake news has emerged as a crucial task in combating malicious propaganda and safeguarding the security of the online environment.While existing methods have achieved commendable results in modeling entity-level inconsistency, addressing event-level inconsistency following the inherent subject-predicate logic of news and robustly learning news representations from poorquality news samples remain two challenges.In this paper, we propose an Event-dRiven fAke news Detection frAmewoRk (Event-Radar) based on multi-view learning, which integrates visual manipulation, textual emotion and multimodal inconsistency at event-level for fake news detection.Specifically, leveraging the capability of graph structures to capture interactions between events and parameters, Event-Radar captures event-level multimodal inconsistency by constructing an event graph that includes multimodal entity subject-predicate logic.Additionally, to mitigate the interference of poor-quality news, Event-Radar introduces a multi-view fusion mechanism, learning comprehensive and robust representations by computing the credibility of each view as a clue, thereby detecting fake news.Extensive experiments demonstrate that Event-Radar achieves outstanding performance on three large-scale fake news detection benchmarks.Our studies also confirm that Event-Radar exhibits strong robustness, providing a paradigm for detecting fake news from noisy news samples.

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.

Event Causality Identification (ECI) aims to detect causal relations between events in unstructured texts. This task is challenged by the lack of data and explicit causal clues. Some methods incorporate explicit knowledge from external knowledge graphs (KGs) into Pre-trained Language Models (PLMs) to tackle these issues, achieving certain accomplishments. However, they ignore that existing KGs usually contain trivial knowledge which may prejudice the performance. Moreover, they simply integrate the concept triplets, underutilizing the deep interaction between the text and external graph. In this paper, we propose an effective pipeline DFP, i.e., Distill, Fuse and Pre-train, to build a commonsense-aware pre-trained model which integrates reliable task-specific knowledge from commonsense graphs. This pipeline works as follows: (1) To leverage the reliable knowledge, commonsense graph distillation is proposed to distill commonsense graphs and obtain the meta-graph which contain credible task-oriented knowledge. (2) To model the deep interaction between the text and external graph, heterogeneous information fusion is proposed to fuse them through a commonsense-aware memory network. (3) Continual pre-training designs three continual pre-training tasks to further align and fuse the text and the commonsense meta-graph. Through extensive experiments on two benchmarks, we demonstrate the validity of our pipeline.

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.

Detecting fake news on social media has become a crucial task in combating online misinformation and countering malicious propaganda. Existing methods rely on semantic consistency across modalities to fuse features and determine news authenticity. However, cunning fake news publisher manipulate image to ensure a high level of semantic consistency between news post and image, making it more difficult to distinguish fake news. To this end, we propose MHFFD (Mixed High-Frequency Feature Detector), a novel fake news detection framework that utilizes token-level semantic consistency evaluation to identify key elements in news content and provide guidance for discovering image manipulation and learning better news representations. Extensive experiments demonstrate that MHFFD outperforms state-of-the-art methods on two widely used fake news detection datasets. Further research also validates the effectiveness of token-level semantic alignment and manipulation detection.

Short videos turn into an important channel for public sharing, as well as they've become a fertile ground for fake news. Fake news video detection is to judge the veracity of news based on its different modal information, such as video, audio, text, image and social context information. Current detection models tend to learn the multimodal dataset biases within spurious correlations between news modalities and veracity labels as shortcuts, rather than learning how to integrate the multimodal information behind them to reason, resulting in seriously degrading their detection and generalization capabilities. To address this issues, we propose a Multimodal Multi-View Debiasing (MMVD) framework, which makes the first attempt to mitigate various multimodal biases for fake news video detection. Inspired by people's misleading situations by multimodal short videos, we summarize three cognitive biases: static, dynamic and social biases. MMVD put forward a multi-view causal reasoning strategy to learn unbiased dependencies within the cognitive biases, thus enhancing the unbiased prediction of multimodal videos. The extensive experimental results show that the MMVD could improve the detection performance of multimodal fake news video. Studies also confirm that our MMVD can mitigate multiple biases on complex real-world scenarios and improve generalization ability of fake news video detection.

Electric vehicles (EVs), which have become one of the most important commuting vehicles in the world, heavily depend on the support of robust and efficient grids. Many researchers focus on optimizing the charging of EVs by the grid. However, they overlook the emergency charging when the large-scale grid fails. Inspired by the DC-2-DC technology, EVs can achieve vehicle-2-vehicle (V2V) energy sharing between each other, which inspires us to study leveraging the significant number of electric buses (e-buses) as effective and cost-efficient standby energy to charge low-power EVs when a large-scale grid outage occurs, whereas the feasibility, scheduling algorithm, and performance of e-bus-based V2V energy sharing remain open questions. With this in mind, we first reveal that it is feasible for e-buses to serve as effective standby power for low-power EVs, after careful analysis of real-world data. Then, we conduct a data-driven estimation of the energy consumption to determine the volume of the V2V shared energy for large-scale EVs. Accordingly, we formulate the e-bus-based V2V energy sharing problem, whose two objectives are to maximize the total number of the sufficiently charged EVs and to minimize the distance of these EVs moving to the e-bus for charging. The first objective is to charge more low-power EVs with the limited energy volume of the e-buses and the second objective is to reduce the range anxiety of the low-power EV drivers. Observing that existing algorithm is time-consuming or inefficient, which cannot be applied for the problem instance with a large number of e-buses and EVs, we design a low-complexity approximation algorithm for the problem. Both theoretical analysis and comprehensive data-driven evaluation demonstrate that the proposed algorithm, 1) significantly optimizes the optimization objectives by 23.6% and 15.8% on average, and up to 34.8% and 34.0% in extreme cases, compared with the existing approximation algorithm and 2) achieves over$100\times $execution speed improvement compared to the linear programming (LP)-based algorithm and evolutionary learning (EL) algorithms. The results demonstrate that the proposed algorithm achieves a better overall performance and makes it a promising solution for large-scale problem instances.

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.

Abstract Relation extraction has evolved from supervised relation extraction to zero-shot setting due to the continuous emergence of newly generated relations. Some pioneering works handle zero-shot relation extraction by reformulating it into proxy tasks, such as reading comprehension and textual entailment. Nonetheless, the divergence in proxy task formulations from relation extraction hinders the acquisition of informative semantic representations, leading to subpar performance. Therefore, in this paper, we take a data-driven view to handle zero-shot relation extraction under a three-step paradigm, including encoder training, relation clustering, and summarization. Specifically, to train a discriminative relational encoder, we propose a novel selective contrastive learning framework, namely, SCL, where selective importance scores are assigned to distinguish the importance of different negative contrastive instances. During testing, the prompt-based encoder is employed to map test samples into representation vectors, which are then clustered into several groups. Typical samples closest to the cluster centroid are selected for summarization to generate the predicted relation for all samples in the cluster. Moreover, we design a simple non-parametric threshold plugin to reduce false-positive errors in inference on unseen relation representations. Our experiments demonstrate that SCL outperforms the current state-of-the-art method by over 3% across all metrics.

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.

Extracting relational triplets aims at detecting entity pairs and their semantic relations. Compared with pipeline models, joint models can reduce error propagation and achieve better performance. However, all of these models require large amounts of training data, therefore performing poorly on many long-tail relations in reality with insufficient data. In this article, we propose a novel end-to-end model, called TGIN, for few-shot triplet extraction. The core of TGIN is a multilayer heterogeneous graph with two types of nodes (entity node and relation node) and three types of edges (relation-entity edge, entity-entity edge, and relation-relation edge). On the one hand, this heterogeneous graph with entities and relations as nodes can intuitively extract relational triplets jointly, thereby reducing error propagation. On the other hand, it enables the triplet information of limited labeled data to interact better, thus maximizing the advantage of this information for few-shot triplet extraction. Moreover, we devise a graph aggregation and update method that utilizes translation algebraic operations to mine semantic features while retaining structure features between entities and relations, thereby improving the robustness of the TGIN in a few-shot setting. After updating the node and edge features through layers, TGIN propagates the label information from a few labeled examples to unlabeled examples, thus inferring triplets from these unlabeled examples. Extensive experiments on three reconstructed datasets demonstrate that TGIN can significantly improve the accuracy of triplet extraction by 2.34%~10.74% compared with the state-of-the-art baselines. To the best of our knowledge, we are the first to introduce a heterogeneous graph for few-shot relational triplet extraction.

Over recent years, a number of knowledge graphs (KGs) have emerged. Nevertheless, a KG can never reach full completeness. A viable approach to increase the coverage of a KG is KG alignment (KGA). The majority of previous efforts merely focus on the matching between entities, while largely neglect relations. Besides, they heavily rely on labeled data, which are difficult to obtain in practice. To address these issues, in this work, we put forward a general framework to simultaneously align entities and relations under scarce supervision. Our proposal consists of two main components, relation-enhanced active instance selection (RAS), and cross-view contrastive learning (CCL). RAS aims to select the most valuable instances to be labeled with the guidance of relations, while CCL contrasts cross-view representations to augment scarce supervision signals. Our proposal is agnostic to the underlying entity and relation alignment models, and can be used to improve their performance under limited supervision. We conduct experiments on a wide range of popular KG pairs, and the results demonstrate that our proposed model and its components can consistently boost the alignment performance under scarce supervision.

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.

Recently, question answering over temporal knowledge graphs (i.e., TKGQA) has been introduced and investigated, in quest of reasoning about dynamic factual knowledge.To foster research on TKGQA, a few datasets have been curated (e.g., CRONQUESTIONS and Complex-CRONQUESTIONS), and various models have been proposed based on these datasets.Nevertheless, existing efforts overlook the fact that real-life applications of TKGQA also tend to be complex in temporal granularity, i.e., the questions may concern mixed temporal granularities (e.g., both day and month).To overcome the limitation, in this paper, we motivate the notion of multi-granularity temporal question answering over knowledge graphs and present a largescale dataset for multi-granularity TKGQA, namely MULTITQ.To the best of our knowledge, MULTITQ is among the first of its kind, and compared with existing datasets on TKGQA, MULTITQ features at least two desirable aspects-ample relevant facts and multiple temporal granularities.It is expected to better reflect real-world challenges, and serve as a test bed for TKGQA models.In addition, we propose a competing baseline MultiQA over MULTITQ, which is experimentally demonstrated to be effective in dealing with TKGQA.The data and code are released at https: //github.com/czy1999/MultiTQ.

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.

Abstract Named Entity Recognition (NER) has so far evolved from the traditional flat NER to overlapped and discontinuous NER. They have mostly been solved separately, with only several exceptions that concurrently tackle three tasks with a single model. The current best-performing method formalizes the unified NER as word-word relation classification, which barely focuses on mention content learning and fails to detect entity mentions comprising a single word. In this paper, we propose a two-stage span-based framework with templates, namely, T2-NER, to resolve the unified NER task. The first stage is to extract entity spans, where flat and overlapped entities can be recognized. The second stage is to classify over all entity span pairs, where discontinuous entities can be recognized. Finally, multi-task learning is used to jointly train two stages. To improve the efficiency of span-based model, we design grouped templates and typed templates for two stages to realize batch computations. We also apply an adjacent packing strategy and a latter packing strategy to model discriminative boundary information and learn better span (pair) representation. Moreover, we introduce the syntax information to enhance our span representation. We perform extensive experiments on eight benchmark datasets for flat, overlapped, and discontinuous NER, where our model beats all the current competitive baselines, obtaining the best performance of unified NER.

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 .

Knowledge graph question answering (KGQA) has recently received a lot of attention and many innovative methods have been proposed in this area, but few have been developed for temporal KGQA. Most of the existing temporal KGQA methods focus on semantic or temporal level matching and lack the ability to reason about time constraints. In this paper we propose a subgraph-based model for answering complex questions over temporal knowledge graphs (TKG), inspired by human cognition. Our method, called SubGraph Temporal Reasoning ( SubGTR ), consists of three main modules: implicit knowledge extraction, relevant facts search, and subgraph logic reasoning. First, the question is reformulated using background knowledge stored in the temporal knowledge graph to acquire explicit time constraints. Then, the TKG is being searched to identify relevant entities and obtain an initial scoring of them. Finally the time constraints are quantified and applied using temporal logic to reach to the final answer. To evaluate our model we experiment against temporal QA benchmarks. We observe that existing benchmarks contain many pseudo-temporal questions, and we propose Complex-CronQuestions , which a filtered version of CronQuestions and which can better demonstrate the model’s inference ability for complex temporal questions. Experimental results show that SubGTR achieves state-of-the-art performance on both CronQuestions and Complex-CronQuestions . Moreover, our model shows better performance in handling the entity cold-start problem compared to existing temporal KGQA methods.

Community Q&A forum is a special type of social media that provides a platform to raise questions and to answer them (both by forum participants), to facilitate online information sharing. Currently, community Q&A forums in professional domains have attracted a large number of users by offering professional knowledge. To support information access and save users’ efforts of raising new questions, they usually come with a question retrieval function, which retrieves similar existing questions (and their answers) to a user’s query. However, it can be difficult for community Q&A forums to cover all domains, especially those emerging lately with little labeled data but great discrepancy from existing domains. We refer to this scenario as cross-domain question retrieval. To handle the unique challenges of cross-domain question retrieval, we design a model based on adversarial training, namely, X-QR , which consists of two modules—a domain discriminator and a sentence matcher. The domain discriminator aims at aligning the source and target data distributions and unifying the feature space by domain-adversarial training. With the assistance of the domain discriminator, the sentence matcher is able to learn domain-consistent knowledge for the final matching prediction. To the best of our knowledge, this work is among the first to investigate the domain adaption problem of sentence matching for community Q&A forums question retrieval. The experiment results suggest that the proposed X-QR model offers better performance than conventional sentence matching methods in accomplishing cross-domain community Q&A tasks.

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.

Commonsense Question Answering is an important natural language processing (NLP) task that aims to predict the correct answer to a question through commonsense reasoning.Previous studies utilize pre-trained models on large-scale corpora such as BERT, or perform reasoning on knowledge graphs.However, these methods do not explicitly model the relations that connect entities, which are informational and can be used to enhance reasoning.To address this issue, we propose a relationaware reasoning method.Our method uses a relation-aware graph neural network to capture the rich contextual information from both entities and relations.Compared with methods that use fixed relation embeddings from pre-trained models, our model dynamically updates relations with contextual information from a multi-source subgraph, built from multiple external knowledge sources.The enhanced representations of relations are then fed to a bidirectional reasoning module.A bidirectional attention mechanism is applied between the question sequence and the paths that connect entities, which provides us with transparent interpretability.Experimental results on the CommonsenseQA dataset illustrate that our method results in significant improvements over the baselines while also providing clear reasoning paths.

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.

Text-to-SQL emerges to play an important role in interactive data analysis, which provides a friendly interface for converting natural language into relational database language (i.e., SQL). In order to translate a user’s query into an executable SQL statement, semantic parsing is essential to the transformation process. In particular, existing efforts provide some feasible solutions, and state-of-the-art models mainly adopt the sketch-based paradigm such that template values are to be filled. To this end, most methods extract values based on column representations. However, if the query contains multiple values that belong to different columns, these methods may fail to extract the values accurately. Moreover, it can be difficult to infer the right values when the query does not explicitly mention the corresponding column names. To bridge the gap, we propose a novel neural architecture, namely, ER-SQL for learning enhanced representations for Text-to-SQL. Based on pre-trained model BERT, ER-SQL uses column contents to better extract features of columns. Moreover, ER-SQL harnesses the column representations to latently reformulate the query. To verify the effectiveness of ER-SQL, comprehensive experiments demonstrate that ER-SQL achieves better results than existing models on the benchmark dataset WikiSQL, as well as on a representative Chinese dataset TableQA.

Knowledge graphs are typical large-scale multi-relational structures and useful for many artificial intelligence tasks. However, knowledge graphs often have missing facts, which limits the development of downstream tasks. To refine the knowledge graphs, knowledge graph embedding models have been developed. Knowledge graph embedding models aim to learn distributed representations for entities and relations and predict unknown triplets by scoring candidate triplets. Nevertheless, state-of-the-art works either aim to capture different relation patterns, or to model the multi-fold relations, and yet fail to consider these two aspects simultaneously. To fill this gap, in this paper, we propose a novel knowledge graph embedding model, MRotatE. It exploits triplet features from the perspective of relational and entity rotations, which can model and infer various relation patterns and handle with multi-fold relations at the same time. The experimental results demonstrate that MRotatE outperforms existing approaches and attains the 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.

Abstract With the proliferation of large-scale knowledge graphs (KGs), multi-hop knowledge graph reasoning has been a capstone that enables machines to be able to handle intelligent tasks, especially where some explicit reasoning path is appreciated for decision making. To train a KG reasoner, supervised learning-based methods suffer from false-negative issues, i.e., unseen paths during training are not to be found in prediction; in contrast, reinforcement learning (RL)-based methods do not require labeled paths, and can explore to cover many appropriate reasoning paths. In this connection, efforts have been dedicated to investigating several RL formulations for multi-hop KG reasoning. Particularly, current RL-based methods generate rewards at the very end of the reasoning process, due to which short paths of hops less than a given threshold are likely to be overlooked, and the overall performance is impaired. To address the problem, we propose , a revised RL formulation of multi-hop KG reasoning that is characterized by two novel designs—the stop signal and the worth-trying signal. The stop signal instructs the agent of RL to stay at the entity after finding the answer, preventing from hopping further even if the threshold is not reached; meanwhile, the worth-trying signal encourages the agent to try to learn some partial patterns from the paths that fail to lead to the answer. To validate the design of our model , comprehensive experiments are carried out on three benchmark knowledge graphs, and the results and analysis suggest the superiority of over state-of-the-art methods.

Abstract Nowadays, the scale of various graphs soars rapidly, which imposes a serious challenge to develop processing and analytic algorithms. Among them, graph pattern matching is the one of the most primitive tasks that find a wide spectrum of applications, the performance of which is yet often affected by the size and dynamicity of graphs. In order to handle large dynamic graphs, incremental pattern matching is proposed to avoid re-computing matches of patterns over the entire data graph, hence reducing the matching time and improving the overall execution performance. Due to the complexity of the problem, little work has been reported so far to solve the problem, and most of them only solve the graph pattern matching problem under the scenario of the data graph varying alone. In this article, we are devoted to a more complicated but very practical graph pattern matching problem, continuous matching of evolving patterns over dynamic graph data, and the investigation presents a novel algorithm for continuously pattern matching along with changes of both pattern graph and data graph. Specifically, we propose a concise representation of partial matching solutions, which can help to avoid re-computing matches of the pattern and speed up subsequent matching process. In order to enable the updates of data graph and pattern graph, we propose an incremental maintenance strategy, to efficiently maintain the intermediate results. Moreover, we conceive an effective model for estimating step-wise cost of pattern evaluation to drive the matching process. Extensive experiments verify the superiority of .

To tackle Named Entity Recognition (NER) tasks, supervised methods need to obtain sufficient cleanly annotated data, which is labor and time consuming. On the contrary, distantly supervised methods acquire automatically annotated data using dictionaries to alleviate this requirement. Unfortunately, dictionaries hinder the effectiveness of distantly supervised methods for NER due to its limited coverage, especially in specific domains. In this paper, we aim at the limitations of the dictionary usage and mention boundary detection. We generalize the distant supervision by extending the dictionary with headword based non-exact matching. We apply a function to better weight the matched entity mentions. We propose a span-level model, which classifies all the possible spans then infers the selected spans with a proposed dynamic programming algorithm. Experiments on all three benchmark datasets demonstrate that our method outperforms previous state-of-the-art distantly supervised methods.

\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.

Most existing work on event extraction (EE) either follows a pipelined manner or uses a joint structure but is pipelined in essence.As a result, these efforts fail to utilize information interactions among event triggers, event arguments, and argument roles, which causes information redundancy.In view of this, we propose to exploit the role information of the arguments in an event and devise a Hierarchical Policy Network (HPNet) to perform joint EE.The whole EE process is fulfilled through a two-level hierarchical structure consisting of two policy networks for event detection and argument detection.The deep information interactions among the subtasks are realized, and it is more natural to deal with multiple events issue.Extensive experiments on ACE2005 and TAC2015 demonstrate the superiority of HPNet, leading to state-of-the-art performance and is more powerful for sentences with multiple events.

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 linking, as one of the fundamental tasks in natural language processing, is crucial to knowledge fusion, knowledge base construction and update. Nevertheless, in contrast to the research on entity linking for English text, which undergoes continuous development, the Chinese counterpart is still in its infancy. One prominent issue lies in publicly available annotated datasets and evaluation benchmarks, which are lacking and deficient. In specific, existing Chinese corpora for entity linking were mainly constructed from noisy short texts, such as microblogs and news headings, where long texts were largely overlooked, which yet constitute a wider spectrum of real-life scenarios. To address the issue, in this work, we build CLEEK, a Chinese corpus of multi-domain long text for entity linking, in order to encourage advancement of entity linking in languages besides English. The corpus consists of 100 documents from diverse domains, and is publicly accessible. Moreover, we devise a measure to evaluate the difficulty of documents with respect to entity linking, which is then used to characterize the corpus. Additionally, the results of two baselines and seven state-of-the-art solutions on CLEEK are reported and compared. The empirical results validate the usefulness of CLEEK and the effectiveness of proposed difficulty measure.

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.

Distinguishing antonyms from synonyms is a key challenge for many NLP applications focused on the lexical-semantic relation extraction. Existing solutions relying on large-scale corpora yield low performance because of huge contextual overlap of antonym and synonym pairs. We propose a novel approach entirely based on pre-trained embeddings. We hypothesize that the pre-trained embeddings comprehend a blend of lexical-semantic information and we may distill the task-specific information using Distiller, a model proposed in this paper. Later, a classifier is trained based on features constructed from the distilled sub-spaces along with some word level features to distinguish antonyms from synonyms. Experimental results show that the proposed model outperforms existing research on antonym synonym distinction in both speed and performance.

Triplets extraction is an essential and pivotal step in automatic knowledge base construction, which captures structural information from unstructured text corpus. Conventional extraction models use a pipeline of named entity recognition and relation classification to extract entities and relations, respectively, which ignore the connection between the two tasks. Recently, several neural network-based models were proposed to tackle the problem, and achieved state-of-the-art performance. However, most of them are unable to extract multiple triplets from a single sentence, which are yet commonly seen in real-life scenarios. To close the gap, we propose in this paper a joint neural extraction model for multitriplets, namely, TME, which is capable of adaptively discovering multiple triplets simultaneously in a sentence via ranking with translation mechanism. In experiment, TME exhibits superior performance and achieves an improvement of 37.6% on F1 score over state-of-the-art competitors.

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.

Indoor semantic floorplan is important for a range of location based service (LBS) applications, attracting many research efforts in several years. In many cases, the out-of-date indoor semantic floorplans would gradually deteriorate and even break down the LBS performance. Thus, it is important to automatically update changed semantics of indoor floorplans caused by environmental variation. However, few research has been focused on the continuous semantic updating problem. This paper presents SISE as a mobile crowdsourcing system that uses a new abstraction for indoor general entities and their semantics, enGraph, to automatically update changed semantics of indoor floorplans using images and inertial data. We first propose efficient methods to generate enGraph. Thus, an image can be associated with an indoor semantic floorplan. Accordingly, we formulate the enGraph matching problem and then propose a quality-based maximum common subgraph matching algorithm so that entities extracted from an image can be corresponded to entities in the indoor semantic floorplan. Furthermore, we propose a quadrant comparison algorithm and a region shrink based localization algorithm to detect and localize changed entities. Thus, the new semantics can be labeled and out-of-date semantics can be removed. Extensive experiments have been conducted on real and synthetic data. Experimental results show that 80 percent of out-of-date semantics of indoor general entities can be updated by SISE.

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.

Natural language inference (NLI) is an important task in natural language processing (NLP), and recently, several deep neural network based models have been proposed for NLI. In this work, we first make two important observations regarding NLI: (1) the existence of extra/interfering semantics and its negative impact on the correctness of final inference; and (2) the unbalanced importance of local inference results and the need to combine all local results for aggregation. Motivated by these two observations, we have designed SDF-NN, a new NLI model with two novel components: (1) a Semantic Dropping Network (SDN) to automatically discard some of the interfering semantics; and (2) a Semantic Fusion Alignment (SFA) method to effectively fuse all local inference results. Our model has achieved 88.2% accuracy on the SNLI corpus, which is currently the best performing single model.

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.

Learning an ideal metric is crucial to many tasks in computer vision. Diverse feature representations may combat this problem from different aspects; as visual data objects described by multiple features can be decomposed into multiple views, thus often provide complementary information. In this paper, we propose a cross-view fusion algorithm that leads to a similarity metric for multiview data by systematically fusing multiple similarity measures. Unlike existing paradigms, we focus on learning distance measure by exploiting a graph structure of data samples, where an input similarity matrix can be improved through a propagation of graph random walk. In particular, we construct multiple graphs with each one corresponding to an individual view, and a cross-view fusion approach based on graph random walk is presented to derive an optimal distance measure by fusing multiple metrics. Our method is scalable to a large amount of data by enforcing sparsity through an anchor graph representation. To adaptively control the effects of different views, we dynamically learn view-specific coefficients, which are leveraged into graph random walk to balance multiviews. However, such a strategy may lead to an over-smooth similarity metric where affinities between dissimilar samples may be enlarged by excessively conducting cross-view fusion. Thus, we figure out a heuristic approach to controlling the iteration number in the fusion process in order to avoid over smoothness. Extensive experiments conducted on real-world data sets validate the effectiveness and efficiency of our approach.

Graph is an increasingly popular way to model complex data, and the size of single graphs is growing toward massive. Nonetheless, executing graph algorithms efficiently and at scale is surprisingly challenging. As a consequence, distributed programming frameworks have emerged to empower large graph processing. Pregel, as a popular computational model for processing billion-vertex graphs, has been employed to improve the scalability of many algorithms. In this paper, we investigate frequent subgraph mining on single large graphs using Pregel. We present the first distributed algorithm based on Pregel for single massive graphs. In addition, two optimizations are proposed to enhance the algorithm, reducing communication cost and distribution overhead. Extensive experiments conducted on real-life data confirm the effectiveness and efficiency of the proposed algorithm and techniques.

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.

Although there have been effective visualizations for simplex continuous or categorical variables, mixed data sets are still difficult to visualize, since no direct approaches are available for them. This paper presents a memory-saving and efficient data transformation technique for mixed data sets visualization,particularly details on describing the application of Correspondence Analysis to quantify categorical variables, and proposes a set of cardinality reduction strategies to reduce the numbers of variables and their values involved in computations. A series of empirical studies are carried out in a Star Coordinates-based environment to evaluate the visualization of mixed datasets. Finally it is concluded that the visualization gives a good graphical view of mixed data sets, with the data transformation technique being efficient in both time and memory.