Differentially Private Graph Algorithms: Theory, Local Models, and Applications

**Title of the Talk:** Differentially Private Graph Algorithms: Theory, Local Models, and Applications **Host Faculty:** Dr.M V Panduranga Rao **Speaker:** Vorapong Suppakitpaisarn **Date:** 28 May 2026 **Time:** 03:30 pm **Abstract** Graphs are fundamental models for representing relationships in many real-world systems, including social networks, communication networks, transportation systems, and biomedical data. However, graph data often contains sensitive information, and publishing or analyzing such data may reveal private information about individuals or relationships. Differential privacy provides a rigorous framework for protecting such information, but designing accurate and scalable graph algorithms under differential privacy remains highly challenging. In this talk, I will introduce recent developments in differentially private graph algorithms, with a particular focus on the local differential privacy model, where each user randomizes their own data before sending it to an analyst. I will discuss private algorithms for basic graph statistics such as triangle counts and graphlet counts, as well as recent approaches for weighted graphs where the graph topology may be public but edge weights are sensitive. These problems reveal interesting connections between privacy, combinatorial structure, covariance control, and communication complexity. The talk aims to give both a high-level introduction to differential privacy in graph analysis and a glimpse of current theoretical challenges in making private data analysis practical for large-scale networked data. No prior knowledge of differential privacy is required. **Bio** Vorapong Suppakitpaisarn is a Project Associate Professor at the Graduate School of Information Science and Technology, The University of Tokyo. His research interests include optimization under differential privacy, quantum optimization, combinatorial optimization, and approximation algorithms. He has worked on several topics in privacy-preserving data analysis, including locally differentially private algorithms for graph statistics, differentially private rank aggregation, and private algorithms for weighted and structured graphs. His recent works have appeared in venues such as KDD, AISTATS, STACS, TMLR, and AAAI.