Message passing & the GCN

Click "pass one round of messages" a few times. Every node's number nudges toward the average of itself and its direct neighbors — nothing fancier than that.

A Graph Convolutional Network (GCN) layer replaces the standard neural-net update with message passing: each node's new feature is a function of the (multi-)set of its neighbors' current features, plus its own:

• $h_v^{(k)}$ — node $v$'s feature after $k$ rounds of message passing.
• $h_v^{(k+1)}$ — node $v$'s updated feature after one more round of message passing.
• $h_u^{(k)}$ — a neighbor $u$'s current feature, one of the values node $v$ aggregates.
• $\mathcal{N}(v)$ — node $v$'s neighborhood: every node it shares an edge with.
• AGGREGATE — the combining function; this chapter fixes it to a plain mean of the node and its neighbors.

1. AGGREGATE fixed to a plain mean

   The simplest possible choice of AGGREGATE — the one this chapter uses — is a plain mean: average the node's own value together with every neighbor's.

2. Stacking layers reaches further hops

   Stack $k$ of these layers, and information from nodes up to $k$ hops away has had a chance to reach any given node.

Watch the variance number, not just the graph. It shrinks every single round — nodes that started far apart in value are ending up closer and closer together. That's not a bug; it's exactly what averaging repeatedly does, and it's the double-edged sword of stacking too many GCN layers: over-smoothing.

Starting features $x=(1,2,0,3,1,2)$ for nodes $(0,1,2,3,4,5)$:

1. One round, computed by hand for a leaf and a hub

   • Node $4$ (a leaf, neighbor $\{3\}$): $h_4^{(1)} = \frac{1+3}{2} = 2$.
   • Node $3$ (a hub, neighbors $\{1,4,5\}$): $h_3^{(1)} = \frac{3+2+1+2}{4} = 2$.

   Every node's group size is $1+\deg(v)$ — the denominator changes depending on the node, since degrees aren't uniform (Chapter 1).

2. Full round 1

   The same mean rule for the remaining four nodes:

   • $h_0^{(1)} = \frac{1+2+0}{3} = 1.0$ (self $1$, neighbors $\{1,2\}$ with features $2,0$)
   • $h_1^{(1)} = \frac{2+1+0+3}{4} = 1.5$ (self $2$, neighbors $\{0,2,3\}$ with features $1,0,3$)
   • $h_2^{(1)} = \frac{0+1+2}{3} = 1.0$ (self $0$, neighbors $\{0,1\}$ with features $1,2$)
   • $h_5^{(1)} = \frac{2+3}{2} = 2.5$ (self $2$, neighbor $\{3\}$ with feature $3$)

   Together with $h_3^{(1)}=2.0$ and $h_4^{(1)}=2.0$ from the step above: $h^{(1)} = (1.0,\ 1.5,\ 1.0,\ 2.0,\ 2.0,\ 2.5)$.

   The new mean is $\frac{1.0+1.5+1.0+2.0+2.0+2.5}{6}=\frac{10.0}{6}\approx1.667$, so the new variance is $\frac{(1.0-1.667)^2+(1.5-1.667)^2+(1.0-1.667)^2+(2.0-1.667)^2+(2.0-1.667)^2+(2.5-1.667)^2}{6} \approx\frac{1.833}{6}\approx0.306$ — down from the original $\frac{11}{12}\approx0.917$, already less than a third of where it started.

3. Keep going and it keeps shrinking

   Running the identical mean rule for three more rounds:

   • Round $2$: $h^{(2)} \approx (1.167,\ 1.375,\ 1.167,\ 2.0,\ 2.0,\ 2.25)$, variance $\approx0.191$
   • Round $3$: $h^{(3)} \approx (1.236,\ 1.427,\ 1.236,\ 1.906,\ 2.0,\ 2.125)$, variance $\approx0.134$
   • Round $4$: $h^{(4)} \approx (1.300,\ 1.451,\ 1.300,\ 1.865,\ 1.953,\ 2.016)$, variance $\approx0.093$

   Every node's value is crawling toward the graph's overall average. Nodes $0$ and $5$ started a full $1.0$ apart; a few rounds of pure local averaging is already enough to blur that gap down to $2.016-1.300\approx0.716$.