# Scalable Motif Counting for Large-scale Temporal Graphs

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 39 references that are in the map.
- First posted on arXiv 20 Apr 2022.

## Builds on (most cited first, 12 of 12)

- [Graph-based Anomaly Detection and Description: A Survey](https://mlsanity.com/paper/1404.4679/) (2014)
- [Higher-order organization of complex networks](https://mlsanity.com/paper/1612.08447/) (2016)
- [Motifs in Temporal Networks](https://mlsanity.com/paper/1612.09259/) (2016)
- [GraLSP: Graph Neural Networks with Local Structural Patterns](https://mlsanity.com/paper/1911.07675/) (2019)
- [A Survey of Community Search Over Big Graphs](https://mlsanity.com/paper/1904.12539/) (2019)
- [Tensor Spectral Clustering for Partitioning Higher-order Network Structures](https://mlsanity.com/paper/1502.05058/) (2015)
- [Graph Sample and Hold: A Framework for Big-Graph Analytics](https://mlsanity.com/paper/1403.3909/) (2014)
- [Temporal Network Motifs: Models, Limitations, Evaluation](https://mlsanity.com/paper/2005.11817/) (2020)
- [A Chronological Edge-Driven Approach to Temporal Subgraph Isomorphism](https://mlsanity.com/paper/1801.08098/) (2018)
- [How to Count Triangles, without Seeing the Whole Graph](https://mlsanity.com/paper/2006.11947/) (2020)
- [Efficient Sampling Algorithms for Approximate Temporal Motif Counting (Extended Version)](https://mlsanity.com/paper/2007.14028/) (2020)
- [A Fast and Provable Method for Estimating Clique Counts Using Tur'an's Theorem](https://mlsanity.com/paper/1611.05561/) (2016)

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

- [ATM-GAD: Adaptive Temporal Motif Graph Anomaly Detection for Financial Transaction Networks](https://mlsanity.com/paper/2508.20829/) (2025)
- [Efficient Discovery of Motif Transition Process for Large-Scale Temporal Graphs](https://mlsanity.com/paper/2504.15979/) (2025)
- [Efficient Approximate Temporal Triangle Counting in Streaming with Predictions](https://mlsanity.com/paper/2506.13173/) (2025)

## Abstract (arXiv)

One fundamental problem in temporal graph analysis is to count the occurrences of small connected subgraph patterns (i.e., motifs), which benefits a broad range of real-world applications, such as anomaly detection, structure prediction, and network representation learning. However, existing works focused on exacting temporal motif are not scalable to large-scale temporal graph data, due to their heavy computational costs or inherent inadequacy of parallelism. In this work, we propose a scalable parallel framework for exactly counting temporal motifs in large-scale temporal graphs. We first categorize the temporal motifs based on their distinct properties, and then design customized algorithms that offer efficient strategies to exactly count the motif instances of each category. Moreover, our compact data structures, namely triple and quadruple counters, enable our algorithms to directly identify the temporal motif instances of each category, according to edge information and the relationship between edges, therefore significantly improving the counting efficiency. Based on the proposed counting algorithms, we design a hierarchical parallel framework that features both inter- and intra-node parallel strategies, and fully leverages the multi-threading capacity of modern CPU to concurrently count all temporal motifs. Extensive experiments on sixteen real-world temporal graph datasets demonstrate the superiority and capability of our proposed framework for temporal motif counting, achieving up to 538* speedup compared to the state-of-the-art methods. The source code of our method is available at: https://github.com/steven-ccq/FAST-temporal-motif.