Fast Approximate Temporal Butterfly Counting on Bipartite Graphs via Edge Sampling

Temporal bipartite graphs are widely used to represent time-evolving relationships between two disjoint sets of nodes, e.g., customer-product interactions in e-commerce and user-group memberships in social networks. Temporal butterflies, i.e., the complete bipartite subgraphs that occur between two nodes from each partition within a short period and in a prescribed order, are essential in modeling the structural and sequential patterns of such graphs. Counting the number of temporal butterflies is a fundamental task in temporal bipartite graph analysis. However, existing methods for butterfly counting on static bipartite graphs and motif counting on temporal unipartite graphs are inefficient for this purpose. Since exact counting can be time-consuming on large graphs, in this paper, we propose an edge sampling-based approach to approximating temporal butterfly counts accurately and efficiently. We provide an analytical bound on the number of edges to be sampled to obtain estimates with small relative errors and high probability. Finally, we evaluate our algorithm on six real-world temporal bipartite graphs to show its superior accuracy and efficiency compared to baselines.