Partial Recovery in the Graph Alignment Problem

DOI10.1287/OPRE.2022.2355MaRDI QIDQ6202672zbMATH OpenOpenAlexFDO

Authors Georgina Hall, Laurent Massoulié

Publication date 26 February 2024

Published in Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

correlated Erdős-Rényi graphsgraph alignmentmachine learning and data sciencepartial recovery

Mathematics Subject Classification ID

Mathematical programming (90Cxx)

Abstract: In this paper, we consider the graph alignment problem, which is the problem of recovering, given two graphs, a one-to-one mapping between nodes that maximizes edge overlap. This problem can be viewed as a noisy version of the well-known graph isomorphism problem and appears in many applications, including social network deanonymization and cellular biology. Our focus here is on partial recovery, i.e., we look for a one-to-one mapping which is correct on a fraction of the nodes of the graph rather than on all of them, and we assume that the two input graphs to the problem are correlated ErdH{o}s-R'enyi graphs of parameters $(n,q,s)$. Our main contribution is then to give necessary and sufficient conditions on $(n,q,s)$ under which partial recovery is possible with high probability as the number of nodes $n$ goes to infinity. In particular, we show that it is possible to achieve partial recovery in the $nqs=Theta(1)$ regime under certain additional assumptions.

Recommendations

• Matching recovery threshold for correlated random graphs
• Aligning random graphs with a sub-tree similarity message-passing algorithm
• Exact matching of random graphs with constant correlation
• Correlation detection in trees for planted graph alignment

Cited in

(17)

• Aligning random graphs with a sub-tree similarity message-passing algorithm
• Matching recovery threshold for correlated random graphs
• Correlation detection in trees for planted graph alignment
• Statistical limits of correlation detection in trees
• 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
• 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
• On Seeded Subgraph-to-Subgraph Matching: The ssSGM Algorithm and Matchability Information Theory
• Optimal recovery of correlated Erdős-Rényi graphs
• Algorithmic contiguity from low-degree conjecture and applications in correlated random graphs

This page was built for publication: Partial Recovery in the Graph Alignment Problem

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