Community Recovery in Graphs with Locality
Yuxin Chen∗

Govinda Kamath†

Changho Suh‡

David Tse§

February 2016; Revised: June 2016

arXiv:1602.03828v3 [] 1 Jun 2016

Abstract
Motivated by applications in domains such as social networks and computational biology, we study
the problem of community recovery in graphs with locality. In this problem, pairwise noisy measurements
of whether two nodes are in the same community or different communities come mainly or exclusively
from nearby nodes rather than uniformly sampled between all node pairs, as in most existing models.
We present two algorithms that run nearly linearly in the number of measurements and which achieve
the information limits for exact recovery.

1

Introduction

Clustering of data is a central problem that is prevalent across all of science and engineering. One formulation that has received significant attention in recent years is community recovery [1–3], also referred to as
correlation clustering [4] or graph clustering [5]. In this formulation, the objective is to cluster individuals
into different communities based on pairwise measurements of their relationships, each of which gives some
noisy information about whether two individuals belong to the same community or different communities.
While this formulation applies naturally in social networks, it has a broad range of applications in other
domains including protein complex detection [6], image segmentation [7, 8], shape matching [9], etc. See [10]
for an introduction of this topic.
In recent years, there has been a flurry of works on designing community recovery algorithms based on
idealised generative models of the measurement process. A particular popular model is the Stochastic Block
Model (SBM) [11, 12], where the n individuals to be clustered are modeled as nodes on a random graph. In
the simplest version of this model with two communities, this random graph is generated such that two nodes
has an edge connecting them with probability p if they are in the same community and probability q if they
belong to different communities. If p > q, then there are statistically more edges within a community than
between two communities, which can provide discriminating information for recovering the communities. A
closely related model is the Censored Block Model (CBM) [13], where one obtains noisy parity measurements
on the edges of an Erdős-Rényi graph [14]. Each edge measurement is 0 with probability 1 − θ and 1 with
probability θ if the two incident vertices are in the same community, and vice versa if they are in different
communities.
Both the SBM and the CBM can be unified into one model by viewing the measurement process as
a two-step process. First, the edge locations where there are measurements are determined by randomly
and uniformly sampling a complete graph between the nodes. Second, the value of each edge measurement
is obtained as a noisy function of the communities of the two nodes the edge connects. The two models
differ only in the noisy functions. Viewed in this light, it is seen that a central assumption underlying
both models is that it is equally likely to obtain measurements between any pair of nodes. This is a very
unrealistic assumption in many applications: nodes often have locality and it is more likely to obtain data
on relationships between nearby nodes than far away nodes. For example, in friendship graphs, individuals
that live close by are more likely to interact than nodes that are far away.
∗ Department of Statistics and of Electrical Engineering, Stanford University, Stanford, CA 94305, USA (email: yxchen@stanford.edu).
† Department of Electrical Engineering, Stanford University, Stanford, CA 94305, USA (email: gkamath@stanford.edu).
‡ Department of Electrical Engineering, KAIST, Daejeon 305-701, Korea (e-mail: chsuh@kaist.ac.kr).
§ Department of Electrical Engineering, Stanford University, Stanford, CA 94305, USA (email: dntse@stanford.edu).

1

This paper focuses on the community recovery problem when the measurements are randomly sampled
from graphs with locality structure rather than complete graphs. Our theory covers a broad range of graphs
including rings, lines, 2-D grids, and small-world graphs (Fig. 1). Each of these graphs is parametrized by
a locality radius r such that nodes within r hops are connected by an edge. We characterize the information limits for community recovery on these networks, i.e. the minimum number of measurements needed
to exactly recover the communities as the number of nodes n scales. We propose two algorithms whose
complexities are nearly linear in the number of measurements and which can achieve the information limits
of all these networks for a very wide range of the radius r. In the special case when the radius r is so large
that measurements at all locations are possible, we recover the exact recovery limit identified by [15] when
measurements are randomly sampled from complete graphs.
It is worth emphasizing that various computationally feasible algorithms [5, 16–21] have been proposed
for more general models beyond the SBM and the CBM, which accommodate multi-community models, the
presence of outlier samples, the case where different edges are sampled at different rates, and so on. Most
of these models, however, fall short of accounting for any sort of locality constraints. In fact, the results
developed in prior literature often lead to unsatisfactory guarantees when applied to graphs with locality, as
will be detailed in Section 3. Another recent work [22] has determined the order of the information limits
in geometric graphs, with no tractable algorithms provided therein. In contrast, our findings uncover a
curious phenomenon: the presence of locality does not lead to additional computational barriers: solutions
that are information theoretically optimal can often be achieved computational efficiently and, perhaps more
surprisingly, within nearly linear time.
The paper is structured as follows. We describe the problem formulation in Section 2, including a concrete
application from computational biology—called haplotype phasing—which motivates much of our theory.
Section 3 presents our main results, with extensions of the basic theory and numerical results provided in
Sections 4 and 5 respectively. Section 6 concludes the paper with a few potential extensions. The proofs of
all results are deferred to the appendices.

2

Problem Formulation and A Motivating Application

This section is devoted to describing a basic mathematical setup of our problem, and to discussing a concrete
application that comes from computational biology.

2.1

Sampling Model

Measurement Graph. Consider a collection of n vertices V = {1, · · · , n}, each represented by a binaryvalued vertex variable Xi ∈ {0, 1}, 1 ≤ i ≤ n. Suppose it is only feasible to take pairwise samples over a
restricted set of locations, as represented by a graph G = (V, E) that comprises an edge set E. Specifically,
(l)
for each edge (i, j) ∈ E one acquires Ni,j samples1 Yi,j (1 ≤ l ≤ Ni,j ), where each sample measures the
parity of Xi and Xj . We will use G to encode the locality constraint of the sampling scheme, and shall pay
particular attention to the following families of measurement graphs.
• Complete graph: G is called a complete graph if every pair of vertices is connected by an edge; see
Fig. 1(a).
• Line: G is said to be a line Lr if, for some locality radius r, (i, j) ∈ E iff |i − j| ≤ r; see Fig. 1(b).
• Ring: G = (V, E) is said to be a ring Rr if, for some locality radius r, (i, j) ∈ E iff i − j ∈ [−r, r]
(mod n); see Fig. 1(c).
√
√
• Grid : G is called a grid if (1) all vertices reside within a n × n square with integer coordinates,
and (2) two vertices are connected by an edge if they are at distance not exceeding some radius r; see
Fig. 1(d).
• Small-world graphs: G is said to be a small-world graph if it is a superposition of a complete graph
G0 = (V, E0 ) and another graph G1 = (V, E1 ) with locality. See Fig. 1(e) for an example.

2

|

rr

}

}

}

