Hierarchical Nearest Neighbor Graph Embedding for Efficient Dimensionality Reduction

Saquib Sarfraz, Marios Koulakis, Constantin Seibold, Rainer Stiefelhagen

CVPR 2022 pp. 336-345

doi:10.1109/CVPR52688.2022.00043 /cvpr/2022/sarfraz2022cvpr-hierarchical/

Abstract

Dimensionality reduction is crucial both for visualization and preprocessing high dimensional data for machine learning. We introduce a novel method based on a hierarchy built on 1-nearest neighbor graphs in the original space which is used to preserve the grouping properties of the data distribution on multiple levels. The core of the proposal is an optimization-free projection that is competitive with the latest versions of t-SNE and UMAP in performance and visualization quality while being an order of magnitude faster at run-time. Furthermore, its interpretable mechanics, the ability to project new data, and the natural separation of data clusters in visualizations make it a general purpose unsupervised dimension reduction technique. In the paper, we argue about the soundness of the proposed method and evaluate it on a diverse collection of datasets with sizes varying from 1K to 11M samples and dimensions from 28 to 16K. We perform comparisons with other state-of-the-art methods on multiple metrics and target dimensions highlighting its efficiency and performance. Code is available at https://github.com/koulakis/h-nne

PDF CVPR Semantic Scholar

Cite

Text

Sarfraz et al. "Hierarchical Nearest Neighbor Graph Embedding for Efficient Dimensionality Reduction." Conference on Computer Vision and Pattern Recognition, 2022. doi:10.1109/CVPR52688.2022.00043

Markdown

[Sarfraz et al. "Hierarchical Nearest Neighbor Graph Embedding for Efficient Dimensionality Reduction." Conference on Computer Vision and Pattern Recognition, 2022.](https://mlanthology.org/cvpr/2022/sarfraz2022cvpr-hierarchical/) doi:10.1109/CVPR52688.2022.00043

BibTeX

@inproceedings{sarfraz2022cvpr-hierarchical,
  title     = {{Hierarchical Nearest Neighbor Graph Embedding for Efficient Dimensionality Reduction}},
  author    = {Sarfraz, Saquib and Koulakis, Marios and Seibold, Constantin and Stiefelhagen, Rainer},
  booktitle = {Conference on Computer Vision and Pattern Recognition},
  year      = {2022},
  pages     = {336-345},
  doi       = {10.1109/CVPR52688.2022.00043},
  url       = {https://mlanthology.org/cvpr/2022/sarfraz2022cvpr-hierarchical/}
}