A Comparative Study on Exact Triangle Counting Algorithms on the GPU

Abstract

We implement exact triangle counting in graphs on the GPU using three different methodologies: subgraph matching to a triangle pattern; programmable graph analytics, with a set-intersection approach; and a matrix formulation based on sparse matrix-matrix multiplies. All three deliver best-of-class performance over CPU implementations and over comparable GPU implementations, with the graph-analytic approach achieving the best performance due to its ability to exploit efficient filtering steps to remove unnecessary work and its high-performance set-intersection core.

7 pages, 6 figures and 2 tables

References in corpus (2)

• Gunrock: A High-Performance Graph Processing Library on the GPU
• Approximately Counting Triangles in Sublinear Time

Cited by in corpus (7)

• Static Graph Challenge: Subgraph Isomorphism
• TRUST: Triangle Counting Reloaded on GPUs
• GraphChallenge.org: Raising the Bar on Graph Analytic Performance
• Parallelizing Maximal Clique Enumeration on GPUs
• A 2D Parallel Triangle Counting Algorithm for Distributed-Memory Architectures
• GraphChallenge.org Triangle Counting Performance
• On Large-Scale Graph Generation with Validation of Diverse Triangle Statistics at Edges and Vertices