Optimal community detection in dense bipartite graphs
Authors: Julien Chhor
Parker Knight
Venue: NeurIPS 2025 poster ()
Keywords: bipartite random graphs
minimax hypothesis testing
signal detection
Primary area: theory
TL;DR: We present new tests for detecting a community in a random bipartite graph and prove that they are minimax optimal.

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 Erdos-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$.

Optimal community detection in dense bipartite graphs
Julien Chhor*
Parker Knight
Department of Mathematics and Statistics Department of Biostatistics
Toulouse School of Economics
Harvard University Boston, MA, USA pknight@g.
Toulouse, France julien. chhor@tse-fr.ee
Beriigh@t..harar..... hwwvarrr edu
Abstract
We consider the problem of detecting community of densely connected vertices in a nigh-dimensional bipartite graph of size n, x R22. Under the null hypothesis, the observed graph is drawn from bipartite Erdōs-Renyi distribution with connection probability po- Under the alternative hypothesis, there exists an unknown bipartite subgraph of size kn h2 in which edges appear with probability pi Po + for some >> 0, while all other edges outside the subgraph appear with probability Po- Specifically, we provide non-asymptotic upper and lower bounds on the smallest signal strength 8* that is both necessary and sufficient to ensure the existence of test with small enough Type I and Type errors. We also derive novel minimax-optinn tests achieving these fundamental limits when the underlying graph sufficiently dense. Our proposed tests involve 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 ni, n22 k1, k2.
Introduction
The analysis of community structure is fundamental task in statistical network science [27, 24]. In the 2000's, series of striking works including (but not limited to) [3, 30, 53, 56] observe the ubiquity of community-based organization in real world network data. Inspired by these observations, a vast literature has emerged over the past two decades attempting to understand the statistical limits of detecting and recovering planted communities in random graphs [20, 48, 50, 59, 4, 8, 499, detecting geometry in graphs defined via latent metric spaces [14, 13, 44, 25], and establishing fundamental computational limits for the community detection and recovery problems [31, 16, 60, 46, 12]. Here, we draw careful distinction between community detection and community recovery. In the community detection problem, also sometimes referred to the Planted Dense Subgraph (PDS) problem, the statistician observes random graph and aims to determine whether the graph was drawn from Erdös-Renyi family, or if it contains densely connected community of vertices (i.e., dense subgraph). In contrast, the community recovery problem involves assigning each vertex in the observed graph to latent community, under the assumption that such community structure exists. We focus on community detection the present work, and we refer readers to [1] for a comprehensive review of the results pertaining to the recovery problem in the stochastic block model.
Existing work studying community detection can be divided into two categories. The first camp. including [4, 59, 57, 61], focuses detecting the presence of small community of k nodes in nodes, typically an asymptotic setting with & = o(n). these papers, the authors focus on deriving sufficient and necessary conditions on the difference in connection
high-dimensional graph
The authors contributed equally to this work and are ordered alphabetically.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

