Aug 2026· Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2· pp. 3027-3038· 0 citations· 35 references
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.
An index structure that, for a temporal graph with N edges, requires O(N) space and can evaluate extended BGPs in wco time and yields wco guarantees for related query types, including snapshot evaluation, version queries, and other temporal variants.
Diego Arroyuelo, Aidan Hogan, Gonzalo Navarro et al.· Proceedings of the VLDB Endo...· 0 citations
A deterministic fully dynamic algorithm that simultaneously maintains SCCs and reachability in directed graphs and significantly outperforms repeated offline recomputation in practical scenarios is presented.
Gregory Morse, Tamás Kozsik· Annales Mathematicae et Info...· 0 citations
Cohesive subgraph mining is a fundamental task in graph data analytics. We re-visit the problem of listing all minimal $k$-cores, where a $k$-core is a subgraph in which every vertex has degree at least $k$, and minimality requires that no proper subset remains a $k$-core. Existing methods are computationally prohibitive due to explosive branching and costly branch state update, leading to the trivial worst-case bound $O^{*}\left(2^{n}\right)$ for the basic branch-and-bound baseline wh, where $O^{*}$ suppresses polynomial factors and $n$ is the number of vertices. In this paper, we present an improved method IMinC based on three key ideas: (i) a principled branching state with lineartime update; (ii) a pivot strategy that guides branching toward promising vertices; and (iii) a divide-and-conquer framework that initializes each subproblem to enable our pivot strategy throughout and reduce recursion depth. We further introduce three reduction rules that aggressively prune infeasible branches. Together, these components yield the worst-case time complexity of $O^{*}\left(\alpha_{\ell}^{n}\right)$, where $\alpha_{\ell}$ is a positive number strictly smaller than 2. We also extend IMinC to list minimal $k$-cores under a size bound, addressing practical needs such as size-bounded community search. Extensive experiments on 12 real-world graphs demonstrate that IMinC outperforms the baselines by up to 2 order of magnitude, delivering substantial gains in efficiency.
Yukai Sun, Kaiqiang Yu, Shengxin Liu et al.· IEEE International Conferenc...· 0 citations
We investigate the data management of temporal property graphs on atemporal Labeled Property Graph (LPG) engines. While existing frameworks define temporal semantics, practitioners lack systematic empirical guidance on mapping these models to concrete representations in the absence of native engine support. We formalize two fundamental representation strategies implemented on top of standard LPG systems: a Versioning strategy that materializes temporal states via topological expansion, and a Property Lists strategy that encapsulates evolution through property-level compression. For each strategy, we define query translations for temporal evolution operators and analytical aggregations, and evaluate them across two heterogeneous real-world datasets. Our evaluation reveals a fundamental trade-off between topological selectivity and historical compactness: Versioning excels at high-throughput ingestion and short-window workloads but suffers from traversal amplification in dense graphs over long horizons, while Property Lists amortizes scan costs for read-heavy, multi-window analytics but incurs higher ingestion overhead and cannot support time-varying labels. We identify workload-dependent crossover points, showing how dataset density and structural volatility determine the superior strategy.
