arXiv CSopen access

DG-CoLearn: An Efficient Collaborative Learning Framework for Dynamic Graphs

arXiv:2605.31427v1 [cs.LG] 29 May 2026

DG-CoLearn: An Efficient Collaborative Learning Framework for Dynamic Graphs

Au Ashley Hoi-Ting1 Zikun Zhang1 Ligang He1 Qiang Ni2 1 Department of Computer Science, The University of Warwick 2 School of Computing and Communications, Lancaster University {ashley.au, zikun.zhang.1, ligang.he}@warwick.ac.uk [email protected]

Abstract Dynamic graph learning (DGL) is essential for modelling evolving graph data, but existing methods suffer from significant computational overhead due to repeated full-snapshot retraining and are not well-suited for collaborative settings with partitioned data. In realistic graph systems, cross-partition edges are unavoidable, but direct sharing of graph structure between clients may violate privacy constraints. We propose DG-CoLearn, a client-oblivious collaborative dynamic graph learning framework built on incremental graph snapshot processing, which focuses computation on graph regions affected by temporal updates while preserving historical information through temporal modelling. This incremental design is consistently applied across the entire graph processing pipeline, including a server-mediated embedding exchange mechanism to enable accurate multi-hop message passing without exposing raw cross-client structural information. Extensive experiments demonstrate that DG-CoLearn achieves up to 33.8× speedup in training time and 27.4× reduction in communication overhead, while consistently improving predictive performance on both node classification (up to 13.36% F1 improvement) and link prediction (up to 8.27% MAP improvement) tasks. These results highlight the effectiveness of DG-CoLearn in bridging efficiency, scalability, and client-to-client structural privacy in collaborative dynamic graph learning.

1

Introduction

Dynamic graphs, where nodes, edges, and their features evolve over time, are prevalent in many real-world applications such as social networks, biology science and financial data analysis [5]. For example, social network platforms such as Instagram and Tiktok collect and send user interactions to a centralized server. These data naturally form a dynamic graph as new interactions are introduced. Learning meaningful representations from these evolving structures, commonly refered to Dynamic Graph Learning (DGL), is critical for tasks including link prediction and node classification. However, centralized DGL faces significant challenges. Frequent graph updates require repeated processing of large and evolving graph snapshots, leading to prohibitive computational and memory cost on the server. Collaborative learning offers a promising solution by distributing computation across multiple clients [31, 36]. In graph settings, this typically takes the form of intra-graph distributed learning, where a central server partitions data into client-specific subgraphs and coordinates distributed learning. While this paradigm improves scalability, it introduces a unique tension between efficiency, structural dependency, and privacy. In particular, real-world graphs are inherently interconnected: crosspartition edges are unavoidable and carry essential information for accurate learning. At the same time, privacy constraints often prohibit clients from accessing cross-partition connectivity, creating incomplete local views and hindering effective message passing. Preprint.

Existing approaches to collaborative or federated graph learning primarily focus on static graphs and assume either (i) disjoint client subgraphs without cross-client edges, or (ii) full visibility of cross-client connectivity [4, 26]. These assumptions limit their applicability in realistic dynamic settings. Moreover, prior work largely adopts the classical federated learning (FL) privacy model, where the central server is treated as untrusted and the primary objective is to prevent data leakage to the server [21]. However, this model does not capture an important class of real-world systems, such as financial platforms or infrastructure networks, where a central coordinator necessarily maintains global topology, and the primary privacy risk lies in preventing information leakage between clients rather than from clients to the server. In this work, we formalize and study this alternative setting, which we term client-oblivious collaborative graph learning. In this regime, a (trusted or secured) central coordinator maintains the global graph structure and mediates communication, while clients are restricted to their local subgraphs and must remain oblivious to cross-client connectivity. The key privacy objective is thus horizontal privacy: ensuring that no client can infer the structure, features, or labels of another client’s subgraph, even in the presence of cross-partition dependencies. This setting introduces new challenges that are not addressed by existing FL frameworks, particularly in dynamic graphs where structural changes are frequent and localized. Additionally, a fundamental inefficiency arises in existing dynamic graph learning methods, both centralized and collaborative, which typically retrain models over entire graph snapshots at each timestamps. This design is particularly wasteful in evolving graphs, where updates are often sparse and localized. In collaborative settings, this inefficiency is further amplified by repeated cross-client communication and redundant recomputation, making existing approaches impractical at scale. To address these challenges, we propose DG-CoLearn, a collaborative learning framework for dynamic graphs built on a unifying principle: incremental snapshot processing. Instead of retraining on full graph snapshots, DG-CoLearn selectively updates only the nodes and edges affected by temporal changes, while preserving historical representations for unchanged regions. This principle permeates all stages of the framework: graph partitioning is restricted to affected regions, clients perform lightweight local training on updated subgraphs, and cross-client node embedding computation are limited to newly influenced nodes. Building on this design, DG-CoLearn achieves both efficiency and effectiveness. By exploiting temporal locality, it significantly reduces computation and communication overhead, while its privacy-aware aggregation mechanism enables accurate modelling of cross-client dependencies. Extensive experiments on multiple dynamic graph benchmarks demonstrate that DG-CoLearn achieves substantial speedups over full-snapshot retraining while consistently improving predictive performance on both link prediction and node classification tasks. Our contributions are summarized as follows: • We formalise client-oblivious collaborative graph learning, a practically motivated privacy regime that focuses on preventing cross-client structural leakage under a centralized coordinator. • We propose a novel duo-stage graph partitioning algorithm tailored to collaborative graph learning, reducing cross-client communication while maintaining balanced and informative subgraphs for effective and generalizable training on both node classification and link prediction tasks. • We incorporate a lightweight local training scheme for clients to incrementally perform dynamic graph learning while preserving historical knowledge. • We design a server-mediated cross-client node knowledge exchange mechanism that derives global representations without raw data exchange.

2

Related Work

Dynamic Graph Learning. Centralized DGL has been studied through both discrete-snapshot models [24, 22, 35] and continuous-time (CT) formulations such as TGAT [6], TGN [27], and DyGFormer [35], which maintain per-node memory states and attend over temporal neighbourhoods. Among snapshot-based approaches, ROLAND [34] decouples temporal modelling from graph structure by hierarchically updating node states across snapshots via a GRU, avoiding sequential retraining over all historical snapshots. DG-CoLearn builds on ROLAND’s state-update perspective 2

but further observes that, if node states are updated incrementally, unchanged nodes need not be retrained at all, motivating our incremental snapshot processing under collaborative and privacyconstrained settings. CT methods are complementary: their backbone-agnostic encoders can be composed as local models within DG-CoLearn, as demonstrated in Section 5.2. From a systems perspective, BLAD and ESDG [8, 2] reduce communication by grouping snapshots onto single GPUs, but this assumes batch access to multiple snapshots and scales poorly as individual snapshots grow large, limiting applicability to streaming or rapidly evolving graphs. Collaborative and Federated Graph Learning. Early federated graph methods such as FedSage, FedEgo, and FedGCN [36, 37, 33] primarily focus on static graphs, and either assume disjoint client graphs or require explicit sharing of structural information. FedDGL [32] extends FL to dynamic graphs via knowledge distillation but inherits the disjoint-subgraph assumption, ignoring cross-client edges entirely. Methods that do address cross-client dependencies, FedSage+ [36] via missing-neighbour generation, LLCG [26] via server-side global correction, recover structural signal but rely on expensive generative reconstruction or repeated full-graph processing, neither of which scales to dynamic graphs with frequent updates. Privacy in Federated Graph Learning. Privacy preservation in FL has primarily been studied under untrusted-server assumptions, with secure aggregation and differential privacy aimed at preventing the server from recovering individual updates. However, gradient inversion attacks [1, 39, 12] have shown that training data can still be reconstructed from shared gradients, and membership inference attacks have been extended to graph neural networks [7, 11, 21, 30], where node or edge membership can be inferred from model outputs or embeddings. While differentially private federated graph learning frameworks [10] introduce noise or restrict information sharing to protect client data, they do not explicitly consider cross-client structural leakage in partitioned graph settings. In contrast, DG-CoLearn considers a different privacy axis, preventing client-to-client structural inference under a trusted coordinator, which is practically motivated by systems where a central operator necessarily maintains global topology and the primary risk lies between clients rather than between clients and server. Graph Incremental Learning. Recent studies distinguishes graph incremental learning (GIL) from dynamic graph learning (DGL) [28], and we maintain this distinction. GIL methods such as DyGRAIN, TWP, and ER-GNN [13, 18, 38] target catastrophic forgetting as new graph data arrives, whereas DGL, the focus of this work, aims to capture temporal dynamics. Although mitigating catastrophic forgetting is not our central objective, we additionally evaluated its ability to retain historical knowledge in Appendix G.

3

Problem Formulation

3.1

Dynamic Graphs

We consider a dynamic graph dataset D = {Gt }Tt=1 , consisting a sequence of temporal graph snapshots. At each timestamp t, the snapshot is defined as Gt = (Vt , Et , Xt , Yt ), where Vt and Et are the set of nodes and edges respectively, Xt ∈ R|Vt |×d represents the raw node features, and Yt is the available node labels for the learning task. The graph topology is encoded by an adjacency matrix Adjt ∈ {0, 1}|Vt |×|Vt | . Following the temporal graph formulation in [20], we define the delta graph ∆G(t,t+1) = (∆V(t,t+1) , ∆E(t,t+1) ), where ∆V(t,t+1) contains newly arrived nodes between timestamps t and t + 1, and ∆E(t,t+1) contains both new edges connecting existing nodes, and edges connecting two new vertices. 3.2

Collaborative Intra-graph learning

We study a collaborative intra-graph learning paradigm, where a global graph at each timestamp is maintained by a central server and partitioned into multiple subgraphs, which are distributed to a set of clients. Each client holds one subgraph and performs local GNN training. 3

