Fast Algorithm for Approximate Motif Counting in Temporal Graph Streams

Graphs often have rich temporal information and evolve dynamically over time, which can be modeled as temporal graph streams. A temporal graph stream consists of a set of vertices and a series of timestamped and directed edges, where new vertices and edges arrive continuously over time. Temporal motifs are generalizations of subgraph patterns in static graphs which take into account edge orderings and durations in addition to topologies. Counting the number of occurrences of temporal motifs is a fundamental problem for temporal graph analysis. However, traditional streaming subgraph counting methods cannot support temporal matching, and are only suitable for simple graphs that do not contain temporal information. In addition, existing temporal motifs counting methods suffer from poor performance in temporal graph streams. We thus study approximate temporal motif counting via random sampling in temporal graph streams. We propose a generic streaming edge sampling (SES) algorithm to estimate the number of instances of any temporal motif in a given temporal graph stream. We then provide comprehensive analyses of the theoretical bounds and time complexities of SES. Finally, we perform extensive experimental evaluations for SES on four real world datasets. The results show that SES achieves up to three orders of magnitude speedups over the state-of-the-art sampling methods while having comparable estimation errors for temporal motif counting in the streaming setting.