Timezone: »
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.
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
-
2021 : RobustBench: a standardized adversarial robustness benchmark »
Francesco Croce · Maksym Andriushchenko · Vikash Sehwag · Edoardo Debenedetti · Nicolas Flammarion · Mung Chiang · Prateek Mittal · Matthias Hein -
2021 Spotlight: An Infinite-Feature Extension for Bayesian ReLU Nets That Fixes Their Asymptotic Overconfidence »
Agustinus Kristiadi · Matthias Hein · Philipp Hennig -
2021 : Being a Bit Frequentist Improves Bayesian Neural Networks »
Agustinus Kristiadi · Matthias Hein · Philipp Hennig -
2021 Poster: An Infinite-Feature Extension for Bayesian ReLU Nets That Fixes Their Asymptotic Overconfidence »
Agustinus Kristiadi · Matthias Hein · Philipp Hennig -
2021 Poster: Meta-Learning the Search Distribution of Black-Box Random Search Based Adversarial Attacks »
Maksym Yatsura · Jan Metzen · Matthias Hein -
2018 : Lunch & Posters »
Haytham Fayek · German Parisi · Brian Xu · Pramod Kaushik Mudrakarta · Sophie Cerf · Sarah Wassermann · Davit Soselia · Rahaf Aljundi · Mohamed Elhoseiny · Frantzeska Lavda · Kevin J Liang · Arslan Chaudhry · Sanmit Narvekar · Vincenzo Lomonaco · Wesley Chung · Michael Chang · Ying Zhao · Zsolt Kira · Pouya Bashivan · Banafsheh Rafiee · Oleksiy Ostapenko · Andrew Jones · Christos Kaplanis · Sinan Kalkan · Dan Teng · Xu He · Vincent Liu · Somjit Nath · Sungsoo Ahn · Ting Chen · Shenyang Huang · Yash Chandak · Nathan Sprague · Martin Schrimpf · Tony Kendall · Jonathan Richard Schwarz · Michael Li · Yunshu Du · Yen-Chang Hsu · Samira Abnar · Bo Wang -
2017 : Poster Spotlights I »
Taesik Na · Yang Song · Aman Sinha · Richard Shin · Qiuyuan Huang · Nina Narodytska · Matt Staib · Kexin Pei · Fnu Suya · Amirata Ghorbani · Jacob Buckman · Matthias Hein · Huan Zhang · Yanjun Qi · Yuan Tian · Min Du · Dimitris Tsipras -
2017 Poster: Formal Guarantees on the Robustness of a Classifier against Adversarial Manipulation »
Matthias Hein · Maksym Andriushchenko -
2016 Poster: Clustering Signed Networks with the Geometric Mean of Laplacians »
Pedro Mercado · Francesco Tudisco · Matthias Hein -
2016 Poster: Globally Optimal Training of Generalized Polynomial Neural Networks with Nonlinear Spectral Methods »
Antoine Gautier · Quynh Nguyen · Matthias Hein -
2015 Poster: Efficient Output Kernel Learning for Multiple Tasks »
Pratik Kumar Jawanpuria · Maksim Lapin · Matthias Hein · Bernt Schiele -
2015 Demonstration: The pMMF multiresolution matrix factorization library »
Risi Kondor · Pramod Kaushik Mudrakarta · Nedelina Teneva -
2015 Poster: Top-k Multiclass SVM »
Maksim Lapin · Matthias Hein · Bernt Schiele -
2015 Spotlight: Top-k Multiclass SVM »
Maksim Lapin · Matthias Hein · Bernt Schiele -
2015 Poster: Regularization-Free Estimation in Trace Regression with Symmetric Positive Semidefinite Matrices »
Martin Slawski · Ping Li · Matthias Hein -
2013 Poster: The Total Variation on Hypergraphs - Learning on Hypergraphs Revisited »
Matthias Hein · Simon Setzer · Leonardo Jost · Syama Sundar Rangapuram -
2013 Spotlight: The Total Variation on Hypergraphs - Learning on Hypergraphs Revisited »
Matthias Hein · Simon Setzer · Leonardo Jost · Syama Sundar Rangapuram -
2013 Poster: Matrix factorization with binary components »
Martin Slawski · Matthias Hein · Pavlo Lutsik -
2013 Spotlight: Matrix factorization with binary components »
Martin Slawski · Matthias Hein · Pavlo Lutsik -
2011 Poster: Sparse recovery by thresholded non-negative least squares »
Martin Slawski · Matthias Hein -
2011 Poster: Beyond Spectral Clustering - Tight Relaxations of Balanced Graph Cuts »
Matthias Hein · Simon Setzer -
2010 Poster: An Inverse Power Method for Nonlinear Eigenproblems with Applications in 1-Spectral Clustering and Sparse PCA »
Matthias Hein · Thomas Bühler -
2010 Spotlight: Getting lost in space: Large sample analysis of the resistance distance »
Ulrike von Luxburg · Agnes Radl · Matthias Hein -
2010 Poster: Getting lost in space: Large sample analysis of the resistance distance »
Ulrike von Luxburg · Agnes Radl · Matthias Hein -
2009 Poster: Semi-supervised Regression using Hessian energy with an application to semi-supervised dimensionality reduction »
Kwang In Kim · Florian Steinke · Matthias Hein -
2009 Poster: Robust Nonparametric Regression with Metric-Space Valued Output »
Matthias Hein -
2008 Poster: Non-parametric Regression Between Manifolds »
Florian Steinke · Matthias Hein -
2008 Poster: Influence of graph construction on graph-based clustering measures »
Markus M Maier · Ulrike von Luxburg · Matthias Hein -
2008 Oral: Influence of graph construction on graph-based clustering measures »
Markus M Maier · Ulrike von Luxburg · Matthias Hein -
2006 Poster: Manifold Denoising »
Matthias Hein · Markus M Maier -
2006 Talk: Manifold Denoising »
Matthias Hein · Markus M Maier