What is the difference between permutation invariance and equivariance for a graph model?

## Why the question exists at all A graph carries no canonical node order. If you load the same molecule from two files and the atoms come out in a different sequence, you have one molecule and two descriptions. Every array-based encoding must pick *some* order to write rows in, so the encoding contains an arbitrary choice the graph itself does not contain. Invariance and equivariance are the two precise statements of "the model must not be fooled by that arbitrary choice". ## The two definitions Let a relabelling be a permutation that reorders the nodes. Applying it means reordering the rows of the node feature matrix and applying the *same* reordering to the structure — for an adjacency matrix, both its rows and its columns; for an edge list, rewriting every stored id through the new numbering. - **Invariant function.** The output is unchanged: `f(permuted graph) = f(graph)`. One number, one class label, one embedding of the whole graph. - **Equivariant function.** The output is permuted the same way: `f(permuted graph) = permute(f(graph))`. One row of output per node, still attached to the right node. Invariance is not a weaker or stronger form of equivariance applied carelessly; they answer different questions. Invariance is what you want when the output has no node index. Equivariance is what you want when it does. ## Which does your task need? Match the symmetry to the shape of the label. - **Graph-level label — invariance.** A single predicted solubility for a small molecule. Relabelling the atoms 1..N differently must return the identical number; if it does not, the model is reading the file order, and file order is not chemistry. - **Node-level label — equivariance.** A predicted partial charge for every atom. The set of charges must be unchanged, but each must travel with its atom. An "invariant" per-node output would be an outright bug: it would return the charges in the original positions after you had relabelled, silently attaching each prediction to the wrong atom. - **Pair-level label — equivariance over pairs.** A link score for the pair (i, j) must follow the pair through the relabelling. Aggregate a set of such scores into one count and you are back to an invariant quantity. ## How models are actually built The standard construction is a stack of equivariant layers followed by, when needed, one invariant step. Each layer transforms every node with the *same* shared weights — a per-node transform is automatically equivariant, since it never looks at the row index — and combines each node's neighbours with an operation that does not depend on the order the neighbours are listed in. Composing equivariant layers gives an equivariant network, so a node-level head can sit on top and inherit the property. For a graph-level answer, one order-free pooling over all node vectors collapses the per-node dimension. Because pooling ignores order, the composition is invariant. Note that invariance is obtained *last*: build the network equivariant and pool once, rather than trying to make each layer invariant, which would destroy per-node identity in the first layer and leave nothing to pass messages between. ## Two tempting non-solutions **Canonical ordering.** "Sort the nodes by degree, then any fixed-size model is fine." Ties are pervasive — a regular graph has every node at the same degree — so the sort is not well defined, and a tie-break by a secondary feature is unstable: a tiny change to one feature can reshuffle the whole encoding, so a model trained on it sees a discontinuity. Genuine graph canonicalisation is expensive and brittle for exactly the same reason. **Augmentation.** "Train on many random relabellings and the model learns invariance." It learns an approximation, at the cost of spending capacity and data on a symmetry that could have been built in for free, and a graph with N nodes has up to N factorial orderings — you cannot cover that space by sampling. ## Testing it The check is cheap and belongs in your test suite. Draw a random permutation, apply it to the node features **and** consistently to the edge list, run the model, and compare. For an invariant output the values must match within floating-point tolerance; for an equivariant output, apply the inverse permutation to the result and compare against the unpermuted run. Permuting the features while forgetting the edges is the classic broken test: it changes the graph, so a mismatch proves nothing. ## When you break invariance on purpose Sometimes you add information that is not permutation-symmetric — a positional or structural encoding, a designated root node, an ordering that genuinely exists in the data such as time. That is a legitimate design choice, but it must be a choice: you are declaring that the extra ordering is real signal, not an artefact of how the file was written.