Differentially Private Release of Count-Weighted Graphs
Resumo
Este trabalho propõe várias contribuições para a privacidade em sistemas complexos, principalmente aqueles modelados como grafos ponderados por contagem. Como dados de grafos geralmente contêm informações sensíveis dos usuários, preservar a privacidade ao compartilhar esse tipo de dado se torna uma questão crucial. Nesse contexto, a privacidade diferencial (PD) tornou-se o padrão para o compartilhamento de dados com fortes garantias matemáticas. No entanto, diversos desafios persistem na implementação eficaz de PD em dados de grafos, incluindo o equilíbrio entre proteção de privacidade, utilidade dos dados e preocupações com escalabilidade. Para preencher essas lacunas, propomos várias técnicas e abordagens eficientes para liberar dados de grafos, mantendo um nível robusto de proteção de privacidade. Nossos resultados foram publicados nos principais veículos da área de gerenciamento de dados. Além disso, disseminamos o conhecimento e a expertise obtidos durante esta pesquisa de doutorado por meio de tutoriais e minicursos apresentados em conferências nacionais e internacionais.
Palavras-chave:
differential privacy, local-DP, count-weighted graphs
Referências
Brazil (2018). Lei Geral de Proteção de Dados Pessoais. [link]. Online; accessed 15 May 2023.
Brito, F. T. (2023). Differentially private release of count-weighted graphs. PhD thesis, Universidade Federal do Ceara.
Brito, F. T., Farias, V. A., Flynn, C., Majumdar, S., Machado, J. C., and Srivastava, D. (2023). Global and local differentially private release of count-weighted graphs. Proceedings of the ACM on Management of Data, 1(2):1–25.
Brito, F. T. and Machado, J. C. (2017). Preservação de privacidade de dados: Fundamentos, técnicas e aplicações. Jornadas de atualização em informática, pages 91–130.
Brito, F. T., Mendonça, A. L. C., and Machado, J. C. (2024). A differentially private guide for graph analytics. In Proceedings 27th International Conference on Extending Database Technology, EDBT 2024, Paestum, Italy, pages 850–853.
Camacho, D., Panizo-LLedot, A., Bello-Orgaz, G., Gonzalez-Pardo, A., and Cambria, E. (2020). The four dimensions of social network analysis: An overview of research methods, applications, and software tools. Information Fusion, 63:88–120.
Chen, L., Han, K., Xiu, Q., and Gao, D. (2022). Graph clustering under weight-differential privacy. In 2022 IEEE 24th Int Conf on High Performance Computing & Communications; 8th Int Conf on Data Science & Systems; 20th Int Conf on Smart City; 8th Int Conf on Dependability in Sensor, Cloud & Big Data Systems & Application (HPCC/DSS/SmartCity/DependSys), pages 1457–1464. IEEE.
Cormode, G., Procopiuc, C., Srivastava, D., and Tran, T. T. (2012). Differentially private summaries for sparse data. In Proceedings of the 15th International Conference on Database Theory, pages 299–311.
Duffield, N., Lund, C., and Thorup, M. (2007). Priority sampling for estimation of arbitrary subset sums. Journal of the ACM (JACM), 54(6):32–es.
Dwork, C. (2006). Differential privacy. In International Colloquium on Automata, Languages, and Programming, pages 1–12. Springer.
European Union (2016). Regulation (eu) 2016/679 of the european parliament and of the council. [link]. General Data Protection Regulation (GDPR).
Fan, C. and Li, P. (2022). Distances release with differential privacy in tree and grid graph. In 2022 IEEE International Symposium on Information Theory (ISIT), pages 2190–2195. IEEE.
Farias, V. A., Brito, F. T., Flynn, C., Machado, J. C., Majumdar, S., and Srivastava, D. (2020). Local dampening: differential privacy for non-numeric queries via local sensitivity. Proceedings of the VLDB Endowment, 14(4):521–533.
Farias, V. A., Brito, F. T., Flynn, C., Machado, J. C., Majumdar, S., and Srivastava, D. (2023). Local dampening: Differential privacy for non-numeric queries via local sensitivity. The VLDB Journal, pages 1–24.
Federal Communications Commission (2018). Customer privacy. [link]. Online; accessed 13 October 2022.
Ferrara, E., Varol, O., Menczer, F., and Flammini, A. (2016). Detection of promoted social media campaigns. In Proceedings of the International AAAI Conference on Web and Social Media, volume 10, pages 563–566.
Ghosh, A., Roughgarden, T., and Sundararajan, M. (2012). Universally utility-maximizing privacy mechanisms. SIAM Journal on Computing, 41(6):1673–1693.
Hardt, M. and Roth, A. (2012). Beating randomized response on incoherent matrices. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 1255–1268.
Hay, M., Li, C., Miklau, G., and Jensen, D. (2009). Accurate estimation of the degree distribution of private networks. In 2009 Ninth IEEE International Conference on Data Mining, pages 169–178. IEEE.
Kasiviswanathan, S. P., Nissim, K., Raskhodnikova, S., and Smith, A. (2013). Analyzing graphs with node differential privacy. In Theory of Cryptography Conference, pages 457–476. Springer.
Le Ny, J. and Pappas, G. J. (2013). Privacy-preserving release of aggregate dynamic models. In Proceedings of the 2nd ACM international conference on High confidence networked systems, pages 49–56.
Leal, B. C., Vidal, I. C., Brito, F. T., Nobre, J. S., and Machado, J. C. (2018). -doca: Achieving privacy in data streams. In International Workshop on Data Privacy Management, pages 279–295. Springer.
Leskovec, J., Adamic, L. A., and Huberman, B. A. (2007). The dynamics of viral marketing. ACM Transactions on the Web (TWEB), 1(1):5–es.
Li, X., Yang, J., Sun, Z., and Zhang, J. (2017). Differential privacy for edge weights in social networks. Security and Communication Networks, 2017.
Manríquez, R., Guerrero-Nancuante, C., Martínez, F., and Taramasco, C. (2021). Spread of epidemic disease on edge-weighted graphs from a database: A case study of covid-19. International Journal of Environmental Research and Public Health, 18(9):4432.
Matsumoto, H., Yoshida, S., and Muneyasu, M. (2021). Propagation-based fake news detection using graph neural networks with transformer. In 2021 IEEE 10th Global Conference on Consumer Electronics (GCCE), pages 19–20. IEEE.
McSherry, F. and Talwar, K. (2007). Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07), pages 94–103. IEEE.
Mendonça, A. L., Brito, F. T., Linhares, L. S., and Machado, J. C. (2017). Dipcoding: a differentially private approach for correlated data with clustering. In Proceedings of the 21st International Database Engineering & Applications Symposium, pages 291–297.
Mendonça, A. L., Brito, F. T., and Machado, J. C. (2023). Privacy-preserving techniques for social network analysis. In Anais Estendidos do XXXVIII Simpósio Brasileiro de Bancos de Dados, pages 174–178. SBC.
Mendonça, A. L., Brito, F. T., and Machado, J. C. (2024). Análise de dados privada em redes sociais. Jornadas de atualização em informática.
Monteiro, F. C., Brito, F. T., Chaves, I. C., and Machado, J. C. (2023). Compartilhamento de dados de tráfego de rede utilizando privacidade diferencial. In Anais do L Seminário Integrado de Software e Hardware, pages 296–307. SBC.
Neto, E. R., Mendonça, A. L., Brito, F. T., and Machado, J. C. (2018). Privlbs: uma abordagem para preservação de privacidade de dados em serviços baseados em localização. In Anais do XXXIII Simpósio Brasileiro de Banco de Dados, pages 109–120. SBC.
Newman, M. E. (2003). The structure and function of complex networks. SIAM review, 45(2):167–256.
Pinot, R., Morvan, A., Yger, F., Gouy-Pailler, C., and Atif, J. (2018). Graph-based clustering under differential privacy. arXiv preprint arXiv:1803.03831.
Sealfon, A. (2016). Shortest paths and distances with differential privacy. In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 29–41.
Silva, R. R. C., Leal, B. C., Brito, F. T., Vidal, V. M., and Machado, J. C. (2017). A differentially private approach for querying rdf data of social networks. In Proceedings of the 21st International Database Engineering & Applications Symposium, pages 74–81.
Varol, O., Ferrara, E., Menczer, F., and Flammini, A. (2017). Early detection of promoted campaigns on social media. EPJ data science, 6:1–19.
Wang, D. and Long, S. (2019). Boosting the accuracy of differentially private in weighted social networks. Multimedia Tools and Applications, 78(24):34801–34817.
Brito, F. T. (2023). Differentially private release of count-weighted graphs. PhD thesis, Universidade Federal do Ceara.
Brito, F. T., Farias, V. A., Flynn, C., Majumdar, S., Machado, J. C., and Srivastava, D. (2023). Global and local differentially private release of count-weighted graphs. Proceedings of the ACM on Management of Data, 1(2):1–25.
Brito, F. T. and Machado, J. C. (2017). Preservação de privacidade de dados: Fundamentos, técnicas e aplicações. Jornadas de atualização em informática, pages 91–130.
Brito, F. T., Mendonça, A. L. C., and Machado, J. C. (2024). A differentially private guide for graph analytics. In Proceedings 27th International Conference on Extending Database Technology, EDBT 2024, Paestum, Italy, pages 850–853.
Camacho, D., Panizo-LLedot, A., Bello-Orgaz, G., Gonzalez-Pardo, A., and Cambria, E. (2020). The four dimensions of social network analysis: An overview of research methods, applications, and software tools. Information Fusion, 63:88–120.
Chen, L., Han, K., Xiu, Q., and Gao, D. (2022). Graph clustering under weight-differential privacy. In 2022 IEEE 24th Int Conf on High Performance Computing & Communications; 8th Int Conf on Data Science & Systems; 20th Int Conf on Smart City; 8th Int Conf on Dependability in Sensor, Cloud & Big Data Systems & Application (HPCC/DSS/SmartCity/DependSys), pages 1457–1464. IEEE.
Cormode, G., Procopiuc, C., Srivastava, D., and Tran, T. T. (2012). Differentially private summaries for sparse data. In Proceedings of the 15th International Conference on Database Theory, pages 299–311.
Duffield, N., Lund, C., and Thorup, M. (2007). Priority sampling for estimation of arbitrary subset sums. Journal of the ACM (JACM), 54(6):32–es.
Dwork, C. (2006). Differential privacy. In International Colloquium on Automata, Languages, and Programming, pages 1–12. Springer.
European Union (2016). Regulation (eu) 2016/679 of the european parliament and of the council. [link]. General Data Protection Regulation (GDPR).
Fan, C. and Li, P. (2022). Distances release with differential privacy in tree and grid graph. In 2022 IEEE International Symposium on Information Theory (ISIT), pages 2190–2195. IEEE.
Farias, V. A., Brito, F. T., Flynn, C., Machado, J. C., Majumdar, S., and Srivastava, D. (2020). Local dampening: differential privacy for non-numeric queries via local sensitivity. Proceedings of the VLDB Endowment, 14(4):521–533.
Farias, V. A., Brito, F. T., Flynn, C., Machado, J. C., Majumdar, S., and Srivastava, D. (2023). Local dampening: Differential privacy for non-numeric queries via local sensitivity. The VLDB Journal, pages 1–24.
Federal Communications Commission (2018). Customer privacy. [link]. Online; accessed 13 October 2022.
Ferrara, E., Varol, O., Menczer, F., and Flammini, A. (2016). Detection of promoted social media campaigns. In Proceedings of the International AAAI Conference on Web and Social Media, volume 10, pages 563–566.
Ghosh, A., Roughgarden, T., and Sundararajan, M. (2012). Universally utility-maximizing privacy mechanisms. SIAM Journal on Computing, 41(6):1673–1693.
Hardt, M. and Roth, A. (2012). Beating randomized response on incoherent matrices. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 1255–1268.
Hay, M., Li, C., Miklau, G., and Jensen, D. (2009). Accurate estimation of the degree distribution of private networks. In 2009 Ninth IEEE International Conference on Data Mining, pages 169–178. IEEE.
Kasiviswanathan, S. P., Nissim, K., Raskhodnikova, S., and Smith, A. (2013). Analyzing graphs with node differential privacy. In Theory of Cryptography Conference, pages 457–476. Springer.
Le Ny, J. and Pappas, G. J. (2013). Privacy-preserving release of aggregate dynamic models. In Proceedings of the 2nd ACM international conference on High confidence networked systems, pages 49–56.
Leal, B. C., Vidal, I. C., Brito, F. T., Nobre, J. S., and Machado, J. C. (2018). -doca: Achieving privacy in data streams. In International Workshop on Data Privacy Management, pages 279–295. Springer.
Leskovec, J., Adamic, L. A., and Huberman, B. A. (2007). The dynamics of viral marketing. ACM Transactions on the Web (TWEB), 1(1):5–es.
Li, X., Yang, J., Sun, Z., and Zhang, J. (2017). Differential privacy for edge weights in social networks. Security and Communication Networks, 2017.
Manríquez, R., Guerrero-Nancuante, C., Martínez, F., and Taramasco, C. (2021). Spread of epidemic disease on edge-weighted graphs from a database: A case study of covid-19. International Journal of Environmental Research and Public Health, 18(9):4432.
Matsumoto, H., Yoshida, S., and Muneyasu, M. (2021). Propagation-based fake news detection using graph neural networks with transformer. In 2021 IEEE 10th Global Conference on Consumer Electronics (GCCE), pages 19–20. IEEE.
McSherry, F. and Talwar, K. (2007). Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07), pages 94–103. IEEE.
Mendonça, A. L., Brito, F. T., Linhares, L. S., and Machado, J. C. (2017). Dipcoding: a differentially private approach for correlated data with clustering. In Proceedings of the 21st International Database Engineering & Applications Symposium, pages 291–297.
Mendonça, A. L., Brito, F. T., and Machado, J. C. (2023). Privacy-preserving techniques for social network analysis. In Anais Estendidos do XXXVIII Simpósio Brasileiro de Bancos de Dados, pages 174–178. SBC.
Mendonça, A. L., Brito, F. T., and Machado, J. C. (2024). Análise de dados privada em redes sociais. Jornadas de atualização em informática.
Monteiro, F. C., Brito, F. T., Chaves, I. C., and Machado, J. C. (2023). Compartilhamento de dados de tráfego de rede utilizando privacidade diferencial. In Anais do L Seminário Integrado de Software e Hardware, pages 296–307. SBC.
Neto, E. R., Mendonça, A. L., Brito, F. T., and Machado, J. C. (2018). Privlbs: uma abordagem para preservação de privacidade de dados em serviços baseados em localização. In Anais do XXXIII Simpósio Brasileiro de Banco de Dados, pages 109–120. SBC.
Newman, M. E. (2003). The structure and function of complex networks. SIAM review, 45(2):167–256.
Pinot, R., Morvan, A., Yger, F., Gouy-Pailler, C., and Atif, J. (2018). Graph-based clustering under differential privacy. arXiv preprint arXiv:1803.03831.
Sealfon, A. (2016). Shortest paths and distances with differential privacy. In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 29–41.
Silva, R. R. C., Leal, B. C., Brito, F. T., Vidal, V. M., and Machado, J. C. (2017). A differentially private approach for querying rdf data of social networks. In Proceedings of the 21st International Database Engineering & Applications Symposium, pages 74–81.
Varol, O., Ferrara, E., Menczer, F., and Flammini, A. (2017). Early detection of promoted campaigns on social media. EPJ data science, 6:1–19.
Wang, D. and Long, S. (2019). Boosting the accuracy of differentially private in weighted social networks. Multimedia Tools and Applications, 78(24):34801–34817.
Publicado
14/10/2024
Como Citar
BRITO, Felipe T.; MACHADO, Javam C..
Differentially Private Release of Count-Weighted Graphs. In: CONCURSO DE TESES E DISSERTAÇÕES (CTDBD) - SIMPÓSIO BRASILEIRO DE BANCO DE DADOS (SBBD), 39. , 2024, Florianópolis/SC.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2024
.
p. 183-189.
DOI: https://doi.org/10.5753/sbbd_estendido.2024.241221.
