동질성 인식 구조 및 의미적 텍스트 속성 그래프 압축을 통한 LLM 추론 개선

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

대규모 언어 모델(LLM)은 텍스트 속성 그래프(TAG) 이해에 있어 유망한 능력을 보여주었습니다. 최근 연구들은 주로 수작업 프롬프트를 통해 그래프 구조를 언어화하고, 대상 노드와 그 이웃 문맥을 LLM에 입력하는 데 초점을 맞추고 있습니다. 그러나 문맥 윈도우의 제약으로 인해 기존 방법들은 주로 노드나 엣지를 무작위로 삭제하는 방식의 무작위 샘플링에 의존하는데, 이는 필연적으로 노이즈를 유발하고 추론의 불안정성을 초래합니다. 우리는 그래프가 본질적으로 풍부한 구조적 및 의미론적 정보를 포함하고 있으며, 이를 효과적으로 활용하면 LLM 추론 성능을 잠재적으로 향상시킬 수 있다고 주장합니다. 이를 위해 우리는 그래프 동질성 활용을 중심으로 하는 프레임워크인 'LLM을 위한 동질성 인식 구조 및 의미적 압축(HS2C)'을 제안합니다. 구조적으로는 구조적 엔트로피 최소화 원칙에 따라 그래프의 본질적인 위상을 파악하는 전역적 계층 분할을 수행합니다. 이 분할은 확률적 연결 노이즈를 제거하면서 자연스럽게 응집된 동질적 커뮤니티를 식별합니다. 의미적으로는 식별된 구조적 동질성을 LLM에 전달하여, 사전 정의된 커뮤니티 유형에 따라 차별화된 의미적 집계를 수행할 수 있도록 합니다. 이 과정은 중복되는 배경 문맥을 간결한 커뮤니티 수준의 합의로 압축하며, 대상 노드와 정렬된 의미적으로 동질적인 정보를 선별적으로 보존합니다. 다양한 크기와 계열의 LLM에 걸친 10개의 노드 수준 벤치마크에 대한 광범위한 실험 결과, 구조적 및 의미적으로 압축된 입력을 LLM에 제공함으로써 HS2C가 압축률과 다운스트림 추론 정확도를 동시에 향상시킴을 입증하였으며, 이는 그 우수성과 확장성을 보여줍니다. 또한 7개의 다양한 그래프 수준 벤치마크로의 확장은 HS2C의 과제 일반화 능력을 더욱 공고히 합니다.

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.