Efficient Simple Temporal Cycle Enumeration on Large Graphs with Lightweight Preprocessing
TL;DR
This work introduces a novel edge-centric framework that treats temporal edges as the core units of exploration and eliminates redundant temporal checks, and extends this framework to dynamic settings by introducing an efficient incremental update algorithm that selectively identifies affected paths only.
Abstract
Temporal cycles are fundamental patterns in graphs, with important applications in finance, security, and neuroscience. In this work, we study the Simple Temporal Cycle Enumeration (STCE) problem, which aims to enumerate all simple cycles with strictly increasing timestamps within a given time window. However, existing methods, such as 2SCENT, suffer from redundant checks and expensive detection phase, making them inefficient for large-scale or dynamically evolving graphs. To overcome these challenges, we introduce a novel edge-centric framework that treats temporal edges as the core units of exploration. By computing edge offsets in linear time, we eliminate redundant temporal checks, and our constraint-based DFS avoids the expensive detection phase required by prior work. This design ensures polynomial delay and leads to substantial performance gains over existing approaches. Furthermore, we extend our framework to dynamic settings by introducing an efficient incremental update algorithm that selectively identifies affected paths only. Experiments show over an order-of-magnitude speedup on static graphs and up to six orders-of-magnitude improvement for dynamic updates, with most updates completing within 1 ms.