Permutation Symmetry and the Message-Passing Blueprint
Published:
The symmetry
An attributed graph is \(\mathcal{G} = (A, H)\) with \(A \in \{0,1\}^{n \times n}\) the adjacency matrix and \(H \in \mathbb{R}^{n \times d}\) the node features. Node \(i\)’s neighbourhood is \(\mathcal{N}_i = \{\, j \in \mathcal{V} \mid a_{ij} = 1 \,\}\).
Nothing about the graph designates node 1 as first. Any relabelling gives an equally valid description of the same object. Formally, a permutation \(\sigma\) acts through its permutation matrix \(P_\sigma\):
The adjacency matrix is conjugated — rows and columns move, because an edge is a pair — while the feature matrix is only row-permuted.
The template that follows
Given that constraint, a layer updates node \(i\) in three steps.
1 — Message. For each neighbour, build a message from the pair:
with \(\psi\) typically an MLP.
2 — Aggregate. Combine the messages into one vector:
where \(\bigoplus\) is permutation-invariant — sum, mean, or max.
3 — Update. Combine with the node’s own state:
That is the whole framework, and it covers GCN, GIN, MPNN and GAT as special cases.
Checking it, and checking that it can fail
Take the 4-node path \(1 - 2 - 3 - 4\) with scalar features \(h = (1, 2, 3, 4)\), and the simplest possible layer, \(h_i' = h_i + \sum_{j \in \mathcal{N}_i} h_j\).
Run it directly: \(h' = (3,\ 6,\ 9,\ 7)\).
Now relabel with \(\sigma\) sending node \(1 \mapsto 3,\ 2 \mapsto 1,\ 3 \mapsto 4,\ 4 \mapsto 2\), so \(H' = (2, 4, 1, 3)\) and the adjacency is conjugated accordingly. Running the same layer on the relabelled graph gives \((6,\ 7,\ 3,\ 9)\) — which is exactly \(P_\sigma\) applied to \((3,6,9,7)\). Equivariant.
The sum readout gives \(25\) either way. Invariant.
Now break it deliberately. Replace the sum with “add the neighbour of lowest index” — a perfectly well-defined function that happens to consult the labelling:
Sweeping all \(24\) permutations of four nodes:
| Aggregator | Equivariant under |
|---|---|
| sum | 24 of 24 |
| lowest-indexed neighbour | 6 of 24 |
A witness: under \(\sigma = (0, 2, 3, 1)\) the order-dependent rule gives \((3, 7, 3, 7)\) when applied to the relabelled graph, but \((3, 7, 3, 5)\) when applied first and relabelled after. Two different answers for the same graph.
Which invariant aggregator
All three standard choices satisfy the constraint; they differ in what they can distinguish.
| Aggregator | Preserves | Blind to |
|---|---|---|
| sum | multiset size and content | nothing, for countable features |
| mean | average | how many neighbours there are |
| max | the extreme | multiplicity, and everything below the max |
Sum is the strictly most expressive of the three, which is the argument behind GIN — the expressivity chapter in Book II works through why. Mean cannot tell \(\{1, 3\}\) from \(\{2, 2\}\)’s average, and max cannot tell \(\{1, 3\}\) from \(\{3, 3\}\). Whether the loss matters depends entirely on your task; a degree-blind aggregator is a liability when degree is informative and a convenience when it is noise.
The step that makes Transformers fall out
The template says nothing about where \(\mathcal{N}_i\) comes from. It is supplied by \(A\), and \(A\) is an input.
Set \(a_{ij} = 1\) for every pair — a complete graph — and \(\mathcal{N}_i\) becomes the entire input. Every node messages every node, the aggregation is over everything, and there is no sparsity left to exploit. That configuration has a name in a different literature: it is self-attention, and it is what the next chapter works through line by line.
Two consequences worth stating now. First, a set is just a graph you have declined to put edges in, so permutation equivariance over sets and over graphs is the same requirement. Second, a model on a complete graph has no structural inductive bias to be wrong about — which is a liability when you know the structure and an asset when you do not.
✅ Key Takeaways
- Relabelling acts as \(P_\sigma \cdot \mathcal{G} = (P_\sigma A P_\sigma^{\top}, P_\sigma H)\) — the adjacency is conjugated because an edge is a pair.
- Layers must be equivariant, the graph-level readout invariant. These are different requirements and mixing them up is the standard error.
- The message/aggregate/update template is forced by permutation symmetry, not chosen. Step 2 is the only place the symmetry is enforced.
- Verified on a 4-node path: the sum aggregator is equivariant under all 24 permutations; an index-order aggregator survives only 6, so a single random permutation is not a valid test.
- Sum is more expressive than mean or max — mean discards degree, max discards multiplicity.
- The neighbourhood is an input, not a constant. Make every node adjacent to every other and message passing becomes self-attention.
References
- Joshi, C. K. (2025). Transformers are Graph Neural Networks. arXiv:2506.22084.
- Bronstein, M. M., Bruna, J., Cohen, T., & Veličković, P. (2021). Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges. arXiv:2104.13478.
- Battaglia, P. W., Hamrick, J. B., Bapst, V., Sanchez-Gonzalez, A., Zambaldi, V., et al. (2018). Relational Inductive Biases, Deep Learning, and Graph Networks. arXiv:1806.01261.
- Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., & Dahl, G. E. (2017). Neural Message Passing for Quantum Chemistry. ICML 2017.
- Xu, K., Hu, W., Leskovec, J., & Jegelka, S. (2019). How Powerful are Graph Neural Networks? ICLR 2019.