At each timestamp t, the server partitions the global node set Vt into M disjoint client subgraphs: M [ (m) (i) (j) Vt = Vt , Vt ∩ Vt = ∅ for i ̸= j, m=1

with corresponding subgraphs (m)

Gt

(m)

= Vt

(m)

, Et

(m)

, Xt

(m)

, Yt

,

(m) (m) where Et = {(u, v) ∈ Et | u, v ∈ Vt } contains only the edges for which both endpoints lie in (m) (m) (m) Vt . The corresponding local adjacency matrix held by client m is Adjt (m) ∈ {0, 1}|Vt |×|Vt | ,

which encodes only intra-client edges. To enable message passing across partitions, a central coordinator maintains global structural information and facilitates controlled information exchange between clients. The learning objective is to jointly optimize local models across clients while preserving performance comparable to centralized training under computational and communication constraints. 3.3

Privacy Model and Threat Assumptions

DG-CoLearn operates under a client-oblivious trusted-server threat model. The server holds the full adjacency matrix Adjt and orchestrates partitioning, model aggregation, and cross-client node embedding exchange. It is assumed to execute the protocol faithfully and does not attempt to infer private client data beyond what is required for aggregation. Each client m observes only its local (m) subgraph Gt , the aggregated global model parameters, and server-computed embedding corrections (k) (j) for its border nodes. Crucially, any cross-client edges connecting Vt to Vt (j ̸= k) are known exclusively to the server. Clients are unaware of whether their local nodes connect to nodes owned by other clients, and must train using incomplete neighbourhood information. The privacy goal is client-to-client structural privacy: no client should be able to reconstruct or infer the subgraph structure, node features, or labels of any other client from the information it receives. Appendix H provides a formal analysis showing that the server-computed embedding corrections received by each client are provably insufficient for reconstructing another client’s private subgraph, even under multi-client collusion. This regime differs from classical federated learning, which targets an untrusted server via secure aggregation or differential privacy, techniques that do not directly prevent inference of cross-client graph structure under partitioned graphs with shared coordination.

4

The DG-CoLearn Framework

At each timestamp t, DG-CoLearn executes a three-stage pipeline: (i) Incremental graph partitioning (§4.1): the server applies CoLearnPartition to assign newly arriving nodes while preserving historical partitions, minimizing cross-client edges and maintaining balanced, learning-effective subgraphs. (ii) Lightweight local training (§4.2): each client update its GNN model using only a k-hop subgraph induced by locally affected nodes, while a temporal module preserves historical representations without reprocessing unchanged regions. (iii) Server-mediated node knowledge aggregation (§4.3): clients submit updated local models together with embeddings of boundary nodes involved in cross-client dependencies; the server incrementally reconstructs exact multi-hop node embeddings using global topology without exposing cross-client connectivity. By explicitly exploiting temporal locality and structural sparsity of updates, DG-CoLearn enables scalable, privacy-preserving collaborative learning on evolving graphs, avoiding full-snapshot retraining and expensive generative reconstruction while achieving centralized-learning accuracy. 4.1

CoLearnPartition: Duo-Stage Temporal Graph Partitioning Algorithm

To support scalable collaborative learning on evolving graphs, DG-CoLearn requires a partitioning algorithm that (i) operates incrementally over temporal snapshots, (ii) preserves partition consistency 4

Figure 1: Architecture of DG-CoLearn. The key four steps are labelled on the processing of snapshot t (bottom dotted box).

over time, and (iii) facilitates effective downstream GNN training under client-to-client privacy constraints. Existing temporal partitioning methods [20] primarily optimize structural objectives such as minimizing edge cuts or balancing partition size, but do not explicitly account for learning effectiveness or computation cost in graph partitioning. We therefore propose CoLearnPartition, a lightweight duo-stage incremental vertex partitioning algorithm tailored for collaborative DGL. CoLearnPartition assigns newly arriving nodes while keeping historical assignments fixed, avoiding costly repartitioning at each timestamp. It jointly optimizes three objectives: (1) minimizing cross-client edges, to reduce embedding exchange overhead; (2) balancing partition edge volume, to ensure comparable computational load across clients; and (3) balancing node label distributions, to promote stable and generalizable collaborative training. CoLearnPartition enforces these objectives through a two-stage decision process: a primary stage that applies a hard constraint on a dominant objective, followed by a secondary refinement stage that softly optimizes the remaining criteria. We empirically evaluate different stage configurations in Appendix B and find that prioritizing cross-client edge minimization in the primary stage, followed by the other two objectives in the secondary stage, yields the most effective trade-off between communication efficiency and learning performance. This design enables efficient partition updates that directly align partition structure with collaborative learning efficiency. At each snapshot t, CoLearnPartition searches for a valid partition from snapshot t − 1, and incrementally assign newly arrived nodes ∆V(t−1,t) based on their 1-hop and 2-hop neighbourhood to the existing partition. Otherwise, the graph will be partitioned according to Appendix A. Note that the border nodes, defined as nodes with neighbours in other subgraphs after the initial partition, play a key role in cross-partition interactions. Unlike snapshot partitioning [8], which segments the graph by time and creates redundant copies, our vertex partitioning preserves enables fine-grained, communication-efficient parallelism and better supports node-centric collaborative learning tasks. The detailed explanation of CoLearnPartition is provided in Appendix A.

4.2

Lightweight Dynamic GNN Learning

As discussed earlier in Section 2, our design is inspired by ROLAND, which models temporal dependencies by updating node states across snapshots using a GRU. This formulation implies that historical node states are already preserved in the recurrent state. We therefore observe that, especially when graph updates are sparse, it is unnecessary to retrain over the entire snapshot. DG-CoLearn enables each client to perform incremental local training, where the learning is restricted to subgraphs induced by affected nodes while integrating historical representations for unchanged regions. Figure 1 illustrates the architecture which proceeds in four steps: 5

1. k-hop subgraph expansion. Given the delta graph ∆G(t−1,t) , the client extracts the k-hop induced subgraph [ gtk = Gt [V(gtk )], V(gtk ) = NGk t (v), (1) v∈∆V(t−1,t)

where k matches the number of GNN layers and NGk t (v) denotes the k-hop neighbourhood of node v in Gt . This restricts computation to nodes whose representations can be affected by the update. 2. GNN layer. gtk is passed through the l-th GNN layer. For each node v ∈ gtk , the layer computes  n o (l−1) k,(l) Ht,v = σ W (l) · AGG(l Ht,u | u ∈ N (v) ∪ {v} (2) S k,(l) k,(l) and Ht = v∈gk Ht,v collects the resulting embeddings. t

3. GRU temporal update. A GRU captures the temporal relationships between consecutive graph updates by fusing the new layer-l embeddings with the previous snapshot’s hidden states for the nodes in gtk :   b k,(l) = GRU Hk,(l) , Hk,(l) H (3) t t t−1 4. Assembling the full hidden states. Since nodes outside gtk are unchanged, their hidden b k,(l) = H b (l) \ H b k,(l) ) are directly reused: states from t − 1 (i.e. H t−1

t−1

t−1

b k,(l) b k,(l) ∪ H b (l) = H H t t t−1

(4)

These steps are repeated k times until subgraph gtk has been processed through all k GNN layers. Full per-step equations and aggregation details are provided in Appendix C. DG-CoLearn improves upon centralized baselines by enabling localized updates and reducing computation via decentralized, k-hop subgraph processing. Compared to knowledge distillation methods such as DyGRAIN [13], which rely on full-graph access to mitigate forgetting, DG-CoLearn preserves historical information through node state reuse and incrementally learns newly updated graph elements. As a result, DG-CoLearn is a better suit for real-world, resource-constrained collaborative settings. 4.3

Exchanging Node Knowledge across Clients

In collaborative intra-graph learning, clients train GNNs on disjoint subgraphs and are unaware of cross-client dependencies. While this preserves privacy, it prevents clients from accurately incorporating information from cross-client neighbours, leading to incomplete message passing. DGCoLearn addresses this challenge through a server-mediated node knowledge exchange mechanism that reconstructs exact embeddings of affected nodes without revealing cross-client edges to clients. Figure 2 illustrates a cross-client edge connecting node 3 (in client X) bi as the set of nodes that are the and node 4 (in client Y). We denote N cross-client neighbours of node i. Crucially, DG-CoLearn performs node embedding exchange incrementally. At snapshot t, only nodes in the k-hop induced subgraph gtk defined in Equation 1 require embedding correction. This incremental exchange strategy reduces communication complexity from O(|Vt |) per snapshot Figure 2: Example graph to O(|∆V(t−1,t) |), while preserving message passing accuracy. with a cross-client edge b3 = {4} (3, 4), where N FedGCN [33] reconstructs cross-client information by summing locally b4 = {3} aggregation node features across clients. While being communication and N efficient, this approach approximates message passing and overlooks interactions among cross-client neighbours, leading to inaccurate multihop embeddings. 6

Figure 3: The Node Embedding Exchange Scheme. Figure on the left shows the four stages of the scheme, and the figure on the right shows the construction of a message from the server to a client. 4.3.1

Computing exact node embeddings k,(l)

From Equation 2, we denote Ht,v

as node v’s embedding after the lth GNN layer.

As discussed in FedGCN [33], communicating with (L > 2)-hop neighbours is infeasible because of potential data leakage and the coverage of the entire graph, incurring prohibitive communication and computation costs. Thus, we restrict ourselves to 2-hop communication as well and derive the method for computing the 1-hop and 2-hop node embeddings. The server, aware of the cross-client edges, computes and redistributes exact 1-hop and 2-hop embeddings for each node via the following theorem. The complete proof of the theorem will be provided in Appendix D.1. ∗,(1)

Theorem 4.1. The exact 1-hop global node embeddings for node i, denoted by Ht computed by: X (0) ∗,(1) k,(1) Ht,i = Ht,i + Ht,j

(i), can be (5)

bi j∈N ∗,(2)

and the 2-hop global node embeddings Ht (i) of node i can be computed by: X X (0) ∗,(2) k,(2) k,(1) (0) (0)
Ht,i = Ht,i + Ht,j + Ht,j + Ht,i + Ht,q , bi j∈N

(6)

bj q∈N

(0)

where Ht,v as its initial node feature of node v. Using the derived formulae, we proposed to have clients share their 1-hop and 2-hop node embeddings to the server to obtain the exact node embeddings for their own cross-client nodes. Figure 3a illustrates the four stages of the proposed scheme. The reconstructed embeddings are then privately returned to the original client as a message structured in Figure 3b. Specifically, the formulae encode the additional node embeddings required from other clients for each cross-client node i in addition to ∗,(1) k,(1) ∗,(2) k,(2) their locally learnt embeddings (i.e. Ht,i − Ht,i and Ht,i − Ht,i ). P (0) Concretely, the additional embedding needed to obtain the exact embedding for node i is j∈Nbi Ht,j , which the server computes by summing the 0-hop node embeddings of node i’s cross-client neighk,(1) bours. The 2-hop correction is constructed analogously by combining the 1-hop embeddings Ht,j bi with the relevant 0-hop features (full derivation in Appendix submitted by clients holding j ∈ N D.1). Because clients only receive aggregated sums returned to them by the server, no client observes another client’s raw embeddings, features, or neighbourhood identities, a property we formulated in Appendix H. To ensure training stability and enhance performance, we explore several synchronisation schedules for when the embedding exchange occurs. Exchanging only once in the last epoch after the first communication round provides a strong accuracy-privacy trade-off, with results summarized in Appendix D.2. 7

Table 1: DGL Models performances on Link Prediction Tasks Models

OTC

MRR UCI

AS-733

OTC

MAP UCI

AS-733

OTC

Accuracy UCI AS-733

GCRN-Baseline GCRN-GRU GCRN-LSTM EvolveGCN-H EvolveGCN-O ROLAND Ours

0.2000 O.O.M O.O.M 0.1241 0.0850 0.1940 0.7830

0.0783 0.0800 0.0830 0.0995 0.0094 0.1120 0.6922

O.O.M O.O.M O.O.M O.O.M O.O.M 0.3390 0.8186

0.9183 O.O.M O.O.M 0.6692 0.5032 0.8752 0.9353

0.6837 0.7343 0.7891 0.6715 0.5230 0.6967 0.8544

O.O.M O.O.M O.O.M O.O.M O.O.M 0.9546 0.9566

0.8337 O.O.M O.O.M 0.5048 0.5056 0.8660 0.9877

0.7931 0.7610 0.8112 0.5985 0.4991 0.8183 0.8372

O.O.M O.O.M O.O.M O.O.M O.O.M 0.8748 0.9083

Improvement

292%

518%

142%

1.85%

8.27%

0.210%

14.1%

2.31%

3.83%

Table 2: FL Graph Learning Models F1 performances on Node Classification Tasks DBLP5

DBLP3

Reddit

0.5188 0.5381 0.5439 0.5648 0.5836

0.2033 0.2353 0.2506 0.2487 0.2733

Baseline Models D-FedGNN FedAvgDyn FedSageDyn FedProtoDyn FedDGL

0.6787 0.6733 0.6856 0.7099 0.7243

Graph Partitioning Algorithm with DG-CoLearn Label-skew Louvain Metis

0.6852 0.7079 0.7131

0.6368 0.6396 0.5966

0.2620 0.2618 0.2709

Ours

0.7269

0.6616

0.2834

Improvement to best

0.359%

13.36%

3.70%

5

Experiments

5.1

Experimental Settings

We evaluate DG-CoLearn on two tasks: link prediction (via dot product of learned embeddings) and node classification, across six datasets spanning social networks (UCI, OTC), citation graphs (DBLP3, DBLP5), online communities (Reddit), and a large scale communication network (AS-733). To assess scalability beyond standard benchmarks, we additionally evaluate on two large-scale temporal graphs from the Temporal Graph Benchmarks [9]: tgbl-coin (link prediction on cryptocurrency transactions, 22M edges) and tgbn-reddit (node classification on user-subreddit interactions, 27M edges). For link prediction we report MRR and MAP following ROLAND [34]; for node classification we report F1 following FedDGL [32]. Baselines span centralized DGL (link prediction) and collaborative DGL (node classification); CoLearnPartition is additionally compared against Label-skew, Louvain, and Metis. Full experimental details are in Appendix E. 5.2

Experimental Results

Overall Performance. Table 1 and 2 show that DG-CoLearn outperforms all baselines across both tasks and all datasets, achieving up to 518% MRR and 8.27% MAP improvement on link prediction, and up to 13.36% F1 improvement on node classification. The gains over centralised DGL methods (Table 1) confirm that collaborative learning, when combined with our incremental learning, captures localized temporal patterns that single-machine approaches miss; the gains over federated baselines (Table 2) confirm that explicitly modelling cross-client edges via server-mediated exchange materially improves accuracy over disjoint-graph methods such as FedDGL. Evaluating graph partitioning algorithms. The bottom of Table 2 shows CoLearnPartition yields up to 4.61% F1 improvement to the strongest baseline by producing subgraphs better suited for 8

Figure 4: Partition + embedding exchange time Figure 5: Per-snapshot embedding exchange time: incremental vs. full-graph. across partitioning methods.

Table 3: Average Test MAP on Cross-Client Edges across Node Embedding Exchange Schemes Exchange Scheme

OTC

UCI

AS-733

No exchange Incremental FedGCN DG-CoLearn

0.8540 0.8955 1.000

0.7637 0.8493 0.9276

0.8192 0.9055 0.9275

Improvement to best

11.7%

9.22%

2.43%

downstream learning. Figure 4 further shows it significantly reduces node embedding exchange time by up to 2.19× compared to the best algorithm Metis, a direct consequence of its cut-edge minimization objective, which dominates communication cost. Ablation study. We isolate the contributions of (i) node embedding exchange and (ii) incremental processing. For (i), we evaluate link prediction restricted to cross-client node pairs against two baselines: no exchange and Incremental FedGCN [33], adapted to DGL by replacing input features with per-client feature aggregations (Appendix E). Table 3 shows DG-CoLearn improves cross-client MAP by up to 11.7% over the strongest baseline, since FedGCN’s feature replacement breaks higherorder message passing while our scheme preserves exact multi-hop embeddings. For (ii), Figure 5 shows our incremental embedding exchange achieves up to 6.3× speedup in computation and 5.9× in communication over full-graph exchange across all six datasets. Backbone compatibility and large-scale scalability. We evaluate DG-CoLearn on two large-scale benchmarks: tgbl-coin and tgbn-reddit (Results in Appendix E.7). On tgbl-coin , DG-CoLearn adapts CT method DyGFormer and achieves a 33.8× training speedup, 51.6× partitioning speedup, and 27.4× reduction in node embedding exchange overhead, while the full-graph retraining baseline fails to complete under the same setting. On tgbn-reddit, DG-CoLearn delivers a 2.19× snapshot processing speedup and a 76.8% reduction in cut-edge ratio compared to FedDGL, while also improving F1 by 11.98%, a gain we attribute to recovering cross-client structural signal that FedDGL’s disjointsubgraph assumption discards. These results show that DG-CoLearn remains effective in regimes where standard distributed baselines do not complete at all.

6

Conclusion

We introduced DG-CoLearn, a collaborative learning framework for dynamic graphs built around incremental snapshot processing. By systematically restricting computation to updated graph regions, DG-CoLearn applies this principle across partitioning, local training, and cross-client embedding reconstruction. We additionally formalise the client-oblivious privacy regime, practically motivated by systems where a trusted coordinator necessarily maintains global topology and the primary risk lies between clients, and prove that our server-mediated exchange mechanism is provably insufficient for cross-client subgraph reconstruction even under collusion. Extensive experiments on node classification and link prediction tasks demonstrate that DG-CoLearn achieves significant efficiency gains while maintaining or improving predictive performance. These results suggest that the apparent tension between client-to-client privacy and accuracy in collaborative DGL is not fundamental, but an artifact of treating each challenge independently rather than designing for them jointly. 9

References [1] V. Carletti, P. Foggia, C. Mazzocca, G. Parrella, and M. Vento. {SoK}: Gradient inversion attacks in federated learning. In 34th USENIX Security Symposium (USENIX Security 25), pages 6439–6459, 2025. [2] V. T. Chakaravarthy, S. S. Pandian, S. Raje, Y. Sabharwal, T. Suzumura, and S. Ubaru. Efficient scaling of dynamic graph neural networks. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC ’21, 2021. [3] A. Chaudhry, M. Rohrbach, M. Elhoseiny, T. Ajanthan, P. Dokania, P. Torr, and M. Ranzato. Continual learning with tiny episodic memories. In Workshop on Multi-Task and Lifelong Reinforcement Learning, 2019. [4] F. Chen, P. Li, T. Miyazaki, and C. Wu. Fedgraph: Federated graph learning with intelligent sampling. IEEE Transactions on Parallel and Distributed Systems, 33(8):1775–1786, 2021. [5] Z. Chen, K. Liang, L. Yuan, W. Zhang, and Z. Yang. Recent advances in efficient dynamic graph processing. Applied Sciences, 15(11):6003, 2025. [6] C. Dai, Q. Tang, and H. Ding. Tgat: temporal graph attention network for blockchain phishing scams detection. In 2024 International Conference on Computer, Information and Telecommunication Systems (CITS), pages 1–7. IEEE, 2024. [7] J. Dai and Y. Lu. Graph-level label-only membership inference attack against graph neural networks. Applied Sciences, 15(9):5086, 2025. [8] K. Fu, Q. Chen, Y. Yang, J. Shi, C. Li, and M. Guo. Blad: Adaptive load balanced scheduling and operator overlap pipeline for accelerating the dynamic gnn training. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC ’23, 2023. [9] J. Gastinger, S. Huang, M. Galkin, E. Loghmani, A. Parviz, F. Poursafaei, J. Danovitch, E. Rossi, I. Koutis, H. Stuckenschmidt, R. Rabbany, and G. Rabusseau. Tgb 2.0: A benchmark for learning on temporal knowledge graphs and heterogeneous graphs. Advances in Neural Information Processing Systems, 2024. [10] F. Gauthier, V. C. Gogineni, S. Werner, Y.-F. Huang, and A. Kuh. Personalized graph federated learning with differential privacy. IEEE Transactions on Signal and Information Processing over Networks, 9:736–749, 2023. [11] F. Guan, T. Zhu, H. Tong, and W. Zhou. Attention-based membership inference attacks on graph neural network through topological features. IEEE Transactions on Dependable and Secure Computing, 2025. [12] Y. Hu, H. Ren, C. Hu, Y. Li, J. Deng, and X. Xie. Gradients stand-in for defending deep leakage in federated learning. In 2024 International Conference on Computing in Natural Sciences, Biomedicine and Engineering (COMCONF), pages 53–64. IEEE, 2024. [13] S. Kim, S. Yun, and J. Kang. Dygrain: An incremental learning framework for dynamic graphs. In IJCAI, pages 3157–3163, 2022. [14] S. Kumar, W. L. Hamilton, J. Leskovec, and D. Jurafsky. Community interaction and conflict on the web. WWW ’18, page 933–943, 2018. [15] S. Kumar, B. Hooi, D. Makhija, M. Kumar, C. Faloutsos, and V. Subrahmanian. Rev2: Fraudulent user prediction in rating platforms. In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, page 333–341, 2018. [16] J. Leskovec, J. Kleinberg, and C. Faloutsos. Graphs over time: densification laws, shrinking diameters and possible explanations. In Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, KDD ’05, page 177–187, New York, NY, USA, 2005. Association for Computing Machinery. [17] H. Liu, P. Xiong, T. Zhu, and P. S. Yu. A survey on machine unlearning: Techniques and new emerged privacy risks. Journal of Information Security and Applications, 90:104010, 2025. [18] H. Liu, Y. Yang, and X. Wang. Overcoming catastrophic forgetting in graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 8653–8661, 2021. [19] Y. Liu, Y. Zhang, P. He, and S. Fang. Fedgnnldp: Federated graph neural network with locally differential privacy. Computers & Security, page 104757, 2025.

10

[20] X. Luo, Y. Luo, G. Xin, X. Gui, J. Wang, and C. Guo. Practical and high-quality partitioning algorithm for large-scale and time-evolving graphs. Knowledge-Based Systems, 227:107211, 2021. [21] I. E. Olatunji, W. Nejdl, and M. Khosla. Membership inference attack on graph neural networks. In 2021 Third IEEE International Conference on Trust, Privacy and Security in Intelligent Systems and Applications (TPS-ISA), pages 11–20. IEEE, 2021. [22] S. Pang, Y. Xue, Z. Yan, W. Huang, and J. Feng. Dynamic and multi-channel graph convolutional networks for aspect-based sentiment analysis. In Findings of the association for computational linguistics: ACL-IJCNLP 2021, pages 2627–2636, 2021. [23] P. Panzarasa, T. Opsahl, and K. M. Carley. Patterns and dynamics of users’ behavior and interaction: Network analysis of an online community. J. Am. Soc. Inf. Sci. Technol., 60(5):911–932, 2009. [24] A. Pareja, G. Domeniconi, J. Chen, T. Ma, T. Suzumura, H. Kanezashi, T. Kaler, T. Schardl, and C. Leiserson. Evolvegcn: Evolving graph convolutional networks for dynamic graphs. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 5363–5370, 2020. [25] M. Pawelczyk, J. Z. Di, Y. Lu, G. Kamath, A. Sekhari, and S. Neel. Machine unlearning fails to remove data poisoning attacks. In The Thirteenth International Conference on Learning Representations, 2026. [26] M. Ramezani, W. Cong, M. Mahdavi, M. T. Kandemir, and A. Sivasubramaniam. Learn locally, correct globally: A distributed algorithm for training graph neural networks. In 10th International Conference on Learning Representations, ICLR, 2022. [27] E. Rossi, B. Chamberlain, F. Frasca, D. Eynard, F. Monti, and M. Bronstein. Temporal graph networks for deep learning on dynamic graphs. arXiv preprint arXiv:2006.10637, 2020. [28] J. Su, D. Zou, Z. Zhang, and C. Wu. Towards robust graph incremental learning on evolving graphs. In A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 32728–32748. PMLR, 23–29 Jul 2023. [29] J. Tang, J. Zhang, L. Yao, J. Li, L. Zhang, and Z. Su. Arnetminer: extraction and mining of academic social networks. In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’08, page 990–998, 2008. [30] X. Wang and W. H. Wang. Subgraph structure membership inference attacks against graph neural networks. Proceedings on Privacy Enhancing Technologies, 2024. [31] Z. Wang, W. Kuang, Y. Xie, L. Yao, Y. Li, B. Ding, and J. Zhou. Federatedscope-gnn: Towards a unified, comprehensive and efficient package for federated graph learning. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD ’22, page 4110–4120, New York, NY, USA, 2022. Association for Computing Machinery. [32] Z. Xie, L. Likun, X. Chen, H. Yu, and Q. Huang. FedDGL: Federated dynamic graph learning for temporal evolution and data heterogeneity. In Proceedings of the 16th Asian Conference on Machine Learning, volume 260, pages 463–478, 05–08 Dec 2025. [33] Y. Yao, W. Jin, S. Ravi, and C. Joe-Wong. Fedgcn: convergence-communication tradeoffs in federated training of graph convolutional networks. Advances in neural information processing systems, 36:79748– 79760, 2023. [34] J. You, T. Du, and J. Leskovec. Roland: graph learning framework for dynamic graphs. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2358–2366, 2022. [35] L. Yu, L. Sun, B. Du, and W. Lv. Towards better dynamic graph learning: New architecture and unified library. Advances in Neural Information Processing Systems, 36:67686–67700, 2023. [36] K. ZHANG, C. Yang, X. Li, L. Sun, and S. M. Yiu. Subgraph federated learning with missing neighbor generation. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, 2021. [37] T. Zhang, C. Mai, Y. Chang, C. Chen, L. Shu, and Z. Zheng. Fedego: Privacy-preserving personalized federated graph learning with ego-graphs. ACM Trans. Knowl. Discov. Data, 18(2), Nov. 2023. [38] F. Zhou and C. Cao. Overcoming catastrophic forgetting in graph neural networks with experience replay. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 4714–4722, 2021.

11

Figure 6: Overall Procedure of CoLearnPartition splitting a graph into 2 clients. Top part illustrates the case when there is no previous partition. Bottom part illustrates the incremental partitioning process. Each node is annotated with its node label (shown in curly brackets) [39] L. Zhu, Z. Liu, and S. Han. Deep leakage from gradients. Advances in neural information processing systems, 32, 2019. [40] R. Zhu, K. Zhao, H. Yang, W. Lin, C. Zhou, B. Ai, Y. Li, and J. Zhou. Aligraph: a comprehensive graph neural network platform. Proc. VLDB Endow., 12(12):2094–2105, 2019.

A

Additional Details of CoLearnPartition

A.1

Overall Flow of CoLearnPartition

Figure 6 shows the complete procedure of CoLearnPartition, where the number of partitions depends on the size of the incoming graph. Therefore, as the graph size grows, the number of partitions required will also increase, and the previous partitioning will no longer be valid. However, if the number of partitions in the previous snapshot is the same as the current snapshot, we can reuse the previous partition so that the existing graph elements do not need to be reprocessed.

A.2

Formulae of Scoring Function

The primary node allocation scoring function P (v, Si ) for resolving conflicts via minimum cut edges is defined as: P (v, Si ) = |N (v) ∩ Vi | where: • v is the node being allocated • Si = (Vi , Ei ) is candidate subgraph i • N (v) is the neighbour set of v • Vi is the node set of subgraph Si The allocation decision selects the subgraph S ∗ that maximizes this score: S ∗ = arg maxP (v, Si )

(7)

Si ∈G

where G is the set of candidate subgraphs. The refinement scoring function evaluates potential moves of a node v to neighbouring subgraphs based on a weighted combination of balance and label diversity metrics. For each candidate subgraph Sj ∈ G, the score is computed as: R(v, Sj ) = α · balance(v, Sj ) + (1 − α) · label_div(v, Sj )

12

where α = 0.5 balances the two objectives. The balance score balance(v, Sj ) considers: • Current subgraph sizes and overall graph balance • Synthetic edge connections (if present) • Isolation status of nodes The label diversity metric is computed as: label_div(v, Sj ) = 1 −

|{u ∈ Sj : L(u) = L(v)}| |Sj | + ϵ

(8)

where L(u) denotes the label of node u and ϵ prevents division by zero. The refinement moves v to the subgraph R∗ that maximizes: R∗ = arg max[R(v, Sj ) − R(v, S ∗ )] > τ

(9)

Sj ∈G

where τ is a minimum improvement threshold. The algorithm only moves v if the improvement exceeds both τ and any previously seen improvement during the evaluation.

A.3

Time Complexity of CoLearnPartition

CoLearnPartition employs a multi-stage strategy including graph preprocessing to partition dynamic graphs while minimising cross-client edges and preserving edge balance. We analyse its complexity step-wise: Phase 1: Preprocessing. Using breadth-first search (BFS) to visit connected components requires O(|V | + |E|) time for a graph G = (V, E). Connecting m connected components costs O(mlogm). Here, O(|V | + |E|) dominates Phase 1. Phase 2: Primary Stage of Conflict Resolving. Computing k furthest nodes via BFS requires O(k(|V | + |E|)). Resolving the number of cut edges involves identifying neighbours of each conflicting node and counting subgraph interaction. Consider a cross-client node v, we iterate through all dv neighbours, where dv is the degree of node v. For each neighbour, we use constant time to lookup and record the partition it is in. Afterwards, we find the partition with the highest count using O(k) time where k is the number of subgraphs. Therefore, the case complexity for one conflicting node is O(k + dv ). For c conflicting nodes, the time complexity becomes O(c · (k + dv )). The cost is dominated by neighbour iteration O(dv ), in sparse graphs such as social networks, we have dv ≪ |V |. Phase 3: Refinement Stage for conflicting and border nodes. This stage evaluates label distribution and edge balance to reassign border nodes. In terms of node label scoring, we iterate through each subgraph’s nodes (i.e. O(|Si |)) and compare the frequencies in constant time, yielding the worst time complexity of O(|V |). For balance scoring, checking the size of each subgraph also takes O(|Si |). Therefore, Phase 3 yields a time complexity of O(|V |). Overall Complexity. Combining the three phases, we have: Ttotal = O(|V | + |E|) + O (k(|V | + |E|) + dv ) + O(|V |) | {z } | {z } | {z } Preprocessing

BFS + Primary Resolve

Refinement

Overall speaking, the full procedure has a time complexity of O(|V | + |E|).

A.4

Pseudocode of CoPartition

B

Experiments on various Partitioning Stage Configurations

In terms of primary and secondary stage of conflict resolving, there are three combinations to be explored: 1. Primary: Minimize Cut Edges; Secondary: Edge Size Balance and Node Label Diversity [MinCut_First] 2. Primary: Edge Size Balance; Secondary: Minimize Cut Edges and Node Label Diversity [Balance_First] 3. Primary: Node Label Diversity; Secondary: Minimize Cut Edges and Edge Size Balance [Label_First]

13

Algorithm 1 CoLearnPartition (without existing valid partition) Require: Snapshot Gt = (Vt , Et ) 1: Select M seed nodes that are maximally distant 2: Grow provisional partitions via BFS from each seed 3: Identify conflicting nodes reached by multiple seeds 4: /* Primary stage: hard constraint */ 5: Assign conflicting nodes to minimize cross-client edges 6: Identify border nodes with neighbours in other partitions 7: /* Secondary stage: soft refinement */ 8: Refine border-node assignments to balance partition edge volume and node label distribution while limiting new edge cuts (1) (M ) 9: Return: Updated partitions {Vt , . . . , Vt }

Figure 7: Cut Edge Ratio across configurations for each dataset

To formally evaluate the impact of each configuration, we used three numerical metrics to measure each objective: To measure the impact of minimizing cut edges, we use the cut edge ratio, which is the proportion of cut edges in the graph: Number of Cut Edges Cut_Edge_Ratio = Total Number of Edges in Graph To measure the direct impact of cut edges to the graph learning pipeline, we also recorded the time of node embedding exchange. To quantify how balanced the subgraphs are, we measure the coefficient of variation (CoV), which captures the relative variation in the subgraphs’ edge counts: CoV =

Standard Deviation σ Mean µ

CoV values are usually bounded between 0 and 1, a CoV close to 0 means more consistency in the subgraph sizes (i.e. balanced subgraph size), while a high CoV means the subgraph sizes are more varied. In rare cases, CoV values can exceed 1, indicating severe imbalance. For node label diversity, we measure with shannon entropy H, which is usually used for categorical distributions. It effectively measures how evenly distributed the node labels are. Given n label classes p1 , p2 , ..., pn , shannon entropy is computed as: n X H=− pi · log2 (pi ) i=1

While the value is bounded between 0 and log2 (n), a high entropy close to log2 (n) implies a more uniform label distribution, while a lower entropy close to 0 indicates a skewed distribution. The direct impact of graph balance on graph learning can be reflected by the variance of clients’ local accuracies.

B.1

Cut Edge Ratio

Figure 7 demonstrates that MinCut_First consistently achieves the lowest cut edge ratio in all three datasets, validating its effectiveness in minimising edge cuts. In contrast, Label_First exhibits a 2.34× higher cut edge ratio, while Balance_First performs significantly worse, with ratios up to 7.75× higher than MinCut_First. This difference highlights the inherent trade-off between balanced partitions (Balance_First) and minimal edge cuts (MinCut_First), with Label_First offering an intermediate compromise.

14

Figure 8: Time taken for Graph Partition and Node Embedding Exchange across configurations for each dataset (Each bolded label value indicates the partition time, (i.e., blue bar) + total time to perform node embedding exchange, (i.e., orange bar))

Figure 9: Coefficient of Variation of training, validation and test edges across configurations (DBLP5) B.2

Time Consumption on Node Embedding Exchange

To further assess the impact of cut edges on the graph learning pipeline, we analysed the node embedding exchange time in Figure 8. The total exchange time (orange bar) comprises both communication time (red bar) and computation time (green bar). Together with the graph partition time, their exact values are annotated above each bar. The results reveal that Balance_First incurs significantly longer embedding exchange times compared MinCut_First and Label_First, directly correlating with its higher cut edges count. Notably, MinCut_First with the lowest cut, achieves the fastest exchange times. Using MinCut_First as the baseline, Balance_First requires up to 5.11× more time, while Label_First takes up to 3.0× longer, demonstrating the computational cost of excessive cross-client edges. Given node embedding exchange is a critical phase in our framework, optimizing this procedure through efficient configuration is essential. Therefore, we exclude Balance_First as a viable candidate due to its prohibitive overhead.

B.3

Coefficient of Variations (CoV)

We next analyse the impact of partition balancing for each dataset. Figures 9,10, and 11 present the coefficient of variation for training, validation, and test edge distributions for three different datasets respectively, where a perfect balance corresponds to CoV = 0. Surprisingly, MinCut_First and Label_First occasionally achieve lower CoV values than Balance_First in DBLP5 and DBLP3, suggesting that explicit balancing does not always yield the most uniform splits. Secondly, all configurations exhibit substantially higher CoV values in Reddit (i.e., higher than 1), indicating severe partition imbalance. We attribute these to fundamental graph structural properties: real-world graphs exhibit heavy-tailed degree distributions. This forces compromises, for instance, balancing partitions would require excessive edge cuts, while avoiding cuts leads to concentration in single partitions. Our results suggest this structural bias dominates even explicit balancing efforts.

B.4

Shannon Entropy

Shannon Entropy exhibits more uniform distribution if its value is close to log2 (n), where n is the number of classes of the dataset. Table 4 shows the best value for each dataset. Figure 12 reveals two key findings about label diversity. Firstly MinCut_First and Label_First achieve nearly identical entropy values, consistently approaching near-optimal entropy for each dataset. Their convergence suggests that MinCut_First indirectly preserves label diversity as effectively as primary label optimization in Label_First. In contrast, Balance_First exhibits more fluctuated and reduced entropy. This reflects inherent conflicts between its

15

Figure 10: Coefficient of Variation of training, validation and test edges across configurations (DBLP3)

Figure 11: Coefficient of Variation of training, validation and test edges across configurations (Reddit)

primary partition balancing objective and label distribution preservation, suggesting force graph splitting to achieve size equality disrupts natural communities sharing the same label.

B.5

Local Client Accuracies

We evaluate the impact of strategies on local client performances through boxplots analysis in Figure 13. The horizontal line within the box marks the median accuracy (50th percentile), providing the central tendency of clients. The box boundaries indicate the 25th (Q1) and 75th (Q3) percentiles, showing where the middle 50% of client accuracies fall. The interquartile ranges (IQR) width reflects performance consistency - narrower boxes denote more uniform client experiences. Points beyond 1.5×IQR indicates statistical outliers. These reveal edge cases where clients significantly over- or under-perform relative to the group. MinCut_First and Label_First demonstrate comparable results IQR widths, indicating similar training stability. This corresponds to the above observations, where they achieve similar cut edge ratio, CoV and Shannon Entropy. On the other hand, despite prioritizing partition balancing, Balance_First exhibits wider IQRs than MinCut_First and Label_First, with more outliers perform unusually well or poorly in Reddit dataset. This contradicts to the expectation that balanced partitions should yield more consistent client performance. Balance_First’s strict size constraints disrupt natural label communities, evidenced by lower Shannon entropy in Figure 12, creating unnatural subgraphs where clients with coherent local data overfit and disrupted data underfit. In contrast, MinCut_First and Label_First preserve graph homophily, yielding more predictable accuracies. This proves that partition balancing does not guarantee stable and consistent local client performances.

B.6

Overall Time Taken

Since MinCut_First and Label_First remain to achieve similar performance in node embedding exchange time consumption and local accuracies, we analyse their total time taken, including graph partitioning and node embedding exchange. Figure 8 shows that in all three datasets, Label_First requires 1.81× longer time to

Dataset

Number of classes n

Best Value (log2 (n))

DBLP5 5 2.32 DBLP3 3 1.58 Reddit 4 2.00 Table 4: Best Shannon Entropy value for each dataset

16

Figure 12: Shannon Entropy across configurations for each dataset

Figure 13: Local Accuracies across configurations for each dataset (The average of the CoV values across snapshots are computed and listed for reference.) complete the procedures. This is because of complex label-aware partitioning and higher cut edge ratios. In label aware partitioning, additional computation is needed to track and optimize label distribution. As Label_First yield higher cut edge ratio (2.34× higher than MinCut_First), it also increases communication overhead in node embedding exchange scheme.

B.7

Conclusion

In conclusion, MinCut_First emerges as the optimal choice, offering: • Time Efficiency: Fastest execution on partitioning and training • Reliable Performance: Tightest IQRs and better accuracies • Theoretical Alignment: Minimal edge cuts preserve graph properties is crucial for GNN training

C

Details of Lightweight Dynamic GNN Learning

C.0.1

Step 1: k-hop subgraph expansion

Consider the delta graph ∆G(t−1,t) , for a node v ∈ ∆V(t−1,t) that is updated in snapshot t, all nodes within k-hop away should also be updated. Therefore, the client first performs a k-hop subgraph expansion based on all updated nodes ∆V(t−1,t) . The parameter k is aligned with the number of layers in the local GNN. In message-passing, each layer aggregates information from immediate neighbours. Consequently, stacking k layers allows node representations to incorporate information from nodes within their k-hop neighbourhood. The k-hop neighbours of all updated nodes at time t form a subgraph, denoted as gtk . [ gtk = Gt [V(gtk )], V(gtk ) = NGk t (v) v∈∆V(t−1,t)

where NGk t (v) denotes the k-hop neighbourhood of node v in Gt .

C.0.2

Step 2: First GNN layer k,(1)

The subgraph gtk is passed through the first GNN layer, producing updated node embeddings, denoted by Ht where the superscript 1 indicates the first GNN layer.

17

,

A GNN layer updates node embedding via iterative neighbourhood aggregation. Mathematically, we write:  n o k,(1) (0) Ht,v = σ W (1) · AGG(1) Ht,u | u ∈ N (v) ∪ {v} (0)

where Ht,u = Xt,u is initial node feature of node u, AGG(1) is an aggregation function (e.g., mean, sum) at the first layer, W (1) are learnable weights, and σ is a non-linear activation function. The collection of node embeddings for all nodes v in gtk is denoted as: [ k,(1) k,(1) Ht = Ht,v v∈gtk

C.0.3

Step 3: GRU module

A GRU module captures the temporal relationships between consecutive graph updates. It takes as input the k,(1) output of the first GNN layer, Ht , along with the hidden states from the previous update for the corresponding k,(1) k b k,(1) nodes in gt , denoted as H . The GRU outputs updated hidden states, H , for the nodes in gtk . t t−1

  k,(1) k,(1) b k,(1) H = GRU Ht , Ht−1 t The GRU takes the current and previous hidden states and outputs the temporally updated states.

C.0.4

Step 4: Assembling the full hidden states

b k,(1) The updated hidden states, H , serve two purposes: (1) they are fed into the next GNN layer, and (2) they are t combined with the hidden states of nodes not in gtk to reconstruct the complete node representation for snapshot t for subsequent graph snapshot. Since nodes not in gtk implies nodes that remains unchanged from the previous snapshot, their node states remains the same and can be directly reused from snapshot t − 1. We denote the hidden states of these unaffected b k,(1) b (1) b k,(1) nodes by H t−1 = Ht−1 \ Ht−1 . b (1) b k,(1) b k,(1) H =H ∪H t−1 t t

D

Node Embedding Exchange Scheme

D.1

Proof of Theorem 4.1

We prove the above formula using the observation of the adjacency matrix of the global graph and the subgraphs to find the additional aggregation required to the submitted feature given by the cross-client neighbours. According to the formulation in Section 3, ignoring the timestamp t, we consider the global graph’s adjacency matrix Adj, where the ith row and j th column of this matrix is 1 if there exists (i, j) ∈ Et and otherwise 0. Note that the adjacency matrix includes self-loops as well. We also define Z(0) = X as the 0-hop node feature matrix. The global 1-hop feature matrix is computed by Z(1) = Adj · Z(0)

(10)

Z(2) = Adj · Z(1) = Adj · (Adj · Z(0) ) = Adj2 Z(0)

(11)

We can get the 2-hop feature matrix by

(1)

To form the global 1-hop feature vector of each node i (i.e. zi ), we start with its local 1-hop feature submitted by the client holding it. Let such client’s subgraph be denoted by s. Since Z(0) is 0-hop node feature matrix which is fixed across clients, we can discard Z(0) when comparing the global and local feature aggregations and generalize the computation of node i’s global 1-hop feature as: (0) Adji Z(0) = Adji Z(0) + c⊤ i Z (s)

implies (s)

Adji = Adji

18

+ c⊤ i

(12)

(s)

Subtracting Adji

th from Adji , c⊤ entry: i is a vector such that its j ( 0 if node j is in global graph G and subgraph s ci,j = 1 if node j is in global graph G but not in subgraph s

In other words, the non-zero entries in ci correspond to the cross-client neighbours of node i (i.e. N̂i ). This implies the exact 1-hop global node embeddings for node i is the sum of the 1-hop feature of node i (derived (s) from Adji ) and the 0-hop features of all nodes j ∈ N̂i (derived from ci ): ∗,(1)

Hi

k,(1)

= Hi

X

+

(0)

Hj

j∈N̂i

proving the first Equation of computing 1-hop node embedding in the main text. We now proceed to the 2-hop case by considering the cross-client neighbours N̂i . By equating Adj2i and (s) (Adji )2 , we obtain the additional nodes and their values needed to compute the exact 2-hop global node embedding for node i. (s) Adj2i = (Adji )2 + d⊤ (13) i To compute the values of d⊤ i , we rearrange Equation 13 and substitute Equation 12 to the equation: Adj2i = (Adji )2 + d⊤ i (s)

(s)

Adji · Adj = Adji

· Adj(s) + d⊤ i

d⊤ i = Adji · Adj − Adji

(s)

(s)

= (Adji

(s)

= Adji

· Adj(s)

+ c⊤ i ) · Adj − Adji

(s)

· Adj(s)

· Adj + c⊤ i · Adj − Adji

(s)

· Adj(s)

= Adji (Adj − Adj(s) ) + c⊤ i · Adj (s)

(s)

which yields two terms Adji (Adj − Adj(s) ) and c⊤ i · Adj. (s)

Consider the first term Adji (Adj − Adj(s) ). (s)

(Adj − Adj(s) ) implies the set of nodes that are not in subgraph s, while Adji,j = 0 for all j not in subgraph s, we get a single row vector filled with zeros. Consider the second term c⊤ i · Adj. From the above proof, we know that c⊤ i records the cross-client neighbours of node i and Adjj is the 1-hop neighbour of node j, including itself, in the global graph. Multiplying c⊤ i by Adj gives a row vector m such that each entry mu in m implies the number of times node u has been visited by any cross-client neighbours j ∈ N̂i . ⊤ Combining the two terms, d⊤ i is simply ci · Adj where it reveals nodes that are reachable in 2 hops from node i via cross-client edges only.

We expand d⊤ i to obtain the corresponding node embeddings needed to complete the 2-hop neighbourhood of node i. Firstly, the cross-client neighbours j ∈ N̂i provide their local 1-hop node embeddings (i.e. P k,(1) ) which are unreachable from node i locally. Next, each 1-hop cross-client neighbour should visit j∈N̂i Hj P (0) (0) node i once in a global graph, vice versa. To record this interaction, we include j∈N̂i (Hj + Hi ). Finally, if there exist 2-hop cross-client neighbours, meaning the 1-hop cross-client neighbours of j ∈ N̂i , it is also P (0) indirectly visited by all cross-client neighbours j. Therefore, we include q∈N̂j Hq . (2)

As a result, the node embeddings needed to complete the 2-hop neighbourhood of node i in addition to Hi X X (0) k,(1) (0) (0) (Hj + Hj + Hi ) + Hq j∈N̂i

are:

q∈N̂j

proving the second equation in the main text.

D.2

Experiments on various Embedding Synchronisation Schedules

Frequent exchange of embeddings can incur significant communication overhead. To investigate the trade-off between performance and communication efficiency, we evaluate four embedding exchange strategies: 1)

19

Table 5: F1 Score and Total Communication Time on Node Classification Tasks with varying Node Embedding Exchange Strategies Node Embedding Exchange Strategies

DBLP5

F1 DBLP3

Reddit

Total Communication Time (s) DBLP5 DBLP3 Reddit

After first epoch, all rounds After last epoch, all rounds After last epoch, first round After last epoch, mid round

0.7215 0.7273 0.7269 0.7167

0.6558 0.6595 0.6616 0.6600

0.2654 0.2703 0.2784 0.2753

4.4994 4.5242 0.4309 0.4410

Parameters

DBLP5

DBLP3

1.4910 1.5013 0.1446 0.1429

221.0935 221.5287 22.5554 22.1005

Reddit

N 1 1 1 Cut_Edge_Ratio 0.0006 0.0006 0.036 |E| 42K 24K 244K T 8 8 8 D 100 100 20 400 400 80 Dbytes Table 6: Parameter values for each dataset

Exchanging after the first local epoch in every communication round; 2) Exchanging after the last local epoch in every communication round; 3) Exchanging after the last local epoch only in the first communication round; 4) Exchanging after the last local epoch at the midpoint of all the communication rounds. We conduct experiments on the above four options to measure their model performance (F1) and total communication time during node embedding exchange in Table 5. Experimental results demonstrate that the most effective strategy is Option 3, where embeddings are exchanged only once, after the last local epoch for the first communication round, achieving a favourable balance between performance and communication cost. Comparing with Option 1 and 2, Option 3 achieves F1 scores either comparable to (DBLP5: ∆ = -0.0004) or superior than (DBLP3: +0.21%, Reddit: +3.0% to next best) the first two options, while reducing communication time by 10.4× (DBLP5) to 9.8× (Reddit). This demonstrates that exchanging solely in the first round is sufficient to maintain performance while optimizing efficiency. In terms of exchanging in a single round, Option 3 consistently outperforms Option 4 across all datasets, with improvements ranging from 0.2% (DBLP3) to 1.4% (DBLP5). Because of the low baseline performance in Reddit, even small gains in F1 are significant (1.1% gain in F1). Since both strategies exchange for a single round, they also share comparable communication time (∆ ≤ 2.0%). This suggests that early exchanges in the first round better preserve graph structure for model learning. Thus Option 3 is strictly preferable for balancing performance and overhead. In conclusion, Option 3 achieves the minimum necessary alignment to stabilize learning without repeated overhead.

D.3

Communication Cost of Node Embedding Exchange

We formalise the communication cost C for node embedding exchanges as: C = N · (Cut_Edge_Ratio · |E| · Dbytes ) + T · L where • N is the number of exchange rounds • Cut_Edge_Ratio is the average cut edge ratio across snapshots • |E| is the total number of edges in the dataset • Dbytes is the node embedding dimension in bytes (dimension D × 4 for float32) • T is the number of snapshots • L is the fixed latency per round While we picked Option 3 as the node embedding exchange strategy and MinCut_First as the graph partitioning configuration, we yield the following statistic in Table 6. (Here we set L ≈ 0.1s)

20

DBLP5

DBLP3

Reddit

C 10.08KB + 0.8s 5.76KB + 0.8s 702.72KB + 0.8s Table 7: Communication Cost C of Node Embedding Exchange for each dataset

Therefore, the calculation of communication cost C for each dataset is shown in Table 7. For DBLP5 and DBLP3, costs remain minimal, aligning with their minimal cut edges and effective MinCut_First partitioning (≤ 0.01 cut edge ratios). In contract, Reddit incurs 702.72KB of traffic, 70x higher than DBLP5, despite its lower cut edge ratio. This arises from Reddit’s massive edge count (≈ 244K edges), where even a small ratio yields 8788 absolute cuts. The observed 112x longer exchange time (56s vs. 0.5s) further reflects this network protocol overhead.

E

Experiment Details

E.1

Details of Learning Tasks

(1) Link prediction aims to predict future edges based on existing node and edge information. After learning node embeddings from both current and historical graph structures, the likelihood of an edge (u, v) is obtained by computing the dot product of the embeddings of nodes u and v. Following standard practice [34], we evaluate the prediction model using Mean Reciprocal Rank (MRR) and Mean Average Precision (MAP), supplemented by test average for robustness. MRR quantifies how highly the first correct link is ranked for each query node, crucial for applications such as recommender system where users rely on the top-ranked results. MAP, in contrast, assesses the ranking quality of all correct links, reflecting overall prediction consistency. (2) Node classification involves assigning labels to nodes based on their features and graph structure. We follow the experimental setup of FedDGL [32], which also addresses federated dynamic graph learning, and use the F1 score as the evaluation metric. Compared to accuracy, F1 gives a more nuanced view by penalising false positives and false negatives. Instead of prioritising on majority labels, F1 shows whether the model generalizes well to minority and edge-case nodes, which is crucial in real-life graphs. Additional details: For all link prediction tasks, we apply negative sampling, generating an equal number of negative edges as positive ones for each client to ensure a balanced dataset.

E.2

Temporal Evaluation Protocol

Our training pipeline follows a temporally shifted evaluation scheme, identical to the live-update evaluation in FedDGL [32]. Specifically, the global model is trained using snapshot t, validated on snapshot t + 1, and tested on snapshot t + 2. During training on each snapshot, clients do not explicitly observe cross-client edges. Such edges are only implicitly incorporated through the node embedding exchange scheme. This protocol resembles closely to real-world dynamic graph systems, where snapshots arrive frequently and models are typically trained on historical data to make predictions on future graph states.

E.3

Dataset Descriptions

We conduct experiments using six standard datasets and two large-scaled temporal benchmark datasets[9]. (1) UCI-Message (UCI) is a link prediction dataset consisting of private messages exchanged among students on an online social network system, used to study social dynamics and message flow [23]. Each edge (u, v, t) in the dataset implies user u sent a private message to user v at time t. With a total time span of 193 days, we made use of a 5-day window which results in 39 time steps. (2) Bitcoin-OTC (OTC) is a link prediction dataset representing who-trusts-whom networks of users trading on the OTC platform, where edges indicate trust relationships between users [15]. There are 138 such networks of sequential time steps. (3) DBLP3 and (4) DBLP5 are node classification datasets derived from the DBLP citation network, focusing on a subset of computer science research papers and their citation relationships [29]. Both datasets consist of 10 graph snapshots, each with an adjacency matrix, feature matrix and one-hot encoded label matrix. (5) Reddit is a node classification dataset constructed from a large social network graph on Reddit, where nodes represent users and edges indicate co-participation in discussions or shared subreddit memberships [14]. Similarly, Reddit has 10 graph snapshots with the same attributes as DBLP5 and DBLP3.

21

Dataset

# Nodes

# Edges

# Classes

Learning Task

DBLP5 DBLP3 Reddit OTC UCI AS-733

6,606 4,257 8,291 6,005 1,899 7,716

42,812 23,538 244,552 355,096 575,971 11,965,533

5 3 4 2 2 2

Node Classification Node Classification Node Classification Link Prediction Link Prediction Link Prediction

tgbl-coin tgbn-reddit

638,486 11,766

22,809,486 27,174,118

2 2

Link Prediction Node Classification

Table 8: Dataset Statistics

(6) AS-733 is a large-scaled link prediction dataset comprising 733 daily subgraphs of routers which span an interval of 785 days from November 8 1997 to January 2 2000, formed as Autonomous Systems (AS). Each AS exchanges traffic flows with some neighbours. In contrast to the existing networks mentioned, where nodes and edges only get added and not deleted over time, this dataset also exhibits deletion of nodes and edges over time [16]. (7) tgbl-coin is a cryptocurrency transaction dataset based on the Stablecoin ERC20 transactions dataset. Each node is an address and each edge represents the transfer of funds from one address to another at a time. The network starts from April 1st, 2022, and ends on November 1st, 2022, and contains transaction data of 5 stablecoins and 1 wrapped token. This duration includes the Terra Luna crash where the token lost its fixed price of 1 USD. (8) tgbn-reddit is a users and subreddits interaction network. Both users and subreddits are nodes and each edge indicates that a user posted on a subreddit at a given time. The dataset spans from 2005 to 2019. Table 8 shows the number of nodes, edges, classes and the type of learning task for each dataset.

E.4

Description of Existing Graph Partitioning Algorithms

Label-skew and Louvain are used in FedDGL [32], where Label-skew simulates non-IID data scenarios and Louvain is a community detection algorithm to group densely connected nodes. Metis is used in Aligraph [40] to partition vertices into subgraphs with balanced node counts while minimizing edge cuts. As mentioned, these existing approaches fail to handle disconnected graphs. For instance, Metis assigns all isolated nodes to one subgraph while the remaining connected components to another to minimize cut edges. This leads to an imbalanced workload across client, thereby reducing computational efficiency in distributed learning. To ensure fair comparison, we also introduce synthetic edges to connected components before employing the existing partitioning approaches.

E.5

Baseline Model and Method Descriptions

Existing dynamic graph learning models, GCRN-Baseline, GCRN-GRU, GCRN-LSTM, EvolveGCN and ROLAND, have been primarily evaluated on link prediction tasks, while collaborative graph learning models, D-FedGNN, FedAvgDyn, FedProtoDyn and FedDGL, have focused on node classification. Since DG-CoLearn supports both link prediction and node classification, we evaluate it against models from both domains accordingly. Among the collaborative learning baselines, FedAvgDyn and FedProtoDyn are adapted from EvolveGCN [24], where the local training model at each client is EvolveGCN, while the aggregation method at the server follows FedAvg and FedProto, respectively. Each result is obtained by taking an average of 3 trials of experiments.

E.6

Additional Findings from ROLAND’s performance

Table 1 reveals that while ROLAND [34] achieves high MAP (indicating broad correctness), its lower MRR suggests a ranking bias: high-degree nodes dominate top predictions, even when less relevant. This aligns with known challenges in graph-based ranking, where structural properties can overshadow semantic relevance.

E.7

Experiment Result on tgbn-reddit

The full result of large scaled temporal graph tgbn-reddit for node classification task is illustrated in Table 9, and tgbl-coin for link prediction task is reported in Table 10.

22

Table 9: Efficiency and performance on tgbn-reddit (node classification). DG-CoLearn improves both system efficiency and predictive quality. Method

Training Time (s)

Partition Time (s)

Cut Edge Ratio (%)

NE Exchange Time (s)

F1 Score

FedDGL DG-CoLearn

117.28 ± 23.31 53.56 ± 10.58

11.44 ± 4.85 3.88 ± 1.52

11.7 ± 3.69 2.72 ± 1.27

N/A 3.72 ± 1.48

0.0929 ± 0.0513 0.1040 ± 0.0468

Improvement

2.19×

2.95×

76.8% ↓

–

+11.98%

Table 10: Scalability results on tgbl-coin (link prediction). DG-CoLearn achieves substantial speedups and reduced communication overhead. ↓ Training Time (s)

↓ Partition Time (s)

↓ Cut Edge Ratio (%)

↓ NE Exchange Time (s)

Completed

Full Retrain DG-CoLearn

5126.9 ± 483.9 151.6 ± 11.7

1553.4 ± 118.5 30.09 ± 3.40

3.35 ± 0.89 2.30 ± 0.81

279.8 ± 23.05 10.22 ± 3.11

No Yes

Improvement

33.8×

51.6×

31.3% ↓

27.4×

–

Method

E.8

Compute Resources

All experiments were conducted on a single workstation equipped with an NVIDIA RTX 4090 GPU (24GB VRAM). Per-dataset training, partitioning, and node embedding exchange timings reported in Tables 4 and 10 and Figures 4–5 were measured on this hardware. The total compute across reported experimental runs was on the order of approximately 10 GPU-hours. Preliminary experiments and hyperparameter exploration during development required additional compute beyond the reported runs.

F

Details on Ablation Studies

F.1

Node Embedding Exchange Ablation

F.1.1

Baseline Selection Rationale

For the ablation study, we focus on isolating the effect of node embedding exchange under the same privacy and partitioning constraints as DG-CoLearn. Specifically, we select the following baselines: • No Node Embedding Exchange: This baseline disables any form of cross-client information sharing. Each client performs local GNN training using only intra-client edges, and the server aggregates model parameters via FedAvg without exchanging node-level representations. This setting serves as a lower bound, highlighting the impact of ignoring cross-client dependencies entirely. • Incremental FedGCN: FedGCN is a representative federated learning method that exchanges aggregated node features to approximate cross-client neighbourhood information. We select FedGCN as it is one of the few methods that explicitly addresses missing neighbours under client-oblivious privacy constraints, making it the closest comparable baseline for our embedding exchange mechanism.

F.1.2

Implementation of the Incremental FedGCN Baseline

FedGCN was originally proposed for static graphs and is not directly applicable to dynamic graph learning or DGL-style temporal processing. To enable a fair comparison, we adapt FedGCN to our experimental setting as follows. At each snapshot t, each client m computes local feature aggregations for its nodes based on its local adjacency matrix which now only includes nodes within 2-hops of all changed nodes: X (m) (m) Fi = Adji,j · xj (m)

j∈Ni (m)

where Ni

denotes the intra-client neighbours of node i, and xj is the input features of node j.

Upon receiving all feature aggregations from the clients, the server, who has access to the full graph topology, aggregates cross-clients contributions by summing feature aggregations from all relevant clients. X (m) Fi∗ = Fi m∈M

23

Figure 14: Measuring Catastrophic Forgetting across incremental learning methods

where M is the set of clients with nodes that are cross-client neighbours N̂i of node i, and within the update subgraph. The resulting Fi∗ is then used as the updated input feature for node i in the next training round. This procedure mirrors the original FedGCN aggregation logic while allowing incremental execution across snapshots. Importantly, this approach replaces original node features with aggregated features and does not preserve intermediate representations across GNN layers. As a result, higher-order message passing interactions between cross-client neighbours are not explicitly modelled.

F.1.3

Setup of Node Embedding Exchange Ablation Study

To explicitly evaluate the effectiveness of our node embedding exchange mechanism, we design a server-side evaluation task restricted to cross-client edges. This setting directly assesses how well different methods recover relational information that is not locally observable by any single client. We consider a cross-client edge prediction (CCE) task, where the objective is to predict the existence of edges connecting nodes that belong to different clients. Positive samples consist of ground-truth cross-client edges from the current snapshot. In alignment with the temporal evaluation protocol in Appendix E.2, this choice reflects a realistic inference scenario in which the server evaluates how well the model trained on snapshot t has internalised cross-client structural relationships present at the timestamp, despite such edges never being directly visible to any single client during training. These edges are extracted from the global edge set by filtering for node pairs whose endpoints belong to different clients under the fixed node-to-client assignment. Only edges satisfying this criterion are included in the CCE evaluation. Negative edges are sampled by first selecting two distinct clients uniformly at random, then sampling one node from each client, and finally rejecting pairs that correspond to existing edges. For each snapshot, we sample an equal number of negative cross-client edges as positive ones. This procedure ensures that all evaluated node pairs are cross-client while avoiding false negatives. We report the Mean Average Precision (MAP) on the constructed CCE evaluation test. This is because the primary objective of CCE prediction task is to assess the overall quality of the learned ranking over candidate cross-client edges.

F.2 F.2.1

Incremental Graph Processing Ablation Baseline Selection Rationale

To assess the efficiency gains introduced by incremental processing, we introduce an additional ablation variant termed Full-graph Node Embedding Exchange. This variant preserves the same node embedding reconstruction mechanism as DG-CoLearn, but disables incremental snapshot processing. In particular, node embedding exchange is performed for all cross-client nodes in the graph at every snapshot, rather than being restricted to updated cross-client nodes. Overall speaking, this baseline is served as a upper bound on communication and computation cost.

G

Additional Experiments – Evaluating Catastrophic Forgetting

A key challenge in incremental learning is catastrophic forgetting, where the model loses previously acquired knowledge while adapting to new data. To evaluate the robustness against this phenomenon, we adopted the same practice as DyGRAIN and use Forgetting [3] to measure the degree of catastrophic forgetting.

24

G.1

Baseline Models

Incremental graph learning methods broadly fall into three categories: replay-based methods, regularizationbased methods, and influence-based methods. Replay-based methods retrain historical data stored in a memory. These sampled past data are mixed into the current data during training to relieve catastrophic forgetting. Representative method is ER-GNN [38]. Regularisation methods penalise the change of important parameters, while the importance is typically measured by gradient distributions of the data. TWP is a recent work that quantifies importance via previous tasks and topological attention between adjacent nodes [18]. Influence-based methods focus on updating parts of the graph that are actually affected by new information. DyGRAIN [13] uses structure-aware computation to select nodes that are influenced by new edges and vulnerable nodes that might forget past knowledge. While their approach is similar to DG-CoLearn, they only consider addition of nodes and edges, ignoring the potential of element deletion.

G.2

Experimental Results

Figure 14 illustrates the Forgetting evaluation across various existing incremental learning approaches, DyGRAIN, TWP and ER-GNN. While our evaluation focuses on Reddit, this dataset is the largest node classification benchmark, which leads to the highest risk of overwriting previous knowledge as a vast amount of new graph data flows in. Therefore, it effectively tests scalability and memory efficiency of incremental methods. As the existing methods have positive Forgetting values, DG-CoLearn results in a negative value, which implies the model not only remembered the previous knowledge, but also improved its performance after learning new tasks. This is commonly regarded as forward transfer, which is a strong indicator of effective knowledge reuse. DG-CoLearn’s ability to achieve negative forgetting stems from its targeted learning of changed graph components and modular integration with prior knowledge. By isolating and training only the dynamic components, we prevent interference with unchanged components. While the previous frozen model retains 100% of the past task (zero forgetting), the combination of the two models additively enhance the model’s performance on both new and old data, effectively turning forgetting into improvement.

H

Privacy Guarantee

H.1

Privacy Model Formulation

DG-CoLearn is designed under the standard trusted-server, client-oblivious privacy model, widely used in intra-graph distributed learning (e.g., FedSage+, LLCG). Specifically: (1) The server is the source of graph data collection and hence has access to the global topology. This is practically motivated: the server harnesses the collective computing power of the clients to achieve distributed learning, which speeds up the training and potentially enables the training of larger-scale graphs compared to training all graphs on a single server. Furthermore, the server is a trusted coordinator to the clients. Under this collaborative graph learning setting, privacy concern mainly focuses on whether clients are aware of the graph data that are not allocated to them by the server. This is a standard in related literature such as FedSage+, and recent work FedGNNLDP [19]. (2) Once the server partitions the graph and distributes subgraphs to clients, each client only has access to their local subgraph and has no visibility to other client’s. In particular, no client can infer cross-client edges, other client’s raw node features, or their local topologies; Clients cannot directly communicate with other clients, and only receive their own updated embeddings which are computed by the server via a well-formulated aggregation (Equations 5–6, Theorem 4.1). Formally, we have: Proposition H.1 (Client Privacy). For client m at snapshot t, the view of the client under DG-CoLearn consists ∗,(l) (m) only of the embeddings Ht,i for i ∈ Vt (all vertices held by client m at time t). No other client’s raw features or edges are revealed.

H.2

Privacy Attack Analysis

There are three main families of recently studied attacks that can potentially leak graph information from model gradients or node embeddings. We analyse each attack and explain how these attacks cannot be directly applied to DG-CoLearn. • Membership Inference Attack (MIAs): [21] showed that GNN models leak information about member nodes they were trained on, and critically, that structural information is the major contributing

25

factor to this leakage. The adversary queries the trained model and observes posterior probabilities. The most recent work, GLO-MIA [7], pushes this further to a label-only setting where the attacker only sees prediction labels, not probability vectors. It perturbs the target graph’s features and measures prediction stability. The Structure MIA (SMIA) [30] goes beyond node membership to infer whether a set of nodes forms a particular subgraph structure (k-clique or k-hop graph) in the training graph. The adversary uses posterior classification probabilities of specific nodes through a shadow-model approach. [11] further showed that attention mechanisms combined with topological features improve node-level MIA, exploiting the graph structure that GNNs inherently encode into their predictions. However, in DG-CoLearn’s client-oblivious design, a client never sees another client’s graph data, making such querying unavailable. • Gradient Inversion Attacks (GIAs): SoK on gradient leakage [1] systematizes this threat: most GIAs presume an honest-but-curious server that passively analyses shared model gradients, while stronger attacks assume a malicious server that can craft or modify model parameters to extract more information. The DLG technique [39] reconstructs original training data by iteratively optimizing randomly initialised inputs to match shared gradients. Even when real gradients aren’t directly accessible, methods like GLAUS can approximate the gradient from leaked indices and signs, reconstructing sensitive data [12]. In GIAs, the attacker intercepts raw gradients or model parameter updates that clients share during distributed training rounds. However, in DG-CoLearn, clients only share updates directly with the server, which is designed to be trusted. Therefore, attacks originating from the server fall outside our privacy model. • Graph Unlearning Privacy Leakage: [17] pointed out that the difference between output distributions of models before and after unlearning can lead to additional information leakage of forgotten data, the prediction changes effectively expose membership information about unlearned samples. Recent work [25] also shows that even if an MIA suggests a datapoint was successfully unlearned, residual traces may remain, allowing adversaries to recover sensitive information through data poisoning vectors. In summary, these rely on comparing model states before and after data removal. However, clients do not have multiple model snapshots corresponding to pre- and post-unlearning states; the trusted server controls the model lifecycle and does not expose such state pairs to clients. Therefore, these comparison-based leakage channel required by existing unlearning attacks is therefore unavailable.

H.3 Mathematical Analysis: Inability of a Colluding Client to Reconstruct Private Subgraphs by Shared Embeddings While the above attacks do not directly transfer, there might still exist a potential that colluding clients could infer coarse structural properties of other clients via server-shared node embeddings. Below we present a rigorous analysis to show that such information is insufficient to reconstruct private subgraphs.

H.3.1

Threat Model

We consider the threat model where client m is adversarial and attempts to reconstruct the private subgraph (m′ ) (m′ ) (m′ ) (m′ ) Gt = (Vt , Et , Xt ) of another client m′ ̸= m. The server is trusted. Client m has access to: (m)

• Its own subgraph Gt

(m)

, including Adjt (m) , Xt

(m)

and Yt

.

• The additional node embeddings needed to obtain the exact 1-hop and 2-hop embeddings (given by Equations 5–6) received from the server for each of its border nodes i. We formally define these additional embeddings as: P (1) (0) – δi = j∈N ci Ht,j P P (2) k,(1) (0) (0) (0) – δt = j∈N + Ht,j + Ht,i ) + q∈N ci (Ht,j cj Ht,q respectively. • The aggregated global model parameters, which are shared across all clients.

H.3.2

Formal Analysis

Proposition H.2 (Unidentifiability of Cross-Client Neighbour Identity). Given only the 1-hop correction (1) bi . δi ∈ Rd , client m cannot determine the identify or cardinality of the cross-client neighbour set N (1)

(0) d b ci Ht,j is a sum of |Ni | feature vectors in R . j∈N (1) bi | nor the individual summands. aggregate δi but knows neither |N

Proof. The correction δi

=

P

26

Client m observes the

(1)

P (0) = j∈N ci Ht,j , the preimage set     X (0) (1) (0) (m) (1) S(δi ) = (S, {Ht,j }j∈S ) : S ⊆ Vt \ Vt , Ht,j = δi  

For the summation function δi

ci j∈N

is infinite (for continuous feature spaces) or combinatorially large (for discrete approximations). Without additional side information, the decomposition is not unique, and hence the individual node identities and features are unrecoverable. (m′ )

Proposition H.3 (Unrecoverability of Remote Graph Topology). Client m cannot infer any edge (j, j ′ ) ∈ Et that is internal to another client m′ .

Proof. We examine every component of the information available to client m and show none reveals intra-client edges of m′ . (0)

The 1-hop correction depends only on the raw node features Ht,j = Xt,j of cross-client neighbours. Raw (1)

features Xt,j are input-level attributes (independent of graph topology). Therefore, δi contains no information (m′ ) about edges within Gt . P k,(1) k,(1) The 2-hop correction contains the term j∈N is the 1-hop embedding of node j ci Ht,j , where Ht,j ′ computed locally computed by client m :  n o ′ k,(1) (0) Ht,j = σ W (1) · AGG(1) Ht,u | u ∈ N (m ) (j) ∪ {j} from section C.0.2. (m′ )

This embedding encodes the aggregated neighbourhood of j within Gt . However, client m receives only the P k,(1) k,(1) sum j∈N , not individual Ht,j vectors. We now show this sum is insufficient to recover the local ci Ht,j adjacency of any node j. k,(1)

Sub-claim 2a (Aggregation irreversibility). Even if client m could isolate a single Ht,j , it cannot recover ′

N (m ) (j). When AGG(1) is mean aggregation: AGG(1) = (0)

1

X

|N (m′ ) (j)| + 1

k,(1)

Recovering {Ht,u }u∈N (m′ ) (j) from Ht,j sum. This is:

(0)

Ht,u

(14)

′

u∈N (m ) (j)∪{j}

requires inverting σ ◦ W (1) and then decomposing the resulting

• Non-invertible when σ is ReLU, since information is destroyed for negative pre-activations. ′

• Under-determined even if σ and W (1) were invertible: the mean/sum of |N (m ) (j)| unknown vectors ′ in Rd admits infinitely many decompositions when |N (m ) (j)| > 1. ′

• Degree-ambiguous: the degree |N (m ) (j)| is unknown to client m, compounding the underdetermination. P k,(1) Sub-claim 2b (Summation over border nodes). Client m receives j∈N̂i Ht,j , not individual embeddings. By the argument in Proposition H.2, decomposing this sum into per-node contributions is itself infeasible without knowing |N̂i | or individual feature vectors. Therefore, the 2-hop correction reveals neither the identity of j’s local neighbours nor the edges between them. Proposition H.4 (Infeasibility of Client–Client Collusion). Even if two clients m and m′′ collude, they cannot (m′ ) reconstruct the subgraph Gt of a third client m′ . Proof. Colluding clients m and m′′ can pool their respective corrections: (1)

(2)

(1)

(2)

{δi , δi }i∈B (m) ∪ {δi , δi }i∈B (m′′ ) ′′

where B (m) and B (m ) are the respective border node sets.

27

(15)

′′

Case 1: Non-overlapping cross-client neighbourhoods. If N̂i ∩N̂i′ = ∅ for all i ∈ B (m) , i′ ∈ B (m ) , ′

(m )

then the corrections provide independent aggregated views of disjoint subsets of Vt Propositions H.2–H.3 apply independently to each.

, and the arguments of ′

Case 2: Overlapping cross-client neighbourhoods. Suppose there exists j ∈ Vt(m ) such that j ∈ N̂i ′′

for i ∈ B (m) and j ∈ N̂i′ for i′ ∈ B (m ) . Then the colluders observe: X (1) (0) (0) δi = Ht,j + Ht,j ′

(16)

j ′ ∈N̂i \{j} (1)

X

(0)

δi′ = Ht,j +

(0)

Ht,j ′′

(17)

j ′′ ∈N̂i′ \{j}

This is a system of 2 equations in Rd with (|N̂i | + |N̂i′ | − 1) unknown vectors. For any |N̂i | + |N̂i′ | > 3, the system is under-determined. Even in the degenerate case |N̂i | = |N̂i′ | = 1 (both corrections encode only j), the colluders recover ′ (0) Ht,j = Xt,j , the raw feature of node j, but learn nothing about j’s internal edges {(j, u) : u ∈ N (m ) (j)}, (1)

since δi

contains only 0-hop features which carry no topological information. k,(1)

For the 2-hop case, even isolating Ht,j from the summed corrections requires solving an under-determined linear system, and by Sub-claim 2a in Proposition H.3, a single embedding still does not reveal the internal (m′ ) topology of Gt . Proposition H.5 (Dimensional Insufficiency). The information received by client m about client m′ is bounded (m′ ) (m′ ) 2 by O(|B (m) | · d), whereas reconstructing Gt requires Ω(|Vt | ) bits. (1)

Proof. For each border node i ∈ B (m) , the client receives at most two d-dimensional vectors (δi Hence the total information is at most 2|B (m) | · d real-valued numbers. (m′ )

The adjacency matrix Adjt

(m′ )

∈ {0, 1}|Vt

(m′ )

|×|Vt

|

(m′ )

has |Vt 2

|

(2)

and δi ).

free entries. From Appendix D.3 (Table 6), (m′ )

the cut-edge ratio is extremely low (e.g., 0.0006 for DBLP5), so |B (m) | ≪ |Vt ! (m′ ) | |Vt (m) 2|B | · d ≪ 2

|. Therefore: (18)

Even treating each received real number as carrying maximal information, the dimensionality of the received (m′ ) signal is fundamentally insufficient to specify the adjacency structure of Gt .

I

Reproducibility

We have open-sourced DG-CoLearn-AB95

J

DG-CoLearn,

available

at:

https://anonymous.4open.science/r/

Limitations

While DG-CoLearn delivers strong empirical results under the client-oblivious trusted-server regime, several limitations are worth noting. First, our privacy guarantees (Appendix H) rely on the server faithfully executing the protocol; extending the framework to handle a malicious server would require integrating complementary techniques such as secure aggregation. Second, we restrict cross-client message passing to 2-hop communication following standard practice [32], which may limit accuracy in graphs where information from deeper neighbourhoods is essential. Third, our scalability evaluation focuses on TGB benchmarks up to 27M edges; extension to billion-edge graphs may require further engineering optimisations such as hierarchical partitioning. Finally, while DG-CoLearn is backbone-agnostic, our experiments with continuous-time encoders are limited to DyGFormer; broader integration with other CTDG methods is left to future work.

28