{z
{z

r

r

(a) a complete graph

|

{z

{z

|

|

(b) a line Lr

{z

|

|

}

r

z{

r

(d) a grid

}

(c) a ring Rr

}

(e) a small-world graph

Figure 1: Examples of a complete graph, a line, a ring, a 2-D grid, and a small-world graph.
Random Sampling. This paper focuses on a random sampling model, where the number of samples Ni,j
taken over (i, j) ∈ E is independently drawn and obeys2 Ni,j ∼ Poisson (λ) for some average sampling rate
λ. This gives rise to an average total sample size
X
m :=
E [Ni,j ] = λ |E| .
(1)
(i,j)∈E

When m is large, the actual sample size sharply concentrates around m with high probability.

Measurement Noise Model. The acquired parity measurements are assumed to be independent given
Ni,j ; more precisely, conditional on Ni,j ,
(
Xi ⊕ Xj ,
with probability 1 − θ
(l)
(l) ind.
Yi,j = Yj,i =
(2)
Xi ⊕ Xj ⊕ 1, else
for some fixed error rate 0 < θ < 1, where ⊕ denotes modulo-2 addition. This is the same as the noise model
in CBM [13]. The SBM corresponds to an asymmetric erasure model for the measurement noise, and we
expect our results extend to that model as well.

2.2

Goal: Optimal Algorithm for Exact Recovery

This paper centers on exact recovery, that is, to reconstruct all input variables X = [Xi ]1≤i≤n precisely
up to global offset. This is all one can hope for since there is absolutely no basis to distinguish X from
X ⊕ 1 := [Xi ⊕ 1]1≤i≤n given only parity samples. More precisely, for any recovery procedure ψ the
probability of error is defined as
Pe (ψ) :=

max

X∈{0,1}n

P {ψ(Y ) 6= X and ψ(Y ) 6= X ⊕ 1} ,

(l)

where Y := {Yi,j }. The goal is to develop an algorithm whose required sample complexity approaches the
information limit m∗ (as a function of (n, θ)), that is, the minimum sample size m under which inf ψ Pe (ψ)
1
vanishes as n scales. For notational simplicity, the dependency of m∗ on (n, θ) shall often be suppressed
when it is clear from the context.
1 Here

and throughout, we adopt the convention that Ni,j ≡ 0 for any (i, j) ∈
/ E.
results presented in this paper hold under a related model where Ni,j ∼ Bernoulli (λ), as long as |E|  n log n and λ ≤ 1
(which is the regime accommodated in all theorems). In short, this arises due to the tightness of Poisson approximation to the
Binomial distribution. We omit the details for conciseness.
2 All

3

1

1

2.3

Haplotype Phasing: A Motivating Application

Before proceeding to present the algorithms, we describe here a genome phasing application that motivates
this research and show how it can be modeled as a community recovery problem on graphs with locality.
Humans have 23 pairs of homologous chromosomes, one maternal and one paternal. Each pair are
identical sequences of nucleotides A,G,C,T’s except on certain documented positions called single nucleotide
polymorphisms (SNPs), or genetic variants. At each of these positions, one of the chromosomes takes on
one of A,G,C or T which is the same as the majority of the population (called the major allele), while the
other chromosome takes on a variant (also called minor allele). The problem of haplotype phasing is that of
determining which variants are on the same chromosome in each pair, and has important applications such
as in personalized medicine and understanding poylogenetic trees. The advent of next generation sequencing
technologies allows haplotype phasing by providing linking reads between multiple SNP locations [23–25].
One can formulate the problem of haplotype phasing as recovery of two communities of SNP locations,
those with the variant on the maternal chromosome and those with the variant on the paternal chromosome
[26, 27]. Each pair of linking reads gives a noisy measurement of whether two SNPs have the variant on
the same chromosome or different chromosomes. While there are of the order of n = 105 SNPs on each
chromosome, the linking reads are typically only several SNPs or at most 100 SNPs apart, depending on the
specific sequencing technology. Thus, the measurements are sampled from a line graph like in Fig. 1(b) with
locality radius r  n.

2.4

Other Useful Metrics and Notation

It is convenient to introduce some notations that will be used throughout. One key metric that captures the
distinguishability between two probability measures P0 and P1 is the Chernoff information [28], defined as
D∗ (P0 , P1 ) := − inf log

nX

0≤τ ≤1

y

o
P0τ (y) P11−τ (y) .

(3)

For instance, when P0 ∼ Bernoulli (θ) and P1 ∼ Bernoulli (1 − θ), D∗ simplifies to
D∗ = KL (0.5 k θ) = 0.5 log

0.5
0.5
+ 0.5 log
,
θ
1−θ

(4)

where KL (0.5 k θ) is the Kullback-Leibler (KL) divergence between Bernoulli(0.5) and Bernoulli(θ). Here and
below, we shall use log (·) to indicate the natural logarithm.
In addition, we denote by dv and davg the vertex degree of v and the average vertex degree of G,
respectively. We use kM k to represent the spectral norm of a matrix M . Let 1 and 0 be the all-one and
all-zero vectors, respectively. We denote by supp (x) (resp. kxk0 ) the support (resp. the support size) of x.
The standard notion f (n) = o (g(n)) means lim f (n)/g(n) = 0; f (n) = ω (g(n)) means lim g(n)/f (n) = 0;
n→∞

n→∞

f (n) = Ω (g(n)) or f (n) & g(n) mean there exists a constant c such that f (n) ≥ cg(n); f (n) = O (g(n)) or
f (n) . g(n) mean there exists a constant c such that f (n) ≤ cg(n); f (n) = Θ (g(n)) or f (n)  g(n) mean
there exist constants c1 and c2 such that c1 g(n) ≤ f (n) ≤ c2 g(n).

3

Main Results

This section describes two nearly linear-time algorithms and presents our main results. The proofs of all
theorems are deferred to the appendices.

3.1
3.1.1

Algorithms
Spectral-Expanding

The first algorithm, called Spectral-Expanding, consists of three stages. For concreteness, we start by
describing the procedure when the measurement graphs are lines / rings; see Algorithm 1 for a precise
description of the algorithm and Fig. 2 for a graphical illustration.

4

Algorithm 1 : Spectral-Expanding
1. Run spectral method (Algorithm 2) on a core subgraph induced by Vc , which yields estimates
(0)
Xj , 1 ≤ j ≤ |Vc |.
2. Progressive estimation: for i = |Vc | + 1, · · · , n,
n
o
(0)
(l)
(0)
Xi ← majority Yi,j ⊕ Xj | j : j < i, (i, j) ∈ E, 1 ≤ l ≤ Ni,j .
3. Successive local refinement:
n for t = 0, · · · , T − 1,
o
(t+1)
(l)
(t)
Xi
← majority Yi,j ⊕ Xj | j : j 6= i, (i, j) ∈ E, 1 ≤ l ≤ Ni,j ,
(T )

4. Output Xi

1 ≤ i ≤ n.

, 1 ≤ i ≤ n.

Here, majority {·} represents the majority voting rule: for any sequence s1 , · · · , sk
Pk
majority {s1 , · · · , sk } is equal to 1 if i=1 si > k/2; and 0 otherwise.

∈

{0, 1},

Algorithm 2 : Spectral initialization

n
o
(l)
1. Input: measurement graph G = (V, E), and samples Yi,j ∈ {0, 1} | j : j < i, (i, j) ∈ E, 1 ≤ l ≤ Ni,j .
2. Form a sample matrix A such that
( 
 (1)
(1)
1 Yi,j = 0 − 1 Yi,j = 1 ,
Ai,j =
0,

if (i, j) ∈ E;
else.

3. Compute the leading eigenvector u of A, and for all 1 ≤ i ≤ n set
(
1, if ui ≥ 0,
(0)
Xi =
0, else.
(0)

4. Output Xi , 1 ≤ i ≤ n.
• Stage 1: spectral metrod on a core subgraph. Consider a subgraph Gc induced by Vc :=
{1, · · · , r}, and it is self-evident that Gc is a complete subgraph. We run a spectral method (e.g. [29])
on Gc using samples taken over Gc , in the hope of obtaining approximate recovery of {Xi | i ∈ Vc }.
Note that the spectral method can be replaced by other efficient algorithms, including semidefinite
programming (SDP) [30] and a variant of belief propagation (BP) [31].
• Stage 2: progressive estimation of remaining vertices. For each vertex i > |Vc |, compute an
estimate of Xi by majority vote using backward samples—those samples linking i and some j < i.
The objective is to ensure that a large fraction of estimates obtained in this stage are accurate. As
will be discussed later, the sample complexity required for approximate recovery is much lower than
that required for exact recovery, and hence the task is feasible even though we do not use any forward
samples to estimate Xi .
• Stage 3: successive local refinement. Finally, we clean up all estimates using both backward and
forward samples in order to maximize recovery accuracy. This is achieved by running local majority
voting from the neighbors of each vertex until convergence. In contrast to many prior work, no sample
splitting is required, namely, we reuse all samples in all iterations in all stages. As we shall see, this
stage is the bottleneck for exact information recovery.
Remark 1. The proposed algorithm falls under the category of a general non-convex paradigm, which starts
5

V1

V2

V1
V1

V2

V6 core
1 4 VV
2 5 V3
V3 VV
V6 V4coreV5subgraph
Vcsubgraph Vc
Stage 1:

V2

V3

V4

V5

Stage 2:

V6

Stage 3:

Stages 1-2:

core subgraph Vc

Stage 1: Stage 2: Stage 3: Stages 1-2:
V3 V4 V5 V6 core subgraph Vc

Stage 1: Stage 2: Stage 3: Stages 1-2:

Figure 2: Illustration of the information flow in Spectral-Expanding: (a) Stage 1 concerns recovery in a
core complete subgraph; (b) Stage 2 makes a forward pass by progressively propagating information through
backward samples; (c) Stage 3 refines each Xv by employing all samples incident to v.
with an approximate estimate (often via spectral methods) followed by iterative refinement. This paradigm
has been successfully applied to a wide spectrum of applications ranging from matrix completion [32, 33] to
phase retrieval [34] to community recovery [17, 35, 36].
An important feature of this algorithm is its low computational complexity. First of all, the spectral
method can be performed within O (mc log n) time by means of the power method, where mc indicates the
number of samples falling on Gc . Stage 2 entails one round of majority voting, whereas the final stage—as
we will demonstrate—converges within at most O (log n) rounds of majority voting. Note that each round
of majority voting can be completed in linear time, i.e. in time proportional to reading all samples. Taken
collectively, we see that Spectral-Expanding can be accomplished within O (m log n) flops, which is nearly
linear time.
Careful readers will recognize that Stages 2-3 bear similarities with BP, and might wonder whether Stage
1 can also be replaced with standard BP. Unfortunately, we are not aware of any approach to analyze the
performance of vanilla BP without a decent initial guess. Note, however, that the spectral method is already
nearly linear-time, and is hence at least as fast as any feasible procedure.
While the preceding paradigm is presented for lines / rings, it easily extends to a much broader family
of graphs with locality. The only places that need to be adjusted are:
1. The core subgraph Vc . One would like to ensure that |Vc | & davg and that the subgraph Gc induced
by Vc forms a (nearly) complete subgraph, in order to guarantee decent recovery in Stage 1.
2. The ordering of the vertices. Let Vc form the first |Vc | vertices of V, and make sure that each
i > |Vc | is connected to at least an order of davg vertices in {1, · · · , i − 1}. This is important because
each vertex needs to be incident to sufficiently many backward samples in order for Stage 2 to be
successful.
3.1.2

Spectral-Stitching

1

We now turn to the 2nd algorithm called Spectral-Stitching, which shares similar spirit as Spectral-Expanding
and, in fact, differs from Spectral-Expanding only in Stages 1-2.
1
• Stage 1: node splitting and spectral estimation. Split V into several overlapping subsets Vl (l ≥
1) of size W , such that any two adjacent subsets share W/2 common vertices. We choose the size W
of each Vl to be r for rings / lines, and on the order of davg for other graphs. We then run spectral
methods separately1on each subgraph Gl induced by Vl , in the hope of achieving approximate estimates
{XiVl | i ∈ Vl }—up to global phase—for each subgraph.
• Stage 2: stiching the estimates. The aim of this stage is to stitch together the outputs of Stage 1
1
computed in isolation for the collection of overlapping subgraphs. If approximate recovery (up to some
global phase) has been achieved in Stage 1 for each Vl , then the outputs for any two adjacent subsets
6

Algorithm 3 : Spectral-Stitching
1. Split all vertices into several (non-disjoint) vertex subsets each of size W as follows
Vl := {i | (i − 1) W/2 + 1 ≤ l ≤ (i − 1) W/2 + W } ,

l = 1, 2, · · · ,

and run spectral method (Algorithm 2) on each subgraph induced by Vl , which yields estimates {XjVl | j ∈ Vl } for each l ≥ 1.
(0)

2. Stitching: set Xj

← XjV1 for all j ∈ V1 ; for l = 2, 3, · · · ,
(0)

Xj
(0)

and Xj

← XjVl (∀j ∈ Vl ) if

X

j∈Vl ∩Vl−1

V

XjVl ⊕ Xj l−1 ≤ 0.5 |Vl ∩ Vl−1 | ;

← XjVl ⊕ 1 (∀j ∈ Vl ) otherwise.
(T )

3. Successive local refinement and output Xi

, 1 ≤ i ≤ n (see Steps 3-4 of Algorithm 1).

core subgraph Vc
VV3 1 VV4 2 VV5 3V1VV6 4V2 V5V3 V6V4 V5 V6
Stage 1: Stage 2: Stage 3: Stages 1-2:

V1

V1

V2

V3

V2

V4

V3

V5

V4

V6

V5

V1

V6

V2

V1 V2 VV
1 VV
4 2 VV53 VV164 VV25 VV36 V4 V5 V6
core subgraph
Vc 3
V1 V2 VV
V3VV16V4V2 V5V3 V6V4
3 1 VV
4 2 V5

Stage 1: Stage 2: Stage 3: Stages 1-2:

V1

V2

V3

Stage 1:

V4

V5

Stage 2:

V6

core subgraph VcV1

Stage 3:

Stages 1-2:

V5

V6

VV
3 1 VV
4 2 VV53 VV164 VV25 VV36 V4 V5 V6

V2

Figure 3: Illustration of the information flow in Spectral-Stitching: (a) Stage 1 runs spectral methods for a
collection of overlapping subgraphs of size W separately; (b) Stage 2 stitches all groups of estimates together
using the information coming from their overlaps; (c) Stage 3 cleans up all estimates by employing all samples
incident to each node.
are positively correlated only when they have matching global phases. This simple observation allows
(0)
us to calibrate the global phases for all preceding estimates, thus yielding a vector {Xi }1≤i≤n that
is approximately faithful to the truth modulo some global phase.
The remaining steps of Spectral-Stitching follow the same local refinement procedure as in SpectralExpanding, and we can employ the same ordering of vertices as in Spectral-Expanding. See Algorithm 3
and Fig. 3. As can be seen, the first 2 stages of Spectral-Stitching—which can also be completed in nearly
linear time—are more “symmetric” than those of Spectral-Expanding. More precisely, Spectral-Expanding
emphasizes a single core subgraph Gc and computes all other estimates based on Gc , while Spectral-Stitching
treats each subgraph Gl almost equivalently. This symmetry nature might be practically beneficial when the
acquired data deviate from our assumed random sampling model.

3.2

Theoretical Guarantees: Rings

We start with the performance of our algorithms for rings. This class of graphs—which is spatially invariant—
is arguably the simplest model exhibiting locality structure.
7

1

3.2.1

Minimum Sample Complexity

Encouragingly, the proposed algorithms succeed in achieving the minimum sample complexity, as stated
below.
Theorem 1. Fix θ > 0 and any small  > 0. Let G be a ring Rr with locality radius r, and suppose
m ≥ (1 + ) m∗ ,
where
m∗ =

(5)

n log n
.
2 1 − e−KL(0.5kθ)

(6)

Then with probability approaching one3 , Spectral-Expanding (resp. Spectral-Stitching) converges to the ground
truth within T = O (log n) iterations, provided that r & log3 n (resp. r ≥ nδ for an arbitrary constant δ > 0).
Conversely, if m < (1 − ) m∗ , then the probability of error Pe (ψ) is approaching one for any algorithm
ψ.
Remark 2. When r = n − 1, a ring reduces to a complete graph (or an equivalent Erdős-Rényi model). For
this case, computationally feasible algorithms have been extensively studied [5, 9, 18, 37, 38], most of which
focus only on the scaling results. Recent work [15,39] succeeded in characterizing the sharp threshold for this
case, and it is immediate to check that the sample complexity we derive in (6) matches the one presented
in [15, 39].
Remark 3. Theorem 1 requires r & poly log(n) because each node needs to be connected to sufficiently
many neighbors in order to preclude “bursty” errors. The condition r & log3 n might be improved to a
lower-order poly log (n) term using more refined analyses. When r . log n, one can compute the maximum
likelihood (ML) estimate via dynamic programming [27] within polynomial time.
Theorem 1 uncovers a surprising insensitivity phenomenon for rings: as long as the measurement graph
is sufficiently connected, the locality constraint does not alter the sample complexity limit and the computational limit at all. This subsumes as special cases two regimes that exhibit dramatically different
graph structures: (1) complete graphs, where the samples are taken in a global manner, and (2) rings with
r = O(poly log (n)), where the samples are constrained within highly local neighborhood. In addition, Theorem 1 does not impose any assumption on the ground truth {Xi : 1 ≤ i ≤ n}; in fact, the success probability
of the proposed algorithms is independent of the true community assignment.
Notably, both [13] and [40] have derived general sufficient recovery conditions of SDP which, however,
depend on the second-order graphical metrics of G [14] (e.g. the spectral gap or Cheeger constant). When
applied to rings (or other graphs with locality), the sufficient sample complexity given therein is significantly
larger than the information limit4 . This is in contrast to our finding, which reveals that for many graphs with
locality, both the information and computation limits often depend only upon the vertex degrees independent
of these second-order graphical metrics.
3.2.2

Bottlenecks for Exact Recovery

Before explaining the rationale of the proposed algorithms, we provide here some heuristic argument as to
why n log n samples are necessary for exact recovery and where the recovery bottleneck lies.
Without loss of generality, assume X = [0, · · · , 0]> . Suppose the genie tells us the correct labels of all
nodes except v. Then all samples useful for recovering Xv reside on the edges connecting v and its neighbors,
and there are Poisson(λdv ) such samples. Thus, this comes down to testing between two conditionally
i.i.d. distributions with a Poisson sample size of mean λdv . From the large deviation theory, the ML rule
fails in recovering Xv with probability
n
o
∗
Pe,v ≈ exp −λdv (1 − e−D ) ,
(7)
∗

precisely, the proposed algorithms succeed with probability exceeding 1 − c1 r−9 − C2 exp{−c2 m
(1 − e−D )} for some
n
constants c1 , c2 , C2 > 0.
4 For instance, the sufficient sample complexity given in [13] scales as n log n with h denoting the Cheeger constant. Since
G
hG D ∗
hG = O(1/n) for rings / lines, this results in a sample size that is about n times larger than the information limit.
3 More

8

where D∗ is the large deviation exponent. The above argument concerns a typical error event for recovering
a single node v, and it remains to accommodate all vertices. Since the local neighborhoods of two vertices v
and u are nearly non-overlapping, the resulting typical error events for recovering Xv and Xu become almost
independent and disjoint. As a result, the probability of error of the ML rule ψml is approximately lower
bounded by
n
o
Xn
∗
Pe (ψml ) &
Pe,v ≈ n exp −λdavg (1 − e−D ) ,
(8)
v=1

where one uses the fact that dv ≡ davg . Apparently, the right-hand side of (8) would vanish only if
∗

λdavg (1 − e−D ) > log n.

(9)

Since the total sample size is m = λ · 21 ndavg , this together with (9) confirms the sample complexity lower
bound
n log n
1
= m∗ .
m = λndavg >
2
2 (1 − e−D∗ )

As we shall see, the above error events—in which only a single variable is uncertain—dictate the hardness
of exact recovery.
3.2.3

Interpretation of Our Algorithms

The preceding argument suggests that the recovery bottleneck of an optimal algorithm should also be determined by the aforementioned typical error events. This is the case for both Spectral-Expanding and
Spectral-Stitching, as revealed by the intuitive arguments below. While the intuition is provided for rings,
it contains all important ingredients that apply to many other graphs.
To begin with, we provide an heuristic argument for Spectral-Expanding.
(i) Stage 1 focuses on a core complete subgraph Gc . In the regime where m & n log n, the total number of
samples falling within Gc is on the order of |Vnc | · m ≥ |Vc | log n, which suffices in guaranteeing partial
recovery using spectral methods [29]. In fact, the sample size we have available over Gc is way above
the degrees of freedom of the variables in Gc (which is r).
(ii) With decent initial estimates for Gc in place, one can infer the remaining pool of vertices one by one
using existing estimates together with backward samples. One important observation is that each vertex
is incident to many—i.e. about the order of log n—backward samples. That said, we are effectively
operating in a high signal-to-noise ratio (SNR) regime. While existing estimates are imperfect, the
errors occur only to a small fraction of vertices. Moreover, these errors are in some sense randomly
distributed and hence fairly spread out, thus precluding the possibility of bursty errors. Consequently,
one can obtain correct estimate for each of these vertices with high probability, leading to a vanishing
fraction of errors in total.
(iii) Now that we have achieved approximate recovery, all remaining errors can be cleaned up via local
refinement using all backward and forward samples. For each vertex, since only a vanishingly small
fraction of its neighbors contain errors, the performance of local refinement is almost the same as in
the case where all neighbors have been perfectly recovered.
The above intuition extends to Spectral-Stitching. Following the argument in (i), we see that the spectral
method returns nearly accurate estimates for each of the subgraph Gl induced by Vl , except for the global
phases (this arises because each Gl has been estimated in isolation, without using any information concerning
the global phase). Since any two adjacent Gl and Gl+1 have sufficient overlaps, this allows us to calibrate
V
the global phases for {XiVl : i ∈ Vl } and {Xi l+1 : i ∈ Vl+1 }. Once we obtain approximate recovery for all
variables simultaneously, the remaining errors can then be cleaned up by Stage 3 as in Spectral-Expanding.
We emphasize that the first two stages of both algorithms—which aim at approximate recovery—require
only O (n) samples (as long as the pre-constant is sufficiently large). In contrast, the final stage is the
bottleneck: it succeeds as long as local refinement for each vertex is successful. The error events for this
stage are almost equivalent to the typical events singled out in Section 3.2.2, justifying the informationtheoretic optimality of both algorithms.
9

lines

2

rings

1

(r = n )
0.2

c

m⇤ = c ·

16

n log n
2(1 e D⇤ )

14

4

0.4

0.6

0.8

1

Lm⇤ = c · n log n

c

L=2

12

grids

3

L=3

10
8

lines

2

6

L!1

4

rings

1

2

error rate: p

(r = n )
0.2

0.4

0.6

0.8

0.1

1

0.2

Figure 4: (Left) Minimum sample complexity m∗ vs. locality radius r; (Right) Minimum number Lm∗ of
vertices being measured (including repetition) vs. single-vertex error rate p.

Recovery in Graphs with Locality
3

4

9

10

15

2
5
8 estimates
11
14
t al., 2015)) on a core subgraph induced by Vc , which
yields
1

n,
(0)
Xi

6

7

12

13

16

1

17
18

Figure 5: Labeling / ordering ofothe vertex set for a grid, where the core subgraph consists of the r2 vertices
| j : j <oni,the
(i,bottom
j) 2 E,left.
1  l  Ni,j .

3.3 Theoretical Guarantees: Inhomogeneous Graphs
1,
o
The proposed algorithms are guaranteed to succeed for a much broader class of graphs with locality beyond
(t)
Xj | j : j 6= i, rings,
(i, j) 2
E, 1 those
l  Nthat
, 1 inhomogeneous
i 1 n.
i,j exhibit
including
vertex degrees. The following theorem formalizes this
claim
for two of the most important instances: lines and grids.
r

Theorem 2. Theorem 1 continues to hold for the following families of measurement graphs:
(1) Lines with r = nβ for some constant 0 < β < 1, where

ule: for any sequence s1 , · · · , sk 2 {0, 1}, majority {s1 , · · · , sk } is
m∗ =

max {1/2, β} n log n
;
1 − e−KL(0.5 k θ)

(10)

(2) Grids with r = nβ for some constant 0 < β < 0.5, where

cr
r
r

ments

m∗ =

max {1/2, 4β} n log n
.
1 − e−KL(0.5 k θ)

(11)

Remark 4. Note that both Spectral-Expanding and Spectral-Stitching rely on the labeling / ordering of
the vertex set V. For lines, it suffices to employ the same ordering and core subgraph as for rings. For grids,
6000 8000 10000
we can start by taking the core subgraph to be a subsquare of area r2 lying on the bottom left of the grid,
and then follow a serpentine trajectory running alternately from the left to the right and then back again;
see Fig. 5 for an illustration.

10 by
s recovery in a core complete subgraph; (b) Stage 2 makes a forward pass
samples; (c) Stage 3 refines each Xv by employing all samples incident to v.

log n
as
Remark 5. Careful readers will note that for lines (resp. grids), m∗ does not converge to 2(1−en−KL(0.5kθ)
)
∗
β → 1 (resp. β → 0.5), which is the case of complete graphs. This arises because m experiences a more
rapid drop in the regime where β = 1 (resp. β = 0.5). For instance, for a line with r = γn for some constant
log n
γ > 0, one has m∗ = (1−γ/2)n
.
1−e−KL(0.5kθ)

Theorem 2 characterizes the effect of locality radius upon the sample complexity limit; see Fig. 4 for a
comparison of three classes of graphs. In contrast to rings, lines and grids are spatially varying models due
to the presence of boundary vertices, and the degree of graph inhomogeneity increases in the locality radius
r. To be more concrete, consider, for example, the first davg / log n vertices of a line, which have degrees
around davg /2. In comparison, the set of vertices lying away from the boundary have degrees as large as davg .
This tells us that the first few vertices form a weakly connected component, thus presenting an additional
bottleneck for exact recovery. This issue is negligible unless the size of the weakly connected component
is exceedingly large. As asserted by√Theorem 2, the minimum sample complexity for lines (resp. grids) is
identical to that for rings unless r & n (resp. r & n1/8 ). Note that the curves for lines and grids (Fig. 4) have
distinct hinge points primarily because the vertex degrees of the corresponding weakly connected components
differ.
More precisely, the insights developed in Section 3.2.2 readily carry over here. Since the error probability
of the ML rule is lower bounded by (8), everything boils down to determining the smallest λ (called λ∗ )
satisfying
n

o
Xn
∗
exp −λ∗ dv 1 − e−D
→ 0,
v=1

which in turn yields m =
way.
∗

3.4

1 ∗
2 λ davg n.

The two cases accommodated by Theorem 2 can all be derived in this

Connection to Low-Rank Matrix Completion

One can aggregate all correct parities into a matrix Z = [Zi,j ]1≤i,j≤n such that Zi,j = 1 if Xi = Xj
(l)

and Zi,j = −1 otherwise. It is straightforward to verify that rank (Z) = 1, with each Yi,j being a noisy
measurement of Zi,j . Thus, our problem falls under the category of low-rank matrix completion, a topic
that has inspired a flurry of research (e.g. [41–45]). Most prior works, however, concentrated on samples
taken over an Erdős–RÃ c nyi model, without investigating sampling schemes with locality constraints. One
exception is [46], which explored the effectiveness of SDP under general sampling schemes. However, the
sample complexity required therein increases significantly as the spectral gap of the measurement graph
drops, which does not deliver optimal guarantees. We believe that the approach developed herein will shed
light on solving general matrix completion problems from samples with locality.

4

Extension: Beyond Pairwise Measurements

The proposed algorithms are applicable to numerous scenarios beyond the basic setup in Section 2.1. This
section presents two important extension beyond pairwise measurements.

4.1

Sampling with Nonuniform Weight

In many applications, the sampling rate is nonuniform across different edges; for instance, it might fall
off with distance between two incident vertices. In the haplotype phasing application, Fig. 7(a) gives an
example of a distribution of the separation between mate-paired reads (insert size). One would naturally
wonder whether our algorithm works under this type of more realistic models.
More precisely, suppose the number of samples over each (i, j) ∈ E is independently generated obeying
ind

Ni,j ∼ Poisson (λwi,j ) ,

(12)

where wi,j > 0 incorporates a sampling rate weighting for each edge. This section focuses on lines / grids
/ rings for concreteness, where we impose the following assumptions in order to make the sampling model
more “symmetric”:
11

(i) Lines / grids: wi,j depends only on the Euclidean distance between vertices i and j;
(ii) Rings: wi,j depends only on i − j (mod n).
Theorem 3. Theorems 1-2 continue to hold under the above nonuniform sampling model, provided that
max(i,j)∈E wi,j
min(i,j)∈E wi,j is bounded.
Theorem 3 might be surprising at first glance: both the performance of our algorithms and the fundamental limit depend only on the weighted average of the vertex degrees, and are insensitive to the degree
distributions. This can be better understood by examining the three stages of Spectral-Expanding and
Spectral-Stitching. To begin with, Stages 1-2 are still guaranteed to work gracefully, since we are still operating in a high SNR regime irrespective of the specific values of {wi,j }. The main task thus amounts to
ensuring the success of local clean-up. Repeating our heuristic treatment in Section 3.2.2, one sees that the
probability of each singleton error event (i.e. false recovery of Xv when the genie already reveals the true
labels of other nodes) depends only on the average number of samples incident to each vertex v, namely,
X
X
E [Nv ] :=
E [Nv,j ] =
λwv,j .
j

j:(v,j)∈E

Due to the symmetry assumptions on {wi }, the total sample size m scales linearly with E [Nv ], and hence
the influence of {wi } is absorbed into m and ends up disappearing from the final expression.
Another prominent example is the class of small-world graphs. In various human social networks, one
typically observes both local friendships and a (significantly lower) portion of long-range connections, and
small-world graphs are introduced to incorporate this feature. To better illustrate the concept, we focus on
the following spatially-invariant instance, but it naturally generalizes to a much broader family.
• Small-world graphs. Let G be a superposition of a complete graph G0 = (V, E0 ) and a ring G1 with
connectivity radius r. The sampling rate is given by
(
Poisson (w0 ) , if (i, j) ∈ E0 ;
ind.
Ni,j ∼
Poisson (w1 ) , else.
We assume that

w0 n2
w1 nr

= O (1), in order to ensure higher weights for local connections.

Theorem 4. Theorem 1 continues to hold under the above small-world graph model, provided that r & log3 n.

4.2

Beyond Pairwise Measurements

In some applications, each measurement may cover more than two nodes in the graph. In the haplotype
phasing application, for example, a new sequencing technology called 10x [47] generates barcodes to mark
reads from the same chromosome (maternal or paternal), and more than two reads can have the same
barcode. For concreteness, we suppose the locality constraint is captured by rings, and consider the type of
multiple linked samples as follows.
• Measurement (hyper)-graphs. Let G0 = (V, E0 ) be a ring Rr , and let G = (V, E) be a hyper-graph
such that (i) every hyper-edge is incident to L vertices in V, and (ii) all these L vertices are mutually
connected in G0 .
ind.

• Noise model. On each hyper-edge e = (i1 , · · · , iL ) ∈ G, we obtain Ne ∼ Poisson (λ) multi-linked
(l)
(l)
samples {Ye | 1 ≤ l ≤ Ne }. Conditional on Ne , each sample Ye is an independent copy of
(
(Zi1 , · · · , ZiL ) ,
with prob. 0.5,
Ye =
(13)
(Zi1 ⊕ 1, · · · , ZiL ⊕ 1) , else,
where Zi is a noisy measurement of Xi such that
(
Xi ,
with probability 1 − p;
Zi =
Xi ⊕ 1, otherwise.
12

(14)

Here, p represents the error rate for measuring a single vertex. For the pairwise samples considered
before, one can think of the parity error rate θ as P {Zi ⊕ Zj 6= Xi ⊕ Xj } or, equivalently, θ = 2p(1−p).
We emphasize that a random global phase is incorporated into each sample (13). That being said, each
sample reveals only the relative similarity information among these L vertices, without providing further
information about the absolute cluster membership.
Since Algorithm 1 and Algorithm 3 operate only upon pairwise measurements, one alternative is to
convert each L-wise sample Ye = (Yi1 , · · · , YiL ) into L2 pairwise samples of the form Yij ⊕ Yil (for all j 6= l),
and then apply the spectral methods on these parity samples. In addition, the majority voting procedure
specified in Algorithm 1 needs to be replaced by certain local maximum likelihood rule as well, in order to
take advantage of the mutual data correlation within each L-wise measurement. The modified algorithms
are summarized in Algorithms 4 and 5. Interestingly, these algorithms are still information-theoretically
optimal, as asserted by the following theorem.
Theorem 5. Fix L ≥ 2, and consider Algorithms 4 and 5 . Theorem 1 continues to hold under the above
L-wise sampling model, with m∗ replaced by
m∗ :=
Here,

(

n log n
.
L 1 − e−D(P0 ,P1 )

P0 = (1 − p)Binomial (L − 1, p) + pBinomial (L − 1, 1 − p) ;
P1 = pBinomial (L − 1, p) + (1 − p) Binomial (L − 1, 1 − p) .

(15)

Here, the Chernoff information D(P0 , P1 ) can be expressed in closed form as
(L−1 
)
r
on
o
X L − 1 n
L−i
i
L−i−1
i+1
D(P0 , P1 ) = − log
pi (1 − p)
+ (1 − p) pL−i
pi+1 (1 − p)
+ (1 − p)
pL−i−1
.
i
i=0
(16)
In particular, when L = 2, this reduces to5 D(P0 , P1 ) = KL (0.5 k θ) for θ := 2p(1 − p), which matches our
results with pairwise samples.
Interestingly, D(P0 , P1 ) enjoys a very simple asymptotic limit as L scales, as stated in the following
lemma.
Lemma 1. Fix any 0 < p < 1/2. The Chernoff information D(P0 , P1 ) given in Theorem 5 obeys
lim D (P0 , P1 ) = KL (0.5 k p) .

L→∞

(17)

Proof. See Appendix F.1.
Remark 6. The asymptotic limit (17) admits a simple interpretation. Consider the typical event where only
X1 is uncertain and X2 = · · · = Xn = 0. Conditional on Z1 , the L−1 parity samples (Z1 ⊕ Z2 , · · · , Z1 ⊕ ZL )
are i.i.d., which reveals accurate information about Z1 ⊕ 0 in the regime where L → ∞ (by the law of large
number). As a result, the uncertainty arises only because Z1 is a noisy version of X1 , which behaves like
passing X1 through a binary symmetric channel with crossover probability p. This essentially boils down
to distinguishing between Bernoulli (p) (when X1 = 0) and Bernoulli (1 − p) (when X1 = 1), for which the
associated Chernoff information is known to be KL (0.5 k p).
With Theorem 5 in place, we can determine the benefits of multi-linked sampling. To enable a fair
comparison, we evaluate the sampling efficiency in terms of Lm∗ rather than m∗ , since Lm∗ captures the
total number of vertices (including repetition) one needs to measure. As illustrated in Fig. 4, the sampling
log n
efficiency improves as L increases, but there exists a fundamental lower barrier given by 1−en−KL(0.5kp)
. This
lower barrier, as plotted in the black curve of Fig. 4, corresponds to the case where L is approaching infinity.
5 This

follows since, when L = 2,
 q

n p
o
D(P0 , P1 ) = − log 2 ((1 − p)2 + p2 ) (2p (1 − p)) = − log 2 (1 − θ) θ = KL (0.5 k θ) .

13

Algorithm 4 : Spectral-Expanding for multi-linked samples

1. Break each L-wise sample Ye = (Yi1 , · · · , YiL ) into L2 pairwise samples of the form Yij ⊕ Yil (for all
j 6= l), and run spectral method (Algorithm 2) on a core subgraph induced by Vc using these
(0)
parity samples. This yields estimates Xj , 1 ≤ j ≤ |Vc |.
2. Progressive estimation: for k = |Vc | + 1, · · · , n,
n
o
(0)
Xk ← local − MLnX (0) |1≤i<ko Ye(l) | e = (i1 , · · · , iL ) with iL = k, 1 ≤ l ≤ Ne .
i

3. Successive local refinement: for t = 0, · · · , T − 1,
n
o
(t+1)
Xk
← local − MLnX (t) |i6=ko Ye(l) | k ∈ e, 1 ≤ l ≤ Ne ,
i

1 ≤ k ≤ n.

(T )

4. Output Xk , 1 ≤ k ≤ n.
L

Here, local − MLX {·} represents the local maximum likelihood rule: for any sequence s1 , · · · , sN ∈ {0, 1} ,
(
PN
P{sj |Xk =1,Xi =Zi (1≤i<k)}
1, if
j=1 log P{sj |Xk =0,Xi =Zi (1≤i<k)} ≥ 0,
local − ML{Zi |1≤i<k} {s1 , · · · , sN } =
0, else,
and
local − ML{Zi |i6=k} {s1 , · · · , sN } =

(
PN
1, if
j=1 log
0, else.

P{sj |Xk =1,Xi =Zi (i6=k)}
P{sj |Xk =0,Xi =Zi (i6=k)}

≥ 0,

Algorithm 5 : Spectral-Stitching for multi-linked samples

1. Break each L-wise sample Ye = (Yi1 , · · · , YiL ) into L2 pairwise samples of the form Yij ⊕ Yil (for all
(0)
j 6= l). Run Steps 1-2 of Algorithm 3 using these pairwise samples to obtain estimates Xj , 1 ≤ j ≤ n.
(T )

2. Run Step 3 of Algorithm 4 and output Xk , 1 ≤ k ≤ n.

14

1

Success rate

0.8

Success rate

1

r=4
r = 18
r = 317
r = 5624

0.6
0.4

0.8
0.6
r=4
r = 18
r = 317
r = 5624

0.4
0.2

0.2
0
0

1
2
3
Number of measurements
normalized by information theoretic limit

0
0

4

1
2
3
4
5
Number of measurements
normalized by information theoretic limit

(a)

(b)
1

r=4
r = 18
r = 317
r = 5624

0.8
0.6

Success rate

Success rate

1

0.4
0.2
0
0

θ = 0.01
θ = 0.10
θ = 0.15

0.8
0.6
0.4
0.2
0
0

1
2
3
4
Number of measurements
normalized by information theoretic limit

1
2
3
4
Number of measurements
normalized by Information Theoretic limit

(c)

(d)

1

1

0.8

0.8

0.6

information
theoretic
limit

0.4
0.2

Success rate

Success rate

Figure 6: Empirical success rate of Spectral-Expanding for: (a) Rings Rr ; (b) Small world graphs; (c) Rings
Rr with non-uniform sampling rate; and (d) Rings R18 with varied measurement error rate θ. Here, the
x-axis is the sample size m normalized by the information limit m∗ .

0.6

information
theoretic
limit

0.4
0.2

0
0
10
20
30
Number of mate−pair measurements per SNP

(a)

(b)

0
0

10
20
30
Number of measurements per SNP

(c)

Figure 7: (a) Insert size distribution [48]; (b) Performance of Spectral-Expanding on a simulation of haplotype
phasing from mate pair reads; (c) Performance of Spectral-Expanding on a simulation of haplotype phasing
from 10x like reads.

15

Time (seconds/run)

r = n0.2
3.47

r = n0.25
3.55

r = n0.5
6.45

r = n0.75
58.4

Table 1: The time taken to run Spectral-Expanding on a MacBook Pro equipped with a 2.9 GHz Intel Core
i5 and 8GB of memory over rings Rr , where n = 100, 000, θ = 10% and m = 1.5m∗ . All experiments
converge to the truth within 2 iterations.

5

Numerical Experiments

To verify the practical applicability of the proposed algorithms, we have conducted simulations in various
settings. All these experiments focused on graphs with n = 100, 000 vertices, and used an error rate of
θ = 10% unless otherwise noted. For each point, the empirical success rates averaged over 10 Monte Carlo
runs are reported.
(a) Regular rings. We ran Algorithm 1 on rings Rr for various values of locality radius r (Fig. 6(a)), with
the runtime reported in Table 1;
(b) Small-world graphs. We ran Algorithm 1 on small-world graphs, where the aggregate sampling rate
for Rr is chosen to be on the same order as that for the complete graph (Fig. 6(b));
(c) Rings with nonuniform sampling weight. We ran Algorithm 1 for rings with nonuniform sampling
rate (Fig. 6(c)). Specifically, the distance between two vertices involved in a parity sample is drawn
according to Poisson(r/2);
(d) Rings with different error rates. We varied the error rate θ for rings with r = 18 = n0.25 , and plotted
the empirical success rate (Fig. 6(d)).
Chromosome number
n
m
L·m
Switch error rate

1
176477
547154
3618604
3.45

2
191829
574189
3858642
3.26

3
163492
504565
3360817
2.91

4
168206
490476
3303015
2.93

5
156352
475430
3144785
2.97

6
152397
467606
3117837
2.77

7
134685
414557
2712355
3.53

Chromosome number
n
m
L·m
Switch error rate

8
128970
394285
2601225
2.96

9
101243
318274
2042234
3.46

10
121986
379992
2476832
3.17

11
114964
357550
2313387
3.29

12
112500
362396
2323349
3.49

13
86643
269773
1719035
2.93

14
76333
247339
1562680
3.18

Chromosome number
n
m
L·m
Switch error rate

15
65256
210779
1322975
3.49

16
73712
231418
1486718
3.73

17
59788
194980
1216416
4.57

18
68720
214171
1345967
3.01

19
56933
183312
1168408
4.93

20
53473
171949
1071688
3.70

21
34738
105313
660016
3.75

22
34240
102633
640396
5.07

Table 2: The parameters and performance of Spectral-Stitching when run on the NA12878 data-set from
10x-genomics [49].
We have also simulated a model of the haplotype phasing problem by assuming that the genome has a
SNP periodically every 1000 base pairs. The insert length distribution, i.e. the distribution of the genomic
distance between the linking reads, is given in Fig. 6(c) for Illumina reads, and a draw from Poisson(3.5)
truncated within the interval 1, · · · , 9 is a reasonable approximation for the number of SNPs between two
measured SNPs. We then ran the simulation on the rings R9 , with non-uniform sampling weight. Using the
16

Figure 8: The switch error rates of Spectral-Stitching when run on the NA12878 data-set from 10x-genomics
[49].
nominal error rate of p = 1% for the short reads, the error rates of the measurements is 2p(1 − p) ≈ 2%.
The empirical performance is shown in Fig. 6(d).
Additionally, we have simulated reads generated by 10x-Genomics [47] , which corresponds to the model
in Section 4. Each measurement consists of multiple linked reads, which is generated by first randomly
picking a segment of length 100 SNPs (called a fragment) on the line graph and then generating Poisson(9)
number of linked reads uniformly located in this segment. The noise rate per read is p = 0.01. The empirical
result is shown in Fig. 6(e). The information theoretic limit is calculated using Theorem 5, with L set to
infinity (since the number of vertices involved in a measurement is quite large here).
To evaluate the performance of our algorithm on real data, we ran Spectral-Stitching for Chromosomes
1-22 on the NA12878 data-set made available by 10x-Genomics [49]. The nominal error rate per read is
p = 1%, and the average number of SNPs touched by each sample is L ∈ [6, 7]. The number of SNPs n
ranges from 34240 to 191829, with the sample size m from 102633 to 574189. Here, we split all vertices into
overlapping subsets of size W = 100. The performance is measured in terms of the switch error rate, that is,
the fraction of positions where we need to switch the estimate to match the ground truth. The performance
on Chromosomes 1-22 is reported in Tab. 2 and Fig. 8.

6

Discussion

We have presented two efficient algorithms that are information theoretically optimal. Rather than resorting
to a “global” method that attempts recovery of all nodes all at once, the proposed algorithms emphasize local
subgraphs whose nodes are mutually well connected, and then propagate information across different parts
of the graph. This way we are able to exploit the locality structure in a computationally feasible manner.
This paper leaves open numerous directions for further investigation. To begin with, the current work
concentrates on the simplest setup where only two communities are present. It would be of interest to extend
the results to the case with M > 2 communities, which naturally arises in many applications including
haplotype phasing for polyploid species [50]. Furthermore, what would be the information and computation
limits in the regime where the number M of communities scales with n? In fact, there often exists a
computational barrier away from the information limit when the measurement graph is drawn from the
Erdős-Rényi model for large M (e.g. [51]). How will this computational barrier be influenced by the locality
structure of the measurement graph? In addition, the present theory operates under the assumption that L
is a fixed constant, namely, each multi-linked measurement entails only a small number of samples. Will the
proposed algorithms still be optimal if L is so large that it has to scale with n?
More broadly, it remains to develop a unified and systematic approach to accommodate a broader family
of graphs beyond the instances considered herein. In particular, what would be an optimal recovery scheme
if the graph is far from spatially-invariant or if there exist a few fragile cuts? Finally, as mentioned before,
it would be interesting to see how to develop more general low-rank matrix completion paradigms, when the
revealed entries come from a sampling pattern that exhibits locality structure.

17

A

Preliminaries

Before continuing to the proofs, we gather a few facts that will be useful throughout. First of all, recall
that the maximum likelihood (ML) decision rule achieves the lowest Bayesian probability of error, assuming
uniform prior over two hypotheses of interest. The resulting error exponent is determined by the Chernoff
information, as given in the following lemma.
Lemma 2. Fix any  > 0. Suppose we observe a collection of Nz random variables Z = {Z1 , · · · , ZNz }
that are i.i.d. given Nz . Consider two hypotheses H0 : Zi ∼ P0 and H1 : Zi ∼ P1 for two given probability
measures P0 and P1 . Assume that the Chernoff information D∗ = D (P0 , P1 ) > 0 and the alphabet of Zi are
1 (z)
both finite and fixed, and that maxz P
P0 (z) < ∞.
(a) Conditional on Nz , one has


P1 (Z)
∗
exp {− (1 + ) Nz D } ≤ P0
(18)
≥ 1 Nz ≤ exp {−Nz D∗ } ,
P0 (Z)
where the lower bound holds when Nz is sufficiently large.
(b) If Nz ∼ Poisson (N ), then


n

o
n

o
∗
P1 (Z)
−D ∗
≥ 1 ≤ exp −N 1 − e−D
,
exp − (1 + ) N 1 − e
≤ P0
P0 (Z)

(19)

where the lower bound holds when N is sufficiently large.
Proof. See Appendix F.2.
We emphasize that the best achievable error exponent coincides with the Chernoff information D∗ when
∗
the sample size is fixed, while it becomes 1 − e−D —which is sometimes termed the Chernoff-Hellinger
divergence—when the sample size is Poisson distributed.
The next result explores the robustness of the ML test. In particular, we control the probability of error
when the ML decision boundary is slightly shifted, as stated below.
Lemma 3. Consider any  > 0, and let N ∼ Poisson (λ).
(a) Fix any 0 < θ < 0.5. Conditional on N , draw N independent samples Z1 , · · · , ZN such that Zi ∼
Bernoulli (θ), 1 ≤ i ≤ N . Then one has
(N
)


n

o
X
1
1−θ
P
Zi ≥ N − λ
≤ exp  · 2 log
λ exp −λ 1 − e−KL(0.5kθ) .
(20)
2
θ
i=1
P1 (z)
(b) Let P0 and P1 be two distributions obeying maxz P
< ∞. Conditional on N , draw N independent
0 (z)
samples Zi ∼ P0 , 1 ≤ i ≤ N . Then one has


N
X

n

o
∗
P1 (Zi )
P0
log
≥ −λ
≤ exp (λ) exp −λ 1 − e−D
,
(21)


P0 (Zi )
j=1

where D∗ = D (P0 , P1 ) denotes the Chernoff information between P0 and P1 .
Proof. See Appendix F.3.

Further, the following lemma develops an upper bound on the tail of Poisson random variables.
Lemma 4. Suppose that N ∼ Poisson (λ) for some 0 <  < 1. Then for any c1 > 2e, one has




c1 λ
c1 λ
P N≥
≤
2
exp
−
.
2
log 1
Proof. See Appendix F.4.
18

Additionally, our analysis relies on the well-known Chernoff-Hoeffding inequality [52, Theorem 1, Eqn
(2.1)].
Lemma 5 (Chernoff-Hoeffding Inequality). Suppose Z1 , · · · , Zn are independent Bernoulli random
variables with mean E [Zi ] ≤ p. Then for any 1 > q ≥ p, one has

 X
n
1
Zj ≥ q ≤ exp {−nKL (q k p)} ,
P
j=1
n
where KL (q k p) := q log

q
p

+ (1 − q) log

1−q
1−p .

We end this section with a lower bound on the KL divergence between two Bernoulli distributions.
Fact 1. For any 0 ≤ q ≤ τ ≤ 1,
KL (τ k q) := τ log
Proof. By definition,
KL (τ k q)

τ
1−τ
+ (1 − τ ) log
q
1−q
(i)

≥

(ii)

≥

where (i) follows since log

B

1
1−q

τ log

≥ τ log (τ /q) − τ.

τ
+ (1 − τ ) log (1 − τ )
q

τ log (τ /q) − τ,

≥ 0, and (ii) arises since (1 − τ ) log (1 − τ ) ≥ − (1 − τ ) τ ≥ −τ .

Performance Guarantees of Spectral-Expanding

The analyses for all the cases follow almost identical arguments. In what follows, we separate the proofs
into two parts: (1) the optimality of Spectral-Expanding and Spectral-Stitching, and (2) the minimax lower
bound, where each part accommodates all models studied in this work.
We start with the performance guarantee of Spectral-Expanding in this section. Without loss of generality,
we will assume X1 = · · · = Xn = 0 throughout this section. For simplicity of presentation, we will focus on
the most challenging boundary case where m  n log n, but all arguments easily extend to the regime where
m  n log n.

B.1

Stage 1 gives approximate recovery for Gc

This subsection demonstrates that the spectral method (Algorithm 2) is successful in recovering a portion
1 − o (1) of the variables in Vc with high probability, as stated in the following lemma.

Lemma 6. Fix θh > 0.i Suppose that G = (V, E) is a complete graph and the sample size m & n log n. The
(0)
estimate X (0) = Xi
returned by Algorithm 2 obeys
1≤i≤n

n
o
min kX (0) − Xk0 , kX (0) + Xk0 = o (n)

(22)


with probability exceeding 1 − O n−10 .

Proof. See Appendix F.6.


Remark 7. Here, 1 − O n−10 can be replaced by 1 − O (n−c ) for any other positive constant c > 0.

Remark 8. It has been shown in [29, Theorem 1.6] that a truncated version of the spectral method returns
reasonably good estimates even in the sparse regime (i.e. m  n). Note that truncation is introduced
in [29, Theorem 1.6] to cope with the situation in which some rows of the sample matrix are “over-represented”.
This becomes unnecessary in the regime where m & n log n, since the number of samples incident to each
vertex concentrates around Θ (log n), thus precluding the existence of “over-represented” rows.
19

According to Lemma 6, Stage 1 accurately recovers (1 − o (1))|Vc | variables in Vc modulo some global
phase, as long as
λ|Vc |2 & |Vc | · log n.
Since λ  m/n2 and |Vc |  davg , this condition is equivalent to
m & n log n,
which falls within our regime of interest. Throughout the rest of the section, we will assume without loss of
generality that
Vc
n
o
1 X
(0)
1 Xi 6= Xi = o (1) ,
|Vc | i=1

i.e. the first stage obtains approximate recovery along with the correct global phase.

B.2

Stage 2 yields approximate recovery for V\Vc

For concreteness, we start by establishing the achievability for lines and rings, which already contain all
important ingredients for proving the more general cases.
B.2.1

Lines / rings

We divide all vertices in V\Vc into small groups {Vi }, each consisting of  log3 n adjacent vertices6 :

Vi := |Vc | + (i − 1)  log3 n + 1, · · · , |Vc | + i ·  log3 n ,

where  > 0 is some arbitrarily small constant. In what follows, we will control the estimation errors
happening within each group. For notational simplicity, we let V0 := Vc . An important vertex set for the
progressive step, denoted by V→i , is the one encompassing all vertices preceding and connected to Vi ; see
Fig. 9 for an illustration.
The proof is recursive, which mainly consists in establishing the claim below. To state the claim, we need
to introduce a collection of events as follows
n
n
o
o

(0)
A0 :=
at most a fraction of progressive estimates Xj : j ∈ Vc is incorrect ;
2
n
n
o
o
(0)
Ai :=
at most a fraction  of progressive estimates Xj : j ∈ Vi is incorrect , i ≥ 1.

Lemma 7. For any i ≥ 0, conditional on A0 ∩ · · · ∩ Ai , one has

As a result, one has


P {Ai+1 | A0 ∩ · · · ∩ Ai } ≥ 1 − O n−10 .
P {∩i≥0 Ai }

≥


1 − O n−9 .

(23)

(24)

Apparently, A0 holds with high probability; see the analysis for Stage 1. Thus, if (23) holds, then (24)
follows immediately from the union bound. In fact, (24) suggests that for any group Vi , only a small fraction
of estimates obtained in this stage would be incorrect, thus justifying approximaterecovery
for this stage.

davg
Moreover, since the neighborhood N (v) of each node v ∈ Vi is covered by at most O |Vi | groups, the event


d
∩i≥0 Ai immediately suggests that there are no more than O ( · |Vi |) O |Vavg
= O (davg ) errors occurring
i|
to either the neighborhood N (v) or the backward neighborhood N (v) ∩ V→i . This observation will prove
useful for analyzing Stage 3, and hence we summarize it in the following lemma.

6 Note that the errors occurring to distinct vertices are statistically dependent in the progressive estimation stage. The
approach we propose is to look at a group of vertices simultaneously, and to bound the fraction of errors happening within this
group. In order to exhibit sufficiently sharp concentration, we pick the group size to be at least  log3 n. A smaller group is
possible via more refined arguments.

20

|

Vi

{z

V!i

}

Vi

Vi

Vi |1

|

{z

V!i

}

Vi

| V {z
}
ViV!i
ii 1 V
i V2!iVi V1i
V!i V
|

{z

Vi
V{z
i V
2i }V!i
|
{z
Vi
|
X

|

Vi

{z

(a)
V!i

X

V!i
{z
X

1

}

⇥

|

V ii i 2V2 !i
} 1 VV
Vi

}

Vi

Vi

Vi

1

|2

1Vi

Vi
{z

X

{z

Vi

}

{z

Vi

}

Vi

|

V!ii
V
u

1

V!i
}

u

Vi
V
} | i 2 {z

1

2

2i
V

1

V!i
}

2

Vi

1

Vi

2

1

Vi

2

2

Vi

(b)
Figure 9: (a) Illustration of Vi , V→i , and Bu , where Bu is the set of samples lying on the dark blue edges.
(b) Illustration of Bugood and Bubad , which correspond to the set of samples lying on the set of blue edges
and black edges, respectively. Here, the symbol X (resp. ×) indicates that the associated node has been
estimated correctly (resp. incorrectly).
Lemma 8. There are at most O (davg ) errors occurring to either the neighborhood N (v) or the backward
neighborhood N (v) ∩ V→i .
The rest of the section is devoted to establish the claim (23) in Lemma 7.
Proof of Lemma 7. As discussed above, it suffices to prove (23) (which in turn justifies (24)). The following argument is conditional on A0 ∩ · · · ∩ Ai and all estimates for V0 ∪ · · · ∪ Vi ; we shall suppress the
notation by dropping this conditional dependence whenever it is clear from the context.
(0)
Consider
n any vertex u ∈ Vi+1 . Ino the progressive estimation step, each Xu relies on the preceding
(0)
estimates Xj | j : j < u, (j, u) ∈ E , as well as the set Bu of backward samples incident to u, that is,
n
o
(l)
Bu := Yu,j | j < u, (j, u) ∈ E, 1 ≤ l ≤ Nu,j ;

see Fig. 9(a). We divide Bu into two parts
(l)

(0)

• Bugood : the set of samples Yu,j in Bu such that (i) Xj

= Xj , and (ii) j ∈ V→(i+1) ;

• Bubad : the remaining samples Bu \Bugood ;
and set

Nugood := Bugood

and Nubad := Bubad .

In words, Bugood is associated with those preceding estimates in V→(i+1) that are consistent with the truth,
while Bubad entails the rest of the samples that might be unreliable. See Fig. 9(b) for an illustration. The
purpose of this partition is to separate out Bubad , which only accounts for a small fraction of all samples.
We now proceed to analyze the majority voting procedure which, by definition, succeeds if the total votes
favoring the truth exceeds 21 Nugood + Nubad . To preclude the effect of Bubad , we pay particular attention to
the part of votes obtained over Bugood ; that is, the partial score
X
(0)
(l)
scoregood
:=
Xj ⊕ Yu,j .
u
(l)

good
Yu,j ∈Bu

It is self-evident to check that the above success condition would hold if
scoregood
u

1 1


1
1
1
Nugood + Nubad − Bubad = Nugood − Nubad ,
<
1
2
2
2

1

21

1

1

and we further define the complement event as


1 good 1 bad
good
Du := scoreu
≥ Nu
− Nu
.
2
2
The main point to work with Du is that conditional on all prior estimates in V→(i+1) , the Du ’s are independent
across all u ∈ Vi+1 .
We claim that
(25)

P {Du } = exp {−Θ (log n)} := Pe,1 .

If this claim holds, then we can control the number of incorrect estimates within the group Vi+1 via the
Chernoff-Hoeffding inequality. Specifically,





 1

 1
n
o
X
X
1
1
(0)
≤
P
P
1
X
=
6
X
≥
1
{D
}
≥
u
u
u
  log3 n
  log3 n
log2 n 
log2 n 
u∈Vi+1
u∈Vi+1






(a)
1
1
3
3
E [1 {Du }]
≤ exp − log n · KL
Pe,1
≤ exp − log n · KL
log2 n
log2 n



(b)
1
1
≤ exp − log3 n ·
log
−1
2
log n
Pe,1 log2 n




1
(c)
= exp −Θ  log2 n < O
,
n10

where (a) follows from Lemma 5, (b) arises from Fact 1, and (c) is a consequence of (25). This reveals that
the fraction of incorrect estimates for Vi is vanishingly small with high probability, thus establishing the
claim (23).
Finally, it remains to prove (25). To this end, we decouple Du into two events:




c0 log n
1 true 1 c0 log n
good
P {Du } ≤ P Nubad ≥
+
P
score
≥
(26)
N
−
u
2 u
2 log 1
log 1
for some universal constant c0 > 0. Recall that each edge is sampled at a Poisson rate λ 
log n
davg ,

m
|E0 |



n log n
ndavg



and that the average number of samples connecting u and other nodes in Vi+1 is atmost λ · O (davg )

(recalling our assumption that r & log3 n). On the event A0 ∩ · · · ∩ Ai , the number of wrong labels in V→(i+1)
is O (du ), and hence


E Nubad ≤ O (λdu ) ≤ c2 log n
(27)
for some constant c2 > 0. This further gives




E Nugood ≥ λc3 du − E Nubad ≥ (1 − c4 ) c3 λdu

for some constants c3 , c4 > 0. Thus, Lemma 4 and the inequality (27) taken collectively yield




c1 c2 log n
c1 c2 log n
≤
2
exp
−
P Nubad ≥
2
log 1

for any c1 > 2e. In addition, in view of Lemma 3, there exists some function ξ˜ (·) such that


n



o
1 true 1 c0 log n
−D ∗
˜
P scoregood
≥
N
−
≤
exp
−
(1
−
o
(1))
1
−
ξ
()
c
λd
1
−
e
n
3
u
u
2 u
2 log 1
=

exp {−Θ (log n)} ,

22

where ξ˜ () is independent of n and vanishes as  → 0. Putting these bounds together reveals that: when
n
ˆ
λ  log
davg and c0 = c1 c2 , there exists some function ξ () independent of n such that





 λd
c1 c2 log n
avg
−D ∗
˜
1−e
+ exp − (1 − on (1)) 1 − ξ ()
(26) ≤ 2 exp −
2
2
= exp {−Θ (log n)} := Pe,1 ,


(28)

where ξˆ () vanishes as  → 0. This finishes the proof.
B.2.2

Beyond lines / rings

The preceding analysis only relies on very few properties of lines / rings, and can be readily applied to many
other graphs. In fact, all arguments continue to hold as long as the following assumptions are satisfied:
1. In G, each vertex v (v > |Vc |) is connected with at least Θ(davg ) vertices in {1, · · · , v − 1} by an edge;


d
=
2. For any v ∈ Vi (i ≥ 1), its backward neighborhood N (v) ∩ V→i is covered by at most O |Vavg
|
i


davg
O  log
distinct groups among V1 , · · · , Vi−1 .
3n

In short, the first condition ensures that the information of a diverse range of prior vertices can be propagated
to each v, whereas the second condition guarantees that the estimation errors are fairly spread out within
the backward neighborhood associated with each node.
We are now in position to look at grids, small-world graphs, as well as lines / rings with nonuniform
weights.

(a) It is straightforward to verify that the choices of Vc and the ordering of V suggested in Section 3.3
satisfy Conditions 1-2, thus establishing approximate recovery for grids.
(b) Suppose

max(i,j)∈E wi,j
min(i,j)∈E wi,j

is bounded. Define the weighted degree as
dw
v :=

X

wi,v

i:(i,v)∈E

P w
1
and let the average weighted degree be dw
dv . Then all arguments continue to hold if dv and
avg := n
w
,
respectively.
This
reveals approximate recovery for lines / rings /
and
d
davg are replaced by dw
avg
v
grids under sampling with nonuniform weight.
(c) The proof for small-world graphs follows exactly the same argument as for rings.
(d) For the case with multi-linked samples, we redefine several metrics as follows:
n
o
(l)
– Bu : the set of backward samples Ye | u ∈ e, j < u for all other j ∈ e, 1 ≤ l ≤ Ne , where e
represents the hyper-edge;
(l)

(0)

– Bugood : the set of samples Ye in Bu such that (i) Xj
j ∈ V→(i+1) for all j ∈ e and j 6= u;

= Xj for all j ∈ e and j 6= u, and (ii)

– Bubad : the remaining samples Bu \Bugood .

– We also need to re-define the score scoregood
as
u
n
o
(l)
(0)
P Ye | Xu = 1, Xi = Xi (i ∈ e, i 6= u)
X
o
scoregood
:=
log n
u
(l)
(0)
P
Y
|
X
=
0,
X
=
X
(i
∈
e,
i
=
6
u)
(l)
good
e
u
i
i
Y ∈B
e

u

with the decision boundary replaced by 0 and the event Du replaced by


Du := scoregood
≥ 0 − smax · |Bubad | = scoregood
≥ −smax Nubad .
u
u
23

Here, smax indicates the maximum possible likelihood ratio for each L-wise sample:
smax := max log
Ye ,{Zi }

P {Ye | Xu = 1, Xi = Zi (i ∈ e, i 6= u)}
.
P {Ye | Xu = 0, Xi = Zi (i ∈ e, i 6= u)}

With these metrics in place, all proof arguments for the basic setup carry over to the multi-linked
sample case.

B.3

Stage 3 achieves exact recovery

We now turn to the last stage, and the goal is to prove that X (t) converges to X within O (log n) iterations.
Before proceeding, we introduce a few more notations that will be used throughout.
• For any vertex v, denote by N (v) the neighborhood of v in G, and let S (v) be the set of samples that
involve v;
• For any vector Z = [Z1 , · · · , Zn ]
follows

>

and any set I ⊆ {1, · · · , n}, define the `0 norm restricted to I as
X
kZk0,I :=
1 {Zi 6= 0} .
i∈I

• Generalize the definition of the majority vote operator such that

>

majority (Z) = [majority1 (Z1 ), · · · , majorityn (Zn )]
obtained by applying majorityv (·) component-wise, where
(
1, if Zv ≥ 21 |S (v) |;
majorityv (Zv ) :=
0, else.

• Let VZ (resp. VX ) denote the local voting scores using Z = [Zi ]1≤i≤n (resp. X = [Xi ]1≤i≤n = 0) as
the current estimates, i.e. for any 1 ≤ u ≤ n,
X
(l)
(VZ )u =
Yi,u ⊕ Zi ;
(29)
(l)

Yi,u ∈S(u)

(VX )u

=

X

(l)

(l)
Yi,u ∈S(u)

Yi,u ⊕ Xi =

X

(l)

Yi,u .

(30)

(l)
yi,u ∈S(u)

With these notations in place, the iterative procedure can be succinctly written as
X (t+1) = majority (VX (t) ) .
The main subject of this section is to prove the following theorem.
Theorem 6. Consider any 0 <  ≤ 0 , where 0 is some sufficiently small constant. Define
n
o
n
Z := Z ∈ {0, 1} | ∀v : kZ − Xk0,N (v) ≤ dv .

(31)

Then with probability approaching one,

majority (VZ ) ∈ Z 12  ,

∀Z ∈ Z and ∀ ∈



1
dmax



, 0 .

Remark 9. When the iterate falls within the set Z (cf. (31)), there exist only a small number of errors
occurring to the neighborhood of each vertex. This essentially implies that (i) the fraction of estimation
errors is low; (ii) the estimation errors are fairly spread out instead of clustering within the neighborhoods
of a few nodes.
24

Remark 10. This is a uniform result: it holds regardless of whether Z is statistically independent of the
samples Y or not. This differs from many prior results (e.g. [17]) that employ fresh samples in each stage in
order to decouple the statistical dependency.
Note that the subscript of Z indicates the fraction of estimation errors allowed in an iterate. According
to the analyses for the the preceding stages, Stage 3 is seeded with some initial guess X (0) ∈ Z for some
arbitrarily small constant  > 0. This taken collectively with Theorem 6 gives rise to the following error
contraction result: for any t ≥ 0,
kX (t+1) − Xk0,N (v) = kmajority (VX (t) ) − Xk0,N (v) ≤

1
kX (t) − Xk0,N (v) ,
2

1 ≤ v ≤ n.

(32)

This reveals the geometric convergence rate of X (t) , namely, X (t) converges to the truth within O (log n)
iterations, as claimed.
The rest of this section is devoted to proving Theorem 6. We will start by proving the result for any
fixed candidate Z ∈ Z independent of the samples, and then generalize to simultaneously accommodate all
Z ∈ Z . Our strategy is to first quantify VX (which corresponds to the score we obtain when only a single
vertex is uncertain), and then control the difference between VX and VZ . We make the observation that all
entries of VX are strictly below the decision boundary, as asserted by the following lemma.
Lemma 9. Fix any small constant δ > 0, and suppose that m  n log n. Then one has
1
1
|S (u)| − δ log n = |S (u)| − δ · O (λdu ) ,
1≤u≤n
2
2


−D ∗
with probability exceeding 1 − C1 exp −c1 m
for some constants C1 , c1 > 0, provided that the
n 1−e
following conditions are satisfied:
(1) Rings with r & log2 n:

n log n
;
m > 1 + ξ (δ)
2 1 − e−KL(0.5 k θ)
(VX )u <

(2) Lines with r = nβ for some constant 0 < β < 1:



1
n log n
;
m > 1 + ξ (δ) max β,
2 1 − e−KL(0.5 k θ)
(3) Lines with r = γn for some constant 0 < γ ≤ 1:



n log n
1
m > 1 + ξ (δ) 1 − γ
;
2
1 − e−KL(0.5 k θ)

(4) Grids with r = nβ for some constant 0 < β < 1/2:



1
n log n
m > 1 + ξ (δ) max 4β,
;
2 1 − e−KL(0.5 k θ)
(5) Small-world graphs:


m > 1 + ξ (δ)

n log n
;
2 1 − e−KL(0.5 k θ)

In all these cases, ξ (·) is some function independent of n satisfying ξ (δ) → 0 as δ → 0. Here, we allow
max(i,j)∈E wi,j
Cases (1), (2) and (4) to have nonuniform sampling weight over different edges, as long as min(i,j)∈E
wi,j is
bounded.
Proof. See Appendix F.7.
It remains to control the difference between VX and VZ :
∆Z := VZ − VX .
25

Specifically, we would like to demonstrate that most entries of ∆Z are bounded in magnitude by δ log n (or
δ · O (λdu )), so that most of the perturbations are absolutely controlled. To facilitate analysis, we decouple
the statistical dependency by writing
VZ = FZ + BZ ,
where FZ represents the votes using only forward samples, namely,
X
(l)
Yi,u ⊕ Zi ,
1 ≤ u ≤ n.
(FZ )u =
(l)

i>u, Yi,u ∈S(u)

This is more convenient to work with since the entries of FZ (or BZ ) are jointly independent. In what follows,
we will focus on bounding FZ , but all arguments immediately apply to BZ . To simplify presentation, we
also decompose VX into two parts VX = FX + BX in the same manner.
Note that the vth entry of the difference
∆F := FZ − FX

(33)

is generated by those entries from indices in N (v) satisfying Zv 6= Xv . From the assumption (31), each ∆F
v
(1 ≤ v ≤ n) is dependent on at most O(dv ) non-zero entries of Z − X, and hence on average each ∆F
v is
only affected by O (λ · davg ) samples. Moreover, each non-zero entry of Z − X is bounded in magnitude by
a constant. This together with Lemma 4 yields that: for any sufficiently large constant c1 > 0,


c1 λdavg
≥
P ∆F
≤ 2 exp {−Θ (c1 λdavg )} ≤ 2n−c2 ,
(34)
i
log 1
provided that λdavg & log n (which is the regime of interest), where c2 = Θ (c1 ) is some absolute positive
c1 λdavg
constant. In fact, for any index i, if ∆F
i ≥ log 1 , then picking sufficiently small  > 0 we have


∆F
i  λdavg

of

∆F
i  log n,

and hence (FZ )i and (FX )i become sufficiently close.
The preceding bound only concerns a single component. In order to obtain overall control, we introduce
a set of independent indicator variables {ηi (Z)}:
(
c1 λdavg
1, if ∆F
i ≥ log(1/) ,
ηi (Z) :=
0, else.
For any 1 ≤ v ≤ n, applying Lemma 5 gives



1 X
P
ηi (Z) ≥ τ
≤

 dv
i∈N (v)

n

o
exp −dv KL τ k max E [ηi (Z)]
i

n

≤ exp −dv τ log

o
τ
−
τ
,
−c
2n 2

where the last line follows from Fact 1 as well as (34). For any τ ≥ 1/n,
τ log
indicating that

τ
− τ & τ log n,
2n−c2



1 X

P
ηi (Z) ≥ τ
≤ exp {−c3 τ davg log n}
 dv

i∈N (v)

for some universal constant c3 > 0. If we pick  > 0 and τ > 0 to be sufficiently small, we see that with high
probability most of the entries have
c1 λdavg
∆F
 λdavg .
i <
log 1
26

We are now in position to derive the results in a more uniform fashion. Suppose that dmax = Kdavg .
 Kd
Kdavg
When restricted to Z , the neighborhood of each v can take at most Kd
2 avg different possible values.
avg
1
If we set τ = 4 , then in view of the union bound,



  Kd 
1 X
avg
P ∃Z ∈ Z s.t.
ηi (Z) ≥ τ ≤
2Kdavg exp {−c3 τ davg log n}


dv
Kdavg
i∈N (v)

Kdavg

≤ (2Kdavg )

exp {−c3 τ davg log n}


1
≤ exp {(1 + o (1)) Kdavg log n} exp − c3 davg log n
4
 


1
≤ exp −
c3 − (1 + o (1)) K davg log n .
4
o
n
n
Since Z, X ∈ {0, 1} , it suffices to consider the case where  ∈ div | 1 ≤ v ≤ n, 1 ≤ i ≤ dv , which has

at most O n2 distinct values. Set c3 to be sufficiently large and apply the union bound
 (over both v and
−10
,
) to deduce that: with probability exceeding 1 − exp (−Θ (davg log n)) ≥ 1 − O n


c1 λdavg
1
card i ∈ N (v) : ∆F
1 ≤ v ≤ n,
(35)
≤ dv ,
i ≥
1
4
log 
1
1
holds simultaneously for all Z ∈ Z and all  ≥ dmax
 davg
.
F
The uniform bound (35) continues to hold if ∆ is replaced by ∆B . Putting these together suggests that
with probability exceeding 1 − exp (−Θ (d log n)),


2c1 λdavg
card i ∈ N (v) : |(∆Z )i | ≥
log 1






c1 λdavg
c1 λdavg
B
∆F i ≥
∆
≥
≤ card i ∈ N (v) :
+
card
i
∈
N
(v)
:
i
log 1
log 1
1
1≤v≤n
≤ dv ,
2

1
holds simultaneously for all Z ∈ Z and all  ≥ dmax
.
1
Taking δ to be 2c1 / log  in (74), we see that all but 12 dv entries of VZ = VX + ∆Z at indices from
N (v) exceed the voting boundary. Consequently, the majority voting yields

kmajority (VZ ) − Xk0,N (v) ≤

1
dv ,
2

1≤v≤n

or, equivalently,
majority (VZ ) ∈ Z 21  ,

∀Z ∈ Z

as claimed.
When it comes to the multi-linked reads, we need to make some modification to the vectors defined above.
Specifically, we define the score vector VZ and VX to be
n
o
(l)
P Ye | Xu = 1, Xi = Zi (for all i 6= u and u ∈ e)
X
o,
(VZ )u =
log n
(36)
(l)
P
Y
|
X
=
0,
X
=
Z
(for
all
i
=
6
u
and
u
∈
e)
(l)
e
u
i
i
Ye ∈S(u)
n
o
(l)
P Ye | Xu = 1, Xi = 0 (for all i 6= u and u ∈ e)
X
o,
(37)
(VX )u =
log n
(l)
P
Y
|
X
=
0,
X
=
0
(for
all
i
=
6
u
and
u
∈
e)
(l)
e
u
i
Y ∈S(u)
e

27

and replace the majority voting procedure as

(
1, if Zv ≥ 0;
majorityv (Zv ) :=
0, else.

With these changes in place, the preceding proof extends to the multi-linked sample case with little modification, as long as L remains a constant. We omit the details for conciseness.

C

Performance Guarantees of Spectral-Stitching

o
n
We start from the estimates XjVl : j ∈ Vl obtained in Stage 1. Combining Lemma 6 and the union bound,
we get




o
o
n
n
X
X
1
= o (1) , l = 1, 2, · · ·
1 XjVl ⊕ 1 6= Xj
min
1 XjVl 6= Xj ,


|Vl |
j∈Vl

j∈Vl

with probability exceeding 1 − O (n−c ) for any constant c > 0. In other words, we achieve approximate
recovery—up to some global phase—for each vertex group Vl . The goal of Stage 2 is then to calibrate
these estimates so as to make sure all groups enjoy the same global phase. Since each group suffers from a
fraction o(1) nof errors and oany two
n adjacent groupsoshare O(|Vl |) vertices, we can easily see that two groups
of estimates

XjVl : j ∈ Vl

V

and Xj l−1 : j ∈ Vl−1
X

have positive correlation, namely,

V

j∈Vl ∩Vl−1

XjVl ⊕ Xj l−1 ≤

1
|Vl ∩ Vl−1 | ,
2

only
when they share
n
o the same global phase. As a result, there are at most o(n) occurring to the estimates
(0)
Xi | 1 ≤ i ≤ n obtained in Stage 2. Moreover, the way we choose Vl ensures that the neighborhood Nv


d
of each vertex v is contained within at most O |Vavg
groups, thus indicating that
1|


X n
o X n
o
1
(0)
(0)
min
1 Xj 6= Xj ,
1 Xj ⊕ 1 6= Xj
= o (1) , v = 1, · · · , n;


|Nv |
j∈Nv

j∈Nv

that is, the estimation errors are fairly spread out across the network. Finally, Spectral-Expanding and
Spectral-Stitching employ exactly the same local refinement stage, and hence the proof for Stage 3 in SpectralExpanding readily applies here. This concludes the proof.

D

Minimax Lower Bound

This section contains the proof for the converse parts of Theorems 1-5; that is, the minimax probability of
error inf ψ Pe (ψ) → 1 unless m ≥ (1 − )m∗ in all of these theorems.

D.1

Pairwise samples with uniform weight

We begin with the simplest sampling model: pairwise measurements with uniform sampling rate at each
edge, which are the scenarios considered in Theorems 1-2. The key ingredient to establish the minimax lower
bounds is to prove the following lemma.
ind.

Lemma 10. Fix any constant  > 0, and suppose that Ni,j ∼ Poisson (λ) for all (i, j) ∈ E. Consider any
vertex subset U ⊆ V with |U| ≥ n , and denote by d˜ the maximum degree of the vertices lying within U. If
λd˜ ≤ (1 − )

log |U|
,
1 − e−D∗

then the probability of error inf ψ Pe (ψ) → 1 as n → ∞.
28

(38)

Proof. See Appendix F.5.
We are now in position to demonstrate how Lemma 10 leads to tight lower bounds. In what follows, we
let davg denote the average vertex degree in G.

• Rings. When G = (V, E) is a ring Rr with connectivity radius r, set U = V = {1, · · · , n} and fix
any small constant  > 0. It is self-evident that d˜ = davg . Applying Lemma 10 leads to a necessary
recovery condition
log n
.
(39)
λdavg > (1 − )
1 − e−D∗
Since m = λ|E| = 21 λndavg , this condition (39) is equivalent to
m > (1 − ) ·

n log n
.
2 (1 − e−D∗ )

• Lines with r = nβ for some constant 0 < β < 1. Take U = {1, · · · , r} for some sufficiently small
constant 0 <  < β, which obeys |U| = nβ ≥ n for large n and d˜ = (1 + O ()) davg /2. In view of
Lemma 10, a necessary recovery condition is
log |U|
,
1 − e−D∗
1−
β log n + log 
>
·
.
1 + O ()
1 − e−D∗

λd˜ > (1 − )

1
λdavg
2
In addition, if we pick U = V, then d˜ = davg . Lemma 10 leads to another necessary condition:
⇐⇒

log n
.
1 − e−D∗
Combining these conditions and recognizing that  can be arbitrarily small, we arrive at the following
necessary recovery condition


1
1
n log n
λdavg > (1 − ) max β,
.
(40)
2
2 1 − e−D∗
λdavg > (1 − ) ·

When β < 1, the edge cardinality obeys |E| = (1 + o(1))ndavg /2, allowing us to rewrite (40) as


1
1−
n log n
max β,
.
m = λ|E| >
1 + o(1)
2 1 − e−D∗

• Lines with r = γn for some constant 0 < γ ≤ 1. Take U = {1, · · · , r} for some sufficiently small
constant  > 0, which obeys |U| = γn ≥ n for large n and d˜ = (1 + O ()) r. Lemma 10 reveals the
following necessary recovery condition:
λd˜ > (1 − )

log |U|
1 − e−D∗

1−
log n + log (γ)
·
.
1 + O ()
1 − e−D∗
On the other hand, the total number of edges in G is given by





1 + o (1)  2
1r
1
2
|E| =
n − (n − r) = (1 + o (1)) nr 1 −
= (1 + o (1)) nr 1 − γ .
2
2n
2
⇐⇒

λr >

This taken collectively with (41) establishes the necessary condition


1
m = λ|E| = (1 + o (1)) λnr 1 − γ
2


1
n log n
> (1 − O ()) 1 − γ
,
2
1 − e−D∗

which completes the proof for this case by recognizing that  can be arbitrary.
29

(41)

(42)

• Grids with r = nβ for some constant 0 < β < 1. Consider a sub-square of edge length r lying
in the bottom left corner of the grid, and let U consist of all 2 r2 vertices residing withinthe subsquare. This obeys |U| = 2 n2β > n for large n and small , and we also have d˜ = 1 + O 2 davg /4.
According to Lemma 10, a necessary recovery condition is
λd˜ > (1 − )
or, equivalently,

log |U|
1 − e−D∗

1
1−
2 (β log n + log )
.
λdavg >
·
4
1 + O (2 )
1 − e−D∗

In addition, by taking U = V one has d˜ = davg ; applying Lemma 10 requires
λdavg > (1 − ) ·

log n
1 − e−D∗

for exact recovery. Putting these two conditions together we derive
λdavg > (1 − O ()) max {8β, 1}
which is equivalent to

n log n
,
1 − e−D∗



1
n log n
m = λ|E| > (1 − O ()) max 4β,
2 1 − e−D∗

since |E| = (1 + o (1))ndavg /2.

D.2

Pairwise samples with nonuniform weight

The preceding analyses concerning the minimax lower bounds can be readily extended to the sampling model
with nonuniform weight, which is the focus of Theorem 3. To be precise, defining the weighted degree of any
node v as
X
dw
wi,v ,
(43)
v :=
i:(i,v)∈E

we can generalize Lemma 10 as follows.
Lemma 11. Suppose that

max(i,j)∈E wi,j
min(i,j)∈E wi,j

is bounded. Then Lemma 10 continues to the hold for the sampling
model with nonuniform weight, provided that d˜ is defined as the maximum weighted degree within V1 and
ind.
that Ni,j ∼ Poisson(λwi,j ) for all (i, j) ∈ E.
Proof. See Appendix F.5.
This lemma allows us to accommodate the following scenarios, as studied in Theorem 3.
• Lines / rings / grids under nonuniform sampling. In view of Lemma 11, the preceding proof
in Section D.1 continues to hold in the presence
Pnof nonuniform sampling weight, provided that davg is
replaced with the average weighted degree n1 v=1 dw
v.

• Small-world graphs. The proof for rings is applicable for small-world graphs as well, as long as davg
is replaced by the average weighted degree.

D.3

Multi-linked samples

Finally, the above results immediately extend to the case with multi-linked samples.

30

Lemma 12. Consider the model with multi-linked samples introduced in the main text, and suppose that L
and  > 0 are both fixed constants. Let U ⊆ V be any vertex subset obeying |U| ≥ n , and denote by d˜ the
maximum degree (defined with respect to the hyper-edges) of the vertices within U. If
λd˜ ≤ (1 − )

log |U|
,
1 − e−D∗

(44)

then the probability of error inf ψ Pe (ψ) → 1 as n → ∞.
Proof. See Appendix F.5.
ind.

Lemma 13. Fix any constant  > 0, and suppose that Ni,j ∼ Poisson (λ) for all (i, j) ∈ E. Consider any
vertex subset U ⊆ V with |U| ≥ n , and denote by d˜ the maximum degree of the vertices lying within U. If
λd˜ ≤ (1 − )

log |U|
,
1 − e−D∗

(45)

then the probability of error inf ψ Pe (ψ) → 1 as n → ∞.
When specialized to rings, setting U = {1, · · · , n} with d˜ = davg gives rise to the necessary condition
λdavg > (1 − )

log n
,
1 − e−D∗

(46)

where davg represents the average number of hyper-edge degree. Since each hyper-edge covers L vertices,
accounting for the over-count factor gives m = L1 nλdavg , allowing us to rewrite (46) as
m > (1 − )

n log n
.
L (1 − e−D∗ )

This establishes the converse bound in the presence of multi-linked samples.

E

Chernoff Information for Multi-linked Samples

Suppose now that each vertex v is involved in Nv multi-linked samples or, equivalently, Nv (L − 1) pairwise
samples. Careful readers will note that these parity samples are not independent. The key step in dealing
with such dependency is not to treat them as Nv (L − 1) independent samples, but instead Nv independent
groups. Thus, it suffices to compute the Chernoff information associated with each group, as detailed below.
Without loss of generality, suppose only X1 is uncertain and X2 = · · · = Xn = 0. Consider a multi-linked
sample that covers X1 , · · · , XL . According to our model, each L-wise sample is an independent copy of (13).
Since we never observe the global phase in any sample, a sufficient statistic for Ye is given by
Ỹe = (Z1 ⊕ Z2 , Z1 ⊕ Z3 , · · · , Z1 ⊕ ZL ) .
By definition (3), the Chernoff information D∗ is the large-deviation exponent when distinguishing between the conditional distributions of
Ỹe | (X1 , · · · , XL ) = (0, · · · , 0)

and Ỹe | (X1 , · · · , XL ) = (1, · · · , 0) ,

which we discuss as follows.
• When X1 = · · · = XL = 0:
– if Z1 = 0 (which occurs with probability 1 − p), then Ỹe ∼ Binomial (L − 1, p);

– if Z1 = 1 (which occurs with probability p), then Ỹe ∼ Binomial (L − 1, 1 − p);
• When X1 = 1 and X2 = · · · = XL = 0:
31

(47)

– if Z1 = 0 (which occurs with probability p), then Ỹe ∼ Binomial (L − 1, p);
– if Z1 = 1 (which occurs with probability 1 − p), then Ỹe ∼ Binomial (L − 1, 1 − p).
To summarize, one has
Ỹe | (X1 , · · · , XL ) = (0, 0, · · · , 0)

∼ (1 − p) Binomial (L − 1, p) + pBinomial (L − 1, 1 − p) := P0 ;

Ỹe | (X1 , · · · , XL ) = (1, 0, · · · , 0)

∼ pBinomial (L − 1, p) + (1 − p) Binomial (L − 1, 1 − p) := P1 .

To derive a closed-form expression, we note that a random variable W0 ∼ P0 obeys




L−1 i
L−1
L−i−1
i
P0 (W0 = i) = (1 − p)
p (1 − p)
+p
(1 − p) pL−i−1
i
i


o
L−1 n i
L−i
i
=
p (1 − p)
+ (1 − p) pL−i .
i

Similarly, if W1 ∼ P1 , then

P1 (W1 = i)

=




o
L − 1 n i+1
L−i−1
i+1 L−i−1
.
p
(1 − p)
+ (1 − p)
p
i

(48)

(49)

By symmetry (i.e. P0 (W0 = i) = P1 (W1 = L − 1 − i)), one can easily verify that (3) is attained when
τ = 1/2, giving
(L−1
)
Xp
D (P0 , P1 ) = − log
P0 (W0 = i) P1 (W1 = i)
i=0

(L−1 
)
r
on
o
X L − 1 n
L−i
i
L−i−1
i+1
= − log
pi (1 − p)
+ (1 − p) pL−i
pi+1 (1 − p)
+ (1 − p)
pL−i−1
. (50)
i
i=0

F
F.1

Proof of Auxiliary Lemmas
Proof of Lemma 1

For notational convenience, set
rn
on
o
L−i
i
L−i−1
i+1 L−i−1
pi (1 − p)
+ (1 − p) pL−i
pi+1 (1 − p)
+ (1 − p)
p
.
bi :=
For any i <

− log L, one can verify that

L
2

i

p (1 − p)

L−i

i

L−i

+ (1 − p) p

(

L−i

i

= p (1 − p)

1+



p
1−p

= (1 + oL (1)) pi (1 − p)

and
i+1

p

L−i−1

(1 − p)

i+1

+ (1 − p)

p

L−i−1

=p

i+1

L−i−1

(1 − p)

L−2i )

L−i

(

1+

= (1 + oL (1)) pi+1 (1 − p)



p
1−p

L−i−1

L−2i−2 )

.

These identities suggest that

 rn
L/2−log L 
L/2−log L 
on
o
X
X
L−1
L−1
L−i
L−i−1
bi = (1 + oL (1))
pi (1 − p)
pi+1 (1 − p)
i
i
i=0
i=0

L/2−log L 
X
p
L−1 i
L−i−1
= (1 + oL (1)) p (1 − p)
p (1 − p)
i
i=0
p
= (1 + oL (1)) p (1 − p),
32

(51)

where the last line makes use of the following fact.
Fact 2. Fix any 0 < p < 1/2. Then one has
L/2−log L 

X
i=0


L−1 i
L−i−1
p (1 − p)
= 1 − oL (1) .
i

Proof. To simplify writing, we concentrate on the case where L is even. From the binomial theorem, we see
that
L−1
X L − 1
L−i−1
pi (1 − p)
= 1.
(52)
i
i=0
 i
PL−1
L−i−1
Hence, it suffices to control i=L/2−log L+1 L−1
p (1 − p)
. To this end, we first make the observation
i
that


i

L/2−log L−2 
X
L−1
p
L−1 i
L−1
L−i−1
(1 − p)
p (1 − p)
≤ (2 log L)
max
i
1−p
i
i≥ L
2 −log L+1
i=L/2−log L+1




 L2 −log L+1
L−1
p
L−1
≤ (2 log L) ·
(1 − p)
L/2
1−p
o
(i) n
L
2 log L−3
−log L+1
≤ (2 log L) (1 − p)
· 2L (p (1 − p)) 2
h
iL
(ii)
1
− log L
≤ oL (1) · 2 (p (1 − p)) 2 L
= oL (1) ,


L−1

2 log L−3

where (i) comes from the inequalities L/2 ≤ 2L−1 ≤ 2L , and (ii) holds because log L (1 − p)
oL (1). The last identity is a consequence of the inequality
p
p (1 − p) < 1/2
(∀p < 1/2),
L
− log
L

→ 1 (L → ∞) and hence
p
1
− log L
− log L
(p (1 − p)) 2 L = p(1 − p) (p (1 − p)) L < 1/2.

as well as the fact that (p (1 − p))

On the other hand, the remaining terms can be bounded as
L−1
X

i= L
2 +log L−1

=



L−1 i
L−i−1
p (1 − p)
=
i

L−1
X

i= L
2 +log L−1

X L − 1 
i
pL−i−1 (1 − p) =
i
i=0

L
2 −log L

= oL (1) ·




L−1
L−i−1
pi (1 − p)
L−i−1


L−2i−1
X L − 1 
p
L−i−1
i
p (1 − p)
·
i
1−p
i=0

L
2 −log L

X L − 1
L−i−1
pi (1 − p)
.
i
i=0

L
2 −log L

Putting the above results together yields

L/2−log L
L−1
X
X
1=
+
i=0

= (1 + oL (1))

L/2−log L−2

+

i= L
2 +log L−1

L/2−log L 

X
i=0

(53)

X

i=L/2−log L+1





 L − 1 pi (1 − p)L−i−1
i


L−1 i
L−i−1
p (1 − p)
+ oL (1) ,
i
33

=

which in turn gives
L/2−log L 

X
i=0


o
L−1 n i
L−i−1
p (1 − p)
= 1 − oL (1)
i

as claimed.
Following the same arguments, we arrive at
L−1
X

i=L/2+log L




p
L−1
bi = (1 + oL (1)) p (1 − p).
i

Moreover,
L/2+log L−1

X

i=L/2−log L+1



L−1
bi ≤
i

L/2+log L−1

X

i=L/2−log L+1




o
L−1 n i
L−i
i
p (1 − p)
+ (1 − p) pL−i
i



o
L − 1 n i+1
L−i−1
i+1 L−i−1
p
(1 − p)
+ (1 − p)
p
+
i
i=L/2−log L+1


 L/2+log
o
X L−1 L − 1 n
L−i−1
=O
pi (1 − p)


i
L/2+log L−1

X

i=L/2−log L+1

= oL (1) ,

where the last line follows the same step as in the proof of Fact 2 (cf. (53)). Taken together these results
lead to



L/2+log L  
L−1
L−1
L/2−log
X L−1
X
X
X L − 1
L−1
bi =
+
+
bi


i
i
i=0
i=0
i=L/2+log L−1
i=L/2−log L
p
= 2 (1 + oL (1)) p (1 − p),
thus demonstrating that

n
o
p
D (P0 , P1 ) = − log 2 (1 + oL (1)) p (1 − p) = (1 + oL (1)) KL (0.5kp) .

F.2

Proof of Lemma 2

Let M be the alphabet size for Zi . The standard method of types result (e.g. [53, Chapter 2] and [28, Section
11.7-11.9]) reveals that


n 
o
1

P1 (Z)
∗
exp
−
1
+
N
D
≤
P
≥
1
N
≤ exp {−Nz D∗ } ;
(54)
z
0
z
M
2
P
(Z)
0
(Nz + 1)
here, the left-hand side holds for sufficiently large Nz , while the right-hand side holds for arbitrary Nz
(see [54, Exercise 2.12] or [55, Theorem 1] and recognize the convexity of the set of types under consideration).
1
− 12 Nz D∗ for
Moreover, since D∗ > 0 and M are fixed, one has (N +1)
M = exp (−M log (Nz + 1)) ≥ exp
z
any sufficiently large Nz , thus indicating that


P1 (Z)
P0
≥ 1 Nz ≥ exp {− (1 + ) Nz D∗ }
(55)
P0 (Z)
as claimed.
34

We now move on to the case where Nz ∼ Poisson (N ). Employing (55) we arrive at




∞
X
P1 (Z)
P1 (Z)
≥1
=
≥ 1 Nz = l
P0
P (Nz = l) P0
P0 (Z)
P0 (Z)
l=0
∞
X

≥

l=Ñ

N l e−N
exp {− (1 + ) lD∗ }
l!

(57)

∞
X
N0l exp (−N0 )
l!

e−(N −N0 )

=

(56)

(58)

l=Ñ

∗

for any sufficiently large Ñ , where we have introduced N0 := N e−(1+)D . Furthermore, taking Ñ = log N0
we obtain
∞
X
N0l
exp (−N0 )
l!

1−

=

l=Ñ

Ñ
X
Nl

0

l=0

l!



≥ 1 − Ñ + 1

exp (−N0 ) ≥ 1 −


N0Ñ

Ñ
X

N0l exp (−N0 )

l=0

exp (−N0 )

1 − (log N0 + 1) N0log N0 exp (−N0 ) = 1 − oN (1)

=

≥ 0.5

as long as N is sufficiently large. Substitution into (58) yields





∗
P1 (Z)
≥1
≥ 0.5e−(N −N0 ) ≥ exp − (1 + ) N 1 − e−(1+)D
.
P0
P0 (Z)

(59)

This finishes the proof of the lower bound in (19) since  > 0 can be arbitrary.
Additionally, applying the upper bound (54) we derive
(56) ≤

∞
X
N l e−N

l!

l=0




∗
∗
· e−lD = exp −N 1 − e−D
,

establishing the upper bound (19).

F.3

Proof of Lemma 3

We start with the general case, and suppose that the Chernoff information (3) is attained by τ = τ ∗ ∈ [0, 1].
It follows from the Chernoff bound that

τ ∗ 
P1 (Zi )
)
(
) Qk E
( N
k
P
0
i=1
P0 (Zi )
X
X
P1 (Zi )
P1 (Zi )
= P0 τ ∗
log
P0
≥ −λ N = k
≥ −τ ∗ · λ ≤
log
∗
P0 (Zi )
P0 (Zi )
exp (−τ · λ)
i=1
i=1
"
#!
τ ∗ k
P1 (Zi )
∗
= exp (τ · λ) EP0
P0 (Zi )
X
k
∗
∗
= exp (τ ∗ · λ)
P01−τ (z) P11−τ (z)
z

≤

This suggests that
(N
)
X
P1 (Zi )
P0
log
≥ −λ
P0 (Zi )
i=1

exp (λ) exp (−kD∗ ) .

= P0

(

N
X

P1 (Zi )
log
≥ −λ N = k
P0 (Zi )
i=1

)

≤ exp (λ) EN ∼Poisson(λ) [exp (−N D∗ )]
n

o
∗
= exp (λ) exp −λ 1 − e−D
,
35

P {N = k}

where the last identity follows from the moment generating function of Poisson random variables. This
establishes the claim for the general case.
When specialized to the Bernoulli case, the log-likelihood ratio is given by
log

θ
1−θ
P1 (Zi )
= I {Zi = 0} log
+ I {Zi = 1} log
P0 (Zi )
1−θ
θ
1−θ
= {2I {Zi = 1} − 1} log
.
θ

When 0 < θ < 1/2, this demonstrates the equivalence between the following two inequalities:
N
X

log

i=1

Recognizing that

F.4

PN

i=1

P1 (Zi )
≥ −λ
P0 (Zi )

Zi =

PN

i=1

N
X

⇐⇒

i=1

I {Zi = 1} ≥

λ
1
.
N−
2
2 log 1−θ
θ

I {Zi = 1} and replacing  with  · 2 log

1−θ
θ ,

we complete the proof.

Proof of Lemma 4

For any constant c1 ≥ 2e,


c1 λ
P N≥
log 1

=

X

c λ

1
k≥ log(1/)

(i)

≤

(ii)

≤

X

(k/e)

X

 √ k
e 
c1

c λ

1
k≥ log(1/)

c λ

1
k≥ log(1/)



k

2 exp − log

=

2 exp −

c1 λ
2





=

k

c λ

1
k≥ log(1/)

X

k

(λ)

≤



X

P {N = k} =

c λ

1
k≥ log(1/)



(λ)
exp (−λ)
k!

eλ
k

k

≤

X

eλ

c λ

1
k≥ log(1/)

c1 λ
log(1/)

!k

c1 λ
 √  log(1/)
e 
≤ 2
c1

(iii)

c1 1
·√
e




c1 λ
log 1





≤ 2 exp − log



1
√




c1 λ
log 1



,

a
√
where (i) arises from the elementary inequality a! ≥ ae , (ii) holds because  log 1 ≤  holds for any
P
K
a
0 <  ≤ 1, and (iii) follows due to the inequality k≥K ak ≤ 1−a
≤ 2aK as long as 0 < a ≤ 1/2.

F.5

Proof of Lemmas 10-12

(1) We start by proving Lemma 10, which contains all ingredients for proving Lemmas 11-12. First of all, we
demonstrate that there are many vertices in U that are isolated in the subgraph induced by U. In fact, let
|U |
U0 be a random subset of U of size log
3 n . By Markov’s inequality, the number of samples with two endpoints
lying in U0 —denoted by NU0 —is bounded above by




1
1
˜
NU0 . log n · E [λ · |E (U0 , U0 )|] . λ
|E (U, U)| log n . λ
|U| d log n
log6 n
log6 n
(i)

.

|U|
= o (|U0 |)
log4 n

with high probability, where E(U, Ũ) denotes the set of edges linking U and Ũ, and (i) follows from the
assumption (38). As a consequence, one can find (1 − o (1)) |U0 | vertices in U0 that are involved in absolutely
no sample falling within E (U0 , U0 ). Let U1 be the set of these isolated vertices, which obeys
|U1 | = (1 − o (1)) |U0 | =

(1 − o (1)) |U|
|U|
≥
log3 n
2 log3 n

36

(60)

for large n. We emphasize that the discussion so far only concerns the subgraph induced by U, which is
independent of the samples taken over E U, U .
Suppose the ground truth is Xi = 0 (1 ≤ i ≤ n). For each vertex v ∈ U1 , construct a representative
singleton hypothesis X v such that
(
1, if i = v,
v
Xi =
0, else.
Let P0 (resp. Pv ) denote the output distribution given X = 0 (resp. X = X v ). Assuming a uniform
prior over all candidates, it suffices to study the ML rule which achieves the best error exponent. For
each v ∈ U1 , since it is isolated in U1 , all information useful for differentiating X = X v and X = 0 falls
within the positions v × U0 , which in total account for at most d˜ entries. The main point is that for any
v, u ∈ U
samples over v × U0 and u × U0 are statistically independent, and hence the
n1 , the corresponding
o
(Y )
events PPv0 (Y
≥
1
are
independent
conditional on U1 .
)
v∈U1

We now consider the probability of error conditional on U1 . Observe that Pv (Y ) and P0 (Y ) only differ
over those edges incident to v. Thus, Lemma 2 suggests that


n

o
∗
Pv (Y )
≥ 1 ≥ exp − (1 + o (1)) λd˜ 1 − e−D
P0
P0 (Y )
o
n
(Y )
≥
1
gives
for any v ∈ U1 . The conditional independence of the events PPv0 (Y
)
Pe (ψml ) ≥
≥
≥
≥





Y 
Pv (Y )
Pv (Y )
P0 ∃v ∈ U1 :
≥1 =1−
≥1
1 − P0
P0 (Y )
P0 (Y )
v∈U1
n
h

io
|U1 |
∗
1 − 1 − exp − (1 + o (1)) λd˜ 1 − e−D

n
h

io |U3|
∗
2 log n
1 − 1 − exp − (1 + o (1)) λd˜ 1 − e−D

h

i |U| 
∗
,
1 − exp − exp − (1 + o (1)) λd˜ 1 − e−D
2 log3 n

(61)
(62)
(63)

where (62) comes from (60), and the last inequality follows since 1 − x ≤ exp (−x).
With (63) in place, we see that ML fails with probability approaching one if
n

o |U|
∗
exp − (1 + o (1)) λd˜ 1 − e−D
→ ∞,
log3 n
which would hold under the assumption (38).
(2) Now we turn to Lemma 11. Without loss of generality, it is assumed that wi,j = Θ (1) for all (i, j) ∈ E.
The preceding argument immediately carries over to the sampling model with nonuniform weight, as long
as all vertex degrees are replaced with the corresponding weighted degrees (cf. (43)).
(3) Finally, the preceding argument remains valid for proving Lemma 12 with minor modification. Let
|U |
U0 be a random subset of U of size log
3 n , denote by EU0 the collection of hyper-edges with at least two
endpoints in U0 , and let NU0 represent the number of samples that involve at least two nodes in U0 . When
L is a fixed constant, applying Markov’s inequality one gets
!
 
2


L
1
1
˜ log n
NU0 . log n · E [λ · |EU0 |] . λ
|E
|
log
n
.
λ
|U|
d
U
2
log3 n
log6 n
(i)

.

|U|
= o (|U0 |)
log4 n

with high probability, where d˜ denotes the maximum vertex degree (defined w.r.t. the hyper-edges) in U.
That said, there exist (1 − o (1)) |U0 | vertices in U0 that are involved in absolutely no sample falling within
37

EU0 , and if we let U1 be the set of these isolated vertices, then
|U1 | = (1 − o (1)) |U0 | =

|U|
(1 − o (1)) |U|
≥
3
log n
2 log3 n

(64)

for large n. Repeating the remaining argument in Part (1) finishes the proof.

F.6

Proof of Lemma 6

To begin with, set λ̃ = 1 − exp (−λ), which satisfies 1 ≥ λ̃ & log n/n under the assumption of this lemma.
Then the sample matrix A generated in Algorithm 2 obeys
i
h
io
 n h (1)
(1)
E [A] = λ̃ 11> − I E Yi,j = 0 − E Yi,j = 1
= λ̃ (1 − 2θ) 11> − λ̃ (1 − 2θ) I,

(65)

where the first term of (65) is the dominant component. Moreover, we claim for the time being that the
fluctuation Ã := A − E[A] obeys
p
(66)
kÃk . λ̃n

−10
with probability at least 1−O n
. In view of the Davis-Kahan sin-Θ Theorem [56], the leading eigenvector
>
u of A = λ̃ (1 − 2θ) 11 + Ã − λ̃ (1 − 2θ) I satisfies


1
1
u − √ 1 , −u − √ 1
n
n
p
λ̃n + λ̃
 1,
.
λ̃n

min



.

kÃk + λ̃ (1 − 2θ) I
λ̃n (1 − 2θ) − kÃk − λ̃ (1 − 2θ) I

which is sufficient to guarantee (22). In fact, suppose without loss of generality that u −
According to the rounding procedure,
(0)

Xi

√1 1
n

≤ −u −

√1 1
n

1
1
= Xi = 1 if ui − √ < √ ,
n
2 n

leading to an upper bound on the Hamming error
X (0) − 1
n

0



n
n
o
1 X n (0)
1
1
1X
I Xi 6= Xi ≤
I ui − √ ≥ √
n i=1
n i=1
n
2 n


2


1
1
1  u − √n 1 
1
+ 2 = o (1) ,
≤
√ 2 .
n
n
λ̃n
 (1/(2 n)) 
≤

as claimed in this lemma.
It remains to justify the claim (66), for which we start by controlling the mean E[kÃk]. The standard
symmetrization argument [57, Page 133] reveals that
h
i
h
i √
(67)
E kÃk ≤ 2πE kÃ ◦ Gk ,

where G is a symmetric standard Gaussian matrix (i.e. {Gi,j | i ≥ j} are i.i.d. standard Gaussian variables),
and Ã ◦ G := [Ãi,j G̃i,j ]1≤i,j≤n represents the Hadamard product of Ã and G. To control E[kÃ ◦ Gk], it
follows from [58, Theorem 1.1] that
rX

h
i
p
n
E kÃ ◦ Gk Ã . max
Ã2i,j + log n,
(68)
j=1

i

38

.

depending on the size of maxi

nqP

n
j=1

o

Ã2i,j . First of all, with probability exceeding 1 − O n−10 one has

rX

n

j=1

Ã2i,j . λ̃n,

1 ≤ i ≤ n,

which arises
Pn by taking Chernoff inequality [59, Appendix A] together with the union bound, and recognizing
that E[ j=1 Ã2i,j ] ≤ λ̃n and λ̃n & log n. In this regime, substitution into (68) gives

Furthermore, the trivial bound

qP

h
i p
p
E kÃ ◦ Gk Ã . λ̃n + log n.

(69)

h
i √
p
E kÃ ◦ Gk Ã . n + log n

(70)

n
j=1

Ã2i,j ≤ n taken together with (68) gives

in the complement regime. Put together (67), (69) and (70) to arrive at
h
i
h h
ii
E kÃk ≤ E E kÃ ◦ Gk Ã





v
v
uX
uX
n


 p
 √


p
p
u n
u
. P max t
λ̃n + log n + 1 − P max t
Ã2i,j . λ̃n
Ã2i,j . λ̃n 
n + log n
 i
 i


j=1

.


p

p

λ̃n +

λ̃n,

p

j=1


p
1 √
log n + 10
n + log n
n

where the last inequality holds as long as
λ̃ &

(71)
log n
.
n

(72)

To finish up, we shall connect kÃk with E[kÃk] by invoking the Talagrand concentration inequality. Note
that the spectral norm kM k is a 1-Lipschitz function in M , which allows to apply [57, Theorem 2.1.13] to
yield
p o
n


P kÃk − E[kÃk] ≥ c1 λ̃n ≤ C2 exp −c2 c21 λ̃n
(73)

for some constants c1 , c2 , C2 > 0. Combining (71)-(73) and taking c1 to be sufficiently large lead to
p
kÃk . λ̃n

with probability at least 1 − O n−10 , concluding the proof.

F.7

Proof of Lemma 9

It follows from Lemma 3 that for any small constant δ > 0


n

o
∗
1
P (VX )v ≥ |S(v)| − δλdv ≤ exp − (1 − o (1)) (1 − ξ (δ)) λdv 1 − e−D
,
2

where D∗ represents the Chernoff information. Recalling that λdv & log n for all 1 ≤ v ≤ n and applying
the union bound, we get
 X

n
n



o
∗
1
P ∃1 ≤ v ≤ n : (VX )v ≥ |S(v)| − δ log n ≤
exp − (1 − o (1)) 1 − ξ˜ (δ) λdv 1 − e−D
2
v=1
39

(74)

for some function ξ˜ (δ) that vanishes as δ → 0. We can now analyze different sampling models on a case-bycase basis.
(1) Rings. All vertices have the same degree davg . Since the sample complexity is m = 12 λndavg , we
arrive at
n
o
 
∗
(74) ≤ n exp − (1 − o (1)) davg · 1 − ξ (δ) λ 1 − e−D


 2m 
−D ∗
1−e
,
= n exp − (1 − o (1)) 1 − ξ (δ)
n
which tends to zero as long as

m>

1+δ
n log n
·
∗ .
1 − ξ˜ (δ) 2 (1 − e−D )

(2) Lines with r = nβ for some constant 0 < β < 1. The first and the last r vertices have degrees at
least (1 − o (1)) 21 davg , while all remaining n − 2r vertices have degrees equal to (1 − o (1)) davg . This gives





1
−D ∗
˜
(74) ≤ 2r · exp − (1 − o (1)) 1 − ξ (δ) λ · davg 1 − e
2
n



o
∗
+ (n − 2r) exp − (1 − o (1)) 1 − ξ˜ (δ) λdavg 1 − e−D
n

m
o
∗
1 − e−D
≤ 2 exp β log n − (1 − o (1)) 1 − ξ˜ (δ)
n


 2m 

∗
1 − e−D
+ exp log n − (1 − o (1)) 1 − ξ˜ (δ)
,
n

which converges to zero as long as


m
m

1+δ
·
> (1 + o (1)) 1−
ξ̃(δ)

1+δ
> (1 + o (1)) 1−
·
ξ̃(δ)

βn log n
;
1−e−D∗
n log n
.
2(1−e−D∗ )

(3) Lines with r = γn for some constant 0 < γ ≤ 1. Each vertex has degree exceeding (1 − o (1)) r,
indicating that
o
n
 
∗
(74) ≤ n exp − (1 − o (1)) 1 − ξ (δ) λr 1 − e−D
o
n
 
∗
≤ exp log n − (1 − o (1)) 1 − ξ (δ) λr 1 − e−D
(
)



∗
m
 1 − e−D
= exp log n − (1 − o (1)) 1 − ξ (δ)
n 1 − 21 γ
where the last line follows from (42). This converges to zero as long as


1
n log n
1+δ
1− γ
.
m>
˜
2
1 − e−D∗
1 − ξ (δ)

(4) Grids with r = nβ for some constant 0 < β < 1. Note that davg  r2 = n2β . There are at
least n − πr2 vertices with degrees equal to (1 − o (1))davg , while the remaining vertices have degree at least
(1 − o (1))davg /4. This gives




 d
∗
avg
1 − e−D
(74) ≤ πr2 · exp −(1 − o (1)) 1 − ξ˜ (δ) λ
4
n



o

∗
2
+ n − πr exp −(1 − o (1)) 1 − ξ˜ (δ) λdavg 1 − e−D




davg 
−D ∗
˜
≤ 4 exp 2β log n − (1 − o (1)) 1 − ξ (δ) λ ·
1−e
4
n



o
∗
+ exp log n − (1 − o (1)) 1 − ξ˜ (δ) λdavg 1 − e−D
,
40

which vanishes as long as

(

λdavg
λdavg

1+δ
·
> (1 + o (1)) 1−
ξ̃(δ)

> (1 + o (1))

1+δ
1−ξ̃(δ)

·

8β log n
1−e−D∗
log n
1−e−D∗

;
.

This together with the fact that m = 12 nλdavg establishes the proof for this case.
Finally, for the cases of lines (with r = nβ for some constant 0 < β < 1) / rings / grids with non-uniform
sampling weight, it suffices to replace davg with the average weighted degree (see Section B.2.2). The case
of small-world graphs follows exactly the same argument as in the case of rings with nonuniform weights.

References
[1] M. Girvan and M. Newman. Community structure in social and biological networks. Proceedings of the
national academy of sciences, 99(12):7821–7826, 2002.
[2] S. Fortunato. Community detection in graphs. Physics Reports, 486(3):75–174, 2010.
[3] Mason A Porter, Jukka-Pekka Onnela, and Peter J Mucha. Communities in networks. Notices of the
AMS, 56(9):1082–1097, 2009.
[4] N. Bansal, A. Blum, and S. Chawla. Correlation clustering. Machine Learning, 56(1-3):89–113, 2004.
[5] Ali Jalali, Yudong Chen, Sujay Sanghavi, and Huan Xu. Clustering Partially Observed Graphs via
Convex Optimization. In International Conference on Machine Learning (ICML), pages 1001–1008,
June 2011.
[6] Jingchun Chen and Bo Yuan. Detecting functional modules in the yeast protein–protein interaction
network. Bioinformatics, 22(18):2283–2290, 2006.
[7] Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions on Pattern
Analysis and Machine Intelligence, 22(8):888–905, 2000.
[8] Amir Globerson, Tim Roughgarden, David Sontag, and Cafer Yildirim. How Hard is Inference for
Structured Prediction? In ICML, pages 2181–2190, 2015.
[9] Y. Chen, L. Guibas, and Q. Huang. Near-Optimal Joint Object Matching via Convex Relaxation.
International Conference on Machine Learning (ICML), pages 100–108, June 2014.
[10] Emmanuel Abbe and Martin Wainwright. ISIT 2015 Tutorial: Information Theory and Machine Learning. 2015.
[11] Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First
steps. Social networks, 5(2):109–137, 1983.
[12] Anne Condon and Richard M Karp. Algorithms for graph partitioning on the planted partition model.
Random Structures and Algorithms, 18(2):116–140, 2001.
[13] E. Abbe, A. Bandeira, A. Bracher, and A. Singer. Decoding binary node labels from censored measurements: Phase transition and efficient recovery. IEEE Trans on Network Science and Engineering,
1(1):10–22, 2015.
[14] R. Durrett. Random graph dynamics, volume 200. Cambridge university press Cambridge, 2007.
[15] Bruce Hajek, Yihong Wu, and Jiaming Xu. Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions. arXiv preprint arXiv:1502.07738, 2015.
[16] Amin Coja-Oghlan. Graph partitioning via adaptive spectral techniques. Combinatorics, Probability
and Computing, 19(02):227–284, 2010.

41

[17] K. Chaudhuri, F. Chung, and A. Tsiatas. Spectral clustering of graphs with general degrees in the
extended planted partition model. Journal of Machine Learning Research, 2012:1–23, 2012.
[18] Yudong Chen, Shiau H Lim, and Huan Xu. Weighted graph clustering with non-uniform uncertainties.
In International Conference on Machine Learning (ICML), pages 1566–1574, 2014.
[19] E. Abbe and C. Sandon. Community detection in general stochastic block models: fundamental limits
and efficient recovery algorithms. arXiv preprint arXiv:1503.00609, 2015.
[20] T Tony Cai and Xiaodong Li. Robust and computationally feasible community detection in the presence
of arbitrary outlier nodes. The Annals of Statistics, 43(3):1027–1059, 2015.
[21] Elchanan Mossel and Jiaming Xu. Density evolution in the degree-correlated stochastic block model.
arXiv preprint arXiv:1509.03281, 2015.
[22] Y. Chen, C. Suh, and A. J. Goldsmith. Information recovery from pairwise measurements: A
Shannon-theoretic approach. IEEE International Symposium on Information Theory, arXiv preprint
arXiv:1504.01369, 2015.
[23] S. Browning and B. Browning. Haplotype phasing: existing methods and new developments. Nature
Reviews Genetics, 12(10):703–714, 2011.
[24] N. Donmez and M. Brudno. Hapsembler: an assembler for highly polymorphic genomes. In Research
in Computational Molecular Biology, pages 38–52. Springer, 2011.
[25] Changxiao Cai, Sujay Sanghavi, and Haris Vikalo. Structured low-rank matrix factorization for haplotype assembly. IEEE Journal of Selected Topics in Signal Processing, 10(4):647–657, 2016.
[26] H. Si, H. Vikalo, and S. Vishwanath. Haplotype assembly: An information theoretic view. In IEEE
Information Theory Workshop, pages 182–186, 2014.
[27] G. Kamath, E. Sasoglu, and D. Tse. Optimal Haplotype Assembly from High-Throughput Mate-Pair
Reads. IEEE International Symposium on Information Theory, pages 914–918, June 2015.
[28] Thomas M Cover and Joy A Thomas. Elements of information theory. Wiley-interscience, 2006.
[29] Peter Chin, Anup Rao, and Van Vu. Stochastic Block Model and Community Detection in the Sparse
Graphs: A spectral algorithm with optimal rate of recovery. arXiv preprint arXiv:1501.05021, 2015.
[30] Adel Javanmard, Andrea Montanari, and Federico Ricci-Tersenghi. Phase Transitions in Semidefinite
Relaxations. arXiv preprint arXiv:1511.08769, 2015.
[31] Elchanan Mossel, Joe Neeman, and Allan Sly. Belief propagation, robust reconstruction, and optimal
recovery of block models. arXiv preprint arXiv:1309.1380, 2013.
[32] R. H. Keshavan, A. Montanari, and S. Oh. Matrix completion from noisy entries. The Journal of
Machine Learning Research, 99:2057–2078, 2010.
[33] Prateek Jain, Praneeth Netrapalli, and Sujay Sanghavi. Low-rank matrix completion using alternating
minimization. In Symposium on Theory of Computing (STOC), pages 665–674, 2013.
[34] Y. Chen and E. Candes. Solving random quadratic systems of equations is nearly as easy as solving
linear systems. In Advances in Neural Information Processing Systems (NIPS), pages 739–747, 2015.
[35] Emmanuel Abbe, Afonso S Bandeira, and Georgina Hall. Exact recovery in the stochastic block model.
IEEE Trans. on Information Theory, 62(1):471–487, 2016.
[36] C. Gao, Z. Ma, A. Y Zhang, and H. Zhou. Achieving optimal misclassification proportion in stochastic
block model. arXiv preprint arXiv:1505.03772, 2015.
[37] C. Swamy. Correlation clustering: maximizing agreements via semidefinite programming. In Symposium
on Discrete Algorithms (SODA), pages 526–527, 2004.
42

[38] Yudong Chen, Sujay Sanghavi, and Huan Xu. Improved graph clustering. IEEE Transactions on
Information Theory, 60(10):6440–6455, 2014.
[39] Varun Jog and Po-Ling Loh. Information-theoretic bounds for exact recovery in weighted stochastic
block models using the Renyi divergence. arXiv preprint arXiv:1509.06418, 2015.
[40] Bruce Hajek, Yihong Wu, and Jiaming Xu. Exact recovery threshold in the binary censored block
model. In Information Theory Workshop, pages 99–103, 2015.
[41] E. J. Candes and B. Recht. Exact Matrix Completion via Convex Optimization. Foundations of Comp.
Math., (6):717–772, 2009.
[42] R. H. Keshavan, A. Montanari, and S. Oh. Matrix completion from a few entries. IEEE Trans on Info
Theory, (6):2980–2998, 2010.
[43] E. J. Candès, X. Li, Y. Ma, and J. Wright. Robust principal component analysis? Journal of ACM,
58(3):11:1–11:37, Jun 2011.
[44] Venkat Chandrasekaran, Sujay Sanghavi, Pablo A Parrilo, and Alan S Willsky. Rank-sparsity incoherence for matrix decomposition. SIAM Journal on Optimization, 21(2):572–596, 2011.
[45] Yudong Chen, A. Jalali, S. Sanghavi, and C. Caramanis. Low-Rank Matrix Recovery From Errors and
Erasures. IEEE Trans on Info Theory, 59(7):4324–4337, 2013.
[46] Srinadh Bhojanapalli and Prateek Jain. Universal matrix completion. International Conference on
Machine Learning (ICML), pages 1881–1889, 2014.
[47] 10x Genomics, 2016. [Online; accessed 5-February-2016].
[48] Illumina. Data processing of Nextera mate pair reads on Illumina sequencing platform. Technical Note:
Sequencing, 2012.
[49] 10x Genomics. NA12878 Loupe data-set, 2015.
[50] Shreepriya Das and Haris Vikalo. SDhaP: haplotype assembly for diploids and polyploids via semidefinite programming. BMC genomics, 16(1):1, 2015.
[51] Yudong Chen and Jiaming Xu. Statistical-computational tradeoffs in planted problems and submatrix
localization with a growing number of clusters and submatrices. arXiv preprint arXiv:1402.1267, 2014.
[52] Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the
American statistical association, 58(301):13–30, 1963.
[53] Imre Csiszár and Paul C Shields. Information theory and statistics: A tutorial. Communications and
Information Theory, 1(4):417–528, 2004.
[54] Imre Csiszar and János Körner. Information theory: coding theorems for discrete memoryless systems.
Cambridge University Press, 2011.
[55] Imre Csiszár. Sanov property, generalized I-projection and a conditional limit theorem. The Annals of
Probability, pages 768–793, 1984.
[56] Chandler Davis and William Morton Kahan. The rotation of eigenvectors by a perturbation. iii. SIAM
Journal on Numerical Analysis, 7(1):1–46, 1970.
[57] Terence Tao. Topics in random matrix theory, volume 132. American Mathematical Soc., 2012.
[58] A. S. Bandeira and R. van Handel. Sharp nonasymptotic bounds on the norm of random matrices with
independent entries. arXiv preprint arXiv:1408.6185, 2014.
[59] Noga Alon and Joel H Spencer. The probabilistic method. John Wiley & Sons, 2015.

43

