Graph Neural Network

A graph neural network (GNN) is a neural network whose input is a graph: a set of nodes with feature vectors, joined by edges that may carry features of their own. Each layer updates every node from its own state and the states of its neighbours, using the same learned functions at every node and every edge, and a readout pools the node states when the whole graph needs one answer. Images are already graphs of a special kind, a regular grid on which a convolution is a fixed-size neighbourhood operation, but much of what vision works with is not a grid: superpixels and their adjacencies, detected objects and their relations, body joints connected by bones, points in a point cloud, the vertices of a mesh, and regions tracked through a video. Graph neural networks give these structures a learned model that does not depend on how the nodes happen to be numbered.

Core Idea

A graph has no canonical order of its nodes and no fixed number of neighbours per node. A fully connected layer applied to the concatenated node features would depend on the order in which the nodes were listed, and would need a new weight matrix for every graph size. A graph layer avoids both problems with two choices:

• Aggregate over the neighbourhood with a symmetric function. A sum, a mean or a weighted average of the neighbours’ messages gives the same result whatever the order of the neighbours.
• Share the weights. The same small network transforms every node’s input, as a convolution applies one kernel at every pixel. Wu et al. (2019, §2.1) describe a $K$-layer graph convolutional network as a $K$-layer multilayer perceptron applied to each node’s feature vector, except that each node’s hidden representation is averaged with its neighbours’ at the start of every layer.

Stacking layers widens each node’s view: after $k$ layers a node has received information from every node at most $k$ hops away, the graph counterpart of a growing receptive field, as Wu et al. note (§2.2).

Building Blocks

Graphs from images. The nodes and edges have to come from somewhere, and in vision the choice of graph is a large part of the model:

• Superpixels. Monti et al. (2017, §5.1) represented MNIST digits as graphs whose vertices are superpixels and whose edges join neighbouring ones, a different graph for every image, with polar coordinates between superpixel barycentres as the pseudo-coordinates of each edge.
• Objects and relations. In a scene graph, nodes are detected objects with their boxes and categories and edges are the relationships between pairs of objects (Xu et al., 2017, §3). Visual Genome annotates such graphs.
• Space-time regions. Wang and Gupta (2018, §4) take object proposals from the frames of a video as nodes and join them in two ways: by a learned similarity between proposals in any frames, and by the overlap (intersection over union) of proposals in consecutive frames.
• Skeletons, point clouds and meshes. The body’s joints and bones form a fixed graph (skeleton-based action recognition); a point cloud is usually turned into a graph by joining each point to its nearest neighbours (point cloud segmentation); a polygon mesh brings its vertices and edges with it.

Message, update and readout functions. Gilmer et al. (2017) gathered several earlier models into one framework, the message passing neural network (MPNN). A forward pass has a message passing phase of $T$ steps, in which each node sums messages from its neighbours and updates its hidden state, followed by a readout phase that computes one vector for the whole graph. The message, update and readout functions are all learned and differentiable (§2).

Edge features. Edges can carry vectors (a bond type, a distance, a relative position, an overlap). Gilmer et al.’s edge network maps each edge’s feature vector through a network to a $d \times d$ matrix that multiplies the neighbour’s state (§5.1), and MoNet weights each neighbour by a function of geometric pseudo-coordinates (below).

Readout. For graph-level outputs the node states are pooled by a function that does not depend on node order: a sum of the final states passed through a network, as in interaction networks, a gated sum, as in gated graph neural networks, or the set2set model, which Gilmer et al. use because it is designed for sets and should be more expressive than a sum (§2, §5.3). Wang and Gupta average the object node features into one vector and concatenate it with a pooled video feature for classification (§5).

How Data Flows

A typical graph network for vision has four stages:

1. Build the graph. A detector, a superpixel algorithm, a pose estimator or a nearest-neighbour search proposes the nodes and edges.
2. Initialize node features. Usually from a convolutional neural network: region features pooled from a backbone’s feature map (Xu et al.; Wang and Gupta, who use I3D), image features sampled at a mesh vertex’s projection (Pixel2Mesh), or raw coordinates (skeleton joints, points).
3. Pass messages. $T$ graph layers, each a neighbourhood aggregation followed by a shared transformation and a nonlinearity, sometimes with residual connections or normalization between layers.
4. Predict. Per-node outputs for node tasks (an object’s class, a vertex’s new position), per-edge outputs for relations, or a readout for a graph-level label (an action, a digit, a molecule’s property).

Mathematical Formulation

