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

arXiv: https://arxiv.org/abs/2504.02299 · HTML: https://mlsanity.com/paper/2504.02299/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Apr 2025.

## Built on by (most cited first, 2 of 2)

- [Diffusion-Network Alignment: An Efficient Algorithm and Explicit Probability Bounds](https://mlsanity.com/paper/2606.12879/) (2026)
- [Achieving Almost Exact Recovery in Almost Quadratic Time: Rank-Based Graph Matching via Local Tree Correlation Tests](https://mlsanity.com/paper/2607.09087/) (2026)

## Abstract (arXiv)

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 ErdHos-R'enyi 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 ErdHos-R'enyi 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, MPAlign, 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' have average degrees λ s and λ s' respectively, where λ is their common density and s,s' are marginal correlation parameters, their tree neighborhoods can be aligned if ss' > α, where α denotes Otter's constant and λ is supposed large enough. The feasibility of this tree comparison problem undergoes a sharp phase transition since ss' ≤ α 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.