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

arXiv: https://arxiv.org/abs/2608.04255 · HTML: https://mlsanity.com/paper/2608.04255/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 42 references that are in the map.
- First posted on arXiv 4 Aug 2026.

## Builds on (most cited first, 15 of 15)

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Exploring the Potential of Large Language Models (LLMs) in Learning on Graphs](https://mlsanity.com/paper/2307.03393/) (2023)
- [Reinforcement learning](https://mlsanity.com/paper/2405.10369/) (2024)
- [Locally Private Graph Neural Networks](https://mlsanity.com/paper/2006.05535/) (2020)
- [GAP: Differentially Private Graph Neural Networks with Aggregation Perturbation](https://mlsanity.com/paper/2203.00949/) (2022)
- [GraphICL: Unlocking Graph Learning Potential in LLMs through Structured Prompt Design](https://mlsanity.com/paper/2501.15755/) (2025)
- [ProGAP: Progressive Graph Neural Networks with Differential Privacy Guarantees](https://mlsanity.com/paper/2304.08928/) (2023)
- [Making the Most of Parallel Composition in Differential Privacy](https://mlsanity.com/paper/2109.09078/) (2021)
- [Privacy-Preserving Graph Machine Learning from Data to Computation: A Survey](https://mlsanity.com/paper/2307.04338/) (2023)
- [PubMed knowledge graph 2.0: Connecting papers, patents, and clinical trials in biomedical science](https://mlsanity.com/paper/2410.07969/) (2024)
- [Fundamental structures of dynamic social networks](https://mlsanity.com/paper/1506.04704/) (2015)
- [InferTurbo: A Scalable System for Boosting Full-graph Inference of Graph Neural Network over Huge Graphs](https://mlsanity.com/paper/2307.00228/) (2023)
- [DPI: Ensuring Strict Differential Privacy for Infinite Data Streaming](https://mlsanity.com/paper/2312.04738/) (2023)

## Abstract (arXiv)

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.