PaperlayerView exact revision on arXiv

Source-linked AI summary

Attending to Graph Transformers

Luis Müller, Mikhail Galkin, Christopher Morris, Ladislav Rampášek

arXiv:2302.04181v3cs.LGcs.AIcs.NE

TL;DR

Graph transformers have emerged as alternatives to message-passing GNNs, whose local-structure bias and associated limitations motivate interest in global information modeling. This paper organizes architectures and encodings, reviews theoretical properties, and probes graph-property recovery, heterophily, and over-squashing; its findings show benefits in these settings but do not resolve over-squashing.

  • Problem

    Graph transformers are often claimed to outperform GNNs and better capture long-range dependencies, but principled explanations and clear understanding of their encodings remain limited.

    Source: §1 · p. 1, §5 · p. 12

  • Method

    The paper develops a taxonomy of graph transformers, surveys theory and encodings, and empirically probes graph-property recovery, heterophily, and over-squashing.

    Source: §1 · p. 2

  • Results

    Different encodings and architectural choices drastically affect predictive performance; graph transformers handle heterophilic graphs and mitigate over-squashing only to some extent.

    Source: §6 · p. 12, §4.3 · p. 12

  • Takeaways & Limitations

    The authors offer the taxonomy, theoretical overview, and experiments as a handbook for graph-transformer and broader graph-machine-learning research.

    Source: §1 · p. 2

    A principled explanation of graph-transformer performance claims and a clearer understanding of structural and positional encodings remain outstanding.

    Source: §5 · p. 12

Abstract

from arXiv · show

Recently, transformer architectures for graphs emerged as an alternative to established techniques for machine learning with graphs, such as (message-passing) graph neural networks. So far, they have shown promising empirical results, e.g., on molecular prediction datasets, often attributed to their ability to circumvent graph neural networks' shortcomings, such as over-smoothing and over-squashing. Here, we derive a taxonomy of graph transformer architectures, bringing some order to this emerging field. We overview their theoretical properties, survey structural and positional encodings, and discuss extensions for important graph classes, e.g., 3D molecular graphs. Empirically, we probe how well graph transformers can recover various graph properties, how well they can deal with heterophilic graphs, and to what extent they prevent over-squashing. Further, we outline open challenges and research direction to stimulate future work. Our code is available at https://github.com/luis-mueller/probing-graph-transformers.

1 Introduction

Graph transformers have emerged as an alternative to graph neural networks, with promising results often attributed to their ability to model global information. This section introduces a taxonomy and research agenda, then sets out the transformer and graph-neural-network background needed to understand it.

1 Introduction

  • Graph transformers have shown promising performance, while their advantage over standard GNNs is often attributed to GNNs’ local-structure bias and difficulty capturing long-range information.The paper notes that graph awareness in transformers requires structural and positional encodings.Source: §1 · pp. 1–2
  • The paper organizes graph-transformer architectures, surveys their theoretical properties and encodings, probes graph-property recovery, heterophily, and over-squashing, and outlines open challenges.The authors present this work as a handbook for the graph-machine-learning community.Source: §1 · p. 2
  • Earlier surveys offered high-level or domain-specific coverage, while this paper distinguishes itself by treating theoretical and practical shortcomings and newer architectures.Rampášek et al. (2022) focus on empirically effective architecture design rather than a detailed, principled literature overview.Source: §1 · p. 2

1.1 Background

  • Graph models ideally respect symmetries: equivariance transforms outputs with inputs, while invariance leaves outputs unchanged under the transformation.The paper notes that such symmetry-respecting models can be expected to generalize better.Source: §1.1 · p. 2
  • Transformer attention can be viewed as weighted aggregation over a complete graph, whereas GNN layers aggregate local-neighborhood information.The attention weights represent each node’s importance in the sum aggregation.Source: §1.1 · p. 3

2 The Landscape of Graph Transformers

The taxonomy organizes graph transformers by theoretical properties, encodings, input features, tokenization, and message propagation. Across these design choices, capturing graph structure depends on suitable encodings, while tokenization and attention choices shape computational cost and scope.

2 The Landscape of Graph Transformers

  • The taxonomy covers theoretical properties, structural and positional encodings, input features, graph tokenization, message propagation, and applications.It also discusses extensions for geometric features such as 3D molecular coordinates.Source: §2 · pp. 3–4

2.1 Theoretical Properties

  • Without sufficiently expressive structural or positional encodings, general graph transformers capture no graph structure beyond node count and match DeepSets-like expressive power.With maximally expressive structural bias, they can approximate any function, but that is equivalent to solving graph isomorphism; GNNs with the same encodings have the same expressive power.Source: §2.1 · p. 4
  • Higher-order transformers can simulate k-IGNs, connecting transformer architectures to the k-WL hierarchy; under mild assumptions, GNNs with a virtual node can simulate graph transformers.These relationships are described through results connecting k-IGNs and k-WL.Source: §2.1 · p. 4

