🤖 machine learning

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

PriDyG is a privacy-preserving framework for dynamic graph inference that combines GNN-based structural learning with LLM-based semantic reasoning to achieve edge-level differential privacy with constant cumulative cost, significantly outperforming existing baselines in utility while mitigating privacy loss accumulation.

Original authors: Yuyang Xia, Ruixuan Liu, Li Xiong

Published 2026-08-06

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Yuyang Xia, Ruixuan Liu, Li Xiong

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine the internet as a giant, ever-changing map of connections. Some lines on this map are friendships, others are financial trades, and some are secret medical consultations. This map is called a "graph," and computers use it to make predictions, like guessing who you might want to be friends with or what product you'll buy next. But here's the catch: if you ask a computer to study this map too closely, it might accidentally reveal those secret lines, exposing private relationships. To stop this, scientists use a mathematical shield called "Differential Privacy." Think of it like adding a little bit of static noise to a radio signal; it makes the signal just fuzzy enough that no one can hear a specific secret, but clear enough to still understand the general music.

The problem gets trickier when the map keeps changing. In the real world, new friendships form and new transactions happen every second. If a computer tries to update its predictions every time a new line is drawn, it has to look at the whole map again and again. Every time it looks, the privacy shield gets a little weaker, and the noise gets a little louder, until the predictions become useless garbage. This paper tackles the big question: How can we keep updating our predictions on a changing map without running out of privacy or drowning in noise?

The authors of this paper, Yuyang Xia, Ruixuan Liu, and Li Xiong, propose a clever new system called PriDyG. Instead of trying to force the computer to re-scan the entire messy map every time a single new line appears, they built a two-part team. One part is a "structural detective" (a Graph Neural Network) that looks at the connections, and the other is a "semantic reader" (a Large Language Model) that reads the text descriptions of the people or items involved.

Here is how their magic trick works. The "structural detective" is the one that needs the privacy shield because it looks at the secret connections. Usually, every time the map changes, this detective has to re-examine the whole thing, which burns through the privacy budget and adds so much noise that it gets confused. PriDyG changes the game by using a "buffer" system. Instead of re-reading the whole map, the system just looks at the new lines that arrived since the last check. It calculates the difference and adds it to the old answer, like updating a scorecard by just adding the new points rather than recounting the whole game. This means the privacy cost stays the same no matter how many times the map updates.

However, this "difference" method isn't perfect; it misses some very complex, long-distance connections that a full re-scan would catch. That's where the second team member, the "semantic reader," comes in. This reader only looks at the public text descriptions (like a person's bio or a product's description) and ignores the secret connections entirely. Because it doesn't touch the private data, it doesn't need any privacy budget at all! It acts as a safety net. When the structural detective gets too fuzzy or unsure because of the noise, the system leans more heavily on the semantic reader's opinion.

The paper shows that this team-up works incredibly well. In tests on four different datasets (including social networks and product catalogs), PriDyG managed to keep its predictions accurate even as the graph changed thousands of times. It proved that by combining a privacy-preserving structural update with a privacy-free text reader, you can maintain high accuracy without the privacy cost spiraling out of control. The authors found that this method is far better than older ways of trying to save privacy, which usually resulted in the computer getting so noisy that it couldn't make any useful predictions after a few updates. They demonstrated that their approach keeps the total privacy cost constant, regardless of how many updates happen, while still delivering results that are competitive with systems that don't use privacy protection at all.

Technical Summary: PriDyG

Problem Formulation

The paper addresses the challenge of Edge-level Differentially Private (DP) Dynamic Graph Inference (EDG). In dynamic graphs, where edges arrive continuously and models require frequent updates, existing privacy-preserving methods face two critical challenges:

Utility-Privacy Trade-off (Challenge 1): Enforcing edge-level DP requires injecting noise into neighborhood aggregation, which distorts the structural signals essential for Graph Neural Networks (GNNs), leading to significant accuracy degradation compared to non-private counterparts.
Privacy Budget Accumulation (Challenge 2): In dynamic settings, repeated model updates typically trigger sequential composition of privacy budgets. If a mechanism re-runs private aggregation on the entire graph for every update, the total privacy cost grows linearly ( $M \cdot \epsilon$ ) with the number of updates $M$ , quickly becoming prohibitive. Alternatively, allocating a geometrically decaying budget to successive updates keeps the total cost bounded but causes the noise scale to grow exponentially, rendering later models unusable.

