Ask Your Neighbours
Only a few dots come with a name tag. Can a robot guess the rest by looking at who they are connected to?
Dots of the same kind tend to be friends. Switch between the two robots and see who guesses better.
Who is who?
Thick ring = has a name tag. A dark cross on a dot means the robot guessed it wrong.
Challenges
What just happened?
- Robot A only sees each dot's own noisy numbers, so with few name tags it is often wrong.
- Robot B lets every dot average its numbers with its friends' numbers. Friends are usually the same kind, so the noise cancels out.
- More hops means a dot hears from friends of friends of friends. A little of this helps a lot.
- Too many hops and everybody ends up averaging with almost everybody. Dots start to look alike and the kinds blur together. This is called over-smoothing.
- This only works because friends tend to be alike. If links were random, asking the neighbours would not help.
For grown-ups: what's really going on
This is semi-supervised node classification with a Graph Convolutional Network (Kipf and Welling, 2017), written from scratch with manual backpropagation and the Adam optimiser. Each layer computes H' = ReLU( H W + b) where  = D−1(A + I) is a mean aggregation over a node and its neighbours (the paper uses a symmetric normalisation).
- The message passing is the multiplication by
Â. StackingLlayers gives every node a receptive field ofLhops. - Loss is cross-entropy on the labelled nodes only. The unlabelled nodes still take part through the graph structure, which is what makes it semi-supervised. Accuracy is measured on the unlabelled nodes.
- Robot A is the same network with
 = I(a plain two-layer MLP), so the only difference is the graph. - Homophily: here 20% of same-kind pairs but 2.5% of different-kind pairs are linked. GNNs rely on this; on heterophilous graphs they can do worse than an MLP.
- Over-smoothing: repeated averaging drives node representations towards the graph's stationary distribution, so they become indistinguishable. The class gap number measures how far apart the three class averages of
ÂLXare, relative toL = 0. Deeper GNNs are also harder to train with so few labels, so accuracy often falls for both reasons. Residual connections, normalisation and sampling are common remedies. - Accuracy in the chart is an average over 2 random initialisations on a single 45-node graph, so small differences are noise. It is a toy, not a benchmark.
Further reading: Kipf and Welling, Semi-supervised classification with graph convolutional networks · Li, Han and Wu, Deeper insights into GCNs for semi-supervised learning (2018).