Faster algorithms for the alignment of sparse correlated Erdős–Rényi random graphs

Abstract The correlated Erdős–Rényi random graph ensemble is a probability law on pairs of graphs with n vertices, parametrized by their average degree λ and their correlation coefficient s . It can be used as a benchmark for the graph alignment problem, in which the labels of the vertices of one of the graphs are reshuffled by an unknown permutation; the goal is to infer this permutation and thus properly match the pairs of vertices in both graphs. A series of recent works has unveiled the role of Otter’s constant α (that controls the exponential rate of growth of the number of unlabeled rooted trees as a function of their sizes) in this problem: for <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mrow> <mml:mi>s</mml:mi> <mml:mo>&gt;</mml:mo> <mml:msqrt> <mml:mi>α</mml:mi> </mml:msqrt> </mml:mrow> </mml:math> and large enough λ , it is possible to recover in a time polynomial in n a positive fraction of the hidden permutation. The exponent of this polynomial growth is, however, quite large and depends on the other parameters, which limits the range of applications of the algorithm. In this work, we present a family of faster algorithms for this task, show through numerical simulations that their accuracy is only slightly reduced with respect to the original one and conjecture that they undergo, in the large λ limit, phase transitions at modified Otter’s thresholds <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mrow> <mml:msqrt> <mml:mrow> <mml:mover> <mml:mi>α</mml:mi> <mml:mo>^</mml:mo> </mml:mover> </mml:mrow> </mml:msqrt> <mml:mo>&gt;</mml:mo> <mml:msqrt> <mml:mi>α</mml:mi> </mml:msqrt> </mml:mrow> </mml:math> , with <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mrow> <mml:mrow> <mml:mover> <mml:mi>α</mml:mi> <mml:mo>^</mml:mo> </mml:mover> </mml:mrow> </mml:mrow> </mml:math> related to the enumeration of a restricted family of trees.