Hierarchical Nearest Neighbor Graph Embedding for Efficient Dimensionality Reduction

Saquib Sarfraz, Marios Koulakis, Constantin Seibold, Rainer Stiefelhagen; Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2022, pp. 336-345

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

Related Material


[pdf] [supp] [arXiv]
[bibtex]
@InProceedings{Sarfraz_2022_CVPR, author = {Sarfraz, Saquib and Koulakis, Marios and Seibold, Constantin and Stiefelhagen, Rainer}, title = {Hierarchical Nearest Neighbor Graph Embedding for Efficient Dimensionality Reduction}, booktitle = {Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)}, month = {June}, year = {2022}, pages = {336-345} }