English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We analyze a new spectral graph matching algorithm, GRAph Matching byPairwise eigen-Alignments (GRAMPA), for recovering the latent vertexcorrespondence between two unlabeled, edge-correlated weighted graphs.Extending the exact recovery guarantees established in the companion paper forGaussian weights, in this work, we prove the universality of these guaranteesfor a general correlated Wigner model. In particular, for two Erd\H{o}s-R\'enyigraphs with edge correlation coefficient $1-\sigma^2$ and average degree atleast $\operatorname{polylog}(n)$, we show that GRAMPA exactly recovers thelatent vertex correspondence with high probability when $\sigma \lesssim1/\operatorname{polylog}(n)$. Moreover, we establish a similar guarantee for avariant of GRAMPA, corresponding to a tighter quadratic programming relaxationof the quadratic assignment problem. Our analysis exploits a resolventrepresentation of the GRAMPA similarity matrix and local laws for theresolvents of sparse Wigner matrices.

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