Xianda Zheng, Huan Gao, Meng-Fen Chiang, Michael J. Witbrock, Kaiqi Zhao, Shangyang Li. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2026.

Xianda Zheng, Zijian Huang, Meng-Fen Chiang, Jiamou Liu, Yuan Fang, Michael J. Witbrock, Kaiqi Zhao. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2026.

Graph-based Retrieval-Augmented Generation (RAG) typically operates on binary Knowledge Graphs (KGs). However, decomposing complex facts into binary triples often leads to semantic fragmentation and longer reasoning paths, increasing the risk of retrieval drift and computational overhead. In contrast, n-ary hypergraphs preserve high-order relational integrity, enabling shallower and more semantically cohesive inference. To exploit this topology, we propose HyperRAG, a framework tailored for n-ary hypergraphs featuring two complementary retrieval paradigms: (i) HyperRetriever learns structural-semantic reasoning over n-ary facts to construct query-conditioned relational chains. It enables accurate factual tracking, adaptive high-order traversal, and interpretable multi-hop reasoning under context constraints. (ii) HyperMemory leverages the LLM's parametric memory to guide beam search, dynamically scoring n-ary facts and entities for query-aware path expansion. Extensive evaluations on WikiTopics (11 closed-domain datasets) and three open-domain QA benchmarks (HotpotQA, MuSiQue, and 2WikiMultiHopQA) validate HyperRAG's effectiveness. HyperRetriever achieves the highest answer accuracy overall, with average gains of 2.95% in MRR and 1.23% in Hits@10 over the strongest baseline. Qualitative analysis further shows that HyperRetriever bridges reasoning gaps through adaptive and interpretable n-ary chain construction, benefiting both open and closed-domain QA. Our codes are publicly available at https://github.com/Vincent-Lien/HyperRAG.git.

Analogical reasoning over Multimodal Knowledge Graphs (MMKGs) couples abductive relation induction with inductive tail completion. However, existing approaches rely on static fusion mechanisms that overlook the inherent asymmetry of modal relevance: while visual cues elucidate concrete entities, they are often noisy or irrelevant for abstract concepts, where text and graph structure provide decisive signals. Furthermore, prior methods fail to enforce consistency between induced relations and the modality patterns implied by the analogical context. To bridge this gap, we introduce RMAR, a Relation-aware Multimodal Analogical Reasoning framework with two complementary paths. An explicit path estimates modality fingerprints to score compatibility during relation induction and guide fusion during tail completion. An implicit path employs adaptive gating to blend structural, textual, and visual signals conditioned on the specific query context. To address the limitations of current benchmarks, which overrepresent concrete entities, we release MCNetAnalogy, and its companion graph, MCNetKG, a rigorous dataset enriched with abstract concepts and actions. RMAR is backbone-agnostic and works with multimodal knowledge graph embedding (MKGE) and transformer-based (MPT) pipelines. Extensive experiments demonstrate that RMAR delivers consistent gains across both embedding-based and transformer-based backbones, achieving a 29% relative improvement on MCNetAnalogy. Ablation studies confirm that RMAR's relation-aware modulation is particularly effective when modal evidence is weak or ambiguous.

Retrieval-Augmented Generation (RAG) systems combine external data retrieval with text generation and have become essential in applications requiring accurate and context-specific responses. However, their reliance on external data raises critical concerns about unauthorized collection and usage of personal information. To ensure compliance with data protection regulations like GDPR and detect improper use of data, we propose the Shadow RAG Auditing Data Provenance (S-RAG) framework. S-RAG enables users to determine whether their textual data has been utilized in RAG systems, even in black-box settings with no prior system knowledge. It is effective across open-source and closed-source RAG systems and resilient to defense strategies. Experiments demonstrate that S-RAG achieves an improvement in Accuracy by 19.9% (compared to the best baseline), while maintaining strong performance under adversarial defenses. Furthermore, we analyze how the auditor’s knowledge of the target system affects performance, offering practical insights for privacy-preserving AI systems. Our code is open-sourced online.

