Accelerating Dynamic Graph Clustering on GPU Architectures with cuGraph

Accelerating Dynamic Graph Clustering on GPU Architectures with cuGraph Nelson Aloysio Reis de Almeida Passos1,2[0000−0003−1869−2976] , Emanuele Carlini2[0000−0003−3643−5404] , and Salvatore Trani2[0000−0001−6541−9409] 1

University of Pisa, Dept. of Computer Science, 56127 Pisa PI, Italy 2 National Research Council, 56124 Pisa PI, Italy

arXiv:2608.03695v1 [cs.DC] 4 Aug 2026

nelson.reis@phd.unipi.it {emanuele.carlini,salvatore.trani}@isti.cnr.it Abstract. This work addresses community detection in temporal networks through GPU-accelerated extensions of spectral clustering and modularity-based algorithms originally designed for static graphs. Built on the NVIDIA RAPIDS ecosystem, the framework enables the characterization and tracking of communities in snapshot-based dynamic graphs, either by Leiden greedy optimization with multi-GPU support via Dask-based workload distribution, or eigendecomposition of a symmetric Bethe-Hessian operator. Our multislice modularity backend achieves up to roughly three orders of magnitude speedup over the CPU reference under an equal-work budget, depending on graph density and snapshot count, while preserving compatibility with existing graph analytics pipelines. We demonstrate its applicability on real-world and synthetic datasets, facilitating exploratory analysis of structural network properties over time. Such capabilities are relevant across several application domains, such as epidemic spreading, financial systems, cybersecurity, and trajectory and mobility analysis. We release our implementation as free and open-source software, including Python bindings through the NetworkX-Temporal3 library for ease of use and zero-code acceleration with existing codebases. Keywords: temporal networks, community detection, GPU computing

1

Introduction

Community detection is a fundamental task in network science, which seeks to identify groups of nodes with functional similarity or shared characteristics. The identification of functional modules in cell structures, the detection of botnets and malicious actors in computer networks, and the discovery of users in social media platforms with shared political or cultural interests are just a few examples of its many applications in real-world settings. Among the many techniques employed for the task, there are inference-based statistical models relying on sampling and optimization strategies, such as Markov-Chain Monte Carlo and simulated annealing; matrix factorization based on eigendecomposition or random walk 3

https://www.networkx-temporal.org. Distributed under the 3-Clause BSD License.

2

N. A. R. A. Passos et al.

sampling; heuristic algorithms optimizing some sort of ‘quality’ function; and more recently, neural models that map nodes to a real-valued vector space, where distances encode structural or attribute similarity. Each method carries its own advantages and trade-offs, and their suitability is expected to be highly dependent on the specific context and requirements of the problem at hand [10,31]. By allowing nodes and edges to change over time, dynamic (temporal) graphs [16] offer a powerful mathematical framework for the analysis of non-Euclidean relational data, where individual elements (nodes) and their connections (edges) may fluctuate in response to external stimuli and internal dynamics. This enables the modeling of evolving relationships and interactions, crucial for studying real-world phenomena such as information diffusion, epidemic spreading, financial fraud, and traffic analysis. Such flexibility, however, also brings additional burdens, for both the definition of communities themselves (i.e., their identity) and the algorithmic implementations for their detection [10], which must now account for these additional dynamics to ensure their consistent tracking across time. In this work, we address the challenge of efficiently managing the increased complexity arising from node clustering in dynamic graphs by implementing GPU-based (graphics processing units) versions of widely adopted techniques for the task, with analytical tractability and scalability as primary goals. The analysis of large-scale networks exemplifies an area where GPUs can deliver a superior performance-to-cost ratio over CPU-bound operations due to higher memory bandwidth and massive parallelism, motivating the present research. We focus on three algorithms along two pathways for temporal community detection, relying on graph spectra and heuristic optimization: eigendecomposition and clustering of either the Bethe-Hessian [37] or the modularity matrix [22]; and Leiden optimization of multislice modularity [21,42], which maximizes the homonymous quality function measuring the density of connections within communities compared to a null model, i.e., a random (‘configuration’) graph with the same degree distribution as the observed network [4]. Our specific contributions are that we: – Implement three algorithms along two pathways for temporal community detection, using the open-source GPU libraries cuGraph for modularity optimization and CuPy with cuML for spectral clustering [24,25,26]; – Demonstrate that they enable the characterization and tracking of evolving communities, with the Leiden backend allowing multi-GPU execution via Dask [8] and achieving substantial speedups over its CPU reference; and – Integrate our implementations into the open-source NetworkX-Temporal library [28], enhancing its functionality and promoting user accessibility through zero-code-change GPU acceleration of existing workflows. The remainder of this paper is as follows. Section 2 discusses related work on static and temporal community detection. Section 3 details our methodology, including the algorithms we extend and their temporal formulations. Section 4 presents experimental results on several benchmark datasets. This work concludes by summarizing our contributions, limitations, and future research directions.

