Graph Transformers

Slide 3 recalls the GNN design space from Lecture 4 (You, Ying, Leskovec, NeurIPS 2020): (1) message, (2) aggregation, (3) layer connectivity, (4) graph augmentation, (5) learning objective. The figure shows an input graph, a two-layer computation graph with message and aggregation boxes, and the objective on top.

Slide 4 asks the lecture's question: we know a lot about the GNN design space — what does the corresponding design space for graph transformers look like? (Left: the GNN design space; right: an empty box with a big question mark.)

Slide 6 shows a chatbot answer to "what is a transformer?": the model from "Attention Is All You Need" (Vaswani et al., 2017) with five ingredients — self-attention (each token attends to all others, so the whole input is processed at once rather than step by step like an LSTM), an encoder–decoder architecture (BERT uses only the encoder, GPT only the decoder), positional encoding (transformers do not know token order by themselves), multi-head attention, and feed-forward networks. Applications: language models (BERT, GPT, T5), vision (ViTs), and graphs. The point: transformers are the backbone of generative AI.

Slide 7 states the goal: bring the power of transformers to graphs. Examples: small molecules (drug structures), knowledge graphs (diseases, drugs, proteins, pathways), code graphs (syntax trees), communication networks. There is a lot of multi-billion node/graph-scale data to learn from.

Slide 8 gives the plan: Part 1 — introduce transformers and relate them to message-passing GNNs; Part 2 — a new design landscape for graph transformers; Part 3 — PEARL, learning efficient positional encodings with GNNs.

Slide 10: a transformer maps a 1D sequence of vectors to a 1D sequence of vectors. The figure feeds the sentence "The cat sat on the mat and sang" as inputs \(x_1,\dots,x_8\) and gets 8 output vectors.

Slide 11: the input vectors are called tokens; a token describes a "piece" of data, e.g. a word. What output sequence do we want?

• Option 1: next token (GPT). Output \(i\) predicts input \(i+1\): above "The" sits "cat", above "cat" sits "sat", and so on.
• Option 2: pool the outputs (e.g. sum-pool, slide 12) into one sequence-level embedding, used for classification. The figure predicts the label "kids story" for the whole sentence.

Slide 13 shows the transformer blueprint (the encoder–decoder diagram from Vaswani et al.: input embedding + positional encoding, then \(N\times\) blocks of multi-head attention and feed-forward layers, each with "Add & Norm"; the decoder adds masked multi-head attention, and a final linear + softmax gives output probabilities). Tokens are processed by many components: normalisation, feed-forward networks, positional encoding (more later), and multi-head self-attention. The key question: what does the self-attention block do?

Compare with GNNs: option 1 is like node-level prediction (one output per token), option 2 is like graph-level prediction with a readout/pooling.

Slides 14–17 follow the Illustrated Transformer tutorial (Jay Alammar) with two input words, "Thinking" (\(x_1\)) and "Machines" (\(x_2\)).

1. Step 1 (slide 15): for each input compute a query, key and value with three learned matrices (the model parameters): \[ \mathbf{q}_i=W^Q\mathbf{x}_i,\qquad \mathbf{k}_i=W^K\mathbf{x}_i,\qquad \mathbf{v}_i=W^V\mathbf{x}_i. \]
2. Step 2 (slide 16, just for \(x_1\)): compute a score between pairs, then turn scores into probabilities. Scores: \(\mathbf{q}_1\cdot\mathbf{k}_1=112\), \(\mathbf{q}_1\cdot\mathbf{k}_2=96\). Divide by \(\sqrt{d_k}=8\) (key dimension 64): 14 and 12. Softmax: 0.88 and 0.12. (Same for \(x_2\).)
3. Step 3 (slide 17): the new embedding is the probability-weighted sum of values: \(\mathbf{z}_1=0.88\,\mathbf{v}_1+0.12\,\mathbf{v}_2\).

