mlsanityData to 14 Oct 2026

Testing network correlation efficiently via counting trees

arXiv 2110.11816 ↗First posted 22 Oct 2021math.ST stat.ML stat.THcited by 22

Not on the map. Why?

Abstract (arXiv)

We propose a new procedure for testing whether two networks are edge-correlated through some latent vertex correspondence. The test statistic is based on counting the co-occurrences of signed trees for a family of non-isomorphic trees. When the two networks are ErdHos-R'enyi random graphs G(n,q) that are either independent or correlated with correlation coefficient ρ, our test runs in n2+o(1) time and succeeds with high probability as n→∞, provided that nminq,1-q ≥ n-o(1) and ρ2>α ≈ 0.338, where α is Otter's constant so that the number of unlabeled trees with K edges grows as (1/α)K. This significantly improves the prior work in terms of statistical accuracy, running time, and graph sparsity.

Key facts. Cited by 22 papers in the map (data through 14 Oct 2026). Builds on 21 of its 50 references that are in the map. First posted on arXiv 22 Oct 2021.

Builds on

21 of 50 references.

References · 21

  1. 2019Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratiocited by 85
  2. 2018Efficient random graph matching via degree profilescited by 48
  3. 2021Settling the Sharp Reconstruction Thresholds of Random Graph Matchingcited by 45
  4. 2017Exact alignment recovery for correlated ErdHos-R'enyi graphscited by 38
  5. 2016Improved Achievability and Converse Bounds for ErdHos-R'enyi Graph Matchingcited by 30
  6. 2018(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphscited by 29
  7. 2017Bayesian estimation from few samples: community detection and related problemscited by 28
  8. 2014Graph Matching: Relax at Your Own Riskcited by 27
  9. 2019Spectral Graph Matching and Regularized Quadratic Relaxations II: ErdHos-R'enyi Graphs and Universalitycited by 27
  10. 2020Partial Recovery in the Graph Alignment Problemcited by 27
  11. 2020From tree matching to sparse graph alignmentcited by 26
  12. 2020Testing correlation of unlabeled random graphscited by 26
9 more
  1. 2014Testing for high-dimensional geometry in random graphscited by 25
  2. 2021Exact Matching of Random Graphs with Constant Correlationcited by 23
  3. 2021Random Graph Matching with Improved Noise Robustnesscited by 16
  4. 2017Optimal hypothesis testing for stochastic block models with growing degreescited by 13
  5. 2019Spectral Graph Matching and Regularized Quadratic Relaxations I: The Gaussian Modelcited by 13
  6. 2016Spectral Alignment of Graphscited by 12
  7. 2017Testing for Global Network Structure Using Small Subgraph Statisticscited by 9
  8. 2019Optimal Adaptivity of Signed-Polygon Statistics for Network Testingcited by 8
  9. 2017Testing Network Structure Using Relations Between Small Subgraph Probabilitiescited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 7; 2023: 4; 2024: 6; 2025: 3; 2026: 2.

22 papers.

Sort:

  1. 2022Random graph matching at Otter's threshold via counting chandelierscited by 25
  2. 2022Matching recovery threshold for correlated random graphscited by 16
  3. 2022Detection threshold for correlated ErdHos-R'enyi graphs via densest subgraphscited by 13
  4. 2022Statistical limits of correlation detection in treescited by 12
  5. 2023A polynomial-time iterative algorithm for random graph matching with non-vanishing correlationcited by 9
  6. 2022A polynomial time iterative algorithm for matching Gaussian matrices with non-vanishing correlationcited by 8
  7. 2024The Umeyama algorithm for matching correlated Gaussian geometric models in the low-dimensional regimecited by 6
  8. 2023Efficiently matching random inhomogeneous graphs via degree profilescited by 5
  9. 2022On Correlation Detection and Alignment Recovery of Gaussian Databasescited by 3
  10. 2023Graph Matching via convex relaxation to the simplexcited by 3
  11. 2025Computational Lower Bounds for Correlated Random Graphs via Algorithmic Contiguitycited by 3
  12. 2023Testing Dependency of Unlabeled Databasescited by 2
10 more
  1. 2024The graph alignment problem: fundamental limits and efficient algorithmscited by 2
  2. 2026Fundamental Limits of Community Detection in Contextual Multi-Layer Stochastic Block Modelscited by 2
  3. 2025Counting Cycles with AI: Counting Cycles with AI: Computationally Efficient Equivalent Forms with Applicationscited by 1
  4. 2022Statistical Limits for Testing Correlation of Hypergraphscited by 0
  5. 2024Detection of Correlated Random Vectorscited by 0
  6. 2024Information-Theoretic Thresholds for the Alignments of Partially Correlated Graphscited by 0
  7. 2024Testing Dependency of Weighted Random Graphscited by 0
  8. 2024Robust Random Graph Matching in Dense Graphs via an Approximate Message Passing Type Algorithmcited by 0
  9. 2025A Smooth Computational Transition in Tensor PCAcited by 0
  10. 2026Sharp Statistical Thresholds for Attributed Gaussian Graph Matchingcited by 0