Exact matching of random graphs with constant correlation

DOI10.1007/S00440-022-01184-3zbMATH Open1512.05361arXiv2110.05000OpenAlexW4313595333MaRDI QIDQ6041769FDOQ6041769

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)

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.

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

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

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)

Cites Work

• High-dimensional probability. An introduction with applications in data science
• Efficient random graph matching via degree profiles
• Settling the Sharp Reconstruction Thresholds of Random Graph Matching
• Improved random graph isomorphism
• Random Graph Isomorphism
• Title not available (Why is that?)
• Title not available (Why is that?)
• Graph isomorphism in quasipolynomial time (extended abstract)
• Distinguishing Vertices of Random Graphs
• Title not available (Why is that?)

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)