Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2512.12031 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908750513700864 |
|---|---|
| author | Moghaddam, Javad Zahedi Nosratinia, Aria |
| author_facet | Moghaddam, Javad Zahedi Nosratinia, Aria |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_12031 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Differentially Private Community Detection in $h$-uniform Hypergraphs Moghaddam, Javad Zahedi Nosratinia, Aria Information Theory Signal Processing 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. |
| title | Differentially Private Community Detection in $h$-uniform Hypergraphs |
| topic | Information Theory Signal Processing |
| url | https://arxiv.org/abs/2512.12031 |