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.
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.
With the widespread adoption of graph-structured data, protecting the complex relational information between nodes and edges while preventing sensitive information leakage has become a critical challenge. However, existing edge protection methods either introduce noise directly into the adjacency matrix, resulting in significant information loss, or uniformly apply noise across all edges, leading to imbalanced privacy budget allocation and inefficiency. To address these issues, we propose DPEI, a Differential Privacy-based Edge Information protection solution designed to safeguard the edge relationships between two nodes, thus reducing the risk of privacy leakage and preventing attackers from repeatedly inferring internal community relationships from the released graph data. Specifically, DPEI achieves protection through PPO (Proximal Policy Optimization)based selection of locally optimal thresholds combined with adaptive Laplace noise operations, and attachment nodes below the threshold into high-information edges to enhance relational information protection. Subsequently, unlike traditional uniform allocation, DPEI distributes the privacy budget in proportion to the information content of each edge, ensuring that edges with higher information content receive stronger privacy protection. Extensive experiments conducted on three real-world graph datasets demonstrate that DPEI significantly outperforms existing methods across seven commonly used graph metrics, thereby validating its effectiveness and practicality.
Graph Neural Networks (GNNs) have shown considerable success in learning from graph-structured data, but their use in privacy-sensitive areas remains difficult because graph structure can leak sensitive link information. To satisfy edge-level differential privacy, a common approach is to inject noise into all elements of the graph's adjacency matrix, thereby obfuscating the existence of any single edge. However, stronger privacy requires more noise, and excessive noise reduces utility, making the privacy-utility balance a major barrier to practical privacy-preserving graph learning. To address this issue, we propose EdgeRefine, a local differential privacy framework that improves this trade-off through adaptive edge refinement. EdgeRefine first estimates edge-existence probabilities using Jaccard similarity and ranks edges for noisy edge removal. To ensure the sparsity and reliability of the final graph, it uses the privacy budget $\epsilon$ to determine the ratio of true to false edges, samples them separately based on this probability ranking, and controls the total number of edges with a separate sampling rate $k$. Extensive experiments show that EdgeRefine achieves accuracy comparable to the noise-free baseline and substantially outperforms other privacy-preserving methods across datasets and GNN architectures. Under privacy budget $\epsilon = 2.5$, EdgeRefine improves node classification accuracy over state-of-the-art baselines by 17.8\% on ACM under GAT and 19.7\% on Cora under GCN. In graph classification, it achieves an average accuracy degradation of around 5\% compared to the noise-free baseline. Under graph reconstruction attacks, EdgeRefine maintains relative absolute error levels above 1 across all privacy budgets, averaging 1.962 on Cora and 1.472 on AMAP, indicating strong resilience against privacy leakage.
Wenxiu Ding, Muzhi Liu, Zheng Yan et al.· 0 citations
PPGNN, a personalized differentially private framework for decentralized graph data, enables user-specific privacy budgets during local perturbation while preserving analytical utility in decentralized graph learning scenarios.
Longzhu He, Peng Tang, Chaozhuo Li et al.· IEEE Transactions on Knowled...· 0 citations
Deploying outsourced graph neural network (GNN) inference services in the cloud is gaining widespread application across various fields, such as fraud detection and social network analysis. Cloud servers utilize outsourced model to analyze the graph data of data owners, enabling data owners to enjoy high-quality GNN inference services. However, this approach leads to privacy concerns regarding GNN models, graph data and inference results. To address the privacy issues, some privacy-preserving GNN inference schemes have been proposed. But the existing schemes are only applicable to graph convolutional network and not to graph attention network (GAT) with stronger expressive power. Therefore, we propose a secure GAT inference scheme (SecGAT) for outsourcing scenarios. First, we represent the Beaver triple-based multiplication process as a two-phase multiplication, which allows us to combine specific algorithms to optimize the communication overhead. Then, we design a graph data encryption method to protect the privacy of outsourced graph data. Finally, we propose a series of customized algorithms for secure GAT inference. Based on the proposed building blocks, we construct a complete GAT inference process. Rigorous security analysis and extensive evaluations demonstrate the effectiveness of our scheme. By comparing the core algorithms, our scheme can improve computational efficiency by more than 20% and reduce communication overhead by 20%−40% compared to existing schemes.
Ruoli Zhao, Hui Zhu, Yandong Zheng et al.· IEEE Transactions on Network...· 0 citations
A systematic evaluation of privacy risks in LLM-enhanced GNNs through a unified framework consisting of five stages and reveals that semantic enrichment amplifies link-, label-, and membership-related signals in the embedding space, making them more exploitable by inference attacks.
Longzhu He, Zekun Wen, Chaozhuo Li et al.· 0 citations
It is proved that sufficiently parameterized RGNNs contain sparse subnetworks that maintain 1-RWL expressivity and derive a lower bound on the probability that a random pruning yields such a subnetwork.
Lorenz Kummer, Samir Moustafa, Anatol Ehrlich et al.· 0 citations