Optimal Lower Bounds for Sketching Graph Cuts
Charles Carlson∗

Alexandra Kolla

†

Nikhil Srivastava‡

Luca Trevisan§

arXiv:1712.10261v1 [cs.DS] 29 Dec 2017

January 1, 2018

Abstract
We study the space complexity of sketching cuts and Laplacian quadratic forms of graphs.
We show that any data structure which approximately stores the sizes of all cuts in an undirected graph on n vertices up to a 1 + ǫ error must use Ω(n log n/ǫ2 ) bits of space in the worst
case, improving the Ω(n/ǫ2 ) bound of [ACK+ 16] and matching the best known upper bound
achieved by spectral sparsifiers [BSS12]. Our proof is based on a rigidity phenomenon for cut
(and spectral) approximation which may be of independent interest: any two d−regular graphs
which approximate each other’s cuts significantly better than a random graph approximates the
complete graph must overlap in a constant fraction of their edges.

1

Introduction

An ǫ−spectral sparsifier [ST04] of a weighted graph G is a weighted graph H such that for every
x ∈ Rn we have the multiplicative guarantee:
(1 − ǫ)xT LG x ≤ xT LH x ≤ (1 + ǫ)xT LG x.

(1)

An ǫ−cut sparsifier [BK96] is a graph such that (1) holds for all x ∈ {−1, 1}n ; the former condition
clearly implies the latter, and it is not hard to see that the converse is not true.
There have been many papers on efficiently constructing sparsifiers with few edges (e.g. [SS11,
FHHP11, AZLO15, LS17]). The best known sparsity-approximation tradeoff is achieved in [BSS12],
who showed that every graph on n vertices has an ǫ-spectral sparsifier with O(n/ǫ2 ) edges (and
this is also the best known upper bound for ǫ-cut sparsification). Since every weighted edge can be
stored using O(log n) bits1 , storing such a sparsifier requires O(n log n/ǫ2 ) bits.
The recent work [ACK+ 16] studied the question of whether it is possible to use substantially
fewer bits if one simply wants a data structure (not necessarily a graph) which answers cut and
quadratic form queries. We will use the following definition, which is inspired by the one in [JS17].
Definition 1.1. An ǫ−spectral sketch of a graph G is a function f : Rn → R such that for every
x ∈ Rn :
(1 − ǫ)xT LG x ≤ f (x) ≤ (1 + ǫ)xT LG x.
(2)
∗

ccarlsn2@illinois.edu. U.I.U.C.
akolla@illinois.edu. U.I.U.C. Supported by NSF Grant 1423452.
‡
nikhil@math.berkeley.edu. U.C. Berkeley. Supported by NSF grant CCF-1553751 and a Sloan research fellowship.
§
luca@berkeley.edu. U.C. Berkeley. Supported by the National Science Foundation under Grants No. 1540685 and
No. 1655215.
1
After discretizing the weights to, say, 1/n4 precision, which introduces negligible error.
†

1

An ǫ−cut sketch is a function f : {−1, 1}n → R such that (2) holds for all x ∈ {−1, 1}n .
A sketching scheme is a deterministic map sk from graphs on n vertices to (ǫ-spectral or ǫ-cut)
sketches f : Rn → R, along with specified procedures for storing the functions as bit strings and for
evaluating any given f on a query x 2 . The number of bits required to store f is called its size.
In [ACK+ 16] it was shown that any ǫ-cut sketch must use Ω(n/ǫ2 ) bits in the worst case,
leaving a logarithmic gap between the best known upper and lower bounds. In this paper, we
close this gap by showing that any ǫ-cut sketching scheme must in fact use Ω(n log n/ǫ2 ) bits
whenever ǫ = ω(n−1/4 ) (Theorem 3.2), which means that it is not in general possible to obtain any
asymptotic savings by considering sketches which are not graphs. We also give a lowerbound for
ǫ-spectral sketching with a simpler proof and slightly better constants (Theorem 2.1).

1.1

Related Work

