CONCENTRATION AND REGULARIZATION OF RANDOM GRAPHS

arXiv:1506.00669v2 [math.PR] 9 Aug 2016

CAN M. LE, ELIZAVETA LEVINA AND ROMAN VERSHYNIN
Abstract. This paper studies how close random graphs are typically to their expectations. We interpret this question through the concentration of the adjacency and Laplacian
matrices in the spectral norm. We study inhomogeneous Erdös-Rényi random graphs on n
vertices, where edges form independently and possibly with different probabilities pij . Sparse
random graphs whose expected degrees are o(log n) fail to concentrate; the obstruction is
caused by vertices with abnormally high and low degrees. We show that concentration can
be restored if we regularize the degrees of such vertices, and one can do this in various ways.
As an example, let us reweight or remove enough edges to make all degrees bounded above
0
by O(d) where d = max npij . Then we show that
√ the resulting adjacency matrix A concen0
trates with the optimal rate: kA −E Ak = O( d). Similarly, if we make all degrees bounded
below by d by adding weight d/n to all edges, √
then the resulting Laplacian concentrates with
the optimal rate: kL(A0 ) − L(E A0 )k = O(1/ d). Our approach is based on GrothendieckPietsch factorization, using which we construct a new decomposition of random graphs. We
illustrate the concentration results with an application to the community detection problem
in the analysis of networks.

1. Introduction
Many classical and modern results in probability theory, starting from the Law of Large
Numbers, can be expressed as concentration of random objects about their expectations. The
objects studied most are sums of independent random variables, martingales, nice functions
on product probability spaces and metric measure spaces. For a panoramic exposition of concentration phenomena in modern probability theory and related fields, the reader is referred
to the books [25, 9].
This paper studies concentration properties of random graphs. The first step of such study
should be to decide how to interpret the statement that a random graph G concentrates near
its expectation. To do this, it will be useful to look at the graph G through the lens of the
matrices classically associated with G, namely the adjacency and Laplacian matrices.
Let us first build the theory for the adjacency matrix A; the Laplacian will be discussed
in Section 1.5. We may say that G concentrates about its expectation if A is close to its
expectation E A in some natural matrix norm; we interpret the expectation of G as the
weighted graph with adjacency matrix E A. Various matrix norms could be of interest here.
In this paper, we study concentration in the spectral norm. This automatically gives us
a tight control of all eigenvalues and eigenvectors, according to Weyl’s and Davis-Kahan
perturbation inequalities (see [5, Sections III.2 and VII.3]).
Concentration of random graphs interpreted this way, and also of general random matrices,
has been studied in several communities, in particular in random matrix theory, combinatorics
and network science.
Date: August 10, 2016.
E. L. is partially supported by NSF grants DMS-1159005 and DMS-1521551. R. V. is partially supported
by NSF grant 1265782 and U.S. Air Force grant FA9550-14-1-0009. This work was done while C. L. was a
Ph.D. student at the University of Michigan.
1

2

CAN M. LE, ELIZAVETA LEVINA AND ROMAN VERSHYNIN

We will study random graphs generated from an inhomogeneous Erdös-Rényi model G(n, (pij )),
where edges are formed independently with given probabilities pij , see [7]. This is a generalization of the classical Erdös-Rényi model G(n, p) where all edge probabilities pij equal
p. Many popular graph models arise as special cases of G(n, (pij )), such as the stochastic
block model, a benchmark model in the analysis of networks [22] discussed in Section 1.7,
and random subgraphs of given graphs.
Often, the question of interest is estimating some features of the probability matrix (pij )
from random graphs drawn from G(n, (pij )). Concentration of adjacency matrix and Laplacian matrix around their expectations, when it holds, guarantees that such features can be
recovered. As an example of this use of our concentration results, we will show that if (pij )
has a block structure, the blocks can be accurately estimated from a single realization of
G(n, (pij )) even when the average vertex degree is bounded.
1.1. Dense graphs concentrate. The cleanest concentration results are available for the
classical Erdös-Rényi model G(n, p) in the dense regime. In terms of the expected degree
d = pn, we have with high probability that
√
(1.1)
kA − E Ak = 2 d (1 + o(1)) if d  log4 n,
see [16, 44, 28]. Since k E Ak = d, we see that the typical deviation here behaves like the
square root of the magnitude of expectation – just like in many other classical results of
probability theory. In other words, dense random graphs concentrate well.
The lower bound on density in (1.1) can be essentially relaxed all the way down to d =
Ω(log n). Thus, with high probability we have
√
(1.2)
kA − E Ak = O( d) if d = Ω(log n).
This result was proved in [15] based on the method developed by J. Kahn and E. Szemeredi
[17]. More generally, (1.2) holds forP
any inhomogeneous Erdös-Rényi model G(n, (pij )) with
maximal expected degree d = maxi j pij . This generalization can be deduced from a recent
√
result of S. Bandeira and R. van Handel [4, Corollary 3.6], while a weaker bound O( d log n)
follows from concentration inequalities for sums of independent random matrices [35]. Alternatively, an argument in [15] can be used to prove (1.2) for a somewhat larger but still useful
value
d = max npij ,
(1.3)
ij

see [27, 12]. The same can be obtained by using Seginer’s bound on random matrices [20].
As we will see shortly, our paper provides an alternative and completely different approach
to general concentration results like (1.2).
1.2. Sparse graphs do not concentrate. In the sparse regime, where the expected degree
d is bounded, concentration breaks down. According to [24], a random graph from G(n, p)
satisfies with high probability that
s
p
log n
if d = O(1),
(1.4)
kAk = (1 + o(1)) d(A) = (1 + o(1))
log log n
where d(A) denotes the maximal degree of the graph (a random quantity). So in this regime
we have kAk  k E Ak = d, which shows that sparse random graphs do not concentrate.
What exactly makes the norm A abnormally large in the sparse regime? The answer is,
the vertices with too high degrees. In the dense case where d  log n, all vertices typically
have approximately the same degrees (1 + o(1))d. This no longer happens in the sparser

3

regime d  log n; the degrees do not cluster tightly about the same value anymore. There
are vertices with too high degrees; they are captured by the second inequality in (1.4). Even
a single high-degree vertex can blow up the norm of the adjacency matrix. Indeed, since
p the
norm of A is bounded below by the Euclidean norm of each of its rows, we have kAk ≥ d(A).
1.3. Regularization enforces concentration. If high-degree vertices destroy concentration, can we “tame” these vertices? One proposal would be to remove these vertices from the
graph altogether. U. Feige and E. Ofek [15] showed that this works for G(n, p) – the removal
of the high degree vertices enforces concentration. Indeed, if we drop all vertices with degrees,
say, larger than 2d, the the remaining part of the graph satisfies
√
(1.5)
kA0 − E A0 k = O( d)
with high probability, where A0 denotes the adjacency matrix of the new graph. The argument
in [15] is based on the method developed by J. Kahn and E. Szemeredi [17]. It extends to
the inhomogeneous Erdös-Rényi model G(n, (pij )) with d defined in (1.3), see [27, 12]. As we
will see, our paper provides an alternative and completely different approach to such results.
Although the removal of high degree vertices solves the concentration problem, such solution is not ideal, since those vertices are in some sense the most important ones. In real-world
networks, the vertices with highest degrees are “hubs” that hold the network together. Their
removal would cause the network to break down into disconnected components, which leads
to a considerable loss of structural information.
Would it be possible to regularize the graph in a more gentle way – instead of removing
the high-degree vertices, reduce the weights of their edges just enough to keep the degrees
bounded by O(d)? The main result of our paper states that this is true. Let us first state
this result informally; Theorem 2.1 provides a more general and formal statement.
Theorem 1.1 (Concentration of regularized adjacency matrices). Consider a random graph
from the inhomogeneous Erdös-Rényi model G(n, (pij )), and let d = maxij npij . For all high
degree vertices of the graph (say, those with degrees larger than 2d), reduce the weights of
the edges incident to them in an arbitrary way, but so that all degrees of the new (weighted)
graph become bounded by 2d. Then, with high probability, the adjacency matrix A0 of the new
graph concentrates:
√
kA0 − E Ak = O( d).
Moreover, instead of requiring that the degrees become bounded by 2d, we
√ can require that the
`2 norms of the rows of the new adjacency matrix become bounded by 2d.
1.4. Examples of graph regularization. The regularization procedure in Theorem 1.1 is
very flexible. Depending on how one chooses the weights, one can obtain as partial cases
several results we summarized earlier, as well as some new ones.
1. Do not do anything to the graph. In the dense regime where d = Ω(log n), all degrees are
already bounded √
by 2d with high probability. This means that the original graph satisfies
kA − E Ak = O( d). Thus we recover the result of U. Feige and E. Ofek (1.2), which
states that dense random graphs concentrate well.
2. Remove all high degree vertices. If we remove all vertices with degrees larger than 2d, we
recover another result of U. Feige and E. Ofek (1.5), which states that the removal of the
high degree vertices enforces concentration.
3. Remove just enough edges from high-degree vertices. Instead of removing the high-degree
vertices with all of their edges, we can remove just enough edges to make all degrees
bounded by 2d. This milder regularization still produces the concentration bound (1.5).

4

CAN M. LE, ELIZAVETA LEVINA AND ROMAN VERSHYNIN

4. Reduce the weight of edges proportionally to the excess of degrees. Instead of removing
edges, we can reduce the weight of the existing edges, a procedure
p which better preserves
the structure of the graph. For instance, we can assign weight λi λj to the edge between
vertices i and j, choosing λi := min(2d/di , 1) where di is the degree of vertex i. One can
check that this makes the `2 norms of all rows of the adjacency matrix bounded by 2d. By
Theorem 1.1, such regularization procedure leads to the same concentration bound (1.5).
1.5. Concentration of Laplacian. So far, we have looked at random graphs through the
lens of their adjacency matrices. A different matrix that captures the geometry of a graph is
the (symmmetric, normalized) Laplacian matrix, defined as
L(A) = D−1/2 (D − A)D−1/2 = I − D−1/2 AD−1/2 .

