PaperlayerView exact revision on arXiv

Source-linked AI summary

Recipe for a General, Powerful, Scalable Graph Transformer

Ladislav Rampášek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, Dominique Beaini

arXiv:2205.12454v4cs.LG

TL;DR

Graph Transformers lack a common foundation for positional and structural encodings and are often limited by quadratic attention to small graphs. The paper proposes GPS, a modular architecture combining categorized encodings, local message passing, and linear global attention, and reports strong performance across 16 tasks. Its main scope boundaries are hyperparameter sensitivity and limited datasets that test long-range dependencies.

  • Problem

    Graph Transformers lack a principled framework for designing positional and structural encodings, while quadratic global attention limits them to small graphs.

  • Method

    GPS combines categorized positional and structural encodings with a hybrid local message-passing and global-attention layer, using linear attention mechanisms such as Performer or BigBird.

  • Results

    GPS outperformed every graph Transformer on 11 of 16 tasks and achieved state-of-the-art results on 8.

  • Takeaways & Limitations

    GPS provides a modular and scalable graph Transformer framework that supports graphs with several thousand nodes and combines multiple encoding and processing strategies.

  • Takeaways & Limitations

    Graph Transformers are sensitive to hyperparameters, and challenging datasets requiring long-range dependencies are lacking for demonstrating linear-attention scalability benefits.

Abstract

from arXiv · show

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 $\textit{local}$, $\textit{global}$ or $\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)$ 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 $\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.

1 Introduction

Graph Transformers address limitations of sparse message passing through global attention, but standard fully connected attention scales quadratically and restricts models to small graphs. GPS offers a modular recipe combining positional and structural encodings, local message passing, and scalable global attention.

  • O(N^2) global attention limits existing Graph Transformers to graphs with up to a few hundred nodes.
  • GPS defines embedding modules for positional and structural encodings and processing modules combining local message passing with global attention.
  • Positional and structural features can serve as local or global node features, while relative features contribute to edge features.
  • Efficient attention mechanisms such as Performer and BigBird avoid directly materializing the attention matrix, making explicit edge features in global attention nontrivial.
  • GPS combines positional and structural encodings, local message passing, and global attention in a general, powerful, scalable blueprint.

2 Related Work

Related work includes Graph Transformers, positional and structural encodings, and linear attention mechanisms. GPS is situated among efforts to improve graph expressivity and extend Transformer-style processing to larger graphs.

  • Graph Transformers use global attention to address over-smoothing, over-squashing, and expressiveness limitations associated with message-passing networks.
  • Prior graph encoding research includes Laplacian, shortest-path, degree-centrality, kernel-distance, random-walk, and structure-aware positional or structural encodings.
  • Figure 1 presents GPS as a modular Graph Transformer with examples of positional and structural encodings.
  • Linear Transformer research seeks attention mechanisms whose computational cost scales linearly with sequence length, including Linformer, Reformer, Longformer, Performer, and BigBird.

3 Methods

GPS is a modular graph Transformer recipe that combines positional and structural encodings with local message passing and global attention. Its design targets greater expressivity and scalability while retaining modularity across encoding and processing choices.

  • 3.1 Modular positional and structural encodings: GPS organizes positional and structural encodings into local, global, and relative categories for modular integration.The framework uses encodings as node-level features or relative edge features, depending on their role.
  • 3.1 Modular positional and structural encodings: GPS focuses empirical evaluations on global PE, relative PE, and local SE, leaving other presented encoding functions for future work.These selected encoding types are described as known to yield significant improvements.
  • 3.1 Modular positional and structural encodings: Positional encodings represent graph position or distance, whereas structural encodings represent graph or subgraph structure and structural similarity.The paper treats these objectives as distinct but complementary, even though one encoding may indirectly convey aspects of the other.
  • 3.3 GPS layer: an MPNN+Transformer hybrid: GPS achieves O(N + E) computational complexity by using linear global attention and restricting positional or structural encodings to real nodes and edges.Excluding edge features from global attention avoids materializing the quadratic attention matrix; the MPNN contributes O(E) complexity.
  • 3.2 Why do we need PE and SE in MPNN?: Global PE and local SE can distinguish circular skip-link graphs that standard 1-WL coloring and corresponding MPNNs fail to separate.Laplacian PE assigns unique initial node colors, while random-walk-based local SE captures differences in skip links.
  • 3.2 Why do we need PE and SE in MPNN?: Relative distance PE or eigenvector-based global PE can differentiate otherwise indistinguishable Decalin link-prediction candidates.The relevant node pairs receive the same 1-WL and local-SE treatment, but edge or global positional information separates the potential links.
  • 3.3 GPS layer: an MPNN+Transformer hybrid: Each GPS layer aggregates a local MPNN output with a global-attention output, followed by an MLP, while edge features enter only the MPNN branch.Both branches are modular: the MPNN acts on local neighborhoods and GlobalAttn can be any fully connected layer.
  • 3.3 GPS layer: an MPNN+Transformer hybrid: Rich PE/SE supports substructure identification and WL-level expressivity, while full connectivity addresses over-smoothing and over-squashing bottlenecks.The paper further states that, with appropriate components, GPS retains edge information and is a universal function approximator on graphs.

