Graph Isomorphism Testing is the computational problem of determining whether two graphs are structurally identical — whether there exists a bijective node mapping $pi: V_1 o V_2$ such that $(u, v) in E_1 iff (pi(u), pi(v)) in E_2$ — one of the most famous open problems in theoretical computer science, occupying a unique position between P and NP-complete, with deep connections to group theory, combinatorics, and the expressiveness limits of Graph Neural Networks.

What Is Graph Isomorphism Testing?

• Definition: Two graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ are isomorphic ($G_1 cong G_2$) if there exists a permutation $pi$ of nodes such that every edge in $G_1$ maps to an edge in $G_2$ and vice versa. The Graph Isomorphism (GI) problem asks: given $G_1$ and $G_2$, does such a $pi$ exist? This requires proving either that a valid mapping exists (positive) or that no valid mapping is possible (negative).
• Complexity Status: GI is the most prominent problem with unknown classification — it is not known to be in P (polynomial time), and it is not known to be NP-complete. It occupies its own complexity class "GI-complete." Babai's landmark 2016 result proved that GI is solvable in quasi-polynomial time $O(2^{(log n)^c})$ — faster than exponential but slower than polynomial, narrowing the gap but not resolving the P vs. GI question.
• Practical vs. Theoretical: Despite its theoretical hardness, most practical instances of GI are easily solvable. The nauty/Traces algorithms solve GI for graphs with tens of thousands of nodes in milliseconds because real-world graphs have structural irregularities (different degrees, attributes, local patterns) that make the search space tractable. The hard cases are pathologically regular graphs where every node looks identical.

Why Graph Isomorphism Testing Matters

• GNN Expressiveness: The Weisfeiler-Lehman (WL) isomorphism test provides the exact expressiveness boundary for standard message-passing GNNs. A GNN can distinguish two graphs only if the 1-WL test can distinguish them. This theoretical connection drives the design of more powerful GNN architectures — $k$-WL GNNs, higher-order message passing, and subgraph GNNs all aim to surpass the 1-WL expressiveness limit.
• Chemical Database Management: Chemistry databases (PubChem, ChEMBL, ZINC) store billions of molecular graphs and must detect duplicates efficiently. Every new molecule submission requires an isomorphism check against existing entries to prevent redundant storage. Fast isomorphism testing via canonical forms (nauty + canonical SMILES) enables this at billion-molecule scale.
• Circuit Verification: In electronic design, verifying that a synthesized circuit graph matches the intended specification requires graph isomorphism testing — proving that the manufactured layout has exactly the same connectivity as the designed schematic.
• Symmetry Detection: The automorphism group of a graph (the set of isomorphisms from the graph to itself) encodes all the graph's symmetries. Computing the automorphism group uses GI algorithms and reveals structural properties — highly symmetric graphs have large automorphism groups, indicating redundancy that can be exploited for compression or efficient computation.

GI Testing Approaches

Graph Isomorphism Testing is structural identity verification — proving or disproving that two tangled webs of connections are actually the same web drawn differently, sitting at the intersection of complexity theory, group theory, and the fundamental limits of graph neural network expressiveness.