Smoothed Analysis for Graph Isomorphism

There is no known polynomial-time algorithm for graph isomorphism testing, but elementary combinatorial "refinement" algorithms seem to be very efficient in practice. Some philosophical justification for this phenomenon is provided by a classical theorem of Babai, Erdős and Selkow: an extremely simple polynomial-time combinatorial algorithm (variously known as "naïve refinement", "naïve vertex classification", "colour refinement" or the "1-dimensional Weisfeiler-Leman algorithm") yields a so-called canonical labelling scheme for "almost all graphs". More precisely, for a typical outcome of a random graph G(n, 1/2), this simple combinatorial algorithm assigns labels to vertices in a way that easily permits isomorphism-testing against any other graph. We improve the Babai-Erdős-Selkow theorem in two directions. First, we consider randomly perturbed graphs, in accordance with the smoothed analysis philosophy of Spielman and Teng: for any graph G, naïve refinement becomes effective after a tiny random perturbation to G (specifically, the addition and removal of O(n log n) random edges). Actually, with a twist on naïve refinement, we show that O(n) random additions and removals suffice. These results significantly improve on previous work of Gaudio, Rácz and Sridhar (resolving one of their conjectures), and are in certain senses best-possible. Second, we complete a long line of research on canonical labelling and automorphisms for random graphs: for any p (possibly depending on n), we prove that a random graph G(n, p) can typically be canonically labelled in polynomial time. This is most interesting in the extremely sparse regime where p has order of magnitude c/n; denser regimes were previously handled by Bollobás, Czajka-Pandurangan, and Linial-Mosheiff. Our proof also provides a description of the automorphism group of a typical outcome of G(n, p) (slightly correcting a prediction of Linial-Mosheiff).