We develop a new graph-theoretic approach for pairwise data clustering which is motivated by the analogies between the intuitive concept of a cluster and that of a dominant set of vertices, a notion introduced here which generalizes that of a maximal complete subgraph to edge-weighted graphs. We establish a correspondence between dominant sets and the extrema of a quadratic form over the standard simplex, thereby allowing the use of straightforward and easily implementable continuous optimization techniques from evolutionary game theory. Numerical examples on various point-set and image segmentation problems confirm the potential of the proposed approach.

Dominant sets are a new graph-theoretic concept that has proven to be relevant in pairwise data clustering problems, such as image seg- mentation. They generalize the notion of a maximal clique to edge- weighted graphs and have intriguing, non-trivial connections to continu- ous quadratic optimization and spectral-based grouping. We address the problem of grouping out-of-sample examples after the clustering process has taken place. This may serve either to drastically reduce the compu- tational burden associated to the processing of very large data sets, or to efficiently deal with dynamic situations whereby data sets need to be updated continually. We show that the very notion of a dominant set of- fers a simple and efficient way of doing this. Numerical experiments on various grouping problems show the effectiveness of the approach.

We develop a framework for the image segmentation problem based on a new graph-theoretic formulation of clustering. The approach is motivated by the analogies between the intuitive concept of a cluster and that of a dominant set of vertices, a notion that generalizes that of a maximal complete subgraph to edge-weighted graphs. We also establish a correspondence between dominant sets and the extrema of a quadratic form over the standard simplex, thereby allowing us the use of continuous optimization techniques such as replicator dynamics from evolutionary game theory. Such systems are attractive as they can be coded in a few lines of any high-level programming language, can easily be implemented in a parallel network of locally interacting units, and offer the advantage of biological plausibility. We present experimental results on real-world images which show the effectiveness of the proposed approach.

Dominant sets are a new graph-theoretic concept that has proven to be relevant in partitional (flat) clustering as well as image segmentation problems. However, in many computer vision applications, such as the organization of an image database, it is important to provide the data to be clustered with a hierarchical organization, and it is not clear how to do this within the dominant set framework. We address precisely this problem, and present a simple and elegant solution to it. To this end, we consider a family of (continuous) quadratic programs, which contain a parameterized regularization term that controls the global shape of the energy landscape. When the regularization parameter is zero the local solutions are known to be in one-to-one correspondence with dominant sets, but when it is positive an interesting picture emerges. We determine bounds for the regularization parameter that allow us to exclude from the set of local solutions those inducing clusters of size smaller than a prescribed threshold. This suggests a new (divisive) hierarchical approach to clustering, which is based on the idea of properly varying the regularization parameter during the clustering process. Straightforward dynamics from evolutionary game theory are used to locate the solutions of the quadratic programs at each level of the hierarchy. We apply the proposed framework to the problem of organizing a shape database. Experiments with three different similarity matrices (and databases) reported in the literature have been conducted, and the results confirm the effectiveness of our approach.