Interactive demo · Probabilistic Machine Learning · Chapter 23

Graph convolution as feature smoothing

A graph of 120 nodes in three communities, each node with a noisy two-dimensional feature whose class means overlap, so features alone classify only about 70 percent of the nodes. One graph-convolution layer replaces every feature by an average over the node and its neighbours: the features become \(\hat{\mathbf S}^{K}\mathbf X\) with \(\hat{\mathbf S}=\tilde{\mathbf D}^{-1/2}(\mathbf A+\mathbf I)\tilde{\mathbf D}^{-1/2}\), and a softmax regression is trained on a few labelled nodes (circled). Averaging cancels feature noise within a community, so the accuracy first rises; but \(\hat{\mathbf S}^{K}\) tends to a rank-one projection, all features collapse to one direction, and the accuracy falls again: over-smoothing. The shaded regions are the classifier's decision regions in the smoothed feature plane.

Propagation steps K

Labelled nodes per class m

Weight decay log10 λ

Try these

The labelled nodes are the first \(m\) of each class in the order of the data file; the test accuracy is measured on all the other nodes. The classifier is multinomial logistic regression with bias on features centred and scaled to unit variance after propagation, fitted by 300 steps of gradient descent from zero. The Dirichlet energy is \(\mathrm{tr}(\mathbf H^{\mathsf T}\mathbf L_{\rm sym}\mathbf H)/\|\mathbf H\|_F^2\) for the propagated features \(\mathbf H\): it measures how much of the signal varies across edges, and falls to nearly zero as the features collapse.

In the lecture notes