Spectral Graph Matching and Regularized Quadratic Relaxations II: Erd\H{o}s-R\'enyi Graphs and Universality

Cheng Mao; Jiaming Xu; Yihong Wu; Zhou Fan

arxiv: 1907.08883 · v1 · pith:I7BSBQ66new · submitted 2019-07-20 · 🧮 math.PR · cs.LG· math.SP· math.ST· stat.ML· stat.TH

Spectral Graph Matching and Regularized Quadratic Relaxations II: ErdH{o}s-R\'enyi Graphs and Universality

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

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

classification 🧮 math.PR cs.LGmath.SPmath.STstat.MLstat.TH

keywords graph matchingErdős-Rényi graphsspectral alignmentquadratic assignmentrandom graphsresolvent methodsexact recoveryuniversality

0 comments

The pith

GRAMPA exactly recovers the latent vertex correspondence between two correlated Erdős-Rényi graphs with high probability when the edge correlation is 1 minus a small noise term and average degree exceeds polylog n.

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

The paper shows that the GRAMPA algorithm, based on pairwise eigen-alignments, succeeds in exact recovery for a pair of edge-correlated Erdős-Rényi graphs under a polylogarithmic degree condition and sufficiently strong correlation. This result extends earlier exact-recovery guarantees that held only for Gaussian edge weights to a broad class of correlated Wigner matrices, establishing a form of universality. A reader would care because the setting directly models practical problems of aligning noisy unlabeled networks that arise in data integration and network analysis. The proof proceeds by representing the GRAMPA similarity matrix through resolvents and invoking local laws for those resolvents.

Core claim

For two Erdős-Rényi graphs with edge correlation coefficient 1-σ² and average degree at least polylog(n), GRAMPA exactly recovers the latent vertex correspondence with high probability whenever σ ≲ 1/polylog(n). The same guarantee holds for a variant of GRAMPA that corresponds to a tighter quadratic programming relaxation of the quadratic assignment problem. The argument relies on a resolvent representation of the GRAMPA similarity matrix together with local laws for the resolvents of sparse Wigner matrices.

What carries the argument

Resolvent representation of the GRAMPA similarity matrix, combined with local laws for resolvents of sparse Wigner matrices.

If this is right

Exact recovery extends from Gaussian weights to general correlated Wigner models including Erdős-Rényi graphs.
A tighter quadratic relaxation of the assignment problem inherits the same exact-recovery threshold.
The method succeeds with high probability once the noise level drops below 1 over polylog(n) under the stated degree lower bound.
The analysis applies to weighted graphs whose edge weights satisfy the sparse Wigner assumptions.

Where Pith is reading between the lines

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

The same resolvent technique may yield recovery thresholds for other sparse random graph ensembles beyond ER.
If local laws can be sharpened to hold at lower degrees, the polylog(n) barrier on average degree could be relaxed.
The universality statement suggests that GRAMPA performance is insensitive to the precise distribution of edge weights provided the second-moment and independence conditions hold.

Load-bearing premise

Local laws for the resolvents of sparse Wigner matrices continue to hold when the average degree is only polylogarithmic in n.

What would settle it

An explicit construction or numerical instance of two correlated ER graphs with average degree polylog(n) and σ of order 1/polylog(n) in which GRAMPA fails to recover the exact correspondence.

read the original abstract

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 the 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\H{o}s-R\'enyi graphs with edge correlation coefficient $1-\sigma^2$ and average degree at least $\operatorname{polylog}(n)$, we show that GRAMPA exactly recovers the latent vertex correspondence with high probability when $\sigma \lesssim 1/\operatorname{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.

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.

Desk Editor's Note private letter to a colleague

This extends GRAMPA exact recovery to correlated ER graphs via resolvents, but the local-law step at polylog degrees is the part that needs the closest check.

read the letter

