Interactive demo · Foundations of Deep Learning · Chapter 13

Message passing and over-smoothing

Each layer of a graph network mixes a node's features with its neighbours'. Strip a layer down to its message passing, H ← M H with a normalised propagation matrix M, and apply it k times. Two things happen. A node's output now depends on every node within k hops (its receptive field, click a node to see it). And the features of all nodes are pulled together: Mk converges to the projection onto its leading eigenvector, at the rate ρk set by the second-largest eigenvalue. That is over-smoothing.

Graph

Propagation matrix M

Number of propagations k

Initial residual α: H ← (1 − α) M H + α X

Try these

Matrices: GCN, D̃−1/2(A + I)D̃−1/2; mean, D̃−1(A + I) (average over the node and its neighbours); no self-loops, D−1/2AD−1/2 (13.14); sum, (A + I) divided by its largest eigenvalue so that the scale stays fixed. Each node starts with 2 features (its community plus noise). Hollow circles in the scatter plot are the limit H∞; the dashed line is the bound ρk.

In the lecture notes