Counting Butterflies over Streaming Bipartite Graphs with Duplicate Edges

Lingkai Meng, Long Yuan, Xuemin Lin, Chengjie Li, Kai Wang, Wenjie Zhang · 2024

Read Counting Butterflies over Streaming Bipartite Graphs with Duplicate Edges by Lingkai Meng, Long Yuan, Xuemin Lin, Chengjie Li, Kai Wang, Wenjie Zhang (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-11488.txt.

Introduction

Lingkai Meng and co-authors count butterfly patterns in two-sided networks that arrive as an endless stream, duplicates included. A butterfly is a tiny complete connection between two pairs of nodes, and counting them powers community finding, fraud spotting, and link prediction on data like user-product clicks. Real streams repeat edges, and older counters that assume otherwise sample the repeats too eagerly and drift off target.

Their method, DEABC, samples edges into buckets with priorities, keeping only the data the estimate needs. Proofs show the count is unbiased with bounded spread. Against the best existing tools on real streams, it used less memory, hit closer to the true counts, and processed the stream faster. The one earlier method built for duplicates suffered high variance and heavy costs from its queue design. The authors present bucket sampling as the fix that makes streaming butterfly counts practical.

Catalog record

CREATORLingkai Meng, Long Yuan, Xuemin Lin, Chengjie Li, Kai Wang, Wenjie Zhang
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE59 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-11488

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Counting Butterflies over Streaming Bipartite Graphs with Duplicate Edges Lingkai Meng, Long Yuan, Xuemin Lin, Chengjie Li, Kai Wang, Wenjie Zhang Abstract Bipartite graphs are commonly used to model relationships between two distinct entities in real-world applications, such as user-product interactions, user-movie ratings and collaborations between authors and publications. A butterfly (a 2×2 bi-clique) is a critical substructure in bipartite graphs, playing a significant role in tasks like community detection, fraud detection, and link prediction. As more real-world data is presented in a streaming format, efficiently counting butterflies in streaming bipartite graphs has become increasingly important. However, most existing algorithms typically assume that duplicate edges are absent, which is hard to hold in real-world graph streams, as a result, they tend to sample edges that appear multiple times, leading to inaccurate results. The only algorithm designed to handle duplicate edges is 𝖥𝖠𝖡𝖫𝖤 \mathsf{FABLE} , but it suffers from significant limitations, including high variance, substantial time complexity, and memory inefficiency due to its reliance on a priority queue. To overcome these limitations, we introduce 𝖣𝖤𝖠𝖡𝖢 \mathsf{DEABC} (Duplicate-Edge-Aware Butterfly Counting), an innovative method that uses bucket-based priority sampling to accurately estimate the number of butterflies, accounting for duplicate edges. Compared to existing methods, 𝖣𝖤𝖠𝖡𝖢 \mathsf{DEABC} significantly reduces memory usage by storing only the essential sampled edge data while maintaining high accuracy. We provide rigorous proofs of the unbiasedness and variance bounds for 𝖣𝖤𝖠𝖡𝖢 \mathsf{DEABC} , ensuring they achieve high accuracy. We compare 𝖣𝖤𝖠𝖡𝖢 \mathsf{DEABC} with state-of-the-art algorithms on real-world streaming bipartite graphs. The results show that our 𝖣𝖤𝖠𝖡𝖢 \mathsf{DEABC} outperforms existing methods in memory efficiency and accuracy, while also achieving significantly higher throughput. I Introduction Butterfly (a 2\times 2 biclique) is the most basic subgraph structure in bipartite graphs, such as \{\{u_{1},u_{2}\},\{v_{1},v_{2}\}\} and \{\{u_{3},u_{5}\},\{v_{4},v_{5}\}\} in Figure 1 , that captures the local connectivity patterns between vertices [ 1 ] . Counting the number of butterflies in a given bipartite graph is a fundamental problem in bipartite graph analysis and has a wide range of applications. For example, in bipartite graph mining [ 2 , 3 , 4 ] , butterfly counting is the core ingredient of the well-known measurement bipartite clustering coefficient , which equals 4\times c_{\Join}/c_{\ltimes} , where c_{\Join} and c_{\ltimes} represent the number of butterflies and three-paths respectively. This measurement reveals how tightly entities are grouped, making it particularly valuable in community detection [ 5 ] , representative graph sampling [ 6 ] , and studies of social collective behaviors [ 7 ] . Moreover, butterfly counting is crucial for identifying k -bitruss in bipartite graphs, which represents the largest subgraph where each edge is contained in at least k butterflies [ 8 , 9 , 10 ] . This has important applications in areas such as community detection [ 11 , 12 , 13 , 14 , 15 ] , spam detection [ 16 , 15 , 17 ] , fraud detection [ 18 , 19 ] . Given its importance, butterfly counting has attracted significant attention recently [ 1 , 14 , 20 , 21 , 22 , 17 , 23 , 15 , 24 , 25 , 26 , 27 , 28 , 29 , 30 , 31 , 32 ] . Fig. 1 : Butterflies in A Bipartite Graph Motivation. Real-world bipartite graphs are inherently streaming, with new edges continuously arriving at high speed. For example, Alibaba reports that during a peak period in 2017, its customer purchase activities generated 320 PB of log data over just six hours [ 30 , 29 ] . Given the potentially large or even infinite size of these streams, as well as their high velocity, storing the entire graph in main memory and then counting butterflies afterward is impractical for real-world applications [ 33 , 12 ] . Consequently, a range of memory-efficient one-pass streaming algorithms which can efficiently estimate the number of butterflies in a bipartite graph stream within a user-specified memory limit are proposed in the literature [ 28 , 30 , 27 ] . However, almost all of existing algorithms assume that edges are unique, an assumption that often fails in real-world bipartite graph stream scenarios [ 34 , 35 ] . Duplicate edges are commonly present in real-world bipartite graph streams, such as system-level retries due to network instability (e.g., in payment or order systems) [ 36 , 37 , 38 , 39 , 40 ] and log duplication caused by distributed collection mechanisms in telemetry and monitoring systems [ 34 , 35 ] . However, duplicate edges can lead to incorrect graph analysis if they are not properly handled. Butterfly counting provides the basis for computing classic metrics such as transitivity and clustering coefficient, which are widely used to measure community structure in bipartite networks [ 14 , 41 , 29 ] . These metrics have been applied to tasks such as community detection [ 5 ] , representative graph sampling [ 6 ] , and studies of social collective behaviors [ 7 ] . Besides, clustering coefficient has also been exploited to analyze the predictive performance of deep neural networks [ 42 ] . However, repeated interactions may cause the same butterfly structure to be counted multiple times, thereby exaggerating the density of communities and distorting cohesiveness measures. For instance, if a single entity forms repeated connections across both sides of the bipartite graph, the resulting butterfly count may misleadingly suggest stronger community structures. Figure 2 illustrates that even when a single user u_{1} generates duplicate edges due to system failures, the clustering coefficient shifts markedly, from 0.675 in (a) to 0.838 in (b). Duplicate edges can also obscure anomalies in fraud detection. Dense butterfly patterns are often used to identify coordinated fraudulent behavior [ 28 , 27 , 43 , 30 ] , but repeated actions by the same user may inflate these structures, thereby concealing true fraud patterns and weakening detection algorithms. Overall, failure to effectively process duplicate edges introduces significant bias into analysis results. Our experiments in Section V show that even a duplication rate as low as 1% can increase relative error by up to an order of magnitude. While one might consider preprocessing to remove duplicates, this is often infeasible in streaming scenarios due to memory limitations and real-time processing demands, as in the case of Alibaba’s large-scale log data. (a) (b) Fig. 2 : Impact of Duplicate Edges on Clustering Coefficient ((a) 0.675 vs. (b) 0.838) Sun et al. propose \mathsf{FABLE} [ 36 ] which is currently the only butterfly counting algorithm that can handle duplicate edges in bipartite graph streaming. However, it still suffers from high variance and time complexity and requires an additional priority queue to store the priorities of sampled edges. Maintaining this priority queue inevitably increases both time complexity and memory usage. Motivated by this, in this paper, we study the problem of butterfly counting over streaming bipartite graphs with duplicate edges and aim to devise efficient algorithms that ensure accurate and memory-efficient butterfly counting of large-scale bipartite graph streams. Challenges. However, it is of great challenge to design such an algorithm for the following reasons: \bullet Memory and computation efficiency. Considering the large-size and high-speed nature of bipartite graph streams, the designed

Read the complete text