The authors define the EDG problem as designing a mechanism that answers node classification and link prediction queries on an evolving graph while satisfying edge-level DP over the entire execution and maintaining high utility. Crucially, the threat model assumes node textual attributes are public, while only edge existence is protected.

Methodology: PriDyG

The authors propose PriDyG, a framework that couples LLM-based semantic reasoning with dynamic DP-GNN structural learning. The architecture operates via three main components:

1. LLM-GNN Collaborative Framework

PriDyG runs two complementary branches:

DP-GNN Branch: Learns structural representations under edge-level DP.
LLM Branch: Performs zero-shot classification or link scoring using only node textual attributes. Since node text is public under the threat model, this branch consumes zero privacy budget.
Confidence-Gated Fusion: The system dynamically fuses predictions. If the GNN prediction is confident (high margin), it is used directly. If uncertain, the system fuses the GNN output with the LLM's semantic prediction. This allows the system to rely on the stable, privacy-free LLM anchor as the GNN's structural accuracy erodes due to noise accumulation over time.

2. Incremental Private Multi-hop Aggregation (PMA)

To solve the budget accumulation problem, PriDyG introduces Incremental PMA, which replaces the approach of re-running full aggregation on the entire graph.

Mechanism: Newly arrived edges are buffered. When a retraining command is issued, the algorithm computes a "delta" aggregation based only on the new edges and adds this noisy delta to the cached aggregations from previous steps.
Privacy Guarantee: Because each edge is processed exactly once (when it is drained from the buffer), the Parallel Composition Theorem applies. The total privacy cost remains constant ( $\epsilon_{PMA}$ ), independent of the number of updates $M$ or the retraining schedule.
Signal Preservation:
- One-hop: The aggregation is signal-exact (lossless in the noiseless case).
- Multi-hop: The method retains at least half of all two-hop information transfers. It omits "backward-in-time" paths (where information flows from newer edges to older edges), but this error is structured and bounded, unlike the unbounded drift of other methods.
Noise Accumulation: While the privacy budget is constant, the noise variance grows linearly ( $O(M)$ ) with the number of updates. However, this is a polynomial growth, contrasting sharply with the exponential noise growth required by geometrically decaying budget baselines.

3. Link Prediction Adaptation

For link prediction, the default predictor uses cosine similarity on privatized PMA representations. To calibrate the fusion weights without violating edge-level DP, the authors use Randomized Response on a disjoint set of node pairs to generate privatized labels for tuning the fusion parameters ( $\alpha, \tau$ ).

Key Contributions

LLM-GNN Collaborative Framework: A unified pipeline that narrows the privacy-utility gap by compensating for privatized GNN utility loss with privacy-free LLM semantic reasoning.
Constant-Budget Dynamic Inference: The proposal of Incremental PMA, which achieves $O(1)$ total privacy cost under arbitrarily many model updates by exploiting the disjointness of edge batches, fundamentally resolving the budget tension in dynamic graph inference.
Comprehensive Evaluation: Extensive experiments on four benchmark datasets (Cora, PubMed, ogbn-arxiv, ogbn-products) for node classification and link prediction.

Results

Experiments demonstrate that PriDyG:

Consistently outperforms geometrically decaying budget baselines under the same total privacy budget.
Reduces the cumulative privacy cost by up to three orders of magnitude compared to per-update retraining approaches, while maintaining competitive utility.
Maintains stable accuracy over long insertion streams, whereas the GNN-only branch suffers substantial accuracy drops relative to static training due to noise accumulation.
Remains competitive with non-private baselines while providing formal edge-level DP guarantees.

Significance and Claims

The paper claims that PriDyG is the first work to formulate and study edge-level DP graph inference over continually updated graphs with the specific goal of ensuring privacy cost does not grow with the number of updates.

The authors emphasize that the LLM-GNN collaboration is not merely a generic accuracy boost but is specifically valuable in the dynamic regime. As the structural branch (GNN) becomes weaker due to accumulated noise, the pipeline naturally shifts reliance toward the stable, privacy-free LLM anchor. This design allows for frequent model updates without additional privacy degradation, addressing a critical bottleneck in real-world dynamic graph applications where data evolves continuously.