Differential Privacy and Its Applications in Social Network Analysis: A Survey.

Honglu Jiang, Jian Pei, Dongxiao Yu, Jiguo Yu, Bei Gong, Xiuzhen Cheng

Abstract

Social network analysis presents unique privacy challenges due to the interconnected nature of relational data. This paper provides a comprehensive survey of Differential Privacy (DP) as applied to graph structures. We explore the fundamental tension between rigorous mathematical privacy guarantees and the practical utility required for extracting insights like degree distributions and subgraph counts. By categorizing privacy definitions, noise calibration techniques, and algorithmic strategies, this survey offers a roadmap for navigating the complex landscape of privacy-preserving network analysis.

Introduction: The Privacy Minefield of Social Data

Social network data is inherently sensitive. Unlike independent records in tabular databases, social networks are defined by relationships. Traditional anonymization techniques, such as removing personally identifiable information (PII) or achieving $k$-anonymity, often fail in this context. An adversary with minimal background knowledge—such as knowing a target individual has a specific number of connections—can easily re-identify individuals in a supposedly de-identified graph.

Differential Privacy offers a robust solution by ensuring that the output of a data analysis remains statistically similar regardless of whether any single individual's data is included in the dataset. However, applying DP to graphs is technically demanding. Removing a high-degree "hub" node can alter thousands of edges, leading to a "sensitivity spike" that often necessitates excessive noise, potentially rendering the data useless.

The basic mechanism of Differential Privacy: adding calibrated noise $Z$ to a query result $f(D)$ to ensure individual privacy.

Methods and Taxonomy

The technical landscape of Graph DP is categorized into several frameworks based on the scope of protection and the method of noise application.

Privacy Definitions

  1. Node Privacy: The most rigorous form, hiding the presence of a user and all their associated connections. It is often difficult to achieve without significant utility loss.
  2. Edge Privacy: Protects specific relationships between users, which is generally easier to implement but offers narrower protection.
  3. Out-link/Partition Privacy: Emerging variants that provide a middle ground for specific query types.

Noise Calibration and Algorithmic Strategies

To manage the sensitivity of graph queries, researchers employ various strategies:

  • Global vs. Smooth Sensitivity: While global sensitivity assumes worst-case scenarios, smooth sensitivity uses local graph neighborhoods to add less noise while maintaining formal guarantees.
  • Bounded Degree Projection: This involves "clipping" the graph so no node exceeds a maximum degree $d$, effectively capping sensitivity at the cost of some structural accuracy.
  • Post-Processing: Techniques like constrained inference are used to ensure noisy outputs remain physically plausible (e.g., preventing negative degree counts).
A summary of previous surveys highlighting the evolution of research from basic DP techniques to specialized social network applications.

Key Insights: The Utility-Privacy Trade-off

The Correlation Crisis

Standard DP assumes data points are independent. In social networks, an individual's privacy is intrinsically linked to their peers. This has led to the development of Dependent Differential Privacy, which accounts for social correlations where one person's data might leak information about another.

The Node Privacy Paradox

While Node Privacy is the gold standard for user protection, it is often computationally infeasible for complex structural queries like triangle counting. This necessitates the use of Restricted Sensitivity or Ladder Functions to provide useful counts without revealing specific clusters.

Local vs. Centralized DP

There is a growing shift toward Local DP (LDP), where users perturb their own data before it reaches a central collector. While this eliminates the need for a trusted third party, it currently introduces a significant "utility gap" compared to centralized models.

Results and Applications

The survey synthesizes findings across the field to evaluate the performance of DP on common network metrics:

  • Degree Distributions: These can be released with high accuracy under Edge Privacy using post-processing. Under Node Privacy, accuracy depends heavily on the success of graph projection.
  • Subgraph Counting: Counting $k$-cliques or triangles remains a challenge. The most successful approaches utilize Lipschitz extensions to maintain utility.
  • Edge Weights: For weighted graphs (e.g., financial transactions), Laplace perturbation is the dominant method, though it can struggle to preserve shortest-path properties.

Limitations and Future Directions

Despite significant progress, several "grand challenges" remain:

  1. The Curse of Dimensionality: Distributing a privacy budget across hundreds of node attributes often results in excessive noise.
  2. Dynamic Data: Most research focuses on static snapshots, but real-world networks are continuous streams. Current composition rules exhaust privacy budgets rapidly as graphs update.
  3. Correlated Data Models: More sophisticated models are required to account for the fact that "no man is an island" in a social graph; structural properties inherently leak information about neighboring nodes.

Conclusion

Differential Privacy provides a rigorous framework for protecting social network data, but its application requires careful calibration. Future work must bridge the utility gap for complex queries and develop more efficient methods for handling the high-dimensional, dynamic, and correlated nature of modern social graphs.

Summary updated

Abstract

Differential privacy is effective in sharing information and preserving privacy with a strong guarantee. As social network analysis has been extensively adopted in many applications, it opens a new arena for the application of differential privacy. In this article, we provide a comprehensive survey connecting the basic principles of differential privacy and applications in social network analysis. We present a concise review of the foundations of differential privacy and the major variants and discuss how differential privacy is applied to social network analysis, including privacy attacks in social networks, types of differential privacy in social network analysis, and a series of popular tasks, such as degree distribution analysis, subgraph counting and edge weights. We also discuss a series of challenges for future studies.
BibTeX
@misc{jiang2020differential,
  author = {Honglu Jiang and Jian Pei and Dongxiao Yu and Jiguo Yu and Bei Gong and Xiuzhen Cheng},
  title = {{Differential Privacy and Its Applications in Social Network Analysis: A Survey.}},
  year = {2020},
  eprint = {2010.02973},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2010.02973},
}
Figure