Slide 18 does the same in matrix form. Stack inputs as rows of \(X\). Step 1: \(Q=XW^Q\), \(K=XW^K\), \(V=XW^V\). Steps 2–3 together:

with the softmax applied row by row.

Slide 19: multi-head self-attention. Do many self-attentions in parallel and combine them. Each head has its own parameters \(W_h^Q,W_h^K,W_h^V\), so different heads can learn different "similarities" between inputs. The figure uses 8 heads (0–7), producing \(Z_0,\dots,Z_7\); these are concatenated and multiplied by an output matrix \(W^O\) to give the final \(Z\). (In every encoder layer after the first, the input is the output \(R\) of the layer below rather than the word embeddings.)

Check yourself: with 112 and 96 before scaling, the softmax would give \(1/(1+e^{-16})\approx 1\) — almost all weight on \(\mathbf{v}_1\). Dividing by \(\sqrt{d_k}\) keeps the scores in a range where softmax is not saturated and gradients still flow.

Slide 20 compares transformers and GNNs. Similarity: GNNs also take a set of vectors (node features \(x_1,x_2,x_3\), in no particular order) and output a set of embeddings (\(z_1,z_2,z_3\)). Difference: GNNs use message passing; transformers use self-attention. Slide 21 asks: are these really different? (Left: a message-passing computation tree; right: the attention matrix computation.)

Slides 23–25 recall the attention formula with inputs stored row-wise in \(X\):

(the \(\sqrt{d_k}\) scaling is dropped for simplicity). This gives all tokens' outputs at once. Look at one token, \(x_1\):

Slide 26 rewrites this as the three steps of a GNN layer:

1. Message from \(j\): \((\mathbf{v}_j,\mathbf{k}_j)=\mathrm{MSG}(\mathbf{x}_j)=(W^V\mathbf{x}_j,\,W^K\mathbf{x}_j)\).
2. Query for 1: \(\mathbf{q}_1=W^Q\mathbf{x}_1\).
3. Aggregate all messages: \(\mathrm{Agg}\big(\mathbf{q}_1,\{\mathrm{MSG}(\mathbf{x}_j):j\}\big)=\sum_{j=1}^n\mathrm{softmax}_j(\mathbf{q}_1^\top\mathbf{k}_j)\,\mathbf{v}_j\).

Slide 27: so self-attention is a GNN. But which graph? Tokens are nodes; since token 1 receives messages from all other tokens, the graph is fully connected (the figure draws a complete graph on 5 nodes). If instead we only sum over \(j\in N(i)\), we get roughly GAT.

Slide 28 lists the takeaways:

• Takeaway 1: self-attention is a special case of message passing.
• Takeaway 2: it is message passing on the fully connected graph.
• Takeaway 3: given a graph \(G\), restricting the softmax to \(j\) adjacent to \(i\) gives ~GAT.

So what is gained by going "full"? Every pair of nodes can talk in one layer, so there is no over-squashing through bottleneck edges and long-range dependencies are one hop away. The cost: \(O(n^2)\) attention, and the graph structure disappears unless we put it back — the topic of Part 2.

Slide 31 repeats the question about the graph-transformer design space. Slide 32: we start with a graph (nodes with feature vectors). How do we input it into a transformer, which expects a sequence \(x_1,\dots,x_5\)?

Slide 33: to answer that, understand the key components of the transformer and make graph versions of each. Seen so far: (1) tokenising (input tokens) and (2) self-attention (the attention module).

Slides 34–36: one key piece is still missing. Recall \(\mathbf{z}_1=\sum_j\mathrm{softmax}_j(\mathbf{q}_1^\top\mathbf{k}_j)\mathbf{v}_j\). Key observation: the order of the tokens does not matter. The figure swaps tokens 1 and 2 ("cat The sat on …"): the outputs \(z_1,z_2\) swap places but otherwise do not change. In other words, self-attention is permutation equivariant.

