Differentially Private Densest Subgraph

Alireza Farhadi, MohammadTaghi Hajiaghayi, Elaine Shi

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 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.

Introduction

The Densest Subgraph Problem (DSP) is a cornerstone of graph mining, essential for identifying communities in social networks, detecting link spam, or finding functional modules in biological systems. However, many real-world graphs—such as friendship networks or medical records—contain highly sensitive information. Standard algorithms for finding dense subgraphs are "privacy-leaking": the inclusion of a specific vertex in the output might reveal the existence of a private connection between individuals.

Traditional Differential Privacy (DP) tools often struggle with graph structures. "Output perturbation" (adding noise to the final result) is ineffective because the densest subgraph can change drastically with the addition or removal of a single edge (high sensitivity). Conversely, "input perturbation" (randomizing the graph before processing) often destroys the structural density the algorithm aims to find. This work introduces a private, linear-time algorithm that maintains high utility on massive, real-world graphs.

Methodology

The proposed approach is based on Charikar’s Greedy Algorithm, a classic non-private method that iteratively removes the vertex with the lowest degree. To achieve $\epsilon$-differential privacy, several key innovations were introduced:

  1. Noisy Residual Degrees: Instead of tracking exact degrees, each vertex maintains a "noisy" count of its neighbors.
  2. DP Prefix Sum Mechanism: To prevent the privacy budget from being exhausted over thousands of iterations, a prefix sum mechanism tracks neighbor removals while adding only logarithmic noise.
  3. Thresholded Updates (Sparse Vector Trick): To maintain efficiency, a vertex only updates its official "noisy degree" once it has lost a significant, predetermined number of neighbors. This keeps the algorithm running in quasilinear time.
  4. Bucketing for Linear Time: By discretizing noisy degrees into buckets, the algorithm eliminates the need for expensive priority queues, achieving a true $O(m+n)$ linear runtime.

Experimental Evaluation

The researchers evaluated the algorithm on six real-world networks from the SNAP and KONECT repositories, including collaboration networks (ca-Astro, ca-GrQc), Twitch social networks (musae_DE, musae_ENGB), and Facebook networks (socfb-Amherst41, socfb-Auburn71).

Accuracy and Utility

Theoretical analysis shows the algorithm provides a $(2, \tilde{O}(\frac{1}{\epsilon} \log^{2.5} n))$-approximation. In practice, the utility is remarkably high. Even with a strict privacy budget ($\epsilon = 1$), the density of the subgraphs found was often very close to the optimal non-private solution, significantly outperforming previous private methods.

Accuracy vs. Epsilon (ε) across six real-world networks. The proposed algorithm (orange) consistently achieves higher accuracy than the previous state-of-the-art (blue).

Computational Efficiency

By reaching linear time, the algorithm can handle graphs with millions of edges in seconds. In head-to-head tests against the previous state-of-the-art (Nguyen & Vullikanti, 2021), this new algorithm was approximately 100 times faster.

Runtime comparison (in seconds) between the proposed algorithm and the method by Nguyen and Vullikanti.

Discussion and Conclusion

A key theoretical insight of this work is the proof of a new lower bound, showing that any DP algorithm providing a constant-factor approximation must incur some additive error. This highlights an inherent trade-off between perfect multiplicative accuracy and differential privacy.

While the current work focuses on edge differential privacy, future research may explore node differential privacy, which protects the existence of entire users. Additionally, the "thresholded prefix sum" approach introduced here could potentially be adapted to other iterative graph algorithms, expanding the suite of practical, private graph mining tools.

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 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