Approximate Butterfly Counting in Sublinear Time

Chi Luo 1∗ , Jiaxin Song 2∗ , Yuhao Zhang 3 , Kai Wang 1 , Zhixing He 3 , Kuan Yang 3 · 2026

Read Approximate Butterfly Counting in Sublinear Time by Chi Luo 1∗ , Jiaxin Song 2∗ , Yuhao Zhang 3 , Kai Wang 1 , Zhixing He 3 , Kuan Yang 3 (2026) 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-2603-21816.txt.

Introduction

Luo and co-authors count butterflies in bipartite graphs without reading most of the graph. A butterfly is a 2 by 2 biclique, and counting them is a basic task for two-sided network data. Their TLS algorithm works through degree, neighbor, and pair queries only. Tricks like small-degree-first sampling keep the estimates stable. A heavy-light split and a guess-and-prove step give accuracy within any chosen error bound. On fifteen datasets, TLS matched estimates with up to a thousand times fewer queries than earlier methods.

Catalog record

CREATORChi Luo 1∗ , Jiaxin Song 2∗ , Yuhao Zhang 3 , Kai Wang 1 , Zhixing He 3 , Kuan Yang 3
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE68902
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.21816

Browse the full library · About the Tower of Babel

Full text

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

Approximate Butterfly Counting in Sublinear Time ∗ Equal contributions. Code is available at: https://github.com/PKFR4ever/Approximate-Butterfly-Counting-in-Sublinear-Time Chi Luo 1∗ , Jiaxin Song 2∗ , Yuhao Zhang 3 , Kai Wang 1 , Zhixing He 3 , Kuan Yang 3 Abstract Bipartite graphs serve as a natural model for representing relationships between two different types of entities. When analyzing bipartite graphs, butterfly counting is a fundamental research problem that aims to count the number of butterflies (i.e., 2 × \times 2 bicliques) in a given bipartite graph. While this problem has been extensively studied in the literature, existing algorithms usually necessitate access to a large portion of the entire graph, presenting challenges in real scenarios where graphs are extremely large and I/O costs are expensive. In this paper, we study the butterfly counting problem under the query model, where the following query operations are permitted: degree query , neighbor query , and vertex-pair query . We propose 𝚃𝙻𝚂 {\tt TLS} , a practical two-level sampling algorithm that can estimate the butterfly count accurately while accessing only a limited graph structure, achieving significantly lower query costs under the standard query model. 𝚃𝙻𝚂 {\tt TLS} also incorporates several key techniques to control the variance, including “small-degree-first sampling” and “wedge sampling via small subsets”. To ensure theoretical guarantees, we further introduce two novel techniques: “heavy-light partition” and “guess-and-prove”, integrated into 𝚃𝙻𝚂 {\tt TLS} . With these techniques, we prove that the algorithm can achieve a ( 1 + ϵ ) (1+\epsilon) accuracy for any given approximation parameter 0 < ϵ < 1 0<\epsilon<1 on general bipartite graphs with a promised time and query complexity. In particular, the promised time is sublinear when the input graph is dense enough. Extensive experiments on 15 datasets demonstrate that 𝚃𝙻𝚂 {\tt TLS} delivers robust estimates with up to three orders of magnitude lower query costs and runtime compared to existing solutions. I Introduction Bipartite graphs serve as a natural model for representing relationships between two different types of entities, such as author-paper, user-item, and actor-movie. As the minimum complete subgraph in bipartite graphs, butterfly, which is also known as 2 \times 2 bicliques, plays an important role in bipartite graph analytics. In the field of bipartite graph analytics, butterfly counting is a fundamental research problem that aims to count the number of butterflies on a given bipartite graph. For an instance of butterfly counting, in Figure 1 , the vertices \{u_{0},u_{1},v_{0},v_{1}\} form a butterfly, and there are two butterflies in this graph. Butterfly counting has been proven useful in many applications, including network modeling [ 1 , 25 , 30 , 33 ] , community structure mining [ 37 , 54 ] , and network security [ 23 ] . Representative application scenarios include the following. 1) Network Measurement . The bipartite clustering coefficient is a cohesiveness measurement of bipartite graphs [ 2 , 24 , 29 , 32 , 42 , 31 ] . For instance, in user-item networks, the bipartite clustering coefficient can be used to identify sticky interest groups, which are useful for group-based recommendation [ 40 ] . Given a bipartite graph G , its bipartite clustering coefficient is defined as 4\times\rotatebox[origin]{90.0}{$\bowtie$}/n_{G} , where \bowtie is the number of butterflies and n_{G} denotes the number of caterpillars (i.e., three-paths) in G . Since n_{G} can be computed in O(m) time [ 2 ] , accelerating butterfly counting will in turn accelerate the computation of the bipartite clustering coefficient. 2) Fraud Detection . Butterfly counting is also widely used in algorithms discovering large and dense subgraphs in massive graphs [ 16 , 45 , 47 ] . For example, many dense subgraphs in the World Wide Web’s host-connection graph correspond to link spam [ 16 ] (i.e., websites that attempt to manipulate search engine rankings through aggressive interlinking to simulate popular content.), making dense subgraph extraction a useful primitive for spam detection in search engines. In e-commerce fraud detection, butterfly counting has further been applied to prune infeasible vertices [ 27 ] . In recent years, this problem has been extensively studied in the literature [ 43 , 34 , 44 ] . However, existing algorithms often require access to a large portion of the entire graph, which poses challenges in real-world scenarios where graphs are massive and I/O costs are prohibitively high. For instance, in the cloud computing environment, graphs can be too large to store locally. In such scenarios, network bandwidth often becomes a critical performance bottleneck [ 41 ] , and accessing input data incurs substantial overhead. To address this challenge, designing a sublinear-time algorithm that avoids reading the entire graph is essential. The sublinear algorithm literature has employed the query model to analyze graph access costs for various problems, including triangle counting [ 9 ] , k -clique counting [ 13 ] , and high-order graphlet estimation [ 5 , 7 , 19 , 28 ] . In this model, we can analyze the query cost and the (local) running time separately. Fig. 1 : A bipartite graph instance. Query Model. Given a graph G , we consider algorithms that can sample an edge uniformly (with one query cost) and perform the following three types of queries. • (Degree query): given a vertex v , it returns its degree d_{v} . • (Neighbor query): given a vertex v and an integer i , it returns the i -th neighbor of v ; • (Vertex-pair query): given a pair of vertices u and v , it returns whether (u,v) forms an edge in G . The query model serves as a foundational framework for many graph parameter estimation tasks, and we provide a brief overview of related works in Section VII . In this paper, we study the approximate butterfly counting problem under the query model for the first time. Since query costs often dominate real-world execution time, minimizing the number of queries while maintaining accuracy is crucial. Existing studies. As sampling is a useful strategy for approximate motif counting, state-of-the-art studies [ 34 , 52 ] on approximate butterfly counting rely on various sampling techniques. We briefly introduce their approaches below and leave a detailed discussion to Section III , with a comparison provided in Section IV after we present our algorithm. We note that sketch-based methods are sometimes also used for approximate counting [ 22 , 20 , 48 ] ; however, in static graph settings they offer limited advantages and are generally ill-suited for capturing butterfly substructures via simple mappings. In [ 34 ] , a sampling-based algorithm {\tt ESpar} is proposed. It reads a constant fraction of the graph (around 20%) and uses an exact butterfly counting algorithm [ 44 ] on this subgraph to estimate the total number of butterflies. This method reduces the running time and achieves high empirical accuracy. However, it does not reduce the asymptotic dependence on the graph size. Specifically, its time complexity remains O(mn) —the same as the exact algorithm in [ 44 ] . As a result, both the running time and query complexity remain prohibitive for large graphs. In a very recent work [ 52 ] , the authors propose a sampling-based algorithm {\tt WPS} , which improves upon the algorithm in

Read the complete text