This work proposes EdgeRefine, a local differential privacy framework that improves this trade-off through adaptive edge refinement and substantially outperforms other privacy-preserving methods across datasets and GNN architectures.
Abstract
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.
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.
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.
This survey presents the first comprehensive and systematic review of Differentially Private Graph Learning (DPGL), and organizes existing DPGL methods into four categories based on the granularity of privacy protection, namely node-level, edge-level, graph-level, and node-level.
This work provides theoretical guarantees for the selective blocking rule by deriving the signed-versus-blocked decision boundary, separating signed-matrix effects from nonnegative block-operator spectral arguments, and showing when adaptive blocking preserves class-dependent components.
Jiho Choi, Yumin Lee, Chanran Kim et al.· ACM Transactions on Intellig...· 0 citations
Subgraph Filtering for Fair Graph Neural Networks is proposed, a lightweight and architecture-agnostic framework that mitigates structural bias at its source and achieves consistent fairness improvements while maintaining competitive predictive performance, leading to a better fairness--accuracy trade-off than recent fairness-aware GNN baselines.
Haohui Lu, Ji-Yuan Tian, Fangyu Zhou et al.· 0 citations
Graph unlearning removes the influence of sensitive edges and nodes from trained Graph Neural Networks (GNNs) without full retraining, which is essential for privacy protection. However, existing graph unlearning methods do not account for the heterogeneity of positive and negative edges in signed graphs, thereby degrading both model utility and unlearning effectiveness when applied to widespread signed graph applications. To fill this research gap, we propose Certified Signed Graph Unlearning (CSGU), which leverages the sociological principles underlying signed graphs, providing provable privacy guarantees while maintaining model utility. Specifically, CSGU efficiently identifies minimal influenced neighborhoods via triangular structures, and then applies sociological theories to quantify edge influence. Subsequently, it performs influence-weighted parameter updates with calibrated noise injection to achieve certified privacy guarantees with minimal utility degradation. Extensive experiments across five datasets show that CSGU outperforms four competing graph unlearning methods on four GNN architectures in most settings, achieving state-of-the-art results in both utility preservation and unlearning effectiveness.
Junpeng Zhao, Lin Li, Yu Yang et al.· Proceedings of the 32nd ACM...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
