TL;DR
This paper tackles the challenge of privately releasing shortest path distances in social graphs, a crucial but privacy-sensitive task. They introduce a novel approach using "asymmetric neighborhoods" and "smooth sensitivity" to significantly improve utility (accuracy) compared to existing differential privacy methods, especially for unweighted graphs.
What Problem Does This Paper Address?
Online social networks generate massive amounts of graph data, making privacy a critical concern when analyzing or sharing this information. Shortest path distances are fundamental metrics in these graphs, used for tasks like route planning and friend recommendations. However, traditional methods for ensuring privacy (like differential privacy) often introduce too much noise when applied to graph data, severely degrading the accuracy of distance queries. Existing work primarily assumes "weight private graphs" (where edge weights are private), but this paper focuses on "edge privacy" in unweighted graphs, where the existence of a relationship (an edge) is the sensitive information. The core problem is how to provide accurate distance queries while protecting the privacy of these relationships without sacrificing too much utility.
Methods
The paper's core innovation lies in leveraging asymmetric neighborhoods and smooth sensitivity for differential privacy.
- Asymmetric Neighborhoods: Instead of assuming that if graph A is a neighbor of graph B, then B is also a neighbor of A (symmetric neighborhood), they consider scenarios where this isn't true. Specifically, they look at two cases:
- Adding an edge: A graph G' is a neighbor of G if it has one additional edge.
-
Removing an edge: A graph G' is a neighbor of G if it has one fewer edge. This asymmetry allows for more tailored privacy mechanisms.
-
Smooth Sensitivity: Traditional differential privacy often relies on global sensitivity, which can be very high for graph queries, leading to excessive noise. Local sensitivity can reduce noise but compromises privacy. Smooth sensitivity offers a balance by considering a range of neighboring graphs, providing a more robust privacy guarantee with potentially better utility.
- Individual Asymmetric Differential Privacy (IADP): They propose a new privacy definition, IADP, which combines the ideas of asymmetric neighborhoods and smooth sensitivity. This allows them to develop mechanisms (like the Individual Asymmetric Laplace Mechanism) that are more efficient and accurate for distance queries.
- Algorithms: They present two algorithms: one for handling distance queries when an edge is added and another for when an edge is removed. These algorithms focus on efficiently computing the smooth sensitivity and then adding calibrated noise. They also incorporate techniques like random rounding and truncation to maintain integer distance properties and further improve utility.
Datasets
The paper evaluates their proposed methods on a mix of real-world and synthetic datasets:
- Real-world Datasets:
- EIES: A social network graph of researchers.
- BOTC: A trust graph from Bitcoin trading.
-
TDE: A Twitch social graph of gamers. These datasets were preprocessed to be unweighted and undirected.
-
Synthetic Datasets:
- Harary Graphs (H3,200, H3,1000, H3,5000): These are k-connected graphs used to specifically test the "removing an edge" scenario, as it requires a certain level of connectivity to maintain graph properties. They are referred to as SHG, MHG, and LHG for small, medium, and large sizes, respectively.
Key Insights and Ideas
- Asymmetry is Key for Utility: The paper demonstrates that exploiting the asymmetric nature of graph modifications (adding/removing edges) is crucial for improving the utility of differentially private queries, especially for unweighted graphs where global sensitivity is otherwise prohibitive.
- Smooth Sensitivity Bridges the Gap: Smooth sensitivity proves to be a powerful tool for balancing privacy and utility. It allows for more accurate results than global sensitivity while avoiding the privacy pitfalls of local sensitivity.
- Distance Queries Benefit Greatly: The proposed IADP mechanism shows significant improvements in accuracy for distance queries, outperforming existing methods like SDP and ADP, particularly at lower privacy budget ($\epsilon$) values.
- The "Removing an Edge" Scenario is Challenging: While adding an edge is relatively straightforward, removing an edge to maintain connectivity and privacy presents greater challenges, requiring stricter graph assumptions (e.g., 3-edge connectivity) and leading to higher noise levels.
Key Results
- The proposed IADP mechanism significantly improves the all-pair distance mean relative error (MRE) compared to Standard Differential Privacy (SDP) and Asymmetric Differential Privacy (ADP).
- For real-world datasets like EIES, IADP showed up to a 10x improvement over SDP and ADP. For larger graphs like BOTC and TDE, the improvement was over 500x at small $\epsilon$.
- The MRE for IADP on real-world datasets reached as low as 0.0865 and 0.0862 at $\epsilon=8$, indicating high utility.
- For synthetic Harary graphs, while IADP still introduced errors (e.g., at least 34% error at $\epsilon=18$), it still offered significantly better utility than SDP and ADP.
- The paper demonstrates that the utility improvement of IADP is more pronounced for graphs with smaller diameters.
Limitations and Future Work
- Strict Graph Assumptions: The "removing an edge" scenario requires graphs to be at least 3-edge connected, which is a strong assumption not always met in real-world social networks. The paper uses synthetic Harary graphs to address this.
- Handling Disconnections: The paper acknowledges the challenge of answering queries when removing an edge might disconnect the graph (resulting in infinite distance). Refusing to answer can also reveal privacy, and this issue needs further exploration.
- Sensitivity Trade-offs: For some queries, smooth sensitivity might not offer a significant advantage over global sensitivity. The paper suggests further research into when local sensitivity can be safely applied to graph queries.
- Future Work: The authors suggest exploring how to handle refusal-to-answer scenarios caused by disconnections, broadening the applicability of their methods. They also propose investigating alternative privacy-preserving strategies, such as masking edges directly, and further analyzing the trade-offs between local and smooth sensitivity.
Summary updated