Message passing. Write $\mathbf{h}_v^t$ for the hidden state of node $v$ after $t$ steps, $N(v)$ for its neighbours and $\mathbf{e}_{vw}$ for the features of edge $(v, w)$. Gilmer et al. (Eqs. 1–3) write one step and the readout as

$$\mathbf{m}_v^{t+1} = \sum_{w \in N(v)} M_t\big(\mathbf{h}_v^t, \mathbf{h}_w^t, \mathbf{e}_{vw}\big), \qquad \mathbf{h}_v^{t+1} = U_t\big(\mathbf{h}_v^t, \mathbf{m}_v^{t+1}\big), \qquad \hat{y} = R\big(\{\mathbf{h}_v^T \mid v \in G\}\big).$$

Different models are different choices of $M_t$, $U_t$ and $R$. Gated graph neural networks use a learned matrix per edge type as the message and a GRU as the update, with weights tied across steps. Kipf and Welling’s graph convolutional network, in Gilmer et al.’s reformulation, uses the message $c_{vw}\mathbf{h}_w^t$ with $c_{vw} = (\deg(v)\deg(w))^{-1/2}A_{vw}$ and the update $\operatorname{ReLU}(W_t \mathbf{m}_v^{t+1})$ (§2).

Graph convolutional network (GCN). The GCN of Kipf and Welling (2017), whose paper is on a host not used for this article and is described here through Wu et al. (2019) and Gilmer et al. (2017), writes one layer for all nodes at once. With adjacency matrix $\mathbf{A}$, self-loops added as $\tilde{\mathbf{A}} = \mathbf{A} + \mathbf{I}$ and $\tilde{\mathbf{D}}$ the diagonal degree matrix of $\tilde{\mathbf{A}}$, Wu et al. (Eqs. 3–5) give

$$\mathbf{S} = \tilde{\mathbf{D}}^{-1/2}\tilde{\mathbf{A}}\tilde{\mathbf{D}}^{-1/2}, \qquad \mathbf{H}^{(k)} = \operatorname{ReLU}\big(\mathbf{S}\mathbf{H}^{(k-1)}\boldsymbol{\Theta}^{(k)}\big), \qquad \mathbf{H}^{(0)} = \mathbf{X}.$$

Row by row, node $i$ with degree $d_i$ first becomes $\mathbf{h}_i/(d_i + 1) + \sum_j a_{ij}\mathbf{h}_j/\sqrt{(d_i+1)(d_j+1)}$, a weighted average with its neighbours (Eq. 2), and then passes through the same fully connected layer $\boldsymbol{\Theta}^{(k)}$ as every other node. Wu et al. call $\mathbf{S}$ the normalized adjacency with self-loops; adding the self-loops is Kipf and Welling’s “renormalization trick”.

Spectral view. In the spectral definition, the eigenvectors of the graph Laplacian play the role of Fourier modes and a filter multiplies each graph frequency by a coefficient (Wu et al., §3.1). Wu et al. (§3 and §4.1) summarize the line: Bruna et al. (2014) proposed spectral graph convolutions, Defferrard et al. (2016, ChebNet) approximated the filters by Chebyshev polynomials to avoid computing the eigenvectors, and the GCN kept only a first-order approximation. Wu et al. show that adding self-loops shrinks the spectrum of the normalized Laplacian (their Theorem 1), so that powers of $\mathbf{S}$ act as low-pass filters: the filter coefficient at Laplacian eigenvalue $\tilde{\lambda}$ is $(1 - \tilde{\lambda})^K$. Monti et al. (§1.1) point out the weakness of a purely spectral definition: the filters are expressed in one graph’s Fourier basis, so a model learned on one graph does not transfer directly to a graph with a different basis.

Simple graph convolution (SGC). Wu et al. removed the nonlinearities between GCN layers and collapsed the weight matrices into one, giving (Eq. 8)

$$\hat{\mathbf{Y}}_{\text{SGC}} = \operatorname{softmax}\big(\mathbf{S}^K \mathbf{X} \boldsymbol{\Theta}\big).$$

The features $\mathbf{S}^K\mathbf{X}$ have no parameters and can be computed once, so training reduces to multinomial logistic regression on the propagated features.

