Pith. sign in

REVIEW 12 references

Sample Complexity of Correlation Detection in the Gaussian Wigner Model

T0 review · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The optimal induced-subgraph sample size for detecting correlation in the Gaussian Wigner model is s ≈ sqrt(max(n log n / log(1/(1-ρ^2)), n)).

arxiv 2505.14138 v1 pith:5N27DSSX submitted 2025-05-20 math.ST stat.TH

Dong Huang , Pengkun Yang This is my paper · ORCID
classification math.STstat.TH
keywords correlationhypothesisunderanalysisdetectiongaussiangraphsmodel
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Two random graphs are correlated if their edge weights are paired through a secret permutation of the vertices. This paper asks: if we only see a random subset of vertices from each graph, called an induced subgraph, how many vertices must we sample to decide whether the graphs are correlated or independent? The answer depends on the graph size n and the correlation strength ρ. For strong correlation, sampling about the square root of n vertices suffices; for weaker correlation, the required sample grows like sqrt(n log n / log(1/(1-ρ^2))).

The proof splits into two directions. To show detection is possible, the authors construct test statistics that look for the best partial matching between the sampled subgraphs. One statistic maximizes the overlap of edge products, the other minimizes the mean squared difference; each works in a different correlation regime. To show detection is impossible below the threshold, they use the second moment method, conditioning on the random number of vertices that the two samples actually share. The main technical novelty is an analysis of the 'core set' of vertices on which two random permutations agree, which controls the explosion of the second moment.

The paper also proposes a clique-based approximate algorithm that avoids exhaustive search over all permutations, with experiments on synthetic and small real networks. The algorithm has no theoretical guarantee, which the authors acknowledge.

Extended reading notes

Core claim

Theorem 1 states: There exist constants C, C' such that, for any 0<ρ<1, if s^2 ≥ C (n log n / log(1/(1-ρ^2)) ∨ n), then TV(P,Q) ≥ 0.9; conversely, if s^2 ≤ C (n log n / log(1/(1-ρ^2)) ∨ n), then TV(P,Q) ≤ 0.1. This pins the optimal sample size to order max(n log n / log(1/(1-ρ^2)), n)^{1/2}.

Load-bearing premise

The latent vertex permutation is modeled as uniformly random and independent of the vertex sampling (Eq. (7), Section 3). All impossibility results use the averaged likelihood ratio over this uniform prior. If the permutation is adversarial or drawn from a non-uniform prior, the sample complexity could be different. This modeling choice is load-bearing and is not justified by real-world alignment problems.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The theoretical results carry no fitted parameters; all constants are universal and fixed in the proofs. The model assumptions (Gaussian Wigner edge weights, uniform random permutation, independent uniform vertex sampling) are standard and stated upfront. The core set I* is a proof tool, not a new physical entity; it has no independent evidential weight.

assumptions (5)
  • domain assumption Edge weights in the Gaussian Wigner model are independent standard normals; correlated pairs have joint normal with correlation ρ (Definition 1).
    This defines the model under H0 and H1.
  • domain assumption The latent permutation π* is uniformly distributed over S_n and independent of the vertex sampling (Eq. (7)).
    The likelihood ratio is an average over the uniform prior; Lemma 1 uses this.
  • domain assumption The two sampled vertex sets are independent uniform s-subsets without replacement (Section 1.1).
    This yields the hypergeometric distribution for the common set size.
  • standard math Full-observation detection threshold of WXY23 (ρ^2 ≍ log n / n) is used as a black box in Proposition 3 (reduction).
    External theorem from WXY23, used to bound TV of the fully correlated model on the common set.
  • standard math Standard concentration inequalities: Chernoff, Hanson-Wright, chi-square tail, hypergeometric concentration (Lemmas 4-6).
    Stated and proved in Appendix D, but rely on classical results.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Sample Complexity of Correlation Detection in the Gaussian Wigner Model." pith.science (2026). https://pith.science/paper/5N27DSSX

@misc{pith2026250514138,
  author       = {Pith},
  title        = {Pith review of: Sample Complexity of Correlation Detection in the Gaussian Wigner Model},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5N27DSSX}},
  note         = {Machine review of arXiv:2505.14138}
}
read the original abstract

Correlation analysis is a fundamental step in uncovering meaningful insights from complex datasets. In this paper, we study the problem of detecting correlations between two random graphs following the Gaussian Wigner model with unlabeled vertices. Specifically, the task is formulated as a hypothesis testing problem: under the null hypothesis, the two graphs are independent, while under the alternative hypothesis, they are edge-correlated through a latent vertex permutation, yet maintain the same marginal distributions as under the null. We focus on the scenario where two induced subgraphs, each with a fixed number of vertices, are sampled. We determine the optimal rate for the sample size required for correlation detection, derived through an analysis of the conditional second moment. Additionally, we propose an efficient approximate algorithm that significantly reduces running time.

