Differentially Private Graph Data Release: Inefficiencies & Unfairness

Ferdinando Fioretto, Diptangshu Sen, Juba ZianiAISTATS 2025 · OpenReview

Abstract

Networks in sectors like telecommunications and transportation often contain sensitive user data, requiring privacy enhancing technologies during data release to ensure privacy. While Differential Privacy (DP) is recognized as the leading standard for privacy preservation, its use comes with new challenges, as the noise added for privacy introduces inaccuracies or biases. DP techniques have also been found to distribute these biases disproportionately across different populations, inducing fairness issues. This paper investigates the effects of DP on bias and fairness when releasing network edge weights. We specifically examine how these privacy measures affect decision-making tasks, such as computing shortest paths, which are crucial for routing in transportation and communications networks, and provide both theoretical insights and empirical evidence on the inherent trade-offs between privacy, accuracy, and fairness for network data release.

Introduction

Sharing network data—such as road maps with traffic levels or communication network costs—is vital for research and public utility. However, these datasets often contain sensitive individual information. Differential Privacy (DP) has emerged as the gold standard for protecting such data by adding calibrated noise. While it is well-known that DP reduces data utility, recent studies have highlighted a more insidious side effect: "disparate impact." This occurs when the errors introduced by privacy mechanisms are distributed unevenly across different user groups.

This paper extends the study of DP fairness from simple tabular data to complex graph structures. We focus on a scenario where a network administrator releases private edge weights used for shortest-path routing. We ask a critical question: how does the noise required for privacy affect the travel costs of different users, and who bears the brunt of these inaccuracies?

Methodology

The authors model the privacy process by transforming a weighted graph $G$ into a privatized version $\tilde{G}$. This is achieved using the Gaussian Mechanism, which adds noise to each edge weight. To ensure physical plausibility (e.g., non-negative travel times), a non-negativity constraint is applied by clipping noisy weights at zero.

The theoretical framework identifies two primary drivers of routing bias:

  1. Effective Relative Noise Effect: In longer paths, noise tends to "average out" relative to the total path weight, potentially reducing relative bias for distant node pairs.
  2. Path Cardinality Effect: As the number of alternative paths between two nodes increases, there is a higher statistical likelihood that noise will make a sub-optimal path appear shorter than the true shortest path.

Experimental Setup

To evaluate these effects, the study utilizes three synthetic graph topologies that represent common real-world networks:

  • 2D Grid Graphs: Representing urban street networks like Manhattan.
  • Scale-Free Graphs: Modeling social or web networks with high-connectivity hubs.
  • Wheel Graphs: Mimicking hub-and-spoke city layouts like Paris.
Synthetic graph topologies: (a) Grid, (b) Scale-Free, and (c) Wheel graphs.

Key Insights: Topology and the Paradox of Choice

The research reveals that privacy is not a "neutral" tax; its cost is distributed based on network location and structure.

  • The Paradox of Choice in Grids: In grid networks, long-distance travelers (Category 4) have significantly more path options than short-distance travelers (Category 1). Here, the Path Cardinality Effect dominates, leading to much higher relative bias for long-distance trips.
  • Hub Dominance in Scale-Free Networks: In highly connected scale-free networks, the trend can reverse. Users near central hubs may have many short alternative paths, making them more susceptible to privacy-induced errors than those on the network periphery.
  • Impact of Sparsity: When many edges have near-zero weights, the non-negativity constraint introduces a systematic positive bias, favoring paths with fewer edges.

Empirical Results

The experiments confirm that DP noise creates systemic unfairness. In grid networks, the disparity between user categories is stark. As shown in the figure below, under high noise conditions, long-distance node pairs (Category 4) are far more likely to experience extreme relative bias compared to short-distance pairs (Category 1).

Empirical probability of relative bias across different node pair categories under high noise (Std 200%).

Theoretical analysis supports these findings, with the authors proving that the upper bound on bias probability scales linearly with the number of alternative paths, confirming the significance of the Path Cardinality Effect.

Conclusion and Future Work

This work quantifies how DP-induced noise leads to inequitable outcomes in network routing. While the current study assumes a public graph topology and independent edge noise, it sets the stage for future research. Key next steps include developing "fair" DP mechanisms that can redistribute noise to ensure more equitable outcomes and exploring scenarios where the graph structure itself is sensitive.

Summary updated

Abstract

Networks in sectors like telecommunications and transportation often contain sensitive user data, requiring privacy enhancing technologies during data release to ensure privacy. While Differential Privacy (DP) is recognized as the leading standard for privacy preservation, its use comes with new challenges, as the noise added for privacy introduces inaccuracies or biases. DP techniques have also been found to distribute these biases disproportionately across different populations, inducing fairness issues. This paper investigates the effects of DP on bias and fairness when releasing network edge weights. We specifically examine how these privacy measures affect decision-making tasks, such as computing shortest paths, which are crucial for routing in transportation and communications networks, and provide both theoretical insights and empirical evidence on the inherent trade-offs between privacy, accuracy, and fairness for network data release.
BibTeX
@inproceedings{fioretto2025differentially,
  author = {Ferdinando Fioretto and Diptangshu Sen and Juba Ziani},
  title = {{Differentially Private Graph Data Release: Inefficiencies \& Unfairness}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2025},
  url = {https://openreview.net/forum?id=q4hCSrCtcn},
}
Figure