Alessio Borgi

Alessio Borgi

PhD in Graph Neural Networks and Generative AI 👨🏻‍💻🤖

Transformers Are GNNs on Fully Connected Graphs

6 minute read

Published:

TL;DR: A Graph Attention Network computes attention over a node's neighbours. A Transformer computes attention over every token. Written in the same notation, the equations differ in exactly one symbol — \(\mathcal{N}_i\) against \(\mathcal{S}\). So a Transformer is a GNN whose graph happens to be complete, and a GAT is a Transformer whose attention has been masked by an adjacency matrix. This chapter does the substitution carefully, then flags two places where "identical" is stronger than the mathematics supports.

The two update rules

Self-attention. For token \(i\) in a sentence \(\mathcal{S}\):

\[ h_i^{\ell+1} = \sum_{j \in \mathcal{S}} w_{ij} \cdot W_V^{\ell} h_j^{\ell}, \qquad w_{ij} = \operatorname{softmax}_{j \in \mathcal{S}}\bigl(W_Q^{\ell} h_i^{\ell} \cdot W_K^{\ell} h_j^{\ell}\bigr). \]

Graph attention. For node \(i\) with neighbourhood \(\mathcal{N}_i\), the message function is

\[ \psi\bigl(h_i^{\ell}, h_j^{\ell}\bigr) = \frac{\exp\bigl(W_Q^{\ell} h_i^{\ell} \cdot W_K^{\ell} h_j^{\ell}\bigr)} {\sum_{j' \in \mathcal{N}_i} \exp\bigl(W_Q^{\ell} h_i^{\ell} \cdot W_K^{\ell} h_{j'}^{\ell}\bigr)} \cdot W_V^{\ell} h_j^{\ell}, \qquad h_i^{\ell+1} = h_i^{\ell} + \sum_{j \in \mathcal{N}_i} \psi\bigl(h_i^{\ell}, h_j^{\ell}\bigr). \]

Put them side by side and the only structural difference is the index set the softmax normalises over and the sum runs across. Replace \(\mathcal{N}_i\) with \(\mathcal{S}\) and you have self-attention. Replace \(\mathcal{S}\) with \(\mathcal{N}_i\) and you have a GAT.

The substitution in one sentence: attention is message passing in which the message from \(j\) to \(i\) is a learned scalar weight times a learned linear transform of \(h_j\), and the aggregator is a sum. Self-attention is that operator on the complete graph.

Verified, on three tokens

Take three tokens with attention scores \(s_{ij}\) given directly (rows \(= i\)):

\[ S = \begin{pmatrix} 2 & 1 & 0 \\ 1 & 2 & 1 \\ 0 & 1 & 2 \end{pmatrix}, \qquad V = \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ 1 & 1 \end{pmatrix}. \]

As a Transformer, each token attends to all three:

tokenattention weightsoutput
0(0.6652, 0.2447, 0.0900)(0.7553, 0.3348)
1(0.2119, 0.5761, 0.2119)(0.4239, 0.7881)
2(0.0900, 0.2447, 0.6652)(0.7553, 0.9100)

As a GAT on the path graph \(0 - 1 - 2\) (with self-loops), each node attends only to its neighbours:

nodeneighbourhoodattention weightsoutput
0\(\{0,1\}\)(0.7311, 0.2689, 0)(0.7311, 0.2689)
1\(\{0,1,2\}\)(0.2119, 0.5761, 0.2119)(0.4239, 0.7881)
2\(\{1,2\}\)(0, 0.2689, 0.7311)(0.7311, 1.0000)

Two things to read off. Node 1 is adjacent to everything, so its row is identical in both tables — locality is only a constraint where it actually removes something. And computing the GAT instead as global attention with \(-\infty\) on non-edges reproduces the GAT table exactly, to machine precision.

So masking is the whole difference. A GAT is a Transformer with an attention mask given by the adjacency matrix. Set the mask to all-ones and you recover full self-attention — I checked this collapse numerically and it is exact, not approximate. This is why modern graph libraries implement GATs as masked attention kernels rather than as gather-scatter loops.

Where “identical” overstates it

The equivalence is real, and two details are usually glossed. Neither breaks the argument; both matter if you are implementing or reasoning precisely.