Slide 37: this is a problem. After sum-pooling, both orders give identical outputs: the model makes the same prediction whatever the word order — it is a "bag of words" model. "The cat sat" and "sat cat The" look the same.

Slide 38: the fix is positional encoding. The transformer does not know the order of the inputs, so we add extra positional features telling it that "Je" is word 1, "suis" is word 2, and so on. The figure: each word embedding \(x_i\) gets a positional vector \(t_i\) added, giving the "embedding with time signal" that enters encoder #0. For NLP, positional encoding vectors are often learnable parameters.

Slide 39 updates the list of key components: (1) tokenising, (2) positional encoding, (3) self-attention. The figure shows tokens \(x_i\) plus positional encodings feeding into the self-attention transformer. Key question: what should these three be for a graph input?

For graphs, permutation equivariance is exactly what we want for the node order — node IDs are arbitrary. The real problem is different: with nodes as tokens, attention also ignores which nodes are connected. Positional encodings for graphs must carry structure, not a sequence index.

Slide 40: a graph transformer must take three kinds of input: (1) node features, (2) adjacency information, (3) edge features. The transformer has three components: (1) tokenising, (2) positional encoding, (3) self-attention.

Slide 41: there are many ways to do this; different approaches correspond to different "matchings" between graph inputs (1)(2)(3) and transformer components (1)(2)(3). Slide 42 shows today's matching with arrows: node features → tokens, adjacency information → positional encoding, edge features → self-attention.

Slide 43, Q1: what should the tokens be? The sensible idea: node features = input tokens. This matches the "attention is message passing on the fully connected graph" view — each node is a token.

Slide 44: problem — we completely lose adjacency information. The transformer sees a set of node feature vectors and nothing about edges. How do we inject adjacency?

Slides 45–46: idea — encode adjacency in the positional encoding of each node. The positional encoding describes where a node is in the graph; it is added to the node feature token (the figure shows a PE vector "+" each red token). Q2: how do we design a good positional encoding?

Slide 47 recalls last lecture's position encoding based on relative distances to anchors and anchor-sets. In the figure (two triangles joined by an edge), node \(v_1\) gets the encoding \((1,2,1)\) from its distances to anchors \(s_1,s_2\) and the size-2 anchor-set \(s_3\); \(v_3\) gets \((1,2,0)\). Anchors \(s_1,s_2\) alone cannot separate \(v_1\) and \(v_3\), but the anchor-set \(s_3\) can. Similar methods use random walks instead of shortest-path distances.

• This is a good idea; it works well in many cases.
• It is especially strong for tasks that require counting cycles.

Slide 48 adds a caveat: relative distances are useful for position-aware tasks, but not suited to structure-aware tasks. The figures show the barbell graph (two triangles joined by an edge) labelled two ways: by position (left triangle A, right triangle B) and by structural role (degree-2 nodes A, bridge nodes B on both sides). Distances to random anchors capture the first labelling, but mirror-image nodes with the same role get different distances, so the encoding does not reflect role.

Slide 49 asks: what other ways are there to build a positional encoding?

Slide 50: draw on graph theory. Key object: the Laplacian matrix \(L = D - A\) (degrees minus adjacency). Each graph has its own Laplacian; it encodes the graph's structure; several variants add degree information differently. Example, the 4-node path \(v_1-v_2-v_3-v_4\):

Slide 51: the Laplacian captures graph structure, and its eigenvectors inherit this structure. This matters because eigenvectors are vectors, so they can be fed into a transformer. Eigenvectors with small eigenvalues describe global structure; large eigenvalues describe local symmetries. (Refresher: \(L\mathbf{v}=\lambda\mathbf{v}\), \(L\) is \(n\times n\), \(\mathbf{v}\in\mathbb{R}^n\), \(\lambda\) a scalar. The figure, from Kreuzer, Beaini et al. 2021, colours a molecule-like graph by eigenvector entries: \(\lambda_1=0.037\) and \(\lambda_2=0.1\) vary smoothly across the whole graph; \(\lambda_{10}=\lambda_{11}=1.0\) vary locally.)

