Exact Procrustes matching of n Gaussian vectors in d≥polylog(n) dimensions is achievable in polynomial time whenever the correlation satisfies ρ²>√α≈0.58, via counting wide trees.
From tree matching to sparse graph alignment
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
In this paper we consider alignment of sparse graphs, for which we introduce the Neighborhood Tree Matching Algorithm (NTMA). For correlated Erd\H{o}s-R\'{e}nyi 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.
fields
stat.ML 1years
2026 1verdicts
ACCEPT 1representative citing papers
citing papers explorer
-
High-Dimensional Procrustes Matching via Tree Counts
Exact Procrustes matching of n Gaussian vectors in d≥polylog(n) dimensions is achievable in polynomial time whenever the correlation satisfies ρ²>√α≈0.58, via counting wide trees.