A Compressive Sensing Approach to Community Detection
with Applications
Ming-Jun Lai∗

Daniel Mckenzie

†

arXiv:1708.09477v2 [cs.IT] 22 Sep 2017

September 25, 2017

Abstract
The community detection problem for graphs asks one to partition the n vertices V of a
graph G into k communities, or clusters, such that there are many intracluster edges and few
intercluster edges. Of course this is equivalent to finding a permutation matrix P such that, if
A denotes the adjacency matrix of G, then PAP> is approximately block diagonal. As there
are k n possible partitions of n vertices into k subsets, directly determining the optimal clustering
is clearly infeasible. Instead one seeks to solve a more tractable approximation to the clustering
problem. In this paper we reformulate the community detection problem via sparse solution of a
linear system associated with the Laplacian of a graph G and then develop a two-stage approach
based on a thresholding technique and a compressive sensing algorithm to find a sparse solution
which corresponds to the community containing a vertex of interest in G. Crucially, our approach
results in an algorithm which is able to find a single cluster of size n0 in O(n ln(n)n0 ) operations
and all k clusters in fewer than O(n2 ln(n)) operations. This is a marked improvement over the
classic spectral clustering algorithm, which is unable to find a single cluster at a time and takes
approximately O(n3 ) operations to find all k clusters. Moreover, we are able to provide robust
guarantees of success for the case where G is drawn at random from the Stochastic Block Model,
a popular model for graphs with clusters. Extensive numerical results are also provided, showing
the efficacy of our algorithm on both synthetic and real-world data sets.

1

Introduction

The clustering problem for a graph G = (V, E) is to divide the vertex set V into subsets V =
C1 ∪ . . . ∪ Ck such that there are many intracluster edges (edges between vertices in the same cluster)
and few intercluster edges (edges between vertices in different clusters) in E. This is a widely studied
problem in exploratory data analysis, as one can reasonably assume that vertices in the same cluster
a ‘similar’, in some sense. We refer the reader to the survey article [20] for further details and a
thorough overview of existing algorithmic approaches. We note that [20] refers to the clustering
problem as the community detection problem, and we shall use these two phrases interchangeably.
As is well-known, detecting clusters in G is equivalent to finding a permutation matrix P such that
if A is the adjacency matrix of G, then PAP> is almost block diagonal. Thus, we can think of the
clustering problem as a special case of the matrix reduction problem where the matrix in question
has binary entries.
∗

mjlai@uga.edu. Department of Mathematics, University of Georgia, Athens, GA 30602. This research is partially
supported by the National Science Foundation under the grant #DMS 1521537.
†
mckenzie@math.uga.edu. Department of Mathematics, University of Georgia, Athens, GA 30602. The second
author gratefully acknowledges the financial support of the NRF of South Africa while this research was conducted

1

One class of robust and accurate algorithms used to solve the clustering problem are the spectral
algorithms. Loosely, they work as follows. Suppose that |V | = n and let L denote the graph Laplacian, while 1Ca denotes the indicator vector of the a-th cluster (both to be defined in §3). Suppose
further that it is known a priori that G has k clusters. Let v1 , . . . , vk be orthogonal eigenvectors
associated to the k smallest eigenvalues of L, and consider the subspace span{v1 , . . . , vk } ⊂ Rn . One
can show that, under certain conditions, this subspace is ‘close’ to span{1C1 , . . . , 1Ck } and hence one
can use the basis {v1 , . . . , vk } to infer the supports of the basis {1C1 , . . . , 1Ck } , thus determining
the clusters C1 , . . . , Ck (of course supp(1Ca ) = Ca ). We refer the reader to [41], [35] or [37] for details.
Despite its theoretical and experimental success,the spectral approach has three main drawbacks:
1. The number of clusters k, needs to be known a priori. Clearly this is not always the case for
real data sets.
2. The algorithm cannot be used to find only a few clusters. As in many applications one is only
interested in finding one or two clusters ( thinking of the problem of identifying friends or
associates of a given user from a social network data set). Moreover in other cases where the
data set is extremely large, or only partially known, it might be computationally infeasible to
identify all clusters.
3. Computing an eigen decomposition of L typically requires O(n3 ) operations, making spectral
methods prohibitively slow for truly large data sets, such as those arising from electronic social
networks like Facebook or LinkedIn, or those arising from problems in Machine Learning.
However, in many situations (the social network example being one such case), the expected size
of the clusters, n0 , is small compared to n, and hence the indicator vectors 1Ca will be sparse. Our
approach is to adapt sparse recovery algorithms from the compressive sensing study to solve the
following problem:
arg min ||Lx||2 :
subject to xi = 1 and ||x||0 ≤ n0
(1.1)
to determine, directly, an approximation to the indicator vector of the cluster containing the vertex
of interest vi . One can then recover the cluster by considering the support of this vector. If desired,
one can iterate the algorithm to find all the remaining clusters of G.
Adapting compressive sensing algorithms to solve (1.1) proves challenging, as L is a poorly
conditioned sensing matrix. In general, a greedy type algorithm such as orthogonal matching pursuit
or iterative hard thresholding (cf. [21]) work very well when there are no intercluster edges (in this
case finding clusters reduces to finding connected components). Unfortunately, in the presence of
even a small number of intercluster edges, the first few iterations of a greedy algorithm are likely
to pick some indices outside the desired cluster. To overcome this difficulty, we propose a novel two
stage algorithm (see Algorithm 4 in §8) in which the first stage identifies a subset Ω ⊂ V which
contains the cluster of interest with high probability. The second stage then extracts the cluster
of interest from Ω using a greedy algorithm (we use Subspace Pursuit cf. [14]). In addition to the
aforementioned algorithm, the main contributions of this paper are the following:
1. An analysis of the Restricted Isometry and Coherence properties of the graph Laplacian. In
particular, we provide a series of probabilistic bounds on the restricted isometry constants and
coherence of Laplacians of graphs drawn from a well-studied model of random graphs (the
Stochastic Block Model (SBM)). See §5 and §6.
2. A proof that the Optimal Matching Pursuit (OMP) algorithm can be successfully used to detect
connected components of any graph, by solving (1.1) (see §7.)
2

3. A proof that, given a vertex vi , our Single Cluster Pursuit (SCP) Algorithm 4 successfully
finds the cluster containing vi when G is drawn from the Stochastic Block Model (SBM), for a
certain range of parameters and with probability tending to 1 as n → ∞. We achieve this by
combining the bounds of contribution with the theory of totally perturbed compressive sensing,
e.g. in [28].
4. An analysis of the computational complexity of Algorithm 4, showing that it finds a single
cluster in O(n2 + ln(n)nn0 ) time and all clusters in O(kn2 + ln(n)n2 ) time.
The structure of this paper is as follows. After briefly reviewing related work in §2, in §3 and
§4 we acquaint the reader with the necessary concepts from spectral graph theory and compressive
sensing, respectively. In §5 and §6 we study the restricted isometry property and coherence property
of Laplacians of random graphs. In §7 and §8, we describe two algorithms to handle graphs from
the Stochastic Block Model G(n, k, p, q) for q = 0 and q > 0, with respectively. We shall show that,
under certain mild assumptions on the graph G, the algorithms will indeed find the correct clustering
with high probability. §9 contains the computational complexity analysis, some possible extensions
and several future research directions. Finally, in §10 we present the results of several numerical
experiments to demonstrate the accuracy and speed of our algorithm and its powerful performance.

2

Related Work

