PriDyG: Privacy-preserving Dynamic Graph Inference with LLM-GNN Collaboration

PriDyG: Privacy-preserving Dynamic Graph Inference with LLM-GNN Collaboration Yuyang Xia

Ruixuan Liu

Li Xiong

Emory University Atlanta, Georgia, USA yuyang.xia@emory.edu

Emory University Atlanta, Georgia, USA ruixuan.liu2@emory.edu

Emory University Atlanta, Georgia, USA lxiong@emory.edu

arXiv:2608.04255v1 [cs.CR] 4 Aug 2026

Abstract Graph inference over relational data can expose sensitive edge information, and this risk becomes more severe in dynamic graphs, where repeated model updates cause privacy loss to accumulate. We formulate Edge-level Differentially Private Dynamic Graph Inference (EDG) and propose PriDyG, a private inference framework that combines GNN-based structural learning with LLM-based semantic reasoning. PriDyG introduces incremental private multi-hop aggregation, which buffers newly arrived edges and processes each edge exactly once. By parallel composition, the total privacy cost equals that of a single static release, independent of the number or schedule of model updates. Compared with geometrically decaying budget allocation, incremental aggregation avoids exponentially increasing noise while preserving exact one-hop signals and at least half of two-hop information transfers. PriDyG further complements privatized GNN outputs with LLM predictions derived solely from node text, incurring no additional edge-level privacy cost. Experiments on four benchmarks for node classification and link prediction show that PriDyG consistently outperforms geometrically decaying baselines under the same privacy budget and matches the utility of naive per-update retraining while reducing cumulative privacy cost by up to three orders of magnitude. ACM Reference Format: Yuyang Xia, Ruixuan Liu, and Li Xiong. 2018. PriDyG: Privacy-preserving Dynamic Graph Inference with LLM-GNN Collaboration. In Proceedings of Make sure to enter the correct conference title from your rights confirmation email (Conference acronym ’XX). ACM, New York, NY, USA, 12 pages. https: //doi.org/XXXXXXX.XXXXXXX

1

Introduction

Graphs support many real-world applications, such as social network analysis, citation analysis, and e-commerce recommendation. Graph inference tasks [28, 34, 36], such as node classification and link prediction, are fundamental to these applications. However, graph structure inherently encodes sensitive information: edges may represent social connections, financial transactions, or medical consultations. Answering inference queries over such graphs

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. Conference acronym ’XX, Woodstock, NY © 2018 Copyright held by the owner/author(s). Publication rights licensed to ACM. ACM ISBN 978-1-4503-XXXX-X/2018/06 https://doi.org/XXXXXXX.XXXXXXX

may therefore expose sensitive relationships encoded in their structure, even when individual node attributes are considered nonsensitive [8]. Differential privacy (DP) [6] offers a principled framework for protecting sensitive information. In the graph setting, edge-level DP guarantees that the presence or absence of any single edge cannot be reliably inferred from a mechanism’s output [18]. Recent work has made significant progress on privacy-preserving graph learning. GAP [22] and ProGAP [21] introduce aggregation perturbation to achieve edge-level DP for Graph Neural Networks (GNNs), while other works [5, 17, 31, 37] explore alternative privacy notions and mechanisms, including node-level DP. However, this protection comes at a steep utility cost (Challenge 1): enforcing edge-level DP requires injecting calibrated noise into the neighborhood aggregation process, which distorts precisely the structural signal that GNNs rely on. Under practical privacy budgets, DP-GNNs suffer substantial accuracy degradation relative to their non-private counterparts. This challenge is further compounded when the graph evolves (Challenge 2). In practice, graphs are rarely static; they evolve as new events and interactions occur [13, 23, 25, 35], and inference models must be updated to reflect the current graph state. Continual inference on an evolving private graph raises a distinct privacy-accounting difficulty: as new edges arrive and the pipeline is repeatedly updated, historical edges are accessed again at every update, so privacy loss accumulates over time. Recent efforts have explored privacy protection for dynamic graphs. For example, Raskhodnikova et al. [19] design private algorithms for traditional tasks, such as triangle counting, on fully dynamic graphs, and DyGAN-EDP [10] studies edge-level DP dynamic graph publishing by modeling a dynamic graph as a sequence of snapshots and synthesizing privacy-preserving future snapshots with a generative adversarial framework. However, these methods target private statistics or synthetic graph release rather than continual private inference over an evolving graph, and none of them addresses the accumulation of privacy loss across model updates. To the best of our knowledge, this is the first work to formulate and study edgelevel DP graph inference over continually updated graphs, with the goal of ensuring that privacy cost does not grow with the number of graph updates. To address these two challenges, we propose PriDyG, a privacypreserving dynamic graph inference framework that couples LLMbased semantic reasoning with dynamic DP-GNN structural learning, as illustrated in Figure 1. PriDyG runs two complementary branches: an LLM branch that answers queries from node textual attributes alone, and a DP-GNN branch that learns from the graph structure under edge-level DP; their predictions are combined

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

Yuyang Xia, Ruixuan Liu, and Li Xiong

through a confidence-gated fusion mechanism. The key insight behind the collaborative design is that edge-level DP protects only the graph structure: node-level textual attributes fall outside the protected data under this threat model, so LLM predictions computed solely from them consume zero privacy budget. This privacy-free semantic signal compensates for the utility loss incurred by the privatized GNN, directly narrowing the privacy–utility gap of Challenge 1. Final Answer Dynamic DP-GNN , ... , Dynamic Graph

Gated Fusion

GNN Answer

Semantic Embedding of node text

Boost Query LLM

Initial LLM Answer

LLM

Refined LLM Answer

Figure 1: Overall architecture of PriDyG.

For the dynamic DP-GNN branch, we build on aggregationperturbation methods [22], whose privacy cost is dominated by the Private Multi-hop Aggregation (PMA) step that perturbs the multi-hop neighborhood aggregation over the entire graph. Naively, every model update re-invokes PMA on the full graph; after 𝑀 updates, sequential composition yields a total cost of 𝑀 · 𝜖PMA , which grows linearly and quickly becomes prohibitive. A seemingly viable alternative, following continual-release practice [7], is to keep re-running full PMA while allocating a geometrically decaying budget to successive updates: the total cost then stays bounded, but the per-update budget decays exponentially toward zero, so the required noise scale grows exponentially and later models rapidly become unusable. Our key observation is that the pre-normalization aggregation is linear in the adjacency matrix, so newly inserted edges can be folded into the cached noisy aggregations as an additive delta—each edge’s raw topology is accessed exactly once, and the parallel composition theorem of DP bounds the total privacy cost by a constant 𝜖PMA , independent of the number of updates 𝑀. The cost of this constant budget is paid in signal rather than privacy: the incremental aggregation only approximates a full retrain, omitting certain multihop propagation paths and accumulating noise across updates. We prove that this approximation is structured and bounded—one-hop aggregation is signal-exact, higher hops retain provable capture guarantees, and noise grows only polynomially, in contrast to the exponential blow-up of geometric decay—resolving Challenge 2. Importantly, the two components are coupled rather than independent fixes to separate problems. Node textual attributes remain fixed as the graph evolves, so the LLM branch provides a stable, privacy-free semantic anchor throughout the dynamic process, whereas the accuracy of the incremental GNN branch gradually erodes as noise accumulates across updates. The confidence-gated fusion mediates between the two adaptively. As accumulating noise shrinks the GNN’s prediction margins, more queries fall below the confidence threshold and are routed to fusion. We observe this in

both node classification and link prediction tasks: over a long insertion stream the GNN branch alone causes substaintial accuracy drop relative to static training, whereas PriDyG’s accuracy remains stable. Hence, the pipeline’s reliance naturally shifts toward the stable LLM anchor over the course of the stream. The LLM-GNN collaboration is therefore most valuable precisely in the dynamic regime—where the structural branch is at its weakest—rather than being a generic accuracy boost bolted onto a dynamic mechanism. Our main contributions are as follows: • LLM-GNN collaborative framework. We design PriDyG, a unified pipeline that combines DP-GNN structural learning with privacy-free LLM semantic reasoning via confidence-gated fusion. The LLM branch compensates for the utility loss caused by privacy protection, thereby narrowing the privacy–utility gap. • Constant-budget dynamic graph inference. We propose incremental PMA, which exploits the disjointness of inserted edge batches to achieve 𝑂 (1) total privacy cost under arbitrarily many model updates. This fundamentally resolves the privacy budget tension in dynamic graph inference, allowing frequent model updates without additional privacy degradation. • Comprehensive evaluation. We evaluate PriDyG on four benchmark datasets (Cora, PubMed, ogbn-arxiv, ogbn-products) for node classification and link prediction. Under graph updates it is the most accurate private method on all four datasets while maintaining formal edge-level DP guarantee, and remains competitive with non-private baselines.

2

Preliminaries

We introduce the key concepts underlying our work and then formally define the problem. Table 1 summarizes important notations used in our paper.

Notations

E X T 𝑞 A Z̄ N B

Definitions Edge set Node feature Textual attribute Graph query Adjacency matrix Normalized encodings for GNN Gaussian noise Edge buffer

Table 1: Notations.

2.1

Attributed and Dynamic Graphs

Let G = (V, E, X, T) denote an attributed undirected graph with 𝑛
nodes, edge set E ⊆ V2 , node features X ∈ R𝑛×𝑑 , and textual attributes T = {𝑡 𝑣 } 𝑣 ∈ V ; each node carries a label 𝑦 𝑣 ∈ Y = {1, . . . , 𝐶}. A dynamic graph evolves through a stream of edge insertions: arriving edges accumulate in a buffer and are incorporated when a retraining command is issued, starting from an initial state G (0) (e.g., containing only edges between training nodes). At any point, two types of inference queries may be issued: a node classification query 𝑞 nc (𝑣) predicts 𝑦ˆ𝑣 ∈ Y, and a link prediction query 𝑞 lp (𝑢, 𝑣) predicts a score 𝑠 (𝑢, 𝑣) ∈ [0, 1] for the likelihood that edge {𝑢, 𝑣 } exists.

PriDyG: Privacy-preserving Dynamic Graph Inference with LLM-GNN Collaboration

2.2

Differential Privacy

A randomized mechanism M : D → R satisfies (𝜖, 𝛿)-DP [6] if for all neighboring 𝐷, 𝐷 ′ ∈ D and all measurable 𝑆 ⊆ R, Pr[M (𝐷) ∈ 𝑆] ≤ 𝑒 𝜖 Pr[M (𝐷 ′ ) ∈ 𝑆] + 𝛿. We use the following standard facts. Edge-level DP. Two graphs are neighbors if they differ by a single undirected edge, |E△E ′ | = 1; DP under this adjacency protects the existence of any individual edge. Removing one undirected edge {𝑢, 𝑣 } changes the neighbor aggregation of both endpoints, each by at √ most one unit-norm vector, so the ℓ2 -sensitivity of aggregation is 2 (vs. 1 under the directed-edge convention of GAP [22]). Gaussian mechanism and accounting. For 𝑓 with ℓ2 -sensitivity Δ2 (𝑓 ), releasing 𝑓 (𝐷) + N (0, 𝜎 2 I) satisfies (𝜖, 𝛿)-DP with 𝜎 calibrated by a standard accountant; we use the Rényi-DP accountant [12] of GAP [22]. Our analysis is accountant-agnostic (Section 3.5). Parallel composition. If 𝐷 is partitioned into disjoint subsets 𝐷 1, . . . , 𝐷 𝑀 and M𝑚 accesses only 𝐷𝑚 with cost 𝜖𝑚 , the total cost of releasing all outputs is max𝑚 𝜖𝑚 , not the sum [24]. This is the structural tool behind our constant budget: naive retraining accesses all edges each time (sequential composition, linear growth), whereas incremental PMA partitions edges into disjoint batches across retrains. Post-processing immunity. Any function of a DP release satisfies the same guarantee; downstream computations on privatized outputs (classifier training, fusion, LLM use of released scores) incur no additional cost.

2.3

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

2.4

Problem Formulation

Definition 2.1 (EDG Problem). Given a dynamic graph {G (0) , G (1) , . . . } evolving through edge insertions and a stream of queries {𝑞 1, 𝑞 2, . . . }, where each query 𝑞𝑖 is either a node classification query 𝑞 nc (𝑣) or a link-prediction query 𝑞 lp (𝑢, 𝑣), our goal is to design a mechanism M that (1) answers each query using the current graph state; (2) satisfies edge-level (𝜖, 𝛿)-DP over the entire execution; and (3) maintains high prediction accuracy and ranking quality despite privacy constraints and graph evolution. Our threat model protects only edge existence; node text and node labels are treated as public. Under this assumption, LLM predictions derived solely from node text incur no additional edge-level privacy cost. The central challenge is the privacy budget tension: each retraining consumes budget under sequential composition, growing as 𝑀 · 𝜖PMA after 𝑀 retrains. Our incremental PMA processes each edge exactly once, so parallel composition applies and 𝜖total = 𝜖PMA , independent of 𝑀 and of the retraining schedule.

3

Methodology

In this section, we present PriDyG, a privacy-preserving dynamic graph inference pipeline that combines GNN-based structural learning with LLM-based semantic reasoning under edge-level differential privacy. Throughout this section, we present PriDyG using node classification as the default task; Section 3.3 describes how the framework is adapted to link prediction. Figure 1 illustrates the overall architecture.

Edge-Level DP Graph Learning 3.1

Our GNN module builds directly on GAP [22], whose decoupled three-stage pipeline—encoder pre-training, private multi-hop aggregation, and classifier training—we recall here; the construction in this subsection is entirely from [22], except for the sensitivity constant noted below.

Overview

PriDyG operates in a streaming setting where edges arrive over time and inference queries must be answered on the fly. The pipeline consists of three modules: (1) GNN module: A DP GNN based on the GAP framework [22] that learns structural representations through private multi-hop aggregation (PMA). Encoder. An MLP encoder 𝑓𝜃 maps node features to lower-dimensional (2) LLM module: An LLM that performs zero-shot classification representations z𝑣 = 𝑓𝜃 (x𝑣 ). Since the encoder accesses only node using node textual attributes, consuming no privacy budget. features and labels, never edges, this stage is privacy-free under (3) Fusion module: A confidence-gated mechanism that dynamiedge-level DP. cally combines GNN and LLM predictions. Since the LLM operates solely on node-level textual attributes, Private multi-hop aggregation (PMA).. Let A be the adjacency its predictions are a function of data outside the protected domain: matrix of the current graph and let Z̄ (0) be the ℓ2 -row-normalized edge-level DP constrains only the edge set, while node text is public encodings. For each hop 𝑘 = 1, . . . , 𝐾: in our setting (Definition 2.1). LLM inference therefore consumes zero privacy budget, allowing PriDyG to maintain high-quality (𝑘 ) (𝑘 −1) 2 (𝑘 ) (𝑘 ) Z̃ = A Z̄ + N (0, 𝜎 I), Z̄ = Normalize( Z̃ ), (1) predictions even when the GNN module operates under a tight privacy budget. where Normalize(·) applies row-wise ℓ2 -normalization. Because −1) has unit norm, the aggregation in (1) has ℓ every row of Z̄ (𝑘√ 2 3.2 Node Classification sensitivity Δ2 = 2 under the undirected-edge adjacency of SecGNN Module. The GNN module is the edge-level DP pipeline tion 2.2. The Gaussian mechanism applied over the 𝐾 hops therefore of Section 2.3. The encoder maps node text embeddings to Z̄ (0) ; yields an edge-level (𝜖PMA, 𝛿)-DP guarantee, where 𝜖PMA (𝜎, 𝛿) de𝐾 rounds of Gaussian-perturbed aggregation (1) over the current notes the cost of a single 𝐾-hop PMA invocation. 𝐾 at an graph state yield the privatized multi-hop features {Z̄ (𝑘 ) }𝑘=0 Classifier. A classifier 𝑔𝜙 takes the multi-hop features {Z̄ (0) , . . . , Z̄ (𝐾 ) } edge-level cost of 𝜖PMA ; and the classifier 𝑔𝜙 maps them to label as input and predicts node labels. As it operates on already-privatized logits for a query node 𝑞:   features, training it incurs no additional privacy cost by post-processing ŷ𝑞 = 𝑔𝜙 Z̄𝑞(0) , . . . , Z̄𝑞(𝐾 ) ∈ R𝐶 . (2) immunity.

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

Yuyang Xia, Ruixuan Liu, and Li Xiong

The module exposes two quantities downstream: the logit vector graph ŷ𝑞 , from which the fusion step below forms s𝑞 , and the top𝑚 labels induced by ŷ𝑞 , which seed the second-stage candidate 𝐾 is a DP release, both are set of the LLM module. Since {Z̄ (𝑘 ) }𝑘=0 post-processing and incur no cost beyond 𝜖PMA . LLM Module: Semantic Reasoning. For a query node 𝑞 with textual attributes 𝑡𝑞 , the LLM computes a probability distribution over candidate labels via token log-probabilities:

𝑃LLM (𝑙 | 𝑡𝑞 ) ∝ exp

|𝑙 | ∑︁

! log 𝑃 (𝑙 𝑗 | 𝑙 < 𝑗 , prompt) .

(3)

𝑗=1

where 𝑙 𝑗 denotes the 𝑗-th token of label 𝑙, and prompt contains the query node’s textual attributes and the candidate label set. We employ a two-stage boost query as shown in Figure 1: the first stage scores all 𝐶 candidate labels; the second stage re-scores a smaller candidate set formed by the union of top-𝑚 labels from the GNN score and the LLM score, so the total size of the union is 2𝑟 . This strategy shrinks the context window and helps the LLM reduce the prompt length and focus on the most likely labels. Since the LLM accesses only public node text (not edges) and DP GNN predictions, it introduces no additional privacy cost. graph

= softmax( ŷ𝑞 ) and p𝑞LLM Confidence-Gated Fusion. Let s𝑞 denote the GNN and LLM score vectors, respectively. Since invoking the LLM for every query incurs substantial computational overhead, we adopt confidence-gated fusion to selectively use the LLM only when the graph-based prediction is uncertain. This design reduces unnecessary LLM inference while allowing complementary textual information to assist with ambiguous queries. Specifically, we define the GNN confidence margin as 𝑚𝑞 = 𝑠𝑞(1) − 𝑠𝑞(2) , where 𝑠𝑞(1) and 𝑠𝑞(2) are the largest and second-largest probabilities, respectively. If 𝑚𝑞 > 𝜏, we directly use the GNN prediction. Otherwise, we fuse the GNN and LLM predictions over the top-2𝑚 candidates: graph

p𝑞fused [𝑙] = 𝛼 · s̄𝑞

[𝑙] + (1 − 𝛼) · p̄𝑞LLM [𝑙],

𝑙 ∈ top-2𝑚, (4)

where s̄ and p̄ are re-normalized to the top-2𝑚 set. The parameters (𝛼, 𝜏) are tuned via grid search on a validation set. Since node labels are treated as public under our edge-level privacy model, this tuning incurs no additional privacy cost.

3.3

Link Prediction

We now turn to the second query type of Definition 2.1. Link prediction is particularly delicate under edge-level DP, because the prediction target is the existence of an edge, which is exactly the information to be protected. In node classification, labels are public supervision, so that channel is privacy-free; any supervised link predictor instead reads edge-existence labels and thus protected data. PriDyG therefore stays in post-processing: its default link predictor is a training-free function of the privatized PMA representations, and the only component that requires edge labels is calibrated on randomized-response labels on a disjoint set of node pairs.

Cosine Scoring as the Default Link Predictor. After private multi-hop aggregation, each node 𝑣 obtains a privatized multihop representation z̄𝑣 = [z̄𝑣(0) ∥z̄𝑣(1) ∥ · · · ∥z̄𝑣(𝐾 ) ], where z̄𝑣(𝑘 ) is derived from PMA. For a candidate node pair (𝑢, 𝑣), PriDyG computes a structural link score as the cosine similarity of these repz̄⊤ z̄ resentations: 𝑠 cos (𝑢, 𝑣) = ∥z̄𝑢 ∥𝑢2 ∥z̄𝑣 𝑣 ∥ 2 . For fusion and calibration, we map the cosine score to [0, 1] by the deterministic transformation 𝑠˜cos (𝑢, 𝑣) = 𝑠cos (𝑢,𝑣)+1 . 2 This cosine-based predictor is the default link prediction method in PriDyG. It does not access raw edge labels and does not inspect the original graph during inference. Since it only operates on already privatized PMA representations, it is a post-processing step of the edge-level DP PMA mechanism and incurs no additional privacy cost. LLM semantic score. Cosine scoring captures privatized structural similarity, but DP noise perturbs every z̄𝑣 and can damage the fine-grained ordering that ranking metrics depend on. As complementary evidence, PriDyG computes a semantic score from node text alone: 𝑠 LLM (𝑢, 𝑣) = 𝑃LLM (“Yes” | 𝑡𝑢 , 𝑡 𝑣 ), where 𝑡𝑢 and 𝑡 𝑣 are the textual attributes of nodes 𝑢 and 𝑣. The prompt is instantiated per domain: for citation graphs, it asks whether two papers are likely connected by citation or topical relevance; for product graphs, whether two products are likely co-purchased. Since the prompt contains only public node text and no topology, 𝑠 LLM consumes no privacy budget. Private fusion-weight calibration. The two scores are combined by the confidence-gated rule of node classification, with the gate measured on a scalar score. The fusion is post-processing, so the choice of (𝛼, 𝜏) is not free. Unlike node classification, where these are tuned on public node labels, the tuning signal is the edge existence itself, which edge-level DP protects. We therefore calibrate on randomized-response labels.
We randomly partition the candidate pairs in V2 into the fusion partition P𝑓 𝑢𝑠 (with 𝑟 = 5% assigned to P𝑓 𝑢𝑠 ) and the remainder P𝑡𝑟𝑎𝑖𝑛 . At 𝑡 = 0, for every pair (𝑢, 𝑣) ∈ P𝑓 𝑢𝑠 , we release a single privatized copy of its existence bit 𝑏𝑢𝑣 = ⊮[(𝑢, 𝑣) ∈ E (0) ] via randomized response [30], 𝜖 𝑏˜𝑢𝑣 = 𝑏𝑢𝑣 w.p. 𝜖𝑒 RR , 𝑏˜𝑢𝑣 = 1 − 𝑏𝑢𝑣 otherwise, (5) 𝑒 RR +1

where 𝜖RR is the privacy budget allocated to randomized response. Parallel composition applies only if each edge is touched by one mechanism, so we exclude the initial edges in P𝑓 𝑢𝑠 from the initial PMA adjacency. A pair of P𝑓 𝑢𝑠 that becomes an edge at some 𝑡 > 0 is instead processed by incremental PMA (Section 3.4). Hence, initial calibration edges are protected through randomized response, while subsequent edge insertions are protected through incremental PMA. The weight 𝛼 and threshold 𝜏 are then selected by grid search, maximizing the empirical AUC computed on the privatized link labels {𝑏˜𝑢𝑣 }. Lemma 3.1 (Privacy of fusion calibration). The release of {𝑏˜𝑢𝑣 } (𝑢,𝑣) ∈ Pfus satisfies edge-level (𝜖RR, 0)-DP. Moreover, the joint release of the full PriDyG output, incremental PMA outputs (Theo-
rem 3.3) and the calibration bits, satisfies edge-level max(𝜖PMA, 𝜖RR ), 𝛿 DP, for any number of retrains and any schedule. The proof of Lemma 3.1 is in Appendix A.

PriDyG: Privacy-preserving Dynamic Graph Inference with LLM-GNN Collaboration

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

In all experiments, we set 𝜖RR = 𝜖PMA , so the end-to-end guarantee of PriDyG remains (𝜖PMA, 𝛿)-DP, unchanged from Theorem 3.3.

the row-normalized encoder output, which depends only on node text and is therefore identical across all retrains. (3) Update the cached features. (𝑘 ) (𝑘 ) (𝑘 ) (𝑘 )
Z̃new = Z̃cached + ΔZ̃ (𝑘 ) , Z̄new = Normalize Z̃new , (7)

3.4

Dynamic Graph Handling via Incremental PMA

A central challenge in dynamic graph inference under DP is that structural changes require re-running PMA, yet each invocation consumes privacy budget. Naively re-running PMA on the entire graph at every retrain would cause the total privacy cost to grow linearly as 𝑀 · 𝜖PMA , where 𝑀 is the number of retrains. We introduce incremental PMA, which keeps the total privacy budget at a constant 𝜖PMA regardless of the number of retrains. 3.4.1 Baseline: Geometrically Decaying Budget Allocation. A straightforward baseline is to rerun full PMA over the entire current graph whenever a retraining command is issued, while assigning a geometrically decaying privacy budget to successive retraining operations. Specifically, given a total privacy budget 𝜖tot , the budget allocated to the 𝑚-th retraining can be defined as 𝜖𝑚 = (1 − 𝑞)𝑞𝑚 𝜖tot, 0 < 𝑞 < 1. Í∞ Since 𝑚=0 𝜖𝑚 = 𝜖tot, this strategy supports an unbounded number of retraining operations without exceeding the prescribed total privacy budget. Similar geometric budget-allocation strategies have been adopted for continual DP release [7]. However, this baseline suffers from severe utility degradation over long-running update streams. As the number of retraining operations increases, the privacy budget available to later retraining operations decays exponentially toward zero. Consequently, the required noise grows rapidly, making the updated model increasingly inaccurate. Moreover, because each retraining still accesses the entire graph, historical edges are repeatedly processed; the method controls the cumulative privacy loss only by progressively weakening the utility of later releases. 3.4.2 Incremental PMA Algorithm. The graph evolves through edge insertions. As shown in Figure 2, incremental PMA maintains an edge buffer B that accumulates newly arrived edges since the last retrain. When a retraining command is issued (by any external policy), incremental PMA processes all edges in B, updates the cached aggregations, and clears B. We denote the edges processed at the 𝑚-th retrain as ΔE (𝑚) and write E (𝑚) = E (𝑚−1) ∪ ΔE (𝑚) . The retraining schedule itself is not part of the algorithm and does not affect the privacy guarantee. At the initial retrain (𝑚 = 0), we run full PMA on E (0) and cache both the pre-normalization aggregations Z̃ (𝑘 ) and their rownormalized counterparts Z̄ (𝑘 ) for all hops 𝑘. At each subsequent retrain 𝑚 ≥ 1, the hops are updated sequentially, in increasing order 𝑘 = 1, 2, . . . , 𝐾; the update for hop 𝑘 begins only after the update for hop 𝑘 − 1 has completed. Each retrain proceeds as follows: (1) Build delta adjacency matrix. Construct ΔA (𝑚) from the new edges ΔE (𝑚) . (2) Compute delta aggregation with noise. For each hop 𝑘 = 1, . . . , 𝐾 in order: (𝑘 −1) ΔZ̃ (𝑘 ) = ΔA (𝑚) Z̄new + N (0, 𝜎 2 I),

(6)

(𝑘 −1) where Z̄new denotes the hop-(𝑘−1) normalized features

finalized in Step 3 of the current retrain, i.e., strictly before (0) hop 𝑘 is processed. For the base case 𝑘 = 1, Z̄new = Z̄ (0) is

(𝑘 ) where Z̃cached is the pre-normalization aggregation carried (𝑘 ) (𝑘 ) over from the previous PMA. Store Z̃new and Z̄new for the next retrain.

Sequential hop updates. Equation (6) intentionally multiplies (𝑘 −1) ΔA (𝑚) by the updated lower-hop features Z̄new rather than by the (𝑘 −1) stale cache Z̄cached . This introduces no circularity: within a retrain, hop 𝑘 consumes only the finalized output of hop 𝑘 − 1, exactly mirroring the sequential hop structure of full PMA in Eqs. (1), and hop 𝑘 never depends on its own output. The choice is also important for utility: using the stale cache would let new edges aggregate only pre-update features, so a two-hop path traversing two newly inserted edges would transfer no information at all. With Eq. (6), (1) hop 1 is exact (since Z̄ (0) is edge-independent, Z̃new equals the hop-1 aggregation of a full retrain up to the noise realization), and higher hops satisfy the capture guarantees of Section 3.6. Privacy is unaffected by this adaptivity: as shown in the proof of Theorem 3.3, conditional on the outputs √ released so far, each hop is a Gaussian mechanism of sensitivity 2, and the 𝐾 hops of a retrain have exactly the same mechanism structure as one static PMA invocation, so any accounting valid for static PMA applies unchanged. Which modules are retrained. Incremental PMA caches aggregations of fixed input features. Accordingly, after the initial retrain, the encoder 𝑓𝜃 is frozen; only the classification head 𝑔𝜙 , whose output is never re-aggregated, is retrained at each retrain, and since 𝑔𝜙 consumes only already-privatized features, its retraining is post-processing and incurs no privacy cost.

1

1

3

2 4

3

2

5

4

Old graph

5

New graph

1 3 4

5

Edge buffer ҧ (𝑘−1) + 𝑁(0, 𝜎 2 𝐼) ∆𝑍෨ (𝑘) = ∆𝐴 ∗ 𝑍𝑛𝑒𝑤 (𝑘) 𝑍෨𝑐𝑎𝑐ℎ𝑒𝑑 (𝑘) 𝑍ҧ

𝑐𝑎𝑐ℎ𝑒𝑑

(𝑘) (𝑘) 𝑍෨𝑛𝑒𝑤 = ∆𝑍෨ (𝑘) + 𝑍෨𝑐𝑎𝑐ℎ𝑒𝑑 (𝑘) ҧ (𝑘) = 𝑁𝑜𝑟𝑚𝑎𝑙𝑖𝑧𝑒 (𝑍෨𝑛𝑒𝑤 𝑍𝑛𝑒𝑤 )

(𝑘) 𝑍෨𝑛𝑒𝑤 ҧ (𝑘) 𝑍𝑛𝑒𝑤

Figure 2: Example for incremental PMA.

Example 3.2. As shown in Figure 2, the edge buffer is {(1, 5), (3, 4)}. When the next retraining command is issued, incremental PMA builds the delta adjacency ΔA, whose only nonzero entries correspond to the two undirected edges: ΔA[1, 5] = ΔA[5, 1] = ΔA[3, 4] = ΔA[4, 3] = 1. The delta aggregation at hop 𝑘 therefore touches only the four endpoints of the buffered edges:  (𝑘 −1)  (𝑘 −1) (𝑘 −1) (𝑘 −1) (𝑘 −1) ΔA Z̄new = Z̄new [5], 0, Z̄new [4], Z̄new [3], Z̄new [1] .

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

The entries correspond to node 1 through 5, respectively. That is, node 1 receives node 5’s (already updated) hop-(𝑘−1) representation and vice versa, nodes 3 and 4 receive each other’s representations, and node 2—incident to no new edge—receives the zero vector. The noisy delta is then added to the cached pre-normalization fea(𝑘 ) tures Z̃cached and re-normalized.

3.5

Privacy Analysis of Incremental PMA

The privacy guarantee of incremental PMA follows from a simple structural property: each edge is processed exactly once. When an edge arrives, it enters the buffer; when a retraining command is issued, the buffer is cleared. Regardless of the retraining schedule, each edge incurs the privacy cost of one static PMA invocation. This decouples the privacy analysis from the retraining policy entirely. Theorem 3.3 (Constant privacy budget under incremental PMA). Fix the noise scale 𝜎, the number of hops 𝐾, and 𝛿 ∈ (0, 1), and let 𝜖PMA be any value such that a single static 𝐾-hop PMA invocation with noise scale 𝜎 satisfies edge-level (𝜖PMA, 𝛿)-DP (e.g., as certified by the accountant of [22]). Let 𝐵 0 = E (0) and 𝐵𝑚 = ΔE (𝑚) for 𝑚 ≥ 1 denote the edge batches drained at each retrain. Then for any number of retrains 𝑀 and any retraining schedule, the full out (𝑘 ) 𝐾 put of incremental PMA, 𝑌0:𝑀 = (𝑌0, 𝑌1, . . . , 𝑌𝑀 ), 𝑌𝑚 = ΔZ̃𝑚 , 𝑘=1 satisfies edge-level (𝜖PMA, 𝛿)-DP. In particular, the privacy cost does not grow with 𝑀, does not depend on the retraining schedule, and equals that of a single static PMA invocation. Proof of Theorem 3.3 can be found in Appendix A.

3.6

Error Analysis of Incremental PMA

We now characterize the approximation error of incremental PMA relative to a full retrain on the current graph. There are two sources of errors. First, because cached contributions from older edges are not recomputed, incremental PMA omits propagation paths that traverse a newer edge followed by an older edge. This yields a structured approximation error: one-hop propagation is exact, and at least half of all two-hop transfers are retained. Second, each retrain adds fresh Gaussian noise to the cached aggregation, causing the accumulated noise variance to grow linearly with the number of retrains. We formalize these two sources of error below. We first analyze path capture in Theorem 3.4 using noiseless, prenormalization linear propagation (row-wise ℓ2 -normalization is a per-hop post-processing and does not change which path can contribute information). We then analyze noise accumulation separately in Proposition 3.7. Captured-path analysis. Assign each edge the index of the retrain at which it was drained from the buffer, with the initial edge set E (0) as batch 0, and let A𝑖 denote the adjacency matrix of 𝑖th batch 𝐵𝑖 . Write Z = Z̄ (0) , which depends only on node text and is identical across retrains, and let F (𝑘 ) and I (𝑘 ) denote the 𝑘-hop aggregations after retrain 𝑚 under a full retrain and under incremental PMA, respectively. Theorem 3.4 (Captured-path characterization). After any retrain 𝑚 and for every hop 𝑘, ∑︁ I (𝑘 ) = A𝑖𝑘 · · · A𝑖 1 Z, (8) 0 ≤ 𝑖 1 ≤ ··· ≤𝑖𝑘 ≤ 𝑚

Yuyang Xia, Ruixuan Liu, and Li Xiong

𝑘 Í whereas the full retrain F (𝑘 ) = 𝑖 ≤𝑚 A𝑖 Z expands into all length𝑘 paths over {A0, . . . , A𝑚 }. Equivalently, a 𝑘-hop path contributes to I (𝑘 ) if and only if the batch indices of its edges, read in traversal order, are non-decreasing: information may flow from older edges onto newer ones, but never from newer edges back across older ones. Proof of Theorem 3.4 can be found in Appendix A, which unrolls the update recursion across retrains; the error F (𝑘 ) − I (𝑘 ) collects exactly the words containing an older-batch step after a newerbatch step, whose source is the staleness of the cache: old edges, frozen in the cache, never re-aggregate features refreshed by later insertions. The error is thus structured and bounded—incremental PMA omits only these “backward-in-time” paths—rather than an unbounded drift, and it vanishes entirely for 𝐾 = 1: Corollary 3.5 (One hop: lossless in signal). After every retrain, I (1) = F (1) , thus incremental PMA preserves all one hop information in the noiseless aggregation. Corollary 3.6 (Two hops: at least half of all wedge transfers). Two-hop information flows along wedges 𝑢−𝑤−𝑣, each carrying two distinct information transfers, one per traversal direction. Let 𝜌 be the fraction of wedge transfers whose two edges lie in distinct batches. Then captured fraction at hop 2 = 1 − 12 𝜌 ≥ 12 . In Example 3.2, edges (1, 3) and (1, 5) arrive in different batches, so the transfer 3 → 1 → 5 is the captured path and 5 → 1 → 3 is the lost one. Noise accumulation analysis. We next quantify how the Gaussian perturbations introduced across incremental retrains accumulate in the cached representations and compare this growth with the geometrically decaying baseline. Proposition 3.7 (Noise accumulation: linear vs. exponential). Fix the noise scale 𝜎 in each PMA invocation. After 𝑀 incremental retrains, the hop-𝑘 cache Z̃ (𝑘 ) contains the sum of 𝑀+1 independent Gaussian noise N (0, 𝜎 2 I), yielding a total variance of √ (𝑀+1)𝜎 2 and a 𝑀+1-fold inflation in noise magnitude over a single full PMA on the final graph under the same privacy budget. At hop 1, Corollary 3.5 shows that the noiseless signal matches the one-shot full retrain, so this noise is the only deviation. In contrast, under the geometrically decaying baseline of Section
3.4.1, the per-retrain noise scale grows exponentially, 𝜎𝑚 = Θ 𝑞 −𝑚 at fixed 𝛿, and perturbs the entire released representation. The one-shot reference is an oracle that observes the entire final graph in advance and therefore √ cannot answer any query while the stream is evolving. So the 𝑀+1 overhead should be interpreted as the intrinsic cost of continual release relative to the unattainable oracle, and price is an 𝑂 (𝑀) accumulation of noise variance. Incremental PMA therefore trades a structured, bounded approximation error (omitting newer-to-older paths while retaining at least half of all two-hop transfers) and a polynomially growing noise floor for a constant privacy budget, whereas geometric decay is structurally unbiased but exponentially noisy. Proofs of Corollary 3.5, 3.6, and Proposition 3.7 can be found in Appendix A.

PriDyG: Privacy-preserving Dynamic Graph Inference with LLM-GNN Collaboration

4

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

Table 2: Static node classification accuracy.

Experiments

We evaluate PriDyG on node classification and link prediction across four benchmark datasets under edge-level DP, in both static and dynamic settings.

4.1

Experimental Setup

Datasets. We use four graph benchmarks spanning different domains and scales: Cora [11]: A citation network of machine learning papers, where each node represents a paper with title and abstract, and edges denote citation links. The task is to classify papers into 7 categories (e.g., Neural Networks, Reinforcement Learning). PubMed [33]: A biomedical citation network of diabetesrelated publications. Nodes are papers classified into 3 categories of diabetes research. ogbn-arxiv [9]: A large-scale citation network of computer science arXiv papers spanning 40 subject areas (e.g., cs.CV, cs.LG, cs.CL). ogbn-products [9]: A co-purchasing network from Amazon, where nodes are products with textual descriptions and edges connect frequently co-purchased items. Products are classified into 44 categories. Each dataset is integrated with a train/valid/test node split. Therefore, each node in the graph belongs to one of the train/valid/test sets. For all datasets, we encode node text (title and abstract/description) into 1024-dimensional embeddings using BGE-large-en-v1.5 [32] as node features. Dynamic Setting. In the streaming evaluation, we consider the edge insertion case. The graph starts with only train-train edges. Remaining edges are inserted one by one in random order. Every insertion has an independent probability 𝑝 to trigger retraining (default 𝑝 = 0.5%). Privacy and Model Configuration. Unless otherwise stated, we use 𝛿 = 10−5 for all experiments. We set 𝜖PMA = 6.0 with 𝐾 = 2 hops, calibrating the noise scale 𝜎 to this budget with the RényiDP accountant of GAP [22]. The GNN module uses a 3-layer MLP encoder (hidden dim = 256, encoding dim = 128, dropout = 0.5) pre-trained for 100 epochs, followed by a 2-layer MLP classification head trained for 200 epochs. The LLM module uses Llama-3-8BInstruct [2] for logit scoring. Baselines. For node classification, we compare PriDyG against the following methods: ProGAP [21]: the state-of-the-art static edgelevel DP GNN and a stronger static backbone than the DP GNN pipeline inside PriDyG; we adopt it so that our comparisons are against the stronger baseline. In the dynamic setting, it is retrained from scratch at each retrain, with 𝜖 accumulating under sequential composition (trivial retrain) or with geometrically decaying budgets. LLM-only: The ablation baseline uses LLM logit scoring using only node text, without any graph-based component. PriDyG w/o LLM: The ablation baseline uses Graph score without any LLM-based component. Other non-private baselines: results on the same datasets as reported in [26], marked with ‘*’. For link prediction, we compare these baseline methods: Cosine: GNN-based node embeddings with cosine similarity scoring. LLMonly: LLM logit scoring using only node text, without any graphbased component. DPLP [17]: A private-training link prediction method that relies on query-specific subgraph extraction, which does not protect the queried graph structure at inference time.

Method

Cora

PubMed

Arxiv

Products

𝜖

𝛿

LLM-only GCN* LLaGA-HO* [3] GraphGPT* [27] GraphICL-70B*[26] ProGAP PriDyG w/o LLM PriDyG

0.613 0.751 0.886 N/A 0.836 0.725 0.722 0.742

0.887 0.864 0.888 0.847 0.931 0.914 0.914 0.915

0.520 0.726 0.740 0.622 0.737 0.729 0.726 0.734

0.631 0.756 0.736 N/A 0.815 0.859 0.850 0.872

0 N/A N/A N/A N/A 6.0 6.0 6.0

0 N/A N/A N/A N/A

10 −5 10 −5 10 −5

Table 3: Node classification accuracy under edge insertion. Cora

PubMed

Arxiv

Products

Method

Acc

𝜖

Acc

𝜖

Acc

𝜖

Acc

𝜖

ProGAP + Without retrain ProGAP + Trivial retrain ProGAP + Geometric Decay LLM-only PriDyG w/o LLM PriDyG

0.709 0.722 0.703 0.621 0.719 0.738

6 168 6 0 6 6

0.908 0.917 0.878 0.900 0.914 0.918

6 924 6 0 6 6

0.726 0.759 0.708 0.543 0.740 0.760

6 12,372 6 0 6 6

0.860 0.875 0.856 0.614 0.873 0.881

6 18,192 6 0 6 6

4.2

Node Classification Results

Static Evaluation. Table 2 reports node classification accuracy in the static setting, where the full graph is available, and the model is trained once. PriDyG achieves accuracy comparable to the ProGAP baseline and other non-DP baselines. Dynamic Evaluation: Edge Insertion. Table 3 reports results under the edge insertion protocol: edges arrive sequentially, and at each insertion we query their endpoints that belong to the test set. PriDyG achieves the highest accuracy among all constant-budget methods, and matches naive retraining, which consumes up to three orders of magnitude more privacy budget. Most of this gain comes from the GNN branch (PriDyG w/o LLM), yet the LLM branch— despite its lower standalone accuracy—still contributes a consistent improvement, since the two branches are accurate on complementary label sets. Among the constant-budget alternatives, geometric decay performs worst—falling below even ProGAP without retraining, i.e., a model frozen at G (0) that ignores all subsequent edges. This ordering is intuitive: geometric decay pays for freshness with exponentially growing noise, which ultimately destroys the graph signal and negates the benefit of incorporating the new edges. In contrast, the frozen model at least retains a clean snapshot. Accuracies here exceed those in Table 2 because the query sets differ: the streaming protocol queries only endpoints of inserted edges, which skew toward high-degree nodes, whereas the static setting also includes isolated and low-degree test nodes. This selection effect inflates all methods uniformly, so comparisons should be read within each table; Table 4, which evaluates the full test set after the stream ends, is the like-for-like counterpart to Table 2. Table 4: Node classification accuracy after edge insertion. Method

Cora

PubMed

Arxiv

Product

PriDyG w/o LLM PriDyG

0.703 0.731

0.896 0.915

0.705 0.721

0.842 0.851

Long-term effectiveness. Table 4 reports the accuracy of PriDyG on the full test set after all the edge insertions. PriDyG loses only

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

Yuyang Xia, Ruixuan Liu, and Li Xiong

1% on average relative to static training on the same graph, against around 2% for its GNN branch alone, indicating that the LLM-GNN collaboration remains effective under long-term updates.

Table 6: Static link prediction AUC (𝜖 = 6.0, 𝛿 = 10−5 ).

Table 5: Effect of privacy budgets 𝜖 on node classification. ProGAP

Method

Cora

PubMed

Arxiv

Products

Cosine DPLP LLM-only PriDyG

0.888 0.910 0.943 0.947

0.853 0.949 0.965 0.977

0.961 N/A 0.983 0.989

0.976 N/A 0.975 0.986

PriDyG

Dataset

Cora PubMed Arxiv Products

𝜖 =1

𝜖 =6

𝜖 = 10

𝜖 =1

𝜖 =6

𝜖 = 10

0.712 0.904 0.711 0.847

0.725 0.914 0.729 0.859

0.723 0.915 0.727 0.859

0.731 0.907 0.730 0.853

0.742 0.915 0.734 0.872

0.739 0.927 0.745 0.874

Effect of the privacy budget. Table 5 shows the accuracy of PriDyG under different 𝜖 for static node classification. The accuracy increases noticeably from 𝜖 = 1 to 𝜖 = 6, while the increase from 𝜖 = 6 to 𝜖 = 10 is small, suggesting that the high 𝜖 has reached the saturation point. PriDyG consistently outperforms or matches ProGAP across privacy budgets.

Table 7: Link prediction AUC under edge insertion. Cora

PubMed

Arxiv

Products

Method

AUC

𝜖

AUC

𝜖

AUC

𝜖

AUC

𝜖

ProGAP + Without retrain ProGAP + Trivial retrain ProGAP + Geometrically Decaying LLM-only PriDyG w/o LLM PriDyG

0.840 0.852 0.824 0.916 0.852 0.929

6 150 6 0 6 6

0.783 0.787 0.774 0.961 0.786 0.967

6 732 6 0 6 6

0.910 0.923 0.893 0.975 0.924 0.983

6 9,828 6 0 6 6

0.921 0.939 0.902 0.972 0.936 0.978

6 14,286 6 0 6 6

Table 8: Link prediction AUC after edge insertion.

4.3

Link Prediction Results

Static Evaluation. Table 6 reports link prediction performance in the static setting. We use AUC as the evaluation metric, i.e., the model’s ability to separate true edges from randomly sampled negative (non-existent) edges by predicted scores. PriDyG achieves the highest AUC on all four datasets, outperforming both the graphonly cosine baseline and LLM-only scoring. The LLM supplies semantic similarity that compensates for DP noise in the embeddings at zero additional privacy cost. DPLP does not complete training on Arxiv or Products within 72 hours, reported as ‘N/A’. Dynamic Evaluation: Edge Insertion. Table 7 compares link prediction AUC under edge insertion. PriDyG achieves the best AUC with the smallest budget cost across all four datasets. Long-term effectiveness. Table 8 reports the accuracy of PriDyG on the test set after all the edge insertions. As in the node classification task, compared with fully training, PriDyG’s accuracy drops by only roughly 1%, while the GNN part drops by at most more than 5%, demonstrating PriDyG’s effectiveness under long-term updates. Effect of the privacy budget. In Table 9, we show the accuracy of PriDyG under different 𝜖 for static link prediction. The conclusion is similar to that of Table 5: the AUC increases noticeably from 𝜖 = 1 to 𝜖 = 6. The AUC difference between 𝜖 = 6 and 𝜖 = 10 is quite small. PriDyG also consistently outperforms ProGAP across privacy budgets, with a significant margin in most cases.

5

Related Works

Differentially Private Graph Learning. Differential privacy [6] is well established for deep learning [1] and increasingly applied to graph-structured data [14]. Under edge-level DP, existing works perturb node features before aggregation [20], decouple graph convolutions [5, 37], or protect edges specifically for link prediction [16, 17]. Most relevant to us, GAP [22] adds calibrated Gaussian noise to multi-hop aggregation, and ProGAP [21] extends it with progressive training. All of them, however, assume static graphs and a single round of training. When the graph evolves over time, and the model must be periodically retrained, sequential composition

Method

Cora

PubMed

Arxiv

Product

PriDyG w/o LLM PriDyG

0.855 0.938

0.793 0.964

0.927 0.977

0.934 0.980

Table 9: Effect of the privacy budgets 𝜖 on link prediction. Cosine

PriDyG

Dataset

Cora PubMed Arxiv Products

𝜖 =1

𝜖 =6

𝜖 = 10

𝜖 =1

𝜖 =6

𝜖 = 10

0.860 0.808 0.954 0.967

0.888 0.853 0.961 0.976

0.897 0.855 0.959 0.977

0.935 0.954 0.988 0.983

0.947 0.977 0.989 0.986

0.948 0.969 0.989 0.986

causes the privacy budget to grow linearly with the number of retrains. We close this gap with incremental PMA, which exploits parallel composition over disjoint edge batches to achieve constant total privacy cost. Privacy-Preserving Dynamic Graph Analysis. Prior work on dynamic graphs under edge-level DP targets traditional graph queries such as graph density [15, 19], or graph publishing—e.g., DyGAN-EDP [10] models a dynamic graph as discrete snapshots and synthesizes privacy-preserving future ones with a GAN. To the best of our knowledge, PriDyG is the first framework for edge-level DP inference over continually updated graphs at a constant privacy budget. LLMs for Graph Learning. LLMs have shown strong potential for graph tasks by leveraging node-level textual attributes [4, 29], through graph-to-token mappings [3], graph instruction tuning [27], or structured prompting for in-context learning [26]. None of them consider privacy constraints. PriDyG instead exploits the fact that LLM inference relies solely on node text, which edgelevel DP does not protect: the LLM branch incurs zero privacy cost, making it an ideal complement to the DP-constrained GNN.

PriDyG: Privacy-preserving Dynamic Graph Inference with LLM-GNN Collaboration

6

Conclusion

We formulated the Edge-level DP Dynamic Graph Inference (EDG) problem and proposed PriDyG, which combines GNN-based structural learning with LLM-based semantic reasoning under edgelevel DP. PriDyG introduces two contributions: (1) incremental PMA, which exploits the linearity of graph aggregation and disjoint edge batching to keep the total privacy budget independent of the number of model updates, and (2) privacy-free LLM augmentation, which uses node text at zero additional privacy cost to complement the DP-constrained GNN through confidence-gated fusion. Experiments on four benchmarks show that PriDyG attains utility with non-private baselines on both node classification and link prediction, while reducing cumulative privacy cost by orders of magnitude over naive retraining. Future work includes extending PriDyG to node-level privacy and to graph streams with edge deletions.

References [1] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. 2016. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security. 308–318. [2] AI@Meta. 2024. Llama 3 Model Card. (2024). https://github.com/meta-llama/ llama3/blob/main/MODEL_CARD.md [3] Runjin Chen, Tong Zhao, Ajay Jaiswal, Neil Shah, and Zhangyang Wang. 2024. Llaga: Large language and graph assistant. arXiv preprint arXiv:2402.08170 (2024). [4] Zhikai Chen, Haitao Mao, Hang Li, Wei Jin, Hongzhi Wen, Xiaochi Wei, Shuaiqiang Wang, Dawei Yin, Wenqi Fan, Hui Liu, et al. 2024. Exploring the potential of large language models (llms) in learning on graphs. ACM SIGKDD Explorations Newsletter 25, 2 (2024), 42–61. [5] Eli Chien, Wei-Ning Chen, Chao Pan, Pan Li, Ayfer Ozgur, and Olgica Milenkovic. 2023. Differentially private decoupled graph convolutions for multigranular topology protection. Advances in Neural Information Processing Systems 36 (2023), 45381–45401. [6] Cynthia Dwork and Aaron Roth. 2014. The algorithmic foundations of differential privacy. Foundations and trends® in theoretical computer science 9, 3-4 (2014), 211–487. [7] Shuya Feng, Meisam Mohammady, Han Wang, Xiaochen Li, Zhan Qin, and Yuan Hong. 2024. Dpi: Ensuring strict differential privacy for infinite data streaming. In 2024 IEEE Symposium on Security and Privacy (SP). IEEE, 1009–1027. [8] Dongqi Fu, Wenxuan Bao, Ross Maciejewski, Hanghang Tong, and Jingrui He. 2023. Privacy-preserving graph machine learning from data to computation: A survey. ACM SIGKDD Explorations Newsletter 25, 1 (2023), 54–72. [9] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. 2020. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems 33 (2020), 22118–22133. [10] Liya Ma, Siqi Sun, Chen Li, Lu Liu, and Lihong Wang. 2026. A novel dynamic graph generative adversarial network with edge-level differential privacy. Neurocomputing 676 (2026), 132926. [11] Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. 2000. Automating the construction of internet portals with machine learning. Information Retrieval 3, 2 (2000), 127–163. [12] Ilya Mironov. 2017. Rényi differential privacy. In 2017 IEEE 30th computer security foundations symposium (CSF). IEEE, 263–275. [13] Anirban Mitra and Subrata Paul. 2025. Analyzing social networks with dynamic graphs: Unravelling the ever-evolving connections. In Applied Graph Data Science. Elsevier, 195–214. [14] Tamara T Mueller, Dmitrii Usynin, Johannes C Paetzold, Daniel Rueckert, and Georgios Kaissis. 2022. SoK: Differential privacy on graph-structured data. arXiv preprint arXiv:2203.09205 (2022). [15] Sudipta Paul, Julián Salas, and Vicenç Torra. 2023. Edge local differential privacy for dynamic graphs. In International Symposium on Security and Privacy in Social Networks and Big Data. Springer, 224–238. [16] Yuxin Qi, Xi Lin, Ziyao Liu, Gaolei Li, Jingyu Wang, and Jianhua Li. 2024. Linkguard: Link locally privacy-preserving graph neural networks with integrated denoising and private learning. In Companion Proceedings of the ACM Web Conference 2024. 593–596. [17] Xun Ran, Qingqing Ye, Haibo Hu, Xin Huang, Jianliang Xu, and Jie Fu. 2024. Differentially private graph neural networks for link prediction. In 2024 IEEE 40th International Conference on Data Engineering (ICDE). IEEE, 1632–1644.

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

[18] Sofya Raskhodnikova and Adam Smith. 2016. Differentially private analysis of graphs. Encyclopedia of Algorithms (2016). [19] Sofya Raskhodnikova and Teresa Anna Steiner. 2025. Fully dynamic algorithms for graph databases with edge differential privacy. Proceedings of the ACM on Management of Data 3, 2 (2025), 1–28. [20] Sina Sajadmanesh and Daniel Gatica-Perez. 2021. Locally private graph neural networks. In Proceedings of the 2021 ACM SIGSAC conference on computer and communications security. 2130–2145. [21] Sina Sajadmanesh and Daniel Gatica-Perez. 2024. Progap: Progressive graph neural networks with differential privacy guarantees. In Proceedings of the 17th ACM International Conference on Web Search and Data Mining. 596–605. [22] Sina Sajadmanesh, Ali Shahin Shamsabadi, Aurélien Bellet, and Daniel GaticaPerez. 2023. { GAP } : Differentially private graph neural networks with aggregation perturbation. In 32nd USENIX Security Symposium (USENIX Security 23). 3223–3240. [23] Vedran Sekara, Arkadiusz Stopczynski, and Sune Lehmann. 2016. Fundamental structures of dynamic social networks. Proceedings of the national academy of sciences 113, 36 (2016), 9977–9982. [24] Josh Smith, Hassan Jameel Asghar, Gianpaolo Gioiosa, Sirine Mrabet, Serge Gaspers, and Paul Tyler. 2021. Making the most of parallel composition in differential privacy. arXiv preprint arXiv:2109.09078 (2021). [25] Li Sun, Zhongbao Zhang, Feiyang Wang, Pengxin Ji, Jian Wen, Sen Su, and Philip S Yu. 2022. Aligning dynamic social networks: An optimization over dynamic graph autoencoder. IEEE Transactions on Knowledge and Data Engineering 35, 6 (2022), 5597–5611. [26] Yuanfu Sun, Zhengnan Ma, Yi Fang, Jing Ma, and Qiaoyu Tan. 2025. Graphicl: Unlocking graph learning potential in llms through structured prompt design. In Findings of the Association for Computational Linguistics: NAACL 2025. 2440–2459. [27] Jiabin Tang, Yuhao Yang, Wei Wei, Lei Shi, Lixin Su, Suqi Cheng, Dawei Yin, and Chao Huang. 2024. Graphgpt: Graph instruction tuning for large language models. In Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval. 491–500. [28] Jean-Philippe Vert and Yoshihiro Yamanishi. 2004. Supervised graph inference. Advances in neural information processing systems 17 (2004). [29] Duo Wang, Yuan Zuo, Fengzhi Li, and Junjie Wu. 2024. Llms as zero-shot graph learners: Alignment of gnn representations with llm token embeddings. Advances in neural information processing systems 37 (2024), 5950–5973. [30] Yue Wang, Xintao Wu, and Donghui Hu. 2016. Using randomized response for differential privacy preserving data collection.. In EDBT/ICDT Workshops, Vol. 1558. 0090–6778. [31] Ruofan Wu, Mingyang Zhang, Lingjuan Lyu, Xiaolong Xu, Xiuquan Hao, Xinyi Fu, Tengfei Liu, Tianyi Zhang, and Weiqiang Wang. 2023. Privacy-preserving design of graph neural networks with applications to vertical federated learning. arXiv preprint arXiv:2310.20552 (2023). [32] Shitao Xiao, Zheng Liu, Peitian Zhang, and Niklas Muennighoff. 2023. C-Pack: Packaged Resources To Advance General Chinese Embedding. arXiv:2309.07597 [cs.CL] [33] Jian Xu, Chao Yu, Jiawei Xu, Vetle I Torvik, Jaewoo Kang, Mujeen Sung, Min Song, Yi Bu, and Ying Ding. 2025. PubMed knowledge graph 2.0: Connecting papers, patents, and clinical trials in biomedical science. Scientific data 12, 1 (2025), 1018. [34] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2018. How powerful are graph neural networks? arXiv preprint arXiv:1810.00826 (2018). [35] Yuanyuan Zeng, Yixiang Fang, Kun Chen, Yangfan Li, and Chenhao Ma. 2025. Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs. Proceedings of the VLDB Endowment 18, 7 (2025), 2005–2017. [36] Dalong Zhang, Xianzheng Song, Zhiyang Hu, Yang Li, Miao Tao, Binbin Hu, Lin Wang, Zhiqiang Zhang, and Jun Zhou. 2023. InferTurbo: A scalable system for boosting full-graph inference of graph neural network over huge graphs. In 2023 IEEE 39th International Conference on Data Engineering (ICDE). IEEE, 3235–3247. [37] Qiuchen Zhang, Hong kyu Lee, Jing Ma, Jian Lou, Carl Yang, and Li Xiong. 2024. Dpar: Decoupled graph neural networks with node-level differential privacy. In Proceedings of the ACM Web Conference 2024. 1170–1181.

A

Proofs

Proof for Lemma 3.1. Neighboring graphs differ in one undirected edge 𝑒 ★ = {𝑢 ★, 𝑣 ★ }. Each pair’s bit is perturbed by Eq. (5) at most once, and the likelihood ratio of the two-point RR channel is bounded by 𝑒 𝜀RR , giving pure 𝜀 RR -DP for the calibration release. For the joint statement: since ℎ is graph-independent, 𝑒 ★ lies in exactly one of Ptrain , Pfus . If 𝑒 ★ ∈ Ptrain , the calibration bits are identically distributed under both graphs and the PMA transcript is (𝜀 PMA, 𝛿)DP by Theorem 3.3; if 𝑒 ★ ∈ Pfus , the PMA transcript is identically

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

Yuyang Xia, Ruixuan Liu, and Li Xiong

distributed (the pair is excluded from all adjacency matrices) and the calibration release is (𝜀 RR, 0)-DP. Parallel composition over the disjoint partition yields the maximum of the two guarantees. □ Proof for Theorem 3.3. Since each edge enters the buffer 𝑀 exactly once and is drained exactly once, the batches {𝐵𝑚 }𝑚=0 are disjoint by construction. Consider two neighboring dynamic graphs 𝐷 and 𝐷 ′ that differ in one undirected edge 𝑒 ★ = {𝑢 ★, 𝑣 ★ }, and let 𝑚★ be the unique retrain with 𝑒 ★ ∈ 𝐵𝑚★ . We decompose the transcript into three segments and compare their conditional distributions under 𝐷 and 𝐷 ′ . Before 𝑚★. For 𝑚 < 𝑚★, the computation accesses only batches disjoint from {𝑒 ★ }, so (𝑌0, . . . , 𝑌𝑚★ −1 ) has identical distribution under 𝐷 and 𝐷 ′ . At 𝑚★. All features consumed at retrain 𝑚★—the cached aggregations carried over from previous retrains, and the lower-hop (𝑘 −1) features Z̄new finalized earlier within the same retrain—are deterministic functions of the transcript released so far. Conditional on that transcript, the only fresh access to 𝐵𝑚★ at hop 𝑘 is the multipli(𝑚★ ) in Eq. (6), whose ℓ -sensitivity to one undirected cation by 2 √ ΔA edge is 2: removing {𝑢 ★, 𝑣 ★ } changes the rows of 𝑢 ★ and 𝑣 ★, each by at most one unit-norm vector. Hence 𝑌𝑚★ , conditional on the prefix, is a sequence√of 𝐾 adaptively composed Gaussian mechanisms with sensitivity 2 and scale 𝜎—exactly the mechanism structure of one static 𝐾-hop PMA invocation with respect to the edge 𝑒 ★. After 𝑚★. For 𝑚 > 𝑚★, the raw edge 𝑒 ★ is never re-accessed: later retrains touch only batches disjoint from {𝑒 ★ } and otherwise depend on 𝑒 ★ solely through the already-released transcript. These segments are therefore (randomized) post-processing with respect to 𝑒 ★ and incur no additional privacy loss. Consequently, for any pair of neighboring graphs, the privacy loss of the full transcript is exactly that of a single static 𝐾-hop PMA invocation with noise scale 𝜎. Any (𝜖PMA, 𝛿)-DP guarantee certified for static PMA therefore transfers verbatim to 𝑌0:𝑀 , for every 𝑀 and every retraining schedule. □ (𝑘 ) Proof of Theorem 3.4. Let I𝑚 denote the noiseless hop-𝑘

cache after retrain 𝑚. By Steps (2)–(3) of the algorithm with the noise omitted, the caches obey (𝑘 ) (𝑘 ) (𝑘 −1) I𝑚 = I𝑚−1 + A𝑚 I𝑚 ,

(0) I𝑚 = Z for all 𝑚,

(9)

since Z̄ (0) depends only on node text, and hop 𝑘 multiplies the delta adjacency by the finalized hop-(𝑘−1) features of the current retrain. We prove (8) by induction on (𝑚, 𝑘) in lexicographic order. For 𝑚 = 0, the initial retrain runs full PMA on 𝐵 0 , so I0(𝑘 ) = A0𝑘 Z, the unique (trivially non-decreasing) length-𝑘 word over {0}. For 𝑘 = 0, both sides equal Z (the empty path). For the inductive step, assume the claim for (𝑚 − 1, 𝑘) and (𝑚, 𝑘 − 1). In (9), the first term is the sum over all non-decreasing paths with indices in {0, . . . , 𝑚 − 1}, i.e., those with 𝑖𝑘 ≤ 𝑚 − 1; the second term equals ∑︁ ∑︁ A𝑚 A𝑖𝑘 −1 · · · A𝑖 1 Z = A𝑖𝑘 · · · A𝑖 1 Z, 0≤𝑖 1 ≤···≤𝑖𝑘 −1 ≤𝑚

0≤𝑖 1 ≤ ··· ≤𝑖𝑘 ≤𝑚 𝑖𝑘 =𝑚

exactly the non-decreasing paths with 𝑖𝑘 = 𝑚 (the constraint 𝑖𝑘 −1 ≤ 𝑚 is automatic). The two index sets are disjoint and their union

is the set of all non-decreasing paths over {0, . . . , 𝑚}, proving (8).
𝑘 Í Expanding F (𝑘 ) = 𝑖 ≤𝑚 A𝑖 Z yields all length-𝑘 paths. For a single retrain (Anew = Aold + ΔA, i.e., 𝑚 = 1 with A0 = Aold and A1 = ΔA), (8) specializes to I (𝑘 ) =

𝑘 ∑︁

𝑘 −𝑖 ΔA 𝑖 Aold Z,

(10)

𝑖=0

the paths in which every old-edge step precedes every new-edge 𝑘 Z for the cached aggregation, the error step. Writing C (𝑘 ) = Aold (𝑘 ) (𝑘 ) (𝑘 ) D = F − I collects all remaining paths—those containing at least one old-edge step after a new-edge step—and obeys the recursion
D (𝑘 ) = Aold F (𝑘 −1) − C (𝑘 −1) + ΔA D (𝑘 −1) , D (1) = 0. (11) The first term of (11) exposes the source of the error: it is Aold propagating the staleness of the cache—new edges always aggregate up-to-date features, but old edges, frozen in the cache, never reaggregate features that were refreshed by later insertions. □ Proof of Corollary 3.5. For 𝑘 = 1, every length-1 word is Í trivially non-decreasing, so by Theorem 3.4, I (1) = 𝑏 ≤𝑚 A𝑏 Z = (1) Anew Z = F . □ Proof of Corollary 3.6. A wedge with
edges 𝑒 1, 𝑒 2
carries two transfers, corresponding to the paths 𝑒 1, 𝑒 2 and 𝑒 2, 𝑒 1 . If the two edges were inserted in the same batch, or both lie in E (0) —then both paths are non-decreasing, and both transfers are captured by Theorem 3.4. If the two edges were inserted in different batches, then one edge is necessarily older than the other and exactly one path (older edge first) is non-decreasing: 50%. Hence the captured fraction is (1 − 𝜌) · 1 + 𝜌 · 12 = 1 − 12 𝜌 ≥ 12 . For a single retrain, this recovers D (2) = Aold ΔA Z from (11): the traversal crossing the old edge first is captured (ΔA Aold Z appears in (10)), while the traversal crossing the new edge first is lost. □ Proof of Proposition 3.7. The initial retrain injects one draw of N (0, 𝜎 2 I) per hop (Eq. (4)), and each of the 𝑀 subsequent retrains injects one fresh draw per hop via Eq. (8), accumulated additively into the cache by Eq. (9). The 𝑀+1 draws are mutually independent, so their variances sum to (𝑀+1)𝜎 2 . By Theorem 3.3, parallel composition over disjoint batches lets every incremental retrain use the full per-invocation noise scale 𝜎; a one-shot full PMA on the final graph at the same (𝜖PMA, 𝛿) calibrates√to the same 𝜎 but perturbs each hop with a single draw, giving the 𝑀+1 inflation in noise magnitude at identical privacy cost. At hop 1, the noiseless aggregations coincide by Corollary 3.5, so the deviation from the one-shot release is exactly this injected noise. For the geometrically decaying baseline, the Gaussian noise scale required for budget 𝜖𝑚
= (1 − 𝑞)𝑞
𝑚 𝜖tot at fixed 𝛿 satisfies 𝜎𝑚 ∝ 1/𝜖𝑚 = 𝑞 −𝑚 / (1 − 𝑞)𝜖tot = Θ 𝑞 −𝑚 ; and because that baseline re-runs full PMA, the entire representation released at retrain 𝑚 is perturbed at scale 𝜎𝑚 , so utility collapses exponentially fast in the number of retrains. □

B

LLM Prompt Templates

This appendix documents all LLM prompt templates used in our experiments. We use zero-shot prompting with logit-based scoring: the LLM computes log-probabilities over candidate answer tokens

PriDyG: Privacy-preserving Dynamic Graph Inference with LLM-GNN Collaboration

(e.g., category names or “Yes”/“No”), and the candidate with the highest probability is selected. All prompts follow a consistent structure tailored to each task and dataset.

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

ogbn-arxiv Node Classification Prompt Classify this computer science paper into exactly one arXiv category. Title: {title} Abstract: {abstract} Categories: 0: cs.AI (Artificial Intelligence) 1: cs.AR (Hardware Architecture) 2: cs.CC (Computational Complexity) ... 39: cs.SY (Systems and Control) Output ONLY the integer label id from the candidate list. Do not output anything else. Answer:

B.1

Node Classification Prompts Cora Node Classification Prompt You are a scientific paper classification assistant. Choose the single best paper category for this paper. Paper title: {title}

The full list of 40 arXiv CS subcategories used as candidates is shown in Table 10.

Paper abstract: {abstract} Choose the single best paper category for this paper from the candidate list. Candidates: Case Based: Papers on case-based reasoning, instance-based learning, and analogy-driven problem solving. Genetic Algorithms: Papers on evolutionary computation, genetic programming, and optimization via natural selection. Neural Networks: Papers on artificial neural networks, deep learning, backpropagation, and connectionist models. Probabilistic Methods: Papers on Bayesian methods, graphical models, expectation-maximization, and statistical inference. Reinforcement Learning: Papers on reward-based learning, policy optimization, Markov decision processes, and Q-learning. Rule Learning: Papers on inductive logic programming, decision rules, association rules, and symbolic rule extraction. Theory: Papers on computational learning theory, PAC learning, VC dimension, and formal analysis of algorithms. Output ONLY the category name from the candidate list. Do not output anything else. Answer:

Table 10: arXiv CS subcategories used as candidate labels. Code

Description

Code

Description

cs.AI cs.AR cs.CC cs.CE cs.CG cs.CL cs.CR cs.CV cs.CY cs.DB cs.DC cs.DL cs.DM cs.DS cs.ET cs.FL cs.GL cs.GR cs.GT cs.HC cs.IR

Artificial Intelligence Hardware Architecture Computational Complexity Comp. Eng., Finance, & Sci. Computational Geometry Computation and Language Cryptography and Security Computer Vision & Pattern Rec. Computers and Society Databases Distributed & Parallel Comp. Digital Libraries Discrete Mathematics Data Structures & Algorithms Emerging Technologies Formal Lang. & Automata Th. General Literature Graphics CS and Game Theory Human-Computer Interaction Information Retrieval

cs.IT cs.LG cs.LO cs.MA cs.MM cs.MS cs.NA cs.NE cs.NI cs.OH cs.OS cs.PF cs.PL cs.RO cs.SC cs.SD cs.SE cs.SI cs.SY

Information Theory Machine Learning Logic in Computer Science Multiagent Systems Multimedia Mathematical Software Numerical Analysis Neural & Evolutionary Comp. Networking & Internet Arch. Other Computer Science Operating Systems Performance Programming Languages Robotics Symbolic Computation Sound Software Engineering Social & Info. Networks Systems and Control

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

PubMed Node Classification Prompt

Link Prediction Prompt – Citation Networks

You are a biomedical paper classification assistant. Choose the single best diabetes category for this paper. Paper title: {title}

You are an expert in analyzing {context}. Given the descriptions of two papers below, determine whether they are likely to cite each other (i.e., one paper references the other).

Paper abstract: {abstract}

Paper A: {description of paper A}

Choose the single best diabetes category for this paper from the candidate list. Candidates: Diabetes Mellitus, Experimental Diabetes Mellitus, Type 1 Diabetes Mellitus, Type 2

Paper B: {description of paper B}

Output ONLY the category name from the candidate list. Do not output anything else. Answer:

Based on the content similarity and topical relevance, are these two papers likely to cite each other (i.e., one paper references the other)? Output ONLY 'Yes' or 'No'. Answer:

The {context} field is set to: • Cora: “academic papers in computer science (Cora citation network)” • ogbn-arxiv: “academic papers from arXiv (OGB-arxiv citation network)” • PubMed: “biomedical research papers from PubMed (citation network)”

ogbn-products Node Classification Prompt

Link Prediction Prompt – Co-purchasing Network

You are a product classification assistant. Choose the single best top-level product category for this Amazon product from the candidate list. Product title: {title} Product description: {content} Choose the single best top-level product category for the given product. Candidates: 0: Home & Kitchen 1: Health & Personal Care 2: Beauty ...

You are an expert in analyzing products from Amazon (co-purchasing network). Given the descriptions of two products below, determine whether they are likely to are frequently co-purchased together.

Output ONLY the integer label id from the candidate list. Do not output anything else. Answer:

B.2

Yuyang Xia, Ruixuan Liu, and Li Xiong

Link Prediction Prompts

For link prediction, we use a unified prompt template parameterized by dataset-specific context. The LLM scores the log-probabilities of “Yes” and “No” tokens, and we use 𝑃 (Yes) as the link likelihood score.

Product A: {description of product A} Product B: {description of product B} Based on the content similarity and topical relevance, are these two products likely to are frequently co-purchased together? Output ONLY 'Yes' or 'No'. Answer:

Related documents

• EdgeRefine: Privacy-Utility Balance for Graphs via Jaccard Sampling under Edge Differential Privacy#353049
• Privacy-Preserving Logistic Regression Training with A Faster Gradient Variant#144165
• Privacy, Prediction, and Allocation#31218
• Privacy Leakage via Output Label Space and Differentially Private Continual Learning#163068
• Trust-Aware Adaptive Disclosure for Inference Privacy Preservation in Multi-Agent Networks#660737