(1.6)

Here
Pn I is the identity matrix and D = diag(di ) is the diagonal matrix with degrees di =
j=1 Aij on the diagonal. The reader is referred to [13] for an introduction to graph Laplacians and their role in spectral graph theory. Here we mention just two basic facts: the
spectrum of L(A) is a subset of [0, 2], and the smallest eigenvalue is always zero.
Concentration of Laplacians of random graphs has been studied in [35, 11, 39, 23, 18]. Just
like the adjacency matrix, the Laplacian is known to concentrate in the dense regime where
d = Ω(log n), and it fails to concentrate in the sparse regime. However, the obstructions
to concentration are opposite. For the adjacency matrices, as we mentioned, the trouble is
caused by high-degree vertices. For the Laplacian, the problem lies with low-degree vertices.
In particular, for d = o(log n) the graph is likely to have isolated vertices; they produce
multiple zero eigenvalues of L(A), which are easily seen to destroy the concentration.
In analogy to our discussion of adjacency matrices, we can try to regularize the graph to
“tame” the low-degree vertices in various ways, for example remove the low-degree vertices,
connect them to some other vertices, artificially increase the degrees di in the definition (1.6)
of Laplacian, and so on. Here we will focus on the following simple way of regularization
proposed in [3] and analyzed in [23, 18]. Choose τ > 0 and add the same number τ /n to all
entries of the adjacency matrix A, thereby replacing it with
Aτ := A + (τ /n)11T
in the definition (1.6) of the Laplacian. This regularization raises all degrees di to di + τ . If
we choose τ ∼ d, the regularized graph does not have low-degree vertices anymore.
The following consequence of Theorem 1.1 shows that such regularization indeed forces
Laplacian to concentrate. Here we state this result informally; Theorem 4.1 provides a more
formal statement.
Theorem 1.2 (Concentration of the regularized Laplacian). Consider a random graph from
the inhomogeneous Erdös-Rényi model G(n, (pij )), and let d = maxij npij . Choose a number
τ ∼ d. Then, with high probability, the regularized Laplacian L(Aτ ) concentrates:
 1 
kL(Aτ ) − L(E Aτ )k = O √ .
d
We will deduce this result from Theorem 1.1 in Section 4. Theorem 1.2 is an improvement
upon a bound in [18] that had an extra log d factor, and it was conjectured there that the
logarithmic factor is not needed. Theorem 1.2 confirms this conjecture.

5

1.6. A numerical experiment. To conclude our discussion of various ways to regularize
sparse graphs, let us illustrate the effect of regularization by a numerical experiment. Consider
an inhomogeneous Erdös-Rényi graph with n = 1000 vertices, 90% of which have expected
degrees 7 and 10% percent have expected degrees 35. We then regularize the graph by
reducing the weights of edges proportionally to the excess of degrees – just as we described in
Section 1.4 item 4, except that we use the overall average degree (approximately 10) instead
of d (which results in a more severe weight reduction suitable for our illustration purpose).
Figure 1 shows the histogram of the spectrum of A (left) and A0 (right). As we can
see, the high degree vertices lead to the long tails in the histogram of the eigenvalues, and
regularization shrinks these tails toward the bulk.

Figure 1. Histogram of the spectrum of adjacency matrix A (left) and regularized adjacency matrix A0 (right) for a sparse random graph generated from
the inhomogeneous Erdös-Rényi model with n = 1000 vertices, 90% of which
have expected degrees 7 and 10% percent have expected degrees 35.
1.7. Application: community detection in networks. Concentration of random graphs
has an important application to statistical analysis of networks, in particular to the problem of
community detection. A common way of modeling communities in networks is the stochastic
block model [22], which is a special case of the inhomogeneous Erdös-Rényi model considered in
this paper. For the purpose of this example, we focus on the simplest version of the stochastic
block model G(n, na , nb ), also known as the balanced planted partition model, defined as
follows. The set of vertices is divided into two subsets (communities) of size n/2 each.
Edges between vertices are drawn independently with probability a/n if they are in the same
community and with probability b/n otherwise.
The community detection problem is to recover the community labels of vertices from a
single realization of the random graph model. A large literature exists on both the recovery
algorithms and the theory establishing when a recovery is possible [14, 33, 34, 32, 1, 29, 8].
There are methods that perform better than a random guess (i.e. the fraction of misclassified
vertices is bounded away from 0.5 as n → ∞ with high probability) under the condition
(a − b)2 > 2(a + b),
and no method can perform better than a random guess if this condition is violated.
Moreover, strong consistency, or exact recovery (labeling all vertices correctly with high
probability) is possible when the expected degree (a + b)/2 is of order log n or larger and
a and b are sufficiently separated, see [32, 30, 6, 20, 10]. Weak consistency (the fraction of
mislabeled vertices going to 0 with high probability) is achievable if and only if
(a − b)2 > Cn (a + b)

with Cn → ∞,

6

CAN M. LE, ELIZAVETA LEVINA AND ROMAN VERSHYNIN

see [32]. Many of these results hold in the non-asymptotic regime, for graphs of fixed size
n. Thus, for any ε > 0 there exists Cε (which only depends on ε) such that one can recover
communities up to εn mislabeled vertices as long as
(a − b)2 > Cε (a + b).
In particular, recovery of communities is possible even for very sparse graphs – those with
bounded expected degrees. Several types of algorithms are known to succeed in this regume,
including non-backtracking walks [33, 29, 8], spectral methods [12] and methods based on
semidefinite programming [19, 31].
As an application of the new concentration results, we show that the regularized spectral
clustering [3, 23], one of the simplest most popular algorithms for community detection, can
recover communities in the sparse regime. In general, spectral clustering works by computing the leading eigenvectors of either the adjacency matrix or the Laplacian or their
regularized versions, and running the k-means clustering algorithm on these eigenvectors to
recover the node labels. In the simple case of the model G(n, na , nb ), one can simply assign
nodes to communities based on the sign (positive or negative) of the corresponding entries
of the eigenvector v2 (L(Aτ )) corresponding to the second smallest eigenvalue of regularized
Laplacian matrix L(Aτ ) (or the regularized adjacency matrix A0 ).
Let us briefly explain how our concentration results validate regularized spectral clustering. If the concentration of random graphs holds and L(Aτ ) is close to L(E Aτ ), then the
standard perturbation theory (Davis-Kahan theorem below) shows that v2 (L(Aτ )) is close
to v2 (L(E Aτ )), and in particular, the signs of these two eigenvectors must agree on most
vertices. An easy calculation shows that the signs of v2 (L(E Aτ )) recover the communities
exactly: this vector is a positive constant on one community and a negative constant on the
other. Therefore, the signs of v2 (L(Aτ )) must recover the communities up to a small fraction
of misclassified vertices.
Before stating our result, let us quote a simple version of the Davis-Kahan theorem perturbation theorem (see e.g. [5, Theorem VII.3.2]).
Theorem 1.3 (Davis-Kahan theorem). Let X, Y be symmetric matrices such that the second
smallest eigenvalues of X and Y have multiplicity one and they are of distance at least δ > 0
from the remaining eigenvalues of X and Y . Denote by x and y the eigenvectors of X and
Y corresponding to the second largest eigenvalues of X and Y , respectively. Then
min kx + βyk ≤

