# From tree matching to sparse graph alignment

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Feb 2020.

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

- [Settling the Sharp Reconstruction Thresholds of Random Graph Matching](https://mlsanity.com/paper/2102.00082/) (2021)
- [Random graph matching at Otter's threshold via counting chandeliers](https://mlsanity.com/paper/2209.12313/) (2022)
- [Exact Matching of Random Graphs with Constant Correlation](https://mlsanity.com/paper/2110.05000/) (2021)
- [Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities](https://mlsanity.com/paper/2107.06767/) (2021)
- [Testing network correlation efficiently via counting trees](https://mlsanity.com/paper/2110.11816/) (2021)
- [Random Graph Matching in Geometric Models: the Case of Complete Graphs](https://mlsanity.com/paper/2202.10662/) (2022)
- [Impossibility of Partial Recovery in the Graph Alignment Problem](https://mlsanity.com/paper/2102.02685/) (2021)
- [Random Graph Matching with Improved Noise Robustness](https://mlsanity.com/paper/2101.11783/) (2021)
- [Matching recovery threshold for correlated random graphs](https://mlsanity.com/paper/2205.14650/) (2022)
- [Correlation detection in trees for planted graph alignment](https://mlsanity.com/paper/2107.07623/) (2021)
- [Detection threshold for correlated ErdHos-R'enyi graphs via densest subgraphs](https://mlsanity.com/paper/2203.14573/) (2022)
- [Statistical limits of correlation detection in trees](https://mlsanity.com/paper/2209.13723/) (2022)
- [A polynomial-time iterative algorithm for random graph matching with non-vanishing correlation](https://mlsanity.com/paper/2306.00266/) (2023)
- [Exact Community Recovery in Correlated Stochastic Block Models](https://mlsanity.com/paper/2203.15736/) (2022)
- [A polynomial time iterative algorithm for matching Gaussian matrices with non-vanishing correlation](https://mlsanity.com/paper/2212.13677/) (2022)
- [Matching Correlated Inhomogeneous Random Graphs using the k-core Estimator](https://mlsanity.com/paper/2302.05407/) (2023)
- [The Umeyama algorithm for matching correlated Gaussian geometric models in the low-dimensional regime](https://mlsanity.com/paper/2402.15095/) (2024)
- [One-Way Matching of Datasets with Low Rank Signals](https://mlsanity.com/paper/2204.13858/) (2022)
- [Efficiently matching random inhomogeneous graphs via degree profiles](https://mlsanity.com/paper/2310.10441/) (2023)
- [Seeded graph matching for the correlated Gaussian Wigner model via the projected power method](https://mlsanity.com/paper/2204.04099/) (2022)
- [Graph Matching via convex relaxation to the simplex](https://mlsanity.com/paper/2310.20609/) (2023)
- [Computational Lower Bounds for Correlated Random Graphs via Algorithmic Contiguity](https://mlsanity.com/paper/2502.09832/) (2025)
- [Graph Alignment via Birkhoff Relaxation](https://mlsanity.com/paper/2503.05323/) (2025)
- [Graph Alignment for Benchmarking Graph Neural Networks and Learning Positional Encodings](https://mlsanity.com/paper/2505.13087/) (2025)
- [Information-Theoretic Thresholds for the Alignments of Partially Correlated Graphs](https://mlsanity.com/paper/2406.05428/) (2024)
- [Robust Random Graph Matching in Dense Graphs via an Approximate Message Passing Type Algorithm](https://mlsanity.com/paper/2412.16457/) (2024)

## Abstract (arXiv)

In this paper we consider alignment of sparse graphs, for which we introduce the Neighborhood Tree Matching Algorithm (NTMA). For correlated ErdHos-R'enyi random graphs, we prove that the algorithm returns -- in polynomial time -- a positive fraction of correctly matched vertices, and a vanishing fraction of mismatches. This result holds with average degree of the graphs in O(1) and correlation parameter s that can be bounded away from 1, conditions under which random graph alignment is particularly challenging. As a byproduct of the analysis we introduce a matching metric between trees and characterize it for several models of correlated random trees. These results may be of independent interest, yielding for instance efficient tests for determining whether two random trees are correlated or independent.