Publishing Number of Walks and Katz Centrality under Local Differential Privacy

Louis Betzer, Vorapong Suppakitpaisarn, Quentin Hillebrand
Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence, PMLR 244:377-393, 2024.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v244-betzer24a, title = {Publishing Number of Walks and Katz Centrality under Local Differential Privacy}, author = {Betzer, Louis and Suppakitpaisarn, Vorapong and Hillebrand, Quentin}, booktitle = {Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence}, pages = {377--393}, year = {2024}, editor = {Kiyavash, Negar and Mooij, Joris M.}, volume = {244}, series = {Proceedings of Machine Learning Research}, month = {15--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v244/main/assets/betzer24a/betzer24a.pdf}, url = {https://proceedings.mlr.press/v244/betzer24a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Publishing Number of Walks and Katz Centrality under Local Differential Privacy %A Louis Betzer %A Vorapong Suppakitpaisarn %A Quentin Hillebrand %B Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2024 %E Negar Kiyavash %E Joris M. Mooij %F pmlr-v244-betzer24a %I PMLR %P 377--393 %U https://proceedings.mlr.press/v244/betzer24a.html %V 244 %X 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.
APA
Betzer, L., Suppakitpaisarn, V. & Hillebrand, Q.. (2024). Publishing Number of Walks and Katz Centrality under Local Differential Privacy. Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 244:377-393 Available from https://proceedings.mlr.press/v244/betzer24a.html.

Related Material