β=±1

2kX − Y k
.
δ

Corollary 1.4 (Community detection in sparse graphs). Let ε > 0 and r ≥ 1. Let A be the
adjacency matrix drawn from the stochastic block model G(n, na , nb ). Assume that
(a − b)2 > Cε (a + b)

(1.7)

where Cε = Cr4 ε−2 and C is an appropriately large absolute constant. Choose τ to be the
average degree of the graph, i.e. τ = (d1 + · · · + dn )/n where di are vertex degrees. Then with
probability at least 1 − e−r , we have
min kv2 (L(Aτ )) + βv2 (L(E Aτ ))k ≤ ε.

β=±1

In particular, the signs of the entires of v2 (L(Aτ )) correctly estimate the partition into the
two communities, up to at most εn misclassified vertices.

7

Proof. We apply Theorem 1.3 with X = L(Aτ ) and Y = L(E Aτ ). A simple calculation shows
that the spectral gap δ defined in Theorem 1.3 is of the order (a − b)/(a + b). The claim
of Corollary 1.4 then follows from Davis-Kahan Theorem 1.3, Concentration Theorem 4.1
(which is a formal version of Theorem 1.2) and condition (1.7).

1.8. Organization of the paper. In Section 2, we state a formal version of Theorem 1.1.
We show there how to deduce this result from a new decomposition of random graphs, which
we state as Theorem 2.6. We prove this decomposition theorem in Section 3. In Section 4, we
state and prove a formal version of Theorem 1.2 about the concentration of the Laplacian. We
conclude the paper with Section 5 where we propose some questions for further investigation.
Acknowledgement. The authors are grateful to Ramon van Handel for several insightful
comments on the preliminary version of this paper.
2. Full version of Theorem 1.1, and reduction to a graph decomposition
In this section we state a more general and quantitative version of Theorem 1.1, and we
reduce it to a new form of graph decomposition, which can be of interest on its own.
Theorem 2.1 (Concentration of regularized adjacency matrices). Consider a random graph
from the inhomogeneous Erdös-Rényi model G(n, (pij )), and let d = maxij npij . For any
r ≥ 1, the following holds with probability at least 1 − n−r . Consider any subset consisting
of at most 10n/d vertices, and reduce the weights of the edges incident to those vertices in
an arbitrary way. Let d0 be the maximal degree of the resulting graph. Then the adjacency
matrix A0 of the new (weighted) graph satisfies
√ 
√
kA0 − E Ak ≤ Cr3/2 d + d0 .
Moreover, the same bound holds for d0 being the maximal `2 norm of the rows of A0 .
In this result and in the rest of the paper, C, C1 , C2 , . . . denote absolute constants whose
values may be different from line to line.
Remark 2.2 (Theorem 2.1 implies Theorem 1.1). The subset of 10n/d vertices in Theorem 2.1
can be completely arbitrary. So let us choose the high-degree vertices, say those with degrees
larger than 2d. There are at most 10n/d such vertices with high probability; this follows by
an easy calculation, and also from Lemma 3.5. Thus we immediately deduce Theorem 1.1.
Remark 2.3 (Tight upper bound). If we do not reduce weights of any edges and d is bounded,
then the upper bound in Theorem 2.1 is tight (up to a constant depending on r). This is
because of (1.4), which states that the adjacency matrix does not concentrate in the sparse
regime without regularization.
Remark 2.4 (Method to prove Theorem 2.1). One may wonder if Theorem 2.1 can be proved
by developing an -net argument similar to the method of J. Kahn and E. Szemeredi [17]
and its versions [2, 15, 27, 12]. Although we can not rule out such possibility, we do not see
how this method could handle a general regularization. The reader familiar with the method
can easily notice an obstacle. The contribution of the so-called light couples becomes hard
to control when one changes, and even reduces, the individual entries of A (the weights of
edges).
We will develop an alternative and somewhat simpler approach, which will be able to
handle a general regularization of random graphs. It sheds light on the specific structure of
graphs that enables concentration. We are going to identify this structure through a graph

8

CAN M. LE, ELIZAVETA LEVINA AND ROMAN VERSHYNIN

decomposition in the next section. But let us pause briefly to mention the following useful
reduction.
Remark 2.5 (Reduction to directed graphs). Our arguments will be more convenient to carry
out if the adjacency matrix A has all independent entries. To be able to make this assumption,
we can decompose A into the upper-triangular and a lower-triangular parts, both of which
have independent entries. If we can show that each of these parts concentrate about its
expectation, it would follow that A concentrate about E A by triangle inequality.
In other words, we may prove Theorem 2.1 for directed inhomogeneous Erdös-Rényi graphs,
where edges between any vertices and in any direction appear indepednently with probabilities
pij . In the rest of the argument, we will only work with such random directed graphs.
2.1. Graph decomposition. In this section, we reduce Theorem 2.1 to the following decomposition of inhomogeneous Erdös-Rényi directed random graphs. This decomposition may
have an independent interest. Throughout the paper, we denote by BN the matrix which
coincides with a matrix B on a subset of edges N ⊂ [n] × [n] and has zero entries elsewhere.
Theorem 2.6 (Graph decomposition). Consider a random directed graph from the inhomogeneous Erdös-Rényi model, and let d be as in (1.3). For any r ≥ 1, the following holds with
probability at least 1 − 3n−r . One can decompose the set of edges [n] × [n] into three classes
N , R and C so that the following properties are satisfied for the adjacency matrix A.
√
• The graph concentrates on N , namely k(A − E A)N k ≤ Cr3/2 d.
• Each row of AR and each column of AC has at most 32r ones.
Moreover, R intersects at most n/d columns, and C intersects at most n/d rows of [n] × [n].
Figure 2 illustrates a possible decomposition Theorem 2.6 can provide. The edges in N
form a big “core” where the graph concentrates well even without regularization. The edges
in R and C can be thought of (at least heuristically) as those attached to high-degree vertices.

Figure 2. An example of graph decomposition in Theorem 2.6.
We will prove Theorem 2.6 in Section 3; let us pause to deduce Theorem 2.1 from it.
2.2. Deduction of Theorem 2.1. First, let us explain informally how the graph decomposition could lead to Theorem 2.1. The regularization of the graph does not destroy the
properties of N , R and C in Theorem 2.6. Moreover, regularization creates a new property
for us, allowing for a good control of the columns of R and rows of C. Let us focus on AR to
be specific. The `1 norms of all columns of this matrix are at most d0 , and the `1 norms of
all rows are O(r) by Theorem
√ 2.6. By a simple calculation which we will do in Lemma 2.7,
this implies that kAR k = O( rd0 ). A similar bound√can √
be proved for C. Combining N , R
and C together will lead to the error bound O(r3/2 ( d + d0 )) in Theorem 2.1.
To make this argument rigorous, let us start with the simple calculation we just mentioned.

9

Lemma 2.7. Consider a matrix B in which
√ each row has `1 norm at most a, and each
column has `1 norm at most b. Then kBk ≤ ab.
Proof. Let x be a vector with kxk2 = 1. Using Cauchy-Schwarz inequality and the assumptions, we have
2 X  X

XX
X
kBxk22 =
Bij xj ≤
|Bij |
|Bij |x2j
i

j

i

j

j


X X
X X
X
≤
a
|Bij |x2j = a
x2j
|Bij | ≤ a
x2j b = ab.
i

j

j

i

j

Since x is arbitrary, this completes the proof.



Remark 2.8 (Riesz-Thorin interpolation theorem implies Lemma 2.7). Lemma 2.7 can also
be deduced from Riesz-Thorin interpolation theorem (see e.g. [40, Theorem 2.1]), since the
maximal `1 norm of columns is the `1 → `1 operator norm, and the maximal `1 norm of rows
is the `∞ → `∞ operator norm.
We are ready to formally deduce the main part of Theorem 2.1 from Theorem 2.6; we defer
the “moreover” part to Section 3.6.
Proof of Theorem 2.1 (main part). Fix a realization of the random graph that satisfies the
conclusion of Theorem 2.6, and decompose the deviation A0 − E A as follows:
A0 − E A = (A0 − E A)N + (A0 − E A)R + (A0 − E A)C .

(2.1)

We will bound the spectral norm of each of the three terms separately.
Step 1. Deviation on N . Let us further decompose
(A0 − E A)N = (A − E A)N − (A − A0 )N .
(2.2)
√
3/2
d. To control the second term in (2.2), denote by
By Theorem 2.6, k(A − E A)N k ≤ Cr
E ⊂ [n] × [n] the subset of edges that are reweighed in the regularization process. Since A
and A0 are equal on E c , we have
k(A − A0 )N k = k(A − A0 )N ∩E k ≤ kAN ∩E k
≤ k(A − E A)N ∩E k + k E AN ∩E k

(since 0 ≤ A − A0 ≤ A entrywise)
(by triangle inequality).

(2.3)

Further, a simple restriction property implies that
k(A − E A)N ∩E k ≤ 2k(A − E A)N k.

(2.4)

Indeed, restricting a matrix onto a product subset of [n] × [n] can only reduce its norm.
Although the set of reweighted edges E is not a product subset, it can be decomposed into
two product subsets:


E = I × [n] ∪ I c × I
(2.5)
where I is the subset of vertices incident
√to the edges in E. Then (2.4) holds; right hand side
of that inequality is bounded by Cr3/2 d by Theorem 2.6. Thus we handled the first term
in (2.3).
To bound the second term in (2.3), we can use another restriction property that states
that the norm of the matrix with non-negative entries can only reduce by restricting onto
any subset of [n] × [n] (whether a product subset or not). This yields
k E AN ∩E k ≤ k E AE k ≤ k E AI×[n] k + k E AI c ×I k

(2.6)

10

CAN M. LE, ELIZAVETA LEVINA AND ROMAN VERSHYNIN

where the second inequality follows by (2.5). By assumption, the matrix E AI×[n] has |I| ≤
10n/d rows and each of its entries is bounded by d/n. Hence the `1 norm of all rows is
bounded by d,√and the `1 norm of all columns is bounded by 10. Lemma 2.7 implies that
k E AI×[n] k ≤ 10d. A similar bound holds for the second term of (2.6). This yields
√
k E AN ∩E k ≤ 5 d,
so we √handled the second term in (2.3). Recalling√that the first term there is bounded by
Cr3/2 d, we conclude that k(A − A0 )N k ≤ 2Cr3/2 d.
√
Returning to (2.2), we recall that the first term
in the right hand is bounded by Cr3/2 d,
√
and we just bounded the second term by 2Cr3/2 d. Hence
√
k(A0 − E A)N k ≤ 4Cr3/2 d.
Step 2. Deviation on R and C. By triangle inequality, we have
k(A0 − E A)R k ≤ kA0R k + k E AR k.
Recall that 0 ≤ A0R ≤ AR entrywise. By Theorem 2.6, each of the rows of AR , and thus also
of A0R , has `1 norm at most 32r. Moreover, by definition of d0 , each of the columns
of A0 ,
√
0
0
0
and thus also of AR , has `1 norm at most d . Lemma 2.7 implies that kAR k ≤ 32rd0 .
The matrix E AR can be handled similarly. By Theorem 2.6, it has at most n/d entries
in each row, and all entries are bounded by d/n. Thus each column of E AR has `1 norm
√ at
most 1, and and each row has `1 norm at most d. Lemma 2.7 implies that k E AR k ≤ d.
We showed that
√
√
k(A0 − E A)R k ≤ 32rd0 + d.
A similar bound holds for k(A0 − E A)C k. Combining the bounds on the deviation of A0 − E A
on N , R and C and putting them into (2.1), we conclude that
√
√
√ 
kA0 − E Ak ≤ 4Cr3/2 d + 2 32rd0 + d .
Simplifying this inequality, we complete the proof of the main part of Theorem 2.1.



3. Proof of Decomposition Theorem 2.6
3.1. Outline of the argument. We will construct the decomposition in Theorem 2.6 by
an iterative procedure. The first and crucial step is to find a big block1 N 0 ⊂ [n] × [n] of size
at least (n − n/d) × n/2 on which A concentrates, i.e.
√
k(A − E A)N 0 k = O( d).
To find such block, we first establish concentration in `∞ → `2 norm; this can be done by
standard probabilistic techniques. Next, we can automatically upgrade this to concentration
in the spectral norm (`2 → `2 ) once we pass to an appropriate block N 0 . This can be
done using a general result from functional analysis, which we call Grothendieck-Pietsch
factorization.
Repeating this argument for the transpose, we obtain another block N 00 of size at least
n/2 × (n − n/d) where the graph concentrates as well. So the graph concentrates on N0 :=
N 0 ∪ N 00 . The “core” N0 will form the first part of the class N we are constructing.
It remains to control the graph on the complement of N0 . That set of edges is quite small;
it can be described as a union of a block C0 with n/d rows, a block R0 with n/d columns and
1In this paper, by block we mean a product set I × J with arbitrary index subsets I, J ⊂ [n]. These subsets

are not required to be intervals of successive integers.

11

an exceptional n/2 × n/2 block; see Figure 3b for illustration. We may consider C0 and R0
as the first parts of the future classes C and R we are constructing.
Indeed, since C0 has so few rows, the expected number of ones in each column of C0 is
bounded by 1. For simplicity, let us think that all columns of C0 have O(1) ones as desired.
(In the formal argument, we will add the bad columns to the exceptional block.) Of course,
the block R0 can be handled similarly.
At this point, we decomposed [n] × [n] into N0 , R0 , C0 and an exceptional n/2 × n/2 block.
Now we repeat the process for the exceptional block, constructing N1 , R1 , and C1 there, and
so on. Figure 3c illustrates this process. At the end, we choose N , R and C to be the unions
of the blocks Ni , Ri and Ci respectively.

(a) The core.

(b) After the first step.

(c) Final decomposition.

Figure 3. Constructing decomposition iteratively in the proof of Theorem 2.6.
Two precautions have to be taken in this argument. First, we need to make concentration
on the core blocks Ni better at each step, so that the sum of those error bounds would not
depend of the total number of steps. This can be done with little effort, with the help of
the exponential decrease of the size of the blocks Ni . Second, we have a control of the sizes
but not locations of the exceptional blocks. Thus to be able to carry out the decomposition
argument inside an exceptional block, we need to make the argument valid uniformly over
all blocks of that size. This will require us to be delicate with probabilistic arguments, so we
can take a union bound over such blocks.
3.2. Grothendieck-Pietsch factorization. As we mentioned in the previous section, our
proof of Theorem 2.6 is based on Grothendieck-Pietsch factorization. This general and well
known result in functional analysis [36, 37] has already been used in a similar probabilistic
context, see [26, Proposition 15.11].
Grothendieck-Pietsch factorization compares two matrix norms, the `2 → `2 norm (which
we call the spectral norm ) and the `∞ → `2 norm. For a k × m matrix B, these norms are
defined as
kBk = max kBxk2 ,
kxk2 =1

kBk∞→2 = max kBxk2 =
kxk∞ =1

max

x∈{−1,1}m

kBxk2 .

The `∞ → `2 norm is usually easier to control, since the supremum is taken with respect to
the discrete set {−1, 1}m , and any vector there has all coordinates of the same magnitude.
To compare the two norms, one can start with the obvious inequality
kBk∞→2
√
≤ kBk ≤ kBk∞→2 .
m

12

CAN M. LE, ELIZAVETA LEVINA AND ROMAN VERSHYNIN

Both parts of this inequality are optimal, so there is an unavoidable slack between the upper
and lower bounds. However, Grothendieck-Pietsch factorization allows us to tighten the
inequality by changing B sightly. The next two results offer two ways to change B – introduce
weights and pass to a sub-matrix.
Theorem 3.1 (Grothendieck-Pietsch’s factorization, P
weighted version). Let B be a k × m
real matrix. Then there exist positive weights µj with m
j=1 µj = 1 such that
p
kBk∞→2 ≤ kBDµ−1/2 k ≤ π/2kBk∞→2 ,
(3.1)
where Dµ = diag(µj ) denotes the m × m diagonal matrix with weights µj on the diagonal.
This result is a known combination of the Little Grothendieck Theorem (see [41, Corollary 10.10] and [38]) and Pietsch Factorization (see [41, Theorem 9.2]). In an explicit form,
a version of this result can be found e.g. in [26, Proposition 15.11]. The weights µj can be
computed algorithmically, see [42].
The following related version of Grothendieck-Pietsch’s factorization can be especially
useful in probabilistic contexts, see [26, Proposition 15.11]. Here and in the rest of the paper,
we denote by BI×J the sub-matrix of a matrix B with rows indexed by a subset I and columns
indexed by a subset J.
Theorem 3.2 (Grothendieck-Pietsch factorization, sub-matrix version). Let B be a k × m
real matrix and δ > 0. Then there exists J ⊆ [m] with |J| ≥ (1 − δ)m such that
kB[k]×J k ≤

2kBk∞→2
√
.
δm

Proof. Consider the weights µi given
P by Theorem 3.1, and choose J to consist of the indices
j satisfying µj ≤ 1/(δm). Since j µj = 1, the set J must contain at least (1 − δ)m indices
−1/2

as
√ claimed. Furthermore, the diagonal entries of (Dµ )J×J are all bounded from below by
δm, which yields
√
k(BDµ−1/2 )[k]×J k ≥ δmkB[k]×J k.
On the other hand, by (3.1) the left-hand side of this inequality is bounded by 2kBk∞→2 .
Rearranging the terms, we complete the proof.

3.3. Concentration on a big block. We are starting to work toward constructing the core
part N in Theorem 2.6. In this section we will show how to find a big block on which the
adjacency matrix A concentrates. First we will establish concentration in `∞ → `2 norm,
and then, using Grothendieck-Pietsch factorization, in the spectral norm.
The lemmas of this and next section should be best understood for m = n, I = J = [n]
and α = 1. In this case, we are working with the entire adjacency matrix, and trying to
make the first step in the iterative procedure. The further steps will require us to handle
smaller blocks I × J; the parameter α will then become smaller in order to achieve better
concentration for smaller blocks.
Lemma 3.3 (Concentration in `∞ → `2 norm). Let 1 ≤ m ≤ n and α ≥ m/n. Then for
r ≥ 1 the following holds with probability at least 1 − n−r . Consider a block I × J of size
m × m. Let I 0 be the set of indices of the rows of AI×J that contain at most αd ones. Then
p
k(A − E A)I 0 ×J k∞→2 ≤ C αdmr log(en/m).
(3.2)

13

Proof. By definition,
k(A − E A)

I 0 ×J

k2∞→2

=

max

x∈{−1,1}m

XX
i∈I 0

(Aij − E Aij )xj

j∈J

2

=

max

x∈{−1,1}m

X

Xi ξi

2

(3.3)

i∈I

where we denoted
Xi :=

X
(Aij − E Aij )xj ,

ξi := 1{P Aij ≤αd} .
i∈J

j∈J

Let us first fix a block I × J and aPvector x ∈ {−1, 1}m .PLet us analyze the independent
random variables Xi ξi . Since |Xi | ≤ j∈J |Aij − E Aij | ≤ j∈J Aij , it follows by definition
of ξi that
|Xi ξi | ≤ αd.
(3.4)
A more useful bond will follow from Bernstein’s inequality. Indeed, Xi is a sum of m
independent random variables with zero means and variances at most d/n. By Bernstein’s
inequality, for any t > 0 we have


−mt2 /2
P {|Xi ξi | > tm} ≤ P {|Xi | > tm} ≤ 2 exp
, t ≥ 0.
(3.5)
d/n + t/3
For tm ≤ αd, this can be further bounded by 2exp(−m2 t2 /4αd), once we use the assumption
α ≥ m/n. For tm > αd, the left-hand side of (3.5) is automatically zero by (3.4). Therefore


−m2 t2
P {|Xi ξi | > tm} ≤ 2 exp
,
t ≥ 0.
(3.6)
4αd
We are now ready to bound the right-hand side of (3.3).
By (3.6), the random variable
√
Xi ξi is sub-gaussian2 with sub-gaussian norm at most αd. It follows that (Xi ξi )2 is subexponential with sub-exponential norm at most 2αd. Using Bernstein’s inequality for subexponential random variables (see Corrollary 5.17 in [43]), we have
(
)
X
2

 
P
Xi ξi > εmαd ≤ 2 exp −c min ε2 , ε m ,
ε ≥ 0.
(3.7)
i∈I

Choosing ε := (10/c)r log(en/m), we bound this probability by (en/m)−5rm .
Summarizing, we have proved that for fixed I, J ⊆ [n] and x ∈ {−1, 1}m , with probability
at least 1 − (en/m)−5rm , the following holds:
X
2
Xi ξi ≤ (10/c)r log(en/m) · mαd.
(3.8)
i∈I

Taking a union bound over all possibilities of m, I, J, x and using (3.3), (3.8), we see that the
conclusion of the lemma holds with probability at least
 2  
n
X
en −5rm
m n
2
≥ 1 − n−r .
1−
m
m
m=1

The proof is complete.



Applying Lemma 3.3 followed by Grothendieck-Piesch factorization (Theorem 3.2), we
obtain the following.
2For definitions and basic facts about sub-gaussian random variables, see e.g. [43].

14

CAN M. LE, ELIZAVETA LEVINA AND ROMAN VERSHYNIN

Lemma 3.4 (Concentration in spectral norm). Let 1 ≤ m ≤ n and α ≥ m/n. Then for
r ≥ 1 the following holds with probability at least 1 − n−r . Consider a block I × J of size
m × m. Let I 0 be the set of indices of the rows of AI×J that contain at most αd ones. Then
one can find a subset J 0 ⊆ J of at least 3m/4 columns such that
p
k(A − E A)I 0 ×J 0 k ≤ C αdr log(en/m).
(3.9)
3.4. Restricted degrees. The two simple lemmas of this section will help us to handle the
part of the adjacency matrix outside the core block constructed in Lemma 3.4. First, we
show that almost all rows have at most O(αd) ones, and thus are included in the core block.
p
Lemma 3.5 (Degrees of subgraphs). Let 1 ≤ m ≤ n and α ≥ m/n. Then for r ≥ 1 the
following holds with probability at least 1 − n−r . Consider a block I × J of size m × m. Then
all but m/αd rows of AI×J have at most 8rαd ones.
Proof. Fix a block I × J, and denote by di the number of ones in the i-th row of AI×J . Then
E di ≤ md/n by the assumption. Using Chernoff’s inequality, we obtain
 8rαd −8rαd  2αn −8rαd
P {di > 8rαd} ≤
≤
=: p.
emd/n
m
Let S be the number of rows i with di > 8rαd. Then S is a sum of m independent Bernoulli
random variables with expectations at most p. Again, Chernoff’s inequality implies
 2αn −4rm
.
P {S > m/αd} ≤ (epαd)m/αd ≤ pm/2αd =
m
The second inequality here holds since eαd ≤ p−1/2 . (To see this, notice that the definition
of p and assumption on α imply that p−1/2 = (2αn/m)4rαd ≥ 24rαd .)
It remains to take a union bound over all blocks I × J. We obtain that the conclusion of
the lemma holds with probability at least
n  2 
X
2αn −4rm
n
≥ 1 − n−r .
1−
m
m
m=1
p
In the last inequality we used the assumption that α ≥ m/n. The proof is complete.

Next, we handle the block of rows that do have too many ones. We show that most columns
of this block have O(1) ones.
p
Lemma 3.6 (More on degrees of subgraphs). Let 1 ≤ m ≤ n and α ≥ m/n. Then for
r ≥ 1 the following holds with probability at least 1 − n−r . Consider a block I × J of size
k × m with some k ≤ m/αd. Then all but m/4 columns of AI×J have at most 32r ones.
Proof. Fix I and J, and denote by dj the number of ones in the j-th column of AI×J . Then
E dj ≤ kd/n ≤ m/αn by assumption. Using Chernoff’s inequality, we have
 32r −32r  10αn −32r
P {dj > 32r} ≤
≤
=: p.
em/αn
m
Let S be the number of columns j with dj > 32r. Then S is a sum of m independent Bernoulli
random variables with expectations at most p. Again, Chernoff’s inequality implies
 10αn −5rm
P {S > m/4} ≤ (4ep)m/4 ≤ pm/6 ≤
.
m
The second inequality here holds since 4e < p1/2 , which in turn follows by assumption on α.

15

It remains to take a union bound over all blocks I × J. It is enough to consider the
blocks with largest possible number of columns, thus with k = dm/αde. We obtain that the
conclusion of the lemma holds with probability at least

n  
X
n
n
10αn −5rm
1−
≤ 1 − n−r .
m dm/αde
m
m=1
p
In the last inequality we used the assumption that α ≥ m/n. The proof is complete.

3.5. Iterative decomposition: proof of Theorem 2.1. Finally, we combine the tools we
developed so far, and we construct an iterative decomposition of the adjacency matrix the
way we outline in Section 3.1. Let us set up one step of this procedure, where we consider
an m × m block and decompose almost all of it (everything except an m/2 × m/2 block) into
classes N , R and C satisfying the conclusion of Theorem 2.6. Once we can do this, we repeat
the procedure for the m/2 × m/2 block, etc.
p
Lemma 3.7 (Decomposition of a block). Let 1 ≤ m ≤ n and α ≥ m/n. Then for r ≥ 1
the following holds with probability at least 1 − 3n−r . Consider a block I × J of size m × m.
Then there exists an exceptional sub-block I1 × J1 with dimensions at most m/2 × m/2 such
that the remaining part of the block, that is (I × J) \ (I1 × J1 ), can be decomposed into three
classes N , R ⊂ (I \ I1 ) × J and C ⊂ I × (J \ J1 ) so that the following holds.
p
• The graph concentrates on N , namely k(A − E A)N k ≤ Cr3/2 αd log(en/m).
• Each row of AR and each column of AC has at most 32r ones.
Moreover, R intersects at most n/αd columns and C intersects at most n/αd rows of I × J.
After a permutation of rows and columns, a decomposition of the block stated in Lemma 3.7
can be visualized in Figure 4c.

(a) Initial step.

(b) Repeat for transpose.

(c) Final decomposition.

Figure 4. Construction of a block decomposition in Lemma 3.7.
Proof. Since we are going to use Lemmas 3.4, 3.5 and 3.6, let us fix realization of the random
graph that satisfies the conclusion of those three lemmas.
By Lemma 3.5, all but m/αd rows of AI×J have at most 8rαd ones; let us denote by I 0 the
set of indices of those rows with at most 8rαd ones. Then we can use Lemma 3.4 for the block
I 0 × J and with α replaced by 8rα; the choice of I 0 ensures that all rows have small numbers
of ones, as required in that lemma. To control the rows outside I 0 , we may use Lemma 3.6
for (I \ I 0 ) × J; as we already noted, this block has at most m/αd rows as required in that

16

CAN M. LE, ELIZAVETA LEVINA AND ROMAN VERSHYNIN

lemma. Intersecting the good sets of columns produced by those two lemmas, we obtain a
set of at most m/2 exceptional columns J1 ⊂ J such that the following holds.
p
• On the block N1 := I 0 × (J \ J1 ), we have k(A − E A)N1 k ≤ Cr3/2 αd log(en/m).
• For the block C := (I \ I 0 ) × (J \ J1 ), all columns of AC have at most 32r ones.
Figure 4a illustrates the decomposition of the block I × J into the set of exceptional columns
indexed by J1 and good sets N1 and C.
To finish the proof, we apply the above argument to the transpose AT on the block J × I.
To be precise, we start with the set J 0 ⊂ J of all but m/αd small columns of AI×J (those
with at most 8rαd ones); then we obtain an exceptional set I1 ⊂ I of at most m/2 rows; and
finally we conclude that A concentrates on the block N2 := (I \ I1 ) × J 0 and has small rows
on the block R := (I \ I1 ) × (J \ J 0 ). Figure 4b illustrates this decomposition.
It only remains to combine the decompositions for A and AT ; Figure 4c illustrates a result
of the combination. Once we define N := N1 ∪ N2 , it becomes clear that N , R and C have
the required properties.3

Proof of Theorem 2.6. Let us fix a realization of the random graph that satisfies the conclusion of Lemma 3.7. Applying that lemma for m = n and with α = 1, we decompose the set of
edges [n] × [n] into three classes N0 , C0 and R0 plus an n/2 × n/2 exceptional block I1p× J1 .
Apply Lemma 3.7 again, this time for the block I1 × J1 , for m = n/2 and with α = 1/2.
We decompose I1 × J1 into N1p
, C1 and R1 plus an n/4 × n/4 exceptional block I2 × J2 .
Repeat this process for α = m/n where m is the running size of the block; we halve this
size at each step, and so we have αi ≤ 2−i/2 . Figure 3c illustrates a decomposition that we
may obtain this way. In a finite number of steps (actually, in O(log n) steps) the exceptional
block becomes empty, and the process terminates. At that point we have decomposed the
set of edges [n] × [n] into N , R and C, defined as the union of Ni , Ci and Ri respectively,
which we obtained at each step. It is clear that R and C satisfy the required properties.
It remains to bound the deviation of A on N . By construction, Ni satisfies
p
k(A − E A)Ni k ≤ Cr3/2 αi d log(eαi ).
Thus, by triangle inequality we have
X
p
√
k(A − E A)N k ≤
Cr3/2 αi d log(eαi ) ≤ C 0 r3/2 d.
i≥0

In the second inequality we used that αi ≤ 2−i/2 , which forces the series to converge. The
proof of Theorem 2.6 is complete.

3.6. Replacing the degrees by the `2 norms in Theorem 2.1. Let us now prove the
“moreover” part of Theorem 2.1, where d0 is the the maximal `2 norm of the rows and columns
of the regularized adjacency matrix A0 . This is clearly a stronger statement than in the main
part of the theorem. Indeed, since all entries of A0 are bounded in absolute value by 1, each
degree, being the `1 norm of a row, is bounded below by the `2 norm squared.
This strengthening is in fact easy to check. To do so, note that the definition of d0 was
used only once in the proof of Theorem 2.1, namely in Step 2 where we bounded the norms
of A0R and A0C . Thus, to obtain the strengthening, it is enough to replace the application of
Lemma 2.7 there by the following lemma.
3It may happen that an entry ends up in more than one class N , R and C. In such cases, we split the tie

arbitrarily.

17

Lemma 3.8. Consider a matrix B with entries in [0, 1]. Suppose
each row of√B has at most
√
a non-zero entries, and each column has `2 norm at most b. Then kBk ≤ ab.
Proof. To prove the claim, let x be a vector with kxk2 = 1. Using Cauchy-Schwarz inequality
and the assumptions, we have

