Part II · Kernels and graphs | encoding graphs, permutation invariance and equivariance, similarity graphs, the graph Laplacian, spectra and the Fiedler vector, harmonic functions and label propagation, random walks, diffusion and PageRank, graph convolutional networks, message passing, graph classification and the Weisfeiler–Leman test | reading: Prince, Understanding Deep Learning, ch. 13; Hamilton, Graph Representation Learning, ch. 1–2 and 5–7; Zhu, Ghahramani & Lafferty (2003)
Lecture 8's graphs were models: a tree of questions. In this lecture the graph is part of the data. Sometimes it is given: friendships, citations, the bonds of a molecule, the stations of a subway. Sometimes we build it, joining each data point to its nearest neighbours. Either way, the graph encodes an assumption familiar from nearest neighbours in Lecture 1: points that are connected tend to share labels. We will make that assumption precise with the graph Laplacian, whose eigenvectors are the smooth "modes" of a graph and whose quadratic form measures how much a labelling disagrees across edges. Minimising that disagreement gives label propagation, which can classify thousands of points from a handful of labels. Making the propagation learnable gives graph neural networks, the deep-learning architecture for molecules, social networks and road maps, and also exposes what such networks fundamentally cannot see.
By the end of this lecture you should be able to encode a graph as matrices and explain why graph models must be permutation-invariant or equivariant; build similarity graphs from data; prove the basic facts about the Laplacian (its quadratic form, its zero eigenvalues) and read its eigenvectors; derive and solve the harmonic label-propagation problem, prove it is well posed, and recognise when it fails; explain random walks, diffusion and PageRank on graphs; implement a graph convolutional network and describe message passing; and classify whole graphs with a readout, knowing the Weisfeiler–Leman limit on what message passing can distinguish.
A (simple, undirected) graph \(G=(V,E)\) has nodes \(V=\{1,\dots,n\}\) and edges
$$E\subseteq\{\{i,j\}:i\ne j\}.$$It is encoded by:
The numbering of the nodes is arbitrary. Relabelling them by a permutation \(\pi\), with permutation matrix \(P\) (\(P_{i,\pi(i)}=1\)), replaces \(A\) by \(PAP^\top\) and \(X\) by \(PX\), and describes exactly the same graph. A model that gave different answers for the two descriptions would be answering a question about our bookkeeping, not about the graph.
A function \(F(A,X)\) is permutation-invariant if
$$F(PAP^\top,PX)=F(A,X)$$for every permutation matrix \(P\); this is what a graph-level prediction (is this molecule toxic?) must satisfy.
It is permutation-equivariant if
$$F(PAP^\top,PX)=P\,F(A,X);$$this is what node-level outputs (one row per node) must satisfy: relabel the nodes and the outputs are relabelled the same way.
The simplest equivariant layer mixes each node's features with its neighbours' and then applies the same transformation to every node.
Let \(\hat A=A+I\), \(W\) a weight matrix and \(\sigma\) any function applied entrywise. The layer
$$F(A,X)=\sigma(\hat AXW)$$is permutation-equivariant, and so is any composition of such layers.
The sum readout
$$r(H)=\mathbf 1^\top H=\sum_iH_{i,:}$$is permutation-invariant, so a stack of layers followed by a sum readout is a permutation-invariant graph-level model. Mean and max readouts are invariant too.
Permutation matrices satisfy \(P^\top P=I\), so
$$(PAP^\top+I)PXW=P(A+I)P^\top PXW=P\hat AXW.$$Applying \(\sigma\) entrywise commutes with reordering rows: \(\sigma(PM)=P\sigma(M)\). Hence
$$F(PAP^\top,PX)=PF(A,X),$$and composing equivariant maps gives an equivariant map.
For the readout, \(\mathbf 1^\top P=\mathbf 1^\top\) (each column of \(P\) contains a single 1), so \(\mathbf 1^\top PH=\mathbf 1^\top H\). The mean is the sum divided by \(n\), and the maximum over rows does not depend on their order. \(\square\)
188 nitroaromatic compounds tested for mutagenicity on Salmonella typhimurium (Debnath et al., 1991), 125 of them mutagenic. Each molecule is a graph whose nodes are atoms, labelled by one of 7 atom types, and whose edges are bonds (17.9 atoms on average). Part of the TUDataset collection (Morris et al., 2020); we read the copy distributed with Xu et al.'s (2019) GIN code.
import numpy as np # Read MUTAG (Debnath et al. 1991), in the text format of Xu et al.'s GIN repository: # for each molecule "n label", then one line per atom: "atom_type degree neighbours..." lines = open('data/MUTAG.txt').read().split('\n'); k = 1 mols = [] for g in range(int(lines[0])): n, lab = map(int, lines[k].split()); k += 1 A = np.zeros((n, n), int); atom = np.zeros(n, int) for i in range(n): row = list(map(int, lines[k].split())); k += 1 atom[i] = row[0] for j in row[2:]: A[i, j] = 1 mols.append((A, atom, int(lab == 2))) # label 1 = mutagenic print(len(mols), 'molecules,', sum(m[2] for m in mols), 'mutagenic; atoms per molecule', np.mean([len(m[1]) for m in mols]).round(1)) A, atom, y = mols[0] X = np.eye(7)[atom] # node features: one-hot atom type (7 types) print('first molecule:', len(atom), 'atoms,', A.sum() // 2, 'bonds; symmetric:', (A == A.T).all(), '; degrees', A.sum(1)) # One message-passing layer H = ReLU(A_hat X W) and a sum readout A_hat = A + np.eye(len(A)) rng = np.random.default_rng(0); W = rng.standard_normal((7, 4)) layer = lambda A_, X_: np.maximum(0, (A_ + np.eye(len(A_))) @ X_ @ W) H = layer(A, X) P = np.eye(len(A))[rng.permutation(len(A))] # relabel the atoms with a random permutation H_perm = layer(P @ A @ P.T, P @ X) print('equivariance: max |layer(PAP^T, PX) - P layer(A, X)| =', np.abs(H_perm - P @ H).max()) print('invariance: max |sum readout after - before| =', np.abs(H_perm.sum(0) - H.sum(0)).max())
188 molecules, 125 mutagenic; atoms per molecule 17.9 first molecule: 23 atoms, 27 bonds; symmetric: True ; degrees [2 2 3 2 2 3 3 2 2 3 3 3 3 2 3 3 2 2 2 2 3 1 1] equivariance: max |layer(PAP^T, PX) - P layer(A, X)| = 0.0 invariance: max |sum readout after - before| = 4.440892098500626e-16
Relabelling the 23 atoms of the first molecule permutes the layer's output rows exactly (difference 0.0) and leaves the sum readout unchanged up to floating-point rounding. Every architecture in this lecture is built from equivariant layers and an invariant readout, which is the graph analogue of the translation equivariance of convolutions in Lecture 11.
Which of these graph-level functions of \((A,X)\) is not permutation-invariant?
When the data are points \(x_1,\dots,x_n\in\mathbb R^p\) rather than a network, we build the graph ourselves from a notion of similarity.
The \(\varepsilon\)-graph is simple but fragile: in regions of low density it falls apart, in dense ones it becomes nearly complete. The kNN graph adapts to density and is the usual choice. Building it naively costs \(O(n^2)\) distance computations; libraries such as FAISS find approximate neighbours among billions of vectors, which is how kNN graphs over images and text embeddings are built in practice. The Gaussian weight is the RBF kernel of Lecture 7 restricted to near neighbours: a sparse similarity matrix.
If connected nodes tend to share labels, a good labelling \(f:V\to\mathbb R\) should change little across edges. One matrix measures exactly that.
For a weighted graph with weights \(W\) and degrees \(d_i=\sum_jW_{ij}\), the (combinatorial) Laplacian is
$$L=D-W.$$The normalised Laplacians are
$$L_{\text{sym}}=I-D^{-1/2}WD^{-1/2}$$and
$$L_{\text{rw}}=I-D^{-1}W.$$For every \(f\in\mathbb R^n\),
$$f^\top Lf=\frac12\sum_{i,j}W_{ij}(f_i-f_j)^2=\sum_{\{i,j\}\in E}W_{ij}(f_i-f_j)^2\ \ge0.$$So \(L\) is symmetric positive semi-definite, and \(L\mathbf 1=0\): constant labellings cost nothing.
using \(d_i=\sum_jW_{ij}\) and the symmetry of \(W\). Each unordered edge appears twice in the double sum. \(\square\)
The name comes from calculus. On a grid, \((Lf)_i=\sum_j(f_i-f_j)\) is minus the discrete second derivative, and \(f^\top Lf\) is the discrete version of \(\int\|\nabla f\|^2\), the Dirichlet energy. A function with small \(f^\top Lf\) is smooth on the graph, whatever the dimension of the data the graph was built from.
The multiplicity of the eigenvalue 0 of \(L\) equals the number of connected components of the graph, and its eigenspace is spanned by the indicator vectors of the components.
\(Lf=0\) implies \(f^\top Lf=0\), so by Proposition 9.2 \(f_i=f_j\) for every edge with \(W_{ij}>0\), and hence \(f\) is constant on each connected component. Conversely, any function constant on each component satisfies \(Lf=0\). The component indicators form a basis of these functions, so the dimension of the kernel is the number of components. \(\square\)
Since \(L\) is symmetric, it has an orthonormal basis of eigenvectors \(u_1,u_2,\dots,u_n\) with eigenvalues \(0=\lambda_1\le\lambda_2\le\dots\le\lambda_n\) (the spectral theorem of Lecture 2). For a unit eigenvector, \(u_k^\top Lu_k=\lambda_k\), so by Proposition 9.2 the eigenvalue is the roughness of its eigenvector. The eigenvectors play the role of Fourier modes: low eigenvalues give slowly varying patterns across the graph, high eigenvalues give patterns that flip sign across many edges. On a path or a cycle they are literally sines and cosines.
The second eigenvector \(u_2\), the Fiedler vector, is the smoothest labelling that is not constant and is orthogonal to the constants. Its sign therefore splits the graph into two parts with few edges between them, the idea behind spectral clustering (Lecture 15), and its eigenvalue \(\lambda_2\), the algebraic connectivity, measures how well connected the graph is: it is zero exactly when the graph is disconnected (Proposition 9.3).
The friendships among 34 members of a university karate club, recorded by the anthropologist Wayne Zachary between 1970 and 1972 (78 ties). During the study a dispute between the instructor ("Mr. Hi") and the club's president (the "Officer") split the club in two, and Zachary recorded which faction each member joined (Zachary, 1977; in networkx).
import networkx as nx G = nx.karate_club_graph() # Zachary (1977): 34 members, 78 friendships A = nx.to_numpy_array(G, weight=None) deg = A.sum(1) L = np.diag(deg) - A # the graph Laplacian lam, V = np.linalg.eigh(L) print('smallest eigenvalues of L:', lam[:4].round(4)) f = V[:, 1] # the Fiedler vector club = np.array([G.nodes[i]['club'] == 'Officer' for i in range(34)]) side = f > 0 agree = max(np.mean(side == club), np.mean(side != club)) print(f'sign of the Fiedler vector matches the real split for {agree * 34:.0f} of 34 members') wrong = np.where((side == club) != (np.mean(side == club) > 0.5))[0] print('misplaced members:', wrong, ' their Fiedler values:', f[wrong].round(3)) print('edges cut by the Fiedler split:', int(A[side][:, ~side].sum()), ' versus by the real split:', int(A[club][:, ~club].sum())) # Quadratic form identity and connected components x = np.random.default_rng(1).standard_normal(34) print('f^T L f =', round(x @ L @ x, 6), ' (1/2) sum_ij a_ij (f_i - f_j)^2 =', round(0.5 * (A * (x[:, None] - x[None, :])**2).sum(), 6)) two = nx.disjoint_union(G, nx.cycle_graph(5)) L2 = nx.laplacian_matrix(two).toarray().astype(float) print('karate club plus a separate 5-cycle: zero eigenvalues =', int(np.sum(np.abs(np.linalg.eigvalsh(L2)) < 1e-9)))
smallest eigenvalues of L: [-0. 0.4685 0.9092 1.125 ] sign of the Fiedler vector matches the real split for 32 of 34 members misplaced members: [2 8] their Fiedler values: [0.023 0.052] edges cut by the Fiedler split: 10 versus by the real split: 11 f^T L f = 144.246252 (1/2) sum_ij a_ij (f_i - f_j)^2 = 144.246252 karate club plus a separate 5-cycle: zero eigenvalues = 2
From the friendship graph alone, before the dispute, the sign of the Fiedler vector predicts the faction of 32 of the 34 members. The two it misplaces (nodes 2 and 8 in zero-based numbering, members 3 and 9 in Zachary's) have Fiedler values close to zero: they had friends on both sides. In fact the Fiedler split cuts 10 friendships, one fewer than the real split; member 9 reportedly joined Mr. Hi's club for reasons beyond friendship, being three weeks from a black-belt test. The code also checks Proposition 9.2 numerically and finds two zero eigenvalues once a separate 5-cycle is added (Proposition 9.3).
A graph consists of three separate triangles. Its Laplacian has zero eigenvalues, and its Fiedler value \(\lambda_2\) is .
Miroslav Fiedler, a Czech mathematician, introduced the "algebraic connectivity" \(\lambda_2\) in 1973 and showed two years later that the signs of its eigenvector split a graph into connected pieces; Donath and Hoffman had proposed eigenvector partitioning the same year. Wayne Zachary's 1977 study of a karate club that split in two became the most famous small network in science, and network researchers award a mock "karate club club" prize to the first speaker at a conference who uses it. Label propagation entered machine learning with Zhu, Ghahramani and Lafferty's harmonic functions (2003) and Zhou et al.'s "local and global consistency" (2004). Sergey Brin and Larry Page's PageRank (1998), computed by the power iteration of Lecture 2, was the founding algorithm of Google, and an echo of Leo Katz's 1953 status index and Pinski and Narin's 1976 journal rankings.
Labels are often expensive and unlabelled data cheap: a radiologist labels a few scans, millions are on file. Suppose a few nodes \(\ell\subset V\) carry known labels \(f_\ell\) and the rest \(u=V\setminus\ell\) do not. The smoothness assumption suggests choosing the unknown labels to make the whole labelling as smooth as possible.
The harmonic solution (Zhu, Ghahramani and Lafferty, 2003) minimises
$$f^\top Lf=\sum_{\{i,j\}}W_{ij}(f_i-f_j)^2$$subject to \(f_\ell\) fixed. Splitting \(L\) into blocks for labelled and unlabelled nodes, setting the gradient with respect to \(f_u\) to zero gives
$$L_{uu}f_u=W_{u\ell}f_\ell,\qquad\text{equivalently}\qquad f_i=\frac1{d_i}\sum_jW_{ij}f_j\quad\text{for every }i\in u.$$Each unlabelled node takes the weighted average of its neighbours, which is what "harmonic" means.
For \(K\) classes, solve once per class with \(f_\ell\) the one-hot labels and predict the class with the largest value.
If every connected component of the graph contains at least one labelled node, then \(L_{uu}\) is invertible, so the harmonic solution exists and is unique, and every value \(f_i\), \(i\in u\), lies between \(\min_{\ell}f_\ell\) and \(\max_\ell f_\ell\).
Moreover \(f_i\) is the probability that a random walk started at \(i\), moving to neighbour \(j\) with probability \(W_{ij}/d_i\), first reaches a labelled node of class 1 (for two classes with labels 0 and 1).
Maximum principle. Let \(f\) satisfy the averaging equations and let \(M=\max_if_i\). If \(M>\max_\ell f_\ell\), the maximum is attained at some unlabelled node \(i\). Being an average of its neighbours, \(f_i\) can equal \(M\) only if every neighbour also has value \(M\); repeating the argument, every node in \(i\)'s component has value \(M\), including the labelled node that the component contains, a contradiction. The same holds for the minimum.
Uniqueness and invertibility. If \(L_{uu}g=0\), then \(g\) on \(u\) together with \(0\) on \(\ell\) solves the averaging equations with all labels 0, so by the maximum principle \(g=0\). Hence \(L_{uu}\) has trivial kernel.
Random walks. Let \(h_i\) be the probability that the walk from \(i\) hits a class-1 node before a class-0 node. Conditioning on the first step,
$$h_i=\sum_j\frac{W_{ij}}{d_i}h_j$$for unlabelled \(i\), with \(h=f_\ell\) on labelled nodes; by uniqueness \(h=f\). \(\square\)
The averaging form suggests an algorithm: start the unlabelled values anywhere, and repeatedly replace each by the weighted average of its neighbours while holding the labelled values fixed. This is label propagation.
The iteration
$$f_u\leftarrow D_{uu}^{-1}\big(W_{uu}f_u+W_{u\ell}f_\ell\big)$$converges to the harmonic solution from any starting point, under the condition of Theorem 9.4.
The error \(e=f_u-f_u^*\) evolves as \(e\leftarrow Me\) with \(M=D_{uu}^{-1}W_{uu}\), a nonnegative matrix whose rows sum to at most 1, and to less than 1 for nodes with a labelled neighbour.
\((M^k)_{ij}\) is the probability that a random walk from \(i\) is at \(j\) after \(k\) steps without having touched a labelled node. Since every component contains a labelled node, from any start the walk hits one within \(m=|u|\) steps with probability at least some \(c>0\), so every row of \(M^m\) sums to at most \(1-c\). Hence
$$\|M^{km}\|_\infty\le(1-c)^k\to0,$$the spectral radius of \(M\) is below 1, and \(e\to0\) geometrically. \(\square\)
Two labels classify most of the 38 others correctly once the propagation has converged (slider at the far right): 29 of them (76%) with \(k=4\) and 32 (84%) with \(k=8\). With \(k=1\) the graph falls apart into pieces, and in pieces with no label the values stay at their starting value of ½: Theorem 9.4's condition is not a technicality. Now a harder test: handwritten digits with one label per class.
import gzip, pickle with gzip.open('data/mnist.pkl.gz', 'rb') as fh: (Xm, ym), _, _ = pickle.load(fh, encoding='latin1') rng = np.random.default_rng(0) idx = rng.choice(len(Xm), 2000, replace=False); Xd, yd = Xm[idx], ym[idx] labelled = np.array([np.where(yd == d)[0][0] for d in range(10)]) # ONE labelled image per digit unl = np.setdiff1d(np.arange(2000), labelled) # kNN similarity graph with Gaussian weights sq = (Xd**2).sum(1); D2 = np.maximum(sq[:, None] + sq[None, :] - 2 * Xd @ Xd.T, 0) def knn_graph(k): nn = np.argsort(D2, axis=1)[:, 1:k + 1] s2 = np.median(D2[np.arange(2000)[:, None], nn]) W = np.zeros((2000, 2000)); rows = np.repeat(np.arange(2000), k) W[rows, nn.ravel()] = np.exp(-D2[rows, nn.ravel()] / s2) return np.maximum(W, W.T) # symmetrise def harmonic(W, lab, y_lab): """Zhu-Ghahramani-Lafferty: solve L_uu F_u = W_ul F_l, one column per class.""" L = np.diag(W.sum(1)) - W u = np.setdiff1d(np.arange(len(W)), lab) return u, np.linalg.solve(L[np.ix_(u, u)], W[np.ix_(u, lab)] @ np.eye(10)[y_lab]) nearest = yd[labelled][np.argmin(D2[np.ix_(unl, labelled)], 1)] print('1-nearest-neighbour from the 10 labelled images: accuracy', round(np.mean(yd[unl] == nearest), 3)) print(' k harmonic class-mass normalised images assigned to "1" by the harmonic solution') for k in [5, 10, 20]: u, F = harmonic(knn_graph(k), labelled, yd[labelled]) raw = F.argmax(1) cmn = (F / F.sum(0)).argmax(1) # rescale each class column to equal total mass print(f'{k:3d} {np.mean(raw == yd[u]):8.3f} {np.mean(cmn == yd[u]):21.3f} {np.sum(raw == 1):5d} of {len(u)} (true count {np.sum(yd[u] == 1)})')
1-nearest-neighbour from the 10 labelled images: accuracy 0.443 k harmonic class-mass normalised images assigned to "1" by the harmonic solution 5 0.371 0.674 1164 of 1990 (true count 212) 10 0.286 0.650 1527 of 1990 (true count 212) 20 0.238 0.609 1711 of 1990 (true count 212)
The plain harmonic solution does worse than simply giving each image the label of its nearest labelled image (37% against 44%), and gets worse as the graph gets denser. The last column shows why: it assigns more than half the images to the digit 1. The harmonic value of a node is a hitting probability, and the labelled "1" sits in a dense, well-connected part of the graph (ones are thin, so they are close to many other images), so random walks from everywhere tend to hit it first. Zhu, Ghahramani and Lafferty anticipated this and proposed class mass normalisation: rescale each class's column so that every class has the same total mass before taking the largest. That one line lifts accuracy to 67% from ten labels. The general lesson, studied by Nadler, Srebro and Zhou (2009), is that with very few labels and much unlabelled data, the harmonic solution becomes almost constant away from the labelled points, and its tiny variations decide everything.
On a path of 5 nodes, node 1 is labelled 0 and node 5 is labelled 1. What is the harmonic value at node 4?
Put a Gaussian prior on labellings that penalises roughness, \(p(f)\propto\exp\big(-\tfrac12f^\top(L+\varepsilon I)f\big)\): a Gaussian Markov random field, whose precision matrix is the (regularised) Laplacian, so each node is conditionally independent of the rest given its neighbours. Conditioning on the observed labels \(f_\ell\) gives a Gaussian posterior for \(f_u\) with mean \(-(L_{uu}+\varepsilon I)^{-1}L_{u\ell}f_\ell\), which tends to the harmonic solution as \(\varepsilon\to0\) (Exercise 6), and with covariance \((L_{uu}+\varepsilon I)^{-1}\), which says how sure we should be about each propagated label. Zhu, Lafferty and Ghahramani (2003) made this a Gaussian process on the graph, with kernel \((L+\varepsilon I)^{-1}\), linking this lecture to Lecture 7.
Theorem 9.4 already used a random walk. The walk's transition matrix is \(P=D^{-1}W\), whose row \(i\) is the distribution of the next node from \(i\). A distribution \(\pi\) over nodes (a row vector) evolves as \(\pi\leftarrow\pi P\).
On a connected undirected graph,
$$\pi_i=d_i/\sum_jd_j$$satisfies \(\pi P=\pi\): in the long run, a random walk spends time at each node in proportion to its degree.
using the symmetry \(W_{ij}=W_{ji}\). \(\square\)
On the web, links are directed, some pages have no outgoing links, and the walk can get trapped. PageRank fixes this with teleportation: with probability \(\alpha\) (typically 0.85) follow a random outgoing link, otherwise jump to a page chosen uniformly at random.
Let \(P\) be the walk's transition matrix (with dangling nodes sent uniformly to all pages) and
$$G=\alpha P+\frac{1-\alpha}n\mathbf 1\mathbf 1^\top$$with \(0<\alpha<1\). Then \(G\) has a unique stationary distribution \(\pi\) (\(\pi G=\pi\), \(\sum\pi_i=1\)), every \(\pi_i>0\), and the power iteration \(\pi\leftarrow\pi G\) converges to it from any starting distribution, with error shrinking by a factor \(\alpha\) per step.
Every entry of \(G\) is positive. The Perron–Frobenius theorem for positive matrices says that the eigenvalue 1 of a positive stochastic matrix is simple, with a positive left eigenvector, and every other eigenvalue has modulus less than 1, which gives existence, uniqueness and positivity.
For the rate: for two distributions \(\mu,\nu\), the teleportation part of \(G\) maps both to the same vector, so
$$\mu G-\nu G=\alpha(\mu-\nu)P,$$and \(\|(\mu-\nu)P\|_1\le\|\mu-\nu\|_1\) because \(P\) is stochastic. \(\square\)
# PageRank on the marriage network of Renaissance Florence (Padgett & Ansell 1993) F = nx.florentine_families_graph() names = list(F.nodes); Af = nx.to_numpy_array(F, nodelist=names) Pw = Af / Af.sum(1, keepdims=True) # random-walk transition matrix alpha = 0.85; pr = np.ones(len(names)) / len(names) for it in range(100): # power iteration pr = alpha * pr @ Pw + (1 - alpha) / len(names) ref = nx.pagerank(F, alpha=alpha) print('max difference from networkx:', f'{max(abs(pr[i] - ref[n]) for i, n in enumerate(names)):.1e}') deg_share = Af.sum(1) / Af.sum() for i in np.argsort(-pr)[:5]: print(f'{names[i]:12s} PageRank {pr[i]:.3f} share of marriage ties {deg_share[i]:.3f}')
max difference from networkx: 1.2e-06 Medici PageRank 0.146 share of marriage ties 0.150 Guadagni PageRank 0.098 share of marriage ties 0.100 Strozzi PageRank 0.088 share of marriage ties 0.100 Albizzi PageRank 0.079 share of marriage ties 0.075 Tornabuoni PageRank 0.071 share of marriage ties 0.075
Padgett and Ansell (1993) reconstructed the marriage ties among sixteen elite Florentine families of the early fifteenth century (fifteen appear in the network) to explain how the Medici, not the wealthiest family, came to dominate the city: they sat at the hub of a network whose other members were poorly connected to each other. A hundred power iterations reproduce networkx's PageRank to \(10^{-6}\). The Medici rank first with 0.146. On an undirected graph PageRank is close to the share of ties (Proposition 9.6), and teleportation pulls the scores slightly toward uniform; the two measures part company on directed graphs, where a link from an important page counts for more than a link from an obscure one.
A walk takes discrete steps; heat diffusion is its continuous-time version. Heat \(h(t)\) on the nodes flows across each edge at a rate proportional to the temperature difference, \(\frac{dh}{dt}=-Lh\), so
$$h(t)=e^{-tL}h(0)=\sum_ke^{-\lambda_kt}\,(u_k^\top h(0))\,u_k.$$Each eigenvector decays at the rate of its eigenvalue: rough patterns die quickly, smooth ones slowly, and as \(t\to\infty\) only the constant survives (Exercise 9). Try it in the widget of Section 4. The matrix \(e^{-tL}\) is positive semi-definite, the diffusion kernel of Kondor and Lafferty (2002), so the whole of Lecture 7 (SVMs, kernel ridge regression, Gaussian processes) can be run on the nodes of a graph.
On a connected undirected graph with no teleportation, a random walk spends what fraction of its time at a node of degree 6 if the degrees sum to 156 (as in the karate club)?
A continuous-time quantum walk on a graph evolves a quantum state by \(|\psi(t)\rangle=e^{-iLt}|\psi(0)\rangle\): the heat equation with time made imaginary, the Schrödinger equation with the Laplacian as Hamiltonian (Farhi and Gutmann, 1998). Where heat spreads diffusively and settles to the uniform distribution, the quantum walk spreads ballistically and keeps interfering with itself. Childs et al. (2003) used this to find an exponential quantum speed-up: on two binary trees glued together at their leaves, a quantum walk crosses from one root to the other in polynomial time, while any classical algorithm needs exponentially many queries. Quantum walks also underlie Grover-type search on graphs and are natural to simulate on quantum hardware, because \(e^{-iLt}\) is exactly the kind of evolution such hardware performs.
Label propagation uses only the graph; a classifier like logistic regression uses only each node's features. Graph neural networks use both, by alternating "mix with your neighbours" with "transform the features", and learning the transformation.
2,708 machine-learning papers in 7 topics (neural networks, probabilistic methods, theory, …) and the 5,278 citation links between them; each paper is described by which of 1,433 dictionary words it contains (McCallum et al., 2000; Sen et al., 2008). We use the standard "Planetoid" split of Yang, Cohen and Salakhutdinov (2016): 140 labelled papers (20 per topic, 5.2% of the total), 500 for validation and 1,000 for testing.
import scipy.sparse as sp def load_cora(): """Planetoid version of Cora (Yang, Cohen & Salakhutdinov 2016): 2,708 papers, 1,433 word features, 7 topics.""" o = {s: pickle.load(open(f'data/ind.cora.{s}', 'rb'), encoding='latin1') for s in ['x', 'y', 'tx', 'ty', 'allx', 'ally', 'graph']} test_idx = np.array([int(l) for l in open('data/ind.cora.test.index')]) X = sp.vstack([o['allx'], o['tx']]).toarray(); Y = np.vstack([o['ally'], o['ty']]) order = np.sort(test_idx); X[test_idx] = X[order]; Y[test_idx] = Y[order] # standard reordering n = X.shape[0]; A = np.zeros((n, n)) for i, nb in o['graph'].items(): for j in nb: if i != j: A[i, j] = A[j, i] = 1 return A, X, Y.argmax(1), np.arange(140), np.arange(140, 640), np.sort(test_idx)[:1000] A, Xc, yc, tr_i, va_i, te_i = load_cora() print(f'{len(A)} papers, {int(A.sum() // 2)} citation links, {Xc.shape[1]} word features, {yc.max() + 1} topics;' f' {len(tr_i)} labelled ({len(tr_i) / len(A):.1%}), {len(te_i)} test') # 1) the graph alone: harmonic label propagation from the 140 labelled papers Lc = np.diag(A.sum(1)) - A u = np.setdiff1d(np.arange(len(A)), tr_i) Fu = np.linalg.solve(Lc[np.ix_(u, u)] + 1e-9 * np.eye(len(u)), A[np.ix_(u, tr_i)] @ np.eye(7)[yc[tr_i]]) pred_lp = np.zeros(len(A), int); pred_lp[tr_i] = yc[tr_i]; pred_lp[u] = Fu.argmax(1) print(f'label propagation (links only): test accuracy {np.mean(pred_lp[te_i] == yc[te_i]):.3f}') # 2) the words alone: logistic regression on the 140 labelled papers from sklearn.linear_model import LogisticRegression lr = LogisticRegression(C=1.0, max_iter=2000).fit(Xc[tr_i], yc[tr_i]) print(f'logistic regression (words only): test accuracy {lr.score(Xc[te_i], yc[te_i]):.3f}')
2708 papers, 5278 citation links, 1433 word features, 7 topics; 140 labelled (5.2%), 1000 test label propagation (links only): test accuracy 0.717 logistic regression (words only): test accuracy 0.576
The citation graph alone, via label propagation from 140 labelled papers, gets 71.7% of the test papers' topics right; the words alone, via logistic regression on the same 140 papers, get 57.6%. Papers cite papers on the same topic, so the graph is the stronger signal here. Kipf and Welling's graph convolutional network (2017) combines them:
$$H^{(1)}=\mathrm{ReLU}\big(\hat AXW^{(1)}\big),\qquad Z=\operatorname{softmax}\big(\hat AH^{(1)}W^{(2)}\big),\qquad\hat A=\tilde D^{-1/2}(A+I)\tilde D^{-1/2},$$where \(\tilde D\) is the degree matrix of \(A+I\). Each layer averages features over a node and its neighbours (with the symmetric normalisation of \(L_{\text{sym}}\)), then applies a learned linear map and a nonlinearity. Two layers let information travel two hops. With \(W=I\) and no nonlinearity, \(\hat A^kX\) is just \(k\) rounds of label propagation applied to features; the GCN learns what to propagate.
# 3) both: a two-layer graph convolutional network (Kipf & Welling 2017), in numpy with hand-written gradients d = (A + np.eye(len(A))).sum(1) A_hat = (A + np.eye(len(A))) / np.sqrt(d[:, None] * d[None, :]) # D^-1/2 (A + I) D^-1/2 Xn = Xc / np.maximum(Xc.sum(1, keepdims=True), 1) # row-normalised word counts AX = A_hat @ Xn # first propagation, computed once def gcn_train(seed, hidden=16, lr=0.01, wd=5e-4, p_drop=0.5, epochs=200): r = np.random.default_rng(seed) W1 = r.uniform(-1, 1, (Xn.shape[1], hidden)) * np.sqrt(6 / (Xn.shape[1] + hidden)) # Glorot initialisation W2 = r.uniform(-1, 1, (hidden, 7)) * np.sqrt(6 / (hidden + 7)) params = [W1, W2]; m = [np.zeros_like(W) for W in params]; v = [np.zeros_like(W) for W in params] Y1 = np.eye(7)[yc[tr_i]]; best = (-1, None) for t in range(1, epochs + 1): Z1 = AX @ W1; H = np.maximum(Z1, 0) mask = (r.random(H.shape) > p_drop) / (1 - p_drop); Hd = H * mask # dropout Z2 = A_hat @ (Hd @ W2) P = np.exp(Z2 - Z2.max(1, keepdims=True)); P /= P.sum(1, keepdims=True) dZ2 = np.zeros_like(Z2); dZ2[tr_i] = (P[tr_i] - Y1) / len(tr_i) # softmax cross-entropy on labelled nodes G2 = A_hat @ dZ2 # A_hat is symmetric gW2 = Hd.T @ G2 + wd * W2 dH = (G2 @ W2.T) * mask * (Z1 > 0) gW1 = AX.T @ dH + wd * W1 for i, (W, g) in enumerate(zip(params, [gW1, gW2])): # Adam (Lecture 2) m[i] = 0.9 * m[i] + 0.1 * g; v[i] = 0.999 * v[i] + 0.001 * g * g W -= lr * (m[i] / (1 - 0.9**t)) / (np.sqrt(v[i] / (1 - 0.999**t)) + 1e-8) out = A_hat @ (np.maximum(AX @ W1, 0) @ W2) # evaluation: no dropout va = np.mean(out[va_i].argmax(1) == yc[va_i]) if va > best[0]: best = (va, out.argmax(1)) return best accs = [] for s in range(5): va, pred = gcn_train(s) accs.append(np.mean(pred[te_i] == yc[te_i])) print(f'GCN (links and words), 5 seeds: test accuracy {np.mean(accs):.3f} ± {np.std(accs):.3f} {np.round(accs, 3)}')
GCN (links and words), 5 seeds: test accuracy 0.812 ± 0.004 [0.814 0.817 0.809 0.806 0.813]
81.2% (±0.4 across five initialisations), matching the 81.5% that Kipf and Welling reported, from 140 labels, with sixteen hidden units and gradients written out by hand: the backward pass is the chain rule through two matrix products and a ReLU, the subject of Lecture 10. The GCN beats both of its ingredients by a wide margin.
A message-passing neural network (Gilmer et al., 2017) updates each node's hidden state \(h_v\) in rounds:
$$m_v^{(t)}=\bigoplus_{u\in N(v)}\psi^{(t)}\big(h_v^{(t)},h_u^{(t)},e_{uv}\big),\qquad h_v^{(t+1)}=\phi^{(t)}\big(h_v^{(t)},m_v^{(t)}\big),$$where \(\bigoplus\) is a permutation-invariant aggregation (sum, mean or max), \(e_{uv}\) are edge features, and \(\psi,\phi\) are learned networks.
GCNs, GraphSAGE, graph attention networks (whose aggregation weights are learned attention scores, Lecture 12) and GIN are all special cases, and all are equivariant by the argument of Proposition 9.1.
Stacking many message-passing layers is not straightforward. Repeated averaging is diffusion, and like heat it smooths node states toward a constant (Exercise 9): the problem of oversmoothing, which is why most GNNs use two to four layers, plus residual connections (Lecture 11) when they go deeper.
In a two-layer GCN, the prediction for a paper depends on which other papers?
Google Maps predicts travel times with a graph neural network over road segments, which cut estimated-time-of-arrival errors by up to 50% in some cities (Derrow-Pinion et al., 2021). Pinterest's PinSage (Ying et al., 2018) runs graph convolutions on a graph of three billion pins and boards to recommend content. In chemistry, message-passing networks predict molecular properties and helped find the antibiotic halicin (Stokes et al., 2020); DeepMind's GNoME used GNNs to propose 2.2 million new crystal structures (Merchant et al., 2023). Banks flag fraud rings through the transaction graph, and AlphaFold 2 passes information over a representation of all pairs of amino-acid residues, a graph neural network in all but name. Every one of these is an instance of Definition 9.6.
To predict a property of a whole graph (is this molecule mutagenic?), run message passing and then pool the node states into one vector with an invariant readout (sum, mean or max over nodes, Proposition 9.1), and feed it to a classifier. Sum readouts can count (how many nitro groups?), which mean and max cannot (Exercise 7). On MUTAG, we compare three graph representations with the same logistic-regression classifier and 10-fold cross-validation: counts of each atom type, ignoring bonds entirely; a three-layer GIN-style network with random weights and sum readouts; and counts of Weisfeiler–Leman colours, defined next.
# Graph classification on MUTAG: a GNN with sum readout, against an atom-count baseline from sklearn.model_selection import StratifiedKFold yM = np.array([m[2] for m in mols]) def gnn_features(mol, Ws): A_, atom_, _ = mol H = np.eye(7)[atom_]; reps = [H.sum(0)] for W in Ws: # GIN-style layer: sum over self and neighbours, then MLP H = np.maximum(0, (A_ + np.eye(len(A_))) @ H @ W) reps.append(H.sum(0)) # sum readout after every layer return np.concatenate(reps) def wl_histograms(mols, iters=3): """Weisfeiler-Leman colour refinement; returns, per molecule, counts of every colour seen.""" cols = [m[1].astype(str) for m in mols]; feats = [dict() for _ in mols] for it in range(iters + 1): for g, (A_, _, _) in enumerate(mols): for c in cols[g]: feats[g][c] = feats[g].get(c, 0) + 1 cols = [np.array([c[i] + '|' + ','.join(sorted(c[np.where(A_[i])[0]])) for i in range(len(c))]) for c, (A_, _, _) in zip(cols, mols)] vocab = sorted({k for f in feats for k in f}); ix = {k: i for i, k in enumerate(vocab)} M = np.zeros((len(mols), len(vocab))) for g, f in enumerate(feats): for k_, c in f.items(): M[g, ix[k_]] = c return M def cv_accuracy(Xf): accs = [] for tr, te in StratifiedKFold(10, shuffle=True, random_state=0).split(Xf, yM): mu, sd = Xf[tr].mean(0), Xf[tr].std(0) + 1e-9 clf = LogisticRegression(C=0.1, max_iter=5000).fit((Xf[tr] - mu) / sd, yM[tr]) accs.append(clf.score((Xf[te] - mu) / sd, yM[te])) return np.mean(accs), np.std(accs) atom_counts = np.array([np.bincount(m[1], minlength=7) for m in mols]) print('atom-count "fingerprint" + logistic regression: %.3f ± %.3f' % cv_accuracy(atom_counts)) r = np.random.default_rng(0) Ws = [r.standard_normal((7, 64)) / np.sqrt(7), r.standard_normal((64, 64)) / np.sqrt(64), r.standard_normal((64, 64)) / np.sqrt(64)] G_feat = np.array([gnn_features(m, Ws) for m in mols]) print('3-layer GNN (random weights) + sum readout: %.3f ± %.3f' % cv_accuracy(G_feat)) print('Weisfeiler-Leman colour counts (3 rounds): %.3f ± %.3f' % cv_accuracy(wl_histograms(mols))) # Relabelling the atoms does not change the graph-level representation Pm = np.eye(len(mols[0][1]))[r.permutation(len(mols[0][1]))] perm_mol = (Pm @ mols[0][0] @ Pm.T, (Pm @ np.arange(len(mols[0][1]))).astype(int), 0) perm_mol = (perm_mol[0], mols[0][1][perm_mol[1]], 0) print('relabelled molecule, max change in representation:', np.abs(gnn_features(perm_mol, Ws) - G_feat[0]).max())
atom-count "fingerprint" + logistic regression: 0.850 ± 0.064 3-layer GNN (random weights) + sum readout: 0.840 ± 0.055 Weisfeiler-Leman colour counts (3 rounds): 0.830 ± 0.067 relabelled molecule, max change in representation: 8.526512829121202e-14
All three land at 83–85% with standard deviations of about 6 points over folds: statistically indistinguishable, and a counting baseline that ignores every bond is as good as the rest. Trained GNNs report around 89% on MUTAG (Xu et al., 2019), within a standard deviation of these. This is a known problem with small graph benchmarks: Errica et al. (2020) found that, under a fair and consistent protocol, structure-agnostic baselines match or beat several published GNNs on such datasets. Relabelling the atoms of a molecule changes its representation by \(10^{-13}\), as Proposition 9.1 promises.
What can message passing distinguish at all? The classic answer comes from graph isomorphism testing.
The (one-dimensional) Weisfeiler–Leman (WL) test starts by colouring every node by its label (or all the same colour) and repeatedly recolours each node by the pair (its colour, the multiset of its neighbours' colours), giving each distinct pair a new colour.
Two graphs whose colour histograms differ at some round are certainly not isomorphic; if the histograms never differ, the test cannot tell them apart.
If two graphs receive the same WL colour histogram after \(t\) rounds, then every \(t\)-layer message-passing GNN (Definition 9.6, any aggregation, any readout of the node multiset) maps them to the same embedding.
Conversely, a GNN whose aggregation and update are injective on multisets, such as the graph isomorphism network (GIN), with sum aggregation followed by a multilayer perceptron, distinguishes every pair of graphs that WL distinguishes (Xu et al., 2019; Morris et al., 2019).
By induction on rounds: if two nodes have the same WL colour after round \(t\), they have the same GNN state after layer \(t\). Initially both are functions of the node label. If two nodes share a WL colour at round \(t+1\), they had the same colour and the same multiset of neighbour colours at round \(t\), hence (induction) the same state and the same multiset of neighbour states, hence the same message and the same updated state. Equal colour histograms then give equal multisets of node states and equal readouts.
For the converse, sums of a suitable feature map are injective on bounded multisets, and an MLP can approximate such a map. \(\square\)
# What message passing cannot see: a hexagon versus two triangles hexagon = nx.to_numpy_array(nx.cycle_graph(6)).astype(int) triangles = nx.to_numpy_array(nx.disjoint_union(nx.cycle_graph(3), nx.cycle_graph(3))).astype(int) same_atom = np.zeros(6, int) pair = [(hexagon, same_atom, 0), (triangles, same_atom, 0)] print('WL colour counts equal:', np.array_equal(*wl_histograms(pair))) for s in range(3): rs = np.random.default_rng(s) W_ = [rs.standard_normal((7, 16)), rs.standard_normal((16, 16)), rs.standard_normal((16, 16))] e1, e2 = gnn_features(pair[0], W_), gnn_features(pair[1], W_) print(f'random GNN {s}: max |embedding(hexagon) - embedding(two triangles)| = {np.abs(e1 - e2).max():.1e}') print('but the graphs differ: number of triangles', int(np.trace(np.linalg.matrix_power(hexagon, 3)) / 6), 'versus', int(np.trace(np.linalg.matrix_power(triangles, 3)) / 6), '; connected?', nx.is_connected(nx.from_numpy_array(hexagon)), nx.is_connected(nx.from_numpy_array(triangles)))
WL colour counts equal: True random GNN 0: max |embedding(hexagon) - embedding(two triangles)| = 0.0e+00 random GNN 1: max |embedding(hexagon) - embedding(two triangles)| = 0.0e+00 random GNN 2: max |embedding(hexagon) - embedding(two triangles)| = 0.0e+00 but the graphs differ: number of triangles 0 versus 2 ; connected? True False
A hexagon and two separate triangles: every node in both has degree 2 and neighbours of degree 2, so WL colours never split and every message-passing network, whatever its weights, gives the two graphs identical embeddings (difference exactly 0). Yet one is connected and the other is not, and one has two triangles and the other none. Message passing cannot count triangles or detect cycles of a given length, which matters in chemistry, where ring structure is everything. Remedies add what WL lacks: higher-order WL tests on tuples of nodes (Morris et al., 2019), counts of substructures as features, random node identifiers, or positional encodings from Laplacian eigenvectors (Section 4) as extra node features, which is how graph transformers (Lecture 12) see structure.
Every node of a graph \(G_1\) and of a graph \(G_2\) has degree 3, both graphs have 8 nodes, and all node features are equal. What can a message-passing GNN conclude?
Next: Lecture 10 opens Part III with the neural networks themselves: what a network of ReLU units computes, how depth multiplies its expressive power, and how backpropagation trains it.
\(L=\begin{pmatrix}1&-1&0\\-1&2&-1\\0&-1&1\end{pmatrix}\), with eigenvalues 0, 1, 3 and eigenvectors \((1,1,1)\), \((1,0,-1)\), \((1,-2,1)\) (unnormalised). The Fiedler vector \((1,0,-1)\) puts the two ends on opposite sides and the middle node exactly at zero: the path has no unique best split.
For a unit vector \(f\), \(f^\top Lf=\sum_{\text{edges}}W_{ij}(f_i-f_j)^2\le\sum_{\text{edges}}2W_{ij}(f_i^2+f_j^2)=2\sum_id_if_i^2\le2d_{\max}\). The bound is attained by bipartite regular graphs with \(f=\pm1\) on the two sides.
At \(\alpha=1\), \(G=P\), and Proposition 9.6 gives the degree distribution as its unique stationary distribution (unique because the graph is connected). The stationary distribution of \(G\) depends continuously on \(\alpha\). With \(\alpha=0.85\), the Medici's 0.146 is close to their 0.150 share of ties, slightly pulled toward the uniform \(1/15\approx0.067\).
The averaging condition \(f_i=\frac12(f_{i-1}+f_{i+1})\) says the second difference is zero, so \(f\) is linear in \(i\); the boundary values fix it. By Theorem 9.4 this is the only solution.
Dividing every column by the same constant does not change which column is largest. When the class-1 label sits in a hub, its column has large values everywhere (walks from everywhere hit it early), so its mass is inflated; dividing by the mass removes that global advantage and leaves the local comparison of each node's relative closeness to each label.
The log density in \(f_u\) is \(-\frac12f_u^\top(L_{uu}+\varepsilon I)f_u-f_u^\top L_{u\ell}f_\ell+\text{const}\), a Gaussian with precision \(L_{uu}+\varepsilon I\) and mean \(-(L_{uu}+\varepsilon I)^{-1}L_{u\ell}f_\ell\). Since \(L_{u\ell}=-W_{u\ell}\) and \(L_{uu}\) is invertible (Theorem 9.4), the limit is \(L_{uu}^{-1}W_{u\ell}f_\ell\), the harmonic solution.
Every node in both graphs has degree 2 and the same features, so every node ends with the same state \(h\) in both. The mean readout gives \(h\) for both; the sum gives \(3h\) against \(6h\), which differ whenever \(h\ne0\). The hexagon and two triangles both have six nodes in state \(h\), so even the sum gives \(6h\) for both (Theorem 9.8).
Initially all colours are equal; a node's new colour depends on its colour and the multiset of \(d\) equal neighbour colours, the same for all nodes. By induction this persists. Examples: the cube graph \(Q_3\) (connected, no triangles) and two disjoint copies of \(K_4\) (disconnected, eight triangles).
\(L\mathbf 1=0\) gives \(e^{-tL}\mathbf 1=\mathbf 1\), and since \(L\) is symmetric, \(\mathbf 1^\top e^{-tL}=\mathbf 1^\top\). In the eigen-expansion every term with \(\lambda_k>0\) decays, leaving the projection onto \(u_1=\mathbf 1/\sqrt n\). Repeated neighbourhood averaging behaves the same way: node states converge to a common value and lose the information that distinguishes nodes, which is oversmoothing.
\((A^3)_{ii}\) counts closed walks of length 3 from \(i\), which are triangles through \(i\) traversed in either direction; each triangle is counted from each of its 3 vertices in 2 directions. Invariance: \(\operatorname{tr}((PAP^\top)^3)=\operatorname{tr}(PA^3P^\top)=\operatorname{tr}(A^3)\).
Each project uses this lecture's methods and public data, and has a clear result.
Data. MUTAG: A. K. Debnath et al., "Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds", J. Medicinal Chemistry 34(2), 786–797 (1991); C. Morris et al., "TUDataset: a collection of benchmark datasets for learning with graphs", ICML Workshop on Graph Representation Learning (2020); copy from github.com/weihua916/powerful-gnns. Cora: A. McCallum, K. Nigam, J. Rennie, K. Seymore, "Automating the construction of internet portals with machine learning", Information Retrieval 3, 127–163 (2000); P. Sen et al., "Collective classification in network data", AI Magazine 29(3), 93–106 (2008); Z. Yang, W. Cohen, R. Salakhutdinov, "Revisiting semi-supervised learning with graph embeddings", ICML (2016), files from github.com/kimiyoung/planetoid. Karate club and Florentine families: in networkx. MNIST: as in Lecture 4.
every number in the text and widgets is computed in verify_L09.py; code-box outputs are pasted from actual runs