Combinatorial-Probabilistic Trade-Off: P-Values of Community Properties Test in the Stochastic Block Models
Authors: Shuting Shen
Junwei Lu
Venue: ICLR 2023 notable top 25% (2023)
Keywords: combinatorial inference
stochastic block models
community properties
minimax lower bound

Abstract: We propose an inferential framework testing the general community combinatorial properties of the stochastic block model.  We aim to test the hypothesis on whether a certain community property is satisfied, e.g., whether a given set of nodes belong to the same community, and provide p-values for uncertainty quantification. Our framework is applicable to all symmetric community properties. To ease the challenges caused by the combinatorial nature of community properties, we develop a novel shadowing bootstrap method.  Utilizing the symmetry, our method can find a shadowing representative of the true assignment and the number of tested assignments in the alternative is largely reduced.  In theory, we introduce a combinatorial distance between two community classes and show a combinatorial-probabilistic trade-off phenomenon. Our test is honest as long as the product of the combinatorial distance between two communities and the probabilistic distance between two connection probabilities is sufficiently large.  Besides, we show that such trade-off also exists in the information-theoretic lower bound.  We also implement numerical experiments to show the validity of our method.

Published as a conference paper at ICLR 2023
COMBINATORRAA--PROOBBBLLITIS TRADE-OFF: P-VALUES OF COMMUNITY PROPERTIES TEST IN THE STOCHASTIC BLOCK MODELS
Shuting Shen & Junwei Lu Department of Biostatistics Harvard T.H. Chan School of Public Health (shs1 45 Junwei u@hsph) hww.ardd edu
ABSTRACT
We propose an inferential framework testing the general community combinatorial properties of the stochastic block model. We aim to test the hypothesis on whether a certain community property satisfied, e.g., whether given set of nodes belong to the same community, and provide p-values for uncertainty quantification. Our framework is applicable to symmetric community properties. To ease the chal- lenges caused by the combinatorial nature of community properties, develop a novel shadowing bootstrap method. Utilizing the symmetry, our method can find a shadowing representative of the true assignment and the number of tested assign- ments in the alternative is largely reduced. In theory, we introduce a combinatorial distance between two community classes and show trade-off phenomenon. Our test is honest as long as the product of the combi- natorial distance between two community property classes and the probabilistic distance between two connection probabilities is sufficiently large. Besides, we show that such trade-off also exists in the information theorreti lower bound. We also implement numerical experiments to show the validity of our method.
INTRODUCTION
Clustering is an important feature for network studies, which refers to the presence of node com- munities the underlying graph. Community partitions the nodes into subgroups, within which higher level of connectivity is perceived. Its broad spectrum of applications includes the fields of sociology (Wasserman Faust, 1994), biology (Barabási & Oltvai, 2004). physics (Newman, 2003) and internet (Albert et al., 1999). Stochastic block model (SBM) (Holland et al., 1983) is one of the most widely studied statistical models depicting the network community structures. is a random graph model which divides the nodes into disjoint communities and assigns the probability of con- nection between two nodes according to their community memberships. One of its central problems in previous studies is community detection. However, most of the existing research focused esti- mating the community labeling without uncertainty quantification (Choi et al., 2012; Mossel et al., 2012: Airoldi et al., 2013; Massoulié, 2014; Abbe et al., 2016; Mossel et al., 2016). Some funda- mental limits of community recovery have also been established in previous studies. For example, Abbe al. (2016) showed the optimal phase transition for the exact recovery of the community signments using the maximum likelihood. The semi-definite relaxation methods (Abbe et al., 2016; Hajek et al.. 2016; Agarwal al., 2017: Bandeira, 2018) and the spectral methods (Yun & Proutiere, 2014: Abbe & Sandon, 2015; Gao et al., 2017: Abbe et al., 2020) are also shown to be optimal in exact recovery. Besides the exact recovery, Zhang & Zhou (2016) quantified the statistical rate of the community estimation via the mismatch ratio and showed the minimax rate of the mismatch ratio for community detection. In summary, the community estimation studies have two major limits: 1) it does not provide the p-values to evaluate the uncertainty of the estimation, which are essential in many scientific applications, and 2) it requires the recovery of community assignments for all nodes, while in many scientific applications, we interested in the community properties of spe- cific subset of nodes, e.g., whether two sets of nodes belong to the same community. We formulate the following examples of statistical hypotheses for illustration.

---

Published as a conference paper at ICLR 2023
Example 1.1 (Same community test for m nodes). We want to test whether given nodes are in the same cluster or not. Without loss of generality, we have the hypothesis:
Ho Nodes ,,...,, m belong to the same community,
H1 There exists two nodes 1 S j * k S m. belonging two different communities.
Example 1.2 (Group community test). For two groups of nodes, we know in prior that nodes within each group belong the same community. We aim to further test whether these two groups belong to the same community. We denote one node set as Sm = m.....,m. and the other as Sm {m + I....,,, m m'). The group community hypothesis
Ho Nodes in Sm U S' belong to the same community, H1 Nodes in Sm belong to community a, but nodes in Sny belong to community o a.
Example 1.3 (Equal-sized communities test). Given an SBM of nodes and K communities, we aim to test whether each community has the same size. Namely, aim to test the hypothesis:
Ho Each community has the size n/ K
H1 At least one of the communities has size equal n/K.
In order to conduct hypothesis tests including the above examples, we develop a general community property test. We consider the SBM with n nodes and K communities. Denote the community assignment of the nodes by (=(1), ...; z(n)) E (l...., KJ". The homogeneous SBM assumes that the edges of the random graph are independent Bernoulli random variables with connection probability p if z(i) = =() and q if z(i) * =(j). We reparameterize p, y as p = Pr,11 and q =Pnd2, where Å and X2 constants independent of and Pn is the signal strength. Let be two disjoint community assignment families. We are interested in the
Co, C1 C. (L...., K.. _K
general community property test:
Ho E Co versus HI CI.
(1.1)
We characterize the hardness of the test by two kinds of "distances": the probabilistic distance between p and q, and the combinatorial distance between Co and C₁. The existing literature on community detection only focused on the probability distance, e.g., the Rényi divergence / (p, q) = -2 log (vrn- + v(1 -
-p) (1 4)) (Zhang & Zhou, 2016). In comparison, our paper introduces a novel combinatorial distance between Co and C₁ denoted as díCo, C1) (see Definition 2.4) and proposes general testing method that is honest and powerful when
Combinatorial-Pe Probaabiilio Trade Off: [(p, ()d(Co. C1) M(2²)
(1.2)
for some arbitrarily small > 0. On the other hand, we show the minimax lower bound of the test in the sense that Ho and H, in (1.1) cannot be differentiated when [p, q)d(Co, C1) I c clog n for some constant 0.! The multiplication between [p, g) and d(Co. C1) reveals the trade-off between the probabilistic distance and the combinatorial distance in the general community property test.
COMMUNITY PROPERTIES OF THE STOCHASTIC BLOCK MODEL
In our paper, consider the fixed assignment stochastic block model, denoted by M(n, K, 2)-
Denote by [n] = {1...., n for any integer n. For simplicity, we start with the scenario where the community sizes are even, and will generalize to the uneven case in Appendix B. We denote the even assignment class by 1C" := {z E [K]" Hi z(i) = k} n/ K, Vk E [K]]. In our paper, assume K to be bounded. Let graph generated from the SBM. In the following part of the paper, we will study the community property test with an observation of the adjacency matrix A M(n, K.p...)).
{0, 10,1) mx be the symmetric adjacency matrix of the random
2.1 SYMMETRIC COMMUNITY PROPERTIES
In this section, we aim to define the community property and the distance between two community families. In general, we say community property is a subset of [K]". However, such a defini- tion too general and may include some ill-posed examples. For instance, if we can transfer one
We refer Theorem 3.2 and Theorem 4.1 for the rigorous arguments about the upper and lower bounds.
2

---

Published as a conference paper at ICLR 2023
assignment to another under certain permutation of the community labels, they are essentially the same assignment and should belong to the same community property. This motivates us to give the following definition of equivalent assignments.
Definition 2.1 (Equivalent community assignments). Let Sk be the symmetric group containing all bijections from [K] to itself. We say two assignments z and z' E [K] are equivalent, denoted as = z', if there exists a permutation a E Sy such that (=) z'. Here a(z) means implementing the permutation a to each entry of the vector 2. More generally, given node set N C [n|]. we denote by zN the sub-vector of with entries in N. We say AN z/y if there exists permutation Sx such that a (2x) = z/x-
With Definition 2.1, we give the definition of symmetric community properties as follows.
Definition 2.2 (Symmetric community properties). We say community property Co is symmetric, there exist a node set N S [n] and an assignment E IC", such that Co = (z K : &N Ev). We say some C1 KC" CCo is an alternative property of Co if C₁ is closed under permutations on the support NV, i..., for any 2 E C1 S (C,) if some satisfies z/y- = 2N: then 2' E C1 as well.
Intuitively, the node set N and the assignment 7 in Definition 2.2 are the representative node set and assignment generating all possible assignments in the community property via permutation. The community property Co "symmetric" in the sense that all its assignments are equivalent on the support of node set N. We impose the following assumption on testing symmetric properties.
Assumption 2.1 (Symmetric community property test). In the hypothesis test Ho E Co v.s. H1 Ci, we assume Co2 C1 C K and Co is symmetric and Cj is alternative property of Co.
By Definition 2.2, C Cj is an alternative property of Co. Meanwhile, C₁ satisfying the assumption above could strict subset of Cj. allowing more examples practice. In fact, we can show that Examples 1.1 and 1 1.2 satisfies Assumption 2.1, whose concrete forms of N and 2 are given below.
Example 1.1: Same community test for m nodes. We can define
Co (= K" =(1) = =(m) and Ci K.
(2.1)
while V [m] and ă is any assignment satisfying vN 11) [K]m.
Example 1.2: Same community test for groups We have
Co {2 e K2" :
(m) s(m 1) 2 m')}
(2.2)
C (2 K"" =1)
(m)) # 2(m 1) 2 m }
where Co is symmetric by choosing N = [m + m²) and ÄN~= = (1,..., mKm-m'
2.2 COMBINATORIAL DISTANCE BETWEEN COMMUNITY PROPERTIES
In order to depict the relationship between Co and C, we propose a metric of distance in terms the number of misaligned edges. We first define the set of misaligned edges between two assignments.
Definition 2.3. For any two assignments in E Co and E CI, we define the two sets of misaligned edges as
21 ((.)) E2(20, 21) =
[n], (1) z0()) + 2 (1) and j,4, [m], (1) + zo(5), (1) = 21)i,,
where & (2o, 21) contains the edges whose corresponding nodes are assigned to the same community in 2g but to two different communities by 21, and Eg (20, 21) is the opposite. See Figure for illustration. We define n; n, 21) = [E, 21)], for i = 1,2 2 as the cardinality of the two edge sets.
Now we are ready to propose the metric of assignment distance defined follows.
Definition 2.4 (Community property distance). We define the distance between two assignments 2o and 21 as d(20,21) = m1(20 21) V fz (ău, 21). Correspondingly, we also define d( 20. C1) = infzrec, d(z0, 21) and the distance between two community properties
inf d(Co. EcCCovELEC,
d(z0, 21).
3

---

Published as a conference paper at ICLR 2023
Community
Community
Ei
Ea 21)
3
4
6
20
Figure 1: Example of misaligned edges in Definition 2.3.
By definition, the distance d(Co, C1) is the minimal number of misaligned edges between Co and C1. We refer the computation of d(Co, C1) for more general examples to Section 2.4.
2.3
LIKELIHOOD- -ATIO TEST FOR COMMUNITY PROPERTIES
Our method starts with defining likelihood-ratio test statistic. We denote the observed adjacency matrix from the true model as A M(n, K, p, q, 2))",, where x" is the true assignment. The likeli- hood function of the stochastic block model is
f(A; 2, p. = II (x(0===))); (1-p) (1-
We then denote the liglliked ratio statistic as
LRT log supzec, ((A;,,p,))
(2.3)
SuPseCoLC, [(A;
order to conduct the property test, we study the limiting distribution of the likelihood ratio statistic. In specific, when 1/pr. o(n -3) for some constant Cg > 0, are able to decompose the LRT as follows
LRT sup log f(A; 2, log f(A; .p.9) + o(1)
=Eć,
sup g(p, 2) =EG,
Σ
Aij
Σ
Ass) + o(1),
(2.4)
(K:))E2(=*1aa)
(LJ))E)(=*.a))
where g(p, 4) = log - /////////// ()/(g()//1/////////1gg1g -0p)p) p)). We observe that the leading term in (2.4) is the difference of edges in two edge sets: E2(2", 2) and E (a 2). By Definition 2.4, the property distance d(Co, C1 larger when the two edge sets are larger, which makes the leading term larger as well. This implies why d(Cn, C1) characterizes the difficulty of the test.
Remark 2.1. The likelihood ratio statistic in (2.3) is similar the one in Wang Bickel (2017).
They considered the hypothesis on specific community property: the number of communities.
Co = {z|2 E [K- - } and C1 = {2|2 e [K]*)/C.
(2.5)
They showed that the suprema supzec, 2. g) in (2.3) is unique, as illustrated in Figure 2(a), which makes their LRT asymptotically normal for Co, C1 in (2.5). However, this is not always true for the general community properties. For some properties, there will be an exponential number of candidate assignments maximizing the likelihood in (2.3), as illustrated in Figure 2(b). Thus the LRT is no longer asymptotically normal for the general case. Therefore, despite the similar formality of the LRT, our testing procedure will be different from theirs.
To characterize the suprema in the LRT, we define the boundary of the alternative properties.
Definition 2.5 (Boundary of community class). For a given null assignment 2o E Co. we define the boundary of C₁ as:
Bz, = = C. d(zo. 2) d(zo, Ci)
Namely, B2, is the projection of 2g onto Ct. Our analysis shows that under the null, the likelihood maximizer's is asymptotically equivalent to the boundary B...? 2 In the next section, will study the asymptotic property of the LRT under such case by studying the structure of Bzg
See Lemma D.2 in the Appendix for the rigorous argument.
4

