Improving LLM Reasoning with Homophily-aware Structural and Semantic Text-Attributed Graph Compression

• URL: http://arxiv.org/abs/2601.08187v2
• Date: Sat, 17 Jan 2026 13:01:51 GMT
• Title: Improving LLM Reasoning with Homophily-aware Structural and Semantic Text-Attributed Graph Compression
• Authors: Zijun Di, Bin Lu, Huquan Kang, Luoyi Fu, Jiaxin Ding, Xiaoying Gan, Lei Zhou, Xinbing Wang, Chenghu Zhou,
• Abstract summary: Large language models (LLMs) have demonstrated promising capabilities in Text-Attributed Graph (TAG) understanding.<n>We argue that graphs inherently contain rich structural and semantic information, and that their effective exploitation can unlock potential gains in LLMs reasoning performance.<n>We propose Homophily-aware Structural and Semantic Compression for LLMs (HS2C), a framework centered on exploiting graph homophily.
• Score: 55.51959317490934
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Large language models (LLMs) have demonstrated promising capabilities in Text-Attributed Graph (TAG) understanding. Recent studies typically focus on verbalizing the graph structures via handcrafted prompts, feeding the target node and its neighborhood context into LLMs. However, constrained by the context window, existing methods mainly resort to random sampling, often implemented via dropping node/edge randomly, which inevitably introduces noise and cause reasoning instability. We argue that graphs inherently contain rich structural and semantic information, and that their effective exploitation can unlock potential gains in LLMs reasoning performance. To this end, we propose Homophily-aware Structural and Semantic Compression for LLMs (HS2C), a framework centered on exploiting graph homophily. Structurally, guided by the principle of Structural Entropy minimization, we perform a global hierarchical partition that decodes the graph's essential topology. This partition identifies naturally cohesive, homophilic communities, while discarding stochastic connectivity noise. Semantically, we deliver the detected structural homophily to the LLM, empowering it to perform differentiated semantic aggregation based on predefined community type. This process compresses redundant background contexts into concise community-level consensus, selectively preserving semantically homophilic information aligned with the target nodes. Extensive experiments on 10 node-level benchmarks across LLMs of varying sizes and families demonstrate that, by feeding LLMs with structurally and semantically compressed inputs, HS2C simultaneously enhances the compression rate and downstream inference accuracy, validating its superiority and scalability. Extensions to 7 diverse graph-level benchmarks further consolidate HS2C's task generalizability.

Related papers

• GCL-OT: Graph Contrastive Learning with Optimal Transport for Heterophilic Text-Attributed Graphs [9.735844753899782]
  We propose a graph contrastive learning framework equipped with tailored mechanisms for each type of heterophily.<n>GCL-OT consistently outperforms state-of-the-art methods on nine benchmarks.
  arXiv  Detail & Related papers  (2025-11-20T20:10:49Z)
• GILT: An LLM-Free, Tuning-Free Graph Foundational Model for In-Context Learning [50.40400074353263]
  Graph Neural Networks (GNNs) are powerful tools for precessing relational data but often struggle to generalize to unseen graphs.<n>We introduce textbfGraph textbfIn-context textbfL textbfTransformer (GILT), a framework built on an LLM-free and tuning-free architecture.
  arXiv  Detail & Related papers  (2025-10-06T08:09:15Z)
• GRIL: Knowledge Graph Retrieval-Integrated Learning with Large Language Models [59.72897499248909]
  We propose a novel graph retriever trained end-to-end with Large Language Models (LLMs)<n>Within the extracted subgraph, structural knowledge and semantic features are encoded via soft tokens and the verbalized graph, respectively, which are infused into the LLM together.<n>Our approach consistently achieves state-of-the-art performance, validating the strength of joint graph-LLM optimization for complex reasoning tasks.
  arXiv  Detail & Related papers  (2025-09-20T02:38:00Z)
