Pith. sign in

REVIEW 1 major objections 3 minor 102 references

Optimal community detection in dense bipartite graphs

T0 review · 1 major / 3 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read This paper establishes that the minimax separation rate for detecting a planted $k_1\times k_2$ dense subgraph in an $n_1\times n_2$ bipartite Erdős-Rényi graph is, up to constants, $\sqrt{p_0(1-p_0)R}$, where $R$ is an explicit function…

desk verdict Strong interior result on minimax bipartite community detection, but the 'any configuration' claim has a real gap at k_i = n_i because the supplement's rate simplification collapses there. read the letter →

arxiv 2505.18372 v1 pith:XRC44CYD submitted 2025-05-23 math.ST stat.MLstat.TH

Julien Chhor , Parker Knight This is my paper · ORCID
classification math.STstat.MLstat.TH MSC 62G1062G2062C2005C80
keywords communitydetectionplanteddensesubgraphbipartitegraphminimaxseparationratehypothesistestingtruncatedchi-squaretestsecondmomentmethodErdős-Rényi
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

This paper claims to determine, up to multiplicative constants, the smallest signal strength $\delta^*$ at which a statistician can reliably detect a planted $k_1\times k_2$ dense subgraph in an $n_1\times n_2$ bipartite Erdős-Rényi graph. The claimed characterization is $(\delta^*)^2 \asymp p_0(1-p_0)R$, where $R$ is an explicit function of the four dimensions, and it is claimed to hold for all $n_1,n_2,k_1,k_2$ in the dense regime. The lower bound is unconditional; the upper bound holds under an explicit density assumption on $p_0$. If true, this fills a gap left by prior work, which covered only symmetric square graphs or constrained asymptotic regimes, and reveals new phase transitions specific to imbalanced bipartite settings.

What carries the argument

The central machinery is the minimax separation-rate framework together with a second-moment analysis of the likelihood ratio: the lower bound reduces the problem to controlling $\mathbb{E}[\exp(\mu^2XY)]$ for independent binomials $X,Y$, and the rate $R$ emerges from partitioning the support of $X$ into regimes. For the upper bound, the paper combines three tests—a total degree test, a truncated degree test, and a max truncated degree test—built on hard-thresholded statistics of the adjacency matrix in which the square of the classical truncated $\chi^2$ test is replaced by the Bennett function $h_B(x)=(1+x)\log(1+x)-x$ to tame the sub-Poissonian tails of binomial entries. The choice among the tests is dictated by which term dominates the rate $R$, and the max truncated degree test is shown to replace the scan test with lower complexity.

What would settle it

For a fixed configuration violating Assumption 1 (e.g., $n_1=n_2=2000$, $k_1=k_2=10$, $p_0=10^{-6}$), simulate the optimal Bayesian test via the Neyman-Pearson likelihood ratio over the uniform prior and estimate the minimax risk; if there exist $\delta$ values an order of magnitude below $\sqrt{p_0(1-p_0)R}$ for which the risk drops below $\eta$, the claimed separation rate all regime is refuted.

Watch

Extended reading notes

Core claim

The paper establishes that the minimax separation rate for the bipartite planted dense subgraph detection problem is $(\delta^*)^2 \asymp p_0(1-p_0) R$, with $R = (\psi_{12}+\psi_{21}) \wedge \phi_{12} \wedge \phi_{21}$, where $\psi,\beta,\phi$ are explicit functions of $n_1,n_2,k_1,k_2$. The lower bound holds for all parameter values, and the upper bound holds under Assumption 1, which requires $p_0\le 1/4$ and a lower bound on $p_0$ that prevents empty-community pathologies. The matching bounds hold for any configuration of $n_1,n_2,k_1,k_2$, including unbalanced regimes not covered by previous asymptotic results, and disclose a new phase transition at $n_1k_2/(k_1^2\log n_2)\asymp 1$ in the imbalanced case.

Load-bearing premise

The matching upper bound, and hence the full minimax characterization $(\delta^*)^2\asymp p_0(1-p_0)R$, holds only under Assumption 1, which requires the baseline edge probability $p_0$ to be at least about $(C_\eta/(k_1k_2))\log\left(e\binom{n_1}{k_1}\binom{n_2}{k_2}\right)$ in the max-truncated-degree regime and to satisfy $p_0\le 1/4$; if the graph is sparser, the stated rate may fail.

Editorial extensions

If this is right

  • For any $n_1,n_2,k_1,k_2$, the detection boundary for dense bipartite graphs is now characterized up to constants, extending earlier square-graph results.
  • In the balanced setting $n_1=n_2=n$, $k_1=k_2=k$ with $n\lesssim k^2$, the boundary refines previous asymptotic results by capturing the transition around $n/k^2\asymp 1$.
  • A new phase transition appears in imbalanced bipartite graphs at $n_1k_2/(k_1^2\log n_2)\asymp 1$, which was undocumented in prior community-detection literature.
  • The max truncated degree test achieves the optimal rate with lower complexity than scanning over all possible communities.
  • If the density assumption holds, the test achieves risk below $\eta$ as soon as $\delta^2\ge C_\delta p_0(1-p_0) R$ for a constant $C_\delta$ depending only on $\eta$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A natural conjecture, which the authors leave open, is that in the very sparse regime the same rate $R$ fails; the boundary may switch to a different function, likely requiring truncated second-moment techniques.
  • The truncated-degree statistics developed here could transfer to other Bernoulli or Poisson matrix testing problems, such as detecting planted dense blocks in count matrices, where Gaussian-based truncated $\chi^2$ tests are known to lose optimality.
  • If the detection rate is indeed sharp for all dimensions, the same $R$ function may control the difficulty of related tasks such as localization of the planted subgraph, since detection is a prerequisite for recovery.
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.

Referee Report

1 major / 3 minor

