  Pattern counting in graphs is fundamental to network science tasks, and there
are many scalable methods for approximating counts of small patterns, often
called motifs, in large graphs. However, modern graph datasets now contain
richer structure, and incorporating temporal information in particular has
become a critical part of network analysis. Temporal motifs, which are
generalizations of small subgraph patterns that incorporate temporal ordering
on edges, are an emerging part of the network analysis toolbox. However, there
are no algorithms for fast estimation of temporal motifs counts; moreover, we
show that even counting simple temporal star motifs is NP-complete. Thus, there
is a need for fast and approximate algorithms. Here, we present the first
frequency estimation algorithms for counting temporal motifs. More
specifically, we develop a sampling framework that sits as a layer on top of
existing exact counting algorithms and enables fast and accurate
memory-efficient estimates of temporal motif counts. Our results show that we
can achieve one to two orders of magnitude speedups with minimal and
controllable loss in accuracy on a number of datasets.
