pith. sign in

arxiv: 1907.08880 · v1 · pith:BRPQQKAGnew · submitted 2019-07-20 · 📊 stat.ML · cs.LG· math.PR· math.SP· math.ST· stat.TH

Spectral Graph Matching and Regularized Quadratic Relaxations I: The Gaussian Model

Zhou Fan , Cheng Mao , Yihong Wu , Jiaming Xu This is my paper

Pith reviewed 2026-05-24 18:27 UTC · model grok-4.3

classification 📊 stat.ML cs.LGmath.PRmath.SPmath.STstat.TH
keywords graph matchingspectral methodsquadratic assignmentGaussian Wigner modelexact recoveryeigenvector alignment
0
0 comments X

The pith

GRAMPA recovers exact vertex correspondence in the Gaussian Wigner graph matching model when noise σ is O(1/log n).

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces GRAMPA, a spectral algorithm for graph matching that seeks the vertex alignment maximizing total edge-weight correlation between two unlabeled graphs. GRAMPA forms a similarity matrix by summing outer products of every pair of eigenvectors from the two graphs, with each pair weighted by a Cauchy kernel on the gap between their eigenvalues, then rounds the matrix to produce a matching. In the Gaussian Wigner model of two complete graphs whose edge weights are jointly Gaussian with correlation 1-σ², the method recovers the true correspondence with high probability as soon as σ = O(1/log n). This threshold matches the best known polynomial-time algorithms and improves on earlier spectral techniques that required polynomially small σ.

Core claim

In the Gaussian Wigner model where two graphs on n vertices have Gaussian edge weights with correlation 1-σ², GRAMPA exactly recovers the correct vertex correspondence with high probability when σ = O(1/log n).

What carries the argument

The similarity matrix constructed as a weighted sum of outer products of all eigenvector pairs from the two graphs, with weights given by a Cauchy kernel on the separation of corresponding eigenvalues.

If this is right

  • GRAMPA matches the state-of-the-art recovery threshold among all polynomial-time algorithms for this model.
  • The method tolerates substantially larger noise than prior spectral approaches that compare only top eigenvectors or same-order eigenvectors.
  • The similarity matrix also solves a regularized quadratic programming relaxation of the quadratic assignment problem.
  • Universality results extend comparable guarantees to dense and sparse Erdős-Rényi graphs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Incorporating contributions from the entire eigenbasis rather than only leading eigenvectors appears necessary to reach the information-theoretic noise threshold with spectral methods.
  • The Cauchy-kernel weighting may generalize to other random matrix ensembles whose eigenvalue spacings follow similar statistics.
  • Because the construction is a regularized relaxation, it may admit efficient convex or semidefinite-programming implementations in related combinatorial problems.

Load-bearing premise

The input graphs are generated exactly from the Gaussian Wigner model with edge-wise correlation 1-σ².

What would settle it

A large-n instance drawn from the Gaussian Wigner model with σ equal to c/log n for moderate constant c where GRAMPA fails to output the exact matching with probability bounded away from zero.

Figures

Figures reproduced from arXiv: 1907.08880 by Cheng Mao, Jiaming Xu, Yihong Wu, Zhou Fan.

