Designing Powerful Graph Encoders — Breaking the WL Limit

Slide 3 recalls the full pipeline (dataset split → input graph → GNN → node embeddings → prediction head → predictions, compared with labels through the loss function and evaluation metrics). Today's question sits inside the "GNN" box: can we make GNN representations more expressive?

Slide 5 runs a thought experiment. A \(K\)-layer GNN embeds a node from its \(K\)-hop neighbourhood structure (the figure shows a node, its neighbourhood, and the computation tree unrolled from it). A perfect GNN would build an injective function from neighbourhood structure (of any number of hops) to node embeddings.

Slide 6 splits "injective and well defined" into two rules (ignoring node attributes, i.e. all nodes have the same feature):

• Observation 1: same neighbourhood structure ⇒ same embedding. The figure shows two nodes \(v_1,v_2\) on identical triangles: \(\mathbf{h}_{v_1}=\mathbf{h}_{v_2}\).
• Observation 2: different neighbourhood structure ⇒ different embeddings. The figure shows \(v_1\) on a triangle and \(v_3\) on a square: we want \(\mathbf{h}_{v_1}\neq\mathbf{h}_{v_3}\).

Slide 7: Observation 2 often cannot be satisfied. The GNNs so far are bounded above by the WL test (previous lecture). Example: message-passing GNNs cannot count cycle length. \(v_1\) lives on a cycle of length 3, \(v_2\) on a cycle of length 4. Every node has degree 2, so the computation graphs of \(v_1\) and \(v_2\) are the same infinite binary-branching tree (the figure shows the identical trees).

Slide 8: Observation 1 can also be a problem. Two nodes may have the same neighbourhood structure, yet a task may want different embeddings because the nodes sit in different positions in the graph. These are position-aware tasks. Even a perfect GNN fails here. Figures: a grid graph with \(v_1\) at the bottom-left corner and \(v_2\) at the top-right corner (locally identical corners), and a NYC road network where two intersections look alike locally but are far apart.

Slide 9 is the plan. Fix Observation 2 by building GNNs more expressive than WL (structurally-aware GNNs). Fix Observation 1 by creating embeddings from positions (position-aware GNNs).

Slide 11: GNNs fail in structure-aware tasks at three levels — node, edge and graph. The cause is always the same: different inputs, but the same computational graph → the GNN fails.

• Node level (slide 12): node \(v_1\) on a triangle (label A) and node \(v_2\) on a square (label B). Their computation trees are equal (each node has two children, each child has two children, …), so any message-passing GNN gives them the same embedding.
• Edge level (slide 13): a path of six nodes, with \(v_1\) and \(v_2\) in the middle. We want to predict two candidate edges, A = \((v_0,v_1)\) and B = \((v_0,v_2)\), which share the endpoint \(v_0\). Edge predictions are built from the endpoint embeddings. Because \(v_1\) and \(v_2\) are symmetric in the path, their computation trees are equal, so edges A and B get the same score — although \(v_0\) is at distance 2 from \(v_1\) and distance 3 from \(v_2\).
• Graph level (slide 14): two different 8-node graphs A and B, drawn on an octagon with different chord patterns. Both are regular (every node has the same degree), so every node in both graphs has the same computation tree (the big radial trees in the figure). Pooling identical node embeddings gives identical graph embeddings.

Intuition: message passing only sees "how many neighbours of each colour", recursively. Regularity and symmetry make that information identical everywhere, so nothing distinguishes the inputs.

Slide 15 starts the spectral perspective. Two graphs:

• \(\mathcal{G}\): two hexagons sharing the edge E–F (10 nodes A…J).
• \(\hat{\mathcal{G}}\): two pentagons joined by the bridge E–F (also 10 nodes A…J).

The node colours are the WL colours. In both graphs E and F (degree 3) get the dark colour, C, D, G, H (neighbours of E/F) get a lighter colour, and A, B, I, J get white. The colourings are identical, so WL cannot tell the graphs apart. Two claims: WL colours inherit the graph symmetries, and symmetric colours are tied to limitations in the spectral decomposition of the graph.

Slides 16–18 recall the GIN update for colours (embeddings) \(\mathbf{c}_v\):

Take the MLP to be a single layer with pointwise activation \(\sigma\). Then (slide 16 keeps the \((1+\epsilon)\); slide 17 absorbs it into the weight):

