Research map / Graph learning / Graph self-supervised learning
From Sequence to Structure: Uncovering Substructure Reasoning in Transformers
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.
Proposes Induced Substructure Filtration (ISF) to explain how decoder-only Transformers extract substructures layer by layer, validates it on small from-scratch GPT-2-style models and fine-tuned Llama-3.1-8B, and introduces Thinking-in-Substructure (Tins) decomposition.
Problem
How a decoder-only Transformer, given a textual graph and a question prompt, identifies and extracts substructures (e.g., triangles, squares, houses) from graphs, and how that mechanism extends to LLMs and attributed molecular graphs.
Approach
Models substructure extraction as a layer-wise induced subgraph filtration: each layer progressively identifies larger induced subgraph isomorphism indicators, so the answer is determined before generation; composite patterns are handled by decomposing them into simpler substructures (Tins) to reduce complexity from O(n^k) to O(n^q).
Key results
- Transformers with at least 2 layers reach over 85% accuracy on several substructure extraction tasks; triangle reaches about 99% with 3 layers and 100K examples.
- Tins decomposition raises overall performance by about 10%, and diagonal accuracy at 3 layers rises from 0.1998 to 0.6606.
- On fine-tuned Llama-3.1-8B-Instruct, ARI and NMI scores increase with depth on a triangle detection task, supporting the layer-wise ISF picture.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| decompose composite targets into simpler substructures with Tins | GPT-2-style Transformer · Composite substructure: Diagonal, Diamond, House, and Complex | accuracy: 0.6314 -> 0.8648; 0.4756 -> 0.7792; 0.5887 -> 0.8066; 0.1182 -> 0.2268 | Helped |
| use a terminology-based prompt instead of a topology-based prompt (ablation) | GPT-2-style Transformer · Prompt Group2: Diagonal | accuracy: 0.2332 -> 0.9082 | Helped |
| use a terminology-based prompt instead of a topology-based prompt (ablation) | GPT-2-style Transformer · Prompt Group1: Triangle | accuracy: 0.9794 -> 0.9782 | No clear effect |
| shuffle node names in a topology-based prompt (ablation) | GPT-2-style Transformer · Prompt Group2: Diagonal | accuracy: 0.2332 -> 0.7354 | Helped |
| increase training examples from 100K to 300K at 3 layers (ablation) | GPT-2-style Transformer · Single-shape extraction across substructures | accuracy: Triangle: 0.9662 ± 0.00 -> 0.9948 ± 0.00; Path: 0.8066 ± 0.02 -> 0.9195 ± 0.01; Square: 0.3991 ± 0.00 -> 0.7247 ± 0.01 | Helped |
| increase model depth from 3 to 4 layers with 300K training examples (ablation) | GPT-2-style Transformer · Single-shape extraction across substructures | accuracy: Square: 0.7247 ± 0.01 -> 0.9403 ± 0.02; Diagonal: 0.6313 ± 0.07 -> 0.9140 ± 0.02; Diamond: 0.6189 ± 0.02 -> 0.8765 ± 0.0 | Helped |
| use attributed adjacency-list input to extract molecular functional groups | GPT-2-style Transformer · Molecular graphs | accuracy: C-O(H): 0.9207; COO(H): 0.9159; C6(H6): 0.7245; Mix: 0.8946 | Helped |
Surprising findings
- Edge list requires more Transformer layers than adjacency list despite both being theoretically equivalent in representational power.
- Transformers rely on symbolic tokens in topology prompts rather than full structural understanding; topology-based prompts struggle with diagonal substructures (accuracy 0.2332 for one phrasing).
Limitations
- Focuses only on the substructure extraction task; other substructure-related tasks are unexplored.
- Theory is a high-level overview of decoder-only Transformers and omits some theoretical details.
- Interpretation of LLMs is qualitative and LLMs generate explanatory content that complicates analysis.
Experimental setup
Datasets: synthetic directed graphs (4-16 nodes, 3-120 edges) molecular graphs with functional group labels
Benchmarks: synthetic substructure extraction tasks (triangle, path, square, diagonal, pentagon, house, diamond) molecular functional group extraction
Metrics: exact-match accuracy ARI NMI
Baselines: Directly predicting substructures (no decomposition) Edge list vs adjacency list representations
Builds on: GPT-2 GraphPatt ALPINE NLGraph Weisfeiler-Lehman tests
Closest papers by meaning
- Talk like a Graph: Encoding Graphs for Large Language Models (ICLR 2024 · similarity 0.89)
- UniGTE: Unified Graph–Text Encoding for Zero-Shot Generalization across Graph Tasks and Domains (NeurIPS 2025 · similarity 0.88)
- The Expressive Power of Transformers with Chain of Thought (ICLR 2024 · similarity 0.88)
- How Do Large Language Models Understand Graph Patterns? A Benchmark for Graph Pattern Comprehension (ICLR 2025 · similarity 0.88)
- DiGraphHal-Bench: Evaluating Multimodal Large Language Models on Complex Directed Graphs (CVPR 2026 · similarity 0.88)
- Transformers need glasses! Information over-squashing in language tasks (NeurIPS 2024 · similarity 0.88)
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.