
Discrete Mathematics and Optimization Seminar

Jan. 5th, 2009
The DominantSet Framework for Pairwise Data Clustering
Marcello Pelillo
Ca' Foscari University, Venice, Italy

In this talk I'll provide an overview of the work we have been doing in my
group on pairwise data clustering. We have developed a graphtheoretic
framework for pairwise clustering which is motivated by the analogies
between the intuitive concept of a cluster and that of a "dominant set" of
vertices, a novel notion that generalizes that of a maximal clique to
edgeweighted graphs. We established a correspondence between dominant
sets and the extrema of a quadratic form over the standard simplex,
thereby allowing us to use straightforward continuous optimization
techniques such as replicator dynamics from evolutionary game theory. We
have also addressed the problem of grouping outofsample examples after
the clustering process has taken place: as it turns out, the very notion
of a dominant set offers a simple and efficient way of doing this.
Finally, we have provided a generalization of the dominantset notion to
the case of arbitrary (i.e., negative and/or asymmetric) affinities which
is based on the notion of a Nash equilibrium, a fundamental concept fron
noncooperative game theory. The approach has been tested extensively on on
image segmentation and perceptual grouping problems.
[joint work with M. Pavan, A. Torsello, S. Rota Bulo']



