MIT 6.7960 Graph Neural Networks (GNN) — Message Passing, Permutation Equivariance, and the Expressiveness Ceiling
A GNN is essentially 'an MLP with local message passing on a graph' — it generalizes CNN's fixed-grid neighborhood to arbitrary topology. It must satisfy permutation equivariance/invariance. In theory, a first-order GNN's expressiveness is bounded by the Weisfeiler–Lehman graph isomorphism test: some structures it can never tell apart, which is exactly the gap GIN, positional encodings, and subgraph tricks later fill.