Research map / Graph learning / GNN architectures
Attention Mechanisms Perspective: Exploring LLM Processing of Graph-Structured Data
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Empirical study of how LLMs (LLaGA-style fine-tuned Llama2-7B) attend to graph nodes serialized as text, finding weak use of connectivity and that intermediate attention windows (k=2/3) train better and transfer to fully connected inference.
Problem
Whether and how LLMs' attention mechanisms process graph-structured data serialized in natural language, and why they underperform GNNs on topology-dependent node tasks.
Approach
Analyzes LLM attention over node tokens before/after fine-tuning, via disruption experiments on connectivity, and introduces a global linkage horizon k that limits node visibility in the attention window; finds intermediate windows train better and transfer to full attention at inference.
Key results
- Disrupting connectivity barely changes accuracy on Wikics and Pubmed, while Roman-Empire degrades (e.g., 80.89% raw to 57.84% under disruption IV for Llama2-7B).
- Intermediate window k=2 unidirectional reaches 78.90% on WikiCS and k=1 reaches 83.12% on Roman-Empire, versus 77.49% and 80.73% for full window k=4.
- Training with k=2 or k=3 and testing at full window k=4 gives better results than training directly at k=4 (e.g., Roman 79.22% for k=3 trained/k=2 test vs 77.49% baseline).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use intermediate attention horizons k=2 or k=3 instead of fully connected k=4 | LLaMA2-7B graph node classification · WikiCS, Roman-Empire, Amazon-Ratings, and Pubmed | accuracy: WikiCS 77.49$\pm$0.21 -> 78.90$\pm$0.17; Roman-Empire 80.73$\pm$0.0 -> 83.12$\pm$0.0; Amazon-Ratings 45.19$\pm$ 0.2 -> 4 | Mixed |
| Train with k=3 unidirectional, then infer with k=4 unidirectional | LLaMA2-7B · WikiCS | accuracy: 77.49$\pm$0.21 -> 77.82$\pm$0.30 | Helped |
| Train with k=3 unidirectional, then infer with k=2 unidirectional | LLaMA2-7B · WikiCS | accuracy: 77.96$\pm$0.13 -> 79.22$\pm$0.15 | Helped |
| Disrupt connectivity by swapping child-node sets (level I) or exchanging child nodes (level II) (ablation) | LLaMA2-7B graph node classification · WikiCS and Pubmed | accuracy: WikiCS 0.7862$7.007 -> 0.7847$7.004 (I), 0.7907$7.0035 (II); Pubmed 0.8367$7.003 -> 0.8363$7.001 (I), 0.8364$7.002 | No clear effect |
| Disrupt connectivity by randomly shuffling node positions (level III) or adding unrelated nodes and random substitutions (level IV) (ablation) | LLaMA2-7B graph node classification · WikiCS, Pubmed, Amazon-Ratings, and Roman-Empire | accuracy: Wikics: 0.7862$\pm$ 0.007 -> 0.7670$\pm$ 0.003 (III), 0.7080$\pm$ 0.005 (IV); Pubmed: 0.8367$\pm$0.003 -> 0.7698$\pm$0.0 | Hurt |
| Disrupt connectivity by swapping child-node sets (I) or exchanging child nodes (II) (ablation) | LLaMA2-7B graph node classification · Amazon-Ratings and Roman-Empire | accuracy: Amazon-Ratings: 0.4486$\pm$0.002 -> 0.3980$\pm$0.003 (I), 0.3977$\pm$0.002 (II); Roman-Empire: 0.8089$\pm$0.001 -> 0.791 | Hurt |
Surprising findings
- Randomly shuffling or swapping connectivity has almost no effect on performance on several datasets, indicating LLMs do not use correct connectivity information.
- Models trained with a smaller linkage horizon transfer to larger horizons at inference and perform better than models trained at full horizon.
Limitations
- Only a subset of discovered phenomena analyzed due to length and resource limits.
- Experiments restricted to four datasets and 7B-scale Llama-family models.
- Intermediate-window settings require pre-labeling node tokens and modifying the attention mask, complicating deployment.
Experimental setup
Datasets: Roman-Empire Amazon-Ratings Pubmed WikiCS
Benchmarks: Roman-Empire Amazon-Ratings Pubmed WikiCS
Metrics: accuracy t-test Kolmogorov-Smirnov test Jensen-Shannon divergence
Baselines: GNNs LLaGA InstructGLM
Builds on: LLaGA InstructGLM StreamingLLM
Closest papers by meaning
- How Do Large Language Models Understand Graph Patterns? A Benchmark for Graph Pattern Comprehension (ICLR 2025 · similarity 0.91)
- Can Large Language Models Analyze Graphs like Professionals? A Benchmark, Datasets and Models (NeurIPS 2024 · similarity 0.90)
- LLaGA: Large Language and Graph Assistant (ICML 2024 · similarity 0.90)
- LoReC: Rethinking Large Language Models for Graph Data Analysis (NeurIPS 2026 · similarity 0.90)
- GraphRouter: A Graph-based Router for LLM Selections (ICLR 2025 · similarity 0.90)
- Talk like a Graph: Encoding Graphs for Large Language Models (ICLR 2024 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.