COSMOS: Connectivity-Oriented Submodular Maximization for Optimal Subgraph Retrieval
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.