Back

Recipe for a General, Powerful, Scalable Graph Transformer

Ladislav RampásekMichael GalkinVijay Prakash DwivediAnh Tuan LuuGuy WolfDominique Beaini

article2022NeurIPS931 citations

Presents GraphGPS, a modular graph Transformer framework that achieves linear computational complexity by decoupling local message passing from global attention while delivering state-of-the-art performance across 16 standard benchmarks.

Listen

Graph neural networks are widely used to model relational data in critical domains such as molecular chemistry, biology, and computer vision. However, standard local message-passing networks suffer from fundamental bottlenecks, including an inability to capture long-range dependencies and a failure to distinguish certain non-isomorphic graph structures. While emerging graph Transformers address these issues by enabling global attention across all nodes, existing designs require computational costs that scale quadratically with graph size, restricting their application to small graphs with only a few hundred nodes.

The main objective of the article is to introduce and evaluate a modular blueprint called the General, Powerful, Scalable (GPS) graph Transformer architecture. This framework aims to achieve linear computational complexity while matching or exceeding the predictive accuracy of specialized graph models across a diverse set of tasks.

To accomplish this, the authors designed a hybrid architecture that decouples local message passing from global attention. The framework incorporates structural and positional encodings—categorized into local, global, and relative features—to provide spatial and structural context. By assigning local edge operations to standard message-passing layers and utilizing linear-complexity attention modules, the design eliminates the need to compute dense pairwise matrices for global attention. The authors evaluated the approach across sixteen diverse benchmarking datasets encompassing chemical properties, image recognition, code analysis, and large-scale malware networks containing up to 5,000 nodes per graph.

The empirical findings demonstrate that the hybrid approach delivers top-tier performance across multiple domains. First, the GPS model outperformed prior graph Transformers on eleven out of sixteen evaluated benchmarks and set new state-of-the-art results on eight. Second, on the large-scale PCQM4Mv2 molecular benchmark, GPS achieved superior error reduction with 19.4 million parameters, outperforming competing models that required more than twice the parameter count. Third, on large graph benchmarks such as MalNet-Tiny, the architecture scaled efficiently to thousands of nodes per graph, reaching over 92% to 93% accuracy where standard graph Transformers fail to compute due to memory limits. Ablation studies further revealed that removing either the local message-passing module or the structural encodings caused substantial performance drops, confirming that both local connectivity and global context are essential.

These results demonstrate that organizations can deploy graph Transformers on large-scale, complex networks without incurring prohibitive computational costs or sacrificing model expressiveness. Decoupling local edge aggregation from global attention lowers hardware requirements, accelerates training runtimes, and reduces overfitting risk. This makes advanced graph modeling practical for production workflows in molecular design, bioinformatics, and software analysis.

Organizations developing graph-based machine learning systems should adopt a hybrid design combining local neighborhood aggregation with global attention, rather than relying solely on pure Transformers or standard message-passing networks. Teams should leverage the open-source GraphGPS framework to experiment with modular combinations of positional encodings and efficient linear attention mechanisms tailored to their domain. When implementing this architecture, practitioners must conduct validation pilots to select dataset-specific encodings and attention variants, as optimal configurations vary across application domains.

The findings are supported by consistent results across extensive benchmarks and multiple random seeds. However, users should note that model performance remains sensitive to hyperparameter choices, and there is no single optimal configuration for every problem. Additionally, some linear attention approximations slightly lag behind full attention mechanisms in predictive accuracy on smaller graphs, requiring a deliberate trade-off between computational scalability and raw performance.

McGill UniversityMilaNanyang Technological UniversityUniversité de MontréalValence Discoveryattention mechanismencoder-decoderfunction approximatorsScalable Graph TransformerLong-Range Graph BenchmarkGraphGPS
arXiv: 2205.12454rampasek/GraphGPS
  • Paper: A Generalization of ViT/MLP-Mixer to Graphs, Xiaoxin He et al. (2023). Extends linear-complexity, scalable graph transformer modeling by partitioning graphs into sub-graph patches with vision-inspired token mixing.
  • Paper: Benchmarking Graph Neural Networks, Vijay Prakash Dwivedi et al. (2023). Provides a comprehensive, standardized benchmarking suite and rigorous parameter-controlled evaluation for advanced message-passing and transformer-based graph architectures.
  • Paper: Specformer: Spectral Graph Neural Networks Meet Transformers, Deyu Bo et al. (2023). Continues the fusion of Transformers and spectral graph theory by applying attention mechanisms directly over graph frequency representations.
  • Paper: Universal Prompt Tuning for Graph Neural Networks, Taoran Fang et al. (2023). Explores parameter-efficient prompt tuning strategies to adapt pre-trained expressive graph architectures to downstream tasks without full fine-tuning.
Cover for Recipe for a General, Powerful, Scalable Graph Transformer

Abstract

We propose a recipe on how to build a general, powerful, scalable (GPS) graph Transformer with linear complexity and state-of-the-art results on a diverse set of benchmarks. Graph Transformers (GTs) have gained popularity in the field of graph representation learning with a variety of recent publications but they lack a common foundation about what constitutes a good positional or structural encoding, and what differentiates them. In this paper, we summarize the different types of encodings with a clearer definition and categorize them as being local\textit{local}, global\textit{global} or relative\textit{relative}. The prior GTs are constrained to small graphs with a few hundred nodes, here we propose the first architecture with a complexity linear in the number of nodes and edges O(N+E)O(N+E) by decoupling the local real-edge aggregation from the fully-connected Transformer. We argue that this decoupling does not negatively affect the expressivity, with our architecture being a universal function approximator on graphs. Our GPS recipe consists of choosing 3 main ingredients: (i) positional/structural encoding, (ii) local message-passing mechanism, and (iii) global attention mechanism. We provide a modular framework GraphGPS\textit{GraphGPS} that supports multiple types of encodings and that provides efficiency and scalability both in small and large graphs. We test our architecture on 16 benchmarks and show highly competitive results in all of them, show-casing the empirical benefits gained by the modularity and the combination of different strategies.

