1

Community Recovery in Hypergraphs
Kwangjun Ahn∗ , Kangwook Lee∗ , and Changho Suh

arXiv:1709.03670v1 [] 12 Sep 2017

Abstract
Community recovery is a central problem that arises in a wide variety of applications such as network clustering, motion
segmentation, face clustering and protein complex detection. The objective of the problem is to cluster data points into distinct
communities based on a set of measurements, each of which is associated with the values of a certain number of data points.
While most of the prior works focus on a setting in which the number of data points involved in a measurement is two, this work
explores a generalized setting in which the number can be more than two. Motivated by applications particularly in machine
learning and channel coding, we consider two types of measurements: (1) homogeneity measurement which indicates whether or
not the associated data points belong to the same community; (2) parity measurement which denotes the modulo-2 sum of the
values of the data points. Such measurements are possibly corrupted by Bernoulli noise. We characterize the fundamental limits
on the number of measurements required to reconstruct the communities for the considered models.

I. I NTRODUCTION
Clustering of data is one of the central problems, and it arises in many fields of science and engineering. Among many
related problems, community recovery in graphs has received considerable attention with applications in numerous domains
such as social networks [3]–[5], computational biology [6], and machine learning [7], [8]. The goal of the problem is to
cluster data points into different communities based on pairwise information. Among a variety of models for the community
recovery problem, the stochastic block model (SBM) [9] and the censored block model (CBM) [10] have received significant
attention in recent years. In SBM, two data points in the same communities are more likely to be connected by an edge than
the other edges. In the case of CBM, each measurement returns the modulo-2 sum of the values assigned to the two nodes,
possibly corrupted by Bernoulli noise.
While these models reflect interactions between a pair of two nodes, there are numerous applications in which interactions
occur across more than two nodes. One such application is a folksonomy, a social network in which users can annotate items
with different tags [11]. In this application, the graph consists of nodes corresponding to different users, different items, and
different tags. When user i annotate item j with tag k, one can view this as a hyperedge connecting node i, node j and node
k. Therefore, in order to cluster nodes of such a graph based on such interactions, one needs a model that can capture such
three-way interactions. Another application is molecular biology, in which multi-way interactions between distinct systems
capture complex molecular interactions [12]. There are also a broad range of applications in other domains including computer
vision [13], VLSI circuits [14], and categorical databases [15].
These applications naturally motivate us to investigate a hypergraph setting in which measurements are of multi-way
information type. Specifically, we consider a simple yet practically-relevant model, which we name the generalized censored
block model (GCBM). In the GCBM, the n data points are modeled as nodes in a hypergraph, and their interactions are encoded
as hyperedges between the nodes. As an initial effort, we focus on a simple setting in which there are two communities: each
node taking either 0 or 1 depending on its affiliation. More concretely, we consider a random d-uniform hypergraph in which
each hyperedge connecting a set of d nodes exists with probability p and takes a function of the values assigned to the d
nodes. In this work, inspired by applications in machine learning and channel coding, we study the following two types of
measurements:
• the homogeneity measurement that reveals whether or not the d nodes are in the same community; and
• the parity measurement that reveals the modulo-2 sum of the affiliation of the d nodes.
Further, we study both the noiseless case and the noisy case.
A. Main contributions
Specialized to the d = 2 case, the above two measurement models reduce to the CBM,in which the information-theoretic
n
limit on the expected number of edges required for exact recovery is characterized as p n2 = 12 · √ n log √
2 [16], [17]. On
( 1−θ− θ)
the other hand, the information-theoretic limits for the case of arbitrary d has not been settled. This precisely sets the goal
of our paper: We seek to characterize the information-theoretic limits on the sample complexity for exact recovery under the
two models. A summary of our findings is as follows. For a fixed constant d, the information-theoretic limits are:
Kwangjun Ahn is with the Department of Mathematical Sciences, KAIST (e-mail: kjahnkorea@kaist.ac.kr). Kangwook Lee and Changho Suh are with the
School of Electrical Engineering, KAIST (e-mail: {kw1jjang, chsuh}@kaist.ac.kr).
This paper was presented in part at the 54th Annual Allerton Conference on Communication, Control, and Computing 2016 [1], and the IEEE International
Symposium on Information Theory 2017 [2].
∗ Kwangjun Ahn and Kangwook Lee contributed equally to this work

2


TABLE I: Summary of main results. The information-theoretic limits on sample complexity (p nd ) are summarized. Here, n denotes the
number of nodes, θ denotes the noise probability, and d denotes the size of hyperedges. “d = f (n)” means that d can scale with n, and
“Θθ,d ” implies that the constant involved depends on θ and d.
d=2
Homogeneity

1
2

Parity

1
2

·
·

n log n
√
√
( 1−θ− θ)2
n log n
√
√
( 1−θ− θ)2

d > 2 (const.)
2d−2
d
1
d

·

n
· √ n log √
( 1−θ− θ)2
n log n
√
√
( 1−θ− θ)2

d = f (n)

Θθ,d



N/A
n
max n,

n log n
d

o


d−2
n
(the homogeneity measurement case) p nd = 2 d · √ n log √
2 if d is a fixed constant; and
1−θ− θ )
(

n log n
n
1
√ 2 if d is a fixed constant.
• (the parity measurement case) p d = d · √
( 1−θ− θ)
For the parity measurement case, we also characterize the information-theoretic limits for a more general setting where d can
arbitrarily scale with n.



n log n
n
• (the parity measurement case) p d = Θ
if d = o(log n); and
d

n
• (the parity measurement case) p d = Θ(n) if d = Ω(log n).
These results provide some interesting implications to relevant applications such as subspace clustering and channel coding.
In particular, the results offer concrete guidelines as to how to choose d that minimizes sample complexity while ensuring
successful clustering. See details in Sec. II-A and Sec. III.
•

B. Related work
1) The d = 2 case: The exact recovery problem in standard graphs (d = 2) has been studied in great generality. In SBM, both
the fundamental limits and computationally efficient algorithms are investigated initially for the case of two communities [17]–
[19], and recently for the case of an arbitrary number of communities [20]. In CBM, [16] characterizes the sample complexity
limit, and [17] develops a computationally efficient algorithm that achieves the limit.
Another important recovery requirement is detection, which asks whether one can recover the clusters better than a random
guess. The modern study of the detection problem in SBM is initiated by a paper by Decelle et al. [21], which conjectures
phase transition phenomena for the detection problem1 . This conjecture is initially tackled for the case of two communities.
The impossibility of the detection below the conjectured threshold is established in [27], and it is proved in [28]–[30] that the
conjectured threshold can be achieved efficiently. The conjecture for the arbitrary number of communities is recently settled
by Abbe and Sandon [26]. For another line of researches, minimax-optimal rates are derived in [31], and algorithms that
achieve the rates are developed in [32]. We refer to a recent survey by Abbe [33] for more exhaustive information.
2) The homogeneity measurement case: Recently, [34], [35] consider a general model that includes our model as a special
case (to be detailed in Sec. II), and provide an upper bound on sample complexity for almost exact recovery, which allows a
vanishing fraction of misclassified nodes. Applying their results to our model, their upper bound reduces to p nd = Ω(n log2 n).
Whether or not the sufficient condition is also necessary has been unknown. In this work, we show that it is not the case,
demonstrating that the minimal sample complexity even for exact recovery is Θ(n log n).
We note that the homogeneity measurement case is closely related to subspace clustering, one of the popular problems in
computer vision [13], [36], [37]; See Sec. II-A1 for details.
3) The parity measurement case: The parity measurement case has been explored by [38] in the context of random constraint
satisfaction
problems. The case of d = 3 has been well-studied: it is shown that the maximum likelihood decoder succeeds

n log n
if p n3 ≥ 2 · (0.5−θ)
2 [38]. Unlike the prior result which only considers the case of d = 3, we cover an arbitrary constant d,
and characterize the sharp threshold on the sample complexity.
Abbe-Montanari [10] relate the parity measurement model to a channel coding problem in which random LDGM codes
with a constant right-degree d are employed. By proving the concentration phenomenon of the mutual information between
channel input and output, they demonstrate the existence of phase transition for an even d. Our results span any fixed d, and
hence fully settle the phase transition (see Sec. III).
4) The stochastic block model for hypergraphs: There are several works which study the community recovery under SBM
for hypergraphs. In [39], the authors explore the case of two equal-sized communities2 . Specializing it to our model, one can
readily show that detection is possible if nd p = Ω(n). Moreover, [40] recently conjectures phase transition thresholds for
detection. Lastly, [41] derives the minimax-optimal error rates, and generalizes the results in [31] to the hypergraph case.
1 In the paper, it is also conjectured that an information-computation gap might exist for the case of more than 3 communites (k ≥ 4). This conjecture
is also extensively studied in [22]–[25], and is recently settled in [26].
2 Actually, the main model in the paper is the bipartite stochastic block model, which is not a hypergraph model. However, the result for the hypergraph
case follows as a corollary (see Theorem 5 therein).

3

5) Other relevant problems: Community recovery in hypergraphs bears similarities to other inference problems, in which the
goal is to reconstruct data from multiple queries. Those problems include crowdsourced clustering [42], [43], group testing [44]
and data exactration from histogram-type information [45], [46]. Here, one can make a connection to our problem by viewing
each query as a hyperedge measurement. However, a distinction lies in the way that queries are collected. For instance, an
adaptive measurement model is considered in the crowdsourced setting [42], [43] unlike our non-adaptive setting in which
hyperedges are sampled uniformly at random. Histogram-type information acts as a query in [44]–[46].
C. Paper organization
Sec. II introduces the considered model; in Sec. III, our main results are presented along with some implications; in
Sec. IV, V and VI, we provide the proofs of the main theorems; Sec. VII presents experimental results that corroborate our
theoretical findings and discuss interesting aspects in view of applications; and in Sec. VIII, we conclude the paper with some
future research directions.
D. Notations
For any two sequences f (n) and g(n): f (n) = Ω(g(n)) if there exists a positive constant c such that f (n) ≥ cg(n);
(n)
= ∞;
f (n) = O(g(n)) if there exists a positive constant c such that f (n) ≤ cg(n); f (n) = ω(g(n)) if limn→∞ fg(n)
(n)
f (n) = o(g(n)) if limn→∞ fg(n)
= 0; and f (n)  g(n) or f (n) = Θ(g(n)) if there exist positive constants c1 and c2 such
that c1 g(n) ≤ f (n) ≤ c2 g(n).

A
For a set A and an integer m ≤ |A|, we denote m
:= {B ⊂ A : |B| = m}. Let [n] denote {1, · · · , n}. Let ei be the ith
standard unit vector. Let 0 be the all-zero-vector and 1 be the all-one-vector. We use I{·} to denote an indicator function. Let
DKL (pkq) be the Kullback-Leibler (KL) divergence between Bern(p) and Bern(q), i.e., DKL (pkq) := p log pq + (1 − p) log 1−p
1−q .
We shall use log(·) to indicate the natural logarithm. We use H(·) to denote the binary entropy function.

II. G ENERALIZED CENSORED BLOCK MODELS
Consider a collection of n nodes V = [n], each represented by a binary variable Xi ∈ {0, 1}, 1 ≤ i ≤ n. Let X :=
{Xi }1≤i≤n be the ground-truth vector. Let d denote the size of a hyperedge. Samples are obtained as per a measurement
[n]
hypergraph H = (V, E) where E ⊂ [n]
belongs to E independently with probability
d . We assume that each element in
d
p ∈ [0, 1]. Sample complexity
is
defined
as
the
number
of
hyperedges
in
a
random
measurement hypergraph, which is

