Search

We analyze a new spectral graph matching algorithm, GRAph Matching by Pairwise eigen-Alignments (GRAMPA), for recovering the latent vertex correspondence between two unlabeled, edge-correlated weighted graphs. Extending the exact recovery guarantees established in a companion paper for Gaussian weights, in this work, we prove the universality of these guarantees for a general correlated Wigner model. In particular, for two Erdős-Rényi graphs with edge correlation coefficient 1 - σ 2 and average degree at least polylog (n) , we show that GRAMPA exactly recovers the latent vertex correspondence with high probability when σ ≲ 1 / polylog (n) . Moreover, we establish a similar guarantee for a variant of GRAMPA, corresponding to a tighter quadratic programming relaxation of the quadratic assignment problem. Our analysis exploits a resolvent representation of the GRAMPA similarity matrix and local laws for the resolvents of sparse Wigner matrices. [ABSTRACT FROM AUTHOR]

Graph matching aims at finding the vertex correspondence between two unlabeled graphs that maximizes the total edge weight correlation. This amounts to solving a computationally intractable quadratic assignment problem. In this paper, we propose a new spectral method, graph matching by pairwise eigen-alignments (GRAMPA). Departing from prior spectral approaches that only compare top eigenvectors, or eigenvectors of the same order, GRAMPA first constructs a similarity matrix as a weighted sum of outer products between all pairs of eigenvectors of the two graphs, with weights given by a Cauchy kernel applied to the separation of the corresponding eigenvalues, then outputs a matching by a simple rounding procedure. The similarity matrix can also be interpreted as the solution to a regularized quadratic programming relaxation of the quadratic assignment problem. For the Gaussian Wigner model in which two complete graphs on n vertices have Gaussian edge weights with correlation coefficient 1 - σ 2 , we show that GRAMPA exactly recovers the correct vertex correspondence with high probability when σ = O (1 log n) . This matches the state of the art of polynomial-time algorithms and significantly improves over existing spectral methods which require σ to be polynomially small in n. The superiority of GRAMPA is also demonstrated on a variety of synthetic and real datasets, in terms of both statistical accuracy and computational efficiency. Universality results, including similar guarantees for dense and sparse Erdős–Rényi graphs, are deferred to a companion paper. [ABSTRACT FROM AUTHOR]

We study the problem of reconstructing a perfect matching M ∗ hidden in a randomly weighted n × n bipartite graph. The edge set includes every node pair in M ∗ and each of the n (n - 1) node pairs not in M ∗ independently with probability d/n. The weight of each edge e is independently drawn from the distribution P if e ∈ M ∗ and from Q if e ∉ M ∗ . We show that if d B (P , Q) ≤ 1 , where B (P , Q) stands for the Bhattacharyya coefficient, the reconstruction error (average fraction of misclassified edges) of the maximum likelihood estimator of M ∗ converges to 0 as n → ∞ . Conversely, if d B (P , Q) ≥ 1 + ϵ for an arbitrarily small constant ϵ > 0 , the reconstruction error for any estimator is shown to be bounded away from 0 for both the sparse (fixed d) and dense (growing d) regimes, resolving the conjecture in Moharrami et al. (Ann Appl Probab 31(6):2663–2720, 2021. https://doi.org/10.1214/20-AAP1660) and Semerjian et al. (Phys Rev E 102:022304, 2020. https://doi.org/10.1103/PhysRevE.102.022304). Furthermore, in the special case of complete exponentially weighted graph with d = n , P = exp (λ) , and Q = exp (1 / n) , for which the sharp threshold simplifies to λ = 4 , we prove that when λ = 4 - ϵ , the optimal reconstruction error is exp - Θ (1 / ϵ) , confirming the conjectured infinite-order phase transition in Semerjian et al. (2020). [ABSTRACT FROM AUTHOR]