2 X  X
X
XX
2
Bij
x2i
kBxk22 =
Bij xi ≤
j

≤

X
j

b

i: Bij 6=0

j

i

X



x2i = b

i: Bij 6=0

X
i

x2i

X

i: Bij 6=0

1≤b

j: Bij 6=0

X

x2i a = ab.

i

Since x is arbitrary, this completes the proof.



4. Concentration of the regularized Laplacian
In this section, we state the following formal version of Theorem 1.2, and we deduce it
from concentration of adjacency matrices (Theorem 2.1).
Theorem 4.1 (Concentration of regularized Laplacians). Consider a random graph from the
inhomogeneous Erdös-Rényi model, and let d be as in (1.3). Choose a number τ > 0. Then,
for any r ≥ 1, with probability at least 1 − e−r one has
Cr2 
d 5/2
kL(Aτ ) − L(E Aτ )k ≤ √ 1 +
.
τ
τ
Proof. Two sources contribute to the deviation of Laplacian – the deviation of the adjacency
matrix and the deviation of the degrees. Let us separate and bound them individually.
Step 1. Decomposing the deviation. Let us denote Ā := E A for simplicity; then
E := L(Aτ ) − L(Āτ ) = Dτ−1/2 Aτ Dτ−1/2 − D̄τ−1/2 Āτ D̄τ−1/2 .
Here Dτ = diag(di + τ ) and D̄τ = diag(d¯i + τ ) are the diagonal matrices with degrees of Aτ
and Āτ on the diagonal, respectively. Using the fact that Aτ − Āτ = A − Ā, we can represent
the deviation as
E =S+T