Topics

attention mechanismencoder-decoderfunction approximatorsgpslinear complexityrepresentation learningbipartite graphs

Keywords

Scalable Graph TransformerLong-Range Graph BenchmarkGraphGPSOpen Graph Benchmarkgraph-level predictiongraph regressionTransformer architecturegraph Laplacianmolecular graphsgraph isomorphism

Table of Contents

  • 1 Introduction
  • 2 Related Work
  • 3 Methods
  • 3.1 Modular positional and structural encodings
  • 3.2 Why do we need PE and SE in MPNN?
  • 3.3 GPS layer: an MPNN+Transformer hybrid
  • 3.4 Theoretical expressivity
  • 4 Experiments
  • 4.1 Ablation studies
  • 4.2 Benchmarking GPS
  • 5 Conclusion
  • References
  • A Experimental Details
  • A.1 Datasets description
  • A.2 Dataset splits and random seeds
  • A.3 Hyperparameters
  • A.4 Computing environment and used resources
  • B Detailed ablation studies
  • C Theoretical results
  • C.1 Why do we need PE and SE?
  • C.2 Preserving edge information in the self-attention layer
  • D GPS schematics
  • D.1 GPS layer
  • D.2 GPS algorithm

Knowls

  1. Knowl 1 — GPS Layer Hybrid Architecture

    model/method

    The General, Powerful, Scalable (GPS) layer is a hybrid graph representation learning block that combines a local message-passing neural network (MPNN) and a global self-attention mechanism in parallel within each layer.

    Let G=(V,E)G = (V, E) be a graph with N=∣V∣N = |V| nodes and E=∣E∣E = |E| edges, represented by an adjacency matrix A∈RN×NA \in \mathbb{R}^{N \times N}, node feature tensor Xℓ∈RN×dℓX^\ell \in \mathbb{R}^{N \times d_\ell}, and edge feature tensor Eℓ∈RE×dℓE^\ell \in \mathbb{R}^{E \times d_\ell} at layer ℓ\ell. The GPS layer computes updated node features Xℓ+1X^{\ell+1} and edge features Eℓ+1E^{\ell+1} through the following decoupled structure:

    1. Local Message-Passing Branch: A modular MPNN layer MPNNeℓ\text{MPNN}_e^\ell operates over the 1-hop neighborhood of each node using both node representations XℓX^\ell and explicit edge attributes EℓE^\ell, producing an intermediate local node update X^Mℓ+1\hat{X}^{\ell+1}_M and updated edge features Eℓ+1E^{\ell+1}.
    2. Global Attention Branch: A global attention mechanism GlobalAttnℓ\text{GlobalAttn}^\ell (such as full dense self-attention, Performer, or BigBird) operates on all pairs of nodes using exclusively the node representations XℓX^\ell, producing an intermediate global node update X^Tℓ+1\hat{X}^{\ell+1}_T. Decoupling the edge features from this branch avoids the necessity of materializing an O(N2)O(N^2) edge-bias matrix.
    3. Aggregation and MLP Update: The outputs of both branches are processed with residual connections, dropout, and batch normalization, summed together, and passed through a 2-layer multi-layer perceptron (MLP) with ReLU activations and an internal dimension of 2dℓ2 d_\ell to produce Xℓ+1X^{\ell+1}.

  2. Knowl 2 — GPS Layer Forward Update Equations

    equation

    For layer index ℓ∈{0,…,L−1}\ell \in \{0, \dots, L-1\}, given adjacency matrix A∈RN×NA \in \mathbb{R}^{N \times N}, node feature representations Xℓ∈RN×dℓX^\ell \in \mathbb{R}^{N \times d_\ell}, and edge feature representations Eℓ∈RE×dℓE^\ell \in \mathbb{R}^{E \times d_\ell}, the GPS layer update equations with residual skip connections, dropout, and batch normalization are formulated as:

    X^Mℓ+1,Eℓ+1=MPNNeℓ(Xℓ,Eℓ,A)\hat{X}^{\ell+1}_M, E^{\ell+1} = \text{MPNN}_e^\ell(X^\ell, E^\ell, A)

    X^Tℓ+1=GlobalAttnℓ(Xℓ)\hat{X}^{\ell+1}_T = \text{GlobalAttn}^\ell(X^\ell)

    XMℓ+1=BatchNorm(Dropout(X^Mℓ+1)+Xℓ)X^{\ell+1}_M = \text{BatchNorm}\left(\text{Dropout}\left(\hat{X}^{\ell+1}_M\right) + X^\ell\right)

    XTℓ+1=BatchNorm(Dropout(X^Tℓ+1)+Xℓ)X^{\ell+1}_T = \text{BatchNorm}\left(\text{Dropout}\left(\hat{X}^{\ell+1}_T\right) + X^\ell\right)

    Xℓ+1=MLPℓ(XMℓ+1+XTℓ+1)X^{\ell+1} = \text{MLP}^\ell\left(X^{\ell+1}_M + X^{\ell+1}_T\right)

    where:

    • MPNNeℓ\text{MPNN}_e^\ell denotes a local message-passing neural network block supporting edge features (e.g., GatedGCN, GINE, or PNA);
    • GlobalAttnℓ\text{GlobalAttn}^\ell denotes a global self-attention module (e.g., standard dense Transformer attention, Performer, or BigBird);
    • BatchNorm\text{BatchNorm} denotes batch normalization with learnable affine parameters applied across node embeddings;
    • Dropout\text{Dropout} applies dropout regularization;
    • MLPℓ\text{MLP}^\ell is a 2-layer multi-layer perceptron with ReLU activation in the hidden layer, where the hidden dimensionality is 2dℓ2 d_\ell and the output dimensionality matches the input dimensionality dℓd_\ell.

  3. Knowl 3 — GPS Network Forward Execution Algorithm

    algorithm

    The GPS architecture processes an input graph with positional and structural encodings through LL consecutive GPS layers, producing contextualized node and edge representations.

    Input: Graph G=(V,E)G = (V, E) with NN nodes and EE edges; Adjacency matrix A∈RN×NA \in \mathbb{R}^{N \times N}; Input node features X∈RN×DnodeX \in \mathbb{R}^{N \times D_{\text{node}}}; Input edge features Ein∈RE×DedgeE_{\text{in}} \in \mathbb{R}^{E \times D_{\text{edge}}}; Local message passing module MPNNe\text{MPNN}_e; Global attention module GlobalAttn\text{GlobalAttn}; Positional encoding function FPEF_{\text{PE}}; Structural encoding function FSEF_{\text{SE}}; Total layers LL.
    Output: Final node representations XL∈RN×DX^L \in \mathbb{R}^{N \times D} and edge representations EL∈RE×DE^L \in \mathbb{R}^{E \times D}.
    Initialize Pnode,Pedge,Snode,Sedge←∅P_{\text{node}}, P_{\text{edge}}, S_{\text{node}}, S_{\text{edge}} \leftarrow \emptyset
    if FPEF_{\text{PE}} is relative then
        Pedge←FPE(G)∈RE×DPEP_{\text{edge}} \leftarrow F_{\text{PE}}(G) \in \mathbb{R}^{E \times D_{\text{PE}}}
    else
        Pnode←FPE(G)∈RN×DPEP_{\text{node}} \leftarrow F_{\text{PE}}(G) \in \mathbb{R}^{N \times D_{\text{PE}}}
    end if
    if FSEF_{\text{SE}} is relative then
        Sedge←FSE(G)∈RE×DSES_{\text{edge}} \leftarrow F_{\text{SE}}(G) \in \mathbb{R}^{E \times D_{\text{SE}}}
    else
        Snode←FSE(G)∈RN×DSES_{\text{node}} \leftarrow F_{\text{SE}}(G) \in \mathbb{R}^{N \times D_{\text{SE}}}
    end if
    X0←NodeEncoder(X)∥Pnode∥Snode∈RN×DX^0 \leftarrow \text{NodeEncoder}(X) \mathbin{\Vert} P_{\text{node}} \mathbin{\Vert} S_{\text{node}} \in \mathbb{R}^{N \times D}
    E0←EdgeEncoder(Ein)∥Pedge∥Sedge∈RE×DE^0 \leftarrow \text{EdgeEncoder}(E_{\text{in}}) \mathbin{\Vert} P_{\text{edge}} \mathbin{\Vert} S_{\text{edge}} \in \mathbb{R}^{E \times D}
    for ℓ=0,1,…,L−1\ell = 0, 1, \dots, L - 1 do
        X^Mℓ+1,Eℓ+1←MPNNeℓ(Xℓ,Eℓ,A)\hat{X}^{\ell+1}_M, E^{\ell+1} \leftarrow \text{MPNN}_e^\ell(X^\ell, E^\ell, A)
        X^Tℓ+1←GlobalAttnℓ(Xℓ)\hat{X}^{\ell+1}_T \leftarrow \text{GlobalAttn}^\ell(X^\ell)
        XMℓ+1←BatchNorm(Dropout(X^Mℓ+1)+Xℓ)X^{\ell+1}_M \leftarrow \text{BatchNorm}(\text{Dropout}(\hat{X}^{\ell+1}_M) + X^\ell)
        XTℓ+1←BatchNorm(Dropout(X^Tℓ+1)+Xℓ)X^{\ell+1}_T \leftarrow \text{BatchNorm}(\text{Dropout}(\hat{X}^{\ell+1}_T) + X^\ell)
        Xℓ+1←MLPℓ(XMℓ+1+XTℓ+1)X^{\ell+1} \leftarrow \text{MLP}^\ell(X^{\ell+1}_M + X^{\ell+1}_T)
    end for
    return XLX^L and ELE^L

    Here ∥\mathbin{\Vert} denotes feature composition (typically concatenation followed by an initial embedding MLP projection to hidden dimension DD). NodeEncoder\text{NodeEncoder} and EdgeEncoder\text{EdgeEncoder} are dataset-specific initial feature embedding modules.

  4. Knowl 4 — Taxonomy of Graph Positional and Structural Encodings

    definition

    Graph encodings are partitioned into Positional Encodings (PE), which capture spatial distance/coordinates of nodes across the graph, and Structural Encodings (SE), which capture graph/subgraph topological invariants. Both are further categorized across three scopes:

    1. Local PE (Node Features): Informs a node of its position within a local cluster. Nodes closer within a cluster receive closer local PE representations. Example: summing non-diagonal elements per row/column in an mm-step random-walk matrix, or distance to a cluster centroid.
    2. Global PE (Node Features): Informs a node of its global coordinate in the graph canvas. Closer nodes globally have closer representations. Examples: the kk lowest non-trivial eigenvectors ϕk\phi_k of the graph Laplacian, SignNet representations, or component identifiers.
    3. Relative PE (Edge Features): Informs pairs of nodes of directional distance or spatial offset. Examples: shortest-path distances, Green's function, diffusion kernel distances, or the eigenvector gradient ∇ϕk\nabla \phi_k.
    4. Local SE (Node Features): Informs a node of the local substructure topology it belongs to. Nodes with isomorphic mm-hop neighborhoods obtain identical/close local SE. Examples: node degree, diagonal of the mm-step random walk transition matrix diag((D−1A)m)\text{diag}((D^{-1}A)^m), heat kernel diagonals, or subgraph isomorphism cycle/clique counts.
    5. Global SE (Graph Features): Informs the network of global graph topology. Graphs with similar spectrum or global invariants receive similar global SE. Examples: the kk lowest eigenvalues λk\lambda_k of the graph Laplacian or graph diameter/girth.
    6. Relative SE (Edge Features): Informs pairs of nodes of the structural differences between their neighborhoods. Examples: pairwise differences/gradients of local SE, or indicator booleans denoting co-membership in specific subgraphs (e.g., rings).

  5. Knowl 5 — Expressive Limitations of Standard MPNNs on Positional and Structural Encodings

    theoretical result

    Proposition 1. Assuming no modification applied to MPNNs for a learning task, there exist Positional Encodings (PE) and Structural Encodings (SE) which MPNNs are not guaranteed to learn.

    Standard message-passing neural networks (MPNNs) operating under 1-hop aggregation are bounded in expressive power by the 1-Weisfeiler-Leman (1-WL) graph isomorphism test. Consequently, MPNNs cannot learn certain topological invariants directly from raw graph structure without explicit PE or SE inputs:

    1. Circular Skip Link (CSL) Graphs: A pair of non-isomorphic regular graphs Gskip(11,2)G_{\text{skip}}(11, 2) and Gskip(11,3)G_{\text{skip}}(11, 3) cannot be distinguished by 1-WL or standard MPNNs because every node receives identical color updates. Supplying a global PE (e.g., Laplacian eigenvectors) assigns distinguishable initial features, while supplying a local SE (e.g., mm-step random walk diagonal diag((D−1A)m)\text{diag}((D^{-1}A)^m)) captures the cycle and skip-link differences, enabling complete graph differentiation.
    2. Decalin Molecular Graph: In the symmetric bicyclic Decalin structure, symmetric node pairs (such as nodes aa and bb, or cc and dd) are assigned identical colorings by 1-WL and local SE. As a result, candidate link prediction between pairs (a,d)(a, d) and (b,d)(b, d) yields identical embeddings. A distance-based relative PE or eigenvector-based global PE is necessary to break symmetry and distinguish between the two links.

  6. Knowl 6 — Edge Information Preservation and Graph Transformer Universality in GPS

    theoretical result

    In the GPS architecture, interleaving local MPNN layers with global self-attention allows the network to maintain universal function approximation on graphs while bypassing the need for explicit edge-bias attention tensors:

    1. Edge Information Propagation: For an MPNN layer with sum aggregation over neighbors Nu\mathcal{N}_u, huℓ+1=∑v∈Nuf(huℓ,hvℓ,euv)h_u^{\ell+1} = \sum_{v \in \mathcal{N}_u} f(h_u^\ell, h_v^\ell, e_{uv}), where node features huh_u are uniquely identifiable (e.g., via full Laplacian eigenvector positional encodings), there exists a function ff mapping each neighbor triplet to an encoding μuv=ouv⊗euv\mu_{uv} = o_{uv} \otimes e_{uv} (ouvo_{uv} being a unique edge identifier and euve_{uv} the edge attributes). The encoding μuv\mu_{uv} is invariant to node permutation and fully preserved under summation. Thus, subsequent global self-attention modules operating exclusively on node representations XX can implicitly recover connectivity and edge attributes without dense pairwise attention matrices.
    2. Universal Function Approximation: When supplied with the complete set of Laplacian eigenvectors as global positional encodings, the GPS architecture is a universal function approximator on graphs and can provide an approximate solution to the graph isomorphism problem, possessing strictly greater expressive capability than any Weisfeiler-Leman (kk-WL) isomorphism test given sufficient parameters.

  7. Knowl 7 — Computational Complexity and Scalability of GPS

    model/method

    The computational complexity of standard fully-connected graph transformers is O(N2)O(N^2) due to the materialization of dense all-pair attention matrices. GPS achieves linear complexity O(N+E)O(N + E) in the number of nodes NN and edges EE per layer:

    • The local MPNN branch operates strictly on real edges in the graph, with time and memory complexity O(E)O(E).
    • The global attention branch operates without explicit edge bias terms, enabling the use of linear attention mechanisms such as Performer or BigBird, which exhibit time and memory complexity O(N)O(N).
    • For sparse graphs (e.g., molecular graphs, citation networks, syntax trees, and knowledge graphs) where E=Θ(N)E = \Theta(N), the overall layer complexity is strictly linear in the number of nodes, O(N)O(N).

    This linear scaling allows GPS to train on large graphs (such as MalNet-Tiny with up to 5,000 nodes per graph) that are computationally intractable for dense O(N2)O(N^2) graph transformers.

  8. Knowl 8 — GPS Performance on Benchmarking-GNNs Suite

    data/table

    Performance of GPS compared to baseline MPNNs and graph transformers on five benchmarks from Dwivedi et al. (mean ±\pm standard deviation across 10 random seeds; top results highlighted in order of ranking):

    Model ZINC MNIST CIFAR10 PATTERN CLUSTER
    MAE ↓\downarrow Accuracy ↑\uparrow Accuracy ↑\uparrow Accuracy ↑\uparrow Accuracy ↑\uparrow
    GCN 0.367 0.011 90.705 0.218 55.710 0.381 71.892 0.334 68.498 0.976
    GIN 0.526 0.051 96.485 0.252 55.255 1.527 85.387 0.136 64.716 1.553
    GAT 0.384 0.007 95.535 0.205 64.223 0.455 78.271 0.186 70.587 0.447
    GatedGCN 0.282 0.015 97.340 0.143 67.312 0.311 85.568 0.088 73.840 0.326
    GatedGCN-LSPE 0.090 0.001 – – – –
    PNA 0.188 0.004 97.94 0.12 70.35 0.63 – –
    DGN 0.168 0.003 – 72.838 0.417 86.680 0.034 –
    GSN 0.101 0.010 – – – –
    CIN 0.079 0.006 – – – –
    CRaWl 0.085 0.004 97.944 0.050 69.013 0.259 – –
    GIN-AK+ 0.080 0.001 – 72.19 0.13 86.850 0.057 –
    SAN 0.139 0.006 – – 86.581 0.037 76.691 0.65
    Graphormer 0.122 0.006 – – – –
    K-Subgraph SAT 0.094 0.008 – – 86.848 0.037 77.856 0.104
    EGT 0.108 0.009 98.173 0.087 68.702 0.409 86.821 0.020 79.232 0.348
    GPS (ours) 0.070 0.004 98.051 0.126 72.298 0.356 86.685 0.059 78.016 0.180

    GPS sets the state-of-the-art on the ZINC benchmark with an MAE of 0.070, while placing within the top three models on MNIST, CIFAR10, PATTERN, and CLUSTER.

  9. Knowl 9 — GPS Performance on Open Graph Benchmark (OGB) Graph-Level Tasks

    data/table

    Performance of GPS compared to baseline GNNs and graph transformers on all four graph-level tasks from the Open Graph Benchmark (mean ±\pm standard deviation across 10 random runs):

    Model ogbg-molhiv ogbg-molpcba ogbg-ppa ogbg-code2
    AUROC ↑\uparrow Avg. Precision ↑\uparrow Accuracy ↑\uparrow F1 score ↑\uparrow
    GCN+virtual node 0.7599 0.0119 0.2424 0.0034 0.6857 0.0061 0.1595 0.0018
    GIN+virtual node 0.7707 0.0149 0.2703 0.0023 0.7037 0.0107 0.1581 0.0026
    GatedGCN-LSPE – 0.267 0.002 – –
    PNA 0.7905 0.0132 0.2838 0.0035 – 0.1570 0.0032
    DeeperGCN 0.7858 0.0117 0.2781 0.0038 0.7712 0.0071 –
    DGN 0.7970 0.0097 0.2885 0.0030 – –
    GSN (directional) 0.8039 0.0090 – – –
    GSN (GIN+VN base) 0.7799 0.0100 – – –
    CIN 0.8094 0.0057 – – –
    GIN-AK+ 0.7961 0.0119 0.2930 0.0044 – –
    CRaWl – 0.2986 0.0025 – –
    ExpC 0.7799 0.0082 0.2342 0.0029 0.7976 0.0072 –
    SAN 0.7785 0.2470 0.2765 0.0042 – –
    GraphTrans (GCN-VN) – 0.2761 0.0029 – 0.1830 0.0024
    K-Subtree SAT – – 0.7522 0.0056 0.1937 0.0028
    GPS (ours) 0.7880 0.0101 0.2907 0.0028 0.8015 0.0033 0.1894 0.0024

    GPS achieves competitive performance across molecular property prediction (molhiv, molpcba), biological interaction networks (ppa), and code AST token prediction (code2), achieving the top accuracy on ogbg-ppa (0.8015) and outperforming all previous Graph Transformer architectures across all four benchmarks (except SAT on code2).

  10. Knowl 10 — GPS Performance on Large-Scale Molecular Benchmark OGB-LSC PCQM4Mv2

    data/table

    Validation MAE and parameter counts on the large-scale PCQM4Mv2 dataset (predicting the HOMO-LUMO energy gap of 3.75M molecules):

    Model Test-dev MAE ↓\downarrow Validation MAE ↓\downarrow Training MAE # Param.
    GCN 0.1398 0.1379 n/a 2.0M
    GCN-virtual 0.1152 0.1153 n/a 4.9M
    GIN 0.1218 0.1195 n/a 3.8M
    GIN-virtual 0.1084 0.1083 n/a 6.7M
    GRPE 0.0898 0.0890 n/a 46.2M
    EGT 0.0872 0.0869 n/a 89.3M
    Graphormer n/a 0.0864 0.0348 48.3M
    GPS-small n/a 0.0938 0.0653 6.2M
    GPS-medium n/a 0.0858 0.0726 19.4M

    GPS-medium achieves a validation MAE of 0.0858, outperforming GRPE (0.0890), EGT (0.0869), and Graphormer (0.0864) with less than half the parameter budget (19.4M vs. 48.3M–89.3M). Unlike Graphormer, GPS utilizes solely 2D graph random-walk structural encodings (RWSE) rather than precomputed 3D spatial conformer distances.

  11. Knowl 11 — GPS Performance on the Long-Range Graph Benchmark (LRGB)

    data/table

    Evaluation of GPS on five long-range graph benchmark datasets under a strict parameter budget of approximately 500k parameters (mean ±\pm standard deviation across 4 runs):

    Model PascalVOC-SP COCO-SP Peptides-func Peptides-struct PCQM-Contact
    F1 score ↑\uparrow F1 score ↑\uparrow AP ↑\uparrow MAE ↓\downarrow MRR ↑\uparrow
    GCN 0.1268 0.0060 0.0841 0.0010 0.5930 0.0023 0.3496 0.0013 0.3234 0.0006
    GINE 0.1265 0.0076 0.1339 0.0044 0.5498 0.0079 0.3547 0.0045 0.3180 0.0027
    GatedGCN 0.2873 0.0219 0.2641 0.0045 0.5864 0.0077 0.3420 0.0013 0.3218 0.0011
    GatedGCN+RWSE 0.2860 0.0085 0.2574 0.0034 0.6069 0.0035 0.3357 0.0006 0.3242 0.0008
    Transformer+LapPE 0.2694 0.0098 0.2618 0.0031 0.6326 0.0126 0.2529 0.0016 0.3174 0.0020
    SAN+LapPE 0.3230 0.0039 0.2592 0.0158 0.6384 0.0121 0.2683 0.0043 0.3350 0.0003
    SAN+RWSE 0.3216 0.0027 0.2434 0.0156 0.6439 0.0075 0.2545 0.0012 0.3341 0.0006
    GPS (ours) 0.3748 0.0109 0.3412 0.0044 0.6535 0.0041 0.2500 0.0005 0.3337 0.0006

    GPS outperforms all MPNN and graph transformer baselines across four of the five LRGB benchmarks (PascalVOC-SP, COCO-SP, Peptides-func, and Peptides-struct).

  12. Knowl 12 — Ablation of Global Attention, MPNN Modules, and Encodings in GPS

    data/table

    Ablation results on component choices for GPS across four benchmark datasets (ZINC subset, PCQM4Mv2-subset, CIFAR10, and MalNet-Tiny):

    Ablation Category Component ZINC subset PCQM4Mv2-subset CIFAR10 MalNet-Tiny
    MAE ↓\downarrow MAE ↓\downarrow Acc. ↑\uparrow Acc. ↑\uparrow
    Global Attention None 0.070 0.1213 69.95 92.23
    Full Transformer 0.070 0.1159 72.31 93.50
    Performer 0.071 0.1142 70.67 92.64
    BigBird 0.071 0.1237 70.48 92.34
    Local MPNN None 0.217 0.3294 68.86 73.90
    GINE 0.070 0.1284 71.11 92.27
    GatedGCN 0.086 0.1159 72.31 92.64
    PNA 0.070 0.1409 73.42 91.67
    PE / SE None 0.113 0.1355 71.49 92.64
    RWSE 0.070 0.1159 71.96 92.77
    LapPE 0.116 0.1201 72.31 92.74
    SignNetMLP\text{SignNet}_{\text{MLP}} 0.090 0.1158 71.74 92.57
    SignNetDeepSets\text{SignNet}_{\text{DeepSets}} 0.079 0.1144 72.37 93.13
    PEGLapEig\text{PEG}_{\text{LapEig}} 0.161 0.1209 72.10 92.27

    Key takeaways from the ablation:

    1. Removing the local MPNN module causes severe degradation across all datasets (e.g., MAE on ZINC drops from 0.070 to 0.217; MAE on PCQM4Mv2 drops from 0.1159 to 0.3294), demonstrating that local message-passing is critical for graph representation learning.
    2. Incorporating a global attention module benefits tasks with long-range dependencies, with dense Transformer attention achieving the best predictive accuracy and Performer linear attention providing competitive performance with linear scalability.
    3. Random-walk structural encodings (RWSE) provide strong gains on molecular graphs (ZINC, PCQM4Mv2), while Laplacian eigenvector positional encodings (LapPE) and SignNet with DeepSets provide the largest gains on image superpixels and structural classification.

  13. Knowl 13 — Limitations of GPS and Graph Transformers

    limitation

    The authors identify the following limitations of graph transformers and the GPS framework:

    1. Hyperparameter Sensitivity: Graph Transformers exhibit high sensitivity to hyperparameters (such as learning rate schedules, layer configurations, and PE/SE dimensionalities), requiring careful dataset-specific tuning without a single universal configuration.
    2. Scarcity of True Long-Range Benchmarks: There is a recognized lack of large-scale graph datasets fundamentally requiring long-range dependency modeling where linear-attention architectures can fully showcase their scaling and performance advantages.

