Sparsity-aware Fine-Grained Parallelization for Set Intersection Computations in Graph Datasets

Abstract

Many real-world applications such as bioinformatics, network analysis, and recommendation systems require computing intersections of vertex neighborhood sets in graph datasets. However, variability in graph sparsity patterns makes it challenging to design a single GPU optimization strategy for such workloads that performs efficiently across all input graphs. We present a fine-grained GPU parallelization approach that adapts to workload characteristics by assigning set intersection computations within a graph to the most suitable parallelization strategies. We partition the work by sorting edges based on the estimated per-edge intersection cost, followed by a prefix-sum–based analysis to determine a split point in the edgelist for assigning work across parallelization strategies. Finally, using graph metrics such as average degree, maximum degree, and degree distribution properties as features in a classifier, we predict the optimal parallelization approach between our fine-grained and other state-of-the-art GPU kernels with 88% accuracy on a held-out test set. When evaluated on an NVIDIA H100 GPU for set intersection–based workloads, edge-connected Jaccard similarity and triangle counting, the predicted kernels deliver average speedups of 1.65 × and 1.66 × over state-of-the-art approaches that assign one thread per edge to compute set intersections and 2.54 × and 2.64 × over approaches that use multiple threads per edge to compute set intersections, respectively.