Source-linked AI summary
Do Transformers Really Perform Bad for Graph Representation?
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, Tie-Yan Liu
TL;DR
Graph-level prediction has not established Transformers as competitive with mainstream GNNs, leaving their suitability for graph representation an open question. Graphormer answers this by retaining the standard Transformer while encoding graph structure through centrality, spatial, and edge mechanisms. It achieves strong results across graph benchmarks, including over 10% relative-error improvement on OGB-LSC, while quadratic attention limits scalability to large graphs.
Problem
Transformers have not become the de-facto standard on public graph-representation leaderboards, leaving their suitability for modeling graphs an open question.
Method
Graphormer directly builds on the standard Transformer and incorporates centrality, spatial, and edge encodings to represent graph structure.
Results
Graphormer achieves state-of-the-art performance across graph-level tasks and exceeds most mainstream GNN variants by more than 10% points in relative error on OGB-LSC.
Takeaways & Limitations
The results support the potential and adaptability of Transformer architectures for graph representation when structural information is encoded.
Takeaways & Limitations
Graphormer’s quadratic self-attention complexity restricts application on large graphs and motivates development of more efficient versions.
Abstract
from arXiv · showhide
The Transformer architecture has become a dominant choice in many domains, such as natural language processing and computer vision. Yet, it has not achieved competitive performance on popular leaderboards of graph-level prediction compared to mainstream GNN variants. Therefore, it remains a mystery how Transformers could perform well for graph representation learning. In this paper, we solve this mystery by presenting Graphormer, which is built upon the standard Transformer architecture, and could attain excellent results on a broad range of graph representation learning tasks, especially on the recent OGB Large-Scale Challenge. Our key insight to utilizing Transformer in the graph is the necessity of effectively encoding the structural information of a graph into the model. To this end, we propose several simple yet effective structural encoding methods to help Graphormer better model graph-structured data. Besides, we mathematically characterize the expressive power of Graphormer and exhibit that with our ways of encoding the structural information of graphs, many popular GNN variants could be covered as the special cases of Graphormer.
1 Introduction
Transformers excel in sequential, visual, and programming domains but have not become standard for graph representation. Graphormer addresses this gap by adding structural encodings to a standard Transformer and achieves strong graph-level results, including on OGB-LSC.
- Transformer has performed strongly in language, speech, vision, and programming, yet remains absent from public graph-representation leaderboards as the de-facto standard.
- Graphormer is directly built upon the standard Transformer and achieves state-of-the-art performance across graph-level prediction tasks and multiple leaderboards.
- Graphormer incorporates structural information because ordinary self-attention models semantic similarity without explicitly considering node and pairwise graph structure.
- Degree-based centrality encoding assigns each node a learnable degree-dependent vector and adds it to the input node features.
- Spatial encoding assigns learnable embeddings to node pairs according to their structural relations, addressing the absence of a canonical grid in graphs.
- Graphormer outperforms most mainstream GNN variants by more than 10% points in relative error on the OGB-LSC quantum chemistry regression dataset and surpasses previous best results on MolHIV, MolPCBA, and ZINC.
2 Preliminary
The preliminaries describe GNNs as iterative neighbor-aggregation models with graph-level readout, and Transformers as layered self-attention and feed-forward architectures. These formulations establish the components that Graphormer later combines for graph representation.
- Graph Neural Network (GNN): GNNs learn node and graph representations by iteratively updating node states through aggregation and combination of first- or higher-order neighbors.
- Graph Neural Network (GNN): The AGGREGATE function gathers neighbor information, while COMBINE fuses it into the updated node representation; common aggregators include MEAN, MAX, and SUM.
- Graph Neural Network (GNN): For graph-level tasks, READOUT aggregates final node features into a representation of the entire graph using permutation-invariant summation or graph-level pooling.
- Transformer: A Transformer consists of stacked layers, each containing a self-attention module and a position-wise feed-forward network.
- Transformer: Self-attention projects the input hidden states H into queries Q, keys K, and values V using learned matrices before computing attention from query-key similarity.
3 Graphormer
Graphormer adapts the standard Transformer to graph-level prediction by encoding node, pairwise, and edge structural information into attention. Its design provides global graph interactions, covers several popular GNNs theoretically, and can exceed classic message-passing expressiveness.
- Structural encodings: Graphormer introduces three structural encodings that incorporate graph information into the Transformer architecture.These designs provide inductive bias for learning graph representations.
- Centrality Encoding: Centrality Encoding adds learnable degree-based embeddings to node features, allowing attention to use node importance alongside semantic features.For directed graphs, separate embeddings represent indegree and outdegree; undirected graphs can unify them.
- Spatial Encoding: Spatial Encoding assigns learnable attention biases from pairwise graph relations, using shortest-path distance for connected nodes and -1 otherwise.The bias is indexed by the spatial relation and shared across Transformer layers.
- Edge Encoding: Edge Encoding incorporates edge features by averaging feature–embedding dot products along a shortest path and adding the result as an attention bias.This directly conditions pairwise attention correlations on the edges connecting the nodes.
- Graph representation: A special [VNode] connected virtually to every node represents the entire graph through its final-layer embedding.Its spatial encodings use a distinct learnable scalar to distinguish virtual from physical connections.
- Expressiveness: Graphormer can represent the AGGREGATE and COMBINE steps of GIN, GCN, and GraphSAGE, while spatial encoding can distinguish graphs that 1-WL fails to separate.The construction uses neighbor-aware attention, degree information, multiple heads, and feed-forward processing.
- Expressiveness: Vanilla self-attention without additional encodings can represent MEAN READOUT functions in every node representation.This connects global self-attention to the graph-level aggregation role of virtual nodes without adding a supernode.
4 Experiments
Experiments evaluate Graphormer on large-scale quantum chemistry, molecular property, and graph regression benchmarks, alongside ablations of its structural encodings. Graphormer achieves strong benchmark performance, while spatial, centrality, and edge encodings each contribute to its effectiveness.
- Experimental Setup: Graphormer is evaluated on PCQM4M-LSC, MolHIV, MolPCBA, and ZINC, with comparisons against GCN, GIN, virtual-node variants, DeeperGCN, and GT.The experiments also include pretraining transfer and ablation studies on PCQM4M-LSC.
- PCQM4M-LSC: 11.5% relative validate MAE decline lets Graphormer surpass GIN-VN on PCQM4M-LSC; an ExpC ensemble reaches 0.1200 MAE on the complete test set.The ensemble won first place in the graph-level track of the OGB Large-Scale Challenge.
- Graph Representation: Graphormer consistently and significantly outperforms previous state-of-the-art GNNs by a large margin on MolHIV, MolPCBA, and ZINC.Other pre-trained GNNs do not achieve competitive performance in the reported comparisons.
- Ablation Studies: The spatial encoding outperforms Laplacian positional encoding, demonstrating the effectiveness of spatial encoding for capturing node spatial information.The ablation compares positional encoding with the proposed spatial encoding as ways to encode node relations for Transformers.
- Ablation Studies: Degree-based centrality encoding yields a large performance boost over models without centrality information, indicating its importance for Transformer-based graph modeling.The result identifies centrality information as an important design element in Graphormer.
- Ablation Studies: Edge encoding as an attention bias performs significantly better than two conventional edge-feature encodings, making it more effective for capturing edge spatial information.The conventional methods encode edge features via nodes or aggregation, whereas Graphormer incorporates them through attention bias.
5 Related Work
Related work explores adapting Transformer architectures and graph structural encodings to improve graph representation learning.
- Prior work modifies Transformer layers with added GNN components, long-range residual connections, and separate branches for node and edge representations.
- Graph research has used path, distance, and higher-order-neighbor information to model interactions during attention or aggregation.
- Several Transformer-based graph models introduce positional encodings based on Weisfeiler-Lehman labels, node intimacy, hops, or Laplacian information.
- Other approaches encode edge features through similarity weighting, integration into GIN, projected embeddings, attention coefficients, or additional feed-forward layers.
6 Conclusion
Graphormer applies Transformers directly to graph representation using three structural encodings and performs well across popular graph benchmarks, while important scalability and sampling challenges remain.
- Graphormer uses three graph structural encodings and works well across a wide range of popular benchmark datasets.
- Quadratic self-attention complexity restricts Graphormer’s application on large graphs, motivating future development of more efficient variants.
- The paper identifies domain-knowledge-powered encodings and graph sampling strategies for node representation extraction as future directions.
A Proofs
Shortest-path-distance information can distinguish some graph pairs that 1-WL-test cannot distinguish.
- In Figure 2, the two graphs share indistinguishability under 1-WL-test but have different shortest-path-distance sets across nodes.
- 1-WL-test fails on some graph pairs, and classic message-passing GNNs consequently also fail to distinguish many such pairs.
A.2 Proof of Fact 1
Graphormer’s spatially encoded self-attention can implement mean, sum, and max neighborhood aggregation, combine node and aggregate representations, and thereby cover popular GNN operations.
- MEAN AGGREGATE: Mean aggregation is implemented by assigning attention only to one-hop neighbors and setting value projections to the identity.
- SUM AGGREGATE: Sum aggregation follows mean aggregation by extracting node degrees through centrality encoding and multiplying averaged representations by those degrees.
- MAX AGGREGATE: Max aggregation uses one attention head per representation dimension to select the largest neighbor value.
- COMBINE: The combine step uses an additional head for the current node and an FFN to approximate functions of aggregated and previous representations.
A.3 Proof of Fact 2
The proof recovers a mean-readout operation by setting query and key projections to zero, using constant bias terms, and making the value projection the identity.
- Setting WQ = WK = 0 removes query-key variation from the attention mechanism.
- Choosing the Q and K bias terms as T1 creates uniform attention logits.
- Using WV as the identity matrix preserves the value representations for aggregation.
B.1 Details of Datasets
The experiments cover large-scale quantum chemistry and molecular graph benchmarks, with Graphormer configurations, pre-training, fine-tuning, and baseline re-implementation details reported across datasets.
- Datasets: PCQM4m-LSC is a quantum chemistry graph-level prediction task curated under the PubChemQC project for the OGB Large-Scale Challenge.
- Datasets: PCQM4M-LSC predicts the DFT-calculated HOMO-LUMO energy gap from 2D molecular graphs across more than 3.8M graphs.
- Pre-training: The pre-trained Graphormer for MolPCBA uses 18 Transformer layers with hidden and FFN dimensions of 1024, while attention dropout is increased to 0.3.
- Fine-tuning: Fine-tuning on MolPCBA and MolHIV uses grid searches, ten independent random-seed runs, and FLAG-based graph data augmentation or tuning.
- Configurations and baselines: GraphormerSLIM uses about 489K learnable parameters for the Benchmarking-GNN setting, while baseline implementations follow official or author-provided configurations.
C More Experiments
The paper compares Graphormer with the pre-trained Transformer-based GNN GROVER on MolHIV and MolPCBA, including GROVER’s additional molecular features where needed.
- GROVER comparison: GROVER has 100 million parameters and was pre-trained on 10 million unlabeled molecules using 250 Nvidia V100 GPUs.
- GROVER comparison: GROVER achieves competitive MolHIV performance only when using Morgan molecular fingerprints and 2D molecular features.
- Results: Graphormer consistently outperforms GROVER on MolHIV and MolPCBA without additional molecular features.
D Discussion & Future Work
The discussion identifies quadratic attention cost, general-purpose structural encodings, and unaddressed node-representation tasks as boundaries and directions for future work.
- Complexity: Graphormer attention scales as O(n^2) in the number of graph nodes, which can be prohibitively expensive for large graphs.
- Encoding choices: The study mainly evaluates degree centrality and shortest-path encodings, leaving domain-specific choices such as 3D molecular distances for future improvement.
- Node representation: Node-representation applications in finance, social networks, and temporal prediction are left for future work because an applicable graph-sampling strategy is needed.