# Efficient Discovery of Motif Transition Process for Large-Scale Temporal Graphs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 81 references that are in the map.
- First posted on arXiv 22 Apr 2025.

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

- [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)
- [DYMOND: DYnamic MOtif-NoDes Network Generative Model](https://mlsanity.com/paper/2308.00770/) (2023)
- [A Scalable Generative Graph Model with Community Structure](https://mlsanity.com/paper/1302.6636/) (2013)
- [When is a Network a Network? Multi-Order Graphical Model Selection in Pathways and Temporal Networks](https://mlsanity.com/paper/1702.05499/) (2017)
- [Motivo: fast motif counting via succinct color coding and adaptive sampling](https://mlsanity.com/paper/1906.01599/) (2019)
- [Temporal motifs reveal homophily, gender-specific patterns and group talk in mobile communication networks](https://mlsanity.com/paper/1302.2563/) (2013)
- [Using Motif Transitions for Temporal Graph Generation](https://mlsanity.com/paper/2306.11190/) (2023)
- [Random graph models for dynamic networks](https://mlsanity.com/paper/1607.07570/) (2016)
- [A Chronological Edge-Driven Approach to Temporal Subgraph Isomorphism](https://mlsanity.com/paper/1801.08098/) (2018)
- [Epidemiologically optimal static networks from temporal network data](https://mlsanity.com/paper/1302.0692/) (2013)
- [Dynamic stochastic blockmodels: Statistical models for time-evolving networks](https://mlsanity.com/paper/1304.5974/) (2013)
- [Statistically validated mobile communication networks: Evolution of motifs in European and Chinese data](https://mlsanity.com/paper/1403.3785/) (2014)
- [The Power of Pivoting for Exact Clique Counting](https://mlsanity.com/paper/2001.06784/) (2020)
- [PRESTO: Simple and Scalable Sampling Techniques for the Rigorous Approximation of Temporal Motif Counts](https://mlsanity.com/paper/2101.07152/) (2021)
- [odeN: Simultaneous Approximation of Multiple Motif Counts in Large Temporal Networks](https://mlsanity.com/paper/2108.08734/) (2021)
- [Temporal Motifs in Patent Opposition and Collaboration Networks](https://mlsanity.com/paper/2110.11198/) (2021)
- [Scalable Motif Counting for Large-scale Temporal Graphs](https://mlsanity.com/paper/2204.09236/) (2022)
- [ITeM: Independent Temporal Motifs to Summarize and Compare Temporal Networks](https://mlsanity.com/paper/2002.08312/) (2020)
- [Efficient Sampling Algorithms for Approximate Motif Counting in Temporal Graph Streams](https://mlsanity.com/paper/2211.12101/) (2022)
- [Everest: GPU-Accelerated System For Mining Temporal Motifs](https://mlsanity.com/paper/2310.02800/) (2023)
- [Accurate and Fast Estimation of Temporal Motifs using Path Sampling](https://mlsanity.com/paper/2409.08975/) (2024)

## Abstract (arXiv)

Understanding the dynamic transition of motifs in temporal graphs is essential for revealing how graph structures evolve over time, identifying critical patterns, and predicting future behaviors, yet existing methods often focus on predefined motifs, limiting their ability to comprehensively capture transitions and interrelationships. We propose a parallel motif transition process discovery algorithm, PTMT, a novel parallel method for discovering motif transition processes in large-scale temporal graphs. PTMT integrates a tree-based framework with the temporal zone partitioning (TZP) strategy, which partitions temporal graphs by time and structure while preserving lossless motif transitions and enabling massive parallelism. PTMT comprises three phases: growth zone parallel expansion, overlap-aware result aggregation, and deterministic encoding of motif transitions, ensuring accurate tracking of dynamic transitions and interactions. Results on 10 real-world datasets demonstrate that PTMT achieves speedups ranging from 12.0× to 50.3× compared to the SOTA method.