---

Published as a conference paper at ICLR 2023
(a) Unique projection
(b) Non-unique projection
Co
Co
20
B
Dr
The boundary of C1 given zo- On the left panel, the projection is unique and Bz 21- On the right panel, the projection is not unique, where 2p is the shadowing assignment 2", and Bg- and Bo have similar structures.
Figure 2:
2.4 SHADOWING BOOTSTRAP FOR THE PROPERTY TEST
There are two major challenges to estimate the p-value LRT. First, the suprema the likelihood are not unique and therefore the limiting distribution of LRT is not necessarily normal. By (2.4), we can in urrn study the limiting distribution the leading term
== sup g(p.9) =ECi
( (1:))EE((=T54))
Σ
A
A4)) )
E
(2.6)
(A5))E1(==".4)
Chernozhukov et al. (2013) studied the limiting distribution of the maximal of high dimensional empirical process and proposed to estimate its quantile by multiplier bootstrap. However, their method imposes that the dimension d of the empirical process and the sample size satisfies log d//n/// 1/5 o(1), whereas in (2.6), the dimension d [11 could be of the order K" and vio- lates the scaling condition. To handle this problem, our key observation is that the supremum over the alternative C1 be represented by the supremum over its boundary B In particular, we show that the leading term L is asymptotically the same as the following statistic:
Lo = sup g(p. 9) BEB
Σ
Au
Σ
Arj)
(2.7)
(L.))EE2(Z"
(1.))
The cardinality of B2- much smaller than that of C₁ (usually polynomial to n)), and therefore sat- isfies the scaling condition of high dimensional multiplier bootstrap. However, we cannot construct By in practice as 2" unknown. This leads the second challenge: how find B.. in practice? Our key insight to solve the second challenge is to utilize the symmetry property in Definition 2.2. This insight relies on the following lemma characterizing the covariance of two processes.
Lemma 2.2 (Shadowing symmetry). For given Cu. we list the assignments in the boundary B, 21, 22..... ... 1. Define |B& -dimensional vector L; as
(L2)x = 9((
Σ
AUJ
Σ
ANs). for k= =1:=1,2. 2,2, |B2/-
(K.))E2((ZAA)
Suppose Assumption 2.1 holds. For any 20, 2 E Co, we have | = |B and Cov Lzn) equals to Cov (Lzz)) up to permutation, ie., there exists a permutation T E S|r., such that Cov Cov(Lzg)) )
Cov(L (()))()))( for all k,l=l,.... BBol
We refer Appendix F.1 for the proof of Lemma 2.2. Therefore, avoid directly constructing B. and choose instead any z E Co as a "shadowing assignment" to construct the shadowing statistic
Lo(2o) == sup g(p.9) 9)
Σ
Ai
Σ
Ary)
(2.8)
sEB
(so.a)
The following proposition shows that the quantiles of Lo(=)) and Lo are asymptotically the same.
5

---

Published as a conference paper at ICLR 2023
Proposition 2.3. Suppose Assumption 2.1 holds, log [B,, O(llgg) and 1/p, o(n!-a2) for some constant C2 0. For any 2g E Co. we have
lim sup (PLo <t) (P(o(z))) <t] =. n-000 tER
We defer the proof Appendix D.I. Now we are ready present the shadowing bootstrap pro- cedure. Based on the previous discussion, we aim to estimate the p-value based on Lo(z)). To achieve this, we take an arbitrary 2g E Co, and generate one realization of the adjacency matrix À M(n, K, P. 20). Here p and q are the maximum likelihood estimator
p q
argmax
sup f(A; 2, 2.
(2.9)
=ECouC,
The likelihood ratio statistic
LRT
log sup (A; log sup zEC1
2(A;,, zECouCi
(2.10)
The next step is to find the assignments in Bzo- We can construct 2g, by Definition 2.5 in general. We will show later how to construct B., for the concrete examples. To estimate the p-value, we ap- ply the Gaussian multiplier bootstrap. Let {eigheiejsn be independent standard Gaussian random variables and define
Wn = sup =E = ISiciSn
Σ
(Aij- - Ep.a A.j)) (I((1,5) E E2(z =)] - 1[(i,) E Ei =))) (2.11)
where Ep. A.
p if 20(1) zo(j) and Ep.(( (Ay)) otherwise. Then estimate the p-value
via the multiplier bootstrap
Pw P(g
DM LRT LR
(2.12)
where ñ. d(Co, Cg the null Hu 2" E Co if Pw S a and do not reject Ho otherwise.
p) is the estimator of the mean of the process in (2.8). Finally, we reject
Now we provide concrete steps to construct Bz and calculate d(Co. C1) for Examples 1.1 and 1.2.
Community
Community 2
Community
Community 2
Swap
Swap
8u
4
31
10
3
4
7
81
3
5 9
(a) Example
(b) Example 1.2
Figure 3: Procedure to construct the assignment in the boundary B Panel (a) is test whether
the first 3 nodes belong to the same community, and Panel (b) is to test whether node sets (1,2,3) and (4, 5) belong the same community.
Example 1.1: For any =o E Co, to construct B.g- we aim to find assignments whose distance to zo d(z0, C.). The simplest way to exchange the community assignment of one node E [m] with another node s' from a different community (see 21 in Figure 3(a) for an example when n = 10, m 3, and K 2). It is easy check all such assignments belong to B On the other hand, any other operation will incur more rode-wise misclassification and the edge-wise misalignment will be much larger. As for d(Co, Ci), we start with evaluating n (20, for some #1 Bzg The edges whose connection probability is changed from p to q will be the edges between the swapped nodes and the rest of the nodes in their original communities. Therefore, we have 71 (Zo, 21) = 2(n/K(11 Similarly, nz 2p, 21) 2(n/K K 1) and thus d(Co. C1) 2(n/K 1). In summary. B=, is composed of all the assignments obtained from swapping two nodes from different communities in 20- The distance between two classes is d(Co, C1) 2nn/ K 1).

---

Published as a conference paper at ICLR 2023
In this example, without loss of generality, we assume that m' m. Then to project an arbitrary 20 E Co onto C1, we will exchange the cluster assignment of the set Sn = {m + I,...,, m
Example 1.2:
m'} with another set S from different cluster of cardinality m' to obtain the smallest number of misaligned edges. See Figure 3(b). Correspondingly, for 21 E Bzg. we have d(zo, 21) = n1 (=1 21) (2,, =1) 2m' (n/ K - m'), and thus d(Co, C1) 2m' annnn/K m'). In summary, Bx, is composed of all the assignments which can be obtained from reassigning the label of nodes am++1..... m+ in 20. The distance between two classes is d(Co. C1) 2m' (n/nn///e m').
3 VALIDITY OF COMMUNITY PROPERTY TEST
In this section, we show that our testing method is honest and powerful. Before presenting our theorems, we first give the following assumption for the alternative class C₁. Assumption 3.1 (Scattering of Ci). For any 2g E Co. we have |zzl = O(n")) for some constant co 0.
We call this assumption the scattering assumption it ensures that the assignments in C1 are scat- tered and not too concentrated on the boundary. In general, if relabeling a constant number of nodes can change assignment from Co to C₁, then |B will be upper bounded by (c) (n*)) ) for some integer general symmetric community properties.
0. The following main theorem shows that our test is honest and powerful for
Theorem 3.2. Suppose Assumptions 2.1 and 3.1 hold, d(Co, Ci) o( for some constant ei 2, and 1/Pn = o(n for some constant C2 > 0. We have
lim sup P(pw S a) = a and lim sup P(reject Ho) = a. n=000 ECo
n-000 x ECa
Moreover, if d(Co. C) = ((n)) for some arbitrarily small constant e >> 0, we have
lim inf Prejectt Ho) = 1. n0000 ECE
We defer the proof Appendix D.2. One may note that under the regime of Theorem 3.2, exact recovery can be achieved. However, previous exact recovery methods cannot provide uncertainty quantification. On the other hand, our approach can provide the p-values for the general community properties which is more challenging compared to estimating the community labeling. We now apply Theorem 3.2 Examples 1.1 and 1.2 by checking Assumption 3.1. The following proposition shows that Assumption 3.1 is satisfied for Examples 1.1 and 1.2.
Proposition 3.3. For Example 1.1, we have |Bzo1 = (mm) and d(Co, C1) = 2(n/K - 1) = O(n/K) K). For Example 1.2, 2 O(K(n/ Kmmmm) and d(Co. C1) = 2(mAmm) (mmmm)
Plugging these results to the general Theorem 3.2, we have the following corollary.
Corollary 3.4 (Examples 1.1 and 1.2). Suppose L/Pm o(n (m)) for some constant 0o > O. If m < n/K for Example 1.1 or m A m = O(1) for Example 1.2, we have +o sup=*eCo P(reject Ho) a. Moreover, if [p, q)n/gK I(n for some small positive constant e, we have lim sup,,ec, P(reject Ho) =1 1.
INFORMATION- INFORMATION-THEORETIC THEORETIC LOWER BOUND
In this section, we discuss the information-thent will give the lower bound of the minimax risk of all possible test defined as
lower bound of community property test. We
r(Co. C2) inf sup (v 1) sup (v = 0)}. zEC.
=EC.
We will show that the combinatoriall-poobbllttttt trade-off phenomenon appears the lower bound as well, thus it essentially characterizes the hardness of the community property test. In order to establish the lower bound, we first introduce the concept of packing number for C1. A key element in defining the packing number is the metrie assigned to C1. Our first insight is that the more misaligned edges there are between Co and C, the easier it is to differentiate C, from Co. This motivates to consider the misaligned edge E 21) & E1(20,2) 21) U E2 21) and use its
7

---

