EdgeRefine uses Jaccard sampling to balance privacy and utility in graph learning

Researchers propose EdgeRefine, a local differential privacy framework that improves the privacy-utility trade-off for Graph Neural Networks through adaptive edge refinement. The method estimates edge-existence probabilities using Jaccard similarity and ranks edges for noisy removal, using the privacy budget to control the ratio of true to false edges.

• EdgeRefine samples true and false edges separately based on probability ranking and controls total edge count with a sampling rate k.
• Under a privacy budget of ε=2.5, it improves node classification accuracy by 17.8% on ACM (GAT) and 19.7% on Cora (GCN) compared to state-of-the-art baselines.
• Graph classification shows an average accuracy degradation of only around 5% compared to noise-free baselines.
• The method maintains strong resilience against graph reconstruction attacks, with relative absolute error levels averaging 1.962 on Cora and 1.472 on AMAP.

EdgeRefine achieves accuracy comparable to noise-free baselines while substantially outperforming other privacy-preserving methods across datasets and GNN architectures.