Coverage note — None was omitted; all key architectural principles, layer equations, algorithmic flows, theoretical propositions, encoding categorizations, empirical tables across all benchmark suites, ablation results, and limitations are fully covered.

References

  1. 1.Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2021.
  2. 2.Sebastian Andres, Jean-Dominique Deuschel, and Martin Slowik. Heat kernel estimates for random walks with degenerate weights. Electronic Journal of Probability, 21:1–21, 2016.
  3. 3.Dominique Beaini, Saro Passaro, Vincent Létourneau, Will Hamilton, Gabriele Corso, and Pietro Liò. Directional graph networks. In International Conference on Machine Learning, pages 748–758. PMLR, 2021.
  4. 4.Iz Beltagy, Matthew E. Peters, and Arman Cohan. Longformer: The long-document transformer. CoRR, abs/2004.05150, 2020.
  5. 5.Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang, Pietro Lio, Guido F Montufar, and Michael Bronstein. Weisfeiler and Lehman go cellular: CW networks. Advances in Neural Information Processing Systems, 34:2625–2640, 2021.
  6. 6.Giorgos Bouritsas, Fabrizio Frasca, Stefanos P Zafeiriou, and Michael Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
  7. 7.Xavier Bresson and Thomas Laurent. Residual Gated Graph ConvNets. arXiv:1711.07553, 2017.
  8. 8.Ivan Chelombiev, Daniel Justus, Douglas Orr, Anastasia Dietrich, Frithjof Gressmann, Alexandros Koliousis, and Carlo Luschi. Groupbert: Enhanced transformer architecture with efficient grouped structures. arXiv:2106.05822, 2021.
  9. 9.Dexiong Chen, Leslie O’Bray, and Karsten Borgwardt. Structure-aware transformer for graph representation learning. Proceedings of the 39th International Conference on Machine Learning, 2022.
  10. 10.Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. Advances in Neural Information Processing Systems, 2019.
  11. 11.Krzysztof Choromanski, Han Lin, Haoxian Chen, Tianyi Zhang, Arijit Sehanobish, Valerii Likhosherstov, Jack Parker-Holder, Tamas Sarlos, Adrian Weller, and Thomas Weingarten. From block-Toeplitz matrices to differential equations on graphs: towards a general theory for scalable masked transformers. arXiv:2107.07999, 2021.
  12. 12.Krzysztof Marcin Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamás Sarlós, Peter Hawkins, Jared Quincy Davis, Afroz Mohiuddin, Lukasz Kaiser, David Benjamin Belanger, Lucy J. Colwell, and Adrian Weller. Rethinking attention with performers. In 9th International Conference on Learning Representations, 2021.
  13. 13.Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. Advances in Neural Information Processing Systems, 33:13260–13271, 2020.
  14. 14.Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. arXiv:2012.09699, 2020.
  15. 15.Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv:2003.00982, 2020.
  16. 16.Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. In International Conference on Learning Representations, 2022.
  17. 17.Vijay Prakash Dwivedi, Ladislav Rampášek, Mikhail Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. Neural Information Processing Systems (NeurIPS 2022), Track on Datasets and Benchmarks, 2022.
  18. 18.Stéphane d’Ascoli, Hugo Touvron, Matthew L Leavitt, Ari S Morcos, Giulio Biroli, and Levent Sagun. Convit: Improving vision transformers with soft convolutional inductive biases. In International Conference on Machine Learning, pages 2286–2296. PMLR, 2021.
  19. 19.Peter Ertl and Ansgar Schuffenhauer. Estimation of synthetic accessibility score of drug-like molecules based on molecular complexity and fragment contributions. Journal of cheminformatics, 1(1):1–11, 2009.
  20. 20.Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
  21. 21.Scott Freitas, Yuxiao Dong, Joshua Neil, and Duen Horng Chau. A large-scale database for graph representation learning. In 35th Conference on Neural Information Processing Systems: Datasets and Benchmarks Track, 2021.
  22. 22.Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pages 1263–1272. PMLR, 2017.
  23. 23.Albert Gu, Karan Goel, and Christopher Re. Efficiently modeling long sequences with structured state spaces. In International Conference on Learning Representations, 2022.
  24. 24.Jianyuan Guo, Kai Han, Han Wu, Chang Xu, Yehui Tang, Chunjing Xu, and Yunhe Wang. CMT: Convolutional neural networks meet vision transformers. arXiv:2107.06263, 2021.
  25. 25.Kai Han, Yunhe Wang, Hanting Chen, Xinghao Chen, Jianyuan Guo, Zhenhua Liu, Yehui Tang, An Xiao, Chunjing Xu, Yixing Xu, et al. A survey on vision transformer. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
  26. 26.Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. arXiv:1905.12265, 2019.
  27. 27.Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open Graph Benchmark: Datasets for Machine Learning on Graphs. 34th Conference on Neural Information Processing Systems, 2020.
  28. 28.Weihua Hu, Matthias Fey, Hongyu Ren, Maho Nakata, Yuxiao Dong, and Jure Leskovec. OGB-LSC: A large-scale challenge for machine learning on graphs. In 35th Conference on Neural Information Processing Systems: Datasets and Benchmarks Track, 2021.
  29. 29.Md Shamim Hussain, Mohammed J Zaki, and Dharmashankar Subramanian. Global self-attention as a replacement for graph convolution. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 655–665, 2022.
  30. 30.Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pages 448–456. PMLR, 2015.
  31. 31.Paras Jain, Zhanghao Wu, Matthew Wright, Azalia Mirhoseini, Joseph E Gonzalez, and Ion Stoica. Representing long-range context for graph neural networks with global attention. Advances in Neural Information Processing Systems, 34, 2021.
  32. 32.Katikapalli Subramanyam Kalyan, Ajit Rajasekharan, and Sivanesan Sangeetha. Ammus: A survey of transformer-based pretrained models in natural language processing. arXiv:2108.05542, 2021.
  33. 33.Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv:1609.02907, 2016.
  34. 34.Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. In 8th International Conference on Learning Representations, 2020.
  35. 35.Ioannis Koutis and Huong Le. Spectral modification of graphs for improved spectral clustering. Advances in Neural Information Processing Systems, 32, 2019.
  36. 36.Devin Kreuzer, Dominique Beaini, William L. Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. In Advances in Neural Information Processing Systems, 2021.
  37. 37.Vitaly Kurin, Maximilian Igl, Tim Rocktäschel, Wendelin Boehmer, and Shimon Whiteson. My body is a cage: the role of morphology in graph-based incompatible control. arXiv:2010.01856, 2020.
  38. 38.Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. Advances in Neural Information Processing Systems, 33:4465–4478, 2020.
  39. 39.Derek Lim, Joshua Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. Sign and basis invariant networks for spectral graph representation learning. arXiv:2202.13013, 2022.
  40. 40.Shizhan Liu, Hang Yu, Cong Liao, Jianguo Li, Weiyao Lin, Alex X. Liu, and Schahram Dustdar. Pyraformer: Low-complexity pyramidal attention for long-range time series modeling and forecasting. In International Conference on Learning Representations, 2022.
  41. 41.Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Conference on Learning Representations, 2019.
  42. 42.Andreas Loukas. What graph neural networks cannot learn: depth vs width. In International Conference on Learning Representations, 2020.
  43. 43.Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. arXiv:1905.11136, 2019.
  44. 44.Grégoire Mialon, Dexiong Chen, Margot Selosse, and Julien Mairal. GraphiT: Encoding graph structure in transformers. arXiv:2106.05667, 2021.
  45. 45.Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and Leman go neural: Higher-order graph neural networks. In The Thirty-Third AAAI Conference on Artificial Intelligence, pages 4602–4609. AAAI Press, 2019.
  46. 46.Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. In International Conference on Machine Learning, pages 4663–4673. PMLR, 2019.
  47. 47.Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In International Conference on Learning Representations, 2020.
  48. 48.Wonpyo Park, Woonggi Chang, Donggeon Lee, Juntae Kim, and Seung won Hwang. GRPE: Relative positional encoding for graph transformer. arXiv:22201.12787, 2022.
  49. 49.Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of Machine Learning Research, 21(140):1–67, 2020.
  50. 50.Ryoma Sato. A survey on the expressive power of graph neural networks. arXiv:2003.04078, 2020.
  51. 51.Yu Shi, Shuxin Zheng, Guolin Ke, Yifei Shen, Jiacheng You, Jiyan He, Shengjie Luo, Chang Liu, Di He, and Tie-Yan Liu. Benchmarking graphormer on large-scale molecular modeling datasets. arXiv:2203.04810, 2022.
  52. 52.Yi Tay, Mostafa Dehghani, Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang, Sebastian Ruder, and Donald Metzler. Long range arena: A benchmark for efficient transformers. In International Conference on Learning Representations, 2021.
  53. 53.Jan Toenshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe. Graph learning with 1d convolutions on random walks. arXiv:2102.08786, 2021.
  54. 54.Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. arXiv:2111.14522, 2021.
  55. 55.Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in Neural Information Processing Systems, 30, 2017.
  56. 56.Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
  57. 57.Haorui Wang, Haoteng Yin, Muhan Zhang, and Pan Li. Equivariant and stable positional encoding for more powerful graph neural networks. In International Conference on Learning Representations, 2022.
  58. 58.Sinong Wang, Belinda Z. Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity. arXiv:2006.04768, 2020.
  59. 59.Boris Weisfeiler and Andrei Leman. The reduction of a graph to canonical form and the algebra which appears therein. NTI, Series, 2(9):12–16, 1968.
  60. 60.Scott A Wildman and Gordon M Crippen. Prediction of physicochemical parameters by atomic contributions. Journal of chemical information and computer sciences, 39(5):868–873, 1999.
  61. 61.Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
  62. 62.Mingqi Yang, Renjian Wang, Yanming Shen, Heng Qi, and Baocai Yin. Breaking the expression bottleneck of graph neural networks. IEEE Transactions on Knowledge and Data Engineering, 2022.
  63. 63.Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yan Liu. Do transformers really perform badly for graph representation? In Advances in Neural Information Processing Systems, 2021.
  64. 64.Chengxuan Ying, Mingqi Yang, Shuxin Zheng, Guolin Ke, Shengjie Luo, Tianle Cai, Chenglin Wu, Yuxin Wang, Yanming Shen, and Di He. First place solution of KDD Cup 2021 & OGB large-scale challenge graph prediction track. arXiv:2106.08279, 2021.
  65. 65.Jiaxuan You, Rex Ying, and Jure Leskovec. Design space for graph neural networks. In Advances in Neural Information Processing Systems, 2020.
  66. 66.Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontañón, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, and Amr Ahmed. Big Bird: Transformers for longer sequences. In Advances in Neural Information Processing Systems, 2020.
  67. 67.Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Labeling trick: A theory of using graph neural networks for multi-node representation learning. Advances in Neural Information Processing Systems, 34, 2021.
  68. 68.Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any GNN with local structure awareness. In International Conference on Learning Representations, 2022.