Slide 52, positional encoding steps:

1. Compute \(k\) eigenvectors (figure: \(k=3\)).
2. Stack them into an \(n\times k\) matrix.
3. Row \(i\) is the positional encoding of node \(i\); add it to node \(i\)'s feature token.

Slide 53 summarises and adds: Laplacian eigenvector PEs can also be used with message-passing GNNs, where they help for the same reasons as the structural and relative-distance encodings of the previous lecture.

Slide 54 repeats the cycle-detection experiment (predict YES if the graph has a cycle). With 5000 training samples: GIN 86.130±1.140 vs GIN-PE 99.570±0.089; GatedGCN 50.000±0.000 (chance, at every training size) vs GatedGCN-PE 99.725±0.027. With only 200 samples, GIN-PE reaches 86.720±3.376 and GatedGCN-PE 95.082±0.346.

Why do Laplacian eigenvectors help with cycles? They are global "coordinates" of the graph. In a tree, nodes far apart along the tree get very different coordinates; a cycle ties distant parts together and changes the eigenvectors in a way the model can see. And unlike constant features (Lecture 7), eigenvectors are not orthogonal to the hidden spectral components — they are those components.

Slide 55: so far, node features → tokens and adjacency → positional encoding. Slide 56: left to do — (3) edge features.

Slide 57: it is not clear how to put edge features into the tokens or the positional encoding. How about in the attention? In \(\mathrm{Att}(X)=\mathrm{softmax}(QK^\top)V\), the matrix \([a_{ij}]=QK^\top\) is \(n\times n\). Entry \(a_{ij}\) says how much token \(j\) contributes to the update of token \(i\). It is the only place where pairs of nodes appear — the natural place for pairwise (edge) information.

Slide 58, idea: adjust \(a_{ij}\) based on edge features. Replace

Slide 59, implementation (Graphormer: Ying et al., "Do Transformers Really Perform Bad for Graph Representation?", NeurIPS 2021):

• If there is an edge between \(i\) and \(j\) with features \(\mathbf{e}_{ij}\): \(c_{ij}=\mathbf{w}_1^\top\mathbf{e}_{ij}\), with learned \(\mathbf{w}_1\).
• If there is no edge: find the shortest path between \(i\) and \(j\), with edges \(\mathbf{e}^1,\mathbf{e}^2,\dots,\mathbf{e}^N\), and set \(c_{ij}=\sum_n\mathbf{w}_n^\top\mathbf{e}^n\), with learned \(\mathbf{w}_1,\dots,\mathbf{w}_N\) (one per position along the path).

Intuition: \(c_{ij}\) is a learned bias that says "these two nodes are connected through edges of this kind", so attention can prefer (or avoid) them. Because the bias is added before the softmax, it reshapes the attention distribution instead of overriding it.

In the Graphormer paper the path sum is averaged over the path length, and two more biases are used: a degree-based "centrality encoding" added to the node tokens and a learned bias per shortest-path distance ("spatial encoding"). The slides show only the edge part.

Slide 60 summarises the design space:

1. Tokenisation: usually node features. Other options exist, such as subgraphs, or node + edge features (not discussed today).
2. Positional encoding: relative distances or Laplacian eigenvectors. This gives the transformer the adjacency structure of the graph.
3. Modified attention: reweight attention using edge features.

Slide 61 places it next to the GNN design space. GNN: message, aggregation, layer connectivity, graph augmentation, learning objective. Graph transformer: input tokens, positional encoding, modified attention. Read the correspondence: tokens ↔ node features; positional encoding plays the role that the graph structure plays in message passing; modified attention ↔ message + aggregation with edge-aware weights.

