Asymmetric graph alignment and the phase transition for asymmetric tree correlation testing

Abstract

Graph alignment – identifying node correspondences between two graphs – is a fundamental problem with applications in network analysis, biology, and privacy research. While substantial progress has been made in aligning correlated Erdős–Rényi graphs under symmetric settings, real-world networks often exhibit asymmetry in both node numbers and edge densities. In this work, we introduce a novel framework for asymmetric correlated Erdős–Rényi graphs, generalizing existing models to account for these asymmetries. We conduct a rigorous theoretical analysis of graph alignment in the sparse regime, where local neighborhoods exhibit tree-like structures. Our approach leverages tree correlation testing as the central tool in our polynomial-time algorithm, MPAʟɪɢɴ, which achieves one-sided partial alignment under certain conditions.
A key contribution of our work is characterizing these conditions under which asymmetric tree correlation testing is feasible: If two correlated graphs $G$ and $G^{\prime }$ have average degrees $\lambda s$ and $\lambda s^{\prime }$ respectively, where $\lambda$ is their common density and $s,s^{\prime }$ are marginal correlation parameters, their tree neighborhoods can be aligned if $s{s}^{\prime }>\alpha$, where $\alpha$ denotes Otter’s constant and $\lambda$ is supposed large enough. The feasibility of this tree comparison problem undergoes a sharp phase transition since $s{s}^{\prime }\le \alpha$ implies its impossibility. These new results on tree correlation testing allow us to solve a class of random subgraph isomorphism problems, resolving an open problem in the field.