Collaborative Research: SaTC: CORE: Medium: Graph Mining and Network Science with Differential Privacy: Efficient Algorithms and Fundamental Limits

数据隐私是众多依赖于图形和网络数据的应用程序的根本挑战，包括医疗保健、社交网络、金融和计算流行病学。采用隐私保护解决方案在此类应用程序中进行实践通常会受到效用损失和缺乏可扩展性的阻碍，无法解决具有数十亿节点/边缘的大规模问题。该项目旨在为图挖掘和网络科学中的几个基本问题开发私有算法，这些算法可以扩展到现实世界应用中出现的网络规模，并提供良好的准确性界限。该项目更广泛的意义和重要性在于，私人算法将可用于公共卫生政策规划，网络安全和社交网络分析的新研究人员社区。 本项目采用图差分隐私（DP）作为隐私的概念，通过在图挖掘和网络科学中的各种基本问题的隐私保护算法设计中的基础性贡献来实现上述目标，例如子图检测，节点排名，社区检测，以及研究图动力系统的性质，例如网络上的流行病传播。该项目利用分布式计算的工具，如采样和草图，并为图DP开发创新工具，以产生具有严格精度界限的高度可扩展的私有图算法（无论是在理论上还是实践中）。最后，该项目将导致开发一个私人图形处理系统，该系统将被纳入网络科学网络基础设施。因此，图形DP的工具将提供给更广泛的网络科学和计算epidemiology.This奖项反映了NSF的法定使命，并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。

Data privacy is a fundamental challenge across numerous applications that rely on graphs and network data, including healthcare, social networks, finance, and computational epidemiology. Adopting privacy-preserving solutions to practice in such applications is often hindered by the loss in utility and lack of scalability to large-scale problems with billions of nodes/edges. This project aims to develop private algorithms for several fundamental problems in graph mining and network science, that can scale to networks of the size that arise in real-world applications and provide good accuracy bounds. The project’s broader significance and importance are that private algorithms will become available to a new community of researchers from public-health policy planning, cybersecurity and social network analysis. Adopting graph differential privacy (DP) as the notion of privacy, this project achieves the above goals through fundamental contributions in privacy-preserving algorithm design for various fundamental problems in graph mining and network science, such as subgraph detection, node ranking, community detection, and studying properties of graph dynamical systems such as epidemic spread on networks. The project leverages tools from distributed computation, such as sampling and sketching, and develops innovative tools for graph DP to yield highly-scalable private graph algorithms with rigorous accuracy bounds (both in theory and practice). Finally, the project will lead to the development of a private graph processing system, which will be incorporated into a network science cyber-infrastructure. Accordingly, the tools of graph DP will be made available to the broader community of network science and computational epidemiology.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.