There are at least three contexts where this result arises and is important:
- Explicit construction of expander graphs. The expansion of a graph is a parameter that is NP-hard to compute. A general rule of thumb in mathematics is that if a parameter is hard to compute, then it is also hard to reason about it and to prove bounds for it on specific objects. In order to prove such bounds, one needs an easily computable approximation; then one proves bounds on the parameter of interest by proving bounds for the approximating parameter. (This intuition is the point of departure for the notion of natural proofs.) Cheeger’s inequality shows that the eigenvalue gap, which is a polynomial time computable parameter of graphs, gives a reasonably good approximation of expansion. This is extremely useful because the expansion of most explicitly constructed families of expander graphs is proved by proving bounds on the eigenvalue gap first. Alon was the first to state this equivalence between expansion and eigenvalue gap, though he worked with vertex expansion while in this post we discuss edge expansion. (The two parameters are related in bounded-degree graphs.)
- Analysis of randomized algorithms. Many approximate counting problems are solved by polynomial time randomized algorithms that work by reducing the counting problem to a sampling problem.
To see a simple example of how it works, consider the problem of approximately counting the number of perfect matchings in a given bipartite graph, and suppose we have an algorithm that given a bipartite graph is able to sample from the uniform distribution over all perfect matchings in the graph. Now, we can focus on an edge and be able to approximate the fraction of perfect matchings that contain (by sampling many matchings and seeing what fraction in our sample contains ). Say we have good confidence that about of the perfect matchings contain . Then we can remove the vertices from the graph, recursively approximate count the number of perfect matchings in the residual graph, and finally multiply the result by . (It should be clear how this generalizes to an approximate counting algorithm. Note that we could also have removed the edge , recursively computed the number of perfect matchings in the residual graph, and multiplied the result by 3. In general, if our estimate for the number of perfect matchings containing is , we recur on the graph in which the vertices are removed and then multiply by if , and otherwise recur on the graph in which the edge is removed, and then multiply by . Also it should be clear that is enough to sample from an approximately uniform distribution of perfect matchings.)
Now, here is an idea on how to approximately sample from the set of perfect matchings: define the (possibly) exponentially big graph that has one vertex for every perfect matching, and an edge between two matchings if one can be transformed into the other by a simple “local” operation; also assume that the local change is efficiently computable, and that the resulting graph is regular. We can then start at an arbitrary vertex of this big graph and perform a random walk. After a number of steps that depends on the eigenvalue gap of the big graph, we will have reached a nearly uniformly distributed matching.
This means that the task of designing an approximate counting algorithm for the number of perfect matchings reduces to defining an appropriate graph of matchings and to be able to bound its eigenvalue gap. Surprisingly, in such a case it is easier to first bound the edge expansion of the big graph, and then to use Cheeger’s inequality to derive a bound on the eigenvalue gap. This approach of reducing approximate counting to approximate sampling, of solving approximate sampling via a random walk in an exponentially big graph, and of bounding the length of the required random walk via a bound on the edge expansion, are due to Sinclair and Jerrum, who also provided a proof of Cheeger’s inequality (some of their results were found independently by Lawler and Sokal around the same time).
But does this contradict our intuition that NP-hard parameters cannot be bounded directly? No, because Sinclair and Jerrum estimate edge expansion via the canonical path method, which is equivalent to providing a lower bound to edge expansion by giving a dual solution to the Leighton-Rao linear programming relaxation of edge expansion (or, in their language, uniform sparsest cut). I will talk more about Leighton-Rao later, but the point for now is that Sinclair and Jerrum lower bound the eigenvalue gap (which is a computable but sometimes difficult-to-understand parameter) via the edge expansion (which is a hard-to-compute parameter) and finally lower bound the edge expansion by constructing a clean combinatorial object that, as it happens, lower bounds a computable parameter (the linear programming optimum of the Leighton-Rao relaxation).
- Graph Partitioning. There are a number of applications, such as image segmentation and the implementation of divide-and-conquer heuristics, where one wants to partition the vertices of a graph into two subsets that are as balanced as possible and such that the partition is crossed by as few edges as possible. A good balance between these two conditions is given by the partition that realizes the edge expansion, that is the partition , , such that the ratio is minimized. As mentioned, finding such a partition is NP-hard, but the constructive way in which Cheeger’s inequality is proved implies that given the eigenvector of the second eigenvalue of the graph one can find an approximately good partition; this algorithm is known as the spectral partitioning algorithm, and it is known to work well in practice. My colleague Jitendra Malik and his then-student Jianbo Shi demonstrated that it is very effective for image segmentation.
The most useful applications of Cheeger’s inequality is its “difficult” direction, in which one shows, algorithmically, that a small eigenvalue gap implies poor edge expansion, that is, the existence of a partition that defines a sparse cut. This is the direction used in (2) and (3) above, though only (3) requires an algorithmic proof.
But I also find the other direction, that a large eigenvalue gap implies good edge expansion, to be impressive. A lower bound on edge expansion is a “coNP-type” statement, something that has to be true for every partition of the vertices in the graph. A polynomial size object, however, can give a certificate that such a lower bound holds. (The object being a basis of eigenvectors.)
Usually, there is just one technique that allows to reduce “coNP-type” statement with a universal quantification to the construction of one polynomial-size object, namely, “duality” results in convex programming. One can, in fact, describe a semidefinite programming relaxation of the edge expansion problem such that the lower bound to edge expansion given by the eigenvalue gap is also a feasible solution for the dual of the relaxation. Similarly, as we said, lower bounds for edge expansion based on the “canonical path” method are feasible dual solutions of the Leighton-Rao linear programming relaxation of edge expansion. The Arora-Rao-Vazirani semidefinite programming relaxation of edge expansion is at least as strong as the one that gives the spectral bound and at least as strong as Leighton-Rao, so feasible solutions for its dual are the most general known “certificates of expansion” for graphs.
In a forthcoming post, I shall explain the proof of the “easy direction” of Cheeger’s inequality by thinking of the eigenvalue gap as a convex programming relaxation of edge expansion, and I shall show how to compare this relaxation with Leighton-Rao and with Arora-Rao-Vazirani.
And, hopefully, I shall then post a proof of the “difficult direction” of Cheeger’s inequality, that is, the analysis of the spectral partitioning algorithm, and compare it with the algorithm of Leighton and Rao. I will then postpone a discussion of the algorithmic part of Arora-Rao-Vazirani to the indefinite future.