Why does sum aggregation distinguish neighbourhoods that mean and max aggregation cannot?

## The neighbourhood is a multiset A node's neighbours have no order, but they can repeat *feature values*: two neighbours may carry the same vector. So what the aggregator really receives is a **multiset** — a bag where multiplicity matters but position does not. The expressive power of a layer is decided by how much of that bag the aggregator preserves. If two different multisets map to the same vector, no amount of downstream depth can ever separate the two nodes; the information is gone before the update ever runs. ## Working the three aggregators on concrete bags Let `A` and `B` be two distinct feature vectors. **Bag pair 1: `{A, B}` versus `{A, A, B, B}`.** - Sum: `A + B` versus `2A + 2B` — different. - Mean: `(A + B) / 2` versus `(2A + 2B) / 4 = (A + B) / 2` — identical. - Max: coordinatewise `max(A, B)` in both — identical. Mean and max both fail here, and the reason is instructive: mean sees only *proportions*, so doubling every neighbour is invisible to it; max sees only the *extremes*, so multiplicity of any kind is invisible to it. **Bag pair 2: `{A, B}` versus `{A, B, B}`.** - Sum: `A + B` versus `A + 2B` — different. - Mean: `(A + B) / 2` versus `(A + 2B) / 3` — different. - Max: `max(A, B)` in both — identical. So the ordering of distinguishing power over multisets is sum > mean > max. Sum retains counts *and* composition; mean retains composition only; max retains the coordinatewise envelope only. ## Why GIN uses sum The Graph Isomorphism Network makes this precise. Its layer is, in words, a small feed-forward network applied to `(1 + eps) * h_v + sum over neighbours of h_u`: a sum over the neighbour multiset, the node's own state scaled by a learnable factor so it is never confused with a neighbour, and then a learned nonlinear map. The point of the construction is that a sum followed by a sufficiently expressive network can be made injective on multisets of bounded-size feature vectors, so distinct neighbourhoods produce distinct outputs. Swap the sum for a mean or a max and the injectivity is lost immediately, by the counterexamples above. ## The ceiling that sum does not break Sum is the most expressive of the three, not a solution to graph isomorphism. A message-passing GNN of this shape is at most as powerful as the **1-dimensional Weisfeiler-Leman colour-refinement test**: repeatedly relabel each node by a hash of its own label and the multiset of its neighbours' labels, and see whether two graphs end up with different label distributions. The standard counterexample is a 6-cycle versus two disjoint triangles, with every node carrying the same initial feature. Both graphs are 2-regular, so at every round every node in both graphs has an identical state; sum, mean and max are all equally helpless, and a sum readout over six identical nodes gives the same graph vector either way. Recognising this ceiling — and that escaping it needs extra input signal such as distinguishing node identifiers or structural counts, not a better pooling operator — is what separates a candidate who has read the GIN result from one who has only memorised *sum is best*. ## When the most expressive aggregator is the wrong one Expressive power is not the only axis. - **Sum entangles degree with content.** The output magnitude scales with the number of neighbours, so on a skewed-degree graph hub nodes produce vectors of a wholly different scale from leaf nodes, and a degree distribution that shifts between training and serving shifts the layer's input distribution with it. When degree is genuinely predictive that coupling is a feature; when degree is an artefact of how the graph was collected it is a liability. - **Mean is degree-invariant.** It answers *what does a typical neighbour look like*, which is the right question when you want a node's representation to be comparable across very different degrees. - **Max surfaces the extreme.** On an intrusion-detection graph of hosts and the peers they talked to, one contact with a hostile signature is the whole answer; max carries that peer's message straight through, while mean would divide it by the 400 ordinary connections around it and bury it in noise. In practice the choice is empirical and cheap to test: sum when counts and multiplicity carry the label, mean when you need degree-invariance, max when the label is driven by an extreme neighbour rather than the typical one.