2.2 Structural and Positional Encodings

  • Structural encodings describe local, relative, or global graph structure, whereas positional encodings represent nodes’ positions relative to other nodes.Examples include degrees and substructure counts for structural encodings, and Laplacian eigenvectors or pairwise distances for positional encodings.Source: §2.2 · p. 4
  • Node-order equivariance is straightforward for degree features but remains an active design challenge for more powerful adjacency- or Laplacian-eigenvector encodings.The paper identifies equivariant Laplacian-based encodings as ongoing work.Source: §2.2 · pp. 4–5

2.3 Input Features

  • Non-geometric GTs use vector-valued node and edge features, while geometric variants also support quantities such as 3D coordinates and must respect task-specific transformation symmetries.Molecular graph-level prediction calls for invariance; node-level tasks such as force-field prediction call for equivariance.Source: §2.3 · p. 5

2.4 Graph to Sequence Tokenization

  • Graph tokenization uses nodes, nodes plus edges, or patches and subgraphs as tokens, with different feature support and computational costs.Node-token attention costs O(n^2); node-and-edge tokens cost O((n + m)^2), while subgraph tokens can scale with the number of extracted subgraphs but may limit long-range capabilities.Source: §2.4 · pp. 5–6

2.5 Message Propagation

  • Message propagation ranges from structurally biased global attention to linear-scaling or reduced-scope attention and hybrids that combine local GNN-style and global attention.Global all-to-all attention is quadratic; kernelized mechanisms can scale linearly, while hybrid designs combine propagation schemes.Source: §2.5 · pp. 6–7

3 Applications of Graph Transformers

Graph transformers have been applied to brain networks, molecular property prediction, heterogeneous graphs, graph-to-sequence tasks, and other domains. These applications adapt structural encodings, equivariant operations, relation-specific attention, or locality to the task.

3 Applications of Graph Transformers

  • Brain Network Transformers use adjacency-matrix rows as structural encodings and module-aware pooling to predict brain-network properties, including disease presence.The paper reports that these encodings outperformed Laplacian-based encodings in previous studies.Source: §3 · p. 7
  • Equivariant transformer architectures for molecular quantum-mechanical properties encode atom types and atomic neighborhoods, then aggregate gated equivariant atom predictions into molecular predictions.The cited work includes Liao and Smidt (2023) and Thölke and Fabritiis (2022).Source: §3 · p. 7
  • For web-scale heterogeneous graphs, relation-specific projection matrices are used during attention; graph-to-sequence models also use Levi graphs and mask non-neighbors.The graph-to-sequence approach splits the Levi graph into subgraphs, learns node representations with transformers, and concatenates them.Source: §3 · p. 7
  • Other reported applications include rumor detection, crystal-property prediction, click-through-rate prediction, and 3D human-pose and mesh reconstruction.Source: §3 · p. 7

4 Experimental Study

The study evaluates prevalent graph-transformer approaches on structural-property recovery, heterophilic node classification, and a long-range interaction task, rather than attempting an exhaustive evaluation of all surveyed methods. Its results show benefits of structural bias and global attention in some settings, alongside dataset-dependent gains and limits in expressivity, generalization, and practical scope.

4 Experimental Study

  • The experiments probe structural awareness, heterophily, and over-squashing using selected prevalent methods, rather than evaluating every work in the taxonomy.The structural-awareness benchmark uses edge detection, triangle counting, and circular skip-link classification, with GIN as a 1-WL reference and an unmodified transformer as a baseline.Source: §4 · p. 7, §4.1 · p. 8

4.1 Structural Awareness of GTs

  • Structurally biased GTs generally perform well, with RWSE and Graphormer nearly solving Edges, Triangles-small, and CSL, but larger Triangles generalization is poor and Graphormer is capped at 90% on CSL.The benchmark uses three tasks of increasing structural-awareness difficulty, estimated from GIN performance, and includes a transformer without structural bias as a baseline.Source: §4.1 · pp. 8–9, Table 2 · p. 8

4.2 Reduced Over-smoothing in GTs?

  • On six small heterophilic datasets, transformer models outperform a 2-layer GCN and often Geom-GCN; adding global attention improves GPS, and removing its local GCN improves performance further.Graphormer performs comparably to Transformer models, while its shortest-path attention bias has no impact in these datasets.Source: Table 3 · p. 10, §4.2 · p. 11
  • On five large datasets, positional/structural encodings help in a dataset-dependent way, while adding Transformer or Performer modules generally does not improve performance.The full Transformer runs out of memory on the three largest datasets; Roman-Empire, the only dataset with diameter 6824, shows the largest improvements from encodings and Transformer modules.Source: Table 4 · p. 10, §4.2 · p. 11