Published as a conference paper at ICLR 2023
cardinality "metric". Our second insight is that how hard it is differentiate C₁ from Cy does not depend on the complexity of the entire C1 but the boundary set B.g, which is also implied by shadowing bootstrap statistic in (2.11). Therefore, we give the following definition of packing number of Bz to characterize the hardness of test.
Definition 4.1 (e-packing of Bz.). For any E Cg. we say f21,22,
22, 22, S Bzo is an E-packing of Bgg if for any Rj + At we have [ 23) n E1,2 #x)1 S e. The e-packing number B denoted as N 2B E), is the maximum cardinality of any e-packing of Bz
By Definition 2.5, Bz, collects the alignments in C1 which are closest 20 E Co, which the hardest cases to test. The following theorem shows the lower bound of the community property test can be characterized by the packing number of these hardest cases.
Theorem 4.1. Suppose Co, C1 C KC" 1/pm = o(n' for some constant 0o > and p S 1 1 8 for some constant > 0. If there exists a 2u E Co such that log N (B vd(zo, C1) = O n) and
d(z0, ())
lim sup n-000 log (Bz0. V /(zo, Cn)
<1,
(4.1)
then liminf r(oo, C1) 2 1/2. 12-000
that the packing entropy log (B s. /d(2o,C) C1)) is the lower bound of the signal strength. In general, the packing entropy is O(log n). Comparing to the upper bound d(Co. C. T q) = 2(n=) for some arbitrarily small constant e > 0 in Theorem 3.2, there is a gap O(log n) in the lower bound. We conjecture that this gap exists as both our upper and lower bounds are for general community property test. We will find a finer analysis in future research. The following theorem gives an alternative lower bound result relaxing the scaling conditions in Theorem 4.1.
We defer the proof Appendix E. From (4.1).
Theorem 4.2. Suppose Co, C1 C KC", 0 9 pppp 1 8 for some constant 5 0 and
limm-+oc d(Co. = co. If one of the following conditions:
(1) d(Co, C 9) < c for some sufficiently small constant c;
(2) lim d(Co, (p) = oo, but there exists a E Co such that
limsup d(zo, C1 (p) 9) < 1,
n log N( 0)
is satisfied, then lim inf r(Co, 2 1/2.
n
We defer the proof to Appendix E. Theorems 4.1 and 4.2 both show the lower bound with the combinatorial probabilistic trade-off. Theorem 4.1 has a sharper lower bound on d(zu, Cp) g) under a stronger scaling condition. In comparison, Theorem 4.2 has less sharp lower bound with weaker scaling conditions. When diCn, C,) q) is bounded, we cannot differentiate two hypotheses. When d(Co, C,) goes infinity, Theorem 4.2 condition (2) gives the lower bound d(Co, (p) 9) < log (N z0. 0). If we have stronger scaling conditions in Theorem 4.1, we get sharper lower bound d(Co. CT) q) < log N ((B,, / /d(zo.Co C1)). Now we apply the general theo- rems for the lower bound to Examples 1.1 and 1.2. By (4.1) in Theorem 4. 1, a key quantity for the lower bound the packing number N( (Bz,, v /22 C1). The following proposition gives concrete results for the two examples.
Proposition 4.3. The packing number for Example 1.1 is N( Vdlzo, C1) = m,, and the pack- ing number for Example 1.2 is (B / /dzzo.C1) N( s,, 0) = =1.
Applying Proposition 4.3 to Theorem 4.1 and Theorem 4.2, we provide the lower bound for Exam- ples 1.1 and 1.2 in Corollary 4.4 and Corollary 4.5 respectively.
Corollary 4.4. For Co and C₁ in (2. if 1 1/pp = o(n for some constant C2 > 0. < - ô for
some constant& > 0 and limsup 2nd (p. /)/ [ m) < 1. then inf (Co, C1) 2 1/2.
x= Corollary 4.5. For Co and C, in (2.2), if np x;, 0 < < p < 1- 8 for some constant 0 > 0 and
n 7-000
lim sinsupni n/ (p.g) < for some sufficiently small constant > then lim inf r(Co, C1) > 1/2. n-+00
8

---

Published as a conference paper at ICLR 2023
5 NUMERICAL RESULTS ON SYNTHETIC DATA
We conduct the shadowing bootstrap on Examples 1.1 and 1.3. We test both hypotheses the sig- nificance level a = 0.05, and consider K = 2 and n = 200, 600. 1000. The connection probabilities are set be p = (1+ Pr, and q = (1 (1-A)) A), where Pr. (n/ K) -0.3
0.3 and A is the parameter con- trolling the difference between p and y. We set A from 0 to 0.8. The maximum likelihood estimator initialized by the singular value decomposition estimator to boost computation. For Example 1.1, we set m [(n/ k) /2] for 8 = 0.3, 0.5, 0.7 to explore the influence of m on type-I and II errors.
(a) Different 72
(b) Different 772
1.00
Duga Siee
1.3
209
669
1830
0.35
0.70
875
10go
8:30
1ygo
0.30
1ypar
0:33
8:50
0.25
9.8
0:55
0.30
833
8:33
Figure 4: Type-I and type-Il errors for Example 1.1. Panel (a) shows the results for different graph sizes 200, 600, 1000 with m as (n/ K /tl//KKu./// jus/22] Panel (b) shows the results m [n/ K2) /2) with R = 0.3, 0.5, 0.7 and the graph size n 600.
In Figure 4, we show how the type-I and type-Il errors vary with A, n and m for Example 1.1 (via 500 Monte Carlos). As A increases, the type-I error converges the nominal level 0.05, which shows that our method is honest. Type-Il eгror is small when A is around zero as the test will always reject the null when the signal strength is too small, while increases drastically as the type- I error drops to O. When A is large enough, the type- error converges to 0, showing that our test powerful. In Figure 4(b), we can see that the type-I and type-ll errors for different m's converge similarly as A increases. This is consistent with Corollary 3.4 as the scaling condition is irrelevant to m. Simulation results for Example 1.3 are shown Figure 5. The type and type error rates vary similarly as in Example 1.1. In summary, the type-I and type-ll errors will not converge to the nominal levels until the metric product d(Co, C₁ (p, q) is approximately larger than 10, which matches the theoretical lower bound (please refer to Tables 2 and 3 in the appendix).
3.50
10pee
Type
8:35
8.5
68
67
65
36
08
65
65
0.6
4
Figure 5: Type-I and type-Il errors for Example 1.3 as A varies in [0, 0.8] and the graph size 200, 600, 1000.
CONCLUSION
We propose a likelihood ratio test for the community property test with uncertainty quantification, implemented via "shadowing bootstrap" method by utilizing the symmetry of Co and C,. We show that our test is generally honest and powerful as long as C, and C, are symmetric. We also prove the minimax lower bound of the general community property test.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
The authors are grateful for the support of NSF DMS1916211, NIH/NCI R35 CA220523, NIH ROI ES32418 and U01CA209414.
REFERENCES
Emmanuel Abbe and Colin Sandon. Community detection in general stochastic block models: fun- damental limits and efficient algorithms for recovery. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science FOCS 2015, pp. 670-688 IEEE Computer Soc., Los Alami- tos, CA, 2015. doi: 10.1109/FOCS URL https: /oi. ttt.:/toooooggg///oo owg/10. http:///...1100/CCC1 1109/FOCS. 2.7...7.
Emmanuel Abbe, Afonso S. Bandeira, and Georgina Hall. Exact recovery in the stochastic block model. IEEE Truns. Inform. Theory, 62(1):471-48)) 2016. ISSN 0018-9448. doi: 10.1109/TIT. 2015.2490670. URL https: /ttp:///oooo////oo htt.//oooooggo//oooo//o
11110//1TT 2015. 22222211...27777 2490670.
Emmanuel Abbe, Jianqing Fan, Kaizheng Wang, and Yiqiao Zhong. Entrywise eigennector analysis of random matrices with low expected rank. Ann. Statist,, 485)):4552-14444 2020. ISSN 0090- 5364. doi: 10.2114/9--AOSEI
URL http:////oo..../...111..11 --01
Naman Agarwal, Afonso S. Bandeira, Konstantinos Koiliaris, and Alexandra Kolla. Multisection in the stochastic block model using semidefinite programming. Compressed sensing and its applications, Appl. Numer. Harmon. Anal., pp. 125-162. Birkhäuser/Springer, Cham, 2017.
Edo M Airoldi, Thiago B Costa, and Stanley Chan. Stochastic blockmodel approximation of graphon: Theory and consistent estimation. In C. J. C. Burges, L. Bottou, M. Welling. Z. Ghahra- mani, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems 26, pp- 692-700. Curran Associates, Inc., 2013.
Réka Albert, Hawoong Jeong, and Albert-Lász1ó Barabási. Diameter of the world-wide web. Na- ture, 401(6749):130-11,, 1999. doi: 10. 1038/43/4.... URL https: :/ts:://doo/ wtt.:ii.rg/1.100//1.3 43601.
Afonso S. Bandeira. Random Laplacian matrices and convex relaxations. Found. Comput. Math., 18(2):345-37,, 2018. ISSN 1615-3375. doi: 10.1007/s10208-000 01000000----991----1 URL https:/ doi doi oor.org/1...... 10077/00.11010111 s200/810002222 01 9341-9.
Albert-LászIó Barabási and Zoltán N. Oltvai. Network biology: understanding the cell's func- tional organization. Nature Reviews Genetics, 5(2):101-113, 2004. doi: 10.1038/nrg122 URL
https://doi.com http:///oooor///////// /t..o///.......... 1038 0038/ng1222..
Peter Bickel, David Choi, Xiangyu Chang, and Hai Zhang. Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels. Ann. Statist., 41(4): 1922-1943, 2013. ISSN 0090-5364. doi: 12.2214/13AOS1122 URL https: htts://ddo.ooot 10.1214/13 AAS1124.
Victor Chernozhukov, Denis Chetverikov, and Kengo Kato. Gaussian approximations and multiplier bootstrap for maxima of sums of high-dimensional random vectors. Ann. Statist, 41(6))2786- 2819, 2013. ISSN 0090--3644. doi: 10. 10.1214/13-A0S1161 URL https:://do/.. org/100.... 1214 11111111--01111111
D. S. Choi, P. J. Wolfe, and E. M. Airoldi. Stochastic blockmodels with growing number of classes. Biometrika, 99)2))273-284, 2012. ISSN 0006-3444. doi: 10.1003/biomee/as0033. URL https://dee wwt.///gg////o
Jianqing Fan, Yingying Fan, Xiao Han, and Jinchi Lv. Simple: Statistical inference on membership profiles in large networks, 2019.
Chao Gao. Zongming Ma. Anderson Y. Zhang, and Harrison H. Zhou. Achieving optimal misclas- sification proportion in stochastic block models. J. Mach. Learn. Res., 18:Paper No. 60, 45, 2017. ISSN 1532-4435.
10

---

Published as a conference paper at ICLR 2023
Bruce Hajek, Yihong Wu, and Jiaming Xu. Achieving exact cluster recovery threshold via semidef- inite programming: extensions. IEEE Trans. Inform. Theory, 62(10)):518- -9337, 2016. ISSN 0018-9448. doi: 10.1109//I1.2011:25548811 URL https::////ccccc. http::///o...ctg/11..1111/// 201 25994222
Paul W. Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: first steps. Social Nenworks, 5(2):109-131) 1983. ISSN 0378-8733. doi: 000016/0378-7731080 90021-7. wtt.tp/s//d....gg1....oo..
8733 (80090717777
Laurent Massoulié. Community detection thresholds and the weak Ramanujan property. In STOC"14-Proceeding of the 2014 ACM Symposium on Theory of Computing, pp. 694-703. ACM, New York, 2014.
Elchanan Mossel, Joe Neeman, and Allan Sly. Stochastic block models and reconstruction, 2012.
Elchanan Mossel, Joe Neeman, and Allan Sly. Consistency thresholds for the planted bisec- tion model. Electronic Journal of Probability, 21(0), 2016. ISSN 1083-6489, doi: 10.1214/ 16-ejp4185. URL http:// /xx doi www.ddo.oooo.oo.o.o....
M. J. Newman. The structure and function of complex networks. SIAM Rev, 45(2):167-256, 2003. ISSN 0036-1445. doi: 10.1137/503614504444800 URL https: http:::/ddo..rgg///
1137/800361450342242
Y. X. Rachel Wang and Peter J. Bickel. Likelihood-based model selection for stochastic block models. Ann. Statist, 45(2)5500-528, 2017. ISSN 0090-5364. doi: 10.1214/16-A0S1457, URL
https://doat /10 wttpg//...../////.... 1214/16 6 AOS1457.
Stanley Wasserman and Katherine Faust. Social network analysis: Methods and applications, vol- ume 8. Cambridge university press, 1994.
Se-Yo Young Yun and Alexandre Proutiere. Accurate community detection the stochastic block model via spectral algorithms, 2014.
Anderson Y. Zhang and Harrison H. Zhou. Minimax rates of community detection in stochas- tic block models. Ann. Statist., 44(5):2252-2280, 2016. ISSN 0090-5364. doi: 10.1214/ 15-AOS1428 URL wttphhtt//// http::://ac..org////aaaea/ 10141100..111111 A0S1428.

---

Published as a conference paper at ICLR 2023
A DISCUSSION AND REMARKS ON MAIN RESULTS
In this section, we provide some remarks on the results in the main text offer insight into our settings that differ from classical hypothesis testing.
A.1 FORM OF LIKELIHOOD RATIO STATISTIC
In this paper, our proposed likelihood ratio statistic (LRT) in (2.3) differs from that in the classical hypothesis testing:
log supaeca f(A;z.p.g)
(A.1)
sup suPsec,uc, J(AA; 2,
where on the numerator we take the supremum over C₁ instead of Co. Here we adopt different form of LRT to reduce the number of potential candidates in the alternative. More specifically, the traditional LRT in classical hypothesis testing for the continuous parameter space, whereas when the null and the alternative are both combinatorial, the LRT will have fundamentally different be- havior due to the discrete optimization over an exponential number of candidates. the numerator, replace sea, by supsec, such that under the null, the number of potential candidates on the numerator can be significantly reduced to the supremum over the boundary Bzg and we can take advantage of the symmetric community property to characterize the null distribution of the LRT, which is not feasible when the numerator is over Co-
A.2 PLUG-IN ESTIMATORS FOR AND
In (2.10), we estimate the connection probabilities p and q from (2.9) by taking the supremum over E Co UC Here apply ÿ and obtained from su,uee,,uc, for both C. UC1 and C1 in (2) be- cause p and q here act like nuisance parameters, and our inferential interest lies in the combinatorial parameter space of the community assignments (Cg and C₁) rather than the continuous parameter space of) p and q. Differentiation of p and q between Co and C1 will have a minor contribution to the test statistic. So long as their plug-in estimators are consistent (which is the case for supsecouc, ) we will have valid test statistic. Hence we also use p and q obtained from supzecouc, for C1 to improve computational efficiency.
A.3 METRIC FOR PACKING NUMBER
In Definition 4.1, we define the packing number based upon the combinatorial metric (z0,(20, n (20 =k)l, with (1, 2k) being the union of misaligned edge sets Ei 2x) and E2 2x) defined in Definition 2.3. The intuition is that for any two assignments 2j E C1, ( 23) (=0, I measures how many common misaligned edges they share. Intuitively, the more misaligned edges there are, the closer žj and z should be, and hence the packing constraint [ 2,) n ( =x)] S e is comparable to the constraint 100 0yl
for the traditional definition of packing number. When e = O, the constraint forces that 2j and 2₁: should be suffi- ciently different from each other. For example. in Example 1.1, for a null assignment 2g E Co. and 2j E Bzg if and 2j are obtained by relabeling nodes in [m] and i2 E [m]] of respec- tively, then ( 25) n E1, 2+] 2 since the edge (i,, i2) will always be contained in the misaligned set (1,2(20, 2z) E =R), which results in (B 2 0) 1. On the other hand, if we relax the packing constraint by taking / d(z, zn, C1), more common misaligned edges are allowed and we will have N (BB., Vd(=o,C) C.)) = m for Example 1.1.
B GENERAL FRAMEWORK FOR UNEVEN COMMUNITY SIZES
In this section, we generalize our theory to the community property tests when the community sizes in Cu and C₁ are not necessarily even, e.g., Example 1.3. For any & E Co UC1, denote the community size n2(2)= = xx = k i [n]]] for k E [K]. Let
CK
max max SEC,UC, 1
|nx K|
(B.1)
12

---

Published as a conference paper at ICLR 2023
When the community sizes even, have ск O. In this section, consider the cases when CK could larger than zero. We will show that the shadowing bootstrap method Section 2.4 can be applied to test the uneven community property as well. The ietemnationnhhorettt lower bound is also similar to the one in Section 4.
B.I GENERAL SYMMETRIC COMMUNITY PROPERTIES
For the uneven community class, we still need some symmetry property for the assignments in Co and CT. When community sizes are even, Definition 2.2 depicts the symmetry via the representative node set N and the representative assignment ž. However, for many community properties of inter- est, e.g., the community size test in Example 1.3, we cannot find such N and ž. Example 1.3, we are interested in testing the community size and thus there is no representative nodes. See Figure 6 for illustration.
Therefore, we define the following generalized symmetric community property pair.
Definition B.1 (Generalized symmetric community property pair). We say two disjoint community properties Co and Ci is a generalized symmetric property pair for any z, E Co. there exist permutations a E SK and Sn such that
T (o) (at)==/(((())....ret((()))))
and
(2) C1 is also closed under such transform a, i..., for any z" C1, T1,T00(2") C1.
Definition B.I generalizes the concept of symmetric community property Definition 2.2 via in- troducing the permutation transform. We can check that Examples 1.1 and 1.2 are still symmetric by Definition B.I. See Figure 6(a) for an example of choosing a and т. On the other hand, the community sizes properties
Co = {= E [K]* all community sizes = =n/K} and C1 = C
(B.2)
are also symmetric by Definition B.1 not by Definition 2.2. See Figure 6(b) for illustration. In fact, the following proposition shows that Definition 2.2 is a special case of Definition B.1.
Proposition B.1. If Co, C1 C K satisfy Assumption 2.1, then Co and C₁ is generalized symmetric property pair. Moreover, the property pairs in (2.1), (2.2) and (B.2) are generalized symmetric property pairs.
We defer the proof of the proposition to Appendix C.2. Figure 6, we show how to choose concrete permutation transforms and for Examples 1.1 and 1.3.
Community
Community
Community
Community 2
N
2
2
3
8
9
Z
6
7
2
4
10
Community permutation
Community permutation
a 1) + (1,2)
(1,2)
(1,2)
(z)
8
(zz)
8
2
4
10
Node permulation
Node permulation
(4,5, 7,8,9, 10)
T: (3,6, 7, 8, 4,5)
6
8
5
10
z'
5
8
9
10
(a) Example 1.1
(b) Example 1.3
Figure 6: Permutation null assignments in Example 1.1 and Example 1.3
13

