Permutation invariance means producing the same result when unordered inputs appear in a different order. In a graph neural network, a node’s neighbors have no natural ordering, so their messages must be combined in an order-independent way. Summing or averaging preserves the result even when graph numbering changes. section 11.4
Within message passing, permutation invariance supports:
- Constructing each message from a neighboring node. section 11.4
- Aggregating messages with a sum or mean. section 11.4
- Updating the node representation from the aggregate and its current value. section 11.4
A graph convolution illustrates permutation-invariant aggregation by combining a node with its neighbors before applying a learned transformation and nonlinearity. section 11.4



