Title :
An Information-Theoretic Derivation of Min-Cut-Based Clustering
Author :
Raj, Anil ; Wiggins, Chris H.
Author_Institution :
Dept. of Appl. Phys. & Appl. Math., Columbia Univ., New York, NY, USA
fDate :
6/1/2010 12:00:00 AM
Abstract :
Min-cut clustering, based on minimizing one of two heuristic cost functions proposed by Shi and Malik nearly a decade ago, has spawned tremendous research, both analytic and algorithmic, in the graph partitioning and image segmentation communities over the last decade. It is, however, unclear if these heuristics can be derived from a more general principle, facilitating generalization to new problem settings. Motivated by an existing graph partitioning framework, we derive relationships between optimizing relevance information, as defined in the Information Bottleneck method, and the regularized cut in a K-partitioned graph. For fast-mixing graphs, we show that the cost functions introduced by Shi and Malik can be well approximated as the rate of loss of predictive information about the location of random walkers on the graph. For graphs drawn from a generative model designed to describe community structure, the optimal information-theoretic partition and the optimal min-cut partition are shown to be the same with high probability.
Keywords :
graph theory; information theory; pattern clustering; K-partitioned graph; cost functions; fast-mixing graphs; graph partitioning; image segmentation; information bottleneck method; information-theoretic derivation; min-cut-based clustering; relevance information; Algorithm design and analysis; Clustering algorithms; Cost function; Image analysis; Image segmentation; Information analysis; Mathematics; Partitioning algorithms; Physics; Probability distribution; Graphs; Information Bottleneck; clustering; graph diffusion.; information theory; min-cut; Algorithms; Artificial Intelligence; Cluster Analysis; Image Processing, Computer-Assisted;
Journal_Title :
Pattern Analysis and Machine Intelligence, IEEE Transactions on
DOI :
10.1109/TPAMI.2009.124