probabilities between the planted subgraph and the rest of the vertices for which detection of the subgraph is possible. While these works are able to give asymptotically precise characterizations of the detection boundary for their problems of interest, their results are limited in generality, as they constrain themselves to fully symmetric settings (the adjacency matrices of the full graph and the subgraph, with the exception of [57], are square) and make asymptotic assumptions that prohibits the appearance of complex phenomena; see for instance equation (6) in [4].
A parallel line of work considers the community detection problem in stochastic block models (SBM's) s) [38, 48, 51, 2. 6, 7, 8, 28]. Here the focus on the statistician' 's ability detect the presence of two or more communities in the observed graph, and deriving conditions on the difference in expected degree between the communities under which detection is possible. The early work [51] gives fundamental results related to the famed Besttnn-Stigmn threshold, although they are confined to the restricted case of two equally sized communities. While recent papers such as [8. 52] allow for growing number of potentially asymmetric communities, these works still required the average expected degree across communities to be held constant, which prevents their results from applying to graphs with highly imbalanced communities. The restriction is lifted in [29], in which the authors study community detection in the degree-corrected block model. However, similar to the works of [4, 59, 57J, the results of [29] hold only in a particular asymptotic regime.
Given the limitations of existing work, there remains a great interest in studying community detection in random graph models beyond those covered by the literature. In particular, previous results do not upply to the family of bipartite graphs, which are defined as sets of edges between two disjoint sets of vertices. In practice, the two sets of vertices may be of very different size, meaning that the results tailored for square adjacency matrices [4, 59, 2, 51] do not capture the subtleties of community detection in bipartite graphs. Furthermore, any planted subgraph in bipartite graph is, by definition, itself bipartite. While the recent paper [57] considers the detection of bipartite communities, they assume that these communities are planted in a larger non-bipartite graph and hence, similarly to [4, 59, 2, 51], fail to fully characterize the detection boundary in the bipartite case, We also comment that bipartite graphs can be thought of as a special case of multi-community SBM: however, as outlined above, the prior work studying this problem introduces its own limitations [8, 52, 29]. As bipartite graphs are increasingly used as modeling tools in the diverse fields of biology and medicine [54], information science [47], and game theory [55], this lack of understanding in the bipartite setting constitutes significant gap in the statistics and machine learning literature.
In this paper, we aim to address this gap. Following [4, 59], we formalize the problem of detecting community in a random bipartite graph as hypothesis testing problem. We observe random bipartite graph G defined on disjoint sets of vertices (nodes) V/ and V22 of size ny and n2 respectively, Under the null hypothesis, an edge appears between any two nodes in G with equal probability Po > O. Under the alternative hypothesis, there exist subsets of nodes VK, C V/2 and Vxs C V22 of size K1 and ky such that any pair of nodes in VK, X VK, are connected with elevated probability O. We derive the minimax rate of separation 5" [35], which is defined
no less than po + 6, where as the smallest value of å such that consistent community detection is possible (see Equation (4) for formal definition). Our results are non-asymptotic in nature, and hold for any values of nı1 R2, ki, and lg. This degree of precision allows to describe subtle phase transitions in the separation rate 5" which have not been observed in the existing community detection literature.
The paper is structured as follows. In Sections 1.1. 1.2, and 1.3 we review relevant literature, outline our contributions, and collect notation used through the paper. In Section 2 we formally state our problem of interest. Our main results and discussion thereof are given in Section 3 and Section 4. We conclude with a summary of the limitations of our results and promising directions for future work in Section 5. All of the proofs are provided in the supplement.
1.1 Prior work
The framework that we use to study optimal community detection in random graphs was pioneered by Arias-Castro and Verzelen [4, 59]. In [4], the authors provide matching asymptotic upper and lower bounds on the minimax risk of detecting a community of vanishing size in dense graph. They also handle the cases when the size of the community and the baseline connection probability Po are unknown, and provide polynomial-time tests using convex relaxation of the max degree test, following [11]. In [59], the authors extend their analysis to sparse graphs. While the papers [4, 59] broke significant ground, their results are still limited, as they only consider the restricted
2

---

fully symmetric setting of n1 = n2 and L1 = k2- Subsequent works derive analogous theoretical results for hypergraphs [62, 611, in which edges can be drawn between more than two vertices. The work [33] studies community detection under information constraints, namely that the statistician can only access small parts of the graph via non-adaptive edge queries. More recently, [57] considers the detection of a bipartite (i.e., imbalanced) community in non-bipartite graph. We provide a detailed comparison of our results to the results of [57] in Section 3.
In the stochastic block model (SBM) literature, the community detection problem is posed as the task of distinguishing an SBM with a given set of parameters from an Erdös-Renyi graph. This problem was first considered by [38], whose results were later refined by [51, 48, 2], which established that detection possible if and only if the signal strength is above the Kesten-Stigum threshold, as conjectured by [23]. In [6, 7], the authors prove analogous results for asymptotically growing expected degrees and provide optimal hypothesis tests based on signed cycle statistics. The work of [8] provides an impossibility result for distinguishability for SBM's ss with possibly growing number of communities, and [28] analyzes a powerful test in this setting constructed using small subgraph statistics.
Under the framework of [4, 59], community detection equivalent detecting a submatrix in the observed adjacency matrix. The seminal work of [15] provides matching upper and lower bounds for detecting sparse submatrix of elevated mean in matrix of Gaussian random variables under particular asymptotic regime. Following this, [46] initiates rigorous study of statistical- computational gaps in the submatrix detection problem which was continued by [16, 32, 12]. In [45], the authors study the problem of detecting a planted sparse sub-tensor in a high dimensional Gaussian tensor. Finally, [22] derives upper and lower bounds for detecting the presence of multiple sparse submatrices in Gaussian noise that are tight up to log factors.
1.2 Our contributions
In this paper, we make the following contributions.
1. We fully settle the non-asymptotic expression of the minimax rate 8" defined in (4), which holds provided the graph is sufficiently dense, as specified Assumption 1. In contrast to the previous literature, our bounds always match up to multiplicative constants for any possible values of n1, n2, k and kg. especially in the under-explored unbalanced regimes where hn & 22 or n. < n2- Our results reveal subtle phase transitions that, to the best of our knowledge, had not been documented in previous work.
2. Our lower bound on 8* stated in Theorem 1 holds without requiring Assumption I and uses a very precise application of the second moment method [42]. It requires several non-trivial lemmas for controlling the moment-generatinn function of the product of binomial random variables, and substantially departs from the lower bound strategies proposed in [15] and [4].
3. Our upper bound stated Theorem is achieved by carefully combining three tests: A standard total degree test and two entirely novel tests referred to as the truncated degree test and the max truncated degree test. The two novel tests are defined using truncated non-linear functions of the adjacency matrix, building on the truncated x² test recently studied in the Gaussian sequence model [21, 40, 43, 19). However, substantial modifications of the truncated x² test needed address two challenges:
(a) Moving from the vector case to the matrix case, which requires subtle Bonferroni corrections of the classical truncated x² test.
(b) Handling matrices whose entries are Bernoulli rather than Gaussian random variables, which require significant adjustments of the truncated x2 test to carefully manage the complex sub- sub-poissonian tails of the binomial distribution.
Our upper bound holds under Assumption 1, which we discuss thoroughly in later sections. We also prove a series of lemmas in the supplement that we use to control the Type I and Type II errors of these tests, and we anticipate that these results will be of interest to researchers studying related problems.
3

---

1.3 Notation
The following notation will be used throughout the paper. For p E N. let [p] := I...p. We use (n(n) to denote the set of subsets of [n] of size k. For a. b E R, denote a V b := max(a, b} and a A b =: min(a,b); b}. We will use a < b if there exists a constant C > depending on n such that < Ch. We say a x b if a S b and b X For two sets A and A2, we denote A1 A₂
[(,,)) : A1.J E A2) as the Cartesian product of A₁ and A2- For a finite set A, we use |A] to denote the cardinality of A. We use (.) as the indicator function, meaning that 1A= = 1 if the event A occurs and 1 0 otherwise. For a matrix X, we use Xúj to denote its (i. )n entry. Given two probability distributions and Q, we use TV(P, Q = supa [P((A) Q(4) to denote the total variation distance between IP and Q We use c, C, C, C", c1, C2, Cz. and e to denote constants whose value may change between instances of their usage in the paper. We will also use the convention that [a, bj = 0 for any two real numbers a, b such that > b. For any two integers n!
& E N U (0), we denote by (#) the binomial coefficient, equal to ki(n-R) Ry!
2 Problem statement
Let n1, R2, k1, 22 E be integers considered as fixed throughout the paper, and assume l S ni and &2 S f2. Let G = (E, V1, 1/2) be a random undirected bipartite graph defined on disjoint sets of vertices V = (Vi.1..... Vi,,, } and 1/2 = (V2.1..... V2,ng): } We observe the adjacency matrix A E [R"11 with entries A,, = 1(V., is connected to V2., by an edge} and assume that the edges are mutually independent Bernoulli random variables. For some parameter Po E [0. 1] assumed to be fixed throughout the paper, our objective is to determine whether each pair of vertices in V x V/ is connected with probability po. or if there exists a community (i.e., a bipartite subset of vertices) that is connected with greater probability P1 2 Po + ō for some 6 > 0.
Formally, we formulate this testing problem in terms of the mean structure of the adjacency matrix A. Define the matrix P = E8] [A] E _"xx,,, which represents the matrix of connection probabilities of the random graph G. For any two subsets K1 E Pky (m1), ), K2 E Pky (12) and any d 2 0, we define
{ P RRIX s.t.
((i,)) E K1 K2 Pij 2 Po + 5 (ii.)) K x K₂ : P.j = Po
θ(1,, ((1,,K2,8)
mean matrix belongs to (KK,, K2, 5) if the bipartite community indexed by K₁ x K₂ is more densely connected than the rest of the graph. Our focus in this paper is to optimally detect an unknown bipartite community of size 1 x 12. To this end, for any >> we let
O(k1, k2, n1, n2, 8) =
U
U
O(K1, K2,
(iEPe,(m) K2EPas(ns)
We consider the following testing problem
Hu V(i.j) E [m1] x [m2), Po against H₁ P k2 n1, n2, 6).
The hypothesis Hy is equivalent to observing a bipartite Erdōs-Renyi random graph with parameter Po- The hypothesis H, is equivalent to the existence of an unknown bipartite community of size kj x k2 with connection probabilities at least po + 8.
A test is measurable function of the observed data A taking its values in (0, We measure the quality of a test A by its risk, defined as the sum of its Type and worst-case Type II errors. Specifically, denoting by IP the probability distribution of A for P E O(k1, k2, n,, n2, 8), and letting Po denote the distribution of A under the null hypothesis, the risk of a test A is defined as
R(A 6) = Po(A 1) +
sup
Pp(A = 0).
The minimax risk associated with the problem (1) is defined as Rd (ki, k2, n1, n2, 8) inf in(
A
where the infimum is taken over all tests A. For desired level of risk 17 (0. 1), considered as fixed constant throughout, we are interested in the minimax separation rate 8 defined as
8 = inf (6 0 R' (K1, k2, n1, n2, 8) < n)
(4)

---

The minimax separation rate 8 encodes the difficulty of the testing problem. It is the infimal signal strength ensuring the existence of test with Type plus Type II errors controlled by the desired level of risk The goal of the paper is to derive the value of 6" in terms of 71, n2, kn, l2 and po up to absolute multiplicative constants, and to construct the minimax-optimal tests achieving a risk at most for the testing problem (1) when the separation satisfies 2 C8" for some constant C' > 0 depending only on r
Main results
For any hi, l2, n1, E N and for a constant C' > 0 to be chosen later, we define
112
n1 k1
(k1 n2, 122) =
k1
log
1+
k2
log
e
(5)
log
ma R2
if
S
C
Φ(k1,
R
(6)
00
otherwise.
722
u(ki, n2,
log
1
(7)
ki
1:2
log
4f
To alleviate the notation, we will write
$12 = <bk1, 12 n1, n2) 1/12 (ki,,, , k2, mi, ,
Φ2 = (k hi, 122 11)
4/21 (Kiz ki, 122, 12,
V12 uKki, K2 ni, 12)
= (k2, 11, 12,
Finally, we define the quantities
R = R(k,, K2, n1, n2) = (V12 + 4/21) Φ12 62
(8)
and
R = (112 v21) A (1/21 + V12) d12 A 621-
We will prove that the minimax separation rate 8* satisfies
(0*)² x Po (1 Po)
for any values of kn k2, ny and n2, under Assumption on given in Section 3.2.
3.1 Lower bound
The following theorem gives a lower bound on 8* that holds for any values of nı, n2, k1, lo2 and po-
Theorem Let [0, be given. There exist constants e, C that depend n only, such that 8 < CP R with (6) defined with C C, then it holds
R* (k1, k2, n1, n2, 8) 7).
Theorem yields the lower bound (8+)2 > cspo uses careful application of the second moment argument [42, 37, 34, 36, 15, 4]. We refer the reader to the supplement for details.
cs (1-Po)
R by definition of 8* The proof of Theorem I
3.2 Upper bound
Now we present matching upper bound on the minimax rate of separation 8*, We do so by carefully combining three testing procedures. which are each constructed from the observed adjacency matrix A. Our three hypothesis tests are defined follows.
1. Total degree test: Let ddeg
nnnnipool Po) and define the test statistic
takg
(Au Po)
(9)
ddeg
The total degree test is defined
Alyy 1 (tddo h) for a choice of threshold h 0.
5

---

2. Truncated degree test: To define this test, we introduce the Bennett function, defined as
(x))) = (1+ + x) log(1 + +x) x, h- =1.
Vx > -1.
(10)
(11)
For any j E [22]. and a 2 let m1po Po) and define
A = 8 im1
Σ (Aig po)
oA, ) + niPo hB
σA
W n1 (1 - Po) hB
(12)
n1 po)
r1Po
Letting Vn = Eg [W, A 2 al and denote a parameter to be chosen later, define
Linnncdegg, Σ (W, - 1ー 1(A3 2).
(13)
The truncated degree test is A Lune-dog..1 [ffunne-deg.1 h) for some threshold 0.
3. Max truncated degree test: For any J1 E Pk, (n1) and any j E [112], we let JJ,.J = kapo(1 Po) and define
Wns Thi iEJi
(Ais [Ass poo)
O ki (1 po)
( kiPo
Wr. = ky (1 - Pn) hB
+ ki h
(14)
Letting 2 Eo [W [WJ,lts, 2 a) and be a parameter be chosen later, define
(W - - 11)) > T) J1 E Prr Pal }.
mmax-truno-dog.1 = max
(15)
Finally, for a choice of threshold > 0, we define the maximum truncated degree test as Ah maxx-mnn-dg.. (4mmxx trunc tranc-deg,1 > h).
Analogously, we define the tests Ah mmmg- and 2 by swapping the roles of k1, k2, and M1, 12 the definitions of A Imax--rune and / Atune-degg11 respectively.
For some constant C > O depending only on the desired level of risk y,, we further combine the degree and truncated degree tests as follows. Let
A A1
hi trune-dog,1
C1
and
A MiA
hg A tonn-dogg22
if
2 2 c1.
A/e
deg
otherwise
A h/
otherwise.
Using these procedures as our building blocks, we construct our final test A by applying the relevant test depending what part dominates in the expression of the rate R. Specifically, optimal test is defined as
if R = 2/12 + 1/21
max-trune-dgg.1
A max-trane-deg..
if f v/21 + V12
A
A
ku Pr
if R Φ12
if R Φ21-
Our upper bound on the risk of A holds under the following assumption, which guarantees that the observed graph G is sufficiently dense.

---

Assumption (Graph density.) There exists a constant Cn > 0 depending only on such that the baseline connection probability po satisfies Po S 1/4 and
Cy_
log
121
if R (v/12 221) A (1221 + v12)
Cn log
1 +
m2 kg
if R = 01 and n2 > k2
Po
Cn log
1 +
ng k
if R Φ2 and ny > ki
n2
Cg
otherwise.
141122
The upper bound Po S 1/ in Assumption is used to apply Slud's inequality for binomial anti- concentration [58]. We invoke the different cases Assumption depending on the exact construction of A' Assumption places control the tails of the test statistics (9), (13), and (15) with sufficient precision. These tests are based binomial statisties, which exhibit sub-Gaussian concentration properties in the moderate deviation regime and sub-poissonian concentration in the large deviation regimes (see, e.g., [5, 17, 39, 18]). This dichotomy has also been noted in the two companion papers [4] and [59], which split the analysis between the case of dense graphs, where a qursi-normal regime emerges (see the first row of Table 1 in [4], and sparse graphs, where fundamentally different behaviors occur due to lower connectivity. In this paper, we follow the same approach by restricting to dense graphs as specified in Assumption and leave the case of sparse graphs for future work. Furthermore, Assumption has natural probabilistic interpretation, as codified in the following propositions.
in quasi-normal moderate deviation regime, which enables to
Proposition 1 Let e > O. There exists a constant C > O such that if
C Clog log
(e n21
122
1
((k))
po S 4'
ki
Kz
then it holds Po (G has an empty k x k2 bipartite subgraph) S c. Here, we say that a subgraph G1 of G is empty if all the vertices in G1 has degree equal to 0.
Proposition 2 Let e > O. There exists a constant C > such that if
C log
(c(m)
[11]
k2 ({
S Po S 4'
n221
then it holds Po TT E (n1) EIE/ Σド Aij = 0) cc
Propositions and 2 shows that Assumption 1 prevents the occurrence of extreme events under Po that would otherwise inflate the Type error of our testing procedures, especially the max truncated degree test in (15). We remark that the lower bound on Po assumed Proposition 2 stronger than what we need in Assumption 1; we include this result to provide intuition.
The following theorem guarantees that the minimax risk of A is small whenever ò is large enough.
Theorem Let 1 E [0. 1] be given. Suppose that Assumption holds. Then there exist constants Cs > 0 and thresholds hy 122, hy, ha >> O such that if 82 2 Cspo(1 Po) R with (6) defined with C = C, then the test A satisfies
R(A,00
Theorem 2 demonstrates that our proposed test A is able to match the lower bound on 8* given in Theorem under Assumption 1. Combining Theorems I and 2, we have therefore identified the minimax rate of separation 8* up to constants.
Discussion
4.1 Discussion the proposed tests
Our test A careful combination of three testing procedures. The total degree test has been commonly applied in previous works [4, 57], along with the sean fest, which consists of scanning
7

---

over all possible subgraphs of size 11 x k2 and rejecting if one of them contains an unusually large number of edges. Notably, our results do not make use of the sean test, and highlight that it can always be successfully replaced by a max truncated degree test, with lower time complexity
Our two novel tests Lrunodegg1 and ha in the Gaussian sequence model. Given vector X E RR, the truncated x² test statistic is given by
mmxx-muunee deg. build on the truncated x² test recently developed
T Ex} - 1o 1
for some a > and where V/ = E (z²) 2 a). On top of being fast to compute, this test has been shown be optimal in the Gaussian sequence model for detecting s-sparse alternatives separated in & norm when I /dd [21], whereas the max test, which rejects for large enough values max { رソ X3|J J E Pa(d)). is known to be statistically suboptimal [10] while exhibiting exponential time complexity.
We aim to adapt this test to the matrix case where X E Rd xd2 For the sake of discussion, we will focus on the truncated degree test (13), the ideas underlying the max truncated degree test (15) being analogous. An idea for adapting the truncated x² test would be to use
n2
X1j
Va 1
2
X 2a)
for some suitable re-centering parameters V4 and 1/2 Whereas squares of Gaussian random variables concentrate sub-exponentially (see Lemma 5 in [43]), squares of binomial distributions do not exhibit such favorable concentration properties, due to their sub-poissonian tails. In the definition of the test statistics (12) and (14), we therefore replace the square function with carefully chosen function with slower growth. Focusing on the truncated degree test for illustration, and recalling (12), we can check that
σA; W n21 - Po) hB n1(1 (1 pu) n1pu hB
TAj
A
x σA log(1
nipo
When Aj S o. which exactly corresponds to the moderate deviation regime for binomial distributions, we obtain Wi x A3 and our test statistic 4mune-deg.1 Σ}= (W, ", (A4 2 7) becomes analogous to the truncated x² test described above. the large deviation regime where A, >> a, have W, AA log( Aj which grows less fast than A3 and mitigates the extreme values of the binomial distribution.
Heuristically, the truncated degree test is optimal when one sub-graph of the elevated community large and the other is small. The max-truncated degree test is optimal when both sub-graphs are small. To demonstrate this: Suppose that one of the communities is very large, for example k2 = n2 to fix ideas, and the other one small (k) < n1)). In the corresponding adjacency matrix, all entries within row are i.i.d. Bernoulli random variables with the same probability parameter. well-known that a sufficient statistic of m i.i.d. data points X Xm ~ Bernoull(p)) is the sum Σ X₁ Binomial p). Therefore, the column vector obtained as the row-wise sum of the adjacency matrix is a sufficient statistic of the data. This vector is simply the vector of node degrees in the first sub-graph of the bipartite graph. Therefore, when one of the two sub-graphs is large enough, the problem can be reduced to a vector-basee based problem. A classical test statistic such cases is the truncated chi chi-square test, which apply the degree vector with slight refinement to account for the sub-Poissonian tails of the binomial distribution. This yields the truncated degree test.
When both sub-graphs of the elevated community are small, collapsing the matrix into single vector (by summing over rows or columns) discards too much information from the data. In this case, a natural idea would rather be to over all possible bipartite subgraphs of size kn x k2 and reject the null hy hypothssis when one such subgraph contains an unusually large number of edges-an approach proposed in [57]. Unfortunately, this procedure is not optimal. Instead, we propose a non-trivial refinement that builds on the truncated chi-square test, adapted to tackle two key challenges: 1) the
*Computing A ha dex.tmme-dgg. requires OKknz (B:)) operations, rather than O kz (()) (?2)) for the scan
test.
8

---

data are matrix-valued, not vector-valued, and 2) the entries are Bernoulli rather than Gaussian random variables. Our procedure, the max maxxtruuncteed degree test as formally defined in equation (14), is obtained by scanning and summing over subsets along one dimension of the matrix, applying non-linear transformation based on the Bennett function, and truncating along the other dimension analogous to the truncated chi-square test statistic. This procedure captures subtle concentration effects of bipartite graphs when both communities are small and achieves the minimax optimal risk in this regime.
4.2 Comparison with existing results
Through Theorems and 2, we have shown
(6))² x Po Po)
(16)
with R defined in (8). We can understand the nuances of (16) by first considering our results when restricted to the fully balanced (effectively non-bipartite) setting. Suppose that k = l22 k and 71 122 n. and that Ck2 From the definition of Rt we can rewrite (16)
(6*)²
71
71
log Po(1 Po)
log
(17)
K
R-2
> 1 FZ < 1, the form of 8* in (17) matches that given by Theorem 2 of [4] in the moderate deviation regime imposed by Assumption 1. Our result is, fact, more refined than that of [4], we are able to precisely capture the phase transition around fo = thanks to our truncated degree test.
If R
The detection boundary for imbalanced bipartite graphs is more complex. The following proposition describes new phase transition that emerges in the imbalanced bipartite setting, but not in the non-bipartite setting.
Proposition 3 Suppose that &ē k2 for constant č > 0 and K2 cyn for j E {1,2} where C2 > 0 are sufficiently small constants. Additionally, suppose that there exists a constant a > 0 such that n2 k22- and that k1 log( n2 Then it holds
(8*)²
log
(1+
n1k2 log(ma))
(18)
Po(1 po)
1o2
ky
particular, this reveals a phase transition at mike log(n2) x1
To our knowledge, (18) is described nowhere in the existing community detection literature, as previous works either impose restrictions on the shape of the observed graph and the community of interest (i.e. enforcing nı n2 and/or k k2) or provide results that are not sharp for all configurations of n1, n22, k1, and kg. The recent paper of [57] presents the results that are most similar to ours in the literature. They consider the case n, n2 n with b₁ * k2 in the asymptotic regime k + 22- = o(n). We again emphasize that our results hold for na * n2 and any k and k2, and as such are immediately more general than those of [57]. However, we argue that our results are more precise even in the restricted case of n1 n2 and h1 + 1o2 = o(n). Under the assumption that Po, 8* = (n -a for a (0, 2), in Theorem of [57] the authors show that (8*)2
= =Ω (
n
n 1VV3 12
^
A
Po (1 Po)
ki
A
k2
k2
and in Theorem 2, they show
= = log(n) Po - po)
(6*)²
n²
n log(n)
k1 K2
R k
We refer readers equations (14) and (15) in [57] and the surrounding discussion for details. Their lower bound on 8* is loose by logarithmic factor in n, and the asymptotic assumption 8* O( (n) excludes the regime which the complex rate that we derive in (16) emerges. As such, the results of
[57] do not describe, for instance, the phase transition (18). We also comment on the assumptions on Po made [57] and our work. Recall that the results of [57] require Po Z n n- for a E (0, 2).
where under Assumption 1, require at least Po 2 1 and, in certain regimes, we need

---

Po 2 ki results from holding for all values of po considered by [57]. However, as their results are not sharp, they are able describe the entirety of the detection boundary in the case when our Assumption I does not hold. We anticipate that the minimax rate of separation 8 may actually differ non-trivially from the rate derived in [57] in this setting, and we view the extension of our results beyond Assumption as crucial piece of future work. Finally, we remark that [26] extends the results of [57] beyond planted bipartite subgraphs, but they do so the same asymptotic setting and thus suffer from the same limitations.
1 log( (2)) This assumption is stronger than that of [57], and hence excludes our
5 Conclusion, limitations, and open problems
We have presented a rigorous study of the community detection problem in bipartite graphs. We present a lower bound the minimax rate of separation, and describe a novel optimal testing strategy that achieves the minimax rate when the observed graph is dense. Our non-asymptotic results hold for all possible dimensions of the observed graph and the planted subgraph, which reveals new behavior in the detection boundary. Here, we outline some limitations and opportunities for future work.
Adaptivity to unknown po, 11, and l2g All three of our tests require knowledge of Po. the connection probability under the null hypothesis, which is typically unavailable in practice. [4], the authors consider this problem in the case of non- non-bipartite graphs, and find that community detection without knowledge Pu exhibits substantially different behavior. We anticipate that similar phenomena will arise in the bipartite setting.
Furthermore, our max truncated degree test requires knowledge of the size of the community as encoded in k and k2.. Optimal adaptivity to unknown ką and k2 is achieved in previous works such as [15, 4] by scanning over possible values of k and l2 and performing a Bonferroni correction. However, this not an option for us, since the tails of the test statistic (15) are too heavy to still be optimal after a union bound. One possible strategy is to use Lepski-style adaption as in [41]; we leave this to future work.
Beyond dense bipartite graphs. The tightness of upper bound in Theorem relies on Assumption 1. Prior work in the non- bin-tipatt community detection literature [59] suggests that the detection landscape is very different for sparse graphs. Understanding optimal detection in bipartite graphs when po is extremely small will potentially require testing procedures and new techniques for proving lower bounds, likely based on the truncated second moment method [35, 15, 4, 59].
Computational considerations. Our max truncated degree test unfeasible to compute on datasets of even moderate size. It is well established that the community detection problem in non-bipartite graphs exhibits a statistical-computtiinn general, possible optimally detect planted community with test that runs polynomial time. We conjecture that this gap persists in the bipartite case, and establishing this phenomenon formally an open problem of great interest.
gap [46, 4, 31, 12, 22, 57, 26), meaning that it is not, in
10

---

References
[1] Emmanuel Abbe. "Community detection and stochastic block models: recent development"". In: Journal of Machine Learning Research 18.177 (2018), pp. 1-86.
[2] Emmanuel Abbe and Colin Sandon. "Community detection in general stochastic block mod- els: Fundamental limits and efficient algorithms for recovery". In: 2015 IEEE 56th Annual Symposium on Foundations of Computer Science. IEEE. 2015, pp. 670-688.
[3] Réka Albert and Albert-László Barabási. "Statistical mechanics complex networks". In: Reviews of modern physics 74.1 (2002), p. 47.
[4] Ery Arias-Castro and Nicolas Verzelen. "Community detection in dense random networks". In: (2014).
[5] Ery
and Meng Wang. "The sparse Poisson means model". In: (2015).
[6] Debapratim Banerjee. "Contiguity and non-reconsttruction results for planted partition models: the dense case". In: Electronic Journal of Probability (2018).
[7] Debapratim Banerjee and Zongming Ma. "Optimal hypothesis testing for stochastic block
models with growing degrees". In: arXiv preprint urXiv:/705.055 (2017).
[8] Jess Banks et al. "Informaaiion-theoreiii thresholds for community detection in sparse net- works". In: Conference on Learning Theory. PMLR. 2016, pp. 383-416.
[9]
Albert-Laszlo Barabasi and Zoltan N Oltvai. "Network biology: understanding the cell's functional organization". In: Nature reviews geneties 5.2 (2004), pp. 101-113.
[10] Yannick Baraud. "Non-asympiotic minimax rates of testing in signal detection". In: (2002).
[11]
Quentin Berthet and Philippe Rigollet. "Optimal detection of sparse principal components in high dimension". In: Annals of Statistics (2013).
[12] 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.
[13] Matthew Brennan, Guy Bresler, and Dheeraj Nagaraj. "Phase transitions for detecting latent geometry in random graphs". In: Probability Theory and Related Fields 178.3 (2020), pp. 1215- 1289.
[14] Sébastien Bubeck et al. "Testing for high-dimensional geometry in random graphs". In: Random Structures & Algorithms 49.3 (2016), pp. 503-532.
[15] Cristina Butucea and Yuri I Ingster. "Detection of sparse submatrix of a high-dimensional noisy matrix". In: Bernoulli (2013).
[16] Yudong Chen and Jiaming Xu. "Statisiccllcoomutttiinn tradcoff's in planted problems and submatrix localization with growing number of clusters and submatrices" In: Journal of Machine Learning Research 17.27 (2016), pp. 1-57.
[17] Julien Chhor and Alexandra Carpentier. "Goodness-of- fit testing for Hölder-continuous densi- ties: Sharp local minimax rates". In: Bernoulli (2025).
[18] Julien Chhor and Alexandra Carpentier. "Sharp local minimax rates for goodness-of-fe testing in multivariate binomial and Poisson families and in multinomials." In: Mathematical Statisties
& Learning (2022).
[19] Julien Chhor, Rajarshi Mukherjee, and Subhabrata Sen. "Sparse signal detection in het- eroscedastic Gaussian sequence models: sharp minimax rates". In: Bernoulli 30.3 (2024),
pp. 2127-2153.
[20] Amin Coja-Oghlan "Graph partitioning via adaptive spectral techniques". In: Combinatorics, Probability and Computing 19.2 (2010), pp. 227-284.
[21] Olivier Collier, Laëtitia Comminges, and Alexandre B Tsybakov. "Minimax estimation of linear and quadratic functionals on sparsity classes". In: (2017).
[22] Marom Dadon, Wasim Huleihel, and Tamir Bendory. "Detection and recovery of hidden submatrices". In: IEEE Transactions on Signal and Information Processing over Networks 10 (2024), pp. 69-82.
[23] Aurelien Decelle et al. "Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications". In: Physical Review E-Statistiaal, Nonlinear, and Soft Matter Physics 84.6 (2011), p. 066106.

---

[24] Asim K Dey, Yahui Tian, and Yulia R Gel. "Community detection in complex networks: From statistical foundations data science applications". In: Wiley Intendisciplinary Reviews: Computational Statistics 14.2 (2022), e1566.
[25] Quentin Duchemin and Yohann De Castro. "Random geometric graph: Some recent develop- ments and perspectives". In: High Dimensional Probability IX: The Ethereal Volume (2023), pp. 347-392.
[26] Dor Elimelech and Wasim Huleihel. "Detecting Arbitrary Planted Subgraphs in Random Graphs". In: arXiv preprint arXiv:2503. 19069 (2025).
[27] Santo Fortunato and Mark EJ Newman. "20 years of network community detection".. In: Nature Physics 18.8 (2022), pp. 848-850.
[28] Chao Gao and John Lafferty. "Testing network structure using relations between small sub- graph probabilities". In: arXiv preprint WxXiv:170.00674 (2017). [29] Chao Gao et al. "Community detection in degree-corrected block models". In: The Annals of Statistics 46.5 (2018) 8), pp. 2153-2185.
[30] Michelle Girvan and Mark EJ Newman. "Community structure in social and biological net- works". In: Proceedings of the national academy of sciences 99. (2002). pp. 7821-7826.
[31] 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. [32] Bruce Hajek, Yihong Wu, and Jiaming Xu. "Information limits for recovering hidden community". In: JEEE Transactions on Information Theory 63.8 (2017), pp. 4729-4745.
[33] Wasim Huleihel, Arya Mazumdar, and Soumyabrata Pal. "Random subgraph detection using queries". In: Journal of Machine Learning Research 25.126 (2024), pp- 1-25.
[34] Yu I Ingster. "Minimax testing of nonparametric hypotheses on distribution density in the L P metries". In: Theory of Probability & Its Applications 31.2 (1987). pp. 333-337.
[35] Yuri Ingster and Irina A Suslina. Nonparametric goodness-of-fi testing under Gaussian models. Vol. 169. Springer Science & Business Media, 2012.
[36] Yuri I Ingster, Alexandre B Tsybakov, and Nicolas Verzelen. "Detection boundary in sparse regression". In: (2010).
[37] Yuri Izmailovich Ingster. "On the minimax nonparametric detection of signals in white gaussian noise". In: Problemy Peredachi Informatsii 18.2 (1982), pp. 61-73.
[38] Svante Janson. "Asymptotic equivalence and contiguity of some random graphs". In: Random Structures & Algorithms 36.1 (2010), pp. 26-45.
[39] Subhodh Kotekal, Julien Chhor, and Chao Gao. "Locally sharp goodness-of fit testing in sup norm for high-dimenni -igh-dimensional counts". In: arXiv preprint arXiv:2409.0887 (2024). [40] Subhodh Kotekal and Chao Gao. "Minimax rates for sparse signal detection under correlation".
In: Information and Inference: A Journal of the IMA 12.4 (2023), pp. 2873-2969.
[41] Subhodh Kotekal and Chao Gao. "Sparsity meets correlation in Gaussian sequence model". In:
arXiv preprint wrXiv:2312.093355 (2023).
[42] Lucien LeCam. "Convergence of estimates under dimensionality restrictions". In: The Annals
of Statistics (1973). pp. 38-53.
[43] Haoyang Liu, Chao Gao, and Richard J. Samworth. "Minimax rates in sparse, high-dimensional
change point detection". In: The Annals of Statistics 49.2 (2021), pp. 1081-1112, DOI: 10. 1214/20- 2214/20-A0S1994. A0S1994.
[44] Suqi Liu and Miklós Z Rácz. "Phase transition in noisy high-dimensional random geometric graphs". .. In: Electronic Journal of Statistics 17.2 (2023), pp. 3512-3574.
[45] Yuetian Luo and Anru R Zhang. "Tensor clustering with planted structures: Statistical optimal- ity and computational limits". In: The Annals of Statistics 50. (2022). pp. 584-613.
[46] Zongming Ma and Yihong Wu. "COMPUTATIONAL BARRIERS IN MINIMAX SUBMA- TRIX DETECTION". In: The Annals of Statistics (2015), pp. 1089-1116.
[47] Cristina Maier and Dan Simovici. "Bipartite graphs and recommendation systems". In: Journal of Advances in Information Techmology-in print (2022).
[48] Laurent Massoulié. "Community detection thresholds and the weak Ramanujan property"'
In: Proceedings of the forty-sixth annual ACM symposium on Theory of computing. 2014,
pp. 694-703.
12

---

[49] Elchanan Mossel, Joe Neeman, and Allan Sly. "A proof of the block model threshold conjec- ture". In: Combinatorica 38.3 (2018). pp. 665-708.
[50] Elchanan Mossel, Joe Neeman, and Allan Sly. "Belief propagation, robust reconstruction and optimal recovery of block models". In: Conference Learning Theory. PMLR. 2014, pp. 356-370.
[51]
Elchanan Mossel, Joe Neeman, and Allan Sly. "Reconstruction and estimation in the planted partition model". In: Probability Theory and Related Fields 162 (2015), pp. 431-461.
[52] 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).
[53] Gergely Palla et al. "Uncovering the overlapping community structure of complex networks in nature and society". In: Nature 435.7043 (2005), pp. 814-818.
[54] Georgios A Pavlopoulos et "Bipartite graphs in systems biology and medicine: a survey of methods and applications". In: GigaScience 7.4 (2018), giy014.
[55] Jorge Pena and Yannick Rochat. "Bipartite graphs models of population structures in evolutionary multiplayer games". : In: (2012).
[56] Martin Rosvall and Carl T Bergstrom. "Maps of random walks on complex networks reveal community structure". In: Proceedings of the national academy of sciences 105,4 (2008), pp. 1118-1123.
[57] Asaf Rotenberg, Wasim Huleihel, and Ofer Shayevitz. "Planted Bipartite Graph Detection".
In: IEEE Transactions on Information Theory (2024).
[58] Eric V Slud. "Distribution inequalities for the binomial law". In: The Annals of Probability 5.3
(1977), pp. 404-412.
[59] Nicolas Verzelen and Ery Arias-Castro. "Community detection in sparse random networks".
In: (2015).
[60] Yihong Wu and Jiaming Xu. "Statistical problems with planted structures: Information- theoretical and computational limits". In: arXiv preprint arXiv:1806.0 00108111 (2018).
[61] Mingao Yuan and Zuofeng Shang. "Sharp detection boundaries on testing dense subhyper-
graph". In: Bernoulli 28.4 38.4 (2022), pp. 2459-2491.
[62] Mingao Yuan et al. "Testing community structure for hypergraphs". In: The Annals of Statistics
50.1 (2022), pp. 147-169.
13

---

1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We substantiate all claims made in the abstract and introduction in Section 3.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We address all serious limitations in Section 5, and outline many possible avenues for future work.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We provide all proofs in the supplementary material.
14

---

Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c)
If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
15

---

Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.c cc/
sil.sssisiiiico)ll for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / /nips. wttpc//ccccppccccccoc httg//uddss///// Stte://ooeSSueiiieeeeeee wwwsssssioiiiiooeeoo for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
16

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: / http///eerrpp..eeee//ee cc
Answer:
[Yes]
Justification:
We affirm that comply with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work is entirely theoretical, and anticipate societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
17

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
We do not use any existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi sepprsswithood thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
18

