NCVis: Noise Contrastive Approach for Scalable Visualization

Aleksandr Artemenkov, Maxim Panov

Abstract

Visualizing high-dimensional datasets with millions of points remains a significant challenge for traditional methods like t-SNE due to computational bottlenecks in probability normalization. We present NCVis, a scalable dimensionality reduction technique based on Noise Contrastive Estimation (NCE). NCVis avoids expensive global normalization by treating the embedding process as a binary classification task between real neighbors and noise. Experimental results demonstrate that NCVis can process over a million data points in minutes on standard hardware while maintaining visualization quality comparable to state-of-the-art methods.

1. Introduction

High-dimensional data visualization is a cornerstone of modern data science, enabling researchers to interpret complex structures through 2D maps. Techniques like t-SNE and UMAP are widely considered the gold standard; however, they often struggle with scalability. The primary bottleneck in t-SNE is the requirement to normalize the 2D distribution at every optimization step, an $O(N^2)$ operation that becomes prohibitive as datasets grow into the millions.

In "NCVis: Noise Contrastive Approach for Scalable Visualization," Aleksandr Artemenkov and Maxim Panov introduce a new method designed to visualize millions of points in minutes on a standard desktop PC. By leveraging a sound statistical framework, NCVis offers a principled and highly parallelizable alternative to existing heuristic-based speedups.

2. Methodology

The "secret sauce" of NCVis is Noise Contrastive Estimation (NCE). Instead of modeling the entire probability distribution—which requires expensive normalization—NCE reframes the dimensionality reduction problem as a simple binary classification task.

2.1. The Classification Trick

The algorithm learns to distinguish between "real" pairs of neighboring points from the dataset and "noise" pairs generated randomly. Because NCE focuses on this contrastive task, it does not need to calculate the global normalization constant. Instead, it treats the normalization factor as a learnable parameter, significantly reducing the mathematical complexity.

2.2. Efficient Graphing and Parallelization

To identify "real" neighbors efficiently, NCVis employs Hierarchical Navigable Small World (HNSW) graphs, one of the fastest methods for k-nearest neighbor searches. Furthermore, the NCE objective function is naturally suited for batch processing. This allows the algorithm to take full advantage of multi-core CPUs, scaling linearly with the number of available threads.

3. Experimental Evaluation

The authors validated NCVis using several benchmarks, including handwritten digits (MNIST), synthetic datasets, and a massive real-world text dataset.

3.1. Scalability and Performance

NCVis demonstrates blazing speed compared to traditional implementations. It processed the MNIST dataset in just 0.9 seconds, whereas standard t-SNE required nearly 30 seconds. In head-to-head tests against FIt-SNE, LargeVis, and UMAP, NCVis consistently allowed for processing more than double the number of samples in the same amount of time, successfully visualizing 1 million points in approximately six minutes.

3.2. Large-Scale Semantic Visualization

To demonstrate real-world utility, the authors applied NCVis to the "News Headlines of India" dataset, containing over 2 million headlines. Using word embeddings to represent text snippets as high-dimensional vectors, NCVis successfully grouped headlines into semantically coherent clusters in less than 15 minutes. For example, the algorithm identified distinct clusters for "medicine" (including headlines about transplants) and "legal" affairs.

Visualization of 2 million news headlines using NCVis, showing semantically coherent clusters such as legal and entertainment news.

3.3. Visualization Quality

A key insight of the paper is that as the "noise ratio" increases, the NCE objective converges to the same result as Maximum Likelihood Estimation. This means NCVis can replicate the behavior of t-SNE without the associated computational cost. As shown in the benchmark scatter plots, NCVis maintains excellent cluster separation and global structure.

Scatter plot showing the clear separation of clusters achieved by NCVis on benchmark data, demonstrating quality comparable to t-SNE.

4. Conclusion

NCVis provides a powerful new tool for researchers dealing with massive, unlabeled datasets. By combining the statistical rigor of NCE with high-performance graph algorithms, it enables the visualization of millions of data points on standard hardware. While currently CPU-based, future transitions to GPU acceleration could further enhance its performance, making real-time visualization of even larger datasets a reality.

Summary updated

Abstract

Modern methods for data visualization via dimensionality reduction, such as t-SNE, usually have performance issues that prohibit their application to large amounts of high-dimensional data. In this work, we propose NCVis -- a high-performance dimensionality reduction method built on a sound statistical basis of noise contrastive estimation. We show that NCVis outperforms state-of-the-art techniques in terms of speed while preserving the representation quality of other methods. In particular, the proposed approach successfully proceeds a large dataset of more than 1 million news headlines in several minutes and presents the underlying structure in a human-readable way. Moreover, it provides results consistent with classical methods like t-SNE on more straightforward datasets like images of hand-written digits. We believe that the broader usage of such software can significantly simplify the large-scale data analysis and lower the entry barrier to this area.
BibTeX
@inproceedings{artemenkov2020ncvis,
  author = {Aleksandr Artemenkov and Maxim Panov},
  title = {{NCVis: Noise Contrastive Approach for Scalable Visualization}},
  booktitle = {The Web Conference},
  year = {2020},
  url = {https://openreview.net/forum?id=Hhlh7ifHnN},
}
Figure