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

\(k\) alignmentErdős-Rényi graphs

Mathematics Subject Classification ID

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) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85)

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

• 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
• 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?)
• Improved random graph isomorphism
• Random Graph Isomorphism
• Settling the Sharp Reconstruction Thresholds of Random Graph Matching

Cited in

(24)

• Graph matching beyond perfectly-overlapping Erdős--Rényi random graphs
• Efficient random graph matching via degree profiles
• Spectral alignment of correlated Gaussian matrices
• Aligning random graphs with a sub-tree similarity message-passing algorithm
• Seeded graph matching for correlated Erdős-Rényi graphs
• Correlation of Paths Between Distinct Vertices in a Randomly Oriented Graph
• 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
• Matching recovery threshold for correlated random graphs
• Partial Recovery in the Graph Alignment Problem
• Correlation detection in trees for planted graph alignment
• Statistical limits of correlation detection in trees
• A polynomial-time approximation scheme for the maximal overlap of two independent Erdős-Rényi graphs
• A computational transition for detecting correlated stochastic block models by low-degree polynomials
• Low-degree hardness of detection for correlated Erdős-Rényi graphs
• Asymptotic mutual information in quadratic estimation problems over compact groups
• Covariance alignment: from maximum likelihood estimation to Gromov-Wasserstein
• Efficiently matching random inhomogeneous graphs via degree profiles
• A polynomial time iterative algorithm for matching Gaussian matrices with non-vanishing correlation
• Average-case and smoothed analysis of graph isomorphism
• The algorithmic phase transition of random graph alignment problem
• Graph matching via convex relaxation to the simplex
• Testing network correlation efficiently via counting trees
• Faster algorithms for the alignment of sparse correlated Erdős-Rényi 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)