ncvis

NCVis

A Rust implementation of the Noise Contrastive Visualization (NCVis) algorithm, a high-performance technique for dimensionality reduction and data visualization.

This implementation is based on the paper "NCVis: Noise Contrastive Approach for Scalable Visualization" by Aleksandr Artemenkov and Maxim Panov (WWW '20).

Algorithm Overview

NCVis uses Noise Contrastive Estimation (NCE) to learn low-dimensional embeddings. Unlike t-SNE which requires computing a global normalization constant at each step, NCVis treats the normalization constant as a learnable parameter Q, enabling efficient parallel batch optimization (see paper Section 3.2).

The algorithm proceeds in three phases:

1. KNN Graph Construction - O(N^2): Finds k-nearest neighbors using GPU-accelerated computation, then symmetrizes the graph.
2. Spectral Initialization - O(kN): Power iteration on the neighbor graph adjacency matrix to place connected points near each other.
3. NCE Optimization - O(kN) per epoch: For each neighbor edge (positive sample), attracts the connected points while repelling randomly sampled non-neighbors (negative samples). The NCE objective balances fitting the data distribution against distinguishing it from noise (see paper Section 3.1).

Usage

The main entry point is the NCVisBuilder, which allows you to configure the algorithm's parameters and then run the embedding process.

use ncvis::NCVisBuilder;
use ndarray::Array2;

// Create some sample high-dimensional data
let n_points = 1000;
let n_dims = 50;
let mut rng = fastrand::Rng::with_seed(42);
let data = Array2::from_shape_simple_fn((n_points, n_dims), || rng.f32());

// Configure and run the NCVis algorithm
let ncvis = NCVisBuilder::new()
    .n_neighbors(15)
    .n_epochs(50)
    .wgpu()
    .expect("Failed to build NCVis");

let embedding = ncvis.fit_transform(&data.view())
    .expect("Failed to compute embedding");

assert_eq!(embedding.shape(), &[n_points, 2]);
println!("Successfully created a 2D embedding!");