Abstract
Analyzing network structures through graphlets—small induced subgraphs—is essential for social network analysis but poses significant privacy risks. This paper presents a novel, non-interactive algorithm for counting graphlets of any size $k$ while maintaining edge local differential privacy (LDP). We prove that our method is theoretically optimal for one-shot communication, achieving an expected error of $O(n^{k-1})$. Empirical evaluations demonstrate that our approach significantly outperforms standard randomized response techniques, particularly as the network size increases.
Introduction
In social network analysis, "graphlets" (small induced subgraphs like triangles, stars, or cliques) serve as fundamental building blocks for understanding complex network structures. However, sharing raw adjacency data is often impossible due to privacy concerns. Local Differential Privacy (LDP) has emerged as a robust standard because it allows users to obfuscate their own data before it reaches a central collector, eliminating the need for a trusted third party.
While previous work has successfully addressed simple structures like triangles ($k=3$), a general-purpose, private method for counting complex graphlets of any size $k$ has remained elusive. The primary challenge lies in the "noise" required for privacy, which typically grows with subgraph size and can easily overwhelm the signal in larger structures.
Methodology
The proposed approach utilizes a non-interactive, edge-local differentially private algorithm. The process involves three main stages:
- Obfuscation via Randomized Response: Each user applies a randomized response mechanism to their adjacency vector. Bits are flipped with a specific probability determined by the privacy budget $\epsilon$, ensuring that individual connections remain private.
- Unbiased Estimation: The central server receives the noisy adjacency data. Since the noise parameters are known, the server applies an inverse transformation to obtain unbiased estimators for the original edges.
- Automorphism-Based Counting: To count a specific graphlet $G$, the server computes a value based on the product of these unbiased edge estimators across all possible sets of $k$ nodes. The final sum is normalized by the number of automorphisms (symmetries) of the graphlet to prevent overcounting.
Theoretical Analysis and Optimality
A key contribution of this work is the rigorous analysis of error bounds. The researchers identified a "Factor of $n$" penalty: for every additional node in the target graphlet, the expected error increases by a factor of $n$. This suggests an inherent trade-off between subgraph complexity and privacy-preserving accuracy.
Crucially, the authors proved a lower bound showing that for any non-interactive algorithm, the error must be at least $\Omega(n^{k-1})$. Because the proposed algorithm achieves an error of $O(n^{k-1})$, it is asymptotically optimal for the non-interactive setting.
Experimental Results
The algorithm was evaluated on synthetic networks, including Barabási-Albert (scale-free) and Stochastic Block Models (community-based), with node counts ranging from 10 to 100.
Key findings from the experiments include:
- Superior Accuracy: In a Stochastic Block Model with 100 nodes and $\epsilon=1$, the proposed algorithm achieved an error 36 times smaller than the classical randomized response baseline.
- Scaling Behavior: As predicted by theory, while the absolute error grows with $n$, the relative error decreases. This occurs because the total number of graphlets in the network grows at a rate of $\Theta(n^k)$, outpacing the $\Theta(n^{k-1})$ growth of the error.
- Privacy-Utility Tradeoff: The algorithm maintains utility even under strict privacy constraints (e.g., $\epsilon=1$), where traditional methods often fail to produce meaningful signals.
Conclusion and Future Work
This research provides a theoretically optimal foundation for privacy-preserving graphlet counting. However, the $O(n^k)$ computational complexity remains a bottleneck for massive real-world networks. Future research directions include integrating sampling techniques to reduce computational overhead and tailoring the algorithm for specific graph topologies, such as bipartite or bounded-degree graphs, to further minimize error.
Summary updated