The message function is not pairwise. The message-passing template says \(m_{ij} = \psi(h_i, h_j)\) — a function of two nodes. But the attention weight has a softmax denominator summing over the entire neighbourhood, so the message from \(j\) to \(i\) depends on every other neighbour of \(i\) as well. Written honestly it is \(\psi\bigl(h_i, h_j; \{h_{j'}\}_{j' \in \mathcal{N}_i}\bigr)\). Attention-based GNNs therefore sit slightly outside the strict pairwise formulation, in a class sometimes distinguished as anisotropic message passing. The three-step template still applies; step 1 is just doing more than the notation admits.

The surrounding layer is not the same. The attention cores match. The layers around them do not, in practice. A Transformer layer wraps attention in a residual connection, layer normalisation, and a token-wise MLP:

\[ h_i^{\ell+1} = \operatorname{MLP}\Bigl( \operatorname{LayerNorm}\bigl( h_i^{\ell} + \textstyle\sum_{j \in \mathcal{S}} \psi(h_i^{\ell}, h_j^{\ell}) \bigr) \Bigr). \]

A standard GAT layer has the residual but typically no token-wise feedforward block. That block is not a detail: it holds more learnable parameters than the attention mechanism does. So “Transformers are GNNs” is precise about the aggregation operator and loose about the layer, and most of a Transformer’s parameters live in the part the equivalence does not cover.

A third simplification, stated by the paper itself: the scores above omit the \(1/\sqrt{d_k}\) factor from real scaled dot-product attention. It changes nothing structurally — it is a variance correction, covered in the Transformers book — but the equations as written are a simplified attention, not the deployed one.

What the equivalence buys you

A Transformer has no graph, and that is a choice with two edges. Committing to a sparse graph is an inductive bias: helpful when the structure is real, harmful when it is wrong or incomplete. The pathologies Book II documents — oversmoothing and oversquashing — are consequences of forcing information through a fixed sparse topology. A complete graph has no bottleneck to squash through. It also has no prior, so everything must be learned from data.

Positional encodings are how you put the structure back, softly. A Transformer given no positional information cannot tell one ordering of its input from another — it is a set model. Positional encodings inject order as a feature rather than as an architectural constraint, so the model can use it or ignore it. That idea transfers directly to graphs: encode structural information (Laplacian eigenvectors, random-walk statistics, shortest-path distances) as node features and hand them to a Transformer. This is the recipe behind Graph Transformers, which combine local message passing with global attention.

GATs and Transformers are one implementation. If your framework has a fast masked-attention kernel, you have a fast GAT.

✅ Key Takeaways

  • Self-attention and graph attention differ in one symbol: the index set the softmax normalises over. \(\mathcal{S}\) gives a Transformer, \(\mathcal{N}_i\) gives a GAT.
  • Verified on three tokens: computing a GAT as global attention masked with \(-\infty\) on non-edges reproduces local attention exactly, and an all-ones mask recovers full self-attention.
  • A node adjacent to everything has an identical row either way — locality only constrains where it actually removes candidates.
  • The message function is not truly pairwise: the softmax denominator makes every message depend on the whole neighbourhood.
  • The equivalence covers the attention core, not the full layer. The token-wise MLP — which holds more parameters than attention — has no GAT counterpart.
  • No graph means no structural prior and no bottleneck. Positional and structural encodings put the information back as features rather than as constraints, which is what Graph Transformers do.

References

You May Also Enjoy

The Standard Library Modules Worth Knowing Before You pip install

8 minute read

Published:

Python ships with a counter, a queue, a memoiser, a CLI parser, a test framework’s smaller cousin, and a JSON-safe date library already installed — most of what people reach for a package to solve is one import away.

Files and Context Managers: Why with Is Not Optional

9 minute read

Published:

A file object that falls out of scope without with does get closed eventually — but ‘eventually’ means whenever the garbage collector gets around to it, which is not a promise any program handling more than a handful of files can live with.

Errors and Exceptions: EAFP, the Hierarchy, and Reading a Traceback

9 minute read

Published:

Exceptions in Python are not exceptional. They are a normal control-flow mechanism that the language leans on so heavily that the idiomatic style is to try the operation and handle the failure, rather than check first — which is faster, shorter, and free of race conditions.