AVERAGE-CASE AND SMOOTHED ANALYSIS OF GRAPH ISOMORPHISM

We propose a simple and efficient local algorithm for graph isomorphism which succeeds for a large class of sparse graphs. This algorithm produces a low-depth canonical labeling, which is a labeling of the vertices of the graph that identifies its isomorphism class using vertices’ local neighborhoods. Prior work by Czajka and Pandurangan showed that in the Erdős–Rényi model G(n, p_n), the degree profile of a vertex (i.e., the sorted list of the degrees of its neighbors) gives a canonical labeling with high probability when np_n = ω(log⁴(n)/log log n) (and p_n ≤ 1/2); subsequently, Mossel and Ross showed that the same holds when np_n = ω(log²(n)). We first show that their analysis essentially cannot be improved: we prove that when np_n = o(log²(n)/(log log n)³), with high probability there exist distinct vertices with isomorphic 2-neighborhoods. Our first main result is a positive counterpart to this, showing that 3-neighborhoods give a canonical labeling when np_n ≥ (1 + δ)log n (and p_n ≤ 1/2); this improves a recent result of Ding, Ma, Wu and Xu, completing the picture above the connectivity threshold. Our second main result is a smoothed analysis of graph isomorphism, showing that for a large class of deterministic graphs, a small random perturbation of the edge set yields a graph which admits a canonical labeling from 3-neighborhoods, with high probability. While the worst-case complexity of graph isomorphism is still unknown, this shows that graph isomorphism has polynomial smoothed complexity.