An Efficient Private Algorithm for Community Detection

Vincent Cohen-Addad, Alessandro Epasto, Haim Kaplan, Hanna Komlós, Silvio LattanziarXiv 2026 · arXiv

TL;DR

This paper introduces the first differentially private (DP) algorithm for exact community detection in the Stochastic Block Model (SBM) that runs in near-linear time and space. By restricting graph access to node-degree queries on edge-disjoint subgraphs, the authors drastically reduce the amount of noise needed for privacy, allowing the algorithm to scale to graphs with tens of thousands of nodes—two orders of magnitude larger than previous state-of-the-art private methods.

What Problem Does This Paper Address?

Community detection—grouping nodes in a network based on their connectivity patterns—is vital for applications like social network analysis, fraud detection, and bioinformatics. The Stochastic Block Model (SBM) is the classic mathematical framework used to study this problem. However, in many real-world networks, edge connections represent highly sensitive data (e.g., financial transactions or personal relationships).

To protect this data, researchers use edge-differential privacy (edge-DP), which ensures that the presence or absence of any single edge cannot be easily inferred from the algorithm's output.

The fundamental challenge has been a harsh tradeoff between privacy, accuracy, and computational speed:

  1. High-noise, fast methods: Naive edge-privatization techniques (like randomized response) flip edges indiscriminately, adding massive amounts of spurious edges ($O(n^2)$) that destroy the graph's structure and make community recovery impossible unless the privacy budget is dangerously high.
  2. Low-noise, slow methods: Advanced private algorithms can recover communities accurately with low noise, but they rely on complex semidefinite programming (SDP) solvers that require quadratic ($O(n^2)$) time or worse, limiting their use to tiny graphs (around 200 nodes).

This paper tackles this gap, aiming for an algorithm that provides strong privacy guarantees, maintains high accuracy (exact recovery), and scales linearly with the size of the graph.

Methods

The authors bridge the gap between efficiency and privacy by introducing a novel framework: Adaptive Disjoint-Star Algorithms.

Instead of trying to make the entire graph private upfront, they restrict how the algorithm interacts with the graph data:

  • Low-Noise Edge Flipping: They perturb the graph by flipping edges and non-edges, but with a much lower probability ($p_f \in \tilde{O}(1/n)$) than standard randomized response. This preserves the graph's inherent sparsity and community structure.
  • Restricted Queries: The algorithm is only allowed to query the number of edges between a node and a subgraph (a "star" query), and these subgraphs must be edge-disjoint.
  • Inherent Stability: The authors mathematically prove that algorithms restricted to these disjoint-star queries are inherently stable against single-edge changes. Because a single edge change can only affect a limited number of queries, the low-noise flipped graph is sufficient to guarantee full $(\epsilon, \delta)$-edge differential privacy.

The final pipeline applies this low-noise flipping to a directed SBM (DSBM), splits the nodes into subsets, and recursively refines the communities using a modified version of a fast, non-private algorithm (Cohen-Addad et al., 2022). They also employ a privacy boosting technique to scale up the success probability to $1 - o(1/n)$ with only a constant-factor hit to the privacy budget.

Datasets

The paper evaluates its algorithms entirely on synthetically generated networks:

  • Stochastic Block Model (SBM) & Directed SBM (DSBM): Homogeneous graphs used to evaluate exact community recovery across varying node counts ($n$ from 10,000 to 40,000).
  • Barabási-Albert Model: A random graph model with a heavy-tailed (power-law) degree sequence ($n = 50,000$, $m = 500$), used to test the framework's adaptability to a secondary task: private degree counting.

No real-world datasets were used in the evaluation.

Key Insights and Ideas

  • The Power of Restricted Access: The "aha moment" of the paper is realizing that you don't need to inject massive noise to make a graph private if you strictly control how the algorithm reads the graph. Restricting queries to edge-disjoint stars limits information leakage naturally.
  • Noise as a Parameter Shift: The authors show that applying low-noise edge flipping to an SBM graph simply transforms it into another SBM graph with slightly shifted edge probabilities ($p \rightarrow p'$ and $q \rightarrow q'$). This elegant property means that well-studied, highly efficient non-private algorithms can be safely run on the privatized graph without losing their structural guarantees.

Key Results

  • Linear Scalability: The algorithm achieves near-linear time and space complexity ($\tilde{O}(|V| + |E|)$).
  • Massive Scale-Up: While prior advanced DP solvers capped out at graphs of roughly 200 nodes, this algorithm successfully processed graphs with 40,000 nodes in about 15 minutes (908 seconds) on a standard single-core machine.
  • High Accuracy: Under strict privacy settings ($\epsilon = 0.5, \delta = 10^{-5}$), the algorithm's accuracy consistently improved with graph size, achieving 100% exact recovery at $n = 30,000$ and above, outperforming efficient baseline alternatives.
+------------+---------------+-----------------------+
|  Nodes (n) | Ours Accuracy | Basic+Spectral Time   |
+------------+---------------+-----------------------+
|   10,000   |    66.71%     |      355.57 sec       |
|   20,000   |    99.79%     |     2736.65 sec       |
|   30,000   |   100.00%     |   (Timed out/OOM)     |
+------------+---------------+-----------------------+

Limitations and Future Work

  • The Small Graph Penalty: The perturbation probability $2_f$ is inversely proportional to the graph size ($n$). For small graphs (e.g., $n < 10,000$), the required noise becomes so large that it completely wipes out the community signal. This algorithm is strictly a "large-scale" solution.
  • Future Directions: The authors suggest extending this framework to more complex SBM variants, such as networks with unequal community sizes or more than two communities. They also note that the adaptive disjoint-star framework could be adapted to solve other private graph problems, such as finding the "planted clique" or identifying densest subgraphs.

Summary updated

Abstract

In this paper, we study the community detection problem in the stochastic block model (SBM) under privacy constraints. We introduce private and highly efficient algorithms for exact community detection within the SBM framework. Our algorithms represent the first differentially private methods capable of achieving exact recovery in a wide range of model parameters with near-linear time and space complexity. This is a significant improvement over previous SBM recovery algorithms, which either required pseudo-polynomial time or a quadratic scaling of resources for a constant privacy budget. Central to our approach is the introduction of a new concept, adaptive disjoint-star algorithms. These algorithms efficiently explore the graph's structure by querying node degrees on edge-disjoint subgraphs. We demonstrate that this general class of algorithms inherently offers strong privacy guarantees, a result that potentially holds value beyond the scope of SBM community detection. Finally, in we perform an empirical analysis of our algorithms showing that they can scale exact recovery on graphs with two orders of magnitude more nodes than prior work.
BibTeX
@misc{cohenaddad2026efficient,
  author = {Vincent Cohen-Addad and Alessandro Epasto and Haim Kaplan and Hanna Komlós and Silvio Lattanzi},
  title = {{An Efficient Private Algorithm for Community Detection}},
  year = {2026},
  eprint = {2606.14540},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2606.14540},
}

Loading related content...

Figure