4.3 Reduced Over-squashing in GTs?

  • On NeighborsMatch, the GT fits training examples perfectly through depth d = 6 and performs much better than GNN baselines, but the task is idealized and does not resolve over-squashing.The task requires long-range interaction between tree leaves and the root; its results demonstrate that global interaction can circumvent the specific problem posed by Alon & Yahav (2021).Source: §4.3 · pp. 11–12, Figure 2 · p. 11

5 Open Challenges and Future Work

The paper identifies unresolved theoretical questions about graph transformers (GTs), alongside practical limits in scaling, heterophily, edge-feature integration, and interpretation. It calls for clearer characterization of encodings and broader benchmarks to study model behavior.

5 Open Challenges and Future Work

  • GT claims about better prediction, long-range dependencies, and preventing over-smoothing or over-squashing still lack a principled explanation.The helpfulness and comparative properties of structural and positional encodings, and generalization to larger graphs, also remain unclear.Source: §5 · p. 12
  • Quadratic token-time limits GTs on truly large graphs, while incorporating edge features and domain knowledge into attention remains unresolved.The experiments also identify heterophily as an open challenge for GTs, including local GNN-like hybrid models.Source: §5 · p. 12
  • Attention scores alone may be insufficient to explain GT performance; the paper advocates diverse property-focused benchmarks and notes that scaling-law research is nascent.The authors draw a parallel with NLP studies that developed tasks tailored to language-model capabilities.Source: §5 · p. 12

6 Conclusion

The paper presents a taxonomy of graph transformers and surveys their theoretical properties, encodings, input features, tokenization, propagation, and applications. Its experiments find that encodings and architectural choices affect predictive performance, while GTs handle heterophilic graphs and alleviate over-squashing to some extent.

6 Conclusion

  • The paper provides a taxonomy of graph transformers and overviews their theoretical properties and connections to structural and positional encodings.It also surveys input-feature handling, including 3D information, graph tokenization, information propagation, and applications.Source: §6 · p. 12
  • Different encodings and architectural choices drastically impact predictive performance; GTs handle heterophilic graphs and prevent over-squashing to some extent.The paper outlines open challenges and future work.Source: §6 · p. 12

A Dataset Details

The appendix describes datasets used in the experiments, covering non-geometric graph prediction and classification tasks. The tasks include product ratings, cell-level mine detection, worker bans, user activity, edge detection, triangle counts, graph classification, and node classification.

A Dataset Details

  • The appendix points to Table 5 for statistics of the datasets used in the experiments.Source: A Dataset Details · p. 18
  • Edges, derived from Zinc, is used for link prediction; the original molecular solubility targets are ignored.Source: A Dataset Details · p. 18
  • Triangles uses synthetic graphs to predict triangle counts, while CSL classifies regular cycle graphs by their skip-link length.Source: A Dataset Details · pp. 18–19
  • Actor, Cornell, Texas, Wisconsin, Chameleon, and Squirrel are node-classification datasets based on actor, webpage, and Wikipedia networks.Their targets are actor categories, webpage categories, and average monthly site traffic, respectively.Source: A Dataset Details · p. 19
  • Roman-Empire represents words and syntactic or sequential relations from a Wikipedia article; its task is predicting each word’s syntactic role.Source: A Dataset Details · p. 19
  • Amazon-Ratings predicts product ratings; Minesweeper predicts whether each grid cell contains a mine; Tolokers predicts which workers were banned.Questions predicts which users remained active at the end of a time span.Source: A Dataset Details · p. 19

B Experimental details

The experiments ran on one A100 GPU and used GraphGPS as their implementation base, with a separate implementation for over-squashing experiments. Experimental configurations vary across structural-awareness tasks and small versus large datasets.

B Experimental details

  • Experiments ran on a single A100 NVIDIA GPU with 80GB of GPU RAM, using GraphGPS as the implementation base.Over-squashing experiments instead used Alon and Yahav’s implementation; model layers apply convolution or attention, then a feed-forward network, with residual connections.Source: B Experimental details · p. 19
  • Table 5 provides statistics for the datasets used in the experiments.Source: Table 5 · p. 20
  • Structural-awareness experiments used six layers; GIN, Transformer, and GPS used batch normalization and mean pooling, while Graphormer used layer normalization and graph-token readout.The final prediction head also differed between these model groups.Source: B Experimental details · p. 20
  • For six small datasets, hyperparameters were selected by a grid search repeated ten times, choosing the best average validation performance.The search varied hidden dimension, dropout, and, where applicable, attention dropout.Source: B Experimental details · p. 20
  • For five large datasets, the experiments followed the cited dataset study’s hyperparameter selection and tuned only the number of layers.They used sum pooling and a linear final MLP head.Source: B Experimental details · p. 20
Loading 2302.04181v3…