Accelerating Dynamic Graph Clustering on GPUs

2

3

Background & Related Work

The definition, identification, and tracking of communities in dynamic graphs remain open problems, compounded by the absence of a universally accepted notion of what constitutes a community and the inherent complexity of temporal networks [10,16]. The most common definition of community is that of a group of nodes with dense internal connections compared to connections to other groups, therefore understood as an assortative structure. Based on an assumption of homophily — ‘birds of a feather flock together’ [20] — it posits that nodes with similar features or connectivity patterns are more likely to belong to the same group, and is the prevailing definition in tasks such as social network analysis, where individuals with similar interests or characteristics tend to form communities. Meanwhile, other systems may exhibit different characteristics, such as hierarchical (e.g., nested communities), disassortative (bipartite), core-periphery, or overlapping (mixed-membership) structures, which call for alternative strategies and definitions outside the scope of this work [10]. This work focuses on modularity optimization and spectral clustering, two techniques widely adopted for community detection in static graphs, extensible to the temporal domain and suitable for GPU-based implementations. Both are commonly employed due to their relative ease of implementation, strong empirical performance, and compatibility with sparse matrices, and traditionally rely on CPU-bound implementations designed for static graphs. Other solutions include divisive strategies for iterative edge removal, such as edge betweenness centrality [12]; statistical physics approaches formulating community detection as an energy minimization problem, including Ising- and Potts-based models [35,39]; inferential models based on, e.g., stochastic block modeling (SBM) [30]; information-theoretic techniques, such as Infomap [36]; propagation-based methods that iteratively diffuse labels across local neighborhoods [34]; non-negative matrix factorization [15] and matrix decomposition by random walk sampling [32]; graph embedding methods to obtain low-dimensional node representations, also based on walk sampling [47]; hybrid and ensemble approaches combining multiple strategies [45]; and more recent deep (multilayer) neural network-based models with strong empirical performance that approximate (‘learn’) a function mapping nodes V of a graph G into a real, d-dimensional (latent) space — where distances among nodes encode their similarity based on both the system structure (topology) defined by edges E, and high-dimensional node attributes X , i.e., f (G) → Rd , where G = (V, E, X ) — either end-to-end differentiable or, much more frequently, subsequently clustered using conventional methods such as k-means [40]. This work focuses instead on non-attributed, large-scale dynamic graph data. Although several methods have been extended to the temporal domain, e.g., by segmenting networks into slices (snapshots) and employing strategies like dynamic SBM, inter-slice couplings, and dynamic embedding procedures [6,21,44], they often rely on expensive CPU-bound operations, such as repeated inference, supra-graph construction, or orthogonal matrix alignment, which hinder their applicability at scale or under high temporal resolution, including mobility and trajectory analysis, social network monitoring, and cybersecurity applications.

4

3

N. A. R. A. Passos et al.

Methodology & Implementation

This section details the algorithms we extend and their temporal formulations, along with implementation details and integration into the NetworkX-Temporal library [28]. We define spectral clustering on supra-graphs and multislice (temporal) modularity optimization, the latter of which is evaluated at scale in Section 4. 3.1

Spectral Clustering

Spectral clustering relies on the eigendecomposition of graph operators to obtain low-dimensional node embeddings that capture the global structure of the network. Specifically, spectral methods cluster vertices by eigendecomposition of the normalized Laplacian L̃ = D−1/2 LD−1/2 , where L = D − A is the graph Laplacian, D is the degree matrix, and A is the adjacency matrix. The k leading eigenvectors of L̃ form a matrix U ∈ Rn×k , where each row corresponds to a node embedding; these rows are then clustered using k-means or another partitioning algorithm [23]. The second smallest eigenvector, known as the Fiedler vector, can be used to bipartition a graph by thresholding its values, and its relation to graph connectivity is formalized by Cheeger’s inequality, which bounds the conductance of the best partition by the second smallest eigenvalue of L̃ [5]. The choice of objective function determines which Laplacian is used and how the resulting partition is evaluated. For instance, minimizing the normalized cut [38] encourages partitions with dense intra-community and sparse inter-

NetworkX-Temporal

á

import networkx_temporal as tx

3

Leiden (Modularity)

Spectral (Bethe-Hessian, Modularity)

