Efficient (α, β)-core Computation and On-the-fly Query at Billion Scale with GPUs Qingshuai Feng1 , Shunyang Li2 , Kai Wang3 , Xuemin Lin3 , Kongzhang Hao4 , Long Yuan5 1
Great Bay University; 2 Alibaba Group; 3 Shanghai Jiao Tong University; 4 University of New South Wales; 5 Wuhan University of Technology
arXiv:2606.07148v1 [cs.DB] 5 Jun 2026
[email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]
Abstract—In bipartite graphs, (α, β)-core is a widely used model for cohesive subgraph mining. Specifically, an (α, β)-core is a maximal subgraph in which each vertex in the upper layer has degree at least α, and each vertex in the lower layer has degree at least β. The state-of-the-art CPU-based solutions incur extensive costs to construct an index structure for all α and β combinations, leading to scalability challenges on large bipartite graphs. Moreover, on-the-fly queries, which aim to determine whether an edge update belongs to a target (α, β)-core, are essential for real-time applications such as fraud monitoring and recommendation systems. However, existing index-based methods struggle to support such queries at scale due to their high maintenance overhead. In this paper, we investigate how to leverage GPU architectures to enable efficient (α, β)-core computation and support on-the-fly queries. While GPUs are widely used to accelerate graph processing, their limited memory capacity makes it impractical to store large index structures. To address this issue, we propose GCC, an index-free GPUbased peeling algorithm that accelerates (α, β)-core computation via warp-centric processing. To further improve efficiency, we develop GCC+, which leverages the nested property of (α, β)core with a core-based early pruning strategy. For handling onthe-fly queries, we propose GFQ, a connectivity-aware algorithm that significantly narrows the computation scope by leveraging connected component information, thereby avoiding full-graph peeling. Extensive experiments on 11 datasets demonstrate that our proposed techniques outperform existing CPU-based solutions in terms of both space and time efficiency. Index Terms—GPU, Cohesive subgraph, Bipartite graphs.
I. I NTRODUCTION Bipartite graphs are widely used to model interactions between two distinct types of entities, such as author–paper networks [1], user–item networks [2], and gene co-expression networks [3]. Cohesive subgraph discovery is a fundamental problem in graph analytics, aiming to identify densely connected subgraphs with strong internal connectivity. It has been widely used in applications such as community detection [4]– [6], social recommendation [7], [8], and anomaly detection [5], [9], [10]. Among various cohesive models tailored for bipartite graphs, the (α, β)-core has been widely studied [8], [11]–[15]. It is defined as a maximal subgraph in which each vertex in the upper layer has degree at least α, and each vertex in the lower layer has degree at least β. For instance, as shown in Figure 1, the (2, 3)-core is the subgraph enclosed by gray dots, which contains vertices u0 –u3 and v0 –v2 .
𝑢𝑢0
𝑣𝑣0
𝑢𝑢1
𝑣𝑣1
𝑢𝑢2
𝑣𝑣2
2,3 − 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐
𝑢𝑢3
𝑢𝑢4
𝑣𝑣3
𝑢𝑢5
𝑣𝑣4
𝑢𝑢6
𝑣𝑣5
2,1 − 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐
𝑢𝑢7
𝑣𝑣6
Fig. 1. A bipartite graph G.
In many real-world scenarios, efficient computation of (α, β)-cores is essential to support large-scale analysis and real-time applications [8], [12], [16]. The peeling-based method [13] computes an (α, β)-core by iteratively removing vertices that violate the degree constraints, but each query is processed from scratch and can be costly on large bipartite graphs. Existing solutions [8], [11] therefore adopt indexbased approaches to enhance the efficiency of (α, β)-core computation and query processing. However, these approaches incur substantial computational and memory overhead for constructing index structures across all (α, β) combinations, posing significant scalability challenges on large-scale bipartite graphs. For instance, on our evaluated PM dataset with 4 × 108 edges, existing index-based solutions [11], [17] consume over 250 GB of memory during index construction with 32 threads, making them impractical for billion-scale graph analytics. Moreover, bipartite graphs in the wild evolve edge by edge, as observed in online social networks, web graphs, and userproduct networks [11], [16], [17]. Consider a user-product platform: when an order request creates a new edge e = (u, v) between user u and product v, the system needs to decide immediately whether to approve or block the payment. A proven way to detect coordinated fraud is to check whether the user, and hence the new edge, is involved in a suspiciously dense subgraph, such as an (α, β)-core, before the transaction is finalized [18]. We formalize this need with an on-the-fly (α, β)-core query: given a newly arrived edge update e = (u, v) in a bipartite graph G, determine immediately after the edge insertion or deletion whether e belongs to an (α, β)-core of the updated graph. Although some works [11], [17] have introduced index-based algorithms to support dynamic edge updates, their maintenance procedures can still degenerate to
the same complexity as rebuilding the index from scratch in the worst case. Such high computational overhead makes it difficult to ensure real-time responsiveness in evolving graphs with frequent updates, rendering index-based solutions impractical for latency-sensitive applications. Modern Graphics Processing Units (GPUs), explicitly architected for massive parallelism, have been widely adopted to accelerate graph applications such as butterfly counting [19], bitruss decomposition [20] and core decomposition [21]. Unlike traditional CPUs, GPUs comprise thousands of cores that execute instructions concurrently, providing substantial throughput for highly parallel graph workloads [20]. However, adapting index-based (α, β)-core approaches to GPUs is infeasible due to limited GPU memory resources [19], [21], [22]. In this paper, we aim to develop efficient GPU-based algorithms for (α, β)-core computation and query processing, while facing the following challenges. 1) Memory overhead. Fast (α, β)-core query processing often relies on index structures, which can consume substantial memory and exceed GPU capacity on large bipartite graphs. 2) Workload imbalance. Without large indexes, (α, β)-core computation relies on iterative peeling with frequent neighbor updates. Skewed degrees in real-world bipartite graphs lead to irregular memory access and imbalanced GPU workloads. 3) Large affected scope for on-the-fly queries. For edge updates, maintaining indexes can be costly, while online peeling may involve a large affected scope for each update, making low-latency on-the-fly query processing difficult on GPUs. Our solutions. To address the memory and workload challenges in (α, β)-core computation, we first propose a GPUfriendly two-phase (α, β)-Core Computation algorithm (GCC), which follows the peeling paradigm [13] without constructing large global indexes. In the scan phase, GCC uses a flat ID-based filtering strategy to check all vertices in parallel, avoiding separate processing of the two bipartite layers. In the peel phase, it adopts a warp-centric execution strategy, where each warp collaboratively processes a vertex and its neighbors, reducing thread divergence and improving memory access efficiency. To further reduce redundant computation, we develop GCC+, which performs lightweight preprocessing to compute vertex core numbers and uses them to prune vertices whose membership can be safely determined before peeling. To address the large affected scope in on-the-fly queries, we propose a GPU-based on-the-Fly (α, β)-core Query algorithm (GFQ). Instead of maintaining expensive global indexes or recomputing over the entire graph, GFQ uses connected component information to localize the computation after an edge update. It then performs GPU-based peeling only within the affected component, thereby reducing both update processing cost and query latency. Contributions. Our principal contributions are as follows. • We are the first to study (α, β)-core computation and onthe-fly (α, β)-core query processing on GPUs. • We propose GCC, a GPU-based peeling algorithm for (α, β)core computation. It combines flat ID-based parallel scanning
with warp-centric peeling to improve GPU utilization under skewed bipartite graph structures. • We develop GCC+, an optimized version of GCC that uses lightweight core-number-based pruning to reduce redundant peeling operations. • We propose GFQ, a GPU-based on-the-fly query algorithm that localizes computation to affected connected components after edge updates, avoiding full-graph recomputation. • We conduct extensive experiments on 11 bipartite graphs to evaluate GCC, GCC+, and GFQ. Compared with online methods that perform no preprocessing, GCC+ achieves at least one order of magnitude speedup in query time. Compared with leading index-maintenance approaches, GFQ achieves up to 175× speedup for on-the-fly queries. Roadmap. The rest of this paper is organized as follows. Section II reviews related work. Section III introduces preliminaries. Sections IV and V present the GPU-based (α, β)-core computation and on-the-fly query algorithms, respectively. Section VI reports the experimental results, and Section VII concludes the paper. II. R ELATED W ORK To the best of our knowledge, this paper is the first to study (α, β)-core computation and on-the-fly query processing by leveraging GPU architectures. Therefore, we review two closely related topics: CPU-based cohesive subgraph computation on bipartite graphs and GPU-accelerated cohesive subgraph computation. CPU-based cohesive subgraph computation on bipartite graphs. A variety of cohesive subgraph models have been proposed for bipartite graphs, including the (α, β)-core model [12]–[15], [17], [23]–[25], the k-bitruss model [23], [26], [27], and biclique-based models [28]–[32]. For the (α, β)-core model, the peeling-based method [13] iteratively removes vertices that violate the degree constraints. The indexbased method [17] further exploits the nested property of (α, β)-cores to support fast query answering. Subsequent studies extend the (α, β)-core model to different settings, such as weighted bipartite graphs [23], hierarchical structure discovery [12], and uncertain bipartite graphs [25]. Beyond (α, β)-cores, the k-bitruss model captures edge cohesion based on butterflies, where each edge is contained in at least k butterflies. Existing CPU-based algorithms study online peeling, index-based computation, and distributed processing for bitruss decomposition [23], [26], [27]. Biclique-based models have also been extensively studied, including maximal biclique enumeration [28], [29], [31] and maximum balanced biclique search [32]. These studies provide important cohesive models and CPU-based computation techniques for bipartite graphs. In contrast, our work focuses on GPU-based, index-free (α, β)core computation and on-the-fly query processing for largescale bipartite graphs. GPU-accelerated cohesive subgraph computation. GPUs have been widely used to accelerate cohesive subgraph computation due to their massive parallelism and high memory bandwidth. On unipartite graphs, existing studies accelerate k-core
2
Example 1. Figure 1 shows a bipartite graph G, where n = 15 and m = 20. The subgraph enclosed by the blue dots forms the (2, 1)-core, which contains all vertices in the bipartite graph. The (2, 3)-core is the subgraph enclosed by gray dots, which contains {u0 , u1 , u2 , u3 , v0 , v1 , v2 }. Consider the insertion of a new edge e = (u4 , v2 ), shown as the red dashed line in Figure 1. An on-the-fly query can be performed to determine whether this edge belongs to the updated (1, 5)core. After the insertion, vertex v2 reaches degree 5, satisfying the constraint β = 5, and u4 trivially satisfies α = 1. Therefore, the edge e belongs to the (1, 5)-core.
decomposition using peeling-based methods, vector primitives, and warp-centric strategies [21], [33], [34]. However, the kcore decomposition approaches cannot be directly applied to (α, β)-core computation, because (α, β)-cores involve two vertex layers with asymmetric degree constraints and highly skewed degree distributions. For k-truss decomposition, GPUbased methods have been developed to accelerate trianglebased support computation and peeling [35]–[38]. For clique enumeration, GPU acceleration has been explored through parallel search and memory-access optimizations [39]. On bipartite graphs, GPU-based studies mainly focus on butterfly-related primitives and biclique enumeration. For example, GPU-based butterfly counting accelerates the enumeration of (2, 2)-bicliques by improving load balancing and memory access efficiency [19]. Recent work on GPU-based bitruss decomposition leverages GPU parallelism to accelerate butterfly-support computation and peeling in bipartite graphs [20]. GPU-based maximal biclique enumeration further addresses the large memory requirement, thread divergence, and workload imbalance of enumerating maximal bicliques on GPUs [40]. Although these GPU-based methods demonstrate the effectiveness of GPU acceleration for cohesive subgraph computation, none of them studies GPU-based (α, β)-core computation or on-the-fly (α, β)-core query processing. These tasks require handling asymmetric degree constraints and avoiding large index structures under limited GPU memory.
A. CPU-based (α, β)-core Computation Since no prior work has studied (α, β)-core computation on GPUs, we first review CPU-based solutions, including the peeling-based method [13] and index-based methods [8], [11], which form the main baselines in our experiments. The peeling-based method [13], denoted by Online, computes an (α, β)-core directly from the input graph without preprocessing. Given a bipartite graph G and degree constraints α and β, Online iteratively removes all upper-layer vertices whose degrees are smaller than α and all lower-layer vertices whose degrees are smaller than β, together with their incident edges. This process continues until every remaining vertex satisfies the corresponding degree constraint, and the remaining vertices form the (α, β)-core. Although Online requires no preprocessing and no extra index storage, each query must perform the peeling process from scratch, which can be expensive on large bipartite graphs. To further improve the efficiency of (α, β)-core computation, BiCore [8] introduces nested computing and builds a three-level index that organizes vertices according to their valid (α, β) ranges, thereby supporting fast arbitrary (α, β)core queries. [17] further studies update algorithms for maintaining this index under dynamic graph changes. Another index-based method, BIR [11], introduces bi-core numbers to summarize the range of (α, β)-cores that each vertex belongs to and provides corresponding maintenance algorithms for edge insertions and deletions. Although these index-based methods can support efficient (α, β)-core computation and querying, they incur significant memory overhead and computational costs. Specifically, they require at least O(m) space and O(δ · m) time, where δ is the maximum value such that the (δ, δ)-core is non-empty. In dynamic settings, index maintenance algorithms can be as expensive as rebuilding the entire index in the worst case, further limiting their scalability [11], [17]. In addition, despite the improved update efficiency of BIR, it still struggles to provide low-latency support for arbitrary queries under frequent updates, since query processing may still require scanning all vertices.
III. P RELIMINARIES Our problem is defined over an undirected and unweighted bipartite graph G = (V (G), E(G)), where the vertex set is defined as V (G) = U (G) ∪ L(G), with U (G) and L(G) denoting the disjoint sets of upper- and lower-layer vertices, respectively. The edge set is denoted as E(G) ⊆ U (G)×L(G). For a vertex u ∈ V (G), its neighbor set is defined as N (u) = {v ∈ V (G) | (u, v) ∈ E(G)}, and its degree is deg(u, G) = |N (u)|. We use n and m to denote the numbers of vertices and edges in G, respectively. To facilitate efficient graph processing, we store the graph in the Compressed Sparse Row (CSR) format [41], a compact and memory-efficient representation that is suited for modern memory hierarchies. Definition 1. (α, β)-core. Given a bipartite graph G and two parameters α and β, a subgraph G ⊆ G is the (α, β)core if (1) deg(u, G) ≥ α for every vertex u ∈ U (G), and deg(v, G) ≥ β for every vertex v ∈ L(G); (2) G is maximal, ′ i.e., no supergraph G ⊃ G qualifies as an (α, β)-core. In this paper, we study the following two problems regarding the (α, β)-core model. Problem Statement ((α, β)-core Computation). Given a bipartite graph G, degree constraints α and β, we aim to retrieve the vertex set of the (α, β)-core in G. Problem Statement (On-the-fly (α, β)-core query). Given a bipartite graph G, degree constraints α and β, and an edge update e = (u, v) (insertion or deletion), we aim to determine whether e belongs to the (α, β)-core of the updated graph.
IV. GPU- BASED (α, β)- CORE C OMPUTATION WITH N ESTED -AWARE P RUNING While index-based approaches such as BiCore [8] and BIR [11] can efficiently support arbitrary (α, β)-core queries, they incur substantial memory overhead, limiting their direct
3
applicability on GPUs. For instance, the index construction processes of both BiCore and BIR consume over 250 GB of memory when using 32 threads, which far exceeds the 80 GB memory capacity of modern A100 GPUs. In contrast, the online peeling-based approach [13] naturally avoids index construction. However, during iterative degree updates, multithreaded CPU implementations of Online require frequent synchronization to ensure consistency, leading to substantial coordination overhead. Moreover, Online alternates layerwise scans over the two partitions to identify removable vertices, which further limits parallelism. To support efficient (α, β)-core computation on GPUs, we propose a GPU-friendly two-phase (α, β)-Core Computation algorithm (GCC), which follows the peeling paradigm. In each iteration, GCC processes vertices in parallel and updates the degrees of their neighbors when vertices are removed. To handle workload imbalance caused by skewed vertex degrees, GCC adopts a warp-centric execution strategy, where each GPU warp collaboratively processes a vertex and its neighborhood. This design improves parallel throughput without relying on costly global index structures. To further improve overall efficiency, we develop an optimized algorithm, GCC+, which integrates lightweight preprocessing based on vertex core numbers for early pruning.
Algorithm 1: GCC Input: G = (U, L, E), degree thresholds α, β Output: Vertex set of the (α, β)-core of G 1 G ← G; C←∅ 2 foreach v ∈ V (G) in parallel do 3 if v ∈ U (G) ∧ deg(v, G) < α then 4 enqueue v into C else if v ∈ L(G) ∧ deg(v, G) < β then enqueue v into C
5 6
while C ̸= ∅ do foreach warp ∈ launched warps in parallel do 9 u ← C(warpid ) 10 foreach v ∈ N (u) in parallel do 11 atomic decrement deg(v, G) 12 if (v ∈ U (G) ∧ deg(v, G) < α) or (v ∈ L(G) ∧ deg(v, G) < β) then 13 enqueue v into warp-local queue 7
8
flush warp-local queue to C
14
block synchronize
15 16
return V (G) 𝑢𝑢0
𝑢𝑢1
𝑣𝑣0
A. The GCC algorithm We now introduce the GCC algorithm in detail. Unlike the CPU-based peeling approach [13], which alternates between scanning upper and lower layers to identify vertices that violate the degree constraints, GCC scans the entire graph in a unified manner to enable efficient parallel execution. Specifically, each vertex u ∈ V (G) is assigned a unique continuous ID, enabling GPU threads to determine whether a vertex belongs to the upper or lower layer via simple range-based checks. CPUbased peeling typically uses conditional checks to determine layers, which can cause branch mispredictions and hurt cache performance [8], [16], [20]. In contrast, our GPU method assigns IDs to reduce these branches and improve efficiency. The input graph G is stored in the Compressed Sparse Row (CSR) format [41], which supports efficient neighbor access during peeling. Algorithm 1 presents the detailed procedure of the scan and peel phases. In the scan phase (Lines 2–6), all vertices are processed in parallel to check whether they violate their corresponding (α, β) constraints. Vertices that violate the constraints are inserted into the global candidate set C for subsequent peeling. To ensure concurrency safety, we employ atomic operations when updating C, thereby reducing race conditions while maintaining high throughput. In the peeling phase (Lines 7–15), GCC processes the candidate set using a warp-centric strategy. Each warp is assigned a vertex u ∈ C and collaboratively traverses its neighbors N (u). This design aligns with the CSR layout, improving memory coalescing and reducing thread divergence. For each neighbor v ∈ N (u), the warp performs an atomic decrement on deg(v, G) to reflect the removal of u (Line 11). If the
𝑣𝑣1
𝑢𝑢2
𝑣𝑣2
𝑢𝑢3
𝑢𝑢5
𝑢𝑢4
𝑣𝑣3
𝑣𝑣4
Round 1
𝑢𝑢6
𝑣𝑣5
𝑢𝑢7
𝑢𝑢0
𝑣𝑣6
𝑣𝑣0
𝑢𝑢1
𝑣𝑣1
𝑢𝑢2
𝑣𝑣2
𝑢𝑢3
𝑢𝑢5
𝑢𝑢4
𝑣𝑣3
𝑣𝑣4
Round 2
𝑢𝑢7
𝑢𝑢6
𝑣𝑣5
𝑣𝑣6
Fig. 2. Illustrating the (1, 3)-core computation using GCC.
updated degree of v falls below its corresponding threshold, i.e., α for upper-layer vertices or β for lower-layer vertices, v is identified as a new candidate and inserted into a warplocal queue (Lines 12-13). To reduce contention on the global candidate set, newly invalidated vertices are first buffered in warp-local queues and then flushed to C (Line 14). Block-level synchronization is enforced between iterations to ensure that all degree updates are visible before the next round. The algorithm terminates when C becomes empty and returns the remaining vertex set as the final (α, β)-core. Since GCC avoids global index construction and processes each edge a constant number of times, its space and time complexity are bounded by O(m). Example 2. Figure 2 illustrates the (1, 3)-core computation process using GCC. In the first round, vertices v3 , v5 , and v6 violate the degree threshold β = 3 and are added to the candidate set for removal, as highlighted by red dashed circles. After removing these vertices, GCC updates the degrees of their neighbors. In the second round, no further vertices violate the constraints, and the process terminates. The final (1, 3)-core consists of u0 , u1 , u2 , u3 , u4 , u5 , u6 , u7 , v0 , v1 , v2 , v4 . B. The GCC+ algorithm Although the GPU-based peeling algorithm GCC substantially accelerates (α, β)-core computation, it may still perform redundant work for queries where α and β are close. In this case, many vertices can be clearly determined before peeling,
4
but GCC still performs full-scale neighbor updates over them. To reduce such unnecessary processing, we introduce an early pruning mechanism that reduces the number of active vertices involved in peeling. Inspired by the classic k-core definition [42], we use vertex core numbers to derive safe pruning conditions for (α, β)core computation. Intuitively, the core number of a vertex indicates the largest symmetric (δ, δ)-core containing that vertex. Thus, it can provide useful bounds for an asymmetric (α, β) query. Vertices with insufficient core numbers can be safely excluded before peeling, while vertices with sufficiently large core numbers can be directly retained. This lightweight preprocessing step can be efficiently parallelized on GPUs and helps reduce the search space, memory traffic, and redundant degree updates. To utilize this strategy, we first define the notion of core numbers in bipartite graphs.
Algorithm 2: GCC+ Input: G, α, β, precomputed core number core(u) for each vertex u ∈ V (G) Output: Vertices in the (α, β)-core of G 1 δl ← min(α, β); δq ← max(α, β) 2 G ← G; C←∅ 3 foreach v ∈ V (G) in parallel do 4 if δl ≤ core(v) < δq then 5 if v ∈ U (G) ∧ deg(v, G) < α then 6 enqueue v into C 7 8
else if v ∈ L(G) ∧ deg(v, G) < β then enqueue v into C
while C ̸= ∅ do foreach warp ∈ launched warps in parallel do 11 u ← C(warpid ) 12 foreach v ∈ N (u) in parallel do 13 if δl ≤ core(v) < δq then 14 atomic decrement deg(v, G) 15 if (v ∈ U (G) and deg(v, G) < α) or (v ∈ L(G) and deg(v, G) < β) then 16 enqueue v into warp-local queue 9
10
Definition 2. Core Number [42], [43]. Given a bipartite graph G, the core number of a vertex u ∈ V (G) is the largest integer δ such that u belongs to the (δ, δ)-core of G. Formally,
core(u) = max {δ ∈ N | u ∈ G, where G is a (δ, δ)-core of G} 17 18
According to the definition of the core number in bipartite graphs (i.e., Definition 2), we can derive a crucial pruning principle that enables early elimination or retention of vertices before the peeling process. This observation leads to the following lemma:
19
flush warp-local queue to C block synchronize return V (G)
Unlike the baseline GCC, which indiscriminately inspects all neighbors during peeling, GCC+ leverages precomputed core numbers (Definition 2) to filter vertices statically. The algorithm begins by deriving two pruning thresholds: δl = min(α, β) and δq = max(α, β) (Line 1). According to Lemma 1, vertices with core(u) < δl are inherently excluded, while those with core(u) ≥ δq satisfy the degree constraints trivially and require no dynamic verification. Consequently, the computation focuses solely on the ”uncertain” vertices within the range [δl , δq ). In the scan phase (Lines 3–8), the algorithm populates the initial candidate set C. A thread is assigned to each vertex v to check two conditions: (1) whether core(v) falls within the pruning range [δl , δq ), and (2) whether it violates the degree constraints. Only vertices satisfying both conditions are enqueued into C, effectively filtering out irrelevant updates before the peeling begins. The peeling phase (Lines 9–18) employs a warp-centric strategy to mitigate thread divergence and memory contention. Each warp processes a vertex u ∈ C and its neighbors N (u) in parallel. A critical optimization occurs at Line 13: before performing an atomic decrement on a neighbor v, the warp verifies if core(v) ∈ [δl , δq ). This ensures that updates are only propagated to vertices whose status is not yet determined, thereby avoiding redundant atomic operations on vertices that are guaranteed to remain in the core. If a neighbor v violates the (α, β) constraints after the update, it is buffered in a warp-local queue and subsequently flushed to the global set C. Global consistency is maintained via blocklevel synchronization (Line 18). The process terminates when
Lemma 1. Given a bipartite graph G, let core(u) denote the core number of vertex u ∈ V (G). When computing the (α, β)core, the following pruning conditions hold: (1) If core(u) < min(α, β), then u ∈ / G, where G is the (α, β)-core of G. (2) If core(u) ≥ max(α, β), then u is guaranteed to be included in G. Proof. Let δl = min(α, β) and δq = max(α, β). (1) If core(u) < δl , then by Definition 2, vertex u does not belong to any (δl , δl )-core. Since any (α, β)-core must satisfy degree thresholds at least δl on both layers, u cannot belong to the (α, β)-core. Thus, Lemma 1(1) holds. (2) If core(u) ≥ δq , then u belongs to the (δq , δq )-core. Since δq ≥ α and δq ≥ β, this (δq , δq )-core also satisfies the (α, β) degree constraints. By the maximality of the (α, β)core, u must be included in G. Thus, Lemma 1(2) holds. Based on Lemma 1, we can significantly reduce the workload of GPU-based online (α, β)-core computation (i.e., GCC) by preemptively pruning vertices that are guaranteed to be either excluded from or included in the result. This enhancement leads to an optimized algorithm design with lower runtime overhead on large bipartite graphs. We next introduce an enhanced GPU-based algorithm, GCC+, that incorporates the core-number-based pruning strategy into the GCC framework. Algorithm 2 outlines GCC+, an optimized GPU-based (α, β)-core computation algorithm that integrates corenumber-based pruning to significantly reduce the search space.
5
𝑣𝑣0
𝑢𝑢3
𝑢𝑢2
𝑢𝑢1
𝑣𝑣1
𝑣𝑣2
𝑢𝑢4
𝑣𝑣3
𝑢𝑢0
𝑢𝑢6
𝑢𝑢5
𝑣𝑣4
𝑣𝑣5
𝑢𝑢7
𝑢𝑢3
𝑢𝑢2
𝑢𝑢1
𝑢𝑢5
𝑢𝑢4
𝑢𝑢7
𝑢𝑢6
𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 𝑢𝑢 = 3
𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 𝑢𝑢 = 2
𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 𝑢𝑢 = 2 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 𝑢𝑢 = 1
𝑣𝑣𝑣𝑣0
6
𝑣𝑣4
𝑣𝑣5
𝑣𝑣6
𝑢𝑢6
𝑢𝑢7
𝑢𝑢0
𝑢𝑢1
Round 1
𝑣𝑣5
𝑣𝑣6
𝑢𝑢5
𝑢𝑢6
𝑢𝑢7
𝑣𝑣5
𝑣𝑣6
𝑣𝑣1
𝑣𝑣2
𝑢𝑢3
𝑢𝑢4
In such cases, fast on-the-fly structural queries are essential for timely fraud detection. To address this challenge, we propose GFQ, a GPU-based on-the-Fly (α, β)-core Query algorithm that leverages graph connectivity to reduce the computation scope. The key observation is that the impact of an edge update is restricted to the connected component region affected by that update. By maintaining component information, GFQ avoids applying peeling to the entire graph and focuses only on the subgraph that may influence the query result. Preprocessing. Instead of maintaining expensive global indexes, GFQ uses a lightweight GPU-parallel union-find procedure to assign a component identifier to each vertex. These component identifiers allow GFQ to quickly locate the affected component when an edge update arrives. Query procedure. Given an edge update e = (u, v), GFQ first updates the component information. If e is an insertion between two different components, the two components are merged. If e is a deletion, GFQ re-invokes the parallel connectivity procedure on the affected component to handle possible component splits. Then, GFQ extracts the induced subgraph G associated with the affected component and executes the peeling process, i.e., Algorithm 1, only on G. This avoids redundant computation on unrelated parts of the graph. Finally, GFQ returns whether the updated edge or its endpoints remain in the target (α, β)-core of the affected subgraph, depending on the update type. Remark. The algorithm GFQ is not limited to verifying the membership of an updated edge e = (u, v). It can also be adapted to retrieve the vertex set of the (α, β)-core containing the updated endpoints by returning the remaining vertices after peeling the affected component. Moreover, in the static setting, GFQ can support localized community search by returning the (α, β)-core that contains a query vertex or edge, without requiring a global index or full-graph traversal. Complexity analysis of GFQ. Let G be partitioned into x disjoint connected components C1 , C2 , . . . , Cx , where each component Ci = (Ui , Li , Ei ) contains a subset of vertices and edges. After the affected component Ci is identified, the query cost of GFQ is bounded by O(|Ei |), since peeling is performed only within Ci . In the worst case, if the graph contains a single connected component, the complexity becomes O(m). However, in practice, many updates affect only local components, and the component-aware design significantly reduces unnecessary computation.
𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 𝑢𝑢 = 3
𝑣𝑣3
𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 𝑢𝑢 = 1
(a) Core number of a bipartite graph G
𝑢𝑢0
𝑣𝑣1
𝑣𝑣0 𝑢𝑢0
𝑣𝑣0
𝑢𝑢2
𝑢𝑢1
𝑢𝑢3
𝑢𝑢2
𝑢𝑢1
𝑣𝑣1
𝑣𝑣2
𝑣𝑣4
𝑣𝑣3
𝑣𝑣2
𝑢𝑢4
𝑣𝑣3
𝑢𝑢5
𝑣𝑣4
Round 3
𝑣𝑣0 𝑢𝑢0
𝑣𝑣0
𝑣𝑣1
𝑣𝑣1
𝑢𝑢7
Round 2
𝑣𝑣5
𝑣𝑣6
𝑢𝑢5
𝑢𝑢6
𝑢𝑢7
𝑣𝑣5
𝑣𝑣6
𝑢𝑢3
𝑣𝑣2
𝑢𝑢5
𝑢𝑢4
𝑣𝑣3
𝑣𝑣2 𝑢𝑢2
𝑢𝑢1
𝑢𝑢6
𝑢𝑢3
𝑢𝑢2
𝑣𝑣4
𝑢𝑢4
𝑣𝑣3
𝑣𝑣4
Round 4
(b) Peeling process Fig. 3. Illustrating the (2, 3)-core computation using GCC+.
C becomes empty, returning the exact (α, β)-core. Example 3. Figure 3 demonstrates the (2, 3)-core computation using the GCC+ algorithm. In Figure 3(a), the preprocessing step computes the core number of each vertex, where blue, green, and gray nodes represent core numbers of 3, 2, and 1, respectively. Given the thresholds α = 2 and β = 3, we determine pruning bounds δl = 2 and δq = 3. Vertices with core number at least δq (i.e., those enclosed by the dashed boundary, such as u0 to u3 and v0 to v3 ) are guaranteed to satisfy the constraints and are excluded from the peeling. In the first round, vertices v3 , v5 , and v6 are identified as violating the degree threshold β = 3 (highlighted as red dashed circles) and are added to the candidate set for removal. Their removal causes degree updates to their neighbors. In Round 2, vertices u4 , u5 , u6 , and u7 fall below the threshold α = 2 and are peeled accordingly. The process terminates when no further violations exist, and the final (2, 3)-core includes vertices {u0 , u1 , u2 , u3 , v0 , v1 , v2 }. V. O N - THE -F LY Q UERY P ROCESSING In many real-world applications, such as user–item networks [2], social networks [15], and financial networks [11], graphs are inherently dynamic, with edges and vertices frequently inserted or deleted over time. A major challenge in such scenarios is to support real-time query processing on dynamic bipartite graphs. For example, in a user–item bipartite graph on an e-commerce platform, when a user purchases a product, the system may need to immediately determine whether this interaction is involved in suspicious behavior, such as forming a dense structure with highly unbalanced interaction patterns between the two sides of the graph [16].
VI. E XPERIMENTAL E VALUATION A. Experimental setting We compare our methods with the following designs for (α, β)-core computation and on-the-fly query processing. CPU-based algorithms. The CPU-based baselines include: 1) Online [13]: the classic peeling algorithm that iteratively removes vertices violating the (α, β) degree constraints. 2) BiCore [8], [17]: an index-based method that precomputes and stores (α, β)-core indexes for fast query answering. 3) BIR [11]: a compact index-based method that maintains
6
Graph-Size
TABLE I S UMMARY OF DATASETS . Dataset RE NY TR Dui LG Dti WT YS OG PM PL
|U (G)| 781,265 299,752 551,787 833,081 3,201,203 4,511,972 27,665,730 1,000,990 2,783,196 8,200,000 220,576
|L(G)| 283,911 101,636 1,173,225 33,778,221 7,489,073 33,777,768 12,756,244 624,961 8,730,857 141,043 5,000,000
|E(G)| 60,569,726 69,679,427 83,629,405 101,798,957 112,307,385 137,240,382 140,613,762 256,804,235 327,037,487 483,450,157 1,000,000,000
δ 191 314 509 184 109 180 438 1,100 467 108 215
BiCore
BIR
PAR
Online
GCC
GCC+
Fig. 4. Memory usage evaluation on all datasets.
B. (α, β)-core Computation Performance Preprocessing cost and query efficiency. Table II reports the preprocessing cost and query time of all evaluated methods across all datasets. For fair comparison, BiCore, PAR, and BIR build their indexes using 32 CPU threads. As shown in Table II, GCC+ incurs much lower preprocessing cost than the index-based methods BiCore, PAR, and BIR on all datasets. For example, on the largest dataset PL, GCC+ takes only 1.00 second for preprocessing, while BiCore, PAR, and BIR require 1525.37, 158.55, and 662.90 seconds, respectively. On Dti and YS, GCC+ takes only 0.32 and 0.86 seconds, respectively, whereas BiCore requires 566.51 and 500.80 seconds, and BIR requires 130.95 and 347.84 seconds. Moreover, PAR runs out of memory on YS and PM, requiring more than 512 GB memory during preprocessing. This is because GCC+ performs only lightweight preprocessing by computing the core number of each vertex u ∈ V (G), instead of maintaining global index structures. Table II also reports the query time under the default setting, where α = 0.4×δ and β = 0.6×αoffset , and αoffset denotes the largest β value such that the (α, β)-core is non-empty. Both GCC and GCC+ achieve millisecond-level query latency with little preprocessing overhead. Compared with Online, GCC+ achieves a 34×–94× speedup, while GCC achieves a 18×–65× speedup. For example, on YS, Online takes 1.3236 seconds, whereas GCC and GCC+ take only 0.0284 and 0.0141 seconds, respectively. The core-number-based pruning of GCC+ further improves over GCC; on WT, GCC+ reduces the query time from 0.0946 seconds to 0.0347 seconds. Compared with CPU-based methods, GCC+ consistently outperforms BIR and Online in query time, and also outperforms BiCore and PAR on several large datasets. For example, on the largest dataset PL, GCC+ answers a query in 0.0003 seconds, achieving 68× and 2787× speedups over BiCore and BIR, respectively. Although BiCore and PAR can answer some queries faster on several datasets, they require substantial preprocessing cost. Overall, GCC+ provides a favorable trade-off by avoiding expensive index construction while still supporting low-latency (α, β)-core computation. Memory usage during preprocessing. Figure 4 reports the peak runtime memory consumption during preprocessing. For BiCore, PAR, and BIR, the reported memory usage corresponds to the peak memory observed during 32-thread index construction. Although PAR reduces the memory consump-
bicore numbers for efficient arbitrary (α, β)-core queries. 4) PAR [44]: a parallel index-based method that adopts the same three-level index structure as BiCore. Both BiCore and BIR provide maintenance methods for dynamic bipartite graphs, whereas PAR focuses on parallel index construction and does not propose a maintenance algorithm. However, BIR runs out of memory on all datasets when processing our dynamic workloads. Therefore, in the on-the-fly query evaluation, we report only BiCore as the representative index-maintenance baseline for comparison with our proposed GFQ algorithm. GPU-based algorithms. We evaluate the following GPUbased algorithms: 5) GCC: our GPU-based parallel peeling algorithm for (α, β)-core computation, as described in Algorithm 1. 6) GCC+: an optimized version of GCC that incorporates core-number-based pruning to reduce redundant computation, as described in Algorithm 2. 7) GFQ: our GPUbased on-the-fly query algorithm that restricts computation to the connected component containing the updated edge. Datasets. We evaluate all algorithms on 11 bipartite graphs, including 10 real-world datasets from KONECT (http://konect. cc/) and one synthetic dataset. The synthetic dataset PL follows a power-law distribution, which is widely used to mimic structural properties of real-world networks [8], [11]. Table I summarizes the dataset statistics, where |U (G)| and |L(G)| denote the numbers of vertices in the upper and lower layers, respectively, and |E(G)| denotes the number of edges. The parameter δ is the largest value such that the (δ, δ)-core of G is non-empty. Experimental environment. All GPU-based algorithms are implemented in CUDA, while all CPU-based algorithms are implemented in C++. By default, GPU-based algorithms are evaluated on a Linux server equipped with an NVIDIA RTX 3090 Ti GPU with 24 GB of global memory. For comparison, CPU-based algorithms are executed on a Linux server with an Intel Xeon Silver 4314 processor and 512 GB of main memory. An algorithm is terminated if its execution time exceeds 10 hours, and dynamic update algorithms are terminated if their running time exceeds 3600 seconds. The abbreviation OOM denotes out-of-memory errors.
7
TABLE II Q UERY EFFICIENCY EVALUATION : PREPROCESSING TIME AND QUERY TIME ( IN SECONDS ).
Preprocessing Time (sec)
Dataset RE NY TR Dui LG Dti WT YS OG PM PL
Query Time (sec)
BiCore
BIR
PAR
Online
GCC
GCC+
BiCore
BIR
PAR
Online
GCC
GCC+
53.84 61.33 101.77 422.26 186.17 566.51 667.48 500.80 621.56 488.88 1525.37
21.05 28.39 54.16 90.64 41.89 130.95 240.45 347.84 313.56 175.87 662.90
11.27 12.95 24.68 110.13 41.17 121.59 214.28 OOM 197.84 OOM 158.55
0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
0.19 0.14 0.28 0.11 0.09 0.32 1.03 0.86 0.53 0.38 1.00
0.0010 0.0012 0.0005 0.0003 0.0015 0.0001 0.0001 0.0006 0.0010 0.0206 0.0204
0.0233 0.0108 0.0176 0.0918 0.0764 0.0881 0.0914 0.0194 0.0605 0.1306 0.8360
0.0015 0.0020 0.0004 0.0005 0.0021 0.0002 0.0001 OOM 0.0015 OOM 0.0219
0.2865 0.1241 0.3449 1.6082 1.4509 2.1534 1.6731 1.3236 2.8658 3.3818 0.0229
0.0100 0.0040 0.0072 0.0467 0.0334 0.0678 0.0946 0.0284 0.0538 0.0520 0.0006
0.0077 0.0029 0.0053 0.0280 0.0222 0.0344 0.0347 0.0141 0.0387 0.0481 0.0003
PAR
Online
GCC
BiCore
BIR
GCC+
BiCore-Ins Time Cost (sec)
103 102 101 100
Time Cost (sec)
Time Cost (sec)
101 101 101 102 100 100 100 101 10 1 10 1 10 1 0 10 10 2 10 2 10 2 10 3 10 3 10 1 10 3 4 2 10 4 10 10 4 10 10 5 0.1 0.3 0.5 0.7 100.93 10 5 0.1 0.3 0.5 0.7 0.9 10 5 0.1 0.3 0.5 0.7 0.9 c c c 10 4 10 5 0.1 (a) OG (b) PM (c) PL 0.3 0.5 0.7 0.9 c
Fig. 5. Performance on retrieving (α, β)-cores varying α.
BiCore
BIR
PAR
Online
GCC
GCC+
BiCore-Del
GFQ-Del
RE NY TR Dui LG Dti WT YS OG PM PL Datasets Fig. 7. Performance on on-the-fly query processing.
101 101 101 102 100 100 100 1 10 1 1 10 10 10 1 100 10 2 10 2 10 2 10 3 10 3 10 1 10 3 10 4 10 4 10 2 10 4 10 5 0.1 0.3 0.5 0.7 100.93 10 5 0.1 0.3 0.5 0.7 0.9 10 5 0.1 0.3 0.5 0.7 0.9 c c c 10 4 5 10 (a) OG (c) PL 0.1 0.3 (b)0.5PM 0.7 0.9 c
datasets, GCC+ outperforms the index-based methods BiCore and PAR under several parameter settings. Since PAR adopts the same index structure as BiCore, their query performance is close across different parameter settings. For example, on the largest dataset PL, when α = 0.5 × δ and β = 0.3 × δ, GCC+ achieves 26× and 198× speedups over BiCore and BIR, respectively, as shown in Figure 6(c). Notably, when α = β = 0.5 × δ, GCC+ achieves the best performance among all methods because it only requires a simple parallel scan. These results show that the lightweight preprocessing strategy enables GCC+ to efficiently handle large-scale bipartite graphs across different (α, β) settings.
Time Cost (sec)
Time Cost (sec)
GFQ-Ins
Fig. 6. Performance on retrieving (α, β)-cores varying β.
tion of parallel index construction compared with BiCore, all index-based methods still require substantial intermediate memory. In particular, the final indexes of BiCore and BIR are linear in the number of edges, i.e., O(m), but their construction processes consume much higher peak memory. As shown in Figure 4, the CPU-based index methods BiCore, PAR, and BIR incur much higher memory overhead than our GPU-based GCC+. For example, on the largest dataset PL, GCC+ peaks at only 11.7 GB, whereas BiCore and BIR each require over 500 GB, and PAR consumes more than 120 GB. In addition, since BIR follows the same index construction mechanism as BiCore, their memory profiles are nearly identical. This substantial gap in memory consumption renders index-based methods impractical for large-scale bipartite graphs. In contrast, GCC+ keeps its peak memory usage below 15 GB on all datasets, making it suitable for deployment on memory-limited GPUs. This is because GCC+ avoids constructing global index structures and only maintains lightweight auxiliary information for online computation. Query sensitivity to α and β. We further evaluate the query performance under different parameter settings by fixing one parameter and varying the other. In Figure 5, we fix β = 0.5 × δ and vary α = c × δ, where c ranges from 0.1 to 0.9. In Figure 6, we fix α = 0.5 × δ and vary β = c × δ. On large
C. On-the-fly (α, β)-core Query Performance Query efficiency. To evaluate the efficiency of on-the-fly queries under dynamic updates, we randomly select 1,000 edges for insertion and deletion on each dataset. For each updated edge e = (u, v), the values of α and β are randomly chosen such that both u and v belong to the corresponding (α, β)-core. We set a timeout threshold of 3,600 seconds for the total running time of 1,000 edge insertions or deletions. As shown in Figure 7, GFQ consistently achieves fast response times for both edge insertions and deletions across all datasets. In contrast, BiCore fails to complete edge insertion within the time limit on most datasets. For insertion queries, BiCore only finishes on Dti and Dui, requiring 25.6 and 994.1 seconds, respectively, while timing out on all other datasets. By contrast, GFQ completes all insertion queries, with running times ranging from 4.94 seconds on NY to 227.9 seconds on WT. For deletion queries, GFQ also consistently achieves lower latency than BiCore. For example, on WT,
8
BiCore Time Cost (sec)
105 104 103 102 101 100200 400 600 800 1000 Edge Updates
GFQ
105 104 103 102 101 100200 400 600 800 1000 Edge Updates
(a) WT (insertion)
(b) YS (insertion)
(c) LG (insertion)
104 103 102 101 100200 400 600 800 1000 Edge Updates
104 103 102 101 100200 400 600 800 1000 Edge Updates
104 103 102 101 100200 400 600 800 1000 Edge Updates
(d) WT (deletion)
(e) YS (deletion)
(f) LG (deletion)
Time Cost (sec)
violate the degree constraints. For dynamic scenarios, we design GFQ, a connectivity-aware on-the-fly query algorithm that confines updates and computation to local components. Extensive experiments on 11 datasets demonstrate that our algorithms significantly outperform existing solutions.
105 104 103 102 101 100200 400 600 800 1000 Edge Updates
R EFERENCES [1] M. Ley, “The DBLP computer science bibliography: Evolution, research issues, perspectives,” in String Processing and Information Retrieval, 9th International Symposium, SPIRE 2002, Lisbon, Portugal, September 11-13, 2002, Proceedings, ser. Lecture Notes in Computer Science, A. H. F. Laender and A. L. Oliveira, Eds., vol. 2476. Springer, 2002, pp. 1–10. [2] A. Beutel, W. Xu, V. Guruswami, C. Palow, and C. Faloutsos, “Copycatch: stopping group attacks by spotting lockstep behavior in social networks,” in 22nd International World Wide Web Conference, WWW ’13, Rio de Janeiro, Brazil, May 1317, 2013, D. Schwabe, V. A. F. Almeida, H. Glaser, R. BaezaYates, and S. B. Moon, Eds. International World Wide Web Conferences Steering Committee / ACM, 2013, pp. 119–130. [3] M. Kaytoue, S. O. Kuznetsov, A. Napoli, and S. Duplessis, “Mining gene expression data with pattern structures in formal concept analysis,” Inf. Sci., vol. 181, no. 10, pp. 1989–2001, 2011. [4] B. Yang, D. Wen, L. Qin, Y. Zhang, L. Chang, and R. Li, “Index-based optimal algorithm for computing k-cores in large uncertain graphs,” in 35th IEEE International Conference on Data Engineering, ICDE 2019, Macao, China, April 8-11, 2019. IEEE, 2019, pp. 64–75. [5] L. Yuan, L. Qin, X. Lin, L. Chang, and W. Zhang, “Diversified top-k clique search,” VLDB J., vol. 25, no. 2, pp. 171–196, 2016. [6] J. Wang, K. Wang, X. Lin, W. Zhang, and Y. Zhang, “Neural attributed community search at billion scale,” Proc. ACM Manag. Data, vol. 1, no. 4, 2023. [7] W. Luo, K. Li, X. Zhou, Y. Gao, and K. Li, “Maximum biplex search over bipartite graphs,” in 38th IEEE International Conference on Data Engineering, ICDE 2022, Kuala Lumpur, Malaysia, May 9-12, 2022. IEEE, 2022, pp. 898–910. [8] B. Liu, L. Yuan, X. Lin, L. Qin, W. Zhang, and J. Zhou, “Efficient (α,β)-core computation: an index-based approach,” in The World Wide Web Conference, WWW 2019, San Francisco, CA, USA, May 13-17, 2019, L. Liu, R. W. White, A. Mantrach, F. Silvestri, J. J. McAuley, R. Baeza-Yates, and L. Zia, Eds. ACM, 2019, pp. 1130–1141. [9] K. Shin, T. Eliassi-Rad, and C. Faloutsos, “Corescope: Graph mining using k-core analysis - patterns, anomalies and algorithms,” in IEEE 16th International Conference on Data Mining, ICDM 2016, December 12-15, 2016, Barcelona, Spain, F. Bonchi, J. Domingo-Ferrer, R. Baeza-Yates, Z. Zhou, and X. Wu, Eds. IEEE Computer Society, 2016, pp. 469–478. [10] Y. He, K. Wang, W. Zhang, X. Lin, and Y. Zhang, “Scaling up k-clique densest subgraph detection,” Proceedings of the ACM on Management of Data, vol. 1, no. 1, pp. 1–26, 2023. [11] 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. [12] K. Wang, W. Zhang, X. Lin, Y. Zhang, and S. Li, “Discovering hierarchy of bipartite graphs with cohesive subgraphs,” in 38th IEEE International Conference on Data Engineering, ICDE 2022, Kuala Lumpur, Malaysia, May 9-12, 2022. IEEE, 2022, pp. 2291–2305. [13] D. Ding, H. Li, Z. Huang, and N. Mamoulis, “Efficient faulttolerant group recommendation usinalg alpha-beta-core,” in Proceedings of the 2017 ACM on Conference on Information
Fig. 8. The scalability of GFQ.
GFQ completes in 305.9 seconds, whereas BiCore takes 3,494.5 seconds. The performance gap mainly comes from the high cost of index maintenance. In the worst case, the maintenance procedure of BiCore has the same O(δ·m) complexity as rebuilding the entire index [17], which is expensive for large and frequently updated graphs. In contrast, GFQ confines the computation to the affected connected components, avoiding global recomputation and enabling efficient on-the-fly query processing under dynamic workloads. Scalability performance. Figure 8 evaluates the scalability of GFQ by varying the number of dynamic updates from 200 to 1,000 on WT, YS, and LG. For each updated edge e = (u, v), the values of α and β are randomly chosen such that both u and v belong to the corresponding (α, β)-core. As shown in Figure 8, GFQ consistently outperforms the CPU-based method BiCore for both edge insertions and deletions across all tested datasets. On WT, Figures 8(a) and 8(d) show that the running time of GFQ increases smoothly as the number of updates grows; for 1,000 insertions, GFQ takes 227.9 seconds, whereas BiCore takes 4109.37 seconds. On YS, the performance gap is even larger: for 1,000 insertions, GFQ takes only 29.35 seconds, while BiCore requires 31640.3 seconds. For deletions, GFQ keeps the running time below 30 seconds on YS across all update sizes, whereas BiCore takes close to 1,000 seconds for 1,000 deletions. The advantage of GFQ comes from its connectivity-aware design, which confines computation to affected connected components and avoids costly global index maintenance. Overall, these results demonstrate that GFQ scales efficiently with the number of dynamic updates and is suitable for on-the-fly query processing on large bipartite graphs. VII. C ONCLUSION In this paper, we propose GPU-based algorithms to efficiently support (α, β)-core computation and on-the-fly query processing on large-scale bipartite graphs. We first introduce GCC, a warp-centric peeling algorithm that eliminates the need for costly index construction. To further reduce unnecessary computation, we propose GCC+, which performs a lightweight preprocessing based on the core numbers of vertices to prune vertices that are guaranteed to satisfy or
9
[28] A. P. Mukherjee and S. Tirthapura, “Enumerating maximal bicliques from a large graph using mapreduce,” IEEE Trans. Serv. Comput., vol. 10, no. 5, pp. 771–784, 2017. [29] A. Das and S. Tirthapura, “Incremental maintenance of maximal bicliques in a dynamic bipartite graph,” IEEE Trans. Multi Scale Comput. Syst., vol. 4, no. 3, pp. 231–242, 2018. [30] Z. Ma, Y. Liu, Y. Hu, J. Yang, C. Liu, and H. Dai, “Efficient maintenance for maximal bicliques in bipartite graph streams,” World Wide Web, vol. 25, no. 2, pp. 857–877, 2022. [31] Y. Zhang, C. A. Phillips, G. L. Rogers, E. J. Baker, E. J. Chesler, and M. A. Langston, “On finding bicliques in bipartite graphs: a novel algorithm and its application to the integration of diverse biological data types,” BMC Bioinform., vol. 15, p. 110, 2014. [32] L. Chen, C. Liu, R. Zhou, J. Xu, and J. Li, “Efficient exact algorithms for maximum balanced biclique search in bipartite graphs,” in Proceedings of the 2021 International Conference on Management of Data, 2021, pp. 248–260. [33] A. Tripathy, F. Hohman, D. H. Chau, and O. Green, “Scalable k-core decomposition for static graphs using a dynamic graph data structure,” in 2018 IEEE International Conference on Big Data (Big Data). IEEE, 2018, pp. 1134–1141. [34] A. Mehrafsa, S. Chester, and A. Thomo, “Vectorising k-core decomposition for GPU acceleration,” in Proceedings of the 32nd International Conference on Scientific and Statistical Database Management, 2020, pp. 1–4. [35] K. Date, K. Feng, R. Nagi, J. Xiong, N. S. Kim, and W.M. Hwu, “Collaborative (CPU+ GPU) algorithms for triangle counting and truss decomposition on the minsky architecture: Static graph challenge: Subgraph isomorphism,” in 2017 IEEE High Performance Extreme Computing Conference (HPEC). IEEE, 2017, pp. 1–7. [36] V. S. Mailthody, K. Date, Z. Qureshi, C. Pearson, R. Nagi, J. Xiong, and W.-m. Hwu, “Collaborative (CPU+ GPU) algorithms for triangle counting and truss decomposition,” in 2018 IEEE High Performance extreme Computing Conference (HPEC). IEEE, 2018, pp. 1–7. [37] M. Almasri, O. Anjum, C. Pearson, Z. Qureshi, V. S. Mailthody, R. Nagi, J. Xiong, and W.-m. Hwu, “Update on k-truss decomposition on GPU,” in 2019 IEEE High Performance Extreme Computing Conference (HPEC). IEEE, 2019, pp. 1–7. [38] Y. Che, Z. Lai, S. Sun, Y. Wang, and Q. Luo, “Accelerating truss decomposition on heterogeneous processors,” Proceedings of the VLDB Endowment, vol. 13, no. 10, pp. 1751–1764, 2020. [39] Y.-W. Wei, W.-M. Chen, and H.-H. Tsai, “Accelerating the bron-kerbosch algorithm for maximal clique enumeration using GPUs,” IEEE Transactions on Parallel and Distributed Systems, vol. 32, no. 9, pp. 2352–2366, 2021. [40] Z. Pan, S. He, X. Li, X. Zhang, R. Wang, and G. Chen, “Efficient maximal biclique enumeration on GPUs,” in Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, 2023, pp. 1–13. [41] J. L. Greathouse and M. Daga, “Efficient sparse matrix-vector multiplication on GPUs using the csr storage format,” in SC’14: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. IEEE, 2014, pp. 769–780. [42] W. Khaouid, M. Barsky, S. Venkatesh, and A. Thomo, “K-core decomposition of large networks on a single PC,” Proc. VLDB Endow., vol. 9, no. 1, pp. 13–23, 2015. [43] V. Batagelj and M. Zaversnik, “An o(m) algorithm for cores decomposition of networks,” CoRR, vol. cs.DS/0310049, 2003. [44] Y. Huang, C. Wang, J. Shi, and J. Shun, “Efficient algorithms for parallel bi-core decomposition,” in 2023 Symposium on Algorithmic Principles of Computer Systems (APOCS). SIAM, 2023, pp. 17–32.
and Knowledge Management, CIKM 2017, Singapore, November 06 - 10, 2017, E. Lim, M. Winslett, M. Sanderson, A. W. Fu, J. Sun, J. S. Culpepper, E. Lo, J. C. Ho, D. Donato, R. Agrawal, Y. Zheng, C. Castillo, A. Sun, V. S. Tseng, and C. Li, Eds. ACM, 2017, pp. 2047–2050. [14] A. Ahmed, V. Batagelj, X. Fu, S. Hong, D. Merrick, and A. Mrvar, “Visualisation and analysis of the internet movie database,” in APVIS 2007, 6th International Asia-Pacific Symposium on Visualization 2007, Sydney, Australia, 5-7 February 2007, S. Hong and K. Ma, Eds. IEEE Computer Society, 2007, pp. 17–24. [15] M. Cerinsek and V. Batagelj, “Generalized two-mode cores,” Soc. Networks, vol. 42, pp. 80–87, 2015. [16] S. Li, K. Wang, X. Lin, W. Zhang, Y. He, and L. Yuan, “Querying historical cohesive subgraphs over temporal bipartite graphs,” in 2024 IEEE 40th International Conference on Data Engineering (ICDE). IEEE, 2024, pp. 2503–2516. [17] B. Liu, L. Yuan, X. Lin, L. Qin, W. Zhang, and J. Zhou, “Efficient (α, β)-core computation in bipartite graphs,” VLDB J., vol. 29, no. 5, pp. 1075–1099, 2020. [18] J. Yu, H. Wang, X. Wang, Z. Li, L. Qin, W. Zhang, J. Liao, and Y. Zhang, “Group-based fraud detection network on ecommerce platforms,” in Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2023, Long Beach, CA, USA, August 6-10, 2023, A. K. Singh, Y. Sun, L. Akoglu, D. Gunopulos, X. Yan, R. Kumar, F. Ozcan, and J. Ye, Eds. ACM, 2023, pp. 5463–5475. [19] Q. Xu, F. Zhang, Z. Yao, L. Lu, X. Du, D. Deng, and B. He, “Efficient load-balanced butterfly counting on GPU,” Proceedings of the VLDB Endowment, vol. 15, no. 11, pp. 2450– 2462, 2022. [20] S. Li, K. Wang, W. Zhang, X. Lin, and Y. He, “Efficient bitruss decomposition on gpu,” IEEE Transactions on Knowledge and Data Engineering, 2025. [21] A. Ahmad, L. Yuan, D. Yan, G. Guo, J. Chen, and C. Zhang, “Accelerating k-core decomposition by a gpu,” in 2023 IEEE 39th International Conference on Data Engineering (ICDE). IEEE, 2023, pp. 1818–1831. [22] Z. Wang, L. Lai, Y. Liu, B. Shui, C. Tian, and S. Zhong, “Parallelization of butterfly counting on hierarchical memory,” The VLDB Journal, pp. 1–32, 2024. [23] K. Wang, X. Lin, L. Qin, W. Zhang, and Y. Zhang, “Efficient bitruss decomposition for large-scale bipartite graphs,” in 36th IEEE International Conference on Data Engineering, ICDE 2020, Dallas, TX, USA, April 20-24, 2020. IEEE, 2020, pp. 661–672. [24] Y. He, K. Wang, W. Zhang, X. Lin, and Y. Zhang, “Efficient reinforcement of bipartite networks at billion scale,” in 2022 IEEE 38th International Conference on Data Engineering (ICDE), 2022, pp. 446–458. [25] G. Zhao, K. Wang, W. Zhang, X. Lin, Y. Zhang, and Y. He, “Efficient computation of cohesive subgraphs in uncertain bipartite graphs,” in 38th IEEE International Conference on Data Engineering, ICDE 2022, Kuala Lumpur, Malaysia, May 9-12, 2022. IEEE, 2022, pp. 2333–2345. [26] Z. Zou, “Bitruss decomposition of bipartite graphs,” in Database Systems for Advanced Applications - 21st International Conference, DASFAA 2016, Dallas, TX, USA, April 1619, 2016, Proceedings, Part II, ser. Lecture Notes in Computer Science, S. B. Navathe, W. Wu, S. Shekhar, X. Du, X. S. Wang, and H. Xiong, Eds., vol. 9643. Springer, 2016, pp. 218–233. [27] A. E. Sariyü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, WSDM 2018, Marina Del Rey, CA, USA, February 5-9, 2018, Y. Chang, C. Zhai, Y. Liu, and Y. Maarek, Eds. ACM, 2018, pp. 504–512.
10