The paper [ACK+ 16] also studied the problem of producing a “for each” sketching algorithm,
which has the property that for any particular query x, f (x) approximates xT Lx with constant
probability. They showed that in this weaker model it is possible to obtain ǫ−cut sketches of
size O(npolylog(n)/ǫ) and ǫ-spectral sketches of size O(npolylog(n)/ǫ1.6 ). The latter bound was
recently improved to O(npolylog(n)/ǫ) and generalized to include queries to the pseudoinverse in
[JS17].
In contrast, in this paper we study only the “for all” model, in which the sketch is required to
work for all queries simultaneously.

1.2

Techniques

Our proof is based on
√ the following rigidity phenomenon: there is a constant c such that if two
d−regular graphs c/ d-cut approximate each other then they must overlap in a constant fraction
of edges (Lemmas 2.2 and 3.1). This allows us to argue that below this approximation threshold
any sketch encodes a constant fraction of the information in the graph, and so any sketch must use
Ω(dn log n) = Ω(n log n/ǫ2 ) bits.
Interestingly, this phenomenon is very sensitive to the value of the constant c — in particular,
a well-known theorem of Friedman [Fri03] says that
√ of the Laplacian of a random
√ the eigenvalues
d−regular graph are contained in the range [d−2 d − 1−o(1),
d+2
d+o(1)] with high probability,
√
which implies that almost every d−regular graph has a 3/ d-spectral sketch of constant size, namely
the complete graph.
Note that according to the Alon-Boppana √
bound [Nil91] it is not possible to approximate Kn
by a d−regular graph with error less than 2/ d. Thus, our result can be interpreted as saying
that a d−regular graph can only be approximated by nearby graphs when the error is substantially
below the Alon-Boppana bound.
We remark that the proof of [ACK+ 16] was based on showing a Ω(1/ǫ2 ) bit lower bound for a
constant sized graph by reducing to the Gap-Hamming problem in communication complexity, and
then concatenating O(n) instances of this problem to obtain an instance of size n. This method
is thereby inherently incapable of recovering the logarithmic factor that we obtain (in contrast, we
work with random regular graphs).
2
We will not be concerned with the details of these procedures since we are only interested in the space used by
the sketches and not computational parameters such as query time / success probability of randomized schemes.

2

1.3

Notation and Organization

We will denote ǫ-spectral approximation as
(1 − ǫ)LG  LH  (1 + ǫ)LG
and ǫ−cut approximation as
(1 − ǫ)LG  LH  (1 + ǫ)LG .
We will use lg and ln to denote binary and natural logarithms.
We prove our lower bound for spectral sketching in Section 2, and the lower bound for cut
sketching in Section 3. Although the latter is logically stronger than the former, we have chosen to
present the spectral case first because it is extremely simple and introduces the conceptual ideas
of the proof.

Acknowledgments
We would like to thank MSRI and the Simons Institute for the Theory of Computing, where this
work was carried out during the “Bridging Discrete and Continuous Optimization” program.

2

Lower Bound for Spectral Sketches

In this section, we prove the following theorem.
Theorem 2.1. For any ǫ = ω(n−1/4 ), any ǫ-spectral sketching scheme sk for graphs with n vertices
n lg n
must use at least 500ǫ
2 · (1 − on (1)) bits in the worst case.
The main ingredient is the following lemma.
Lemma 2.2 (Rigidity of Spectral Approximation). Suppose G and H are simple d−regular graphs
such that
(1 − ǫ)LG  LH  (1 + ǫ)LG .
Then G and H must have at least

dn
2 (1

− ǫ2 d/2) edges in common.

Proof. Since G and H are d−regular, we have LH − LG = (dI − AH ) − (dI − AG ) = AG − AH and
kLG k ≤ 2d. Thus the hypothesis implies that:
−2dǫI  −ǫ · LG  LH − LG = AG − AH  ǫ · LG  2dǫI,
which means kAG − AH k ≤ 2ǫd. Passing to the Frobenius norm, we find that
X
(AG (i, j) − AH (i, j))2 = kAG − AH k2F ≤ nkAG − AH k2 ≤ 4ǫ2 d2 n.
ij

