Frank-Wolfe Optimization for Dominant Set Clustering
Ladda ner
Typ
Examensarbete för masterexamen
Program
Publicerad
2020
Författare
Johnell, Carl
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
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.
Beskrivning
Ämne/nyckelord
clustering , convergence rate , dominant set , rank-wolfe , optimization , replicator dynamics , stqp