Part of Advances in Neural Information Processing Systems 15 (NIPS 2002)
Chakra Chennubhotla, Allan Jepson
Using a Markov chain perspective of spectral clustering we present an algorithm to automatically ﬁnd the number of stable clusters in a dataset. The Markov chain’s behaviour is characterized by the spectral properties of the matrix of transition probabilities, from which we derive eigenﬂows along with their halﬂives. An eigenﬂow describes the ﬂow of probabil- ity mass due to the Markov chain, and it is characterized by its eigen- value, or equivalently, by the halﬂife of its decay as the Markov chain is iterated. A ideal stable cluster is one with zero eigenﬂow and inﬁ- nite half-life. The key insight in this paper is that bottlenecks between weakly coupled clusters can be identiﬁed by computing the sensitivity of the eigenﬂow’s halﬂife to variations in the edge weights. We propose a novel EIGENCUTS algorithm to perform clustering that removes these identiﬁed bottlenecks in an iterative fashion.