Source-linked AI summary
Butterfly Counting in Bipartite Networks
Seyed-Vahid Sanei-Mehri, Ahmet Erdem Sariyuce, Srikanta Tirthapura
TL;DR
Counting bipartite butterflies matters because projection can inflate networks and lose information, while unipartite motif methods do not directly address this structure. The paper develops randomized sparsification and local-sampling algorithms with provable accuracy. Across evaluated networks, its best sampling and sparsification methods achieved relative error below 1% in about five and four seconds, respectively.
Problem
Projection of bipartite networks can inflate edge counts and lose information, motivating direct methods to estimate the butterfly, a basic cohesive bipartite motif.
Source: §1 · p. 2Method
The paper introduces randomized one-shot sparsification and local sampling algorithms, including color-based sparsification and sampling around local graph elements.
Source: §1 · p. 3, §6.2 · p. 22, §7 · p. 25Results
Across all networks considered, the best sampling and sparsification algorithms achieved <1% relative error in ≈5 and ≈4 seconds, respectively.
Source: §7 · p. 25Takeaways & Limitations
Local sampling can estimate butterfly counts when access to graph data is limited, including through rate-limited network APIs.
Source: §1 · p. 3ESpar uses O(mp) memory, requires choosing a sampling parameter, and assumes the entire graph is available locally.
Source: §6.4 · p. 25
Abstract
from arXiv · showhide
We consider the problem of counting motifs in bipartite affiliation networks, such as author-paper, user-product, and actor-movie relations. We focus on counting the number of occurrences of a "butterfly", a complete $2 \times 2$ biclique, the simplest cohesive higher-order structure in a bipartite graph. Our main contribution is a suite of randomized algorithms that can quickly approximate the number of butterflies in a graph with a provable guarantee on accuracy. An experimental evaluation on large real-world networks shows that our algorithms return accurate estimates within a few seconds, even for networks with trillions of butterflies and hundreds of millions of edges.
1 Introduction
The paper develops exact and randomized methods for counting butterflies directly in bipartite networks. Its randomized algorithms combine global sparsification or local sampling with accuracy guarantees and fast performance on large real-world graphs.
1 Introduction
- Projection to a unipartite network can inflate edge counts, artificially boost triangle and clustering counts, and lose information.For French Wikipedia articles and editors, projection increased edges from 22M to more than 200B.Source: §1 · p. 2
- A butterfly is the smallest bipartite cohesive motif, a complete 2 × 2 biclique used as a building block for community structure.The paper treats butterfly counting as a first step toward broader motif analysis in bipartite affiliation networks.Source: §1 · pp. 2–3
- One-shot sparsification samples edges globally and then counts butterflies in the resulting smaller graph.The two proposed algorithms are ESpar and ClrSpar.Source: §1 · p. 3
- Local sampling estimates counts from small subgraphs around vertices, edges, or wedges, and can work with limited graph access.The corresponding methods are VSamp, ESamp, and WSamp; this setting is useful for rate-limited network APIs.Source: §1 · p. 3
- The randomized estimates are unbiased, and their error can be reduced through independent repetitions or suitable sparsification parameters.The paper proves accuracy guarantees through variance analysis.Source: §1 · pp. 3–4
- ESamp+Fast-eBFC estimates butterfly counts with relative error below 1% within 5 seconds, while ESpar typically does so within 4 seconds.The evaluation includes graphs with hundreds of millions of edges and trillions of butterflies; prior exact algorithms took tens of thousands of seconds on such large graphs.Source: §1 · p. 4
2 Preliminaries
The paper works with simple, unweighted bipartite graphs and defines butterflies as complete 2 × 2 bicliques. It also specifies the probabilistic accuracy criterion used for randomized estimates.
2 Preliminaries
- The graph model excludes self-loops and multiple edges, partitions vertices into L and R, and defines degree, neighborhood, and maximum degree notation.A wedge is a path of length two.Source: §2 · p. 4
- A butterfly is a complete 2 × 2 biclique with two vertices from each partition and all four cross-partition edges present.The paper also defines per-vertex and per-edge butterfly counts.Source: §2 · p. 4, Figure 1 · p. 5
- An (ϵ, δ)-approximation has probability at most δ of deviating from the target by more than ϵ times that target.The evaluation uses massive real-world bipartite networks converted to simple, undirected graphs.Source: §2 · pp. 4–5
3 Related Work
Prior work on motifs largely focuses on unipartite graphs, while bipartite work motivates the butterfly as a cohesion measure. The paper positions its contribution as improved exact counting and new randomized approximate counting.
3 Related Work
- Bipartite cohesion research considered 3 × 3 bicliques, while later work argued that 2 × 2 bicliques better capture multiple vertices with shared neighbors.Butterflies have also been used in bipartite clustering coefficients, community-structured graph generation, and graphical-code analysis.Source: §3 · pp. 5–6
- Random motif sampling had mostly addressed unipartite graphs and triangles; the authors report that butterfly sampling in bipartite networks had not been studied.Source: §3 · p. 6
- Wang et al. presented exact butterfly-counting algorithms, and this paper proposes an improved exact algorithm followed by randomized approximations.Source: §3 · p. 6
4 Exact Butterfly Counting
ExactBFC chooses the cheaper vertex partition using degree-square sums, improving on the fixed-side approach. The paper also reports runtime gains and gives local algorithms for counting butterflies incident to a vertex or edge.
4 Exact Butterfly Counting
- ExactBFC chooses the starting partition by comparing the sums of squared degrees, using the side with the lower computational cost.Its implementation counts shared length-two paths with a hash map, and its cost improves on the fixed-left traversal of Wang et al. [30].Source: §4 · pp. 7–8
4.2 Local Butterfly Counting
- vBFC and eBFC count butterflies incident to a specified vertex and edge, respectively, and serve as building blocks for sampling algorithms.Their stated time bounds are O(∆dv) for vBFC and O(∆du + dv) for eBFC, with du < dv.Source: §4.2 · pp. 9–10
4.1 Performance of Exact Butterfly Counting
- ExactBFC is always faster than WFC, with 700× speedup on Journal and 35× on Orkut; WFC did not finish on Web within 40,000 seconds, while ExactBFC took about 9,000 seconds.The comparison reports that the preprocessing choice of which side to start from is effective.Source: §4.1 · p. 8, Figure 2 · p. 9
5 Approximation by Local Sampling
The section develops and compares vertex-, edge-, and wedge-sampling methods for estimating butterfly counts from sampled local subgraphs, analyzing their accuracy and runtime. It also reports ESamp with Fast-eBFC’s observed accuracy and speed, as well as the poor performance of a faster wedge-sampling variant.
5.1 Vertex Sampling (Algorithm VSamp)
- VSamp samples a uniform vertex, counts butterflies containing it in its distance-2 induced neighborhood, and yields an unbiased estimate; averaging independent runs reduces variance.Source: §5.1 · pp. 10–11
5.2 Edge Sampling (Algorithm ESamp)
- ESamp samples a uniform edge and counts butterflies containing it with eBFC, producing an unbiased estimate of the total butterfly count.Source: §5.2 · p. 13
5.3 Wedge Sampling (Algorithm WSamp)
- WSamp samples a uniformly random wedge, counts butterflies containing it via endpoint-neighborhood intersection, and averaging independent samples yields an (ϵ, 1/32)-estimator.Source: §5.3 · pp. 15–16
5.4 Accuracy and Runtime of Sampling
- VSamp has much higher variance than ESamp; theory gives no clear ESamp–WSamp winner, though ESamp typically has lower real-world variance and its slowest iteration cost reduces overall accuracy.The variance comparisons are reflected in Table 3; Figure 4 compares average time per iteration for the five largest networks.Source: §5.4 · p. 17, Table 3 · p. 17, Figure 4 · p. 17
5.6 Comparing Sampling-based Approaches
- Less than 1% relative error within 5 seconds across all networks: ESamp with Fast-eBFC achieves the best results among the compared sampling methods.The comparison includes VSamp, ESamp with eBFC, ESamp with Fast-eBFC, and WSamp; ESamp and WSamp have comparable accuracy, with ESamp slightly better, while VSamp performs poorly under the same time budget.Source: Figure 5 · p. 18, §5.6 · pp. 19–20
5.5 Faster Edge Sampling using Fast-eBFC
- Fast-eBFC estimates butterflies per sampled edge by sampling one neighbor from each endpoint and checking whether the four vertices form a butterfly; 1,000 repetitions make it 15x–357x faster than eBFC in ESamp.Although each iteration is less accurate than exact per-edge counting, the increased iteration rate improves accuracy over eBFC in ESamp on large graphs.Source: §5.5 · p. 18
- Fast Wedge Sampling performs poorly: on Deli it has 29% error after 10 seconds versus WSamp’s under 2% after 5 seconds, and its error on Web is 60% higher.The authors attribute the weak results partly to WSamp already having relatively short iterations.Source: §5.5 · p. 19
5.4 Accuracy and Runtime of Sampling
- Figure 5 tracks relative percent error against runtime for five large bipartite graphs, reporting the median of 30 sampling trials at each data point.Sampling algorithms begin producing estimates immediately, with accuracy improving as iterations accumulate; measurements extend to 60 seconds.Source: §5.6 · p. 19
6 Approximation by One-Shot Sparsification
One-shot sparsification estimates butterfly counts by sampling the whole graph and counting butterflies in the smaller sampled graph. ESpar samples edges independently, while ClrSpar uses shared vertex colors; their accuracy, runtime, memory, and access trade-offs inform when to use each approach.
6 Approximation by One-Shot Sparsification
- One-shot sparsification globally thins the input graph, then uses butterfly counts in the reduced graph to estimate the original count.The section compares independent edge sampling with color-based sampling, where edge choices are dependent.Source: §6 · p. 20
6.1 Edge Sparsification (ESpar)
- ESpar independently retains each edge with probability p, counts butterflies in the sampled graph using ExactBFC, then scales the count to estimate the original.The smaller sampled graph can make counting faster than on the original graph.Source: §6.1 · p. 20, §6 · p. 20
6.2 Colorful Sparsification (ClrSpar)
- ClrSpar assigns random colors to vertices and samples edges whose endpoints share a color, increasing the likelihood that dense structures are preserved.At p=1/N, its expected sampled butterfly count is p^3 rather than ESpar’s p^4, but this alone does not establish lower estimator variance.Source: §6.2 · p. 22
6.3 Comparison of Sparsification Algorithms
- ESpar achieved less than 1% error when sampling 5% of edges, while ClrSpar required a larger sampling probability for reasonable accuracy on several graphs.The analysis attributes the variance difference to the high number of butterfly pairs sharing two vertices without sharing an edge.Source: §6.3 · p. 24
6.4 Sampling or Sparsification?
- ESpar and ESamp with Fast-eBFC both reached 1% error in 1.7–5 seconds across the considered graphs, with ESpar faster.ESpar uses O(mp) memory and requires the whole graph; ESamp uses O(∆) memory and needs only a subgraph, so it may suit more restrictive settings.Source: Table 5 · p. 24, §6.4 · p. 25
7 Conclusion
The paper combines a cheap statistic that reduces exact butterfly-counting runtime with randomized estimates carrying provable accuracy guarantees. On the tested networks, its best sampling and sparsification algorithms are fast, while larger motifs and streaming remain future directions.
7 Conclusion
- A cheap vertex-set statistic drastically reduces exact-algorithm runtime, and scalable randomized algorithms provide provable accuracy guarantees.Source: §7 · p. 25
- Less than 1% relative error in ≈5 and ≈4 seconds on all tested networks; the state-of-the-art exact algorithm exceeds 40,000 seconds on the Web graph.The passage reports the two times for the best sampling and sparsification algorithms, respectively.Source: §7 · p. 25
- The work focuses on butterflies; larger motifs have a more serious combinatorial explosion than triangles, making them challenging to consider.The authors suggest this work's ideas as building blocks for other bipartite motifs.Source: §7 · p. 26
- For streaming, sparsification-based algorithms may adapt quite easily, whereas the same cannot be said for local-sampling algorithms.Source: §7 · p. 26