Graph Isomorphism and the Universality of Graph Neural Networks

This direction is merged into another direction: 1-WL expressivity limit, invariant function approximation. Its last version stays readable and citable here.

Version 1 of 110 papers16 conceptsfrozen 2026-10-04

When we design a Graph Neural Network (GNN), we usually think about message passing—nodes whispering features to their neighbors to build a representation. But from a theoretical perspective, a GNN is simply a function that maps a graph to a vector or a value. The fundamental question of GNN theory is: Which functions can a GNN actually represent?

Recent research has revealed a deep, mathematical equivalence between a GNN's ability to solve the "Graph Isomorphism" problem (telling two different graphs apart) and its "Universality" (its ability to approximate any possible function on graphs).

The Isomorphism Bottleneck

To understand why GNNs are limited, we first have to look at the Weisfeiler-Lehman (WL) test. This is a classical algorithm used to determine if two graphs are isomorphic—meaning they have the exact same structure despite different node labels. Most standard GNNs are essentially a differentiable version of the 1-WL test.

The intuition is simple: if a GNN cannot distinguish between two different graphs (i.e., it produces the same output for both), it cannot possibly assign them different target values. For example, if a GNN thinks a "safe" molecule and a "toxic" molecule look identical, it can never learn to classify them correctly.

Zhengdao Chen, Soledad Villar, and Joan Bruna formalized this in On the equivalence between graph isomorphism testing and function approximation with GNNs. They proved that the capacity to distinguish non-isomorphic graphs is mathematically equivalent to the power to approximate any permutation-invariant function. This means that if you want a "Universal" GNN, you are effectively trying to solve the Graph Isomorphism problem.

From Separation to Universality

How do we move from "distinguishing graphs" to "approximating any function"? The bridge is a classic mathematical tool called the Stone-Weierstrass theorem.

In A Simple Proof of the Universality of Invariant/Equivariant Graph Neural Networks, Takanori Maehara and Hoang NT show that if a set of functions can distinguish between any two distinct inputs and is closed under multiplication (forming a "subalgebra"), it can approximate any continuous function on those inputs.

In the context of graphs, this means that if your GNN architecture is powerful enough to give every unique graph a unique "fingerprint," and you can combine these fingerprints through network layers, you can learn to map those graphs to any desired output. This principle isn't limited to simple static graphs; Silvia Beddar-Wiesing and colleagues demonstrated in Weisfeiler-Lehman goes Dynamic that these same guarantees extend to edge-attributed and dynamic graphs that evolve over time.

Permutation Compatibility

A key constraint in graph learning is permutation invariance: the output shouldn't change if you just reorder the rows and columns of the adjacency matrix. Hamed Hassani and his co-authors in The Exact Class of Graph Functions Generated by Graph Neural Networks introduced the concept of permutation compatibility.

They argue that GNNs are not just a random collection of functions; they are exactly the class of functions that respect the symmetry of the graph while processing node features. By using distinct node features (feature augmentation), GNNs can move beyond simple structural tests and solve complex algorithmic problems like finding shortest paths or calculating maximum flows.

Beyond Isomorphism: Solving Optimization Problems

This theoretical framework is now being used to explain why GNNs are surprisingly good at solving hard combinatorial and optimization problems.

In Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programs, Ziang Chen and Xiaohan Chen applied these universality theorems to Quadratic Programming (QP). They found that if a QP instance has a unique representation under the WL test, a sufficiently large GNN can approximate its optimal solution.

This bridges the gap between theory and practice: we now know that GNNs aren't just "guessing" solutions to optimization problems; they are acting as universal approximators for the underlying mathematical structures, provided those structures are "GNN-friendly"—meaning they can be distinguished by the network's inherent symmetry-aware architecture.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_graph_isomorphism_and_the_universality_o_9fdcb4a9,
  title = {Graph Isomorphism and the Universality of Graph Neural Networks},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/graph-isomorphism-and-the-universality-of-graph-neural-networks/rdr_9fdcb4a9577c48e38fd86a8c347df808},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_graph_isomorphism_and_the_universality_o_9fdcb4a9_v1,
  title = {Graph Isomorphism and the Universality of Graph Neural Networks},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/graph-isomorphism-and-the-universality-of-graph-neural-networks/rdr_9fdcb4a9577c48e38fd86a8c347df808/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}