Attention on graphs. Graph attention networks (Veličković et al., 2018; not read for this article, its paper being on a host not used) belong to the models that, in Wu et al.’s summary (§4.1), learn to assign different edge weights at each layer based on node features; Wu et al. add that attention usually adds significant computation and memory. A readable vision example of learned, feature-dependent edge weights is Wang and Gupta’s similarity graph: the affinity of proposals $i$ and $j$ is $\phi(\mathbf{x}_i)^\top\phi'(\mathbf{x}_j)$ with two learned linear maps, normalized over each row by a softmax (Eqs. 1–2), the form of self-attention’s weights without the scaling by the key dimension; a graph layer is then $\mathbf{Z} = \mathbf{G}\mathbf{X}\mathbf{W}$ (Eq. 4).

Permutation equivariance. Renumber the nodes with a permutation matrix $\mathbf{P}$, so that the features become $\mathbf{P}\mathbf{X}$ and the adjacency $\mathbf{P}\mathbf{A}\mathbf{P}^\top$. A node-level layer $f$ is equivariant if

$$f\big(\mathbf{P}\mathbf{A}\mathbf{P}^\top, \mathbf{P}\mathbf{X}\big) = \mathbf{P}\, f(\mathbf{A}, \mathbf{X}),$$

so that renumbering the input renumbers the output in the same way, and a readout $R$ is invariant if $R(\mathbf{P}\mathbf{A}\mathbf{P}^\top, \mathbf{P}\mathbf{X}) = R(\mathbf{A}, \mathbf{X})$. The GCN layer is equivariant because $\mathbf{P}\mathbf{S}\mathbf{P}^\top\mathbf{P}\mathbf{X} = \mathbf{P}\mathbf{S}\mathbf{X}$ and the shared weight matrix and pointwise nonlinearity act on each row separately. Gilmer et al. (§2) state the requirement for the readout: it must be invariant to permutations of the node states for the network to be invariant to graph isomorphism. A fully connected layer on the flattened features has neither property, as the example below checks.

Why It Works

Neighbouring nodes in the graphs vision builds tend to share labels: adjacent superpixels usually belong to the same object, and consecutive detections of one object are the same object. Averaging over neighbours then removes noise that is independent from node to node while keeping what neighbours share. Li, Han and Wu (2018) show that the GCN’s graph convolution is a special form of Laplacian smoothing, which makes the features of vertices in the same cluster similar and so eases classification; they name this as the key reason GCNs work. Wu et al. reach a compatible conclusion from the other side: since SGC, with a fixed low-pass filter and a linear classifier, matched the GCN on their benchmarks, they consider it likely that the GCN’s expressive power comes mainly from the repeated propagation rather than from the nonlinear feature extraction (§6). The same averaging spreads information from the few labelled nodes to unlabelled ones, which relates graph networks to the classical label propagation methods Wu et al. survey (§4.2) and to the random walker in interactive segmentation, which spreads seed labels across the pixel graph.

Training Considerations

Depth and over-smoothing. Repeated averaging is also a weakness. Li et al. illustrate it with untrained GCNs of one to five layers on Zachary’s karate club network: after two smoothing steps the two classes separate fairly well, and with more steps their points mix (Fig. 2). They prove that repeated smoothing makes the features of all nodes in a connected component converge to a fixed pattern, so that over-smoothing makes the features indistinguishable and hurts classification (Theorem 1). Their text says that with symmetric normalization the features converge to values proportional to the square root of the vertex degree, while the theorem as printed writes the limit with $\mathbf{D}^{-1/2}$. The text matches the eigenvector: $\mathbf{S}\tilde{\mathbf{D}}^{1/2}\mathbf{1} = \tilde{\mathbf{D}}^{-1/2}\tilde{\mathbf{A}}\mathbf{1} = \tilde{\mathbf{D}}^{1/2}\mathbf{1}$, so the vector of square-rooted degrees is the eigenvector of $\mathbf{S}$ with eigenvalue 1, and the example below measures convergence toward it. The same kind of repeated neighbour averaging is the Laplacian smoothing that shrinks a mesh in the polygon mesh article’s example; there it acts on vertex positions rather than on features. Li et al. add that a deep GCN is also much harder to train.

Reaching far with few layers. Shallow networks see only a few hops. Li et al. note that with few labels a shallow GCN cannot propagate the labels across the whole graph, and they propose co-training with a random-walk model and self-training to enlarge the labelled set. Gilmer et al. add “virtual” edges between unconnected pairs, or a latent master node connected to every node, which serves as global scratch space and lets information travel long distances (§5.2). Pixel2Mesh takes the opposite route and makes the network deep, 14 graph convolutional layers with shortcut connections per block, because each graph convolution exchanges features only between neighbouring vertices (§3.4).

