netcl wiki
concepts

Clustering & Graph Partitioning

Clustering & Graph Partitioning

Located at: netcl.cluster (Algorithms: kmeans.py, spectral.py, gmm.py, dbscan.py, Kernels: ops.py)

GPU-accelerated clustering serves a critical engineering purpose: partitioning and analyzing large sets of high-dimensional representations (e.g. 512-dimensional image embeddings from a ResNet or dense text embeddings) directly within GPU device memory, completely bypassing CPU memory bandwidth bottlenecks.

Traditional libraries like Scikit-learn allocate intermediate matrices in host RAM, hitting severe PCIe bandwidth limits. netcl.cluster executes distance calculations, neighbor searches, and assignments directly within optimized OpenCL GPU kernels.

[!TIP] Theory & Curriculum Link: For the first-principles geometric derivations of Voronoi partitions, fused distance-argmin execution, and Graph Laplacians, see Curriculum: Clustering & Geometry and Curriculum: Spectral Graph Theory.

Algorithm Selection Guide

Use Case Recommended Algorithm Distance Metric / Mechanism Core Advantage
Standard Clustering with known cluster count $K$ KMeans Euclidean (L2) Ultra-fast with k-means++ seeding and fused argmin
Dataset exceeds GPU VRAM capacity MiniBatchKMeans Euclidean (Streaming mini-batches) Clusters millions of samples in chunks
Feature vectors from SSL or NLP SphericalKMeans Cosine Distance (L2-normalized) Measures direction and orientation, ignoring magnitude
Generating pseudo-labels for training (DeepCluster / SwAV) BalancedKMeans Sinkhorn Equipartition Prevents cluster collapse where one cluster swallows all points
Clusters have complex, non-convex shapes (rings, manifolds) SpectralClustering k-NN Affinity Graph + LOBPCG Maps graph topology into linearly separable eigenspaces
Unknown $K$ and dataset contains noise and outliers DBSCAN Density-based ($\epsilon$-neighborhoods) Marks noise as -1 and scales with linear $O(N)$ VRAM
Requiring soft posterior probabilities per cluster GaussianMixture EM with diagonal covariance Provides calibrated probabilistic cluster memberships

1. Quick Example: GPU KMeans

import numpy as np
from netcl import cluster
from netcl.core.device import manager
from netcl.core.tensor import Tensor

q = manager.default("auto").queue

# 1. Prepare data (e.g. 10,000 embeddings of dimension 128)
X_np = np.random.randn(10000, 128).astype(np.float32)
X = Tensor.from_host(q, X_np)

# 2. Configure and fit KMeans
km = cluster.KMeans(
    n_clusters=10,
    init="k-means++",
    max_iter=50,
    seed=42,
).fit(X)

# 3. Retrieve results
labels = km.labels_           # NumPy int32 array of cluster assignments (0 to 9)
centers = km.cluster_centers_ # Tensor of shape (10, 128)
inertia = km.inertia_         # Sum of squared distances to closest centroid

# 4. Predict cluster assignments for new data points
new_samples = Tensor.from_host(q, np.random.randn(5, 128).astype(np.float32))
new_labels = km.predict(new_samples)
print("Assigned clusters for new samples:", new_labels)

Why NetCL is Memory-Efficient

Classical KMeans minimizes the Within-Cluster Sum of Squares (WCSS):

$$\min_{\mathcal{C} = \{\mathbf{c}_1, \dots, \mathbf{c}_K\}} \sum_{i=1}^N \min_{k=1, \dots, K} \|\mathbf{x}_i - \mathbf{c}_k\|_2^2$$

Standard implementations materialize an $(N \times K)$ distance matrix in VRAM. For $N = 100,000$ points and $K = 1,000$ clusters, that consumes 400 MB of VRAM for temporary distance values. At $N = 1,000,000$, it consumes 4 GB.

netcl.cluster.ops employs a Fused Distance-Argmin Kernel: - Each GPU thread loads sample $\mathbf{x}_i \in \mathbb{R}^D$, streams through centroids $\mathbf{c}_k$, and tracks the running minimum distance directly inside private GPU registers. - The $(N \times K)$ matrix is never written to global VRAM. - Centroids are accumulated via a single atomic reduction directly in device buffers.

2. Spectral Clustering & Graph Manifolds

When clusters form nested spirals, rings, or continuous manifolds, KMeans fails because it cannot draw non-linear boundaries. SpectralClustering constructs a neighborhood affinity graph and embeds data into the eigenvectors of the Graph Laplacian.

