Papers to credit for spectral partitioning of graphs

Question

If $G=(V,E)$ is an undirected $d$-regular graph and $S$ is a subset of the vertices of cardinality $\leq |V|/2$, call the edge expansion of $S$ the quantity

$\phi(S) := \frac {Edges(S,V-S)}{d\cdot |S|\cdot |V-S|}$

Where $Edges(A,B)$ is the number of edges with one endpoint in $A$ and one endpoint in $B$. Then the Edge Expansion problem is to find a set $S$ with $|S|\leq |V|/2$ that minimizes $\phi(S)$. Call $\phi(G)$ the expansion of an optimal set.

The Spectral Partitioning Algorithm for the Edge Expansion problem works by finding an eigenvector $x$ of the second largest eigenvalue of $A$, the adjacency matrix of $G$, and then considering all the ``threshold sets'' $S$ of the form $\{ v : x(v) \leq t \}$ over all thresholds $t$. If we let $\lambda_2$ be the second largest eigenvalue of the matrix $\frac 1d \cdot A$, then the analysis of the Spectral Partitioning Algorithm shows that the best threshold set $S_{SP}$ found by the algorithm satisfies

$\phi(S_{SP}) \leq 2\sqrt {\phi(G)}$

Which follows from the Cheeger's Inequalities

$\phi(S_{SP}) \leq \sqrt{2\cdot (1-\lambda_2)}$

and

$1-\lambda_2 \leq 2 \phi(G)$

What is the first paper to make such a claim? What papers are to credit for the ideas? Here is what I have got:

• N. Alon and V.D. Milman. $\lambda_1$, isoperimetric inequalities for graphs, and superconcentrators, Journal of Combinatorial Theory, Series B, 1985, 38(1):73-88

  Prove a result in the spirit of the "simple" Cheeger inequality $1-\lambda_2 \leq 2\phi(G)$, but for vertex expansion instead of edge expansion. Recognize that the relation between edge expansion and eigenvalues is the discrete version of a problem studied by Cheeger in

  J. Cheeger. A lower bound for the smallest eigenvalue of the Laplacian. Problems in Analysis, 1970.

• N. Alon. Eigenvalues and expanders. Combinatorica. 6(2):83-96, 1986.

  Proves a result in the spirit of the difficult Cheeger inequality $\phi(S_{SP}) \leq \sqrt{2\cdot (1-\lambda_2)}$ but for vertex expansion instead of edge expansion.

• A. Sinclair, M. Jerrum. Approximate counting, uniform generation, and rapidly mixing Markov chains. Information and Computation 82:93-133, 1989 (Conference version 1987)

  Prove the Cheeger inequalities as stated above. (Their paper studies _conductance_ of time-reversible Markov chains, which happens to equal _edge expansion_ in regular graphs.) They credit the work of Alon and Milman and of Alon for the techniques. They also credit Aldous for a related bound between mixing time and edge expansion in regular graphs.

• M Mihail. Conductance and convergence of Markov chains-a combinatorial treatment of expanders. FOCS 1989, pages 526-531

  While the main point of the paper is that its techniques apply to non-time-reversible Markov chains, when it is applied to regular undirected graphs it has an advantage over previous work: it shows that if one runs the spectral partitionig algorithm with an arbitrary vector, one still obtains the inequality $\phi(S_{SP}) \leq \sqrt{2\cdot (1-\lambda')}$ where $\lambda'$ is the Rayleigh quotient of the vector. The arguments of Alon, Milman, Sinclair and Jerrum require an actual eigenvector. This is relevant to fast spectral partitioning algorithms that use approximate eigenvectors.

Are there other papers that should be credited in terms of proof techniques?

When is the algorithmic significance of the above results, as graph partitioning algorithms, first recognized? The above papers have no such discussion.

Answer 1

It seems that the first paper introducing this set of ideas (using the algebraic invariant $\lambda_2$, the second smallest eigenvalue of the graph Laplacian, to bound various properties of the graph) to graph theory was Fiedler's "Algebraic Connectivity of Graphs" in Czechoslovak Mathematical Journal. It appeared in 1973, roughly at the same time as the Cheeger's paper (1970), which dealt with manifolds. I am not sure who was the first to observe the parallel between graphs and manifolds in that respect. $\lambda_2$ is sometimes called the Fiedler number.

Interestingly, there is a remark at the end of the Fiedler's paper, pointing out an independent technical report by Anderson and Morley titled Eigenvalues of the Laplacian on a Graph from 1971, which apparently had similar ideas. However, it the paper by Anderson and Morley with the same title appeared in Linear and Multilinear Algebra only in 1985.

Answer 2

Some additional references I remember of that era:

1) Diaconis and Stroock, Geometric bounds for eigenvalues of Markov chains, The Annals of Applied Probability, 1991; but I remember getting my hands on a preprint sometime in 1990. This paper in turn refers to

2) Dodziuk, Difference equations, isoperimetric inequality and transience of certain random walks,Transactions of the American Mathematical Society, 1984.

Also, an important "algorithmic companion" paper to Sinclair and Jerrum at that time was

3) Dyer Frieze Kannan, A Random Polynomial Time Algorithm for Approximating the Volume of Convex Bodies, STOC 89. Of course, the results here were built on top of SJ.