Slide 18 points out two things: this is just GraphSAGE with sum aggregation, and the neighbour sum is a sparse matrix-vector multiplication. The next block makes that precise.

Why only one layer of MLP? Only the first linear layer touches the graph structure; later MLP layers act per node. So everything structural that the layer "knows" passes through this one linear map.

Slides 19–29 build one equation step by step on a 4-node path \(v_1 - v_2 - v_3 - v_4\). Its adjacency matrix (\(A[u,v]=1\) if \((u,v)\) is an edge, else 0) is

Stack all colours as rows of a matrix: \(C^{(l)}\in\mathbb{R}^{N\times d}\), with \(C^{(l)}[v,:]=\mathbf{c}_v^{(l)}\) (slide 20). Now look at the product \(AC^{(l)}\) row by row (slides 23–29, with the relevant entries boxed in red):

• Row 1 of \(A\) is \((0,1,0,0)\), so \(AC^{(l)}[1,:]=\mathbf{c}_{v_2}^{(l)}\) — the sum over \(N(v_1)=\{v_2\}\).
• Row 2 is \((1,0,1,0)\): \(AC^{(l)}[2,:]=\mathbf{c}_{v_1}^{(l)}+\mathbf{c}_{v_3}^{(l)}\).
• Row 3 is \((0,1,0,1)\): \(AC^{(l)}[3,:]=\mathbf{c}_{v_2}^{(l)}+\mathbf{c}_{v_4}^{(l)}\).
• Row 4 is \((0,0,1,0)\): \(AC^{(l)}[4,:]=\mathbf{c}_{v_3}^{(l)}\).

So row \(v\) of \(AC^{(l)}\) is exactly \(\sum_{u\in N(v)}\mathbf{c}_u^{(l)}\). The whole layer, for all nodes at once (slides 28–30), is

(Row vectors now multiply weights from the right, so \(W\) appears after \(C\).) The neat form \(\sum_k A^k C W_k\) says: one GIN layer is a degree-1 polynomial in \(A\) applied to the colours, followed by a pointwise non-linearity.

Slide 31: compute the eigendecomposition of the (symmetric) adjacency matrix:

• The spectral decomposition is a universal characterisation of the graph: it determines \(A\), so it contains everything about the graph.
• Different graphs have different spectral decompositions (different \(V\) and/or \(\Lambda\)).
• The number of cycles can be written as a function of eigenvalues and eigenvectors. The slide's example:

where \(|\mathbf{v}_n|^2\) means the element-wise square. Entry \(v\) of \(\mathrm{diag}(A^3)\) counts closed walks of length 3 from \(v\); each triangle through \(v\) gives 2 such walks (two directions), so triangles at \(v\) = \(\tfrac12(A^3)_{vv}\).

Slides 32–33 substitute \(A^k=V\Lambda^kV^\top\) into the GIN layer:

So the update depends on three things: the eigenvalues, the eigenvectors, and the dot products between the eigenvectors and the previous colours, \(V^\top C^{(l)}\) (boxed in red on slide 33). Intuition: the GNN first projects the colour signal onto each eigenvector ("frequency"), rescales each projection by \(\lambda_n^k\), and maps back.

Slide 34 recalls colour refinement (WL) on two graphs. Both start with all colours 1. After one round each node's new colour is (own colour, multiset of neighbour colours): labels such as "1,1111" (degree 4), "1,111" (degree 3), "1,11" (degree 2) and "1,1" (degree 1). The two graphs produce the same multiset of new colours, so this round cannot separate them.

Slide 35 explains why, spectrally. With uniform initial colours, \(C^{(0)}=\mathbf{1}\) (the all-ones vector), so the boxed term is

• The new colours depend only on eigenvectors that are not orthogonal to \(\mathbf{1}\). If \(\langle\mathbf{v}_n,\mathbf{1}\rangle=0\), the pair \((\lambda_n,\mathbf{v}_n)\) drops out of the layer.
• Graphs with symmetries admit eigenvectors orthogonal to \(\mathbf{1}\). An automorphism that swaps two parts of the graph creates eigenvectors that are "antisymmetric" (+ on one side, − on the other), and those sum to 0.

Small example: the 4-cycle has eigenvalues \(2,0,0,-2\). The eigenvector for \(-2\) is \((1,-1,1,-1)\), which is orthogonal to \(\mathbf{1}\). A GNN started from constant colours never sees it.

Slides 36–37 return to \(\mathcal{G}\) (two hexagons sharing an edge) and \(\hat{\mathcal{G}}\) (two pentagons joined by a bridge). The table lists each eigenvalue \(\lambda_n\) and its projection \(\langle\mathbf{v}_n,\mathbf{1}\rangle\):

Read it carefully. The spectra are different (e.g. \(\hat{\mathcal{G}}\) has 1.861, which slide 37 boxes in red; \(\mathcal{G}\) does not). So the graphs are different. But the eigenpairs with a nonzero projection on \(\mathbf{1}\) are the same in both: \((2.303, 3.048)\), \((1, -0.816)\), \((-1.303, -0.210)\). Every eigenpair that differs has projection 0. A GNN started from constant colours sees only the visible pairs, so it cannot distinguish \(\mathcal{G}\) from \(\hat{\mathcal{G}}\) — exactly what WL gives on slide 15.

Slide 38: the WL kernel also cannot count basic structures. Cycle counts, such as \(\mathrm{diag}(A^3)=\sum_n\lambda_n^3|\mathbf{v}_n|^2\), use all eigenpairs, including the hidden ones. Here \(\mathcal{G}\) has 6-cycles and \(\hat{\mathcal{G}}\) has 5-cycles, but that difference lives in the invisible part of the spectrum.

Slide 39 summarises:

• The limitations of WL are limitations of the initial node colour, and they are well understood in the spectral domain.
• Constant colourings are orthogonal to some adjacency eigenvectors, so critical spectral components (eigenvalues and eigenvectors) are omitted.
• At a high level, WL colours obey the same symmetries as the graph; these joint symmetries lock message passing into limited representations.

The conclusion points directly to the fix: change the input features so they are not orthogonal to the important eigenvectors.

Slide 41: what if we use eigenvectors as additional features? The key object is the Laplacian \(L = D - A\) (degree matrix minus adjacency). Each graph has its own Laplacian; it encodes the graph structure; several variants exist that add degree information differently (e.g. normalised Laplacians). For the 4-node path:

Slide 42: the Laplacian captures structure, and its eigenvectors inherit this structure. Recall an eigenvector is \(\mathbf{v}\) with \(L\mathbf{v}=\lambda\mathbf{v}\) (\(L\) is \(n\times n\), \(\mathbf{v}\in\mathbb{R}^n\), \(\lambda\) a scalar). Small eigenvalues ↔ global structure; large eigenvalues ↔ local symmetries. The figure (from Kreuzer, Beaini et al. 2021) colours a molecule-like graph by eigenvector values: for \(\lambda_1=0.037\) and \(\lambda_2=0.1\) the colour changes slowly across the whole graph (one side green, other side purple); for \(\lambda_{10}=\lambda_{11}=1.0\) the pattern is local, alternating within small rings.

Slide 43: feature augmentation steps.

1. Compute \(k\) eigenvectors \(\mathbf{v}_1,\dots,\mathbf{v}_k\) (the figure uses \(k=3\)).
2. Stack them as columns of an \(n\times k\) matrix.
3. Row \(i\) is a \(k\)-dimensional feature for node \(i\); append it to the node's input features.

Slide 44 tests this on a synthetic task: given a graph, predict YES if it has a cycle, NO otherwise. "PE" = augmented with Laplacian eigenvectors. Test accuracy (± s.d.), 4 layers:

GatedGCN without PE is at chance (50%) for every training size: it cannot detect cycles at all. With PE both models reach about 99.6–99.7% with 5000 samples, and are far better even with 200 samples, while adding only ~2% more parameters.

A caveat the slides do not dwell on: eigenvectors are defined only up to sign (and up to rotation inside a repeated eigenvalue, like \(\lambda_{10}=\lambda_{11}\) here). The same graph can give different PEs, so models usually randomly flip signs during training or use sign-invariant architectures.

Slide 46 states the reasoning we use for all feature augmentations. Two different inputs (nodes, edges, graphs) are labelled differently. A "failed" model always assigns them the same embedding; a "successful" model assigns different embeddings. Embeddings are determined by computation graphs. Example: nodes \(v_1\) (triangle, label A) and \(v_2\) (square, label B) — goal: different embeddings.

Slide 47: one-hot encoding. Give each node a different ID (e.g. 1000, 0100, 0010, 0001). Then the computation graphs are clearly different: the leaves of \(v_1\)'s tree repeat \(v_1\)'s own ID at depth 3 (the walk closes around the triangle), which never happens in the square tree. So we can always tell nodes, edges and graphs apart.

