@inproceedings{peng-etal-2026-cosmos,
    title = "{COSMOS}: Connectivity-Oriented Submodular Maximization for Optimal Subgraph Retrieval",
    author = "Peng, Boci  and
      Liu, Xiao  and
      Hu, Boren  and
      Zhu, Yun  and
      Fan, Xuanbo  and
      Yue, Yanwei  and
      Yang, Chunyu  and
      Zhang, Yan",
    editor = "Liakata, Maria  and
      Moreira, Viviane P.  and
      Zhang, Jiajun  and
      Jurgens, David",
    booktitle = "Proceedings of the 64th Annual Meeting of the {A}ssociation for {C}omputational {L}inguistics (Volume 1: Long Papers)",
    month = jul,
    year = "2026",
    address = "San Diego, California, United States",
    publisher = "Association for Computational Linguistics",
    url = "https://preview.aclanthology.org/ingest-acl/2026.acl-long.1662/",
    pages = "35904--35924",
    ISBN = "979-8-89176-390-6",
    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 **COSMOS** (**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 mathematically 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 $\text{M}^3\text{GQA}$ benchmarks demonstrate that COSMOS achieves state-of-the-art performance."
}