# Scalable Fine-Grained Parallel Cycle Enumeration Algorithms

arXiv: https://arxiv.org/abs/2202.09685 · HTML: https://mlsanity.com/paper/2202.09685/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Feb 2022.

## Built on by (most cited first, 3 of 3)

- [Realistic Synthetic Financial Transactions for Anti-Money Laundering Models](https://mlsanity.com/paper/2306.16424/) (2023)
- [Provably Powerful Graph Neural Networks for Directed Multigraphs](https://mlsanity.com/paper/2306.11586/) (2023)
- [Graph Feature Preprocessor: Real-time Subgraph-based Feature Extraction for Financial Crime Detection](https://mlsanity.com/paper/2402.08593/) (2024)

## Abstract (arXiv)

Enumerating simple cycles has important applications in computational biology, network science, and financial crime analysis. In this work, we focus on parallelising the state-of-the-art simple cycle enumeration algorithms by Johnson and Read-Tarjan along with their applications to temporal graphs. To our knowledge, we are the first ones to parallelise these two algorithms in a fine-grained manner. We are also the first to demonstrate experimentally a linear performance scaling. Such a scaling is made possible by our decomposition of long sequential searches into fine-grained tasks, which are then dynamically scheduled across CPU cores, enabling an optimal load balancing. Furthermore, we show that coarse-grained parallel versions of the Johnson and the Read-Tarjan algorithms that exploit edge- or vertex-level parallelism are not scalable. On a cluster of four multi-core CPUs with 256 physical cores, our fine-grained parallel algorithms are, on average, an order of magnitude faster than their coarse-grained parallel counterparts. The performance gap between the fine-grained and the coarse-grained parallel algorithms widens as we use more CPU cores. When using all 256 CPU cores, our parallel algorithms enumerate temporal cycles, on average, 260× faster than the serial algorithm of Kumar and Calders.