Slide 48: the issues.

• Not scalable: needs \(O(N)\) feature dimensions (\(N\) = number of nodes).
• Not inductive: cannot generalise to new nodes or graphs (and IDs depend on an arbitrary node ordering).

Slide 49 compares constant and one-hot features:

The rest of the section looks for a middle ground: features that are structural (so they transfer to new graphs) but still break the WL symmetry.

Slide 50: certain structures are hard for GNNs to learn, so give them as features. Use cycle counts as augmented node features: a vector whose position \(i\) says whether the node lies on a cycle of length \(i\), starting from length 0.

• \(v_1\) on a triangle: \([0,0,0,1,0,0]\).
• \(v_1\) on a square: \([0,0,0,0,1,0]\).

Slide 51: ID-GNN-Fast (You, Gomes-Selman, Ying, Leskovec, AAAI 2021). Idea: count cycles originating from a given node and use them as initial features. The figure "colours" the root node \(v\) (orange) and unrolls the ID-GNN rooted subtree; at each depth, count how many tree nodes carry the root's identity. That gives a "cycle count at each level":

• \(v_1\) (triangle): \([1,0,2,2]\) — depth 3 has 2 copies of \(v_1\) ("length-3 cycles = 2": go around the triangle in either direction).
• \(v_2\) (square): \([1,0,2,0]\) — "length-3 cycles = 0".

The counts differ at level 3, so the rooted subtrees are now different (≠ in the figure). Two ways to see the idea: include identity information as an augmented node feature, and use cycle counts at each layer as augmented features. This works together with any GNN.

Notice: "number of times the root reappears at depth \(k\)" equals the number of closed walks of length \(k\), i.e. \((A^k)_{vv}\). This leads straight into the next block.

Slide 52 (Kanatsoulis and Ribeiro, ICASSP 2024): use the diagonals of adjacency powers as augmented node features. \((A^k)_{vv}\) counts closed loops (closed walks) of length \(k\) through \(v\):

The slide's examples (\(D=6\)): \(v_1\) on a triangle gets \([1,0,2,2,6,8]\); \(v_1\) on a square gets \([1,0,2,0,8,0]\). The entry at \(k=3\) (2 vs 0, marked with an arrow) shows the triangle.

Slide typo: for the triangle the last entry should be 10, not 8. Closed walks of length \(k\) on \(K_3\) are \((2^k+2(-1)^k)/3\), giving \(1,0,2,2,6,10\). For the 4-cycle, \((2^k+(-2)^k)/4\) for \(k\ge1\) gives \(0,2,0,8,0\), matching the slide.

Why this works, spectrally: \(\mathrm{diag}(A^k)=\sum_n\lambda_n^k|\mathbf{v}_n|^2\) involves every eigenpair, so these features are not orthogonal to the hidden eigenvectors. Slide 53 states the results:

• Theorem: if two graphs have adjacency matrices with different eigenvalues, there exists a GNN with closed-loop initial node features that can always tell them apart.
• GNNs with structural initial node features can produce different representations for almost all real-world graphs.
• GIN with structural initial node features is strictly more powerful than the WL kernel.

Apply it to \(\mathcal{G}\) vs \(\hat{\mathcal{G}}\): their eigenvalues differ (1.618 vs 1.861 …), so closed-loop features separate them, while WL could not.

Slide 54: other common augmented features — clustering coefficient, PageRank, centrality, … Any feature from Lecture 1 can be used.

Slide 55 adds a structure-aware column to the earlier table:

Slide 57 (You, Ying, Leskovec, ICML 2019) defines two task types on the same graph: two triangles joined by a bridge edge.

• Structure-aware task: nodes are labelled by their structural roles. The two bridge endpoints (degree 3) are B, the four other triangle nodes (degree 2) are A — on both sides.
• Position-aware task: nodes are labelled by their positions. Every node in the left triangle is A, every node in the right triangle is B.

Slide 58: for structure-aware tasks, GNNs work. \(v_1\) (degree 2) and \(v_2\) (bridge node) have different computation graphs, so they can be separated (feature augmentation handles harder cases like cycles).

