# An exponential lower bound for Individualization-Refinement algorithms for Graph Isomorphism

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 May 2017.

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

- [Relational Learning in Pre-Trained Models: A Theory from Hypergraph Recovery Perspective](https://mlsanity.com/paper/2406.11249/) (2024)

## Abstract (arXiv)

The individualization-refinement paradigm provides a strong toolbox for testing isomorphism of two graphs and indeed, the currently fastest implementations of isomorphism solvers all follow this approach. While these solvers are fast in practice, from a theoretical point of view, no general lower bounds concerning the worst case complexity of these tools are known. In fact, it is an open question whether individualization-refinement algorithms can achieve upper bounds on the running time similar to the more theoretical techniques based on a group theoretic approach. In this work we give a negative answer to this question and construct a family of graphs on which algorithms based on the individualization-refinement paradigm require exponential time. Contrary to a previous construction of Miyazaki, that only applies to a specific implementation within the individualization-refinement framework, our construction is immune to changing the cell selector, or adding various heuristic invariants to the algorithm. Furthermore, our graphs also provide exponential lower bounds in the case when the k-dimensional Weisfeiler-Leman algorithm is used to replace the standard color refinement operator and the arguments even work when the entire automorphism group of the inputs is initially provided to the algorithm.