Summary. This paper studies the hypothesis testing problem of detecting a planted k1 x k2 bipartite subgraph with elevated connection probability p0+delta in an n1 x n2 bipartite Erdos-Renyi graph with null probability p0. The main results are a lower bound (Theorem 1), valid for all parameter values, and an upper bound (Theorem 2), valid under Assumption 1, which together claim the minimax separation rate satisfies delta*^2 asymptotically equal to p0(1-p0)R with R defined in (8). The upper bound is achieved by a combination of a total degree test, a truncated degree test, and a max truncated degree test, with the choice among them determined by the value of the auxiliary quantity tilde(R) in (9). The proofs are deferred to a long supplement.

Significance. If the claimed matching held, this would be a substantial contribution: it gives non-asymptotic sharp minimax rates for arbitrary aspect ratios and community sizes, including the under-explored unbalanced regimes, and it introduces new concentration tools for binomial truncated statistics that are likely to be useful elsewhere. The lower-bound proof via the second moment method is independent of the upper bound and does not rely on the density assumption, and that part appears robust. However, the upper-bound argument has a gap at the boundary of the allowed parameter set, so the central 'any configuration' claim is not yet established.

major comments (1)
  1. [Section 3.2 / Theorem 2, Lemma 17, Eqs. (5)-(9)] At the allowed configuration k1=n1 (and symmetrically k2=n2), the test-selection rule in Theorem 2 and the proof in Section B.4 break down. From definitions (5)-(9), when k1=n1 one has psi12=0 and beta21=0, so tilde(R)=0, while R>0 can still hold; for example n1=k1=1000, k2=10, n2=10^5, and p0=0.1 satisfy Assumption 1 (first case) and give R approximately (1/n1) log(1+n2/k2^2)>0. In this configuration the algorithm selects Delta_max-trunc-deg,1 because tilde(R)=psi12+beta21=0. Lemma 17, the only lemma used for this test, requires n2/k2^2 log(n1/k1)>c, which fails since log(n1/k1)=0; if one nevertheless follows the lemma's rate it collapses to 0, which would imply detectability for arbitrarily small delta, contradicting the lower bound delta*^2 >= c p0(1-p0)R from Theorem 1. Thus the proof of Theorem 2 does not cover an allowed boundary case, and the claim that the bounds match for any configuration is not supported. A fix requires either excluding k_i=n_i from the problem, proving a separate boundary case using a test whose assumptions do hold there, or revising the selection rule so that the max truncated degree test is invoked only when its assumptions are satisfied.
minor comments (3)
  1. [Section 1.3 and equations (5)-(7)] The definitions of psi, beta, and phi are typeset in a way that is hard to read, especially the indicator condition in (6); the main text should use a notation matching the supplement's (23)-(25) unambiguously.
  2. [Supplement B.4] The proof of Theorem 2 says 'By Lemma 14, we always have R >= tilde(R)'; this one-sided comparison does not by itself ensure that the threshold conditions of Lemmas 15-17 are implied by delta^2 >= C delta p0(1-p0) R, and the converse comparison is established in the supplement only under auxiliary restrictions such as k_j <= c' n_j. Please make the dependency explicit and check each case of the selection rule against the hypotheses of the invoked lemma.
  3. [Lemma 17] The assumption 'n2/k2^2 log(n1/k1) > c' with c >= 0 excludes the boundary case log(n1/k1)=0 even when c=0, because the inequality is strict; the text should state this exclusion and verify it in the proof of Theorem 2 before Lemma 17 is applied.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: rate R is parameter-derived and bounds are proven independently.

full rationale

The central rate R in (8) is a closed-form function of n1, n2, k1, k2 only; it is not fitted to data and does not presuppose the minimax separation rate. The lower bound (Theorem 1) is obtained by a second-moment argument over a uniform prior on planted bipartite subgraphs, and the upper bound (Theorem 2) is obtained by explicit tests (total degree, truncated degree, max truncated degree) whose analyses in Section B prove Type I and Type II error bounds independently of the lower bound. Although the tests are selected to match the rate R, the matching is proven through Lemmas 14-17 rather than imposed by definition. The paper proves its own tail bounds (Lemmas 15-21) and cites [18,19,20,41] only as background or as sources of concentration facts, not as load-bearing uniqueness theorems or as substitutes for the main argument. No fitted parameter is renamed as a prediction, and no assumption contains the target result. The boundary-gap concern raised by the reviewer (e.g., k1=n1) is a potential correctness issue about the validity of Lemma 17 at endpoints, not a circularity, and therefore does not affect the circularity score.

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

No free parameters are fitted to data; the constants C, c_delta, C_delta, and similar are universal and depend only on eta. Axioms are standard probability inequalities, the model's domain assumptions, and the dense-graph Assumption 1. No invented entities are introduced.

assumptions (7)
  • domain assumption Independent Bernoulli edge model under H0 and H1 with p1 >= p0 + delta.
    This is the statistical model defining the testing problem in Section 2. All results are relative to this model.
  • standard math Bennett's inequality and Bernstein's inequality for binomial tails.
    Used in Lemma 24 and other tail bounds in the supplement.
  • standard math Slud's inequality for binomial anti-concentration, Theorem 2.1 in reference [62].
    Invoked in Lemma 18 and Corollary 1 to lower bound binomial tail probabilities when p0 <= 1/4.
  • domain assumption Assumption 1: p0 bounded below by C_eta times log terms, and p0 <= 1/4.
    Imposes a dense graph; the upper bound Theorem 2 relies on it. The lower bound Theorem 1 does not.
  • domain assumption Knowledge of p0, k1, and k2 is available to the statistician.
    All three tests require these parameters; the paper notes adaptivity is future work in Section 5.
  • standard math Stirling approximation bounds for binomial coefficients, stated as Lemma 25.
    Used to control binomial probabilities in the upper bound proofs.
  • standard math Lemma 3 of Arias-Castro et al. [4] bounding hypergeometric couplings by independent binomials.
    Used in the lower bound proof to upper bound the second moment of the likelihood ratio by an independent binomial moment generating function.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Optimal community detection in dense bipartite graphs." pith.science (2026). https://pith.science/paper/XRC44CYD

