.png){kind=icon}
.png){kind=icon}
Return
Efficiently Counting Four-Node Motifs in Large-Scale Temporal Graphs
.png){kind=icon}
PRE
AI
DOI：10.1007/s00778-025-00926-8.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Temporal motifs are compact subgraph patterns that recur frequently within a sequence of timestamps. They reveal implicit insights in the graph data and guide informed decision-making. However, current methods for exactly counting temporal motifs face challenges of high time complexity and inapplicability when motifs involve four nodes and struggle to scale to larger temporal graphs. In this paper, we propose a novel and exact counting framework tailored to 4-node, 3-edge, and 4-edge single-interaction temporal motifs whose time window size is constrained in a fixed interval. To speed up the counting process, we begin by categorizing all 4-node temporal motifs based on their structural characteristics. Subsequently, we present three rapid and precise sub-algorithms, each dedicated to counting motifs within its category. To expedite the counting process, we implement a series of straightforward and highly effective counters. Our algorithm cleverly uses these counters to identify and record all temporal motif instances based on the information and interrelationships of edges, significantly enhancing counting efficiency, especially for large-scale temporal graphs. Our extensive experiments on 14 large-scale real-world temporal graphs demonstrate the superiority of our work in terms of efficiency. Results show that our work significantly outperforms all state-of-the-art baselines and achieves a remarkable speedup of up to 25,816-fold.
Keywords:
Temporal motif
Motif counting
4-node motif
Temporal graph
Journal
IF:
3.8
Papers:
77
Citations:
2.4K