Testing correlation of unlabeled random graphs

DOI10.1214/22-AAP1786MaRDI QIDQ6109918zbMATH OpenFDO

Authors Yihong Wu, Jiaming Xu, Sophie H. Yu

Publication date 31 July 2023

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2008.10097, https://projecteuclid.org/journals/annals-of-applied-probability/volume-33/issue-4/Testing-correlation-of-unlabeled-random-graphs/10.1214/22-AAP1786.full

zbMATH Keywords

conditional second moment methodcycle decompositionErdős-Rényi graphsgraph matchinghypothesis testingunlabeled graphs

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Random graphs (graph-theoretic aspects) (05C80) Hypothesis testing in multivariate analysis (62H15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Abstract: We study the problem of detecting the edge correlation between two random graphs with $n$ unlabeled nodes. This is formalized as a hypothesis testing problem, where under the null hypothesis, the two graphs are independently generated; under the alternative, the two graphs are edge-correlated under some latent node correspondence, but have the same marginal distributions as the null. For both Gaussian-weighted complete graphs and dense ErdH{o}s-R'enyi graphs (with edge probability $n^{-o(1)}$), we determine the sharp threshold at which the optimal testing error probability exhibits a phase transition from zero to one as $noinfty$. For sparse ErdH{o}s-R'enyi graphs with edge probability $n^{-Omega(1)}$, we determine the threshold within a constant factor. The proof of the impossibility results is an application of the conditional second-moment method, where we bound the truncated second moment of the likelihood ratio by carefully conditioning on the typical behavior of the intersection graph (consisting of edges in both observed graphs) and taking into account the cycle structure of the induced random permutation on the edges. Notably, in the sparse regime, this is accomplished by leveraging the pseudoforest structure of subcritical ErdH{o}s-R'enyi graphs and a careful enumeration of subpseudoforests that can be assembled from short orbits of the edge permutation.

Cites work

• Analytic combinatorics
• Community detection in dense random networks
• Community detection in sparse random networks
• Correlated randomly growing graphs
• Dense subgraphs in random graphs
• Detection of a sparse submatrix of a high-dimensional noisy matrix
• Efficient random graph matching via degree profiles
• Generalized Sphere-Packing Bounds on the Size of Codes for Combinatorial Channels
• scientific article; zbMATH DE number 714526 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 3096864 (Why is no real title available?)
• Introduction to nonparametric estimation
• Introduction to Random Graphs
• Reconstruction and estimation in the planted partition model
• Settling the Sharp Reconstruction Thresholds of Random Graph Matching
• Spectral alignment of correlated Gaussian matrices
• Testing correlation of unlabeled random graphs
• The all-or-nothing phenomenon in sparse linear regression
• The graph matching problem
• The number of trees

Cited in

(15)

• 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
• 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
• 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
• Testing network correlation efficiently via counting trees
• Optimal recovery of correlated Erdős-Rényi graphs
• Algorithmic contiguity from low-degree conjecture and applications in correlated random graphs
• Strong detection threshold for correlated Erdős-Rényi graphs with constant average degree

This page was built for publication: Testing correlation of unlabeled random graphs

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