---

Answer:
[NA]
Justification:
We do not release any assets in the present work.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper dow not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
19

---

Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https: /atpa////.//oooaaeeraa/////////0 for what should or should not be described.
20


Reviews:
[{"review_id": "ivhpdb8oxF", "reviewer": "Reviewer_RfAb", "summary": "This paper studies the problem of detecting a dense bipartite subgraph. More specifically, this is a hypothesis testing problem between a null distribution of bipartite Erd\\H{o}s–R\\´enyi graphs (of size $n_1 \\times n_2$) against an alternative distribution of bipartite random graph with a planted denser subgraph (of size $k_1 \\times k_2$). The result establishes the minimax rate of the edge density separation $\\delta^*$, for any values of $n_1, n_2, k_1$, and $k_2$. The optimal test consists of three parts: a total degree test, a truncated degree test, and a max truncated degree test. Each of them is optimal up to multiplicative constants under some conditions of the size parameters. A careful combination makes it optimal down to the complete regime, under a graph density constraint. It worth notice that the lower bound is not restricted on the graph density constraint.", "questions": "1. Could you clarify which specific regime in Assumption 1 is associated with Proposition 2?\n2. Could you elaborate on the intuition for when the max-truncated degree test is preferable to the truncated degree test, and conversely, in which regimes the truncated degree test would be more appropriate? The construction of $\\Delta_{a}^{h_1}$ and $\\Delta_{a}^{h_2}$ have a simple threshold, but the other thresholds in terms of $\\psi_{12}, \\psi_{21}, \\phi_{12},$ and $\\phi_{21}$ are a bit hard to grab the idea.\n3. Would you expect the lower bound to be tight when Assumption 1 fails?\n4. A minor point I noticed that is the notation of $\\Theta(n_1,n_2,k_1,k_2,\\delta)$ in equation (1) is inconsistent with other places.", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "**Strengths**\n1. This work gives a lower bound of the minimax rate of density separation $\\delta^*$ under any $n_1,n_2,k_1,k_2$.\n2. Although the upper bound result relies on a density constraint, it is very interesting to be independent of balanced community or balanced planted bipartite graph assumptions.\n3. The proposed truncated degree test and max truncated degree test carefully extend the idea of the truncated $\\chi^2$-test by coming up a statistic of the normalized (under null) average degree to control the tail probability.\n\n**Weaknesses**\n1. Many parts of the paper are well-written, but I find Section 3 a bit lack of intuitions. It would be nice to explain more on what would each regime look like when each of $\\psi_{12}+\\psi_{21}$, $\\phi_{12}$, or $\\phi_{21}$ becomes the smallest among those three quantities. This would largely help the readers grab the idea of when would each test become more natural or useful.\n2. The constructed test potentially runs in exponential time, depending on the size of the planted dense bipartite subgraph. The potential of an information-computational gap does exist so we are not sure about whether this is a weakness of this constructed test or not. It would also be interesting to see whether there are some regimes where you can actually construct efficient tests.", "was_revised": true, "final_justification": "I raised my point as the authors addressed my main concerns in the rebuttal.", "rebuttal": "1. *Could you clarify which specific regime in Assumption 1 is associated with Proposition 2?*\n\nResponse: Proposition 2 is specifically associated with the third regime in Assumption 1, corresponding to $R = \\phi_{21}$ and $n_1 > k_1^2$. We remark here that the form of Proposition 2 is in fact stronger than what is needed in Assumption 1; we include the result of Proposition 2 in the paper for the reader’s intuition. We will add a comment after Proposition 2 clarifying this in the camera-ready version of the paper.\n\n2. *Could you elaborate on the intuition for when the max-truncated degree test is preferable to the truncated degree test, and conversely, in which regimes the truncated degree test would be more appropriate?*\n\nResponse: In a nutshell, the truncated degree test is optimal when one of the two communities is large and the other is small. The max-truncated degree test is preferable when both communities are small. \n\nThe intuition for the **truncated degree test** is as follows. Suppose that one of the communities is very large–for example, $k_2 = n_2$, to fix ideas– and the other one is small ($k_1 \\ll n_1$). In the corresponding adjacency matrix, all entries within a row are iid Bernoulli random variables with the same probability parameter. It is well-known that a sufficient statistic of $m$ iid data points $X_1, \\dots, X_m \\sim Ber(q)$ is the sum $\\sum_{i=1}^m X_i \\sim Binomial(m,q)$. Therefore, the column vector obtained as the row-wise sum of the adjacency matrix is a sufficient statistic of the data. This vector is nothing but the vector of node degrees in the first population of the bipartite graph. Therefore, when one of the two communities is large enough, the problem can be reduced to a vector-based problem. A classical test statistic in such cases is the truncated chi-square test (see the definition of T at the bottom of Page 7), which we apply to the degree vector with a slight refinement to account for the subpoissonian tails of the binomial distribution. This yields the truncated degree test. \n\nThe intuition for the **max-truncated-degree test** is as follows. When both communities are small, collapsing the matrix into a single vector (by summing over rows or columns) discards too much information from the data. In this case, a natural idea would rather be to scan over all possible bipartite subgraphs of size $k_1 \\times k_2$ and reject the null hypothesis when one such subgraph contains an unusually large number of edges–an approach proposed in  (Rotenberg, Huleihel and Shayevitz, Planted Bipartite Graph Detection, IEEE TIT 2024). Unfortunately, this procedure is not optimal. Instead, we propose a non-trivial refinement that builds on the truncated chi-square test, adapted to tackle two key challenges: 1) the data are matrix-valued, not a vector-valued, and 2) the entries are Bernoulli rather than Gaussian random variables. Our procedure, formally defined in equation (14), is obtained by scanning and summing over subsets along one dimension of the matrix, applying a non-linear transformation based on the Bennett function, and truncating along the other dimension–analogously to the truncated chi-square test statistic. This procedure captures subtle concentration effects of bipartite graphs when both communities are small. \n\nPlease let us know if this clarifies your intuition for when each test is optimal. If so, we will be happy to add this heuristic explanation to Section 3 of our paper to clarify the reader’s understanding.\n\n\n3. *Would you expect the lower bound to be tight when Assumption 1 fails?*\n\nResponse: We do not expect the lower bound to be tight when Assumption 1 fails. A similar gap has been established in the companion papers (Arias-Castro and Verzelen, Community detection in dense random networks, AoS 2014) and (Arias-Castro and Verzelen, Community detection in sparse random networks, AoS 2015), which study a special case of our setting by imposing the restriction $n_1 = n_2$ and $k_1 = k_2$. When the graph is sparse (that is, when an assumption on the connectivity akin to our Assumption 1 is violated), their lower bound requires further truncating the second moment of the likelihood ratio on a carefully chosen high-probability event, which leads to fundamentally different statistical rates. \n\nHere, we take a similar approach by focusing on dense graphs first and leaving the case of sparse graphs for future work. Our lower bound technique relies on a careful analysis of the moment generating function of the product of two binomial random variables. Assumption 1 is used in the upper bound only. Given the technical difficulty of the analysis under Assumption 1, we anticipate that relaxing this assumption will present substantial interesting challenges that we plan on pursuing in future work. We kindly refer the Referee to our response to Question 1 from Reviewer QZpt regarding possible extensions of our upper bounds when Assumption 1 does not hold. \n\n4. *A minor point I noticed is that the notation of Theta in equation (1) is inconsistent with other places.*\n\nResponse: We thank the reviewer for pointing out this typo, and we will fix this in the camera-ready version of our paper.\n\n\n*Regarding computational challenges:* We kindly refer the Referee to our response to Question 3 from Reviewer QZpt for a discussion of the computational challenges associated with our tests."}, {"review_id": "VzHkUbc1sk", "reviewer": "Reviewer_QZpt", "summary": "The authors presented a rigorous study of the community detection problem in bipartite graphs. In particular, the paper presented a lower bound on the minimax rate of separation, and described a novel optimal testing strategy that achieves the minimax rate when the observed graph is dense. Their non-asymptotic results hold for all possible dimensions of the observed graph and the planted subgraph, which reveals new behavior in the detection boundary.", "questions": "(1) Given the reliance of the upper bound on Assumption 1, what are the key technical obstacles preventing the extension of your optimal testing strategies to the sparse graph setting? Do you anticipate the minimax rate $\\delta^*$ itself changing fundamentally under sparsity?\n\n(2) For truncated degree tests, how to choose the thresholds $\\tau,h$?", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: The paper presents non-asymptotic, matching upper and lower bounds for $\\delta^*$ valid for all parameter configurations ($n_1,n_2,k_1,k_2$). This universality is a major advance over prior work constrained to asymptotic regimes, square matrices and symmetric communities. Besides, the introduction of the truncated degree test and max truncated degree test is significant. These adapt the truncated $\\mathcal{X}^2$ concept to the challenges of binomial data and the matrix setting, requiring careful function design and handling of moderate vs. large deviations.\n\nWeaknesses: (1) The upper bound and optimality of the proposed tests crucially depend on Assumption 1, requiring the graph to be sufficiently dense. This excludes the practically important regime of sparse bipartite graphs. (2) The max truncated degree test requires scanning over all subsets of $\\mathcal{V}_1$ or $\\mathcal{V}_2$, making it computationally infeasible for moderate-sized graphs. This paper doesn't offer any computationally efficient alternative achieving the rate, even heuristically. (3) This paper lacks empirical validation of the derived rates or the performance of the proposed tests.", "was_revised": false, "final_justification": "", "rebuttal": "1. *Given the reliance of the upper bound on Assumption 1, what are the key technical obstacles preventing the extension of your optimal testing strategies to the sparse graph setting? Do you anticipate the minimax rate itself changing fundamentally under sparsity?*\n\nResponse: In the analysis of our testing procedures, Assumption 1 allows us to control the tail probabilities of the test statistics in question with sub-Gaussian concentration results as well as moderate and large deviation bounds for the binomial distribution. This is necessary to extract the correct rates that match the lower bound that we present in Theorem 1. We do not expect this analysis to carry over to the sparse regime, as our upper bound proof fundamentally breaks if one of the assumptions of the form $a \\in [C, c\\sigma]$ in Lemmas 18, 19, 20, 21 is violated. Such assumptions are guaranteed by Assumption 1 in the proof of Theorem 2.\n\nIndeed, in the sparse graph regime, we expect the optimal testing strategies to dramatically change compared to those developed in the paper. This difference has been described in (Arias-Castro and Verzelen, Community detection in dense random networks, AoS 2014) and (Arias-Castro and Verzelen, Community detection in sparse random networks, AoS 2015), which study a special case of our setting (namely, the non-bipartite setting) by imposing the restriction $n_1 = n_2$ and $k_1 = k_2$. In the sparse case, their test statistics are based on a “broad scan test statistic”, the number of triangles, the size of the largest connected component or the largest subtree in the graph, leading to substantially different statistical rates. Certain challenging regimes are also left unsolved. In our case, we expect the optimal test statistics to depend on delicate subpoissonian properties of sparse bipartite graphs, which will constitute a crucial piece of future research.\n\n2. *For truncated degree tests, how to choose the thresholds tau and h?*\n\nWe present precise choices of $\\tau$ and $h$ that achieve the optimal testing risk for each of the truncated degree tests in the supplement; see the results in Section B for details. The $h$’s are defined at the bottom of page 37 and top of page 38 and $\\tau$ is defined in statements of Lemma 16 and 17. In particular, for the truncated degree test defined over the columns of the adjacency matrix we take $\\tau = \\sqrt{C\\log(1 + n_2/k_2^2)}$ and $h = 9(\\sqrt{n_2 \\exp(−c′\\log(1 +n_2/k_2^2) c} + c)$.  For the max truncated degree test defined over the columns of the adjacency matrix we take $\\tau = \\sqrt{C\\log(1 + n_2/k_2^2\\log{n_1 \\choose k_1})}$ and $h = 9(\\sqrt{n_2 \\exp(−c′\\log(1 +n_2/k_2^2) c\\log{n_1 \\choose k_1}} + c\\log{n_1 \\choose k_1})$. We simply flip the indices of $k_1, k_2, n_1$, and $n_2$ if the test is rather defined over the columns. Here, $c, c'$ and $C$ are positive constants whose value may depend on the level of desired testing risk $\\varepsilon$. We will add the thresholds to the main text for clarity.\n\n3. *On computational challenges:*\n\nResponse: There do exist known statistical-computational gaps in the community detection problem. This phenomenon was described formally in the non-bipartite case in (Verzelen and Arias-Castro, Community detection in dense random networks, AoS 2014), as well as in the bipartite subgraph case in (Rotenberg, Huleihel and Shayevitz, Planted Bipartite Graph Detection, IEEE TIT 2024). Therefore, we also expect statistical-computational gaps to arise in our setting. However, our objective was to settle the statistical aspects of the community detection problem in dense bipartite graphs, as no precise, optimal rates were previously known under any configuration of $k_1, k_2, n_1$ and $n_2$. We therefore leave the derivation of computational gaps to future work.\n\n\t\nAs a side note on computational complexity: we never use the scan test, which was the only previously known test achieving near-optimal statistical rates of detection in specific regimes (Rotenberg, Huleihel and Shayevitz, Planted Bipartite Graph Detection, IEEE TIT 2024). Instead, we always replace it with our max-truncated-degree test. Although computing our test statistic requires exponential time, its time complexity still substantially improves upon that of the scan test, while also providing a statistically more powerful test in most regimes (see Section 4.1 for details)."}, {"review_id": "TXjG5mvU01", "reviewer": "Reviewer_Kxva", "summary": "The authors present new statistical tests for community detection in random bipartite graphs and prove that they are minimax optimal.", "questions": "- *theorem 2 of [2]  deals with G(n,p,Q) where p_i’s is the probability of a node belonging to community i, and pi’s are in (0,1). This does not seem to be consistent  with the claim that they “are confined to the restricted case of two equally sized communities”. Please clarify. \n\n- “the two sets of vertices may be of very different size, meaning that the results tailored for square adjacency matrices … do not capture the subtleties of community detection in bipartite graphs.” This seems to suggest that using a square adjacency matrix to represent a bipartite graph might be restrictive. Please clarify whether this is what you meant.", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- the problem studied in the paper is interesting\n- the paper is well written and organized\n\nWeaknesses:\n- a statistics conference or journal might be a better fit\n- it is difficult to assess the novel contribution w.r.t. to the state of the art (see questions below)", "was_revised": true, "final_justification": "There are some inaccuracies in the paper, which however seem minor. Given that I am not familiar with this line of work I feel more comfortable to let the other reviewers decide whether accepting it or not.", "rebuttal": "1. *Theorem 2 of [2] deals with G(n,p,Q) where p_i’s is the probability of a node belonging to community i, and pi’s are in (0,1). This does not seem to be consistent with the claim that they “are confined to the restricted case of two equally sized communities”. Please clarify.*\n\nResponse: We thank the reviewer for pointing out this inaccuracy. It is true that the work of [2] allows for multiple communities of possibly unequal size, and we will correct this in the literature review section of our paper. However, they are not studying the same problem as us. “Community detection” in their language refers to clustering each vertex in a non-bipartite SBM and recovering the true underlying clusters asymptotically. In contrast, we consider the problem of testing whether a community exists in a bipartite graph, in a fully non-asymptotic setting. We will correct this slight inaccuracy in our literature review. However, we emphasize that this does not detract from the novelty of our results, as no optimal rates were previously known for arbitrary values of $k_1, k_2, n_1$ and $n_2$ in our detection problem.\n\n2. *“The two sets of vertices may be of very different size, meaning that the results tailored for square adjacency matrices … do not capture the subtleties of community detection in bipartite graphs.” This seems to suggest that using a square adjacency matrix to represent a bipartite graph might be restrictive. Please clarify whether this is what you meant.*\n\nResponse: For bipartite graphs with two populations of $n_1$ and $n_2$ nodes respectively, the adjacency matrix is a rectangular matrix of size $n_1 \\times n_2$. This contrasts with a non-bipartite graph with n nodes, whose adjacency matrix is a square matrix of size $n \\times n$. Results developed in the case of non-bipartite graphs–that is, for square adjacency matrices–are therefore inapplicable to the case of bipartite graphs whose adjacency matrices can have substantially more rows than columns, or vice versa. Of course, it is always possible to represent a rectangular matrix as a square matrix by simply adding empty rows or columns. However, existing results for square adjacency matrices still do not apply in this case. Indeed, they assume that under the null hypothesis, all entries are iid Bernoulli random variables with non-zero parameter, which excludes cases where adjacency matrices have entire rows or columns that are identically zero (see e.g. Verzelen and Arias-Castro, Community detection in dense random networks, AoS 2024). \n\nIt may be the case that the reviewer thinks that the setting concerns the detection of a bipartite community of size $k_1 \\times k_2$ in a larger, non-bipartite graph of size $n \\times n$. In reality we consider the detection of a bipartite community of size $k_1 \\times k_2$ within a larger bipartite graph of size $n_1 \\times n_2$.  The former setting is considered in (Rotenberg, Huleihel and Shayevitz, Planted Bipartite Graph Detection, IEEE TIT 2024). We present a thorough comparison of our results to theirs in Section 4 of our paper. To summarize, the restrictive non-bipartite setting of (Rotenberg, Huleihel and Shayevitz, Planted Bipartite Graph Detection, IEEE TIT 2024) prevents them from articulating the new phrase transitions with respect to relative sizes of the two disjoint sets of vertices that constitute the bipartite graph as we derive in this work, specifically in Proposition 3. This is one of the primary contributions of our paper. Furthermore, their results are loose by log factors, which we are able to tighten up to constants.\n\n\n3. *Regarding novelty compared to the state of the art*\n\nThe Referee requested clarification regarding our paper's contributions in relation to the existing literature. We are happy to outline them more clearly here and hope this will address the Referee’s main concern.\n\n- We consider the problem of detecting a bipartite community of size $k_1 \\times k_2$ in a bipartite graph with two populations of size $n_1$ and $n_2$, respectively. We allow the parameters $k_1, k_2, n_1, n_2$ to assume arbitrary values--provided of course that $k_1 \\leq n_1$ and $k_2 \\leq n_2$. This very general setting goes far beyond the current literature, where the observed graph is most often non-bipartite, that is $n_1 = n_2$ and the community is non-bipartite as well, that is $k_1 = k_2$ (see e.g. [4], (Arias-Castro and Verzelen, *Community detection in sparse random networks*, AoS 2015)). A few works consider imbalanced settings, e.g. [15], which considers Gaussian data rather than Bernoulli matrices, but operates under the very restrictive setting $k_1 \\log(n_1/k_1) \\asymp k_2 \\log(n_2 / k_2)$ and also provides asymptotic results. The most closely related paper that we are aware of is [57], which considers arbitrary $k_1$ and $k_2$ but still $n_1 = n_2$, and obtains upper and lower bounds that do not match in all cases. They also do not propose any new tests compared to previous literature, therefore only obtaining suboptimal results. To the best of our knowledge, our paper is the first work to fully settle the **non-asymptotic rates** of community detection under any values of $k_1, k_2, n_1$ and $n_2$ by obtaining **matching upper and lower bounds in any case**. Our analysis reveals subtle phase transitions that, to the best of our knowledge, had not been established in previous work.  This level of generality requires substantially **new proof techniques and ideas**, and **entirely novel testing procedures** that we outline below and believe will be of independent interest to the community. \n     \n- Our lower bound on $\\delta^*$ stated in Theorem 1 is entirely novel and uses a very precise application of the second moment method. It requires several non-trivial lemmas for controlling the moment-generating function of the product of binomial random variables, and substantially departs from the lower bound strategies proposed in [15], [4] or [57].\n\n- Our upper bound stated in Theorem 2 is achieved by carefully combining three tests: A standard *total degree* test and two entirely novel tests referred to as the *truncated degree* test and the *max truncated degree* test. The two novel tests are defined using truncated non-linear functions of the adjacency matrix. We emphasize that our tests are non-trivial refinements of the truncated $\\chi^2$ test recently studied in the Gaussian sequence model [21, 40, 43, 19]. Indeed, substantial modifications of the truncated $\\chi^2$ test are needed to address two key challenges:\n     - Extending from the vector setting to the matrix setting, which requires careful Bonferroni-type corrections to control the type I error.\n     - Handling matrices whose entries are Bernoulli rather than Gaussian random variables, which require significant adjustments of the truncated $\\chi^2$ test to carefully manage the complex sub-poissonian tails of the binomial distribution.\n\n\nWe hope this discussion will convince the Referee of the novelty and significance of our results. We are happy to further revise the introduction or conclusion to make these points more prominent if the Referee believes this would benefit the reader."}, {"review_id": "Wg2w8ykHfm", "reviewer": "Reviewer_1bpB", "summary": "The authors consider the problem of detection between on the one hand: a bipartite Erdos-Rényi graph with bipartition sizes n_1, n_2 and probability of an edge p_0, and on the other hand a bipartite graph where the edge presence probability is, between two sets of respective sizes k_1 and k_2, elevated from p_0 to being larger than p_0+delta. Their objective is to determine, for a target risk level \\eta (defined in Eq(2)), necessary and sufficient conditions on the magnitude of the elevation parameter delta, for the existence of a test Delta that discriminates between the two hypotheses with risk at most \\eta.\n\nThey then provide a lower bound on the critical value of delta, given in theorem 1, below which no such test exists. Under additional Assumption 1 (which guarantees that the graph be sufficiently dense), they give in Theorem 2 an upper bound on the critical value of delta above which a sophisticated test succeeds. This upper bound is within a constant factor of the lower bound, so that under Assumption 1 the two theorems characterize the magnitude of the critical value of delta. \n\nFinally the authors discuss implications of their results. They show that these generalize previously known thresholds in a balanced setting, and that their result reveals a novel phase transition specific to the unbalanced bipartite case (proposition 3). \n\nA discussion of limitations and future directions concludes the paper.", "questions": "-At the bottom of page 3, \\eta is first mentioned while not being defined yet, you may want to fiw that.\n\n-Could you comment on the fact that the constant C discussed at the bottom of page 4 depends on \\eta? What would happen in a regime where eta goes to zero?\n\n-In statement of theorem 1, notation c_delta for the constant is a bit awkward, as it might lead the reader to believe that this constant does depend on delta. However this would not make sense. Please use an alternative notation.\n-On page 6, line 106, under what probability distribution is expectation taken? P_0?\n\n-In Eq(14), is the maximum over sets J_1?\n\n-Can you comment on the choice of thresholds h_i used in Theorem 2?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:The test setup considered is challenging, as the authors consider for alternative hypothesis a whole class of edge probabilities, specified by the elevation parameter delta. The result obtained is difficult, and it is interesting that it reveals a new phase transition for community detection specific to the unbalanced bipartite case. The underlying proof techniques seem powerful and delicate to use. The writing is good.", "was_revised": true, "final_justification": "After the discussion phase, I finally upgraded my rating to \"accept\": the paper is very solid, and even though it is of theoretical nature, its contribution is of interest to a significant subset of the NeurIPS comunity.", "rebuttal": "1. *At the bottom of page 3, \\eta is first mentioned while not being defined yet, you may want to fix that.*\n\nResponse: Thank you for pointing this out, we will make sure that $\\eta$ is well-defined in the camera-ready version of our paper.\n\n2. *Could you comment on the fact that the constant C discussed at the bottom of page 4 depends on \\eta? What would happen in a regime where eta goes to zero?*\n\nResponse: The constant $C$ will be increased as $\\eta$ decreases. In the non-asymptotic minimax framework that we work in, $\\eta$ is fixed between $0$ and $1$ prior to the subsequent analysis, and therefore we need not concern ourselves with $C$ tending to infinity. This framework is standard in the literature (see the references [10, 11, 15, 17, 18, 19, 21, 39, 43, 59], among others, in the current version of our paper). We do not allow for $\\eta = 0$, as it is not possible in a non-asymptotic setting to guarantee that the type 1 and 2 errors are identically 0. The case where $\\eta \\to 0$ is certainly of interest, but does not fit within our framework, as our goal is to provide non-asymptotic statistical guarantees. \n\n3. *In statement of theorem 1, notation $c_\\delta$ for the constant is a bit awkward, as it might lead the reader to believe that this constant does depend on delta. However this would not make sense. Please use an alternative notation.*\n\nResponse: Thank you for this note on notation. We agree with you and will replace $c_\\delta$ with $\\underline{c}$ in the camera-ready version of our paper.\n\n4. *On page 6, line 106, under what probability distribution is expectation taken? P_0?*\n\nResponse: Yes, this expectation is taken under $P_0$. We will add a subscript to the expectation notation to make this clear in the camera-ready version of our paper.\n\n5. *In Eq(14), is the maximum over sets J_1?*\n\nResponse: Yes, that is correct. The max truncated degree is constructed by scanning over subsets of size $k_1$ (or $k_2$) of the number of rows (or columns) and computing the average truncated degree statistics on each subset of indices. We will adjust the notation in the paper to improve clarity for the reader.\n\n6. *Can you comment on the choice of thresholds h_i used in Theorem 2?*\n\nResponse: We present precise choices of $h$ and $\\tau$ that achieve the optimal testing risk for each of the truncated degree tests in Section B of the supplement. We refer the Referee to our response to Reviewer QZpt for the precise values of $h$ and $\\tau$ that are used for each test. We will include these values in the camera ready version of our paper for clarity."}]

