# A Cheeger Inequality for Size-Specific Conductance

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

## Key facts

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

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

- [Suboptimality bounds for trace-bounded SDPs enable a faster and scalable low-rank SDP solver SDPLR+](https://mlsanity.com/paper/2406.10407/) (2024)

## Abstract (arXiv)

The μ-conductance measure proposed by Lov'asz and Simonovits is a size-specific conductance score that identifies the set with smallest conductance while disregarding those sets with volume smaller than a μ fraction of the whole graph. Using μ-conductance enables us to study the network structures in new ways. In this manuscript we study a modified spectral cut for μ-conductance that is a natural relaxation of the integer program of μ-conductance and show that the optimum of this program has a two-sided Cheeger inequality with μ-conductance.