# odeN: Simultaneous Approximation of Multiple Motif Counts in Large Temporal Networks

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 53 references that are in the map.
- First posted on arXiv 19 Aug 2021.

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

- [Motifs in Temporal Networks](https://mlsanity.com/paper/1612.09259/) (2016)
- [Mining Persistent Activity in Continually Evolving Networks](https://mlsanity.com/paper/2006.15410/) (2020)
- [Exploring the structure and function of temporal networks with dynamic graphlets](https://mlsanity.com/paper/1412.3885/) (2014)
- [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)
- [A Chronological Edge-Driven Approach to Temporal Subgraph Isomorphism](https://mlsanity.com/paper/1801.08098/) (2018)
- [Motifs for processes on networks](https://mlsanity.com/paper/2007.07447/) (2020)
- [Efficient Sampling Algorithms for Approximate Temporal Motif Counting (Extended Version)](https://mlsanity.com/paper/2007.14028/) (2020)
- [Flow Motifs in Interaction Networks](https://mlsanity.com/paper/1810.08408/) (2018)
- [Clustering Uncertain Graphs](https://mlsanity.com/paper/1612.06675/) (2016)
- [Efficiently Counting Vertex Orbits of All 5-vertex Subgraphs, by EVOKE](https://mlsanity.com/paper/1911.10616/) (2019)
- [Motif Discovery Algorithms in Static and Temporal Networks: A Survey](https://mlsanity.com/paper/2005.09721/) (2020)
- [Heterogeneous Graphlets](https://mlsanity.com/paper/2010.14058/) (2020)
- [PRESTO: Simple and Scalable Sampling Techniques for the Rigorous Approximation of Temporal Motif Counts](https://mlsanity.com/paper/2101.07152/) (2021)
- [Behavior Query Discovery in System-Generated Temporal Graphs](https://mlsanity.com/paper/1511.05911/) (2015)

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

- [A Temporal Graphlet Kernel for Classifying Dissemination in Evolving Networks](https://mlsanity.com/paper/2209.07332/) (2022)
- [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)

Counting the number of occurrences of small connected subgraphs, called temporal motifs, has become a fundamental primitive for the analysis of temporal networks, whose edges are annotated with the time of the event they represent. One of the main complications in studying temporal motifs is the large number of motifs that can be built even with a limited number of vertices or edges. As a consequence, since in many applications motifs are employed for exploratory analyses, the user needs to iteratively select and analyze several motifs that represent different aspects of the network, resulting in an inefficient, time-consuming process. This problem is exacerbated in large networks, where the analysis of even a single motif is computationally demanding. As a solution, in this work we propose and study the problem of simultaneously counting the number of occurrences of multiple temporal motifs, all corresponding to the same (static) topology (e.g., a triangle). Given that for large temporal networks computing the exact counts is unfeasible, we propose odeN, a sampling-based algorithm that provides an accurate approximation of all the counts of the motifs. We provide analytical bounds on the number of samples required by odeN to compute rigorous, probabilistic, relative approximations. Our extensive experimental evaluation shows that odeN enables the approximation of the counts of motifs in temporal networks in a fraction of the time needed by state-of-the-art methods, and that it also reports more accurate approximations than such methods.