Md. Asif Uddin

    Chapter 14 I.14

    Graph Neural Networks

    Message passing is permutation-equivariant, and no amount of it can distinguish graphs that the 1-WL test cannot.

    Each node repeatedly summarises its neighbours. After k rounds it knows its k-hop neighbourhood, and after many rounds it knows only the average.

    How this chapter is built

    M3Load-bearing

    The content is mathematics. Understanding is demonstrated by computation, not recall.

    basics11/11what the words mean
    concept2/2what to picture
    theory4/4why it works, and when it does not
    mathematics15/15derive it, then compute it
    practice9/9build it, break it, read the papers

    Five strands, not one. Mathematics is the spine; the other four are the body. A chapter cannot pay its way out of teaching with problems, nor out of problems with teaching.

    Before you start

    The problem

    Grids and sequences are graphs with a fixed, regular neighbourhood. Molecules, interaction networks and citation graphs are not, and their nodes have no natural order. Generalising convolution to an arbitrary neighbourhood is the last piece of neural machinery Elementa needs. We build the layer from the one constraint a graph imposes, that numbering the nodes means nothing; derive the graph convolution and what it cannot represent; show that repeating it averages every node into the same vector; and prove a limit on what any such network can tell apart.

    One round of message passing at node 3A small graph: a triangle on nodes 1, 2 and 3, and a fourth node joined to node 3. Nodes 1, 2 and 4 send their states to node 3. On the right, the three messages enter a sum, the sum and node 3's own state enter an update function, and the result is node 3's new state. The same rule runs at every node, and the sum does not depend on the order of the neighbours.one round, one node1234h₁ + h₂ + h₄sum: order-freeupdate φ(h₃, ·)h₃′Every node runs the same rule on its own neighbours.Renumber the nodes and every output moves with itsnode: the layer is permutation-equivariant.
    Fig. 14 — One round of message passing at node 3 of a four-node graph. The neighbours' states are summed, so their order cannot matter, and the same rule runs at every node. Renumbering the nodes renumbers the outputs and changes nothing else.

    What this chapter covers

    • Node features, adjacency and what a relabelling does to them
    • Permutation equivariance of layers and invariance of readouts
    • Message passing: messages, aggregators, updates
    • Receptive fields on a graph: k layers see k hops
    • The graph Laplacian, spectral filters and the graph convolution
    • Why a graph convolution cannot tell its neighbours apart
    • Over-smoothing: repeated averaging and the second eigenvalue
    • Colour refinement and the limit it sets on message passing
    • Sum, mean and max aggregators, and which can count
    • Sparse computation, batching graphs and neighbour sampling

    Apparatus

    The mathematics this chapter leans on, held in Book 0 so it can be assumed here without being taught here. Not a gate — follow a link when a step stops making sense.

    Graphs, vertices and edges 0.GR.01 · Representing a graph 0.GR.02 · Walks, paths, cycles and connectivity 0.GR.03 · The identity, the inverse and the transpose 0.LA.02 · Rank, eigenvalues and the singular value decomposition 0.LA.04

    Notation

    • WA weight matrix
    • XA batch of token representations, T×d, rows are tokens
    • λA regularisation coefficient, or an eigenvalue where the context is linear algebra
    • dModel width
    • σThe logistic function, or a standard deviation
    • ∇Gradient operator
    • ℒThe loss

    Definitions

    Definition 1Node features

    A matrix X with one row per node and one column per feature, n by d. Together with the adjacency matrix A it is the whole input. The order of its rows is a labelling, not information.

    Definition 2Relabelling

    A permutation of the node numbers, written as a permutation matrix P. It sends A to P A P^T and X to P X, and describes the same graph with the same features.

    Definition 3Permutation equivariance and invariance

    A layer f is equivariant if f(P A P^T, P X) = P f(A, X) for every permutation: relabelling the input relabels the output. A readout r is invariant if r(P A P^T, P X) = r(A, X): relabelling changes nothing.

    Definition 4Message passing

    A layer in which every node computes a message from each neighbour, combines the messages with a permutation-invariant aggregator, and updates its own state from the result and its previous state. The same functions are used at every node.

    Definition 5Aggregator

    The function that combines a node's incoming messages: sum, mean, max, or a weighted sum such as attention. It must not depend on the order of the neighbours, so it acts on a multiset.

    Definition 6Node embedding

    A node's state after the last layer, a vector that depends on the node's features and on its neighbourhood up to as many hops as there are layers.

    Definition 7Readout

    A permutation-invariant function of all node states that produces one vector per graph, usually their sum or mean, used for predictions about whole graphs.

    Definition 8Graph Laplacian

    L = D - A, with D the diagonal matrix of degrees. Its quadratic form x^T L x is the sum over edges of (x_u - x_v)^2, so small values mean a signal that varies little across edges. The normalised form is I - D^(-1/2) A D^(-1/2).

    Definition 9Graph convolution

    The layer H' = sigma(A-hat H W) of Kipf and Welling, with A-hat = D-tilde^(-1/2) (A + I) D-tilde^(-1/2) and D-tilde the degrees counted with self-loops. Every node takes a degree-weighted average of itself and its neighbours, then all nodes share W.

    Definition 10Over-smoothing

    The convergence of node states towards a common direction as averaging layers are stacked. The nodes become indistinguishable except for a factor set by their degrees.

    Definition 11Colour refinement (1-WL)

    The Weisfeiler-Lehman test: give every node the same colour, then repeatedly recolour each node by its own colour and the multiset of its neighbours' colours. Two graphs whose colour counts differ at some round are not isomorphic; equal counts prove nothing.

    Formal results

    I.14.T1

    Message passing with an invariant aggregator is permutation-equivariant

    If every node applies the same message, aggregation and update functions, and the aggregator depends only on the multiset of incoming messages, then relabelling the nodes by P sends the layer's output H to P H. A readout that sums or averages over nodes is then permutation-invariant, and so is any composition of such layers followed by it.

    What this does not promise

    Equivariance is a restriction as well as a guarantee: a node cannot tell its neighbours apart, so no layer of this kind computes a directional difference. Nor does it promise that structurally different nodes receive different states; I.14.T4 bounds that.

    I.14.T2

    k layers see k hops

    After k message-passing layers, a node's state depends only on the features and edges within distance k of it. In matrix form, the entry of A^k for nodes v and u counts walks of length k between them, and is zero when they are more than k apart.

    What this does not promise

    Possible dependence is not effective dependence. A node k hops away may influence the state by a negligible amount, and a fixed-width state must summarise a neighbourhood that can grow exponentially with k.

    I.14.T3

    The graph convolution's averaging converges at the rate of its second eigenvalue

    For a connected graph, A-hat = D-tilde^(-1/2) (A + I) D-tilde^(-1/2) has eigenvalue 1 once, with unit eigenvector u proportional to the square roots of the degrees with self-loops, and every other eigenvalue strictly between -1 and 1. Hence A-hat^k x tends to u (u^T x), and the distance to that limit is at most |lambda_2|^k times the starting distance, where |lambda_2| is the largest other eigenvalue in absolute value.

    What this does not promise

    This is the linear part only. Learned weights and nonlinearities change the rate, and residual connections or normalisation can prevent the collapse. Without self-loops a bipartite graph has eigenvalue -1 and the iteration oscillates instead. A disconnected graph converges separately on each component.

    I.14.T4

    Message passing is no more discriminating than colour refinement

    If colour refinement gives two graphs the same colour counts at every round, then every message-passing network started from identical node features gives them the same multiset of node states at every layer, and so the same readout. With a sum aggregator and injective update functions a message-passing network separates every pair that colour refinement separates. Mean and max aggregators are strictly weaker.

    What this does not promise

    Matching colour refinement in principle does not mean a trained network does. Distinct node features break the ties the theorem assumes. Colour refinement separates almost all graphs drawn at random, and fails on regular graphs such as two triangles against a hexagon.

    Assumptions

    Each is paired with the problem that shows what its removal costs. An assumption nobody tests is a disclaimer.

    • The aggregator is invariant to the order of the neighbours. A layer that reads neighbours in index order depends on the labelling. I.14.X02
    • The graph is connected and has self-loops when convergence is claimed. Without self-loops a bipartite graph oscillates. I.14.X05
    • Graphs batched together are offset so that their edges stay within their own blocks. I.14.B05
    • Node features, or extra structural features, break the symmetries that colour refinement cannot. I.14.B03
    • The dependencies the task needs lie within as many hops as there are layers. I.14.X07
    • Where counting matters, the aggregator is injective on multisets, as a sum is and a mean or a max is not. I.14.X03

    Propositions

    1. Prop. 1A graph layer must give the same answer however the nodes are numbered, and message passing is the layer that does.Numbering the nodes of a graph is a choice, not information. A layer that runs one rule at every node and combines neighbours with an order-free aggregator relabels its output exactly as its input was relabelled, and k such layers see k hops.
    2. Prop. 2A graph convolution is a degree-weighted average, and it cannot tell its neighbours apart.The graph Laplacian supplies a graph's frequencies, and a first-order filter on them, renormalised, is the graph convolution. Its coefficients come from degrees alone, so it has no notion of direction, and it merges nodes whose neighbourhoods coincide.
    3. Prop. 3Repeated averaging forgets where it started, at a rate the graph's spectrum sets.Stacked graph convolutions drive every node towards one direction fixed by the degrees. The distance to that limit shrinks by the second eigenvalue at every layer, which is why graph networks are shallow.
    4. Prop. 4Message passing cannot separate what colour refinement cannot.A message-passing network's node states are functions of colour-refinement colours, so two graphs that refinement confuses get identical outputs. A sum aggregator reaches that limit; a mean or a max falls short of it. Passing the limit takes features the graph alone does not supply.

    Numbered equations

    1. A -> P A P^T, X -> P X; f(P A P^T, P X) = P f(A, X); r(P A P^T, P X) = r(A, X)

      A relabelling changes the description of a graph, not the graph.

      (I.14.1)

    2. h_v' = phi(h_v, aggregate over u in N(v) of psi(h_v, h_u))

      Every node runs the same rule on the multiset of its neighbours.

      (I.14.2)

    3. H' = sigma(H W_0 + A H W_1); (A^k)_vu = number of walks of length k from v to u

      Sum aggregation is a product with A, and k products reach k hops.

      (I.14.3)

    4. L = D - A; x^T L x = sum over edges (x_u - x_v)^2; L = U Lambda U^T; g(L) x = U g(Lambda) U^T x

      The Laplacian's eigenvectors are a graph's frequencies, and a filter reweights them.

      (I.14.4)

    5. A-hat = D-tilde^(-1/2) (A + I) D-tilde^(-1/2); H' = sigma(A-hat H W)

      A graph convolution averages each node with its neighbours, weighted by degree.

      (I.14.5)

    6. A-hat^k x -> u u^T x, u proportional to D-tilde^(1/2) 1; distance <= |lambda_2|^k times its start

      Repeated averaging forgets everything but one direction.

      (I.14.6)

    7. c_v(t+1) = hash(c_v(t), multiset of c_u(t) over u in N(v))

      Colour refinement is message passing with an injective update.

      (I.14.7)

    8. h_v' = MLP((1 + epsilon) h_v + sum over u in N(v) of h_u)

      A sum and an injective update are enough to match colour refinement.

      (I.14.8)

    9. cost per layer: O(m d + n d^2) with an edge list; O(n^2 d + n d^2) with a dense A

      A sparse graph is cheap only if its sparsity is used.

      (I.14.9)

    Worked problems

    5/5 problems5/4 variants10/10 exercisesquota met, and enforced

    1. I.14.B01 — One round of message passing, three aggregatorsnumeric▲△△
    2. I.14.B02 — Where repeated averaging converges, and how fastsymbolic▲▲▲
    3. I.14.B03 — Two triangles and a hexagoncounterexample▲▲△
    4. I.14.B04 — What a graph layer costscomplexity▲▲△
    5. I.14.B05 — A batch of three graphsshape▲▲△

    The whole problem set, with the exercises →

    Practice

    • Stacking averaging layers. On the four-node paw graph the distance of the state from its limit falls from 2.516217 to 0.244093 after four rounds and to 0.000255 after sixteen; after ten the four nodes differ by less than one per cent.
    • A mean or max aggregator where counts matter. The centres of stars with two and four leaves receive the same mean, 1, from constant features; the multisets {1, 1, 2, 2} and {1, 2} have the same mean and the same maximum.
    • Merging nodes with the same closed neighbourhood. One graph convolution gives nodes 1 and 2 of the paw graph the same output, 1.866025, although their features are 1 and 2.
    • Batching graphs without offsetting their edge lists. Three graphs of sizes 4, 3 and 5 should read out 8, 4 and 10 after one summed round; without offsets they read out 10, 2 and 0.
    • Omitting self-loops on a bipartite graph. On a hexagon the normalised adjacency has eigenvalue -1, and the alternating signal flips sign at every layer instead of converging.
    • Expecting message passing to separate regular graphs. Two triangles and a hexagon get identical outputs from every message-passing network with identical starting features, though one has two triangles and the other none.
    • Using a dense adjacency matrix. For a million nodes and ten million edges it needs 4e12 bytes and 1.28e14 multiply-accumulates per layer of width 128; an edge list needs 3.2e8 bytes and 1.89e10.
    • Too few layers for the task. Node 1 of a four-node path and of a five-node path has the same state after two layers, 0.892956, and the two differ only from the third.
    • Ignoring neighbourhood growth. With average degree 20, a three-layer network's prediction for one node can depend on up to 8,000 nodes; sampling 25 and then 10 neighbours bounds two layers at 250.
    • Feeding Laplacian eigenvectors as positions without handling their ambiguity. Each eigenvector is defined only up to sign, and the eigenvalue 3 of two triangles has multiplicity four, with no preferred basis.