Efficient random graph matching via degree profiles

DOI10.1007/S00440-020-00997-4MaRDI QIDQ2660385zbMATH OpenOpenAlexFDO

Authors Jian Ding, Zongming Ma, Yihong Wu, Jiaming Xu

Publication date 30 March 2021

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

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

zbMATH Keywords

degree profilesErdős-Rényi graphgraph matchingquadratic assignment problemrandom graph isomorphism

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) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Abstract: Random graph matching refers to recovering the underlying vertex correspondence between two random graphs with correlated edges; a prominent example is when the two random graphs are given by ErdH{o}s-R'{e}nyi graphs $G(n,fracdn)$. This can be viewed as an average-case and noisy version of the graph isomorphism problem. Under this model, the maximum likelihood estimator is equivalent to solving the intractable quadratic assignment problem. This work develops an $ildeO(n{d}^2+n^2)$-time algorithm which perfectly recovers the true vertex correspondence with high probability, provided that the average degree is at least $d=Omega(lo{g}^{2}n)$ and the two graphs differ by at most $delta=O(lo{g}^{-2}(n))$ fraction of edges. For dense graphs and sparse graphs, this can be improved to $delta=O(lo{g}^{-2/3}(n))$ and $delta=O(lo{g}^{-2}(d))$ respectively, both in polynomial time. The methodology is based on appropriately chosen distance statistics of the degree profiles (empirical distribution of the degrees of neighbors). Before this work, the best known result achieves $delta=O(1)$ and $n^{o(1)}leqdleq{n}^c$ for some constant $c$ with an $n^{O(logn)}$-time algorithm cite{barak2018nearly} and $delta=ildeO((d/n{)}^4)$ and $d=ildeOmega(n^{4/5})$ with a polynomial-time algorithm cite{dai2018performance}.

Recommendations

• Exact matching of random graphs with constant correlation
• Graph matching beyond perfectly-overlapping Erdős--Rényi random graphs
• Spectral graph matching and regularized quadratic relaxations. I: Algorithm and Gaussian analysis

Cites work

• A complete proof of universal inequalities for the distribution function of the binomial law
• A sharp estimate of the binomial mean absolute deviation with applications
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Central limit theorems for the Wasserstein distance between the empirical and the true distributions
• Distinguishing Vertices of Random Graphs
• Distributed optimization and statistical learning via the alternating direction method of multipliers
• Gaussian processes: Inequalities, small ball probabilities and applications
• Generalized Sphere-Packing Bounds on the Size of Codes for Combinatorial Channels
• Graphs on unlabelled nodes with a given number of edges
• scientific article; zbMATH DE number 5604036 (Why is no real title available?)
• 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 741240 (Why is no real title available?)
• scientific article; zbMATH DE number 1131873 (Why is no real title available?)
• Improved random graph isomorphism
• Maximal Flow Through a Network
• Mean, Median and Mode in Binomial Distributions
• On convex relaxation of graph isomorphism
• On spectral properties for graph matching and graph isomorphism problems
• Order Statistics
• Probability and Computing
• Random Graph Isomorphism
• Random graphs.
• Seeded graph matching for correlated Erdős-Rényi graphs
• Semidefinite programming relaxations for the quadratic assignment problem
• Some inequalities relating to the partial sum of binomial probabilities
• The graph matching problem
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(36)

• Graph matching beyond perfectly-overlapping Erdős--Rényi random graphs
• Iterative algorithm for discrete structure recovery
• Correlated randomly growing graphs
• A Fast Perfect-Matching Algorithm in Random Graphs
• Vertex nomination via seeded graph matching
• Matchability of heterogeneous networks pairs
• scientific article; zbMATH DE number 7626795 (Why is no real title available?)
• Maximum Likelihood Estimation and Graph Matching in Errorfully Observed Networks
• Spectral alignment of correlated Gaussian matrices
• Aligning random graphs with a sub-tree similarity message-passing algorithm
• Data Reduction for Maximum Matching on Real-World Graphs
• Exact matching of random graphs with constant correlation
• 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
• Testing correlation of unlabeled random graphs
• Matching recovery threshold for correlated random graphs
• Statistical limits for testing correlation of random hypergraphs
• Correlation detection in trees for planted graph alignment
• 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
• Statistical and Computational Efficiency for Smooth Tensor Estimation with Unknown Permutations
• Alignment and comparison of directed networks via transition couplings of random walks
• 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
• On Seeded Subgraph-to-Subgraph Matching: The ssSGM Algorithm and Matchability Information Theory
• Cluster-Aware Matching via Laplacian Optimal Transport
• Robust point matching with distance profiles
• Optimal recovery of correlated Erdős-Rényi graphs
• Algorithmic contiguity from low-degree conjecture and applications in correlated random graphs

Describes a project that uses

Uses Software

• IsoRank

This page was built for publication: Efficient random graph matching via degree profiles

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