4 Experiments

GPS combines positional or structural encodings, local message passing, and global attention, with ablations and diverse benchmarks evaluating their contributions. It achieves strong results across small, large-scale, and long-range graph tasks while exposing dataset-dependent encoding effects and computational trade-offs.

  • 4.1 Ablation studies: RWSE provides consistent gains at relatively low computational cost, whereas SignNetDeepSets is the best-performing encoding but costs more computation.Encoding benefits depend on the dataset: RWSE helps molecular data, LapPE helps image superpixels, and SignNetDeepSets is broadly successful.
  • 4.1 Ablation studies: Removing the MPNN layer causes a major performance drop, while adding Transformer attention benefits most datasets without negative impact.The ablation compares the hybrid design against Transformer-only variants.
  • 4.2 Benchmarking GPS: GPS attains SOTA on ZINC and ranks second on three additional Benchmarking GNNs datasets, demonstrating strong performance across synthetic expressivity tasks.The benchmark covers ZINC, MNIST, CIFAR10, PATTERN, and CLUSTER, with results reported as means and standard deviations over 10 seeds.
  • 4.2 Benchmarking GPS: GPS ranks among the top three models on molpcba, ppa, and code2, and outperforms every other graph Transformer on all four OGB benchmarks except SAT on code2.On molhiv, GPS overfits but still outperforms SAN.
  • 4.2 Benchmarking GPS: GPS outperforms GRPE, EGT, and Graphormer on PCQM4Mv2 with less than half their parameters and significantly less training-set overfitting.It also improves over message-passing networks at comparable parameter budgets and uses graph-based RWSEs without precomputed approximate 3D conformer distances.
  • 4.2 Benchmarking GPS: 92.72% ± 0.7pp test accuracy is achieved on MalNet-Tiny with Performer attention, rising to 93.36% ± 0.6pp with Transformer attention at doubled runtime.Both configurations outperform the best reported GIN model at 90% accuracy; GPS also improves over all evaluated baselines on 4 of 5 LRGB datasets.

5 Conclusion

GPS provides a modular graph Transformer foundation that performs strongly across diverse benchmarks and scales to graphs with several thousand nodes. The authors identify hyperparameter sensitivity and limited long-range-dependency datasets as important boundaries.

  • GPS outperformed every graph Transformer on 11 of 16 tasks and achieved state-of-the-art results on 8 tasks.The evaluation covered 5 Benchmarking-GNN, 5 OGB(-LSC), 5 LRGB tasks, and MalNet-Tiny.
  • GPS scaled to graphs with several thousand nodes, far beyond any previous graph Transformer.
  • The Transformer, flexible message passing, and rich positional and structural encodings each contributed to GPS performance across benchmarks.
  • Limitations: Graph Transformers are sensitive to hyperparameters, with no one-size-fits-all solution across datasets.
  • Limitations: The available datasets lack challenging long-range-dependency tasks where linear attention could realize all its scalability benefits.

Checklist

The checklist records affirmative disclosures for claims, limitations, societal impacts, theoretical assumptions and proofs, experimental reproducibility, assets, and data considerations.

  • The paper states that its main claims accurately reflect its contributions and scope, and that it describes its limitations.
  • The paper reports discussing potential negative societal impacts and conforming to ethics review guidelines.
  • The paper states that it provides theoretical assumptions and complete proofs, with a proof sketch in Section 3.4 and more details in Appendix C.
  • Code, data, instructions, training details, configuration files, performance traces, and random-seed error bars are reported as available or described.
  • The paper reports compute resources and addresses licenses, new assets, consent, personally identifiable information, offensive content, and participant-study requirements.