concentrated around p nd in the limit of n. Each sampled edge E ∈ E is associated with a noisy binary measurement YE :
YE = f (Xi1 , Xi2 , · · · , Xid ) ⊕ ZE ,

(1)
i.i.d.

where f : {0, 1}d → {0, 1} is some binary-valued function, ⊕ denotes modulo-2 sum, and ZE ∼ Bern(θ) is a random
variable with noise rate 0 ≤ θ < 21 . For the choice of f , we focus on the two cases:
• the homogeneity measurement:
fh (Xi1 , Xi2 , · · · , Xid ) = I{Xi1 = Xi2 = · · · = Xid };
•

the parity measurement:
fp (Xi1 , Xi2 , · · · , Xid ) = Xi1 ⊕ Xi2 ⊕ · · · ⊕ Xid .

Let Y := {YE }E∈E . We remark that when d = 2, this reduces to CBM [16].
The goal of this problem is to recover X from Y. In this work, we will focus on the case of even d since the case of odd
d readily follows from the even case [1]. When d is even, the conditional distribution of Y|X is equal to that of Y|X ⊕ 1.
Hence, given a recovery scheme ψ, the probability of error is defined as
Pe (ψ) :=

max

X∈{0,1}n

Pr (ψ(Y) ∈
/ {X, X ⊕ 1}) .

We intend to characterize the minimum sample complexity, above which there exists a recovery algorithm ψ such that
Pe (ψ) → 0 as n tends to infinity, and under which Pe (ψ) 9 0 for all algorithms.
A. Relevant applications
1) Subspace clustering and the homogeneity measurement: Subspace clustering is a popular problem of which the task is
to cluster n data points that approximately lie in a union of lower-dimensional affine spaces. The problem arises in a variety
of applications such as motion segmentation [47] and face clustering [48], where data points corresponding to the same class
(tracked points on a moving object or faces of a person) lie on a single lower-dimensional subspace; for details, see [49] and
references therein. A common procedure of the existing algorithms for subspace clustering [37], [50]–[52] begins construction
of a d-th order affinity tensor (d ≥ 2) whose entries represent similarities between every d data points. Since this construction
incurs a complexity that scales like nd , sampling-based approaches are proposed in [13], [36], [37].

4

1 (similar)
0 (dissimilar)

Fig. 1: Connection to subspace clustering. Subspace clustering is illustrated for a simple scenario in which the entire signal space is two-dimensional
and data points are approximately lying on a union of two 1-dimensional affine spaces (lines). A common procedure in the existing algorithms includes
construction of a d-th order affinity tensor (d ≥ 2) each entry of which represents a quantity that captures a level of similarity across d data points, so taking
either 0 or 1 depending on the similarity level. For instance, the four points involved in E1 in the figure lie near the same affine space, so the similarity
measure is decided as 1; on the other hand, the four points in E2 span different affine spaces, so the similarity measure is decided as 0. Since each data
point does not exactly lie in a subspace, an error can occur in the decision—the similarity measurement can be noisy. Hence one can view this problem as
the GCBM under the homogeneity measurement model.

Fig. 2: Connection to channel coding. GCBM with the parity information can be seen as a channel coding problem which employs random LDGM codes
with a constant right-degree d. To see this, we first draw a random d-uniform hypergraph with n nodes, where each edge of size d appears with probability
p. Given the input sequence of n information bits, the parity bits corresponding to all the sampled hyperedges are concatenated, forming a codeword. The
noisy measurement can be mapped to the output of a binary symmetric channel (BSC) with crossover probability θ, when fed by the codeword. A recovery
algorithm ψ corresponds to the decoder which wishes to infer the n information bits from the received signals. One can then see that recovering communities
in hypergraphs is equivalent to the above channel coding problem.

A similarity between d data points in prior works [13], [36], [37] is defined such that it tends to 1 if all of the d points are
on the same subspace and 0 otherwise. Hence, restricted to the two-subspace case, one can view a similarity over a d-tuple
E as a homogeneity measurement 3 . By setting the probability of each entry being sampled as p, one can relate this to our
homogeneity measurement model; see Fig. 1 for visual illustration.
2) Channel coding and the parity measurement: The community recovery problem has an inherent connection with channel
coding problems [16], [18]. To see this, consider a communication setting which employs random LDGM codes with a constant
right-degree d. To make a connection, we begin by constructing a random d-uniform hypergraph with n nodes, where each
edge of size d appears with probability p. Given the input sequence of n information
 bits, we then concatenate the parity bits
with respect to the sampled hyperedges to form a codeword of average length p nd . Note that the expected code rate is p nn .
(d)
The noisy measurement can be mapped to the output of a binary symmetric channel (BSC) with crossover probability θ, when
fed by the codeword. A recovery algorithm ψ corresponds to the decoder which wishes to infer the n information bits from
the received signals. One can then see that recovering communities in hypergraphs is equivalent to the above channel coding
problem; see Fig. 2 for visual illustration.
3 In subspace clustering, similarities can be sometimes noisy in that even though the d data points are from the same (different) subspace, similarity can
be 0 (1). Note that ZE in (1) precisely captures this noise.

5

III. M AIN RESULTS
A. The homogeneity measurement case
Theorem 1. Fix d ≥ 2 and  > 0. Under the homogeneity measurement case (f = fh ),


n
inf ψ Pe (ψ) → 0 if n p ≥ (1 + ) 2d−2 √ n log √
d ( 1−θ− θ)2 ;
d

d−2
n
inf ψ Pe (ψ) 6→ 0 if nd p ≤ (1 − ) 2 d √ n log √
.
( 1−θ− θ)2
Proof: See Sec. IV.
We first make a comparison to the result in [34]. While [34] models a fairly general similarity measurement, it considers a
more relaxed performance metric, so called almost exact recovery, which allows a vanishing fraction of misclassified nodes;
and provides a sufficient condition on sample complexity under the setting [53]. On the other hand, we identify the sufficient
and necessary condition for exact recovery, thereby characterizing the fundamental limit. Specializing their result to the model
of our interest, the sufficient condition in [34] reads Ω(n log2 n), which comes with an extra log n factor gap to the optimality.
d−2
One interesting observation in Theorem 1 is that the sample complexity limit is proportional to 2 d . This suggests that
d
bits. To understand why this is the
the amount of information that one hyperedge reveals on average is approximately 2d−2
case, consider a setting in which θ = 0 and an hyperedge E = {i1 , i2 , · · · , id } is observed. The case of YE = 1 implies
Xi1 = Xi2 = · · · = Xid , in which there are only two uncertain cases (all zeros and all ones), i.e., the d − 1 bits of information
are revealed. On the other hand, the case of YE = 0 provides much less information as it rules out only two possible cases
(Xi1 = Xi2 = · · · = Xid = 0 and Xi1 = Xi2 = · · · = Xid = 1) out of 2d possible candidates. This amounts to roughly d · 22d
1
bits. Since YE = 1 occurs with probability
 d 2d−1d, the amount of information that one hyperedge can carry on average should
1
1
read about 2d−1 (d − 1) + 1 − 2d−1 2d−1 ≈ 2d−2 .
Relying on the connection to subspace clustering elaborated in Sec. II-A, one can make an interesting implication from
Theorem 1. The result offers a detailed guideline as to how to choose d for sample-efficient subspace clustering. In the case
where the measurement quality reflected in θ is irrelevant of the number d of data points involved in a measurement, the limit
increases in d. In practical applications, however, θ may depend on d. Actually, the quality of similarity measure can improve
as more data points get involved, making θ decrease as d increases. In this case, choosing d as small as possible minimizes
2d−2
but may make θ too large. Hence, there might be a sweet spot on d that minimizes the sample complexity. It turns out
d
this is indeed the case in practice. Actually we identify such optimal d∗ for motion segmentation application; see Sec. VII-A
for details.
B. The parity measurement case
Theorem 2. Fix d ≥ 2 and  > 0. Under the parity measurement case (f = fp ),

