| title | abstract | openreview | software | video | section | layout | series | publisher | issn | id | month | tex_title | firstpage | lastpage | page | order | cycles | bibtex_author | author | date | address | container-title | volume | genre | issued | extras | |||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Publishing Number of Walks and Katz Centrality under Local Differential Privacy |
In our study, we present an algorithm for publishing the count of walks and Katz centrality under local differential privacy (LDP), complemented by a comprehensive theoretical analysis. While previous research in LDP has predominantly focused on counting subgraphs with a maximum of five nodes, our work extends this to larger subgraphs. The primary challenge in such an extension lies in managing the exponentially increasing noise associated with LDP as the size of the subgraph grows. Our solution involves an algorithm for publishing the count of walks originating from each node in the graph, which subsequently enables us to publish the Katz centrality of all nodes. This algorithm incorporates multiple communication rounds and employs a clipping technique. Through both theoretical and empirical evaluation, we demonstrate that our algorithm achieves has a relatively small bias and variance, showing significant improvements over both the randomized response method and non-clipping algorithms. Additionally, our approach to estimating Katz centrality successfully identifies up to 90% of the nodes with the highest centrality values. |
76UkTmdmkB |
Papers |
inproceedings |
Proceedings of Machine Learning Research |
PMLR |
2640-3498 |
betzer24a |
0 |
Publishing Number of Walks and Katz Centrality under Local Differential Privacy |
377 |
393 |
377-393 |
377 |
false |
Betzer, Louis and Suppakitpaisarn, Vorapong and Hillebrand, Quentin |
|
2024-09-12 |
Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence |
244 |
inproceedings |
|