A graph layer must give the same answer however the nodes are numbered, and message passing is the layer that does.

The input has no order

A graph has $n$ nodes and $m$ edges (Graphs, vertices and edges · 0.GR.01). A network receives it as two arrays: the adjacency matrix $\mat A$, of shape $n\times n$ (Representing a graph · 0.GR.02), and the node features $\mat X$, of shape $n\times d$, one row per node.

Those arrays depend on how the nodes were numbered. Renumbering by a permutation matrix $\mat P$, whose inverse is its transpose (The identity, the inverse and the transpose · 0.LA.02), describes the same graph with different arrays:

The second line of (I.14.1) asks a node-level layer $f$ to be equivariant: renumber the input and the output is renumbered the same way. The third asks a graph-level readout $r$ to be invariant: renumbering changes nothing.

A multilayer perceptron applied to the flattened adjacency matrix has neither property. A graph on $n$ nodes can be numbered in up to $n!$ ways, $3{,}628{,}800$ for ten nodes, and the perceptron would have to learn separately that all of them are the same graph. It also fixes $n$. A convolution escaped the same problem on a grid by reusing one local rule at every position (I.11). A graph needs one local rule that also does not care in which order a node’s neighbours are listed.

Message passing

A message-passing layer gives every node the same three steps. Each neighbour sends a message computed from the two nodes’ states. The messages are combined by an aggregator that sees them only as a multiset. The node updates its state from the result and its previous state:

Here $\mathcal N(v)$ is the set of $v$‘s neighbours and $\bigoplus$ is a sum, a mean, a maximum, or an attention-weighted sum. The functions $\psi$ and $\varphi$ are small networks shared by every node. Scarselli and colleagues (2009) introduced graph networks of this kind, and Gilmer and colleagues (2017) showed that most later variants are instances of (I.14.2).

The equivariance proof takes three sentences. Renumbering moves each node together with its features and its set of neighbours. The aggregator receives the same multiset of messages under any numbering, because a multiset has no order. So every node computes the same new state as before, and only its row number changes: the output is $\mat P\mat H'$. That is I.14.T1. A readout that sums or averages the rows is then invariant, because a sum over all nodes does not depend on their order. Zaheer and colleagues (2017) showed that sums are general here: every permutation-invariant function of a finite set from a countable domain can be written as $\rho\big(\sum_i\phi(\vec x_i)\big)$.

Sum aggregation is a product with the adjacency matrix

With a sum aggregator and linear messages, the layer is a few matrix products:

Row $v$ of $\mat A\mat H$ is the sum of $v$‘s neighbours’ rows. Equivariance is now one line: $(\mat P\mat A\mat P^{\mathsf T})(\mat P\mat H)=\mat P(\mat A\mat H)$, because $\mat P^{\mathsf T}\mat P=\mat I$, and the weights act on the feature axis, which relabelling does not touch.

The chapter’s running example is the paw: a triangle on nodes $1$, $2$ and $3$, and node $4$ joined to node $3$. Its degrees are $2$, $2$, $3$ and $1$. With scalar features $\vec x=(1,2,3,4)$, the summed messages $\mat A\vec x$ are $(5,4,7,3)$: node $3$ receives $1+2+4$. The mean aggregator divides by the degrees and gives $(2.5,\,2,\,2.333333,\,3)$. Swap the labels of nodes $1$ and $4$, and both results come back with their first and last entries swapped. I.14.B01 works it through, and I.14.X02 shows a layer that reads neighbours in index order and is not equivariant.

k layers see k hops

The second line of (I.14.3) is the graph form of a receptive field. A walk of length $k$ can reach only nodes within distance $k$ (Walks, paths, cycles and connectivity · 0.GR.03), so after $k$ layers a node’s state depends only on the features and edges within $k$ hops of it. That is I.14.T2. Like the receptive field of I.11.T3, it bounds what can matter, not what does.

Two features of graphs make the bound bite harder than on a grid. The number of nodes within $k$ hops can grow like $c^k$ for average degree $c$, so a few layers can depend on a large part of the graph (I.14.B04). And a task whose answer depends on something three hops away cannot be solved by two layers, however wide: I.14.X07 builds two paths whose end nodes look identical for two layers and differ at the third.

Node embeddings and readouts

The rows of the final state matrix are node embeddings: vectors that describe each node in the context of its neighbourhood. A node-level task, such as classifying the atoms of a molecule or the proteins of an interaction network, reads them directly. A graph-level task, such as predicting a molecule’s toxicity, applies a readout first. An edge-level task combines the embeddings of the edge’s two ends. Book VII uses all three.

One round, relabelled

A = [[0, 1, 1, 0], [1, 0, 1, 0], [1, 1, 0, 1], [0, 0, 1, 0]]   # the paw graph
x = [1.0, 2.0, 3.0, 4.0]

def layer(A, x):                     # sum over neighbours, then a fixed update
    return [x[v] + 0.5*sum(x[u] for u in range(len(A)) if A[v][u])
            for v in range(len(A))]

p = [3, 1, 2, 0]                     # relabel: node i becomes node p[i]
PA = [[0]*4 for _ in range(4)]
Px = [0.0]*4
for i in range(4):
    Px[p[i]] = x[i]
    for j in range(4):
        PA[p[i]][p[j]] = A[i][j]
print(layer(A, x))
print(layer(PA, Px))

It prints [3.5, 4.0, 6.5, 5.5] and then [5.5, 4.0, 6.5, 3.5]: the same four numbers, with nodes $1$ and $4$ exchanged as the input was.