tx.algorithms.leiden_communities

tx.algorithms.spectral_clustering

>

pylibcugraph

libcugraph

cupy + cuml

(cuGraph bindings)

(C++/CUDA)

(Lanczos + k-means)

G(2)

···

G(T )

Supra-graph Asupra

GPU

CPU

G(1)

Fig. 1. NetworkX-Temporal integration. Temporal graph snapshots G(t) are assembled into a supra-graph and dispatched through one of two GPU-accelerated paths: multislice modularity via Leiden optimization, or spectral clustering of a (temporal) Bethe-Hessian or modularity matrix. All methods execute on the RAPIDS ecosystem and return per-snapshot community assignments, allowing zero-code-change execution and device selection by setting an environment variable. In blue: our contributions.

Accelerating Dynamic Graph Clustering on GPUs

5

community connections, i.e., normalized by edge volume. It is expressed as NCut(C1 , . . . , Ck ) =

k X cut(Ci , C̄i ) i=1

vol(Ci )

,

cut(Ci , C̄i ) =

X

Auv ,

(1)

u∈Ci , v ∈C / i

P where vol(Ci ) = u∈Ci du is the sum of node degrees in Ci , and cut(Ci , C̄i ) is the total volume of edges connecting nodes in Ci to those outside of it. A similar formulation4 employs the random-walk Laplacian L̂ = D−1 L = I − D−1 A, which shares the eigenvalues of L̃, but whose eigenvectors correspond directly to the relaxed cluster indicator vectors, solvable as a generalized eigenproblem. Minimizing balanced ratio cut [13] instead considers partition size |Ci | rather than edge volume, and is the default implementation in cuGraph [24], defined as RCut(C1 , . . . , Ck ) =

k X cut(Ci , C̄i ) i=1

|Ci |

.

(2)

Note that, while both objectives are NP-hard in their discrete form, their continuous relaxations allow efficient approximations corresponding to eigenvector problems on the normalized (L̃) and unnormalized (L) graph Laplacians, which can be solved using iterative methods such as the Lanczos algorithm or power iteration, which are efficient for large sparse graphs. Spectral methods are computationally efficient on sparse graphs, but require the number of communities k to be specified in advance and are sensitive to disconnected graph components, i.e, groups of nodes with no paths in between, and may therefore yield suboptimal partitions on dynamic graphs where nodes are not present across all time steps. Constructing a supra-Laplacian Lsupra from (temporal) adjacencies Asupra encoding intra-slice connections and inter-slice couplings as off-diagonal blocks allows for spectral clustering techniques to be extended to the temporal domain,  (1)  A ωI ··· 0  ωI A(2) · · · 0    supra A = . (3) , . .. . .. ..  ..  . 0 0 · · · A(T ) where A(t) is the adjacency matrix of snapshot t, ω is the inter-slice coupling strength that encourages temporal persistence of community assignments across snapshots, and I is the identity matrix connecting corresponding temporal nodes. Although this enables the use of iterative solvers (Lanczos, power iteration), leveraging GPU acceleration for eigendecomposition and clustering, the resulting matrix has a prohibitive order of nT × nT , where n is the number of nodes and T is the number of snapshots. Moreover, it is well-known that Laplacian spectral methods fail in sparse graphs near the detectability threshold of communities, 4 Symmetric normalization introduces a D1/2 scaling that requires an additional (heuristic) row-normalization step to correct for high node degree heterogeneity [18].

6

N. A. R. A. Passos et al.

