2026· Annual Meeting of the Association for Computational Linguistics· pp. 35904-35924· 0 citations· 60 references
Computer Science
TL;DR
This paper proposes COS-MOS, a unified framework that formalizes evidence retrieval as a constrained submodular maximization problem, and introduces Structure-Aware Contrastive Tuning to align semantic space with KG topology.
Abstract
Retrieving coherent evidence subgraphs is critical for Knowledge Base Question Answering (KBQA). Existing paradigms often treat facts independently, rely on biased heuristics, or employ myopic search, failing to optimize collective subgraph utility. In this paper, we propose COS-MOS ( C onnectivity-O riented S ubmodular M aximization for O ptimal S ubgraph Retrieval), a unified framework that formalizes evidence retrieval as a constrained submodular maximization problem. This formulation mathe-matically captures the trade-off between information relevance and structural complexity. To tractably solve this combinatorial challenge, COSMOS employs a decompose-and-conquer strategy, which first performs a seed-guided greedy expansion to maximize local semantic utility, followed by a topology-aware component aggregation to bridge disjoint evidence clusters via Maximum Spanning Tree aggregation. Guided by theoretical bounds, we introduce Structure-Aware Contrastive Tuning to align semantic space with KG topology. Experimental results on WebQSP, CWQ, and M 3 GQA benchmarks demonstrate that COS-MOS achieves state-of-the-art performance.
A Spectral-Aware Feature Alignment module to unify feature dimensionality and align cross-domain semantics in a community-aware manner and a Graph Diffusion Tokenized Transformer that constructs hybrid token sequences from local and global structural contexts for Transformer encoding, and applies diffusion-based refinement to mitigate distribution shifts on unseen graphs.
Mo Li, Zhaosong Zhao, Linlin Ding et al.· Annual International ACM SIG...· 0 citations
BoxDPpS performs box-level search with safe region pruning, eliminates redundant representations of the same iRM-set, improves early pruning through bounded warm-up, and compresses each fixed-M auxiliary network for exact parametric pseudoflow solving.
Jiadong Xie, Jiaming Yang, Kangfei Zhao et al.· 0 citations
CP-McSplitDAL is introduced, a cooperative parallel framework that extends McSplit-DAL with portfolio-style multi-heuristic search on shared-memory machines and achieves lower regret in time to optimality, improves solution quality under time limits, and better exploits multi-core hardware than non-cooperative or purely sequential variants.
Lorenzo Cardone, Stefano Quer· International Conference on...· 0 citations
TopoBudget couples exact multiscale connectivity with budgeted, reusable community preservation, and proves exact preservation of the component partition at every threshold, and that the conditioned objective is monotone and submodular, so greedy attains a (1-1/e) guarantee for the fixed-backbone residual problem.
Organizing long-term memory for multimodal agents remains challenging because existing methods either suffer from expensive question-agnostic offline summaries or naive embedding similarity matching that introduces incomplete and redundant context. To address these issues, we propose GraphMemix, a combinatorial-optimization graph memory framework that models memory organization as query-aware evidence-forest construction. Specifically, our method consists of three key components:(1) candidate graph construction, which expands multi-view seed memories through schema and semantic relations to acquire query-aware original context; (2) evidence utility and activation costs, which decouples direct memory support from anchor-conditioned relation verification to suppress redundant or conflicting information; and (3) forest optimization, which jointly selects a forest-format memory context under a maximum evidence budget and its reliable relational structure. By organizing memory into a query-relevant subgraph, the method avoids substantial lifecycle cost and recovers low-similarity complementary evidence. Experimental results across four long-term multimodal memory benchmarks demonstrate significant improvements with different foundation models and establish a new Pareto frontier between accuracy and lifecycle cost.
Secondary private equity transactions require rapid synthesis of fragmented, unstructured financial disclosures, where critical metrics and their entity anchors are distributed across disjoint documents with limited lexical overlap. We present Aethel, a reproducible framework that combines bipartite Personalized PageRank graph retrieval with a coreference-aware Bipartite Coreference Teleportation layer and an orchestrated specialist-agent architecture. Aethel models corpora as entity-passage graphs and propagates relevance through explicit relational paths to support multi-hop financial diligence. We evaluate the retrieval layer on 200-question samples from the MuSiQue and 2WikiMultiHopQA validation sets, comparing sparse lexical, dense bi-encoder, vanilla graph, and coreference-aware graph retrieval. Aethel achieves HR@5 of 100.0% on 2WikiMultiHopQA and 88.5% on MuSiQue, improving coverage over vanilla graph retrieval while trading off top-rank precision. We also evaluate retrieval over a 4,123-chunk corpus of financial disclosures and find that graph retrieval outperforms dense retrieval on multi-hop recall but does not surpass a strong BM25 baseline at open-corpus scale. The results show that graph-based retrieval offers interpretable multi-hop evidence paths and degrades more gracefully than dense retrieval as corpus size grows, while also demonstrating that its advantage depends strongly on corpus scale and entity-index quality. Code and evaluation artifacts are released for reproducibility.
Krish Sapru· arXiv.org· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