@misc{pith2026250518372,
  author       = {Pith},
  title        = {Pith review of: Optimal community detection in dense bipartite graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XRC44CYD}},
  note         = {Machine review of arXiv:2505.18372}
}
abstract

We consider the problem of detecting a community of densely connected vertices in a high-dimensional bipartite graph of size $n_1 \times n_2$. Under the null hypothesis, the observed graph is drawn from a bipartite Erd\H{o}s-Renyi distribution with connection probability $p_0$. Under the alternative hypothesis, there exists an unknown bipartite subgraph of size $k_1 \times k_2$ in which edges appear with probability $p_1 = p_0 + \delta$ for some $\delta > 0$, while all other edges outside the subgraph appear with probability $p_0$. Specifically, we provide non-asymptotic upper and lower bounds on the smallest signal strength $\delta^*$ that is both necessary and sufficient to ensure the existence of a test with small enough type one and type two errors. We also derive novel minimax-optimal tests achieving these fundamental limits when the underlying graph is sufficiently dense. Our proposed tests involve a combination of hard-thresholded nonlinear statistics of the adjacency matrix, the analysis of which may be of independent interest. In contrast with previous work, our non-asymptotic upper and lower bounds match for any configuration of $n_1,n_2, k_1,k_2$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

102 extracted references · 73 canonical work pages

  1. [1]

    Community detection and stochastic block models: recent developments

    Emmanuel Abbe. “Community detection and stochastic block models: recent developments”. In:Journal of Machine Learning Research18.177 (2018), pp. 1–86

    2018

  2. [2]

    Community detection in general stochastic block models: Fun- damental limits and efficient algorithms for recovery

    Emmanuel Abbe and Colin Sandon. “Community detection in general stochastic block models: Fun- damental limits and efficient algorithms for recovery”. In:2015 IEEE 56th Annual Symposium on Foundations of Computer Science. IEEE. 2015, pp. 670–688

    2015

  3. [3]

    Statistical mechanics of complex networks

    Réka Albert and Albert-László Barabási. “Statistical mechanics of complex networks”. In:Reviews of modern physics74.1 (2002), p. 47

    2002

  4. [4]

    GLOBAL TESTING UNDER SPARSE ALTERNATIVES: ANOVA, MULTIPLE COMPARISONS AND THE HIGHER CRITICISM

    Ery Arias-Castro, Emmanuel J Candès, and Yaniv Plan. “GLOBAL TESTING UNDER SPARSE ALTERNATIVES: ANOVA, MULTIPLE COMPARISONS AND THE HIGHER CRITICISM”. In:The Annals of Statistics(2011), pp. 2533–2556

    2011

  5. [5]

    Community detection in dense random networks

    Ery Arias-Castro and Nicolas Verzelen. “Community detection in dense random networks”. In: (2014)

    2014

  6. [6]

    The sparse Poisson means model

    Ery Arias-Castro and Meng Wang. “The sparse Poisson means model”. In: (2015). 13

    2015

  7. [7]

    Contiguity and non-reconstruction results for planted partition models: the dense case

    Debapratim Banerjee. “Contiguity and non-reconstruction results for planted partition models: the dense case”. In:Electronic Journal of Probability(2018)

    2018

  8. [8]

    Optimal hypothesis testing for stochastic block models with growing degrees

    Debapratim Banerjee and Zongming Ma. “Optimal hypothesis testing for stochastic block models with growing degrees”. In:arXiv preprint arXiv:1705.05305(2017)

    arXiv 2017

