Differentially Private Densest Subgraph

Alireza Farhadi, MohammadTaghi Hajiaghayi, Elaine Shi

Abstract

The densest subgraph problem (DSP) is a fundamental task in graph mining with applications ranging from community detection to link spam identification. However, standard algorithms for DSP can inadvertently leak sensitive information about the graph's structure, such as the existence of specific edges. This paper introduces the first linear-time, $\epsilon$-differentially private algorithm for DSP. Our approach achieves a 2-approximation of the densest subgraph with a poly-logarithmic additive error, nearly matching the performance of the classic non-private algorithm by Charikar. We also establish a new lower bound proving that a sub-logarithmic additive error is inherent for any differentially private algorithm providing a constant-factor approximation. Empirical evaluations on real-world networks demonstrate that our algorithm is both highly accurate and significantly faster than existing private alternatives.

Introduction

Identifying dense regions in large-scale networks is a cornerstone of modern data analysis. Whether detecting tightly-knit communities in social networks or identifying clusters of fraudulent accounts in financial transaction graphs, the Densest Subgraph Problem (DSP) provides a robust mathematical framework for these tasks. Formally, given a graph $G=(V, E)$, the goal is to find a subset of vertices $S \subseteq V$ that maximizes the density $d(S) = |E(S)|/|S|$, where $E(S)$ is the set of edges induced by $S$.

While efficient algorithms like Charikar’s greedy peeling provide a 2-approximation in linear time, they are not designed with privacy in mind. In many contexts, the edges of a graph represent sensitive relationships—friendships, communications, or transactions. Because the output of DSP is highly sensitive to the presence or absence of a single edge, standard algorithms can leak information about individual connections. This paper addresses this gap by developing a differentially private (DP) framework for DSP that maintains both utility and efficiency.

The Challenge of Privacy in Graph Mining

Differential privacy (DP) provides a rigorous mathematical guarantee that the output of an algorithm does not change significantly if any single record (in this case, an edge) is added or removed. The primary challenge in making DSP private is the high "global sensitivity" of the problem. A single edge change can drastically alter which set of vertices is considered the densest.

Previous attempts to solve this problem under DP constraints often faced a trilemma: they were either computationally prohibitive for large graphs, required a massive "privacy budget" that rendered the results useless, or only estimated the density without identifying the actual vertices involved.

Methodology: Private Greedy Peeling

The authors propose an algorithm that adapts Charikar’s classic greedy "peeling" strategy. In the non-private version, vertices are iteratively removed based on their current degree until the densest core is found. To make this process $\epsilon$-differentially private, the authors introduce several key innovations:

1. Noisy Peeling

Instead of removing the vertex with the absolute minimum degree, the algorithm removes the vertex with the minimum noisy degree. By injecting controlled noise into the selection process, the algorithm masks the influence of any single edge.

2. DP Prefix Sum and Sparse-Vector Techniques

To maintain efficiency, the algorithm must track degree changes as vertices are removed. The authors utilize an $\epsilon$-adaptive-DP prefix sum mechanism. Furthermore, they employ a Sparse-Vector Technique (SVT) to update noisy degrees only when a significant number of neighbors have been removed. This reduces the total noise required over the course of the algorithm, preserving accuracy.

3. Linear-Time Bucketing

To achieve the "gold standard" of $O(m+n)$ complexity, the algorithm discretizes noisy degrees into buckets. Rather than searching for the exact minimum, it selects any vertex from the lowest non-empty bucket, ensuring the algorithm remains practical for massive datasets.

Theoretical and Empirical Results

The paper provides the first comprehensive upper and lower bounds for private DSP.

Upper Bound: The proposed algorithm achieves a 2-approximation with an additive error of $O(\frac{1}{\epsilon} \log^{2.5} n)$. This matches the approximation ratio of Charikar’s algorithm while providing strong $\epsilon$-DP guarantees.

Lower Bound: The authors prove that for any DP algorithm providing a constant-factor approximation, a sub-logarithmic additive error is mathematically unavoidable. This result is significant because it justifies the additive error in their algorithm as a fundamental trade-off of privacy rather than a technical limitation.

Experimental Performance: The algorithm was tested on various real-world datasets from the SNAP and Network Repository collections, including social networks (Twitch, Facebook) and collaboration networks (Astrophysics, General Relativity). The results showed:

  • Accuracy: The algorithm's utility improves rapidly as the privacy budget $\epsilon$ increases, consistently outperforming previous state-of-the-art private methods.
  • Scalability: The linear-time implementation is approximately 100 times faster than concurrent private algorithms like SEQDENSEDP, making it the first private DSP algorithm truly suitable for large-scale applications.

Conclusion

This work bridges the gap between theoretical privacy guarantees and practical graph mining. By combining noisy peeling with advanced DP mechanisms, the authors demonstrate that it is possible to find dense subgraphs privately without sacrificing linear-time efficiency. While the current focus is on edge differential privacy, future work may explore the even more challenging domain of node differential privacy, as well as extending these techniques to directed and weighted graphs.

Summary updated

Abstract

Given a graph, the densest subgraph problem asks for a set of vertices such that the average degree among these vertices is maximized. Densest subgraph has numerous applications in learning, e.g., community detection in social networks, link spam detection, correlation mining, bioinformatics, and so on. Although there are efficient algorithms that output either exact or approximate solutions to the densest subgraph problem, existing algorithms may violate the privacy of the individuals in the network, e.g., leaking the existence/non-existence of edges. In this paper, we study the densest subgraph problem in the framework of the differential privacy, and we derive the first upper and lower bounds for this problem. We show that there exists a linear-time $\epsilon$-differentially private algorithm that finds a $2$-approximation of the densest subgraph with an extra poly-logarithmic additive error. Our algorithm not only reports the approximate density of the densest subgraph, but also reports the vertices that form the dense subgraph. Our upper bound almost matches the famous $2$-approximation by Charikar both in performance and in approximation ratio, but we additionally achieve differential privacy. In comparison with Charikar's algorithm, our algorithm has an extra poly-logarithmic additive error. We partly justify the additive error with a new lower bound, showing that for any differentially private algorithm that provides a constant-factor approximation, a sub-logarithmic additive error is inherent. We also practically study our differentially private algorithm on real-world graphs, and we show that in practice the algorithm finds a solution which is very close to the optimal
BibTeX
@inproceedings{farhadi2022differentially,
  author = {Alireza Farhadi and MohammadTaghi Hajiaghayi and Elaine Shi},
  title = {{Differentially Private Densest Subgraph}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2022},
  url = {https://openreview.net/forum?id=5SNDNxdfKW},
}
Figure