netcl wiki
api

netcl.cluster: Clustering & Graph Algorithms

netcl.cluster: Clustering & Graph Algorithms

The netcl.cluster module provides hardware-accelerated clustering and graph partitioning algorithms on OpenCL devices. GPU kernels evaluate distance metrics and argmin reductions in a single pass. Large intermediate distance matrices are never allocated in VRAM, preserving memory for high-dimensional representations.

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

1. Quick Example: KMeans and Spectral Clustering

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
X = Tensor.from_host(q, np.random.randn(1000, 64).astype(np.float32))

# 1. GPU-accelerated KMeans
km = cluster.KMeans(n_clusters=8, seed=0).fit(X)
labels = km.labels_

# 2. Graph-based Spectral Clustering with k-NN affinity graph
sc = cluster.SpectralClustering(n_clusters=4, n_neighbors=10, affinity="knn").fit(X)

2. Algorithm Overview

Class Distance Metric / Mechanism Target Application
KMeans Euclidean (L2) Standard clustering of spherical point clouds
MiniBatchKMeans Euclidean (Streaming batches) Datasets that exceed available GPU VRAM
SphericalKMeans Cosine Distance (L2-normalized) Embeddings from language models or SSL vision
BalancedKMeans Sinkhorn Equipartition Pseudo-labels for deep learning preventing cluster collapse
GaussianMixture Diagonal Covariance (Log-space) Soft probabilistic cluster memberships
DBSCAN Density-based ($O(N)$ VRAM) Unknown cluster count, noise/outlier filtering (-1)
SpectralClustering k-NN Graph + LOBPCG Non-convex geometries, concentric rings, manifolds

Geometric Clustering: Distance Partitions vs Density Reachability

3. SpectralClustering (Graph-Based Clustering)

Constructs a $k$-Nearest Neighbors ($k$-NN) graph and computes spectral graph decomposition to separate non-linear cluster manifolds.

from netcl.cluster import SpectralClustering

sc = SpectralClustering(
    n_clusters=4,         # Number of target clusters
    n_neighbors=10,       # Number of neighbors per node in k-NN graph
    affinity="knn",       # "knn" with local density scaling or "rbf"
    n_power_iter=200,     # Maximum iterations for LOBPCG eigensolver
    seed=0,
)
sc.fit(X)

labels = sc.labels_       # NumPy int32 array of shape (N,)
coords = sc.embedding_    # Spectral coordinates of shape (N, n_clusters)

Graph Execution Pipeline

  1. k-NN Graph with Local Density Scaling: Rather than using a rigid global Gaussian bandwidth, netcl scales edge weights by local density:

$$W_{ij} = \exp\left(-\frac{\text{dist}(x_i, x_j)^2}{\sigma_i \cdot \sigma_j}\right)$$

Where $\sigma_i$ is the Euclidean distance from sample $i$ to its $k$-th nearest neighbor. The matrix is symmetrized via $W = \max(W, W^T)$.

  1. Normalized Graph Laplacian: Using degree vector $d = W\mathbf{1}$, the normalized affinity operator is formed:

$$A = D^{-1/2} W D^{-1/2}$$

  1. GPU-Accelerated LOBPCG Eigensolver: Finds the leading eigenvectors of $A$. All compute-heavy sparse matrix-vector multiplications execute on the GPU, while the small $(3K \times 3K)$ Rayleigh-Ritz subproblem is solved on the host CPU. Embeddings are normalized onto the unit hypersphere and clustered via KMeans.

4. KMeans

Classical Lloyd algorithm featuring k-means++ seeding and empty-cluster reseeding.

from netcl.cluster import KMeans

km = KMeans(
    n_clusters=8,
    init="k-means++",
    n_init=1,
    max_iter=100,
    tol=1e-4,
    seed=0,
)
km.fit(X)

# Fitted attributes
labels = km.labels_           # int32 cluster assignments
centers = km.cluster_centers_ # Centroid tensor of shape (n_clusters, D)
inertia = km.inertia_         # Sum of squared distances to closest centroid

# Assign new samples
new_labels = km.predict(new_X)

5. SphericalKMeans & BalancedKMeans

SphericalKMeans (Cosine Similarity)

Projects all vectors onto the unit sphere and optimizes cosine similarity. Ideal for normalized embeddings where angular direction represents semantic content:

from netcl.cluster import SphericalKMeans

skm = SphericalKMeans(n_clusters=16, seed=0).fit(embeddings)
labels = skm.labels_

BalancedKMeans (Equipartition Constraints)

Prevents cluster collapse by enforcing that every cluster contains approximately $\frac{N}{K}$ samples using the Sinkhorn-Knopp optimal transport algorithm:

from netcl.cluster import BalancedKMeans

bkm = BalancedKMeans(n_clusters=10, max_iter=50, eps=0.05, seed=0).fit(X)
pseudo_labels = bkm.labels_

6. GaussianMixture

Expectation-Maximization (EM) algorithm for Gaussian Mixture Models with diagonal covariance in log-space:

from netcl.cluster import GaussianMixture

gmm = GaussianMixture(
    n_components=5,
    max_iter=100,
    tol=1e-4,
    init="kmeans",
    seed=0,
).fit(X)

hard_labels = gmm.predict(X)            # Discrete cluster assignment
probs = gmm.predict_proba(X)            # Soft posterior probabilities (N, K)
bic = gmm.bic(X)                        # Bayesian Information Criterion for model selection

7. DBSCAN

Density-based clustering with automated cluster discovery and outlier detection:

from netcl.cluster import DBSCAN

db = DBSCAN(eps=0.5, min_samples=5, metric="euclidean").fit(X)

labels = db.labels_       # -1 designates noise / outlier points
n_clusters = db.n_clusters_
core_points = db.core_sample_indices_

8. Evaluation Metrics (netcl.cluster.metrics)

from netcl.cluster import (
    silhouette_score,
    davies_bouldin_score,
    cluster_report,
)

# Unsupervised metrics (without ground-truth labels)
sil = silhouette_score(X, km.labels_)
db = davies_bouldin_score(X, km.labels_)

# Supervised evaluation (against validation ground truth y_true)
print(cluster_report(y_true, km.labels_, X))