Timezone: »

 
Poster
Beyond Spectral Clustering - Tight Relaxations of Balanced Graph Cuts
Matthias Hein · Simon Setzer

Mon Dec 12 10:00 AM -- 02:59 PM (PST) @
in Poster Session and Reception »

Spectral clustering is based on the spectral relaxation of the normalized/ratio graph cut criterion. While the spectral relaxation is known to be loose, it has been shown recently that a non-linear eigenproblem yields a tight relaxation of the Cheeger cut. In this paper, we extend this result considerably by providing a characterization of all balanced graph cuts which allow for a tight relaxation. Although the resulting optimization problems are non-convex and non-smooth, we provide an efficient first-order scheme which scales to large graphs. Moreover, our approach comes with the quality guarantee that given any partition as initialization the algorithm either outputs a better partition or it stops immediately.

[ PDF] 

Author Information

Matthias Hein (University of Tübingen)
Simon Setzer (Saarland University)

More from the Same Authors