The matrix AG − AH has entries in {−1, 0, 1}, with exactly two nonzero entries for every edge in
E(G)∆E(H), so the left hand side is equal to
2|E(G)∆E(H)| = 2(|E(G)| + |E(H)| − 2|E(G) ∩ E(H)|) = 2(dn − 2|E(G) ∩ E(H)|),
since |E(G)| = |E(H)| = dn/2. Rearranging yields the desired claim.
3

Note that the above lemma is vacuous for ǫ ≥
fraction of their edges for ǫ below this threshold.

p

2/d but indicates that G and H must share a

Lemma 2.3. For any function f : Rn → R and ǫ < 1/2:

lg |{G ∈ Gn,d : G is ǫ−spectrally approximated by f }| ≤ dn/2 + 5ǫ2 d2 n lg n,

where Gn,d denotes the set of all d−regular graphs on n vertices.
Proof. If f does not ǫ−approximate any d−regular graph then we are done. Otherwise, let H be
the lexicographically (in some pre-determined ordering on d−regular graphs) first graph which f
ǫ-approximates. Suppose G is another graph that f ǫ−approximates. Notice that by applying (2)
twice, we have that for every x ∈ Rn :
xT L H x
f (x)
xT L H x
1+ǫ
1−ǫ
≤ T
= T
·
≤
,
1+ǫ
x LG x
x LG x
f (x)
1−ǫ

so G 3ǫ-spectrally approximates H. By Lemma 2.2, H and G must share
dn
(1 − 9ǫ2 d/2)
2
edges. Thus, G can be encoded by specifying:
k :=

1. Which edges of H occur in G. This is a subset of the edges of H, which requires at most
dn/2 bits.
2. The remaining dn/2 − k = 9ǫ2 d2 n/4 edges of G. Each edge requires at most 2 lg(n) bits to
specify, so the number of bits needed is at most 18ǫ2 d2 n lg n/4.
Thus, the total number of bits required is at most
dn/2 + 18ǫ2 d2 n lg n/4,
as desired.
√
Theorem 2.4. ([Wor99]Cor. 2.4) For d = o( n), the number of d−regular graphs on n vertices
is:
 2 

(dn)!
d
d3
1 − d2
−
+O
≥ exp(dn ln(n/d)/2 · (1 − on (1))).
exp
dn/2
n
4
12n
n
(dn/2)!2
(d!)
1
Proof of Theorem 2.1. Let N be the number of distinct sketches produced by sk and let d = ⌈ 25ǫ
2 ⌉.
By Lemma 2.3, the binary logarithm of the number of d−regular graphs ǫ-spectrally approximated
by any single sketch f ∈ range(sk) is at most

dn/2 + dn lg n/5 ≤ dn lg n/5 · (1 + o(1)).
√
On the other hand by Theorem 2.4, since d = o( n) we have
lg |Gn,d | ≥ dn lg(n/d)/2 · (1 − o(1)) ≥ dn lg n/4 · (1 − o(1)).
Since every d−regular graph receives a sketch, we must have
(1 + o(1)) lg N ≥ dn lg n/4 − dn lg n/5 = dn lg n/20 = n lg n/500ǫ2 ,
as desired.

4

(3)

√
Remark 1. The proof above actually shows that any 1/5 d-spectral sketching scheme for d−regular
graphs on n vertices must use at least Ω(dn lg n) bits on average, since the same proof goes through
if we only insist that the sketches work for most graphs.
Remark 2. The result of [BSS12] produces ǫ-spectral sparsifiers with 16n/ǫ2 edges, which yield
ǫ-spectral sketches with 64n lg n/ǫ2 bits by discretizing the edge weights up to 1/n2 error, so the
bound above is tight up to a factor of 64 · 500. We have not made any attempt to optimize the
constants.

3

Lower Bound for Cut Sketches

