A polylogarithmic higher-order Cheeger inequality

Source abstract

Let $λ_k(G)$ be the $k$th eigenvalue of the normalized Laplacian of a finite undirected weighted graph, and let $ρ_G(k)$ be the minimum possible maximum conductance of $k$ disjoint nonempty vertex sets. We prove $$ρ_G(k)\le C[1+\log(k+1)]^5\sqrt{λ_k(G)}$$ for an absolute constant $C$. The construction gives exactly $k$ sets and a bound in terms of $λ_k(G)$, with all boundaries and volumes measured in the original graph. More strongly, it yields $k$ nonnegative functions with pairwise disjoint supports and Rayleigh quotients $O([1+\log(k+1)]^{10}λ_k(G))$. The proof uses independent local cutoffs whose lost covariance is controlled by conditioning on the loss along a principal direction in each cell. A regularized spectral embedding bounds cutoff energy on the entire original low eigenspace, while an adaptive construction reduces the remaining coefficient dimension by at least half at each stage. A dimension argument then converts almost rank-one local covariances into exactly $k$ scalar witnesses.