# Graph Isomorphism in Quasipolynomial Time

arXiv: https://arxiv.org/abs/1512.03547 · HTML: https://mlsanity.com/paper/1512.03547/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Dec 2015.

## Built on by (most cited first, 19 of 19)

- [Weisfeiler and Leman go Machine Learning: The Story so far](https://mlsanity.com/paper/2112.09992/) (2021)
- [Ordered Subgraph Aggregation Networks](https://mlsanity.com/paper/2206.11168/) (2022)
- [Group-Invariant Quantum Machine Learning](https://mlsanity.com/paper/2205.02261/) (2022)
- [A Short Tutorial on The Weisfeiler-Lehman Test And Its Variants](https://mlsanity.com/paper/2201.07083/) (2022)
- [SpeqNets: Sparsity-aware Permutation-equivariant Graph Networks](https://mlsanity.com/paper/2203.13913/) (2022)
- [The expressive power of pooling in Graph Neural Networks](https://mlsanity.com/paper/2304.01575/) (2023)
- [On the Universality of Graph Neural Networks on Large Random Graphs](https://mlsanity.com/paper/2105.13099/) (2021)
- [Random graph matching at Otter's threshold via counting chandeliers](https://mlsanity.com/paper/2209.12313/) (2022)
- [Exact Matching of Random Graphs with Constant Correlation](https://mlsanity.com/paper/2110.05000/) (2021)
- [Agent-Q: Fine-Tuning Large Language Models for Quantum Circuit Generation and Optimization](https://mlsanity.com/paper/2504.11109/) (2025)
- [Random Graph Matching with Improved Noise Robustness](https://mlsanity.com/paper/2101.11783/) (2021)
- [Graph Embedding via Diffusion-Wavelets-Based Node Feature Distribution Characterization](https://mlsanity.com/paper/2109.07016/) (2021)
- [Computing Graph Descriptors on Edge Streams](https://mlsanity.com/paper/2109.01494/) (2021)
- [Wasserstein Graph Distance Based on L1-Approximated Tree Edit Distance between Weisfeiler-Lehman Subtrees](https://mlsanity.com/paper/2207.04216/) (2022)
- [Frequent Pattern Mining in Continuous-time Temporal Networks](https://mlsanity.com/paper/2105.06399/) (2021)
- [Complexity-based partitioning of CSFI problem instances with Transformers](https://mlsanity.com/paper/2106.14481/) (2021)
- [Computing Graph Edit Distance with Algorithms on Quantum Devices](https://mlsanity.com/paper/2111.10183/) (2021)
- [Detection of Common Subtrees with Identical Label Distribution](https://mlsanity.com/paper/2307.13068/) (2023)
- [Permutation-Invariant Spectral Learning via Dyson Diffusion](https://mlsanity.com/paper/2510.08535/) (2025)

## Abstract (arXiv)

We show that the Graph Isomorphism (GI) problem and the related problems of String Isomorphism (under group action) (SI) and Coset Intersection (CI) can be solved in quasipolynomial (exp((log n)O(1))) time. The best previous bound for GI was exp(O(√nlog n)), where n is the number of vertices (Luks, 1983); for the other two problems, the bound was similar, exp(tildeO(√n)), where n is the size of the permutation domain (Babai, 1983). The algorithm builds on Luks's SI framework and attacks the barrier configurations for Luks's algorithm by group theoretic "local certificates" and combinatorial canonical partitioning techniques. We show that in a well-defined sense, Johnson graphs are the only obstructions to effective canonical partitioning. Luks's barrier situation is characterized by a homomorphism φ that maps a given permutation group G onto Sk or Ak, the symmetric or alternating group of degree k, where k is not too small. We say that an element x in the permutation domain on which G acts is affected by φ if the φ-image of the stabilizer of x does not contain Ak. The affected/unaffected dichotomy underlies the core "local certificates" routine and is the central divide-and-conquer tool of the algorithm.