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

Image generated by AI

TLDR

• What: EdgeRefine is a local differential privacy (LDP) framework that preserves graph structural utility under strict edge-level differential privacy by combining Jaccard similarity estimation, quantile-based histogram binning, and deterministic optimal sampling.
• Who's at risk: Distributed graph-structured systems (e.g., social networks, recommendation engines, and bioinformatics applications) that outsource Graph Neural Network (GNN) training on sensitive adjacency matrices to untrusted cloud servers.
• Key number: Under a strict privacy budget of $\epsilon = 2.5$, EdgeRefine improves node classification accuracy by 19.7% on the Cora dataset under GCN compared to the state-of-the-art Blink baseline, while keeping the normalized graph density on DBLP constant at $4.255 \times 10^{-6}$.

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

2. Opening Paragraph

In modern machine learning pipelines, GNNs are routinely deployed for high-stakes tasks such as social network analysis, recommendation systems, and bioinformatics. However, sharing raw graph adjacency matrices with centralized servers poses severe privacy risks, as malicious or honest-but-curious servers can easily reconstruct sensitive connections using inference attacks. To solve this, EdgeRefine proposes a decentralized local differential privacy (LDP) pipeline that allows clients to perturb their graph locally while enabling servers to reconstruct a highly accurate, denoised, and sparse adjacency matrix for GNN training.

3. Threat Model

4. Background / Problem Setup

Traditional approaches to edge-level differential privacy (DP) inject noise directly into the adjacency matrix to satisfy $\epsilon$-edge differential privacy. While this mathematically hides individual links, it severely degrades GNN utility by introducing massive spurious edges, destroying the graph's natural sparsity and message-passing routes.

Prior works have attempted to reconcile this utility-privacy trade-off, but they fail to balance formal guarantees with practical downstream performance. As summarized in Table 1 of the paper:

Related Work Comparison

Unlike Blink [50], which uses Bayesian estimation and separate privacy budgets for degree sequences (causing graph density to explode under higher privacy budgets), EdgeRefine maintains strict rate-controlled sparsity while relying entirely on post-processing properties of DP, avoiding any extra privacy budget leakage.

5. Methodology

EdgeRefine divides graph protection and restoration into a two-sided pipeline:

[Client-Side] Private Graph A 
      │
      ▼ (Algorithm 2: Randomized Response)
Noisy Graph à (Satisfies ε-edge DP)
      │
      ▼ (Sent to Server)
[Server-Side] Phase 1: Jaccard Similarity Matrix J
      │
      ▼ (Phase 2: Quantile-Based Binning)
Histogram Probability Calibration (Matrix L)
      │
      ▼ (Algorithm 4: Deterministic Optimal Sampling)
Denoised Adjacency Matrix  ──► GNN Training (GCN, GAT, GIN)

Step 1: Client-Side Edge Randomization

The client applies randomized response to the upper triangle of the adjacency matrix $A \in \{0, 1\}^{N \times N}$. For each node pair $(i, j)$ with $i < j$, the entry $\tilde{A}_{ij}$ is sampled via: $\tilde{A}_{ij} \sim \text{Bernoulli}(A_{ij} = 1 ? p : q)$ Where the true edge retention probability $p$ and fake edge flipping probability $q$ are governed by the privacy budget $\epsilon$: $p = \frac{e^\epsilon}{e^\epsilon + 1}, \quad q = \frac{1}{e^\epsilon + 1}$ Symmetry is enforced by mirroring $\tilde{A}_{ji} = \tilde{A}_{ij}$, and the noisy matrix $\tilde{A}$ is transmitted to the server.

Step 2: Server-Side Probability Estimation

To denoise the received graph, the server estimates true edge-existence probabilities in three phases:

1. Jaccard Similarity Computation: The server calculates the Jaccard coefficient for all node pairs to capture neighborhood structural overlap: $J(i, j) = \frac{|N(i) \cap N(j)|}{|N(i) \cup N(j)|}$
2. Quantile-Based Binning: To avoid parameter assumptions, the server extracts the upper triangle of $J$ and partitions the values into $B$ bins determined by the quantiles of the empirical distribution.
3. Probability Calibration: For each bin $b$, the calibrated edge existence probability $P_b$ is computed as the ratio of actually existing edges ($A_{ij} = 1$) to the total number of node pairs assigned to that bin: $P_b = \frac{\text{sum}(edges)}{\text{count}(pairs)}$ This empirical probability is mapped back to form the symmetric probability matrix $L$.

Step 3: Deterministic Optimal Sampling with Rate Control

Rather than randomly sampling edges (which introduces high variance), EdgeRefine uses a deterministic selection approach:

• Target Edge Count ($K$): Defined by a global sampling rate $k$ and the original edge count $E$: $K = \lfloor k \times E \rfloor$.
• Theoretical True Edge Ratio ($\rho$): Calculated directly as $\rho = \frac{e^\epsilon}{1 + e^\epsilon}$.
• Candidate Partitioning: Split node pairs into $E_{\text{real}}$ (where $\tilde{A}_{ij} = 1$) and $E_{\text{fake}}$ (where $\tilde{A}_{ij} = 0$).
• Selection: Sort both sets in descending order of their calibrated probabilities in $L$. Select the top $K_{\text{real}} = \lfloor \rho K \rfloor$ edges from $E_{\text{real}}$, and the remaining $K_{\text{fake}} = K -$K_{\text{real}}$from$E_{\text{fake}}$. This combination yields the reconstructed matrix$\hat{A}$.

