Information Theoretic Pairwise Clustering

Abstract. In this paper we develop an information-theoretic approach for pairwise clustering. The Laplacian of the pairwise similarity matrix can be used to define a Markov random walk on the data points. This view forms a probabilistic interpretation of spectral clustering methods. We utilize this probabilistic model to define a novel clustering cost func-tion that is based on maximizing the mutual information between con-secutively visited clusters of states of the Markov chain defined by the graph Laplacian matrix. The algorithm complexity is linear on sparse graphs. The improved performance and the reduced computational com-plexity of the proposed algorithm are demonstrated on several standard datasets.