Aligning random graphs with a sub-tree similarity message-passing algorithm

Giovanni Piccioli, Guilhem Semerjian, Gabriele Sicuro +1

The problem of aligning Erdös-Rényi random graphs is a noisy, average-case version of the graph isomorphism problem, in which a pair of correlated random graphs is observed through…