Phase transition for detecting a small community in a large network
Authors: Jiashun Jin
Tracy Ke
Paxton Turner
Anru Zhang
Venue: ICLR 2023 poster (2023)
Keywords: community detection
degree-correct block model
global testing
planted clique
statistical-computational gap

Abstract: How to detect a small community in a large network is an interesting problem, including clique detection as a special case, where a naive degree-based $\chi^2$-test was shown to be powerful in the presence of an Erdös-Renyi (ER) background. Using Sinkhorn's theorem, we show that the signal captured by the $\chi^2$-test may be a modeling artifact, and it may disappear once we replace the Erdös-Renyi model by a broader network model.  We show that the recent SgnQ test is more appropriate for such a setting. The test is optimal in detecting communities with sizes comparable to the whole network, but has never been studied for our setting, which is substantially different and more challenging.  Using a degree-corrected block model (DCBM), we establish phase transitions of this testing problem concerning the size of the small community and the edge densities in small and large communities.  When the size of the small community is larger than $\sqrt{n}$, the SgnQ test is optimal  for it attains the computational lower bound (CLB), the information lower bound for methods allowing polynomial computation time. When the size of the small community is smaller than $\sqrt{n}$, we establish the parameter regime where the SgnQ test has full power and make some conjectures of the CLB. We also study the classical information lower bound (LB) and show that there is always a gap between the CLB and LB in our range of interest. 	

Published as a conference paper at ICLR 2023
PHASE TRANSITION FOR DETECTING A SMALL COMMUNITY IN A LARGE NETWORK
Jiashun Jin Carnegie Mellon University j jia sashun@stat. cmu. edu
Zheng Tracy Ke Harvard University zke@ fas. harvard.edu
Paxton Turner
Anru R. Zhang
Harvard University
Duke University anru. anru. 2hangg edu
paxtonturner fas harvard. edu
ABSTRACT
How detect small community in large network an interesting problem, including clique detection as special case, where a naive degree-based -²-test was shown be powerful in the presence of an Erdös-Renyí background. Using Sinkhorn's theorem, we show that the signal captured by the t-ttest may be a modeling artifact, and may disappear once we replace the Erdös-Renyi model by a broader network model. We show that the recent SgnQ test is more appropriate for such a setting. The test is optimal in detecting communities with sizes com- parable to the whole network, but has never been studied for our setting, which is substantially different and more challenging. Using a degree-corrected block model (DCBM), we establish phase transitions of this testing problem concerning the size of the small community and the edge densities in small and large commu- nities. When the size of the small community is larger than vn, the SgnQ test is optimal for it attains the computational lower bound (CLB), the information lower bound for methods allowing polynomial computation time. When the size of the small community is smaller than /n, we establish the parameter regime where the SgnQ test has full power and make some conjectures of the CLB. We also study the classical information lower bound (I.B) and show that there is always gap between the CLB and LB in our range interest.
INTRODUCTION
Consider undirected network with nodes and K communities. We assume is large and the network is connected for convenience. We are interested in testing whether K == or K >> and the sizes of some of the communities are much smaller than (communities
scientifically meaningful but mathematically hard to define; intuitively, they are clusters of nodes that have more edges "within" than "across" (Jin 2015 Zhao et 2012)). The problem is special case of network global testing, a topic that has received lot of attention (c.g.. Din et al. (2018) (021b)). However, existing works focused on the so-called balanced case, where the sizes of communities are the same order. Our case is severely unbalanced, where the sizes of some communities are much smaller than n (e.g., n²)..
The problem also includes clique detection (a problem of primary interest in graph learning (Alon et al. 1998 Ron & Feige, 2010)) as a special case. Along this line, Arias Crras-Castroo & Verzelen (2014); Verzelen & Arias-Castro (2015) have made remarkable progress. detail, they considered the problem of testing whether graph is generated from marammrre Erdōs-Rent Renyi model
two-parameter model: for any nodes 1 S í, < n, the probability that they have an edge equals if i, both are in small planted subset and equals otherwise. remarkable conclusion of these papers is: naive degree-basee -aased x2 2-ttest is optimal, provided that the clique size is in a certain range. Therefore, at first glance, it seems that the problem has been elegantly solved, at least to some extent.
Unfortunately, recent progress in network testing tells a very different story: the signal captured by the 2test may be modeling artifact. It may disappear once replace the models in Arits-Castro

---