• Refining Interactions: Enhancing Anisotropy in Graph Neural Networks with Language Semantics [6.273224130511677]
  We introduce LanSAGNN (Language Semantic Anisotropic Graph Neural Network), a framework that extends the concept of anisotropic GNNs to the natural language level.<n>We propose an efficient dual-layer LLMs finetuning architecture to better align LLMs' outputs with graph tasks.
  arXiv  Detail & Related papers  (2025-04-02T07:32:45Z)
• GMLM: Bridging Graph Neural Networks and Language Models for Heterophilic Node Classification [0.0]
  We propose a novel framework that enables effective fusion between pre-trained text encoders and Graph Convolutional Networks (R-GCNs)<n> Experiments on five heterophilic benchmarks demonstrate that our integration method achieves state-of-the-art results.<n>These results highlight the effectiveness of our fusion strategy for advancing text-rich graph representation learning.
  arXiv  Detail & Related papers  (2025-02-24T07:44:01Z)
• Predict, Cluster, Refine: A Joint Embedding Predictive Self-Supervised Framework for Graph Representation Learning [0.0]
  Graph representation learning has emerged as a cornerstone for tasks like node classification and link prediction.<n>Current self-supervised learning (SSL) methods face challenges such as computational inefficiency, reliance on contrastive objectives, and representation collapse.<n>We propose a novel joint embedding predictive framework for graph SSL that eliminates contrastive objectives and negative sampling while preserving semantic and structural information.
  arXiv  Detail & Related papers  (2025-02-02T07:42:45Z)
• Bridging Large Language Models and Graph Structure Learning Models for Robust Representation Learning [22.993015048941444]
  Graph representation learning is crucial for real-world applications but often encounters pervasive noise. We introduce LangGSL, a framework that integrates the complementary strengths of pre-trained language models and graph structure learning models.
  arXiv  Detail & Related papers  (2024-10-15T22:43:32Z)
• A Pure Transformer Pretraining Framework on Text-attributed Graphs [50.833130854272774]
  We introduce a feature-centric pretraining perspective by treating graph structure as a prior. Our framework, Graph Sequence Pretraining with Transformer (GSPT), samples node contexts through random walks. GSPT can be easily adapted to both node classification and link prediction, demonstrating promising empirical success on various datasets.
  arXiv  Detail & Related papers  (2024-06-19T22:30:08Z)
• Multi-View Empowered Structural Graph Wordification for Language Models [12.22063024099311]
  We introduce an end-to-end modality-aligning framework for LLM-graph alignment: Dual-Residual Vector Quantized-Variational AutoEncoder, namely Dr.E.<n>Our approach is purposefully designed to facilitate token-level alignment with LLMs, enabling an effective translation of the intrinsic'of graphs into comprehensible natural language.<n>Our framework ensures certain visual interpretability, efficiency, and robustness, marking the promising successful endeavor to achieve token-level alignment between LLMs and GNNs.
  arXiv  Detail & Related papers  (2024-06-19T16:43:56Z)
• SE-GSL: A General and Effective Graph Structure Learning Framework through Structural Entropy Optimization [67.28453445927825]
  Graph Neural Networks (GNNs) are de facto solutions to structural data learning. Existing graph structure learning (GSL) frameworks still lack robustness and interpretability. This paper proposes a general GSL framework, SE-GSL, through structural entropy and the graph hierarchy abstracted in the encoding tree.
  arXiv  Detail & Related papers  (2023-03-17T05:20:24Z)
• Unifying Graph Contrastive Learning with Flexible Contextual Scopes [57.86762576319638]
  We present a self-supervised learning method termed Unifying Graph Contrastive Learning with Flexible Contextual Scopes (UGCL for short) Our algorithm builds flexible contextual representations with contextual scopes by controlling the power of an adjacency matrix. Based on representations from both local and contextual scopes, distL optimises a very simple contrastive loss function for graph representation learning.
  arXiv  Detail & Related papers  (2022-10-17T07:16:17Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.