Figure 1
Figure 1. Figure 1: Diagonal dominance of the similarity matrix [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: which we now explain. 0 0.1 0.2 0.3 0.4 0.5 0.6 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 [PITH_FULL_IMAGE:figures/full_fig_p035_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Comparison of six spectral methods for matching Erd˝os-R´enyi graphs with expected edge [PITH_FULL_IMAGE:figures/full_fig_p037_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Comparison of three competitive methods for matching Erd˝os-R´enyi graphs with expected [PITH_FULL_IMAGE:figures/full_fig_p038_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Comparison of GRAMPA and DegreeProfile on synthetic networks In Figures 5(c) and 5(d), we consider the stochastic blockmodel [HLL83] with two communities each of size 500. The probability of an edge between vertices in the same (resp. different) community is denoted by pin (resp. pout). The values of pin and pout are chosen so that the overall expected edge densities are p = 0.01 and 0.005 as in the Erd˝os… view at source ↗
Figure 6
Figure 6. Figure 6: Comparison of GRAMPA and DegreeProfile for matching networks of autonomous systems on nine days to that on the first day the nine days, in both measures of performance. 5 Conclusion We have proposed a highly practical spectral method, GRAMPA, for matching a pair of edge￾correlated graphs. By using a similarity matrix that is a weighted combination of outer products uiv > j across all pairs of eigenvectors … view at source ↗
read the original abstract

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-\sigma^2$, we show that GRAMPA exactly recovers the correct vertex correspondence with high probability when $\sigma = O(\frac{1}{\log n})$. This matches the state of the art of polynomial-time algorithms, and significantly improves over existing spectral methods which require $\sigma$ 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\H{o}s-R\'{e}nyi graphs, are deferred to the companion paper.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper introduces GRAMPA, a spectral graph matching algorithm that constructs a similarity matrix as a weighted sum of outer products between all pairs of eigenvectors of the two graphs, with weights from a Cauchy kernel on eigenvalue separations, followed by a rounding step to obtain the matching. This is also interpreted as the solution to a regularized quadratic programming relaxation of the QAP. For the Gaussian Wigner model with edge-weight correlation 1-σ², the paper proves exact recovery of the vertex correspondence with high probability when σ = O(1/log n), matching the best known polynomial-time algorithms and improving on prior spectral methods. Empirical results on synthetic and real datasets are included; universality extensions are deferred to a companion paper.

Significance. If the recovery guarantee holds, this advances spectral methods for graph matching by achieving the state-of-the-art threshold in the Gaussian Wigner model, demonstrating that eigenvector alignment with a suitable kernel can compete with more complex polynomial-time algorithms. The regularized relaxation view and the use of all eigenvector pairs (rather than top or same-order only) provide new theoretical insight into quadratic assignment relaxations.

major comments (2)
  1. [Proof of the main recovery theorem (likely §3–4)] The central recovery guarantee for σ = O(1/log n) depends on the error analysis of the similarity matrix; the handling of eigenvalue gaps in the Wigner ensemble and the resulting Cauchy-kernel weights must be shown to ensure the correct matching dominates (this is load-bearing for the claimed threshold).
  2. [Abstract] The abstract states that the result 'matches the state of the art of polynomial-time algorithms'; the specific prior work achieving the same O(1/log n) threshold should be cited explicitly so the improvement over existing spectral methods can be verified.
minor comments (2)
  1. [Abstract and main theorem statement] Clarify the precise high-probability statement (e.g., 1-n^{-ω(1)}) and any implicit constants in the O(1/log n) bound for direct comparison with prior results.
  2. [Model definition] The notation for the two graphs, their adjacency matrices, and the unknown permutation should be introduced with explicit equations in the model section.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive evaluation and the recommendation for minor revision. We address the two major comments point by point below.

read point-by-point responses

  1. Referee: [Proof of the main recovery theorem (likely §3–4)] The central recovery guarantee for σ = O(1/log n) depends on the error analysis of the similarity matrix; the handling of eigenvalue gaps in the Wigner ensemble and the resulting Cauchy-kernel weights must be shown to ensure the correct matching dominates (this is load-bearing for the claimed threshold).

    Authors: The proof of the main recovery result (Theorem 3.1 and its supporting lemmas in Sections 3–4) already contains the required error analysis. We bound the operator-norm deviation of the constructed similarity matrix from its ideal form by exploiting the typical eigenvalue spacing of order n^{-1/2} in the Wigner ensemble together with the decay properties of the Cauchy kernel; the resulting bound shows that the contribution of the true permutation strictly dominates all other terms with high probability precisely when σ = O(1/log n). The argument is self-contained and does not rely on external results beyond standard Wigner tail bounds. No additional revision is required, though we are happy to insert a short clarifying sentence if the editor prefers. revision: no

  2. Referee: [Abstract] The abstract states that the result 'matches the state of the art of polynomial-time algorithms'; the specific prior work achieving the same O(1/log n) threshold should be cited explicitly so the improvement over existing spectral methods can be verified.

    Authors: We agree that explicit citations will make the comparison clearer. We will revise the abstract (and the corresponding sentence in the introduction) to cite the polynomial-time algorithms that achieve the same O(1/log n) threshold, thereby highlighting both the matching statistical performance and the improvement over earlier spectral methods that required polynomially small σ. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper derives its central high-probability exact recovery guarantee for GRAMPA directly from analysis of the Gaussian Wigner model's eigenvector and eigenvalue statistics. The construction of the similarity matrix via Cauchy kernel on eigenvector pairs and the subsequent rounding are defined independently of the target recovery threshold; the bound σ = O(1/log n) is obtained as a mathematical consequence for this specific ensemble rather than by fitting parameters or renaming inputs. No load-bearing step reduces to a self-citation chain, self-definition, or fitted-input prediction. The companion paper is invoked only for universality extensions outside the present claim.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard properties of eigenvectors of symmetric random matrices and the specific statistics of the Gaussian Wigner ensemble; no free parameters, invented entities, or ad-hoc axioms are visible in the abstract.

axioms (1)
  • standard math Eigenvectors of symmetric matrices form an orthonormal basis
    Invoked when constructing the similarity matrix from all pairs of eigenvectors of the two graphs.

pith-pipeline@v0.9.0 · 5822 in / 1328 out tokens · 19251 ms · 2026-05-24T18:27:16.511441+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. The feasibility of multi-graph alignment: a Bayesian approach

    math.ST 2025-02 unverdicted novelty 7.0

    Establishes an all-or-nothing threshold for exact multi-graph alignment in the Gaussian model and a partial-alignment threshold in the sparse Erdős-Rényi model using a general Bayesian estimation framework over metric spaces.

  2. The feasibility of multi-graph alignment: a Bayesian approach

    math.ST 2025-02 unverdicted novelty 7.0

    Proves all-or-nothing exact alignment threshold in Gaussian multi-graph model and partial alignment impossibility threshold in sparse ER model, via a Bayesian estimation framework over metric spaces.

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages · cited by 1 Pith paper · 6 internal anchors

  1. [1]

    (Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs

    [BCL+18] Boaz Barak, Chi-Ning Chou, Zhixian Lei, Tselil Schramm, and Yueqi Sheng. (Nearly) efficient algorithms for the graph matching problem on correlated random graphs. arXiv preprint arXiv:1805.02349 ,

    work page internal anchor Pith review Pith/arXiv arXiv

  2. [2]

    Eigenvectors distribution and quantum unique ergodicity for deformed Wigner matrices

    [Ben17] Lucas Benigni. Eigenvectors distribution and quantum unique ergodicity for deformed Wigner matrices. arXiv preprint arXiv:1711.07103 ,

    work page arXiv

  3. [3]

    Improved achievability and converse bounds for Erd¨ os-R´ enyi graph matching

    [CK16] Daniel Cullina and Negar Kiyavash. Improved achievability and converse bounds for Erd¨ os-R´ enyi graph matching. InProceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science , pages 63–72. ACM,

    work page 2016

  4. [4]

    Exact alignment recovery for correlated Erd\H{o}s-R\'enyi graphs

    [CK17] Daniel Cullina and Negar Kiyavash. Exact alignment recovery for correlated Erd¨ os- R´ enyi graphs.arXiv preprint arXiv:1711.06783 ,

    work page internal anchor Pith review Pith/arXiv arXiv

  5. [5]

    Partial Recovery of Erd\H{o}s-R\'enyi Graph Alignment via $k$-Core Alignment

    [CKMP18] Daniel Cullina, Negar Kiyavash, Prateek Mittal, and H Vincent Poor. Partial recovery of Erd˝ os-R´ enyi graph alignment via k-core alignment. arXiv preprint arXiv:1809.03553, Nov

    work page internal anchor Pith review Pith/arXiv arXiv

  6. [6]

    Database alignment with gaussian features

    [DCK19] Osman Emre Dai, Daniel Cullina, and Negar Kiyavash. Database alignment with gaussian features. arXiv preprint arXiv:1903.01422 ,

    work page arXiv 1903

  7. [7]

    On the performance of a canonical labeling for matching correlated Erd˝ os-R´ enyi graphs

    46 [DCKG18] Osman Emre Dai, Daniel Cullina, Negar Kiyavash, and Matthias Grossglauser. On the performance of a canonical labeling for matching correlated Erd˝ os-R´ enyi graphs. arXiv preprint arXiv:1804.09758 ,

    work page arXiv

  8. [8]

    Efficient random graph matching via degree profiles

    [DMWX18] Jian Ding, Zongming Ma, Yihong Wu, and Jiaming Xu. Efficient random graph matching via degree profiles. arxiv preprint arxiv:1811.07821 , Nov

    work page arXiv

  9. [9]

    Spectral Alignment of Graphs

    [FQRM+16] Soheil Feizi, Gerald Quon, Mariana Recamonde-Mendoza, Muriel M´ edard, Mano- lis Kellis, and Ali Jadbabaie. Spectral alignment of networks. arXiv preprint arXiv:1602.04181,

    work page internal anchor Pith review Pith/arXiv arXiv

  10. [10]

    On the Rate of Convergence to the Marchenko--Pastur Distribution

    [GT11] Friedrich G¨ otze and A Tikhomirov. On the rate of convergence to the marchenko– pastur distribution. arXiv preprint arXiv:1110.1284 ,

    work page internal anchor Pith review Pith/arXiv arXiv

  11. [11]

    On the Structure and Efficient Computation of IsoRank Node Similarities

    47 [KG16] Ehsan Kazemi and Matthias Grossglauser. On the structure and efficient computation of isorank node similarities. arXiv preprint arXiv:1602.00668 ,

    work page internal anchor Pith review Pith/arXiv arXiv

  12. [12]

    Correcting the output of approximate graph matching algorithms

    [LS18] Joseph Lubars and R Srikant. Correcting the output of approximate graph matching algorithms. In IEEE INFOCOM 2018-IEEE Conference on Computer Communica- tions, pages 1745–1753. IEEE,

    work page 2018

  13. [13]

    De-anonymizing social networks

    [NS09] Arvind Narayanan and Vitaly Shmatikov. De-anonymizing social networks. In Security and Privacy, 2009 30th IEEE Symposium on , pages 173–187. IEEE,

    work page 2009

  14. [14]

    Seeded graph matching: Efficient algorithms and theoretical guarantees

    [SGE17] Farhad Shirani, Siddharth Garg, and Elza Erkip. Seeded graph matching: Efficient algorithms and theoretical guarantees. In 2017 51st Asilomar Conference on Signals, Systems, and Computers , pages 253–257. IEEE,

    work page 2017