Slide 59: GNNs always fail for position-aware tasks. A left-triangle node \(v_1\) and its mirror image \(v_2\) in the right triangle have the same computation graph, because of the graph's symmetry. No message-passing GNN, however powerful, can separate them. Question: can we define deep learning methods that are position-aware?

Link to SNA: "community membership" or "which side of a polarised network" is a position-aware label. A structural GNN with constant features sees two equally shaped echo chambers as the same.

Slide 60: the power of an "anchor". Randomly pick a node \(s_1\) as an anchor. Represent \(v_1\) and \(v_2\) by their distances to \(s_1\). In the figure \(s_1\) is in the left triangle: \(d(v_1,s_1)=1\), \(d(v_2,s_1)=2\). The distances differ, so the symmetry is broken. An anchor works like a coordinate axis that locates nodes in the graph.

Slide 61: pick more anchors \(s_1, s_2\) (one in each triangle's bridge node). The relative-distance table is \(v_1: (1, 2)\), \(v_2: (2, 1)\). More anchors characterise position better in different regions of the graph: many anchors = many coordinate axes.

Slide 62: generalise an anchor from one node to a set of nodes. The distance to an anchor-set is the minimum distance to any node in the set. In the figure, \(v_3\) is another node in the left triangle; the size-2 anchor-set \(s_3=\{s_1, v_3\}\). Table:

Single anchors \(s_1,s_2\) cannot separate \(v_1\) from \(v_3\) (both at distances 1 and 2), but the anchor-set \(s_3\) can. Observation: large anchor-sets can sometimes give a more precise position estimate, which lets us use fewer anchors in total.

Intuition: a small anchor-set tells you precisely about the neighbourhood of a few nodes; a large anchor-set tells you "how close you are to anything in a big random region". Mixing sizes gives coordinates at many scales.

Slide 63 states the goal: embed the graph's metric space \((V,d)\) into Euclidean space \(\mathbb{R}^k\) so that distances are preserved — for all \(u,v\in V\), \(\|\mathbf{z}_u-\mathbf{z}_v\|_2\) is close to \(d(u,v)\).

Slide 64: Bourgain's theorem (informal; Bourgain 1985). Define for each node \(v\)

• \(c\) is a constant;
• \(S_{i,j}\subset V\) is a random set that contains each node independently with probability \(1/2^i\) (\(i=1..\log n\) sets the scale, \(j=1..c\log n\) repeats);
• \(d_{\min}(v,S_{i,j})=\min_{u\in S_{i,j}} d(v,u)\).

Then the embedding distance produced by \(f\) is provably close to the original metric. (The precise statement: distortion \(O(\log n)\) with high probability.) Notice that the anchor-sets of the previous block are exactly the \(S_{i,j}\): small \(i\) → large sets, large \(i\) → small sets.

Slide 65: P-GNN follows the theorem. It samples \(O(\log^2 n)\) anchor-sets \(S_{i,j}\) and embeds each node via \(f(v)\in\mathbb{R}^{c\log^2 n}\). P-GNN stays inductive: anchor-sets are re-sampled every time during training, so the network learns to work with any anchor-sets; at test time, on a new unseen graph, new anchor-sets are sampled.

Slide 66 summarises position encoding for graphs: represent a node's position by its distances to randomly selected anchor-sets; each dimension is tied to one anchor-set (e.g. \(v_1\mapsto(1,2,1)\), \(v_3\mapsto(1,2,0)\)).

How to use it?

• Slide 67, the simple way: use the position encoding as an augmented node feature. It works well in practice. Issue: each dimension is tied to a random anchor-set, so the dimensions can be randomly permuted without changing the meaning. A normal NN is not invariant to permuting its input dimensions — its output would change.
• Slide 68, the rigorous way: a special NN that keeps the permutation-invariant property of the encoding: permuting input dimensions only permutes output dimensions, without changing the values. The figure (from the P-GNN paper) shows anchor-set selection \(S=\{S_1,S_2,S_3\}\) on a 5-node graph; for node \(v_1\), a function \(F\) combines \(v_1\)'s feature with each anchor-set's features into messages \(M_{v_1}[1],M_{v_1}[2],M_{v_1}[3]\) (one per anchor-set); \(\mathrm{AGG}_S\) aggregates them into \(\mathbf{h}_{v_1}\) for the next layer, and a projection \(\times\mathbf{w}\) maps the per-anchor-set messages to the output \(\mathbf{z}_{v_1}\in\mathbb{R}^3\), one coordinate per anchor-set.