Normalized Cuts Are Approximately Inverse Exit Times
Lists
Only you see this
Abstract
Normalized cut is a widely used measure of separation between clusters in a graph. In this paper we provide a novel probabilistic perspective on this measure. We show that for a partition of a graph into two weakly connected sets, $V=A\uplus B$, the multiway normalized cut is approximately $MNcut \approx 1/\tau_{A\to B}+1/\tau_{B\to A}$, where $\tau_{A\to B}$ is the unidirectional characteristic exit time of a random walk from subset $A$ to subset $B$. Using matrix perturbation theory, we show that this approximation is exact to first order in the connection strength between the two subsets $A$ and $B$, and we derive an explicit bound for the approximation error. Our result implies that for a Markov chain composed of a reversible subset $A$ that is weakly connected to an absorbing subset $B$, the easy-to-compute normalized cut measure is a reliable proxy for the chain's spectral gap.
BibTeX
@article{gavish2013normalized,
author = {Matan Gavish and Boaz Nadler},
title = {{Normalized Cuts Are Approximately Inverse Exit Times}},
journal = {SIAM J. Matrix Anal. Appl.},
year = {2013},
doi = {10.1137/110826928},
}Loading related content...