A.1 Datasets description

The study evaluates GPS on molecular, image-derived, synthetic, protein, code, and malware graph benchmarks spanning node, edge, graph, classification, regression, and prediction tasks.

  • The benchmark overview covers datasets from Dwivedi et al., OGB, OGB-LSC, MalNet-Tiny, and LRGB.
  • Molecular datasets: ZINC contains 12K molecular graphs with 9–37 nodes for constrained-solubility regression using a 10K/1K/1K split.
  • Structural datasets: ogbg-code2 uses Python abstract syntax trees to predict the first five subtokens of function names, truncating trees above 1,000 nodes.
  • Molecular datasets: PCQM4Mv2 predicts the HOMO-LUMO gap, while ogbg-molhiv and ogbg-molpcba perform molecular property classification.
  • Large and structural datasets: MalNet-Tiny contains 5,000 structure-only function-call graphs of up to 5,000 nodes for software-type prediction.
  • LRGB datasets: LRGB includes superpixel node-classification datasets, 3D-contact link prediction, and peptide functional and structural prediction tasks.

A.2 Dataset splits and random seeds

The experiments follow standard dataset splits and generally report repeated-seed means and standard deviations, while evaluation and hyperparameter procedures vary by dataset and resource constraints.

  • Splits and seeds: All benchmarks use standard train/validation/test splits, with mean performance and standard deviation reported across multiple random seeds.
  • Splits and seeds: Main results use 10 runs except PCQM4Mv2, which uses one seed, and LRGB, which uses four seeds.
  • Splits and seeds: Ablation studies use four seeds, or three for PCQM4Mv2-Subset and MalNet-Tiny, and are run independently from the main experiments.
  • Hyperparameters: The hyperparameter search was not exhaustive; choices were extrapolated from ablations and refined through one-parameter-at-a-time line searches.
  • Experimental configuration: Experiments use dataset-specific parameter budgets, listed hyperparameters, and runtime measurements including encoding precomputation and epoch timing.
  • Experimental configuration: Runtime measurements were affected by shared-resource variation, so ablations used NVIDIA A100 nodes for greater consistency.

B Detailed ablation studies

The appendix reports detailed GPS ablations that vary one model component at a time while keeping other hyperparameters fixed, across seven benchmark settings.

  • Ablation studies vary one MPNN, self-attention, or positional/structural encoding component at a time.The remaining GPS hyperparameters are held at the best selected architecture for each dataset.
  • The reported ablation settings cover ZINC and a 10% PCQM4Mv2 subset.
  • Additional ablations cover MalNet-Tiny, CIFAR10, and PascalVOC-SP.The PascalVOC-SP table reports mean ± s.d. over 4 runs.
  • The appendix also evaluates ablations on Peptides-func from LRGB.The Peptides-func table reports mean ± s.d. over 4 runs.

C.1 Why do we need PE and SE?

PE and SE are needed because standard MPNNs are limited by 1-WL-level expressivity and cannot reliably distinguish some graph structures or node relationships. The section motivates encodings that provide global, local, or relative information and describes how GPS combines them with local message passing and global attention.

  • 1-WL and MPNN limitations: 1-WL iteratively updates node colors from 1-hop neighborhoods, and MPNNs are at most as powerful as this test.The final color histogram distinguishes graphs only when the histograms differ.
  • 1-WL and MPNN limitations: Standard MPNNs therefore cannot distinguish a wide variety of non-isomorphic graphs.
  • CSL and Decalin examples: In CSL graph pairs, 1-WL and MPNNs assign identical colors, whereas global PE can assign unique node colors and distinguish the graphs.
  • CSL and Decalin examples: In Decalin, 1-WL, MPNNs, and local SE can give the same embedding to two candidate links, while distance-based relative PE or global PE differentiates them.
  • Theoretical motivation: The proposition states that, without modification, MPNNs are not guaranteed to learn some positional or structural encodings.
  • Preserving edge information: GPS combines local message passing with global attention so edge information can be propagated to nodes and used when computing attention between nodes.
  • GPS encoding pipeline: The GPS pipeline supports positional and structural encodings on nodes or edges through separate node and edge encoders.Relative encodings are assigned to edges; otherwise encodings are assigned to nodes, and the encoded features are combined with inputs.
Loading 2205.12454v4…