Differentially Private Community Detection in $h$-Uniform Hypergraphs

This paper studies the exact recovery threshold subject to preserving the privacy of connections in$h$-uniform hypergraphs. Privacy is characterized by the$(\epsilon, \delta)$-hyperedge differential privacy (DP), an extension of the notion of$(\epsilon, \delta)$-edge DP in the literature. The hypergraph observations are modeled through a$h$-uniform stochastic block model ($h$-HSBM) in the dense regime. We investigate three differentially private mechanisms: stability-based, sampling-based, and perturbation-based mechanisms. We calculate the exact recovery threshold for each mechanism and study the contraction of the exact recovery region due to the privacy budget,$(\epsilon, \delta)$. Sampling-based mechanisms and randomized response mechanisms guarantee pure$\epsilon$-hyperedge DP where$\delta =0$, while the stability-based mechanisms cannot achieve this level of privacy. The dependence of the limits of the privacy budget on the parameters of the$h$-uniform hypergraph is studied. More precisely, it is proven rigorously that the minimum privacy budget scales logarithmically with the ratio between the density of in-cluster hyperedges and the cross-cluster hyperedges for stability-based and Bayesian sampling-based mechanisms, while this budget depends only on the size of the hypergraph for the randomized response mechanism.