In this section we prove Theorem 3.2. The new ingredient is a rigidity lemma for cuts, which may
be seen as a discrete analogue of Lemma 2.2. The lemma holds for bipartite graphs and is proven
using a Goemans-Williamson [GW95] style rounding argument.
Lemma 3.1 (Rigidity of Cut Approximation). Suppose G and H are simple d−regular bipartite
graphs with the same bipartition L ∪ R, such that
(1 − ǫ)LG  LH  (1 + ǫ)LG .
√
Then G and H must have at least dn
2 (1 − 3 dǫ) edges in common.

(4)

Proof. We will show the contrapositive. Assume
|E(G) \ E(H)| = |E(H) \ E(G)| = δdn/2
√
for some δ ≥ 3 dǫ. To show that (4) does not hold, it is sufficient to exhibit a vector x ∈ {−1, 1}n
such that
xT M x := xT (LG − LH )x > 2ǫdn ≥ ǫ · xT LG x,

where M = LG − LH = AH − AG , since both graphs are d−regular and the latter inequality follows
from kLG k ≤ 2d. To find such an x we will first construct n vectors y1 , . . . , yn ∈ Rn such that
n
X

i,j=1

Mij hyi , yj i > πǫdn

(5)

and then use hyperplane rounding to find scalars x1 , . . . , xn ∈ {−1, 1} which satisfy:
n
X

Mij xi xj > 2ǫdn.

(6)

i,j=1

Let z1 , . . . , zn ∈

Rn

be the columns of

M
I+√ ,
d
2
2
and note that kzi k ∈ [1, 3] since zi (i) = 1 and every vertex is incident with at most d edges in each
of E(H) \ E(G) and E(G) \ E(H). The relevant inner products of the zi are easy to understand:


if Mij = 0
0

1
1
2
if ij ∈ E(H) \ E(G)
Mij hzi , zj i = √d = 1 · (1 · √d + 1 · √d )


−1
−1
 √2 = (−1) · (1 · √
+1· √
) if ij ∈ E(G) \ E(H),
d

d

5

d

where in the latter two cases we have used the fact that i and j cannot have any common neighbors
because they lie on different sides of the bipartition. Letting yi = zi /kzi k, we therefore have
n
X

2
Mij hyi , yj i ≥ 2 · δdn · √ > πǫdn
3 d
i,j=1

(7)

