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

协作研究：SaTC：核心：媒介：具有差异隐私的图挖掘和网络科学：高效算法和基本限制

• 批准号: 2317193
• 负责人: Anil Kumar Vullikanti
• 金额: $ 40万
• 依托单位: University of Virginia Main Campus
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-07-01 至 2027-06-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2317193&HistoricalAwards=false
• 关键词: Collaborative; Research; SaTC; CORE; Medium

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.

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