StepTC: Stepwise Triangle Counting on GPU with Two Efficient Set Intersection Methods

Triangle counting (TC) plays a vital role in graph mining systems. However, existing methods often rely on single intersection kernel function, limiting their performance across diverse datasets. To address this challenge, we proposed StepTC (a novel Stepwise Triangle Counting algorithm). StepTC selects appropriate set intersection methods for each counting step to ensure optimal efficiency on a global scale. Additionally, two efficient set intersection methods and a dynamic shared memory assignment strategy are implemented to enhance the adaptability of StepTC for GPUs. A round-robin scheduling strategy for task partitioning is employed to achieve load balancing across multiple GPUs. It is noteworthy that StepTC outperforms state-of-the-art solutions, delivering impressive speedups ranging from 1.4 \(\times \) to 22.4 \(\times \) on various datasets.