# Aligning Multiple Inhomogeneous Random Graphs: Fundamental Limits of Exact Recovery

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 May 2024.

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

- [The feasibility of multi-graph alignment: a Bayesian approach](https://mlsanity.com/paper/2502.17142/) (2025)
- [Exact Matching in Correlated Networks with Node Attributes for Improved Community Recovery](https://mlsanity.com/paper/2501.02851/) (2025)
- [Attributed Network Alignment: Statistical Limits and Efficient Algorithm](https://mlsanity.com/paper/2604.04365/) (2026)
- [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)

This work studies fundamental limits for recovering the underlying correspondence among multiple correlated graphs. In the setting of inhomogeneous random graphs, we present and analyze a matching algorithm: first partially match the graphs pairwise and then combine the partial matchings by transitivity. Our analysis yields a sufficient condition on the problem parameters to exactly match all nodes across all the graphs. In the setting of homogeneous (ErdHos-R'enyi) graphs, we show that this condition is also necessary, i.e. the algorithm works down to the information theoretic threshold. This reveals a scenario where exact matching between two graphs alone is impossible, but leveraging more than two graphs allows exact matching among all the graphs. Converse results are also given in the inhomogeneous setting and transitivity again plays a role. Along the way, we derive independent results about the k-core of inhomogeneous random graphs.