Graph Attention Networks and Graph Transformers

A graph convolution weights a neighbour by degree: in GCN, node \(j\) contributes to node \(i\) in proportion to \(1/\sqrt{d_i d_j}\), a number fixed by the graph before any learning happens. In a citation network where one neighbour is a foundational paper and another is an off-topic self-citation, both count the same. Attention lets the model decide instead.

This concept assumes the aggregate-and-update template from graph neural networks and message passing, and it connects directly to the depth limits in over-smoothing and over-squashing, which global attention was partly invented to escape.

GAT and the static attention problem

The graph attention network computes a score for each edge, normalises over the neighbourhood, and aggregates (Veličković et al., 2017, Graph Attention Networks, arXiv:1710.10903):

Here \(h_i \in \mathbb{R}^F\) is node \(i\)'s feature vector, \(W\) a shared linear map, \(a\) a learned attention vector, and \(\|\) concatenation.

Brody, Alon and Yahav noticed a flaw in the order of operations (Brody et al., 2022, How Attentive are Graph Attention Networks?, ICLR, arXiv:2105.14491). Split \(a\) into halves \(a_1, a_2\). The argument to LeakyReLU is \(a_1^\top W h_i + a_2^\top W h_j\), and LeakyReLU is monotone, so the ranking of neighbours \(j\) is decided by \(a_2^\top W h_j\) alone. The query node's term is a constant shift. Every node therefore ranks a shared set of candidate neighbours in the same order, whoever is asking. They call this static attention, and show tasks GAT cannot fit even on training data.

GATv2 moves the nonlinearity inside:

Now \(h_i\) and \(h_j\) interact before the final projection, so the ranking can depend on the query. The change costs about the same compute, and the paper reports GATv2 outperforming GAT across 11 benchmarks; the bug had hidden for years because benchmark accuracy looked fine.

Graph transformers: attend to everything, then restore structure

GAT still attends only along edges, so it inherits message passing's limits: information travels one hop per layer and is compressed through bottlenecks. A graph transformer lets every node attend to every other node in each layer. The cost is immediate. Full attention over \(N\) nodes needs an \(N \times N\) matrix, and at \(N = 100{,}000\) that is \(10^{10}\) entries, about 40 GB in float32 for a single head of a single layer. Graph transformers therefore thrive on molecules with tens of nodes and struggle on web-scale graphs.

The subtler problem is that full attention is permutation-equivariant and ignores edges entirely: without extra input it sees a set, not a graph. Structure has to be injected, and the design space is mostly about how.

Laplacian eigenvector encodings give each node the entries of the \(k\) smallest non-trivial eigenvectors of the graph Laplacian, the graph analogue of sinusoidal positions (Dwivedi & Bresson, 2020, A Generalization of Transformer Networks to Graphs, arXiv:2012.09699). Eigenvectors are defined only up to sign, so \(k = 8\) eigenvectors have \(2^8 = 256\) equally valid sign assignments, and the model must not depend on the arbitrary one the solver returns. Dwivedi and Bresson randomly flip signs during training; SignNet and BasisNet build networks that are invariant to sign and to basis choice within repeated eigenvalues by construction (Lim et al., 2022, Sign and Basis Invariant Networks for Spectral Graph Representation Learning, arXiv:2202.13013).

Relative structural biases add a learned term to each attention logit. Graphormer adds a bias indexed by the shortest-path distance between the two nodes, plus a degree-based centrality embedding to each node, and reported strong results on the OGB Large-Scale Challenge (Ying et al., 2021, Do Transformers Really Perform Bad for Graph Representation?, NeurIPS, arXiv:2106.05234).

Hybrids stop choosing. GraphGPS runs a local message-passing layer and a global attention layer in parallel in every block, classifies encodings as local, global or relative, and with a linear-attention variant reaches \(O(N + E)\) cost (Rampášek et al., 2022, Recipe for a General, Powerful, Scalable Graph Transformer, NeurIPS, arXiv:2205.12454).

Positional encodings are also how graph transformers exceed the one-dimensional Weisfeiler-Lehman bound discussed in expressive power and the WL test: distances and eigenvectors carry information that neighbourhood colour refinement cannot compute.

Where the evidence disagrees

The Long-Range Graph Benchmark was built to show where message passing fails, and early results showed transformers well ahead. Tönshoff and colleagues retuned the message-passing baselines and found the gap was largely an artefact of suboptimal hyperparameters, alongside a feature normalisation issue and a flawed link-prediction metric implementation (Tönshoff et al., 2023, Where Did the Gap Go? Reassessing the Long-Range Graph Benchmark, arXiv:2309.00367). Global attention may still help on genuinely long-range tasks. The benchmark evidence that it does is weaker than the first round of papers suggested.

When it breaks

Quadratic memory is not negotiable at scale. Beyond tens of thousands of nodes, full attention needs sampling, clustering or linear attention, each of which approximates away part of what made global attention attractive.

Eigendecomposition is expensive and unstable. Exact eigenvectors of a dense Laplacian cost \(O(N^3)\), and when eigenvalues are close or repeated, tiny edits to the graph can rotate the eigenvectors substantially, so encodings do not transfer cleanly between similar graphs.

Attention weights are not explanations. A high \(\alpha_{ij}\) says a message was weighted heavily, not that it changed the prediction.

Attention does not repair heterophily for free. Learned neighbour weights can downweight dissimilar neighbours, but GAT still averages within the neighbourhood, so on graphs where neighbours systematically carry opposite labels it can remain worse than a model that ignores the graph.