Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering

Shyam Narayanan, Sandeep Silwal, Piotr Indyk, Or Zamir

Abstract

Random dimensionality reduction is a versatile tool for speeding up algorithms for high-dimensional problems. We study its application to two clustering problems: the facility location problem, and the single-linkage hierarchical clustering problem, which is equivalent to computing the minimum spanning tree. We show that if we project the input pointset $X$ onto a random $d = O(d_X)$-dimensional subspace (where $d_X$ is the doubling dimension of $X$), then the optimum facility location cost in the projected space approximates the original cost up to a constant factor. We show an analogous statement for minimum spanning tree, but with the dimension $d$ having an extra $\log \log n$ term and the approximation factor being arbitrarily close to $1$. Furthermore, we extend these results to approximating solutions instead of just their costs. Lastly, we provide experimental results to validate the quality of solutions and the speedup due to the dimensionality reduction. Unlike several previous papers studying this approach in the context of $k$-means and $k$-medians, our dimension bound does not depend on the number of clusters but only on the intrinsic dimensionality of $X$.

Introduction

Clustering high-dimensional data is computationally expensive because distance metrics scale with dimensionality. While the Johnson-Lindenstrauss lemma allows for projection into $O(\log n)$ dimensions, recent work in $k$-means clustering has reduced this to $O(\log k)$. However, many clustering problems, such as Facility Location (FL) and Single-Linkage Clustering (Minimum Spanning Tree, or MST), do not have a fixed number of clusters $k$. This paper explores how the intrinsic geometry of a dataset, specifically its doubling dimension ($d_X$), can be used to determine the target dimensionality for random projections, independent of the number of clusters.

Methodology

The authors employ random Gaussian projections to reduce the dimensionality of the input pointset $X$. The core innovation lies in the theoretical analysis, which parameterizes the target dimension $d$ by the doubling dimension $d_X$. The doubling dimension is a measure of intrinsic dimensionality; a space has doubling dimension $d_X$ if every ball of radius $R$ can be covered by $2^{d_X}$ balls of radius $R/2$.

The analysis focuses on two primary guarantees:

  1. Cost Preservation: The optimal cost in the projected space approximates the optimal cost in the original space.
  2. Solution Preservation: A solution computed in the projected space (a "pullback" solution) remains a high-quality approximation when applied back to the original high-dimensional space.

Theoretical Guarantees

For Facility Location, the authors prove that projecting to $d = O(d_X)$ dimensions preserves both cost and solution quality within a constant factor. This requires the projected solution to be locally optimal.

For MST, the projection requires $d = O(d_X \log(1/\epsilon) + \log \log n)$ dimensions to achieve a $(1+\epsilon)$ approximation. The proof uses chaining arguments to ensure that distances between far-apart points do not collapse excessively.

Interestingly, the authors demonstrate a fundamental difference between these problems and $k$-means/k-medians: for the latter, a low doubling dimension does not allow one to bypass the $O(\log k)$ dimension limit, whereas for FL and MST, $d_X$ is the primary governing factor.

Experimental Evaluation

The approach was tested on real-world datasets (Faces, MNIST) and synthetic Gaussian datasets with varying doubling dimensions.

Performance of MST pullback solutions and running times across different datasets and doubling dimensions.

As shown in Figure 2, the quality of the pullback MST solution (measured as the ratio to the true MST) improves as the projected dimension increases. Crucially, Figure 2(c) validates the theoretical dependence on doubling dimension: the dataset with a low doubling dimension converges to a low error much faster than the high-doubling-dimension counterpart.

Facility Location performance on the MNIST '2' dataset for varying number of clusters (k).

For Facility Location, the empirical results show significant speedups. Projecting the 4096-dimensional Faces dataset to $d=20$ resulted in an 80x speedup, while the 784-dimensional MNIST dataset saw a 30x speedup. Figure 5 illustrates that the pullback clustering quality for MNIST remains stable across different scales of $k$, confirming that the projection quality is robust to the number of clusters.

Conclusion

This work establishes that for clustering problems with a variable number of clusters, like FL and MST, the intrinsic doubling dimension of the data is the key factor for effective dimensionality reduction. By leveraging this, practitioners can achieve massive computational speedups (30x–80x) while maintaining strong mathematical guarantees on solution quality. A critical takeaway is the requirement for local optimality in the lower-dimensional space to ensure valid pullback solutions.

Summary updated

Abstract

Random dimensionality reduction is a versatile tool for speeding up algorithms for high-dimensional problems. We study its application to two clustering problems: the facility location problem, and the single-linkage hierarchical clustering problem, which is equivalent to computing the minimum spanning tree. We show that if we project the input pointset $X$ onto a random $d = O(d_X)$-dimensional subspace (where $d_X$ is the doubling dimension of $X$), then the optimum facility location cost in the projected space approximates the original cost up to a constant factor. We show an analogous statement for minimum spanning tree, but with the dimension $d$ having an extra $\log \log n$ term and the approximation factor being arbitrarily close to $1$. Furthermore, we extend these results to approximating solutions instead of just their costs. Lastly, we provide experimental results to validate the quality of solutions and the speedup due to the dimensionality reduction. Unlike several previous papers studying this approach in the context of $k$-means and $k$-medians, our dimension bound does not depend on the number of clusters but only on the intrinsic dimensionality of $X$.
BibTeX
@inproceedings{narayanan2021randomized,
  author = {Shyam Narayanan and Sandeep Silwal and Piotr Indyk and Or Zamir},
  title = {{Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=RRHbe-Bjnr},
}
Figure