Source-linked AI summary
Transformer for Graphs: An Overview from Architecture Perspective
Erxue Min, Runfa Chen, Yatao Bian, Tingyang Xu, Kangfei Zhao, Wenbing Huang, Peilin Zhao, Junzhou Huang, Sophia Ananiadou, Yu Rong
TL;DR
Graph Transformer research lacked a comprehensive review and systematic evaluation despite many proposed models for graph-structured data. This survey classifies over 20 models into three architectural groups, implements representative components, and compares them across six benchmarks, finding consistent benefits from graph-specific modules with task-dependent advantages. It also identifies scalability as an important boundary because many approaches are designed for small graphs and can impair performance on sampled subgraphs.
Problem
Comprehensive literature review and systematic evaluation of Transformer variants for graph-structured data were unavailable.
Method
The survey classifies over 20 Graph Transformer models into auxiliary GNNs, graph positional embeddings, and graph-improved attention matrices, then compares representative modules across six benchmarks.
Results
Graph-specific modules improve Transformer performance on graph-level and node-level tasks; GA and AT generally contribute more than PE, with gains larger on graph-level tasks.
Takeaways & Limitations
GA methods perform best in 5 of 9 node-level cases, while AT methods perform best in 8 of 9 graph-level cases.
Takeaways & Limitations
Many Graph-Transformer models are designed for small graphs, and applying them to sampled subgraphs can impair performance, motivating scalable architectures.
Abstract
from arXiv · showhide
Recently, Transformer model, which has achieved great success in many artificial intelligence fields, has demonstrated its great potential in modeling graph-structured data. Till now, a great variety of Transformers has been proposed to adapt to the graph-structured data. However, a comprehensive literature review and systematical evaluation of these Transformer variants for graphs are still unavailable. It's imperative to sort out the existing Transformer models for graphs and systematically investigate their effectiveness on various graph tasks. In this survey, we provide a comprehensive review of various Graph Transformer models from the architectural design perspective. We first disassemble the existing models and conclude three typical ways to incorporate the graph information into the vanilla Transformer: 1) GNNs as Auxiliary Modules, 2) Improved Positional Embedding from Graphs, and 3) Improved Attention Matrix from Graphs. Furthermore, we implement the representative components in three groups and conduct a comprehensive comparison on various kinds of famous graph data benchmarks to investigate the real performance gain of each component. Our experiments confirm the benefits of current graph-specific modules on Transformer and reveal their advantages on different kinds of graph tasks.
1 Introduction
Graph Transformers address limitations of message-passing GNNs while adapting the Transformer to graph structure. This survey organizes graph-specific designs into three architectural groups and evaluates their effects across graph tasks.
- Motivation: Message-passing GNNs are limited by the Weisfeiler-Lehman hierarchy and suffer from over-smoothing and over-squashing.Existing methods do not eliminate these problems from the Message Passing paradigm.
- Motivation: Transformer variants have achieved competitive or superior performance to GNNs in several graph applications.Examples include quantum property prediction and catalyst discovery.
- Survey scope: The survey reviews over 20 Graph Transformer models and identifies three ways to inject graph information into vanilla Transformers.The groups are GNNs as auxiliary modules, graph-derived positional embeddings, and graph-improved attention matrices.
- Architectural taxonomy: Graph information can be injected through GNN placement, structural positional vectors, graph bias terms, or attention masking.GNNs may be placed above, alternated with, or parallel to Transformer blocks; graph embeddings can use degree or centrality.
- Evaluation: Ablation studies on six graph benchmarks test the real performance gains of representative components across graph-level and node-level tasks.The survey also compares the relative contributions of the three groups under a uniform evaluation.
2 Transformer Architecture
The vanilla Transformer uses stacked self-attention and position-wise feed-forward blocks to transform token representations. Multi-head attention separates representations across heads, while positional embeddings distinguish sequence positions.
- Architecture: The Transformer was introduced as an encoder-decoder architecture built from multiple self-attention blocks.The layer maps an input X ∈ R^n×d to an output Z ∈ R^n×d.
- Architecture: Each Transformer layer combines attention computation with position-wise feed-forward network layers.Layer normalization, row-wise softmax, activation functions, and trainable projection parameters are part of the layer.
- Multi-head attention: Multi-head self-attention decomposes Q, K, and V into H heads whose outputs are concatenated.The multi-head mechanism enables representations to be learned from different aspects.
- Positional embedding: Sine and cosine functions with different frequencies provide positional embeddings that distinguish token positions in the sequence.These embeddings supplement the attention mechanism in the standard Transformer.
3 Transformer Architecture for Graphs
Graph Transformers incorporate topology into vanilla self-attention through auxiliary GNNs, graph-derived positional embeddings, or graph-informed attention matrices. These designs combine local structural modeling with global interactions, encode graph structure into node representations, or directly modify attention computation.
- Graph-aware Transformer methods fall into three groups: auxiliary GNN modules, graph positional embeddings, and graph-improved attention matrices.The standard Transformer treats input tokens as a fully connected graph and is therefore unaware of intrinsic topology.
- GNNs as Auxiliary Modules in Transformer: GNN-Transformer architectures place GNN and Transformer blocks sequentially, alternately, or in parallel.The sequential design commonly builds Transformer blocks on top of GNN blocks, while other variants interleave or parallelize the modules.
- GNNs as Auxiliary Modules in Transformer: GraphTrans uses a GNN to learn local neighborhood representations and a Transformer subnetwork to compute global pairwise interactions.This separates local structure learning from position-agnostic global reasoning.
- GNNs as Auxiliary Modules in Transformer: Mesh Graphormer applies a graph residual block after multi-head self-attention to model local and global interactions among mesh vertices and body joints.Its alternatives, placing the graph residual block before attention or in parallel, perform worse than the proposed ordering.
- Improved Positional Embedding from Graphs: Graph positional embeddings encode topology before the Transformer using Laplacian eigenvectors, adjacency-matrix SVD vectors, or degree centrality.These methods either compress adjacency structure into dense vectors or inject selected structural signals such as node degree.
- Improved Attention Matrices from Graphs: Graph-informed attention methods inject topology through graph bias terms, edge-feature biases, or masks that restrict attention to local neighbors or assign different graph priors to heads.Shortest-path edge features can contribute to attention scores, while multi-head masking can represent distinct edge-type subgraphs and implicit relationships.
4 Experimental Evaluations
The evaluation isolates representative graph-specific modules within a standardized Transformer setup and compares them across six graph benchmarks. Graph-specific modules generally improve performance, with benefits varying by task type and module category.
- Evaluation design: The experiments fix Transformer scale at small, middle, and large levels while keeping remaining hyperparameters at empirical values.For large-scale node-level tasks, shadow k-hop sampling generates subgraphs on which graph-aware modules are applied.
- Evaluation design: The study evaluates ten graph-specific modules from auxiliary GNN, positional embedding, and improved attention categories across six graph-level and node-level benchmarks.Representative modules are evaluated individually to reduce confounding from architectures combining multiple graph-specific components and training tricks.
- Overall results: 56% performance improvement is observed at most on molpcba compared with the vanilla Transformer.The reported improvement supports the effectiveness of graph-specific modules across various graph tasks.
- Task differences: Graph-level tasks receive more significant improvements than node-level tasks.For node-level tasks on a single large graph, sampled induced subgraphs can lose graph integrity, introducing variance and information loss.
- Module comparison: GA and AT methods generally bring more benefits than PE methods.The survey attributes PE weaknesses to incomplete graph information and structural information decaying across Transformer layers after being fed only at the input.
- Task-dependent advantages: GA methods achieve the best performance in 5 of 9 node-level cases, whereas AT methods achieve the best performance in 8 of 9 graph-level cases.The results suggest task-dependent advantages: GA for node-level settings and AT for graph-level settings.
5 Conclusion and Future Directions
The survey organizes Graph Transformer research into three module groups and identifies future work in developing graph-aware paradigms and extending models beyond current graph settings.
- Conclusion: The survey classifies graph-specific Transformer modules into auxiliary GNNs, graph-derived positional embeddings, and graph-derived attention matrices.The review and comparison are intended to foster understanding and stimulate new ideas.
- Future Directions: Future work should develop paradigms that reflect graph properties beyond treating graphs only as strong priors for modifying Transformers.
- Future Directions: Existing Graph Transformer models mostly focus on homogeneous graphs, motivating study of heterogeneous graphs and hypergraphs.
- Future Directions: Most existing methods target small graphs and may be computationally infeasible at large scale.Applying them directly to sampled subgraphs impaired performance in the experiments, motivating scalable Graph Transformer architectures.