Cost. A message passing step on a dense graph needs $O(n^2 d^2)$ multiplications for $n$ nodes and $d$-dimensional states, which Gilmer et al. reduce by splitting the state into $k$ towers of size $d/k$ (§5.4). Sparse graphs cost in proportion to their edges. SGC precomputes $\mathbf{S}^K\mathbf{X}$ with sparse products; on the Reddit graph Wu et al. report training up to two orders of magnitude faster than sampling-based GCN variants (§5.1, Fig. 3).

Labels. Node classification on a single graph is usually transductive: the whole graph, including the test nodes’ features, is seen during training, and only the labels of the test nodes are hidden. Wu et al.’s citation-network experiments are transductive; their Reddit experiment, which they call inductive, trains on the subgraph of training nodes and tests on the full graph (§5.1).

Variants

• Recurrent message passing. Scarselli et al. (2009), whose paper was not read for this article, defined a message passing process run until convergence rather than for a fixed number of steps, as Gilmer et al. describe it (§3); Monti et al. (§1.1) name Gori et al. (2005) and Scarselli et al. as the earliest attempts they know of to generalize neural networks to graphs. Gated graph neural networks run a fixed number of steps with a shared GRU update.
• Spectral networks and ChebNet, defined through the Laplacian’s eigenvectors or polynomials of the Laplacian (above).
• GCN and its linear simplification SGC. On the Cora, Citeseer and Pubmed citation graphs Wu et al. report test accuracies of 81.0%, 71.9% and 78.9% for SGC against 81.4%, 70.9% and 79.0% for the GCN in their own runs, averaged over 10 runs (Table 2), and 94.9% test micro-F1 for SGC on Reddit (Table 3).
• Spatial models with geometric weights. MoNet (Monti et al., 2017) builds a patch operator from pseudo-coordinates between a node and its neighbours (polar coordinates of superpixel barycentres for images) weighted by learned Gaussian kernels, so the filter is defined locally rather than in one graph’s Fourier basis.
• Attention. Graph attention networks and feature-dependent graphs such as Wang and Gupta’s similarity graph learn their edge weights. The adaptive graphs of skeleton models (2s-AGCN and CTR-GCN in skeleton-based action recognition) do the same for the body graph.
• Edge and relation updates. Some models keep hidden states on edges as well as nodes. Gilmer et al. note this as an option (§2); Xu et al.’s scene graph model keeps one GRU per object and one per relation (below).
• Point graphs. DGCNN performs graph convolutions on nearest-neighbour graphs of points with a module called EdgeConv, as point cloud segmentation describes from its repository and from the Point Transformer authors.

Use in Computer Vision

Superpixel graphs. On MNIST with 300, 150 and 75 superpixels per digit (55,000 training, 10,000 test and 5,000 validation images), Monti et al. report 97.30%, 96.75% and 91.11% accuracy for MoNet against 88.05%, 80.94% and 75.62% for the spectral ChebNet (Table 2). They attribute ChebNet’s drop to each image being a different graph, across which its spectral filters fail to generalize; on the full regular grid shared by every image both reach about 99%.

Scene graphs. Xu et al. (2017) generate a scene graph from an image by iterative message passing. Each object proposal has a node GRU and each pair of proposals an edge GRU, with weights shared among all node GRUs and among all edge GRUs. In the node-centric primal graph each node GRU receives messages from its inbound and outbound edge GRUs, and in the edge-centric dual graph each edge GRU receives messages from its subject and object node GRUs; learned weighted sums pool the incoming messages, and the final hidden states predict object classes, box offsets and relationships (§3). Visual Genome covers the dataset and the recall measures on which scene graph generation is scored.

Skeletons. ST-GCN and its successors treat joints across frames as a spatial-temporal graph, with spatial edges along the bones and temporal edges between the same joint in consecutive frames; skeleton-based action recognition describes the partitions, normalizations and adaptive graphs and runs one layer in its example.

Point clouds and meshes. Nearest-neighbour graphs over points carry graph convolutions for classification and segmentation (point cloud segmentation). Pixel2Mesh (Wang et al., 2018) reconstructs a mesh from a single RGB image by deforming an initial ellipsoid of 156 vertices, raised to 628 and then 2,466 vertices by graph unpooling layers. Each vertex’s feature concatenates its 3D coordinates, a shape feature and image features pooled from a VGG-16 at the vertex’s projection, and a graph convolution updates vertex $p$ as $\mathbf{f}_p^{l+1} = \mathbf{w}_0\mathbf{f}_p^l + \sum_{q \in N(p)} \mathbf{w}_1\mathbf{f}_q^l$, with $\mathbf{w}_1$ shared by all edges so that vertices of any degree are handled (§3.1–§3.5).

