Back
How the result of graph clustering methods depends on the construction of the graph
We study the scenario of graph-based clustering algorithms such as spectral clustering. Given a set of data points, one rst has to construct a graph on the data points and then apply a graph clustering algorithm to nd a suitable partition of the graph. Our main question is if and how the construction of the graph (choice of the graph, choice of parameters, choice of weights) in uences the outcome of the nal clustering result. To this end we study the convergence of cluster quality measures such as the normalized cut or the Cheeger cut on various kinds of random geometric graphs as the sample size tends to in nity. It turns out that the limit values of the same objective function are systematically di erent on di erent types of graphs. This implies that clustering results systematically depend on the graph and can be very di erent for di erent types of graph. We provide examples to illustrate the implications on spectral clustering.
@article{MaiervH2012, title = {How the result of graph clustering methods depends on the construction of the graph}, journal = {ESAIM: Probability & Statistics}, abstract = {We study the scenario of graph-based clustering algorithms such as spectral clustering. Given a set of data points, one rst has to construct a graph on the data points and then apply a graph clustering algorithm to nd a suitable partition of the graph. Our main question is if and how the construction of the graph (choice of the graph, choice of parameters, choice of weights) in uences the outcome of the nal clustering result. To this end we study the convergence of cluster quality measures such as the normalized cut or the Cheeger cut on various kinds of random geometric graphs as the sample size tends to in nity. It turns out that the limit values of the same objective function are systematically di erent on di erent types of graphs. This implies that clustering results systematically depend on the graph and can be very di erent for di erent types of graph. We provide examples to illustrate the implications on spectral clustering.}, volume = {17}, pages = {370--418}, month = jan, year = {2013}, slug = {maiervh2012}, author = {Maier, M. and von Luxburg, U. and Hein, M.}, month_numeric = {1} }