nips nips2008 nips2008-107 nips2008-107-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Markus Maier, Ulrike V. Luxburg, Matthias Hein
Abstract: 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. 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 are applied to. We also provide examples which show that these differences can be observed for toy and real data already for rather small sample sizes. 1
Data Repository by G. R¨ tsch. http://ida.first.fraunhofer.de/projects/bench/benchmarks.htm. a M. Maier, M. Hein, and U. von Luxburg. Cluster identification in nearest-neighbor graphs. In M.Hutter, R. Servedio, and E. Takimoto, editors, Proceedings of the 18th Conference on Algorithmic Learning Theory, volume 4754 of Lecture Notes in Artificial Intelligence, pages 196–210. Springer, Berlin, 2007. Markus Maier, Ulrike von Luxburg, and Matthias Hein. Influence of graph construction on graph-based quality measures - technical supplement. http://www.kyb.mpg.de/bs/people/mmaier/nips08supplement.html, 2008. Hariharan Narayanan, Mikhail Belkin, and Partha Niyogi. On the relation between low density separation, spectral clustering and graph cuts. In NIPS 20, 2007. J. Shi and J. Malik. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8):888–905, 2000. U. von Luxburg. A tutorial on spectral clustering. Statistics and Computing, 17(4):395 – 416, 2007. U. von Luxburg, S. Bubeck, S. Jegelka, and M. Kaufmann. Consistent minimization of clustering objective functions. In NIPS 21, 2008. 8