Slide 64 recalls Laplacian eigenvector PEs: compute \(L=D-A\), take \(k\) eigenvectors, row \(i\) is the PE of node \(i\). Slide 65: they work — but is this the best we can do? (Hint: no.) The problem: eigenvectors are not arbitrary vectors. They have special structure that we have ignored, and we must account for it in our models.

Slide 66, sign ambiguity: if \(L\mathbf{v}=\lambda\mathbf{v}\), then also \(L(-\mathbf{v})=\lambda(-\mathbf{v})\). So \(-\mathbf{v}\) is an equally valid eigenvector (the figure draws \(\mathbf{v}_i\) and \(-\mathbf{v}_i\) as opposite arrows). The choice of sign is arbitrary.

Slides 67–69: when we use eigenvectors as PEs, we pick one sign arbitrarily (the eigensolver decides). Why does this matter? If we had picked the other sign, the input PE changes, so the model's predictions change. With \(k\) eigenvectors there are \(2^k\) sign choices, so potentially \(2^k\) different predictions for the same input graph.

Slide 70, simple idea: randomly flip the signs during training (data augmentation), so the model learns not to use sign information. Issue: there are exponentially many sign choices, which is very hard to learn.

Slide 71, better idea: build a network that is invariant to sign choices (SignNet; Lim, Robinson et al., "Sign and Basis Invariant Networks for Spectral Graph Representation Learning"). Because it is invariant, predictions no longer depend on the sign choice.

Slide 72: there is still a problem with eigenvector PEs. (A1) computing eigenvectors has cubic complexity, \(O(n^3)\); (A2) storing them needs quadratic space. Can we do better? This motivates Part 3.

Sign is only the simplest ambiguity. When an eigenvalue is repeated (e.g. \(\lambda_{10}=\lambda_{11}=1.0\) in the figure of slide 51), any rotation of the eigenvectors inside that eigenspace is also valid — a "basis ambiguity" that BasisNet, in the same paper, addresses.

Slides 74–75 recall from Lecture 7 that GNNs are nonlinear functions of eigenvectors. With a single-layer MLP, the GIN update in matrix form is \(C^{(l+1)}=\sigma\big(\sum_{k=0}^1A^kC^{(l)}W_k^{(l)}\big)=\sigma\big(\sum_k V\Lambda^kV^\top C^{(l)}W_k^{(l)}\big)\) with \(A=V\Lambda V^\top\). Per node \(v\) and output feature \(f\):

So a GNN already builds combinations of eigenvectors — it could produce eigenvector-like positional encodings itself, without an eigendecomposition. But the weights depend on \(\langle\mathbf{v}_n,C^{(l)}[:,i]\rangle\).

Slide 76 recalls the catch: the WL colours inherit the graph symmetries (the hexagon pair \(\mathcal{G}\) vs pentagon pair \(\hat{\mathcal{G}}\) from Lecture 7), and symmetric colours hide parts of the spectrum.

Slide 77: can we break these symmetries? Standard approach: assign unique IDs to nodes and convert them to one-hot vectors. The figure: a 6-node graph with IDs 1–6; the node with ID 5 gets \([0,0,0,0,1,0]\) (total number of IDs = 6).

Slides 78–79 recall that one-hot IDs make computation graphs clearly different, but they are not scalable (\(O(N)\) feature dimensions) and not inductive (cannot generalise to new nodes/graphs).

Slide 80 (Kanatsoulis, Choi et al., "Learning Efficient Positional Encodings with Graph Neural Networks", ICLR 2025): can we learn powerful PEs with GNNs only? Still assign unique IDs, but represent them by random samples: each node gets a different set of random numbers. Example: node 3 gets \([0.2, 1.5, -2.3, -10.1]\); total number of random samples = 4.

Why random numbers instead of one-hot? A random vector is almost surely different for every node (so symmetry is broken), its dimension does not depend on \(N\) (scalable), and a new graph can be given new random values from the same distribution (inductive).

