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

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

• 批准号: 2317192
• 负责人: Ravi Tandon
• 金额: $ 40万
• 依托单位: University of Arizona
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-07-01 至 2027-06-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2317192&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的法定任务，并使用基金会的知识分子优点和更广泛的影响审查标准，被认为是通过评估来获得的支持。

项目成果

Generalization Bounds for Neural Belief Propagation Decoders

• DOI: 10.1109/isit54713.2023.10206901
• 发表时间: 2023-05
• 期刊: 2023 IEEE International Symposium on Information Theory (ISIT)
• 作者: S. Adiga;Xin Xiao;Ravi Tandon;Bane V. Vasic;Tamal Bose