Date of publication xxxx 00, 0000, date of current version xxxx 00, 0000. Digital Object Identifier 10.1109/ACCESS.2024.0429000
Distributed Balanced Butterfly Counting in Signed Bipartite Graphs KIRAN MEKALA1 , APURBA DAS2 , SUMAN BANERJEE3 , 1 2 3
Computer Science and Information Systems, BITS Pilani Hyderabad Campus, Hyderabad, India (e-mail: [email protected]) Computer Science and Information Systems, BITS Pilani Hyderabad Campus, Hyderabad, India (e-mail: [email protected]) Department of Computer Science and Engineering, Indian Institute of Technology Jammu, Jammu & Kashmir, India (e-mail: [email protected])
arXiv:2609.21848v1 [cs.DC] 18 Sep 2026
Corresponding author: MEKALA KIRAN (e-mail: [email protected]).
ABSTRACT The balanced butterfly is a fundamental primitive for analyzing signed bipartite graphs and provides a basis for studying higher-order structural properties, such as clustering coefficients and community structure. Despite its importance, existing approaches primarily rely on serial algorithms for balanced butterfly counting, which become inefficient on large-scale graphs. To address this limitation, we propose a distributed algorithm, D-BBC, based on a hybrid MPI+TBB framework that exploits MPI for inter-process communication and Intel TBB for intra-node parallelism. We conduct an experimental assessment of the proposed approach across 15 real-world datasets. Experimental results demonstrate that, on a single-node distributed system, D-BBC achieves average speedups of 1321× and 16.2× over the serial BB2K and multi-core M-BBC implementations, respectively. Furthermore, D-BBC achieves a maximum speedup of 23.58× over the distributed baseline S-Monarch in terms of end-to-end execution time. These results demonstrate the efficiency of the proposed distributed approach and its potential to enable highperformance signed motif analysis on large-scale bipartite graphs. INDEX TERMS Bipartite graph, butterfly, distributed algorithm, multi-core, motif, signed bipartite graph.
I. INTRODUCTION
Signed bipartite graphs are ubiquitous. They model interactions between two disjoint sets of entities, where relationships are associated with positive or negative semantics, such as trust/distrust, like/dislike, and approval/disapproval [1], [2]. For example, in user-product networks, users express positive or negative feedback through ratings or reviews, while in legislator-bill networks, legislators cast yay or nay votes on bills, naturally yielding polarized relationships [3]. Unlike traditional bipartite graphs, which assume homogeneous relationships and treat all edges identically [4]–[6], signed bipartite graphs explicitly capture the polarity of interactions and therefore provide a richer representation of many real-world systems [7], [8]. Figure 1 shows an example of unsigned and signed bipartite networks constructed from a user-product network. The rapid growth of large-scale signed bipartite graphs has created an increasing demand for efficient graph analytics. Among various graph mining tasks, counting and enumerating network motifs are fundamental because they constitute the basic building blocks of complex networks [5], [9]. Numerous cohesive structures have been studied in bipartite graphs, including bicliques, bicores, and bitrusses [10]–[15]. VOLUME 4, 2016
Among them, the butterfly (i.e., a complete 2 × 2 biclique) is the smallest and most fundamental motif, serving as the basis for applications such as graph decomposition, community detection, dense subgraph mining, and link prediction [4], [6], [16]–[18]. To extend this concept to signed bipartite graphs, Derr et al. [3] introduced the notion of a balanced butterfly based on social balance theory [10]. Balanced butterflies have become an important primitive for analyzing structural balance in signed bipartite networks and have found applications in sign prediction, multidrug discovery, and higher-order signed network analysis [1], [7], [8]. Despite their importance, counting balanced butterflies in large-scale signed bipartite graphs remains computationally challenging. Real-world graphs are typically massive and sparse, with highly skewed degree distributions, leading to irregular workloads and substantial computational and memory requirements. Existing studies on balanced butterfly counting have primarily focused on sequential algorithms [1], [3], [7], while parallel and distributed efforts have largely targeted butterfly counting in unsigned bipartite graphs [9], [17], [19], [20]. However, these techniques cannot be applied directly to signed bipartite graphs because edge signs impose additional constraints during butterfly verification. In 1
Mekala et al.: D-BBC: Distributed Balanced Butterfly Counting in Signed Bipartite Graphs
u1
p1
u1
p1
u2
p2
u2
p2
u3
p3
u3
p3
u4
p4
u4
p4
(a) (Bipartite graph)
(b) (Signed bipartite graph)
FIGURE 1: Example of a user-product network: an unsigned bipartite graph (grey edges) and a signed bipartite graph (solid/dashed edges represent positive/negative interactions).
addition, distributed execution also requires efficient graph partitioning, communication minimization, and workload balancing. Consequently, scalable distributed algorithms for balanced butterfly counting in signed bipartite graphs remain largely unexplored. A. MOTIVATION AND CHALLENGES
The increasing scale of signed bipartite graphs makes exact balanced butterfly counting computationally challenging, particularly for vertices with large neighborhoods. Existing serial approaches [3], [7], [21] and shared-memory approaches [22] are constrained by the computational and memory resources of a single machine, limiting their applicability to large-scale graphs. Although distributed algorithms have been developed for butterfly counting in unsigned bipartite graphs, they do not consider edge signs and therefore cannot directly support balanced butterfly counting in signed bipartite graphs [9], [23]. This motivates the development of a distributed solution that can exploit the computational resources of multiple processing nodes while preserving the sign information required for balanced butterfly verification. Extending distributed butterfly counting to signed bipartite graphs introduces several challenges. Since a butterfly may span multiple graph partitions, local counting can miss cross-partition butterflies or result in duplicate counting when replicated neighborhoods are used. In addition, edge signs must be preserved during partitioning and communication to correctly identify balanced butterflies. The highly irregular distribution of neighborhood sizes can further lead to workload imbalance and straggler processes. Therefore, an effective distributed algorithm must address three key challenges: (i) ensuring that every balanced butterfly is counted exactly once, (ii) minimizing inter-rank communication, and (iii) balancing the computational workload across MPI ranks. To address these challenges, we propose D-BBC, a hybrid MPI+TBB algorithm that combines distributed-memory parallelism with intra-node sharedmemory parallelism. D-BBC employs workload-balanced pivot assignment, communication-efficient neighborhood exchange, and distributed reduction to achieve exact balanced 2
butterfly counting while reducing communication overhead and improving computational scalability. The main contributions of this paper are summarized as follows. We adapt and extend the Monarch algorithm [9], originally developed for counting butterflies in unsigned bipartite graphs, to the signed setting. The resulting algorithm, S-Monarch, enables exact counting of balanced butterflies in signed bipartite graphs. • We extend our prior CPU-based algorithm, BB2K [7], by designing and implementing a vertex-level parallel algorithm, M-BBC, that accelerates wedge-based balanced butterfly counting while avoiding the enumeration of unbalanced substructures. • We propose D-BBC, a distributed algorithm for exact balanced butterfly counting in signed bipartite graphs. We implement D-BBC using a hybrid MPI+TBB framework, enabling distributed-memory execution with intra-node parallelism. • We conduct extensive experiments on 15 real-world signed bipartite graphs and compare D-BBC against serial (BB2K), multi-core (M-BBC), and distributed (S-Monarch) baselines, demonstrating substantial speedups across the evaluated datasets. •
The rest of the paper is organized as follows. Section II reviews the related work. Section III presents the preliminaries and problem formulation. Section IV describes the proposed distributed algorithm. Section V presents the experimental evaluation of the proposed methods. Finally, Section VII concludes the paper. B. APPLICATIONS OF BALANCED BUTTERFLIES
We list a few applications to motivate balanced butterfly counting. Detection of multidrug combinations [2]. The relationship between drugs and targets can be classified as positive (activator) or negative (inhibitor). This sign information helps understand drug-target interactions in multi-drug combinations. As illustrated in Fig. 2, balanced butterflies are useful for detecting underlying patterns where multiple drugs exhibit similar effects on common targets, enabling the identification of synergistic effects or anomalies. Panel (a) shows examples where drug actions are coherent at each target and the cycle is balanced, whereas panel (b) shows incoherent drug actions on each target. Such patterns help identify synergistic interactions or contradictions, supporting the design of effective therapeutic strategies. • Detecting dense subgraphs [24]: Balanced butterfly counts can reveal dense regions in signed bipartite graphs using both vertex- and edge-based measures. For instance, in Fig. 3(a), vertices a, b, e, and f each participate in two balanced butterflies, while c and d are part of three. Since their induced subgraph contains only one butterfly, forming a 2-tip dense •
VOLUME 4, 2016
Mekala et al.: D-BBC: Distributed Balanced Butterfly Counting in Signed Bipartite Graphs
Drug 1
Target 1
Drug 1
Drug 2
Target 2
Drug 2
Target 1
Drug 1
Target 1
Target 2
Drug 2
Target 2
(a)
Drug 1
Target 1
Drug 2
Target 2
(b)
FIGURE 2: Coherent/incoherent butterflies in drug-target signed networks.
region. Similarly, in Fig. 3(b), the central edges (c, 3), (c, 4), (d, 3), (d, 4) each belong to a balanced butterfly, giving them a wing number of 1 and collectively defining a 1-wing. Additionally, two (3, 2)-bicliques (abc, 12) and (def, 56) have edges participating in two balanced butterflies (2-wing), highlighting highly connected substructures. Vertex g has no balanced butterflies. 1
2
3
5
4
6
during butterfly enumeration. As the size of bipartite graphs increased, subsequent research improved scalability by developing shared-memory parallel algorithms [5], [20], GPU implementations [19], I/O-efficient techniques [17], and algorithms for temporal [26], [27], uncertain [28], and streaming graphs [29]. To process graphs that exceed the memory capacity of a single machine, several distributed butterfly counting algorithms have also been proposed. Early distributed approaches employed graph partitioning and parallel execution across multiple machines [16], [23]. More recently, Tang et al. [9] proposed Monarch, a communication-efficient distributed framework that combines neighborhood expansion with workload balancing to achieve scalable exact butterfly counting in large unsigned bipartite graphs. Despite these advances, all existing distributed butterfly counting algorithms are designed exclusively for unsigned bipartite graphs. They neither preserve edge-sign information nor verify structural balance during enumeration. Consequently, these approaches cannot be directly extended to balanced butterfly counting in signed bipartite graphs, where every candidate butterfly must additionally satisfy balance constraints while avoiding duplicate counting and excessive communication across distributed graph partitions. B. BALANCED STRUCTURES IN SIGNED BIPARTITE GRAPHS
II. RELATED WORK A. BUTTERFLY COUNTING IN BIPARTITE GRAPHS
Structural balance theory has recently been extended from signed graphs to signed bipartite graphs, giving rise to several balanced cohesive structures. Derr et al. [3] introduced the balanced butterfly as the fundamental balanced motif for signed bipartite graphs and demonstrated its usefulness in characterizing structural balance. Subsequently, Sun et al. [8] investigated maximal balanced signed bicliques, while Chung et al. [21] proposed the balanced (k, ϵ)-bitruss model for discovering cohesive balanced subgraphs. More recently, Kiran et al. [7] generalized balanced butterfly analysis by proposing an efficient algorithm for balanced (2, k)-biclique counting. In addition, recent work has developed sharedmemory multi-core and GPU algorithms for exact balanced butterfly counting, significantly improving the performance of single-machine implementations [22]. Although these studies have substantially advanced balanced butterfly analysis in signed bipartite graphs, they are all limited to single-machine execution. To the best of our knowledge, no existing work has investigated exact distributed balanced butterfly counting in signed bipartite graphs. This paper addresses this gap by proposing D-BBC, the first distributed algorithm for exact balanced butterfly counting using a hybrid MPI+TBB framework.
Butterfly counting has been extensively studied in unsigned bipartite graphs due to its importance in graph mining, community detection, dense subgraph discovery, and network analysis. Early studies focused on exact butterfly counting through edge- and wedge-based enumeration strategies [4], [16], [25], significantly reducing redundant computations
We consider a signed bipartite graph G = (U, V, E = E + ∪ E − ), in which U and V are the bipartitions, and E ⊆ U × V is the edge set partitioned into positive edges E + and negative edges E − . We define sign(e) = “ + ” for
a
b
c
e
d
g
f
(a): Tip-based hierarchical dense region. 1
2
3
4
5
6
a
b
c
d
e
f
g
(b): Edge-based dense regions FIGURE 3: Comparison of vertex-centric (tip-based) and edge-centric (wing-based) dense region detection using balanced butterflies.
VOLUME 4, 2016
III. PRELIMINARIES AND PROBLEM DEFINITION
3
Mekala et al.: D-BBC: Distributed Balanced Butterfly Counting in Signed Bipartite Graphs
an edge e ∈ E + and sign(e) = “ − ” for an edge e ∈ E − . For a vertex u ∈ U , let d(u) refer to the degree of u and Γ(u) indicate the neighbors of u in G. Now, we define some basic terms for our problem. Definition 1 (Butterfly [5]). Given a bipartite graph G = (U, V, E), a butterfly is a cycle of length four induced by vertices (ui , uj , vi , vj ), where ui , uj ∈ U and vi , vj ∈ V , such that all four possible edges between {ui , uj } and {vi , vj } exist in G. Definition 2 (Balanced Butterfly [3]). A butterfly in G is a subgraph induced by four distinct vertices {u, u′ } ⊆ U and {v, v ′ } ⊆ V such that all four edges (u, v), (u, v ′ ), (u′ , v), and (u′ , v ′ ) exist in E. Let k denote the number of negative edges (i.e., edges with sign 0) in the butterfly. The butterfly is said to be balanced if k is even, otherwise unbalanced. Fig. 4 represents the balanced and unbalanced butterflies. ui vj ui vj ui vj ui vj ui vj ui vj ui vj
uk vℓ uk vℓ uk vℓ uk vℓ uk vℓ uk vℓ uk vℓ (g) (a) (b) (c) (d) (e) (f) Balanced Unbalanced FIGURE 4: Illustration of balanced and unbalanced butterflies. Definition 3 (Vertex Priority [5]). Let a, b ∈ {U ∪ V } be two vertices. We say that vertex a has higher priority than vertex b, denoted by p(a) > p(b), if one of the following conditions holds: 1) degree(a) > degree(b); 2) id(a) > id(b), if degree(a) = degree(b) Here, id(a) is the vertex ID of a. Definition 4 (Wedge (∨) [5]). Given a bipartite graph G = (U, V, E), let ui , uk ∈ U and vj ∈ V . A wedge ∨(ui , vj , uk ) is a path of length two that starts at ui , passes through vj , and ends at uk , as illustrated in Fig. 5(a). We assume an ordering on vertices in U such that p(ui ) > p(uk ). Definition 5 (Symmetric Wedge (∨s ) [7]). A wedge ∨(ui , vj , uk ) in a signed bipartite graph G = (U, V, E) is called a symmetric wedge if the two edges (ui , vj ) and (uk , vj ) have the same sign, i.e., both are positive or both are negative. Such a wedge is denoted by ∨s (ui , vj , uk ) and is illustrated in Fig. 5(b). Definition 6 (Asymmetric Wedge (∨a ) [7]). A wedge ∨(ui , vj , uk ) in a signed bipartite graph G = (U, V, E) is called an asymmetric wedge if the two edges (ui , vj ) and (uk , vj ) have different signs, i.e., one is positive and the other is negative. Such a wedge is denoted by ∨a (ui , vj , uk ) and is illustrated in Fig. 5(c). We further propose a lemma to establish the significance of these wedges. 4
ui
ui vj
uk (a) Unsigned wedge
ui vj
uk
ui vj
uk
(b) Symmetric wedges
vj uk (c) Asymmetric wedge
FIGURE 5: Wedge structures in unsigned and signed bipartite graphs. Gray solid edges represent positive edges, while red dashed edges represent negative edges.
Lemma 1. Any balanced butterfly in a signed bipartite graph can be formed either using a pair of symmetric wedges or a pair of asymmetric wedges, but not both. Proof. Considering a signed bipartite graph G = (U, V, E), let butterf ly(u, w, v, x) represent a balanced butterfly in G in which u, w ∈ U and v, x ∈ V with two wedges ∨(u, v, w) and ∨(u, x, w). case-1. ∨s (u, v, w) and ∨s (u, x, w). In this case, the number of negative edges is 0, 2, or 4, thus even. case-2. ∨a (u, v, w) and ∨a (u, x, w). In this case, the number of negative edges is 2, thus even. case-3. ∨s (u, v, w) and ∨a (u, x, w). In this case, the number of negative edges is 1 or 3, thus odd. So, this combination cannot make a balanced butterfly. This completes the proof. Problem Statement. Given a signed bipartite graph G = (U, V, E), the problem is defined as determining the total number of balanced butterflies in G. IV. ALGORITHMS
We compare D-BBC against two baselines: a state-of-theart serial algorithm and a distributed algorithm adapted from prior work on unsigned graphs. 1) Serial Baseline: BB2K
As research on balanced butterfly counting in signed bipartite graphs remains limited, we adopt our prior serial algorithm [7], denoted BB2K (where k = 2), as our first baseline. We extended this work to a multi-core algorithm, M-BBC, for exact counting of balanced butterflies in large-scale signed graphs, exploiting fine-grained parallelism to accelerate butterfly counting. (The full version is in [22]). 2) Distributed Baseline: S-Monarch
To establish a distributed baseline, we adapt Monarch [9], a distributed butterfly-counting algorithm originally designed for unsigned bipartite graphs. We extend its counting procedure to account for edge signs, thereby identifying balanced butterflies in signed bipartite graphs; we refer to this adapted version as S-Monarch. While S-Monarch supports distributed balanced butterfly counting, its enumeration does not exploit the sign structure to prune unbalanced candidates VOLUME 4, 2016
Mekala et al.: D-BBC: Distributed Balanced Butterfly Counting in Signed Bipartite Graphs
Input signed bipartite graph |L|+|R| vertices, |E| edges, N bytes total Byte-offset partitioning (N bytes → ≈ N/P bytes per rank)
[0, b1 ) Rank0
[b1 , b2 ) Rank1
···
[bP −1 , N )
· · · RankP −1
T0 T1 · · ·Tk−1
Partition into parsing ranges (Multi-threaded compute)
Parsed local edge list (Rank1 )
Rank0 Parsed local edge list
Rank1 Parsed local edge list
partial degree(v), owner(v)
partial degree(v), owner(v)
A. DISTRIBUTED BALANCED BUTTERFLY COUNTING ALGORITHM: D-BBC
The proposed Distributed Balanced Butterfly Counting (D-BBC) framework consists of five sequential phases. Each phase addresses a key challenge in distributed graph processing, including scalable graph loading, global graph representation, workload balancing, communication-efficient local subgraph construction, and parallel balanced butterfly counting. The following subsections describe each phase in detail. 1) Phase 1: Parallel Graph Loading
As illustrated in Fig. 6, the proposed D-BBC framework begins with a parallel graph loading phase, in which the input signed bipartite graph is partitioned into multiple byte ranges, allowing each MPI process to independently read a distinct portion of the graph file in parallel. To ensure correctness, the boundaries of each byte range are aligned to complete edge records, preventing graph edges from being split across adjacent MPI processes. Consequently, every edge is assigned to exactly one MPI process, ensuring that the entire graph is loaded without duplication. After reading its assigned graph chunk, each MPI process further divides its local data into multiple parsing ranges proportional to the chunk size. These parsing ranges are processed concurrently using Intel Threading Building Blocks (TBB), where each thread independently parses its assigned byte range and stores the extracted edges in a private thread-local buffer. Upon completion of all parsing tasks, the thread-local buffers are merged to construct the parsed local edge list for the corresponding MPI process. By combining inter-process parallel file access with intraprocess multithreaded parsing, the hybrid MPI-TBB strategy VOLUME 4, 2016
···
partial degree(v), owner(v)
Route vertex metadata MPI_A LLTOALLV (owner(v), partial degree(v))
.. .
Aggregate partial degrees and computes global degree(v)
.. .
vertex degrees MPI_A LLTOALLVReturn back to requesters
FIGURE 6: Phase 1
early. As a result, it performs unnecessary work on candidate butterflies that cannot contribute to the balanced count, particularly in graphs with a high fraction of unbalanced butterflies. To mitigate the above mentioned limitations, in the following section we present our proposed distributed algorithm D-BBC.
Rankp−1 Parsed local edge list
global degree(v), owner(v)
global degree(v), owner(v)
global degree(v), owner(v)
FIGURE 7: Phase 2.
exploits both distributed-memory and shared-memory parallelism, alleviating the I/O bottleneck of single-process graph loading. 2) Phase 2: Global Degree Computation
Since the input graph is distributed across MPI processes through byte-offset partitioning, the same vertex may be referenced by multiple processes, and vertex identifiers are not globally contiguous. Each process first deduplicates its local vertices and computes their partial degrees. Every distinct vertex is then routed, through a single all-to-all exchange, to its owner process, defined as owner(v) = h(v) mod P , where h(·) is a deterministic multiplicative hash function and P denotes the number of MPI processes. Each owner process consolidates duplicate occurrences of each vertex, aggregates the received partial degrees to compute its global degree, and assigns the vertex a unique compact identifier. A lightweight collective communication is then performed to establish globally contiguous identifier ranges across all owner processes, ensuring that every vertex is assigned a globally unique identifier. Finally, each owner process returns the generated indexing information only to the processes that originally referenced the corresponding vertex through a second all-to-all exchange. As illustrated in Fig. 7, the resulting distributed graph index provides globally consistent vertex identifiers and degrees, while each MPI process stores indexing information only for the vertices appearing in its local graph partition. 3) Phase 3: Workload Distribution
As illustrated in Fig. 8, the objective of this phase is to balance the computational workload among MPI processes before distributed butterfly counting begins. Since the computational cost of processing a pivot vertex depends on the sizes of the neighborhoods visited during wedge enumeration, each process first estimates the workload of the pivot 5
Mekala et al.: D-BBC: Distributed Balanced Butterfly Counting in Signed Bipartite Graphs
Rank0 Local graph global degrees
Rank1 Local graph ··· global degrees
Rankp−1 Local graph global degrees
estimate partial , vertex workload
estimate partial , vertex workload
estimate partial , vertex workload
Route vertex metadata (partial workload (v) to owners)
MPI_A LLTOALLV
. . .
Aggregate Partial Workloads Compute Global Vertex Workloads
. . .
MPI_G ATHERV Rank0 , Greedy bin-packing (Load balancing) owner’s assigned ranks
pivot owner per vertex
W (u) = d(v1 ) + d(v2 ) + d(v3 ) = 4 + 6 + 5 = 15. MPI_S CATTERV
owner’s assigned ranks
owner’s assigned ranks
MPI_A LLTOALLV
Return vertex loads back to requesters
pivot owner per vertex
pivot owner per vertex
FIGURE 8: Phase 3.
vertices appearing in its local graph partition. The workload of a pivot vertex u is estimated as X W (u) = d(v), (1) v∈Γ(u)
where Γ(u) denotes the neighbors of u, and d(v) is the degree of neighbor v. This metric approximates the computational effort required to process each pivot vertex during the local butterfly counting phase. Each MPI process computes partial workload contributions for the pivot vertices referenced in its local partition. Since the same pivot vertex may appear in multiple partitions, the partial workload information is routed to the corresponding owner process through an MPI_Alltoallv communication. Each owner process aggregates the received partial workloads to obtain the global workload estimate for every pivot vertex under its ownership (as shown in example 1). The aggregated workload is then collected at Rank0 using MPI_Gatherv. Since workload distribution is performed only once prior to the counting phase, the scheduling overhead is negligible compared with the overall execution time. Therefore, a centralized scheduler is employed to simplify workload management and to construct a globally balanced assignment without requiring iterative coordination among MPI processes. Based on the global workload information, Rank0 performs a greedy bin-packing strategy by sorting pivot vertices in descending order of workload and repeatedly assigning each pivot vertex to the MPI process with the 6
minimum accumulated workload (as shown in example 2). The resulting pivot assignments are distributed to the owner processes using MPI_Scatterv. Since multiple processes may reference the same pivot vertex, each owner process then forwards its assigned MPI rank to the corresponding requesters via a second MPI_Alltoallv communication. At the end of this phase, every MPI process knows the assigned process of each pivot vertex required for subsequent computation. This globally consistent, workload-aware pivot distribution enables balanced computation while minimizing idle time during the distributed counting phase. Example 1 (Workload estimation): Consider a pivot vertex u with neighbors Γ(u) = {v1 , v2 , v3 } having degrees 4, 6, and 5, respectively. Using Eq. (1), its workload is
After aggregating workloads from all MPI processes, the greedy scheduler assigns this pivot vertex to the MPI process with the minimum accumulated workload, thereby improving load balance across the distributed system. Example 2 (Greedy Bin-Packing): Consider six pivot vertices with workloads {15, 12, 9, 7, 6, 4} to be assigned to P = 3 MPI processes. Using a naive vertexbased assignment, where consecutive pivot vertices are assigned to each process without considering their computational costs, the resulting assignments are R0 = {u1 , u2 }, R1 = {u3 , u4 }, and R2 = {u5 , u6 }. The corresponding workloads are 27, 16, and 10, respectively, yielding a straggler ratio of 27/10 = 2.7. This indicates a significant workload imbalance: the process assigned the heaviest workload becomes the execution bottleneck, while the remaining processes remain underutilized. In contrast, the proposed workload-aware greedy binpacking strategy first sorts the pivot vertices in descending order of their estimated workloads and iteratively assigns each pivot to the process currently with the least load. This results in the assignments R0 = {u1 , u6 }, R1 = {u2 , u5 }, and R2 = {u3 , u4 }, with final workloads of 19, 18, and 16, respectively. Consequently, the straggler ratio is reduced to 19/16 ≈ 1.19, demonstrating that the proposed workloadaware assignment substantially improves load balance and minimizes the likelihood of idle processes waiting for the slowest MPI process to complete. 4) Phase 4: Distributed Local Subgraph Construction
As illustrated in Fig. 9, this phase constructs, on every MPI process, the local subgraph required to count the butterflies anchored at its assigned pivot vertices. The workload-aware pivot assignment produced in Phase 3 specifies, for each vertex, the MPI process responsible for processing it. However, the edges incident to a pivot vertex may be scattered across several processes due to the byte-offset partitioning in Phase 1. Before counting can begin, all edges and adjacency information relevant to a pivot must be gathered on the process to which that pivot is assigned. VOLUME 4, 2016
Mekala et al.: D-BBC: Distributed Balanced Butterfly Counting in Signed Bipartite Graphs
Rank0 pivot owner per vertex
Rank1 pivot owner per vertex
···
Rankp−1 pivot owner per vertex
Rank0
local subgraph
Distribute edges according MPI_A LLTOALLV to pivot ownership
construct local subgraph
construct local subgraph
local subgraph · · · local subgraph T0 T1 · · ·Tk−1
receive all edges receive all edges receive all edges of the pivots of the pivots of the pivots assigned to this process assigned to this process assigned to this process
MPI_A LLTOALLV
Rankp−1
Rank1
Exchange adjacent vertices required for 2-hop subgraph construction construct local subgraph
.. . local count
(u, w, v) sym asym · choose 2 2
by following Definition 3
local count
.. .
local count
FIGURE 9: Phase 4.
total balanced butterflies Guided by the pivot assignment, each MPI process routes every local edge to the process that owns its pivot endpoints through an MPI_Alltoallv communication. After this exchange, each process holds the complete set of edges incident to the pivot vertices assigned to it, i.e., the onehop neighborhood of each of its pivots. Because butterfly enumeration requires closing wedges of the form u → w → v, the two-hop neighborhood of each pivot is also required. A second MPI_Alltoallv communication, therefore, exchanges the adjacency lists of these intermediate vertices so that every process obtains the two-hop adjacency needed to enumerate all wedges centered at its assigned pivots. Once all required adjacency information has been received, each MPI process locally assembles its subgraph in a compact adjacency (CSR) representation, indexing its assigned pivots together with their one-hop and two-hop neighbors. This distributed construction ensures that every process holds exactly the portion of the graph needed for its assigned pivots, and no more, so that the subsequent butterfly counting phase can proceed entirely on local data without any further communication. By localizing all adjacency information ahead of counting, the proposed design confines communication to these two well-defined exchange steps and eliminates fine-grained remote access during the computation-intensive counting phase.
FIGURE 10: Phase 5.
its two edge signs. For every endpoint vertex, two bucket counters are maintained: B1 stores symmetric wedges (signsum 0 or 2), whereas B2 stores asymmetric wedges (signsum 1). Since a balanced butterfly is formed by pairing two wedges of the same type, the accumulated bucket counts are used to compute the number of balanced butterflies. To exploit shared-memory parallelism, the assigned pivot vertices are distributed among Intel TBB threads. Each thread processes a disjoint subset of pivots and maintains private bucket counters, thereby eliminating the need for synchronization during enumeration. After all threads complete, their local counts are combined to obtain the process-local butterfly count. Finally, a single MPI_Reduce operation aggregates the local counts from all MPI processes to produce the total number of balanced butterflies in the input graph. Algorithm 1 summarizes the complete workflow of the proposed D-BBC framework, consolidating the five phases described above into a single procedure, with phase boundaries marked by side comments corresponding to the subsections above. Theorem 1. Algorithm 1 correctly computes the total number of balanced butterflies in the signed bipartite graph G.
5) Phase 5: Parallel Local Balanced Butterfly Counting
As illustrated in Fig. 10, each MPI process counts the balanced butterflies anchored at its assigned pivot vertices using the local subgraph constructed in Phase 4. Since all required one-hop and two-hop neighborhood information has already been localized, this phase is performed entirely on local data without any inter-process communication. For each assigned pivot vertex, the process traverses its two-hop neighborhood to enumerate wedges. To ensure that every balanced butterfly is counted exactly once, wedge traversal follows the vertex priority rule defined in Definition 3, thereby eliminating duplicate enumeration across MPI processes. Each wedge is classified according to the sum of VOLUME 4, 2016
Proof. We prove that Algorithm 1 counts every balanced butterfly exactly once. In Phase 1, the input edge list is partitioned into disjoint byte ranges whose boundaries are aligned with complete edge records; hence every edge of E is read by exactly one MPI. In Phase 2, the partial degrees produced by different partitions are aggregated at the unique owner of each vertex, yielding the exact global degree. In Phase 3, the workload of each pivot is computed from its complete neighborhood, and the greedy assignment maps every pivot to exactly one MPI rank. The resulting assignment associates every pivot with exactly one MPI rank. Phase 4, then exchanges the 7
Mekala et al.: D-BBC: Distributed Balanced Butterfly Counting in Signed Bipartite Graphs
7
7
2
8
Sample Input Graph
Graph: edges (2, 5, 0), (2, 8, 0), (7, 5, 0), (7, 8, 0)
Phase 1
Phase 2
Rank0
Rank1
Rank2
Rank3
edge (2,5)
edge (2,8)
edge (7,5)
edge (7,8)
global degrees: deg(2) = deg(7) = deg(5) = deg(8) = 2 greedy bin-pack → pivot assignment
Phase 3
2 → Rank3 · 5 → Rank0 · 7 → Rank2 · 8 → Rank1
Phase 4
Phase 5
Rank0: piv 5 5 → {2, 7}
Rank1: piv 8 8 → {2, 7}
Rank2: piv 7 7 → {5, 8}
Rank3: piv 2 2 → {5, 8}
2 → {5, 8} 7 → {5, 8}
2 → {5, 8} 7 → {5, 8}
5 → {2, 7} 8 → {2, 7}
5 → {2, 7} 8 → {2, 7}
u=5 mid 2 (2 < 5✓) v 7 (7 < 5✗) mid 7 (7 < 5✗) no pair
count 0
u=8 mid 2 (2 < 8✓) → 8·2·5 mid 7 (7 < 8✓) → 8·7·5 c0 [5] = 2
count 1 ⋆
u=7 mid 5 (5 < 7✓) v 2 (2 < 7✓) mid 8 (8 < 7✗) c0 [2] = 1
count 0
u=2 mid 5 (5 < 2✗) mid 8 (8 < 2✗) all pruned
count 0
Reduce(+): 0 + 1 + 0 + 0 one global reduction 1 balanced butterfly the butterfly 2–5–7–8 is counted exactly once, at its highest-id pivot u = 8
FIGURE 11: End-to-end trace of the five-phase pipeline on a K(2, 2) example
edges and adjacency information required by each assigned pivot, so each rank obtains the complete one-hop and twohop neighborhood needed for its assigned pivots. It remains to show that Phase 5 counts exactly the balanced butterflies. For an assigned pivot u, the priority condition p(v) < p(u) and p(w) < p(u) ensure that each butterfly has a unique highest-priority pivot and is therefore processed by exactly one rank. For every common endpoint v, the algorithm classifies each wedge according to whether its two edge signs are equal or different, storing them in B1 [w] and B2 [w], respectively. By Lemma 1, a balanced butterfly is formed if and only if its two wedges belong to the same class: either two symmetric wedges or two asymmetric wedges. Thus, B1 [w] B2 [w] + counts exactly the balanced butterflies 2 2 associated with endpoint w. B. COMPLEXITY ANALYSIS
Let n = |U | + |V |, m = |E|, and let P and T denote the numbers of MPI ranks and threads per rank, respectively. Computation. Phase 1 reads O(N/P ) bytes and parses O(m/(P T )) edges per thread. Phase 2 deduplicates local vertices and aggregates degrees in expected O(m/P ) time 8
per rank via hashing. In Phase 3, partial workloads are obtained in O(m/P ) time, and the centralized scheduler sorts the n workloads in O(n log n) and performs the heap-based greedy assignment in O(n log P ). Phase 5 dominates: under the degree-based priority of Definition 3, each edge (u, v) is expanded only from its higher-priority endpoint at a cost equal to the degree of itsP lower-priority endpoint, so the total enumeration work is O (u,v)∈E min(d(u), d(v)) . Communication. All exchanges are sparse, since payload flows only between ranks that share graph data. In Phases 2 and 3, each rank routes O(m/P ) vertex and workload records to their owner ranks, for an aggregate volume of O(m), plus O(n) words for the scheduler’s gather and scatter operations. In Phase 4, each edge travels only to the ranks owning its (at most two) pivot endpoints, and adjacency lists are sent only to the ranks whose assigned pivots require them, yielding the enumeration P O(m) words plus at most volume O min(d(u), d(v)) . Phase 5 requires a (u,v)∈E single reduction of O(log P ) cost.
VOLUME 4, 2016
Mekala et al.: D-BBC: Distributed Balanced Butterfly Counting in Signed Bipartite Graphs
Algorithm 1: D-BBC: Distributed balanced butterfly counting algorithm. Input : Signed bipartite graph G = (U, V, E), P MPI ranks, and T threads per rank Output: β: Total number of balanced butterflies β Phase 1: Parallel graph loading Read the assigned graph partition in parallel Construct the global vertex index and compute the global vertex degrees d(·) // Phase 2 foreach vertex x ∈X U ∪ V do wload (x) ← d(y) // Phase 3 y∈Γ(x)
Sort vertices by decreasing w(·) foreach vertex x in sorted order do Assign x to the least-loaded rank Exchange aggregated higher-priority neighborhoods and construct the local subgraph // Phase 4 βr ← 0 // Phase 5 parallel for pivot u assigned to the current rank do Initialize thread-local buckets B1 and B2 foreach v ∈ Γ(u) such that p(v) < p(u) do foreach w ∈ Γ(v) such that p(w) < p(u) do if s(u, v) = s(v, w) then B1 [w] ← B1 [w] + 1 else B2 [w] ← B2 [w] + 1 foreach touched endpoint!w do ! B2 [w] B1 [w] + βr ← βr + 2 2 Reset the bucket entries corresponding to all touched endpoints β ← R EDUCE(βr , +) return β
// Phase 6
C. ILUSTRATIVE EXAMPLE
To illustrate the complete pipeline, we trace the execution of D-BBC on a small complete bipartite graph (2, 2) using P = 4 MPI processes, as shown in Fig. 11. The graph consists of four signed edges, (2, 5, 0), (2, 8, 0), (7, 5, 0), and (7, 8, 0), where {2, 7} are left vertices and {5, 8} are right vertices, forming exactly one balanced butterfly. Phase 1. The four edges are distributed one per process through byte-offset partitioning: Rank0 reads (2, 5, 0), Rank1 reads (2, 8, 0), Rank2 reads (7, 5, 0), and Rank3 reads (7, 8, 0). Phase 2. Each vertex participates in two edges, so the global degree computation yields d(2) = d(7) = d(5) = d(8) = 2. Phase 3. Using the workload estimate of Eq. (1), all pivots have equal workload, and the greedy scheduler produces a balanced assignment: vertex 5 → Rank0 , 8 → Rank1 , 7 → Rank2 , and 2 →Rank3 . Phase 4. Each process gathers the one-hop and two-hop adjacency of its assigned pivot. For instance, Rank1 , which is assigned pivot 8, receives 8 → {2, 7} together with the VOLUME 4, 2016
adjacency 2 → {5, 8} and 7 → {5, 8} needed to close the wedges centered at 8. Phase 5. Each process enumerates the wedges anchored at its pivot under the priority rule of Definition 3, which (with equal degrees) retains only intermediate and endpoint vertices whose identifier is smaller than the pivot. Consequently, the single butterfly is counted at exactly one canonical pivot, its highest-identifier vertex u = 8: At Rank1 (u = 8), both wedges 8 → 2 → 5 and 8 → 7 → 5 are valid, giving c0 [5] = 2 and, by 22 = 1 butterfly. • At the remaining pivots (u = 5, 7, 2), the priority rule prunes one or both endpoints, so no complete wedge pair is formed and each contributes a count of 0. •
A single MPI_Reduce then sums the local counts, 0 + 1 + 0 + 0 = 1, yielding the correct total of one balanced butterfly. This example confirms that the priority-based pruning enumerates each butterfly exactly once, even though its vertices are distributed across multiple processes. V. EXPERIMENTAL EVALUATION
In this section, we assess the performance of the proposed algorithm. Computing Resources: We implemented all algorithms in C++. Experiments were conducted on an HPC cluster using the big_compute_amd_9655 partition. Each compute node is equipped with two AMD EPYC 9655 processors, providing 192 physical CPU cores, 385 GB of main memory, and a 200 Gbps Mellanox HDR InfiniBand interconnect. The distributed implementation employs MPI for inter-node communication and Intel TBB for shared-memory parallelism. All algorithms, including the baseline methods, were evaluated under the same experimental settings. Algorithms: We evaluate the following algorithms. BB2K: A serial algorithm from our prior work [7]. M-BBC: The proposed shared-memory multi-core algorithm for exact counting of balanced butterflies in large-scale signed graphs, exploiting fine-grained parallelism to accelerate butterfly counting [22]. • S-Monarch: An adaptation and extension of the distributed butterfly-counting algorithm [9] for balanced butterfly counting in signed bipartite graphs. • D-BBC: The proposed hybrid distributed-memory algorithm for counting balanced butterflies, employing MPI for inter-node communication and Intel oneTBB for intra-node parallelism. • •
Datasets Description: We evaluate the proposed algorithms on a diverse collection of 15 real-world bipartite datasets, covering a wide range of graph sizes and densities. The SE and HO datasets are obtained from the signed bipartite network repository1 . The DBLP, MV, KDD, AOL, and NX datasets are collected from the bipartite network repository2 . The remaining datasets, namely NAP, BC, NIPS, 1 https://github.com/tylersnetwork/signed_bipartite_networks 2 https://renchi.ac.cn/datasets/
9
Mekala et al.: D-BBC: Distributed Balanced Butterfly Counting in Signed Bipartite Graphs
TABLE 1: Characteristics of the datasets with BBF (balanced butterflies count). Dataset Senate (SE) DBLP (DBLP) House (HO) Wiki-Nap (NAP) BookCrossing (BC) NIPS-Papers (NIPS) Last.fm (LF) Movielens (MV) Jester 150 (JE) KDD Cup (KDD) Digg Votes (DG) AOL (AOL) Epinions (EP) Netflix (NX) Yahoo (YH)
|U | 145 6,001 515 1,753 77,802 1,500 992 6,040 50,692 255,170 139,409 4,811,647 120,492 480,189 1,000,990
|V | 1,201 1,308 1,281 25,881 185,955 12,375 174,077 3,706 140 1,848,114 3,553 1,632,788 755,760 17,770 624,961
LF, JE, DG, EP, and YH, are obtained from the KONECT collection3 . Among these datasets, SE, HO, BC, LF, and EP are naturally signed bipartite graphs and have been widely used in previous studies on balanced butterfly counting and maximal balanced biclique enumeration [3], [8], [21]. The JE and MV datasets are rating networks that can be regarded as signed networks, as in prior work [8], [30], [31]. Following the convention adopted in these studies, ratings are converted into edge signs. The remaining datasets (DBLP, NAP, NIPS, KDD, AOL, DG, and YH) are originally unsigned bipartite graphs. Following the experimental setting of [32], we generate signed bipartite graphs by randomly assigning 30% of the edges as negative and the remaining 70% as positive. Several datasets, such as DG, NAP, and LF, contain duplicate edges with conflicting signs, which are resolved by retaining the latest interaction. A summary of all datasets is provided in Table 1 along with BBF (balanced butterflies count). A. PERFORMANCE OF THE PROPOSED ALGORITHMS
The experimental evaluation consists of the following studies: • Performance Comparison: Comparison of the serial, shared-memory parallel, and distributed implementations on a single node. • Runtime Breakdown: Analysis of the execution time by decomposing the total runtime into the I/O, Index, Exchange, Count, and Reduce phases. • Hybrid Configuration Analysis: Evaluation of different MPI rank and TBB thread configurations to identify the best-performing hybrid execution setup. • Load Balancing: Evaluation of the workload distribution among MPI processes. • Communication Analysis: Analysis of communication volume with varying MPI ranks and across multiple compute nodes. 3 http://konect.cc/networks/
10
|E| 27,083 29,256 114,378 265,546 433,652 746, 315 898,062 1,000,208 1,728,847 2,766,393 3,010,197 10,741,953 13,668,320 100,480,507 256,804,235
Density 0.155 0.004 0.174 0.006 0.00003 0.00003 0.005 0.045 0.244 0.0000059 0.006 0.0000014 0.00015 0.012 0.0004
BBF 15.32 M 0.85 M 280.79 M 2.24 B 1.11 M 3.75 B 2.35 B 8.90 B 136.88 B 9.20 M 15.06 B 104.47 M 158.33 B 8.39 T 5.20 T
Multi-node Scalability Analysis: Evaluation of countphase performance and communication overhead on one, two, and four compute nodes. We compare the proposed algorithm with the baseline methods in terms of execution time on the aforementioned datasets. The serial baseline (BB2K) is executed using a single CPU core, the shared-memory baseline (M-BBC) is evaluated on a single compute node with 192 threads, and the proposed distributed algorithm (D-BBC) is evaluated on 1, 2, and 4 compute nodes using multiple MPI processes and TBB thread configurations. •
B. PERFORMANCE COMPARISON
Figure 12 compares the counting time of the proposed D-BBC against the serial BB2K and the shared-memory M-BBC across all 15 datasets. Across the 13 datasets on which the serial baseline completed, D-BBC reduces the counting time by 31.6× to 3723.9× over BB2K, with an average speedup of 540.9×. Relative to the shared-memory M-BBC, D-BBC achieves an additional 2.73× (NAP) to 49.4× (DG) improvement across all 15 datasets, with an average speedup of 11.9×. For the two largest datasets, NX and YH, the serial BB2K did not finish within the 5-hour execution limit. Both parallel methods, however, processed these graphs successfully: D-BBC reduces the counting time from 30.9 s to 3.23 s on NX (9.6×) and from 154.95 s to 31.63 s on YH (4.9×) relative to M-BBC, demonstrating its ability to scale to large-scale signed bipartite graphs that are intractable for a serial implementation. Figure 13 compares the counting time of D-BBC with the distributed S-Monarch baseline across all datasets. Among the 13 datasets completed by S-Monarch, D-BBC consistently outperforms the baseline, achieving speedups ranging from 2.00× (DBLP) to 96.00× (JE), with an average speedup of 21.07×. For datasets with relatively few balanced butterflies, such as DBLP, BC, and KDD, the performance gap is small because the overhead of explicit balancedbutterfly verification is limited. As illustrated in Figure 13, VOLUME 4, 2016
Mekala et al.: D-BBC: Distributed Balanced Butterfly Counting in Signed Bipartite Graphs
M-BBC
D-BBC
> 5_hrs
Y H
N X
EP
AO L
D G
K D D
JE
V M
LF
S IP N
BC
H O
NA P
D
BL P
102 101 100 10−1 10−2 10−3 SE
Execution Time (seconds)
BB2K
Datasets
FIGURE 12: Counting-time comparison of BB2K, M-BBC, and D-BBC across all datasets. TABLE 2: Configurations used in the experiments. Configuration MPI Ranks TBB Threads
C1 C2 1 2 192 96
D-BBC
S-Monarch
C3 3 64
C4 4 48
Counting Time (s)
103 102 101 100 10−1 10−2 S D E BL P H O NA P BC N IP S LF M V JE K D D D G AO L EP N X Y H
10−3
Datasets
FIGURE 13: Counting-time comparison between D-BBC and the S-Monarch baseline across all datasets (log scale). the performance gap becomes more pronounced as the graph size increases. In particular, S-Monarch fails to complete on the NX and YH datasets due to their substantially higher computational cost and memory requirements. In contrast, D-BBC successfully processes NX and YH in 2.68, s and 29.20, s, respectively, demonstrating its superior scalability on large graphs. The improved performance of D-BBC is primarily due to the elimination of the explicit balancedbutterfly verification required by the adapted S-Monarch baseline.
C5 6 32
C6 8 24
C7 12 16
C8 16 12
C9 24 8
C10 32 6
C11 48 4
C12 64 3
Exchange (all-to-all wedge/edge communication), Count (local butterfly counting), and Reduce (global aggregation of local butterfly counts). Table 2 summarizes the hybrid MPI+TBB configurations evaluated in the experiments. Each configuration uses 192 CPU cores, varying the number of MPI ranks and TBB threads. Figure 14 presents the runtime breakdown for six representative datasets, including two large (YH and NX), two medium (AOL and EP), and two small (DG and DBLP) graphs, across the twelve hybrid configurations (C1 –C12 ). This analysis highlights how the execution time of each phase evolves with different MPI/TBB configurations and graph sizes. As shown in Figure 14, the Count phase dominates the execution time for large datasets, whereas its contribution decreases for medium and small datasets. Increasing the number of MPI ranks significantly reduces the counting time but increases the Exchange time because of additional interprocess communication. For large graphs, the reduction in computation outweighs the communication overhead, leading to the best overall performance. In contrast, for medium and small graphs, communication overhead becomes increasingly significant, resulting in diminishing performance gains. Across all datasets, the IO, Index, and Reduce phases remain relatively small. Figure 15 compares the end-to-end execution time (including I/O, Communication, and Counting phase) of D-BBC and S-Monarch across all datasets. D-BBC consistently achieves lower end-to-end execution times, confirming the effectiveness of the proposed approach.
C. RUNTIME BREAKDOWN AND SCALING ANALYSIS
To understand how execution time is distributed across the proposed algorithm, we decompose the end-to-end runtime into five phases: IO (parallel graph ingestion), Index (global vertex indexing, degree computation, and pivot assignment), VOLUME 4, 2016
D. HYBRID CONFIGURATION ANALYSIS
Figure 16 presents the speedup of the six largest datasets under different hybrid MPI+TBB configurations, using the single-rank configuration (C1 ) as the baseline. The speedup 11
Mekala et al.: D-BBC: Distributed Balanced Butterfly Counting in Signed Bipartite Graphs
IO
Index
Exchange
Count
Reduce
0.2 15
0.6 10
5 · 10−2
0.2
5
0
0
0 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12
0.4
C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12
0.1
C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12
Time (s)
0.8 0.15
Configuration DBLP
Configuration DG
Configuration AOL
40
Time (s)
6
150
30
4
100 20
2
50
10 0 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12
C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12
0
C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12
0 Configuration EP
Configuration NX
Configuration YH
FIGURE 14: Per-phase execution-time breakdown across configurations. D-BBC
S-Monarch
End-to-End Time (s)
101 100 10−1
EP
L AO
G D
D D K
JE
V M
LF
S N IP
BC
P NA
H O
P D BL
SE
10−2
Datasets
FIGURE 15: End-to-end execution time of D-BBC andthe S-Monarch baseline across all datasets.
generally increases with the number of MPI ranks, demonstrating the effectiveness of the proposed hybrid parallelization strategy. The largest speedups are observed for the computation-intensive datasets, where additional parallelism significantly reduces butterfly-counting time. At higher MPI rank counts, the performance gain gradually saturates as communication overhead increasingly offsets the reduction in computation time. Overall, configurations C9 –C12 consistently deliver the highest speedups, indicating an effective balance between inter-process communication and intraprocess thread parallelism. E. LOAD BALANCING ANALYSIS
Table 3 reports the dynamic load imbalance, measured by count the straggler ratio (β = tcount max /tmin ), across all 15 datasets and 12 hybrid configurations. Since the proposed partitioning balances the estimated workload, the remaining imbalance 12
reflects variations in the actual cost of counting during execution. Overall, the proposed strategy achieves good dynamic load balancing, particularly for the large, computation-intensive datasets such as YH and NX, where the straggler ratio remains relatively low across most configurations. In contrast, smaller datasets, including DBLP, SE, NAP, and HO, exhibit higher imbalance under fine-grained configurations because their limited computational workload amplifies executiontime variations across MPI ranks. However, these datasets have very short execution times, and therefore the increased imbalance has a negligible impact on the overall runtime. These results demonstrate that the proposed partitioning strategy effectively balances the workloads of large graphs, where load balancing has the greatest impact on performance, while maintaining acceptable imbalance across the remaining datasets. VOLUME 4, 2016
Mekala et al.: D-BBC: Distributed Balanced Butterfly Counting in Signed Bipartite Graphs
TABLE 3: Single-node dynamic load imbalance across all configurations. Configuration (MPI ranks × threads/rank) Dataset
C1
C2
C3
C4
C5
C6
C7
C8
C9
C10
C11
C12
1×192
2×96
3×64
4×48
6×32
8×24
12×16
16×12
24×8
32×6
48×4
64×3
YH NX AOL EP KDD DG JE LF BC MV NIPS NAP HO DBLP SE
1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00
1.11 1.02 1.17 1.03 1.03 1.16 1.05 1.10 1.05 1.78 1.28 1.07 1.18 1.29 1.07
1.84 1.39 1.41 1.07 1.34 1.02 1.76 1.38 1.55 4.20 1.80 1.94 1.94 1.48 1.19
1.68 1.22 1.51 1.22 1.10 1.12 1.35 1.40 1.25 1.24 1.71 1.13 1.90 1.48 1.21
1.70 1.21 1.94 1.46 1.06 1.24 1.81 1.53 1.09 1.47 1.87 1.66 1.51 1.60 1.21
1.43 1.32 2.02 1.55 1.15 1.45 1.64 1.56 1.22 1.68 1.98 2.10 1.72 1.20 1.46
1.54 1.35 2.42 1.66 1.23 1.37 1.93 1.67 1.50 1.43 1.39 2.14 1.42 1.35 1.57
1.39 1.25 2.40 1.69 1.10 1.41 1.62 1.44 1.44 1.87 1.82 2.16 2.02 1.73 1.75
1.34 1.56 2.54 1.82 1.24 1.44 1.76 1.50 1.56 1.57 1.57 2.54 2.15 2.05 2.02
1.27 1.29 2.64 1.95 1.56 1.59 1.72 1.82 1.56 1.62 1.46 2.52 2.33 2.43 2.29
1.19 1.66 2.67 2.04 1.77 1.51 1.92 1.75 1.73 1.58 1.74 2.71 2.72 2.55 2.59
1.19 1.84 2.89 2.28 1.71 1.89 1.93 1.66 1.40 1.66 1.65 2.91 2.93 2.66 2.9
YH EP
NX KDD
YH EP
AOL DG
10
Bytes sent (GB)
Speedup (×)
AOL DBLP
102
8 6 4 2 0 C1
NX DG
100
10−2 1
C2
C3
C4
C5
C6
C7
C8
C9
C10 C11 C12
Configuration
FIGURE 16: Speedup for different hybrid MPI+TBB configurations, with C1 as the baseline.
2
4
8
16
32
64
MPI ranks (threads/rank = 192/ranks)
FIGURE 17: Communication volume (total bytes sent, summed over all MPI ranks) as a function of the number of MPI ranks for six representative datasets.
F. COMMUNICATION ANALYSIS
G. MULTI-NODE SCALABILITY ANALYSIS
Figure 17 illustrates the total communication volume (bytes sent) for six representative datasets as the number of MPI ranks increases while maintaining a fixed worker budget of 192 CPU cores. For all datasets, the communication volume increases monotonically with the number of MPI ranks. For example, the communication volume of YH grows from 11.0 GB with a single MPI rank to 193.8 GB with 48 MPI ranks, while NX increases from 4.32 GB to 100.36 GB. The increase in communication volume is expected because partitioning the graph among more MPI processes creates additional boundary vertices and wedges that must be exchanged between processes. Although the total amount of communicated data increases, the runtime of the communication phase on a single node decreases due to efficient sharedmemory communication and reduced per-rank computational workload. Consequently, the additional communication volume does not become a performance bottleneck in the singlenode experiments.
Figure 18a shows the count-phase execution time of the proposed distributed algorithm on one, two, and four compute nodes. The execution time consistently decreases as the number of nodes increases, indicating the strong scalability of the proposed approach. Larger datasets benefit more from distributed execution due to their higher computational workload, whereas smaller datasets achieve relatively lower improvements. Figure 18b presents the communication volume (bytes sent) of the proposed distributed algorithm on one, two, and four compute nodes. As the deployment scales out, the communication volume increases because finer graph partitioning across more MPI processes introduces additional boundary vertices and wedges that require inter-process communication. Despite this increase, the counting phase continues to scale effectively across all datasets, with execution time consistently decreasing as more compute nodes are employed. Figure 19a presents the communication (exchange) time achieved using the best MPI/thread configuration for each
VOLUME 4, 2016
13
Mekala et al.: D-BBC: Distributed Balanced Butterfly Counting in Signed Bipartite Graphs
2 nodes
4 nodes
1 node
2 nodes
4 nodes
3
10
102
Bytes sent (GB)
Count-phase time (s)
1 node
101 100 10−1
102 101 100
10−2 DG
KDD
EP
AOL
NX
YH
DG
KDD
EP
AOL
NX
YH
(b) Communication volume (bytes sent).
(a) Count-phase time.
FIGURE 18: Multi-node behavior on the six largest datasets. 1 node
2 nodes
4 nodes
1 node
2 nodes
4 nodes
105 Peak RSS per rank (MB)
Exchange time (s)
102
101
100
10−1 DG
KDD
EP
AOL
NX
YH
Dataset (a) Exchange time.
104
103
102
DG
KDD
EP
AOL
NX
YH
Dataset
(b) Peak memory usage.
FIGURE 19: Communication and memory analysis of the proposed distributed algorithm. (a) Exchange time decreases as the number of nodes increases due to improved communication parallelism. (b) Peak memory usage per MPI rank decreases as the graph is partitioned across more processes.
node count. As the number of MPI ranks increases, the communication volume increases because the pivot exchange involves more graph partitions, leading to additional crossrank communication. Consequently, the total number of bytes exchanged is primarily determined by the number of physical nodes. Despite the increase in communication volume, communication time decreases as execution scales from 1 to 4 nodes. This improvement is achieved by distributing the communication workload across more MPI processes and network links, allowing each process to exchange a smaller portion of the data in parallel. Overall, these results demonstrate that the communication phase scales efficiently and does not become the primary performance bottleneck as the distributed execution scales across multiple nodes. Figure 19b shows the peak memory usage (RSS) per MPI rank for the best MPI/thread configuration at each node count. As the number of nodes and MPI ranks increases, the memory usage per rank consistently decreases because the input graph is partitioned across more MPI processes, allowing each process to store only a smaller portion of the graph. For example, peak memory usage for the NX dataset decreases from approximately 25.9 GB to 17 GB, 14
and for the YH dataset from about 55 GB to 40 GB. These results demonstrate that the proposed distributed approach effectively reduces per-rank memory usage, enabling the processing of larger graphs that may not fit within the memory capacity of a single compute node. VI. ABLATION STUDY: A. PURE MPI VS. HYBRID MPI+TBB
To evaluate the contribution of the hybrid programming model, we compare D-BBC using 24 MPI ranks with 8 TBB threads per rank against a pure-MPI configuration using 192 MPI ranks with one thread per rank. Both configurations utilize the same total of 192 CPU cores, ensuring a fair comparison while isolating the effect of intra-process thread parallelism. Figure 20 reports the count-phase execution time across all datasets. The hybrid configuration consistently outperforms the pure-MPI configuration, achieving an average speedup of 20.2×. The largest improvements are observed on the smaller datasets, reaching up to 97× on DBLP, where the computation is relatively small and the communication and synchronization overhead of managing 192 MPI processes VOLUME 4, 2016
Mekala et al.: D-BBC: Distributed Balanced Butterfly Counting in Signed Bipartite Graphs
becomes more significant. As the dataset size increases, the counting workload dominates the execution time, reducing the relative impact of MPI overhead. Consequently, the speedup decreases to 1.9× on NX and 2.1× on YH. Overall, the results demonstrate that combining MPI with shared-memory parallelism significantly reduces communication overhead while maintaining efficient utilization of the available CPU cores. Pure MPI (192×1)
Hybrid (24×8)
Count-phase time (s)
102
SRnaive − SRload-aware × 100, (2) SRnaive where SRnaive and SRload-aware denote the straggler ratios obtained using the naive vertex-centric and the proposed load-aware partitioning strategies, respectively. Improvement (%) =
101 100 10−1 10−2
C. SIGN DISTRIBUTION S D E BL P H O NA P B N C IP S LF M V JE K D D D G AO L EP N X Y H
10−3
Datasets
FIGURE 20: Count-phase time of the hybrid configuration versus a pure-MPI.
Vertex-Centric
Load-Aware INF
6 Straggler Ratio
modest improvement (2.63%) since its workload is already relatively balanced. For the largest dataset, YH, the naive partitioning fails to complete due to severe workload skew and memory exhaustion, whereas the proposed load-aware strategy successfully completes execution with a straggler ratio of 1.43. These results demonstrate that workload-aware partitioning effectively mitigates workload imbalance and improves the robustness of the proposed distributed algorithm. NOTE: The percentage improvement in workload balance is computed as
4 2
D. SYMMETRIC AND ASYMMETRIC WEDGES
0 DG
KDD
AOL
EP
NX
YH
Datasets
FIGURE 21: Comparison of the straggler ratio achieved by the vertex-centric and load-aware partitioning strategies. Lower values indicate better workload balance; INF indicates that the vertex-centric approach did not terminate within the allowed execution time.
B. EFFECTIVENESS OF LOAD-AWARE PARTITIONING.
Figure 21 compares the workload imbalance achieved by the naive vertex-centric and the proposed load-aware partitioning strategies. The proposed method consistently reduces the straggler ratio across all datasets. The largest improvement is observed on AOL, where the straggler ratio decreases from 5.67 to 2.89 (48.97%), followed by KDD (32.90%), EP (28.04%), and DG (13.04%). In contrast, NX shows only a VOLUME 4, 2016
To assess the robustness of the proposed framework under different edge-sign distributions, we vary the positiveto-negative edge ratio from 10% to 90% while preserving the underlying graph topology. Figure 22 shows that both the counting time and communication time remain nearly unchanged across all evaluated datasets, indicating that the computational cost of the proposed algorithm is largely independent of the edge-sign distribution. In contrast, the number of balanced butterflies varies substantially with the sign ratio, as expected, because balanced butterfly formation is directly determined by the arrangement of positive and negative edge labels. Overall, these results demonstrate that the proposed framework delivers stable runtime performance across diverse sign distributions while accurately reflecting the corresponding changes in balanced butterfly counts.
To evaluate the effectiveness of separating symmetric and asymmetric wedges into distinct buckets, we compare the proposed approach with a baseline that does not employ this separation. Without bucket-based separation, the algorithm must first enumerate candidate wedge pairs and then explicitly verify whether each pair forms a balanced butterfly by checking the signs of the four edges in the resulting 4-cycle. This additional enumeration and verification introduces substantial computational overhead, as many candidate 4-cycles must be examined and subsequently discarded because they correspond to unbalanced butterflies. The results presented in Table 4 demonstrate the performance advantage of explicitly separating symmetric and asymmetric wedges into distinct buckets. VII. CONCLUDING REMARKS
We studied balanced butterfly counting in signed bipartite graphs and presented D-BBC, a distributed algorithm based on a hybrid MPI+TBB model with a workload-aware partitioning strategy. Experiments on 15 real-world datasets show 15
Mekala et al.: D-BBC: Distributed Balanced Butterfly Counting in Signed Bipartite Graphs
NAP
−1
10
10−2 10−3 10
KDD
NIPS
Exchange time (s)
Count time (s)
DBLP
30 50 70 90 Positive edge ratio (%)
DG
AOL
100 10−1 10−2 10
30 50 70 90 Positive edge ratio (%)
FIGURE 22: Impact of varying the positive-to-negative edge ratio on counting time and exchange time across all datasets. TABLE 4: Study of symmetric-asymmetric wedge separation. Dataset SE HO
Without Wedge (s) 3.69 157.00
With Separate Wedge (s) 0.0.031628 0.935430
Speedup 123× 128×
that D-BBC consistently outperforms state-of-the-art serial, shared-memory, and distributed (S-Monarch) baselines, and scales to large graphs on which S-Monarch runs out of memory. The phase-wise analysis confirms that the counting phase scales efficiently with parallelism, while communication gradually becomes the dominant cost in multi-node execution. As future work, we plan to reduce boundarywedge communication through locality- and communicationaware partitioning, and to extend D-BBC to web-scale graphs and to temporal, dynamic, and higher-order motif counting. REFERENCES [1] C. Chen, Y. Wu, R. Sun, and X. Wang, “Maximum signed θ -clique identification in large signed graphs,” IEEE Transactions on Knowledge and Data Engineering, vol. 35, no. 2, pp. 1791–1802, 2021. [2] N. B. Torres and C. Altafini, “Drug combinatorics and side effect estimation on the signed human drug-target network,” BMC systems biology, vol. 10, no. 1, p. 74, 2016. [3] T. Derr, C. Johnson, Y. Chang, and J. Tang, “Balance in signed bipartite networks,” in Proceedings of the 28th ACM International Conference on Information and Knowledge Management, pp. 1221–1230, 2019. [4] S.-V. Sanei-Mehri, A. E. Sariyuce, and S. Tirthapura, “Butterfly counting in bipartite networks,” in Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 2150–2159, 2018. [5] K. Wang, X. Lin, L. Qin, W. Zhang, and Y. Zhang, “Vertex priority based butterfly counting for large-scale bipartite networks.,” PVLDB, 2019. [6] K. Wang, X. Lin, L. Qin, W. Zhang, and Y. Zhang, “Accelerated butterfly counting with vertex priority on bipartite graphs,” The VLDB Journal, vol. 32, no. 2, pp. 257–281, 2023. [7] M. Kiran, A. Das, and S. Banerjee, “Efficient counting of balanced (2, k)-bicliques in signed bipartite graphs,” in 2024 IEEE International Conference on Big Data (BigData), pp. 735–740, IEEE, 2024. [8] R. Sun, Y. Wu, C. Chen, X. Wang, W. Zhang, and X. Lin, “Maximal balanced signed biclique enumeration in signed bipartite graphs,” in 2022 IEEE 38th International Conference on Data Engineering (ICDE), pp. 1887–1899, IEEE, 2022. [9] Y. Tang, M. Bendre, and M. Das, “Monarch: Distributed butterfly counting for large-scale bipartite graph,” in 2024 IEEE International Conference on Big Data (BigData), pp. 799–804, IEEE, 2024. [10] F. Heider, “Attitudes and cognitive organization,” The Journal of psychology, vol. 21, no. 1, pp. 107–112, 1946. 16
[11] K. Yao, L. Chang, and J. X. Yu, “Identifying similar-bicliques in bipartite graphs,” Proceedings of the VLDB Endowment, vol. 15, no. 11, pp. 3085– 3097, 2022. [12] B. Lyu, L. Qin, X. Lin, Y. Zhang, Z. Qian, and J. Zhou, “Maximum biclique search at billion scale,” Proceedings of the VLDB Endowment, 2020. [13] L. Chen, C. Liu, R. Zhou, J. Xu, and J. Li, “Efficient maximal biclique enumeration for large sparse bipartite graphs,” Proceedings of the VLDB Endowment, vol. 15, no. 8, pp. 1559–1571, 2022. [14] A. Zhou, Y. Wang, and L. Chen, “Butterfly counting and bitruss decomposition on uncertain bipartite graphs,” The VLDB Journal, vol. 32, no. 5, pp. 1013–1036, 2023. [15] W. Luo, Q. Yang, Y. Fang, and X. Zhou, “Efficient core maintenance in large bipartite graphs,” Proceedings of the ACM on Management of Data, vol. 1, no. 3, pp. 1–26, 2023. [16] J. Wang, A. W.-C. Fu, and J. Cheng, “Rectangle counting in large bipartite graphs,” in 2014 IEEE International Congress on Big Data, pp. 17–24, IEEE, 2014. [17] J. Shi and J. Shun, “Parallel algorithms for butterfly computations,” in Massive Graph Analytics, pp. 287–330, Chapman and Hall/CRC, 2022. [18] R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon, “Network motifs: simple building blocks of complex networks,” Science, vol. 298, no. 5594, pp. 824–827, 2002. [19] Y. Xia, F. Zhang, Q. Xu, M. Zhang, Z. Yao, L. Lu, X. Du, D. Deng, B. He, and S. Ma, “Gpu-based butterfly counting,” The VLDB Journal, vol. 33, no. 5, pp. 1543–1567, 2024. [20] Z. Wang, L. Lai, Y. Liu, B. Shui, C. Tian, and S. Zhong, “Parallelization of butterfly counting on hierarchical memory,” The VLDB Journal, vol. 33, no. 5, pp. 1453–1484, 2024. [21] K. H. Chung, A. Zhou, Y. Wang, and L. Chen, “Maximum balanced (k, ϵ)bitruss detection in signed bipartite graph,” Proceedings of the VLDB Endowment, vol. 17, no. 3, pp. 332–344, 2023. [22] M. Kiran, A. Das, S. Banerjee, and T. Ray, “Multi-core & gpu-based balanced butterfly counting in signed bipartite graphs,” arXiv preprint arXiv:2601.17707, 2026. [23] T. Weng, X. Zhou, K. Li, K.-L. Tan, and K. Li, “Distributed approaches to butterfly analysis on large dynamic bipartite graphs,” IEEE Transactions on Parallel and Distributed Systems, vol. 34, no. 2, pp. 431–445, 2022. [24] A. E. Sarıyüce and A. Pinar, “Peeling bipartite networks for dense subgraph discovery,” in Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, pp. 504–512, 2018. [25] R. Zhu, Z. Zou, and J. Li, “Fast rectangle counting on massive networks,” in 2018 IEEE International Conference on Data Mining (ICDM), pp. 847– 856, IEEE, 2018. [26] X. Cai, X. Ke, K. Wang, L. Chen, T. Zhang, Q. Liu, and Y. Gao, “Efficient temporal butterfly counting and enumeration on temporal bipartite graphs,” arXiv preprint arXiv:2306.00893, 2023. [27] S. Papadias, Z. Kaoudi, V. Pandey, J.-A. Quiané-Ruiz, and V. Markl, “Counting butterflies in fully dynamic bipartite graph streams,” in 2024 IEEE 40th International Conference on Data Engineering (ICDE), pp. 2917–2930, IEEE, 2024. [28] A. Zhou, Y. Wang, and L. Chen, “Butterfly counting on uncertain bipartite graphs,” Proceedings of the VLDB Endowment, vol. 15, no. 2, pp. 211– 223, 2021. VOLUME 4, 2016
Mekala et al.: D-BBC: Distributed Balanced Butterfly Counting in Signed Bipartite Graphs
[29] L. Meng, L. Yuan, X. Lin, C. Li, K. Wang, and W. Zhang, “Counting butterflies over streaming bipartite graphs with duplicate edges,” IEEE Transactions on Knowledge and Data Engineering, 2026. [30] W. Kudo, M. Nishiguchi, and F. Toriumi, “Gcnext: graph convolutional network with expanded balance theory for fraudulent user detection,” Social Network Analysis and Mining, vol. 10, no. 1, p. 85, 2020. [31] K. Cheng, J. Li, J. Tang, and H. Liu, “Unsupervised sentiment analysis with signed social networks,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 31, 2017. [32] R.-H. Li, Q. Dai, L. Qin, G. Wang, X. Xiao, J. X. Yu, and S. Qiao, “Efficient signed clique search in signed networks,” in 2018 IEEE 34th International conference on data engineering (ICDE), pp. 245–256, IEEE, 2018.
MEKALA KIRAN was born in Khammam, Telangana, India, in 1994. He received the B.Tech. degree in Computer Science and Engineering from Jawaharlal Nehru Technological University (JNTU), Hyderabad, India, in 2016, and the M.Tech. degree in Computer Science and Engineering from Jawaharlal Nehru Technological University (JNTU), Hyderabad, India, in 2019. He is currently pursuing a Ph.D. degree in Computer Science and Information Systems at Birla Institute of Technology and Science (BITS) Pilani, Hyderabad Campus, Hyderabad, India. His research interests include graph algorithms and high-performance computing.
APURBA DAS is an Assistant Professor in the Department of Computer Science and Information Systems at Birla Institute of Technology and Science, Hyderabad Campus. He earned his PhD in Computer Engineering from Iowa State University, USA, in 2019, and M.Tech in Computer Science from the Indian Statistical Institute, Kolkata. He completed a postdoctoral fellowship at the School of Computing, National University of Singapore, from 2019 to 2020. His research interests include large-scale graph analysis, parallel algorithms, data stream mining, and related areas.
SUMAN BANERJEE obtained his Ph.D. from the Indian Institute of Technology Kharagpur in 2020. After a short stay at the Indian Institute of Technology Gandhinagar as a Post Doctoral Fellow, he joined the Department of Computer Science and Engineering, Indian Institute of Technology Jammu, as an assistant professor in the same year. His research interests include algorithm design with a particular focus on social and information network analysis, scheduling and schedulability analysis in cloud computing systems, distributed and multi-core systems, real-time systems, etc.; structural pattern analysis for time-varying graphs; graph theory and graph algorithms; and parameterised complexity. He has published more than 50 research papers in international journals and conferences.
VOLUME 4, 2016
17