Lin Hu’s paper “Accelerating triangle counting on GPU” has been accepted by SIGMOD 2021.

Triangle counting is an important algorithm on graphs, which lays foundation for many other algorithms such like k-core and k-truss. As the scale of graph increases in recent years, many works try to transplant triangle counting to new hardwares like GPU for better performance. We find that preprocessing strategies, including edge direction and vertex ordering, have great influence on the performance of triangle counting on all implementations. Therefore, we aim to design preprocessing strategies for triangle counting  on GPU, which could accelerate existing triangle counting methods with changing their implementations. We first abstract computation patterns from state-of-the-art implementations, then summarize  run-time models based on those patterns. Next, we give analytic model to describe how the preprocessing influence performance accurately, based on which we design final strategies. And our strategies achieve great performance on all existing state-of-the-art triangle counting implementations on GPU.