Lecture 9: Sparsification (Combinatorial and Spectral), Effective Resistance, Matrix Pseudoinverses and Tail Bounds

10/8/2009 18.409 An Algorithmist’s Toolkit Lecture 9 Lecturer: Jonathan Kelner At the end of the previous lecture, we began to motivate a technique called Sparsification. In this lecture, we describe sparsifiers and their use, and give an overview of Combinatorial and Spectral Sparsifiers. We also define Spectral Sparsifiers, and create tools and language with which to construct and analyze them. 1 Sparsification Suppose we are given a graph G = (V, E). We would like to solve some cut problem (i.e. min-cut, s-t min cut, sparsest cut) and so on. The running time of algorithms for these problems typically depends on the number of edges in the graph, which might be as high as O(n2 ). Is there any way to approximate our graph with a sparse graph G in which all cuts are approximately of the same size? We will describe two ways of “sparsifying” our graph. The first is the method of Benczur-Karger, and relies on random sampling of edges. The second technique is Spectral Sparsification, and uses spectral techniques to improve upon Benczur-Karger’s algorithm. 1.1 First Try Our first attempt at sparsifying will use random sampling. Let’s start by sampling each edge with probability p. Then, if a cut has c edges crossing it in G, the expected value of edges crossing it in the new graph G is pc. Our algorithm will solve the cut problem in G . Say the answer is a cut with value S  ; then our algorithm will output the estimate S = S  /p for the original graph G. Denoting the number of edges between S and S¯ by e(S) = pc, we have the following concentration result due to Chernoff’s inequality: P (|eG� (S) − pc| ≥ pc) ≥ e− 2 pc/2 . (1) So our result will be close to the correct answer provided pc is large. In particular, picking p = Ω( d log n ), 2 c will make the right side of Eq. (1) at most n−d . Summarizing, we can choose p to get an  multiplicative approximation with probability at least 1 − n−d . Is it possible to choose p to get this multiplicative approximation for all cuts, rather than just one as above? The answer is yes; the main ingredient is a result of Karger that the number of small cuts in a graph is not too large: Theorem 1 (Karger) If G has a min-cut of size c, then the number of cuts of value αc or less is at most n2α . 1.2 Second try The problem with this proposal is that it breaks for small cuts. Say c is small, but an edge e is only involved in cuts of size ≥ k. What we want to do is to sample these edges with a small probability of failure. The idea that we use is to sample edges, but with a “weight” of 1/p. This method is called importance sampling. To do this, we need a slightly modified version of the Chernoff bound: 9-1 Theorem 2 (Chernoff Bound) Let X1 , . . . , Xn be random variables so that Xi ∈ [0, 1], and let X = Then, 2 P r[|X − E[X]| ≥ X] ≤ 2e−Θ(1) E[X]  Xi . Proof The only difference here is that the random variables Xi are no longer discrete variables, but lie in the interval [0, 1]. The proof is carried out the same as with the regular Chernoff bound. What this allows us to do is to scale our random variables without changing the error bounds. Returning to our case, we assign to every edge e a random variable Ye and a weight we . If e is in a cut of size c, we require that we ≤ c. We will set Ye = 1 with probability p/we ; and Ye = 0 with probability 1 − p/we . Instead of counting how many edges cross a cut (S, S̄), we will compute a weighted sum:  YS = we Ye e∈∂(S,S̄) The expectation is still correct; if there are c edges across the cut (S, S̄) in G, then  p we = pc. E[YS ] = we e∈∂(S,S̄) This scheme gives us an advantage: if an edge is present in only cuts of large size, we can keep it with low probability, which corresponds to setting we to be large. On the other hand, if an edge is present in cuts of small size, we will keep it with high probability, which corresponds to setting we to be small. In this way, we can approximate cut problems while throwing away more edges which are present in only cuts of high size. Thus, a natural choice for we would be the size of the smallest cut containing e. Unfortunately, we do not know we ; however, it is possible to approximate it quickly. The final result is an  multiplicative approximation based on this scheme. We refer the reader to [1] for details. 2 Spectral Sparsifiers The construction shown above is known as a Combinatorial Sparsifier. In the upcoming section and following lecture, we will see how to improve upon it with the spectral methods that we have been learning. Let G = (V, E) be our original graph. Recall that the laplacian has the property that  xT LG x = (xi − xj )2 , (i,j)∈E for some x ∈ Rn , and the sum is being taken over all edges in G. If x takes value 1 on the set S and −1 on the S̄, this equation becomes xT LG x = 4e(S). Let G be a combinatorial sparsifier of the graph G. The condition that all cuts in G are approximated with a multiplicative error of at most  by cuts in G can be restated as (1 − )xT LG� x ≤ xT LG x ≤ (1 + )xT LG� x, (2) for all x that take on only the values 1 and −1. This is true for all such discrete values of x. On the other hand, consider if Eq. (2) is true for all x ∈ Rn . Note that in this case we can limit ourselves to the instances x ∈ [−1, 1]n by normalization. We now have a good definition for a spectral version of sparsification: Definition 3 A Spectral Sparsifier G of a graph G is one for which the relation (1 − )xT LG� ≤ xT LG x ≤ (1 + )xT LG� x for all x ∈ [0, 1]n 9-2 It is clear from this definition that spectral sparsifiers are combinatorial sparsifiers. A natural question is then to ask if all combinatorial sparsifiers also spectral sparsifiers. The answer is no, and we provide a proof by counterexample. Consider the graph G with vertex set {1, 2, . . . , n} and an edge between i, j when i − j mod n ≤ k. G is G with the edge (1, n/2) added. The graph looks something like the figure below. Then, for an appropriate , G is a combinatorial sparsifier of G. Indeed, the min cut in G cuts Θ(k) edges; the min cut in G cuts one less. With  = Θ(1/k), we have that G is a combinatorial sparsifier of G. On the other hand, G is not a spectral sparsifier of G. Let   x = 0 1 . . . n/2 − 1 n/2 − 1 . . . 1 0 . Then, we have that xT LG� x = Θ(nk 3 ) k since each vertex contributes Θ( i=1 k 2 ) to the sum. On the other hand, xT LG x = Θ(nk 3 ) + ( n − 1)2 2 If k is constant, we get that we need  = Θ(1/n) for G to be a spectral sparsifier of G. 2.1 Order Relations on Laplacians In order to define spectral approximations, we first need to define the appropriate vocabulary. Earlier, we made error approximations based on cut size. In the spectral case, we will be using the laplacian of the graph instead - so a nice way to compare laplacians would be idea. That is to say, we want a good relation  on symmetric matrices that is an ordering on them, and also is somewhat consistent with the notions of cuts. How will we define this ordering? An immediate idea is the following: M  N ⇔ mi,j ≥ ni,j ∀i, j Upon second thought, we realize that this is no good for our purposes. For one, spectral graph theory is all about eigenvalues, and this relation tells us nothing about the eigenvalues of the matrix! Furthemore, the values of individual entries are highly dependent on choice of basis, which would be bad. If such a definition were used, a process like diagonalizing the Laplacians could possibly affect the graph orders. We try again with another definition: M  N if the ith eigenvalue of M is ≥ the ith eigenvalue of N for all indices i This is better in that it is basis independent - but it is too basis independent. Under this definition, we have both 9-3  1 0 0 −1  1 √ 2  1 1 1 −1  as well as 1 √ 2  1 1 1 −1    1 0 0 −1  After this experimentation, we claim that the following is the “right” definition of order. Definition 4 We write that M  N if xT M x ≥ X T N x ∀x ∈ Rn Note that this definition of order has the following properties: 1. If M  N and N  M , then M = n 2. M  0 if M is a positive semidefinite matrix. 3. M  N if M − N is positive semidefinite 4. If M1  N1 and M2  N2 , then M1 + M2  N 1 + N 2 These properties suffice for our purposes, and with this, we can define an associated order on graphs as well. Definition 5 Given graphs G and H, say that G  H if LG  LH . Claim 6 Let G = (V, EG , wG ) and H = (V, EH , wH ) be weighted graphs on the same vertex set such that wG (i, j) ≥ wH (i, j) for all edges (i, j) ∈ E. Then, G  H 2.2 Towards Spectral Sparsification With this order relation on graphs, we can now restate the goal of spectral sparsification: Given a dense graph G, we want to create a sparse graph H where Lh LG (1 + )LH By “sparse,” we mean that H has polylog(n) edges, where n is the number of nodes. We will show in this and the next lecture how to construct spectral sparsifiers with O(nlogn) edges in Polynomial time. This can actually be improved to a linear time construction, but will use geometric techniques that we will learn. Moreover, it is possible to construct O(n) edge sparsifiers in polynomial time. The benefits of this are that the problem is more geometrically flavored. It is also a nice example of how generalizing can make things easier sometimes. The algorithm that we propose is very simple. It is similar in structure to the B-K algorithm, but we use different probabilities for sampling the edges. • Compute probability pe for each edge e. • Sample each edge uniformly with probability pe , and if an edge is selected, include it with weight 1/pe . These probabilities are based on a linear algebra sense of importance, and have a nice interpretation in terms of effective resistance of circuits. To proceed with our analysis, however, we need to develop the ideas of pseudoinverses, calculating effective resistances, and a matrix version of the Chernoff Bound. 9-4 2.3 Pseudoinverses In our analysis, we will come across the need to “invert” a singular matrix. Since this is obviously not possible, we redefine our question to one that makes more sense. Let M be a n × n symmetric matrix. We can diagonalize M : n  λi vi viT M= i=1 n If all the eigenvalues are nonzero, then it obviously invertible, and M −1 = i=1 λ1i vi vit The case we worry about is when there is a zero eigenvalue. But this is okay too: when M is degenerate, we define the pseudoinverse by throwing away the zero eigenvalues and eigenvectors. In that case, we have  1 M+ = vi v T λi i i|λi =0 The pseudoinverse has many nice properties. Of these, we use: • ker(L) = ker(L+  • M M + = i|λi =0 vi viT = the projection onto the nonzero eigenvectors.  It is easy to see that M M + = I when restricted to the image of M . 2.4 Effective Resistance We mentioned earlier that Spectral Sparsification also samples edges with different probability. It turns out that the correct way to do this is to sample each edge with probability proportional to its “effective resistance.” The basic idea is to treat each edge as a resistor with resistance 1. If the edge had a capacity of c, we give it a resistance of 1/c. After calculating these values, we sample the edge (u, v) with probability proportional to the effective resistance between nodes u and v. Students may recall learning methods to solve circuits from their previous classes. For example, students may use a combination of Ohm’s law and Kirchoff’s law, as well as the rules for calculating effective resistances of resistors in series and parallel. To those who are comfortable with solving circuits, this may be a good way to think about the problem. However, the students who don’t like solving circuits are in luck too: now that we have the tools of Spectral Graph Theory, we can solve circuits with only linear algebra! In fact, we will combine our frequent use of the graph Laplacian with the pseudoinverse defined above. Let U be the edge-vertex adjacency matrix, C be the diagonal matrix with the various capacitances, and re = 1/ce . That is, we define U as in: ⎧ if v is the head of e ⎨ 1 −1 if v is the tail of e U (e, v) = ⎩ 0 otherwise Then, we have that L = U T CU . From ohm’s law, we have i = CU v for i ∈ RE , and v ∈ Rv . From the conservation of current, we have iext = U T i, for iext ∈ RV . Finally, we have iext = Lv, and v = L+ iext We define U (e, v) to be the adjacency matrix with ±1 values. Let ue be the eth row, and v = L+ ie xt. We have Ref f (e) = ue L+ uTe and as a result, Ref f (e) = (U L+ U T )e,e Thus, calculating the effective resistance of an edge is as simple as calculating the pseudoinverse of the Laplacian. Simple! 9-5 2.5 Error Bounds The last tool that we need to build is a way to define error bounds for matrices. In particular, we will use the following theorem. Theorem 7 For distributions on vectors y where y ≤ t and norm) then: q 1 T E Eyy − yi yiT 2 ≤ kt q i=1 Eyy t 2≤ 1 (where we are using the l2 log q q This is a “concentration of measure theorem, and we claim that it is similar to the Chernoff bound. Now, onto approximation. For our sparisifier H to approximate the original dense graph G, we want that 1−≤ xT LH x ≤1+ xT LG x for all vectors x. Rather, it is sufficient to show that z T M T LH M z ≤1+ z T M T LG M z 1−≤ for all vectors z, provided that x ⊥ (LG ) ⇒ x ∈ range(M ). Choose M so that M T LG M is a projection. Then, it suffices to show that M T LH M − M T LG M 2 ≤  T 1/2 From before, we have that LG = U T CU . Choose M = L+ . Then, we have GU C T 1/2 Π = M T LG M = C 1/2 U L+ = ΠΠ GU C Now, recall that LG = U T CU . If we let de be the weight of e in the sparsifier H, set Se,e = we can write LH = U T CSU = U T C 1/2 SC 1/2 U de ce . Then, yielding M T LH M = ΠSΠ We need to choose a diagonal S such that the number of nonzero elements of S is O(nlogn/2 ) With this choice, we have ΠSΠ − Π 2 ≤   Define πe as the eth column of Π: that is, πe = Π(·, e). Then, ΠSΠ = Se,e πe πeT , so πe 2 = Πe,e = ce Ref f (e) T 1/2 (this is because Π = Π2 = C 1/2 (U L+ ) G U )C We then set τe = Recall that n−1 ce Ref f (e) πe with  τe = √ n − 1. Choose edges with probability pe = ce Ref f (e) = e Then, we find that E[τe τeT ] =  c2 Ref f (e) . n−1 Πe,e = n − 1 e  pe τe τeT = e  πe πeT = Π e Sample q times with replacement, and set S(e, e) = Then, from the theorem above, we have 9-6 1 qce Ref f (e) × the number of times that e is chosen. E[ Π − ΠSΠ 2] √ ≤k n−1 logq ≤ /2 q for q = O(n log n/2 ). Thus, we see that our construction yields a spectral sparsifier as desired. From the algorithmics of the construction, it is easy to see that this is a poly-time procedure. The whole procedure is constructive, and uses the standard linear algebra operations. The bottleneck in this procedure comes from computing effective resistances, and in particular, the matrix inversions and multiplications. We claim that the procedure can be improved to nearly linear time. Doing so would involve two components: • Close to linear algorithms for solving linear equations of the form Lx = b for a laplacian L. • A way to compute all the effective resistances by solving logarithmically many linear systems. This uses the Johnson-Lindenstrauss Lemma. References [1] “Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs, ” A. Benczur, D. Karger, manuscript. 9-7