GPU-Accelerated Construction of the Gabriel Graph: Parallelization Strategies and Applications to Large-Margin Classification and Graph-Based Clustering
Authors: Diego Sanches Nere dos Santos, Luiz Carlos Bambirra Torres
Organizations: Department of Computing and Systems, Institute of Exact and Applied Sciences, Federal University of Ouro Preto (UFOP), João Monlevade, MG, Brazil · Department of Computing, Institute of Exact and Biological Sciences, Federal University of Ouro Preto (UFOP), Ouro Preto, MG, Brazil
The Gabriel graph is a proximity graph widely used in computational geometry and geometric machine learning, underlying large-margin classifiers and, as we show in this work, density-aware clustering methods. Its construction, however, has cubic time complexity O(N3) in the naive formulation, which severely limits its use on datasets beyond a few thousand samples. This paper presents a set of GPU parallelization strategies, implemented in CUDA, that make Gabriel graph construction practical at scale. We introduce (i) an implicit closed-form mapping from a linear thread index to the corresponding vertex pair (i,j), which removes the need for an explicit O(N2) adjacency structure and lets every thread locate its pair in constant time and constant memory; (ii) a two-pass, bitmask-based, atomically-compacted edge-list construction that produces a dense edge array proportional only to the number of edges actually found; and (iii) a thread-coarsening strategy in which each thread evaluates several candidate pairs, trading launch and scheduling overhead against load balance. We evaluate these strategies on the acceleration of a Gabriel-graph-based large-margin classifier (NN-clas) and on a novel Gabriel-graph clustering algorithm that identifies connected components on a residual graph and performs GPU-parallel Union-Find with hierarchical edge-based merging. On 14 public benchmark datasets, the GPU implementation reduces Gabriel graph construction time by two to nearly four orders of magnitude relative to a sequential CPU baseline (up to 8484x), without loss of classification accuracy, and the proposed clustering method is statistically competitive with DBSCAN on the topological validity index Dunn while eliminating the need for an explicit density radius parameter.
Figures & tables
Figure 1: A Gabriel graph built on a synthetic two-class point set. Grey edges connect same-class neighbors; red edges are support edges joining points of different classes. The dashed circle illustrates the empty-hypersphere test of Eq. ( 1 ) for one admitted edge: no other point falls inside it.
Figure 2: Schematic illustration of the thread-coarsening trade-off in Gabriel graph construction: very fine granularity is dominated by kernel-launch and scheduling overhead, while very coarse granularity is dominated by load imbalance across threads. An intermediate “sweet spot” minimizes total execution time; measurements on two datasets, where the optimum turns out to be dataset-dependent, are reported in Section 6.3 .
Dataset
N
Feat.
Seq. (s)
Par. (s)
Speedup
Acc.
F1
Australian
690
14
10.3789
0.0026
3933.8×
0.8487
0.8250
BankNote
1372
4
15.1423
0.0022
6882.5×
0.9978
0.9970
Breast Cancer
683
9
4.4336
0.0019
2333.8×
0.9648
0.9730
BreastHess
133
30
0.4752
0.0009
558.6×
0.7879
0.8510
Bupa
345
6
0.5933
0.0008
742.1×
0.5916
0.5360
Climate
540
18
23.4760
0.0064
3665.6×
0.8870
0.9380
Table 1: Execution time, speedup, accuracy and F1-score: sequential vs. GPU-parallel Gabriel-graph classifier.
Figure 3: Execution time of Gabriel-graph-based classification, sequential (CPU) vs. GPU-parallel construction, log scale. Speedups range from 237× (Golub, N=72 ) to 8484× (German, N=1000 ).
Memory-efficient scaling on clustering problems without sacrificing statistical accuracy is of central interest for large-scale data analysis and machine learning problems. Nonnegative low-rank (NLR) matrix factorization for K-means is a scalable clustering method, which connects to semidefinite relaxations with optimal average-case exact recovery guarantees. However, a direct GPU implementation of NLR requires multiple large factor-sized buffers and substantial data movements that are essentially memory-bound. In this paper, we introduce GEM-KMeans, a spectrally normalized yet mathematically equivalent NLR formulation that fuses the gradient update, nonnegative projection, and sufficient statistics for normalization and iterate movement into a matrix-multiplication epilogue. Instead of retaining three massive factor-sized arrays, our IO-aware GPU implementation materializes only one single factor with small tile-reduction arrays as additional storage in the High Bandwidth Memory (HBM). We derive explicit memory costs and spectrally normalized smoothness bounds for optimizing the clustering objective function. Accurate clustering is demonstrated at massive scales on synthetic and real datasets, where performance gains of GEM-KMeans over existing GPU-accelerated Lloyd's algorithms involve data-dependent runtime tradeoffs.
Peng Xu, Nihar Koganti, Volodymyr Kindratenko +1
Department of Statistics, University of Illinois Urbana-Champaign · Department of Electrical and Computer Engineering, University of Illinois Urbana-Champaign · National Center for Supercomputing Applications, University of Illinois Urbana-Champaign +3
The stable coloring of the Weisfeiler-Leman (1-WL) test is a cornerstone of Graph Neural Networks because it provides an upper bound to the expressive power of message-passing architectures. Unfortunately, computing it presents two fundamental bottlenecks. First, classic algorithms are inherently sequential and cannot exploit modern massively parallel hardware. Second, these are global algorithms, i.e., they require availability in memory of the full graph, severely limiting applicability to real-world instances. We leverage a linear-algebraic interpretation of 1-WL stable coloring and introduce two key contributions: (i)~a randomized refinement algorithm with tight probabilistic guarantees and (ii)~a correctness-preserving batching scheme that decomposes the graph into independently processable subgraphs while provably returning a stable coloring of the original graph. This approach maps directly to GPU-efficient primitives. In numerical experiments, our CUDA implementation delivers speedups up to two orders of magnitude over classical CPU-based partition refinement and, for the first time, successfully computes stable colorings on web-scale graphs with over 30 billion edges, where CPU baselines time out or fail.
Filippo Biondi, Mirco Tribastone, Max Tschaikowski
IMT Lucca, Italy · Sapienza University Rome, Italy
We present Flash-GMM, a fused Triton kernel for efficient computation of Gaussian Mixture Models (GMMs) over large-scale data in a single GPU pass. By eliminating the need to materialize the full responsibility matrix in GPU memory, Flash-GMM achieves a \textbf{20×} speedup over existing implementations and enables training on datasets more than \textbf{100×} larger than previously feasible on one device. To demonstrate its impact, we integrate Flash-GMM into the IVF coarse quantizer for approximate nearest-neighbor (ANN) search. We show that soft GMM clustering is now a viable drop-in replacement for k-means, and that GMM responsibilities can be leveraged to assign border vectors to multiple clusters. Our approach reaches fixed recall targets with up to 1.7× fewer distance computations, or equivalently, yields +2--12 recall@10 at matched computational cost. We release the kernel as an open-source project.