Same graph, different order

A node’s answer should follow its identity, not its row number.

Reorder everything consistently

Our arrays use A, B, C, D, E. Another program might store E, C, A, D, B. If the features and edge references move consistently with their nodes, this is the same graph in a different storage order.

FIG-ORDERThe result follows the node when storage rows move.

Same features and edges, reordered consistently
Node ID	Original row	New row	New state
E	5	1	1.500
C	3	2	1.333
A	1	3	1.250
D	4	4	1.750
B	2	5	0.750

Original output order: A 1.250, B 0.750, C 1.333, D 1.750, E 1.500. New order: E 1.500, C 1.333, A 1.250, D 1.750, B 0.750.

The output attached to C remains 4/3. It simply occupies a different array row. This is permutation equivariance: permuting the input representation permutes the node outputs in the same way.

That is different from invariance, where an output stays exactly the same under a permutation. A sum of incoming messages is invariant to their list order. The collection of per-node outputs is equivariant to reordering the nodes. Neither property says that all nodes must have equal states.

CL-003 · Battaglia et al., §3.2.2–3.2.4: shared functions and invariant aggregation

Why the update follows the node

C still receives the same three values on the same three edges. A sum or mean does not care whether those messages are listed as A, B, D or D, A, B. The update uses the same coefficients at every receiver. Therefore C gets the same answer.

For a compact statement, let $P$ mean a consistent reordering, and let $F_G$ mean one update on graph $G$ . If $PG$ is the graph with node records and edge references reordered together, then:

F_{PG}(Ph)=P\,F_G(h)

Read the equality as: reorder then compute, or compute then reorder—the result agrees. This is a derivation from shared functions and an order-independent reducer. Floating-point summation order may introduce tiny rounding differences in an implementation; our tests compare with an explicit absolute tolerance.

Shuffling only the feature values is a different experiment. Giving A the old value of E while leaving the edges fixed changes which entity has which input. Equivariance does not require that change to leave predictions alone.

CL-012 · Derived equivariance. A node ID is a stable reference here, not a special learned parameter or an extra numerical input.

A state still needs a job

A readout maps the resulting states to a desired output. A shared node head could produce one output for each node. A graph head might first sum node states and then produce one output for the whole graph. A graph-level output can be invariant to node order while node-level outputs remain equivariant.

\widehat{y}_i=R_\phi(h_i^{(L)})

Here $L$ is the last layer, $R_\phi$ is a parameterized node readout, and $\widehat{y}_i$ is a proposed prediction. A supervised objective would compare those predictions with targets and adjust $\theta$ and $\phi$ . The symbols locate where learning would happen; the toy has no fitted readout.

CL-016 · Gilmer et al., §2, equation (3) and output-level examples

For document intelligence, nodes could represent text regions and edges could represent a chosen spatial relation. For a grid study, nodes could represent buses with suitably defined features. Those are possible problem formulations, not evidence of useful accuracy. The graph construction, target, loss and held-out evaluation would need their own justification.

A useful local aggregation can also discard a distinction that the target needs. The next chapter examines a case where repeated mixing erases almost everything that distinguishes our five starting values.