How the result of graph clustering methods depends on the construction of the graph

Markus Maier, Ulrike von Luxburg, Matthias Hein

We study the scenario of graph-based clustering algorithms such as spectral clustering. Given a set of data points, one first has to construct a graph on the data points and then a…