Sparsity-aware Kernel Selection for Edge-Connected Jaccard Similarity in Graph Datasets

Performance of graph algorithms often depends both on the underlying hardware architecture and on structural properties of the input graph. Optimizations that deliver high performance on one class of graphs, such as hypersparse graphs with low average degree, can degrade performance on other classes, for example denser graphs with high average degree. In this work, we investigate sparsity-aware GPU kernel selection for computing the Jaccard similarity index, a measure of neighborhood overlap in graph datasets. In our kernel selection approach, we use the vertex-centric Jaccard similarity implementation from the cuGraph library as the baseline and include both vertex- and edge-centric variants of this kernel, with set-intersection algorithms varying between two-pointer linear search, binary search, and adaptive dynamic search.