Graph alignment asks which vertex of a given graph corresponds to which vertex of a second, unlabelled graph. We formalise this question as a statistical inference problem: two random graphs are correlated through a latent vertex correspondence, and the goal is to recover this correspondence with high probability in polynomial time.

In this talk, we introduce a model of correlated Erdős–Rényi graphs that may have different numbers of vertices as well as varying edge densities. In the sparse setting with constant average degrees, these graphs are locally tree-like. Our alignment algorithm compares local tree neighbourhoods, which leads to a tree correlation testing problem. The feasibility of this testing problem exhibits a sharp phase transition, which we quantify in our main result. This result is surprising in two ways. First, the density of one tree can compensate for the sparsity of the other. Second, the proof revolves around a diagonalisation formula for the likelihood ratio over the space of unlabelled trees.