Why standard MLPs & CNNs fail on graphs: and the symmetry that fixes it
Source: Unless otherwise stated, the information and images in this section come from “Sanchez-Lengeling, et al., A Gentle Introduction to Graph Neural Networks, Distill, 2021.” https://distill.pub/2021/gnn-intro/ and Machine Learning with PyTorch and Scikit-Learn, Sebastian Raschka, Yuxi Liu, Vahid Mirjalili, Dmytro Dzhulgakov, February-2022, Packt Publishing
Molecules can be represented as undirected graphs. - Node label matrix: each row is a one-hot encoding of the atom type. - Edge label matrix: each row is a one-hot encoding of the bond type.
Although they almost work
Inductive bias is the set of assumptions built into a model that make it prefer some generalizations over others, letting it extend from the finite data it has seen to inputs it hasn’t.
Examples of inductive bias:
The core trade-off:
This may seem trivial, but there’s a strong connection between convolutional neural networks and graph neural networks.
Note that the convolution operation extracts local information, where local in this context means around a central pixel.


Equivariant: transform the input → the output transforms the same way.
Invariant: transform the input → the output doesn’t change at all.
T (e.g. a spatial shift):
f(T(x)) = T(f(x)): “move the input, the answer moves with it”f(T(x)) = f(x): “move the input, the answer stays put”Either of these is an acceptable condition: in one case, the transformation has no effect on the output and is therefore irrelevant; in the other, the transformation systematically alters the output, which is also reasonable, because it remains a useful output.
A rotation matrix
R(θ)turns a vector by angleθabout the origin: it changes direction while preserving length.
θ; every vector rotates rigidly with them.R are just where the unit axes land after the turn.2-D rotation, then a simple 90° example:
\[ R(\theta)=\begin{bmatrix}\cos\theta & -\sin\theta\\[2pt] \sin\theta & \cos\theta\end{bmatrix}, \qquad R(90^\circ)=\begin{bmatrix}0 & -1\\ 1 & 0\end{bmatrix} \]
\[ R(90^\circ)\begin{bmatrix}1\\0\end{bmatrix}=\begin{bmatrix}0\\1\end{bmatrix} \qquad\text{— the } x\text{-axis rotates onto the } y\text{-axis.} \]
Important properties:
A permutation matrix
Pis a square matrix of 0s and 1s with exactly one 1 in each row and each column: it reorders the entries of whatever it multiplies.
I with its rows shuffled.Px → reorders the rows (entries) of a vector; right-multiply reorders columns.Simple example: cyclically shift a 3-vector:
\[ P=\begin{bmatrix}0&1&0\\0&0&1\\1&0&0\end{bmatrix}, \qquad P\begin{bmatrix}a\\b\\c\end{bmatrix}=\begin{bmatrix}b\\c\\a\end{bmatrix} \]
[0 1 0] picks the 2nd entry, row 2 picks the 3rd, row 3 picks the 1st.Important properties:
Why we care (graphs): relabeling a graph’s nodes is exactly \(A \mapsto P A P^{\top}\): the tool we need to state permutation equivariance for GNNs.
Px reorders the entries.PA reorders the rows, AP^⊤ reorders the columns → PAP^⊤ does both.Why both sides?
A[i,j] = “edge from node i to node j”: both axes are indexed by nodes.P … P^⊤ renumbers both axes the same way, keeping every edge intact.Nice fact:
P is orthogonal, so \(P^{\top}=P^{-1}\) → \(PAP^{\top}=PAP^{-1}\), a change of basis where the “coordinates” are just node labels.One-liner: one P reorders a list; P … P^⊤ reorders a table indexed by the same objects on both sides.
The general pattern \(M \mapsto S M S^{-1}\) (matrix on one side, its inverse on the other) is a similarity transformation, and \(M\) and \(S M S^{-1}\) are similar matrices. This is the change-of-basis operation: M and \(SMS^\{-1\}\) represent the same linear map in different bases. Similar matrices share eigenvalues, determinant, trace, and rank.
Yes:
Pxis a change of basis, but the most rigid kind: it only reorders the axes (feature dimensions), never rotates, scales, or mixes them.
x ↦ Sx can blend axes: e.g. a new axis = 0.3·x_1 + 0.7·x_5.x ↦ Px is the special case where each new coordinate is exactly one old coordinate: pure relabeling, information-preserving.One subtlety: active vs. passive:
P = moving the point by \(P^{-1}=P^{\top}\) (the two are inverses).Why it matters for graphs:
Px generalizes to \(PAP^{\top}\).One-liner: Px reorders the axes; it’s a change of basis stripped down to pure relabeling: which is precisely what a symmetry needs.
Mean aggregation summarizes a node’s neighborhood by averaging the feature vectors of its neighbors: one representative “average neighbor” vector, regardless of how many neighbors there are.
Equation: aggregated message at node i:
\[ h_{\mathcal{N}(i)} \;=\; \frac{1}{|\mathcal{N}(i)|}\sum_{j \in \mathcal{N}(i)} h_j \]
ijAGG(PAP⊤, PX) = P·AGG(A, X) (equivariance preserves where).We actually need respect permutation symmetry: the difference is whether node identity still matters at the output.
The output’s structure dictates which you need:
| Output type | Required property | Why |
|---|---|---|
| Per-node (node labels, embeddings) | Equivariance | identity must travel with the permutation |
| Whole-graph (one prediction) | Invariance | no node to label → relabeling can’t matter |
Realized in a standard modern GCN:
The design rule:
One-liner: stack equivariant layers; add an invariant readout only when the task is about the whole graph.