---

Published as a conference paper at ICLR 2023
B.2 SHADOWING BOOTSTRAP FOR GENERAL CASE
We now generalize the testing method proposed in Section 2.4 to the uneven case. A key step is to generalize the boundary 2x, in Definition 2.5. Recall that for the even case, our insight is that the statistic L in (2.6) taking the supremum over C is asymptotically equal to the Lo in (2.7) taking the supremum over B.-, which is much smaller than C1. Similar insight applies to the uneven case using the following generalized definition of the boundary.
Definition B.2. For a given žu E Co, we define the boundary centered 2g with radius r as
Bzo {= Ci (i)d(z =) S r).
We illustrate the two types of boundary in Figure 7. From Figure 7(a), we can see that B Ba (d(Co, C.)). Therefore, Definition B.2 is a generalization Lo is no longer asymptotically equal to L. We need to enlarge Bz, to Bz (r) for some > d(Co. Ci) and modify the statistic Lo in (2.7) by taking the supremum over Bg- (r).
Definition 2.5, For the uneven case,
Co
C
B
B ir)
20
C1Co,Ca)
d(Co. Ca)
B.-
B. (r)
(a) Boundary Bz in Definition 2.5 (b) Generalized boundary Bz (r)
Figure 7: The boundary Big defined previously for even cases is essence a ball centered at 2o with radius d(Co, C1)
In fact, we can still apply the shadowing bootstrap method in Section 2.4 to the uneven case. All procedures are exactly the same as in Section 2.4 except that we need to replace the bootstrap statistic W, in (2.11) by
Wn sup =E (r) ISiciSn
Σ (A E E2(20 =){-1(((,)) E (zo. =)))ew. (B.3)
where r a tuning parameter to be specified in the following theorem.
Theorem B.2. Suppose C. and Ci are generalized symmetric community property pair and ск = O(1). Suppose d(Co, C1) o(n for some constant C1 2, and 1/pm o(n!-c2) for some constant > 0. We choose the radius r in (B.3) as 2 Tk == d(Co, Ci) + CkpK/ - q)) and d(Co, C,) + O(1). If for any 20 E Co. we have BB (r) O(1)) for some positive constant co. then
lim sup P(pw S aa = a and lim sup P(reject Ho) a. 1=+00 x ECo
n-000 ECo
Moreover, ((C..))))Tp.))>> = ((n)) for some arbitrarily small constant e > 0, we have
lim inf P(reject Ho) = n EC,
We defer the proof of the theorem to Appendix D.2. The scaling assumptions in Theorem B.2 are similar to Theorem 3.2. The condition [B,, (r)) = (n))) ) for some co > Os similar to Assumption 3.1. We need cк in (B.1) to be bounded to prevent specific community from being too large. By the theorem, we need to choose r 2 тк := d(Cu.C,) + ck ((((p - 4)), while p. g. Cк unknown. In practice, some sufficiently large C. In fact, for many concrete examples, even though F is unknown, we can directly construct B2g (rx). The following proposition shows how to construct (rk) for
suggest choose the radius as r d(Co, C1) + CpK/(p 9) for
14

---

Published as a conference paper at ICLR 2023
Examples 1.1-1.3. Moreover, it shows the conditions d(Cu, C1) and (ra)) in Theorem B.2 are true for all these examples.
Proposition B.3. For any 20 Co. Be (TK) can be constructed as follows.
(1) Example 1.1: 22 (Fx) is composed of all the assignments obtained from reassigning one node of any 20 E Co in [mi] to different community. See Figure 8(a) for an illustration. Moreover, we have d(Co, Ci) = n/K and |Bzo (rx) = =m(K
m' S CK, Bzg (FR) is composed of all the assignments ob- tained from reassigning nodes m m+11... +l...... m+ m' in any 2g Co collectively to a different community. Moreover, we have d(Co, C1) n(m m m')/K and (xx()))) Suppose A m > CK. Bzg (FK) is composed of all the assignments obtained from ex- changing label of nodes m + ,....,,, different community for any
Example 1.2: Suppose
K 1.
m' collectively with another m' nodes from Co- See Figure 8(b) for an illustration. Moreover, we have d(Co, C1) 2m A m (n/ K m Amm) and [B (rx) (((nn/))))
(3) Example 1.3: For an arbitrary zo E Co. (rx) can be constructed by reassigning any node of 2g a different community. See Figure 8(c) for an illustration. Moreover, we have d(Co, C1) = n K and B2, (rx) n(K 1).
We defer the proof Appendix C.3. The construction of Bz (rk) is visualized in Figure 8, We also summarize the results in Table 1.
Community
Community
Community
Community
Community
Community
Move
Move
Move
6
7
8
10
5
10
6 77899 10
10
2
6
B
10
1 1
6
10
(a) Example 1.1
(b) Example 1.2
(c) Example 1.3
Figure 8: Construction of Be, in Proposition B.3: (a) Co is that nodes (1,2,3) 3} belong to the same community; (b) Co is that the nodes set 21, 3} and (4, 5) belong to the same community; (c) Co is that community and community 2 have equal size of 5.
We, therefore, have the following corollary of Theorem B.2.
Corollary B.4 (Examples 1.1 -1.3). Suppose 1/pz o(n1-o2) for some constant > 0 and ск = O1). We assume that ma A vn' = O(1) in Example 1.2. For Examples 11.3, with Bag (rk) constructed in Proposition B.3 our test for the hypothesis Ho z Co versus Hi x E C is honest, i.e.,
lim sup P(reject Ho) n EC
Moreover, if T(p, q) K- (2n=)) for some small positive constant e, we have
lim sup PP(reject Ho) 1. n-00 Et
B.3 GENERAL LOWER BOUND
We also generalize the information-theorete lower bound in Theorem 4.1 and Theorem 4.2 the uneven case. Similar to the even case, we need to define the packing number of B (r), which follows the same definition of N (Bzy: e) in Definition 4.1. We then have the lower bound of the general follows.
Theorem B.5, Suppose 1/p, = o(n' -2) for some constant C2 0, < 1 - for some constant 5 0 and cx O()). If there exists zo E Co and some d(z0, C1) O(1) such that
15

---

Published as a conference paper at ICLR 2023
d(zo,C1) C1) n/K
(ro((r))
v z( (rk))
C1)
Example 1.1
m(K -1)
Example 1.2
n(m A m')/K
m' I cк
Example 1.2
2m A (n/(n/K K m Am)
O(K (n/ Kymmnn')
m m > ск
Example 1.3
n/K
n(K 1)
n
Table I: Important values for general cases of Examples 1.1-1.3.
(r).))()))))))o ((z, = Ollog n). and
d(z0, ()) n-000 log (Bzz (l(zz
lim sup
<
(B.4)
then lim inf 2 n=+00
Remark B.1. If we choose = d C1), as B = Bz, (d(20. C1)), (B.4) reduces to (4.1). The relaxed assumption on r == d(20: C1) ) + (11) can give us a better lower bound.
We can also generalize Theorem 4.2 to the following theorem.
Theorem B.6. Suppose 0 < q < & 1 8 for some constant 8 >> 0 and lim, ((Co.C,)) co. one of the following conditions:
(1) d(Co, C g) I for some sufficiently small constant c;
(2) limn-soo d(Co, (p, q) co, but there exists zo Co and some d(zo, such that lim -cc d( zo. [i) g)/log N (B2 (r), < 1,
satisfied, then lim rCoo, C) 2 1/2.
n-
We defer the proof of the above two theorems Appendix E.1.
To apply the general lower bound theorem to Examples 1.1-1.3, we need the following proposition on the packing number.
Proposition B.7. We have the packing number N (B (TK), dd(zo, Ci)) for three examples as follows:
Example 1.1: (N.,,, (Fk), v d(zo,Ci) m;;
Example 1.2: (TB2,(TK), / d(20) (1) = 1;
Example 1.3: ((Bz,TK)) v d(zzz C1)) = n.
We defer the proof Appendix C.4. The results also summarized in Table
Since тк = d(Co, Ci) + ckpK/ 4)), where cxpK/(2(pp - 4)) = 0(1) and d(Co, Ci) = d(zn, C1) by the symmetry of Co, C1, have that rx = d( (((0, C1) + 0(1). Applying Theorem B.5 and Proposition B.7, we have the following lower bound of same community test in Example 1.1.
Corollary B.8. For Co and C₁ defined Example 1.1, if 1/Pm o(n=-o2) some constant 02 0, - 5 for some constant ó > 0, Cg O(1) and
lim sup (p log m) < 1,
we have inf r(Co. C2) 2 1/2. 22-000
Applying Theorem B.6 and Proposition B.7, we have the following lower bound same community test for groups in Example 1.2.
16

---

Published as a conference paper at ICLR 2023
Corollary B.9. For Co and C₁ defined in (2.2), if np oc, < <.0 8 for some 8 >> 0 and
lim sup (p. q) <c.
T x-+20
for some sufficiently small constant e > 0, we have lim inf rnniinrrr...a rCo, C1) 2 1/2.
n=
For Example 1.3, applying Theorem B.5 and Proposition B.7, we have the following result.
Corollary B.10. For Co and C defined in (B.2), if 1/pm o(n' for some constant C2 0, << 1 for some constant and
lim wusppp/ppee logg)) < n-+00
have inf ((Co: CT) 2 1/2. R2000
C PROOFS OF COMMUNITY PROPERTIES
In this section, we mainly focus on the proofs concerning community properties, including the generalization of symmetric community property pairs from even to uneven cluster sizes, the size of the ball Bz (Tx) in three examples, and the packing number of the ball in each case.
C.I PROOF OF PROPOSITION 4.3
Example 1.1: In this case, for a given 20 E Co. we have derived the form of Bzg For any 2g E P(Br.: dlzzo C()) we know from Section 2.4 that they are transformed from 2g by swapping of the first nodes with another node from different cluster. The node among the first m to be swapped 8 E [m]] cannot be the same for the two assignments, otherwise [E1,(Z2,, 2)) n E1,2(20,2)) 25)l 2 [E1(20, 21) n E
Vd(zo,C1) C1). Thus each P(Bzo: / d(2 C)) corresponds to different swapped node among the first nodes, and we have ((B.., / /d(20,C C1) I m. On the other hand, for the given assignment 2u, we can construct the following set [= we take a set of nodes S = {81, 82, 5m) from a cluster different from the cluster to which the first m nodes of belong. Then for each k; we swap the cluster assignment of node & with node Sk. = L..., m, and obtain the corresponding alternative assignment øg. Then for any two alternative assignments and 2j obtained this way, have m. Example 1.2: For a given 2u E Co and the corresponding boundary Bio, it can be perceived that [( R0 /d(zo. C1) N (B 2 0) 1, because any Ba, involves swapping the set S2 that Vzz, Zj E B2o1 (1,2 2)) n E 2 (=0, 2,) 2 m m' (n/K m A m²).
- n/K-1
(200 2,) EnE (22 2,)1 S 4. Thus NB v /d(2u,C))
C.2 PROOF OF PROPOSITION B.I
To prove that Definition 2.2 is special case of Definition B.1 when the community size is even, it suffices for us to construct a concrete community label permutation a and node label permutation satisfying Definition I. based on N and Here we use Figure Given any z, =' / E Co. we first construct a. Since ZN = zy = ΣNo by Definition 2.2, there must exist E Sx mapping
illustrate the construction.
z' on the support N, i.e., o(æx) z'y- For example, in Figure 6, we construct a swapping communities and 2. After matching the community labels, we now construct 7 in order transform (2) z'. Since the community size is even and a (2N) = 2'y- (=)) and z' have equal cluster sizes on the support of S Therefore, there exists E S, such that (a(())==) = z'y= and (()()))) = (=)) = z'y- We can see the example of J in Figure Using and constructed above, can check that a(z) = 2'. We now check the last condition in Definition B. For any z" E C, since 7 is invariant on N, we have a (2K) = a (zKr) ~ = By Definition 2.2, the alternative community C1 is closed under permutation the support of N, we have 7 (x")) E C, Therefore, we check that Definition 2.2 a special case of Definition B.1.
Since the property pairs in (2.1) and (2.2) symmetric property pairs, they also generalized symmetric property pairs following the preceding arguments. As for the property pair in (B.2), we see from Figure 6(b) that for any two assignments 2, Co, since they have equal community
17

---

