Supervised Graph-Theoretic Clustering

Dominant set is a recently proposed graph-theoretic concept for pairwise data clustering problem. It owns a number of attractive features: it generalizes the notion of a maximal complete subgraph to edge-weighted graph and establishes a correspondence between dominant set and continuous quadratic optimization. The intriguing and non-trivial extension of dominant set clustering to supervised clustering is independently proposed by us in this paper. Cluster labels are incorporated in our method to modify the objective function, and to learn the similarity measurement. In experiments, we compare our method with both the unsupervised one and a number of other clustering methods based on learning, which demonstrates the enhanced clustering quality by employing such supervision when compared to the original dominant set clustering algorithm and a better performance when compared to other clustering methods based on learning.