🤖 machine learning

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

EdgeRefine is a local differential privacy framework that optimizes the privacy-utility trade-off in graph learning by employing Jaccard similarity-based edge ranking and adaptive sampling to preserve graph structure while satisfying edge-level differential privacy, thereby significantly outperforming existing methods in node and graph classification tasks.

Original authors: Wenxiu Ding, Muzhi Liu, Zheng Yan, Mingjun Wang, Yifan Zhao, Qiao Liu

Published 2026-07-10

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Wenxiu Ding, Muzhi Liu, Zheng Yan, Mingjun Wang, Yifan Zhao, Qiao Liu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a secret map of a giant social network, like a web of who knows whom in a massive school. You want to share this map with a super-smart computer (a Graph Neural Network) so it can learn cool things, like predicting who will become friends next. But there's a catch: if you just hand over the map, the computer might figure out your secret connections, and that's a privacy disaster.

To stop this, you usually have to scramble the map by adding "noise"—like sprinkling glitter everywhere so the real paths get lost in the sparkles. This is called Differential Privacy. The problem is, if you add too much glitter, the map becomes a useless, blurry mess, and the computer can't learn anything. If you add too little, the secrets are still visible. Finding the perfect amount of glitter has been a nightmare for scientists.

Enter EdgeRefine, a new method that acts like a magical, super-smart filter for your noisy map.

The Problem with Old Filters

Previous methods tried to clean up the scrambled map in two ways that didn't quite work:

The "Guess and Keep" approach: Some methods looked at the noisy map and kept every connection that looked likely to be real. But this was like keeping every rumor in a school hallway just because it sounded plausible. It kept too many fake friends (noise) and ruined the map's structure.
The "Just Keep It Sparse" approach: Others tried to force the map to stay small by cutting out edges randomly. But this ignored the actual shape of the network, often chopping off real friendships just to keep the map small, leaving the computer confused.

The paper explicitly argues that these old ways fail to balance privacy and usefulness. They either leak secrets or destroy the map's value.

How EdgeRefine Works: The "Similarity Detective"

EdgeRefine changes the game by using a two-step process that feels less like random guessing and more like a detective solving a puzzle.

Step 1: The Glittery Map (Client Side)
First, the person holding the secret map adds the necessary privacy glitter (noise) to hide the real connections. This is done strictly so that no one can prove if two specific people were friends or not. This noisy map is sent to the server.

Step 2: The Detective Work (Server Side)
Here is where the magic happens. The server doesn't just guess which edges are real. Instead, it uses a tool called Jaccard Similarity. Think of this as a "friend-of-a-friend" detector.

Imagine two students, Alex and Sam. They might not be friends, but if they both know 10 of the same other people, they probably should be friends.
EdgeRefine calculates this "overlap score" for everyone. Even though the map is covered in glitter, the pattern of who knows whom usually stays somewhat visible.
The system groups these scores into buckets (like sorting marbles by size) to estimate how likely a connection is to be real.

Step 3: The Precision Filter (Sampling)
Now comes the clever part. The system knows exactly how much privacy "budget" (a number called $\epsilon$ ) was used. It uses this number to calculate the perfect ratio of real edges to fake edges.

It doesn't just pick the "most likely" edges randomly. It deterministically picks the top-ranked real edges and the top-ranked fake edges to fill the map.
It acts like a strict bouncer at a club: "We need exactly 1,000 people in here. We will let in the top 800 people who look like they belong (real edges) and the top 200 who might belong but were kicked out (fake edges), based on our strict rules."
This ensures the map stays the right size (sparse) and doesn't get clogged with too much noise.

The Results: A Map That Actually Works

The authors tested EdgeRefine on real-world data, including citation networks (like academic papers) and social networks. Here is what they found:

