# Partitioning into Expanders

arXiv: https://arxiv.org/abs/1309.3223 · HTML: https://mlsanity.com/paper/1309.3223/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Sep 2013.

## Built on by (most cited first, 7 of 7)

- [A Tighter Analysis of Spectral Clustering, and Beyond](https://mlsanity.com/paper/2208.01724/) (2022)
- [Hierarchical Clustering: O(1)-Approximation for Well-Clustered Graphs](https://mlsanity.com/paper/2112.09055/) (2021)
- [Nearly-Optimal Hierarchical Clustering for Well-Clustered Graphs](https://mlsanity.com/paper/2306.09950/) (2023)
- [An Information-theoretic Perspective of Hierarchical Clustering](https://mlsanity.com/paper/2108.06036/) (2021)
- [Sublinear-Time Clustering Oracle for Signed Graphs](https://mlsanity.com/paper/2206.13813/) (2022)
- [A Differentially Private Clustering Algorithm for Well-Clustered Graphs](https://mlsanity.com/paper/2403.14332/) (2024)
- [Offline Local Search for Online Stochastic Bandits](https://mlsanity.com/paper/2604.09423/) (2026)

## Abstract (arXiv)

Let G=(V,E) be an undirected graph, lambdak be the k-th smallest eigenvalue of the normalized laplacian matrix of G. There is a basic fact in algebraic graph theory that lambdak > 0 if and only if G has at most k-1 connected components. We prove a robust version of this fact. If lambdak>0, then for some 1≤ ℓ≤ k-1, V can be em partitioned into l sets P1,ldots,Pl such that each Pi is a low-conductance set in G and induces a high conductance induced subgraph. In particular, φ(Pi)=O(l3√λl) and φ(G[Pi]) >= λk/k2). We make our results algorithmic by designing a simple polynomial time spectral algorithm to find such partitioning of G with a quadratic loss in the inside conductance of Pi's. Unlike the recent results on higher order Cheeger's inequality [LOT12,LRTV12], our algorithmic results do not use higher order eigenfunctions of G. If there is a sufficiently large gap between lambdak and lambdak+1, more precisely, if λk+1 >= poly(k) lambdak1/4 then our algorithm finds a k partitioning of V into sets P1,...,Pk such that the induced subgraph G[Pi] has a significantly larger conductance than the conductance of Pi in G. Such a partitioning may represent the best k clustering of G. Our algorithm is a simple local search that only uses the Spectral Partitioning algorithm as a subroutine. We expect to see further applications of this simple algorithm in clustering applications.