Graph Isomorphism and Permutation Invariance
You'll learn why ML models for graphs must produce the same output regardless of how nodes are numbered.
The Core Problem
Imagine you have two social networks. In Network A, Alice is node 1, Bob is node 2, and Carol is node 3. In Network B, the same three people exist but Carol is node 1, Alice is node 2, and Bob is node 3. The friendship connections are identical—just the numbering differs.
These two graphs are isomorphic: they represent the same structure but with different node orderings (permutations). To a human, they're clearly the "same" network. Your ML model should agree.
Why This Matters for Graph Neural Networks
When you represent a graph using an adjacency matrix (as covered in lesson 2484), changing the node order completely rearranges the matrix—same edges, different matrix! If your model treats these as different inputs, it's learning arbitrary numbering patterns rather than true graph structure.
Permutation invariance means: if you shuffle (permute) node indices, the model's output for graph-level predictions stays the same. For node-level predictions, outputs get permuted in the same way as inputs—but predictions about node relationships remain consistent.
The Design Requirement
Graph neural networks must be built with operations that don't depend on node ordering. This typically means:
- Aggregating neighbor information using sum, mean, or max (order-independent operations)
- Avoiding operations that treat position in the adjacency matrix as meaningful
Think of it like averaging grades: whether you sum Alice's 90, Bob's 85, then Carol's 95, or sum them in any other order, the average is always 90.
Key Takeaway: Graph ML models must be permutation invariant—producing equivalent outputs regardless of arbitrary node numbering—because graph structure, not node IDs, carries the meaning.