Graphs, Ranking & Search

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

Watch it learn: press "Train from scratch" and let both robots finish.
Neighbours win: with 2 or fewer name tags per kind, get Robot B at least 10 points above Robot A.
Hunt for the sweet spot: try every number of hops, then set the hops slider to the best one.
Over-smoothing: push the hops to 6 and watch the class gap fall below 60%.

What just happened?

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 Â. Stacking L layers gives every node a receptive field of L hops.
  • 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 ÂLX are, relative to L = 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).