Homophily-aware Structural and Semantic Compression for Graph Reasoning with LLM

Abstract

Large language models (LLMs) have demonstrated promising capabilities in text-attributed graph (TAG) understanding. Recent studies focus on verbalizing the graph structures via hand-crafted prompts for LLMs, typically incorporating the target node information and its neighborhood context. However, constrained by the context window, existing methods mainly resort to random sampling, which inevitably introduces noise and redundancy, thereby causing reasoning instability. A straightforward solution is graph compression, dropping some nodes/edges according to node-level importance criteria (e.g., degree, semantic similarity). Nevertheless, these methods overlook the global structure and semantic information from a local perspective, thereby leading to suboptimal performance. To solve this problem, we propose a Homophilyaware Structural and Semantic Compression (HS₂C) for LLMs, discovering the community-level graph homophily for accurate LLM reasoning. Specifically, we first conduct a structural entropy minimization guided global hierarchical partition of TAG, which detects groups of structurally strongly cou-pled nodes and organizes them into homophilic communities utilizing the coding tree. Secondly, based on predefined community types, we apply differentiated summary of background nodes within each community, selectively preserving semantically homophilic information aligned with the target nodes. Finally, we reconstruct the compressed graph for downstream LLM inference. Extensive experiments on 10 node-level benchmarks across LLMs of varying sizes and families show that, by feeding LLMs with structurally and semantically compressed inputs, HS₂C reduces graph storage cost and improves reasoning performance, validating its superiority and scalability. On OGBN-ArXiv, it achieves a 94.98% graph scale compression while improving accuracy by 3.06%–4.86%. Extensions to 7 diverse graphlevel benchmarks further consolidate HS₂C’s task generalizability.

Keywords

Large Language Model Reasoning / Structural Entropy / Homophily-aware Compression / Community Detection

Rights & permissions

Higher Education Press 2026

Just Accepted

This article has successfully passed peer review and final editorial review, and will soon enter typesetting, proofreading and other publishing processes. The currently displayed version is the accepted final manuscript. The officially published version will be updated with format, DOI and citation information upon launch. We recommend that you pay attention to subsequent journal notifications and preferentially cite the officially published version. Thank you for your support and cooperation.