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

数据隐私是许多依赖图表和网络数据的应用程序的根本挑战，包括医疗保健、社交网络、金融和计算流行病学。在这样的应用中采用隐私保护解决方案通常会受到实用性的损失和对具有数十亿个节点/边的大规模问题缺乏可扩展性的阻碍。该项目旨在为图挖掘和网络科学中的几个基本问题开发专用算法，这些算法可以扩展到现实世界应用程序中出现的网络规模，并提供良好的精度界限。该项目更广泛的意义和重要性在于，私人算法将提供给公共卫生政策规划、网络安全和社交网络分析等领域的新研究人员。本课题采用图差分隐私(DP)作为隐私的概念，通过对图挖掘和网络科学中的各种基本问题，如子图检测、节点排序、社区检测，以及研究网络上流行病传播等图动态系统的性质，在隐私保护算法设计方面做出了基本贡献，从而实现了上述目标。该项目利用分布式计算的工具，如采样和草图绘制，并为图DP开发创新工具，以产生具有严格精度界限的高度可扩展的私有图算法(无论是在理论上还是在实践中)。最后，该项目将导致开发一个私人图形处理系统，该系统将被纳入网络科学网络基础设施。因此，GRAPE DP的工具将提供给更广泛的网络科学和计算流行病学社区。这一奖项反映了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.