Published as a conference paper at ICLR 2023
& Verzelen (2014); Verzelen &
(2013) by a properly broader model. When this happens, the X -tett will be asymptotically powerless in the whole range of parameter space.
We explain the idea with the popular Degree- Corrected Block Model (DCBM) (Karrer & Newmaan 2011). though it is valid in broader settings. Let R"." be the network adjacency matrix, where A(i,j) E f0, }} indicates whether there is edge between nodes i and j. 1 S i,j S n. By convention, we do not allow for self-edges, so the diagonals of A are always 0. Suppose there are K communities, CI,...,CR: For each node i, S S n, we use a parameter 0g to model the degree heterogeneity and π. to model the membership: when i E Ck. (e( = 1 if & = k and (t( otherwise. For a K x K symmetric and irreducible non-negative matrix P that models the community structure, DCBM assumes that the upper triangle of A contains independent Bernoulli random variables satisfying
P(A(i,)) = 1) = 0,0,m/PP.
1 isijs S
(1.1)
In practice, we interpret P(k,)) E) as the baseline connecting probability between communities is and 0,Y, 11 [TT, ( T....., Anl', and θ diag (0) = diag(O), .2, .2.....0))) 0,).
l. Write 0 = Introduce n x n matrices Q and W by s2 = III and W = A E []. We can re-write (1.1] as
A = Ω - diag((?) + W.
(1.2)
We call Ω the Bernoulli probability matrix and W the noise matrix. When 0, in the same community equal, DCBM reduces to the Stochastic Block Model (SBM) (Holland et al. 1983). When K the SBM reduces to the Rends model, where (2(i, j) take the same value for all 1 S i,j S n.
We first describe why the signal captured by the x2-test in Arias- Castro & Verzelen (2014); Verzelen & Arias-Castro 2013) is modeling artifact. Using Sinkhorn's 's matrix scaling theorem (Sinkhorn 1974). possible to build null DCBM with K that has no community structure and an alternative DCBM with K 2 2 and clear community structure such that the two models have the same expected degrees. Thus, we do not expect that degree-based test such as x2 can tell them apart. We make this Sinkhorn argument precise in Section 2.1 and show the failure of x² in Theorem 2.3
In the Erdös-Renyi setting in Arias-Castro & Verzelen (2144), the null has one parameter and the alternative has two parameters. In such a setting, we cannot have degree-matching In these cases, a naive degree-based tettt may have good power, but it is due to the very specific models they choose. For clique detection in more realistic settings, we prefer to use broader model such as the DCBM, where by the degree-matching argument above, the -tttsst is asymptotically powerless.
This motivates to look for different test. One candidate is the scan statistic [Bogerd et al. (202I) However, a sean statistic is only computationally feasible when each time we scan a very small subset of nodes. For example, if each time we only scan finite number of nodes, then the computational cost is polynomial; we call the test the Economic Scan Test (EST). Another candidate may come from the Signed-Polygon Polygon test family (Jin et al.) 2021b), including the Signed- Quadrilateral (SgnQ) as a special case. Let r = A1, 11,A,,, A1,, and A = A în- Define
Qn = En, 62, (dist) A in Aigis Asgia Args where the shorthand (dist) indicates we sum over distinct indices. The SgnQ test statistic is
S [Qn. 1
(1.3)
SgnQ is computationally attractive because it can be evaluated in time O(n² d), where d is the average degree of the network (Jin et al.) 2021b).
Moreover, it was shown in Jin et al. (2021b) that (a) when K 1 (the null case), vh, + NN 1), and (b) when K > and all communities are at the same order (i.c., a balanced alternative case), the SgnQ test achieves the classical information lower bound (LB) for global testing and so is optimal. Unfortunately, our case is much more delicate: the signal of interest is contained a community with size that is much smaller than n (e-g., n²),, so the signal can be easily overshadowed by the noise term of Qu. Even in the simple alternative case where we only have two communities (with sizes N and (n N)). it is unclear (a) how the lower bounds vary as N/n + 0, and especially whether there is a gap between the computation lower bound (CLB) and classical information lower bound (LB), and (b) to what extent the SgnQ test attains the CLB and is optimal.
In this work we M' to denote the transpose of a matrix or vector M.
2

---

Published as a conference paper at ICLR 2023
1.1 RESULTS AND CONTRIBUTIONS
We consider the problem of detecting a small community in the DCBM. In this work, we specifically focus on the case K 2 as this problem already displays a rich set of phase transitions, and we believe it captures the essential behavior for constant K > 1. Let N < n denote the size of this small community under the alternative. Our first contribution analyzes the power of SgnQ for this problem, extending results of Jin et al. (2021b) that focus on the balanced case. Let Y = (9)). In Section 2.2 define population counterpart f of À and let À X1 (92). We show that SgnQ has full power /1/ + oo, which reduces (aaa c)/ /nc + oo in the SBM case.
For optimality, we obtain a computational lower bound (CLB), relying on the low-degree polynomial conjecture. which a standard approach in studying CLB (c.g.. Kunisky et al. (2019). Consider a case where K = 2 and we have a small community with size N. Suppose the edge probability within the community and outside the community are and c, where a > c. The quantity (a (a-c)/v Ve acts as the Node-wise Signal-to-Noiie the CLB is completely determined by N and node-wise SNR; moreover, SgnQ matches with the CLB and is optimal. When N < VT,, the situation is more subtle: if the node-wise SNR (a c) c//ve (weak signal case), we show the problem is computationally hard and the LB depends on N and the node-wise SNR. If (a c)/ Vc > n/1/2 (strong signal case), then SgnQ solves the detection problem. In the range < (a c)--c//vo c)/ < n 1/2 (moderate signal case), the CLB depends on not only N and the node-wise SNR but also the background edge density c. In this regime, we make conjectures of the CLB, from the study of the aforementioned economic scan test (EST). Our results are summarized in Figure and explained in full detail in Section 2.7
Ratio (SNR) for the detection problem When N >> vn, we find that
O
We also obtain the classical information lower bound (LB), and discover that as N/n + 0, there is big gap between CLB and LB. Notably the LB is achieved by an (inefficient) signed scan test. In the balanced case in Jin et al. (202Tb), the SgnQ test is optimal among all tests (even those that are allowed unbounded compu- tation time), and such a gap does not exist.
P+
Strong signal
Moderate signal
Weak signal
N
Statistically impossible
We also show that that the naive degree-based -ttte is asymptotically powerless due to the aforementioned degree-matchine matching phenomenon.
SgnQ
N V
0.5
Our statistical lower bound, computational lower bound, and the powerlessness of x² based on sggree-matching are also valid for all K since any model with K 2 2 contains K = 2 as a special case. We also expect that our lower bounds are tight for these broader models and that our lower bound constructions for K = represent the least favorable cases when community sizes are severely unbalanced.
Computationally impossible
Figure 1: Phase diagram ((a c)/ve= n- and N = n 1-9).
Compared to Verzelen& & Arias-Castra (2015); Arias Castro & Verzelen (2014), we consider network global testing in
realistic setting, and show that optimal tests there (i.c., naive degree-based
x2 test) may be asymptotically powerless here. Compared with Bogerd et al. (021), our setting is very different (they considered a setting where both the null and alternative are DCBM with K 1). Compared to the study in the balanced case (e.g., Jin et al. 2018 202 (221b): Gao & Lafferty (001))) our study is more challenging for two reasons. First, in the balanced case, there is no gap between the UB (the upper bound provided by the SgnQ test) and LB, so there is no need to derive the CLB, which is usually technical demanding. Second, the size of the smaller community can get as small as nf, where s > 0 is any constant. Due this imbalance in community sizes, the techniques of Jin et al. (2021b) do not directly apply. As a result, our proof involves the careful study of the 256 terms that compose SgnQ, which requires using bounds tailored specifically for the severely unbalanced case.
Note that the node-wise SNR captures the ratio of the mean difference and standard deviation of Bernouli(a)) versus Bernouli(c)) which motivates our terminology.
3

---

Published as a conference paper at ICLR 2023
Our study of the CLB is connected to that of Hajek et al. (2015) in the Erdös-Reny setting of Casts-Castro& & Verzelen (2014). Hajek et al. (2015) proved via computational reducibility that the naive ttest is the optimal polynomial-time test (conditionally on the planted clique hypothesis). We also note work of Chen & Xu (016) that studied a K-cluster generalization of the Erdös-Renyi model of AriasCCastro & Verzelen (2014); Verzelen & Arias-Castro (2015) and provided conjectures of the CLB. Compared to our setting, these models are very different because the expected degree profiles of the null and alternative differ significantly. In this work we consider the DCBM model, where due to the subtle phenomenon of degree matching between the null and alternative hypotheses, both CLB and LB are different from those obtained by (Hajek et al. (2015).
Notations: We use 1, to denote n-dimensional vector of ones. For a vector 0 = -01,.... 0n). diag(( (0) is the diagonal matrix where the i-th diagonal entry 0,. For a matrix E Raxx, diag(S)) is the diagonal matrix where the i-th diagonal entry is S2 i). For a vector 0 E IR", 0 Omar max .f.,.... .. 6,) and 0mnnn = min 0n) For two positive sequences {a,) and (bn), J. we
write an x bn if e1 an/bn S eg for constants 0 C1 > 0. We say an bn if (an/bi, (b, = (1).
2 MAIN RESULTS
In Section 2.1
following our discussion on Sinkhorn's theorem in Section T we introduce calibrations (including conditions on identifiability and balance) that are appropriate for severely unbalanced DCBM and illustrate with some examples. In Sections 2.2 2.3] we analyze the power of the SgnQ test and compare with the -test. In Sections 2.5 2 we discuss the information lower bounds (both the LB and CLB) and show that SgnQ test is optimal among polynomial time tests, when N >> vn. In Section 2.6 we study the EST and make some conjectures of the CLB when N < vn. In Section 2.7 we summarize our results and present the phase transitions.
2.1
DCBM FOR SEVERELY UNBALANCED NETWORKS: IDENTIFIABILITY, BALANCE METRICS, AND GLOBAL TESTING
In the DCBM 1.1 1.2 Ω O It is known that the matrices (9, II, P) are not identifiable.
One issue is that [I. are only unique up to a permutation: for a K x K permutation matrix Q. is usually neglected. A bigger issue is that, (e, P) are not uniquely defined. For example, fixing a positive diagonal matrix
IPII= (QI (IQ)) This issue is easily fixable in applications
DE DERKXE x let P = DPD and O* = diag 01 .,...., 0%) 1 1 < K. It is seen that OIIPII' I'''"''''* so P)) are not uniquely defined.
where 0ī 0:/ D(k, k) if i E Cs.
To motivate our identifiability condition, we formalize the segree-matching argument discussed in the introduction. Fix (0, P) and let h = (h...... hrg) and h4 > 0 is the fraction of nodes in community k. 1 < k < K. By the main result of (Sinkhorn (1974), there is a unique positive diagonal matrix k. Consider a pair of two DCBM, a null with K = and an alternative with K > 1, with parameters Ω = 1,,10 = 06' and 52" (i, = 0 0,0"=²' n. P with 0: = dg0, 0, if i E CR. 1 S S K, respectively. Direct calculation shows that node has the same expected degree under the null and alternative.
D diag(d1, ... dx) such that DPDh
There are many ways to resolve the issue. For example, in the balanced case (e.g..Jin et al. (202bb) 2022)), we can resolve it by requiring that P has unit diagonals. However, for case, this is inappropriate. Recall that, in practice. P(k, E') represents as the bascline connecting probability between community i and f. If we forcefully rescale P to have unit diagonal here, both (P, +) lose their practical meanings.
Motivated by the megteeenatccing argument, we propose identifiability condition that is more appropriate for the severely unbalanced DCBM. By our discussion in Section [ for any DCBM with Bernoulli probability matrix Ω we can always use Sinkhorn's 's theorem to define (O, P) (while IT is unchanged) such that for the new (9, P). θ = IIIIII and Ph x 1k. where h = (hi....,ha hk) and h& > is the fraction of nodes in community identifiability condition (which is more appropriate for our case):
< k < K. This motivates the following
||0]] = n,
Ph x 1x, where hgg is fraction of nodes in Cr. S.
(2.1)
Lemma 2.1. For any Ω that satisfies the DCBM [1. and has positive diagonal elements, we can always find (e, I1, P) such that Q = IIIPI' θ and 2.1 holds. Also, any (0, P) that satisfy
Ω = O and 2. are unique.
4

---

Published as a conference paper at ICLR 2023
Moreover, for network balance, the following two vectors in I natural metrics:
d (110111) 'r''ee,
9 = (1001))-ir'e e
(2.2)
In the balanced case (c.g.. Jin et al. (2021b 2022)), we usually assume the entries of d and are at the same order. For our setting, this is not the case.
Next we introduce the null and alternative hypotheses that we consider. Under each hypothesis, we impose the identifiability condition (2.1.
and h 1, P is scalar (say, = a). and Ω = ad0' satisfies ||0||1 by (2.I). The expected total degree is (110 [ - [|0133)
General null model for the DCBM. When
0| i n²a
under mild conditions, so we view a as the parameter for network sparsity. In this model, = = 1.
Alternative model for the DCBM We assume K and that the sizes of the two communities, Co and Ci, are (n2 N) and N, respectively. For some positive numbers a, b, c, we have
0,0, a, P = C ] and (). = 0,0, C, 0,0, b.
if E C₁, i, E Co.
(2.3)
otherwise.
In the classical clique detection problem (e.g., Bogerd et al. (202T); ). and are the baseline probability where two nodes have an edge when both of them are in the clique and outside the clique, respectively. By (2.I), ae + b(1 - c) be c(1 E) if we write N/n. Therefore.
b = (c(n - N) - aNV)/(n 2N).
(2.4)
Note that this is the direct result of Sinkhorn's is theorem and the parameter calibration we choose, not condition we choose for technical convenience. Write d (dg d1 and g = (gu. 91)' It is seen that do 1 d1. 9o
9o. d1 |0|| Eiec, 1,, and 91 ||0| - 1 08. If all 0 are the same order, then d1 x 91 (N/n) and do 9o We also observe that b c c (ae) which makes the problem seem very close to Arias Castro & Verzelen (2014); Bogerd et al. (021
although in fact the problems are quite different.
Extension. An extension of our alternative is that, for the K communities, the sizes of m of them are at the order of N, for an N < n and an integer m, S m < K, and the sizes of remaining (K - m) are at the order of n. In this case, m entries of d are (NN/n) and other entries are O(1); same for g.
2.2 THE SGNQ TEST: LIMITING NULL, P- VALUE, AND POWER
In the null case, K = 1 and we assume Ω = a00', where ||0|| = n. As n oo, both (a,0) may vary with n. Write max = |10|| 30. We assume
na - xo, and
o02 max log(n2a) + 0.
(2.5)
The following theorem is adapted from Jin al. (0221) and the proof is omitted.
Theorem 2.1 (Limiting null of the SgnQ statistic). Suppose the null hypothesis is true and the regularity conditions [2. and 2.5) hold, As n + 0o, the N(, 1) in law.
We have two comments. First, since the DCBM has many parameters (even in the null case), it is not an easy task to find a test statistic with a limiting null that is completely parameter free. For example, if we use the largest eigenvalue of A as the test statistic, it is unclear how to normalize so have such a limiting null. Second, since the limiting null completely explicit, we can approximate the (one-sided) p-value of vi, by (P 1) 2 v.)) The p-values are useful in practice, as we show in our numerical experiments.. For example, using a recent data set on the statisticians' publication (Ji al.] 2022). for each author, we can construct an ego network and apply the SgnQ test. We can then use the p-value to measure the co-authorship diversity of the author. Also, in many hierarchical community detection algorithms (which are presumably recursive, aiming to estimate the tree structure of communities), we can use the p-values to determine whether we should further divide sub-community in each stage of the algorithm (e.g. J et al. (002))
The power of the SgnQ test hinges on the matrix Ω Ω (1,,0,,) 1, By basic algebra,
ύ= OIPi'e, where P P (d' (d'Pd))'Pdd''
(2.6)
Let X₁ be the largest (in magnitude) eigenvalue of Ω. Lemma 2.2 is proved in the supplement.
5

---

Published as a conference paper at ICLR 2023
Lemma 2.2. The rank and trace of the matrix S are (K- 1) and [0]]'dia((P)s respectively. When K 2, X1 trace([)) 1 (ac (2)(1 / (ad} 2bdgd1 + cdi).
As result of this lemma, we observe that in the SBM case, h and thus \ X2 N(a c). To see intuitively that the power of the SgnQ test hinges on X /A, we heuristically replace the terms of SgnQ by population counterparts, we obtain
On =
Σ d (distinct)
Ariss Aisis Auss s trace( mpn'(*) )+ = trace (f2*) = X1.
We now formally discuss the power of the SgnQ test. We focus on the alternative hypothesis in Section 2.1 Let d (d,, do) and y = 9o), be as (2.2). and let 0max,0 = maxseco 0; and
8 max,, 1 max4e, 0,. Suppose
d 4 x N/n,
aB? 2 = ((),
cn + 00,
Smax, log(n" c) - 0.
(2.7)
These conditions are mild. For example, when 0/'s are at the same order, the first inequality in 2.7
automatically holds, and the other inequalities in (2.7 hold if a I C for absolute constant C >
en - x0, and è clog(n) + O.
1, let 2, > be the value such that P(N(0.1) 1) > 2,)) test rejects the null if and only if th 2 Eg, where u/ is as in 1 Theorem (.2 and Corollary 2.1 are proved the supplement. Recall that our alternative hypothesis is defined Section 2.1 By power we mean the probability that the alternative hypothesis is rejected, minimized over all possible alternative DCBMs satisfying our regularity conditions.
Fixing 0
The level-x SgnQ
Theorem 2.2 (Power of the SgnQ test). Suppose that (2. holds, and let K (0, 1). Under the alternative hypothesis, if (Ail/V/i - :o, the power of the level-k SgnQ test tends to
Corollary 2.1. Suppose the same conditions of Theorem 2.2 hold, and additionally Omax S CC0min so all 0, are at the same order. In this case, x1 = en and A1 x N(a - c). and the power of the level-x SgnQ test tends 1 if (aa c)/ /cn Do.
In Theorem 2.2 and Corollary 2.1 if K. Fin and K,, 0 slowly enough, then the results continues to hold, and the sum of Type and Type II errors of the SgnQ test at level-K,, + O.
The power of the SgnQ test was only studied in the balanced case (Jin et al. 2021b), but our setting is a severely unbalanced case, where the community sizes are at different orders as well as the entries of d and In the balanced case, the signal-to-noise ratio of SgnQ is governed by /22// Vol/V,,, but in our setting, the signal-to-noie ratio is governed by | / The proof is also subtly different. Since the entries of P are different orders, many terms deemed negligible in the power analysis of the balanced case may become non-negligible in the unbalanced case and require careful analysis.
2.3 COMPARISON WITH THE NAIVE DEGREE -TEST
Consider setting where Ω 101,, = a00' under the null and Ω OITPIT' under the alternative, and 2.1 holds. When 0 is unknown, it is unclear how to apply the >tttest: the null and need use the degrees estimate 0 first. As a result, the resultant x2 -statisstic may be trivially 0. Therefore, we consider simpler SBM case where 0 1, In this case, f Il, and IIIII' and the null case only has one unknown parameter a. Let yi be the degree of node i, and let å [n(n 1)]- A1, The x² statistic is
case has n unknown parameters 01, ...... .,. Oz.
X, = Σ (u
a)).
(2.8)
It is seen that as na - 00 and + 0, -X,, - N(0, 1) in law. For a fixed level
E (0, 1), consider the -tets that rejects the null if and only if (Xn, 2n > 2x. Let ag (1,, The power of the 2tetest hinges on the quantity (nan) (I
nao 1| Tnan)-"|[TPh (h'Ph) ',, 1, 2 = 0, if Ph x 1k. The next theorem is proved in the supplement.
Theorem 2.3. Suppose 0 1, and (2.7) holds. If //l// - Do under the alternative hypothesis, the power of the level-x. SgnQ test goes to 1, while the power of the level-k x" 2-ess goes to

---

Published as a conference paper at ICLR 2023
2.4 THE STATISTICAL LOWER BOUND AND THE OPTIMALITY OF THE SCAN TEST
For lower bounds, it is standard to consider random membership DCBM (Jin et al. 2021b). where ||0|| n, P is as 2.3 2.4 and for number N < n, [Ti, T2. ................................ Tn. satishes
T2 = ( X,),
where X, are iid Bernoulli(e) with E = N/n.
(2.9)
Theorem 2.4 (Statistical lower bound). Consider the null and alternative hypotheses of Section 2.7 and assume that (2.9) is satisfied, max I mimn and Ne/ log oc. 1f Vf c)/ /C 0, then for any test, the sum of the type-I and lype-ll errors tends to 1.
To show the tightness of this lower bound, we introduce the signed scan test, by adapting the idea in Arias- & Verzelen (2014) from the SBM case the DCBM case. Unlike the SgnQ test and the x"-test, signed scan test is not polynomial time test, but it provides sharper upper bounds. Let f be the same as in (1.3). For any subset S (1.2.... .......................... n2. let 1g RR be the vector whose ith coordinate is l E S}. Define the signed scan statistic
max Qec SC(L2...,)/||IIE
1's(A fs
(2.10)
Theorem 2.5 (Tightness of the statistical lower bound). Consider the signed scan test (2.00) that rejects the null hypothesis if &sc > La- Under the assumptions of Theorem 2.4 if VN - c)/ //l//clooe cllo(n) + co, then there exists a sequence tn such that the sum of type I and rype Il errors of the signed scan test tends to O.
By Theorems 2.4 and Corollary 2.1 the two hypotheses are asymptotically indistinguishable if (Naac)/ 0, and asymptotically distinguishable by the SgnQ test if N(a-c)/ / co. Therefore, the lower bound is sharp. up to log-factors, and the signed scan test is nearly optimal. Unfortunately, the signed scan test is not polynomial-time computable. Does there exist a polynomial- time computable test that is optimal? We address this in the next section.
2.5 THE COMPUTATIONAL LOWER BOUND
Consider the same hypothesis pair as in Section 2.4 where K 2, P is as in (2.4 and II is as in (2.9). For simplicity, we only consider SBM, i.e., 0; = 1. The low-degree polynomials argument emerges recently as a major tool to predicting the average-Case computational barriers in a wide range of nigh-dimensiona problems (Hopkins & Steurer 2017 Hopkins et al. 2017). Many powerful methods, such as spectral algorithms and approximate message passing, can be formulated as functions of the input data, where the functions are polynomials with degree at most logarithm of the problem dimension. In comparison to many other schemes of developing computational lower barriers, the low-degree polynomial method yields the same threshold for various average-case hardness problems, such as community detection the SBM (Hopkins & Steurer 2017) and (hyper)- planted clique detection (Hopkins 2018 Luo & Zhang 2022). The foundation of the low-degree polynomial argument is the following low-degree polynomial conjecture (Hopkins et al., 2017):
Conjecture 2.1 (Adapted from Kunisky et (2019). Let P., and Qn denote a sequence of proba- bility measures with sample space Rnn where k O(1). Suppose that every polynomial f of degree Ollog n) with f2 = is bounded under P,, with high probability as n. - oo and that some further regularity conditions hold. Then there is no polynomial-tim test distinguishing P.. from Q with type and type II error tending to as n + xc.
We refer to Hopkins (2018) for a precise statement of this conjecture's 's required regularity conditions. The low-degree polynomial computational lower bound for our testing problem is as follows.
Theorem 2.6 (Computational lower bound). Consider the null and alternative hypotheses in Section 2. and assume 0g = 1 and (.9) holds. As n + DC, assume e < a, e < 1-8 for constant 8 > 0, N <
n/3, D O)ogn), and lim sup { [Iogn vn + logn 4 (VD/2 1 llg
a=c } 0.
For any series of degree-D polynomials on A R. whenever EH, on (A) = O, VarH, (6. (A) 1.
we must have EH, on (A) = o(1). This implies if Conjecture 2.7 is true, there is no consistent polynomial- -imme lest for this problem.
7

---

Published as a conference paper at ICLR 2023
Figure 2: Left: Null distribution of SgnQ (n 500). Middle and right: Power comparison of SgnQ and x2 (n 100, N = 10, 50 repetitions). We consider a 2-community SBM with P1 = a, P22 0.1, P12 = 0.1 (middle plot) and P12 an an-[a+00. 10.10.) (right plot, the case of degree matching).
By Theorem 2.6 if both (a-c)/ve and N(a c)/ + O. the testing problem is computa- tionally infeasible. The region where the testing problem is statistically possible but the SgnQ test loses power corresponds to (a c)/Vcr + O. If N ž vn, Theorem 2.6 already implies that this is the computationally infeasible region; other words, SgnQ achieves the CLB and optimal. If N ol (), SgnQ solves the detection problem only when (a c)/ //vC > n//2 i.e. when the node-wise SNR is strong, We discuss the case of moderate node-wise SNR in the next subsection.
2.6 THE POWER OF EST, AND DISCUSSIONS OF THE TIGHTNESS OF CLB
When = = and (a ()-o + oc both hold, the upper bound by SgnQ does not match with the CLB. It is unclear whether the CLB is tight. To investigate the CLB in this regime, we consider other possible volynomial-time tests. The economic scan test (EST) is one candidate. Given fixed (w) positive integers and e, the EST statistic is defined to be ΦEST supis So Σn,es Aij. and the
d EST is defined to reject if and only if EST 2 EST can be computed in time Onn"), which is
polynomial time. For simplicity, we consider the SBM, i.c. where 1n and a specific setting of parameters for the null and alternative hypotheses.
Theorem 2.7 (Power of EST). Suppose 3 E [1/2, 1) and 0 < w < 5 1 are fixed constants. Under the alternative, suppose = 1., (.9) holds, N = n-13, a = n and = n Under the null, suppose 0- 1n and errors of the EST with and satisfying w/(1 3) < v/e < 8 tends to 0.
(n) + b(1 N/n). lfw/(1
3) < 6, the sum of type I and type II
Theorem 2.7 follows from standard results in probabilistic combinatorics Alon & Spencer 2016).
conjectured Bhaskara al. (2010) that EST attains the CLB the Erdös-Renyi setting considered by AAiia- Castro & Verzelen (2014); Verzelen & Arias-Castra 2015). This suggests that the CLB Theorem 2.6 is likely not tight when N o(vn) and (a
Ve + oo. However, this is not because our inequalities in proving the CLB are loose. A possible reason is that the prediction from the low-degree polynomial conjecture does not provide tight bound. It remains an open question whether other computational infeasibility frameworks provide tight CLB in our problem.
2.7 THE PHASE TRANSITION
We describe more precisely our results in terms of the phase transitions shown in Figure I] Consider the null and alternative hypotheses from Section 2.1 For illustration purposes, we constants 3 E (0, 1) and 7 E R and assume that N = n - and (a - -c)-c// c)/vc ?? In the two-dimensional space of (7, 3), the region of B > 1/2 and < 1/2 corresponds to that the size of the small community is > /ni and n)) respectively. and the regions of 7 > 0. -1/1/2 < < O and < -1/2 correspond to 'weak node-wise signal', 'moderate node-wise wise signal,' and the 'strong node-wise signal', , respectively. See Figure By our results in Section 2.4 the testing problem is statistically impossible 3 27 > (orange region). By our results in Scction 2.2 SgnQ has a full power if 8 + 1/2 (blue region). Our results in Section 2.5 state that the testing problem is computationally infeasible if both y > 0 and B + 7 > 1/2 (green and orange regions). Combining these results, when 3 < 1/2, we have complete understanding of the LB and CLB.
8

---

Published as a conference paper at ICLR 2023
3 NUMERICAL RESULTS
Simulations. First in Figure (left panel) we demonstrate the asymptotic normality of SgnQ under a null of the form Ω 00', where Og are i.i.d. generated from Pareto(4, 0.375). Though the degree heterogeneity is severe, SgnQ properly standardized is approximately standard normal under the null. Next in Figure 2 we compare the power of SgnQ in an asymmetric and symmetric SBM model. As our theory predicts, both tests are powerful when degrees are not calibrated in each model, but only SgnQ is powerful in the symmetric case. We also compare the power of SgnQ with the scan test to show evidence of a matistical-computatie
gap. We relegate these experiments to the supplement.
Real data: Next we demonstrate the effectiveness of SgnQ in detecting small communities in coauthorship networks studied in et al. (022). In Example I, we consider the personalized network of Raymond Carroll, whose nodes consist of his coauthors for papers a set of 36 statistics journals from the time period 1975 2015. An edge is placed between two coauthors if they wrote paper in this set of journals during the specified time period. The SgnQ p-value for Carroll's personalized network Caarrlll is 0.02, which suggests the presence of more than one community. In et al. (2022).
the authors identify a small cluster of coauthors from a collaboration with the National Cancer Institute. We applied the SCORE community detection module with K = 2 (c.g. [Ke & Jin (2022)
and obtained a larger community Gearoll of size 218 and a smaller community Cāarroll of size 17. Precisely, removed Carroll from his network, applied SCORE on the remaining giant component, and defined Glarrll to be the complement of the smaller community. The SgnQ p-values in the table below suggest that both Ga and Ga are tightly clustered. Refer to the supplement for a visualization of Carroll's 's network and its smaller community labeled by author names. In Example 2, we consider three different coauthorship networks Gold. Grecent. and Gnw corresponding time periods (i) 1975-1999 1997, (ii)
and (iii) 2005-2015 for the journals AoS, Bka, JASA, and JRSSB. Nodes are given by authors, and an edge is placed between two authors if they coauthored at least one paper in one of these journals during the corresponding time period. For each network, we perform a similar procedure as in the first example. First we compute the SgnQ p-value, which turns out to be s 0 (up to 16 digits of precision) for all networks. For each i E fold, recent, new), we apply SCORE with K = 2 to G; and compute the SgnQ p-value on both resulting communities, let us call them G. and G.- We refer to the table below for the results. For Gald and Grecent. SCORE with K = 2 extracts a small community. The SgnQ p- p-value further supports the hypothesis that this small community is well-connected. In the last network, SCORE splits Gnew into two similarly sized pieces whose p-values suggests they can be split into smaller subcommunities.
Examplc
Network
Size
SgnQ p-value
Communitics
Sizes
SgnQ p-values
Geomol
235
0.02
(a Gramon)
(218, 17)
(0.134, 0.682)
2
Goid
2647
0
(G) Cld G
(2586, 61)
(0, 0.700)
Grecen
2554
Grecmms C1 (nonee) (2540,14)
(0, 0.759)
Gnen
2920
0
(G C
(1685,1235)
(0, 0)
Global testing is a fundamental problem and often the starting point of a long line of research. For example, in the literature of Gaussian models, certain methods started as a global testing tool, but later grew into tools for variable selection, classification, and clustering and motivated many researches _g.,Doooho & Jin 2004 2015)). The SgnQ test may also motivate tools for many other problems, such as estimating the locations of the clique and clustering more generally. For example, in Jin et al. (2022), the SgnQ test motivated tool for estimating the number of communities (see also Ma et al. (222I). ). SgnQ is also extendable to clique detection in a tensor (Yuan et al. 2021 Jiin al. 2222 la and for network change point detection. The LB and CLB we obtain in this paper are also useful for studying other problems, such as clique estimation. If you cannot tell whether there is clique in the network, then it is impossible to estimate the clique. Therefore, the LB and CLB are also valid for the clique estimation problem (Alon et al. 1998 Ron & Feige 2010).
Discussions:
The limiting distribution of SgnQ is (O. 1). This is not easy to achieve if we use other testing ideas, such as the leading eigenvalues of the adjacency matrix: the limiting distribution depends on many unknown parameters and is hard to normalize (Liu et al., 2019). The p-value of the SgnQ test is easy to approximate and also useful in applications. For example, we can use it to measure the research diversity of a given author. Consider the ego sub-network of an author in a large co- co-authorship or citation network. A smaller p-value suggests that the ego network has more than 1 communitiy and has more diverse interests. The p-values can also be useful as a stopping criterion in hierarchical community detection modules.
9

---

Published as a conference paper at ICLR 2023
Acknowledgments. We thank the anonymous referees for their helpful comments. We thank Louis
Cammarata for assistance with the simulations in Section A.3. J. Jin was partially supported by NSF grant DMS-2015469, Z.T. Ke supported in part by NSF CAREER Grant DMS-1943902. A.R.
Zhang acknowledges the grant NSF CAREER-2205744
REFERENCES
Noga Alon and Joel H Spencer. The probabilistic method. John Wiley & Sons, 2016.
Noga Alon, Michael Krivelevich, and Benny Sudakov. Finding a large hidden clique in a random graph. Random Structures & Algorithms, 13(3-4):457-466 1998.
Ery Arias-Castro and Nicolas Verzelen. Community detection in dense random networks. The Annals of Statistics, 42(3):940-969, 2014.
Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, and Aravindan Vijayaraghavan. Detecting high log- degddenit::s:: an o (n 1/4) approximation for densest k-subgraph. In Proceedings of the secty- ACM symposium Theory of computing, pp. 201-210, 2010.
Kay Bogerd, Rui M Castro, Remco van der Hofstad, and Nicolas Verzelen. Detecting a planted community in an inhomogeneous random graph. Bernoulli, 27-2):1559-1188 2021.
Yudong Chen and Jiaming Xu. Statistical
Statisticllccopputaiie computational tradeoffs in planted problems and submatrix localization with growing number of clusters and submatrices. The Journal of Machine Learning Research, 17(1):882-995 2016.
David Donoho and Jiashun Jin. Higher criticism for detecting sparse heterogeneous mixtures. The Annals of Statistics, (2(3):962-944 2004.
David Donoho and Jiashun Jin. Special invited paper: Higher criticism for large-scale inference, especially for rare and weak effects. Statistical Science, pp. 1-25, 2015.
Chao Gao and John Lafferty. Testing for global network structure using small subgraph statistics. 1oX1v:7110000800 2017.
Bruce Hajek, Yihong Wu, and Jiaming Xu. Computational lower bounds for community detection on random graphs. In Conference on Learning Theory, pp. 899-928. PMLR, 2015.
Paul W. Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Soc. Netw., 5(2):109 137, 1983.
Samuel B Hopkins and David Steurer. Efficient bayesian estimation from few samples: community detection and related problems. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 390. IEEE, 2017.
Samuel B Hopkins, Pravesh Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, and David Steurer. The power of sum-of-squares for detecting hidden structures. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 720-731. IEEE, 2017.
Samuel Brink Klevit Hopkins. Statistical inference and the sum of squares method. 2018.
Pengsheng Ji, Jiashun Jin, Zheng Tracy Ke, and Wanshan Li. Co-citation and co-authorship networks for statisticians (with discussions). J. Bus. Econ. Statist., 40(2), 2022.
Jiashun Jin. Fast community detection by SCORE, Ann. Statist., 43(1):57-89, 2015.
Jiashun Jin, Zheng Tracy Ke, and Shengming Luo. Netwok global testing by counting graphlets. 35th International Conference on Machine Learning, 2018.
Jiashun Jin, Zheng Tracy Ke, and Jiajun Liang. Sharp impossibility results for hyper-graph testing. Advances in Neural Information Processing Systems, 34:7220-7231, 2021a.
Jiashun Jin, Zheng Tracy Ke, and Luo. Optimal adaptivity of signed-polygen statistics for network testing. Ann. Statist., 49(6):440 3433, 2021b.
10

---

Published as a conference paper at ICLR 2023
Jiashun Jin, Zheng Tracy Ke, Shengming Luo, and Minzhe Wang. Optimal estimation of the number of network communities. J. Amer. Statist. Assoc., pp. 1-16, 2022.
Brian Karrer and Mark EJ Newman. Stochastic blockmodels and community structure in networks. Physical review E, 83(1)011107, 2011.
Zheng Tracy Ke and Jiashun Jin. The score normalization, especially for highly heterogeneous
network and text data. arXiv preprint arXiv: 2022,
Dmitriy Kumisky, Alexander S Wein, and Afonso Bandeira. Notes computational hard- ness of hypothesis testing: Predictions using the low-degree likelihood ratio. arXiv preprint arXiv: 2019.
Yan Liu, Zhiqiang Hou, Zhigang Yao, Zhidong Bai, Jiang Hu, and Shurong Zheng. Community detection based on the lo convergence of cigenvectors in dcbm. arXiv preprint arXiv:1906.06113, 2019.
Yuetian Luo and Anru R Zhang. Tensor clustering with planted structures: Statistical optimality and computational limits. The Annals of Statistics, 50(1):584-6133 -13,-613, 2022.
Shujie Ma, Liangjun Su, and Yichong Zhang. Determining the number of communities in degree- corrected stochastic block models. Journal of Machine Learning Research, 22(69):1-63, 2021.
Dorit Ron and Uriel Feige. Finding hidden cliques in linear time. Discrete Mathematics & Theoretical Computer Science, 2010.
Richard Sinkhorn. Diagonal equivalence to matrices with prescribed row and column sums. Proc. Amer. Math. Soc., (2):195-198, 1974.
Nicolas Verzelen and Ery CastsoC Community detection in sparse random networks. The Annals of Applied Probability, 25(6):3465-33 346--510, 2015.
Mingao Yuan, Ruiqi Liu, Yang Feng, and Zuofeng Shang. Testing community structures for hyper- graphs. Ann. Stafist. (to appear), 2021.
Yunpeng Zhao, Elizaveta Levina, and Zhu. Consistency of community detection in networks under degree-corrected stochastic block models. Ann. Statist., 40(4):2266-22)) 2292, 2012.


Reviews:
[{"review_id": "lMdvkqEfZ8", "reviewer": "Reviewer_JaWW", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers community detection with unbalanced communities. Specifically, they consider the hypothesis testing problem on the degree-corrected block model, which is to distinguish whether a graph is generated from a null model with one community or an alternative model with unbalanced communities. \n\nThey show phase transitions of this testing problem. When the size of the small community is larger than $\\sqrt{n}$, they show that the SgnQ test (Jin et al. 2021) is optimal. They show the matching computational lower bound in this case. When the size of the small community is smaller than $\\sqrt{n}$, they show the parameter regime where the SgnQ test works.", "summary_of_the_review": "Overall, this paper is very interesting. However, the main techniques to make the SgnQ test work for the unbalanced community detection is unclear to me since it is not well explained in the main paper. ", "strength_and_weaknesses": "Strengths:\n1. The small community detection problem is well-motivated. They show the naive degree-based $\\chi^2$ test is powerless for some scenarios. \n2. They provide the phase transitions for this testing problem. The unbalanced community detection is harder than the balanced version. They show SgnQ test still works for unbalanced community detection in some regimes.\n\nWeaknesses:\n1. Does the identifiable issue only happen for the degree-corrected block model? I think it would also hold for the stochastic block model.   \n2. I think some explanations like general settings with more than two communities and normalization in section 2.1 are not helpful. It makes the setting too complicated to follow. \n3. Although it is mentioned it is not easy to analyze the SgnQ test in the unbalanced setting, I think it would be very helpful to see a more intuitive explanation of how the analysis works.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "LPy--mGyTbR", "reviewer": "Reviewer_dBYC", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies phase transition for detecting communities under the degree-corrected block model (DCBM). The motivation is that chi-square test is not good for DCBM because of artifacts, so they use the the Signed-Quadrilateral (SgnQ) instead. The authors provide the SgnQ efficient regime, the computationally infeasible regime, as well as the statistically impossible regime for the model. Some simulations and experiments are included.", "summary_of_the_review": "The technical novelty of this paper is unclear. The writing can be hard to follow, especially in the introduction.", "strength_and_weaknesses": "- I don't know how technically novel this paper is. A lot of analysis are similar to those in [Arias-Castro & Verzelen], [Ji et al.], except considering on an arguably more general model DCBM. The authors highlight in the introduction, that their problem is more challenging because they need to consider the computational gap. That is not entirely new because it is well-studied for the SBM (e.g. [1]). Could the authors highlight their technical novelties? What can other researchers learn from this paper if they want to work on similar models?\n\n- Section 2.5: Why we only consider the case of SBM instead of more general cases here? Is it because of any difficulty in analysis?\n\n- Figure 2: How should I interpret the white region (\\beta > 0.5)? Is it because of any difficulty or limitation in analysis?\n\n- Figure 2: I note that Theorem 2.4 (statistical lower bound, orange region) and Theorem 2.2 (SgnQ upper bound, blue region) all talk about the general DCBM case, while Theorem 2.6 (computational lower bound, green region) talks about the specific SBM case. The paper claims to establish the phase transitions for DCBM. How does that connect to the SBM assumption (the computational lower bound for SBM is already known [1])? Is that sufficient for the claim? This could be a writing issue but I don't know if there is any hidden assumption here, and if yes it should be pointed out in the figure. \n\n- Does the real-world dataset follow the DCBM? Why DCBM is a reasonable ground assumption in this case?\n\n\nReferences:\n[1] Chen, Yudong, and Jiaming Xu. \"Statistical-computational phase transitions in planted models: The high-dimensional setting.\" International conference on machine learning. PMLR, 2014.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "8bSrhHJ3kxT", "reviewer": "Reviewer_US3K", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the task of detecting a planted community structure with small clusters (e.g. a planted clique) inside a graph with heterogeneous degrees. More precisely, the authors consider a random graph model such that\n$$ P(i \\sim j) = \\theta_i \\theta_j P_{\\pi(i), \\pi(j)}  $$\nwhere $\\theta$ models the degree heterogeneity between vertices, and $\\pi$ is an assignment of vertices into $K$ different communities. The goal is to find a test that discriminates between the null hypothesis $K = 1$ and its alternative, even in the presence of very small communities. In particular, the alternative model considered consists in taking $K=2$, and two communities of size $n$ and $N \\ll n$, with the matrix $P$ given as \n$$ P = \\\\begin{bmatrix} a & b \n\\\\\\\\ b & c \\\\end{bmatrix} $$\n\nThe paper's contributions are threefold:\n- **Existence of a polynomial test:** consider the *signed quadrilateral* statistic\n$$ \\psi_n = \\sum_{i_1, \\dots, i_4} \\hat A_{i_1 i_2} \\hat A_{i_2 i_3} \\hat A_{i_3 i_4} \\hat A_{i_4 i_1},  $$\nwhere $\\hat A$ is a centered version of $A$. The authors show that there exists a certain threshold $\\tau$ depending on the eigenvalues of $\\mathbb E[A]$ (and related matrices), such that if $\\tau\\to\\infty$ there exists a test based on the value of $\\psi_n$ that discriminated between $K = 1$ and $K > 1$ whp. In the two-community case above, this corresponds to \n$$ \\tau = N(a-c)/\\sqrt{cn}. $$\n\n- **Statistical exact threshold:** in the two-community case, this paper show the existence of a statistical threshold at \n$$\\tau' = \\sqrt{N}(a-c)/\\sqrt{c} $$ such that if $\\tau' \\to 0$, no test can distinguish between $K=1$ and $K>1$. Conversely, if $\\tau' \\to \\infty$, then there exists a (non-polynomial) test that discriminates between the two hypotheses.\n\n- **Computational lower bound:** finally, if $\\tau \\to 0$, the authors provide a computational lower-bound based on the low-degree framework, showing that there is no succesfull test based on a low-degree polynomial in $A$. This is a proxy for polynomial hardness. Since $\\tau$ and $\\tau'$ differ significantly only when $N \\ll \\sqrt{n}$, this implies that the signed quadrilateral test is optimal above $\\sqrt{n}$.", "summary_of_the_review": "This paper presents very interesting results on testing a generalized version of the planted clique setting, which is closer to real-world applications. However, the presentation must be significantly improved, and the proof made self-contained, hence I do not recommend acceptance.", "strength_and_weaknesses": "The setting considered by the paper is both natural and interesting; it is closer to a real-world setting than the vanilla planted clique problem, and therefore the failure of $\\chi^2$ and the need for other methods are meaningful. The authors obtain a near complete phase diagram, with only a small gap in the $N \\gg \\sqrt{n}$ regime.\n\nHowever, the main weakness of the paper is the overall clarity and presentation of the results; precise feedback is given in the next section. In particular, it is nearly impossible to check the proof without constantly referring to Jin et al. for every single definition.\n\nIt is also my opinion that this paper would be more suited for a more theoretical CS conference/paper, although I do not consider it grounds for rejection.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster