  Dynamic networks, a.k.a. graph streams, consist of a set of vertices and a
collection of timestamped interaction events (i.e., temporal edges) between
vertices. Temporal motifs are defined as classes of (small) isomorphic induced
subgraphs on graph streams, considering both edge ordering and duration. As
with motifs in static networks, temporal motifs are the fundamental building
blocks for temporal structures in dynamic networks. Several methods have been
designed to count the occurrences of temporal motifs in graph streams, with
recent work focusing on estimating the count under various sampling schemes
along with concentration properties. However, little attention has been given
to the problem of uncertainty quantification and the asymptotic statistical
properties for such count estimators. In this work, we establish the
consistency and the asymptotic normality of a certain Horvitz-Thompson type of
estimator in an edge sampling framework for deterministic graph streams, which
can be used to construct confidence intervals and conduct hypothesis testing
for the temporal motif count under sampling. We also establish similar results
under an analogous stochastic model. Our results are relevant to a wide range
of applications in social, communication, biological, and brain networks, for
tasks involving pattern discovery.

Methodology