Sharp Impossibility Results for Hyper-graph Testing
Authors: Jiashun Jin
Tracy Ke
Jiajun Liang
Venue: NeurIPS 2021 Poster (2021)
Keywords: community detection
social network
Degree-corrected Mix-membership model
non-uniform hypergraph
global testing
minimax lower bound
region of impossibility
tensor scaling
degree matching
SBM
tensor

Abstract: In a broad Degree-Corrected Mixed-Membership (DCMM) setting, we test whether a non-uniform hypergraph has only one community or has multiple communities. Since both the null and alternative hypotheses have many unknown parameters, 
the challenge is, given an alternative, how to identify the null that is hardest to separate from the alternative. We approach this by proposing a degree matching strategy where the main idea is leveraging the theory for tensor scaling to create a least favorable pair of hypotheses. We present a  result on standard  minimax lower bound theory and a result on Region of Impossibility (which is more informative than the minimax lower bound). We show that our lower bounds are tight by introducing a new test that attains the lower bound up to a logarithmic factor. We also discuss the case where the hypergraphs may have mixed-memberships.

Sharp Impossibility Results for Hypergraph Testing
Jiashun Jin Carnegie Mellon University j jiashundstat. cmu.edu
Zheng Tracy Ke Harvard University zke@fas aaefaas.harvardcco edu
Jiajun Liang Purdue University liangj jarngjj@pureen @puuruuuue.... edu
Abstract
In a broad Degree- Crrree-Crreeeedd Mixed-Membersiee (DCMM) setting, we test whether non-uniform hypergraph has only one community or has multiple communities. Since both the null and alternative hypotheses have many unknown parameters, the challenge is, given an alternative, how to identify the null that is hardest separate from the alternative. We approach this by proposing degree matching stralegy where the main idea is leveraging the theory for tensor scaling to create a least favorable pair of hypotheses. We present result standard minimax lower bound theory and a result on Region of Impossibility (which is more informative than the minimax lower bound). We show that our lower bounds are tight by introducing new test that attains the lower bound up to a logarithmic factor. We also discuss the case where the hypergraphs may have mixeedmmmmbershps.
Introduction
The hypergraph is a useful representation of social relationships beyond pairwise interactions [5, 11]. For example, the co-authorship hypergraph is often used to analyze the co-authorship topology of authors, and it provides more information than co-authorship graph (where an m-author paper is treated as an m-clique). The community detection on hypergraph [10] is problem of great interest (communities in hypergraph are clusters of nodes that have more hyperedges within than across). has many applications in social network analysis [15] and machine learning [1. 17, 18, 23]. We are interested the problem of global testing, where we test whether the hypergraph has one community or multiple communities. It has applications in measuring co-authorship and citation diversity [12] and discovering non-obvious social groups and patterns [4]. It is also useful for understanding other problems such community detection and change-poie detection in dynamic hypergraphs.
For instructional purpose only, we start with the 3-uniform hypergraphs (i.e., each hyperedge consists of 3 nodes), but our results cover both higher-order hypergraphs and non-uniform hypergraphs. Let A be the adjacency tensor of a uniform and symmetric order-3 hypergraph with nodes, where
Aniiis equals if i,, ig, is share hyperedge and equals O otherwise,
(1.1)
for 1 S 11, i2, is (distinct) S n. Since the tensor is symmetric, Aiiaii = Ajjiii for two sets of indices {ir, ig, is} and (j1.j2.ja] if is permutation of the other. We do consider self hyperedges, hence, Aizizia = 0 whenever i,, i2, ig are non-distinct.
Real world hypergraphs have several noteworthy features. First, there may be severe degree het- erogeneity (i.e.. the degree one node is many times higher than that of another). Second, the overall sparsity levels may vary significantly from one hypergraph to another. Last, node may have mixed-memie memeershmmbrssssss across multiple communitics (i.c., nonzero weights on more than one community). To accommodate these features, we adopt the Degree- Cocreet-d Mixed-Membershe (tensor-DCMM) model. The notations below are frequently used in tensor analysis.
Definition 1.1. (matricizationn, slicing, and slice aggregation). Let be a 3-symmetric tensor of n- dimension. First, we call the n x n² matrix A the matricization of A, defined by Aij+n(k-1) = Aisk.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

