# PRESTO: Simple and Scalable Sampling Techniques for the Rigorous Approximation of Temporal Motif Counts

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 34 references that are in the map.
- First posted on arXiv 18 Jan 2021.

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

- [Higher-order organization of complex networks](https://mlsanity.com/paper/1612.08447/) (2016)
- [Motifs in Temporal Networks](https://mlsanity.com/paper/1612.09259/) (2016)
- [Modern temporal network theory: A colloquium](https://mlsanity.com/paper/1508.01303/) (2015)
- [Detecting Mixing Services via Mining Bitcoin Transaction Network with Hybrid Motifs](https://mlsanity.com/paper/2001.05233/) (2020)
- [TRI`EST: Counting Local and Global Triangles in Fully-dynamic Streams with Fixed Memory Size](https://mlsanity.com/paper/1602.07424/) (2016)
- [Mining Persistent Activity in Continually Evolving Networks](https://mlsanity.com/paper/2006.15410/) (2020)
- [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)
- [Subgraph Frequencies: Mapping the Empirical and Extremal Geography of Large Graph Collections](https://mlsanity.com/paper/1304.1548/) (2013)
- [Science, AskScience, and BadScience: On the Coexistence of Highly Related Communities](https://mlsanity.com/paper/1612.07487/) (2016)
- [A Chronological Edge-Driven Approach to Temporal Subgraph Isomorphism](https://mlsanity.com/paper/1801.08098/) (2018)
- [Efficient Sampling Algorithms for Approximate Temporal Motif Counting (Extended Version)](https://mlsanity.com/paper/2007.14028/) (2020)
- [Multilayer motif analysis of brain networks](https://mlsanity.com/paper/1606.09115/) (2016)
- [Clustering Uncertain Graphs](https://mlsanity.com/paper/1612.06675/) (2016)
- [Network Classification in Temporal Networks Using Motifs](https://mlsanity.com/paper/1807.03733/) (2018)
- [Tiered Sampling: An Efficient Method for Approximate Counting Sparse Motifs in Massive Graph Streams](https://mlsanity.com/paper/1710.02108/) (2017)
- [Change points, memory and epidemic spreading in temporal networks](https://mlsanity.com/paper/1712.08948/) (2017)

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

- [odeN: Simultaneous Approximation of Multiple Motif Counts in Large Temporal Networks](https://mlsanity.com/paper/2108.08734/) (2021)
- [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)

The identification and counting of small graph patterns, called network motifs, is a fundamental primitive in the analysis of networks, with application in various domains, from social networks to neuroscience. Several techniques have been designed to count the occurrences of motifs in static networks, with recent work focusing on the computational challenges provided by large networks. Modern networked datasets contain rich information, such as the time at which the events modeled by the networks edges happened, which can provide useful insights into the process modeled by the network. The analysis of motifs in temporal networks, called temporal motifs, is becoming an important component in the analysis of modern networked datasets. Several methods have been recently designed to count the number of instances of temporal motifs in temporal networks, which is even more challenging than its counterpart for static networks. Such methods are either exact, and not applicable to large networks, or approximate, but provide only weak guarantees on the estimates they produce and do not scale to very large networks. In this work we present an efficient and scalable algorithm to obtain rigorous approximations of the count of temporal motifs. Our algorithm is based on a simple but effective sampling approach, which renders our algorithm practical for very large datasets. Our extensive experimental evaluation shows that our algorithm provides estimates of temporal motif counts which are more accurate than the state-of-the-art sampling algorithms, with significantly lower running time than exact approaches, enabling the study of temporal motifs, of size larger than the ones considered in previous works, on billion edges networks.