Rationale learning aims to automatically uncover the underlying explanations for NLP predictions. Previous studies in rationale learning mainly focus on the relevance of independent tokens with the predictions without considering their marginal contribution and the collective readability of extracted rationales. Through an empirical analysis, we argue that the sufficiency, informativeness, and readability of rationales are essential for explaining diverse end-task predictions. Accordingly, we propose Shapley-value Guided Rationale Editor (SHARE), an unsupervised approach that refines editable rationales while predicting task outcomes. SHARE extracts a sequence of tokens as a rationale, providing a collective explanation that is sufficient, informative, and readable. SHARE is highly adaptable for tasks like sentiment analysis, claim verification, and question answering, and can integrate seamlessly with various language models to provide explainability. Extensive experiments demonstrate its effectiveness in balancing sufficiency, informativeness, and readability across diverse applications. Our code and datasets are available at \url{https://github.com/zixinK/SHARE.}

Good rationale quality from large language models (LLMs) is essential for reliability and interpretability. However, the rationales produced by existing LLMs still have shortcomings, such as the lack of informativeness and faithfulness, which affect their practical applications. Reproduction experiments for enhancing rationale generation present significant challenges due to several factors. To study rationale quality in an agnostic manner, we develop a novel framework, Metric-guided Rationale Enhancement Framework (MREF), that re-weighs training instances based on multiple aspects of rationale quality. Specifically, MREF fine-tunes an LLM at hand on two benchmark multiple-choice question (MCQ) datasets, ECQA and MedMCQA, to generate answers and rationales. In the fine-tuning process, it exploits metrics from ROSCOE to evaluate the produced rationales across five dimensions: faithfulness, informativeness, coherence, repetition, and grammar, and uses these metric scores to guide re-weighting of training instances, hence encouraging the LLM to emphasize rationales of higher quality. Comprehensive experimental results demonstrate that this metric-guided re-weighting strategy significantly improves rationale quality across all evaluated ROSCOE metrics over the baselines without re-weighting, leading to more reliable and understandable outputs. MREF can be seamlessly integrated with existing LLMs for various NLP tasks beyond MCQs. Our code and datasets will be made available upon acceptance.

Human annotation is costly and impractical when it comes to scarcely labeled data. Besides, the presence of biased language in well-known benchmarks notably misleads predictive models to perform incredibly well, not because of the model capability but due to the hidden false correlations in the linguistic corpus. Motivated by this, we propose a neutralized Knowledge Transfer framework (NKT) to equip pre-trained language models with neutralized transferability. Specifically, we construct debiased multi-source corpora (CV and EL) for two exemplary knowledge transfer tasks: claim verification and evidence learning, respectively. To counteract biased language, we design a neutralization mechanism in the presence of label skewness. We also design a label adaptation mechanism in light of the mixed label systems in the multi-source corpora. In extensive experiments, the proposed NKT framework shows effective transferability contrarily to the disability of dominant baselines, particularly in the zero-shot cross-domain transfer setting.

Logical reasoning over Knowledge Graphs (KGs) for first-order logic (FOL) queries performs the query inference over KGs with logical operators, including conjunction, disjunction, existential quantification and negation, to approximate true answers in embedding spaces. However, most existing work imposes strong distributional assumptions (e.g., Beta distribution) to represent entities and queries into presumed distributional shape, which limits their expressive power. Moreover, query embeddings are challenging due to the relational complexities in multi-relational KGs (e.g., symmetry, anti-symmetry and transitivity). To bridge the gap, we propose a logical query reasoning framework, Line Embedding (LinE), for FOL queries. To relax the distributional assumptions, we introduce the logic space transformation layer, which is a generic neural function that converts embeddings from probabilistic distribution space to LinE embeddings space. To tackle multi-relational and logical complexities, we formulate neural relation-specific projections and individual logical operators to truthfully ground LinE query embeddings on logical regularities and KG factoids. Lastly, to verify the LinE embedding quality, we generate a FOL query dataset from WordNet, which richly encompasses hierarchical relations. Extensive experiments show superior reasoning sensitivity of LinE on three benchmarks against strong baselines, particularly for multi-hop relational queries and negation-related queries.

The task of reasoning over knowledge graph for factoid questions has received significant interest from the research community of natural language processing. Performing this task inevitably faces the issues of question complexity and reasoning efficiency. In this paper, we investigate modern reasoning approaches over knowledge graph to tackle complex factoid questions of diverse reasoning schemas with attractive speedup in computational efficiency. To this end, we propose two evidence retrieval strategies to generate concise and informative evidence graph of high semantic-relevance and factual coverage to the question. Then, we adopt DELFT, a graph neural networks based framework that takes the linguistic structure representation of a question and the evidence graph as input, to predict the answer by reasoning over the evidence graph. We evaluate the performance across several baselines in terms of effectiveness and efficiency on two real-world datasets, MOOCQA and MetaQA. The results show the superiority of message passing paradigm in delivering a robust reasoner with better answer quality and significantly improved computational efficiency.

We study the problem of representation learning for multiple types of entities in a co-ordered network where order relations exist among entities of the same type, and association relations exist across entities of different types. The key challenge in learning co-ordered network embedding is to preserve order relations among entities of the same type while leveraging on the general consistency in order relations between different entity types. In this paper, we propose an embedding model, CO2Vec, that addresses this challenge using mutually reinforced order dependencies. Specifically, CO2Vec explores in-direct order dependencies as supplementary evidence to enhance order representation learning across different types of entities. We conduct extensive experiments on both synthetic and real world datasets to demonstrate the robustness and effectiveness of CO2Vec against several strong baselines in link prediction task. We also design a comprehensive evaluation framework to study the performance of CO2Vec under different settings. In particular, our results show the robustness of CO2Vec with the removal of order relations from the original networks.

Learning the dependency relations among entities and the hierarchy formed by these relations by mapping entities into some order embedding space can effectively enable several important applications, including knowledge base completion and prerequisite relations prediction. Nevertheless, it is very challenging to learn a good order embedding due to the existence of partial ordering and missing relations in the observed data. Moreover, most application scenarios do not provide non-trivial negative dependency relation instances. We therefore propose a framework that performs dependency relation prediction by exploring both rich semantic and hierarchical structure information in the data. In particular, we propose several negative sampling strategies based on graph-specific centrality properties, which supplement the positive dependency relations with appropriate negative samples to effectively learn order embeddings. This research not only addresses the needs of automatically recovering missing dependency relations, but also unravels dependencies among entities using several real-world datasets, such as course dependency hierarchy involving course prerequisite relations, job hierarchy in organizations, and paper citation hierarchy. Extensive experiments are conducted on both synthetic and real-world datasets to demonstrate the prediction accuracy as well as to gain insights using the learned order embedding.

The knowledge of all occupied and unoccupied trips made by self-employed drivers are essential for optimized vehicle dispatch by ride-hailing services (e.g., Didi Dache, Uber, Lyft, Grab, etc.). However, the occupancy status of vehicles is not always known to the service operators due to adoption of multiple ride-hailing apps. In this paper, we propose a novel framework, Learning to INfer Trips (LINT), to infer occupancy of car trips by exploring characteristics of observed occupied trips. Two main research steps, stop point classification and structural segmentation, are included in LINT. In the stop point classification step, we represent a vehicle trajectory as a sequence of stop points, and assign stop points with pick-up, drop-off, and intermediate labels. The classification of vehicle trajectory stop points produces a stop point label sequence. For structural segmentation, we further propose several segmentation algorithms, including greedy segmentation (GS), efficient greedy segmentation (EGS), and dynamic programming-based segmentation (DP) to infer occupied trip from stop point label sequences. Our comprehensive experiments on real vehicle trajectories from self-employed drivers show that (1) the proposed stop point classifier predicts stop point labels with high accuracy, and (2) the proposed segmentation algorithm GS delivers the best accuracy performance with efficient running time.

As road transportation supports both economic and social activities in developed cities, it is important to maintain smooth traffic on all highways and local roads. Whenever possible, traffic congestions should be detected early and resolved quickly. While existing traffic monitoring dashboard systems have been put in place in many cities, these systems require high-cost vehicle speed monitoring instruments and detect traffic congestion as independent events. There is a lack of low-cost dashboards to inspect and analyze the lifecycle of traffic congestion which is critical in assessing the overall impact of congestion, determining the possible the source(s) of congestion and its evolution. In the absence of publicly available sophisticated road sensor data which measures on-road vehicle speed, we make use of publicly available vehicle trajectory data to detect the lifecycle of traffic congestion, also known as congestion cascade. We have developed Traffic-Cascade, a dashboard system to identify traffic congestion events, compile them into congestion cascades, and visualize them on a web dashboard. Traffic-Cascade unveils spatio-temporal insights of the congestion cascades.

The knowledge of traffic health status is essential to the general public and urban traffic management. To identify congestion cascades, an important phenomenon of traffic health, we propose a Bus Trajectory based Congestion Identification (BTCI) framework that explores the anomalous traffic health status and structure properties of congestion cascades using bus trajectory data. BTCI consists of two main steps, congested segment extraction and congestion cascades identification. The former constructs path speed models from historical vehicle transitions and design a non-parametric Kernel Density Estimation (KDE) function to derive a measure of congestion score. The latter aggregates congested segments (i.e., those with high congestion scores) into traffic congestion cascades by unifying both attribute coherence and spatio-temporal closeness of congested segments within a cascade. Extensive evaluations on 11.8 million bus trajectory data show that (1) BTCI can effectively identify congestion cascades, (2) the proposed congestion score is effective in extracting congested segments, (3) the proposed unified approach significantly outperforms alternative approaches in terms of extended precision, and (4) the identified congestion cascades are realistic, matching well with the traffic news and highly correlated with vehicle speed bands.

Large cities today are facing major challenges in planning and policy formulation to keep their growth sustainable. In this paper, we aim to gain useful insights about people living in a city by developing novel models to mine user lifestyles represented by the users' activity centers. Two models, namely ACMM and ACHMM, have been developed to learn the activity centers of each user using a large dataset of bus and subway train trips performed by passengers in Singapore. We show that ACHMM and ACMM yield similar accuracies in location prediction task. We also propose methods to automatically predict "home", "work" and "others" labels of locations visited by each user. Through validating with human-labeled home and work locations, we show that the accuracy of location label assignment is surprisingly very good even using an unsupervised method. With the location labels assigned, we further derive interesting insights of urban lifestyles at both individual and population levels.

Taxi bookings are events where requests for taxis are made by passengers either over voice calls or mobile apps. As the demand for taxis changes with space and time, it is important to model both the space and temporal dimensions in dynamic booking data. Several applications can benefit from a good taxi booking model. These include the prediction of number of bookings at certain location and time of the day, and the detection of anomalous booking events. In this paper, we propose a Grid-based Gaussian Mixture Model (GGMM) with spatio-temporal dimensions that groups booking data into a number of spatio-temporal clusters by observing the bookings occurring at different time of the day in each spatial grid cell. Using a large-scale real-world dataset consisting of over millions of booking records, we show that GGMM outperforms two strong baselines: a Gaussian Mixture Model (GMM) and the state-of-the-art spatio-temporal behavior model, Periodic Mobility Model (PMM), in estimating the spatio-temporal distribution of bookings at specific grid cells during specific time intervals. GGMM can achieve up to 95.8% (96.5%) reduction in perplexity compared against GMM (PMM). Further, we apply GGMM to detect anomalous bookings and successfully relate the anomalies with some known events, demonstrating GGMM's effectiveness in this task.

In mobile social networks, users can communicate with each other over different telecom operators. Thus, for telecom operators, how to attract new customers is a significant issue. The work of churn prediction is to determine whether a customer would leave soon. Differing from churn prediction, our work is to find those users who are likely to join target services from the competitors in the near future, where these users are called potential users. To infer potential users, we propose a framework including feature extraction, feature selection, and classifier learning to solve the problem. First, we construct a heterogeneous information network from the call detail records of users. Then, we extract the explicit features from potential users' interaction behavior in the heterogeneous information network. Moreover, because users are influenced by their community, we extract community-based implicit features of potential users. After feature extraction, we explore the Information Gain to select the effective features. We use the effective explicit and implicit features to learn potential user classifiers, and use the classifiers to determine the potential users. Finally, we conduct experiments on real datasets. The results of our experiments show that the features extracted by our proposed method can improve the accuracy of inferring potential users.

The advances in location-acquisition and smart phone technologies have led to a myriad of location-based social media. Therefore, analyzing the increasing amount of spatio-temporal data emerges as an important topic. Most studies on geographic data mining focus on exploring static mobility patterns. As the amount of incoming data streams increases, revealing the temporal aspect of user mobility patterns is worth investigating. This paper targets on mining user mobility patterns over time (referred to as mobility evolution) from streams of check-in records. Intuitively, at each time slot, a mobility pattern indicates spatial regions where users stay. Therefore, given a set of time slots, mobility evolution refers a sequence of spatial regions at each time slot. Note that nearby time slots may have similar spatial region distribution. Thus, given check-in datasets, we use the idea of data compression to obtain a sequence of representative segments, where each representative segment captures spatial region distribution at the corresponding time interval. To measure the quality of a segmentation result, we propose a representation cost function based on the Minimum Description Length (MDL) principle. In addition, because deriving the sequence of segments incurs expensive computational cost, we propose a family of greedy algorithms for segmentation to serve diverse requirements: efficient compression, informative compression, and cost-effective compression. Besides, to handle the massive amount of incoming check-in data, we also propose an incremental compression approach to incrementally update the mobility evolution. We conduct experiments on Foursquare datasets to demonstrate both the effectiveness and efficiency of our proposed algorithms.

With the growth of location-based services and social services, low- sampling-rate trajectories from check-in data or photos with geo- tag information becomes ubiquitous. In general, most detailed mov- ing information in low-sampling-rate trajectories are lost. Prior works have elaborated on distant-time location prediction in high- sampling-rate trajectories. However, existing prediction models are pattern-based and thus not applicable due to the sparsity of data points in low-sampling-rate trajectories. To address the sparsity in low-sampling-rate trajectories, we develop a Reachability-based prediction model on Time-constrained Mobility Graph (RTMG) to predict locations for distant-time queries. Specifically, we de- sign an adaptive temporal exploration approach to extract effective supporting trajectories that are temporally close to the query time. Based on the supporting trajectories, a Time-constrained mobility Graph (TG) is constructed to capture mobility information at the given query time. In light of TG, we further derive the reacha- bility probabilities among locations in TG. Thus, a location with maximum reachability from the current location among all possi- ble locations in supporting trajectories is considered as the predic- tion result. To efficiently process queries, we proposed the index structure Sorted Interval-Tree (SOIT) to organize location records. Extensive experiments with real data demonstrated the effective- ness and efficiency of RTMG. First, RTMG with adaptive tempo- ral exploration significantly outperforms the existing pattern-based prediction model HPM [2] over varying data sparsity in terms of higher accuracy and higher coverage. Also, the proposed index structure SOIT can efficiently speedup RTMG in large-scale trajec- tory dataset. In the future, we could extend RTMG by considering more factors (e.g., staying durations in locations, application us- ages in smart phones) to further improve the prediction accuracy.

With the growth of location-based services and social services, low-sampling-rate trajectories from check-in data or photos with geo-tag information becomes ubiquitous. In general, most detailed moving information in low-sampling-rate trajectories are lost. Prior works have elaborated on distant-time location prediction in high-sampling-rate trajectories. However, existing prediction models are pattern-based and thus not applicable due to the sparsity of data points in low-sampling-rate trajectories. For example, it becomes difficult to derive trajectory patterns, let alone utilizing trajectory patterns for distant-time location prediction. In this paper, given a query time, the current location and time, we aim to predict the location of an object at the query time. To address the sparsity in low-sampling-rate trajectories, we develop a Reachability-based prediction model on Time-constrained Mobility Graph (abbreviated as RTMG) to predict locations for distant-time queries. Specifically, we design an adaptive temporal exploration approach to extract effective supporting trajectories that are temporally close to the query time. These data points are then represented as a Time-constrained user mobility Graph (refers to as TG). In light of TG, we further derive the reachability probabilities among locations in TG. Thus, a location with maximum reachability from the current location among all possible locations in supporting trajectories is considered as the prediction result. To efficiently process queries, we proposed an index structure SOIT to organize location records for on-line query processing. We conduct extensive experiments on real low-sampling-rate datasets and demonstrate the effectiveness and efficiency of RTMG.

This paper presents a novel framework for dynamic circle recommendation for a query user at a given time point from historical communication logs. We identify the fundamental factors that govern interactions and aim to automatically form friend circles for scenarios, such as, who should I share the photo with in the early morning? Whose post should be listed on top of my Facebook Wall feed at night? We develop a temporal probabilistic model that not only captures temporal tendencies between the query user and each friend candidate but also blends frequency and recency into circle formation. Experimental results on Enron dataset and Call Detail Records prove the effectiveness of dynamic circle formation with proposed temporal probabilistic model.

A point of interest (POI) is a location that users can find something interesting. The POI information is typically made by the POI service provider and users can also add comments to a POI or add a new POI to enrich the POI contents. However, the information does not update frequently and some new points or time-sensitive events may not be marked in the POI service. Therefore, we construct a framework to extract the events from microblog to support an event-based POI service different from traditional POI service. With this kind of application, users can easily to get the events around them. In Web 2.0, microblog has become an important media spreading information in the web. With the help of mobile devices, microblogs can spread the information with greater spatiotemporal sensitivity. We take the spatial and temporal features of messages in microblogs to detect spatiotemporal events and use it to enrich POI service. This work aims at detecting spatiotemporal events in microblogs with an pair {location, time} from an handset device and feedbacks information to the users. To achieve this goal, we propose a framework with 4 phases: (1) profile construction; (2) feature extraction; (3) event summary detection; (4) ranking events. In this paper, we propose STF(standing for Spatio-Temporal Focus) value to evaluate the distinctiveness of a feature. Furthermore, we combine STF value with document overlap to expand an event cluster from an event seed. To extract the top-k possible event summaries, an efficient top-k soft clustering algorithm is proposed in this paper. In the experiments, we use real data set from Twitter to verify our proposed framework.

Recently, the growth of social bookmark sites (e.g., del.icio.us) brings a new way to organize and share Web pages. Specially, the social bookmarking sites contain many bookmarks of users, and users, who bookmark Web pages, would frequently browse these pages in the future. Therefore, we argue that social bookmarking sites provide the readers' perspective and are able to take the perspective into consideration in ranking Web pages. In this paper, we propose two ranking algorithms, ExpertVoteRank and RecommendationPageRank, to reveal the diverse information of Web pages in the social bookmarking sites. The concept of both algorithms are based on the views of readers: ExpertVoteRank takes advantage of experts of readers, while RecommendationPageRank applies recommendations from crowds to Web pages. Note that we collected about 90 millions data. Experiments show that both algorithms have effectiveness to rank Web pages according to the viewpoint of users.

With the growth of digital music, the development of music recommendation is helpful for users. The existing recommendation approaches are based on the users' preference on music. However, sometimes, recommending music according to the emotion is needed. In this paper, we propose a novel model for emotion-based music recommendation, which is based on the association discovery from film music. We investigated the music feature extraction and modified the affinity graph for association discovery between emotions and music features. Experimental result shows that the proposed approach achieves 85% accuracy in average.