Accuracy: On a dataset called ACM, when the privacy budget was set to $\epsilon = 2.5$ , EdgeRefine improved the computer's accuracy by 17.8% compared to the best previous method (Blink). On the Cora dataset, it improved accuracy by 19.7%.
Stability: The results were incredibly steady. While other methods jumped around wildly (like a shaky hand drawing a line), EdgeRefine's performance was smooth, with very low variance (as low as 0.0001 on some tests).
Privacy: The system is tough against hackers trying to reconstruct the original map. Even when attackers tried to reverse-engineer the data, the error rate stayed high (Relative Absolute Error above 1.0, averaging 1.962 on Cora), meaning the attack performed no better than random guessing.
Speed: Because EdgeRefine keeps the map very sparse (keeping only the most important connections), the computer learns much faster. In tests, it trained in just 1.5 milliseconds to 3.4 milliseconds, while other methods took hundreds of milliseconds or even seconds.

What the Paper Rules Out

The paper is very clear about what doesn't work:

It rules out simply keeping edges that have a high probability score without a strict sampling plan (like the "Blink" method), because that leads to too many fake edges as privacy gets looser.
It rules out methods that ignore the original graph's sparsity, as they make the graph too dense and slow.
It suggests that while probability estimation is important, the exact accuracy of the probability numbers isn't the only thing that matters; the way you sample (select) the edges based on those numbers is what makes the difference.

The Bottom Line

EdgeRefine isn't a magic wand that makes privacy disappear, but it is a highly effective tool that finds the "sweet spot." It proves that you can protect people's secrets with strong mathematical guarantees while still letting computers learn useful patterns from the data. The authors measured this across multiple datasets and different types of computer brains (GNNs like GAT, GCN, and GIN), showing that this approach consistently beats the current state-of-the-art methods.

In short, EdgeRefine takes a messy, noisy map and uses smart math to clean it up just enough to be useful, without ever revealing the secrets hidden inside.

Technical Summary: EdgeRefine

Problem Statement

Graph Neural Networks (GNNs) have achieved significant success in learning from graph-structured data; however, their deployment in privacy-sensitive domains is hindered by the risk of leaking sensitive link information. While Differential Privacy (DP) offers a rigorous framework for protecting data, existing edge-level DP methods struggle to balance privacy guarantees with data utility. Current approaches face three primary limitations:

Inability to Identify Trustworthy Edges: Existing methods often fail to distinguish high-confidence edges from noise in the perturbed adjacency matrix, leading to poor downstream task performance.
Ineffective Denoising Strategies: Probability-based denoising often lacks robust strategies for filtering noisy edges. Estimation errors combined with random sampling result in unstable graph structures and degraded classification performance.
Structural Distortion: Noise injection frequently destroys graph sparsity, a critical property of real-world networks. This leads to denser graphs that reduce computational efficiency and distort the structural meaning required for GNN message passing.

The core challenge is to develop a framework that provides strict edge-level differential privacy while maintaining the sparsity and structural integrity necessary for effective GNN training.

Methodology: EdgeRefine

EdgeRefine is a local differential privacy (LDP) framework designed to denoise graph adjacency matrices through a client-server pipeline. It employs a two-stage process to refine the noisy graph into a structure suitable for downstream tasks.

1. Client-Side Perturbation

The client, holding the original graph with adjacency matrix $A$ , applies Edge Randomization to satisfy $\epsilon$ -edge differential privacy.

Mechanism: The client uses a randomized response mechanism on the upper triangle of the adjacency matrix.
Parameters: Based on the privacy budget $\epsilon$ , the client calculates flipping probabilities: $p = e^\epsilon / (1 + e^\epsilon)$ for retaining true edges and $q = 1 / (1 + e^\epsilon)$ for flipping non-edges.
Output: A symmetric, noisy adjacency matrix $\tilde{A}$ is generated and transmitted to the server.

2. Server-Side Denoising

The server receives $\tilde{A}$ and performs a two-stage refinement process to reconstruct a denoised graph $\hat{A}$ .

Stage 1: Probability Estimation via Jaccard Similarity and Histogram Binning

To estimate the existence probability of edges despite the noise:

Jaccard Similarity: The server computes the Jaccard similarity coefficient for all node pairs $(i, j)$ based on their neighborhood sets in the noisy graph: $J(i, j) = |N(i) \cap N(j)| / |N(i) \cup N(j)|$ . This normalization helps suppress the impact of random perturbations.
Quantile-Based Binning: The computed similarity values are partitioned into $B$ bins using quantiles of the empirical distribution. This non-parametric approach adapts to diverse graph topologies without manual thresholds.
Probability Calibration: Within each bin, the probability of edge existence is estimated as the ratio of observed edges to the total number of pairs in that bin. This yields a calibrated probability matrix $L$ .

