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

点击翻译按钮获取中文摘要

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.