Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering

Shyam Narayanan, Sandeep Silwal, Piotr Indyk, Or Zamir

Clustering high-dimensional data is notoriously computationally expensive because distance calculations scale linearly with the number of dimensions. While the Johnson-Lindenstrauss (JL) Lemma offers a standard workaround—projecting $n$ points into $O(\log n)$ dimensions while preserving pairwise distances—researchers have often wondered if we can compress data even further.

For problems with a fixed number of clusters ($k$), like $k$-means, it is possible to project into $O(\log k)$ dimensions. However, many real-world problems do not have a predetermined $k$. This paper investigates two such variable-cluster problems:

  1. Facility Location (FL): Balancing the cost of opening "facilities" (cluster centers) against the distance points must travel to reach them.
  2. Single-Linkage Clustering (MST): Building a hierarchy of clusters by connecting the closest points, mathematically equivalent to finding a Minimum Spanning Tree.

The authors demonstrate that for these problems, randomly projecting data into a lower dimension proportional to its intrinsic doubling dimension ($d_X$) is sufficient to preserve solution quality. This approach yields massive speedups on high-dimensional datasets with minimal loss in accuracy.

Leveraging Intrinsic Geometry

The core theoretical contribution of the paper links the target projection dimension not to the raw number of points ($n$), but to the dataset's doubling dimension ($d_X$).

The doubling dimension measures a dataset's "intrinsic" dimensionality. If a set of points covered by a ball of radius $r$ can always be covered by a small number of balls of radius $r/2$, the dataset has a low doubling dimension. By proving that the "true" complexity of clustering depends on this intrinsic shape rather than the raw point count, the authors justify much more aggressive compression than the JL lemma suggests.

To prove this works, the authors rely on two main technical arguments:

  • Local Optimality for FL: They prove that a solution that is "locally optimal" in the projected space is still a good approximation when evaluated in the original high-dimensional space.
  • Chaining Arguments for MST: They utilize sophisticated "chaining" techniques to ensure that edges in the Minimum Spanning Tree don't shrink or expand excessively after projection.

Key Findings and Experimental Results

The authors validated their theory using both real-world datasets (Faces, MNIST) and synthetic datasets designed to test sensitivity to intrinsic dimensionality.

Massive Speedups: By projecting data to just $d=20$ dimensions, the authors achieved an 80x speedup for MST computation on the Faces dataset (4096 original dimensions) and a 30x speedup on the MNIST dataset (784 original dimensions).

High Accuracy: Despite the aggressive dimensionality reduction, the "Pullback" cost—the cost of the low-dimensional solution when measured back in the high-dimensional space—quickly approaches the optimal cost as the projected dimension increases.

Facility Location clustering performance on the Faces dataset

Sensitivity to Doubling Dimension: The experiments perfectly confirmed the paper's central theory regarding intrinsic geometry. When comparing synthetic datasets, the dataset with a low doubling dimension reached a high-quality MST approximation much faster (at lower projected dimensions) than the dataset with a high doubling dimension.

MST approximation performance and doubling dimension sensitivity

Limitations and Future Directions

While the results are highly promising, the paper notes a few limitations:

  • Uniform Costs: The primary theoretical results for Facility Location assume uniform opening costs for all facilities. While generalizations are possible, the core proofs focus on this simpler case.
  • Worst-case Scenarios: If a dataset is truly high-dimensional with no underlying structure (e.g., random points uniformly distributed on a sphere), the doubling dimension $d_X$ becomes $O(\log n)$, and the benefits over standard JL reduction disappear.

Ultimately, this paper proves that standard clustering algorithms work exceptionally well on aggressively projected data. Rather than proposing a new end-to-end algorithm, it provides a rigorous theoretical justification for using random projections as a highly effective pre-processing step for variable-cluster problems.

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