Stage 2: Deterministic Optimal Sampling

To convert the probability matrix into a deterministic graph structure while controlling sparsity:

Target Edge Count: The server defines a target number of edges $K = \lfloor k \times E \rfloor$ , where $E$ is the original edge count and $k$ is a global sampling rate.
Candidate Partitioning: Edges are split into two sets based on the noisy matrix $\tilde{A}$ $\tilde{A}$ :
- $E_{real}$ : Observed edges ( $\tilde{A}_{ij}=1$ ).
- $E_{fake}$ : Non-edges ( $\tilde{A}_{ij}=0$ ).
Selection Strategy: Using the theoretical true edge ratio $\rho = e^\epsilon / (1 + e^\epsilon)$ $ρ = e^{ϵ} / (1 + e^{ϵ})$ derived from the privacy budget, the server selects:
- The top $\lfloor \rho K \rfloor$ edges from $E_{real}$ (sorted by probability $L_{ij}$ ).
- The top $K - \lfloor \rho K \rfloor$ edges from $E_{fake}$ (sorted by probability $L_{ij}$ ).
Output: The union of selected edges forms the final symmetric adjacency matrix $\hat{A}$ . This deterministic approach eliminates sampling variance and ensures reproducible results.

Key Contributions

EdgeRefine Framework: A novel framework that balances privacy and utility through deterministic edge refinement, addressing the trade-off in graph learning.
Jaccard-Based Estimation: A method for estimating edge existence probabilities using Jaccard similarity combined with histogram binning, which accurately calibrates probabilities from noisy data.
Rate-Controlled Sampling: A deterministic sampling approach that precisely controls the ratio of true to false edges and the overall graph sparsity, eliminating selection variance.
Theoretical and Empirical Validation: Rigorous analysis confirming computational efficiency and strict privacy compliance, alongside extensive experiments demonstrating superior performance over state-of-the-art baselines.

Experimental Results

Experiments were conducted on four real-world datasets (ACM, DBLP, AMAP, Cora) using three GNN architectures (GAT, GCN, GIN) across various privacy budgets ( $\epsilon \in [0.5, 3.5]$ ).

Accuracy Improvement: EdgeRefine achieves accuracy comparable to noise-free baselines and significantly outperforms existing privacy-preserving methods.
- Under $\epsilon=2.5$ , EdgeRefine improved node classification accuracy by 17.8% on ACM (GAT) and 19.7% on Cora (GCN) compared to the state-of-the-art Blink baseline.
- In graph classification (MUTAG), it achieved an average accuracy degradation of only ~5% compared to the noise-free baseline.
Stability: EdgeRefine demonstrates exceptional stability with significantly lower variance ( $\sigma^2$ ) and coefficient of variation (CV) compared to competitors. For instance, on ACM and DBLP, the variance was as low as $0.0001$.
Sparsity and Efficiency: The method maintains ultra-sparse graph structures (density $10^{-6}$ to $10^{-5}$ ), which is 2-5 orders of magnitude sparser than other methods. This results in training times that are 3-4 orders of magnitude faster than methods like LDPGen.
Privacy Resilience: Under graph reconstruction attacks, EdgeRefine maintains a Relative Absolute Error (RAE) consistently above 1 (averaging 1.962 on Cora), indicating strong resistance to edge inference.
Privacy-Utility Balance Index (PUBI): EdgeRefine achieved the highest average PUBI (0.9386) across all combinations, outperforming Blink-hybrid (0.7101) and Blink-hard (0.6902), demonstrating its ability to maintain utility as privacy requirements relax.

Significance

The paper posits that EdgeRefine addresses the fundamental barrier of privacy-utility balance in graph learning. By rethinking the denoising process through adaptive edge refinement, the framework enables the practical deployment of GNNs in privacy-sensitive scenarios without sacrificing the structural integrity required for effective message passing. The authors claim that EdgeRefine provides a robust solution that is computationally efficient, theoretically sound, and empirically superior to existing state-of-the-art methods, making it a viable candidate for real-world privacy-preserving graph analysis.