i.e., the regime where many real temporal networks are expected to lie. To escape these issues, we first consider instead a principled alternative based on linearizing belief propagation [11], yielding the non-backtracking (Hashimoto-type) operator   λAs −λI λAs 0  λ(Ds − I) 0 λDs 0  , B= (4) t  ηA 0 ηAt −ηI  t t ηD 0 η(D − I) 0 L (t) where each of As , At , Ds , Dt is an nT × nT matrix: As = is the tA block-diagonal intra-slice adjacency matrix, At is the inter-slice adjacency matrix connecting each node to its time-adjacent copies with block-bidiagonal identities, Ds and Dt are the corresponding diagonal degree matrices, and I is the nT dimensional identity. The scalar λ = (cin − cout )/(k c) is the second eigenvalue of the (normalized) k×k block affinity matrix — with cin and cout the average withinand between-community connection rates, k the number of communities, and c the average degree — and governs how storngly community signal propagates along spatial edges; analogously, η governs its propagation along temporal edges. Together they yield a more flexible and expressive formulation than that based solely on ω (Eq. 3), with effective SNR cλ2 dictating detectability5 and η ∈ [0, 1] the probability that a node retains its community label on consecutive time steps. The construction is intentionally asymmetric (direction-aware), yielding a method that preserves the arrow of time, is asymptotically optimal in the sparse regime [11], and robust to degree heterogeneity, avoiding the localization on high-degree nodes of Laplacian operators (Footnote 4). Although the resulting matrix is 4nT × 4nT , it is also critically sparse and therefore more amenable to iterative solvers on GPUs: each block of B corresponds to either an adjacency or diagonal matrix, and its k − 1 eigenvectors with largest eigenvalues may be extracted to perform k-means clustering on the resulting n vectors in Rk−1 . However, sparse GPU eigensolvers are currently restricted6 to symmetric or Hermitian matrices, so the asymmetric non-backtracking operator B cannot be solved directly by available routines. We therefore reformulate it as a symmetric problem by considering the Bethe-Hessian H(r) = (r2 − 1)I − rA + D [37], where A and D are the adjacency and degree matrices of the supra-graph, and r is a regularization parameter. This maps the informative (out-of-bulk) eigenvalues of B to the negative eigenvalues of H(r), effectively preserving asymptotic optimality in the static case with appropriate r selection. If r = 1, H(r) reduces to the √ standard Laplacian L; in the static SBM regime, r is optimally set near c, i.e., a degree-based approximation (refined in our implementation for degree 5

Below the information-theoretic threshold (Almeida–Thouless line), recovery is impossible for any algorithm, while cλ2 = 1 (Kesten–Stigum threshold) defines the limit of efficient recovery for polynomial-time algorithms [11]. For k > 4 communities, they separate, defining a regime where detection is possible but not known to be efficient. 6 Although ARPACK’s non-symmetric Arnoldi routines are available in SciPy, their use on GPUs requires matvec callbacks (CPU-side iterations of per-step host-device transfers), effectively negating the potential gains of acceleration for large-scale problems.

Accelerating Dynamic Graph Clustering on GPUs

7

heterogeneity), while temporal extensions require accounting for both spatial and temporal connectivity, characterized only in specific settings [7]. This symmetric eigenproblem is solved fully on-GPU using open-source libraries [25,26] — yielding an efficient and consistent algorithm [48] for clustering on dynamic graphs. 3.2

Modularity Optimization

Modularity Q aims to quantify the extent to which a network exhibits community structures by comparing the density of intra-community edges against a random graph that preserves the degree distribution of the observed network [4]. Let m be the number of edges, dout and din i j the out- and in-degrees of nodes i and j, ci the community of node i, and γ = 1 (default) the resolution parameter. Then, Q=

 dout din 1 X i j Aij − γ δ(ci , cj ), 2m i,j 2m

(5)

where δ(ci , cj ) = 1 if nodes i and j belong to the same community and 0 otherwise. Higher values of Q indicate denser intra-community and sparser inter-community connections relative to the null model; while γ allows tuning the resolution7 of detected communities, with higher values favoring smaller community sizes. Maximizing Q over all possible partitions is NP-hard [10], so heuristic approaches are employed in practice. The Leiden algorithm [42] adds a refinement phase to the widely used Louvain method [2], which iteratively merges nodes into communities to maximize local modularity gains and recursively aggregates communities into supernodes — resulting in faster runtimes and guaranteeing well-connected partitions, a built-in modeling assumption. The heuristic extends to directed and weighted graphs, and supports alternative quality functions such as surprise [1] and the Constant Potts Model (CPM) [41]. Alternatively, modularity also admits a spectral formulation Q = Tr(C⊤ MC)/2m, where M = A − γ(dout d⊤ in )/2m is the modularity matrix. In this case, projecting (‘embedding’) nodes onto the leading eigenvectors of M yields a low-dimensional representation that approximates the discrete optimization problem, which may be subsequently clustered to recover partitions [22] — for bipartitioning, the sign of the leading eigenvector determines the split, and the absence of positive eigenvalues signals that the current bipartition is optimal under modularity. The measure has been extended to dynamic graphs through, e.g., the multislice formulation [21], which couples snapshot-level modularity matrices through interslice edges encoding temporal dependencies, enabling community detection and tracking across discrete-time aggregations. Continuous-time extensions, such as the longitudinal formulation [3], instead impose smoothness regularization and null model constraints. Both variants increase the problem size with the number of snapshots or pairwise interactions, compounding the scalability challenges of the 7 Modularity maximization is subject to a resolution limit [9]: because the null model term couples all node pairs globally, communities smaller than a scale determined by √ 2m may be merged into larger ones, even in the partition that globally maximizes Q.