by our choice of δ. Let w be a random unit vector and let
(
+1 if hyi , wi ≥ 0
xi =
−1 if hyi , wi < 0.
We denote the angle between vectors yi , yj ∈ Y as θij . We recall that θij = cos−1 hyi , yj i since
θ
yi and yj have unit length. It follows that the probability that xi 6= xj is equal to πij and the
θ
probability of xi = xj is equal to (1 − πij ). Thus,


n
n
X
X
E
Mij xi xj  =
Mij E[xi xj ]
i,j=1

i,j=1
n
X


θij
θij
Mij
(−1) + (1 −
)(1)
=
π
π
i,j=1


n
X
2θij
Mij 1 −
=
π

=
=
=
≥



i,j=1
n
X

Mij

π

− θij

2
π

Mij

π


− cos−1 hyi , yj i

2
π

2
π
2
π

i,j=1
n
X
i,j=1
n
X
i,j=1
n
X
i,j=1

2
2



Mij sin−1 hyi , yj i
Mij hyi , yj i since sin−1 (x) ≥ x

> 2ǫdn,
by (7), as desired.

Remark 3. The analysis of the rounding scheme above can be improved from 2/π to the GoemansWilliamson constant 0.868 . . ., but we have chosen not to do so for simplicity.
Theorem 3.2. For any ǫ = ω(n−1/4 ), any ǫ-cut sketching scheme sk for graphs with n vertices
n lg n
must use at least 2304ǫ
2 · (1 − on (1)) bits in the worst case.

6

1
Proof. Assume n is divisible by 4 (add a constant if this is not the case). Let d = 16·9ǫ
2 and let
Bn,d be the set of bipartite graphs on n vertices with respect to a fixed bipartition. We proceed as
in the proof of Theorem 2.1. Let f : {−1, 1}n → R be any function which is an ǫ−cut sketch for
some graph H. Arguing as in Lemma 2.3, any other graph G ∈ Bn,d which has √
the same sketch
must 3ǫ-cut approximate H, so by Lemma 3.1, any such G must have at most 9 dǫ · dn/2 edges
which are not present in H. Thus, the encoding length of such H is at most

ℓ := dn/2 + 9d3/2 nǫ lg n = dn lg n/16 · (1 + o(1))
bits, by our choice of d, so any particular f can only be an ǫ-cut sketch for 2ℓ graphs in Bn,d
On the other hand, Bn,d is quite large. Recall that the bipartite double cover of a graph F on n
vertices is the graph on 2n vertices obtained by taking its tensor product with K2 , and two distinct
graphs must have distinct double covers. Thus, by (3) we have
lg |Bn,d | ≥ lg |Gn/2,d | ≥ dn lg n/8 · (1 − o(1)).
Thus, if N is the number of distinct sketches produced by sk, we must have
(1 + o(1)) lg N ≥ dn lg n/8 − dn lg n/16 = dn lg n/16 = n lg n/(16)2 · 9ǫ2 ,
as desired.

References
[ACK+ 16] Alexandr Andoni, Jiecao Chen, Robert Krauthgamer, Bo Qin, David P Woodruff, and
Qin Zhang. On sketching quadratic forms. In Proceedings of the 2016 ACM Conference
on Innovations in Theoretical Computer Science, pages 311–319. ACM, 2016.
[AZLO15] Zeyuan Allen-Zhu, Zhenyu Liao, and Lorenzo Orecchia. Spectral sparsification and
regret minimization beyond matrix multiplicative updates. In Proceedings of the fortyseventh annual ACM symposium on Theory of computing, pages 237–245. ACM, 2015.
[BK96]

András A Benczúr and David R Karger. Approximating st minimum cuts in õ (n 2) time.
In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing,
pages 47–55. ACM, 1996.

[BSS12]

Joshua Batson, Daniel A Spielman, and Nikhil Srivastava. Twice-ramanujan sparsifiers.
SIAM Journal on Computing, 41(6):1704–1721, 2012.

[FHHP11] Wai Shing Fung, Ramesh Hariharan, Nicholas JA Harvey, and Debmalya Panigrahi.
A general framework for graph sparsification. In Proceedings of the forty-third annual
ACM symposium on Theory of computing, pages 71–80. ACM, 2011.
[Fri03]

Joel Friedman. A proof of alon’s second eigenvalue conjecture. In Proceedings of the
thirty-fifth annual ACM symposium on Theory of computing, pages 720–724. ACM,
2003.

[GW95]

Michel X Goemans and David P Williamson. Improved approximation algorithms for
maximum cut and satisfiability problems using semidefinite programming. Journal of
the ACM (JACM), 42(6):1115–1145, 1995.
7

[JS17]

Arun Jambulapati and Aaron Sidford. Efficient o(n/ǫ) spectral sketches for the laplacian
and its pseudoinverse. arXiv preprint arXiv:1711.00571, 2017.

[LS17]

Yin Tat Lee and He Sun. An sdp-based algorithm for linear-sized spectral sparsification.
arXiv preprint arXiv:1702.08415, 2017.

[Nil91]

Alon Nilli. On the second eigenvalue of a graph. Discrete Mathematics, 91(2):207–210,
1991.

[SS11]

Daniel A Spielman and Nikhil Srivastava. Graph sparsification by effective resistances.
SIAM Journal on Computing, 40(6):1913–1926, 2011.

[ST04]

Daniel A Spielman and Shang-Hua Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the thirtysixth annual ACM symposium on Theory of computing, pages 81–90. ACM, 2004.

[Wor99]

Nicholas C Wormald. Models of random regular graphs. London Mathematical Society
Lecture Note Series, pages 239–298, 1999.

8