Author rebuttal:

Meta-review: The paper studies the problem of community detection in dense bipartite random graphs. More specifically, the authors analyze the following hypothesis testing problem: under the null hypothesis, the observed graph is drawn from a bipartite Erdős–Rényi distribution with connection probability $p_0$. Under the alternative hypothesis, there exists an unknown bipartite subgraph of size exactly $k_1 \times k_2$, in which edges appear with probability $p_1 = p_0 + \delta$, while all other edges outside the subgraph appear with probability $p_0$. The authors present minimax lower bounds and propose a test whose performance can be analyzed.

All reviewers acknowledged the soundness of the analysis. However, discussions in the rebuttal phase focused on assumptions, intuition, novelty, and computational challenges. These points should be incorporated into the paper. In particular:

The problem should be better motivated, as the authors currently do not mention any practical application.

The relevance of the problem should be discussed. At present, it seems rather narrow—partly because of the assumptions (dense regime), but mainly because of the objective itself: detecting whether there is a more connected set of nodes of size exactly $k_1 \times k_2$. Why is this specific formulation important?

The authors should provide a clearer explanation of why novel techniques are required for this problem, and explicitly outline the techniques they introduce.

The analysis is purely information-theoretic, meaning that computational aspects are not addressed. The authors should comment on the implementability of the proposed test and, if possible, include numerical experiments to support the theoretical findings.
Decision: Accept (poster)