Graph Expressivity

There are pairs of graphs a message-passing network simply cannot tell apart — not because it was trained badly, but because no amount of training would help. Two different molecules can produce identical computations at every node. Knowing which pairs those are tells you when the architecture is the ceiling rather than the data.

Standard message passing is at most as discriminative as the one-dimensional Weisfeiler–Leman colour refinement test, and that bound is tight — with an injective aggregator you reach it, and with mean or max you fall short of it. The practical repairs all add something WL cannot see: random node identifiers, distance encodings, subgraph counts. Each buys expressivity and gives up some of the permutation equivariance that made the architecture attractive.

If 1-WL assigns two graphs the same colour multiset, no message-passing network can separate them. Sum aggregation with an injective φ achieves the bound, which is the result GIN is built on: h sub _v  = MLP((1+ε)·h sub _v  + Σ sub _{u ∈ N(v)}  h sub _u ). Regular graphs of the same degree are the standard counterexample — every node sees the identical picture forever.