The notion of community detection in graphs arises independently in multiple fields of applied
science, such as Sociology ([47],[40]), Computer Engineering ([26]), Machine Learning ([43]) and
Bioinformatics ([13]). In addition, many data sets can be represented as graphs by considering data
points as vertices and attaching edges between vertices that are ‘close’ with respect to an appropriate
metric. Thus, community detection algorithms can also be used to detect clusters in general data
sets, and indeed they have been shown to be superior to other clustering algorithms (for example
k-means) at detecting non-convex clusters ([30]).
The canonical probabilistic model of a graph containing communities is the Stochastic Block Model
(SBM), first explicitly introduced in the literature in the early 1980’s by Holland, Laskey, and
Leinhardt in [29]. Since then, there has been an explosion of interest in the SBM, driven in large part
by its many applications. In [1], Abbe identifies three forms of the community detection problem,
based on the kind of asymptotic accuracy we require (here, as in the rest of the paper, when we
speak of asymptotics we are considering the situation where the number of vertices, n, goes to
∞). In this paper we shall be concerned with the Exact Recovery Problem, where we require that
P (#misclassified vertices > 0) = o(1). A fundamental information theoretic barrier to exact recovery
is given by the following result (cf. [3]):
Theorem 2.1. The exact recovery problem , i.e. P (#misclassified vertices > 0) = o(1) with respect
to n for the symmetric SBM G(n, k, p, q) is solvable in polynomial time if, writing p = P ln(n)/n and
q = Q ln(n)/n:
p 
1 √
P − Q >1
(2.1)
k
and not solvable if:
p 
1 √
P − Q <1
(2.2)
k
Remark 2.2. This result was proved in [3] (and see also [1]). We note that in the cases our
algorithm
is guaranteed to solve the exact recovery problem (see Theorem 8.2), we assume that
√
√ 
1
P − Q → ∞, well above this theoretical bound.
k
3

Given the bound (2.1), the challenge then is to construct efficient algorithms to solve the Exact
Recovery Problem. There are myriad algorithmic approaches, such as the spectral approach (originally proposed by Fiedler in [19] for the two cluster case), hierarchical approaches like the DIANA
algorithm popular in bioinformatics ([31]) and message passing algorithms ([24]), to name a few.
Recently, two new classes of algorithms, namely degree-profiling ([3]) and semidefinite progamming
approaches ([2], [36], [27] and [33] among others) have been shown to solve the exact recovery problem with high probability right down to the theoretical bound (2.1). Degree-profiling even runs in
quasi-linear time, although it requires the parameters p, q and k as inputs, making it less than ideal
for analysing real world data sets. As the new algorithm we propose is most closely related to the
spectral approach, let us recall this algorithm here (as formulated by Ng, Jordan and Weiss in [41]).
Algorithm 1 The Spectral Clustering Algorithm (SC)
Input: the adjacency matrix A.
(1) Form the degree matrix D = diag (d1 , . . . , dn ) and Laplacian L := D−1/2 AD−1/2
(2) Find the k (orthogonal) eigenvectors v1 , . . . , vk corresponding to the k largest eigenvalues of
L.
(3) Form the matrix U = [v1 , . . . , vk ] and normalize the rows to get V
(4) Sort the rows of V into k clusters B1 , . . . , Bk using k-means.
(5) Assign vertex i to community Cj if and only if row i is in Bj .
Output: Communities C1 , . . . , Ck .
We mention that notions from Compressive Sensing have been applied to community detection
before, notably in the semidefinite programming approaches mentioned above, and in [45] where
signal processing techniques for functions defined on a graph G are used to speed up the computation
of the eigenvectors of L. Our approach is distinct from these. To the best of the authors’ knowledge,
the study in this paper is the first attempt to find the indicator vectors 1Ci directly using sparse
recovery.

3

Preliminary on Graph Theory

3.1

Some Elementary Notions and Definitions

Formally, by a graph G we mean a set of vertices V together with a subset E ⊂ {{u, v} : u, v ∈ V }
of edges1 . As we are only concerned with finite graphs, we shall always identify the vertex set V
with a finite set of consecutive natural numbers: V = [n] := {1, 2, . . . , n}. The degree of any vertex
i ∈ G is the total number of edges incident to i, that is di = |{{i, j} ∈ E}|.
0
0
0
0
0
A subgraph G of G is a subset of vertices V ⊂ V together with a subset of vertices E ⊂ E ∩ V × V .
Given any subset S ⊂ V , we denote by GS the subgraph with vertex set S and edge set all edges
{i, j} with i, j ∈ S. A path in G is a set of ‘linked’ edges {{i1 , i2 }, {i2 , i3 }, . . . , {ik−1 , ik }, and we say
that G is connected if there is a path linking any two vertices i, j ∈ V , and disconnected otherwise.
If G is disconnected, any subgraph GS ⊂ G which is connected and maximal with respect to the
property of being connected is called a connected component.
If G is connected, we define the diameter of G to be the length of (i.e. the number of edges in)
the longest path. Given any i ∈ V and any non-negative integer j, we define the ball Bj (i) ⊂ V
to be the set of all vertices connected to i be a path of length j or shorter. A good reference on
elementary graph theory is [5].
1

We only consider undirected graphs

4

3.2

The Graph Laplacian

To any graph G with |V | = n we associate a symmetric, n × n, non-negative matrix called the
adjacency matrix A, defined as Aij = Aji = 1 if {i, j} ∈ E and Aij = 0 otherwise. The graph
Laplacians of G are defined as follows.
Definition 3.1. Let A denote the adjacency matrix of a graph G and let D denote the matrix
diag(d1 , . . . , dn ) where di is the degree of the i-th vertex. We define the normalized, symmetric graph
Laplacian of G as Ls := I − D−1/2 AD−1/2 and the normalized, random walk graph Laplacian as
Lrw := I − D−1 A.
We first have a few basic properties of graph Laplacians.
Theorem 3.2. Suppose that L = Ls or Lrw . We have the following properties:
1. The eigenvalues of L are real and non-negative.
2. λn−1 ≤ 2
3. Let λ1 ≤ λ2 ≤ . . . ≤ λn denote the eigenvalues of L in ascending order. Let k denote the
number of connected components of G. Then λi = 0 for i ≤ k and λi > 0 for i > k.
Proof.
For L = Ls , Items 1 to 3 follow from Lemma 1.7 in [12]. If L = Lrw , observe that
Lrw = D−1/2 Ls D1/2 , and so the eigenvalues of Lrw and Ls coincide. Hence the above hold for Lrw
as well.

n
For any subset S ⊂ [n] we define its indicator vector, denoted 1S ∈ R , by (1S )i = 1 if i ∈ S and
zero otherwise. Let C1 , · · · , Ck be the clusters of G. One can check (and see also [35] proposition 2)
that Lrw 1Ci = 0 for i = 1, · · · , k. Thus we have the following:
Theorem 3.3. The indicator vectors of the connected components of G, 1C1 , . . . , 1Ck , form a basis
for the zero eigenspace (i.e. the kernel) of Lrw .
For the rest of this paper, by L we shall mean Lrw . We shall refer to the i-th column of L as `i .
One can easily check that:
Aik
(`i )k = δik −
.
dk
Finally, we shall denote by L−i the submatrix of L obtained by dropping the column `i .

3.3

Random Graph Theory

As outlined in §2, the Stochastic Block Model (SBM) is a widely used mathematical model of a
random graph with clusters.
Definition 3.4. Given n = kn0 , fix a partition of V := [n] into k subsets C1 , . . . , Ck of equal size
n0 . We say G is drawn from the SBM G(n, k, p, q) if, for all i, j ∈ [n] with i 6= j , the edge {i, j} is
inserted independently and with probability p if i, j ∈ Ca for some a = 1, · · · , k and q otherwise.
As we area interested in clustering we assume that q << p. We emphasize that the partition
V = C1 ∪C2 ∪. . .∪Ck is fixed before any edges are assigned. We note that the subgraphs GCa are i.i.d
instances of a simpler random graph model, the Erdös-Rényi (ER) model G(n0 , p), first introduced
in [18]
Definition 3.5. We say H is drawn from the ER model G(n0 , p) if H has n0 vertices and for all
i, j ∈ [n0 ] the edge {i, j} is inserted independently and with probability p.
5

Returning to the SBM, for any vertex i in community Ca , we define its in-community degree as
d0i = #{{i, j} ∈ E : j ∈ Ca } and its out-of-community degree as di := #{{i, j} ∈ E : j ∈
/ Ca }. One
can easily see that
E[d0i ] = p(n0 − 1) and E[di ] = q(n − n0 )
and by definition di = d0i + di . In fact d0i is the degree of i considered as a vertex in the ER subgraph
GCa . An important fact about degrees in ER random graphs is that they concentrate around their
mean:
Theorem 3.6. Suppose G is drawn from G(n, k, p, q).
1. For any α > 0, if p ≥

4 ln(n)
then with probability at least 1 − 1/n:
α 2 n0

(1 − α)n0 p ≤ d0i ≤ (1 + α)n0 p
2. In particular, if p ≥
p
1/ ln(n) = o(1).

for all i ∈ {1, 2, · · · , n}

(3.1)

4k(ln(n))2
then (3.1) holds, with probability at least 1 − 1/n, for α =
n

Proof. This theorem is a variation on a well known result for ER graphs (e.g. theorem 3.6 in
[25]). Each d0i follows the binomial distribution with parameters n0 − 1 and p, so by the Chernoff


2
bound: P |d0i − n0 p| ≥ αn0 p ≤ e−α n0 p/2 . Hence:




0
P max |di − n0 p| ≥ αn0 p = P |d01 − n0 p| ≥ αn0 p or |d02 − n0 p| ≥ αn0 p or . . . or |d0n − n0 p| ≥ αn0 p
i∈[n]

n
X


2
P |d0i − n0 p| ≥ αn0 p = ne−α n0 p/2

≤

i=1


Thus P max

i∈[n0 ]

|d0i


4 ln(n)
2 ln(n2 )
2
− n0 p| ≤ αn0 p = 1 − ne−α n0 p/2 If p ≥ 2
=
then:
α n0
α 2 n0
1 − ne−α

2 n p/2
0

2

≤ 1 − ne− ln(n ) = 1 − 1/n
p
This proves part 1. Part 2 follows by taking α = 1/ ln(n), in which case the lower bound on p
becomes:
4k(ln(n))2
4 ln(n)
4(ln(n))2
4(ln(n))2
=
=
=
α 2 n0
n0
n/k
n

The second remarkable property of the ER model is that the eigenvalues of L also concentrate
around their mean:
Theorem 3.7. Let L be the Laplacian of a random graph drawn from G(n0 , p) with p >> (ln(n0 ))2 /n0
and let λ1 ≤ λ2 ≤ . . . ≤ λn0 denote its eigenvalues. Then almost surely 2 :
max |1 − λi | ≤ (1 + o(1)) √
i6=1

4
g(n0 ) log2 (n0 )
+
pn0
pn0

where g(n0 ) is a function tending to infinity arbitrarily slowly.
2

Given a family of random graph models Gn we say that some graph property P holds almost surely if
P[G ∈ Gn , G does not have P] = o(1) with respect to n

6

Proof. Given that the expected degree of each vertex in G is pn0 , this is just Theorem 3.6 in [11]

Remark 3.8. For our purposes, it will be enough to note that this gives:
√
√
4/ p
4/ p
1
1
λ2 ≥ 1 − √
− o( √ ) and λn0 ≤ 1 + √
+ o( √ )
n0
n0
n0
n0
almost surely.

4

Preliminaries on Compressive Sensing

Let Φ ∈ Rm×N and y ∈ Rm with m < N . We say that a vector x is sparse if it has few non-zero
entries relative to its length. We follow the convention of defining the ‘0 quasi-norm’ as:
kxk0 = #{xi : xi 6= 0}
and we say x is s-sparse if kxk0 ≤ s. Compressive sensing is concerned with solving
arg min{kxk0 :

x ∈ RN , Φx = y}

(4.1)

in the case where m < N (that is, when the linear system is underdetermined). We call (4.1)
the Sparse Recovery Problem. One also considers the Perturbed Sparse Recovery Problem where
y = Φx∗ + e with kek2 ≤ η << kyk2 and we wish to solve:
x# := arg min{kxk0 :

x ∈ RN , kΦx − yk2 ≤ η}

(4.2)

while guaranteeing that x# is a good approximation to x∗ by bounding kx# − x∗ k2 ? We remark
that problem (4.2) is equivalent to the dual problem:
x# := arg min{kΦx − yk2 :

x ∈ RN , kxk0 ≤ n0 }

(4.3)

We refer the reader to [21] for an excellent introduction to the area.

4.1

Computational Algorithms

Many numerical algorithms have been invented for solving (4.1) and (4.3), for example, `1 convex
minimization and its variations, hard thresholding iteration and its variations, greedy approaches
such as orthogonal matching pursuit (OMP) as well as more exotic approaches like `q nonconvex
minimization. See, for example, [10], [8], [6], [46], [7], [22], [23]. Due to its efficiency, we shall focus
on the greedy approach in this paper, specifically the Orthogonal Matching Pursuit (OMP) and
Subspace Pursuit (SP) algorithms, see Algorithms 2 and 3, respectively. For notational convenience,
we shall follow [21] and denote by ΦS the column submatrix of Φ consisting of the columns indexed
by the subset S ⊂ [N ]. For a vector x ∈ RN we denote by xS either the subvector in R|S| consisting
of the entries xi for i indexed by S, or the vector

xi if i ∈ S
(xS )i =
0 if i ∈
/S
It should always be clear from the context which definition we are referring to. We also remind the
reader of the following operations on vectors v ∈ Rn , defined in [21]:

vi if i ∈ S
Ls (v) = index set of s largest absolute entries of v and Hs (v) = vLs (v) =
0 if i ∈
/S
7

where Hs is sometimes referred to as the Hard Thresholding Operator.
Algorithm 2 The OMP Algorithm
Inputs: y and Φ
Initialize: r(0) = y, S (0) = ∅, x(0) = 0 and α = 0.
while True do
α←α+1
i(α) := L1 (Φ> rα−1 )
S (α) = S (α−1) ∪ {i(α) }
x(α) := arg min{||ΦS (α) zS (α) − y||2 : z ∈ RN and supp(z) ⊂ S (α) }
r(α) := y − Φx(α)
if Stopping Criterion met then
Output x# := xα
Break
end if
end while

Algorithm 3 The SP algorithm ([14])
Inputs: y, Φ and an integer s ≥ 1
Initialization:
(1) T 0 = Ls (Φ> y).
(2) x0 = arg min{ky − ΦT 0 xk2 : supp(x) ⊂ T 0 }
(3) r0 = y − ΦT 0 x0
Iteration:
for k = 1 : kmax do

(1) T̂ k = T k−1 ∪ Ls Φ> rk−1
(2) u = arg min{ky − ΦT̂ k xk2 : x ∈ RN and supp(x) ⊂ T̂ k }
(3) T k = Ls (u) and xk = Hs (u)
(4) rk = y − ΦT k xk
end for
The most common stopping criteria for Algorithm 2 are α = k, or kr(α) k2 <  for a given k or .
A sufficient condition to guarantee the convergence of Algorithm 2 is the following
Theorem 4.1. For any S ⊂ [N ], if ΦS is injective and satisfies
kΦ†S ΦS c k1→1 < 1,

(4.4)

where Φ†S is the pseudo-inverse of ΦS , then any vector x with support S is recovered in at most
s = |S| steps of OMP.
We refer to [46] for a proof. See also Remark 3.6 in [21].
Remark 4.2. In [14] where the SP algorithm is introduced, they suggest solving the least squares
problems (that is (2) in Initialization and (2) in Iteration) exactly. In our implementation, we use
MATLAB’s lsqr algorithm to solve them approximately, to a high precision. As pointed out by [38]
in their analysis of CoSaMP, a very similar algorithm, this does not affect the convergence analysis
of the algorithm.
8

4.2

Fundamental Concepts

A very important concept, the restricted isometry property (RIP), introduced by Candés and Tao
([10]) plays a critical role in the study of the existence and uniqueness of a sparse solution from
a sensing matrix and whether the solution of an `1 minimization is the sparse solution. Another
concept, mutual coherence, introduced by Donoho and his collaborators in ([17] is also used in this
study.
Definition 4.3. Letting 0 < s < m < N be an integer and ΦS be a submatrix of Φ which consists
of columns of Φ whose column indices are in S ⊂ [N ]. The restricted isometry constant (RIC) δs of
Φ is the smallest quantity such that
(1 − δs )kxk22 ≤ kΦS xk22 ≤ (1 + δs )kxk22

(4.5)

for all subsets S with with cardinality |S| ≤ s. If a matrix Φ has such a constant δs < 1 for some s,
Φ is said to possesses RIP of order s. It is known that
δs =

min
S⊂{1,··· ,n}
|S|≤s

kΦ>
S ΦS − Is k2→2 ,

(4.6)

where Is is the identity matrix of size s × s.
Definition 4.4. The coherence of a matrix Φ, denoted µ, is the largest normalized inner product
between its columns:
|hφi , φj i|
.
µ := max
i6=j kφi k2 kφj k2

4.3

Totally Perturbed Compressive Sensing

Frequently it is useful to modify problem (4.3) further to allow for small perturbations in the observed
measurement matrix. That is, suppose that y = Φx∗ + e and let Φ̂ = Φ + E, where E is a small
perturbation matrix. Denoting again:
x# := arg min{kΦ̂x − yk2 :

x ∈ RN , kxk0 ≤ s},

(4.7)

can we still guarantee that x# is a good approximation to x∗ by bounding kx# −x∗ k2 ? Problem (4.7)
is called the Totally Perturbed Sparse Recovery Problem. Analyzing (4.7) is often more important for
applications than analyzing (4.3), as frequently we only know the measurement matrix Φ to within
a certain error tolerance.
Theorem 4.5 (Herman and Strohmer, [28]). Suppose that Φ̂ = Φ + E. Let δs and δ̂s denote the s
restricted isometry constants of Φ and Φ̂ respectively. Define3 sΦ := kEk2,s /kΦk2,s . Then:
δ̂s ≤ (1 + δs ) (1 + sΦ )2 − 1
To bound the error kx# − x∗ k2 , we need the following result. Define y = Φx and suppose that
ŷ = Φx + e is the observed (perturbed) measurement vector. Suppose further that we only have
access to Φ̂ = Φ + E, a small perturbation of the measurement matrix. Define y := kek2 /kyk2 ,
Φ = kEk2 /kΦk2 and let sΦ be as above.
3

For a matrix Φ we denote by kΦkp the induced operator norm kΦkp = maxx6=0
semi-norm max kΦS kp
S⊂[n]
|S|=s

9

kΦxkp
kxkp

By kΦkp,s we mean the

Theorem 4.6. Suppose that x is s-sparse. Define the following constants:
q
√
√
2 (1 + δ̂ 2 )
2δ̂3s
2 2+1
( 2 + 2)δ̂3s
3s
(1 − δ̂3s )(1 − ρ̂) +
and τ̂ = q
ρ̂ =
.
2
1 − δ̂3s
(1 − δ̂3s )(1 − ρ̂)
1 − δ̂ 2
3s

Suppose that δ̂3s ≤ 0.4859. Then after m = ln(Φ + y )/ ln(ρ̂) iterations of Subspace Pursuit (Algorithm 3) applied to problem (4.7), we have
!
p
kx − xm k2
1 + δ̂s
≤ τ̂
+ 1 (sΦ + y ).
kxk2
1 − sΦ
Remark 4.7. This is Theorem 2 in [34], adapted to the case the x is s-sparse (the result in. loc.
sit. is for the more general case where x is compressible).

5

The RIP of Laplacian of Random Graphs

We first study the RIP for the Laplacian of a connected ER graph drawn from G(n0 , p). We then
extend this to a result on the RIP for graphs drawn from the SBM G(n, k, p, 0), as these can be
thought of as a disjoint union of k ER graphs. Finally, we extend to graphs drawn from G(n, k, p, q)
for 0 < q << p using a perturbation argument.

5.1

RIP for Laplacian of G(n0 , p)

Lemma 5.1. Let L be the Laplacian of a connected graph G with n0 vertices. Let S ⊂ [n0 ] with
|S| = s < n0 . Then σmin (LS ) ≥ (1 − s/n0 )λ2 and δs = max{1 − (1 − s/n0 ) λ22 , λ2n0 − 1}, where λi
denotes the i-th eigenvalue of L, ordered from smallest to largest.
Proof. Let w1 , . . . , wn0 be an orthonormal basis of eigenvectors of L with eigenvalues
P 0 λ1 ≤ · · · ≤
λn0 , where λ1 = 0 and λ2 > 0. For any v supported on S with kvk2 = 1, write v = ni=1
αi wi . Note
that w1 = √1n0 1 and ker(L) = span(w1 ). Then:
kLvk22 = L

n
X

!

2

αi wi

=

i=1

2

n
X

2

αi λi wi

i=2

=
2

n
X

αi2 λ2i ≥

i=2

n
X

!
αi2

λ22

i=2

P 0 2
P 0 2
αi = 1 − α12 . Thus kLvk22 ≥ λ22 (1 − α12 ) and so
Because ni=1
αi = kvk22 = 1 we have that ni=2
clearly this quantity is minimized by making α1 as large as possible. Observe that:


√
1
1 √
s
1
α1 = √ 1 · v ≤ √ kvk1 ≤ √ ( skvk2 ) = √ .
n0
n0
n0
n0
We remark that this bound on α1 is sharp, and is achieved by taking v =
σmin (LS ) =

min
supp(v)⊂S
kvk2 =1

kLvk22

r
≥

1−

s
n0

2 !

λ22


=

On the other hand:
max kLvk22 ≤ max kLvk22 = λ2n0 .

supp(v)⊂S
kvk2 =1

kvk2 =1

10

√1 1S .
s

s
1−
n0



Hence:

λ22 .

Hence for any S ⊂ [n] with |S| = s, and any v with supp(v) ⊂ S and kvk2 = 1, we have:


s
λ22 ≤ kLvk22 ≤ λ2n0
1−
n0
and the claim about δs follows.



Theorem 5.2 (RIP for Laplacian of ER graphs). Suppose that G ∈ G(n0 , p) with Laplacian L and
suppose that p >> (ln(n0 ))2 /n0 . If s = γn0 with γ ∈ (0, 1) then
8p−1/2
1
δs ≤ γ + (1 − γ) √
+ o( √ )
n0
n0
almost surely

4

Proof. By Theorem 3.7, and Remark 3.8,
4p−1/2
4p−1/2
1
1
λ2 ≥ 1 − √
− o( √ ) and λn0 ≤ 1 + √
+ o( √ )
n0
n0
n0
n0
almost surely. Combining this with Lemma 5.1, we get that:
!2
4p−1/2
1
δs ≤ 1 − (1 − s/n0 ) 1 − √
− o( √ )
n0
n0
!
1
8p−1/2
+ o( √ )
= 1 − (1 − γ) 1 − √
n0
n0
!
8p−1/2
1
8p−1/2
1
= 1 − 1 − γ − (1 − γ) √
+ o( √ ) = γ + (1 − γ) √
+ o( √ ).
n0
n0
n0
n0
as claimed.

We conclude this subsection with a lower bound for kLk2,s (see §4.3 for the definition of k · k2,s ),
where L is the Laplacian of a connected graph.
Lemma 5.3. If L is the Laplacian of a connected graph G with n0 vertices, then kLk2,s ≥ λs−1 ,.
Proof. Recall that:
kLk2,s := max kLS k2 = max σmax (LS )

(5.1)

S⊂[n]
|S|=s

S⊂[n]
|S|=s

We shall apply Theorem 5.4 below. For a matrix such as L which is conjugate to a symmetric nonnegative definite matrix, the eigenvalues coincide with the singular values. Translating the notation
of this Theorem 5.4 into the current situation, for p = n, q = s, βi = σi (LS ) and αi = λi (L). Clearly,
min(m, n) = min(n, n) = n and min(p, q) = min(n, s) = s. We use Theorem 5.4 again to get:
σmax (LS ) ≥ λs−1 .
And so

max σmax (LS ) ≥ λs−1 .



S⊂[1,··· ,n]
|S|=s

In the proof above, we have used the following classic interpolation Theorem for singular values:
4

Recall that here and throughout this paper we say that a property holds almost surely if the probability that it
does not hold is o(1) with respect to n0 (or sometimes n)

11

Theorem 5.4. Let A be an m × n matrix with singular values α1 ≤ α2 ≤ . . . ≤ αmin(m,n) . Suppose
that B is a p × q submatrix of A, with singular values β1 ≤ β2 ≤ . . . ≤ βmin(p.q) Then:
αmin(m,n)−i ≥ βmin(p,q)−i for i = 0, 1, . . . , min(p, q) − 1
and
βi ≥ αmin(m,n)−min(p,q)−(m−p)−(n−q)−1+i
for integer i satisfying min(p, q) + (m − p) + (n − q) + 2 − min(m, n) ≤ i ≤ min(m, n).
Proof.
This is Theorem 1 in [44]. Note that they use the opposite notational convention:
α1 ≥ α2 ≥ . . . ≥ αmin(m,n) and β1 ≥ β2 ≥ . . . ≥ βmin(p.q) .


5.2

RIP for Laplacian of Graphs from G(n, k, p, 0)

Lemma 5.5. Suppose that a graph G has k connected components C1 , · · · , Ck , all of size n0 (for
example, G ∈ G(n, k, p, 0)). Let GC1 , . . . , GCk denote the subgraphs on these components and let Li
denote their Laplacians. Then for any s < n0 , δs (LG ) = maxi δs (Li ).
Suppose S ⊂ Ci for
i. For simplicity we assume i = 1, but the other cases are

 1some
LS
where L1 denotes the Laplacian of GC1 and 0 here is the zero
identical. In this case LS =
0
matrix of the appropriate size. If supp(v) ⊂ S, then kLS vk22 = kL1S vs k22 and so:
Proof.

(1 − δs (L1 ))kvk22 ≤ kLS vk22 ≤ (1 + δs (L1 ))kvk22

(5.2)

It follows that, for all index sets S contained in a single component (i.e. S ⊂ Ci for some i), we have:


(1 − max δs (Li ) )kvk22 ≤ kLS vk22 ≤ (1 + max δs (Li ) )kvk22 .
i

i

Now suppose that
Pk S 6⊂ Ci . Write S = ∪i Si where Si := S ∩ Ci . Given any v with supp(v) = S, we
can write v = i=1 vi with vi = HSi (v). Then:
kLS vk22

=

k
X

2

LSi vi

i=1

2

Crucially, observe that all the terms LSi vi have disjoint support. Hence:
2

kLS vk22

=

X
i

LSi vi

=
2

X

kLSi vi k22 ≥

X

i


1 − δsi (Li ) kvi k22 by (5.2)

i
i

≥ min 1 − δsi (L )
i

X


kvi k22 = min 1 − δsi (Li ) kvk22

i

i





i
2
i
= 1 − max δsi (L ) kvk2 ≥ 1 − max δs (L ) kvk22
i

i

with the final inequality holding as si ≤ s for all i and δt is non-decreasing in t. An identical argument
yields that:


kLS vk22 ≤

1 + max δs (Li ) kvk22
i

12

and so we have


(1 − max δs (Li ) )kvk22 ≤ kLS vk22 ≤ (1 + max δs (Li ) )kvk22 .
i

i

This completes the proof.



Theorem 5.6 (RIP for Laplacian of Graphs from Stochastic Block Model). Suppose G ∈ G(n, k, p, 0),
with n0 = n/k and Laplacian L. Suppose further that p >> (ln(n0 ))2 /n0 and that k is O(1) with
respect to n. If s = γn0 with γ ∈ (0, 1) then:
8p−1/2
1
δs (L) ≤ γ + (1 − γ) √
+ o( √ )
n0
n0

(5.3)

almost surely.
Proof. Because q = 0, G will have k connected components with probability 1. Note that each
subgraph Gi is an i.i.d ER graph, drawn from G(n0 , p). Let Li denote the Laplacian of GCi . By
Theorem 5.2
8p−1/2
1
δs (Li ) ≤ γ + (1 − γ) √
+ o( √ )
(5.4)
n0
n0
almost surely. That is, there exists a function f (n0 ) going to 0 as n0 → ∞ such that (5.4) holds with
probability 1 − f (n0 ). As the GCi are i.i.d:
8p−1/2
1
max δs (Li ) ≤ γ + (1 − γ) √
+ o( √ )
1≤i≤k
n0
n0

(5.5)

with probability (1 − f (n0 ))k . As long as k is eventually bounded with respect to n0 (i.e. k is O(1)
with respect to n), (1 − f (n0 ))k → 1 as n0 → ∞. Hence (5.5) holds almost surely.

Again, we conclude this subsection with a lower bound for kLk2,s .
Lemma 5.7. Suppose that a graph G has k connected components C1 , · · · , Ck , all of size n0 . Let
GC1 , . . . , GCk denote the subgraphs on these components and let Li denote their Laplacians. Then
kLk2,s ≥ maxa∈[k] λs−1 (La ).
Proof. We leave the proof to the interested reader.

5.3



RIP for Laplacian of Graphs from G(n, k, p, q) with q > 0

Finally, we study the RIP for Laplacian of graphs from G(n, k, p, q) with q > 0. Observe that for
G ∈ G(n, k, p, q) we may write A = A0 + A where A0 contains the intracluster edges and A
contains the intercluster edges:

1 if {i, j} ∈ E and i, j ∈ Ca for an a ∈ {1, · · · , k}
0
Aij =
0
otherwise

1 if {i, j} ∈ E and i ∈ Ca and j ∈ Cb for some a 6= b
Aij =
0
otherwise.
Assuming that q << p, there are much fewer intercluster than intracluster edges, and thus A is
much sparser than A0 . Observe further that we can regard A0 as the adjacency matrix of a subgraph
G0 ⊂ G, obtained by removing all the intercluster edges. In fact, G0 ∈ G(n, k, p, 0). Let L0 denote
the Laplacian of the underlying graph G0 . It is tempting to assume that L = L0 + L , where L is a
13

Laplacian associated to A , but unfortunately this is not the case. However, one can still regard L as
a small perturbation of L0 , i.e. L = L0 + E. In order to establish bounds on the restricted isometry
constants of L, we need to bound the size of the perturbation E, which we do in Theorem 5.8. First,
recall that, as in §3.3, for any i ∈ Ca , d0i denotes the in-community degree (equivalently the degree
P of
i in GCa or G0 ) and di denotes the out-of-community degree. In terms of A0 and A , d0i = j A0ij
P
and di = j Aj . Define ri = di /d0i . We can assume that di << d0i , equivalently ri << 1, for all i.
Theorem 5.8. Let L be the Laplacian of a graph drawn at random from G(n, k, p, q) with p ≥
4k(ln(n))2 /n and let α be as in part 2 of Theorem 3.6. Suppose further that max1≤i≤n ri ≤ r << 1.
Then L = L0 + E where L0 is the Laplacian of G0 and E = E1 + E2 such that supp(E1 ) = supp(A0 )
and supp(E2 ) = supp(A ) and the following bounds hold:
1. kE1 k∞ , kE2 k∞ ≤ r + O(r2 ).
2. kE1 k1 , kE2 k1 ≤ β 2 r + O(r2 )
3. kE1 k2 , kE2 k2 ≤ βr + O(r2 ).
4. for any s < n, kE1 k2,s , kE2 k2,s ≤ βr + O(r2 ) and kEk2,s ≤ 2βr + O(r2 )
where β 2 = (1 + α)/(1 − α).
The proof of Theorem 5.8 uses the following lemma:
Lemma 5.9. Suppose that L is the Laplacian of a graph G drawn from G(n, k, p, q), and let L0 denote
the Laplacian of the underlying (disconnected) graph G0 , thought of as drawn from G(n, k, p, 0).
Suppose further that max1≤i≤n ri ≤ r << 1. Then L = L0 + E, where:

(
1
ri + O(r2 ) A0ij
if i, j ∈ Ca
d0i
 
Eij =
1
2
(ri − 1) + O(r ) Aij if i ∈ Ca and j ∈ Cb for a 6= b
d0
i

A

Proof.
By definition Lij = δij − dij
where δij = 1 if i = j and zero otherwise. Observe
i
1
1
1
1 1
1
1
= 0
Because ri << 1 for all i, by Taylor’s Theorem
=
that
= 0
 =
0

d
di
di
di + di
di 1 + 0i
di 1 + ri
di


1
1 − ri + O(ri2 ) . Direct computation reveals that, for i, j ∈ Ca :
0
di
!
0
A


1
1
ij
Lij = δij − 0 1 − ri + O(ri2 ) A0ij = δij − 0 + 0 ri + O(r2 ) A0ij
di
di
di

1
= L0ij + 0 ri + O(r2 ) A0ij
di
as 1/d0i ≤ ri = O(r). The calculation for i, j in different clusters is similar.

Let us write E = E1 + E2 where E1 will contain the ‘on-diagonal’ perturbation, and E2 will
contain the ‘off diagonal’ perturbation:


Eij if i, j ∈ Ca , a ∈ [k]
Eij if i ∈ Ca and j ∈ Cb for a 6= b, a, b ∈ [k]
1
2
Eij =
and Eij =
0
otherwise
0
otherwise
We are now ready to prove Theorem 5.8.
14

Proof. [Proof of theorem 5.8] By definition, k · k∞ is the maximum absolute row sum of the matrix
in question. For any i, let Ca be the cluster to which it belongs. Then:
X

|E1ij | =

j

X ri + O(r2 )
ri + O(r2 ) X 0
ri + O(r2 ) 0
0
A
=
(di ) = ri + O(r2 ).
A
=
ij
ij
d0i
d0i
d0i

j∈Ca

j∈Ca

Hence, we have


X
= max 
|E1ij | = max(ri ) + O(r2 ) ≤ r + O(r2 ).

kE1 k∞

i

i

j

Similarly:
X

|E2ij | =

j

X (ri − 1) + O(r2 )
1 + O(r2 ) X 
1 + O(r2 ) 

A
≤
A
=
(di ) ≤ ri + O(r2 )
ij
ij
d0i
d0i
d0i

j ∈C
/ a

j ∈C
/ a

as ri := di /d0i , and so again:

kE2 k∞ = max 


X

i

|E2ij | = max(ri ) + O(r2 ) ≤ r + O(r2 )
i

j

Before continuing, recall that as p ≥ 4k(ln(n))2 /n we may choose an α = o(1) with respect to n such
that (1 − α)n0 p ≤ d0i ≤ (1 + α)n0 p almost surely for all i ∈ [n], by part 2 of Theorem 3.6. Now,
because k · k1 is the maximum absolute column sum, for any j in cluster Ca , we have
X

|E1ij | =

1≤i≤n

X ri + O(r2 )
r + O(r2 ) X 0
r + O(r2 ) 0
0
A
≤
A
≤
(dmax )
ij
ij
d0i
d0min
d0min
i∈Ca

i∈Ca

≤ (r + O(r2 ))

(1 + α)n0 p
r(1 + α)
=
+ O(r2 ) = β 2 r + O(r2 )
(1 − α)n0 p
(1 − α)

and so:

!
1

kE k1 = max

X

j

|E1ij |

≤ β 2 r + O(r2 ).

i

Similarly;
X

|E2ij | =

1≤i≤n

X (ri − 1) + O(r2 )
dj
1 + O(r2 ) X 

2
A
≤
A
=
(1
+
O(r
))
ij
ij
d0i
d0min
d0min

i∈C
/ a

i∈C
/ a

≤ (1 + O(r2 ))

1+α
1−α

dj
d0max

≤ (1 + O(r2 ))

1 + α dj
≤ β 2 rj + O(r2 )
1 − α d0j

and so again we have
!
kE2 k1 = max
j

X

|E2ij |

≤ β 2 max(rj ) + O(r2 ) ≤ β 2 r + O(r2 ).
j

i

Now, by the Riesz-Thorin interpolation theorem:
1/2

2
2
kE1 k2 ≤ kE1 k1 kE1 k1/2
∞ ≤ β r + O(r )

15

1/2

(r + O(r2 ))1/2 = βr + O(r2 )

and by an identical argument kE2 k2 ≤ βr + O(r2 ). Part 4 follows from the simple fact that for any
matrix B, kBk2,s ≤ kBk2 , and the bound for kEk2,s follows from the fact that E = E1 + E2 and the
triangle inequality.

We are now ready to state and prove the main result of this section.
Theorem 5.10. Suppose that G ∈ G(n, k, p, q), with block sizes n0 = n/k and Laplacian L. Suppose
further that:
1. p >> (ln(n0 ))2 /n0
2. k is O(1) with respect to n.
3. max ri ≤ r << 1.
1≤i≤n

If t = γn0 with γ ∈ (0, 1) then:
r
1
D2
δt (L) ≤ γ + D1 r + √ + D3 √ + O(r2 ) + o( √ )
n0
n0
n0

(5.6)

almost surely, where D1 , D2 and D3 are O(1) with respect to n0
Proof. As above, we write L = L0 + E, where L0 is the Laplacian of the subgraph G0 , thought of
as drawn from G(n, k, p, 0). We define δt := δt (L0 ) and δ̂t := δt (L). By Theorem 4.5:
δ̂t ≤ (1 + δt )(1 + tL )2 − 1.

(5.7)

As defined in a previous section, tL := kEk2,t /kL0 k2,t . Theorem 5.8 gives us that kEk2,t ≤ 2βr +
O(r2 ), while Lemma 5.7 gives kL0 k2,t ≥ max1≤a≤k λt−1 (La ) (recall that La denotes the Laplacian of
the subgraph GCa ). By a similar argument to that of Theorem 5.6, we can apply Lemma 3.7 (and
see also remark 3.8) to get:
4p−1/2
1
max λt−1 (La ) ≥ 1 − √
− o( √ )
1≤a≤k
n0
n0
almost surely, assuming that k is eventually bounded with respect to n0 . For convenience, choose n0
√
large enough such that 4p−1/2 / n0 + o( √1n0 ) ≤ 1/4. Under this assumption:
tL0 =

kEk2,t
2βr + O(r2 )
8βr
≤
=
+ O(r2 )
kL0 k2,t
1 − 1/4
3

Combining this with (5.7) and Theorem 5.6:
!
2
8p−1/2
1
8βr
2
δ̂s ≤ 1 + γ + (1 − γ) √
+ o( √ )
1+
+ O(r ) − 1
n0
n0
3
!

8p−1/2
1
16βr
2
= 1 + γ + (1 − γ) √
+ o( √ )
1+
+ O(r ) − 1
n0
n0
3
!



−1/2 β
1 
128(1
−
γ)p
1
16β(1 + γ)
r
=γ+r
+√
8(1 − γ)p−1/2 + √
+ O(r2 ) + o( √ )
3
n0
n0
3
n0
and letting D1 = 16β(1 + γ)/3, D2 = 8(1 − γ)p−1/2 , D3 = 128(1 − γ)p−1/2 β 2 /3 gives equation (5.6).
Finally, because β → 1 as n → ∞, we indeed have that D1 , D2 and D3 are O(1) with respect to n0 .

16

6

The Coherence Properties for Laplacians of Random Graphs

In this section we study the coherence properties of Laplacians of random graphs. Mainly, we
compute a lower bound for |h`i , `j i| when i and j are in the same cluster and hence a lower bound
for µ(L−1 ). We begin with a basic result for graphs from G(n, k, p, 0).
0
Theorem 6.1.
P Let A be the adjacency matrix of a graph G drawn at random from G(n, k, p, 0) and
define χi,j = k Aik Akj . Suppose further that there exists an α ∈ (0, 1) such that (1 − α)pn0 ≤ d0i ≤
(1 + α)pn0 . Then for any i, j ∈ C1 with i 6= j:
r
r
(1 + α)n0 p ln(1/δ)
(1 + α)n0 p ln(1/δ)
2
2
(1 − α)n0 p −
≤ χi,j ≤ (1 + α)n0 p +
(6.1)
2
2

with probability 1 − δ.
Proof. Let B1 (i) denote the ball of radius 1 centered at i. That is, B1 (i) := {k ∈ [n] : {i, k} ∈ E}.
By definition |B1 (i)| = di . Observe that:
X
X
χi,j =
Aik Akj =
Akj
k

k∈B1 (i)

Each Akj is an i.i.d. Bernoulli random variable with parameter p. Applying the Chernoff bound to
this sum:

q
2 


di ln(1/δ)
r
 2

2
X
di ln(1/δ) 



P
Akj ≤ pdi −
≤ exp −
=δ
2
di


k∈B1 (i)

and (1 − α)pn0 ≤ di ≤ (1 + α)pn0 so:
#
#
"
"
r
r
(1
+
α)n
p
ln(1/δ)
d
ln(1/δ)
0
i
P χi,j ≤ (1 − α)n0 p2 −
≤ P χi,j ≤ pdi −
≤δ
2
2
The upper bound on χi,j is proved analogously.

We now provide a bound on the inner product |h`0i , `0j i| when i and j are in the same cluster:
Theorem 6.2. Let L0 be the Laplacian of a graph G0 drawn at random from G(n, k, p, 0). As in
Theorem 6.1, suppose that there exists an α ∈ (0, 1) such that (1 − α)pn0 ≤ d0i ≤ (1 + α)pn0 but
in addition assume that α is o(1) with respect to n. Define β 2 = (1 + α)/(1 − α). Then for any
δ ∈ (0, 1) and for any i, j ∈ Ca , a ∈ [k], with i 6= j:
s


2
β
1
ln(1/δ)
1
− 3/2
|h`0i , `0j i| ≥
n0 (1 + α)
2(1 + α)3 p3
n
0

with probability 1 − δ for n large enough.
Proof. Recall that
h`0i , `0j i


= −

1
1
+
di dj

17


Aij +

n
X
Aik Ajk
k=1

d2k

There are two possibilities; either i and j are connected ({i, j} ∈ E) or they are not ({i, j} ∈
/ E).
We treat these cases separately. Suppose first that {i, j} ∈
/ E. In this case, Aij = 0 and so:
h`0i , `0j i

=

n
X
Aik Ajk

d2k

k=1

≥

1
d2max

χij

by assumption, dmax ≤ (1 + α)pn0 and by so by Theorem 6.1:
!
r
1
(1 + α)n0 p ln(δ)
0 0
2
h`i , `j i ≥
(1 − α)n0 p − −
2
(1 + α)2 p2 n20
s


1
1
1
− ln(δ)
=
− 3/2
2
n0 (1 + α)β
2(1 + α)3 p3
n

(6.2)

0

Alternatively, suppose that {i, j} ∈ E. Then Aij = 1 and by Theorem 6.1:
2
1
−
χij
dmax
(1 + α)pn0 (1 − α)2 p2 n20
!
r
2
1
(1
+
α)n
p
ln(δ)
0
≥
−
(1 + α)n0 p2 + −
(1 + α)pn0 (1 − α)2 p2 n20
2
s


1
2
β2
1
− ln(δ)β 2
=
−
− 3/2
n0 (1 − α)p (1 + α)
2(1 − α)3 p3
n0

|h`0i , `0j i| ≥

2

−

1

χij
d2min

≥

(6.3)

Let us compare the leading terms in (6.2) and (6.3). Because α → 0 as n → ∞, β → 1 and thus
1/((1 + α)β) → 1. On the other hand, 2/((1 − α)p) − β 2 /(1 − α) → 2/p − 1 > 1, assuming p < 1.
Thus, for n large enough, the right hand side of (6.3) is larger than the right hand side of (6.2), and
so we can summarize both bounds as:
s


1
1
− ln(δ)
β2
0 0
|h`i , `j i| ≥
− 3/2
n0 (1 + α)
2(1
+ α)3 p3
n0
for large enough n.
Next we consider the case where intercluster edges are present, i.e. where q > 0.



Theorem 6.3. Let L be the Laplacian of G drawn from G(n, k, p, q), q > 0, and suppose that i, j ∈ C1 .
Assume further that:
1. p ≥ 4k(ln(n))2 /n
√
2. maxi ri ≤ r with r = r0 / n0 where r0 = O(1) with respect to n0 .
Then almost surely:
1
|h`i , `j i| ≥
n0



β2
1+α


− o(

1
).
n0

where α is o(1) with respect to n and β 2 = (1 + α)/(1 − α).
Proof. As before, let e1i (resp. e1j ) denote the i-th (resp. j-th) column of E1 , while e2i (resp. e2j )
denote the i-th (resp. j-th) column of E2 . Then:
h`i , `j i = h`0i + e1i + e2i , `0j + e1j + e2j i
= h`0i , `0j i + h`0i , e1j i + h`0i , e2j i + he1i , `0j i + he1i , e1j i + he1i , e2j i + he2i , `0j i + he2i , e1j i + he2i , e2j i
18

By construction, e1i and e2j have disjoint support (and similarly for e1j and e2i ), as do `0i and e2j (and
similarly `0j and e2i ). Hence:
h`0i , e2j i = he1i , e2j i = he2i , `0j i = he2i , e1j i = 0
and so:
|h`i , `j i| ≥ h`0i , `0j i − h`0i , e1j i − he1i , `0j i − he1i , e2j i − he2i , e2j i

(6.4)

Now `0i and `0j can be thought of as columns in the Laplacian of a graph drawn at random from
G(n, k, p, 0). By part 2 of Theorem 3.6 we may choose an α = o(1) with respect to n such that
(1 − α)pn0 ≤ d0i ≤ (1 + α)pn0 for all i, with probability 1 − 1/n. Now we apply Theorem 6.2 to get:
s


β2
1
− ln(δ)
1
0 0
− 3/2
|h`i , `j i| ≥
n0 (1 + α)
2(1
+ α)3 p3
n
0

√
−p3 n0

3√

(and noting e−p n0 < 1/n0 for large enough n0 )
with probability 1 − δ − 1/n. Taking δ = e
s
s




1/2
2
2
1
β
1
− ln(δ)
1
β
1
n0
− 3/2
=
− 3/2
n0 (1 + α)
2(1 + α)3 p3
n0 (1 + α)
2(1 + α)3
n0
n0
 2 
 2 
1
β
1
1
β
1
=
− 5/4 √
=
− o(1/n0 )
n0 1 + α
n0 1 + α
2(1 + α)3/2
n0
with probability at least 1 − 1/n0 − 1/n = 1 − (k + 1)/n. Next, we consider the term h`0i , e1j i.
!

0
0
X
r
A
ri A0ij X rm A0im A0mj
A
m
mj
3
|h`0i , e1j i| =
δim − 0im
+
O(r
)
=
+ O(r3 )
0 −
0
0 )2
d
d
(d
d
m
m
m
i
m
m
X
r
r
r
r
0
0
3
≤ 0 + 0 2
A A + O(r ) ≤ 0 + 0 2 min{d0i , d0j } + O(r3 )
dmin (dmin ) m im mj
dmin (dmin )


r
d0
≤ 0
1 + max
+ O(r3 )
dmin
d0min
As stated earlier, d0min ≥ (1 − α)pn0 and d0max ≤ (1 + α)pn0 with probability 1 − 1/n, and so:



r
(1 + α)pn0
r
0 1
|h`i , ej i| ≤
1+
+ O(r3 ) =
1 + β 2 + O(r3 )
(1 − α)pn0
(1 − α)pn0
(1 − α)pn0
Clearly the same bound holds for |he1i , `0j i|. Finally, consider |he1i , e1j i|. A similar calculation to the
one above reveals that:


r2
β4
1 1
|hei , ej i| ≤
+ O(r4 )
n0 (1 − α)p
as well as:
|he2i , e2j i| ≤

r
+ O(r3 )
(1 − α)pn0

Putting all these bounds back in to equation (6.4), we get:
 2 




1
β
1
2r(1 + β 2 )
r2
β4
r
3
4
3
|h`i , `j i| ≥
− o( ) −
+ O(r ) +
+ O(r ) +
+ O(r )
n0 1 + α
n0
(1 − α)pn0
n0 (1 − α)p
(1 − α)pn0
 2 


1
β
r 2(1 + β 2 )
rβ 4
1
=
−
+
+
+ O(r3 )
n0 1 + α
n0 (1 − α)p
(1 − α)p (1 − α)p
19

√
3/2
Using the assumption that r = r0 / n0 , we see that r/n0 = r0 /n0 which is of order o(1/n0 ).
3/2
Similarly r3 = r03 /n0 which is also of order o(1/n0 ). Thus:
 2 
1
β
1
|h`i , `j i| ≥
− o( )
n0 1 + α
n0
with probability 1 − O(1/n0 ), as claimed.



Remark 6.4.
 Since
 the coherence µ of L is defined as µ = maxi6=j |h`i , `j i|. Theorem 6.3 also implies
β2
1
thatµ ≥ n0 1+α − o( n10 ).

7

Compressive Sensing Clustering for Graphs from G(n, k, p, 0)

In this section, we consider graphs from G(n, k, p, 0). This is the case that there are no inter-cluster
edges. We may safely assume that each GCi is connected, as long as p > ln(n0 )/n0 .
Lemma 7.1. Let L be the Laplacian of a graph with k connected components C1 , . . . , Ck . Assume,
without loss of generality, that vertex 1 ∈ C1 . Define x# as:
x# := arg min{kxk0 : x ∈ Rn , Lx = 0 and x1 = 1}

(7.1)

Then x# = 1C1
Proof. From Theorem 3.3, ker(L) = span{1C1 , . . . , 1Ck } and hence any x with Lx = 0 can be
P
written as: x = ki=1 ci 1Ci . If x1 = 1 (recall we are assuming that 1 ∈ C1 ) then c1 = 1 and so
P
x = 1C1 + ki=2 ci 1Ci . Recall that all the 1Ci have disjoint support, and so clearly the sparsest
solution x such that Lx = 0 is that x has c2 = c3 = . . . = ck = 0. Hence indeed x# = 1C1

One can rephrase this slightly as a standard compressed sensing problem. Recall `i is the i-th
column of L and L−i := [`1 , . . . , `i−1 , `i+1 , . . . , `n ] in which case:
xi = 1

⇔

L−i x−i = −`i ,

where if x = [x1 , x2 , . . . , xn ]> ∈ Rn , x−i = [x1 , . . . , xi−1 , xi+1 , . . . , xn ]> ∈ Rn−1 . Thus problem (7.1)
becomes:
x# := arg min{kxk0 : x ∈ Rn−1 , Lx = −`1 }.
(7.2)
We now show that problem (7.2) can be efficiently solved using OMP (Algorithm 2 in §4)
Theorem 7.2. Suppose that G ∈ G(n, k, p, 0) has k connected components C1 , . . . , Ck ⊂ V each of
size n0 . OMP (Algorithm 2) applied to the sparse recovery problem (7.2) will return x# = 1C1 \{1}
after n0 − 1 iterations. C1 can then be recovered as {1} ∪ supp(x# ).
Remark 7.3. Note that the assumption that G ∈ G(n, k, p, 0) is not necessary; this theorem holds
for all graphs with k connected components. Also, observe that this theorem is not probabilistic. It
holds with certainty for all graphs G.
We shall appeal to the exact recovery condition, Theorem 4.1 to establish Theorem 7.2. Let us
begin with
Lemma 7.4. If C1 ⊂ V is a connected component then LC1 \{1} is injective, where LC1 \{1} is the
submatrix from L with column indices in C1 \ {1}.
20


L1−1
Proof. First, observe that LC1 \{1} =
, where L1 is the Laplacian of GC1 . It suffices to
0
show that L1−1 is injective. As GC1 is connected, ker(L1 ) = span{1}, by Theorem 3.2. Suppose
there exists a u ∈ Rn0 −1 , u 6= 0 such that L1−1 u = 0. Then [0, u> ]> is in ker(L1 ) = span{1}, a
contradiction.



Theorem 7.5. With notation as above (i.e. C1 is the connected component of G containing the first
vertex) we have that:
kL†C1 \{1} LC1c k1 = 0
(7.3)
Proof. By Lemma 7.4 LC1 \{1} is injective so its pseudo-inverse is given by:

−1
L
L†C1 \{1} = L>
L>
C1 \{1} C1 \{1}
C1 \{1}
 1 
 
0
L−1
As observed in the proof of Lemma 7.4, LC1 \{1} =
. Similarly, LC1c =
, where L̃ denotes
0
L̃
the Laplacian of GC1c . In both cases 0 denotes the zero matrix of appropriate size. To show (7.3) it
c
will suffice to show that L>
C1 \{1} LC1 = 0, but this follows easily as:
 

 0
(L1−1 )> 0>
= (L1−1 )> 0 + 0> L̃ = 0
L̃
This completes the proof.
 Theorem 7.2 now follows easily:
Proof. [Proof of Theorem 7.2] By Theorem 7.5 the exact recover condition (Theorem 4.1) holds ,
and thus the result follows.


8

Compressive Sensing Clustering for Graphs from G(n, k, p, q)

We now turn our attention to the same problem for G(n, k, p, q) with 0 < q << p. We follow the
notation established in §5.3, and decompose A as A = A0 + A where A contains the intercluster
edges and A0 is the adjacency matrix of the subgraph G0 with k connected components. Denoting
the i-th column of L0 as `0i and the i-th column of E as ei , observe that
`1 = `01 + e1 = −L0 1C1 \{1} + e1

or

− `1 = L1C1 \{1} − e1 .

Defining x# as:
x# := arg min{kL−1 x − (−`1 )k2 : x ∈ Rn−1 , kxk0 ≤ n0 }.

(8.1)

Then x# ≈ 1C1 \{1} . We recognize this as a totally perturbed sparse recovery problem (4.7), with
Φ = L0 , Φ̂ = L0 + E = L, y = −`1 = −`01 − e1 . We shall show that, provided E is small enough,
supp(x# ) = supp(1C1 \{1} ) = C1 \ {1}. Hence, solving problem (8.1) is equivalent to finding the
community C1 .
Unfortunately, a straightforward application of Algorithm 2 to (8.1) does not work. Empirically,
it is observed that the first several greedy steps in Algorithm 2 invariably pick up wrong indices due
to the presence of noise E. We need a new approach. Let us start with the following
Theorem 8.1. Let L be the Laplacian of a graph G ∈ G(n, k, p, q) with p ≥ 4k(ln(n))2 /n. Suppose
that
max ri := max di /d0i ≤ r,
(8.2)
i∈{1,...,n}

i∈{1,··· ,n}

√

where r = r0 / n0 with r0 a constant independent of n0 . Define Ω := Ld10(n0 −1)/9e (L>
−1 `1 ). For n0
large enough, we have that C1 \ {1} ⊂ Ω almost surely.
21

Proof. Suppose otherwise, then there exists an i∗ ∈ C1 \ {1} not in Ω. Let Λ = Ω ∩ C1c . As we are
assuming that C1 \ {1} 6⊂ Ω, we have that |Λ| ≥ n0 /9. Moreover, by definition of i∗ , we have that
|h`1 , `i∗ i| ≤ |h`1 , `j i| for all j ∈ Ω, and in particular:
|h`1 , `i∗ i| ≤ |h`1 , `j i| for all j ∈ Λ
Summing over Λ we get:
|Λ||h`1 , `i∗ i| ≤

X

|h`1 , `j i| = kL>
Λ `1 k 1

(8.3)

j∈Λ

We shall show that equation (8.3) cannot hold for n0 large enough. Because p ≥ 4k(ln(n))2 /n and
r << 1, we may use Theorem 5.8, which we shall do repeatedly. By this theorem, we have that
L = L0 + E = L0 + E1 + E2 with kEj k∞ ≤ r = O(r2 ) for j = 1, 2. Moreover by construction
0
L0Λ =
where L̃ denotes the Laplacian of the subgraph GC1c and 0 is the zero matrix of size
L̃Λ
 1
`
n0 × |Λ|. Similarly, `1 = `01 + e1 and we may write `01 = 1 where `11 ∈ Rn0 is the first column of
0
1
L , the Laplacian of the subgraph GC1 and 0 is the zero vector of length n − n0 . Thus:
0 > 0
0 >
> 1
kL>
Λ `1 k1 ≤ k(LΛ ) `1 k1 + k(LΛ ) e1 k1 + kE ` k1
 1
 `1

+ k(L0Λ )> e1 k1 + kE> `1 k1
= 0> L̃>
Λ
0

≤ 0 + k(L0Λ )> k1 ke1 k1 + kE> k1 k`1 k1

(8.4)

Now k(L0Λ )> k1 = kL0Λ k∞ , as these are dual norms. As k · k∞ is equal to the maximum absolute row
sum, it is clear that kL0Λ k∞ ≤ kL0 k∞ . Now:




0
X
X
A
1
1
ij
0
0
0
kL k∞ = max
δij − 0 = max 1 + 0
Aij  = max 1 + 0 (di ) = 2
i
i
i
d
d
di
i
i
j
j6=i

Moreover, ke1 k1 ≤ maxi kei k1 = kEk1 , hence ke1 k1 ≤ 2β 2 r + O(r2 ), while kE> k1 = kEk∞ ≤
kE1 k∞ + kE2 k∞ = 2r + O(r2 ) both by Theorem 5.8. Finally, `1 = `01 + e1 as above, so k`1 k ≤
k`01 k1 + β 2 r + O(r2 ). We compute k`01 k1 :
k`01 k1 =

n
X
i=1

n

δi1 −

X A0
A0i1
1
(1 + α)pn0
i1
(d01 ) ≤ 1 +
= 1 + β2
=
1
+
≤1+
0
0
d
(1
−
α)pn
di
d
min
0
i
i=2

Returning to equation (8.4):
2
2
2
2
2
kL>
Λ `1 k1 ≤ (2)(2β r) + (2r)(1 + β ) + O(r ) = (2 + 6β )r + O(r ) =

On the other hand, by Theorem 6.3 we have that:
 2 
1
β
1
− o( )
|h`1 , `i∗ i| ≥
n0 1 + α
n0

22

(2 + 6β 2 )r0
+ O(r2 )
√
n0

almost surely, and so we can bound the left hand side of (8.3) as:
  2 

β
1
β2
n0 1
∗
− o( ) =
|Λ||h`1 , `i i| ≥
− o(1)
9 n0 1 + α
n0
9(1 + α)
Thus, if inequality (8.3) were true, it would imply that:
β2
(2 + 6β 2 )r0
+ O(r2 )
− o(1) ≤
√
9(1 + α)
n0
which cannot be true for n0 large enough, as α and r are o(1) with respect to n0 and β 2 is O(1), thus
√
β 2 /(9(1 + α)) − o(1) → 1/9 while (2 + 6β 2 )r0 / n0 → 0. Hence we may always take n0 large enough
so that, with probability at least 1 − 1/n0 , inequality (8.3) cannot hold. Thus no such i∗ which is in
C1 \ {1} but not in Ω can be found, and so the Theorem 8.1 is proved.

With the result of Theorem 8.1 in mind, we are able to derive a new algorithm to find the
communities from G ∈ G(n, k, p, q) for p >> q > 0:
Algorithm 4 Single Cluster Pursuit (SCP)
Input: The adjacency matrix A of a graph G, and estimate of the size of clusters n0
(1) Initialization Compute L = I − D−1 A.
(2) Trimming
Let Ω = Ld10(n0 −1)/9e (L>
−1 `1 )
(3) Perturbed Sparse Recovery
P
(a) y = i∈Ω `i + `1
(b) Solve z# = arg min{kLΩ z − yk2 s.t. z ∈ R|Ω| and kzk0 ≤ n0 /9} using the SP algorithm
(c) Λ# = supp(z# ).

Output: C1# = {1} ∪ Ω \ Λ# .
Next we show that Algorithm 4 succeeds almost surely.
Theorem 8.2. Let G be a graph drawn at random from the G(n, k, p, q) model. Suppose that k = O(1)
with respect to n and either:
1. q =

Q
n

and p =

√

P ln(n)
n ln(ln(n))

with Q and P being constants and P > 979, or

with Q → ∞ as n → ∞ and p =
2. q = Q ln(n)
n
large enough n.

P ln(n)
√
n

with P → ∞ as n → ∞ and

Q
P

<

1
979

for

Then Algorithm 4 will recover C1 (that is, C1# = C1 ) almost surely.
Proof. For notational convenience let s := (n0 − 1)/9. In both cases, p ≥ 4k(ln(n))2 /n and so by
part 2 of Theorem 3.6, d0min ≥ (1 − α)n0 p almost surely for α = o(1) with respect to n. In case 1,
by (i) of Theorem 3.4 in [25], dmax ≤ ln(n)/(ln(ln(n)) − ln(ln(ln(n))) almost surely. Ignoring the
triple-logarithmic term:
d
d
1
r0
max 0i ≤ max
≤
√ =: √
i di
P (1 − α) n0
n0
d0min
with r0 < 1/979 for large enough n as α = o(1). In case 2, by (ii) of Theorem 3.4 in [25], dmax ≤
Q ln(n) almost surely, and so:
max
i

di
dmax
Q/P
r0
≤
≤
√ =: √
0
0
(1
−
α)
n
n0
di
dmin
0
23

and again r0 < 1/979 for large enough n. We may thus apply Theorem 8.1 to get that C1 \ {1} ⊂ Ω
almost surely. As before we define Λ := Ω ∩ C1c ; it is easy to see |Λ| ≤ n0 /9. The challenge in step (3)
of Algorithm 4 is to separate C1 \ {1} from Λ. We do this by solving for 1Λ = 1Ω − 1C1 \{1} instead
of 1C1 \{1} , as:
X

L0Ω 1Λ = L0Ω 1Ω − 1C1 \{1} = L0Ω 1Ω − L0Ω 1C1 \{1} =
`0i − (−`01 ) =: y0

(8.5)

i∈Ω

and noting that k1Λ k0 ≤ n0 /9, we see that 1Λ is the unique solution to
arg min{kL0Ω z − y0 k2 : z ∈ Rd10n0 /9e , kzk0 ≤ n0 /9}

(8.6)

Defining y to be a perturbation of y0 and writing, as in §5.3, LΩ = L0Ω + EΩ :
!
y :=

X
i∈Ω

Defining e = e1 +

P

i∈Ω ei

`i + `1 =

X

`0i +

i∈Ω

X

ei + `01 + e1 = y0 +

e1 +

i∈Ω

X

ei

i∈Ω

we recognize the problem:

z# = arg min{kLΩ z − yk2 : z ∈ Rd10n0 /9e , kzk0 ≤ n0 /9}

(8.7)

as a totally perturbed version of (8.6). Thus, we may apply the results of §4.3 to bound kz# − 1Λ k2 .
As in §4.3, we define δt := δt (L0 ) and δ̂t := δt (L). (We refer the reader to §4.3 for the definitions of
sL0 , y , ρ̂ and τ̂ .) Let us bound on these quantities. Observe that in both cases, p >> (ln(n0 ))2 /n0
and by assumption k is O(1) with respect to n, thus as in the proof of Theorem 5.10 we get sL0 =
√
8βr/3 = 8βr0 /(3 n0 ), for n0 large enough. Applying the result of Theorem 5.10 with t = 3s = n0 /3:
1
D2
D3 r
1
+ D1 r + √ + √ + O(r2 ) + o( √ )
3
n0
n0
n0
1 (D1 r0 + D2 ) D3 r0
1
1
1 (D1 r0 + D2 )
1
= +
+
+ O( ) + o( √ ) = +
+ o( √ ).
√
√
3
n0
n0
n0
n0
3
n0
n0

δ̂3s ≤

Hence for large enough n0 , we certainly have δ̂3s ≤ 0.4859 as required. In fact, let us take n0 large
enough such that δ̂3s ≤ 1/3 + 1/18 = 7/18 ≈ 0.39. Choosing n0 larger if necessary, we shall also
assume that sL0 < 1/3. In this case, a straightforward, but tedious calculation will reveal that
ρ̂ ≤ 0.7 and similarly τ̂ < 166 (see the statement of Theorem 4.6 for the definitions of ρ̂ and τ̂ ). We
now turn our attention to y .
p
p
√
ky0 k2 = kL0Ω1 1Λ k2 ≥ 1 − δs k1Λ k2 = 1 − δs s
while
kek2 = kE1Ω + e1 k2 ≤ kEk2 k1Ω∪{1} k2 ≤ 2βr + O(r2 )
So we have

√

10s.

√

√
2 10 2βr + O(r2 )
kek2
2 10βr0
1
√
y :=
=
=p
+ o( √ )
0
ky k2
n0
1 − δs
n0 (1 − δs )

Appealing to Theorem 5.10 with s = n0 /9:
δs ≤ 1/9 +

64p−1/2
1
+ o( √ ).
√
9 n0
n0
24

Again, we will assume that n0 is large enough such that δs ≤ 2/9 ≈ 0.22. Under this assumption:
√
βr0
2 10 βr0
y ≤ p
√ ≤ 8√
n0
7/9 n0
Finally, we use Theorem 5.10 again, this time with t = s = n0 /9:
δ̂s ≤ 1/9 +

1
D1 r0 + D2
+ o( √ )
√
n0
n0

and take n0 large enough such that δ̂s ≤ 2/9 (this is possible as D1 and D2 are O(1) with respect to
n0 ). Now Theorem 4.6 guarantees that
!
p
kxm − 1Λ k2
1 + δ̂s
≤ τ̂
+ 1 (sL0 + y )
k1Λ k2
1 − sL0
Where m := ln(sL0 + y )/ ln(ρ̂) = O(ln(n0 )). Substituting in for the various constants:
!
p
√

1 + 2/9
kxm − 1Λ k2
8βr0
166( 11)(32) βr0
8βr0
=
< (166)
√ +√
√
k1Λ k2
1 − 1/3
3 n0
n0
6
n0
√ 
n0
βr0
2937 √ = 979βr0
⇒kxm − 1Λ k2 <
3
n0
As the Lemma 8.3 below, as long as kxm − 1Λ k2 < 1, we have that supp(xm ) = supp(1Λ ). Because
β → 1 and r0 < 1/979, this will hold for large enough n0 .

Lemma 8.3. Suppose that x∗ ∈ Rn is a binary vector with kx∗ k0 = t, and x ∈ Rn is any other
vector that also has kxk0 = t. If kx∗ − xk2 < 1 then supp(x) = supp(x∗ ).
Proof. Suppose otherwise. Then there exists an i ∈ supp(x∗ ) \ supp(x). Clearly:
kx∗ − xk2 ≥ |x∗i − xi | = |1 − 0| = 1
which contradicts the hypotheses.

As mentioned in the introduction, we may iterate Algorithm 4 to find all the clusters of G. We
call this algorithm Iterated Single Cluster Pursuit, or ISCP.

9

Computational Complexity and Extensions

In this section we bound the computational complexity and explain some extensions.

9.1

Computational Complexity

In this subsection we show that Algorithm 4 is faster than existing spectral methods. We do this by
determining the approximate number of operations required in each step of Algorithm 4. Throughout,
we shall assume that A and L are sparse matrices.
P
1. Computing di = j Aij requires di operations. We can safely assume that di = d0i + di ≤ n0
so the cost of computing each di is at most O(n0 ) This needs to be done a total of n times to
compute D = diag(d1 , . . . , dn ), giving a total cost of O(nn0 ).
25

2. The cost of the thresholding step is dominated by the matrix-vector multiply L>
−1 `1 . Because
`1 has d1 + 1 ≤ n0 non-zero entries, the cost of this is bounded by O(nn0 ).
3. The computational cost of solving the perturbed sparse recovery problem in step 3 using SP
is equal to the number of iteration times the cost of each iteration. As shown in the proof of
Theorem 8.2, it suffices to perform O(ln(n0 )) = O(ln(n)) iterations. The cost of each iteration
is determined by calculating the cost of each step in the iterative part of SP (see Algorithm 3):
k−1 ) is dominated by the cost of the matrix-vector multiply L> rk−1 ,
(a) Computing Ls (L>
Ωr
Ω
hence is O(nn0 ).

(b) Solving the least square problem in step (2) using a good numerical solver (we used
MATLAB’s lsqr algorithm) is on the order of the cost of a matrix-vector multiply, i.e.
O(nn0 ), as explained in [38].
(c) The cost of sorting and thresholding (step (3)) is O(n ln(n)).
(d) Finally the cost of computing the new residual rk in step (4) is dominated by the matrix
k
vector multiply L>
Ω1 r , hence is O(nn0 ).
We conclude that the cost of a single iteration of the SP Algorithm is O(nn0 ), and so the cost
of step 3 of Algorithm 4 is O(n ln(n)n0 )
Thus, the number of computations required to find a single cluster using Algorithm 4 is O(n ln(n)n0 ).
To find all the clusters C1 , . . . , Ck one can iterate Algorithm 4 k − 1 times. The cost of this is
certainly less than O(kn ln(n)n0 ) = O(n2 ln(n)).

9.2

Extensions

1. Our Algorithm 4 can be extended to deal with the communities of non-equal size. Hence, our
study can be extended too. A numerical example is included in the next section to demonstrate
this extension. For simplicity, we leave the study for the interested reader.
2. Although Algorithm 4 works on binary adjacency matrices, it handles weighted adjacency
matrices just as well (see §10.2.2).
3. As mentioned in the introduction, graph clustering can also be applied to more general data
sets. Given any (finite) set of points X = {x1 , . . . , xn } in some metric space (M, d), there
are several ways to associate a graph on n vertices to X. For example, we could attach an
edge between vertices i and j whenever d(xi , xj ) ≤ C for some constant C. Alternatively, for
each vertex i we could determine the K closest points to xi , say {xj1 , . . . , xjK }, and insert the
edges {i, j1 }, . . . , {i, jK } to obtain the K-nearest neighbours graph GK . Empirically, we have
found the latter approach to perform better, as dmin (GK ) = K giving better control over the
quantities ri crucial to the analysis of Algorithm 4. See §10.2.2 for an example of this approach.
4. Algorithm 4 can easily be extended to the co-clustering problem, as described in [15]. Briefly
suppose that we are given two categorically different sets of variables X = {x1 , . . . , xn } and
Y = {y1 , . . . , ym } as well as a n × m matrix B such that the Bij -th entry represents the
correlation between xi and yj . The goal of co-clustering is to simultaneously partition X
and Y into subsets X = X1 ∪ . . . Xk and Y = Y1 ∪ . . . ∪ Yk such that the correlations
between x ∈ Xi and y ∈ Yi are strong while the correlations between x ∈ Xi and y ∈ Yj for
i 6= j are weak. As pointed out by Dhillon in [15], one can regard this as a graph clustering
26

problem for a weighted5 bipartite graph with vertex set V = {u1 , . . . , un , v1 , . . . , vm } and
weights w(ui , vj ) = Bij , w(ui , uj ) = w(vi , vj ) = 0. The adjacency matrix and Laplacian of G
are:




0 B
In×n
−D−1
B
X
A=
L=
>
B> 0
−D−1
Im×m
Y B
where DX represents the row sums of B while DY represents the column sums. Assume
temporarily that instead of clusters G has k connected components C1 , . . . , Ck . Each GCi will
be a bipartite graph, and Ci splits as Ci = CiX ∪ CiY where CiX corresponds to Xi and similarly
> >
CiY corresponds to Yi . The indicator vector will split similarly: 1Ci = [1>
Xi 1Yi ] and:
1Xi − D−1
X B1Yi
=
−1 >
1Yi − DY B 1Xi


0 = L1Ci



We may convert these two ‘first-order’ equations into a single ‘second-order’ equation as 1Yi =
>
D−1
Y B 1Xi and so:


−1 >
−1
−1 >
0 = 1Xi − D−1
BD
B
1
=
I
−
D
BD
B
1Xi
X
i
X
Y
X
Y
−1 >
Defining the ‘bi-partite Laplacian’ as LBP = I − D−1
X BDY B we see that if x1 ∈ X1 then the
indicator vector 1X1 is the unique solution to:

arg min{kzk0 :

z ∈ Rn , LBP z = 0 and z1 = 1}

−1 >
once we have found 1X1 we can recover 1Y1 as 1Y1 = DY
B 1X1 . Returning to the clustering
problem, we see that we may approximate 1X1 ( and hence 1Yi ) by solving the problem

arg min{kLBP
−1 z − (−`BP,1 )k2 :

z ∈ Rn−1 , kzk0 ≤ nX
0 − 1}

using Algorithm 4, where nX
0 is the size of the clusters Xi . We leave the technical analysis of
this approach to the interested reader.
5. In future work, we intend to show how Algorithm 4 can be adapted into an ‘online’ algorithm
which allows one to rapidly update the community assignments as more vertices are added to
the graph.

10

Numerical Examples

10.1

Synthetic Data

We tested Single Cluster Pursuit (SCP, Algorithm 4) on graphs drawn from the SBM. We implemented this algorithm in MATLAB 2016b and run on a mid-2010 iMac computer with 8 GB of RAM and
a 3.06 GHz Intel Core i3 processor. For comparison we used the Trembley, Puy, Gribonval and Vandergheynst implementation of Spectral Clustering (SC, Algorithm 1) included in their Compressive
Spectral Clustering toolbox available at http://cscbox.gforge.inria.fr/ ([45]).
5

We assume that the correlations Bij are non-negative

27

10.1.1

Example 1

Typical output of SCP applied to randomly drawn graphs from the SMB G(n, k, p, q) with p =
√
P ln(n)/ n and q = Q ln(n)/n as in case 2 of Theorem 8.2 is shown in the third frame of figure 1.
Both SCP and SC succeed in finding cluster 1 without error (indeed SC finds all clusters without
error) but SCP is faster, taking 0.0262 seconds compared to the 0.1018 seconds required by SC. We
remark that even for Q, P such that Q/P >> 1/979 SCP is successful, suggesting that the bounds
in Theorem 8.2 are too conservative.

√
, 2 ln(n)
Figure 1: The adjacency matrix of a graph drawn from G(1000, 5, 2 ln(n)
n ) is shown in the top
n
left. The same matrix, with its rows and columns randomly permuted (using the same permutation
for both) is shown in the top right. The output of SCP applied to the permuted matrix is shown in
the bottom left, while the output of SC on the same matrix is shown on the bottom right.

10.1.2

Example 2

We then tested Iterated SCP (ISCP) for graphs randomly drawn from the SBM G(n, k, p, q) with
√
p = P ln(n)/ n and q = Q ln(n)/n. Typical output is shown in Figure 2. Again, both algorithms
are successful (that is, both find all 10 communities without error).

28

√
Figure 2: The adjacency matrix of a graph drawn at random from G(5000, 10, 4 ln(n)
, 4 ln(n)
n ) is shown
n
in the top left. The same matrix, with its rows and columns randomly permuted (using the same
permutation for both) is shown in the top right. The output of SCP applied to the permuted matrix
is shown in the bottom left, while the output of SC on the same matrix is shown on the bottom
right.

10.1.3

Example 3

Next, we tested the resilience of SCP to noise by running it on G drawn at random from G(2400, 6, 0.5, q)
with q increasing from 0 to 150/2000. For each q, we ran SCP on 10 different G drawn independently and at random from G(2400, 6, 0.5, q) and computed the average fraction of indices that were
misclassified. Figure 3 shows the result of this experiment, with E[di ] = q(n − n0 ) on the x-axis.
As observed in Experiment 1, SCP performs much better than theoretically guaranteed by Theorem
8.2. Indeed, Figure 3 demonstrates that SCP detects community 1 without error up until E[di ] = 40,
at which r ≈ 40/200 = 1/5.

29

Figure 3: Fraction of indices misclassified by SCP, for G ∈ G(2400, 6, 0.5, Q/2000). The horizontal
axis represents Q, that is, the level of ‘noise’ in the graph. The vertical axis represents the fraction
of misclassified vertices = |C1# \ C1 |/|C1# |. As can be seen, SCP performs without error until Q ≈ 40,
well beyond the theoretical guarantees given by Theorem 8.2
10.1.4

Example 5

In our final example, we use ISCP to solve the co-clustering problem, as discussed in §9.2. Typical
output is shown in image 4

Figure 4: A 2000 × 1000 binary matrix with 10 equally sized block, randomly permuted and then
co-clustered using ISCP, applied as discussed in §9.2.
10.1.5

Example 4

Finally we compared the run times of SCP, SC and ISCP on G(n, k, p, q) for increasing n. We studied
√
three regimes: constant k, constant n0 (cluster size) and k, n0 = O( n). In all three cases we fixed
√
p = 2 log(n)/ n and q = 2 log(n)/n. The results of these experiments are presented in figures 5c
- 5b (the run times are in seconds, and are the average of ten independent trials for the same n).
As is clear, SCP significantly outperforms SC in finding a single cluster. Moreover, when k is large
enough compared to the number of vertices (n), ISCP finds all clusters faster than SC.
30


(a) Varying k from 20 to 120 and n accordingly, while fixing n0 . G ∈ G 400k, k,


(b) Varying k, n0 and n. G ∈ G kn0 , k,

2 log(n) 2 log(n)
√
, n
n


log(n)
(c) Varying n and n0 while fixing k. G ∈ G n, 40, 2√
,
(n)

2 log(n) 2 log(n)
√
, n
n





2 log(n)
n



Figure 5: Comparing SCP, ISCP and SC for graphs drawn from the SBM of increasing size. As can
be seen, SCP is significantly faster than SC
31

10.2

Real Data Sets

We now present two examples of SCP and ISCP applied to real-world data sets.
10.2.1

Political Blogs Data Set

The polblogs data set is a collection of 1494 political weblogs, or blogs, collected by Adamic and
Glance ([4]) prior to the 2004 American presidential election. The data is presented as an unweighted,
undirected graph, with vertices corresponding to the blogs, and edges between blogs i and j if there
is a hyperlink from i to j, or vice versa. This data set is well-studied (see, for example [32], [39] and
[42], amongst others), and is a good test case for at least two reasons:
1. In addition to a natural division into two roughly equally sized clusters (liberal vs. conservative), the data set exhibits additional clustering at smaller scales. That is, within the set of
all liberal blogs, one can identify subclusters of blogs, and similarly for the conservative blogs.
This is explored further in [42].
2. The ground truth for the division into liberal vs. conservative is known, as Adamic and Glance
([4]) manually labelled the data set. This provides an opportunity to verify one’s results that
is rare for real-world data sets.
Our methodology was as follows. We follow Olhede and Wolfe ([42]) in using only the 1224 blogs
with links to at least one other blog in the data set. As SCP can be thrown off by low degree vertices
( these will have high values of ri ) we experimented with different thresholds. That is, we discarded
vertices of degree lower than dthresh for varying values of dthresh . We then used SCP to detect a
cluster containing an arbitrary liberal blog, of size approximately equal to the number of liberal
blogs. We call this cluster Cluster 1 (C1 ). We call the remaining vertices Cluster 2 C2 . The results
are tabulated in ??. We record the number of vertices left after thresholding, the percentage of the
first cluster consisting of liberal blogs, the percentage of the second cluster consisting of conservative
blogs and the time taken. The values shown are the averages of ten independent runs.
dthresh
0
2
4
6
8
10
12
14
16
18

# of vertices
1224
1087
903
813
735
693
644
596
547
505

% of C1 liberal
63.71
71.57
81.45
89.12
91.95
93.14
93.95
93.05
94.24
93.97

% of C2 conservative
66.93
75.68
83.86
91.06
93.69
94.57
95.32
94.66
95.39
94.87

time (in seconds)
0.0380
0.0928
0.0467
0.0479
0.0428
0.0411
0.0256
0.0377
0.0379
0.0225

Table 1: Results of SCP applied to the polblogs data set for varying degree thresholds. When
dthresh = 10 the fraction of cluster 1 classified as liberal, and the fraction of cluster 2 identified as
conservative, closely resemble the compositions reported by Newman in [39]

As is clear, increasing dthresh above 10 makes little difference. Our results also agree with the
clusters found by Newman in [39], where he finds one cluster which is 93% liberal, and a second
32

cluster which is 97% conservative. Of course, to achieve this accuracy we have had to discard over
40% of our data points. An interesting future line of research would be to improve the handling of
low degree vertices by SCP.
To detect clustering at a finer scale, we ran SCP to find a cluster of size 80 containing a randomly
selected liberal blog (smithersmpls.com). The output of this is shown in figure 7. As can be seen
by the increased density of the top-left hand corner, our algorithm finds a subset of blogs containing
smithersmpls.com that are more densely connected to each other than they are to the rest of the
data set. We remark that this experiment took approximately 0.06 seconds, so with even modest
computational resources one could investigate clustering at a large range of scales in such a data set.

Figure 6: Typical Output of SCP applied to the polblogs data set with dthresh = 10.

Figure 7: Detecting fine scale structure in the polblogs data set. The top left hand corner represents
a sub-cluster of 80 liberal blogs containing a given randomly selected liberal blog.

33

10.2.2

Gene Expression Data Set

Our second data set consists of Gene Expression values collected via Microarray for a sample of
Neurospora crassa at 13 different time points, originally studied in [16]. The data consists of 2436
time series, one for each Gene of interest, consisting of 13 scaled expression readings. Each scaled
expression reading is a floating point number between 4 and 13. We treat this data as a set of 2436
data points X = {x1 , . . . , x2436 } in R13 . We then constructed an Affinity
Matrix A1 as suggested
√
in [41] defined as A1ij = exp(−kxi − xj k22 /σ 2 ). Here σ was chosen to be 10 although we note that
experimenting with other values of σ did not qualitatively change the results.
To promote sparsity, we added the additional step of constructing a K-nearest-neighbours adjacency matrix from A1 by retaining the (weighted) edge {i, j} if and only if xj is among the K
nearest neighbours of xi or vice versa. Call the resulting adjacency matrix A2,K . We remark that,
much like the parameter σ used in constructing A1 , varying K did not qualitatively affect the results
obtained. Thus, we shall fix K = 100 and refer to A2,100 simply as A2 . Figure 8 shows the results
of this preprocessing in reverse-grayscale (that is, larger values are darker).

Figure 8: The adjacency matrix A2 , resulting from preprocessing the Gene Expression Data set
originally studied in [16].

We used ISCP to look for clusters on two different scales, informed by the underlying biology of

34

the data set6 . First, we looked for clusters of size 90 − 100, as this is around the number of genes
targeted by a single regulator in N. crassa. The results of this experiment are shown in figure 9.
In a well studied organism such as N. crassa, the functions of many genes are known. In fact of the
2436 genes in this data set, more than half of them (1442) have been assigned a MIPS label, which is
an hierarchical system for labelling genes by function. Moreover, in [16], the genes in this data set are
grouped into twelve categories according to their functions, for example ‘signaling’ or ‘transcriptional
control and regulation’. Biologically, an interesting question is which functional categories cluster
together. Thus, for our second numerical experiment we used ISCP to detect clusters of size 450−550
(results pictured in Figure 10) and recorded the number of genes of each category 7 occurring in each
cluster. We can assess the biological significance of this clustering by performing a chi-squared test.
The null hypothesis is that there is no relation between the clusters and the functional categories,
in which the expected number of genes in Category j contained in Cluster i, in the notation of
R
Table ??, is Eij = TC
j × (Ti /1442). For example, E12 = 164 × (321/1442) = 36.51 Denoting the
observed
(i.e. O12 = 32, O21 = 19 and so on) we compute the chi-squared test statistic
P P counts by Oij
2
as i j (Eij − Oij ) /Eij = 73.87. From a table of values for the χ2 distribution8 , we get that
assuming the null hypothesis there is a 0.1% chance that this statistic is greater than 73.40. Thus,
we may safely reject the null hypothesis, and assume that the Clustering found by ISCP is related
to the functions of the genes in the data set.
Category

1

2

3

4

5

6

7

8

9

10

11

TR

Cluster size

1
2
3
4
5

13
19
13
15
20

32
36
23
32
41

15
18
21
14
19

22
28
33
17
31

42
24
34
22
35

46
37
57
27
26

36
11
10
17
18

19
10
13
2
15

8
12
11
5
9

20
25
32
22
13

68
70
71
47
66

321
290
318
220
293

527
513
452
554
390

TC

80

164

87

131

157

193

92

59

45

112

322

1442

2436

Cluster

Table 2: The number of genes in each category present in each cluster. The row totals represent
the number of genes with a MIPS classifier present in each cluster (the total number of genes with
a MIPS classifier is 1442). Anomalously high or low counts are shown in bold.
6

and the authors gratefully acknowledge many informative discussions with Professor Jonathan Arnold and his lab
For a description of the categories the reader is referred to [16]. The counts are displayed in Table ??. The
categories are numbered by the order in which they appear in figure 15 in [16], omitting the category ‘clock’ as there
are no MIPS codes associated with this category.
8
Note that there are (#rows − 1)(#columns − 1) = 40 degrees of freedom here
7

35

Figure 9: Output of ISCP applied to A2 , set to find clusters of size 90 − 100.

Figure 10: Output of ICSP applied to A2 , set to find clusters of size 450 − 550.

36

References
[1] E. Abbe, Community detection and stochastic block models: recent developments, arXiv
preprint arXiv:1703.10146 (2017).
[2] E. Abbe, A.S. Bandeira, and G. Hall, Exact recovery in the stochastic block model, IEEE
transactions on Information Theory Vol. 62 no. 1, pp. 471-487 (2016).
[3] E. Abbe and C. Sandon, Community detection in general stochastic block models: Fundamental
limits and efficient algorithms for recovery. Foundations of Computer Science (FOCS), 2015
IEEE 56th Annual Symposium on, pp. 670-688 (2015).
[4] L. A. Adamic and N. Glance, The political blogosphere and the 2004 us election: divided they
blog. Proceedings of the 3rd international workshop on Link discovery, pp. 36-43 (2005).
[5] J. M. Aldous and R. J. Wilson, Graphs and Applications: An Introductory Approach, Springer
Science & Business Media (2000).
[6] A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse
problems, SIAM J. Image Sciences, Vol. 2, pp. 183–202 (2009).
[7] T. Blumensath and M. E. Davies, Iterative hard thresholding for compressed sensing, Appl.
Comput. Harmon. Anal., Vol. 27, pp.265–274 (2009).
[8] E. J. Candès, M. B. Wakin, and S. Boyd, Enhancing sparsity by re-weighted `1 minimization,
Journal of Fourier Analysis and Applications, Vol. 14, pp. 877-905 (2008).
[9] E. J. Candés, J. K. Romberg, and T. Tao, Stable signal recovery from incomplete and inaccurate
measurements, Communications on Pure and Applied Mathematics, Vol. 59 issue 8, pp. 12071223 (2006).
[10] E. J. Candés and T. Tao, Decoding by linear programming, IEEE Transactions on Information
Theory, Vol 51, pp. 4203–4215 (2005).
[11] F. R. K. Chung, L. Lu, and V. Vu. The spectra of random graphs with given expected degrees,
Proceedings of the National Academy of Sciences, Vol. 100 issue 11, pp. 6313-6318 (2003).
[12] F. R. K. Chung, Spectral graph theory, No. 92, American Mathematical Soc. (1997).
[13] M. S. Cline, M. Smoot, E. Cerami, A. Kuchinsky, N. Landys, C. Workman, R. Christmas, I.
Avila-Campilo, M. Creech, B. Gross et al., Integration of biological networks and gene expression
data using cytoscape, Nature protocols, Vol. 2 issue 10, pp. 2366-2382 (2007).
[14] W. Dai and O. Milenkovic, Subspace pursuit for compressive sensing signal reconstruction, IEEE
Transactions on Information Theory, Vol. 55 issue 5, pp. 2230-2249 (2009).
[15] I. S. Dhillon, Co-clustering documents and words using spectral graph partitioning, Proceedings of the seventh ACM SIGKDD International Conference on Knowledge Discovery and Data
Mining, pp. 269-274 (2001).
[16] W. Dong, X. Tang, Y. Yu, R. Nilsen, R. Kim, J. Griffith, J. Arnold and H-B. Schüttler, Systems
biology of the clock in Neurospora crassa, PloS one, 3.8, e3105 (2008).

37

[17] D. L. Donoho and M. Elad, Optimally sparse representation in general (nonorthogonal) dictionaries via `1 minimization, Proceedings of the National Academy of Sciences, Vol. 100 issue 5,
pp. 2197-2202 (2003).
[18] P. Erdõs and A. Rènyi, On Random Graphs 1, Publicationes Mathematicae Debrecen, Vol. 6,
pp. 290-297 (1959).
[19] M. Fiedler, A property of eigenvectors of nonnegative symmetric matrices and its application
to graph theory, Czechoslovak Mathematical Journal Vol 25.4, pp. 619-633 (1975).
[20] S. Fortunato, Community detection in graphs, Physics reports, Vol. 486 issues 3-5 , pp. 75-174
(2010).
[21] S. Foucart and H. Rauhut, A Mathematical Introduction to Compressive Sensing, Birkäus Verlag
(2013).
[22] S. Foucart, Hard thresholding pursuit: an algorithm for compressive sensing, SIAM Journal on
Numerical Analysis, Vol. 49 issue 6, pp. 2543-2563 (2011).
[23] S. Foucart and M-J. Lai, Sparsest solutions of underdetermined linear Systems via `q minimization for 0 ≤ q ≤ 1, Applied and Computational Harmonic Analysis, Vol. 26 issue
3, pp. 395-407 (2009).
[24] B. J. Frey and D. Dueck, Clustering by passing messages between data points, Science Vol. 315
no. 5814, pp. 972-976 (2007).
[25] A. Frieze and M. Karoński, Introduction to Random Graphs, Cambridge University Press (2015).
[26] L. Hagen and A. B. Kahng, New spectral methods for ratio cut partitioning and clustering,
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 11 issue
9, pp.1074-1085 (1992).
[27] B. Hajek, Y. Wu, and J. Xu, Achieving exact cluster recovery threshold via semidefinite programming, IEEE Transactions on Information Theory Vol. 62.5, pp. 2788-2797 (2016).
[28] M. A. Herman and T. Strohmer, General deviants: An analysis of perturbations in compressed
sensing, IEEE Journal on Selected Topics in Signal Processing, Vol. 4 issue 2, pp. 342-349 (2010).
[29] P. W. Holland, K. B. Laskey, and S. Leinhardt, Stochastic block models: First steps, Social
Networks, Vol. 5 issue 2, pp.109-137 (1983).
[30] A. K. Jain, Data clustering: 50 years beyond K-means, Pattern Recognition Letters, Vol. 31
issue 8, pp. 651-666 (2010).
[31] L. Kaufman and P. J. Rousseeuw, Fitting Groups in Data. An Introduction to Cluster Analysis,
Wiley, New York (1990).
[32] F. Krzakala, C. Moore, E. Mossel, J. Neeman, A. Sly, L. Zdeborovà and P. Zhang, Spectral
Redemption in clustering sparse networks Proceedings of the National Academy of Sciences,
Vol. 110 no. 52, pp. 20935-20940 (2013).
[33] C. M. Le, E. Levina, and R. Vershynin, Sparse random graphs: regularization and concentration
of the Laplacian, arXiv preprint arXiv:1502.03049 (2015).
38

[34] H. Li, Improved analysis of SP and CoSaMP under total perturbations, EURASIP Journal on
Advances in Signal Processing 2016, no. 1, pp. 112 (2016).
[35] U. Von Luxburg, A tutorial on spectral clustering, Statistics and Computing, Vol. 17 issue 4,
pp. 395-416 (2007).
[36] A. Montanari and S. Sen, Semidefinite programs on sparse random graphs, arXiv preprint
arXiv:1504.05910 (2015).
[37] M. C. V. Nascimento and A. De Carvalho, Spectral methods for graph clustering - A survey,
European Journal of Operational Research, Vol. 211 issue 2, pp. 221-231 (2011).
[38] D. Needell and J. A. Tropp, CoSaMP: Iterative signal recovery from incomplete and inaccurate
samples, Applied and Computational Harmonic Analysis, Vol. 26 issue 3, pp. 301-321 (2009).
[39] M. E. J. Newman, Modularity and community structure in networks, Proceedings of the National
Academy of Sciences, Vol. 103 no. 23, pp 8577-8582 (2006).
[40] M. E. J. Newman, D. J. Watts, and S. H. Strogatz, Random graph models of social networks,
Proceedings of the National Academy of Sciences, Vol. 99 suppl. 1, pp. 2566-2572 (2002).
[41] A. Y. Ng, M. I. Jordan, and Y. Weiss, On spectral clustering: analysis and an algorithm,
Advances in Neural Information Processing Systems, pp. 849-856 (2002).
[42] S. C. Olhede and P. J. Wolfe, Network histograms and universality of block model approximation,
arXiv preprint arXiv:312-5306v3 (2014).
[43] J. Shi and J. Malik, Normalized cuts and image segmentation, IEEE Transactions on Pattern
Analysis and Machine Intelligence, Vol. 22 issue 8, pp. 888-905 (2000).
[44] R. C. Thompson, Principal submatrices IX: Interlacing inequalities for singular values of submatrices, Linear Algebra and Its Applications, Vol. 5 issue 1, pp. 1-12 (1972).
[45] N. Tremblay, G. Puy, R. Gribonval and P. Vandergheynst, Compressive spectral clustering,
Machine Learning, Proceedings of the Thirty-third International Conference (ICML 2016), pp.
20-22 (2016).
[46] J. A. Tropp, Greed is good: Algorithmic results for sparse approximation, IEEE Transactions
on Information Theory, Vol. 50 issue 10, pp. 2231-2242 (2004).
[47] W. W. Zachary, An Information flow model for conflict and fission in small groups, Journal of
Anthropological Research, Vol. 33 issue 4, pp. 452-473 (1977).

39

