Timezone: »
Graph clustering methods such as spectral clustering are defined for general weighted graphs. In machine learning, however, data often is not given in form of a graph, but in terms of similarity (or distance) values between points. In this case, first a neighborhood graph is constructed using the similarities between the points and then a graph clustering algorithm is applied to this graph. In this paper we investigate the influence of the construction of the similarity graph on the clustering results, from a theoretical point of view. We first study the convergence of graph clustering criteria such as the normalized cut (Ncut) as the sample size tends to infinity. We find that the limit expressions are different for different types of graph, for example the r-neighborhood graph or the k-nearest neighbor graph. In plain words: Ncut on a knn graph does something systematically different than Ncut on an r-neighborhood graph! This finding shows that graph clustering criteria cannot be studied independently of the kind of graph they will be applied to. We also provide examples which show how those differences lead to big differences in clustering results in practice.
Author Information
Markus M Maier (Max Planck Institute for Biological Cybernetics)
Ulrike von Luxburg (University of Tuebingen)
Matthias Hein (University of Tübingen)
Related Events (a corresponding poster, oral, or spotlight)
-
2008 Poster: Influence of graph construction on graph-based clustering measures »
Tue. Dec 9th through Mon the 8th Room
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 -
2022 Poster: Interpolation and Regularization for Causal Learning »
Leena Chennuru Vankadara · Luca Rendsburg · Ulrike Luxburg · Debarghya Ghoshdastidar -
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 -
2019 Poster: Foundations of Comparison-Based Hierarchical Clustering »
Debarghya Ghoshdastidar · Michaël Perrot · Ulrike von Luxburg -
2018 Poster: When do random forests fail? »
Cheng Tang · Damien Garreau · Ulrike von Luxburg -
2018 Poster: Measures of distortion for machine learning »
Leena Chennuru Vankadara · Ulrike von Luxburg -
2018 Poster: Practical Methods for Graph Two-Sample Testing »
Debarghya Ghoshdastidar · Ulrike von Luxburg -
2017 : Ordinal distance comparisons: from topology to geometry »
Ulrike von Luxburg -
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 -
2017 Poster: Kernel functions based on triplet comparisons »
Matthäus Kleindessner · Ulrike von Luxburg -
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 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 -
2014 Poster: Tight Continuous Relaxation of the Balanced k-Cut Problem »
Syama Sundar Rangapuram · Pramod Kaushik Mudrakarta · Matthias Hein -
2013 Poster: Density estimation from unweighted k-nearest neighbor graphs: a roadmap »
Ulrike von Luxburg · Morteza Alamgir -
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 Workshop: Relations between machine learning problems - an approach to unify the field »
Robert Williamson · John Langford · Ulrike von Luxburg · Mark Reid · Jennifer Wortman Vaughan -
2011 Poster: Phase transition in the family of p-resistances »
Morteza Alamgir · Ulrike von Luxburg -
2011 Poster: Sparse recovery by thresholded non-negative least squares »
Martin Slawski · Matthias Hein -
2011 Spotlight: Phase transition in the family of p-resistances »
Morteza Alamgir · Ulrike von Luxburg -
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 Workshop: Clustering: Science or art? Towards principled approaches »
Margareta Ackerman · Shai Ben-David · Avrim Blum · Isabelle Guyon · Ulrike von Luxburg · Robert Williamson · Reza Zadeh -
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 -
2007 Session: Spotlights »
Ulrike von Luxburg -
2007 Session: Spotlights »
Ulrike von Luxburg -
2007 Spotlight: Consistent Minimization of Clustering Objective Functions »
Ulrike von Luxburg · Sebastien Bubeck · Stefanie S Jegelka · Michael Kaufmann -
2007 Poster: Consistent Minimization of Clustering Objective Functions »
Ulrike von Luxburg · Sebastien Bubeck · Stefanie S Jegelka · Michael Kaufmann -
2006 Poster: Manifold Denoising »
Matthias Hein · Markus M Maier -
2006 Talk: Manifold Denoising »
Matthias Hein · Markus M Maier