Approximating the Expansion Profile and Almost Optimal Local Graph Clustering

Understand

Spectral partitioning is a simple, nearly-linear time, algorithm to find sparse cuts, and the Cheeger inequalities provide a worst-case guarantee for the quality of the approximation found by the algorithm.

• Local graph partitioning algorithms [ST08,ACL06,AP09] run in time that is nearly linear in the size of the output set, and their approximation guarantee is worse than the guarantee provided by the Cheeger inequalities by a polylogarithmic $\log^{\Omega(1)} n$ factor.
• It has been a long standing open problem to design a local graph clustering algorithm with an approximation guarantee close to the guarantee of the Cheeger inequalities and with a running time nearly linear in the size of the output.
• In this paper we solve this problem; we design an algorithm with the same guarantee (up to a constant factor) as the Cheeger inequality, that runs in time slightly super linear in the size of the output.