Timezone: »

 
Poster
Tight Continuous Relaxation of the Balanced k-Cut Problem
Syama Sundar Rangapuram · Pramod Kaushik Mudrakarta · Matthias Hein

Thu Dec 11 11:00 AM -- 03:00 PM (PST) @ Level 2, room 210D
in Poster Session »

Spectral Clustering as a relaxation of the normalized/ratio cut has become one of the standard graph-based clustering methods. Existing methods for the computation of multiple clusters, corresponding to a balanced k-cut of the graph, are either based on greedy techniques or heuristics which have weak connection to the original motivation of minimizing the normalized cut. In this paper we propose a new tight continuous relaxation for any balanced k-cut problem and show that a related recently proposed relaxation is in most cases loose leading to poor performance in practice. For the optimization of our tight continuous relaxation we propose a new algorithm for the hard sum-of-ratios minimization problem which achieves monotonic descent. Extensive comparisons show that our method beats all existing approaches for ratio cut and other balanced k-cut criteria.

[ PDF] 

Author Information

Syama Sundar Rangapuram (Saarland University)
Pramod Kaushik Mudrakarta (The University of Chicago)
Matthias Hein (University of Tübingen)

More from the Same Authors