Video. Wang and Gupta (2018) recognize actions by reasoning over a graph of 800 object proposals per video (50 per frame over 16 output frames on Charades), with graph convolutions on the similarity graph and on the forward and backward space-time graphs in two branches whose outputs are summed. On the Charades validation set, with a ResNet-50 I3D backbone, they report 31.8% mAP for the backbone alone, 34.2% with the space-time graph, 35.0% with the similarity graph and 36.2% with both, and 37.5% when the backbone is replaced by a non-local network; the graph adds about 3% to the backbone’s FLOPs (Table 2 and §6.1). They also report results on Something-Something. Fusing all three graphs in every layer performed worse than the similarity graph alone, which they attribute to optimization difficulties, hence the two branches (§5).

Knowledge graphs for recognition. Graphs can also connect categories rather than image parts. Wu et al. (§5.2, Table 7) replace the GCN of a zero-shot ImageNet classifier (GCNZ), which maps category names, related through WordNet, to the image-feature domain, by an MLP followed by SGC, and report 21.2% top-1 on unseen categories in the 2-hop setting against 20.9% for their own run of GCNZ, averaged over 10 runs, with 55% fewer parameters.

Example: Propagation Depth and Over-Smoothing on a Superpixel Graph

The example classifies the nodes of a superpixel graph from a few labels with SGC, the propagation-then-logistic-regression model above, and measures what happens as the number of propagation steps $K$ grows. It runs in NumPy 2.3.5, SciPy 1.16.3, scikit-image 0.25.2 and scikit-learn 1.7.2, in about 3 seconds (approximate, measured while other agents shared the machine); two runs gave identical output.

• Image. A $128 \times 128$ RGB image with three known classes: a grey background, two reddish disks and a bluish rectangle and bar; each object colour differs from the background grey by 0.15 in one channel and 0.05 in another. Gaussian noise of standard deviation 0.6 per channel (NumPy seed 0) is added to every pixel. The noise level was fixed by a rule stated before any part of the example was run: the value on a grid from 0.2 to 1.2 at which a logistic regression on the raw superpixel colours, fitted with all labels, scores closest to 75%.
• Graph. SLIC superpixels from scikit-image (256 segments, compactness 0.3, pre-smoothing $\sigma = 1.5$, no Lab conversion) are the nodes; each node’s features are its mean noisy RGB values and its label is the majority class of its pixels. Two superpixels are joined by an unweighted edge when they share a horizontal or vertical pixel border. The script prints the share of pixels whose class matches their superpixel’s label and checks that the graph is connected.
• Propagation. $\mathbf{S} = \tilde{\mathbf{D}}^{-1/2}(\mathbf{A} + \mathbf{I})\tilde{\mathbf{D}}^{-1/2}$ as in SGC, applied $K = 0, 1, 2, 4, \dots, 1024$ times.
• Classifier. At each $K$ the three feature columns are standardized over all nodes (a label-free step, transductive like SGC’s citation experiments), and scikit-learn’s multinomial logistic regression is fitted on 2 labelled nodes per class and scored on the other 250 nodes, for 20 random draws of the labelled nodes (seeds 0–19), printing the mean, minimum and maximum. SGC tunes its weight decay on a validation split, which six labels cannot provide, and the sources leave the regularization open, so two inverse strengths are printed, scikit-learn’s default $C = 1$ and $C = 100$.
• Oracle. As a ceiling, the same classifier with $C = 10^4$ is fitted on all nodes with their true labels and scored on them: how linearly separable the classes are after $K$ steps.
• Spread. With $\mathbf{u}$ the unit vector of square-rooted degrees, the eigenvector of $\mathbf{S}$ with eigenvalue 1, the spread is $\lVert \mathbf{S}^K\mathbf{X} - \mathbf{u}\mathbf{u}^\top\mathbf{S}^K\mathbf{X} \rVert_F / \lVert \mathbf{X} - \mathbf{u}\mathbf{u}^\top\mathbf{X} \rVert_F$, the share of the features left outside the over-smoothed limit. Since $\mathbf{S}$ is symmetric, this share can be at most $\rho^K$, with $\rho$ the largest absolute value among the other eigenvalues; the script prints both.
• Equivariance. A random renumbering of the nodes is applied to a GCN layer with random weights, to $\mathbf{S}^8\mathbf{X}$, to a mean readout and to a fully connected layer on the flattened $256 \times 3$ features.

