Frank-Wolfe Optimization for Dominant Set Clustering

Abstract

It is convenient to represent a clustering problem as an edge-weighted graph, where the nodes and weights represent the objects and pairwise similarities of the problem. Dominant set is a graph-theoretical definition that extends the idea of maximal clique from unweighted to weighted graphs – intuitively it is a group of connected nodes with relatively large weights. Dominant Set Clustering is based on extracting groups of nodes (clusters) from the graph that satisfy the definition of dominant set. The clusters are computed by solving standard quadratic optimization problems (StQPs) and utilizing a correspondence between the solutions and graph-theoretical definition. In this thesis we study the StQP from the perspective of the Frank-Wolfe (FW) algorithm, and variants thereof, and relate them to replicator dynamics – a method commonly used for computing dominant sets. We consider standard FW, pairwise FW, and away-steps FW, and conclude that all variants perform similarly and are much more efficient compared to replicator dynamics. Explicit proofs of the convergence rate O (1/pt), in terms of the so called Frank-Wolfe gap, are also included for the FW variants when applied to the StQP.