Proximity Graphs for Clustering and Manifold Learning

Miguel Carreira-Perpinan and Rich Zemel

Consider a cloud of points in Euclidean space. Machine learning problems such as clustering or dimensionality reduction, when formulated on the pairwise distances between points, assume a graph having as vertices the data points. The graph is then partitioned (clustering) or used to redefine metric information (dimensionality reduction). There has been much recent work on different algorithms for graph-based clustering and dimensionality reduction, but not much on learning the graph itself. Graphs typically used include the fully-connected graph, a fixed-grid graph (for image segmentation) or a nearest-neighbour graph.

We suggest that the graph should adapt locally to the structure of the data and take into account its noisy nature. This can be attained by a graph ensemble obtained by combining multiple minimum spanning trees, each fit to a perturbed version of the data set. We show that such a graph ensemble usually produces a better representation of the data manifold than standard methods; and that it provides robustness to a subsequent clustering or dimensionality reduction algorithm based on the graph.