Figures

Figures reproduced from arXiv: 2505.14138 by the authors.

Figure 1
Figure 1. The histogram of the approximate test statistic [PITH_FULL_IMAGE:figures/full_fig_p013_1.png] view at source ↗
Figure 2
Figure 2. Comparison for the ROC curve of the approximate test statistic for different sample size [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗
Figure 3
Figure 3. Comparison for the ROC curve of the approximate test statistic for different correlation [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 3 canonical work pages

  1. [3]

    Detecting correlation efficiently in stochastic block models: breaking otter’s threshold by counting decorated trees.arXiv preprint arXiv:2503.06464,

    [CDGL25] Guanyi Chen, Jian Ding, Shuyang Gong, and Zhangsong Li. Detecting correlation efficiently in stochastic block models: breaking otter’s threshold by counting decorated trees.arXiv preprint arXiv:2503.06464,

    arXiv

  2. [6]

    Efficiently matching random inhomo- geneous graphs via degree profiles.arXiv preprint arXiv:2310.10441,

    [DFW23] Jian Ding, Yumou Fei, and Yuanzheng Wang. Efficiently matching random inhomo- geneous graphs via degree profiles.arXiv preprint arXiv:2310.10441,

    arXiv

  3. [7]

    A polynomial-time iterative algorithm for random graph matching with non-vanishing correlation.arXiv preprint arXiv:2306.00266,

    [DL23] Jian Ding and Zhangsong Li. A polynomial-time iterative algorithm for random graph matching with non-vanishing correlation.arXiv preprint arXiv:2306.00266,

    arXiv

  4. [8]

    A survey and taxonomy of graph sampling.arXiv preprint arXiv:1308.5865,

    [HL13] Pili Hu and Wing Cheong Lau. A survey and taxonomy of graph sampling.arXiv preprint arXiv:1308.5865,

    arXiv

  5. [10]

    Faster algorithms for the alignment of sparse correlated Erd\"os-R\'enyi random graphs

    [MS24] Andrea Muratori and Guilhem Semerjian. Faster algorithms for the alignment of sparse correlated Erd˝ os-R´ enyi random graphs.arXiv preprint arXiv:2405.08421,

    work page Pith review arXiv

  6. [2007]

    A computational transi- tion for detecting correlated stochastic block models by low-degree polynomials.arXiv preprint arXiv:2409.00966,

    [CDGL24] Guanyi Chen, Jian Ding, Shuyang Gong, and Zhangsong Li. A computational transi- tion for detecting correlated stochastic block models by low-degree polynomials.arXiv preprint arXiv:2409.00966,

    arXiv

  7. [2011]

    Align- ing random graphs with a sub-tree similarity message-passing algorithm.Journal of Statistical Mechanics: Theory and Experiment, 2022(6):063401,

    [PSSZ22] Giovanni Piccioli, Guilhem Semerjian, Gabriele Sicuro, and Lenka Zdeborov´ a. Align- ing random graphs with a sub-tree similarity message-passing algorithm.Journal of Statistical Mechanics: Theory and Experiment, 2022(6):063401,

    2022

  8. [2016]

    Exact alignment recovery for correlated Erd˝ os- R´ enyi graphs.arXiv preprint arXiv:1711.06783,

    [CK17] Daniel Cullina and Negar Kiyavash. Exact alignment recovery for correlated Erd˝ os- R´ enyi graphs.arXiv preprint arXiv:1711.06783,

    arXiv

Show all 12 references
  1. [2018]

    Lexical semantic relatedness with random graph walks

    [HR07] Thad Hughes and Daniel Ramage. Lexical semantic relatedness with random graph walks. InProceedings of the 2007 joint conference on empirical methods in natural language processing and computational natural language learning (EMNLP-CoNLL), pages 581–589,

    2007

  2. [2023]

    Low-degree hardness of detection for corre- lated Erd˝ os-R´ enyi graphs.arXiv preprint arXiv:2311.15931,

    [DDL23] Jian Ding, Hang Du, and Zhangsong Li. Low-degree hardness of detection for corre- lated Erd˝ os-R´ enyi graphs.arXiv preprint arXiv:2311.15931,

  3. [2024]

    Detecting correlation between multiple unlabeled gaussian networks.arXiv preprint arXiv:2504.16279,

    [AH25] Taha Ameen and Bruce Hajek. Detecting correlation between multiple unlabeled gaussian networks.arXiv preprint arXiv:2504.16279,

    arXiv

  4. [2025]

    Optimal partial graph matching

    [RNW24] Gathika Ratnayaka, James Nichols, and Qing Wang. Optimal partial graph matching. arXiv preprint arXiv:2410.16718,

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.