{"ID":2829993,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.12031","arxiv_id":"2512.12031","title":"Differentially Private Community Detection in $h$-uniform Hypergraphs","abstract":"This paper studies the exact recovery threshold subject to preserving the privacy of connections in $h$-uniform hypergraphs. Privacy is characterized by the $(ε, δ)$-hyperedge differential privacy (DP), an extension of the notion of $(ε, δ)$-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, $(ε, δ)$. Sampling-based mechanisms and randomized response mechanisms guarantee pure $ε$-hyperedge DP where $δ=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.","short_abstract":"This paper studies the exact recovery threshold subject to preserving the privacy of connections in $h$-uniform hypergraphs. Privacy is characterized by the $(ε, δ)$-hyperedge differential privacy (DP), an extension of the notion of $(ε, δ)$-edge DP in the literature. The hypergraph observations are modeled through a $...","url_abs":"https://arxiv.org/abs/2512.12031","url_pdf":"https://arxiv.org/pdf/2512.12031v1","authors":"[\"Javad Zahedi Moghaddam\",\"Aria Nosratinia\"]","published":"2025-12-12T20:45:22Z","proceeding":"cs.IT","tasks":"[\"cs.IT\",\"eess.SP\"]","methods":"[]","has_code":false}