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

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

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.