EdgeRefine: Privacy-Utility Balance for Graphs via Jaccard Sampling under Edge Differential Privacy

Graph Neural Networks (GNNs) have shown considerable success in learning from graph-structured data. However, their application in privacy-sensitive areas remains difficult as the structural information of graphs is prone to leaking sensitive link information. To satisfy edge-level differential privacy, a common approach is to directly inject noise into all elements of the graph's adjacency matrix, thereby obfuscating the existence of any single edge. While increased noise strengthens privacy protection, excessive noise reduces utility. Privacy-utility balance becomes a major barrier to practical privacy-preserving graph learning. To address this issue, we propose EdgeRefine, a new local differential privacy framework that rethinks the privacy-utility trade-off in graph learning through adaptive edge refinement. EdgeRefine first estimates edge-existence probabilities using Jaccard similarity and ranks edges accordingly for noisy edge removal. To ensure the sparsity and reliability of the final graph, we leverage the privacy budget 𝜖 to determine the ratio of true to false edges, sample them separately based on the previously obtained probability ranking, and then control the total number of edges with a separate sampling rate 𝑘. We conducted extensive experiments to evaluate the effectiveness of EdgeRefine, which achieves accuracy comparable to the noise-free baseline and performs much better than other privacy-preserving methods on various datasets and GNN architectures. Under privacy budget 𝜖 = 2.5, EdgeRefine achieves significant node classification accuracy improvements over state-of-the-art baselines: 17.8% on ACM under GAT and 19.7% on Cora under GCN. In graph classification task, an average accuracy degradation of around 5% has also been achieved compared to noise-free baseline. Under graph reconstruction attacks, EdgeRefine maintains relative absolute error levels consistently above 1 across all privacy budgets (averaging 1.962 on Cora and 1.472 on AMAP), indicating strong resilience against privacy leakage. CCS Concepts • Security and privacy; • Computing methodologies → Machine learning; • Theory of computation → Graph algorithms analysis;