8

N. A. R. A. Passos et al.

static case. The multislice formulation is compatible with existing optimization methods, such as Leiden, which we efficiently implement on GPUs by building the supra-adjacency matrix encoding intra-slice and inter-slice connections. Multislice modularity QMS [21] is defined analogously to the static case, with additional inter-slice couplings of (optionally time-varying) strength ω that encourage temporal persistence of community labels across snapshots. This yields a similar objective function to be maximized, which may be expressed as # ! " (s) (s) k kj 1 X (s) (r) (s) (sr) (sr) (s) i δ + δij ω δ(ci , cj ), (6) QMS = Aij − γ 2µ i,j,s,r 2m(s) (s)

(s)

where Aij is the adjacency matrix of snapshot s, ki is the degree of node i in snapshot s, m(s) is the number of edges in snapshot s, γ (s) is the resolution parameter for snapshot s, ω (sr) is the inter-slice node coupling strength between s and r, and µ is the supra-graph size (weighted intra- and inter-slice connections). Following Equation 6, we may express multislice modularity in spectral form by defining a supra-modularity matrix incorporating both intra-slice and inter-slice contributions, and a community assignment matrix C encoding the partition across all snapshots. This yields a spectral formulation expressed as QMS = Tr(C ⊤ MC)/2µ, where M is the (temporal) modularity matrix with diagonal blocks corresponding to the modularity matrices of each snapshot and offdiagonal blocks encoding the inter-slice couplings, and each block in C ∈ RnT ×k corresponds to the community assignments of a snapshot. If C is binary with one non-zero entry per row, then QMS = QMS ; solving its continuous relaxation approximates the discrete optimization problem, allowing for efficient community detection and tracking across time through eigendecomposition and subsequent clustering of the resulting embeddings (leading eigenvectors) with, e.g., k-means. This spectral relaxation therefore enables the application of sparse eigensolver implementations: unlike the non-backtracking operator, the modularity matrix yields a real, orthogonal eigenvector embedding when symmetric, i.e., for undirected graphs with inter-slice couplings ω (sr) = ω (rs) . Meanwhile, the Leiden algorithm [42] and its GPU backend [24] allow for identity-preserving characterization of communities across snapshots, encouraging temporal persistence in label assignments through multislice modularity. Note that the supra-graph optimization strategy is also compatible with alternative quality functions beyond modularity, such as a temporal (multislice) variant of CPM [41], provided the null model is appropriately defined for the metric and temporal setting at hand. In sum, both spectral decomposition and greedy optimization allow leveraging GPU acceleration, offering a unified framework for community detection on dynamic graphs. It is worth noting that the spectral pathway, which directly captures the global structure of the network through its eigenvectors, allows for a more principled approach to detecting communities. While Leiden optimization relies on heuristics that may not guarantee optimal partitions and can be sensitive to the resolution parameter γ and inter-slice coupling strength ω, it allows for multi-GPU execution via Dask-based workload distribution, advantageous for large-scale dynamic graphs, making it a practical choice for diverse applications.

Accelerating Dynamic Graph Clustering on GPUs

9

Table 1. Dataset properties. |V| and |E| denote unique nodes and edges; Σ(V) and Σ(E), the sum of nodes and edges over time, i.e., counting each occurrence across snapshots; |T | and |C| are the number of snapshots and communities; † marks static graphs used as single-snapshot baselines; and ‡, the largest dataset, where a single CPU run allowed to exceed the time budget completed in ≈6 h, versus ≈10 min on GPU. |V|

Σ(V)

|E|

Σ(E)

|T |

|C|

CiteSeer† [46] Cora† [46]

3 279 2 708

3 279 2 708

4 552 5 278

4 552 5 278

1 1

6 7

Brain [33] Dblp [49] Patent [14] PubMed [27] School [19]

5 000 28 085 12 214 19 717 327

60 000 101 797 41 529 37 003 309 006

878 207 153 822 41 916 44 324 7 004

947 744 222 165 41 916 44 324 188 508

12 27 891 42 7 375

10 10 6 3 9

69 854 169 343 1 324 064 270 013

142 316 374 433 4 998 391 614 578

696 819 1 157 799 13 649 351 783 165

696 819 1 157 799 13 649 351 783 165

27 29 40 31

5 40 172 31

50 000 100 000 50 000 50 000

250 000 500 000 250 000 500 000

1 250 539 2 500 515 2 498 067 2 495 376

1 251 057 2 501 000 2 500 045 2 497 636

5 5 5 10

10 10 10 10

Dataset