import numpy as np
from scipy.sparse.csgraph import connected_components
from skimage.segmentation import slic
from sklearn.linear_model import LogisticRegression

# --- a noisy synthetic image with three known classes --------------------------------
H = W = 128
colours = np.array([[0.50, 0.50, 0.50],   # class 0: background
                    [0.65, 0.45, 0.50],   # class 1: two disks
                    [0.45, 0.50, 0.65]])  # class 2: a rectangle and a bar
yy, xx = np.mgrid[0:H, 0:W]
truth = np.zeros((H, W), int)
truth[(yy - 40) ** 2 + (xx - 44) ** 2 <= 34 ** 2] = 1
truth[(yy - 100) ** 2 + (xx - 100) ** 2 <= 16 ** 2] = 1
truth[76:124, 8:64] = 2
truth[8:40, 84:124] = 2
img = colours[truth] + 0.6 * np.random.default_rng(0).standard_normal((H, W, 3))

# --- superpixel graph: nodes, features, labels, edges ---------------------------------
seg = slic(img, n_segments=256, compactness=0.3, sigma=1.5,
           convert2lab=False, start_label=0, channel_axis=-1)
n = seg.max() + 1
size = np.bincount(seg.ravel(), minlength=n)
X = np.stack([np.bincount(seg.ravel(), img[..., c].ravel(), n) / size for c in range(3)], 1)
counts = np.zeros((n, 3))
np.add.at(counts, (seg.ravel(), truth.ravel()), 1)
y = counts.argmax(1)                      # majority class of each superpixel
A = np.zeros((n, n))
for a, b in ((seg[:, :-1], seg[:, 1:]), (seg[:-1, :], seg[1:, :])):
    m = a != b
    A[a[m], b[m]] = A[b[m], a[m]] = 1     # superpixels that share a pixel border
print(f"nodes {n}, per class {np.bincount(y)}, label purity {counts.max(1).sum() / counts.sum():.3f}, "
      f"components {connected_components(A, directed=False)[0]}, majority rate {np.bincount(y).max() / n:.3f}")

# --- SGC propagation matrix S = D~^-1/2 (A + I) D~^-1/2 -------------------------------
At = A + np.eye(n)
deg = At.sum(1)
S = At / np.sqrt(np.outer(deg, deg))
mu = np.sort(np.linalg.eigvalsh(S))[::-1]
rho = max(abs(mu[1]), abs(mu[-1]))
u = np.sqrt(deg) / np.linalg.norm(np.sqrt(deg))   # top eigenvector of S (eigenvalue 1)
print(f"eigenvalues of S: top {mu[0]:.6f}, second {mu[1]:.6f}, smallest {mu[-1]:.6f}; rho {rho:.6f}")


def standardize(Z):
    return (Z - Z.mean(0)) / Z.std(0)


def few_label_accuracy(Z, C, seed, per_class=2):
    rng = np.random.default_rng(seed)
    train = np.concatenate([rng.choice(np.flatnonzero(y == c), per_class, replace=False) for c in range(3)])
    test = np.setdiff1d(np.arange(n), train)
    Zs = standardize(Z)
    clf = LogisticRegression(C=C, max_iter=10000).fit(Zs[train], y[train])
    return clf.score(Zs[test], y[test])


# --- accuracy and spread against the number of propagation steps K ---------------------
Ks = [0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]
seeds = range(20)
R0 = np.linalg.norm(X - np.outer(u, u @ X))
print("    K  oracle | 2 labels/class, C=1: mean (min-max) | C=100: mean (min-max) |  spread   rho^K")
Z, k = X.copy(), 0
for K in Ks:
    while k < K:
        Z, k = S @ Z, k + 1
    oracle = LogisticRegression(C=1e4, max_iter=10000).fit(standardize(Z), y).score(standardize(Z), y)
    row = f"{K:5d}  {oracle:.3f}"
    for C in (1, 100):
        acc = np.array([few_label_accuracy(Z, C, s) for s in seeds])
        row += f" | {acc.mean():.3f} ({acc.min():.3f}-{acc.max():.3f})"
    spread = np.linalg.norm(Z - np.outer(u, u @ Z)) / R0
    print(row + f" | {spread:.2e} {rho ** K:.2e}")

