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

2026-07-09 · Source: Machine Learning · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Cybersecurity & Data Privacy · Depth: Expert, quick

Summary

EdgeRefine is a novel local differential privacy framework designed to enhance the privacy-utility balance for Graph Neural Networks (GNNs) operating on sensitive graph-structured data. It addresses the challenge of edge-level differential privacy, where traditional noise injection often compromises utility. EdgeRefine employs adaptive edge refinement, estimating edge-existence probabilities via Jaccard similarity to rank edges for noisy removal. It uses the privacy budget ε to determine the ratio of true to false edges, sampling them separately based on probability ranking, and controls total edge count with a sampling rate k. Experiments show EdgeRefine achieves accuracy comparable to noise-free baselines and significantly outperforms other privacy-preserving methods. Under ε= 2.5, it improves node classification accuracy by 17.8% on ACM (GAT) and 19.7% on Cora (GCN) over baselines. Graph classification shows an average accuracy degradation of only 5% compared to noise-free. It also maintains strong resilience against graph reconstruction attacks, with relative absolute error levels above 1, averaging 1.962 on Cora and 1.472 on AMAP.

Key takeaway

For Machine Learning Engineers developing GNNs in privacy-sensitive domains, EdgeRefine offers a robust solution to the privacy-utility dilemma. You should consider integrating its Jaccard sampling and adaptive edge refinement to achieve strong edge-level differential privacy without severe accuracy degradation. This approach allows you to maintain high model performance, with reported improvements of up to 19.7% in node classification accuracy, while effectively mitigating graph reconstruction attack risks.

Key insights

Adaptive edge refinement using Jaccard similarity and privacy budget ε significantly improves privacy-utility trade-offs in graph differential privacy.

Principles

• Stronger privacy often requires more noise, reducing utility.
• Graph structure can leak sensitive link information.
• Balancing true and false edges is key for graph sparsity.

Method

EdgeRefine estimates edge-existence probabilities using Jaccard similarity, ranks edges for removal, then samples true and false edges separately based on ε and probability ranking, controlling total edges with sampling rate k.

In practice

• Apply Jaccard similarity for edge probability estimation.
• Use ε to control true/false edge ratios.
• Implement k for total edge count management.

Topics

• Graph Neural Networks
• Differential Privacy
• Edge Privacy
• Jaccard Similarity
• Graph Classification
• Node Classification

Best for: Research Scientist, AI Scientist, Machine Learning Engineer, AI Security Engineer

Related on AIssential

• Beyond Homophily: Towards Generalized Graph Reconstruction Attack and Defense — GNNs are vulnerable to graph reconstruction attacks, but a Markov chain approximation can inform both stronger attacks and effective defenses.
• Minimax Optimal Two-Sample Testing under Local Differential Privacy — Minimax optimal two-sample tests under LDP are developed for multinomial and continuous data.
• Community Concealment from Unsupervised Graph Learning-Based Clustering — Community concealment in GNNs depends on boundary connectivity and feature similarity, mitigated by targeted perturbations.
• Differentially Private Natural Gradient Descent — DP-NGD improves differentially private training utility and convergence by integrating curvature-aware optimization while mitigating privacy and stability challenges.
• Classification Under Local Differential Privacy with Model Reversal and Model Averaging — Reinterpreting LDP as transfer learning improves classification utility by inverting and averaging noisy models.
• A Van Trees Lower Bound for Fully Interactive Differentially Private Federated Learning — A general federated van Trees lower bound quantifies privacy-utility trade-offs in interactive differentially private federated learning.

See Counsel's argued verdicts on the open AI decisions leaders are weighing →

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by Machine Learning.