(
n log √
n
;
inf ψ Pe (ψ) → 0 if nd p ≥ (1 + ) d1 (√1−θ−
θ)2

n
n
1 √ n log √
inf ψ Pe (ψ) 6→ 0 if d p ≤ (1 + ) d ( 1−θ− θ)2 .
Proof: See Sec.V.
Notice that for a fixed θ and n, the minimum sample complexity is proportional to d1 , hence decreases in d unlike the
homogeneity measurement case.
In view of the connection made in Sec. II-A, a natural question that arises in the context of channel coding is to ask how
far the rate of the random LDGM code is from the capacity of the BSC channel. The connection can help immediately answer
the question. We see from Theorem 2 that the rate of the LDGM code is
√
√
d( 1 − θ − θ)2
n

=
.
log n
p nd
This suggests that the code rate increases in d. Note that as long as d is constant, the rate vanishes, being far from the capacity
of BSC channel 1 − H(θ). On the other hand, it is not clear as to whether or not the random LDGM code can achieve a
non-vanishing code rate possibly by increasing the value of d. To check this, we explore the case where d can scale with n.
By symmetry, it suffices to consider the case 2 ≤ d ≤ n/2. Moreover, to avoid pathological cases where d fluctuates as n
increases, we assume that d is a monotone function.
Theorem 3. Fix d, a monotone function of n such that 2 ≤ d ≤ n/2, and  > 0. Under the parity measurement case (f = fp ),
• (upper bound) inf ψ Pe (ψ) → 0 if
 
n
5/2
n log n
√
p ≥ (1 + )
and
(2)
√
d
d ( 1 − θ − θ)2
 
n
n
√
p ≥ (1 + )5 log 2 √
;
(3)
d
( 1 − θ − θ)2

6

•

(lower bound) inf ψ Pe (ψ) 6→ 0 if
 
n
1
n log n
√
or
p ≤ (1 − ) √
d
d ( 1 − θ − θ)2
 
n
n
p≤
.
d
1 − H(θ)

(4)
(5)

Proof: See Sec. VI.
To see what these results mean, consider the two cases: d = Ω(log n) and d = o(log n). In the case d = Ω(log n), the
theorem says that for a fixed θ,
 
n
inf Pe (ψ) → 0 if
p > β1 n and
ψ
d
 
n
inf Pe (ψ) 6→ 0 if
p < β2 n ,
ψ
d
o
n
n
o
5/2 log n
5 log √
2
log n
1
√
√
√
√

1
and
β
=
max
where β1 = max (√1−θ−
,
,
 1. This suggests that as long
2
2
2
2
θ) d ( 1−θ− θ)
( 1−θ− θ) d 1−H(θ)
as d grows asymptotically larger than log n, we can achieve an order-wise tight sample complexity that is linear in n. On the
other hand, in the case d = o(log n), the theorem asserts that
 
n
5/2
n log n
√
and
inf Pe (ψ) → 0 if
p>
√
ψ
d
d ( 1 − θ − θ)2
 
n
1
n log n
√
.
inf Pe (ψ) 6→ 0 if
p<
√
ψ
d
d ( 1 − θ − θ)2
This implies that one cannot achieve the linear-order sample complexity if d grows slower than log n. The implication of the
above two can be formally stated as follows.
Corollary 1. For d = o(log n), reliable recovery is impossible with linear-order sample complexity, while it is possible for
d = Ω(log n).
From this, we see that the random LDGM code can achieve a constant rate as soon as d = Ω(log n).
IV. P ROOF OF T HEOREM 1
The achievability and converse proofs are streamlined with the help of Lemmas 1 and 2, of which the proofs are left
in Appendix A. For illustrative purpose, we focus on the noisy case (θ > 0) and assume that n is even. For a vector
V := {Vi }1≤i≤n ∈ {0, 1}n , we define


f{i1 ,i2 ,··· ,id } (V) := f (Vi1 , Vi2 , · · · , Vid );
(6)
F(V)
:= {fE (V)}E∈E ;


dH (V)
:= kY − F(V)k1 .
Let ψML be the maximum likelihood (ML) decoder. One can easily verify that
ψML (Y) = arg

min

V∈{0,1}n

dH (V),

where ties are randomly broken.
A. Achievability proof
We intend to prove that
max

X∈{0,1}n

Pr(ψML (Y) ∈
/ {X, X ⊕ 1}) → 0

under the claimed condition. Let A ∈ {0, 1}n be the ground-truth vector. Without loss of generality, assume that the first k
coordinates are 0’s and the next n − k coordinates are 1’s, where 0 ≤ k ≤ n/2.
Let Ai,j denote the collection of all vectors whose coordinates are different from that of A in i many positions among the
first k coordinates and in j many positions among the next n − k coordinates. Note that A0,0 = {A} and Ak,n−k = {A ⊕ 1}.
Thus, a decoding algorithm ψ is successful if and only if the output ψ(Y) ∈ A0,0 ∪ Ak,n−k . Let I := {(i, j) : (i, j) ∈
/
{(0, 0), (k, n − k)}, 0 ≤ i ≤ k, and 0 ≤ j ≤ n − k}. We also define
Vi,j := (1, · · · , 1, 0, · · · , 0, 0, · · · , 0, 1, · · · , 1) ,
| {z }
| {z }
i
j
|
{z
} |
{z
}
k

n−k

7

which is a representative vector of Ai,j .
Using these notations and the union bound, we get:
Pr(ψML (Y) ∈
/ {X, X ⊕ 1} | X = A)


[
[
(a)
[dH (V) ≤ dH (A)]
≤ Pr 
(i,j)∈I V∈Ai,j

X

X

(i,j)∈I

V∈Ai,j

≤

Pr (dH (V) ≤ dH (A))

X k n − k 
=
Pr (dH (Vi,j ) ≤ dH (A)) ,
i
j

(7)

(i,j)∈I

where the step (a) follows from the fact that the ML decoder outputs V ∈
/ {A, A ⊕ 1} if dH (V) ≤ dH (A).
To compare dH (Vi,j ) with dH (A), we define the set of distinctive hyperedges, i.e., the set of hyperedges such that fE (A) 6=
fE (Vi,j ):

 

[n]
Fi,j := E ∈
: fE (A) 6= fE (Vi,j )
(8)
d
and Ei,j := E ∩Fi,j . By definition, for E ∈ Ei,j , YE = fE (A) if ZE = 0; YE = fE (Vi,j ) otherwise. Hence, dH (Vi,j ) ≤ dH (A)
P
|E |
if and only if E∈Ei,j ZE ≥ i,j
2 . This leads to:
Pr (dH (Vi,j ) ≤ dH (A))
|Fi,j |

X

=

Pr (dH (Vi,j ) ≤ dH (A) | |Ei,j | = `) Pr(|Ei,j | = `)

(9)

`=1



|Fi,j |

=

X

Pr 

E∈Ei,j

`=1
(a)

≤


X

`
ZE ≥
2

|Fi,j |

X

e

−`D(0.5kθ)

`=1



|Ei,j | = ` ·



|Fi,j | `
p (1 − p)|Fi,j |−`
`


|Fi,j | `
p (1 − p)|Fi,j |−`
`

= (1 − (1 − e−D(0.5kθ) )p)|Fi,j | ,

(10)

where (a) is due to Chernoff-Hoeffding [54]. By letting p0 := (1 − e−D(0.5kθ) )p and applying this to (7), we get:
Pr(ψML (Y) ∈
/ {X, X ⊕ 1} | X = A)
X k n − k 
≤
(1 − p0 )|Fi,j | .
i
j

(11)

(i,j)∈I

To give a tight upper bound on (11), one needs a tight lower bound on the size of the set of distinctive hyperedges, i.e.,
|Fi,j |. It turns out that bounding |Fi,j | when d > 2 requires non-trivial combinatorial counting. Note that this was not the
case when d = 2 since |Fi,j | can be exactly computed via simple counting. Indeed, one of our main technical contributions
lies in the derivation of tight bounds on |Fi,j |, which we detail below.
Fact 1. The number of distinctive hyperedges can be calculated as follows:
 X
 X
 X


d−1  
d−1  
d−1  
d−1 
X
i
k−i
j
n−k−j
i
n−k−j
k−i
j
|Fi,j | =
+
+
+
.
` d−`
`
d−`
`
d−`
`
d−`
`=1

`=1

`=1

(12)

`=1

Proof: Consider a hyperedge E = {i1 , i2 , · · · , id } such that fE (A) = 1. That is, the hyperedge is connected only
to a subset of the first k nodes or only to a subset of the last n − k nodes. That is, {i1 , i2 , · · · , id } ⊂ {1, 2, · · · , k} or
{i1 , i2 , · · · , id } ⊂ {k + 1, k + 2, · · · , n}. Consider the first case, i.e., {i1 , i2 , · · · , id } ⊂ {1, 2, · · · , k}. In order for this
hyperedge to be distinctive, i.e., fE (Vi,j ) = 0, at least one element of E must be in {1, 2, · · · , i}, and
at least one element
Pd−1  k−i
of E must be in {i + 1, · · · , k}. Thus, the total number of such distinctive hyperedges is `=1 `i d−`
. Similarly, one

Pd−1 
can count the number of distinctive hyperedges for the case {i1 , i2 , · · · , id } ⊂ {k + 1, k + 2, · · · , n}: `=1 j` n−k−j
d−` . By
considering the opposite case where fE (A) = 0 and fE (Vi,j ) = 1, one can also obtain the remaining two terms, proving the
statement.

8

By symmetry, we see that |Fi,j | = |Fk−i,n−k−j |. Hence,
X k n − k 
(1 − p0 )|Fi,j |
i
j
(i,j)∈I
 

 

X
X
k
n−k
k
n−k
(1 − p0 )|Fi,j | +
(1 − p0 )|Fi,j |
≤
i
j
i
j
(i,j)∈I, j≥d n−k
(i,j)∈I, j≤b n−k
2 c
2 e
 




X
X
k
n−k
k
n−k
0 |Fi,j |
=
(1 − p )
(1 − p0 )|Fk−i,n−k−j |
+
i
j
k
−
i
n
−
k
−
j
(i,j)∈I, j≤b n−k
(i,j)∈I, j≤b n−k
2 c
2 c
 

X
k
n−k
(1 − p0 )|Fi,j | =: 2V.
=2
i
j
n−k
(i,j)∈I, j≤b

2

(13)
(14)

(15)

(16)

c


In order to bound V , for a fixed constant δ > 0, we define
the following index sets: Ibig := {(i, j) ∈ I : j ≤

∩ ([i < δn] ∩ [j < δn])}. Then,
([i ≥ δn] ∪ [j ≥ δn])} and Ismall := {(i, j) ∈ I : j ≤ n−k
2
 

X
k
n−k
V =
(1 − p0 )|Fi,j |
i
j
(i,j)∈Ibig ∪Ibig
X k n − k 
=
(1 − p0 )|Fi,j |
i
j
(i,j)∈Ibig
X k n − k 
+
(1 − p0 )|Fi,j | .
i
j

n−k
2



∩

(17)
(18)
(19)

(i,j)∈Ismall

Let us first consider (18). Without loss of generality, assume i ≥ δn. Then it follows from (12) that


d−1  
d−1  
X
i
n − k − j (a) X i
n/4
|Fi,j | ≥
≥
`
d−`
` d−`
`=1
`=1





i
n/4
n/4
≥
≥ δn
= Ω(nd ),
1 d−1
d−1
where (a) follows from the hypothesis that j ≤ n−k
and k ≤ n2 . Then it is easy to show that (18)→ 0:
2
X k n − k 
0
d
e−p Ω(n )
(18) ≤
j
i
(i,j)∈I
 

k
n−k
(a) −Ω(n log n) X
= e
≤ e−Ω(n log n) 2n → 0,
i
j
(i,j)∈I


where (a) follows from the fact that p0 Ω(nd )  p nd = Ω(n log n).
Now we consider (19). The following lemma gives a tight lower bound on |Fi,j | for this case:
Lemma 1. For i < δn and j < δn,



(1 − 2δ)d−1 n − 1
|Fi,j | ≥ (i + j) ·
.
2d−2
d−1

Proof: See Sec. A-A.
Applying Lemma 1 to (19), we get:
X

(19) =

(i,j)∈Ismall
(a)

≤

 

k
n−k
(1 − p0 )|Fi,j |
i
j
0

ni nj e−p (i+j)·

X

(1−2δ)d−1
2d−2

(n−1
d−1 )

(i,j)∈Ismall

(
=

X
(i,j)∈Ismall

exp (i + j) log n −

p0 (1 − 2δ)d−1
2d−2

 )!

n−1
d−1

,

(20)

9



where (a) follows due to ki ≤ ni , n−k
≤ nj and Lemma 1. A straightforward computation yields (1 − e−DKL (0.5kθ) ) =
j
√
√
( 1 − θ − θ)2 , so the claimed condition
 
n
2d−2
n log n
√
p ≥ (1 + )
√
d
d ( 1 − θ − θ)2
becomes
 
n 0
2d−2
n log n .
p ≥ (1 + )
d
d

(21)

Under the claimed condition, we get:
p0 (1 − 2δ)d−1

n−1
d−1



2d−2

p0 (1 − 2δ)d−1
=
2d−2

n d
d n



(a)

≥ (1 + )(1 − 2δ)d−1 log n

(b)

≥ (1 + /2) log n,
where (a) follows from (21); (b) follows by choosing δ sufficiently small ((1 − 2δ)d−1 → 0 as δ → 0). Thus, (20) converges
to 0 as n tends to infinity. This completes the proof.
B. Converse proof
Let V1/2 be the collection of n-dimensional vectors, each consisting of n/2 number of 0’s and n/2 number of 1’s. Moreover,
let X1/2 be the random vector sampled uniformly at random over V1/2 . For any scheme ψ, by definition of Pe (ψ), we see
that

Pr ψ(Y) ∈
/ {X, X ⊕ 1} | X = X1/2 ≤ Pe (ψ)
and hence

inf Pr ψ(Y) ∈
/ {X, X ⊕ 1} | X = X1/2 ≤ inf Pe (ψ).
ψ

ψ

Relying on this inequality, our proof strategy is to show that the left hand side is strictly bounded away from 0. Note that the
infimum in the left hand side is achieved by ψML,1/2 :
ψML,1/2 (Y) = arg min dH (V) .
V∈V1/2

By letting A = (0, · · · , 0, 1, · · · , 1), we obtain
| {z } | {z }
n/2

n/2

Pr ψML,1/2 (Y) ∈
/ {X, X ⊕ 1} | X = X1/2

= Pr ψML,1/2 (Y) ∈
/ {A, A ⊕ 1} | X = A .



Let S be the success event:
S :=

\

[dH (V) > dH (A)] .

V∈V1/2 \{A,A⊕1}


One can show that Pr ψML,1/2 (Y) ∈
/ {A, A ⊕ 1} | X = A ≥
more than two candidates for arg minV∈V1/2 dH (V), so

1
3

Pr(S c ). This is due to the fact that given S c , there are

 1
Pr ψML,1/2 (Y) ∈
/ {A, A ⊕ 1} | X = A, S c ≥ .
3
Hence, it suffices to show Pr(S) → 0. To give a tight upper bound on Pr(S), we construct a subset of nodes such that any two
nodes in the subset do not share the same hyperedge. To this end, we use the deletion technique (alteration technique) [55].
We first choose a big subset
o
[ nn
n
n
Rbig = {1, 2, · · · , r}
+ 1, + 2, · · · , + r ,
2
2
2
n
where r = d log7 n e; then erase every node in Rbig which shares hyperedges with other nodes in Rbig to obtain Rres . The
following lemma guarantees that Rres has a comparable size as that of Rbig with high probability. For the later usage, we
allow d to scale with n.

10


Lemma 2. Suppose nd p = O(n log n) and d = O(log n). Let Rbig be a subset of [n] and Rres be a subset obtained from
Rbig by deleting every node which shares hyperedges with other nodes in Rbig . If |Rbig | = O(n/ log7 n), then with probability
approaching 1,
|Rres | = (1 − o(1))|Rbig | .
Proof: See Sec. A-B.

Let ∆ be the event that |Rres | ≥ (1−o(1))|Rbig |. Given the event ∆, both {1, 2, · · · , n/2}∩Rres and n2 + 1, n2 + 2, · · · , n ∩
Rres contain more than r/2 elements. We collect r/2 elements from each of these sets and denote by {b1 , b2 , · · · , br/2 } and
{c1 , c2 , · · · , cr/2 }, respectively. Suppose that there exist (k, `) such that dH (A ⊕ ebk ) ≤ dH (A) and dH (A ⊕ ec` ) ≤ dH (A).
Conditioning on ∆, there are no hyperedges that contain both bk and c` , so dH (A ⊕ ebk ⊕ ec` ) ≤ dH (A). Hence conditioning
on ∆,
r/2

\

S⊂

[dH (A ⊕ ebk ) > dH (A)]

k=1
0

[ r/2
\

[dH (A ⊕ eck ) > dH (A)]

k=1

=: S .
Since the event ∆ occurs with probability approaching 1 and S ⊂ S 0 , Pr(S) ' Pr(S | ∆) ≤ Pr(S 0 | ∆). Hence,
Pr(S) . Pr (S 0 | ∆)

r/2
\
≤ 2 Pr 
[dH (A ⊕ ebk ) > dH (A)]


∆

k=1
(a)

= 2 Pr dH (A ⊕ eb1 ) > dH (A)

∆

r/2

,

where (a) follows from the fact that the events {[dH (A⊕ebk ) > dH (A)]}1≤k≤r/2 are mutually independent conditioned on ∆.

Let p0 = (1−e−DKL (0.5kθ) )p as in the achievability proof. We intend to give an upper bound on Pr dH (A ⊕ eb1 ) > dH (A) ∆ ,
i.e., a lower bound on Pr dH (A ⊕ eb1 ) ≤ dH (A) ∆ . Recall from the proof of achievability (see (10)) that

For the case of Vi,j

Pr (dH (Vi,j ) ≤ dH (A)) ≤ (1 − (1 − e−DKL (0.5kθ) )p)|Fi,j | .


n/2
= A ⊕ eb1 , |Fi,j | = n/2−1
+ d−1
(note that k = n/2, i = 1, j = 0). So we get:
d−1
0

Pr (dH (A ⊕ eb1 ) ≤ dH (A)) ≤ e−p ((

n/2−1
d−1

n/2
)+(d−1
)) .

(22)

On the other hand, what we need for the converse proof is a lower bound. In what follows, we will show that (22) is tight
enough, more precisely,

0 n/2−1
Pr dH (A ⊕ eb1 ) ≤ dH (A) ∆ ≥ (1 − o(1))e−2p ( d−1 ) .
(23)
What this means at a high level is that Chernoff-Hoeffding is tight enough. Let us condition on the event ∆ for the time
being. As in (8), we define the following sets:

 

[n]
Fb1 := E ∈
: fE (A) 6= fE (A ⊕ eb1 )
d
and Eb1 := E ∩ Fb1 . By definition, for E ∈ Eb1 , YE = fE (A) if ZE = 0; YE = fE (A ⊕ eb1 ) otherwise. We see that
X
|Eb1 |
dH (A ⊕ eb1 ) ≤ dH (A) ⇔
ZE ≥
.
2
E∈Eb1

Now we want to manipulate Pr dH (A ⊕ eb1 ) ≤ dH (A) ∆ as we did in (9). However, here we need to give a careful
attention to the range of summation as Eb1 cannot be equal to Fb1 due to the following reason. Since we conditioned on ∆,
no hyperedge in Eb1 intersects Rbig at more than one node (indeed, b1 is the only node where they intersect); in other words,
Eb1 is always contained in a proper subset of Fb1 :

 

[n]
Eb1 ⊂ Fb1 \ E ∈
: |E ∩ Rbig | ≥ 2 =: Gb1 .
(24)
d
Now a manipulation similar to (9) yields:
Pr (dH (A ⊕ eb1 ) ≤ dH (A) | ∆)
|Gb1 |

=

X
`=1

Pr dH (A ⊕ eb1 ) ≤ dH (A)


|Eb1 | = `, ∆ Pr(|Eb1 | = `|∆).

11

Since the event ∆ is related to the occurrence of edges in

 

[n]
E∈
: |E ∩ Rbig | ≥ 2
d
and Eb1 is subject to (24), ∆ and [|Eb1 | = `] are independent. Thus, we get:
Pr (dH (A ⊕ eb1 ) ≤ dH (A) | ∆)
|Gb1 |

=

X

Pr dH (A ⊕ eb1 ) ≤ dH (A)

`=1
|Gb1 |

=

X
`=1


Pr 


|Eb1 | = `, ∆ Pr(|Eb1 | = `)


X

ZE ≥

E∈Eb1



|Gb1 |
p`
`
|Eb1 | = `
.
`
2
(1 − p)`−|Gb1 |

(25)

By the reverse Chernoff-Hoeffding bound [54], for a fixed δ > 0, there exists nδ > 0 such that


X
`
Pr 
ZE ≥ |Eb1 | = ` ≥ e−(1+δ)`DKL (0.5kθ)
2
E∈Eb1

for all ` ≥ nδ . Let gn be a sequence (to be determined) such that gn → ∞ as n → ∞. For sufficiently large n,
|Gb1 | 


|Gb1 | (e−(1+δ)DKL (0.5kθ) p)`
(25) ≥
`
(1 − p)`−|Gb1 |
`=1

gX
n −1 
|Gb1 | (e−(1+δ)DKL (0.5kθ) p)`
−
.
`
(1 − p)`−|Gb1 |
`=1
X

Actually one can choose gn so that (27) is negligible compared to (26). To see this, we consider:
`
Pgn −1 
−(1+δ)DKL (0.5kθ)
(1 − p)|Gb1 | `=1
|Gb1 | pe
1−p
(27)
≤
P|Gb1 | |Gb |  pe−(1+δ)DKL (0.5kθ) `
(26)
1
(1 − p)|Gb1 | `=1
1−p
`

`
Pgn −1
−(1+δ)DKL (0.5kθ)
|Gb1 | pe
`=1
1−p
= 
|Gb1 |
−(1+δ)DKL (0.5kθ)
1 + pe
1−p
`
Pgn −1 
pe−(1+δ)DKL (0.5kθ)
|G
|
b
1
`=1
1−p
(a)


=
pe−(1+δ)DKL (0.5kθ)
(1 + o(1)) exp |Gb1 |
1−p
Pgn −1 `
`=1 q
=:
,
(1 + o(1))eq

(26)

(27)

(28)

where (a) follows from the fact that limx→0+ 1+x
following definition: q :=
ex = 1, and the last equation is due to the


pe−(1+δ)DKL (0.5kθ)
n/2−1
n/2
n/2−1−r
|Gb1 |
. One can easily verify that |Fb1 | = d−1 + d−1 and |Gb1 | =
+ n/2−r
d−1 . Since r = o(n),
1−p
d−1
limn→∞ |Gb1 |/|Fb1 | → 1. Thus,
pe−(1+δ)DKL (0.5kθ)
1−p
−(1+δ)DKL (0.5kθ)
pe
 |Fb1 |
 nd−1 p = Ω(log n) .
1−p

q = |Gb1 |

Therefore, if one chooses gn = blog qc,
Pgn −1 `
2
q
(27)
gn q gn
log q · q log q
log q · e(log q)
= `=1q
≤
≤
=
→ 0,
(26)
e
eq
eq
eq
and thus (27) = o(1) · (26).

(29)
(30)

12

Hence, we get:
(25) = (26) − (27)
|Gb1 | 


|Gb1 | (e−(1+δ)DKL (0.5kθ) p)`
`
(1 − p)`−|Gb1 |
`=1

|Gb1 |
= (1 − o(1)) 1 − (1 − e−(1+δ)DKL (0.5kθ) )p
n/2

2(d−1
(a)
)
≥ (1 − o(1)) 1 − (1 − e−(1+δ)DKL (0.5kθ) )p
 


n/2
(b)
= (1 − o(1)) exp −2
(1 − e−(1+δ)DKL (0.5kθ) )p ,
d−1

n/2
where (a) follows since |Gb1 | ≤ |Fb1 | ≤ 2 d−1
; (b) follows from the fact that limx→0+ 1+x
ex = 1. As δ > 0 can be chosen
−(1+δ)DKL (0.5kθ)
arbitrarily small, the term e
can be made arbitrarily close to e−DKL (0.5kθ) , which in turn ensures that the last
term is essentially equal to
0 n/2
(1 − o(1))e−2p (d−1) .
X

≥ (1 − o(1))

Applying this to the previous upper bound on Pr(S), we get:
r/2
Pr(S) ≤ Pr dH (A ⊕ eb1 ) > dH (A) ∆

r/2
0 n/2
≤ 1 − (1 − o(1))e−2p (d−1)


0 n/2
r
≤ exp −(1 − o(1)) e−2p (d−1)
2
!
n
p0 d( )
n
−(1+o(1))· d−2d
2
n
= exp −(1 − o(1))
e
,
2 log7 n
where the last equality follows from the fact that



n/2
2p0 d−1
n

lim
→ 1 and r =
.
n→∞ p0 d n /2d−2 n
log7 n
d
d−2

The last term converges to 0 as p0 ≤ (1 − ) 2 d

n log n

(nd)

.

V. P ROOF OF T HEOREM 2
In this section, we prove a similar statement for the parity measurement case.
A. Achievability proof
Note that the parity measurement is symmetric in a sense that for any two vector A and B, Pr (ψML (Y) ∈
/ {X, X ⊕ 1} | X = A) =
Pr (ψML (Y) ∈
/ {X, X ⊕ 1} | X = B). Hence, we will prove that
Pr (ψML (Y) ∈
/ {X, X ⊕ 1} | X = 0) → 0

13

under the claimed condition. Conditioning on X = 0,
Pr (ψML (Y) ∈
/ {0, 1})


[
≤ Pr 
[dH (A) ≤ dH (0)]
A6=0,1





n−1
[

[

= Pr 

[dH (A) ≤ dH (0)]

k=1 kAk1 =k
n−1
X

≤

X

Pr (dH (A) ≤ dH (0))

k=1 kAk1 =k
(a)

= 2·

n/2
X
X

Pr (dH (A) ≤ dH (0))

k=1 kAk1 =k
(b)

= 2·

n/2  
X
n
k=1

k

Pr dH

k
X

!
ei

!
≤ dH (0) ,

(31)

i=1

where (a) follows
P form
 the fact that Pr (dH (A) ≤ dH (0)) = Pr (dH (A ⊕ 1) ≤ dH (0)); (b) follows due to symmetry. To
k
compare dH
e
i=1 i and dH (0), we define
(
!)
 
k
X
[n]
Fk := E ∈
: fE (0) 6= fE
ei
d
i=1
and Ek := E ∩ Fk . As in (10), we obtain
Pr dH

k
X

!
ei

!
≤ dH (0)

≤ (1 − (1 − e−DKL (0.5kθ) )p)|Fk |

i=1

= (1 − p0 )|Fk | ,
yielding
n/2  
X
n
1
· (31) ≤
(1 − p0 )|Fk | .
2
k

(32)

k=1

We again count |Fk | in an effort to obtain a tight upper bound on (32). Notice that E ∈ Fk if |E ∩ [k]| is odd, and hence
X k  n − k 
|Fk | =
·
.
(33)
i
d−i
i≤d
i is odd

Let δ > 0 be a small constant that will be determined later. For the case k ≥ δn, it follows that
 



k
n−k
n/2
|Fk | ≥
≥ δn
= Ω(nd ) .
1
d−1
d−1
Then it is easy to show (32)→ 0 for this case:
n/2  
n/2  
X
X
n
n −p0 Ω(nd )
(1 − p0 )|Fk | ≤
e
k
k
k=δn
k=δn
n/2  
n
(a) −Ω(n log n) X
= e
≤ e−Ω(n log n) 2n → 0 ,
k
k=δn

n
0
d
where (a) follows from the fact that p Ω(n )  p d = Ω(n log n). For the case k < δn, we see that
 



k
n−k
(1 − δ)n
|Fk | ≥
≥k
1
d−1
d−1


n−1
(a)
= (1 + o(1))k(1 − δ)d−1
,
n→∞
d−1

(34)

14

where (a) follows since
lim

n−1
d−1

αn
d−1

αd−1

n→∞


=1

(35)

holds for a fixed d and α ∈ (0, 1). Hence, we get
δn  
δn
X
X
n
0
d−1
n
(1 − p0 )|Fk | ≤
nk e−(1+o(1))p k(1−δ) (d−1)
k
k=1
δn
X

=

k=1
0

ek·{log n−(1+o(1))p (1−δ)

d−1

n
(d−1
)} .

(36)

k=1

By choosing δ arbitrarily small, under the claimed condition, one can make


 
n
d
0
d−1
d−1 n
p (1 − δ)
= (1 + o(1))(1 − δ)
p0
n
d−1
d
≥ (1 + /2) log n ,
which implies that (36) converges to 0 as n tends to infinity.
B. Converse proof
As the parity measurement is symmetric,
inf Pe (ψ) = Pr (ψML (Y) ∈
/ {X, X ⊕ 1} | X = 0) .
ψ

As before, we define the success event as:
S :=

\

[dH (V) > dH (0)] .

(37)

V6=0,1

Again, it suffices to show that Pr(S) → 0, and to this end, we construct a subset of nodes such that any two nodes in the
subset do not share the same hyperedge. Unlike the previous case, the subset is now defined as:
Rbig := {1, 2, · · · , r}

(38)

d logn7 n e,

where r =
and we erase every node in Rbig which shares hyperedges with other nodes in Rbig to obtain Rres . In
view of Lemma 2, we have |Rres | ≥ (1 − o(1))r almost surely; let ∆ be such event. Conditioning on ∆, we enumerate r/2
many elements of Rres by b1 , · · · , br/2 . As there are no hyperedges that connect two nodes in Rres , the events {[dH (ebk ) >
dH (0)]}1≤k≤r/2 are mutually independent conditioned on ∆. Hence, we get:
Pr(S) . Pr (S | ∆)

r/2
\
≤ Pr 
[dH (ebk ) > dH (0)]


∆

k=1

= Pr dH (eb1 ) > dH (0)

∆

r/2

.

Let p0 = (1 − e−DKL (0.5kθ) )p as before. Using similar arguments used in the previous section, we have

0 n−1
Pr dH (eb1 ) ≤ dH (0) ∆ ≥ (1 − o(1))e−p ( d−1 ) .
This gives:
r/2
Pr dH (eb1 ) > dH (0) ∆

r/2
0 n−1
≤ 1 − (1 − o(1))e−p ( d−1 )




n−1
r
≤ exp −(1 − o(1)) exp −p0
2
d−1
(
 )!
p0 nd d
n
≤ exp −(1 − o(1))
exp −(1 + o(1)) ·
.
n
2 log7 n

n
, which completes the proof.
Notice that the last term converges to 0 as nd p0 ≤ (1 − ) n log
d

(39)

(40)

15

VI. P ROOF OF T HEOREM 3
When d scales with n, a technical challenge arises, and we will focus on such technical difficulties, skipping most of the
redundant parts.
A. Proof of the upper bound
From (32) and (33), we get
Pe (ψML ) ≤

n/2  
X
n
k=1

k

(1 − p0 )Nk ,

(41)

where
Nk :=

X k  n − k 
·
i
d−i

(42)

1≤i≤d
i is odd

√
√

d
and p0 := ( 1 − θ − θ)2 p. Let us focus on counting Nk . When d  1, nd ≈ nd! suffices to obtain a proper bound on Nk .
However, in the general case where d scales with n, one needs a more delicate bounding technique to obtain sharp results.
The following lemma presents our new bound.
n−d+1
Lemma 3. Let β := d n−d+1
. Then
2d+1 e < n/2 and α :=
d
(

2k n
X k n − k 
d ,

≥ 5α
1 n
i
d−i
5 d ,
1≤i≤d
i is odd

k < β;
β ≤ k ≤ n/2 .

Proof: See Sec. VI-C. The proof requires an involved combinatorial counting, which is one of our main technical
contributions.
Employing Lemma 3, we get:
n/2  
β−1
X n
X
n
0 Nk
(41) ≤
(1 − p ) +
(1 − p0 )Nk
k
k
k=1

≤

k=1

≤

k=β

β−1
X

β−1
X
k=1
β−1
X

n/2  
X
1 n
2k n
n
n
(1 − p0 ) 5 ( d )
(1 − p0 ) 5α ( d ) +
k
k



k=β

nk e−p

0 2k
5α

(nd) + 2n e− 15 p0 (nd)

(

 !)
2p0 nd
≤
exp k log n −
5α
k=1

 
1
n
+ exp n log 2 − p0
.
5
d

(43)
(44)

Note that (44) vanishes due to (3). In order to show that (43) vanishes as well, we consider two cases: d = o(n) and d  n.
When d = o(n),
(
 !)
β−1
X
2p0 nd
exp k log n −
5α
k=1
(
 !)
β−1
X
2dp0 nd
≤
exp k log n −
5n
k=1


0 n
2dp ( )
exp log n − 5n d

 → 0,
≤
2dp0 (n)
1 − exp log n − 5n d
since log n −

2dp0 (n
d)
5n

→ −∞.

16

If d  n,
β−1
X
k=1

(

2p0 nd
exp k log n −
5α

 !)

(

2p0 nd
≤ β max exp k log n −
1≤k≤β−1
5α

 !)

2p0 nd
= β exp log n −
5α

!
,

2p0 (n)
where the last equality holds since log n − 5αd < 0, and hence k = 1 achieves the maximum value. Note that this vanishes
since β is asymptotically bounded by a constant. Therefore, (43) always vanishes, completing the proof.

B. Proof of the lower bound



n log √
n
n
.
The lower bound statement can be rewritten as follows: inf ψ Pe (ψ) 6→ 0 if nd p ≤ max (1 − ) d1 (√1−θ−
,
θ)2 1−H(θ)

n
n
Note that when d = ω(log n), the condition reduces to d p ≤ 1−H(θ) . Hence, it is sufficient to show the following two
statements.



n log √
n
n
1
n
.
• If d = O(log n): inf ψ Pe (ψ) 6→ 0 if d p ≤ max (1 − ) d √
,
( 1−θ− θ)2 1−H(θ)

n
n
• If d = ω(log n): inf ψ Pe (ψ) 6→ 0 if d p ≤ 1−H(θ) .


n
n
implies inf ψ Pe (ψ) 6→ 0 for all d. By rearranging terms, we have nd p ≤ 1−H(θ)
⇔
We first show that nd p ≤ 1−H(θ)
n
n
≥
1
−
H(θ).
One
can
immediately
observe
that
this
implies
inf
P
(ψ)
→
6
0
since
(which
can
be
viewed
as
the
ψ
e
n
n
( d )p
( d )p
rate of a code) cannot exceed
the
Shannon
capacity
of
the
channel
1
−
H(θ).

n log √
n
implies inf ψ Pe (ψ) 6→ 0 if d = O(log n). Further, we will focus on the
We now prove that nd p ≤ (1 − ) d1 (√1−θ−
θ)2

n log n
n
case of d p  d since this is the regime where the largest amount of information is available. Again, it is enough to
show that Pr(S) → 0, where S is defined as (37). By defining Rbig , Rres , ∆ and b1 , · · · , br/2 as before, we again obtain (39):
r/2
Pr(S) ≤ Pr dH (eb1 ) > dH (0) ∆
.
(45)
We finish the proof by showing the following for the considered case:

0 n−1
Pr dH (eb1 ) ≤ dH (0) ∆ ≥ (1 − o(1))e−2p ( d−1 ) .
While following the proof of (23),
the key technical difficulty arises when checking q = Ω(log
(see

 n)n−1
 (30)): a simple
n−|Rbig |
big |
calculation yields |Fb1 | = n−1
, but here it is not clear whether n−|R
 d−1 when d is not a
d−1 and |Gb1 | =
d−1
d−1
constant. We resolve this using a careful estimation as follows. As |Rbig | = Θ( logn7 n ) and d = O(log n), it is straightforward
to verify
1−

n − |Rbig | − j
1
≤
n−1−j
log2 n

for 0 ≤ j ≤ d − 2. This simple yet crucial inequality concludes:
 d−2
n−|Rbig |
Y n − |Rbig | − j
d−1
 =
n−1
n−1−j
d−1
j=0

d−1


1
d−1
≥ 1−
≈
exp
−
→ 1.
log2 n
log2 n
C. Proof of Lemma 3
Without loss of generality, we prove the lemma assuming that k ≥ d. The proof for the other cases is similar.
We wish to obtain lower bounds on
 
 


X k n − k  k n − k 
X
k
n−k
k
n−k
Nk =
=
+
+
i
d−i
1
d−1
i
d−i
d−1
1
1≤i≤d
,d−3,d−1
|
{z
} i=1,3,···
{z
}
|
{z
} |
i is odd

in terms of

boundary odd term

intermediate odd terms

(46)

boundary odd term


n

. First, observe that
 
  
 

X k n − k  k n − k 
X
k
n−k
n
k
n−k
=
=
+
+
.
d
i
d−i
0
d
i
d−i
d
0
0≤i≤d
i=1,2,···
,d−2,d−1
{z
} |
{z
}
|
{z
} |

d

boundary term

intermediate terms

boundary term

(47)

17

Suppose we have the following bounds:
 
 


 
  

k
n−k
k
n−k
k
n−k
k
n−k
≤ A1
+
;
+
1
d−1
d−1
1
0
d
d
0
{z
}
|
{z
}
|
sum of boundary terms
sum of boundary odd terms
 

 

X
X
k
n−k
k
n−k
≤ A2 ·
+A3 Nk ,
i
d−i
i
d−i
i=1,3,··· ,d−3,d−1
i=1,2,··· ,d−2,d−1
{z
}
|
{z
}
|
intermediate terms

(48)

(49)

intermediate odd terms

for some quantities A1 , A2 , A3 > 0. Then, by summing up the two inequalities, one can obtain a lower bound on Nk :
 
n
≤ (max(A1 , A2 ) + A3 ) Nk .
(50)
d
Thus, the proof is completed as long as one can find the quantities A1 , A2 and A3 that satisfy (48) and (49).
We begin with (49). The following lemma asserts that A2 = 2 and A3 = 3 satisfy (49).
Lemma 4. For 1 ≤ k ≤ n/2,
X
i=1,2,··· ,d−2,d−1

 

k
n−k
≤2·
i
d−i

X
i=1,3,··· ,d−3,d−1

 

k
n−k
+ 3Nk .
i
d−i

Proof: See Sec. A-C.
For (49), the following lemma characterizes A1 .
l
m
Lemma 5. Let β := n−d+1
2d+1 . For β ≤ k ≤ n/2,
 
  

 
 


k
n−k
k
n−k
k
n−k
k
n−k
+
≤2
+
.
0
d
d
0
1
d−1
d−1
1

(51)

For k < β,
 
 


 
  

k
n−k
k
n−k
k
n−k
k
n−k
α
+
+
≤
k
1
d−1
d−1
1
0
d
d
0

(52)

α
≥ 2,
k

(53)

and

where α =

n−d+1
.
d

Proof: See Sec. A-D.
That is, A1 = 2 if β ≤ k ≤ n/2, and A1 = αk if k < β.
We now are ready to prove Lemma 3 with the help of Lemma 4, Lemma, 5 and (50). When β ≤ k < n/2,
 
n
≤ 5Nk .
d
When k < β,

where the last inequality holds since

  

 α
5α
n
+ 3 Nk ≤
Nk ,
≤ max 2,
k
2k
d
α
k

≥ 2. This completes the proof.
VII. E XPERIMENTAL RESULTS

A. The homogeneity measurement case
1) Efficient algorithms: We also develop a computationally-efficient algorithm that achieves the information-theoretic limit
characterized in Theorem 1. Here we only present the algorithm while deferring a detailed analysis to our companion paper [56].
The algorithm operates in two stages, beginning with a decent initial estimate from Hypergraph Spectral Clustering [56]
followed by iterative refinement. Detailed procedures are presented in Algorithm 1. Our algorithm is inspired by two-stage
approaches that have been applied to a wide variety of problems including matrix completion [57], [58], phase retrieval [59],
[60], robust PCA [61], community recovery [18], [20], [32], [62], [63], EM-algorithm [64], and rank aggregation [65].

18

Algorithm 1
1:

For E ∈

[n]
d



, define
(
YE
WE :=
0,

if E ∈ E;
otherwise.
(0)

Apply Spectral Hypergraph Clustering [56] to a weighted hypergraph ([n], {WE }E∈([n]) ) to obtain X(0) = {Xi }1≤i≤n ∈
d
{0, 1}n .
(t)
3: For t = 0, 1, · · · , T − 1 (T = c log n for some constant c > 0), update X(t) = {Xi }1≤i≤n as per
(
(t)
Xi
if dH (X(t) ) < dH (X(t) ⊕ ei );
(t+1)
Xi
=
(t)
Xi ⊕ 1 if dH (X(t) ) ≥ dH (X(t) ⊕ ei ),
2:

for i = 1, 2, · · · , n, where dH (·) is defined in (6).
(T )
Output X(T ) = {Xi }1≤i≤n .
1

1

0.9

0.9

0.8

0.8

Probability of success

Probability of success

4:

0.7
0.6
0.5
0.4
=0.01
=0.05
=0.10
=0.20

0.3
0.2
0.1

0.7
0.6
0.5
0.4
d =3
d =4
d =5
d =6

0.3
0.2
0.1

0

0
0

0.5

1

1.5

Normalized sample complexity

(a) Varying θ

2

0

0.5

1

1.5

2

Normalized sample complexity

(b) Varying d

Fig. 3: Algorithm 1 achieves the optimal sample complexity. We run Monte Carlo simulations to estimate the probability of success when: (a) n = 1000,
d = 4, and for various choices of θ; (b) n = 1000, θ = 0.05, and for various choices of d. For each curve, we normalize the number of samples by the
respective information theoretic limits, characterized in Theorem 1. Observe that the probability of success quickly approaches 1 as the normalized sample
complexity crosses 1.

2) Performance of Algorithm 1: We demonstrate the performance of Algorithm 1 by running Monte Carlo simulations.
Each point plotted in Fig. 3a and Fig. 3b indicates an empirical success rate. We take 100 Monte Carlo trials. Fig. 3a shows
the probability of success when n = 1000, d = 4, and for various choices of θ. Shown in Fig. 3b is the performance of our
algorithm with n = 1000, θ = 0.05, and for various choices of d. For both figures, the x-axis denotes the number of samples
normalized by the respective information-theoretic limits, characterized in Theorem 1. One can observe that the success
probability due to Algorithm 1 quickly approaches 1 as the normalized sample complexity crosses 1, which corroborates our
theoretical findings.
3) Optimal d for subspace clustering: We observe how the fundamental limit varies as a function of d. As we briefly
discussed in Sec. III, if the noise rate θ is irrelevant to d, the optimal choice of d would be the minimum possible value of
d. However, if the noise quality θ depends on d, there may be a sweet spot for d.
We demonstrate the existence of a sweet spot in one of subspace clustering applications: motion segmentation. We use
the benchmark Hopkins 155 [66] dataset to compute an empirical noise rate θ as a function d as follows. For each sampled
hyperedge E = {i1 , · · · , id }, we adopt the method proposed in [37] to evaluate similarity between the corresponding d data
points that we denote by D. Then, we set YE = 1 if and only if D is less than a fixed threshold, which is appropriately
chosen so that Pr(YE = 0 | i1 , i2 , · · · , id are from the same line) ≈ Pr(YE = 1 | i1 , i2 , · · · , id are not from the same line).
We estimate the effective noise rate θ̂ := Pr(YE = 0 | i1 , i2 , · · · , id are from the same line) for various d, and observe that
θ̂ quickly decreases as d increases; see Fig. 4a. We then plug these θ̂’s to the limit characterized in Theorem 1; see Fig. 4b.
Note that d = 5 is not the optimal choice, but d = 6 is the sweet spot.
We also corroborate the existence of a sweet spot in a synthetic data set for subspace clustering, shown in Fig. 5a. Here the
goal is to cluster n (= 200) 2-dimensional data points approximately lying on a union of two lines (1-dimensional subspaces).

19

10 4

The information-theoretic limit

Estimated noise rate

0.3

0.2

0.1

0

2

1.5

1
5

10

15

20

5

6

Degree (d)

7

8

Degree (d)

(b) d∗

(a) Estimated empirical noise rate θ̂

Fig. 4: Existence of d∗ in motion segmentation. (a) We estimate the empirical noise rate θ̂ as a function of d in motion segmentation. (b) We plug θ̂ to
the limit characterized in Theorem 1 and verify that d∗ = 6.

10

1

Probability of success

0.9

5
0
-5
cluster 1
cluster2

-10

0.8
0.7
0.6
0.5
0.4
0.2
0.1
0
1000

-10

-5

0

5

(a) Randomly generated data set

d=3
d=4
d=5
d=6

0.3

10

2000

3000

4000

5000

6000

Normalized sample complexity

(b) Varying d

Fig. 5: Optimal choice of d when θ decays with d. We run Monte Carlo simulations to estimate the probability of success with the data set shown in
(a). We observe that the effective noise rate decreases as d increases. For varying d from 3 to 6, the success probability of Algorithm 1 is shown in (b): the
best performance of the algorithm is observed when d = 4.

We compute YE as above and evaluate the performance of Algorithm 1, shown in Fig. 5b. As a result, we observe that the
optimal choice of d here is 4 rather than 3.
B. The parity measurement case
1) Efficient algorithms: For the parity measurement case, there are two efficient algorithms in the literature [38], [67].
In [38], it is shown
that for d = 3, a variant of message passing algorithm successfully recovers the ground-truth vector

provided that n3 p = Ω(n2 / log n). Another efficient algorithm is based ona low-rank tensor factorization algorithm proposed
in [67], and it is proved that reliable community recovery is feasible if n3 p = Ω(n1.5 log4 n). In either of the two cases, the
sufficient condition comes with a polynomial term (n or n1/2 ) to the fundamental limit characterized in Theorem 1. In fact,
it is conjectured in [39] (see Conjecture 1 therein) that at least n1.5 many samples are required for exact recovery.
On the other hand, focusing on the θ = 0 case, recovering the ground-truth vector from the measurement vector Y is
essentially the same as solving linear equations over the Galois field of two elements F2 . Hence it immediately follows that
efficient algorithms for solving linear equations such as Gaussian elimination can be employed in the noiseless case.
2) Information-theoretic limit: We first provide Monte Carlo simulation results which corroborate our theoretical findings
in Theorem 2. Each point plotted in Fig. 6 and Fig. 7 is an empirical success rate. All results are obtained with 50 Monte
Carlo trials. In Fig. 6, we plot the probability of successful recovery for n = 1000, varying d, and θ = 0. For each d, we
normalize the number of samples by max(n, n log n/d). One can observe that the probability of success quickly approaches

20

1

Probability of success

0.8

0.6

0.4
d=4
d=7
d = 11

0.2

0
0

0.5
1
1.5
Normalized sample complexity

2

Fig. 6: We run the Monte Carlo simulations to estimate the probability of success for n = 1000, varying d, and θ = 0. For each d, we normalize the
number of samples by max(n, n log n/d). Observe that the probability of success quickly approaches 1 as the normalized sample complexity crosses 1.
1
0.9
Probability of success

0.8
0.7
0.6
0.5
0.4
0.3

n = 50
n = 200
n = 800
n = 3200

0.2
0.1
0
2

4

6
Degree (d)

8

10

Fig. 7: We run the Monte Carlo simulations to estimate the probability of success for varying n, varying d, θ = 0, and p = 1.1n/
increases by a multiplicative factor of 4, the curve shifts rightward about the same amount, supporting our result in Corollary 1

n
.
d

Note that when n

1 as the normalized sample complexity crosses 1.
3) Minimum d for linear sample complexity: Plotted in Fig. 7 are the simulation results for varying n, varying d, θ = 0,
and p = 1.1n/ nd . We note that when n increases by a multiplicative factor of 4, the curve shifts rightward about the same
amount, supporting our result in Corollary 1.
VIII. C ONCLUSION
In this paper, we investigate the problem of community recovery in hypergraphs under the two generalized censored block
models (GCBM), one based on the homogeneity measurement and the other based on the parity measurement. For these two
models, we fully characterize the information-theoretic limits on sample complexity as a function of the number of nodes n,
the size of edges d, the noise rate θ, and the edge observation probability p. We also corroborate our theoretical findings via
experiments.
We conclude our paper by highlighting a few interesting open problems. One interesting question is whether or not
one can sharpen Theorem 3 to characterize exact information-theoretic limits for the scaling d case. From the simulation
results in
n Sec. VII-B, we make othe following conjecture: Under the setting of Theorem 3, the information-theoretic limits
n log √
n
n
, d1 (√1−θ−
. Another interesting open problem is about the computational gap for the parity measureis max 1−H(θ)
θ)2
ment case: Investigating efficient algorithms for this case would shed some light on the study of information-computation
gaps.
R EFERENCES
[1] K. Ahn, K. Lee, and C. Suh, “Community recovery in hypergraphs,” Allerton Conference on Communication, Control and Computing, 2016.
[2] ——, “Information-theoretic limits of subspace clustering,” in IEEE International Symposium on Information Theory (ISIT), Aachen, Germany, Jun.
2017, pp. 2473–2477.

21

[3] M. Girvan and M. E. Newman, “Community structure in social and biological networks,” Proceedings of the National Academy of Sciences, vol. 99,
no. 12, pp. 7821–7826, 2002.
[4] S. Fortunato, “Community detection in graphs,” Physics reports, vol. 486, no. 3, pp. 75–174, 2010.
[5] M. A. Porter, J.-P. Onnela, and P. J. Mucha, “Communities in networks,” Notices of the AMS, vol. 56, no. 9, pp. 1082–1097, 2009.
[6] J. Chen and B. Yuan, “Detecting functional modules in the yeast protein–protein interaction network,” Bioinformatics, vol. 22, no. 18, pp. 2283–2290,
2006.
[7] Q.-X. Huang and L. Guibas, “Consistent shape maps via semidefinite programming,” in Computer Graphics Forum, vol. 32, no. 5. Wiley Online
Library, 2013, pp. 177–186.
[8] J. Shi and J. Malik, “Normalized cuts and image segmentation,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 22, no. 8, pp.
888–905, 2000.
[9] P. W. Holland, K. B. Laskey, and S. Leinhardt, “Stochastic blockmodels: First steps,” Social networks, vol. 5, no. 2, pp. 109–137, 1983.
[10] E. Abbe and A. Montanari, “Conditional random fields, planted constraint satisfaction and entropy concentration,” in Approximation, Randomization,
and Combinatorial Optimization. Algorithms and Techniques. Springer, 2013, pp. 332–346.
[11] G. Ghoshal, V. Zlatić, G. Caldarelli, and M. Newman, “Random hypergraphs and their applications,” Physical Review E, vol. 79, no. 6, p. 066118,
2009.
[12] T. Michoel and B. Nachtergaele, “Alignment and integration of complex networks by hypergraph-based spectral clustering,” Physical Review E, vol. 86,
no. 5, p. 056111, 2012.
[13] S. Agarwal, K. Branson, and S. Belongie, “Higher order learning with graphs,” in ICML. ACM, 2006, pp. 17–24.
[14] G. Karypis and V. Kumar, “Multilevel k-way hypergraph partitioning,” VLSI design, vol. 11, no. 3, pp. 285–300, 2000.
[15] D. Gibson, J. Kleinberg, and P. Raghavan, “Clustering categorical data: An approach based on dynamical systems,” Databases, vol. 1, p. 75, 1998.
[16] E. Abbe, A. S. Bandeira, A. Bracher, and A. Singer, “Decoding binary node labels from censored edge measurements: Phase transition and efficient
recovery,” IEEE Transactions on Network Science and Engineering, vol. 1, no. 1, pp. 10–22, 2014.
[17] B. Hajek, Y. Wu, and J. Xu, “Achieving exact cluster recovery threshold via semidefinite programming: Extensions,” IEEE Transactions on Information
Theory, vol. 62, no. 10, pp. 5918–5937, Oct 2016.
[18] E. Abbe, A. S. Bandeira, and G. Hall, “Exact recovery in the stochastic block model,” IEEE Transactions on Information Theory, vol. 62, no. 1, pp.
471–487, 2016.
[19] E. Mossel, J. Neeman, and A. Sly, “Consistency thresholds for binary symmetric block models,” arXiv preprint arXiv:1407.1591, 2014.
[20] E. Abbe and C. Sandon, “Community detection in general stochastic block models: Fundamental limits and efficient algorithms for recovery,” in FOCS.
IEEE, 2015, pp. 670–688.
[21] A. Decelle, F. Krzakala, C. Moore, and L. Zdeborová, “Asymptotic analysis of the stochastic block model for modular networks and its algorithmic
applications,” Physical Review E, vol. 84, no. 6, p. 066106, 2011.
[22] Y. Chen and J. Xu, “Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and
submatrices,” The Journal of Machine Learning Research, vol. 17, no. 1, pp. 882–938, 2016.
[23] J. Neeman and P. Netrapalli, “Non-reconstructability in the stochastic block model,” arXiv preprint arXiv:1404.6304, 2014.
[24] A. Montanari, “Finding one community in a sparse graph,” Journal of Statistical Physics, vol. 161, no. 2, pp. 273–299, 2015.
[25] J. Banks, C. Moore, J. Neeman, and P. Netrapalli, “Information-theoretic thresholds for community detection in sparse networks,” in Conference on
Learning Theory (COLT), 2016, pp. 383–416.
[26] E. Abbe and C. Sandon, “Proof of the achievability conjectures in the general stochastic block model,” To Appear in Communications on Pure and
Applied Mathematics, 2017.
[27] E. Mossel, J. Neeman, and A. Sly, “Reconstruction and estimation in the planted partition model,” Probability Theory and Related Fields, vol. 162, no.
3-4, pp. 431–461, 2015.
[28] ——, “A proof of the block model threshold conjecture,” arXiv preprint arXiv:1311.4115, 2013.
[29] L. Massoulié, “Community detection thresholds and the weak ramanujan property,” in Proceedings of the forty-sixth annual ACM symposium on Theory
of computing. ACM, 2014, pp. 694–703.
[30] C. Bordenave, M. Lelarge, and L. Massoulie, “Non-backtracking spectrum of random graphs: Community detection and non-regular ramanujan graphs,”
in FOCS. IEEE, 2015, pp. 1347–1357.
[31] A. Y. Zhang, H. H. Zhou et al., “Minimax rates of community detection in stochastic block models,” The Annals of Statistics, vol. 44, no. 5, pp.
2252–2280, 2016.
[32] C. Gao, Z. Ma, A. Y. Zhang, and H. H. Zhou, “Achieving optimal misclassification proportion in stochastic block model,” Journal of Machine Learning
Research, 2017.
[33] E. Abbe, “Community detection and stochastic block models: Recent developments,” Journal of Machine Learning Research, Special Issue, 2017.
[34] D. Ghoshdastidar and A. Dukkipati, “Uniform hypergraph partitioning: Provable tensor methods and sampling techniques,” Journal of Machine
Learning Research, vol. 18, no. 50, pp. 1–41, 2017. [Online]. Available: http://jmlr.org/papers/v18/16-100.html
[35] ——, “Consistency of spectral hypergraph partitioning under planted partition model,” The Annals of Statistics, 45(1), pp. 289-315, 2017.
[36] V. M. Govindu, “A tensor decomposition for geometric grouping and segmentation,” in 2005 IEEE Computer Society Conference on Computer Vision
and Pattern Recognition, vol. 1. IEEE, 2005, pp. 1150–1157.
[37] G. Chen and G. Lerman, “Spectral curvature clustering (scc),” International Journal of Computer Vision, vol. 81, no. 3, pp. 317–330, 2009.
[38] O. Watanabe, “Message passing algorithms for MLS-3LIN problem,” Algorithmica, vol. 66, no. 4, pp. 848–868, 2013.
[39] L. Florescu and W. Perkins, “Spectral thresholds in the bipartite stochastic block model,” In Proceedings of the Conference on Learning Theory (COLT),
pp. 943–959, 2016.
[40] M. Angelini, F. Caltagirone, F. Krzakala, and L. Zdeborova, “Spectral detection on sparse hypergraphs,” in Allerton Conference on Communication,
Control, and Computing, Sept 2015, pp. 66–73.
[41] C.-Y. Lin, C. I, and I.-H. Wang, “On the fundamental statistical limit of community detection in random hypergraphs,” in IEEE International Symposium
on Information Theory (ISIT), June 2017, pp. 2183–2187.
[42] N. Vesdapunt, K. Bellare, and N. Dalvi, “Crowdsourcing algorithms for entity resolution,” Proceedings of the VLDB Endowment, vol. 7, no. 12, pp.
1071–1082, 2014.
[43] H. Ashtiani, S. Kushagra, and S. Ben-David, “Clustering with same-cluster queries,” in Advances in Neural Information Processing Systems, 2016, pp.
3216–3224.
[44] R. Dorfman, “The detection of defective members of large populations,” The Annals of Mathematical Statistics, vol. 14, no. 4, pp. 436–440, 1943.
[45] I. H. Wang, S. L. Huang, and K. Y. Lee, “Extracting sparse data via histogram queries,” in Allerton Conference on Communication, Control, and
Computing, Sept 2016, pp. 39–45.
[46] I. H. Wang, S. L. Huang, K. Y. Lee, and K. C. Chen, “Data extraction via histogram and arithmetic mean queries: Fundamental limits and algorithms,”
in IEEE International Symposium on Information Theory (ISIT), July 2016, pp. 1386–1390.
[47] R. Vidal, R. Tron, and R. Hartley, “Multiframe motion segmentation with missing data using powerfactorization and GPCA,” International Journal of
Computer Vision, vol. 79, no. 1, pp. 85–105, 2008.

22

[48] J. Ho, M.-H. Yang, J. Lim, K.-C. Lee, and D. Kriegman, “Clustering appearances of objects under varying illumination conditions,” in IEEE Computer
Society Conference on Computer Vision and Pattern Recognition, 2003., vol. 1. IEEE, 2003, pp. I–11.
[49] R. Vidal, “Subspace clustering,” IEEE Signal Processing Magazine, vol. 28, no. 2, pp. 52–68, March 2011.
[50] E. Elhamifar and R. Vidal, “Sparse subspace clustering: Algorithm, theory, and applications,” IEEE transactions on pattern analysis and machine
intelligence, vol. 35, no. 11, pp. 2765–2781, 2013.
[51] E. L. Dyer, A. C. Sankaranarayanan, and R. G. Baraniuk, “Greedy feature selection for subspace clustering.” Journal of Machine Learning Research,
vol. 14, no. 1, pp. 2487–2517, 2013.
[52] R. Heckel and H. Bölcskei, “Robust subspace clustering via thresholding,” IEEE Transactions on Information Theory, vol. 61, no. 11, pp. 6320–6342,
2015.
[53] B. Hajek, Y. Wu, and J. Xu, “Information limits for recovering a hidden community,” in Information Theory (ISIT), 2016 IEEE International Symposium
on. IEEE, 2016, pp. 1894–1898.
[54] W. Hoeffding, “Probability inequalities for sums of bounded random variables,” Journal of the American Statistical Association, vol. 58, no. 301, pp.
13–30, 1963.
[55] N. Alon and J. H. Spencer, The probabilistic method. John Wiley & Sons, 2004.
[56] K. Ahn, K. Lee, and C. Suh, “Hypergraph spectral clustering in the weighted stochastic block model,” 2017. [Online]. Available:
https://sites.google.com/site/kw1jjang/HSC WSBM.pdf
[57] R. H. Keshavan, A. Montanari, and S. Oh, “Matrix completion from a few entries,” IEEE Transactions on Information Theory, vol. 56, no. 6, pp.
2980–2998, 2010.
[58] P. Jain, P. Netrapalli, and S. Sanghavi, “Low-rank matrix completion using alternating minimization,” in Proceedings of the forty-fifth annual ACM
symposium on Theory of computing. ACM, 2013, pp. 665–674.
[59] P. Netrapalli, P. Jain, and S. Sanghavi, “Phase retrieval using alternating minimization,” in Advances in Neural Information Processing Systems, 2013,
pp. 2796–2804.
[60] E. J. Candes, X. Li, and M. Soltanolkotabi, “Phase retrieval via wirtinger flow: Theory and algorithms,” IEEE Transactions on Information Theory,
vol. 61, no. 4, pp. 1985–2007, 2015.
[61] X. Yi, D. Park, Y. Chen, and C. Caramanis, “Fast algorithms for robust pca via gradient descent,” in Advances in Neural Information Processing
Systems, 2016, pp. 4152–4160.
[62] Y. Chen, G. Kamath, C. Suh, and D. Tse, “Community recovery in graphs with locality,” in ICML, 2016.
[63] P. Chin, A. Rao, and V. Vu, “Stochastic block model and community detection in sparse graphs: A spectral algorithm with optimal rate of recovery.”
in Proceedings of the Conference on Learning Theory (COLT), 2015, pp. 391–423.
[64] S. Balakrishnan, M. J. Wainwright, and B. Yu, “Statistical guarantees for the em algorithm: From population to sample-based analysis,” Ann. Statist.,
vol. 45, no. 1, pp. 77–120, 02 2017. [Online]. Available: http://dx.doi.org/10.1214/16-AOS1435
[65] Y. Chen and C. Suh, “Spectral MLE: Top-k rank aggregation from pairwise comparisons,” in ICML, 2015, pp. 371–380.
[66] R. Tron and R. Vidal, “A benchmark for the comparison of 3-d motion segmentation algorithms,” in Computer Vision and Pattern Recognition, 2007.
CVPR’07. IEEE Conference on. IEEE, 2007, pp. 1–8.
[67] P. Jain and S. Oh, “Provable tensor factorization with missing data,” in Advances in Neural Information Processing Systems, 2014, pp. 1431–1439.

A PPENDIX A
P ROOFS OF L EMMAS
A. Proof of Lemma 1
Recall that
|Fi,j | =


d−1  
X
i
k−i
`=1

`

d−`

+


d−1  
X
i
n−k−j
`=1

d−`

`

+


d−1  
X
j
n−k−j
`=1

`

d−`



d−1 
X
k−i
j
+
.
`
d−`

In order to prove the lemma, it is sufficient to prove the following inequalities:
 X



d−1  
d−1  
X
i
k−i
i
n−k−j
(1 − 2δ)d−1 n − 1
Z :=
+
≥i·
` d−`
`
d−`
2d−2
d−1
`=1

(54)

`=1

(55)

`=1

and

d−1  
X
j
n−k−j
`=1

`

d−`

+





d−1 
X
k−i
j
(1 − 2δ)d−1 n − 1
≥j·
.
`
d−`
2d−2
d−1

Here, we will focus on proving (55). We remark that the proof of (56) is essentially identical.
Since i < δn and j < δn,
 X

d−1  
d−1  
X
i
k − δn
i
n − k − δn
Z≥
+
.
`
d−`
`
d−`
`=1

(56)

`=1

(57)

`=1

We further bound Z by considering two cases separately: k ≥ δn and k < δn. When k ≥ δn,
 X





d−1  
d−1  
X
i
k − δn
i
n − k − δn
k − δn
n − k − δn
+
≥i
+i
`
d−`
`
d−`
d−1
d−1
`=1
`=1
"
d−1 
d−1 # 

k
k
n−1
≈i·
−δ
+ 1− −δ
,
n
n
d−1

(58)

23




where the last inequality holds since an
≈ ab nb ≈ ab n−1
for constants a and b. We then apply Hölder’s inequality:
b
b
P
P
1/p P
1/q
Given p, q such that 1/p + 1/q = 1, we have z |xz yz | ≤ ( z |xz |p ) ( z |yz |q )
for all sequences {xz } and {yz }. By
setting (x1 , x2 ) = (α, β), (y1 , y2 ) = (1, 1), p = d − 1, q = d−1
d−2 , we have
d−2

1

α + β ≤ (αd−1 + β d−1 ) d−1 2 d−1 .

(59)

Applying (59) to (58), we have
"


d−1 
d−1 # 

k
n−1
(1 − 2δ)d−1 n − 1
k
+ 1− −δ
.
−δ
≥i·
i·
d−1
n
n
d−1
2d−2

Pd−1 
When k < δn, `=1 `i n−k−j
becomes the dominant term. Hence,
d−`

d−1  
X
j
n − k − δn
`=1

`

d−`







d−1 
X
k−i
δn
n − k − δn
n − 2δn
+
>i
>i
`
d−`
d−1
d−1
`=1




(1 − 2δ)d−1 n − 1
d−1 n − 1
.
≈ i · (1 − 2δ)
>i·
d−1
d−1
2d−2

(60)

(61)
(62)

This completes the proof.
B. Proof of Lemma 2
Denote by Rbig ⊂ [n] the set of nodes of size n/ log7 n. One can easily show that with high probability, some nodes of
this set are connected by the same hyperedge(s). Denote by Rres the largest subset of Rbig , whose elements do not share the
same hyperedges. The lemma states that with high probability, |Rres | ' |Rbig |.
We now formally prove this statement. Note that for a hyperedge E = (i1 , i2 , · · · , id ), |E ∩ Rbig | is the number of nodes
in Rbig that are connected by the hyperedge. Hence, if 2 ≤ |E ∩ Rbig | ≤ d, this hyperedge connects more than one nodes in
Rbig , and E ∩ Rbig is the set of the nodes that share the same hyperedge E.
Let us denote by Rshare the subset of nodes that are connected by the same hyperedge(s). Then,
Rshare :=

d
[

(k)

Rshare :=

d
[
k=2

k=2

[

E ∩ Rbig .

(63)

E∈E:
|E∩Rbig |=k

Our proof strategy is as follows. Since
Rres = Rbig − Rshare = Rbig −

d
[

(k)

Rshare ,

(64)

k=2

it is sufficient to show that
d
[

(k)

Rshare = o(|Rbig |).

(65)

k=2

More specifically, we will show

(k)
Pr ∃k ∈ {2, 3, . . . , d} s.t. |Rshare | >

n
log9 n


→ 0.

(66)

(k)

That is, with probability approaching 1, |Rshare | = o(n/ log8 n) for all k, 2 ≤ k ≤ d. Note that this implies (65) since




d
d
[
X
n
n
(k)
(k)
Rshare ≤
|Rshare | = O(d) × o
=
o
= o(|Rbig |).
log8 n
log7 n
k=2
k=2

(67)

(k)

In order to bound (66), we first derive an upper bound on the expected value of |Rshare |. By definition,
X
X
(k)
|Rshare | ≤
|E ∩ Rbig | ≤
k = |{E ∈ E : |E ∩ Rbig | = k}| · k.
E∈E:
|E∩Rbig |=k

E∈E:
|E∩Rbig |=k

(68)

24

Observe that |{E ∈ E : |E ∩ Rbig |}| is the sum of
Hence,

|Rbig |
k



n−|Rbig |
d−k



i.i.d. Bernoulli random variables with probability p.





|Rbig | n − |Rbig |
E {|{E ∈ E : |E ∩ Rbig | = k}| · k} = k
p
(69)
k
d−k



|Rbig | − 1 n − |Rbig |
= |Rbig |
p.
(70)
k−1
d−k
 n−|Rbig |


big |−1
big |
As |Rbig | = o(n), we have |Rk−1
≤ |Rbig1|−1 n−|R
, which in turn gives
d−k
d−2



|Rbig | − 1 n − |Rbig |
(70) ≤ |Rbig |
p
1
d−2


n−2
≤ 2|Rbig |2
p
d−2


n − 2 n log n

= 2|Rbig |2
n
d−2
d




|Rbig |2 d2 log n
n
=O
=O
,
n
log11 n


n d2
where the last equality holds since n−2
d−2 ≈ d n2 . Note that this inequality holds for any 2 ≤ k ≤ d. Using Markov’s
inequality,






n
log9 n
n
1
Pr |{E ∈ E : |E ∩ Rbig | = k}| · k >
≤
·O
=O
.
(71)
n
log9 n
log11 n
log2 n
Applying the union bound over all 2 ≤ k ≤ d,

Pr ∃k ∈ {2, 3, . . . , d} s.t. |{E ∈ E : |E ∩ Rbig | = k}| · k >

n
log9 n




≤d·O

1
log2 n

This completes the proof.
C. Proof of Lemma 4
Since 1 ≤ i ≤ P − 1,
k
i+1



n−k
k
d−(i+1) + i−1


k n−k
i
d−i





n−k
d−(i−1)



(k − i)(d − i)
i(n − k − d + i)
+
(i + 1)(n − k − d + i + 1) (k − i + 1)(d − i + 1)
s
(k − i)(d − i)
i(n − k − d + i)
≥2
·
(i + 1)(n − k − d + i + 1) (k − i + 1)(d − i + 1)
s
(d − i)
i
(n − k − d + i)
(k − i)
·
·
·
=2
(k − i + 1) (d − i + 1) i + 1 (n − k − d + i + 1)
s 
4
1
1
= .
≥2
2
2
=

D. Proof of Lemma 5
1) β ≤ k ≤ n/2
Since d ≤ n/2 and β < n/2, one can verify the inequality using the following facts:
 

 

k
n−k
k
n−k
n−d+1
≤2
⇔k≥
;
0
d
1
d−1
2d + 1
 




k
n−k
k
n−k
n−d+1
≤2
⇔k ≤n−
.
d
0
d−1
1
2d + 1
2) k < β




=O

1
log n


.

(72)

25


  n−d+1 
n−d+1 α
n−d+1
n−d+1
e
−
1
≤
,
=
/k
>
/ 2d+1 =
We first show that α/k ≥ 2. Since k ≤ d n−d+1
2d+1
2d+1
k
d
d
Next, the inequality can be checked using the following facts:
 




k
n−k
k
n−k
n−d+1
≤2
⇔k ≤n−
d
0
d−1
1
2d + 1


k n−k
n−d+1
α
n−k−d+1
0
≤
= .
 d =
k n−k
kd
kd
k
1 d−1

2d+1
d

≥ 2.