Slide 81 lists the random samples for the 6-node graph (A–F; edges A–B, A–C, B–C, A–D, C–E, C–F, E–F): A \([3.3,-1.7,-1.2,-0.1]\), B \([-0.1,-5.4,3.0,-9.8]\), C \([0.2,1.5,-2.3,-10.1]\), D \([0.5,1.9,-12.7,11.1]\), E \([5.1,-0.7,-2.9,-13.5]\), F \([-1.2,7.5,-0.3,-7.9]\).

Slides 82–84, independent processing of samples. Sample \(m\) uses the \(m\)-th number of every node as a 1-dimensional node feature:

• Sample 1 (slide 82): A=3.3, B=−0.1, C=0.2, D=0.5, E=5.1, F=−1.2 → GNN → \(\mathbf{y}^{(1)}\).
• Sample 2 (slide 83): A=−1.7, B=−5.4, C=1.5, D=1.9, E=−0.7, F=7.5 → the same GNN → \(\mathbf{y}^{(2)}\).
• … up to sample 4 (slide 84): A=−0.1, B=−9.8, C=−10.1, D=11.1, E=−13.5, F=−7.9 → \(\mathbf{y}^{(4)}\).

Each run is an ordinary message-passing GNN, but on inputs that break all symmetries, so each output \(\mathbf{y}^{(m)}\) can depend on the full structure.

Slides 85–86 give an approximate analogy: a survey. Sample one person per state (the US map as the "input graph") and ask them the same set of questions → answers \(\mathbf{y}^{(1)}\); repeat with other random people → \(\mathbf{y}^{(4)}\). Any single respondent is random, but the statistics over many samples describe each state stably. Slide 86 shows such a summary: a bar map with three bars (PW 1, PW 2, PW 3) in each state. Slide 87 repeats the processing picture.

Why averaging extracts structure — a short derivation (ours, connecting to Lecture 7). Let \(\mathbf{x}\) have i.i.d. zero-mean entries with variance \(s^2\). Then \(\mathbb{E}\big[x_v\,(A^k\mathbf{x})_v\big]=s^2\,(A^k)_{vv}\): the expectation of a product a GNN can form turns random inputs into closed-walk counts, the same structural features as \(\mathrm{diag}(A^k)\) in Lecture 7. A single sample is noisy; the average is not.

Slide 88: to keep the model inductive (and permutation equivariant), the final output is an expectation over the random samples,

Theorem: PEARL is strictly more expressive than the WL test. PEARL can count 7-node cycles with near-linear complexity. So a GNN can break the limits of the WL kernel and count important substructures — with no eigendecomposition.

Slide 89, PEARL in practice:

1. Sample node IDs from a probability distribution.
2. Process each set of node samples independently with a GNN.
3. Summarise the outputs by the empirical expectation (a pooling \(\rho[\cdot]\) giving the PE matrix \(P\)).
4. Concatenate the PEARL embeddings with the node features \(X\).
5. Pass through the main GNN or transformer as usual.
6. Backpropagate to train PEARL and the prediction model jointly.

The figure: the input graph's attributes (people, text) go straight to the main model; a copy with node attributes removed goes to the PEARL GNN (red box), whose output \(P\) is fed in alongside.

Slide 90: small-molecule property prediction — given a molecule (e.g. MBX-2982), predict its solubility. The bar chart shows mean absolute error for four positional encodings: No PE and Laplacian PE are the worst (Laplacian PE is no better than none), sign-invariant Laplacian PE roughly halves the error, and PEARL is the lowest — the slide reports a 60% reduction in test error (the arrow runs from the PEARL bar to the No PE / Laplacian PE bars).

Slide 91 summarises the lecture. Part 1: transformers = message passing on a fully connected graph. Part 2: new design landscape for graph transformers — tokenisation, positional encoding, modified self-attention. Part 3: PEARL, positional encodings for graph transformers. Slide 92 shows the final picture: the GNN design space next to the graph-transformer design space (input tokens, positional encoding, modified attention).