ArxivAI [17] ArxivCS [17] ArxivLarge‡ [17] ArxivMath [17] SBM [29] SBM-N [29] SBM-E [29] SBM-T [29]

4

Experimental Results

We present experimental results of our code implementation on several real-world and synthetic dynamic graph datasets, summarized in Table 1 and Figure 2. Our central comparison is temporal-versus-temporal: the GPU multislice Leiden backend against its CPU reference, leidenalg [43], on the supra-adjacency representation. For fairness across implementations with differing stopping criteria, all methods are capped at two optimization passes; we therefore report runtime under a fixed, equal-work budget rather than time-to-convergence. Observed speedups (Fig. 2a) are consistent and substantial, ranging from 22× on ArxivAI (336.3 s → 15.4 s) and Dblp (145.5 s → 6.6 s) to 31× on ArxivCS (916.3 s → 29.2 s) and 64× on ArxivMath (1357.7 s → 21.2 s); dense but low-snapshot Brain yields a more modest 2.7× (154.7 s → 56.3 s). The most striking case is Patent, collapsing by 978× (1397.0 s → 1.4 s). This is precisely the scaling challenge our work targets, and constitutes our main empirical result, as it demonstrates the practical benefits of GPU acceleration for fine-grained community detection on datasets with a large number of snapshots, where CPU-bound methods struggle to meet demand. For the largest temporal instances, the effect is less a speedup than a change in tractability (Tab. 1, ‡). We further report on two interesting boundary cases. First, School (7375 snapshots) exposes a scaling limit of the supra-graph construction: the inter-slice coupling grows with the snapshot count, so building and solving the supra-adjacency dominates (211 s for our method), with the CPU baseline failing to complete within the time budget (OOT); this limit motivates approximate strategies such as windowed optimization or distributed sparse construction. Second, the GPU advantage emerges only at scale: for small static graphs (CiteSeer, Cora), the CPU outperforms the GPU backend, as kernel launch and

N. A. R. A. Passos et al. leidenalg (CPU, temporal)

(a)

Ours (GPU, temporal)

Execution time (s)

978×

64×

103 102 10

31×

22× 22×

3×

30×

1

100

0.7×

0.8×

SBM artificial graphs

(b) Execution time (s)

10

100

87s

80

62s

60 40

57s

29s

20 2× 2× 2× nodes edges snapsh.

A

rx

iv C

at M iv

base

A

rx

S

h

I

in

iv A rx

A

p bl

ra B

D

ed Pa te nt

r

bM

ee eS

Pu

C

it

C or

a

0

Fig. 2. Runtime evaluation. (a) Execution time of the GPU-based Leiden backend against its CPU-bound baseline across real-world datasets (log scale). (b) Effect on runtime of doubling each generation parameter (nodes, edges, snapshots) over synthetic SBM instances. Algorithm runs were limited to two iterations only (leidenalg [43] default) to ensure fair comparisons. Results reported over five runs, including host-device transfer and kernel launch overheads; error bars show standard deviation. Experiments conducted on an Intel Xeon Gold 6330 (CPU) and an NVIDIA A100 80GB (GPU).

transfer overheads dominate; these could potentially be mitigated by assembling the supra-graph directly on device. Moreover, the synthetic SBM graphs (Fig. 2b) characterize how the GPU implementation scales along distinct axes (nodes, edges, snapshots) rather than draw head-to-head comparisons against the CPU.

5

Final Remarks

In this work, we presented GPU-accelerated implementations of spectral clustering and modularity optimization for dynamic graphs, to our knowledge the first in literature to leverage the RAPIDS ecosystem for efficient matrix operations and eigensolvers on GPU hardware; and a unified integration of both as a zero-codechange backend for NetworkX-Temporal, yielding concrete usability benefits. Our implementations are designed to be compatible with existing graph analytics pipelines, allowing for seamless integration with data processing workflows without extensive codebase modifications. Limitations include the focus on non-attributed graphs, which may not capture the full richness of real-world networks, and the reliance on assortative community structures, which is not suitable for all contexts. Lastly, we leave evaluating the empirical performance of our spectral clustering approach under different regimes of detectability to the near future.

References 1. Aldecoa, R., Marín, I.: Surprise maximization reveals the community structure of complex networks. Scientific Reports 3(1) (Jan 2013) 2. Blondel, V.D., Guillaume, J.L., Lambiotte, R., Lefebvre, E.: Fast unfolding of community in large networks. Stat. Mech.: Theory and Experiment (10 2008)

Accelerating Dynamic Graph Clustering on GPUs

11

