Accurate and Fast Estimation of Temporal Motifs using Path Sampling

Abstract

Counting the number of small subgraphs, called motifs, is a fundamental problem in social network analysis and graph mining. Many real-world networks are directed and temporal, where edges have timestamps. Motif counting in directed, temporal graphs is especially challenging because there are a plethora of different kinds of patterns. Temporal motif counts reveal much richer information and there is a need for scalable algorithms for motif counting. A major challenge in counting is that there can be trillions of temporal motif matches even with a graph with only millions of vertices. Both the motifs and the input graphs can have multiple edges between two vertices, leading to a combinatorial explosion problem. Counting temporal motifs involving just four vertices is not feasible with current state-of-the-art algorithms. We design an algorithm, TEACUPS, that addresses this problem using a novel technique of temporal path sampling. We combine a path sampling method with carefully designed temporal data structures, to propose an efficient approximate algorithm for temporal motif counting. TEACUPS is an unbiased estimator with provable concentration behavior, which can be used to bound the estimation error. For a Bitcoin graph with hundreds of millions of edges, TEACUPS runs in less than 1 minute, while the exact counting algorithm takes more than a day. We empirically demonstrate the accuracy of TEACUPS on large datasets, showing an average of 30$\times$ speedup (up to 2000$\times$ speedup) compared to existing GPU-based exact counting methods while preserving high count estimation accuracy.

Accepted in ICDM'24

References in corpus (10)

• The structure and function of complex networks
• Motifs in Temporal Networks
• Path lengths, correlations, and centrality in temporal networks
• Temporal motifs in time-dependent networks
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting
• Temporal motifs reveal homophily, gender-specific patterns and group talk in mobile communication networks
• Inferring the interplay of network structure and market effects in Bitcoin
• Wedge Sampling for Computing Clustering Coefficients and Triangle Counts on Large Graphs
• The Power of Pivoting for Exact Clique Counting
• odeN: Simultaneous Approximation of Multiple Motif Counts in Large Temporal Networks

Cited by in corpus (1)

• DX100: A Programmable Data Access Accelerator for Indirection