You are currently browsing the tag archive for the ‘Expanders’ tag.
Readers of in theory have heard about Cheeger’s inequality a lot. It is a relation between the edge expansion (or, in graphs that are not regular, the conductance) of a graph and the second smallest eigenvalue of its Laplacian (a normalized version of the adjacency matrix). The inequality gives a worst-case analysis of the “sweep” algorithm for finding sparse cuts, it shows a necessary and sufficient for a graph to be an expander, and it relates the mixing time of a graph to its conductance.
Readers who have heard this story before will recall that a version of this result for vertex expansion was first proved by Alon and Milman, and the result for edge expansion appeared in a paper of Dodzuik, all from the mid-1980s. The result, however, is not called Cheeger’s inequality just because of Stigler’s rule: Cheeger proved in the 1970s a very related result on manifolds, of which the result on graphs is the discrete analog.
So, what is the actual Cheeger’s inequality?
Theorem 1 (Cheeger’s inequality) Let be an -dimensional smooth, compact, Riemann manifold without boundary with metric , let be the Laplace-Beltrami operator on , let be the eigenvalues of , and define the Cheeger constant of to be
where the is the boundary of , is the -dimensional measure, and is -th dimensional measure defined using . Then
The purpose of this post is to describe to the reader who knows nothing about differential geometry and who does not remember much multivariate calculus (that is, the reader who is in the position I was in a few weeks ago) what the above statement means, to describe the proof, and to see that it is in fact the same proof as the proof of the statement about graphs.
In this post we will define the terms appearing in the above theorem, and see their relation with analogous notions in graphs. In the next post we will see the proof.
Long in the planning, my online course on graph partitioning algorithms, expanders, and random walks, will start next month.
The course page is up for people to sign up. A friend of mine has compared my camera presence to Sheldon Cooper’s in “Fun with Flags,” which is sadly apt, but hopefully the material will speak for itself.
Meanwhile, I will be posting about some material that I have finally understood for the first time: the analysis of the Arora-Rao-Vazirani approximation algorithm, the Cheeger inequality in manifolds, and the use of the Selberg “3/16 theorem” to analyze expander constructions.
If you are not a fan of recorded performances, there will be a live show in Princeton at the end of June.
Now that the Winter break is coming, what to read in between decorating, cooking, eating, drinking and being merry?
The most exciting theoretical computer science development of the year was the improved efficiency of matrix multiplication by Stother and Vassilevska-Williams. Virginia’s 72-page write-up will certainly keep many people occupied.
Terence Tao is teaching a class on expanders, and posting the lecture notes, of exceptional high quality. It is hard to imagine something that would a more awesome combination, to me, than Terry Tao writing about expanders. Maybe a biopic on Turing’s life, starring Joseph Gordon-Levitt, written by Dustin Lance Black and directed by Clint Eastwood.
Now that I have done my part, you do yours. If I wanted to read a couple of books (no math, no theory) during the winter, what would you recommend. Don’t recommend what you think I would like, recommend what you like best, and why.
In which we prove properties of expander graphs.
In which we define and analyze the zig-zag graph product.
In which we give an explicit construction of expander graphs of polylogarithmic degree, state the properties of the zig-zag product of graphs, and provide an explicit construction of a family of constant-degree expanders using the zig-zag product and the polylogarithmic-degree construction.
A family of expanders is a family of graphs , , such that each graph is -regular, and the edge-expansion of each graph is at least , for an absolute constant independent of . Ideally, we would like to have such a construction for each , although it is usually enough for most applications that, for some constant and every , there is an for which the construction applies in the interval , or even the interval . We would also like the degree to be slowly growing in and, ideally, to be bounded above by an explicit constant. Today we will see a simple construction in which and a more complicated one in which .
An explicit construction of a family of expanders is a construction in which is “efficiently computable” given . The weakest sense in which a construction is said to be explicit is when, given , the (adjacency matrix of the) graph can be constructed in time polynomial in . A stronger requirement, which is necessary for several applications, is that given and , the list of neighbors of the -th vertex of can be computed in time polynomial in .
In many explicit constructions of constant-degree expanders, the construction is extremely simple, and besides satisfying the stricter definition of “explicit” above, it is also such that the adjacency list of a vertex is given by a “closed-form formula.” The analysis of such constructions, however, usually requires very sophisticated mathematical tools.
Example 1 Let be a prime, and define the graph in which , and, for , the vertex is connected to , to and to its multiplicative inverse . The vertex is connected to , to , and has a self-loop. Counting self-loops, the graph is 3-regular: it is the union of a cycle over and of a matching over the vertices ; the vertices , , have a self-loop each. There is a constant such that, for each , the graph has edge expansion at least . Unfortunately, no elementary proof of this fact is known. The graph is shown in the picture below.
Constructions based on the zig-zag graph product, which we shall see next, are more complicated to describe, but much simpler to analyze.
We begin by describing a building block in the construction, which is also an independently interesting construction: a family of expanders with polylogarithmic degree, which have both a very simple description and a very simple analysis.
In which we prove the easy case of Cheeger’s inequality.
1. Expansion and The Second Eigenvalue
Let be an undirected -regular graph, its adjacency matrix, its normalized adjacency matrix, and be the eigenvalues of .
Recall that we defined the edge expansion of a cut of the vertices of as
and that the edge expansion of is .
We also defined the related notion of the sparsity of a cut as
and ; the sparsest cut problem is to find a cut of minimal sparsity.
Recall also that in the last lecture we proved that if and only if is disconnected. This is equivalent to saying that if and only if . In this lecture and the next we will see that this statement admits an approximate version that, qualitatively, says that is small if and only if is small. Quantitatively, we have
Theorem 1 (Cheeger’s Inequalities)
In which we describe what this course is about.
This class is about the following topics:
- Approximation algorithms for graph partitioning problems. We will study approximation algorithms for the sparsest cut problem, in which one wants to find a cut (a partition into two sets) of the vertex set of a given graph so that a minimal number of edges cross the cut compared to the number of pairs of vertices that are disconnected by the removal of such edges.
This problem is related to estimating the edge expansion of a graph and to find balanced separators, that is, ways to disconnect a constant fraction of the pairs of vertices in a graph after removing a minimal number of edges.
Finding balanced separators and sparse cuts arises in clustering problems, in which the presence of an edge denotes a relation of similarity, and one wants to partition vertices into few clusters so that, for the most part, vertices in the same cluster are similar and vertices in different clusters are not. For example, sparse cut approximation algorithms are used for image segmentation, by reducing the image segmentation problem to a graph clustering problem in which the vertices are the pixels of the image and the (weights of the) edges represent similarities between nearby pixels.
Balanced separators are also useful in the design of divide-and-conquer algorithms for graph problems, in which one finds a small set of edges that disconnects the graph, recursively solves the problem on the connected components, and then patches the partial solutions and the edges of the cut, via either exact methods (usually dynamic programming) or approximate heuristic. The sparsity of the cut determines the running time of the exact algorithms and the quality of approximation of the heuristic ones.
We will study three approximation algorithms:
- The Spectral Partitioning Algorithm, based on linear algebra;
- The Leighton-Rao Algorithm, based on a linear programming relaxation;
- The Arora-Rao-Vazirani Algorithm, based on a semidefinite programming relaxation.
The three approaches are related, because the continuous optimization problem that underlies the Spectral Partitioning algorithm is a relaxation of the ARV semidefinite programming relaxation, and so is the Leighton-Rao relaxation. Rounding the Leighton-Rao and the Arora-Rao-Vazirani relaxations raise interesting problems in metric geometry, some of which are still open.
There are two families of approaches to the explicit (efficient) construction of bounded-degree expanders. One is via algebraic constructions, typically ones in which the expander is constructed as a Cayley graph of a finite group. Usually these constructions are easy to describe but rather difficult to analyze. The study of such expanders, and of the related group properties, has become a very active research program, involving mostly ergodic theorists and number theorists. There are also combinatorial constructions, which are somewhat more complicated to describe but considerably simpler to analyze.
The design of approximation algorithms for combinatorial counting problems, in which one wants to count the number of solutions to a given NP-type problem, can be reduced to the design of approximately uniform sampling in which one wants to approximately sample from the set of such solutions. For example, the task of approximately counting the number of perfect matchings can be reduced to the task of sampling almost uniformly from the set of perfect matchings of a given graph. One can design approximate sampling algorithms by starting from an arbitrary solution and then making a series of random local changes. The behavior of the algorithm then corresponds to performing a random walk in the graph that has a vertex for every possible solution and an edge for each local change that the algorithm can choose to make. Although the graph can have an exponential number of vertices in the size of the problem that we want to solve, it is possible for the approximate sampling algorithm to run in polynomial time, provided that a random walk in the graph converges to uniform in time poly-logarithmic in its size.
The study of the mixing time of random walks in graphs is thus a main analysis tool to bound the running time of approximate sampling algorithms (and, via reductions, of approximate counting algorithms).
These three research programs are pursued by largely disjoint communities, but share the same mathematical core.
In June, I wrote about my work on using spectral partitioning to approximate Max Cut.
I have now posted a revised paper with a couple new things.
One is an improved analysis due to Moses Charikar, of the algorithm described in the June paper. Moses shows that if one starts from a graph in which the optimum cuts a fraction of edges, then the algorithm cuts at least a fraction of edges (and also at least half of the edges). Cutting more than a fraction of edges is Unique-Games-hard. Optimizing the fraction
we see that the approximation ratio of the algorithm is always at least .
The second new result answers a question raised by an anonymous commenter in June: what about Max Cut Gain? Read the rest of this entry »