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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

In the \emph{graph matching} problem we observe two graphs $G,H$ and the goalis to find an assignment (or matching) between their vertices such that somemeasure of edge agreement is maximized. We assume in this work that theobserved pair $G,H$ has been drawn from the correlated Wigner model -- apopular model for correlated weighted graphs -- where the entries of theadjacency matrices of $G$ and $H$ are independent Gaussians and each edge of$G$ is correlated with one edge of $H$ (determined by the unknown matching)with the edge correlation described by a parameter $\sigma\in [0,1)$. In thispaper, we analyse the performance of the \emph{projected power method} (PPM) asa \emph{seeded} graph matching algorithm where we are given an initialpartially correct matching (called the seed) as side information. We prove thatif the seed is close enough to the ground-truth matching, then with highprobability, PPM iteratively improves the seed and recovers the ground-truthmatching (either partially or exactly) in $\mathcal{O}(\log n)$ iterations. Ourresults prove that PPM works even in regimes of constant $\sigma$, thusextending the analysis in \citep{MaoRud} for the sparse Erd\H{o}s-R\'enyi modelto the (dense) Wigner model. As a byproduct of our analysis, we see that thePPM framework generalizes some of the state-of-art algorithms for seeded graphmatching. We support and complement our theoretical findings with numericalexperiments on synthetic data.

Seeded graph matching for the correlated Wigner model via the projected power method