# 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.