Lecture 6: Diameters and Eigenvalues, Expander Graphs

18.409 An Algorithmist’s Toolkit Lecture 6 Lecturer: Jonathan Kelner Topics • Diameters and their relationship to λ2 • Expanders • Butterfly networks 1 Diameters and Eigenvalues So far, every time we’ve dealt with eigenvalues, it’s had something to do with connectivity. For example, the spectral gap can be used to approximate the quality of cuts; it also describes how well a graph can mix under a random walk. They both are saying similar things: the eigenvalue is saying how connected a graph is. A walk will mix quickly if there’s a lot connected to everything else. The min-cut will likewise be large if there’s a lot of connectivity. For almost every reasonable property about a graph, there’s something you can write down regarding its relation to the second eigenvalue of the Laplacian. Today, we’re going to show the relation between λ2 and the diameter of a graph. Definition 1 The diameter, δ, is the longest, shortest path between any two vertices of a graph. In other words, we can define the distance between two vertices u and v in G as the shortest path connecting the two. The diameter of G is the largest distance between any two vertices in G. It’s not immediately clear why the diameter should be related to λ2 ; the following provides intuition1 : 1. Well-connected graphs have big λ2 2. Well-connected graphs have a small δ 3. So, graphs with big λ2 should have small δ Before proceeding, we’ll be making the following assumption: Assumption 2 G is a d-regular graph (this is for simplicity and not really a limiting assumption). We’ll also be utilizing lazy random walks in our investigation. As a reminder, Definition 3 A lazy random walk is simply a random walk along a graph with self loops added in: A 2d  M= Random Walk + I 2  (1) Self-loops where A is the graph’s adjacency matrix and I is the identity matrix. Since we’re using adjacency matrices, the interesting eigenvalues will be close to 1. So, let μ2 be the second largest eigenvalue of M and λ be the gap (i.e., λ = 1 − μ2 ). 1 Note, however, that this is not a proper syllogism 6-1 1.1 A First Bound Claim 4 For any G, ln(n) (2) λ where δ is the diameter of G, n is the number of vertices in the graph, and λ = 1 − μ2 , where μ2 is the second largest eigenvalue of the M associated with G. δ≤ Claim 4 means that λ, up to a logarithmic factor, really does provide a direct bound on the diameter of the graph. For most graphs, this isn’t very tight, but it’s a good place to start. So, why is it true? Proof We will use random walks to prove claim 4. Let u and v be vertices that are as far as possible from one another. Start a random walk at u and let pt (v) be the probability of a walk being at vertex v at time t. If pt (v) > 0, then δ ≤ t. Intuitively, this means that if we start at u and, after t time steps, there is some probability of ending up at v (the farthest vertex from u), then there must be a path of length t between the two. If there wasn’t, pt (v) would be 0. Recalling that the stationary distribution is π(v) = 1/n for regular graphs, we can equivalently state that if |pt (v) − π(v)| < n1 , then δ ≤ t. Why? Because if |pt (v) − π(v)| < n1 , then pt (v) > 0, implying δ ≤ t. Recall from our earlier lecture on random walks that  d(v ) t = (1 − λ)t |pt (v) − π(v)| < (1 − λ) miny d(y) Since G is regular, d(v) = d for all vertices (allowing the last equality above). We’ll now look at what happens when we set t = lnλn :  ln n ln n 1 1 = (1 − λ)t = (1 − λ) λ < e n With the inequality coming from the fact that (1 − λ)1/λ < |pt (v) − π(v)| < n1 , and therefore, δ ≤ t = lnλn . 1.2 1 e for all λ > 0. Thus, for t = ln n λ , we have that A better bound As stated earlier, bounding δ by n1 is not that great. So, can we do better? Yes. And we do so by using an important trick that frequently comes up. First, note that if the (u, v)th entry of Ak is non-zero, then there’s a path of at most length k from u to v. Replacing A with M doesn’t change this (it just makes the non-zero entries smaller). If eu and ev are basis vectors, then |pk (v) − π(v)| = |eTv M k eu − 1 1 |< n n which would imply δ ≤ k. Let’s then let p(x) be a polynomial of degree k: k cj xj p(x) = j=1 Note that we can also interpret M as a variable and apply p to it as follows: k cj M j p(M ) = j=1 If p(M ) has no zero entries, then δ ≤ k. Why? Because all non-zero elements of M indicate all vertices that can be reached in one step, M 2 is all vertices that can be reached in two steps, and so on. Thus, 6-2 for any non-zero entry (u, v) in p(M ), there must have been a non-zero element in M j for 0 < j ≤ k, implying the existence of a path from u to v of at most length k. If this is true for all entries in p(M ), then a path of at most length k exists from any vertex to any other vertex, which means the diameter is at most k.2 Claim 5 Suppose p has degree k, p(1) = 1, and |p(μi )| < 1 n for all i ≥ 2, then δ≤k (3) Proof For this proof, it is sufficient to show that every entry in p(M ) is non-zero. First, recall that we can write down any matrix, M , as the following: μi vi viT M= i where μi and vi are the i-th eigenvalue and eigenvector, respectively. Since Mk = μki vi viT i we can write k cj M j = p(M ) = j=0 ⎛ k μji vi viT cj j=0 ⎝ = i i = eTa cj μji ⎠ vi viT p(μi )vi viT = j=0 Therefore, we can write the (a, b)th entry of p(M ) as follows  eTa p(M )eb ⎞ k i  p(μi )vi viT eb i p(μi )(eTa vi )(viT eb ) = i = p(μi )vi (a)vi (b) i n = ≥ 1 + p(μi )vi (a)vi (b) n i=2   n  1   − p(μi )vi (a)vi (b)  n  i=2 n ≥ 1 − |p(μi )| |vi (a)| |vi (b)| n i=2 ≥ 1 − max |p(μi )| |vi (a)| |vi (b)| i≥2 n i=2 n 1 − max |p(μi )| i≥2 n > 0  Where the penultimate step follows from i |vi (a)| |vi (b)| ≤ 1. Let V be the matrix where rows are the eigenvectors vi ’s. Then V · V T = I by the orthonormal condition. It follows that V T · V = I and the columns ≥ 2 Note that we’re not saying anything about δ if p(M ) has zero entries. Since there are no restrictions on c , it’s possible j that the summation produces a zero entry for p(M ) where for all positive cj a non-zero entry would have existed. 6-3  n  n n 2 2 2 ≤ 1. The of V form an orthonormal basis. Hence ( i=2 |vi (a)||vi (b)|) ≤ i=2 |vi (a)| i=2 |vi (b)| ultimate step follows from our assumption that |p(μi )| < n1 for all i ≥ 2. Thus, if p(1) = 1 and |p(μi )| < n1 for all i ≥ 2, we have that every entry in p(M ) is non-zero, implying that δ ≤ k. (t) Claim 6 For any t ∈ (0, 1), I assert the existence of a magic polynomial, pk , with the following properties: (t) 1. pk is of degree k (t) 2. pk (1) = 1   √ −k   (t)  for any x ∈ [0, 1 − t] 3. pk (x) ≤ 2 1 + 2t We will provide no proof for this claim here, but the polynomials are derived from Chebyshev polynomials, and we’ll use them again later. To provide some intuition, figure 1 shows graphs of these polynomials for k = 10 with varying t. Notice that to keep the same bound for smaller values of t, a larger k is required due to the “oscillations” that the polynomial must take on in order to achieve p(1) = 1 while keeping p(x) small for x ∈ [0, 1 − t]. 1 1 1 0.8 0.8 0.8 0.6 0.6 0.6 0.4 0.4 0.4 0.2 0.2 0.2 0 0 0 −0.2 −0.2 −0.2 −0.4 −0.4 −0.4 −0.6 −0.6 −0.6 −0.8 −0.8 −1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 −1 1 (a) −0.8 0 0.1 0.2 0.3 0.4 0.5 0.6 (b) 0.7 0.8 0.9 −1 0.99 1 0.991 0.992 0.993 0.994 0.995 0.996 0.997 0.998 0.999 1 (c) Figure 1: (a) t = 0.1 (b) t = 0.001 (c) t = 0.001 zoomed in for x from 0.99 to 1 If we set t = λ, we get a degree k polynomial, p, such that 1. p(1) = 1  √ −k for any x ∈ [0, μ2 ]. 2. |p(x)| ≤ 2 1 + 2λ   Additionally, if we set k = 1 + √12λ ln (2n), then it is possible to show that p(x) < which gives the following bound:   1 √ δ ≤ 1+ ln (2n) 2λ 1 n for all x ∈ [0, μ2 ], (4) This is much better than our previous bound of δ ≤ ln(n) λ . So, strangely, by putting in a particular √ polynomial, we get a bound that grows with 1/ λ as opposed to just 1/λ. This foreshadows our next unit on iterative linear algebra. 1.3 Example Application Suppose that you have a symmetric matrix M and want the eigenvector associated with the largest eigenvalue. For purposes of this example, let them be normalized such that the largest eigenvalue is 1. Then an easy way to get an approximate answer for the eigenvector is to compute M k x for a large k and a random x. 6-4 Why does this give the eigenvector associated with μ1 = 1? If all other eigenvalues are less than 1, then for a large enough k, they will diminish in importance, until all that is left is v1 . This is a very intuitive and natural algorithm that takes about 1/λ steps to get close. But we just found a much faster algorithm! Assuming that we know some good bound on λ (if we don’t, (λ) we could easily search for it), we can compute pk (M )x instead of M k x to get the dominant eigenvector. This method converges much faster, and we’ll get into this more in a few lectures. 2 Expanders If you had to know one set of graphs in your life, these are the ones to know. They often are a counterexample to many long-standing conjectures. Also, they turn up literally everywhere. If you didn’t know any better, you would think that they don’t exist from the described properties. But they’re almost every single graph. Specifically, we’ll be looking at families of d-regular graphs (Gn )n as n goes to infinity: Definition 7 (Gn )n is an expander family if λ2 (Gn ) ≥ c for some constant c and for all n. Most of the graphs we’ve looked at are not expanders. For example, path graphs have λ2 ≤ O(1/n2 ) and binary trees have λ2 ≤ O(1/n). This means that λ2 very quickly goes to zero as n → ∞ for both cases. Expanders don’t have this property. Even as n → ∞, λ2 stays above a constant. Given this, it’s not clear that they should exist. Note: We should think of d as a constant. In other words, we’ll pick a d and study expanders in that family. 2.1 Relating Expanders to Cuts The first thing we’ll look at is Cheeger’s inequality for expanders. Recall that λ2 ≤ φ(G) 2 For expanders, this implies c ≤ φ(G) 2 What does this mean? It means that any set, S, of vertices with |S| ≤ n/2 has at least (c/2)|S| edges leaving it. This is a strong property: for expanders, there are no small cuts that can be made in the graph. Every cut that balances the sizes of the sets of vertices cuts a constant fraction of the edges in the graph. The other side of Cheeger’s inequality says Θ(1) φ(G)2 ≤ λ2 d Again, for expanders, this can be rewritten.  φ(G) ≤ cd 2Θ(1) Since d is a constant, this says that the isoperimetry, φ, is also bounded above by a constant. Nor­ mally, there’s a large gap between the upper-bound and lower-bounds in Cheeger’s inequality. Here we’ve sandwiched φ between two constants. Therefore, an equivalent definition of expanders is as follows: Definition 8 (Gn )n is expander family if φ(G) ≥ c for some constant c and all n. 6-5 2.2 Do Expanders Exist? A natural question is if expanders exist, what are the required parameters of the graphs? It turns out that random graphs are expanders, and so, almost all graphs are expanders. But, there’s a limit as to how “good” of an expander you can have: Claim 9 For any G, √ λ2 ≤ d − 2 d − 1 + o(1) (5) In other words, even though λ2 is always larger than a constant, there’s a limit as to how well-connected it can be. √ We won’t prove this. But this is not that strong a bound. We already know that λ2 ≤ d. This is just O( d) smaller. Furthermore, this bound is tight since Ramanujan graphs meet it. So that’s the limit of what an expander can be. 2.3 Expanders and Randomness Expanders are all over the study of randomness, but we’ll just study one interesting property. We’ll use μ2 = d − λ2 to simplify formulas, where now, μ2 is the second largest eigenvalue of the adjacency matrix. Suppose you make a graph by randomly including each edge with probability d/n. In other words, construct a graph such that each vertex has an expected number of d edges leaving it. Since the total number of possible edges is |S||T | and there’s a d/n probability of having each edge, the expected number of edges between any two sets S and T will be d|Sn||T | . Claim 10 Expander Mixing Lemma: If you choose any two vertex sets, S and T , the difference in the total number of edges between the two and the expected number for a random graph is bounded. Formally,          e(S, T ) − d|S||T |  ≤ μ2 |S|S¯|T |T¯  n  n      ≤ μ2 min(|S|, S¯) · min(|T |, T¯) This is surprising because there is no randomness here. This is just a property associated with expanders, but it behaves similarly to random graphs. Proof Let α and β be the fraction of total vertices that are in the sets S and T : |S| = αn |T | = βn. Let x and y be the characteristic vectors of S and T , respectively. Definition 11 A characteristic vector, x, of a set S is a vector of length n that has xi = 1 if vi ∈ S, and xi = 0 otherwise. We can now write the number of edges between sets S and T as e(S, T ) = xT Ay. Now, as you’ve probably noticed, it’s beneficial to use vectors that are perpendicular to the all-ones vector, 1. So, we’ll rewrite x and y as v = x − α1 w = y − β1. Clearly, v · 1 = w · 1 = 0, implying orthogonality. Rewriting the number of edges between sets S and T , we get e(S, T ) = xT Ay = (v + α1)T A(w + β1) = v T Aw + v T Aβ1 + α1T Aw + α1T Aβ1. 6-6 Using the following identities, A1 = d1 1T A = d1T , we get = v T Aw + βv T A1 + α1T Aw + αβ1T A1 e(S, T ) = v T Aw + βv T d1 + αd1T w + αβd1T 1 = v T Aw + αβdn, where we have used the orthogonality of v and w with 1 (i.e., v T 1 = 0) to cancel out the middle two terms. We now have the following bound:   |e(S, T ) − αβdn| = v T Aw ≤ |v||Aw| ≤ |v|μ2 |w| μ2  (αn) ((1 − α)n) (βn) ((1 − β)n) = n     μ2 |S|S¯|T |T¯, = n where the third line follows from the fact that w is orthogonal to 1, and  thus, μ2 is the largest eigenvalue that can affect w, and the fourth line follows from the fact that |v | = nα(1 − α). To see this, note that |v| = |x − α1|    = |S |(1 − α)2 + S¯(−α)2  = αn(1 − α)2 + (1 − α)nα2  αn(1 − α)(1 − α + α) =  = αn(1 − α), and the same steps show that |w| = 2.4  nβ(1 − β). Thus, we have shown that |e(S, T ) − αβdn| ≤ μ2 n      |S|S¯|T |T¯. Some Properties We Now Know • Random walks on expanders mix in a logarithmic number of steps • Expanders have logarithmic diameter • Expanders have a constant isoperimetric number 2.5 Vertex Expansion We’ve discussed cutting a graph and looking at the number of edges cut. An equivalent way of thinking about a cut is to select a set of vertices and then count the number of edges with one vertex in the set and one out. Another useful metric can be obtained by counting the number of vertices that are neighbors of a set. In other words, for a set of vertices, X, let N (X), be the set of vertices, Y , such that (x, y) ∈ E such that x ∈ X and y ∈ X̄. Claim 12 N (X) ≥ d2 |X| μ2 + (d2 − μ2 )|X|/n 6-7 We don’t prove this, but the high level idea is the following: • Select a set of vertices from G. Call this set X. • Let Y be the set of vertices that are neither in X nor in N (X). In other words, Y = V \(N (X) ∪ X). • Now, by construction, we have that e(X, Y ) = 0. Algebra gets a little messy, but you can just plug the above into the expander mixing lemma to show √ this bound. It turns out also that for X/n small and μ = 2 d − 1, we can achieve N (X) ≥ d |X|. 4 Why is this interesting? What this is saying is that for any set X, there are at least d/4 neighbors not in X. Since each vertex has d neighbors total, this bound is quite strong. It turns out that this is about as good as you can get with spectral graph theory. To see this, we will generalize the vertex expansion as follows. We want to show bounds of the form |N (S)| ≥ γ|S|. In other words, we want to say that the vertex expansion of G is greater than or equal to γ for any S. Sometimes we’ll only care about expansions of smaller sets (e.g., for |S| ≤ 0.01n). Definition 13 G is an (α, β)-expander if for αβ < 1 and all sets S with |S| ≤ αn have |N (S)| ≥ β|S|. We showed that Ramanujan graphs are (α, d/4) expanders for some constant α. Some applications need expansion greater than d/2 but with small (constant) α. These exist, but we can’t prove better than d/2 with spectral techniques.3 2.6 Bipartite Expanders Many of the applications of expanders use bipartite expanders. These are just expanders that are bipartite graphs. It is easier to show that these exists (it will be a homework problem!). Definition 14 A d-regular bipartite graph is an (α, β)-expander if every set S on the left with |S| ≤ αn has N (S) ≥ β|S|. Whenever αβ < 1, there exists some d such that almost all d-regular graphs on n nodes (for n sufficiently large), are (α, β)-expanders. 3 It turns out that random graphs work here. In 2002, Capalbo, Reingold, Vadhan, and Wigderson gave an explicit construc­ tion technique with expansion d − o(1). 6-8