# --- permutation equivariance --------------------------------------------------------
rng = np.random.default_rng(1)
p = rng.permutation(n)
P = np.eye(n)[p]                                   # (P X)[i] = X[p[i]]
Wg = np.random.default_rng(2).standard_normal((3, 8))
gcn_layer = lambda S_, X_: np.maximum(S_ @ X_ @ Wg, 0)
sgc_feat = lambda S_, X_: np.linalg.matrix_power(S_, 8) @ X_
for name, f in (("GCN layer ReLU(S X W)", gcn_layer), ("SGC features S^8 X", sgc_feat)):
    diff = np.abs(f(P @ S @ P.T, P @ X) - P @ f(S, X)).max()
    print(f"{name}: max |f(PSP^T, PX) - P f(S, X)| = {diff:.1e}")
readout = lambda S_, X_: gcn_layer(S_, X_).mean(0)
print(f"mean readout: max |r(PSP^T, PX) - r(S, X)| = {np.abs(readout(P @ S @ P.T, P @ X) - readout(S, X)).max():.1e}")
Wfc = np.random.default_rng(2).standard_normal((3 * n, 3 * n)) / np.sqrt(3 * n)
fc = lambda X_: (Wfc @ X_.ravel()).reshape(n, 3)
print(f"fully connected layer on the flattened features: max |f(PX) - P f(X)| = {np.abs(fc(P @ X) - P @ fc(X)).max():.2f}")

nodes 256, per class [126  68  62], label purity 0.921, components 1, majority rate 0.492
eigenvalues of S: top 1.000000, second 0.991762, smallest -0.589256; rho 0.991762
    K  oracle | 2 labels/class, C=1: mean (min-max) | C=100: mean (min-max) |  spread   rho^K
    0  0.758 | 0.578 (0.460-0.720) | 0.560 (0.332-0.716) | 1.00e+00 1.00e+00
    1  0.930 | 0.812 (0.612-0.916) | 0.794 (0.600-0.908) | 6.39e-01 9.92e-01
    2  0.938 | 0.822 (0.544-0.912) | 0.813 (0.480-0.924) | 5.52e-01 9.84e-01
    4  0.953 | 0.807 (0.548-0.936) | 0.800 (0.512-0.908) | 4.79e-01 9.67e-01
    8  0.910 | 0.758 (0.632-0.848) | 0.757 (0.572-0.876) | 4.05e-01 9.36e-01
   16  0.875 | 0.724 (0.612-0.816) | 0.736 (0.600-0.864) | 3.26e-01 8.76e-01
   32  0.863 | 0.716 (0.616-0.804) | 0.722 (0.560-0.860) | 2.39e-01 7.67e-01
   64  0.836 | 0.705 (0.572-0.812) | 0.707 (0.516-0.852) | 1.46e-01 5.89e-01
  128  0.797 | 0.626 (0.460-0.784) | 0.659 (0.464-0.796) | 6.65e-02 3.47e-01
  256  0.793 | 0.563 (0.360-0.708) | 0.586 (0.352-0.756) | 1.97e-02 1.20e-01
  512  0.793 | 0.475 (0.316-0.648) | 0.535 (0.356-0.672) | 2.31e-03 1.45e-02
 1024  0.496 | 0.484 (0.464-0.496) | 0.481 (0.452-0.496) | 3.31e-05 2.10e-04
GCN layer ReLU(S X W): max |f(PSP^T, PX) - P f(S, X)| = 4.4e-16
SGC features S^8 X: max |f(PSP^T, PX) - P f(S, X)| = 7.8e-16
mean readout: max |r(PSP^T, PX) - r(S, X)| = 6.7e-16
fully connected layer on the flattened features: max |f(PX) - P f(X)| = 2.74

The graph. About 92% of the pixels carry their superpixel’s label, so the node labels are a slightly coarsened version of the true classes, and the graph is connected, which is the case Li et al.’s theorem covers: one component, one limiting direction. The background holds just under half of the nodes, so a classifier that always answered “background” would score about 0.49.

Propagation first helps. From the raw colours, six labels give a classifier that is right on just over half of the unlabelled nodes on average, and even the oracle, fitted with every label, reaches only about three in four: the superpixel means are too noisy to separate the classes by colour. One to four steps of averaging with neighbours, nearly all of which belong to the same region, lift the oracle to 0.93–0.95 and the few-label mean by about 0.24. The spread falls fastest in the first step, far faster than the bound $\rho^K$, which only limits the slowest-decaying component. In our reading of the construction, the noise differs from node to node, so it lies mostly in the high graph frequencies that $\mathbf{S}$ damps most, while the region colours, constant over many neighbouring nodes, lie in the low frequencies it keeps; this is the low-pass filtering Wu et al. describe.