where

S = Dτ−1/2 (A − Ā)Dτ−1/2 ,

T = Dτ−1/2 Āτ Dτ−1/2 − D̄τ−1/2 Āτ D̄τ−1/2 .

Let us bound S and T separately.
Step 2. Bounding S. Let us introduce a diagonal matrix ∆ that should be easier to
work with than Dτ . Set ∆ii = 1 if di ≤ 8rd and ∆ii = di /τ + 1 otherwise. Then entries of
τ ∆ are upper bounded by the corresponding entries of Dτ , and so
τ kSk ≤ k∆−1/2 (A − Ā)∆−1/2 k.
Next, by triangle inequality,
τ kSk ≤ k∆−1/2 A∆−1/2 − Āk + kĀ − ∆−1/2 Ā∆−1/2 k =: R1 + R2 .
A0

∆−1/2 A∆−1/2

(4.1)

In order to bound R1 , we use Theorem 2.1 to show that
:=
concentrates
0
around Ā. This should be possible because A is obtained from A by reducing the degrees
that are bigger than 8rd. To apply the “moreover” part of Theorem 2.1, let us check the
magnitude of the `2 norms of the rows A0i of A0 :
kA0i k22 =

n
X
j=1

Aij
di
≤
≤ max(8rd, τ ).
∆ii ∆jj
∆ii

18

CAN M. LE, ELIZAVETA LEVINA AND ROMAN VERSHYNIN

P
Here in the first inequality we used that ∆jj ≥ 1 and j Aij = di ; the second inequality
follows by definition of ∆ii . Applying Theorem 2.1, we obtain with probability 1 − n−r that
√
√
R1 = kA0 − Āk ≤ C1 r2 ( d + τ ).
To bound R2 , we note that by construction of ∆, the matrices Ā and ∆−1/2 Ā∆−1/2 coincide
on the block I × I, where I is the set of vertices satisfying di ≤ 8rd. This block is very large
– indeed, Lemma 3.5 implies that |I c | ≤ n/d with probability 1 − n−r . Outside this block,
i.e. on the small blocks I c × [n] and [n] × I c , the entries of Ā − ∆−1/2 Ā∆−1/2 are bounded
by the corresponding entries of Ā, which are all bounded by d/n. Thus, using Lemma 2.7,
we have
√
R2 ≤ kĀI c ×[n] k + kĀ[n]×I c k ≤ 2 d.
Substituting the bounds for R1 and R2 into (4.1), we conclude that
√
C2 r 2 √
kSk ≤
( d + τ)
τ
with probability at least 1 − 2n−r .
Step 3. Bounding T . Bounding the spectral norm by the Hilbert-Schmidt norm, we get
n
q i
h p
X
kT k ≤ kT kHS =
Tij2 , where Tij = (Āij + τ /n) 1/ δij − 1/ δ̄ij
i,j=1

and δij = (di + τ )(dj + τ ) and δ̄ij = (d¯i + τ )(d¯j + τ ). To bound Tij , we note that
0 ≤ Āij + τ /n ≤

d+τ
n

and

1/

q
p
δij − 1/ δ̄ij =

δij − δ̄ij
|δij − δ̄ij |
q
.
≥
p
2τ 3
δij δ̄ij + δ̄ij δij

Recalling the definition of δij and δ̄ij and adding and subtracting (di + τ )(d¯j + τ ), we have
δij − δ̄ij = (di + τ )(dj − d¯j ) + (d¯j + τ )(di − d¯i ).
So, using the inequality (a + b)2 ≤ 2(a2 + b2 ) and bounding d¯j + τ by d + τ , we obtain
n
n
n
i
X
X
(d + τ )2 h X
2
2
2
2
¯
¯i )2 .
kT k ≤
(4.2)
(d
+
τ
)
(d
−
d
)
+
n(d
+
τ
)
(d
−
d
i
j
j
i
n2 τ 6
i=1

j=1

i=1

We claim that
n
X
(dj − d¯j )2 ≤ C3 r2 nd

with probability 1 − e−2r .

(4.3)

j=1

Indeed, since the variance of each di is bounded by d, the expectation of the sum in (4.3) is
bounded by nd. To upgrade the variance bound to an exponential deviation bound, one can
use one of the several standard
methods.
For example, Bernstein’s inequality implies that
n
√ o
¯
Xi = dj − dj satisfies P Xi > C4 t d ≤ e−t for all t ≥ 1. This means that the random
variable Xi2 belongs to the Orlicz space Lψ1/2 and has norm kXi2 kψ1/2 ≤ C3 d, see [26]. By
P
triangle inequality, we conclude that k ni=1 Xi2 kψ1/2 ≤ C3 nd, which in turn implies (4.3).
Furthermore, (4.3) implies
n
X
i=1

(di + τ )2 ≤ 2

n
X
i=1

(di − d¯i )2 + 2

n
X
i=1

(d¯i + τ )2 ≤ 2C3 r2 nd + 2n(d + τ )2 ≤ C5 r2 n(d + τ )2 .

19

Substituting this bound and (4.3) into (4.2) we conclude that
h
i C r4 
(d + τ )2
d 5
6
2
2
2
2
kT k2 ≤
.
·
C
r
nd
C
r
n(d
+
τ
)
+
n(d
+
τ
)
≤
1
+
3
5
n2 τ 6
τ
τ
It remains to substitute the bounds for S and T into the inequality kEk ≤ kSk + kT k, and
simplify the expression. The resulting bound holds with probability at least 1 − n−r − n−r −
e−2r ≥ 1 − e−r , as claimed.

5. Further questions
5.1. Optimal regularization? The main point of our paper was that regularization helps
sparse graphs to concentrate. We have discussed several kinds of regularization in Section 1.4
and mentioned some more in Section 1.4. We found that any meaningful regularization works,
as long as it reduces the too high degrees and increases the too low degrees. Is there an optimal
way to regularize a graph? Designing the best “preprocessing” of sparse graphs for spectral
algorithms is especially interesting from the applied perspective, i.e. for real world networks.
On the
√ theoretical level, can regularization of sparse graphs produce the same optimal
bound 2 d(1 + o(1)) that we saw for dense graphs in (1.1)? Thus, an ideal regularization
should bring all parasitic outliers of the spectrum into the bulk. If so, this would lead to a
potentially simple spectral clustering algorithm for community detection in networks which
matches the theoretical lower bounds. Algorithms with optimal rates exist for this problem
[33, 29], but their analysis is very technical.
5.2. How exactly concentration depends on regularization? It would be interesting
to determine how exactly the concentration of Laplacian depends on the regularization parameter τ . The dependence in Theorem 4.1 is not optimal, and we have not made efforts to
improve it. Although it is natural to choose τ ∼ d as in Theorem 1.2, choosing τ  d could
also be useful [23]. Choosing τ  d may be interesting as well, for then L(E Aτ ) ≈ L(E A)
and we obtain the concentration of L(Aτ ) around the Laplacian of the expectation of the
original (rather than regularized) matrix E A.
5.3. Average expected degree? Both concentration results of this paper, Theorems 1.1
and 1.2, depend on dP= maxij npij . Would it be possible to reduce d to the maximal expected
degree dave = maxi j pij ?
5.4. From random graphs to random matrices? Adjacency matrices of random graphs
are particular examples of random matrices. Does the phenomenon we described, namely
that regularization leads to concentration, apply for general random matrices? Guided by
Theorem 1.1, we might expect the following for a broader general class of random matrices
B with mean zero independent entries. First, the only reason the spectral norm of B is too
large (and that it is determined by outliers of spectrum) could be the existence of a large row
or column. Furthermore, it might be possible to reduce the norm of B (and thus bring the
outliers into the bulk of spectrum) by regularizing in some way the rows and columns that
are too large. For related questions in random matrix theory, see the recent work [4, 21].
References
[1] E. Abbe, A. S. Bandeira, and G. Hall. Exact recovery in the stochastic block model. IEEE Transactions
on Information Theory, 62(1):471–487, 2016.
[2] N. Alon and N. Kahale. A spectral technique for coloring random 3-colorable graphs. SIAM J. Comput.,
(26):1733–1748, 1997.

20

CAN M. LE, ELIZAVETA LEVINA AND ROMAN VERSHYNIN

[3] A. A. Amini, A. Chen, P. J. Bickel, and E. Levina. Pseudo-likelihood methods for community detection
in large sparse networks. The Annals of Statistics, 41(4):2097–2122, 2013.
[4] A. Bandeira and R. V. Handel. Sharp nonasymptotic bounds on the norm of random matrices with
independent entries. Annals of Probability, to appear, 2014.
[5] R. Bhatia. Matrix Analysis. Springer-Verlag New York, 1996.
[6] P. J. Bickel and A. Chen. A nonparametric view of network models and Newman-Girvan and other
modularities. Proc. Natl. Acad. Sci. USA, 106:21068–21073, 2009.
[7] B. Bollobas, S. Janson, and O. Riordan. The phase transition in inhomogeneous random graphs. Random
Structures and Algorithms, 31:3–122, 2007.
[8] C. Bordenave, M. Lelarge, and L. Massoulié. Non-backtracking spectrum of random graphs: community
detection and non-regular Ramanujan graphs. arxiv:1501.06087, 2015.
[9] S. Boucheron, G. Lugosi, and P. Massart. Concentration inequalities: a nonasymptotic theory of independence. Oxford University Press, 2013.
[10] T. Cai and X. Li. Robust and computationally feasible community detection in the presence of arbitrary
outlier nodes. Ann. Statist., 43(3):1027–1059, 2015.
[11] 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 Workshop and Conference
Proceedings, 23:35.1 – 35.23, 2012.
[12] P. Chin, A. Rao, and V. Vu. Stochastic block model and community detection in the sparse graphs : A
spectral algorithm with optimal rate of recovery. arXiv:1501.05021, 2015.
[13] F. R. K. Chung. Spectral Graph Theory. CBMS Regional Conference Series in Mathematics, 1997.
[14] A. Decelle, F. Krzakala, C. Moore, and L. Zdeborová. Asymptotic analysis of the stochastic block model
for modular networks and its algorithmic applications. Physical Review E, 84:066106, 2011.
[15] U. Feige and . Ofek. Spectral techniques applied to sparse random graphs. Wiley InterScience, 2005.
[16] Z. Fredi and J. Komls. The eigenvalues of random symmetric matrices. Combinatorica, 1:3:233–241, 1980.
[17] J. Friedman, J. Kahn, and E. Szemeredi. On the second eigenvalue in random regular graphs. Proc Twenty
First Annu ACMSymp Theory of Computing, pages 587–598, 1989.
[18] C. Gao, Z. Ma, A. Y. Zhang, and H. H. Zhou. Achieving optimal misclassification proportion in stochastic
block model. arXiv:1505.03772, 2015.
[19] O. Guédon and R. Vershynin. Community detection in sparse networks via grothendieck’s inequality.
Probability Theory and Related Fields, to appear, 2014.
[20] B. Hajek, Y. Wu, and J. Xu. Achieving exact cluster recovery threshold via semidefinite programming.
arXiv:1412.6156, 2014.
[21] R. V. Handel. On the spectral norm of inhomogeneous random matrices. arXiv:1502.05003, 2015.
[22] P. W. Holland, K. B. Laskey, and S. Leinhardt. Stochastic blockmodels: first steps. Social Networks,
5(2):109–137, 1983.
[23] A. Joseph and B. Yu. Impact of regularization on spectral clustering. Ann. Statist., 44(4):1765–1791,
2016.
[24] M. Krivelevich and B. Sudakov. The largest eigenvalue of sparse random graphs. Combin Probab Comput,
12:61–72, 2003.
[25] M. Ledoux. The Concentration of Measure Phenomenon, volume 89 of Mathematical Surveys and Monographs. Amer. Math. Society, 2001.
[26] M. Ledoux and M. Talagrand. Probability in Banach spaces: Isoperimetry and processes. Springer-Verlag,
Berlin, 1991.
[27] J. Lei and A. Rinaldo. Consistency of spectral clustering in stochastic block models. Ann. Statist.,
43(1):215–237, 2015.
[28] L. Lu and X. Peng. Spectra of edge-independent random graphs. The electronic journal of combinatorics,
20(4), 2013.
[29] L. Massoulié. Community detection thresholds and the weak Ramanujan property. In Proceedings of the
46th Annual ACM Symposium on Theory of Computing, STOC ’14, pages 694–703, 2014.
[30] McSherry. Spectral partitioning of random graphs. Proc. 42nd FOCS, pages 529–537, 2001.
[31] A. Montanari and S. Sen. Semidefinite programs on sparse random graphs and their application to
community detection. arXiv:1504.05910, 2015.
[32] E. Mossel, J. Neeman, and A. Sly. Consistency thresholds for binary symmetric block models.
arXiv:1407.1591, 2014.

21

[33] E. Mossel, J. Neeman, and A. Sly. A proof of the block model threshold conjecture. arXiv:1311.4115,
2014.
[34] E. Mossel, J. Neeman, and A. Sly. Reconstruction and estimation in the planted partition model. Probability Theory and Related Fields, 2014.
[35] R. Oliveira. Concentration of the adjacency matrix and of the laplacian in random graphs with independent edges. arXiv:0911.0600, 2010.
[36] A. Pietsch. Operator Ideals. North-Holland Amsterdam, 1978.
[37] G. Pisier. Factorization of linear operators and geometry of Banach spaces. Number 60 in CBMS Regional
Conference Series in Mathematics. AMS, Providence, 1986.
[38] G. Pisier. Grothendiecks theorem, past and present. Bulletin (New Series) of the American Mathematical
Society, 49(2):237–323, 2012.
[39] T. Qin and K. Rohe. Regularized spectral clustering under the degree-corrected stochastic blockmodel.
In Advances in Neural Information Processing Systems, pages 3120–3128, 2013.
[40] E. M. Stein and R. Shakarchi. Functional Analysis: Introduction to Further Topics in Analysis. Princeton
University Press, 2011.
[41] N. Tomczak-Jaegermann. Banach-Mazur distances and finite-dimensional operator ideals. John Wiley &
Sons, Inc., New York, 1989.
[42] J. A. Tropp. Column subset selection, matrix factorization, and eigenvalue optimization. Proceedings of
the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 978–986, 2009.
[43] R. Vershynin. Introduction to the non-asymptotic analysis of random matrices. In Y. Eldar and G. Kutyniok, editors, Compressed sensing: theory and applications. Cambridge University Press. Submitted.
[44] V. Vu. Spectral norm of random matrices. Combinatorica, 27(6):721–736, 2007.
Department of Statistics, University of California, Davis, One Shields Ave, Davis, CA 95616,
U.S.A.
E-mail address: canle@ucdavis.edu
Department of Statistics, University of Michigan, 1085 S. University Ave, Ann Arbor, MI
48109, U.S.A.
E-mail address: elevina@umich.edu
Department of Mathematics, University of Michigan, 530 Church St, Ann Arbor, MI 48109,
U.S.A.
E-mail address: romanv@umich.edu