3. Brabant, V., Asgari, Y., Borgnat, P., Bonifati, A., Cazabet, R.: Longitudinal modularity, a modularity for link streams. EPJ Data Science 14(1) (Feb 2025) 4. Chung, F., Lu, L.: Connected Components in Random Graphs with Given Expected Degree Sequences. Annals of Combinatorics 6(2), 125–145 (2002) 5. Chung, F.R.K.: Spectral Graph Theory. CBMS Regional Conference Series in Mathematics, American Mathematical Society (1996) 6. Cugmas, M., Žiberna, A.: Approaches to blockmodeling dynamic networks: A monte carlo simulation study. Social Networks 73, 7–19 (May 2023) 7. Dall’Amico, L., Couillet, R., Tremblay, N.: Community detection in sparse timeevolving graphs with a dynamical bethe-hessian (2020) 8. Dask Corporation: Dask Documentation. (2026), accessed: 2026-06-29 9. Fortunato, S., Barthélemy, M.: Resolution limit in community detection. Proceedings of the National Academy of Sciences 104(1), 36–41 (1 2007) 10. Fortunato, S., Hric, D.: Community detection in networks: A user guide. Physics Reports 659, 1–44 (Nov 2016) 11. Ghasemian, A., Zhang, P., Clauset, A., Moore, C., Peel, L.: Detectability thresholds and optimal algorithms for community structure in dynamic networks. Physical Review X 6(3) (Jul 2016) 12. Girvan, M., Newman, M.E.J.: Community structure in social and biological networks. National Academy of Sciences 99(12), 7821–7826 (6 2002) 13. Hagen, L., Kahng, A.: New spectral methods for ratio cut partitioning and clustering. IEEE Tr. on Computer-Aided Design of Int. Circuits and S. 11(9), 1074–1085 (1992) 14. Hall, B., Jaffe, A., Trajtenberg, M.: The NBER Patent Citation Data File: Lessons, Insights and Methodological Tools (Oct 2001) 15. He, C., Fei, X., Cheng, Q., Li, H., Hu, Z., Tang, Y.: A survey of community detection in complex networks using nonnegative matrix factorization. IEEE Transactions on Computational Social Systems 9(2), 440–457 (2022) 16. Holme, P., Saramäki, J. (eds.): Temporal Network Theory. Springer International Publishing (2023) 17. Liu, M., Liang, K., Liu, Y., Wang, S., Zhou, S., Liu, X.: arXiv4TGC: Large-scale datasets for temporal graph clustering (2023) 18. von Luxburg, U.: A tutorial on spectral clustering. Statistics and Computing 17(4), 395–416 (Aug 2007) 19. Mastrandrea, R., Fournet, J., Barrat, A.: Contact patterns in a high school: A comparison between data collected using wearable sensors, contact diaries and friendship surveys. PLOS ONE 10(9), e0136497 (Sep 2015) 20. McPherson, M., Smith-Lovin, L., Cook, J.M.: Birds of a feather: Homophily in social networks. Annual Review of Sociology 27(1), 415–444 (8 2001) 21. Mucha, P.J., Richardson, T., Macon, K., Porter, M.A., Onnela, J.P.: Community structure in time-dependent, multiscale, and multiplex networks. Science 328(5980), 876–878 (5 2010) 22. Newman, M.E.J.: Modularity and community structure in networks. Proceedings of the National Academy of Sciences 103(23), 8577–8582 (2006) 23. Ng, A., Jordan, M., Weiss, Y.: On spectral clustering: Analysis and an algorithm. In: Dietterich, T., Becker, S., Ghahramani, Z. (eds.) Advances in Neural Information Processing Systems. vol. 14. MIT Press (2001) 24. NVIDIA Corporation: cuGraph Documentation. (2026), accessed: 2026-06-29 25. NVIDIA Corporation: cuML Documentation. (2026), accessed: 2026-06-29 26. Okuta, R., Unno, Y., Nishino, D., Hido, S., Loomis, C.: CuPy: A NumPy-compatible library for NVIDIA GPU calculations. In: Workshop on Machine Learning Systems (LearningSys), Neural Information Processing Systems (NIPS) (2017)

12

N. A. R. A. Passos et al.