Published as a conference paper at ICLR 2023
sizes, take to be the identity map and there exists S, such that 7(2) = z'. Then for any z" E C1, since T does not change the community sizes, we know that r(2") still have uneven community sizes and r==") E C₁. Therefore, by Definition B.1, the property pair in (B.2) is generalized symmetric property pair.
C.3 PROOF OF PROPOSITION B.3
Example 1.1: To construct z (rx), we need to find all the assignments in C₁ whose distance from 20 is no larger than d(Co. C1) by an extra constant term. To construct assignments in Ci closest to 2o, we would pick one node in [m] and reassign to different community (see Figure 8 (a))- Assignments constructed in such ways will satisfy d(20, 21) = d(Co.C) C1) community changes to any other nodes on the basis of such construction, then d(zo. 21) would increase by at least n/ K 2, which exceeds the constant level. Thus Bzo (rx) consists of all assignments constructed by moving one node of zu in [m] to a different cluster. Since we can pick m nodes in total and reassign them K - different clusters, 20 (rx)] [ 1)m = (m). Example 1.2: For an arbitrary E Co. without loss of generality, we assume that m S m. Then when m & CK, construct assignments in C₁ that closest zo. need to reassign nodes m + ,....,,. m + m' collectively to different community (see Figure 8 (b). Such constructed assignments have distance d( 21) d(Co, C1) = m'n/K. Similar the previous example, any community changes to other nodes on the basis of such construction would result in an increase Therefore, Bzo (rx) consists of those assignments in C₁ m'. Since there are K - 1 other clusters to
n.K. If we make
of ((z,, 21) by at least n/K m'
constructed by reassigning nodes reassign in total, we have [a (rx) K - = O(1). On the other hand, when m'' > сk. then we cannot reassign nodes + 1,..., + m' collectively without exchanging with other nodes, otherwise, the community size bound will be violated. Then d(Co, C1) and B (TK) is exactly the and the claim follows.
1,
same as the even Example 1.3: As for the hall Bz, (rx) for an arbitrary 2g E Co. to transform 2p into an assignment reassign arbitrary node to different community, and d(z0, 21)
21 C1, the simplest way d(Co, C1) = n/ K X n. Further community changes will result in increasing in d(zo, =1) that exceeds the constant level. Since we can obtain such 21 by reassigning any one of the n nodes into the other K" 1 clusters, we have B (rx) = n(K 1) O(n).
C.4 PROOF OF PROPOSITION B.7
The arguments for Example 1.1 and Example 1.2 are almost the same as in the even cases and are hence omitted.
Example 1.3: For a given zp E Co, from previous discussion we can see that the ball Bz (r) with d(20, C1) + ((1) is composed of all the assignments that differ from 2o by one mis- aligned node. For any 24, 2j PP PB (r), / [[== C)). the misaligned node cannot be the same, otherwise (8,,(20, =)) n 21,( 2;)l 2 n/K K > V C.). Thus we have N (Bzo (r), v /d(zo,Ca) S n. Also since the set { where each z is obtained by reassigning the node & into another cluster obviously satisfies the condition that {& (20, 2;) n & (zo, 2,)1 + (E2 2)) n E 2z)1 1, we
have that N (B2. (r), ((2o.C.) n.
18

---

Published as a conference paper at ICLR 2023
D PROOF OF INFERENCE RESULTS
In this section, we provide the proofs of the theorems on inference results. We will first prove Propo- sition 2.3 which implies that the p-value based the maximal leading term Lo can be estimated without knowing the true assignment, then we prove main Theorem 3.2 using Proposition 2.3 along with other lemmas. The proof of the technical lemmas will be deferred to Section F.
In the following part of our paper, we use c, C, 02, C1, C2 ... to represent generic constants and their values may vary in different places.
D.1 PROOF OF PROPOSITION 2.3
To prove Proposition 2.3, need the following generalized version of Lemma 2.2 stated previously
Lemma D.1 (Shadowing symmetry lemma). For a given E Co and given radius r >> O, we list the assignments in the ball B, (r) as 21, .2,..., (r)( Define [r)) -dimensional vector L as
(Lz)& g(p.9)
Σ
Aij
Σ
Ais) for k 1,,,,...,BB.U..
(1.))E1((2.4))
Suppose Co and C1 satisfy definition B.1, then for any 20. 2/1 E Co, we have BB (r) = 1B& (r)( and Cov(Lz.) is equal to Cov(Lz;) up to permutation, i.c. there existing a permutation T E ()) such that Cov(L )m Cov(L (o,((L)))(())) ((())(()) for all k- l.... B20 (r)).
We defer the proof of Lemma D.1 to Section F.1. Now we are ready to prove Proposition 2.3. In fact, the boundary in the definition of To can be generalized to the ball (r(r) with r 2 TK = d(Co,C,) + cxpK (2(p 4)) and C For the true assignment 2" E Co. we have that
Lo = sup
(l
Σ
Aij
Σ
Am)
m.B., (r)
(1.))E8(3*'
= =g(p,9) sup
Σ (Ai ((Av))(1((())) E E2(2", [((,)) E1
2xEB (r)
{
L Σ (X (x)) + I(p, q)no + Sn.
+ slpp.))m + 8n = g(, 9)00
sup
kellB.- (r)1l
00
where the vector X E gll BB_ (r) and
(Xi)a (A E(A (1((1.)) E E=''" 11 ((.j)) E=(,,, 6n = O(pn)
and V / C1) (p(1 p) + g(1 4)), Hu = diC -
We can see that for different (i, the vector Xis are independent of each other. For a fixed k [ (r)]], when (i,j) & Ei,((=,, (x), (Xij) 0. When (i, E E =k), under the regime 1/pm o(x)-=x) for some positive cg there exists B, 1/ (1n(1-)))22) such that (Xig)x/ < Bn and (log 2d(Co, B,, (r))) < n -a//2 where d(Co, C1) = o(n²). Therefore, following very similar proof as Theorem 2.2 and Corollary 2.1 in Chernozhukov et al. (2013), we have
g(p.g)
sup
Σ
(X1))a/00
sup kr]l
Z
kr[l
19

---

Published as a conference paper at ICLR 2023
where 7 ~ No, and Σ., Cov(L:-). Therefore, we have that
sup rER
P(Lo st) -P((0
sup ke[ (r)1
Z + g(p. uo <t)
sup teR
P(Lo s 1) - P(o0
sup (r)l
Zx + g(p, 4)00 + on S1)
sup
P(ao
sup
Zx 9 9)10 + 8n 5 - P(oo
sup
Z plp $1)
1ER
(r]]
kEl (r)
< {1)
sup tE
P
sup
2 (t - gl. 9)/ /ool s 6n/oo)
B (r)ll
We know that minkel B. (r)] Var (Zx) = N(o(p. 9) 2(1). log B3- (r)] Ollogn) and
0n/00 ((n-1/2) Then by Lemma 2.1 in Chernozhukov et al. (2013), we have
sup
P
sup
2x (t g 7)1 /ool S 6n/0o)
tE
B. (r)ll
8n
V2 B (r)
Var Var(Zz)oo/bk (r)]
min
S n -1/1
And thus we have
sup
PLLo =) Pi
sup 7, + g(p, 2)00 St) = o(1) kEIlB,- (+)1)
ER
Following the same procedure with x" replaced by zo, we also have
P(Lo(z)) 51 - (P(00 sup (z'), + gl. g) 21) =01);
sup EE
kell (r)ll
where Ż' NO, / and Σ., Z.. By Lemma D.1 we know that Σ., and E., are equal up to permutation. Therefore, the claim follows. We may also note that the validity of the proof does not depend on the values of p, q as long as the regime is 1/Pn o(n!-e2) for some constant
02 0, and thus the statement is also true for Lo sup:LEB.-(n) (r) g 9) (2 ((t))eesse Au
Easeesior Au) with plugged-in estimators p, q.
D.2 PROOF OF THEOREM 3.2
In fact, Proposition B.1 shows that the symmetric community property pairs defined in Section 2 are general symmetric property pairs under the general framework, and Theorem B.2 is generalization of Theorem 3.2 under uneven cluster sizes. Thus we can just prove the more general Theorem B.2 and the proof will also apply Theorem 3.2.
The proof of the main theorem requires the help of Proposition 2.3 and the following lemma that shows why the maximizer the alternative assignment space can be restricted to the ball centered at the true assignment 20 E Co.
Lemma D.2. We denote z the true assignment, and B (rx) is the ball centered at 2* with pk radius FK d(=",C1) + 2(rタg cr. CK O(1). Under the same conditions of Theorem B.2, when z" Co
sup log fA; 2. sup log f(A; Op(p)) =EC,
(D.1)
=rR)
20

---

Published as a conference paper at ICLR 2023
Moreover, for any true assignment 2², we have
sup log f(A Φ) = log f(A;2" ... f Or(p.).
(D.2)
zECoUCt
With help of this lemma, instead of taking the supremum over the entire assignment space C1. we are able to restrict the maximizer to a much smaller set Bz (rx) ) so that the Central Limit Theorem can be applied. Recall that the boundary B.- defined in Section 2.3 is in essence ball with radius d(=", C1). We defer the proof Lemma D.2 to Appendix F.2.
Now we are ready to present the proof of Theorem B.2:
We first define the a quantile of the LRT statistic. Let Cw be the 1 a quantile of Wn, condi- tioning on Å and A, i.., P(W,, & Cw(a)) by
a. We then estimate the quantile of LRT
= g Cw (a) + g(p M),
(D.3)
then it can be seen that the two events {LRT 2 9a) and {pw S a} are equivalent. Therefore, it suffices to show that lim sup=- P(LRT < 9.)
The proof is mainly composed of three parts. The first part is to briefly illustrate the derivation Lo as the leading term of
log-likelihood ratio, the second part is to control the error caused by plugging in the estimators of connection probabilities p. q. and the third part is to illustrate the multiplier bootstrap as a valid approximation of the LRT quantile.
D.2.1 DERIVATION OF THE LEADING TERM FOR LRT
For a given true assignment =² E Co. by Lemma D.2 we have:
sup=ec; 2A;
LRT = log
SuP:ECOLC, J(A;
= sup log f(A; 2, ). log f(af [A; P. + Op(p))
sEC,
(lo 2A, - fog 2A; .0.0) + +p((x))
sup srEB,+(r)
where r 2 TK := d(Co.C1) ccppK/ 4)) and and d(C. C1) 0 In practice, due to the consistency f7, 7. when we choose the radius r = CC CpK for some sufficiently large C, we can make sure that the conditions on the radius is satisfied with probability 1 - o(1). Thus we can see that the LRT is essentially the supremum of the log-likelihood difference between the true assignment =" and the alternative assignments in the ball B (r). We further expand the log-likelihood terms and can write
LRT
sup (r)B.-(r)
M Σ Aij
AU)) + log { (-2) (1)))))()))
Σ
T (mi (==,, ;x) - ==22=",,,, ,(=)
(65))Ea((+).x))
+Op(pn)
Lo 8n.
where 8, uuPzyen.-(m flog -1- (119/(11 -D) (m12",22 (1)0)/10)))mm((> =2(222220 2w + Op(Pa) =
Op(pn), and T.o g(p 7 sup, EB, (E(t))ess((x==))) Aij E(I.)EE Aiz)- From Proposition 2.3 we have that lim suPres [T. < 1) - PT(( < 1) for any 2n E Co- Therefore, it suffices for to prove that P(LRT 2 qa) 20 E Cg. Now we are ready to prove the validity of the multiplier bootstrap for estimating the quantile based the leading term.
o(1) for given true assignment
21

---

Published as a conference paper at ICLR 2023
D.2.2 BOUNDING OF ERROR CAUSED BY PLUGGING IN P.
From previous sections, we know that
Lo(zo) = =0(0. Do
Σ (X (Xi;)k g(0.0uu + Op(pn),
sup
(r)
where (X,j) = (Aij E(A we give the following notations:
(I((1,) E E2(20, 2사)] - (( E & (zo. )))) For any 2n Co.
To = sup kell (r)) ou
E
sup
Σ (G
5S
sup Br
1 Σ
Gola
kell (r)ll d0 {
60 [<)
i<j
and denote
Wn = Wn
sup
(2) Σ
X sy)aei
kellB (r)]]
icj
where (Xi))s (A., (p (A((i.)) E2(20, (((jj) E (10, 24)) and the ad- jacency matrix À is generated by p. 7. and T = diCo, (i) - P) + q( 7) Egg and Ey the independent mean zero Gaussian vectors with covariance matrix equal to that of X and X respectively (fEig) h = if (i.j) & E1,2(20 2x). and the same for (E.j hu ) feighes are i standard Gaussian, By Corollary 2.1 in Chernozhukov al. (2013), have
sup IP (To < t) PP (Eo < t) o(1);
EER
Also, by Lemma 3.2 and Corollary 3.1 of Chernozhukov et al. (2013) we have
sup ER
P
Wn < x(xx))) - IP (=6 < t) or()).
We let 0 and E be the covariance matrix of the vectors {Eisstusda/oo) and
(Ecs } respectively. Thus for k, E [[])((r]] we have:
x Cov
(Eig bk
((shh))
= of
17
Cov
(5)
R.
(Xi))i
i<
E2(20, 2x)
E2 19) g) + (20, zx) n x))p(1 p)
d(Co, (p) - p) + q(1 - -9)
Accordingly,
D Cov
(Xx,))) X
x<)
Eg( 2 1 (= 21) 2)) ② + ( 2)) p(1
NE
d(Co. C1) (p)
- p) 91 -
2x) 2) (a
2) p(1 -p) +
(p(1-)) ()) Op C1)
Then have
Op(d(Co, CP)/p/) = =Op( 63
Au = max
+
k.l
Vn²Pm
22

---

Published as a conference paper at ICLR 2023
Thus by Lemma 3.1 in Chernozhukov et al. (2013), there exists constant C. such that
(E < () - P( < 0) < / (1 v log (2 (r)1/ Op(n 1/6-ca/22)
sup ER
and thus
sup tR
|P (Eo & t) - P P(6 & ()] - op(1),
and in turn we have
(Th < - P (W, < < - op(1).
sup ER
D.2.3 VALIDITY OF MULTIPLIER BOOTSTRAP IN ESTIMATING LRT QUANTILE
Now recall that Ow, (a) is the a quantile of Wn conditional on X,j, and we would like to control the order of Cw, (a) in order to bound the error in estimating the quantile of LRT. Give a constant t /20, we have
P(W, > tetlloogo X:,) = P(E > log + 01(
Eogb > tv Vlognn +or(1)
P
k B2 (r)]l
iej
x B:o (r)le 2/2 log + orr = Or (100-1912) + (or(1)=0p[]
Thus we know that Cw. (a) = Op(vlogn). We know that Ca 010,7)000m (a) + glā, Dño.
LRT = Ln + 5n and also lim,, suPIeR [P(Lo < t) P(Co(2)) < <t) 0. Therefore,
P(RT 2 qa) PLo on 2 qa) P( 20) + 6, 2 qa) + o(1)
= P(g(f. NooTo + (p.9)H + 6n 2 20. To
Ww (a) + 9 17)) + o(1)
P =P(TO
To 2 T0 C
- Po 4u
5n
(a)
+ o(1
9
W.
00
We have that [ōp - 0ol = Op((v d(Co, C n) and Tim pal = Or(d(Co, Or(d(Co,Ci))//au C/n////n)
Therefore,
To 2 Cw, (a) + Ci Civd(Co, C1)
C W; (a) + C2d(Co,
8n
PLRT 2 9o) =
+ o(1
oon
Jon
g Moo
Pn = P To 2 W. (a) + C1 v logn/(nt (n'nn/n2pn)))) pn) + C2Vd(Co, CD)/n Cav d(Co,
+ +0
= =P(To 2 Cw. (a) + A.) + o1))
where A, = (p(n for some positive constant > Now from previous results we have
PPRRT 2 )x) al S (T, 2 Cw, (a) + Am) - PP,W, 2 Ow (a) +A)] + IP,, v 2 Cw. (a) + Am) P(W, 2 Cw, (a)) + o(1
< <(((,, -Cw. (a) < A (1).
Now we study the distribution of Wn: if we denote Ye 1 Eieg (X s)ee then YA |2 X
50
N (0, of), where of Eieg( (x,, / and sup, [B(o 1| S /0/00 1| + or(1) 0p(1).
Also, (X,)) < 1. Under the event A (p = [(1) n (ύ- = o(1)) with P((A) o(1, by
Bernstein's 's inequality, we have
1 o
370
P Ex(o > 1/2) S 2exp
(T] + 1)62
2 exp
14
23

---

Published as a conference paper at ICLR 2023
where Px and B& denotes probability and expectation with p and fixed and consider only the randomness of X. Also
Px (min of <//) - 2 P - Ex(ox)] 1/2)
= B2 (r) exp (- 3
= 0p(1);
14
where the last (p(1) term is due to the fact that 03 32 (mp(p)a) = (2( and (r) = 0(
Then by Lemma 2.1 Chernozhukov al. (2013), we have
P([,, Cw. (a:] s A.) P(( max Y Cw. (a)) S An) S sup P( max Ye - S A.)
#ER
log (min of (a)) }) -
Op An 2 Bz (r)
and thus lim sup=- PLRTT 9n) =
As for the Type error, from the preceding proof we see that P(RTT 2 9.) = a + (1), and the convergence of the (1) term is independent of 2² E Co due the symmetry of Co. Therefore, have
sup Preject Ho) = sup P(LRT qo) = a op()), ECo
ECo
and hence the claim follows. As for the Type II error, when the true assignment is 2" E C1. by (D.2) in Lemma D.2, have
LRT log sup f(A;2,p,
SUP:ECoUC, 2(A;
SUP:EC, J(A;
log J(A; ,p Op(pn).
llog f(A; x" :)99)
supsec,ue, f(A; 2, p,
And since ōo- VCl Ci)., No -dCoo Ci ())(n and Cw, (a) = Op(ylogn),
have 9a = g(,, ConC (a) + g(p, Th0 + -0. Since the convergence is independent of =", we have for any true assignment 21 E C1.
inf P(reject Ho) = sup P(LRT q,) = op(1) rec
Ecc
E PROOF OF THEOREMS FOR THE LOWER BOUND
In this section, will prove the theorems for the lower bound. Similar the upper bound, since Theorem B.5 and Theorem B.6 are general versions of Theorem 4.1 and Theorem 4.2, we will only prove the general versions and the proof can be applied to Theorem 4.1 and Theorem 4.2, too. Also, the proof of Theorem B.5 is actually based on the proof of Theorem B.6 under stronger regime. Therefore, we will prove the two theorems together: we will first prove Theorem B.6 under more general conditions, and then we will apply the proof of Theorem B.6 to the proof of Theorem B.5 under stronger conditions.
E.1 PROOF OF THEOREM B.5 AND THEOREM B.6
The proof proceeds in the following order: first prove the results under the two conditions of Theorem B.6, namely the proof of Theorem B.6 (1) and the proof of Theorem B.6 (2), then we provide the proof of Theorem B.5.
24

---

Published as a conference paper at ICLR 2023
E.1.1 PROOF OF THEOREM B.6 (1)
As for the minimax rate, we have:
r(Co, min V
sup HapPP& (1b = 1) + sup P. (v - 0
=E
=EC1
Peo (v = Ps, (v) 00)
2
min
where 20 and 21 are fixed cluster assignments in Co and C1 respectively. For a given adja- cency matrix A, we know that v0 is a function of A, and the only information of A relevant to classification of the true assignment is {Aij. (i,5) E (za, 21) UE 21)}- Larger sizes of E (=0, 21) and E2(20, 21) will provide more information and lead to smaller type I and type II er- rors, Thus, the worst case is when the size of & (zo, 21) and Ez æ1) obtains the infimum, i.c. d(zu,2) = n1 (1 21) V n2 n2 21) d(Co,C C)).
To obtain inf { sup:eec (= = 1) + supsec, P=(V = 0)}. the optimal method & must be the mode of the posterior distribution. For the convenience of notations, we denote L(z, A) as E, q), and n, as n. (2, 21), i = 1, 2 for short:
L( A) x P ELLEELLO Au (1 p) - "0 Aus q _ (L Au - 9))²² "0 0)0²~2(0s -12-Ennnee ELLNEEZ0DD= Ag
L(21, A) 1 (LNEEEAN Aud (1 m)²²² 2 -0==EaJEE22t0oo- Ass
D (as))Eett)) Au A111 - 1)(² -V.-Ennneettaa Ad
and correspondingly.
((A) =
= {
O, if L(20, A) > L(21,A); 1, 120,, A) S M(2, A).
Then 12.. (0 = 1) = P2,, (L(z,, A) S L(21, A)) and Ps, (U = 0) = Ps, (L(20, A) > L(21, A)). Without loss of generality, we assume that nı (zo, 21) n2 21). Then, if we expend the size of E2(20, 21) to be the same as E (20, 21). adding i.i.d entries {Ai,, (i.j) E E 21) E2(0 21) conforming to the same distribution as (Aiy, (i. E2 21)), more information will be provided and the error rate will decrease, where Eye (20, 21) denotes the set expended on E2 21), and have:
L(=o. A) 1 (aNEeetoo Au (1 - p)m² E(ssEes1000))) Aus Canceffooen) Ass (1 9)) 11 n1 -EEsseeee Av n1 -E..neef( Au L(=1,A xp Panneetoo As (1 (1-p) p)
D (UN)EEE As (1 m) -U-,))) (50.1)) Au
Thus we can obtain a lower bound on the minimax rate:
r(w) = Pro (L A) < L(21, A)) + P.,, (L(z0, A) > I(21, A))
2 P.o 20, A) S i(2 A)) + P,, (I(e0, A) > [(21, A))
P
Σ
Ag Σ AUj + +P...
Σ
Aij
Σ Ang)
(2o.)))
(1)))E1(300:11
(1
2 2P
X
rm)
where {Xu} Lid Ber(g), (Y") itd Ber(p), and {X") are independent to (Y").
Now nn = dd(Co, Ci). and both p and g change with n1. We have E[ Y E[X 33
p(1 - 9) + + p). Since 0 < < <p< - 5, we have ōp < p(1 q) + 9(( - p) < 2p. Thus
B([X-- - yu B[X Y 313) x p. Similarly Var(X Yu) x p. Thus,
ΣnL TE X yu= EE EX a 33
n g) + ((11p))))
+0
Var EVl {X 1u) 3/2
3/2 (/2 - 4) + +1 (1-
VmP
25

---

Published as a conference paper at ICLR 2023
Therefore, by the Lyapunov's ' Central Limit Theorem and the independence of {Xx" and {Y"), as - DO, we have ΣV=
X
Σx= Y" 4 N(ni (q p), m1g(1 9) + p( 1 - p)). Therefore,
2 0) = 1 1 ( VTi(D 9)
P
+ o(1)
vp(1
p) + q(1 - 9)
==1
==1
u=1
u=1
When lim sup no I (p, 1) = (1)), we can see that p - q o We have
n=+000
[vp v/)² + (vT v1- -
1p, -2 log 1
2
(p- 9)2
(p- 9)²
(VP + vT)
+ [VI- p vI 9)
(1 (1+)
8
(p - q)
2 p( p) (11 9)
(1+ + (11))
Thus,
if
lum n1 (p)
S (3/44/22 namely,
lim sup Vn n
0/Vp(1 p) q(1 9) S lim v 222 2/5 4 (3/44, we have
200
T1
11
PP
X
2 1
( - 9)/ vll p(1 +) 9)) 1/4.
==1
and
r(Co: C2) 2 2(1 - ( 9hpi-/9/VVl11110 + +1 (1)) g))) 2 1/2.
E.1.2 PROOF OF THEOREM B.6 (2)
When d(z0, (p).g)))))))) + oc, if there exists a 20 E Co and some r = d(zg,C1) + Q(1 such that lim = d(Ca, [p) q)/ log N ( (r), 0) < 1, then we take O-packing (r).
(denoted P00)) for short) of the ball Bz (r), and we have:
P=(V- = oo}
C1) = min
sup PupP=(0) = 1) + sup = 0) 2 min P.o (1 1)+ sup
+
LEEOo
=EC;
=EP(O)
Pz(1= = 0 (A= {1)}
min
P (1 = 1/A A TTP: (A A) + sup =EP(O)
(A = A) + (()(A) = 0) sup (A = A) A1) } Σ (A(b(A)= = 1) SA
min
=EP(O)
where the sum over A is the summation over all possible realizations of the adjacency matrix A. Thus the optimal method yb in this scenario should be:
(A) = { O, if L( A A) 2 sup SuPzEP(0) L(2, A); 1, if L(za, A A) < SUP,EP(O) L(z, A A).
and we have L(xu, A- = A) < sup=EP(o) L(z,A A = A)
rCoo 2 P2, (v + + sup
P = 0) P 200 [(20, A A) =EP(U)
sup L(z,
= A)) L(z,A A
=EP(O)
sup P. L(zo, A A) sup
AzzA==A) A))
sEP(()
zEP(O)
Pro sup log L(z, A = A) - log L( A = A) > 0) (0)(0)
sup P. sup log L(2, A A) - log L(20, A = A) AA))50) 50)
sCP(0) SEP(()
26

---

Published as a conference paper at ICLR 2023
Similar with the case when d(20, (p))( O(), we expand each E2(20, 2) to E/ 2) (or E (20, 2) to (20, 2), we use the former notation for convenience) so that E 12000 2) and E2(20, 2) are of equal sizes, and then we have
r(Cu. Pz0
sup =EP(O)
Σ
Aij
E
AU) 20)
(1.))E2 (z0.2)
(
sup =EP(()
P2
sup (EP(()
Aij
Σ Ais)
50)
(A.))EE) (20,2)
(
P
sup (EE((0)
Σ
Aij
Σ
Ais
(1.))E2 (20.2)
(1J))EE
(20.2) Σ
ni (20.2)
Pzz sup (EP(()
Y
0
where {XW} lid Ber(g), (rT) iid Ber(p). { 1 (x (x 1 - * j and
{Xx} T (8g), j. By Lemma 5.2 Zhang & Zhou (2016), we know that there exists - such that
Ni ())
Wi (50.2)
X
Y Y=
>) 0) 2 exp ( - (1 + 7)) (.)
When lim sup d( [p,, log [P(O)| < 1. for sufficiently large n we have (1 + 7)d(20, ())(p)))))))))) 9) log [P(0),, and since > (1/2)" for > 0, we have that for large enough
(1)02)
(2
P 20
Σ
yr>0 2 exp (- (1 + m)d(
2 exp
log (P(O))) = 1/IP(0)) 21 1- (1/2)
and thus
(20.22)
nu (20.=)
x1)20.2)
(20.2)
rCCo, C1) 2 Pz0
sup #0P(0)
X
yuu >
P.o
sup 2EP(()
X
Σ Yuu
00
Ti (20.2)
2 21 (a/((22)//P000))
[P(O)
= =1 - (o)
Y < 0
1/2.
The statement is true for any O-packing of the ball Bz (r), and thus the statement follows.
1.3 PROOF OF THEOREM B.5
Under the regime! 1/pm o(n)-=x), take one vdlzo, J-ackcining P(Bz, (r), v dll C1) (de- noted P for short) of the ball (r), similar with the proof of Theorem 3.2, by Corollary 2.1 in
Chernozhukov al. (2013), have:
ns (=o.=)
ni (20.z)
C1)
d(zo.Cr)
r(Co, (C 2 Pro
sup eEP
X
Σ
Yu >0
2
=P
sup sER
Σ
y > 8n
T=1
l=1
u=1
u=1
d(zo.C1)
d(zo.C1)
Y + d(200,c))p - 9)) > d(z0, Cp) 9) + 8n
Pa
sup
X
sEP
d(zn, Ci)(p 4)
Pso
sup {
+ bn/Oa + o(1)
sEP
0d
27

---

Published as a conference paper at ICLR 2023
where nn = sup 1 X Ed(20.01) yz²)
sup sE Em((2 X
Em (20.2) yz) (1) and oo = Vdllo. (i) (1)( - p) + a(1 - v)), and (Ea) are stan-
dard Gaussian variables with the same covariance matrix as (E X - Ddla y + (p
By Lemma 2.1 in Chernozhukov et al. (2013), combined with the fact that d(20, (2p(n) and Pn = 03)) we have that
d(z0, Ci)(p 4) +8n/oa -Pzo sup &= =EP
d(zo CiX( g) ②
S On
sup & sEP
v log nogn- o(1).
Od
We let (XHJu, Ju, be i.id Ber(g) random variables and {Y:') Ju,z be i.id Ber(p) random variables, and {X") hus and (Yr" are independent of each other. Then for each E P, d(( X
Eus dd( Yu + +,((2,, Cp)(p -q) shares the same distribution with Ed(z X E y +
d(z0, (D)(p 9). We let { be the corresponding Gaussian analog of { (Ee=l Eaao / + d(zu. Cp g))/oulse3. Then we have:
d(z
X
if J. if + j.
Cov((E Ez,) Cov(EE., E.,) O (
Thus by Lemma 3.1 in Chernozhukov et al. (2013), we have An = -1 (0(1/Vll d(z0, Ci)) and
sup & >t) 2t) s /A. (log 11/ o(1)
sup tek
P sup =EP
>t)
P2
ZEP
and thus
d()
d(za,C,) Σ
Y + d(z00 Cp 9)) > d(zu, C1(pp ( -0)
Pzo
sup
X
u=1
u=1
d(zo.C1)
d(so,C1)
Σ
Y. + d(zu, C.)(p 9)) > Cz) - 9) + o(1).
sup xEP
Then similar with previous proof, we have when lim sup limn d(z0, C2) /) log | 1,
mi (H0.2)
ne (20.s)
r(Co, C1) 2 P...
sup LEA((K)
Σ
X
0) + +o(1) 1/2 + o(1).
Also the results hold for any Ci of the ball Bzo (r). Therefore, we proved the claim.
F PROOF OF TECHNICAL LEMMAS
Now we will provide proofs for the technical lemmas used for the proof of Theorem B.2.
F.I PROOF OF LEMMA 2.2
It suffices for to prove Lemma D.I. the more general version of Lemma 2.2. Due to the structure of Lz, it suffices for us to prove that the edge-wise distance between assignments is permutation- invariant.
28

---

Published as a conference paper at ICLR 2023
For any given 2u Co and 21 C1, we have:
n1 (2(, 21) =
E
= =0)
KJAJEEM
= (z(00))))(()6)))) +4
=
Σ (foottalft))--roooodld)h)))----- (To(())())))
Then very similarly we have nz( 21) = (2 (o r20(21)) and thus d(za, 21) = n1 mzo 21
n2(=0, =1) = n1 (T o (20),, T o (21)) V (2 o (zz), 7 oo)()))) = d(r o o t oo (21)). This
suggests that the permutation T o does not change the distance between assignments. Also,
[E) a)) N =1)1= z1)1= =
Σ (.J.EE
((20(1) = =o a1) +0)
21)
+1)
KHHJEE
= = (20) ot
And similarly,
|Eg(2o, =1) n (=0, =1)1 r o(())) (z))) roo
Thus the cardinality of the intersection of the sets E i = 1, is also invariant under the permutation TOO.
Now for any 20, 26 E Co, if T o = 2 and d( z(20. x1) = d(zo, C1), from previous results we have d(z): J (())) d(z,,C) If there exists an assignment z E C1 such that d(=/, z1) < d(26, o (21)). then d(zo. (r oro = d(zb. 2 < d(2o, C1) due to the fact that a is one to one mapping. Since 2p (r - (=6). we know that C1 is closed under (r o)-1 and
(T o a) (21) C.. This is contradictory to the fact that 21 argmingec, d(z0, 2). Therefore, d(=6. Ci) = d(=b,
= d(zo. CI).
Similarly, if 21 E (r), then r (21) B2g If 2f E B Therefore, o is a one to one mapping from Bz, (r) to B2g (r), and B2 (r) [B,(r))
(r), then (7 (z)) E (r)
Now for a given radius we find the permutation E Si8 (r) such that T(2) r ooo(2)) = 2
for 2; E Bz (r) and 2 E BBg (r).
When the true assignment is zg, the (k, 1)-th entry of the covariance matrix for the vector Lzo can be expressed as
Cov(Lz))r g(. ((.(0)))(( 4) ())g 9) + & +1) (20 21) pp1pp1 p))
- =utp://ffhoooooooooocoossseoooaa 4)
pp)
= Cov (o(ox))
Σ
Aij
Σ
E
Aij
Σ An))
((((=)))((E
(((((())
((((=())<(())
Cov Log(L=))r(t)rtt)
Hence finish the proof.
29

---

Published as a conference paper at ICLR 2023
F.2 PROOF OF LEMMA D.2
The proof mainly follows from Lemma 2.3 and Lemma 2.6 in Wang & Bickel (2017) with modifi- cations for the function F(-) and G(.). We provide the sketch of proof as follows:
We first define the count statistics as proposed in Wang & Bickel (2017);
A (=(i) = a, x(i = b) ~ Ber (Ha ,), , j.a, b b [K].
where Ha,b = = A1 if a = b, and Ha,b = q = A2pm if a + b. H P....
Oab(z)= Σ
1 (=(1) a, = b) Aij.
jæi
L ==
An Kn = n²pm. pm.
jm
For two assignments 2, The confusion matrix is:
Rx,a(2,2) = =n Σ [ =a)
By definition, we have (n)(2) n/K S CK. V2 Co UC, Vk = 1,2, K. We let m(z) denote the number of within-cluster edges, and assume
nx(2) = n/ K + ak. |ax| S CK. k = 1,2,.... K,
K
Σ
ak =0 0.
k=1
Then
KK (n/ K + azx)² -n n²/K n
K
2
((z)=
k=1
dj
2
2
2
n² n2/K K -
+ K2
2
Therefore, 22 E C₁ we have A(z) + n2(2, z') n (2,222) = 7(='), |n2(2, - ni (2,z')]
(π()) 7((²)) < K Kex/
2. Thus, we denote x" as the true assignment, and Vz E Co UC, we have
1
Ho.b ) + +(2) log(1 D) (n(n 1)/2 -)(=) log(1 7
log f(A;,,
Oa,((2) log
2
1- Ho,b
0,
K
1
(log (u)(=) (log Sa, + log log(1 Hatb)) +C(=*)+0r(())
2
0,
Pn
K
Oa.(z) (log Sa. + +O((m))) + log
2
Un
a,b=1
where C(=*) = 712 log(1 - P) + (n(n 1)/2 - -m(=")) log(1 - 7) We let F(O /m)) =
Σ On.(()) log S.,b
H. and F F(RSR) T (z)) Σx (RSR (z))o,b log i-Ha.s' where
S.,
As
R(2) = R(z, =*) and RSR (=) = R(z, ==x==*))"" *)SR(z,,** We denote Č C Co UC, as some subset
of assignments, and we let Vo denote the set of E C that maximizes F [SRR (z)). Obviously F(.) is Lipschitz, for en + 0 slowly,
F (O())\/u)))) - -F())/)a)F((RRRRR (z)) SC- Σ
Ok.(2)/Um - (RSR' (8) k1
=0p (Ex)
k.
30

---

Published as a conference paper at ICLR 2023
We choose some positive 8, - slowly enough such that 8n/en - We take any Z' E Va, then we define
J8n = { E [K] F(RSR (z)) - F(RSR'
(Z')) ((R)R((Z)) < -ōn
Then we have
JOB (oBI(A
< f(A (
#EJ6n
For 2 E (J,. Uvel. FIRSSR (x)) F(RSR (Z')) 7 0 and |SS (2)
RSR T (Z)) 7 0. Treating R(=) as vector, choosing 21 be such that R (=1) =
min = [R(z)) - R (zo)]l2 for given C) (Js. U VV.. Due the consistency of p, G,
the function F()) is linear function with constant coefficients. We know that with probability
1 - o())
ar (1 (1-+) (=1) + +I)+ (=)
0.
de
Given a matrix A, we denote the matrix maximum norm || c=
maxçk AA,al- Letting =
mina(x) (o(2) |, and (() Oz))/u, RSR (z), have
max sf8(=1)
|X
X (21)ll > c1z - -21l/1)
P
max
X X (21)ll m
2:2=2 3 -1 =m
2K K n th
km
exp (-c mpp - 0.
m=1
where S(z) = {o())) E Sk}. Since RSR (3) - -RSR (31) = 2( - =11): 1), we have that
( (21) = =p
RSR (z) RSR (BL))
Hn
Un
And thus we probability (11 uniform on all 2, we have
F (O(3)/pp) (O(z))//u))
In turn, we have
log f(A; log f (A; + Op(pn).
Since from Lemma A.I in Wang & Bickel (2017) the high probability is uniform on all assign- ments, we have that, with probability 1 o(1), for any CV we can find z' E Va such that log (A;2, = log f(A; 2', p. q) + +p(p).) and therefore,
sup log [(A; 2, P. sup log (A;; 2. Op(n)) .Eδ
seVe
Now we consider F(RSR* T (2)):
F(RSR* (z)) ((F((
1 (C((=)) + log
2 - P)
(12(2", 2)4 ( 10--mmn =)1==((=",=)))
Pm
22 ②
1 (Ci(=))
21 D
(12(2",2) vm A1) + co(=)) pm).
+og
11 3
31

---

Published as a conference paper at ICLR 2023
d 1-p ,=)"(²))))) ap+ + log - (n(n 1)/2 - 7)(2))g and where 21 p/p x2 9/pm Pr and C1(2*) log
co(2) I A2 /2, 42 E Cu UC1.
Thus when =" Co and C C1, it can be easily perceived that VG (rr( with high probability, and hence
sup log 2 =EC1
sup log a p. + Op(pn)
(rx)-(rx)
Moreover, when x" E Č, Va C Bx-(r") with high probability, where 1* = X1K / }2)} 0(). By Lemma 5.3 in Zhang & Zhou (2016), for any z B2. ) if + 2,, then
d(z", = (()).. Therefore, Bx- (r-) = {2*}. In other words, we have
sup f(A; 2, p, ② = log f(A; z", P..) + Op(pn).
(F.)
zeč
More concretely, if we take Č Co U C1, we have
sup zECouC1
log (A; log f(A;=' 22. + Op(pn):
and if x" E C1, we have
sup log f(A; = log f(A: ...)) +
=EC;
F.3 CONSISTENCY OF PROBABILITY ESTIMATION
Recall the estimators P and q are defined in (2.9), and that 2₁ P/pp. and π22 -/Pu. The following lemma shows that Å₁ and X2 are consistent.
Lemma F.l. Under the same condition of Theorem B.2, we have
1T A₂ = O(1/ n²pp). i= 1,2
Proof. From Lemma 1 and Theorem 2 in Bickel et al. (2013), we know that log (0/(1 D)) log (p/ (1) = O(1/ /nppm) and log (Q/(1 7)) - log (q/ (1 - -))] | O11// (11p//n2p))) pn) We let Vi and 1/2 denote the logit of p and q. Then since (v, 122) is one-to-one function of (p. 9). we know the relationship between (0i, (22 and (f,g) should be i = log 01 P) and D2 log 7/(1 θ)
Then we have
Tipn
Aipr
i - -; = =log-
log 1 1-xipo
1 1-Xipo -xpp
log 7ipn
- -log Aipn + +log(1 \ipr) log(1 -Repm)
7=- dj
1+ (); -xe)pm
log
1+
log
A
>>iPn
3, A
A - ->:)pm
(1 +(l)))
+ +1+ o(1)
1 AiPn
x o A₁
and thus by previous results we have
- Aal 0 n22)., - 112
G ADDITIONAL NUMERICAL RESULTS
We present in this section some additional numerical results to further evaluate the performance of method. In Table 2 and Table 3, we provide the numerical results of the type-I and type-Il emrrs
32

---

Published as a conference paper at ICLR 2023
corresponding to Figure 4 (a) and Figure 5 at different settings of A. We list the values of the metric product d(Co, C q) corresponding to each setting for reference.
200
600
1000
A
d(Co, Ci (p..))
Type-I
Type-11 emorr
d(Ca, (p) q)
Type-1
Type-I1 enoor
d(Co, (p. 4)
Type-1
Type- II
error
evoor
enror
error
0.005
0.002
0.928
0.050
0.003
0.924
0.038
0.005
0.934
0.104
0.010
0.007
0.922
0.056
0.013
0,922
0.074
0.018
0.930
0.110
0,020
0.027
0.912
0.042
0.053
0,924
0.062
0.073
0,930
0.118
0.050
0.166
0.926
0.050
0.330
0.918
0.068
0.458
0.920
0.082
0.100
0.666
0.906
0.074
1.322
0,728
0.244
1.835
0.198
0.766
0,200
2.687
0.136
0.882
5,331
0.004
1.000
7.399
0.010
1.000
0,300
6.134
0.008
1,000
12.160
0.062
0.002
16.876
0.050
0.000
0.400
11.141
0.044
0.002
22.060
0.042
0.000
30,606
0.046
0.000
0,500
17.927
0.044
0.000
35.441
0.040
0.000
49.155
0,054
0.000
0.600
26.853
0.060
0.000
52,984
0.038
73,453
0.000
0.700
38.542
0.060
0.000
75.864
0.036
0.000
105.114
0.040
0.000
Table 2: Type-I and type-Il errors of Example 1.1.
200
600
1000
A
d(Co; (p).g)
Type-1
Type-I1
C(Co.C,))(p.. .)
Type-I
Type-I1
d(Co, (p)
Type-I
Type-11
eтror
eтror
emor
error
error
error
0,005
0.001
0.942
0.054
0.002
0,922
0.088
0,002
0.936
0.068
0,010
0.003
0.944
0.058
0,007
0,910
0.086
0,009
0.926
0.078
0.020
0.013
0.938
0.062
0.026
0.916
0.078
0.037
0.914
0.082
0,050
0.084
0,948
0.056
0.165
0.924
0.084
0.229
0.916
0.088
0.100
0.336
0.902
0.082
0.663
0.788
0.232
0.919
0.236
0.786
0,200
1.357
0.122
0.844
2.674
0.000
1.000
3.707
0.002
0.300
3.098
0.000
0.998
6.100
0.002
0.994
8.455
0.004
0.994
0.400
5.627
0.008
0.982
11.067
0.042
0.000
15.334
0.044
0.000
0.500
9.054
0.050
0.086
17.780
0.050
0.000
24.627
0.030
0.000
0.600
13.562
0.044
0.000
26.581
0.042
0.000
36,800
0.038
0.000
0.700
19.465
0.040
0.000
38.059
0.034
0.000
$2.662
0.036
0.000
Table 3: Type-I and type-Il errors of Example 1.3.
We also compare our method with an alternative method SIMPLE proposed in Fan al. (2019). SIMPLE was designed to conduct a two-sample test whether two nodes belong to the same community. This the case of Example 1.1 in our paper with m = We compare SIMPLE with method under Example 1.1 with m 2 2 by combining SIMPLE with Bonferroni correction. We consider π = 600, = 2 and m = 2, 3, 28, where m = 28 is chosen by setting å 0.7 in the formula [[n/K)
The probabilities p and are chosen in the same way in Section 5. The results of the comparison are shown in Table 4. We applied the Bonferroni Correction to the SIMPLE method when doing the multiple comparisons. From the results, our method outperforms SIMPLE in both the single-pair testing and the multiple testing. For the multiple testing results, Bonferroni Correction would result in SIMPLE is still larger than the desired size of 0.05, indicating a lack of accuracy of the method under our setting of parameters. comparison, the performance of our method is good and stable under all settings.
conservative type-l error, yet the reported size from
To evaluate the performance of our method as the cluster size and the number of clusters increase, we provide in Table 5 additional simulation results of Example 1.1 on the type-I error, type-ll error and runtime under different settings. Specifically, we set P., n ..n, where 5p. is the signal strength parameter taking values at 0. 0.3 and 0.5 respectively, and we set 1.5pm. q 0.5p, and m 0o./Ko0.5/// /2]. Consistent with the results in Table 2 and Table 3, we have high type-I and type-Il errors when d(Co, Cj (p),(p.)) q) is approximately smaller than 10, suggesting that need large enough d(Co, C₁ (p, q) to perform valid hypothesis testing.
33

---

Published as a conference paper at ICLR 2023
m =
A
0.1
0.2
0.3
0.4
0.5
0.6
0.7
Size
0.770
0.008
0.056
0.040
0.060
0.048
0.056
Our Method
Power
0.768
0.018
0.998
1.000
1.000
1.000
1.000
Size
0.270
0.116
0.102
0.086
0.082
0.076
0.064
SIMPLE
Power
0.312
0.756
0.990
1.000
1.000
1.000
1.000
m =
3
A
0.1
0.2
0.3
0.4
0.5
0.6
0.7
Size
0.752
0.014
0.048
0.048
0.044
0.046
0.046
Our Method
Power
0.728
0.018
0.998
1.000
1.000
1.000
1.000
Size
0.344
0.118
0.070
0.074
0.070
0.084
0.070
SIMPLE
Power
0.426
0.816
0.992
1.000
1.000
1.000
1.000
m = 28
0.1
0.2
0.3
0.4
0.5
0.6
0.7
Size 0.792
0.000
0.054
0.040
0.036
0.030
0.038
Our Method
Power
0.784
0,000
0.752
1.000
1.000
1.000
1.000
Size 0.938
0.232
0.126
0.088
0.072
0.06
0.044
SIMPLE
Power
0.950
0.998
1.000
1.000
1.000
1.000
1.000
Table 4: Comparison of our method with SIMPLE for Example 1.1 with m 2, 3, 28.
34

---

Published as a conference paper at ICLR 2023
n m/K
K
Pp
d(Co, (p.
Type-1 error
Type-11
error
Runtime (in scconds)
100
0.150
45.787
0.077
0.000
2.066
100
2
0.300
13.657
0.067
0.000
2.065
100
2
0,500
4.038
0.007
1.000
2.041
100
3 0.150
40.696
0.060
0.000
7.498
100
3 0,300
11.735
0.043
0.000
7.471
100
3 0,500
3.252
0.007
1.000
7.659
100
4 0.150
37.597
0.083
0.000
16.029
100
0.300
10.565
0.040
0.000
15,894
100
4 0,500
2.793
0.037
0.987
15.326
100
5 0.050
35.432
0.060
0.000
27.801
100
5 0.300
9.752
0.100
0.000
27.722
100
5 0,500
2.484
0.043
0.963
26.485
150
2 0.150
61.250
0.050
0.000
8.989
150
2 0.300
17.661
0.047
0.000
8.951
150
0,500
4.894
0.003
1.000
8,977
150
3 0.150
54.829
0.057
0.000
37.333
150
3
0.300
15.241
0.053
0.000
37.347
150
3
0.500
3,951
0.007
1.000
36.861
150
050
50.867
0.077
0.000
82.281
150
4
0.300
13.758
0.027
0.000
82.371
150
4
0,500
3.399
0.003
0.993
79.962
150
0.150
48.077
0.067
0.000
135.419
150
5 0.300
12.722
0.057
0.003
135.634
150
5 0.500
3.026
0.007
1.000
130.579
200
2 0.150
75.573
0.047
0.000
30.893
200
0.300
21.238
0.040
0.000
31,069
200
2 0.500
5.614
0.007
1.000
30,606
200
3 0.150
67.937
0.063
0.000
115.165
200
0.300
18.375
0.053
0.000
115.183
200
3 0.500
4.540
0.010
1.000
I 114.633
200
4
0.150
63.188
0.070
0.000
232.970
200
4 0.300
16.614
0.027
0.000
233.203
200
0,500
3,909
0.007
1.000
227.977
200
5 0.150
59,828
0.077
0.000
372.845
200
5 0.300
15,380
0.030
0.003
371.971
200
0,500
3,483
0.003
1.000
363.691
300
2 0.150
102.076
0.057
0.000
133.766
300
2 0.300
27.609
0.040
0.000
131.782
300
2 0.500
6.821
0.007
1.000
125.900
300
050
92.227
0.053
0.000
406.462
300
3 0.300
23,964
0.060
0.000
412.823
300
3 0.500
5.526
0.007
1.000
409,896
300
0.150
86.047
0.067
0.000
867.116
300
0.300
21.708
0.040
0.000
865.617
300
4
0.500
4.763
0.007
1.000
867.681
300
5 150
81.647
0.047
0.000
1490.006
300
0.300
20.123
0.030
0.000
15 1514.333
300
5 0.500
4.247
0.000
1.000
1450.086
400
2
0.150
126.694
0.060
0.000
377.973
400
0,300
33.311
0.037
0.000
374,540
400
2 0,500
7,838
0.000
1.000
374.889
400
3 0.150
114,825
0.057
0.000
1349.159
400
3 0.300
28.969
0.037
0.000
1353.448
400
3 0.500
6.356
0.007
1.000
1336.669 669
400
4 0.150
107.334
0.037
0.000
2715.127
400
4 0.300
26.274
0.053
0.000
2810.849
400
4
0.500
5.483
0.000
1.000
2796.724
400
5
0.150
101.982
0.063
0.000
4626. 111
400
5
0.300
24.376
0.033
0.000
4583,932
400
5
0.500
4.891
0.003
1.000
4525.389
Table 5: Type-I error, type-ll error and runtime (in seconds) for Example 1.1 under different cluster size n/K, number clusters K and signal strength parameter 8p.,-
35


Reviews:
[{"review_id": "UviiVp1nnZ", "reviewer": "Reviewer_XzCa", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 problem of hypothesis testing in community detection: instead of asking to recover the exact community assignments, the goal is to perform hypothesis testing on them (e.g. asking whether two given nodes belong to the same community or not).\n\nThe authors introduce a framework for measuring distances between community assignments, that depends on the number of mismatched edges between the two assignments. Using this notion, they propose a test based on Gaussian approximation to discriminate between hypothesis classes $\\mathcal C_0$ and $\\mathcal C_1$. They show that this test has the prescribed asymptotic power, i.e. that the p-values are asymptotically the same for the original hypothesis test and its Gaussian approximation. Finally, they show an information-theoretic lower bound involving the SBM parameters and the classes themselves, under which no test can discriminate between the two.\n\n", "summary_of_the_review": "See above", "strength_and_weaknesses": "This is overall a very enjoyable to read paper; it departs from the classical point of view on the SBM, and introduces several new tools to handle hypothesis testing in this setting. It is overall quite clear: all technical definitions are accompanied with figures, and the authors included several extended examples throughout the paper to illustrate the main results. The more technical setting is relegated to the appendix,\n\nMy main reservation about the paper is about its practical usefulness. The fact that $\\rho_n \\gg n^{\\epsilon - 1}$ is glossed upon a bit too fast: it is a scaling where the actual assignment $z^*$ can be recovered with absurdly overwhelming probability, and hence the p-values for any (rejected) test should be extremely small. It also does not seem to be a technical assumption, since a non-negligible level of signal is certainly needed for a Gaussian approximation to hold. Can you explain why your framework is more powerful/useful than simply computing $z^*$ and then testing whichever hypotheses we want ?\n", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "PbdLEbveMO", "reviewer": "Reviewer_f6aS", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "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 presents a framework to test whether a certain [symmetric] community property of the stochastic block model (SBM) is satisfied and calculate p-values the quantify the uncertainty. The paper introduces a shadowing bootstrap method to deal with the combinatorial challenges of the test. The framework relies a combinatorial distance (a.k.a community property distance in Def. 2.4) between communities and uses it together with a probabilistic distance (difference of community parameters/probabilities) to ensure the test remains “honest”. The model works applying a likelihood ratio test for the SBM, where the limiting distribution of the likelihood ratio is driven by the two edge sets of misaligned edges (assigned to the same community by one assignment in a community property and to different communities by another assignment in the other property). The paper also presents an analysis of the limiting distribution of the leading term of the LRT statistic and a Shadowing Bootstrap for the test. The theoretical component of the paper concludes with both: a validity analysis of the proposed test for general symmetric community properties, and an alternative (information theoretical) lower bound result relaxing the scaling conditions of the test. The experiments show numerical evaluations (Type I and II errors) of the shadowing bootstrap to test the community hypothesis with $\\alpha=0.5$ for various sizes of networks $n$ and varying difference between $p$ and $q$ (i.e., $\\Delta$).", "summary_of_the_review": "The paper has its pros, such as the relevance, the clear stated goals and the analysis of the effect of $\\Delta$ over Type I and II errors. However, there are several reservations with respect to the applicability of the framework because a hypothesis testing technique is as important as its application. The advantage seems to be more due to the some of the insights but more evaluations are highly recommended. I detailed my comments on what could be improved in the Strength and Weaknesses section.\n\n%%%Post Rebuttal Comment%%%\n\nThank you for the answer to my questions. This clarifies most of my doubts and I raise my score.", "strength_and_weaknesses": "With respect to its strengths, the paper is well organized, the problem is relevant to the ML community, particularly to hypothesis testing SBM modeling and could be applicable to clustering and other domains. The paper states a clear goals although it is at times obscure in its notation. Another strength is the thorough analysis of permutation impacting computation of likelihood in the SBM which highlights the practical difficulties of LRT for probabilistic models due to isomorphisms. The Shadowing Bootstrap to estimate the p-value of the LRT is also interesting but it seems that it may present scaling challenges.\nThere are some areas where the paper could be improved. For instance, the evaluations are interesting on the impact of $\\Delta$ (distinguishing an SBM from an Erdös-Rényi model) but not fully developed. The computational costs and runtimes (e.g. as K and n grows) could be interesting to identifyfy applicability of the technique and possible future work to ensure scalability. Another weakness is that no evaluation is provided with respect to the choice of other parameters. In general the contribution is more theoretical. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Fmt2KJo7ff7", "reviewer": "Reviewer_on1z", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 is about testing properties of stochastic block models. In particular, the framework presented in the paper is applicable to symmetric properties. A property is defined to be a set of assignments of the $n$ nodes into $K$ communities and it can be described by a subset of $[K]^n$. A symmetric property is a property that contains all of the assignments that partition a specific subset $\\mathcal{N}\\subseteq [n]$ of the nodes in a specific way (the labels can be permuted though). The alternative hypothesis for the tests considered in the paper, need to be a union of symmetric properties for the same subset $\\mathcal{N}$.\n\nThe authors define a notion of distance that depends both on combinatorial properties of the partitions and the probabilities of the models in different instances. In particular, the proposed distance is a product of the 2 distances, which implies a trade-off: the null hypothesis can be rejected if either the edge probabilities are close and the instances are very different combinatorially, or vice versa. Using a likelihood ratio statistic, it is shown that the test accepts the null hypothesis with constant probability when the minimum distance does not exceed a certain threshold and rejects it with probability that approaches 1 when the distance does go above a different threshold. The authors complement these results with information theoretic lower bounds, which show that the aforementioned trade-off is indeed necessary. ", "summary_of_the_review": "The main contribution of this paper is showing that the right metric (justified by upper and lower bounds) for a testing symmetric properties of stochastic block models is a product of a combinatorial and a probabilistic distance metric. I consider this to be a solid contribution and recommend acceptance.  ", "strength_and_weaknesses": "Strengths:\n- The paper addresses a very important problem and proposes the use of a novel distance metric to quantify the quality of the propose statistical test. \n- The results are complemented with lower bounds showing that the new distance metric is indeed inherent to the problem.\n\nWeaknesses:\n- It seems that the examples on which the test is applied in the paper, do not capture the full generality of the framework. So, it would be nice to see a characterization (or at least a discussion) of what type of problems could be solved using this test. \n- To that end, it might also be useful to discuss about how restrictive Assumption 3.1 is in terms of the type of problems that satisfy it.\n\nMinor comments:\n\n- Last line of section 2.1: \"$[K]^m$\" should be \"$[K]^{m+m^\\prime}$\"\n\n- Section 2.4, lines 9-10: \"supreme\"->\"supremum\"\n\n- Page 5, 2nd line from the bottom: \"there existing\"->\"there exists\" \n ", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "2rBosSBnHwD", "reviewer": "Reviewer_uY7c", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 a very general hypothesis testing problem about the community assignement on stochastic block model. Given two disjoint community properties, the difficulty of distinguishing between the properties depends on distance between properties and probability distance between communities in the stochastic block model. The authors propose a method to define p-value, which can be applied to define the rejection rule of the test. The author also derive the information-theoretic lower bound. ", "summary_of_the_review": "I believe this is a good paper if the author can clarify my concerns. ", "strength_and_weaknesses": "Strength\n\n1. I believe this paper studies a very important and very general problem about stochastic block model. \n2. The authors provide examples for definitions, which help the reader understand the paper better. \n3. Overall, this paper is well-written. The statements in definitions, assumptions and theorems are clear. \n4. The theoretical results are novel and interesting. \n\nWeakness\n\nThere is a critical limitation in the theoretical result, which has been stated after Theorem 3.2. This main theorem assumes $1/\\rho_n=o(n^c)$ for $c\\in(0,1)$. In the existing result, if $n\\rho_n/\\log n\\to\\infty$, then then the assignments can be exactly recover with high probability. The assumption in Theorem 3.2 is even stronger than $n\\rho_n/\\log n\\to\\infty$. The case when exact recovery is not possible is still very interesting. \n\nI also have some comments and questions about the clarity in the next part. ", "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": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%