Fast triangle counting on large graphs with GPUs scales greatly
Enumeration-based Triangle Counting on GPUs
Distributed, Parallel, and Cluster Computing
Summary
Counting triangles in a network helps understand how connected the network is, but it can be very slow because there are many possible connections to check. The authors created a way to use powerful NVIDIA GPUs spread across multiple machines to count these triangles much faster than before. Their method works well even for very large networks with billions of connections. They tested it and found it can be 2 to 100 times faster than other leading GPU methods and up to 10 times faster than CPU-based methods.
What this means in practice
- •For network engineers: Quickly count connected cycles in large communication networks to help optimize routing and detect network structure changes.
- •For social media analysts: Analyze large social graphs rapidly to identify tightly knit user groups based on triangle connectivity.
Authors
Sayan Ghosh
Abstract
Subgraph enumeration in partitioned graphs across distributed-memory systems is beset with challenges in balancing data movement with the local computation. Especially, counting the number of triangles induced by the closed wedges (i.e., length-3 cycles) is a measure of connectedness in a graph, but often limited by the significant search space caused by open wedges or length-2 paths (usually greater than the number of edges in a graph), which must be inspected to assess whether a particular wedge is closed. To mitigate triangle counting on massive graphs, distributed-memory partitioned-graph approaches are viable (i.e., assessing closed wedges independently within a partition), but load imbalance due to arbitrary communication can overshadow any gains from enhanced concurrency, owing to the inherent lack of structure in regular graphs. In this paper, we discuss a distributed-memory exact graph triangle counting implementation, and assess its performance over billion-edge real-world graphs on contemporary scale-out and scale-up based NVIDIA GPU platforms (considering NVIDIA ``Ampere'' and ``Hopper'' architectures), depicting a scalability spectrum of multiple orders of magnitude. Comparisons with existing state-of-the-art approaches demonstrates up to 10$\times$ improvements relative to distributed-memory CPU baseline, 2-100$\times$ over single-GPU vendor-optimized NVIDIA RAPIDS cuGraph and 10-60\% over multi-GPU $G^2$Miner, in terms of end-to-end execution times.