27. Passos, N.A.R.A., Carlini, E., Trani, S.: Deep community detection in attributed temporal graphs: Experimental evaluation of current approaches. In: Proceedings of the 3rd Graph Neural Networking Workshop (GNNet ’24). pp. 1–6. ACM (2024) 28. Passos, N.A.R.A., Carlini, E., Trani, S.: NetworkX-Temporal: Building, manipulating, and analyzing dynamic graph structures. SoftwareX 31, 102277 (2025) 29. Passos, N.A.R.A., Carlini, E., Trani, S.: Tadc-sbm: a time-varying, attributed, degree-corrected stochastic block model. In: 2025 IEEE Symposium on Computers and Communications (ISCC). pp. 1–6 (2025) 30. Peixoto, T.P.: Bayesian stochastic blockmodeling (Nov 2019) 31. Peixoto, T.P.: Descriptive vs. Inferential Community Detection in Networks: Pitfalls, Myths and Half-Truths. Elements in the Structure and Dynamics of Complex Networks, Cambridge University Press (2023) 32. Pons, P., Latapy, M.: Computing communities in large networks using random walks. Journal of Graph Algorithms and Applications 10(2), 191–218 (2006) 33. Preti, M.G., Bolton, T.A., Van De Ville, D.: The dynamic functional connectome: State-of-the-art and perspectives. NeuroImage 160, 41–54 (Oct 2017) 34. Raghavan, U.N., Albert, R., Kumara, S.: Near linear time algorithm to detect community structures in large-scale networks. Physical Review E 76(3) (Sep 2007) 35. Reichardt, J., Bornholdt, S.: Detecting fuzzy community structures in complex networks with a potts model. Physical Review Letters 93(21) (Nov 2004) 36. Rosvall, M., Bergstrom, C.T.: Maps of random walks on complex networks reveal community structure. PNAS 105(4), 1118–1123 (Jan 2008) 37. Saade, A., Krzakala, F., Zdeborová, L.: Spectral clustering of graphs with the bethe hessian. In: Ghahramani, Z., Welling, M., Cortes, C., Lawrence, N., Weinberger, K. (eds.) Advances in NIPS. vol. 27. Curran Associates, Inc. (2014) 38. Shi, J., Malik, J.: Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence 22(8), 888–905 (2000) 39. Son, S.W., Jeong, H., Noh, J.D.: Random field ising model and community structure in complex networks. The European Physical Journal B - Condensed Matter and Complex Systems 50(3), 431–437 (Apr 2006) 40. Su, X., Xue, S., Liu, F., Wu, J., Yang, J., Zhou, C., Hu, W., Paris, C., Nepal, S., Jin, D., Sheng, Q.Z., Yu, P.S.: A comprehensive survey on community detection with deep learning. IEEE T. on N.Networks and Learning Systems pp. 1–21 (2022) 41. Traag, V.A., Van Dooren, P., Nesterov, Y.: Narrow scope for resolution-limit-free community detection. Physical Review E 84(1) (Jul 2011) 42. Traag, V.A., Waltman, L., van Eck, N.J.: From Louvain to Leiden: guaranteeing well-connected communities. Scientific Reports 9(1), 5233 (3 2019) 43. Traag, V.A.: Leidenalg Documentation. (2026), accessed: 2026-06-29 44. Xue, G., Zhong, M., Li, J., Chen, J., Zhai, C., Kong, R.: Dynamic network embedding survey. Neurocomputing 472, 212–223 (Feb 2022) 45. Yan, C., Chang, Z.: Modularized tri-factor nonnegative matrix factorization for community detection enhancement. Physica A: S.Mech.&Ap. 533, 122–050 (2019) 46. Yang, Z., Cohen, W.W., Salakhutdinov, R.: Revisiting semi-supervised learning with graph embeddings. In: ICML’16 Proc., Vol.48. pp. 40–48. JMLR.org (2016) 47. Zhang, D., Yin, J., Zhu, X., Zhang, C.: Network representation learning: A survey. IEEE Transactions on Big Data 6(1), 3–28 (2020) 48. Zhao, Y., Levina, E., Zhu, J.: Consistency of community detection in networks under degree-corrected stochastic block models. Ann. Statist. 40(4) (2012) 49. Zuo, Y., Liu, G., Lin, H., Guo, J., Hu, X., Wu, J.: Embedding temporal network via neighborhood formation. In: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. KDD ’18, ACM (Jul 2018)

Related documents

• Efficient Coupled-Cluster Python Frameworks for Next-Generation GPUs: A Comparative Study of CuPy and PyTorch on the Hopper and Grace Hopper Architecture.#375310
• GPU-Accelerated Multilevel Graph Clustering: A Parallel Perspective on Louvain and Leiden#423934
• Performance modeling and optimization techniques for heterogeneous computing#957827
• Exploiting Dependency and Parallelism: Real-Time Scheduling and Analysis for GPU Tasks#2742
• SAGA: Workflow-Atomic Scheduling for AI Agent Inference on GPU Clusters#151760