1 i.ijj n. Second, for 1 S k S n. we use A.s to denote the n X n matrix whose row-i-and- column-j Aigk. 1 I i,j n, and call the k-th slice of A. Last, for any a x vector z, we use (Ax) to denote the matrix =k=1 Ank, which is an aggregation of the slices.
Now, suppose the tensor has K perceivable communities. Let P be a symmetric (3-uniform) tensor of K K-dimension that models the community structure, let 0 (01, 02. ................................ .,, be positive parameters that model the degree hetcrogeneity of nodes, and T1, T2..... Tn be --dimensional membership vectors where TT (k) the weight node puts community k. S k S K. We assume for all 1 I i1, f2, is I n that are three distinct indicies, Airigi are independent Bernoulli random variables with i(A 1) 0z 0:p Oig Σk -ki k1.k3=1 Pko Ny. (ki )=a (k:2) mig (ka), where by Definition 1.1, the right hand side equals to 0g Oig02g OisT (PTiig MTz Introduce non-stochastic 3-uniform tensor Q of n-dimension where Qipizis
0z 0ig 0ig T,, (PTig) Mi, for 1 S én, i2, ig S Let diag( Q) be the tensor with the same size of Q where (diag( ())s = Quizis if i1, 12, ig are non-distinct, and (diag( 2) inpits otherwise. follows that
B(A) = Q (Q),
where Qigizis 0,,0, 0ig00 0i (PTis)me.
(1.2)
For identifiability, let P E R.K.K² be the matricization P (see Definition 1.1). We assume
rank P) K, and Pai = 1 for all S.sK.
(1.3)
Definition 1.2. We call (1.1)-1.3) the Censor-DCMM, model for 3-uniform hypergraphs. We call Q and P the Bernoulli probability tensor and community structure tensor for DCMM, respectively.
Later in Section 3, we introduce the non-uniform tensor-DCMM as more sophisticated model. In Censor-DCMN, if we require all ग. to be degenerate (i.c., onc entry is 1, all other entries are 0), then tensor- DessOr-DMMM reduces to the Degree- Corrected Block Model (tensor-DCBi require 0 = reduces to the Stochastic Block Model (tensor-SBM) [9]. For simplicity, we may drop "tensor" in these terms if there is no confusion. The global testing problem above is then to test
[15]. If we further in (but the second condition in (1.3) can be removed), then tensor-DCBr further
Ho Mo:K- 1=
VS.
H1 K>1.
(1.4)
Our primary goals are (a) to find a sharp information lower bound for 3-uniform DCMM, and especially, to fully characterize the lower bound by simple quantity to be discovered, and (b) extend the results to more sophisticated non- oon-uniform hypergraphse (see Section 3). A good understanding of the problem greatly helps us understand the fundamental limits of many other problems (e.g.. community detection, determining the number of communities K, dynamic hypergraphs). For example, for community detection (e.g., [10]), we either assume K as known or estimate it first. Note that in parameter regions where we cannot tell whether K = 1 or K > 1, we cannot estimate K cannot have consistent community detection either. Therefore, lower bound for global testing is always a valid lower bound for estimating K and for community detection.
consistently,
To facilitate the lower bound study, we frequently adopt a Random Mired-MMmmbrshhp (RMM) model. Introduce subset Vo- {x RK I& 0, >x= 24 1}. and let F be a K-variate distribution with support contained in Vo. We assume
kid nj F;
(let = Exr[r)]
(1.5)
Moreover, let Vi = fer, 62, .......,. ex C Vo, where e the k-th basis vector of R Similarly, RMM-DCMM reduces to RMM-DCBM if we require supp( F) = Vo. and reduces to RMM-SBM
we further require 01 = 02 = =... = 6n (but the second condition in (1.3) can be removed). Let 0 = (01, 02....,,,,, O,))' We allow (0, P, h, F)) to vary with n to cover a variety of settings where allow for severe degree heterogeneity, mixeed-membershpp.. flcxible sparsity levels, and weak signals.
Example 1 (2-parameter SBM [2, 22, 19]). This model is a special case of DCMM, where 0 = 0, = a. (no degree heterogeneity). all Ty are degenerate (no mixed membership), and Piyk = i = j = k and Pisk Pr. otherwise, for two parameters (a,, Pn). Also, Lin et al. [20] studied a 3 3-parameter SBM, which is the same as above except that they assume a different form of P. where Piya equals to 1, Pn. or Tn if i, j. k take 1, 2, or 3 distinct values, respectively, for three parameters (Oiz Pa; T.). Compared to DCMM, these models are much narrower: they do not accommodate severe degree heterogeneity or mexxxe-mmmmershisss. and P is parametrized by 2 or 3 different values.

---

How to derive sharp lower bound for global testing (and especially, to identify a simple quantity that fully characterizes the lower bound) in our setting a rather challenging problem. Our model is a non-uniform hypergraph model (see Section 3), which consists of hypergraphs of order 2, ......., ..,M, ..... and each layer consists of many unknown parameters (0, P, h, F). Existing works on lower bounds have been focused on uniform hypergraphs, and non-uniform hypergraphs are much less studied. Even for uniform hypergraphs, existing works have been focused on the the special SBM as in Example 1, not the more general DCMM model. For example, Yuan et al. [22] derived the lower bounds for global testing with the 2-parameter SBM, focusing on the extremely sparse case. Ahn et al. [2] provided lower bound results for exactly recovering the communities (see Liang et al. [19] and Kim et al. [16] for related settings) with a similar model. Lin et al. [20] and Chien et al. [7] used the 3- parameter SBM in Example 1 for study of the lower bounds for community detection. While these papers are very interesting, their lower bounds are characterized by only 2 or 3 parameters (i.e., On Pr; Tu) assumed in their models. For the much broader tensor- DMMM model considered here, we have many parameters 0, P, h, F (0 is an n-vector and P is a tensor), and how to extend existing results to the tensor-DCMM setting here is a challenging problem.
Our contributions. The main challenge in lower bound study is that, since each DCMM model (no matter what K is) has a large number of unknown parameters, given an alternative hypothesis (K > 1), it is hard to identify the null hypothesis (K = 1) that is most difficult to distinguish from the alternative hypothesis. As our main contribution, strategy, where for any given DCMM model with K > 1. we pair it with a DCMM model with K = 1 in a way so that for each node, the expected degree under the null matches with that under the alternative. This way, it is hard to separate the two hypotheses by a naive begree-based statistic. We show (a) the degree matching is always possible by using tensor scaling technique [3, 8]. and (b) the pair of hypotheses we construct this way lead to sharp results on lower bounds. See Section 2.
approach this by proposing degree matching
We have the following results. Consider the 3-uniform hypergraph first. We first present the standard minimax theory. Define a class of RMM-DCMM models with K > and μ3 [2]10|||00]] - 0 (12 is the second singular value of P). In this class, we can find an RMM-DCMM model (the alternative), and pair it with a DCMM model with K = (the null), such that the x² divveeegee between the pair converges to 0 as - co. Therefore, in this class, there exists alternative model that is asymptotically inseparable from the null.
The standard minimax theory only claims that there exists an alternative model within a specified class that is inseparable from the null. It is desirable to show a much stronger result where for any alternative in the class, we can pair it with null so that the x <d-divergence of the pair goes to 0 as n - oc. In detail, we show that in the parameter space (0, P, h, F) of RMM-DCBM, there is a + O; for any alternative in Region of Impossibility,
Region of Impossibility defined by | we can pair it with null such that the x divvergene between the pair goes 0 as n + co. Compared with existing results minimax lower bounds, these results are more informative and theoretically more satisfactory. The proof is also diffcrent from the proof of minimax lower bounds: we have used the tensor scaling theory [3, 8] and the "degree matching strategy" aforementioned. We also extend such results to the broader RMM- DCMM case (Section 2.3) and discuss some major differences on the Region of Impossibility between DCBM and the more restrictive SBM (Section 2.4).
Next, we generalize the results to higher-order and non-uniform hypergraphs. Fix M 2 and consider a non-uniform hypergraph (e.g., see [10]) that consists of m-uniform hypergraphs for all m = ,,..., M, each following DCMM model with individual (0(m), p(()) but the common Ti. .n. Let lm 1,0 for the m- m--unformm hypergraph case, the Region of Impossibility for the hypothesis testing (1.4) is fully characterized by the condition of fm - O, and (b) for the non-umd non-uniform hypergraph case, the Region of Impossibility for the hypothesis testing (1.4) is fully characterized by the condition of max as ( ++ O.
[1( (? (to be defined in Section 3). We show that (a)
Last, we show that our lower bounds are tight. Consider the non-uniform hypergraph above. We propose a new test statistic and show that the sum of Type I error and Type II error + if max2<m M ( } > 1=g for a constant ò > 0 (taking 8 = 0.1 will work). Therefore, except for a logarithmic factor here, our lower bounds are tight.
In summary, existing results on lower bounds are largely focused on more restrictive settings (e.g.. uniform hypergraphs without degree heterogeneity or mixed membership). We provide sharp lower bounds for a much broader setting. Our study is highly non-trivial because we need (i) a novel degree
3

---

matching strategy to construct least favorable hypothesis pairs, (ii) to identify simple quantity that able to fully characterize the lower bounds, (iii) delicate analysis the x²-divergence between the null and alternative, (iv) carefully designed test that leads to tight upper bounds.
2 Sharp Lower Bounds for 3-Uniform Hypergraphs
For notational simplicity, we focus 3-uniform hypergraphs in this section. The study of higher- order and non-uniform hypergraphs is deferred to Section 3. Consider a (3-uniform) DCMM model. Recall that h Es [Ts] and that P E RR.K* is the matricization of the tensor P. In this paper, we use C > 0 as a generic constant which may vary from occurrence to occurrence. We assume
||||| S C, mmax max 8n) S C, max (ha} S C min { 1101 + co. (2.6) ISkSK
ISASK
The first condition is mild, because the model identifiability already requires that all diagonal entries P are 1. The second one is also mild (note that while the largest possible value of max is O(1), max is allowed to tend to 0 relatively fast). The third one assumes that the community memberships are balanced, which is also mild. For the last condition, we will see soon that if [|0] - 0, then the signal is so weak that successful global testing is impossible, so this condition also mild.
2.1 Standard minimax lower bounds (RMM-DCMM)
We start with the least favorable configuration. The goal is to find pair of models (a null model with K = 1, and an alternative model with K > 1) which are hard to distinguish from each other. We the following degree-matching technique: we choose the pair in way that for each node, the expected degree under the null matches with that under the alternative, approximately. The idea is, the degrees are not matching, then we may separate the two hypotheses by a simple degree-based statistic, so we should not expect the x" x²-divergence between the pair to be small.
In detail, consider a pair of models, DCMM model with K = 1 and an RMM-DCMM model with K3 > 1, where for all 1 I i1, 12, 13 I n, the Bernoulli probability tensors Q and Q" satisfy
Qi = 0,, 0is:
2i 07, 01 07 The (Priy)mTs)
(2.7)
here we recall that (Pm,,) is K x K matrix (see Definition 1.1). We call the two models the null and the alternative, respectively. In (2.7), the community structure tensor P is as in (1.2), and n, and h E [ms) are as in (1.5). Recall that 0 (0,,0,..... ".) Similarly, let 0 (0i -.,,....4 0,) YtYY Fix < i S n. By definitions and elementary statistics, the leading term of the expected degree of node 11, conditional
its own membership Ti,- under the null and alternative are
0,, 101l and 0 -100 Ti,0, respectively, where a = (Ph)h E RRK
(2.8)
For least favorable construction, choose (P, h) in way so that
a (Ph)h = k for a sealar co >
(2.9)
For broadness, we allow co to depend on n. There are many (P, h) that satisfy (2.9). For example, in the 2-parameter SBM model as in Example I with h = (1/ K, ..... 1/KY and a (I/K²)[1=
(K² - Pn] for < k < K, (2.9) is satisfied with ce = (1/K2) ) (K2 1)p,). Moreover, we choose o in the alternative model such that
0: (1/co)0,,
1sisn.
(2.10)
Now, by (2.8)-2.100) for all 1 S i S n, 0 10-12 ,[ 0 100 - Therefore, for each node, the expected degree under the alternative matches that under the null (at least in the leading term), making hard to separate the null and alternative by any naive degree-based statistics. Only when such a degree-matching holds, we can hope two models are asymptotically indistinguishable. This is the key for our least favorable configuration. Recall that P E K. is the matricization of the community tensor P and μı is the k-th largest singular value of P.
Theorem 2.1 (Least favorable configuration). Fix K > and consider a pair of models, a null and an alternative with K communities, given in (2.7), where (2.9)-(2.10) hold. Assume (2.6) holds and

---

|011:1011331 o(1). As - cc. the divergeene between the pair tends to O. Therefore, the two models are asymptotically indistinguishable: for any test, the sum of Type I and Type Il errors is no smaller than + (())
Remark (How degree matching affects the x2 <ivvieergecce) Intuitively speaking, the x² -iveerggee has many terms, each being the sum (or function) of terms in a Taylor expansion. We can roughly call these terms the first-order term, second-ordes term, and so on. When the expected node degrees are not matched between the null and the alternative, the first-order term dominates, and correspondingly, a degree- -tetes may have power; see Section 2.4. When the expected degrees are matched, the first-order term vanishes as we have hoped, and the degree- based x² -e-test loses power. As result, the second-orded term in the Xi-divergence now dominates and gives the sharp lower bound.
The above least favorable configuration gives rises to the standard minimax theorem. Fix K 2 1 and consider a DCMM model (where Tr are non-random). Introduce a vector 9 E R by gh (1/110111) D"= 0gT,((k) (k). < k < K. For a constant O < co < 1, and two positive sequences (an)n=) and 13,)==1 we define a class of DCMM models by
Mn (K, co, an Br) = (6, II P):
|P|| S co. max S Co. max SASK Ik S Go min SKSK 9h: 101110011 2 1/Bm. | 22 S ap
Here, we assume max, K {9: S C mininggs K (gk ). so the tensor is balanced. This is similar to the third condition in (2.6), except that n, is are random there. For the null case, K P = my 1, and the above defines a class of 0, which we write for short by Mn.(1, co. On, 3x) = M, The following theorem is proved in the supplement.
Theorem 2.2 (Minimax lower bound). Fix K 2 2, a constant co > O, and any sequences {an } and {Bn ) where on = d11) and 3, = o(1). As co, inf & { {suPoεM; (9.) IP(s) = 1)
BUP.O...P)MMM.KKco P(v) = 0)} = o(1), where the infimum is over all possible tests tb.
2.2 Region of Impossibility for RMM-DCBM
The standard minimax theorem in Section 2.1 only says that in the class of all alternative models with |0111100]] - O, there exists one where we can pair it with a null so the pair are asymptotically inseparable. A much more satisfactory result is show that, for any alternative in the same class, we can pair it with a null such that the pair are asymptotically inseparable. In this section, we prove this for the RMM-DCBM case mmixed-membershipp are not allowed). The discussion for the RMM-DCMM mexxedd-mmbershipss allowed) is in Section 2.3 and the supplement.
Consider again pair of models, DCBM null model and an RMM-DCBM model with K > 1, where the Bernoulli probability tensors are Q and Q", respectively. We assume for all 1 < i1, 82. ig $ n,
Qiitnia 0,,00.
2i 07, 0, , (PTTt)TTi
(2.11)
Here, the community structure tensor P is as in (1.2), n; and h = Er[z,] are as in (1.5), and SFP = [e1,..., (ex J. Similarly, the goal is degree-matching" for any (0, P. hi F), we construct 8" in a way so that for each node, the expected degrees under the null and the alternative match with each other approximately. Recall that in Section 2.2, in order to have desired degree matching, it is crucial to pick an alternative model where the (P, h) satisfics a = (Ph)/ 101K for some scalar co 0: once this holds, we have the desired degree matching by taking 0 (1 /c/c Unfortunately, for general (P, h). we don't have a = (Ph)h x K, so we should not expect to have the desired degree matching by taking 8* x 0. In short, for our purpose here, the approach in Section 2.1 no longer works, and we must find new approach to constructing the model pair.
Our proposal is as follows. For any diagonal matrix D = diag(d),... dx) with du > 1 0 K, K. define a K -ddimensional vector a by (PD a 3-tensor in dimension K)
P = (PPh)h,
with Philigs = dx, dee dks P Pkykaks 1 S k2 Kog S K.
We aim to select matrix D such that d 1k. The next lemma states that such 1 always exists and is unique. It leverages classic results on tensor scaling (e.g., [3, 8)) and is proved in the supplement.
'The X² diverrgen between two models, (o( and (AA), is defined as [[[f(AA) - ((AA))//o((A)) In setting, the alternative model fi (AA) alone involves integral over the distribution of m; in (1.5)
5

---

Lemma 2.1. Fix K > 1 and let P, h, D. and a² be as above. Suppose min {h1, he..... There exists a unique diagonal matrix D diag(d,, (d.
"e......k''' hxk 2 C.
d2.................. .......... ....)...)))).)... such that a 1k.
Now, given (0,P, h, P,h, F) and the two models in (2.11), let D = diaggdl (d1, d2,.... dx) be as in Lemma 2.1. Moreover, in (2.11), we choose 02 as follows:
0- = =dx0,, if node i belongs to community k. Combining it with (2.11), we have Qi By similar calculations as in (2.8), for 1 S i S n. in the null and the alternative, the leading terms of the expected degrees of node i are
(2.12)
0 0% 0f T/ (Prcg Mi, 0g 0,, =, (PD Tig Tig. i2
0: 11 and (T(( respectively, where a² (PDh)h.
By Lemma 2.1, P = 1x. Hence, for each node, the expected degrees match under the null and alternative, it is hard to separate two models by naive hearee-based statistic. Recall that P is the matricization of P and jug. is the k-th singular value of P. Theorem 2.3 is proved in the supplement. Theorem 2.3 (Impossibility for RMM-DCBM), Fix K 1. For any given (0, h, F), consider a pair of models, a null and an alternative with K communities, as in (2.11), where 0f are given by (2.12) with the matrix D as in Lemma 2.1. Suppose (2.6) holds and ||0|||10|| 2u o(1). As n + oc, the x² diveeeggee between the pair tends to O. Therefore, the two models are asymptotically indistinguishable: for any test, the sum of Type I and Type II errors is no smaller than + o(1).
Region of Possibility, Region of Impossibility, and tightness. In the parameter space (0, P, h,, F) for DCBM, we call the region prescribed by [|0]] ||0]] - O the Region of Impossibility: by s
Theorem 2.3, for any model in this region, we can pair with a null that the pair are asymptotically inseparable. We call the region prescribed by |||]||00|//2] log -og--((n (m) + oo the Region of Possibility: for any alternative model in this region, there is a method that can separate it from any null with asymptotically full power (this follows from Theorem 3.2 special case). Comparing Region of Impossibility and Region of Possibility, except for a log(n) term, our lower bounds are tight.
2.3 Region of Impossibility for RMM-DCMM
The discussion for RMM-DCMM is similar, so for reasons of space, we leave it to Section A of the supplement. In that section, we present a similar theorem for RMM-DCMM, where the hypergraphs may have mixed- mexxeddmembrrshis... The proofs are largely similar, where again the key is to construct a pair of null and alternative using the degree matching strategy. Since the model more complicated than RMM-DCBM, we need an extra (but mild) condition. See details therein.
2.4 Major differences on Region of Impossibility for the more restrictive RMM-SBM
For an alternative RMM-DCBM, we can always pair it with null using tensor scaling technique: for each node, the expected degrees under the null and the alternative match with each other. For the more restrictive RMM-SBM (where 0 _.. 6,). such degree matching is not always possible: A null SBM has only parameter, so we have insufficient flexibility in choosing the null for degree matching. A consequence is that a naive degree-basse test may have non-trivial power for SBM.
Consider a pair of models, where the Bernoulli probability tensors Q and Q* under two hypotheses are such that, for 1 S ii, 12,12,, S n,
Qipisis = On. Dii = =T', (Piig))ii
(2.13)
Same as before, M; are iid generated from a distribution F on fei, .2....,,eyyy with h Ey(m, Let ân (nin - 1)(n 2) ',, (A1,)) 17 (1/2)(A1.,),,, and be the mean of m), ....... IKK- Consider the centered -statissic
v' (2n) 112
Σ ISiS
[nn. - 7)2 ((22(((()((111 an)) 1].
Lemma 2.2. Consider the global testing problem (1.4) under the SBM model (2.13) Ho and Hi
respectively. Let an = E[],,,, h (1/n) Ex_ n. and Σ, = 1 Σi= (TT - h)( (T. -h.. Let A x (E) be the (K- 1)-th largest eigenvalue (in magnitude) of Assume an Co. maxisij&sk PPyk S
Co. n² n²an, - oc, and n. ū. - Do. Also, assume min h1 he...... 2 C and xx- 2 C.
Write 8n = ||ā (IK H (Ph))hl,, where Hx = [[/K)IæTl 1'x and TK is the identity matrix the
same size. As n 00, 2/ + (0, 1) if Ho holds, and Un co if H1 holds and n 3/222212 62

---

By Lemma 2.2, the power of the -ttt hinges on 6n,
on = ||ā (4K (Ph)kl]
Note that 6, = O if and only if (Ph)h x 1x- We call the cases of (Ph)h x 1 and (Ph)h K 1x the symmettrc case and the asymmetric case, respectively. For symmetric SBM, 6, 0, and do not expect the x² to have power. However, for asymmetric SBM, the x²-test may have non-trivial power, implying a potential shift of the lower bound.
Example 2. Consider an SBM setting where we either have K = 1 (null) or K (alternative). Also, when K = 2, we assume h (a, 1 1 a) for some 0 < a < 1, Piyk is equal to pa if = k and Pl otherwise. Suppose n² + and p1/ 1. This can be viewed as a special DCBM with f; = Po 1/3 and off-diagonals of P being PI/Po. In this case, we have ||0|| x n² po- Tn = |0] | / x pnpop p - po)2, and r," = (11po)-1/222)) - T) In the symmetric case where = 1/2, the -test is powerless, and the Region of Impossibility is given by Tn - 0 (same as in the DCBM case). In the asymmetric case where aa - 1/2| 2 co. by direct calculations, we have that even when Tn - O, we may have n/ 0 + (so 2test has asymptotically full power). Here, the interesting range of Po is (n-2, 1). so we may have (npo)-1// - cc. Therefore, for the asymmetric case, the Region of Impossibility is different from that of DCBM.
In most lower bound results for SBM [2, 7, 20, 22], they focused on the symmetric case (Ph)h x 1x- Our lower bound restricted to symmetric SBM agrees with those in the literature. The asymmetric case (Ph)h & 1 is less studied, except for [14, 21] which focused on the network setting (m = 2). We discover: (i) the Region of Impossibility for symmetric SBM is similar to that of DCBM (see Example 2), and (ii) the Region of Impossibility for asymmetric SBM is quite different from that of DCBM. This because DCBM is much broader than SBM, where the problem of global testing is much harder, and naive degree-based based test statistic may lose power.
3 Sharp lower bound for non-uniform hypergraphs
Section 2 discusses lower bounds for uniform 3-hypergraph. We now first extend the results to more general oon-uniform hypergraphs, and then present a tight upper bound. Note that our results include those for m-uniform hypergraphs as special cases (see the paragraph behind Theorem 3.1). The notation below useful:
Definition 3.1. Given an order-m tensor M in dimension K and vectors bi, b2, ..., bm E RK let
[M:b,. b,, ... ,bm] denote the summation Eiski ka....k. <K [ [Maska...... k.. by (kg (k2) ... bm (km)).
Fix M 2 2. Consider a general non non-uniform hypergraph that consists of m-uniform hypergraphs for all 2 & m & M. Fixing? 2 S m < M, let ((m) be the adjacency tensor of the order-m hypergraph (i.e., (mm) f2 1 if {dz, .2,..., im } is hyper-edge and otherwise). As before, we model A with the Sensor-DCMI model. Let p(()) be a symmetric order-m tensor in di- mension K, and let g(m)_ = (m(m) m ..... olmyy be positive vector of degree parameters. Let T1, .T. Ny the K-dimensionna membership vectors (which do not depend on m)) We assume (A Ai, hsn are independent Bernouli variables, where the Bernouli probabilities specified by the tensor Q(m)) given by
(m) 2iriz...m
(m)
(m))
x [p(m), Ten
Te...
5 i im S
(3.14)
Similar to (1.2), we have E[A(m)] = @(m)) diag( ((m)) This extends the tensor-DCMM model to m-uniform hypergraphs for general m. Finally, we denote the non-uniform hypergraph by
A[M] (A(2) A()) ((M)) (MM).
Definition 3.2. We say that A[M = (A(2)...,, A(M)) follows a (general non-uniform) tensor- DCMM model if (A(mm) S are independent of each other and each (m)) follows an m-uniform lensor-DCMM model as in (3.14), where Tı, T2 ... nn are shared by all m M.
similar model is introduced in [10], but is more restrictive for it assumes m()) = o.m) for each 2 < m M. Note also the focus of [10] is on community detection, while the focus here is
of?)
7

---

on global testing, As argued before. since in parameter regions where we cannot tell whether K = 1 or K > is impossible estimate K and community labels consistently. Therefore, our lower bound is also a valid lower bound for estimating K and for community detection.
We present the Region of Impossibility for testing Hn: K versus H1: K > 1. Similarly as in Section 2.2, we focus on the special case of Vensor-DCBA. models (i.e., each क,ę is degenerate); the study of tensor-DCMM is similar. Fix K > 1. Consider DCBM null model with probability tensors [ {0(2) ..... Q("}} and an RMM-DCBM model with probability tensors Q" [M] (Q)(2) ..... (*(M)), ), where for every < m M and 1 S in, i2, ................................ Im n,
Linkka....m = 0 )! pLm)
(m)
(3.15)
b2
(m(m)
(m)) (m(mm) x [p(m);
T F.
atd
(3.16)
The support of F is in VO = f e2,, ext,.,,,., }-} Let h = Ep(Td and suppose min .......................... .xkb 2 C. In the supplemental material, we provide lemma analogous to Lemma 2.1: For each 2 S m S M, there exists a unique diagonal matrix (mm) = diag(d) ((m) mm)
d(m)) such that
Σ
d(Th)
p((m) Pi (d(m)) h.z) ... (dd him =1 for every 1 shisk. K.
SK
Its proof leverages the Sinkhorn theorems for higher-order tensors [3, 8). We choose (mmm) in (3.16)
by
(,(m) = - )! if node belongs to community k.
(3.17)
This is analogous the degree matching strategy in (2.12), and it is conducted for each m separately.
Let p(m) E R K "m=
xxK" be the matricization of p(m) and let p12
(m) be the second singular value of
p(m), For short, let
fm = |10 (m)) || m (1 (m))
Theorem 3.1 is proved the supplement.
Theorem 3.1 (Impossibility for non-uniform RMM-DCBM), Fix > and M 2 2. For any given (h, F) and {(0mm), pimm) 125mms,, consider a pair of models, a null as in (3.15) and an alternative with K communities as in (3.16), where (0)(m)) DSSga22MMM are as in (3.17). Suppose [|p(m)] || I C. maxisien 0(m) < C. and mini<ksK h& 2 C. max [bm] = o1), then as + 0o, the x² diverreee between the pair tends to O.
Remark (Comparison with [22]). Yuan et al. [22] gave nice impossibility result for the 2- 2-parameter
symmetric SBM. Their model special case of our model where g(m) (mm) and p(m) has
equal dia-dia entries pm (see Example for m 3). In this case, 1 [m)] |1 - p(m)) |. and
fm x -a (1 - (2 Hence, fm - 0 is equivalent n nn (m)) p (m)) O, which matches with results in [22].
la,
Below in Section 3. we show that the lower bounds are tight. Theorem 3.1 includes m-uniform hypergraphs as a special case (e.g., apply the theorem an mg-uniform hypergraph, we set ((m) zero vector for all m & mg). For an m-uniform hypergraph, the Region of Impossibility is given by fm-> 0, which is the same as that in Theorem 2.3 when
While many lower bound results
available for uniform hypergraphs [2, 7, 20, 22]. non-uniform hypergraphs are less studied. Our lower bound in Theorem 3.1 leads two notable discoveries: (i) the Regions of
for
((m) are fully characterized by the simple quantity of L, (ii) the Regions of PossibiliyyIIpoossbbiit for non- uniform hypergraphs are fully characterized by the simple quantity of max2<m M (lm }.
3.1 Tightness of the lower bounds
We propose test for the global testing problem (1.4) and show that it attains the lower bounds in Theorems 2.3 and Theorem 3. For simplicity, we only discuss this for DCBM with moderate degree heterogeneity but the tightness holds in much broader settings (c.g., DCMM).
8

---

For each 2 S m S M, we first compute a vector m7(m) E R", which serves as an estimate of ((m)
when the null hypothesis is true. Fix m. Given a positive vector u E R", define L(u) E R" by
Li(u)= = Ln (distinet) ss2.ndm + Σ bo
(m)
Ugllsy ... Um
(3.18)
(Dir (distinnc) f1
(m)
+ > Li (non-distinee) Us, U6m)) (m-1)/mm 1)/m²
Let Nm = -- Initialize at (0)) On, compute (²))) ((((k-1) iteratively for 1,... Nm- and output (N)) m)( We note that each un is simple function of node degrees, 1 S i S For m E (2, since r7(m) a we estimate ((m) directly from node degrees. However, for m 4, (1) is biased estimator of g(m) under the null, and the bias is caused by diag( (ans(Q(m)) @(m)). The iteration serves to reduce this bias. The required number of iterations depends on m explicitly.
Next, we construct a statistic Q!T) to capture the difference between A and rank-1 estimate of the Bernoulli probability tensor. Let (mm) be a tensor of the same size as A where Ar(m))
(m)) for 1 S i1,-... Am n. We say that S = (S1, S2, S2,.... Sm.1)) is (m+ 1)- partition of {1, 2, ................................ n) if S1,..... Sm+1 are disjoint and their union is {1, ......,,1....... nn. Let B be the set of all (m + 1) 1)partiiioons. For each S = (SI..... Sm..1)) E B and 1 < ki,.., km S m + 1, let
(m)) (/m))
}.
((m))=
max S=(Si..... (m+1)EB
max 1ski km Sm+1
Σ
Ai...oo
(m))
(3.19)
1155k prmim ES.. (distinct)
Finally, we combine [nn mm)!/nn]] Σn
Q!" ..... Qa (M) For each m, let (m())
(n) ân (1 an)). where ån
A (m)
km...mm The test statistic is
On = max 25m M
(3.20)
Recall that by Theorem 3.1, for any alternative with max2gmgM = o(1), we can pair it with a null so that the pair are asymptotically indistinguishable. The next theorem says that the proposed test statistic @n can successfully separate any alternative satisfying maxe<msM {fm] >> log 1+6 (n) (for some d >> O; taking 5 = 0.1 is adequate) from the null. Therefore, except for a logarithmic factor, our lower bounds are tight. Recall that f = ||0(m) | (1((m)))))))))))))))))))))))22 (1² (m)) Let ofma) and ((m)) maximum and minimum entry of the vector ((m), respectively.
be the
Theorem 3.2 (Tightness of lower bounds). Consider the general tensor-DCBM. model with M 2 2. Let h = = Em Ty, and let p(m) E R.K.K"" be the matricization of p(m)) Suppose || [[mm)]] S C. maxi (hx) S C mimnggg (hx), 0lm) S (Col))
min' ofmo) S Co for constant co 1, and 100m=)17~31100mm) llg(()) + 30, for every S m S M. Then, On - 0 in probability, if Ho holds, and on + oo in probability, if H1 holds and maxe M (fm 3/Dog' [n)) + co.
To speed up the computation of o, for large n, we introduce a proxy statistic by replacing the search over B by a specific B as follows: conduct SVD on the matricization of A(m), take the first (m + 1) left singular vectors, and apply the spectral algorithm [13] to partition nodes into (m + +1) groups.
We use this partition B to replace the maximization over B in (3.19), to get proxy to Q! the test statistic on is then defined similarly as in (3.20). As long as the hypergraph is not too sparse, this proxy works well and is computationally much faster.
4 Numerical study
We use simulated data to validate our theoretical results. Fix (n, K, K, = (500, 2, 3). In Experiment 1, we consider the SBM model and verify that the Regions of Impossibility are different for symmetric and asymmetric SBM (see Section 2.4). Let 6, = n 1/2 for 1 < i S n, and Pisa= = 1 if i = j k and Pıys = 1/4 otherwise. We consider symmetric case where each communities have 250 nodes and an asymmetric case where two communities have 375 and 125 nodes, respectively. For each setting, we randomly generate the hypergraphs, apply the degree- based x2 -tsttisstic vha in Section 2.4, and repeat for 500 times. The histograms of vi, for two cases are on the left panel of the figure below

---

(green: symmetric alternative; red: asymmetric alternative: blue: density of (0. 1)). By Lemma 2.2, Vn (0, 1) in the null. Hence, the results suggest that 4 is unable to distinguish the symmetric alternative from the null but can distinguish the asymmetric alternative from the null.
In Experiment 2, we consider DCBM and use the lavoa-lae configuration in Section 2.2 where the degree matching strategy is employed. We verify that a degree-based test such as ún, indeed has no power. Let (n, K,m) m) be the same above. In the null, we let 0; be iid drawn from Pareto 5) and then re-normalize the vector of 0 so that n =| let (P*, hh) be the same as the asymmetric case in Experiment I and generate 0 is in (2.12) (D = 1g as a nonlinear equation and apply the Matlab function solve). The histograms of thn under the null (green) and alternative (red) are shown on the middle panel of the figure below. The two histograms are inseparable from each other.
Ca. for C. n in the alternative,
is obtained by treating ((P(Dh))
0.5
0.15
2.0
density
0.4
Symmetric case
Asymmetic case
density
0.10
Altemative
Null
density
1.5
Altemative
Nuil
0.3
1.0
0.2
0.05
0.1
0.5
0.0
0.00
0.0
-10
-5
5
10
15
10
20
30
0
4 6
Wn under SBM
Un under DCBM
(h under DCBM
In Experiment 3, we study the test statistic on proposed in Section 3.1. The simulation setting is the same as that in Experiment 2, except that e, = n 11/2, To save computing time, we use the proxy of on by plugging in from spectral clustering (see Section 3.1). The histograms of the test statistic under the null (green) and alternative (red) are shown on the right panel of the figure above. We see that on successfully distinguishes the alternative from the null. This validates our result in Theorem 3.2. The distribution of on in the alternative has two modes, due to that the proxy we plug in has two most frequent realizations. However, this does affect the testing performance.
5 Conclusion
We consider the problem of global testing for non-uniform hypergraphs in broad DCMM setting. Given an alternative, how to identify the null that is hardest to separate from the alternative is a challenging problem. We solve this by proposing degree matching strategy, and use it to derive a tight lower bound by tensor scaling techniques and delicate analysis of the x >i-divergence. We discover that for m-uniform hypergraph, the Regions of Impossibilit/Possiilliy are governed by the simple quantity of f = ||@(m) || m- ( (
governed by maxg<ms AM [4m }). We also propose (and so those for a non non-uniform hypergraph test that attains the lower bounds, so our lower bounds are tight. For future work, we notice that the test in Section 3.1 is computationally expensive. It is desirable signed-cycle statistics [6, 14] are polynomial-time statistics that have shown appealing performance for network global testing. It is possible that these statisties can be generalized hypergraphs to provide polynomial-time tests that are also theoretically optimal. We leave it to future study.
find some fast algorithms that also achieve the lower bounds. The
Acknowledgments and Disclosure of Funding
The authors thank the anonymous reviewers for useful comments. J. Jin is supported in part by NSF Grant DMS-2015469. Z. Ke is supported in part by NSF CAREER Grant DMS-1943902
References
[1] Sameer Agarwal, Jongwoo Lim, Lihi Zelnik-Manor, Pietro Perona, David Kriegman, and Serge Belongie. Beyond pairwise clustering. In 2005 IEEE Computer Society Conference Computer Vision and Pattern Recognition (CVPR OS), volume 2, pages 838-845. IEEE, 2005.
[2] Kwangjun Ahn, Kangwook Lee, and Changho Suh. Community recovery in hypergraphs. IEEE Transactions on Information Theory, 65(10):6561-6657, 2019.
10

---

[3] Ravindra Bapat. D1AD2 theorems for multidhmensional matrices. Linear Algebra and its Applications. 48:437-442, 1982.
[4] Javier Béjar, Sergio Álvarez, Dario García, Ignasi Gómez, Luis Oliva, Arturo Tejeda, and Javier Vázquez-Salceda. Discovery of apatio-tempord patterns from location- based social networks. J. Exp. Theor. Artif. Intell., 28(1-2):313-322 13-3399,, 2016.
[5] Austin R Benson, David F Gleich, and Jure Leskovec. Higher-order organization of complex networks. Science, 35366255: 2016.
[6] Sébastien Bubeck, Jian Ding. Ronen Eldan, and Miklós Z Rácz. Testing for high-dimensional geometry in random graphs. Random Structures & Algorithms, 49(3):503-532, 2016.
[7] I Chien, Chung-Yi Yi Lin, and I-Hsiang Wang. Community detection in hypergraphs: Optimal statistical limit and efficient algorithms. In International Conference on Artificial Intelligence and Statistics, pages 871-879. 2018.
[8] Shmuel Friedland. Positive diagonal scaling nonnegative tensor to one with prescribed slice sums. Linear Algebra and its Applications. 434(7):1615-1619, 2011.
[9] Debarghya Ghoshdastidar and Ambedkar Dukkipati. Consistency of spectral partitioning of
uniform hypergraphs under planted partition model. Advances in Neurul Information Processing Systems, 27:397-405, 2014.
[10] Debarghya Ghoshdastidar and Ambedkar Dukkipati. Consistency of spectral hypergraph partitioning under planted partition model. The Annals of Statisties, 45(1):289-315, 2017.
[11] Jacopo Grilli, György Barabás, Matthew Michalska-Smmtth and Stefano Allesina. Higher-order interactions stabilize dynamics in competitive network models. Nature, 548(7666):210, 2017.
[12] Pengsheng Ji, Jiashun Jin, Zheng Tracy Ke, and Wanshan Li. Co-citation and co-authorship networks of statisticians. Journal of Business & Economic Statistics, to appear, 2021.
[13] Jiashun Jin, Fast community detection by SCORE. The Annals of Statistics, 43(1):57-89, 2015.
[14] Jiashun Jin. Zheng Tracy Ke, and Shengming Luo. Optimal adaptivity of statisties for network testing. Annals of Statistics, to appear, 2021.
[15] Zheng Tracy Ke, Feng Shi, and Dong Xia. Community detection for hypergraph networks via regularized tensor power iteration. arXiv preprint arXiv: /900: (9999990995333 2019.
[16] Chihcon Kim, Afonso S Bandeira, and Michel Goemans. Stochastic block model for hypergraphs: Statistical limits and semidefinite programming approach. 107i::1807.02884, 2018.
[17] Sungwoong Kim, Sebastian Nowozin, Pushmeet Kohli, and Chang Yoo. Higher-order correla- tion clustering for image segmentation. Advances in Neural Information Processing Systems, 1538, 2011.
[18] Lei Li and Tao Li. News recommendation via hypergraph learning: encapsulation of user behavior and news content. In Proceedings of the 6th ACM International Conference on Web Search and Data Mining, pages 305-314, 2013.
[19] Jiajun Liang, Chuyang Ke, and Jean Honorio. Information theoretic limits exact recovery in sub-hypergraph models for community detection. IEEE International Symposium on Information Theory, 2021.
[20] Chung- Yi Lin, Eli Chien, and I-Hsiang Wang. On the fundamental statistical limit of commu- nity detection in random hypergraphs. In 2017 IEEE International Symposium on Information Theory (ISIT), pages 2178 2182. IEEE, 2017.
[21] Cammarata Louis and Zheng Tracy Ke. Power enhancement and phase transitions for global testing of the mixed membership stochastic block model. Manuscript, 2021.
11

---

[22] Mingao Yuan, Ruiqi Liu, Yang Feng, and Zuofeng Shang, Testing community structures for hypergraphs. Annals of Statisties, to appear. 2021.
[23] Dengyong Zhou, Jiayuan Huang, and Bernhard Schölkopf. Learning with hypergraphs: Clus- tering, classification, and embedding. Advances in Neural Information Processing Systems, 19:1601-1608, 2006.
12


Reviews:
[{"review_id": "nk2ImSCxkvs", "reviewer": "Reviewer_LQ2Q", "summary": "This paper studies a binary hypothesis testing problem that considers whether a given hypergraph has one or more than one community. Under a general class of degree-corrected mixed-membership model for hypergraphs, it identifies conditions under which it is impossible for any test to distinguish between the null and alternative hypothesis. The above results, which are first derived for uniform hypergraphs, are then extended to non-uniform hyper-graphs by viewing a non-uniform hypergraph as a collection of uniform hypergraphs. The paper also proposes a statistical test that successfully solves the above-mentioned hypothesis testing problem under conditions that can get logarithmically close to the impossibility regime. Experiments on simulated data validate some of the theoretical findings.", "questions": "", "limitations": "", "rating": 5, "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": " 1. This paper argues that it is the first to consider significantly more flexible models that support mixed-membership and degree-heterogeneity in hypergraphs. The key idea is degree matching, which allows construction of a difficult-to-distinguish alternative hypothesis. It would be better to present an intuitive explanation for the technical difficulties that arise due to the use of a richer model. What techniques have been borrowed from the existing literature and why are existing techniques not applicable in the current setting?\n\n2. Why is $\\pi_{i_1}$ still present while computing the expected degree of node i_1 under the alternative hypothesis? Under the alternative hypothesis, $\\pi_{i_1}$ is a random quantity.\n\n3. Degree matching aims at matching the expected degrees of nodes under the null and alternative model. Thus, it appears reasonable to argue that a degree-based test would fail in this case. However, to argue that \"any\" test would fail, the paper shows that $\\chi^2$-divergence between the null and alternative distribution goes to zero asymptotically. An intuitive explanation for how one goes from arguing that expected degree matches to arguing that $\\chi^2$-divergence is zero would be very helpful in making the paper more accessible.\n\n4. Sections 2.4 and 3.1 are difficult to understand. Consider providing additional details and more intuition.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 "}, "extra_text": {}}, {"review_id": "bYWDJXptNU", "reviewer": "Reviewer_V2Sb", "summary": "The current paper explore information-theoretic results for testing the existence of community underlying an observed hypergraph. The nodes of hypergraph are degree hetergeneous extending homogeneous results in literature. Both uniform and non-uniform hypergraphs are considered.\n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The results are new, original, solving a basic problem in graphical model. The results are important, and proving deeper theoretical insights on the nature of the testing problem.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is a lack of comparison with existing results such as Yuan et al. (AoS, 2021) who explored testing limits under homogeneous setting, i.e., $\\theta_1=\\cdots=\\theta_n$. Can the authors compare their results? For instance, setting all $\\theta_i$'s to be equal, can they recover the results of   Yuan et al. (AoS, 2021) ?\n\nAlso, I am a bit confused by the definition of degree-corrected model which seems a bit different from literature. Can the authors explain why they consider such a different version?", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "SMmTqFyyEyY", "reviewer": "Reviewer_oDcv", "summary": "This paper introduces and studies a hypergraph community detection model called RMM-DCMM. In this model, each vertex may have a different degree (degree-corrected) and may also belong to many different communities (mixed-membership).\n\nA main takeaway from the paper is that possibility/impossibility of testing whether this complicated model has K = 1 or K > 1 communities boils down to the quantity ||\\theta||^2 ||\\theta||_1 \\mu_2^2. \n\nThe main results are:\n1) Region of impossibility result for RMM-DCBM (a subset of RMM-DCMM). This shows that given any:\n\t(a) degree-correction factors \\theta for a 1-community model\n\t(b) tensor P representing connection strengths between subsets of the K communities,\n\t(c) distribution F over mixed membership vectors, supported on {e_1,...,e_K},\n\tif ||\\theta||^2 ||\\theta||_1 \\mu_2^2 --> 0 (where \\mu_2 is the second eigenvalue of the matricization of P), then there is a choice of degree-correction factors \\theta^* such that the K-community model given  by (P, \\theta^*, F) is information-theoretically indistinguishable from the 1-community model given by \\theta\n\n2) Region of possibility result for RMM-DCBM. For any K-community model (P,\\theta,F) with K > 2, such that ||\\theta||^2 ||\\theta||_1 \\mu_2^2 / log(n)^{1.1} --> \\infty, there is a test (based on estimating the degree-correction vector \\theta assuming that the model is null) to distinguish it from any 1-community model.\n\nThese results extend to RMM-DCMM under some additional conditions.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper appears technically correct, and the connection to tensor scaling is especially nice. Furthermore, it is nice that the paper boils down the study of a complicated testing problem to whether a simple quantity ||\\theta||^2 ||\\theta||_1 \\mu_2^2 tends to 0 or to infinity. Finally, the RMM-DCMM model introduced by the paper is a natural community detection model.\nOverall, this paper is of interest to researchers specializing in community detection, so it seems on-topic for the conference.\n\nNevertheless, I am on the fence about acceptance, since I think that the result may only be of interest to a very small group of attendees.\nFrom a practical point of view, the testing algorithm to distinguish H0 (1 community) from H1 (more than one community), seems to depend heavily on the null distribution being Erdos-Renyi, and my best guess is that it will not be effective on real-world data (I could be convinced otherwise if the paper had experiments on real-world data). Furthermore, the testing algorithm is computationally inefficient, as it involves an exponentially-large sum. Because of this, the experiments implemented by the paper use an entirely different algorithm -- a standard spectral algorithm based on the matricization of the adjacency tensor.\n\nThus, the significance of the paper appears to be mainly theoretical. The main theoretical insight that I gleaned was that if the expected degrees of the K > 2-community model and the K = 1 community model match, then their information-theoretic distinguishability depends on the quantity ||\\theta||^2 ||\\theta||_1 \\mu_2^2, and whether it tends to 0 or to infinity sufficiently quickly.\n\n\nMinor comments\n\n* \"hypergraph\" in the title should be capitalized for consistency\n* typos: indicies, hypergraphse, \"can not\" --> \"cannot\", \"the simply quantity\"\n\n* Line 127, \\theta^{(m)}, P^{(m)} \\mu_2^{(m)} have not yet been defined. Please either define them or add a remark that they will be defined later and are analogues of the 3-hypergraph case.\n\n* Line 233, write log(n)^{1.1} instead of log(n)^{1+delta}\n\n* Line 286, \"[M; b1, · · · , bK]\" should be \"[M; b1, · · · , bm]\"\n\n* Lines 320, 321: (3.16) and (3.15) are flipped", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "0r2zpxVwila", "reviewer": "Reviewer_jdLd", "summary": "This paper considers the community detection problem in the hypergraph setting: determine whether there is a single community (null hypothesis) or K > 1 communities (alternate hypothesis). The main contribution is the development of lower bounds via bounding the \\Chi^2-divergence, which is a standard method, although quite technically demanding in this setting due to the many parameters involved. Overall, this is a clear contribution to the theory literature on stochastic block models and community detection. It is a bit harder to judge its appropriateness for NeurIPS.", "questions": "", "limitations": "", "rating": 5, "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": "On the technical side, the main contribution of this paper is pushing through the challenging technical analysis for the \\Chi^2-divergence to demonstrate a lower bound that is tight up to logarithmic factors. I believe this is a valuable theoretical contribution, that extends the community detection work from the random graph to the random hypergraph setting. The paper is a dense read, due to the need to capture all of the notation and technical details within the page limit. I did not check the proofs carefully, but the results seems correct.\n\nIt does not devote much space or effort to justifying where this form of hypergraph model might arise and where the obtained theoretical understanding might lead to some useful algorithms. This would have significantly strengthened the paper with respect to NeurIPS, and might give the broader audience an appreciation for why such these results might be needed as part of a larger body of work. As the paper currently stands, it is an interesting contribution to a seemingly narrow set of technical questions arising from the stochastic block model community, and might be a better fit in a venue that is more targeted towards that community. To be clear, I do not see a clear reason to reject this paper from NeurIPS but I do not see a compelling reason to include it either. The paper would have been much stronger with a sample application and a real dataset, to justify the complexity of the proposed hypergraph models. I completely agree that this is a challenging technical problem, but I would prefer to see how and why this level of complexity might be needed some day in a data-driven setting.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I did not have any concerns on this front.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper's main contribution is to provide a crisp theoretical characterization of the feasibility of detecting multiplicity of underlying communities in a degree-corrected mixed membership hypergraph model. 

It has been recognized by all reviews that this is a significant achievement that will be of interest to researchers working on stochastic block models and related inference questions. The reviewers did not give very high marks on the basis that the topic may be of interest to only a limited subset of the NeurIPS community, also pointing to the fact that the paper could be made more attractive if a compelling application was brought forward. 

The authors' reply to these comments is an argument that the problem they tackle is important in network science, an area which is relevant for NeurIPS, and a description of concrete applications to hypergraphs of co-authorships in scientific articles. The authors further point to the usefulness of their result to hierarchical clustering, and explain in greater detail how their non-polynomial time test informs the design of the polynomial test used in the experiments. 

I believe that these answers by the authors alleviate the concerns expressed by the reviewers, and suffice to justify acceptance of the paper to the conference. 






Decision: Accept (Poster)