6. Key Results

Node Classification Performance & Stability

The authors evaluated EdgeRefine across four real-world datasets: ACM, DBLP, AMAP, and Cora. Table 4 details the Privacy-Utility Balance Index (PUBI) where 1.000 represents a perfect utility-to-privacy profile.

Table 4: Privacy-Utility Balance Index (PUBI)

Analysis: Under high noise (low privacy budgets like $\epsilon = 0.5$), Blink variants quickly degrade as more noisy edges are wrongly classified. EdgeRefine maintains an outstanding average PUBI of 0.9386, outperforming the closest baseline by over 24.3%.

Graph Density Maintenance

A primary failure of other private frameworks is the structural distortion where noisy graphs become too dense. Table 5 compares normalized density on the DBLP dataset:

Table 5: Normalized Graph Density

Analysis: While Blink-hard's density inflates by 5 orders of magnitude as the privacy constraints loosen ($\epsilon$ goes from $0.5$ to $3.5$), EdgeRefine preserves a constant, ultra-sparse density of $4.255 \times 10^{-6}$ across all privacy budgets.

Resilience Against Graph Reconstruction Attacks

To prove robust privacy preservation, the authors tested the reconstructed graph $\hat{A}$ against the SOTA GRAND [2] reconstruction attack. A Relative Absolute Error (RAE) of 1 means the attack is equivalent to guessing.

Table 9: Resistance (RAE) to GRAND Reconstruction Attack

Analysis: EdgeRefine consistently maintains RAE scores well above 1.0. On Cora, the RAE remains high (averaging 1.962) regardless of the privacy budget, indicating that GRAND is unable to accurately reconstruct the original topology.

7. Limitations & Open Questions

Despite the strong results, security teams must note the following:

1. High Preprocessing Time: As shown in Table 6, EdgeRefine requires longer preprocessing times. At $\epsilon = 0.5$, preprocessing DBLP takes 1104.3 seconds, whereas baseline LDPGen takes just 1.9 seconds. Although this is an offline task, it restricts runtime adaptability for rapidly evolving graphs.
2. Link Prediction Failure: Table 16 shows that under all privacy budgets, Link Prediction AUC drops heavily (from 0.9524 noise-free down to 0.5905 at $\epsilon = 1.5$). Because edge privacy explicitly obfuscates real connections, EdgeRefine is structurally incompatible with downstream link prediction tasks.
3. AMAP Dataset Instability: In GIN models trained on the AMAP dataset, accuracy exhibited erratic fluctuations (Table 10 reports standard deviation spikes of 0.0944). Practitioners should use GAT/GCN backbones for heterogeneous graph topologies.

8. What Practitioners Should Do

If you are outsourcing GNN training to public clouds under strict privacy regulations:

1. Decouple Preprocessing: Run the Jaccard similarity and quantile-based calibration (Algorithms 3 and 4) on an offline, isolated staging cluster before sending the denoised matrix to the active training cluster. This mitigates the high preprocessing overhead shown in Table 6.
2. Enforce Constant Sparsity: Consider setting the global sampling rate $k = 0.01$ as a baseline (refer to Table 7, where $k = 0.01$ is optimal for the Cora dataset across all three architectures, while larger datasets like DBLP may benefit from slightly higher sampling rates like $k = 0.05$ or $k = 0.1$).
3. Avoid Link Prediction Deployments: If your downstream model relies on accurate link inference (e.g., biological network analysis), do not use edge-level LDP. The performance drop of up to 38% AUC (Table 16) makes the graph structure unsuitable for this task.

9. The Takeaway

EdgeRefine proves that edge-level differential privacy does not have to result in highly distorted, over-dense graphs that break GNN convergence. By implementing deterministic sampling alongside Jaccard-based structural denoising, engineers can keep graph structures ultra-sparse and secure against modern reconstruction attacks, though they must budget for high offline preprocessing overhead.

Den's Take

EdgeRefine tackles a frustrating bottleneck in graph privacy: the fact that traditional edge-level local differential privacy (LDP) obliterates message-passing routes by flooding the graph with noisy, spurious edges. What excites me about this work is its pragmatic approach to preserving structural sparsity and utility through deterministic Jaccard sampling and quantile-based binning. Scoring a 19.7% improvement in GCN node classification accuracy on the Cora dataset compared to the Blink baseline—at a strict privacy budget of $\epsilon = 2.5$ while keeping the normalized graph density of the DBLP dataset locked at $4.255 \times 10^{-6}$—proves we don't have to completely destroy graph structure for formal LDP guarantees.

However, as a practitioner, I want to see how this scales beyond academic benchmarks. Real-world transaction networks are massive, dynamic, and often non-homophilous, where Jaccard similarity estimation might fall short. In my experience analyzing membership inference and statistical releases, I've observed how statistical releases leak identity information under adaptive adversaries, which makes me skeptical of how robust these reconstructed, denoised graphs actually are against targeted topology reconstruction attacks in highly sparse settings. It’s a step in the right direction, but the evaluation needs to move beyond toy datasets to prove its real-world viability.