Sparse Hypergraph Community Detection Thresholds in Stochastic Block Model
Authors: Erchuan Zhang
David Suter
Giang Truong
Syed Zulqarnain Gilani
Venue: NeurIPS 2022 Accept (2022)
Keywords: community detection
hypergraph stochastic block model
Kesten-Stigun threshold

Abstract: Community detection in random graphs or hypergraphs is an interesting fundamental problem in statistics, machine learning and computer vision. When the hypergraphs are generated by a {\em stochastic block model}, the existence of a sharp threshold on the model parameters for community detection was conjectured by Angelini et al. 2015. In this paper, we confirm the positive part of the conjecture, the possibility of non-trivial reconstruction above the threshold, for the case of two blocks. We do so by comparing the hypergraph stochastic block model with its Erd{\"o}s-R{\'e}nyi counterpart. We also obtain estimates for the parameters of the hypergraph stochastic block model. The methods developed in this paper are generalised from the study of sparse random graphs by Mossel et al. 2015 and are motivated by the work of Yuan et al. 2022. Furthermore, we present some discussion on the negative part of the conjecture, i.e., non-reconstruction of community structures.

Sparse Hypergraph Community Detection Thresholds in Stochastic Block Model
Erchuan Zhang School of Science Edith Cowan University erchuan. watauuaan.anggeec... edu.au
David Suter School of Science Edith Cowan University
Giang Truong School of Science
Edith Cowan University h. truong@ecu. edu, au
d. suter edu.aa
Syed Zulqarnain Gilani School of Science Edith Cowan University s. gilani@ecu edu au
Abstract
Community detection in random graphs hypergraphs is interesting funda- mental problem in statistics, machine learning and computer vision. When the hypergraphs are generated by stochastic block model, the existence of sharp threshold on the model parameters for community detection was conjectured by Angelini al. 2015. In this paper, confirm the positive part of the conjecture, the possibility of non-trivial reconstruction above the threshold, for the case of two blocks. We do by comparing the hypergraph stochastic block model with its Erdös-Rényi counterpart. We also obtain estimates for the parameters of the hyper- graph stochastic block model. The methods developed in this paper are generalised from the study of sparse random graphs by Mossel et al. 2015 and are motivated by the work of Yuan al. 2022. Furthermore, we present some discussion on the negative part of the conjecture, i.e., non-reconstruccton of community structures.
1 Introduction
Community detection, or clustering, aims identify groups sharing similar properties from a global population. It is fundamentally important problem in statistics, network analysis and computer vision 15
26 Many clustering algorithms have been developed based on graphs in which each edge contains exactly two vertices representing pairwise relationships on data. However, real-world data are often much more complicated than the ordinary graph structures. For example, in the co-authorship network 9 24 277, the number of co-authors may vary from paper to paper that one can hardly study edges consisting two co-authors only.
To represent higher order relationships among data, hypergraphs have been proposed to model data and have been shown have some advantages over graphs (36). In the co-authorship example above, a generalised edge (called hyperedge) allows us to consider the connectivity of arbitrarily many co- authors. In recent years, hypergraphs have been widely used model complex data relationships, for instance, in robust multi-structure clustering (26). bioinformatics [31], and social networks extraction [35]. However, from both theoretical and methodological sides, the complexity of hypergraphs creates much more challenges in the sense that many amalysis tools developed in the graph case can not be easily generalised to the hypergraph case. In general, analysing the spectral properties of the adjacency tensor of hypergraph is more difficult than studying the spectrum of the adjacency matrix of graph.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

The stochastic block model (SBM), also known as the planted partition model, was initially proposed by Holland et al. [7 to model random graphs with community structures. The general idea behind this model is to label each vertex as community member identically and independently, and then construct a random graph based on the membership and some given probabilities. It becomes the well-known Erdös-Rényi graph model if we ignore the membership restriction. The recovery and/or detection problem, based on the SBM, is to find the community membership when the number of vertices is sufficiently large. SBM often serves as benchmark for clustering algorithms graph data. Likewise, an analogous model called the hypergraph stochastic block model (HSBM) was proposed to model higher-order relationships for random hypergraphs [13]. In what follows, we will present a brief introduction to hypergraphs, HSBM and its associated detection problem.
1.1 The stochastic block model for hypergraphs
hypergraph is pair H (V. where V set of vertices and is a set of hyperedges, which is a collection of subsets of V. The degree of a vertex v E V is the number of hyperedges in H that contains v. The degree of a hyperedge e E E is the number of vertices contained in e. The hypergraph & is d. A 2-uniform hypergraph is cyclic ordering of a subset of the vertex set, and of hyperedges,
H is called d-uniform if the degree of every hyperedge a graph. An l-cycle in H where any two adjacent hyperedges have exactly I common vertices. We call an l-cycle loose if I = 1. For instance, let H1 (V. be a 3-uniform hypergraph, where V = {1r, 02 . E ((1, Uj, ux]l1 S i < < k S 7). Then {(V1, 02, va), (V3, U4, v5), (Us, Us. v133 is loose cycle.
There are many ways to represent hypergraph. For instance, the incidence matrix of hypergraph if the vertex v V is contained in the
H is defined as A (0, 10.1).10 1 where e(v,e) hyperedge e E E, and 0 otherwise. The adjacency tensor of H is defined as T, where Ti..-.. .a = 1 if (i,,... id) is hyperedge of H, and otherwise. The adjacency matrix of H is defined as B = (Bag)l x [V], where Bij = [e:(ee) Te if ( j. and 0 otherwise, here is a hyperedge and Te is an element in its associated adjacency tensor. Unfortunately, most of the computations involving the adjacency tensor are NP-hard, for examples, determining the rank-1 I approximation of a tensor, whether a tensor has a given spectral norm [16].
For simplicity, from now on, we specify our d-uniform hypergraph stochastic block model with two roughly balanced communities. Considering non-uniform hypergraphs or hypergraphs with multi- communities may require extra effort, which will be reserved for future work. Let H = ([x)] E be bead. d- uniform hypergraph with vertex set [n] == { 2, n} and hyperedge set E, a == (a),
σn) =
1+11-11" the spins on [n], which means each vertex E [n] is assigned with a spin o; 11] Let S, be the set of all pairs (H,o), we can generate a random pair (H, o) from the finite set S,, as
follows (13 14 25
First generate i.i.d random variables os E {+1, uniformly for each E [n]]
Then, for the obtained a = (01, Jn), we generate a random d-uniform hypergraph H where hyperedge = {ii.-. ia) is included independently with probability Pn. if o,, = ... = oi., and with probability qn. otherwise, where 0 < In < Pn < (pn qn possibly depending on ni).
We denote by Ha(n,, Pn, (n) d-uniform hypergraph generated by the process above. (With a little notation abuse, we sometimes denote the distribution that such hypergraphs follow by the same notation). In particular, H2(n1 Pas 9n) is random graph generated by the graph version of the SBM.
Suppose C1 = {i E [n]la, = +1} and C2 = {i E [m]lo, = -1} are two communities in the hypergraph H. The goal of community detection is to estimate the unknown spin up to sign flip by observing H only from a sample (H, o) drawn from Hn( Pr: qn), i.c., to find estimators à, [[+1--1] that are correlated with the true partition o, By correlation, we mean there exists constant e E (0, 1), for any e > O.
lim
-
+ >}) = 0,
where O,,0,) == A. Eie(n) σ is the empirical overlap between a and 6.

---

Recall the definitions of exact recovery and almost exact recovery of communities in the literature (for example, see (25) By exact recovery, we mean finding a spin vector (+1,-1)" such that
lim P((O,(6,o) 1 = - 1.
That is, the estimated spin vector à is either exactly the true spin vector exactly the negative true spin vector -a. By almost exact recovery, we mean finding a spin vector à E ++11-11 such that, for any c >> 0,
lim P(11O, - 1| (6, 0) + + ,}) =0.
2 n-000
That is, the empirical overlap (ō, σ) is in [-1, U e, c. asymptotically almost surely. This case almost exactly recovers the community, as indicated by the terminology, compared with the definition of exact recovery.
(1
The study of sparse graphs/hypergraphs as well as those with constant average degree, is well motivated from the viewpoint of real networks. For instance, many large social networks like Twitter or LinkedIn, may have several millions of nodes but only ten times more edges [20] A coauthorship network may have millions of nodes, but the average degree no more than 20 in general [24 Therefore, it is natural to consider the sparse HSBM with Ps, and In of the order O (1/nd=1).
Decelle al. 7 conjectured the existence of sharp threshold, called Kesten-Stigun threshold, of detection in the sparse graph SBM based on some ideas from statistical physics. More precisely, if
P. = -. On L. where a, b are constants independent of n, then detection possible if and only
(a b) > 2(a + b). This conjecture was confirmed in 21 22 23 6. for examples, by studying the
spectra of the bonbbacktracking (6), self-avoiding [21] or graph powering [T] matrices. Moreover,
some efficient algorithms were proposed to achieve detection at the threshold 66 [I.
In the case of the hypergraph SBM, Angelini et al. conjectured the existence of a sharp threshold on the model parameters, for community detection in the sparse hypergraph. If pm [2")
In
i.e., the hypergraph H Ha(n, Pre (n)) has constant expected vertex degree. Pal et al.
25
proved
the positive part of the conjecture, the detection is possible if 3 a, where (d 1) a+ 1)b
= (d - 1) g= Their method is based on the spectral analysis of the so-called self-avoiding matrix associated with the hypergraph, which is a generalisation to random hypergraphs of the method developed by Massoulié [21] for sparse random graphs. Moreover, the consistent estimators for model parameters a and b are still unknowr[]
In the present paper, we reconfirm the positive part of the conjecture by comparing the sparse HSBM with an appropriate Erdös-Rényi hypergraph model (see Theorem T.T). which has also been used by Yuan al. [34]. Further, we give consistent estimators for a and 6 if the detection is possible. Our methods are motivated by the study of the community detection problem on the graph SBM conducted by Mossel et al. [22] The main results of the present paper are summarised as follows.
1.2
Main results
Let Hd (n, P=+(22-1-1))) be the Rédös-Rényi model in which each hyperedge is included with 20-1
common probability P2 Din. which is chosen to make sure this model has the same average degree as Ha(n, (1, 9.). other words, Ha (n.. (2 represents d-uniform random Pa,
20-1
hypergraph without any community structures. In particular, Ho (n. Pectol is the traditional Erdös- Rényí random graph that has been extensively studied in the graph literature 4 12 8.
Let Pn. and Pr denote the probability measures with respect to Ha(n, Pn, gn) and Pa + (2 (22-1-1)a) respectively. Then I, and F, are said to be mutually contiguous if for any 2
Ha n,
measurable sets A,, P., (An) 0 if and only if P,, (A.,) +
- P. and P.,, are said to be By some personal correspondence with Ludovic Stephan and Yizhe Zhu, we now realized that the algorithm provided in (25) implied some way to find a way to estimate the parameters a, b, i... Theorem 6.1 of (25 gave an estimate of and a lower bound on B. However, it is not efficient and precise as the method in 30 where the two leading eigenvalues of the non- backtracking operator give an estimation of and b.
3

---

asymptotically orthogonal if there exists sequence of measurable sets A, such that (n,(A,) - 0 Pnd (A,,) + 1 as n + co. From now on, we fix the following notation,
b
On =
d-
where a b >> are some constants independent of n, d is integer. Define
(d (2 1)6
- 2d-1¹
= (d
2d-1
where measures the expected degree of any vertex and measures the discrepancy between the number of neighbors with different signs of any vertex.
Theorem 1.1. If f > then Pn and Pn, are asymptotically orthogonal. Theorem 1.2. Let c. be the number of loose cycles of length in and define
d|El
ân = (d=1))
Bn = (2 - ) t
where Sn
llog nl. [El is the number of observed hyperedges, then ān d-1 (ān + (2d-1 - 1),3)) and bn = --116 (ăn ( are consistent estimators for a and b, re-
spectively. Namely, än - a and bn + in probability as n - 0c.
When d = 2, the condition 8 = becomes (a= 2(a+b), which is the threshold for community
detection the (graph-based) SBM. Readers may refer to [2 23 for more detail. Intuitively speaking, Theorem 1.1 says that Ha(n, Pn; Pn; qn) and H.d n2 2
(2--121)s)-- are asymptotically
almost surely distinguishable above the threshold (i.e.. can distinguish a community with structure from random hypergraph with the same average degree). Note that Theorem 1.1 also appeared which is
in 34 though there are some subtleties. In 34 the setting is Pn - Qn (only differs by constant factor (d (d-1))) 1)!). Moreover, k in Equation (4) in Section 2.2 in 34 corresponds to our 8²/a here. We generally follow the proof techniques of Normal instead of Poisson distribution
the same order
(34] The difference is that they show convergence for the model (n, Pn, ). If we take h: = 2, m = 3 in Theorem 2.6 in [33, which means the 2-block, 3-uniform HSBM, they showed sharp phase transition: when 1, Ha(n, Pn: 9n) and
H.g
Pr, +2" 1)gm.
indistinguishable and distinguishable when 1.
There are two types problems or results: (a) find way to distinguish HSBM with a corresponding Rénöi hypergraph model and find way to estimate the model parameters a, by (b) develop an algorithm to output a partition that is correlated (at least 1/2 + c portion of the labels are correct up to sign flip) to the ground truth labeling a. Our work addresses (a), which does not imply any way to find an estimator of the partition for (b). We get an estimator for the model parameters a, by counting cycles, but it does not provide way to find partition ô. Also, solving (b) does not
immediately imply solving (a), although most algorithms for (b) (such as the ones 25 30 may imply some way to solve (a).
The remainder of the present paper organised follows: In section 2 we study the probability distribution of the number of G. loose cycle Xç.. and then prove our main results based on the techniques developed by Mossel al. [22]. In section 3 we show some building blocks of proving our main results, which followed the proof techniques of [34]. In section 4 we discuss the barriers on showing the negative side of the threshold conjecture, i.e., nonsssconttinttion of community structures. Section SisionnSSoonee concludes the paper, including some further discussion.
2 The distribution of loose cycles
In this section, we mainly show that the number of C,-oo cycles of H Ha(n, Pao qn) or p2 is asymptotically approximately Poisson-distributed. In general H Ha (n, Pa+ 2d-1
inhomogencous graphs, Bollobás et al. [5] demonstrated that the number of cycles asymptotically

---

follows the Poisson distribution. We borrow their proof techniques to get similar conclusion in the hypergraph case. Then, by comparing the first two moments of the number of -noooe cycles, find that (n Pni qn) and Ha nn, P-2
2 1-1
asymptotically orthogonal if 3 >
Theorem 2.1. Let Xc. be the number of Sn-loose cycle of a hypergraph H. Suppose Ca O (og (n))).
1f) Halni, Pas 9n), then Xsn 4 Pois
(ofn (28m+ 2kn
(2) ~ Ha (n, P 1)98)) ) then Xc.
Sn Pois 5n 25n
2a
where 4 denotes convergent in distribution.
For any non-negative integer let [X], be the product X X(X 1)
(X (X- -
Lemma 2.2 (Lemma 2.8 in 32 ).
'I,..., AE be some set of fixed non-negative reals, and let Xi.: K be non-negative integer random variables defined on the same space 9n, for each n.
If for each fixed set of non-negative integers ri,"" Tkk
A
lim n 10000
III
then the variables X1,
N are asymptotically independent Poisson with means X4.
By Lemma 2.2 if we can prove the expectation [[ -> 1x", then Xc. 4 Pois(u), which will be shown in the next section.
With the preparation provided by establishing Theorem 2.1 now we can prove our first main result, Theorem 1.I We use (.,(.). (E()), Var(-) to denote probability, mean and variation with respect to Ha (n., Pn: Qn) while notations with tilde above denote their counterparts with respect to
Ha n, Pa +2" -11gg
24-1
Proof of Theorem I.I Since 32 > a, there exists a constant p satisfying > P Va. Then EX,, Var = =(pp2c)) and FX,,, VarX,, o(p²6n) as > oo.
Let An (Xcm s EXx, + p by Chebyshev's inequality,
(An)))= Xc. EXc VarXan
pon
VarX p²Gn
S
2
1, as - oc.
(3)
v VarXa.
Since EX;,, - EXG,
gen = w(pfm), then for larger enough Sn. EX,, - phnn 2 EX c. + p Hc
which implies (An) 5 PPa(Xc S IX.... -poe). By Chebyshev's inequality,
X -EX
-h
Var D2Cn
(A(AA) < Pn
0, as n - oc.
VarXç,
v VarXç,
By 3 and
we have shown that P, and P. are asymptotically orthogonal.
Proof of Theorem T.2 First of all, we have a consistent estimator &, for by simply count-
ing the number hyperedges. If we can prove that can be consistently estimated by 3, = (2,,XX,, á cn then à --1 (ân (2d-1 1)3r)) and b,. a-1 (ăn Bx)) are consis- tent estimators for and b, respectively.
5

---

Take E (va, B), by Chebyshev's inequality,
asm 40m
Xc.
Pn aa 2 g -p Pm
25n
25n
VarxX
Va
(5)
26 / Varvaar
2
+1 as Sn - oc.
ponn
a 48n+ 25n
ein
X
(2 a - + p Pn
25n
VarX
VarXXn
(6)
2n /SnnVarXe VarX
2 1
+1, as Sn - xc.
phnn
Thus, 2Gn - afn 186. - p g5n + + a.a.s. Since p = o(35n) as Sn + 00, we have Xn a= = (1 + 6(1)) a.a.s. Since a.. + a as Sn - cc, we have 25n - a (1 (1)) a.s.s. Therefore, B, (2 a to - as Sn. 00.
Building blocks for proving Theorem 2.1
The main purpose of this section is provide some building blocks for proving Theorem 2.1 the techniques originate from (34]. See also Lemma 6.3 on Page 28 and some proof techniques on Page 24 in 33
Note,
The proof that the number of loose cycles hypergraphs follows the Poisson distribution is very different from that in the graph case. In [22), since & vertices in graph forming cycle of length m follow the Binomial distribution, we can calculate the probability P(N = m) =
(Binom (k- 1, 2) E {m 1, m)) for even m and the probability of these vertices form a cycle the summation of IP(N m) over all possible (see the proof of Lemma in (2)). In the hypergraph case. the distribution of k loose cycles of length G. forming a cycle is no longer the Binomial distribution.
Lemma 3.1 (Lemma 6.3 in 33
For any in, "., E {+1,- -1), let Tiig
D)T
is = id) + b, then for j j2 1.
F:
Σ
Iniiannd -ishanr Tie- ()-- (12))-)-))------ 1)) ()---))d--))) -)d- -aa
11 E,-,-,;
= (a byr + (a + 1 11)b}².
Proof. Let Jj = (11--1)d-443) 443, Ase 1,)s then
F Σ
Σ
Tessii Tinssian ... lig -u-------:
J. iadee Mo na-6--0-0 n
= Σ
...
Ju
where T(J.) (Ir,,a) is a 2 x 2 matrix defined as follows,
I(J.)= =
+
b
b
Σ
I(Ja)
b
0
Ja eeeementss are different
Ta b
2b
(2
2)
bb b
Io.
2h
a +
b
b
Then, we have F= =Tr(Tg))

---

Note that To- (a b)1² + 2bJ" where I is the x 2 identity matrix, J is the 2 x 2 matrix with all entries Since the eigenvalues of J are and 0, and
X/ = (a- - A) bbJ = det(To X12) (2d (2d X x- 1aaaa) b) 12),
2d-21
the cigenvalues of Lo are b and + (2 1)b. Therefore, finally get F = (a - b)² + (a + (20-1 -16)
Proof of Theorem 2.7 (1) Note that (x r is the number of ordered r-tuples of Sn -a-hyperedge loose cycles. Let (Lgg, 2. r..,.) be the r-tuple of Ga-loose cycles, S₁ the set of r-tuples where the vertices of all the loose cycles are disjoint and S2 the set of r-tuples where least pair of the loose cycles is not disjoint, i.., they share some common vertices. Then the expectation [X Jo is given by
E|X = Σ BI +
Σ
Elur honntt
(E
where Lun Aem.
Lemit is the indicator that Lç.,s are Sn -lose cycles.
Let U1, U2, (c-(dd1) be the distinct vertices and Y the indicator that U1, "2,""" (d-(dd)) is Sn-loose cycle, then E/ = (d.()-))
(Gn (dd()))))) RY. Let be random label assignment and 2((d 2)1jcn
(LG,,)) the hyperedge set of Ls,,i then
Iirigron n
EY = Eg
II
(1 (a)EE(L)))))
d-1
(8)
1
II
I
26=(d-1) ((
oE(#1)(n(d-)) (6), AalEE(LE...)
where Tegigr-ig (o) is the expected degree. If ow, = =... = = then ligig (0) = ((_1) = a.
Otherwise, (a (o) ( = b. We thus write Isfézr-ee (0) (a-b)
Ov.) +
By Lemma 3.1 in the Appendix, we have
a (2--1- 1)b 11)-
5n
/ a a- b)
EY
(9)
2d-1
2d-1
which implies
(Gn - - 1)!
1
+ (2d-1 - 1)6 5n
a- b
Sn
EI Eiin
+
(n 1))
((d-2).){
2((d"1))
2d-1
2d-T
(d 1)5m
a + (24-1 1)b
a b
Sn
+
(d-1)
2d-1
2d-1
Note that the number of elements of S1 is |S|
(m)
ma! ch.
where mg = (a - 1)r. When
mg o(vn), the first term in the right side of is given by
|S1] x EI Ksm. 1S x EI
n!!
1 (d 1)snr
a + (2d-1111 (24-111-1))
1)6 )
Co
b
Sn
+ 2d-1
(n mo)! S (d-111
2d-1
n!
1
(a5t + gla) )
(n my mm))
2Gn
(a5 + BCo
26n

---

where have used the fact that (n-mo)ln""g + 1 if my = olv
me
Now it remains to show that the second term in the right side of converges to 0. Since |S2| s mon mo-1
we have
Σ
Elur ben.d = |S2| Elujzrtenn
(E.
(E(H))
I mnn"" mo-1
I mi0
a
- 0
(ahn 4.66% g6) )" 26n
when mo S cloga for constant E (0, Therefore, E[Xç,. - the proof of the first result of Theorem 2.1
which completes
(2) To distinguish the distribution used in (I), we use E to express the expectation with respect to Ha,n, 10+4221-1100 Similar to the proof of (1), we have 24-1
B[X
Σ
El +
E
Elu 4and
(10)
(LS
(ES
and
(Sn(d - 1) 1)!
Pa + (2 1)4m²
ET L
(n ((d--)) 1)) 2((d - [[][d=)])5mv (1)s"(((()))))))
2d-1
(d (d-1) 1)60 (a (2 1)b)
(d-11
2d-1
The first term in the right side of (10) is given by
a (20-1 - 1)b Sut
mo! (d- 1)5nt 2'nculd-1)r
1
[1 Elu koni
mo
S
2d-1
n!
am
(n mo
26n
5m
2Gr
For (Lg..e) E S2, : U [= has at most Sn (d - 1)r 1 vertices and Snr hyperedges, which implies
[V(L] (d- 1))(())) Then, we have
18(L)
[E(L)I
+ (2d-1 1)6
Bluig
)
n 2d
n
d-1)
d-11)
[E(L))
((d ((d-1)))(E(M))
nd-1
where we have assumed a > b 0. Since there are (1v())))
[[L] many hyperedges isomorphic to
L, we get the estimation of the second term in the right side of (10 as follows,
(E(L)
Σ
Elu ben. I ((d 1)))
( V(L)]
+ as n - ao.
nd-I
a)ES
Therefore, E[X;,Ir 7 Sn
which completes the proof of the second result of Theorem 2.1
4 Discussion on non-reconstruution of the community structures
Motivated by Theorem in [22,, we have the following conjecture.

---

Conjecture 4.1. If S a, then any fixed vertices and U2 H ~ Ha(n, Pn, In).
lim (T 1-000
Tog 2
In the case of graph based SBM, the core strategy is to find a connection between H2 Pu. In) and a Markov processes on a Galton- Watson tree. Before going further, we give the definition of a Galton- Watson free. Given e E [0, 1), let T an infinite rooted tree with root p. the spin Tp of the root p is uniformly assigned from (+1, -1). Then, conditionally independently on Tp: the spins Ty of every children v of p assigned as T₁ = Tp with probability and Tμ -Tp with probability 1 - c. Continuing this process will give Galton- Watson tree with spins. The broadcasting problem on (T, p. is whether the spin Tp could be deduced from the spins at generation of the tree, where I is sufficiently large. Such problem
general infinite trees was initially proposed by Kesten and Stigum 1966 [8] although they used somewhat different terminologies. This problem was solved by Blecher al. 3 and Evans et al. [10].
In the case of HSBM, Pal and Zhu 25 generalized the above defined Galton-Wasd Watson tree to the so-called multi-type Galton- Watson hypertree. Let TT' be an infinite rooted hypertree with root constructed as follows: Generate a root P with spin Tp E (+1,-1) and then generate Pois(a)) many hyperedges that only intersects at p. For 0 S I d - 1, hyperedge is called rype if there are many children (i.e., the vertices in the hyperedge) with spin Tp and d
s many children with spin -Tp in the hyperedge. Hyperedges of type d 1 are generated with probability [d-1]a
a2a-T and of
type with probability (d-1)6("
for 0 S S - 2. It is easy to check that
a24-1
(d - 1)a
2-2 (d 1)b((= : =1
a2d-1
a2
We generate hyperedges of different types i.i.d. by Poisson distribution. For each hyperedge of type 8, in the first generation, we uniformly and randomly pick s vertices with spin Tp and the rest of the d - 1 - vertices with spin -Tp. The subsequent generations are generated by induction.
Note we cannot use Theorem 1.1 in I0] directly to show that the threshold on deducing the spin of the root based the spin of vertex at long generations. A key difference between the Galton- -ationn tree and the hypertree analogy is that the vertex spins in each hyperedge are not independent conditioned on the previous generations. In other words, the independence we need is the paths from the root to a vertex with the spins +1 and that are independent. Although it the case for vertices belonging to different hyperedges (by the definition above), this cannot be the case for two vertices belonging to the same hyperedge. Therefore, there is a key barrier to analyzing the broadcasting problem and relating that to the percolation model analyzed in [0]. We are very grateful to Ludovic Stephan and Yizhe Zhu for pointing out the key difference (personal correspondence).
The statement Pa (T = +1|H, Teg) - 1/ is equivalent to (T (To, Teg) + 0, i.e. Var, H, Toz) 1. By the monotonicity of conditional variance, we have Var(T, H, Tu, TaH;) S Var(T, H, Tw), where TaH, is the spin of vertex at generation / from the root p. It was shown that neighborhood H looks like broadcasting process on a multi-type Galton-Watson hypertree (see Theorem 5.2 in (25] for more strict claim). In order to close Conjecture/4.1 in addition to overcoming the barrier above, we need to show that т, and rp are asymptotically almost surely conditionally
independent given TaH, and H.
5 Conclusion
Community detection is of great interest in many fields such as network analysis, statistics and computer vision. Hypergraphs have been widely used to model higher-order relationships among data. The SBM (graph-based) model is popular in community detection but only directly models pair-wise interactions. Its hypergraph version, HSBM, likewise serves as benchmark for clustering algorithms on higher order interaction (hypergraph) data.
This paper provides some theoretical analysis on the community detection thresholds in the sparse HSBM. Specifically, motivated by a previous conjecture that there exists a sharp threshold on the model parameters for community detection, we proved that above the threshold, it is possible

---

to distinguish the hypergraph graph stochastic block model with a corresponding Erdös-Réns hypergraph model. Importandly we also provide consistent estimators for the model parameters. when the detection is possible.
Our estimators require the counting of the number of loose cycles in the hypergraph. To our best knowledge, there is no efficient algorithm to count the number of loose cycles in hypergraphs in general. Therefore, from the algorithmic side, might be more practical count the number of hawbbackkracking/slllavviiiiii walks of the same length [25 30], which can be computed by matrix multiplication efficiently. Moreover, providing more practical estimators (or examining whether one can estimate the number of loose cycles sufficiently accurate to still use the estimators of model parameters we provide), a worthy topic of future research.
Acknowledgments and Disclosure of Funding
The authors would like to express their gratitude to three anonymous referees for their helpful suggestions and comments. We are very grateful for some insightful comments from Ludovic Stephan and Yizhe Zhu. This work was partly supported by the Australian Research Council grants DP200103448 (D. Suter & E. Zhang).
References
[1] Emmanuel Abbe, Enric Boix-Adsera, Peter Ralli, and Colin Sandon. Graph powering and spectral robustness. SIAM Journal Mathematics of Data Science, 2(1):122-157,22 2020.
[2] Maria Chiara Angelini, Francesco Caltagirone, Florent Krzakala, and Lenka 7deborová. Spectral detection sparse hypergraphs. In 2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 66-73. IEFE, 2015.
[3] Pavel Bleher, Jean Ruiz, and Valentin Zagrebnov. On the purity of the limiting Gibbs state Ising model on the Bethe lattice. Journal of Statistical Physics, 79(1):433-45 482, 1995.
[4] Béla Bollobás. Random graphs. In Modern graph theory, pages 215-252. Springer, 1998.
[5] Bollobás, Svante Janson, and Oliver Riordan. The phase transition inhomogeneous random graphs.
Random Structures & Algorithms, (1(1)33-12, 2007.
[6] Charles Bordenave, Mare Lelarge, and Laurent Massoulié. Non- ba-bbbrktackinnggg spectrum of random graphs: community detection and non-regular Ramanujan graphs. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 1347-1357. IEEE, 2015.
[7] Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová. Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. Physical Review 84(6))066106, 2011.
Paul Erdös, Alfréd Rényi, al. On the evolution of random graphs. Publ. Math, Inst. Hung. Acad. Sci, 561);17-60, 1960.
[9] Ernesto Estrada Juan A Rodriguez-Velazquee, Complex networks as hypergraphs. arXiv preprint physics/0501137, 2005.
[10] William Evans, Claire Kenyon, Yuval Peres, and Lconard Schulman. Broadcasting on trees and the Ising model. Annals of Applied Probability, pages 410-433, 2000.
[11] Santo Fortunato. Community detection in graphs. Physics reports, 486(3-5):55-774, 2010.
[12] Alan Frieze and Michal Karoúski. Introduction to random graphs. Cambridge University Press, 2016.
[13] Debarghya Ghoshdastidar and Ambedkar Dukkipati. Consistency of spectral partitioning of uniform hypergraphs under planted partition model. Advances in Neural Information Processing Systems, 27, 2014.
[14] Debarghya Ghoshdastidar and Ambedkar Dukkipati. Consistency of spectral hypergraph partitioning under planted partition model. The Annals of Statistics, 45(1):289-315, 2017.
[15] Anna Goldenberg, Alice X Zheng. Stephen E Fienberg, Edoardo M Airoldi, et al. A survey of statistical network models. Foundations and Trends@ in Machine Learning, 2(2):129-25 2010.
10

---

[16] Christopher J Hillar and Lek-Heng Lim. Most tensor problems are NP-hard. Journal of the ACM (JACM). 60(6):1-39, 2013.
[17] Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels; First steps. Social networks, 5(2):109-13)) 1983.
[18] Harry Kesten and Bernt P Stigum. A limit theorem for multidimennsooall Malton-Watson processes. The Annals of Mathematical Statistics, 37(5):111-12223, 1966.
[19] Chihcon Kim, Afonso S Bandeira, and Michel X Goemans. Stochastic block model for hypergraphs: Statistical limits and semidefinite programming approach. arXiv preprint 1cXiv:1807.02884. 2018.
[20] Jure Leskovec, Kevin J Lang, Anirban Dasgupta, and Michael W Mahoney. Statistical properties of community structure in large social and information networks. In Proceedings of the 17th international conference on World Wide Web. pages 195-704,22 2008.
[21] Laurent Massoulié. Community detection thresholds and the weak Ramanujan property. In Proceedings of the forty-sixth annual ACM sympoxium on Theory of computing, pages 694-703, 2014.
[22] Elchanan Mossel, Joe Neeman, and Allan Sly. Reconstruction and estimation in the planted partition model. Probability Theory and Related Fields, 162(3)4431-45)) 2015.
[23] Elchanan Mossel, Joe Neeman, and Allan Sly. A proof of the block model threshold conjecture. Combina- torica, 38(3)6665-708 2018
[24] Xavier Ouvrard, Jean-Maric Le Goff, and Stéphane Marchand-Maillet. Networks of collaborations: Hypergraph modeling and visualisation. arXiv preprint arXiv:1707.00115. 2017.
[25] Soumik Pal and Yizhe Zhu. Community detection in the sparse hypergraph stochastic black model. Random Structures & Algorithms, 59(3)-407-463, 2021.
[26] Pulak Purkait, Tat-Jun Chin, Alireza Sadri, and David Suter. Clustering with hypergraphs: the case for large hyperedges. IEEE transactions on pattern analysis and machine intelligence, 3997)1197-1171, 2016.
[27] José J Ramasco, Sergey N Dorogovtsev, and Romualdo Sattor-Satoras... Self-organization collaboration networks. Physical review E, 70(3):036106, 2004.
[28] Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions on pattern analysis and machine intelligence, 2288)8888-905, 2000.
[29] Ludovic Stephan and Laurent Massoulié. Robustness of spectral methods for community detection. In Conference on Learning Theory, pages 2831-2860. PMLR, 2019.
[30] Ludovic Stephan and Yizhe 7hu. Sparse random hypergraphs: Non-backtracking spectra and community detection, arXiv preprint arXiv:2003.07346 2022.
[31] Ze Tian, TacHyun Hwang, and Rui Kuang. A hypergraph- based learning algorithm for classifying gene expression and arrayCGH data with prior knowledge. Bioinformatics, 25(21):2831 282312883,, 2009.
[32] Nicholas C Wormald et al. Models of random regular graphs. London Mathematical Society Lecture Note Series, pages 239-298, 1999.
[33] Mingao Yuan, Ruiqi Liu, Yang Feng, and Zuofeng Shang. Testing community structures for hypergraphs. arXiv preprint arXiv: 181000461, 2018.
[34] Mingao Yuan, Ruiqi Liu, Yang Feng, and Zuofeng Shang. Testing community structure for hypergraphs. The Annals of Statistics, 50((): 169, 2022.
[35] Yunpeng Zhao, Elizaveta Levina, and Ji Zhu, Community extraction for social networks. Proceedings of the National Academy of Sciences, 108(18 7):7211777 2011.
[36] Dengyong Zhou, Jiayuan Huang, and Bernhard Schölkopf. Learning with hypergraphs: Clustering, classification, and embedding. Advances in neural information processing systems, 19, 2006.

---

Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information how to answer these questions. For each question, change the default [TODO] to [Yes], [No], or [N/A] . You are strongly encouraged to include justification your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:
Did you include the license the code and datasets? [Yes] See Section 2.
Did you include the license to the code and datasets? [No] The code and the data are proprictary.
Did you include the license to the code and datasets? [N/A]
Please do modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] See the abstract and introduction.
(b) Did you describe the limitations of your work? [Yes] See the last two paragraphs of the conclusion section.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] We have read the ethics review guidelines.
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See the main results subsection.
(b) Did you include complete proofs of all theoretical results? [Yes] Some proofs are added in the Appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "zxrARex-4U2", "reviewer": "Reviewer_pS3F", "summary": "In this paper, the authors look at the problem of when it is possible to detect latent communities in a hypergraph stochastic block model. Previously the answer was known for SBM in graphs and a similar sharp threshold was conjectured for hypergraphs as well. The authors answer both the positive part and the negative part of the conjecture. The first part is answered by showing that the distribution of the number of loose cycles approach the Poisson distribution; in that case the detection problem can be resolved if certain conditions are met. On the other hand, if the conditions are not met, then by using a Galton-Watson style argument (similar to SBM), the prove the negative  part of the conjecture.", "questions": "1) In L75, approximate recovery is discussed. However, the problem that is solved is that of detection and not of recovery (even approximately). Here, I am a bit confused. Can you please explain?\n\n2) Is it not possible to show the proof of Theorem 1.1 in the finite samples regime as well? \n\n3) I believe that the writing in Section 3 can be improved significantly. It is not clear to me at all why the difficulty in solving the hypertree problem (spin of the root) translates to difficulty in solving the detection problem in hypergraph SBM? Can you please point me to the formal proof that rigorizes this argument? For now, I think the paper simply says that the neighborhood looks similar for a particular node but this is very hand-wavy.\n\n", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well-written and the results are very strong theoretically. The techniques are also quite interesting and I learned a lot from the paper.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "iVMLc9Zxab6", "reviewer": "Reviewer_DJ3N", "summary": "This paper considers community detection in the Hypergraph Stochastic Block Model (HSBM), an extension of the popular SBM for graphs. The paper is concerned with the detection problem; namely, when is it possible to distinguish the HSBM from its Erdos-Renyi counterpart? Prior work by Pal et al. proves a result in the positive direction; when the model parameters satisfy a certain inequality, then detection is possible. The paper gives an alternate proof of the same result by relating the community detection problem to the problem of broadcasting on hypertrees (in a similar vein to the work of Mossel et al. in the SBM). This paper also gives consistent estimates of the model parameters whenever detection is possible. Finally, the paper proves a negative result, completing the conjecture of Angelini et al. (2015).", "questions": "•\tPlease comment on whether your hypertree analysis techniques apply to any broadcasting/percolation problems outside the scope of your paper.\n\n•\tIt would be valuable to include a description of the technical challenges and how you overcame them.\n\n", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "•\tThe proof of the positive result seems to be much simpler than the existing result of Pal et al. Even though the result is not novel, this is a valuable contribution. Moreover, the consistent estimation results are novel. \n\n•\tThe negative result is significant because it confirms a conjecture, identifying the detection threshold.\n\n•\tThe positive result follows by analyzing the number of “loose cycles” in the HSBM and its Erdos-Renyi counterpart, showing that the loose cycle distributions differ.\n\n•\tThe negative result applies an existing result to prove contiguity of the two hypergraph distributions; the main effort is in verifying its conditions.\n\n•\tThere are pervasive writing issues; please proofread carefully! The writing issues are my main concern.\n\n•\tLemma 3.4 is hard to parse.\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "QQTTc376O3P", "reviewer": "Reviewer_e8Wi", "summary": "This paper studies the problem of community detection in hypergraph stochastic block models. The paper gives a proof of the detection threshold proposed by Angelini et al. [2].\n\nThe positive direction has previously been shown by Pal and Zhu [26], and this paper gives a new proof of the same result based on counting loose cycles in the hypergraph.\n\nThe negative direction was not previously known, and this paper generalises the proof of Mossel et al. [23] from graphs to hypergraphs.", "questions": "## Questions\nMy key question, to help judge the significance of this paper is: what are the key differences between the proof in this paper, and the one in [23]? What are the challenges in generalizing the result to hypergraphs, and how does this paper solve them?\n\n## Minor Comments\n* Line 13 - the first sentence is not grammatically correct. It could be \"Community detection, or clustering, *aims* ... population. *It* is a *fundamentally* important ...\"\n* Lines 14 + 26 - I think there should not be colons here. I suggest just starting a new sentence.\n* Line 28 typo: 'spectral' -> 'spectrum'\n* Line 30 typo: 'known as *the* planted...'\n* Line 37 typo: 'called *the* hypergraph...'\n* Line 43: the number of vertices in a hyperedge is usually called the 'rank' of the hyperedge, and 'degree' always refers to a vertex. For example, Line 77 is ambiguous, because this paper overloads the term 'degree'.\n* Lines 54-55: this is a little vague. Which computations on an adjacency tensor are NP-hard?\n* Line 72 typo: \"up a sign\" -> \"up to a sign\"\n* Line 97 - \"see Theorem 1.1\" should be in parentheses\n* Figure 1 - I believe the caption is the wrong way round. Detection is impossible **above** the dashed curves, and possible **below** the dashed curves.\n* Line 186 - it is not immediately clear what the 'children' of a hyperedge are. Does this refer to the vertices in the hyperedge?\n* Line 189, and throughout the paper. It is quite difficult to follow inline math with many fractions and subscripts. I would recommend re-formatting to avoid inline fractions (like this $\\frac{1}{2}$ ), either by rewritting as $1/2$ or using a full equation environment for more complex expressions.\n* Line 209 typo: *and* also equivalent to\n* Line 210 typo: 'variation' -> 'variance'\n* Line 211-215: this is quite difficult to follow\n* Line 216: what does it mean that \"$V_2$ separates $V_1$ and $V_3$\"?\n* Line 222: there is a large gap after \"a.a.s.\" - you can fix this by using \"a.a.s.\\ \" in Latex.\n* Line 231: brackets are not large enough to surround their contents. You can use \"\\left(\" and \"\\right)\" in latex. Though also see my earlier comment on inline math.\n* Between lines 231 and 232 - the notation on this line is a bit confusing.\n", "limitations": "The authors have addressed the limitations of their work.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n* This paper studies an interesting problem which is of interest to the community.\n* The presented result is new, and the proof appears to be sound.\n\n## Weaknesses\n* This paper is quite difficult to follow. It is very mathematically dense and would benefit from some additional explanation and discussion. There are also some careless errors - for example the caption of Figure 1 (see the detailed comments).\n* The proof follows the proof for the graph case (Mossel et al. [23]) very closely. It is not clear how the proof differs. It would be helpful to include more discussion of the key ideas which are needed to generalise the proof to hypergraphs. This would help to determine the significance of the result.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept