PaperlayerView exact revision on arXiv

Source-linked AI summary

HDLouvain: High-Throughput Incremental Clustering for Hyperdimensional Data

Beenish Gul, Mahbod Afarin, Farhat Ahmed, Sumukh Pinge, Tsung-Han Lu, Tajana Rosing, Kevin Skadron

arXiv:2610.30687v1cs.AR

TL;DR

At repository scale, spectral clustering is a data-management bottleneck, and existing approaches do not provide both principled cluster discovery and incremental assignment. HDLouvain uses Louvain to discover bootstrap communities and binary hypervectors for online assignment. Across the reported datasets, its bootstrap fraction tunes a monotonic throughput–fidelity trade-off, with modularity remaining within 8% of full static recomputation.

  • Problem

    At repository scale, dense all-pairs comparison is infeasible, while scalable HDC methods lack principled cluster discovery and existing tools require batch data or repeated clustering.

    Source: §I · p. 1

  • Method

    HDLouvain runs Louvain once on a bootstrap fraction, bundles each community into a binary representative, and assigns later spectra against bucket-local representatives.

    Source: §I · p. 2

  • Results

    Across five datasets, HDLouvain’s speedup and modularity vary monotonically with α, while modularity never falls more than 8% below full static recomputation.

    Source: §I · p. 2

  • Takeaways & Limitations

    The bootstrap fraction α provides a tunable throughput–fidelity trade-off, with online assignment cost set by the bucket’s representatives rather than stream volume.

    Source: §I · p. 2

    The paper does not claim that binary HDC outperforms quantized representations; it presents binary encoding as an operational design choice.

    Source: C. Hyperdimensional Computing · p. 3

Abstract

from arXiv · show

Modern shotgun proteomics generates tens of thousands of tandem mass spectra per hour, producing hundreds of gigabytes of data that strain conventional clustering pipelines. DBSCAN and hierarchical agglomerative clustering (HAC) offer flexible similarity search, but DBSCAN is unstable across varying data densities, HAC costs $O(n^2)$, and both yield poor cluster quality. Graph-based methods such as Louvain produce high-quality clusters but scale poorly on streaming data. We observe that Louvain's poor scalability can be resolved without sacrificing its quality, and present HDLouvain, which combines Louvain community detection with the bit-parallel similarity computation of hyperdimensional computing (HDC). HDLouvain partitions a bootstrap fraction of the stream into precursor-mass buckets, applies Louvain to each bucket's kNN similarity graph, and condenses each community into a single binary hypervector by bitwise-majority bundling rather than iterative centroid recomputation. New spectra are assigned by a GPU-accelerated Hamming distance lookup against representatives in their mass bucket, or seed a new cluster when no match meets a similarity threshold $\tau$, so the partition grows incrementally without full re-clustering. On five PRIDE datasets (0.99M to 21.13M spectra), sweeping the bootstrap fraction $\alpha$ from 0.2 to 0.9 exposes an explicit, monotonic throughput-fidelity trade-off. On PXD003258, speedup ranges from 4.5x at $\alpha=0.3$ to 1.65x at $\alpha=0.7$. Modularity rises from 0.75-0.76 at $\alpha=0.2$ to 0.95-0.97 at $\alpha=0.9$, never more than 8% below full static recomputation. The Louvain stage achieves 0.86-0.93 normalized mutual information (NMI) on LFR benchmark networks with 30k to 2M nodes, whereas DBSCAN and HAC degrade to 0.57.

I. INTRODUCTION

HDLouvain combines Louvain community detection with hyperdimensional computing to address the scale and streaming limits of spectral clustering. Its bootstrap fraction α exposes a throughput–fidelity trade-off while later spectra are assigned without full re-clustering.

I. INTRODUCTION

  • Clustering is a growing bottleneck as spectral data volumes and submission rates increase.Mass spectrometers produce tens of thousands of tandem spectra per hour, and clustering itself has emerged as the primary bottleneck as data generation outpaces compute resources.Source: §I · p. 1
  • At repository scale, dense all-pairs comparison is infeasible, while existing high-quality graph methods scale poorly and fast HDC methods lack principled cluster discovery.Continuous acquisition also makes repeated batch clustering costly; existing scalable HDC tools are static, and Louvain requires rebuilding the graph or using dynamic variants that still recompute per batch.Source: §I · pp. 1–2
  • Online spectra are bucketed by precursor mass and matched against bucket-local representatives, or seed a new cluster when no match is found.The pipeline uses XOR/popcount matching against representatives in the same bucket, avoiding a full re-clustering pass.Source: Figure 1 · p. 2, §I · p. 2
  • HDLouvain separates one-time cluster discovery from incremental assignment, bundling each Louvain community into a single binary representative after the bootstrap.Unlike k-means or HAC-based pipelines, it does not recompute representatives as the stream grows; online cost depends on the bucket’s representative set rather than accumulated volume.Source: §I · p. 2
  • 3.21× over static Louvain at a 50/50 bootstrap/incremental split and 4.5× at 30/70 on four evaluated datasets characterize HDLouvain’s throughput gains.Across five datasets spanning 0.99 M to 21.13 M spectra, α acts as a monotonic throughput–fidelity knob; modularity rises from 0.75–0.76 at 20% bootstrap to 0.95–0.97 at 90%, never more than 8% below full static recomputation.Source: §I · p. 2

II. BACKGROUND AND MOTIVATION

Mass-spectrometry clustering reduces redundant spectra and supports downstream identification, but clustering at repository scale remains expensive and existing accelerated approaches are batch-oriented. Louvain provides graph-based communities by optimizing modularity, though its heuristic partitions have no optimality guarantee.

A. Mass Spectrometry Clustering

  • Clustering groups spectra from the same peptide so downstream database searching can use a representative spectrum, while unidentified spectra can benefit from association with identified neighbors.Cluster patterns can also help correct identification errors and detect modified peptides or outliers.Source: A. Mass Spectrometry Clustering · p. 3
  • Accelerated clustering approaches reduce comparisons but remain batch procedures, motivating incremental clustering for continuously growing repositories.State-of-the-art tools can still take hours to days, negating acquisition speed gains.Source: A. Mass Spectrometry Clustering · p. 3

B. Louvain Algorithm

  • Louvain greedily optimizes modularity by merging nodes into communities that yield the greatest gain, and runs essentially linearly in the number of edges.Modularity measures connection density within communities versus outside and does not require ground-truth labels.Source: B. Louvain Algorithm · p. 3
  • Louvain is a heuristic with no optimality guarantee, and different node orderings can produce different partitions.Modularity maximization is NP-hard; Leiden repairs Louvain’s tendency to produce internally disconnected communities, but adds passes at each level.Source: B. Louvain Algorithm · p. 3

C. Hyperdimensional Computing

HDLouvain combines Louvain community detection with HDC’s binary hypervectors to support incremental clustering. Spectra are encoded as fixed-length vectors, and online assignments compare them with cluster representatives.

C. Hyperdimensional Computing

  • HDC represents information as high-dimensional binary hypervectors manipulated with XOR, bundling, and permutation.These operations are bit-parallel across thousands of dimensions and are described as efficient on modern hardware and noise-tolerant through distributed representation.Source: C. Hyperdimensional Computing · p. 3

III. HDLOUVAIN DESIGN

  • HDLouvain integrates Louvain community detection with HDC, while CPU preprocessing and bucketing are separated from GPU encoding, distance computation, and online assignment.The framework is governed by the bootstrap fraction α, neighborhood size k, hypervector dimension D, and assignment threshold τ.Source: §III · p. 3

A. Spectrum Preprocessing

  • Preprocessing filters peaks, retains the N most intense remaining peaks, then square-root transforms and L2-normalizes intensities.These steps are applied independently per spectrum, making preprocessing embarrassingly parallel.Source: A. Spectrum Preprocessing · p. 3

III. HDLOUVAIN DESIGN

  • The offline phase uses a bootstrap prefix, sorts its spectra by precursor m/z, and bundles communities into representative hypervectors.The bootstrap fraction α controls the offline/online split.Source: §III · p. 3, A. Spectrum Preprocessing · p. 4
  • Online spectra join a representative’s cluster when their distance is at most τ; otherwise, they open a new cluster.The representative is not updated by the assignment, and an uninitialized bucket opens a new cluster.Source: A. Spectrum Preprocessing · p. 4

A. Spectrum Preprocessing

  • ID–Level encoding binds bin-identity and quantized-intensity hypervectors with XOR, then bundles occupied bins into a binary spectrum vector.Nearby m/z bins receive correlated level hypervectors, so small mass shifts produce small Hamming distances; the reported settings are D = 2048, N = 50, δm/z = 0.05, and a fragment window of [101 m/z, 1500 m/z].Source: A. Spectrum Preprocessing · p. 4

B. Precursor-Mass Bucketing

Precursor-mass bucketing confines pairwise comparisons to mass-compatible spectra, reducing the offline clustering burden. Its non-overlapping boundaries can nevertheless separate spectra from the same peptide.

B. Precursor-Mass Bucketing

  • Bucketing removes cross-bucket pairwise comparisons, reducing the memory footprint and computation needed to make offline clustering tractable at repository scale.The design targets the dense O(n^2) distance matrix induced by all-pairs comparison.Source: B. Precursor-Mass Bucketing · p. 4
  • Eq. (2) places bucket edges in gaps between physically possible peptide-mass centers and maps reported values in constant time.The divisor reflects average spacing between tryptic peptide-mass cluster centers; spectra of the same peptide can still be separated if measured masses straddle a gap.Source: B. Precursor-Mass Bucketing · p. 4
  • Non-overlapping buckets can split otherwise identical spectra near an edge because of mass error or isotope-assignment mistakes, fragmenting a true cluster.Overlapping buckets are described as a remedy, but the reported results use non-overlapping buckets and leave residual boundary loss for future quantification.Source: B. Precursor-Mass Bucketing · p. 4
  • The k-NN graph uses normalized Hamming distances and partial selection to find each vertex’s k nearest neighbors without fully sorting the distance row.Introselect takes O(|V|) time rather than O(|V| log |V|) for sorting.Source: C. k-NN Graph Construction · pp. 4–5
  • Edge weights use one minus normalized distance, so greater similarity receives greater weight for modularity optimization.Using distance directly would give the greatest weight to the most dissimilar pair and invert the objective.Source: C. k-NN Graph Construction · p. 5

D. Community Detection

HDLouvain applies Louvain to each bucket’s k-NN graph to obtain communities by heuristic modularity optimization. The choice accommodates unknown cluster counts and skewed cluster sizes, unlike balanced partitioning.

D. Community Detection

  • Louvain avoids HAC’s quadratic time and space and DBSCAN’s difficult density parameters, while K-means requires a preset cluster count and assumes spherical, equally sized clusters.The passage frames these properties as impractical when the number and geometry of peptide groups are unknown.Source: D. Community Detection · p. 5
  • Louvain heuristically partitions each bucket’s k-NN graph into disjoint, exhaustive communities that maximize modularity.The reported partition is Louvain’s greedy result, not a global optimum, because modularity maximization is NP-hard.Source: D. Community Detection · p. 5
  • Balanced partitioning is a poor fit because peptide counts are unknown and cluster sizes are strongly skewed, while balance constraints could penalize the correct partition.Very large communities may also make bundling more expensive and their representatives less discriminative.Source: D. Community Detection · p. 5

E. Cluster Representatives

HDLouvain converts each Louvain community into a binary representative that online spectra can compare against. The representative is computed once by bitwise-majority bundling and then frozen.

E. Cluster Representatives

  • Each community’s representative is its members’ bitwise-majority hypervector, with ties at even community sizes resolved to 0.Bundling is performed once at the end of the offline phase.Source: E. Cluster Representatives · p. 5
  • A representative is computed once from the Louvain partition and frozen, avoiding iterative prototype recomputation as spectra arrive.The paper notes this is still a centroid computation, not a centroid-free method.Source: E. Cluster Representatives · p. 5
  • Within a query’s mass bucket, Hamming distances to active representatives identify the nearest cluster; the example joins Cluster 2 at 1 bit.Representatives in other buckets are not compared.Source: Figure 2 · p. 6
  • Frozen representatives keep online cost independent of spectra already ingested, but cannot track membership drift during long acquisitions.Periodic re-bundling could address drift at some throughput expense.Source: E. Cluster Representatives · p. 6

F. Online Incremental Assignment

Each arriving spectrum is routed to its precursor-mass bucket, encoded, and compared only with that bucket’s active representatives. A threshold determines whether it joins the nearest representative or opens a new cluster.

F. Online Incremental Assignment

  • A query is routed using its precursor m/z and charge, then compared only with representatives active in that bucket.Routing requires no comparison against stored data.Source: F. Online Incremental Assignment · p. 6
  • Bit-packed hypervectors let CUDA XOR and popcount evaluate Hamming distance in O(D/32) rather than O(D), a 32-fold reduction per distance.All Rb representatives in a bucket are evaluated in one GPU kernel launch with a parallel arg-min reduction.Source: F. Online Incremental Assignment · p. 6
  • A spectrum joins its nearest representative when normalized Hamming distance is at most τ; otherwise, it opens a new cluster.τ is the online phase’s only parameter and sets the cluster count: tighter values fragment clusters, while looser values merge distinct peptides.Source: F. Online Incremental Assignment · p. 6

G. Complexity Analysis

Mass bucketing confines the quadratic distance-matrix work to individual buckets, while approximate-neighbor indexing could further reduce the remaining cost. Louvain and bundling add near-linear work in the stated analysis.

G. Complexity Analysis

  • The offline phase is dominated by per-bucket distance matrices, which remain quadratic in bucket occupancy rather than total spectra.The passage defines n as total spectra and nb as bucket b’s occupancy.Source: G. Complexity Analysis · p. 6
  • For roughly balanced buckets, intra-bucket distance matrices cost O(n^2D/(32B)), a factor-B reduction over global all-pairs comparison.With B on the order of 10^3–10^4, the passage estimates a three-to-four-order-of-magnitude reduction.Source: G. Complexity Analysis · p. 6
  • Louvain contributes O(kn), bundling a linear pass over the bootstrap set, and sorting by precursor m/z costs O(n log n); neither is the bottleneck described.The distance-matrix term dominates these costs.Source: G. Complexity Analysis · p. 6
  • LSH and ANN can attack the residual quadratic term with sub-quadratic behavior, while bucketing is exact within each bucket and avoids hash collisions and recall loss.The paper describes combining these candidate-generation approaches with the Louvain-then-bundle-then-assign core as possible.Source: G. Complexity Analysis · p. 6

H. Design Rationale

HDLouvain separates one-time cluster discovery from incremental assignment against binary representatives, avoiding full-dataset re-clustering. The evaluation covers runtime, synthetic-network quality, and sensitivity to the offline/online split across five PRIDE datasets.

H. Design Rationale

  • Louvain discovers high-modularity partitions on the bootstrap fraction, after which bit-parallel XOR and popcount assign arrivals against bucket representatives.The assignment cost is set by D and the number of active representatives in the bucket.Source: H. Design Rationale · p. 6
  • The initial partition serves as a structural prior rather than being recomputed from scratch; α tunes the fidelity-runtime trade-off, and unmatched spectra open new clusters.The passage says the trade-off is monotonic in α and can be dialed to a target.Source: H. Design Rationale · p. 6

IV. EVALUATION

  • Evaluation measures runtime against static Louvain, LFR-ground-truth clustering quality, and sensitivity to the split ratio α..Source: §IV · pp. 6–7

A. Datasets and Experimental Setup

  • The study uses five PRIDE datasets spanning roughly 9.9 × 10^5 to 2.1 × 10^7 spectra, from 11 GB to 141 GB on disk.The experiments use an RTX 4090 workstation, and the static baseline uses identical preprocessing, encoding, bucketing, and graph-construction code on all spectra.Source: A. Datasets and Experimental Setup · p. 7

B. Runtime Evaluation

Louvain provides stronger LFR community recovery than DBSCAN and HAC, while HDLouvain reduces runtime relative to static Louvain, especially on larger datasets. The evaluations also show how speedup varies with dataset size and the offline/online split.

C. Clustering Quality Evaluation

  • Louvain scores 0.86–0.93 NMI, while DBSCAN and HAC fall to roughly 0.57; at 100k nodes and above, their ARI drops to 0.002–0.009 versus Louvain’s 0.33–0.61.Fig. 3 compares NMI and ARI against LFR ground truth; Fig. 4 presents the corresponding percentage improvements.Source: Figure 3 · p. 7, Figure 4 · p. 7, C. Clustering Quality Evaluation · p. 8

B. Runtime Evaluation

  • At the 50/50 split, HDLouvain speedup rises from 1.01× on the smallest dataset to 3.21× on the largest, while static Louvain runtime grows from roughly 34 seconds to over 10,000 seconds.Table II reports the five-dataset runtime comparison; at scale, offline graph construction and community detection increasingly dominate the online phase.Source: B. Runtime Evaluation · p. 7, Table II · p. 8
  • On the four-dataset split sweep, speedup peaks at 30/70, reaching 4.5× on PXD003258; the two smaller datasets fall below break-even as the offline fraction approaches 0.7.The two near-1-million-spectrum datasets have little headroom to amortize setup costs, while multi-million-spectrum workloads are recommended for HDLouvain.Source: B. Runtime Evaluation · p. 7, Figure 6 · p. 8

D. Sensitivity to the Offline/Online Split Ratio

The offline fraction α controls a monotonic trade-off: larger bootstraps improve modularity but reduce speedup. The preferred split therefore depends on the quality budget and dataset scale.

D. Sensitivity to the Offline/Online Split Ratio

  • Speedup falls monotonically as α increases, peaking at 30/70 with 4.5× on PXD003258 and 3.43× on PXD001511; the two smaller datasets fall below break-even near 70/30.The offline phase grows with α, while online runtime stays nearly flat.Source: D. Sensitivity to the Offline/Online… · p. 8, Figure 7 · p. 9
  • At 20/80, modularity is 0.75–0.76; at 90/10, it rises to 0.95–0.97 across four datasets, within 0.02 of static Louvain at 70/30.The wider quality sweep shows modularity rising monotonically with the offline fraction.Source: Figure 8 · p. 9, D. Sensitivity to the Offline/Online… · p. 9
  • For multi-million-spectrum datasets, α ≥0.7 retains 1.45× and 1.65× speedups while bringing modularity within about 7% of static Louvain; α ∈[0.3, 0.5] yields 2.17× to 4.5× speedups when coarser partitions suffice.The suggested split depends on the application's quality budget; smaller datasets fall below break-even at high α.Source: D. Sensitivity to the Offline/Online… · p. 9

V. RELATED WORK

Prior clustering approaches address scale through greedy, hierarchical, approximate-search, or incremental graph methods, but none combines incremental spectrum-level assignment with frozen Louvain communities. HDLouvain reports speedups over static Louvain across five datasets and identifies long-running cluster drift as future work.

V. RELATED WORK

  • Wang et al. scale batch-granularity clustering to 368 M spectra, while HDLouvain assigns spectra against frozen representatives without re-deriving per batch.HDLouvain complements approximate-search methods such as msCRUSH and Falcon, which reduce candidate counts rather than discovery frequency.Source: §V · p. 9
  • HDLouvain replaces random HDC prototypes with bundled Louvain communities as long-lived representatives, addressing the initialization sensitivity of prior HDC clustering applications.HyperSpec, SpecHD, RapidOMS, and SmartMS are described as static and batch-oriented.Source: §V · p. 9
  • Incremental Louvain variants assume modest graph perturbations, whereas HDLouvain freezes offline communities and assigns new spectra using HDC similarity.Balanced (hyper)graph partitioning is described as mismatched to heavy-tailed distributions with unknown cluster counts.Source: §V · p. 9

VI. CONCLUSIONS

  • 3.21× over static Louvain at α = 0.5 across five datasets, with 4.5× at α = 0.3 on four swept datasets and 1.45–1.65× at α ≥0.7.The datasets span 0.99–21.13 M spectra; future work will explore periodic re-clustering and cleanup to bound drift and improve quality over long-running streams.Source: §VI · p. 9

Related papers

Loading 2610.30687v1…