# Higher-Order Cheeger Inequality for Partitioning with Buffers

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Aug 2023.

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

- [Theoretical Analysis of Weak-to-Strong Generalization](https://mlsanity.com/paper/2405.16043/) (2024)

## Abstract (arXiv)

We prove a new generalization of the higher-order Cheeger inequality for partitioning with buffers. Consider a graph G=(V,E). The buffered expansion of a set S subseteq V with a buffer B subseteq V setminus S is the edge expansion of S after removing all the edges from set S to its buffer B. An varepsilon-buffered k-partitioning is a partitioning of a graph into disjoint components Pi and buffers Bi, in which the size of buffer Bi for Pi is small relative to the size of Pi: |Bi| ≤ varepsilon |Pi|. The buffered expansion of a buffered partition is the maximum of buffered expansions of the k sets Pi with buffers Bi. Let hk,varepsilonG be the buffered expansion of the optimal varepsilon-buffered k-partitioning, then for every δ>0, hGk,varepsilon ≤ Oδ(1) · Big( fraclog k varepsilonBig) · λlfloor (1+δ) krfloor, where λlfloor (1+δ)krfloor is the lfloor (1+δ)krfloor-th smallest eigenvalue of the normalized Laplacian of G. Our inequality is constructive and avoids the ``square-root loss'' that is present in the standard Cheeger inequalities (even for k=2). We also provide a complementary lower bound, and a novel generalization to the setting with arbitrary vertex weights and edge costs. Moreover our result implies and generalizes the standard higher-order Cheeger inequalities and another recent Cheeger-type inequality by Kwok, Lau, and Lee (2017) involving robust vertex expansion.