Show all 102 references
  1. [9]

    Information-theoretic thresholds for community detection in sparse networks

    Jess Banks et al. “Information-theoretic thresholds for community detection in sparse networks”. In: Conference on Learning Theory. PMLR. 2016, pp. 383–416

    2016

  2. [10]

    Network biology: understanding the cell’s functional organization

    Albert-Laszlo Barabasi and Zoltan N Oltvai. “Network biology: understanding the cell’s functional organization”. In:Nature reviews genetics5.2 (2004), pp. 101–113

    2004

  3. [11]

    Non-asymptotic minimax rates of testing in signal detection

    Yannick Baraud. “Non-asymptotic minimax rates of testing in signal detection”. In: (2002)

    2002

  4. [12]

    Optimal detection of sparse principal components in high dimension

    Quentin Berthet and Philippe Rigollet. “Optimal detection of sparse principal components in high dimension”. In:Annals of Statistics(2013)

    2013

  5. [13]

    Reducibility and computational lower bounds for problems with planted sparse structure

    Matthew Brennan, Guy Bresler, and Wasim Huleihel. “Reducibility and computational lower bounds for problems with planted sparse structure”. In:Conference On Learning Theory. PMLR. 2018, pp. 48–166

    2018

  6. [14]

    Phase transitions for detecting latent geometry in random graphs

    Matthew Brennan, Guy Bresler, and Dheeraj Nagaraj. “Phase transitions for detecting latent geometry in random graphs”. In:Probability Theory and Related Fields178.3 (2020), pp. 1215–1289

    2020

  7. [15]

    Testing for high-dimensional geometry in random graphs

    Sébastien Bubeck et al. “Testing for high-dimensional geometry in random graphs”. In:Random Structures & Algorithms49.3 (2016), pp. 503–532

    2016

  8. [16]

    Detection of a sparse submatrix of a high-dimensional noisy matrix

    Cristina Butucea and Yuri I Ingster. “Detection of a sparse submatrix of a high-dimensional noisy matrix”. In:Bernoulli (2013)

    2013

  9. [17]

    Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices

    Yudong Chen and Jiaming Xu. “Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices”. In:Journal of Machine Learning Research17.27 (2016), pp. 1–57

    2016

  10. [18]

    Goodness-of-fit testing for Hölder-continuous densities: Sharp local minimax rates

    Julien Chhor and Alexandra Carpentier. “Goodness-of-fit testing for Hölder-continuous densities: Sharp local minimax rates”. In:Bernoulli (2025)

    2025

  11. [19]

    Sharp local minimax rates for goodness-of-fit testing in multivariate binomial and Poisson families and in multinomials

    Julien Chhor and Alexandra Carpentier. “Sharp local minimax rates for goodness-of-fit testing in multivariate binomial and Poisson families and in multinomials.” In:Mathematical Statistics & Learning 5 (2022)

    2022

  12. [20]

    Sparse signal detection in heteroscedastic Gaussian sequence models: sharp minimax rates

    Julien Chhor, Rajarshi Mukherjee, and Subhabrata Sen. “Sparse signal detection in heteroscedastic Gaussian sequence models: sharp minimax rates”. In:Bernoulli 30.3 (2024), pp. 2127–2153

    2024

  13. [21]

    Graph partitioning via adaptive spectral techniques

    Amin Coja-Oghlan. “Graph partitioning via adaptive spectral techniques”. In:Combinatorics, Probability and Computing19.2 (2010), pp. 227–284

    2010

  14. [22]

    Minimax estimation of linear and quadratic functionals on sparsity classes

    Olivier Collier, Laëtitia Comminges, and Alexandre B Tsybakov. “Minimax estimation of linear and quadratic functionals on sparsity classes”. In: (2017). 14

    2017

  15. [23]

    Detection and recovery of hidden submatrices

    Marom Dadon, Wasim Huleihel, and Tamir Bendory. “Detection and recovery of hidden submatrices”. In: IEEE Transactions on Signal and Information Processing over Networks10 (2024), pp. 69–82

    2024

  16. [24]

    Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications

    Aurelien Decelle et al. “Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications”. In:Physical Review E—Statistical, Nonlinear, and Soft Matter Physics84.6 (2011), p. 066106

    2011

  17. [25]

    Community detection in complex networks: From statistical foundations to data science applications

    Asim K Dey, Yahui Tian, and Yulia R Gel. “Community detection in complex networks: From statistical foundations to data science applications”. In:Wiley Interdisciplinary Reviews: Computational Statistics 14.2 (2022), e1566

    2022

  18. [26]

    Random geometric graph: Some recent developments and perspectives

    Quentin Duchemin and Yohann De Castro. “Random geometric graph: Some recent developments and perspectives”. In:High Dimensional Probability IX: The Ethereal Volume(2023), pp. 347–392

    2023

  19. [27]

    Detecting Arbitrary Planted Subgraphs in Random Graphs

    Dor Elimelech and Wasim Huleihel. “Detecting Arbitrary Planted Subgraphs in Random Graphs”. In: arXiv preprint arXiv:2503.19069(2025)

    2025 arXiv

  20. [28]

    20 years of network community detection

    Santo Fortunato and Mark EJ Newman. “20 years of network community detection”. In:Nature Physics 18.8 (2022), pp. 848–850

    2022

  21. [29]

    Testing network structure using relations between small subgraph probabilities

    Chao Gao and John Lafferty. “Testing network structure using relations between small subgraph probabilities”. In:arXiv preprint arXiv:1704.06742(2017)

    2017 arXiv

  22. [30]

    Community detection in degree-corrected block models

    Chao Gao et al. “Community detection in degree-corrected block models”. In:The Annals of Statistics 46.5 (2018), pp. 2153–2185

    2018

  23. [31]

    Community structure in social and biological networks

    Michelle Girvan and Mark EJ Newman. “Community structure in social and biological networks”. In: Proceedings of the national academy of sciences99.12 (2002), pp. 7821–7826

    2002

  24. [32]

    Computational lower bounds for community detection on random graphs

    Bruce Hajek, Yihong Wu, and Jiaming Xu. “Computational lower bounds for community detection on random graphs”. In:Conference on Learning Theory. PMLR. 2015, pp. 899–928

    2015

  25. [33]

    Information limits for recovering a hidden community

    Bruce Hajek, Yihong Wu, and Jiaming Xu. “Information limits for recovering a hidden community”. In: IEEE Transactions on Information Theory63.8 (2017), pp. 4729–4745

    2017

  26. [34]

    The smallest uniform upper bound on the distance between the mean and the median of the binomial and Poisson distributions

    Kais Hamza. “The smallest uniform upper bound on the distance between the mean and the median of the binomial and Poisson distributions”. In:Statistics & Probability Letters23.1 (1995), pp. 21–25. issn: 0167-7152. doi: https://doi.org/10.1016/0167-7152(94)00090-U

    1995 doi

  27. [35]

    Random subgraph detection using queries

    Wasim Huleihel, Arya Mazumdar, and Soumyabrata Pal. “Random subgraph detection using queries”. In: Journal of Machine Learning Research25.126 (2024), pp. 1–25

    2024

  28. [36]

    Minimax testing of nonparametric hypotheses on a distribution density in the L_p metrics

    Yu I Ingster. “Minimax testing of nonparametric hypotheses on a distribution density in the L_p metrics”. In:Theory of Probability & Its Applications31.2 (1987), pp. 333–337

    1987

  29. [37]

    Yuri Ingster and Irina A Suslina.Nonparametric goodness-of-fit testing under Gaussian models. Vol. 169. Springer Science & Business Media, 2012. 15

    2012

  30. [38]

    Detection boundary in sparse regression

    Yuri I Ingster, Alexandre B Tsybakov, and Nicolas Verzelen. “Detection boundary in sparse regression”. In: (2010)

    2010

  31. [39]

    On the minimax nonparametric detection of signals in white gaussian noise

    Yuri Izmailovich Ingster. “On the minimax nonparametric detection of signals in white gaussian noise”. In: Problemy Peredachi Informatsii18.2 (1982), pp. 61–73

    1982

  32. [40]

    Asymptotic equivalence and contiguity of some random graphs

    Svante Janson. “Asymptotic equivalence and contiguity of some random graphs”. In:Random Structures & Algorithms36.1 (2010), pp. 26–45

    2010

  33. [41]

    Locally sharp goodness-of-fit testing in sup norm for high-dimensional counts

    Subhodh Kotekal, Julien Chhor, and Chao Gao. “Locally sharp goodness-of-fit testing in sup norm for high-dimensional counts”. In:arXiv preprint arXiv:2409.08871(2024)

    2024 arXiv

  34. [42]

    Minimax rates for sparse signal detection under correlation

    Subhodh Kotekal and Chao Gao. “Minimax rates for sparse signal detection under correlation”. In: Information and Inference: A Journal of the IMA12.4 (2023), pp. 2873–2969

    2023

  35. [43]

    Sparsity meets correlation in Gaussian sequence model

    Subhodh Kotekal and Chao Gao. “Sparsity meets correlation in Gaussian sequence model”. In:arXiv preprint arXiv:2312.09356 (2023)

    2023 arXiv

  36. [44]

    Convergence of estimates under dimensionality restrictions

    Lucien LeCam. “Convergence of estimates under dimensionality restrictions”. In:The Annals of Statistics (1973), pp. 38–53

    1973

  37. [45]

    Minimax rates in sparse, high-dimensional change point detection

    Haoyang Liu, Chao Gao, and Richard J. Samworth. “Minimax rates in sparse, high-dimensional change point detection”. In:The Annals of Statistics49.2 (2021), pp. 1081–1112.doi: 10.1214/20-AOS1994

    2021 doi

  38. [46]

    Phase transition in noisy high-dimensional random geometric graphs

    Suqi Liu and Miklós Z Rácz. “Phase transition in noisy high-dimensional random geometric graphs”. In: Electronic Journal of Statistics17.2 (2023), pp. 3512–3574

    2023

  39. [47]

    Tensor clustering with planted structures: Statistical optimality and computational limits

    Yuetian Luo and Anru R Zhang. “Tensor clustering with planted structures: Statistical optimality and computational limits”. In:The Annals of Statistics50.1 (2022), pp. 584–613

    2022

  40. [48]

    COMPUTATIONAL BARRIERS IN MINIMAX SUBMATRIX DETECTION

    Zongming Ma and Yihong Wu. “COMPUTATIONAL BARRIERS IN MINIMAX SUBMATRIX DETECTION”. In:The Annals of Statistics(2015), pp. 1089–1116

    2015

  41. [49]

    Bipartite graphs and recommendation systems

    Cristina Maier and Dan Simovici. “Bipartite graphs and recommendation systems”. In:Journal of Advances in Information Technology-in print(2022)

    2022

  42. [50]

    Community detection thresholds and the weak Ramanujan property

    Laurent Massoulié. “Community detection thresholds and the weak Ramanujan property”. In:Proceed- ings of the forty-sixth annual ACM symposium on Theory of computing. 2014, pp. 694–703

    2014

  43. [51]

    A proof of the block model threshold conjecture

    Elchanan Mossel, Joe Neeman, and Allan Sly. “A proof of the block model threshold conjecture”. In: Combinatorica 38.3 (2018), pp. 665–708

    2018

  44. [52]

    Belief propagation, robust reconstruction and optimal recovery of block models

    Elchanan Mossel, Joe Neeman, and Allan Sly. “Belief propagation, robust reconstruction and optimal recovery of block models”. In:Conference on Learning Theory. PMLR. 2014, pp. 356–370

    2014

  45. [53]

    Reconstruction and estimation in the planted partition model

    Elchanan Mossel, Joe Neeman, and Allan Sly. “Reconstruction and estimation in the planted partition model”. In:Probability Theory and Related Fields162 (2015), pp. 431–461. 16

    2015

  46. [54]

    Weak recovery, hypothesis testing, and mutual information in stochastic block models and planted factor graphs

    Elchanan Mossel, Allan Sly, and Youngtak Sohn. “Weak recovery, hypothesis testing, and mutual information in stochastic block models and planted factor graphs”. In:arXiv preprint arXiv:2406.15957 (2024)

    2024 arXiv

  47. [55]

    Uncovering the overlapping community structure of complex networks in nature and society

    Gergely Palla et al. “Uncovering the overlapping community structure of complex networks in nature and society”. In:Nature 435.7043 (2005), pp. 814–818

    2005

  48. [56]

    Bipartite graphs in systems biology and medicine: a survey of methods and applications

    Georgios A Pavlopoulos et al. “Bipartite graphs in systems biology and medicine: a survey of methods and applications”. In:GigaScience 7.4 (2018), giy014

    2018

  49. [57]

    Bipartite graphs as models of population structures in evolutionary multiplayer games

    Jorge Pena and Yannick Rochat. “Bipartite graphs as models of population structures in evolutionary multiplayer games”. In: (2012)

    2012

  50. [58]

    High-dimensionalstatistics

    PhilippeRigolletandJan-ChristianHütter.“High-dimensionalstatistics”.In: arXiv preprint arXiv:2310.19244 (2023)

    2023 arXiv

  51. [59]

    Modern discrete probability: An essential toolkit

    Sebastien Roch. Modern discrete probability: An essential toolkit. Cambridge University Press, 2024

    2024

  52. [60]

    Maps of random walks on complex networks reveal community structure

    Martin Rosvall and Carl T Bergstrom. “Maps of random walks on complex networks reveal community structure”. In:Proceedings of the national academy of sciences105.4 (2008), pp. 1118–1123

    2008

  53. [61]

    Planted Bipartite Graph Detection

    Asaf Rotenberg, Wasim Huleihel, and Ofer Shayevitz. “Planted Bipartite Graph Detection”. In:IEEE Transactions on Information Theory(2024)

    2024

  54. [62]

    Distribution inequalities for the binomial law

    Eric V Slud. “Distribution inequalities for the binomial law”. In:The Annals of Probability5.3 (1977), pp. 404–412

    1977

  55. [63]

    Community detection in sparse random networks

    Nicolas Verzelen and Ery Arias-Castro. “Community detection in sparse random networks”. In: (2015)

    2015

  56. [64]

    Statistical problems with planted structures: Information-theoretical and computational limits

    Yihong Wu and Jiaming Xu. “Statistical problems with planted structures: Information-theoretical and computational limits”. In:arXiv preprint arXiv:1806.00118(2018)

    2018 arXiv

  57. [65]

    Sharp detection boundaries on testing dense subhypergraph

    Mingao Yuan and Zuofeng Shang. “Sharp detection boundaries on testing dense subhypergraph”. In: Bernoulli 28.4 (2022), pp. 2459–2491

    2022

  58. [66]

    Testing community structure for hypergraphs

    Mingao Yuan et al. “Testing community structure for hypergraphs”. In:The Annals of Statistics50.1 (2022), pp. 147–169. 17 A Proofs for lower bound A.1 Proof of Theorem 1 In this section, we prove the lower bound on the minimax rate of separationδ∗. Our general strategy is to l...

    2022

  59. [67]

    In thegeneral sparsitysetting, meaning thatk1≤c1n1 and k2≤c2n2 for sufficiently small constants c1,c 2 > 0, we show that there exists a constantcµ > 0 such that ifµ2≤cµR, then (20) holds. The proof of this claim constitutes the primary technical difficulty of the derivation of...

  60. [68]

    In this case, the problem roughly reduces to the sparse signal detection 20 problem in a standard Gaussian sequence model

    Otherwise, we place ourselves in thevery dense setting and assume without loss of generality that k1≥cn1 for a constantc∈ (0, 1). In this case, the problem roughly reduces to the sparse signal detection 20 problem in a standard Gaussian sequence model. In Section A.3, we prove...

  61. [69]

    Then if µ2 <C−1 ∗ n1 k2 1 log ( cn2 k2 ) + cµ k2 log (C∗ 2e ) , it holds E [ exp(µ2XY )1 ( X≥⌈C∗ k2 1 n1 ⌉ )] <α

    Suppose thatc−1 µ k2 log ( cn2 k2 ) ≤C∗ k2 1 n1 . Then if µ2 <C−1 ∗ n1 k2 1 log ( cn2 k2 ) + cµ k2 log (C∗ 2e ) , it holds E [ exp(µ2XY )1 ( X≥⌈C∗ k2 1 n1 ⌉ )] <α

  62. [70]

    Then if µ2 < cµ k2 log (k2n1 log(cn2 k2 ) cµ2ek2 1 ) , it holds E [ exp(µ2XY )1 ( X≥⌈C∗ k2 1 n1 ⌉ )] <α

    Suppose thatC∗ k2 1 n1 <c−1 µ k2 log ( cn2 k2 ) ≤k1. Then if µ2 < cµ k2 log (k2n1 log(cn2 k2 ) cµ2ek2 1 ) , it holds E [ exp(µ2XY )1 ( X≥⌈C∗ k2 1 n1 ⌉ )] <α

  63. [71]

    Suppose thatk1 <c−1 µ k2 log ( cn2 k2 ) .Then if µ2 < 1 k1 log ( cn2 k2 ) + cµ k2 log (n1 2ek1 ) , it holds E [ exp(µ2XY )1 ( X≥⌈C∗ k2 1 n1 ⌉ )] <α. Proof. DefineA ={⌈C∗ k2 1 n1 ⌉,...,k 1} and g as in (22). Fork∈A , it holds cµk k2 log (kn1 2ek2 1 ) ≥ cµC∗k2 1 k2n1 log (C∗ 2e ...

  64. [72]

    Thenf is increasing overA, and by our assumption onµ2, it holds µ2 <C−1 ∗ n1 k2 1 log ( cn2 k2 ) + cµ k2 log (C∗ 2e ) ≤ min k∈A f(k) ≤ min k∈A g(k)

    Suppose thatc−1 µ k2 log ( cn2 k2 ) ≤C∗ k2 1 n1 . Thenf is increasing overA, and by our assumption onµ2, it holds µ2 <C−1 ∗ n1 k2 1 log ( cn2 k2 ) + cµ k2 log (C∗ 2e ) ≤ min k∈A f(k) ≤ min k∈A g(k)

  65. [73]

    Then by our assumption onµ2, we have µ2 < cµ k2 log (k2n1 log(cn2 k2 ) cµ2ek2 1 ) ≤ min k∈A f(k) ≤ min k∈A g(k)

    Suppose thatC∗ k2 1 n1 <c−1 µ k2 log ( cn2 k2 ) ≤k1. Then by our assumption onµ2, we have µ2 < cµ k2 log (k2n1 log(cn2 k2 ) cµ2ek2 1 ) ≤ min k∈A f(k) ≤ min k∈A g(k)

  66. [74]

    Thenf is decreasing overA and is minimized atk =k1

    Suppose thatk1 <c−1 µ k2 log ( cn2 k2 ) . Thenf is decreasing overA and is minimized atk =k1. Therefore by our assumption onµ2, we have µ2 < 1 k1 log ( cn2 k2 ) + cµ k2 log (n1 2ek1 ) = min k∈A f(k) ≤ min k∈A g(k). 33 By Lemma 2, the proof is complete. A.4.1 Simplification of ...

  67. [75]

    Then the following two properties hold ( ψ12 +ψ21 ) ∧ϕ12≍ψ21∧ϕ12 (26) ψ21∧ϕ12≍ ( ψ21 +β12 ) ∧ϕ12. (27)

  68. [76]

    It follows that, for anyα> 0, there exists a constantcµ > 0 such that, wheneverµ2≤cµR, we have E [ exp(µ2XY ) 1 ( X≥C∗ k2 1 n1 )] <α

  69. [77]

    34 Proof of Lemma 8

    Moreover, it holds thatR≍ ( ψ21 +β12 ) ∧ ( ψ12 +β21 ) ∧ϕ12∧ϕ21. 34 Proof of Lemma 8

  70. [78]

    We start by showing that ψ21∧ϕ12≍ψ21∧~ϕ12

    For anyk1,k 2,n 1,n 2, we let ~ϕ12 = n1 k2 1 log ( 1 +n2 k2 2 ) . We start by showing that ψ21∧ϕ12≍ψ21∧~ϕ12. This is clear ifn1 k2 1 ≤ 1 by definition ofϕ12. Assume now thatn1 k2 1 > 1, which implies thatϕ12 =∞ and ψ21∧ϕ12 =ψ21. By the assumptionk2 1≥ ¯cn1k2, we obtaink2≤ k2 1...

  71. [79]

    Assume first thatc−1 µ k2 log ( cn2 k2 ) ≤ C∗ k2 1 n1

    Now, letα> 0 and letcµ,c> 0 be the constants defined in Lemma 7. Assume first thatc−1 µ k2 log ( cn2 k2 ) ≤ C∗ k2 1 n1 . Recalling that n2 k2 ≥ 1 c′ where c′ can be taken arbitrarily small, we have R≤ϕ12 = n1 k2 1 log ( 1 +n2 k2 2 ) ≤ n1 k2 1 log ( 2n2 k2 ) providedc′ is small...

  72. [80]

    We now prove the converse bound

    We immediately deduce from(26) that R ≳ ( ψ21 +β12 ) ∧ ( ψ12 +β21 ) ∧ϕ12∧ϕ21. We now prove the converse bound. Note that ifn2k1 k2 2 log ( n1 k1 ) ≤ 1, then we haveβ21 = 0 and ψ12 +β21 =ψ12 ≲ϕ21 by Lemma 13 and the result follows. We assume thatn2k1 k2 2 log ( n1 k1 ) > 1 from...

  73. [81]

    Hence, for any α> 0, there exists a constantc′ µ > 0 such that, wheneverµ2≤c′ µR, we have E [ exp(µ2XY )1 ( 1∨C∗ k2 1 n1 ≤X≤k1∧ k2 log (n1k2 k2 1 ) )] <α

    Then for some sufficiently small constantc> 0 depending only onµ, it holds thatM≥cR. Hence, for any α> 0, there exists a constantc′ µ > 0 such that, wheneverµ2≤c′ µR, we have E [ exp(µ2XY )1 ( 1∨C∗ k2 1 n1 ≤X≤k1∧ k2 log (n1k2 k2 1 ) )] <α

  74. [82]

    Moreover, we have R≥    1 2(ψ12 +β21)∧ϕ12∧ϕ21 if k1≤ k2 log ( n1k2 k2 1 ) 1 2(ψ21 +β12)∧ϕ12∧ϕ21 otherwise. (30) 38

  75. [83]

    Proof of Lemma 9

    Moreover, it holds thatR≍ ( ψ21 +β12 ) ∧ ( ψ12 +β21 ) ∧ϕ12∧ϕ21. Proof of Lemma 9

  76. [84]

    We start by showing thatM≥c(ψ21 +ψ12). Using Lemma 4 and Lemma 31.(i), we obtain 2M≥ 1 k1 log ( 1 +cµ n2k1 k2 2 log( n1 2ek1 ) ) + log (n1k2 k2 1 ) k2 log ( 1 +cµ n2 k2 log (n1k2 k2 1 )log ( n1k2 2ek2 1 log(n1k2 k2 1 ) )) ≥ cµ k1 log ( 1 +n2k1 k2 2 log( n1 2ek1 ) ) +cµ log (n1...

  77. [85]

    Assume first thatk1≤ k2 log ( n1k2 k2 1 )

    We now prove equation (30). Assume first thatk1≤ k2 log ( n1k2 k2 1 ). Then we obtain n1 k1 ≤ n1k2 k2 1 log (n1k2 k2 1 ), hence n1k2 k2 1 ≥ n1 k1 log (n1 k1 ) , i.e. 1 k1 ≥ 1 k2 log (n1 k1 ) (32) 39 by Lemma 30.(ii). Note that, sincen2k1 k2 2 ≥ n1 k1 ≥ 1 c′ can be made arbitra...

  78. [86]

    We aim to prove thatψ21 +β12 ≳ ψ12 +β21

    Assume thatk1≤ k2 log ( n1k2 k2 1 ), which impliesk2≥k1 log ( n1 k1 ) by (32). We aim to prove thatψ21 +β12 ≳ ψ12 +β21. We have ψ12 = 1 k1 log ( 1 +n2k1 k2 2 log (n1 k1 )) ≤ 1 k1 log ( 1 +n2 k2 ) ≲β12. Moreover, ψ21 = 1 k2 log ( 1 +n1k2 k2 1 log (n2 k2 )) The lemma below shows...

  79. [87]

    Then for anyα> 0, there exist constantscµ > 0 and C∗≥ 1 such that if1∨ ⌈ C∗ k2 1 n1 ⌉ ∨ ⌈ C∗k2 2/n2 log (n1k2 2 k2 1n2 ) ⌉ ≤ k1∧ ⌊ k2 log ( n1k2 k2 1 )⌋ and µ2≤cµR, E [ exp(µ2XY )1 ( C∗ k2 1 n1 ∨ C∗k2 2/n2 log (n1k2 2 k2 1n2 )≤X≤k1∧ k2 log (n1k2 k2 1 ) )] <α

  80. [88]

    Consequently, we haveR≥ ( ψ21 +β12 ) ∧ ( ψ12 +β21 ) ∧ϕ12∧ϕ21

    Moreover, we have R≥    ( ψ21 +β12 ) ∧ϕ12∧ϕ21 if k2≤k1 log ( n1 k1 ) ( ψ12 +β21 ) ∧ϕ12∧ϕ21 otherwise. Consequently, we haveR≥ ( ψ21 +β12 ) ∧ ( ψ12 +β21 ) ∧ϕ12∧ϕ21. 41 Proof of Lemma 11

  81. [89]

    By the assumptionn1k2 k2 1 ≥ ¯c−1≥ 16e4, we can repeat the steps leading to equation (31) to obtain log (n1k2 k2 1 ) k2 log ( 1 +cµ n2 k2 log (n1k2 k2 1 )log ( n1k2 2ek2 1 log(n1k2 k2 1 ) )) ≥ cµ 4 log ( 1 + n1k2 k2 1 log (n2 k2 )) k2 = cµ 4 ψ21. It immediately follows that, f...

  82. [90]

    Then we have ψ12 = 1 k1 log ( 1 +n2k1 k2 2 log (n1 k1 )) ≥ 1 k1 log ( 1 +n2 k2 ) ≥β12, which yields the desired result

    Assume now thatk2≤k1 log ( n1 k1 ) . Then we have ψ12 = 1 k1 log ( 1 +n2k1 k2 2 log (n1 k1 )) ≥ 1 k1 log ( 1 +n2 k2 ) ≥β12, which yields the desired result. Assume now thatk2 >k 1 log ( n1 k1 ) . Then ψ21 = 1 k2 log ( 1 +n1k2 k2 1 log (n2 k2 )) > 1 k2 log (n1 k1 log (n1 k1 ) l...

  83. [91]

    Then for anyα4 > 0, there exist constantscµ > 0 and C∗≥ 1 such that ifµ2≤cµR, then E [ exp(µ2XY )1 ( X≥ k2 log (n1k2 k2 1 )∨C∗ k2 1 n1 ⌉)] <α 4. 42

  84. [92]

    Consequently, we haveR≥ ( ψ21 +β12 ) ∧ ( ψ12 +β21 ) ∧ϕ12∧ϕ21

    Moreover, it holds that R≥    1 4 ( (ψ21 +β12) + (ψ12 +β21) ) ∧ϕ12∧ϕ21 if k1≤k2 log ( n2 k2 ) 1 2 ( ψ21 +β12 ) ∧ϕ12∧ϕ21 otherwise. Consequently, we haveR≥ ( ψ21 +β12 ) ∧ ( ψ12 +β21 ) ∧ϕ12∧ϕ21. Proof of Lemma 12

  85. [93]

    Note that the relationk2 <k 1 log ( (n1k2)/k2 1 ) implies that n1k2 k2 1 < n1 k1 log (n1k2 k2 1 ) ≤ 2n1 k1 log (2n1 k1 ) by Lemma 30.(i) which yields k2≤ 4k1 log(n1/k1). (33) Now, we obtain n2k1 k2 2 log (n1 k1 ) = n2 k2 · k1 k2 log (n1 k1 ) ≥ 1 4c′≥ 1 providedc′≤ 1/4, and n1k...

  86. [94]

    Assume first thatk1 <k 2 log ( n2 k2 ) . Then we have ψ12 +ψ21 = 1 k1 log ( 1 +n2k1 k2 2 log (n1 k1 )) + 1 k2 log ( 1 +n1k2 k2 1 log (n2 k2 )) ≥ 1 k1 log ( 1 + n2 4k2 ) + 1 k2 log (n1k2 k2 1 log (n2 k2 )) > 1 4k1 log ( 1 +n2 k2 ) + 1 k2 log (n1 k1 ) ≥ 1 4 ( β12 +β21 ) , which ...

  87. [95]

    Similarly, if˜R =ϕ21 and n1 >k 2 1, the result follows by Lemma 16

    Then the result follows by Lemma 16. Similarly, if˜R =ϕ21 and n1 >k 2 1, the result follows by Lemma 16. Finally, if none of the conditions above are satisfied, then we have ∆∗ = ∆h2 deg and the result follows by Lemma 15. The proof is complete. C Additional results C.1 Techni...

  88. [96]

    Then for anyk∈{ 1,...,n}, we have Pr(X =k)≤ (2enp k )k exp ( −np ) Proof. Using the bound (n k ) ≤ (ne k )k (Appendix A in [59]), we have Pr(X =k) = (n k ) pk( 1−p )n−k ≤ (npe k )k( 1−p )n−k = (npe k )k( 1−p )n( 1−p )−k ≤ (npe k )k( 1−p )n( 1/2 )−k = (2enp k )k( 1−p )n ≤ (2enp...

  89. [97]

    We havew(x)≤ (x−np0)2 σ2 whereσ2 =np0(1−p0)

  90. [98]

    There exists a universal constantc0 > 0 such that, for anyx∈ [np0,np 0+c0σ2], we havew(x)≥ (x−np0)2 8σ2

  91. [99]

    Proof of Lemma 32

    For anyx∈ [c0σ2,n ], we havew(x)≍σx−np0 σ log ( 1 + x−np0 σ2 ) . Proof of Lemma 32

  92. [100]

    Using the inequalitylog(1 +x)≤x that holds for anyx∈ [−1,∞) with the conventionlog(0) =−∞, we have, for anyx∈ [0,n ] w(x) =n(1−p0)hB ( − x−np0 n(1−p0) ) +np0hB (x−np0 np0 ) =n(1−p0) {( 1− x−np0 n(1−p0) ) log ( 1− x−np0 n(1−p0) ) + x−np0 n(1−p0) } +np0 {( 1 +x−np0 np0 ) log ( 1...

  93. [101]

    For any x ∈ [np0,np 0 + cσ2], we have x−np0 np0 ∨ x−np0 n(1−p0) ∈ [0,c ]. Choosing c small enough that 81 log(1 +t)≥t− 3t2 4 for anyt∈ [−c,c ], we obtain that, w(x) =n(1−p0)hB ( − x−np0 n(1−p0) ) +np0hB (x−np0 np0 ) =n(1−p0) {( 1− x−np0 n(1−p0) ) log ( 1− x−np0 n(1−p0) ) + x−n...

  94. [102]

    We have n(1−p0)hB ( − x−np0 n(1−p0) ) =n(1−p0) {( 1− x−np0 n(1−p0) ) log ( 1− x−np0 n(1−p0) ) + x−np0 n(1−p0) } ∈ [ 0,x−np0 ]

    Assume now thatx∈ [np0 +c0σ2,n ]. We have n(1−p0)hB ( − x−np0 n(1−p0) ) =n(1−p0) {( 1− x−np0 n(1−p0) ) log ( 1− x−np0 n(1−p0) ) + x−np0 n(1−p0) } ∈ [ 0,x−np0 ] . Moreover, using the relationhB(y)≍y log(1 +y) that holds for anyy >0, we have np0hB (x−np0 np0 ) ≍ (x−np0) log ( x ...

Pith tools

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