Then it over-smooths. Beyond a few steps the averaging reaches across region borders (in our reading, the smaller objects begin to take on the background’s colour), and accuracy falls, slowly at first and then to about the majority rate by $K = 1024$, where the spread is about $3 \times 10^{-5}$ of its starting value: every node’s features point almost exactly along $\mathbf{u}$, so what remains is mostly the degree pattern, which in our reading has no reason to follow the classes. The spread stays below $\rho^K$ at every $K$, as the bound requires, and both regularization strengths give the same rise and fall, so the conclusion does not depend on that open choice. The range over the 20 draws is wide at every useful $K$ (from about 0.5 to above 0.9 at $K = 2$): which six nodes are labelled matters a great deal, the label-scarcity problem Li et al. raise.

Why the oracle holds at 0.79 from $K = 128$ to 512. The few-label accuracy sinks toward the majority rate over these steps, and below it for $C = 1$ at $K = 512$, while the oracle stays near 0.79. In our reading this follows from the code’s construction. As $K$ grows, each feature column approaches a multiple of the same square-rooted degree pattern, plus a shrinking remainder that still carries class information. Standardization rescales each column to unit variance, and a linear classifier can take differences of columns that cancel the shared degree pattern, leaving only the remainder; the oracle, nearly unregularized and fitted with all 256 labels, can exploit even a small remainder, while six labels and a stronger penalty cannot. By $K = 1024$ the remainder is too small for the oracle as well.

Equivariance. Renumbering the nodes changes the GCN layer’s output, the SGC features and the mean readout only at the level of floating-point rounding ($10^{-16}$), whereas the fully connected layer’s output changes by up to 2.74, some sixteen orders of magnitude more: its weights are tied to positions in the flattened vector, which is exactly what a graph layer must not depend on.

Limitations

• The graph is an input. Results depend on how nodes and edges are built: superpixel algorithm and size, the detector behind object nodes, the $k$ of a nearest-neighbour graph. Errors in the graph propagate. Wang and Gupta’s finding that fusing three graphs in every layer performed worse than one graph alone shows that more edges are not automatically better.
• Over-smoothing limits depth. Repeated averaging drives node features in a connected component toward a common pattern (Li et al., Theorem 1); deep graph networks need devices such as shortcut connections (Pixel2Mesh), virtual edges or master nodes (Gilmer et al.), or a decoupling of propagation from depth.
• Expressiveness. Wu et al. (§4.1) summarize Xu, Hu, Leskovec and Jegelka (2019) as showing that graph networks differ in their ability to distinguish graphs, with GIN as powerful as the Weisfeiler–Lehman isomorphism test, and report that on graph classification an SGC variant is on par with its GCN counterpart but far behind GIN (§5.2).
• Spectral filters do not transfer. Filters defined in one graph’s Fourier basis do not transfer directly to graphs with a different basis, which hurt ChebNet on per-image superpixel graphs (Monti et al.).
• Cost on dense graphs. A step on a dense graph costs $O(n^2 d^2)$ (Gilmer et al.); fully connected similarity graphs, such as Wang and Gupta’s 800-node graphs, scale quadratically with the number of nodes.

Important Models

• Graph neural network model (Scarselli et al., 2009): message passing run to convergence (not read; described through Gilmer et al. and Monti et al.).
• Spectral networks (Bruna et al., 2014) and ChebNet (Defferrard et al., 2016): graph convolution through the Laplacian’s spectrum (not read; described through Wu et al. and Monti et al.).
• GCN (Kipf and Welling, 2017): first-order spectral filters with the renormalized adjacency, stacked with nonlinearities (not read; described through Wu et al. and Gilmer et al.).
• MPNN (Gilmer et al., 2017): the message, update and readout framework, with edge networks, virtual edges, master nodes and set2set readout.
• MoNet (Monti et al., 2017): spatial graph convolution with learned Gaussian kernels on pseudo-coordinates; superpixel MNIST.
• Iterative message passing for scene graphs (Xu et al., 2017): node and edge GRUs on primal and dual graphs.
• GAT (Veličković et al., 2018): attention-weighted aggregation (not read; described through Wu et al.).
• ST-GCN and its successors: spatial-temporal graphs of skeleton joints (skeleton-based action recognition).
• Space-time region graphs (Wang and Gupta, 2018): similarity and space-time graphs of object proposals for action recognition.
• Pixel2Mesh (Wang et al., 2018): deep graph convolution and graph unpooling on a deforming mesh.
• SGC (Wu et al., 2019): fixed propagation $\mathbf{S}^K\mathbf{X}$ followed by logistic regression.