Computing epidemic metrics with edge differential privacy

George Z. Li, Dung Nguyen, Anil Vullikanti
Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, PMLR 238:4303-4311, 2024.

Abstract

Metrics such as the outbreak size in an epidemic process on a network are fundamental quantities used in public health analyses. The datasets used in such models used in practice, e.g., the contact network and disease states, are sensitive in many settings. We study the complexity of computing epidemic outbreak size within a given time horizon, under edge differential privacy. These quantities have high sensitivity, and we show that giving algorithms with good utility guarantees is impossible for general graphs. To address these hardness results, we consider a smaller class of graphs with similar properties as social networks (called expander graphs) and give a polynomial-time algorithm with strong utility guarantees. Our results are the first to give any non-trivial guarantees for differentially private infection size estimation.

Cite this Paper

BibTeX
@InProceedings{pmlr-v238-li24q, title = {Computing epidemic metrics with edge differential privacy}, author = {Li, George Z. and Nguyen, Dung and Vullikanti, Anil}, booktitle = {Proceedings of The 27th International Conference on Artificial Intelligence and Statistics}, pages = {4303--4311}, year = {2024}, editor = {Dasgupta, Sanjoy and Mandt, Stephan and Li, Yingzhen}, volume = {238}, series = {Proceedings of Machine Learning Research}, month = {02--04 May}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v238/li24q/li24q.pdf}, url = {https://proceedings.mlr.press/v238/li24q.html}, abstract = {Metrics such as the outbreak size in an epidemic process on a network are fundamental quantities used in public health analyses. The datasets used in such models used in practice, e.g., the contact network and disease states, are sensitive in many settings. We study the complexity of computing epidemic outbreak size within a given time horizon, under edge differential privacy. These quantities have high sensitivity, and we show that giving algorithms with good utility guarantees is impossible for general graphs. To address these hardness results, we consider a smaller class of graphs with similar properties as social networks (called expander graphs) and give a polynomial-time algorithm with strong utility guarantees. Our results are the first to give any non-trivial guarantees for differentially private infection size estimation.} }
Endnote
%0 Conference Paper %T Computing epidemic metrics with edge differential privacy %A George Z. Li %A Dung Nguyen %A Anil Vullikanti %B Proceedings of The 27th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2024 %E Sanjoy Dasgupta %E Stephan Mandt %E Yingzhen Li %F pmlr-v238-li24q %I PMLR %P 4303--4311 %U https://proceedings.mlr.press/v238/li24q.html %V 238 %X Metrics such as the outbreak size in an epidemic process on a network are fundamental quantities used in public health analyses. The datasets used in such models used in practice, e.g., the contact network and disease states, are sensitive in many settings. We study the complexity of computing epidemic outbreak size within a given time horizon, under edge differential privacy. These quantities have high sensitivity, and we show that giving algorithms with good utility guarantees is impossible for general graphs. To address these hardness results, we consider a smaller class of graphs with similar properties as social networks (called expander graphs) and give a polynomial-time algorithm with strong utility guarantees. Our results are the first to give any non-trivial guarantees for differentially private infection size estimation.
APA
Li, G.Z., Nguyen, D. & Vullikanti, A.. (2024). Computing epidemic metrics with edge differential privacy. Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 238:4303-4311 Available from https://proceedings.mlr.press/v238/li24q.html.

Related Material