English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  Influence of graph construction on graph-based clustering measures

Maier, M., von Luxburg, U., & Hein, M. (2009). Influence of graph construction on graph-based clustering measures. In D. Koller, D. Schuurmans, Y. Bengio, & L. Bottou (Eds.), Advances in neural information processing systems 21 (pp. 1025-1032). Red Hook, NY, USA: Curran.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0013-C483-0 Version Permalink: https://hdl.handle.net/21.11116/0000-0002-DE62-6
Genre: Conference Paper

Files

show Files

Creators

show
hide
 Creators:
Maier, M1, 2, Author           
von Luxburg, U1, 2, Author           
Hein, M, Author           
Affiliations:
1Department Empirical Inference, Max Planck Institute for Biological Cybernetics, Max Planck Society, ou_1497795              
2Max Planck Institute for Biological Cybernetics, Max Planck Society, Spemannstrasse 38, 72076 Tübingen, DE, ou_1497794              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s):
 Dates: 2009-06
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: BibTex Citekey: 5393
 Degree: -

Event

show
hide
Title: Twenty-Second Annual Conference on Neural Information Processing Systems (NIPS 2008)
Place of Event: Vancouver, BC, Canada
Start-/End Date: 2008-12-08 - 2008-12-10

Legal Case

show

Project information

show

Source 1

show
hide
Title: Advances in neural information processing systems 21
Source Genre: Proceedings
 Creator(s):
Koller, D, Editor
Schuurmans, D, Editor
Bengio, Y, Editor
Bottou, L, Editor
Affiliations:
-
Publ. Info: Red Hook, NY, USA : Curran
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 1025 - 1032 Identifier: ISBN: 978-1-60560-949-2