The one thing to know is that this paper claims exact recovery for GRAMPA on two correlated Erdős-Rényi graphs when the average degree is at least polylog(n) and the noise parameter sigma is at most 1 over polylog(n). It does this by moving from the Gaussian companion paper to a resolvent representation that works for the general correlated Wigner model, and it also treats a tighter quadratic relaxation variant. That universality step is the actual new content. The abstract states the result cleanly and the proof outline via resolvents looks like a reasonable way to get the error control without extra combinatorial machinery. The paper does well in making the similarity matrix and its eigen-alignment properties explicit, and in flagging the local-law dependence up front. The citation pattern to prior spectral matching work is standard and not obviously missing key references. The soft spot is exactly the one the stress-test note flags: the local laws for sparse Wigner resolvents at polylog degrees. Those bounds are sensitive to the imaginary-part cutoff and the precise scaling of sigma, and if the paper only cites them rather than proving the needed error terms in this regime, the high-probability claim could slip. The rest of the argument appears to follow once that step is granted, so the result is not circular beyond the companion paper. This is aimed at people working on random graphs, network alignment, or quadratic assignment relaxations. A reader who wants concrete thresholds for a spectral method in the standard ER model would get something usable from it. It deserves a serious referee because the claim is specific, the model is central, and the technical approach is developed enough to be worth checking in detail. I would send it to peer review.

Referee Report

1 major / 1 minor

Summary. The manuscript proves exact recovery guarantees for the GRAMPA spectral graph matching algorithm (and a tighter quadratic relaxation variant) on pairs of edge-correlated Erdős-Rényi graphs. For average degree at least polylog(n) and edge correlation coefficient 1-σ² with σ ≲ 1/polylog(n), GRAMPA recovers the latent vertex correspondence with high probability. The argument extends the Gaussian case from the companion paper by establishing a resolvent representation of the GRAMPA similarity matrix and invoking local laws for the resolvents of sparse Wigner matrices.

Significance. If the local-law error bounds hold at the stated sparsity and correlation scales, the result establishes universality of the spectral method beyond Gaussian weights in the sparse regime. This is a meaningful advance for the quadratic assignment problem and network alignment, as it supplies the first such guarantees for ER graphs under polylog degree. The resolvent approach itself is a technical strength.

major comments (1)

[Abstract, final paragraph] Abstract (final paragraph) and the resolvent analysis section: the exact-recovery claim rests on local laws for sparse Wigner resolvents controlling the error in the GRAMPA matrix representation at degree d ≳ polylog(n) and imaginary-part cutoff compatible with σ ≲ 1/polylog(n). The manuscript must explicitly state the local-law error bounds (including the dependence on the imaginary part and the correlation parameter) and verify that they are sufficient for the high-probability exact-recovery conclusion; otherwise the central guarantee does not follow.

minor comments (1)

Notation for the correlation parameter and the degree threshold should be made uniform between the abstract and the main theorems.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive assessment of our work and for the detailed comment. We address the major comment below.

read point-by-point responses

Referee: [Abstract, final paragraph] Abstract (final paragraph) and the resolvent analysis section: the exact-recovery claim rests on local laws for sparse Wigner resolvents controlling the error in the GRAMPA matrix representation at degree d ≳ polylog(n) and imaginary-part cutoff compatible with σ ≲ 1/polylog(n). The manuscript must explicitly state the local-law error bounds (including the dependence on the imaginary part and the correlation parameter) and verify that they are sufficient for the high-probability exact-recovery conclusion; otherwise the central guarantee does not follow.

Authors: We agree that explicitly stating the local-law error bounds would make the central argument fully self-contained. In the revised manuscript we will add, in the resolvent analysis section, the precise statements of the local laws for the resolvents of sparse Wigner matrices (including the explicit dependence of the error terms on the imaginary part η and on the correlation parameter σ). We will also insert a short verification paragraph confirming that these bounds are compatible with the stated scales d ≳ polylog(n) and σ ≲ 1/polylog(n) and therefore suffice to control the GRAMPA similarity-matrix error, yielding the high-probability exact-recovery conclusion. The abstract will be updated to reference these bounds. revision: yes

Circularity Check

0 steps flagged

Minor self-citation to companion paper; ER analysis uses independent resolvent argument

full rationale

The paper explicitly extends exact-recovery guarantees from a companion paper (Gaussian weights) but states that it proves universality for the ER case via a resolvent representation of the GRAMPA matrix plus local laws for sparse Wigner matrices. No step reduces a claimed prediction to a fitted input or self-citation by construction; the ER result is presented as a new derivation under the polylog(n) degree regime. The self-citation is therefore load-bearing only for the Gaussian baseline and does not force the ER conclusion.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on domain assumptions from random matrix theory rather than new free parameters or invented entities.

axioms (1)

domain assumption Local laws for resolvents of sparse Wigner matrices hold under polylog(n) average degree
Invoked to analyze the GRAMPA similarity matrix (abstract, final sentence).

pith-pipeline@v0.9.0 · 5730 in / 1144 out tokens · 23391 ms · 2026-05-24T18:28:29.801508+00:00 · methodology