Testing network correlation efficiently via counting trees

DOI10.1214/23-AOS2261MaRDI QIDQ7035877zbMATH OpenFDO

Authors Cheng Mao, Yihong Wu, Jiaming Xu, Sophie H. Yu

Publication date 29 January 2025

Published in The Annals of Statistics (Search for Journal in Brave)

Full work available at URL https://projecteuclid.org/journals/annals-of-statistics/volume-52/issue-6/Testing-network-correlation-efficiently-via-counting-trees/10.1214/23-AOS2261.full

zbMATH Keywords

correlated Erdős-Rényi graphscounting signed treesdetecting network correlationgraph matchinglow-degree polynomials

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Hypothesis testing in multivariate analysis (62H15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Cites work

• Aligning random graphs with a sub-tree similarity message-passing algorithm
• Analysis of Boolean Functions
• Color-coding
• Constant Time Generation of Free Trees
• Contiguity and non-reconstruction results for planted partition models: the dense case
• Efficient Bayesian estimation from few samples: community detection and related problems
• Efficient random graph matching via degree profiles
• Exact matching of random graphs with constant correlation
• scientific article; zbMATH DE number 1979521 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 7829306 (Why is no real title available?)
• Introduction to Random Graphs
• Linear Time Automorphism Algorithms for Trees, Interval Graphs, and Planar Graphs
• Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
• Optimal adaptivity of signed-polygon statistics for network testing
• Partial Recovery in the Graph Alignment Problem
• Reconstruction and estimation in the planted partition model
• Settling the Sharp Reconstruction Thresholds of Random Graph Matching
• Spectral graph matching and regularized quadratic relaxations. II: Erdős-Rényi graphs and universality
• Testing correlation of unlabeled random graphs
• Testing for high-dimensional geometry in random graphs
• Testing network correlation efficiently via counting trees
• The number of homeomorphically irreducible trees, and other species
• The number of trees
• Vector correlation

Cited in

(8)

• 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

This page was built for publication: Testing network correlation efficiently via counting trees

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