Citation

MLA
Rampášek, L., et al. “Recipe for a General, Powerful, Scalable Graph Transformer”. arXiv, 2022, http://arxiv.org/abs/2205.12454v4.
APA
Rampášek, L., Galkin, M., Dwivedi, V. P., Luu, A. T., Wolf, G., & Beaini, D. (2022). Recipe for a General, Powerful, Scalable Graph Transformer. arXiv. http://arxiv.org/abs/2205.12454v4
Chicago
Rampášek, L., M. Galkin, V. P. Dwivedi, A. T. Luu, G. Wolf, and D. Beaini. 2022. “Recipe for a General, Powerful, Scalable Graph Transformer”. arXiv. http://arxiv.org/abs/2205.12454v4.
Harvard
Rampášek, L. et al. (2022) “Recipe for a General, Powerful, Scalable Graph Transformer”, arXiv [Preprint]. Available at: http://arxiv.org/abs/2205.12454v4.
Vancouver
1. Rampášek L, Galkin M, Dwivedi VP, Luu AT, Wolf G, Beaini D (2022) Recipe for a General, Powerful, Scalable Graph Transformer. arXiv

BibTeX

@article{rampasek2022recipe,
  title = {Recipe for a General, Powerful, Scalable Graph Transformer},
  author = {Rampášek, Ladislav and Galkin, Mikhail and Dwivedi, Vijay Prakash and Luu, Anh Tuan and Wolf, Guy and Beaini, Dominique},
  year = {2022},
  journal = {arXiv},
  url = {http://arxiv.org/abs/2205.12454v4},
  eprint = {2205.12454}
}
Metadata:arXiv

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF
License: Authors