Message Passing

The operation nearly every graph network is built from: each node sends a message to its neighbours, each node adds up what it receives, and each node updates itself from the total. Repeat, and information travels one hop per round. Depth is reach — how far a node can hear is exactly how many rounds you ran.

Message, aggregate, update — and the aggregator has to be permutation-invariant, so sum, mean and max are the usual choices and they are not interchangeable. Sum preserves how many neighbours there were and mean throws it away, which is why mean-aggregation cannot tell a node with three identical neighbours from one with thirty. That single choice is most of the expressivity difference between architectures.

h sub _v  super ^(l+1)  = φ(h sub _v  super ^(l) , ⊕ sub _{u ∈ N(v)}  ψ(h sub _v  super ^(l) , h sub _u  super ^(l) , e sub _uv )) with ⊕ a permutation-invariant aggregator. Because ⊕ is invariant and φ is shared across nodes, the layer is equivariant — and because reach grows one hop per layer, an L-layer network cannot represent any dependency longer than L hops.