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

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