Source-linked AI summary
Efficient Butterfly Counting for Large Bipartite Networks
Kai Wang, Xuemin Lin, Lu Qin, Wenjie Zhang, Ying Zhang
TL;DR
Large-scale butterfly counting is costly because existing methods enumerate wedges. The paper proposes vertex-priority counting and cache-aware strategies; its experiments report up to two orders of magnitude speedup over state-of-the-art methods on real datasets.
Problem
Existing wedge-enumerating algorithms do not efficiently handle large-scale bipartite networks, although exact butterfly counts are needed for applications such as k-wing computation.
Source: §1 · p. 2Method
BFC-VP orders vertices by priority to reduce wedge enumeration, and BFC-VP++ adds cache-aware strategies while retaining BFC-VP’s time complexity.
Source: §1 · pp. 2–3, §5.1 · p. 6Results
Up to 2 orders of magnitude faster than state-of-the-art algorithms on real datasets; BFC-VP++ counted 10^12 butterflies on Tracker in 50 seconds versus about 9,000 seconds for the state-of-the-art algorithm.
Source: §1 · p. 3Takeaways & Limitations
The experiments show that BFC-VP++ significantly outperforms state-of-the-art butterfly-counting algorithms on the evaluated real datasets.
Source: §8 · p. 12The cache-aware strategies are not applicable to BFC-BS or BFC-IBS because those algorithms are not priority-based.
Source: §5.3 · p. 8
Abstract
from arXiv · showhide
Bipartite networks are of great importance in many real-world applications. In bipartite networks, butterfly (i.e., a complete 2 x 2 biclique) is the smallest non-trivial cohesive structure and plays a key role. In this paper, we study the problem of efficient counting the number of butterflies in bipartite networks. The most advanced techniques are based on enumerating wedges which is the dominant cost of counting butterflies. Nevertheless, the existing algorithms cannot efficiently handle large-scale bipartite networks. This becomes a bottleneck in large-scale applications. In this paper, instead of the existing layer-priority-based techniques, we propose a vertex-priority-based paradigm BFC-VP to enumerate much fewer wedges; this leads to a significant improvement of the time complexity of the state-of-the-art algorithms. In addition, we present cache-aware strategies to further improve time efficiency while theoretically retaining the time complexity of BFC-VP. Moreover, we also show that our proposed techniques can work efficiently in external and parallel contexts. Our extensive empirical studies demonstrate that the proposed techniques can speed up the state-of-the-art techniques by up to two orders of magnitude for the real datasets.
1. INTRODUCTION
Butterfly counting supports analyses of bipartite networks, but wedge-enumerating algorithms can be costly on large graphs. The paper introduces vertex-priority and cache-aware algorithms and reports up to two orders of magnitude over prior methods.
1. INTRODUCTION
- Butterfly counts support bipartite clustering coefficients, inter-corporate relationship analysis, and k-wing computation; counting can be the bottleneck in clustering-coefficient calculation.For k-wing computation, each edge’s butterfly count is used in iterative edge removal.Source: §1 · pp. 1–2
- On a 2,002-vertex, 3,000-edge example, BFC-VP scans 2,000 wedges, compared with 500,500 for existing algorithms that must use high-degree middle-vertices.BFC-VP selects higher-degree vertices as start-vertices, leaving lower-degree vertices as middle-vertices.Source: §1 · p. 2
- BFC-VP++ prioritizes end-vertices to improve cache locality while retaining BFC-VP’s total end-vertex access count and time complexity.Its cache-aware projection groups high-priority end-vertices together in memory.Source: §1 · p. 3
- Up to 2 orders of magnitude faster than state-of-the-art algorithms; BFC-VP++ counted 10^12 butterflies on Tracker in 50 seconds, versus about 9,000 seconds for the state-of-the-art algorithm.The reported Tracker network has 10^8 edges.Source: §1 · p. 3
- Triangle-counting techniques do not directly solve butterfly counting efficiently: butterflies can reach O(m^2) in the worst case, and their structure differs from triangles.The paper also distinguishes its target from other bipartite motifs and notes that a general matrix-multiplication approach has time and space costs that hinder large graphs.Source: §1 · p. 3
2. PROBLEM DEFINITION
The paper defines butterfly counting on an undirected bipartite graph and formalizes the butterfly as a complete 2 × 2 biclique. The task is to compute the number of such structures in the graph.
2. PROBLEM DEFINITION
- The input is an undirected bipartite graph G with disjoint upper and lower vertex layers and edges only between the layers.The paper denotes the vertex and edge counts by n and m and assumes m > n.Source: §2 · p. 3
- A butterfly is a (2,2)-biclique formed by two vertices from each layer, with every vertex in one layer connected to both vertices in the other.Source: §2 · p. 4
- The problem is to compute the number of butterflies in the given graph; wedges are paths whose first, middle, and last vertices are termed start-, middle-, and end-vertices.Source: §2 · p. 4
3. EXISTING SOLUTIONS
The existing exact butterfly-counting algorithms BFC-BS and BFC-IBS enumerate wedges. BFC-IBS improves on BFC-BS through layer selection and a hash map, while retaining the wedge-based framework.
3. EXISTING SOLUTIONS
- Both BFC-BS and BFC-IBS count butterflies using wedge enumeration.Source: §3 · p. 4
- BFC-IBS improves the shared framework by preselecting a start-vertex layer to reduce time complexity and using a hash map to speed implementation.Source: §3 · p. 4
- BFC-IBS avoids counting a butterfly twice by processing wedge (u, v, w) only when end-vertex w.id > start-vertex u.id; Algorithm 1 then omits factor 1/2 in Equation 2 of Lemma 1.Source: §3 · p. 4
4. ALGORITHM BY VERTEX PRIORITY
BFC-VP chooses start-vertices by vertex priority rather than choosing a layer, avoiding unnecessary wedges through hubs. It is correct, with time complexity governed by the sum of edge-wise minimum endpoint degrees.
4. ALGORITHM BY VERTEX PRIORITY
- BFC-VP assigns each vertex a priority based on degree, breaking ties by vertex ID, then processes wedges only when the start-vertex outranks both middle- and end-vertices.Neighbors are sorted by priority so processing can stop when a vertex outranks the start-vertex.Source: §4 · p. 5
- BFC-VP counts every butterfly exactly once by constructing it from two wedges sharing a start-vertex and end-vertex.The proof considers the possible priority distributions among the four vertices.Source: §4 · p. 5
- BFC-VP runs in O(∑_(u,v)∈E(G) min{degG(u), degG(v)}) time, with O(m) space.The time bound follows because each processed edge contributes wedges proportional to the lower-degree endpoint.Source: §4 · p. 5
- In the Figure 3 example, BFC-VP processes 2,000 wedges, while BFC-IBS processes 1,000,000.BFC-VP avoids using hubs unnecessarily as wedge middle-vertices.Source: §4 · pp. 4, 6
5. CACHE-AWARE TECHNIQUES
End-vertex accesses dominate memory traffic, motivating cache-aware strategies that improve locality while retaining BFC-VP’s time complexity. The section combines wedge reordering with graph projection in BFC-VP++.
5.1 Cache-aware Wedge Processing
- Cache-aware wedge processing reverses the priority rule so end-vertices outrank both start- and middle-vertices, increasing high-priority endpoint accesses without changing wedge count.Neighbor sorting and early termination address the added cost of checking priorities.Source: §5.1 · pp. 6–7
- On Tracker, BFC-VP+ raises the share of end-vertex accesses to vertices of degree > 2000 from 9% to 81% while processing the same number of wedges as BFC-VP.In the Figure 2(b) example, distinct end-vertices fall from three to two.Source: §5.1 · p. 7
5.2 Cache-aware Graph Projection
- Graph projection bijectively relabels vertices without changing graph structure, clustering high-priority vertices to shorten their buffer distance and lower cache-miss ratios.In the example, the distance between high-priority endpoints falls from three to one.Source: §5.2 · p. 7
5.3 Putting Cache-aware Strategies Together
- BFC-VP++ combines projection, neighbor sorting, and priority-based wedge processing to count each butterfly once.It projects the graph, sorts each vertex’s neighbors, then processes wedges whose end-vertex outranks the start- and middle-vertices.Source: §5.3 · pp. 7–8
- BFC-VP++ runs in O(∑_(u,v)∈E(G) min{degG(u), degG(v)}) time and uses O(m) space.The time bound is retained by sorting neighbors to support early termination of priority checks.Source: §5.3 · p. 8
- The cache-aware strategies do not apply to BFC-BS or BFC-IBS because those algorithms are not priority-based.Source: §5.3 · p. 8
6. EXTENSIONS
The extensions apply the vertex-priority framework to per-edge butterfly counts, shared-memory parallelism, and external-memory processing. They retain priority-based wedge enumeration while adapting storage or scheduling to each setting.
6.1 Counting the Butterflies for Each Edge
- BFC-EVP++ computes butterfly counts for every edge with an extra array and a second wedge-processing round, retaining the BFC-VP time complexity.The stated complexity is O(∑_(u,v)∈E(G) min{deg_G(u), deg_G(v)}).Source: §6.1 · p. 8
6.2 Parallelization
- Shared-memory parallelization assigns different start-vertices to threads, using private counters to avoid conflicts while threads read the graph concurrently.After thread computations finish, a master thread combines the results.Source: §6.2 · pp. 8–9
- Priority-based dynamic scheduling performs best on Tracker and Bi-twitter among the evaluated strategies; the workload for each start-vertex is unknown in advance.The passage also notes that minimizing makespan is NP-hard even when workloads are known.Source: §6.2 · p. 9
6.3 External memory butterfly counting
- BFC-EM groups graph edges by vertex using external sorting, generates priority-valid wedges, then sorts and scans their endpoint pairs on disk.Its I/O cost is dominated by scanning and sorting the generated pairs.Source: §6.3 · pp. 9–10
7. EXPERIMENTS
Across the evaluated datasets, BFC-VP++ is the most efficient of the compared exact-counting algorithms, while BFC-VP also outperforms BFC-IBS. The experiments also examine per-edge counts, wedge processing, scalability, parallelization, approximate counting, external memory, and graph projection versus Gorder.
7.1 Datasets
- The experiments use 12 datasets, including nine real datasets from prior work and three additional networks for scalability evaluation.The algorithms were implemented in C++ and runs exceeding 10 hours were terminated.Source: §7.1 · p. 10, §7 · p. 10
7.2 Performance Evaluation
- On Tracker, BFC-VP and BFC-VP++ are at least 100× faster than BFC-IBS; BFC-VP++ is most efficient, and BFC-IBS times out on three larger datasets.On Bi-twitter, Bi-sk, and Bi-uk, BFC-IBS cannot finish within 10 hours.Source: §7.2 · p. 10, Figure 9 · p. 10
- For per-edge butterfly counts, BFC-EVP++ is the most efficient evaluated algorithm, following trends similar to the overall-count comparison.Figure 10 covers counting butterflies containing each edge.Source: §7.2 · p. 10, Figure 10 · p. 10
- On Tracker, Bi-twitter, Bi-sk, and Bi-uk, BFC-IBS processes 100× more wedges than BFC-VP and BFC-VP++; the latter pair process the same number.The paper attributes the difference to high-degree vertices in both layers and the larger BFC-IBS degree-square bound.Source: §7.2 · pp. 10–11, Figure 11 · p. 10
- BFC-VP and BFC-VP++ scale as graph size increases; in parallel, their computation costs decrease as thread count rises, while BFC-IBS has reported completion difficulties.For the graph-size test, induced subgraphs used 20% to 100% of original vertices; parallel tests varied thread count from 1 to 32.Source: §7.2 · p. 11, Figure 12 · p. 11
- Graph projection has lower total time cost than Gorder; it also yields fewer cache misses and lower miss ratios on nine datasets.Computation time favors graph projection on nine datasets and Gorder on three; their cache-reference counts are similar.Source: §7.2 · p. 12, Table 7 · p. 12, Table 8 · p. 12
8. CONCLUSION
The paper introduces BFC-VP to handle high-degree vertices in butterfly counting and BFC-VP++ to improve its CPU-cache performance. Experiments on real datasets show BFC-VP++ significantly outperforms state-of-the-art algorithms.
8. CONCLUSION
- BFC-VP uses vertex priorities to handle high-degree vertices in butterfly counting.The conclusion identifies BFC-VP as the paper’s butterfly-counting algorithm.Source: §8 · p. 12
- BFC-VP++ adds two cache-aware strategies to improve BFC-VP’s CPU-cache performance.Source: §8 · p. 12
- Experiments on real datasets show that BFC-VP++ significantly outperforms state-of-the-art algorithms.Source: §8 · p. 12