Exact matching of random graphs with constant correlation

DOI10.1007/S00440-022-01184-3MaRDI QIDQ6041769zbMATH OpenOpenAlexFDO

Authors Cheng Mao, Mark Rudelson, Konstantin E. Tikhomirov

Publication date 12 May 2023

Published in Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2110.05000

zbMATH Keywords

Erdős-Rényi graphs\(k\) alignment

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: This paper deals with the problem of graph matching or network alignment for ErdH{o}s--R'enyi graphs, which can be viewed as a noisy average-case version of the graph isomorphism problem. Let $G$ and $G^{\prime }$ be $G(n,p)$ ErdH{o}s--R'enyi graphs marginally, identified with their adjacency matrices. Assume that $G$ and $G^{\prime }$ are correlated such that $mathbbE[G_{ij}G{\text{'}}_{ij}]=p(1-alpha)$. For a permutation $pi$ representing a latent matching between the vertices of $G$ and $G^{\prime }$, denote by $G^{p}i$ the graph obtained from permuting the vertices of $G$ by $pi$. Observing $G^{p}i$ and $G^{\prime }$, we aim to recover the matching $pi$. In this work, we show that for every $varepsilonin(0,1]$, there is $n_0>0$ depending on $varepsilon$ and absolute constants $alph{a}_0,R>0$ with the following property. Let $nge{n}_0$, $(1+varepsilon)lognlenple{n}^{frac1Rloglogn}$, and $0<alpha<min(alph{a}_0,varepsilon/4)$. There is a polynomial-time algorithm $F$ such that $mathbbPF(G^{p}i,G^{\prime })=pi=1-o(1)$. This is the first polynomial-time algorithm that recovers the exact matching between vertices of correlated ErdH{o}s--R'enyi graphs with constant correlation with high probability. The algorithm is based on comparison of partition trees associated with the graph vertices.

Recommendations

• Graph matching beyond perfectly-overlapping Erdős--Rényi random graphs
• scientific article; zbMATH DE number 2127722
• The matching energy of random graphs
• The number of matchings in random graphs
• Maximum matchings in a class of random graphs
• Perfect matchings in random intersection graphs
• Random matchings in regular graphs
• Perfect matchings in the semirandom graph process
• Random-link matching problems on random regular graphs
• Matching recovery threshold for correlated random graphs

Cites work

• scientific article; zbMATH DE number 1302195 (Why is no real title available?)
• scientific article; zbMATH DE number 714526 (Why is no real title available?)
• scientific article; zbMATH DE number 7626795 (Why is no real title available?)
• Distinguishing Vertices of Random Graphs
• Efficient random graph matching via degree profiles
• Graph isomorphism in quasipolynomial time (extended abstract)
• High-dimensional probability. An introduction with applications in data science
• Improved random graph isomorphism
• Random Graph Isomorphism
• Settling the Sharp Reconstruction Thresholds of Random Graph Matching

Cited in

(13)

• Aligning random graphs with a sub-tree similarity message-passing algorithm
• Graph matching beyond perfectly-overlapping Erdős--Rényi random graphs
• Seeded graph matching for correlated Erdős-Rényi graphs
• Spectral alignment of correlated Gaussian matrices
• Correlation detection in trees for planted graph alignment
• Correlation of Paths Between Distinct Vertices in a Randomly Oriented Graph
• Efficient random graph matching via degree profiles
• Statistical limits of correlation detection in trees
• Spectral graph matching and regularized quadratic relaxations. I: Algorithm and Gaussian analysis
• Spectral graph matching and regularized quadratic relaxations. II: Erdős-Rényi graphs and universality
• Partial Recovery in the Graph Alignment Problem
• A polynomial-time approximation scheme for the maximal overlap of two independent Erdős-Rényi graphs
• Matching recovery threshold for correlated random graphs

This page was built for publication: Exact matching of random graphs with constant correlation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6041769)