# Spectral clustering over a k-NN affinity graph
sc = cluster.SpectralClustering(
    n_clusters=3,
    n_neighbors=15,       # Connect each point to its 15 nearest neighbors
    affinity="knn",       # k-NN graph with Zelnik-Manor local density scaling
    seed=42,
).fit(X)

cluster_labels = sc.labels_
embedding = sc.embedding_  # (N, n_clusters) spectral coordinates

The Spectral Pipeline

  1. k-NN Graph with Local Density Scaling: Rather than using a fixed global bandwidth, edge weights adapt to local neighborhood density:

$$\mathbf{W}_{ij} = \exp\left(-\frac{\|\mathbf{x}_i - \mathbf{x}_j\|_2^2}{\sigma_i \cdot \sigma_j}\right)$$

Where $\sigma_i$ is the Euclidean distance from $\mathbf{x}_i$ to its $k$-th nearest neighbor. Edges are symmetrized via $\mathbf{W} = \max(\mathbf{W}, \mathbf{W}^T)$.

  1. Normalized Symmetric Laplacian:

$$\mathbf{L}_{\text{sym}} = \mathbf{I} - \mathbf{D}^{-1/2} \mathbf{W} \mathbf{D}^{-1/2}$$

Where $\mathbf{D}_{ii} = \sum_j \mathbf{W}_{ij}$ is the degree matrix.

  1. GPU LOBPCG Eigensolver: Standard power iteration requires thousands of steps when eigenvalues cluster tightly. NetCL employs LOBPCG (Locally Optimal Block Preconditioned Conjugate Gradient):

    • All compute-heavy sparse matrix-vector multiplications run on the GPU.
    • Only the tiny $(3K \times 3K)$ Rayleigh-Ritz subproblem is solved on the host.
    • Typically converges in fewer than 150 iterations even on poorly conditioned graphs.

3. Balanced K-Means (Optimal Transport Equipartition)

When clustering representations in self-supervised pipelines (e.g. DeepCluster), standard KMeans often suffers from cluster collapse: 90% of data points fall into a single dominant cluster while others become empty.

BalancedKMeans enforces an equipartition constraint via the Sinkhorn-Knopp algorithm, solving an entropy-regularized optimal transport problem:

$$\min_{\mathbf{P} \in \mathcal{U}(\mathbf{r}, \mathbf{c})} \langle \mathbf{P}, \mathbf{M} \rangle - \varepsilon H(\mathbf{P})$$

Where $\mathbf{M}_{ik} = \|\mathbf{x}_i - \mathbf{c}_k\|_2^2$ is the cost matrix, and marginal constraints $\mathbf{r} = \frac{1}{N} \mathbf{1}_N$ and $\mathbf{c} = \frac{1}{K} \mathbf{1}_K$ guarantee that every cluster receives exactly $\frac{N}{K}$ samples.

# Guarantees that every cluster receives approximately N / K samples
bkm = cluster.BalancedKMeans(
    n_clusters=10,
    max_iter=50,
    eps=0.05,
    seed=42,
).fit(X)

pseudo_labels = bkm.labels_

4. Density-Based Clustering: DBSCAN

When cluster count $K$ is unknown or the dataset contains noisy outliers:

db = cluster.DBSCAN(
    eps=0.4,              # Neighborhood search radius
    min_samples=5,        # Minimum neighbors to qualify as a core point
    metric="euclidean",   # Or "cosine"
).fit(X)

labels = db.labels_       # -1 designates noise / outlier points
n_clusters = db.n_clusters_
print(f"Identified clusters: {n_clusters}, Noise points: {(labels == -1).sum()}")

5. Evaluating Cluster Quality

# Intrinsic evaluation (without ground-truth labels)
sil = cluster.silhouette_score(X, km.labels_)
db_score = cluster.davies_bouldin_score(X, km.labels_)
print(f"Silhouette Score: {sil:.3f} | Davies-Bouldin Index: {db_score:.3f}")

# Supervised evaluation against validation targets
report = cluster.cluster_report(y_true, km.labels_, X)
print(report)

The Silhouette coefficient $s(i)$ for sample $\mathbf{x}_i$ measures the ratio of intra-cluster distance $a(i)$ to nearest inter-cluster distance $b(i)$:

$$s(i) = \frac{b(i) - a(i)}{\max(a(i), b(i))} \in [-1, +1]$$

cluster_report computes Normalized Mutual Information (NMI), Adjusted Rand Index (ARI), Purity, and Hungarian-matched unsupervised classification accuracy.