Scalable Graph Algorithms: Parallel, Dynamic, and Private

Abstract

Graph algorithms are ubiquitous in today’s world where graph analytics are performed over massive datasets containing potentially sensitive information. Modern graphs present many new challenges not considered by classic static, sequential computation models. First, network graphs have up to trillions of edges and are several orders of magnitude larger than what traditional sequential algorithms can handle. In addition to scale, modern graphs are also dynamically evolving with up to millions of changes per second. Second, data leaks and commercial data trading threaten to expose the large volume of sensitive private information contained in these graphs. Third, the monetary and resource incentives associated with large distributed graphs (e.g., for cryptocurrency) make them vulnerable to malicious adversaries. Thus, modern graph algorithms must achieve several simultaneous goals: efficiency, scalability, privacy, and robustness against adversaries.

In this talk, I will present algorithms that rise to these aforementioned challenges. I will first present novel scalable algorithms for k-core decomposition, subgraph counting, coloring, and related important problems in computational models that take advantage of modern parallel computing architectures and dynamic environments. These algorithms not only achieve theoretical improvements but also hundreds of times speedups over the state-of-the-art in practice. Then, I will formalize models and give algorithms that combat broader societal concerns of privacy breaches and susceptibility to adversarial attacks. Finally, I’ll discuss my broader research vision in combining scalability with adversary-robustness.

Bio:

Quanquan C. Liu is a postdoctoral scholar at Northwestern University under the mentorship of Samir Khuller. She completed her PhD in Computer Science at MIT where she was advised by Erik D. Demaine and Julian Shun. Before that, she obtained her dual bachelor’s degree in computer science and math also at MIT. She has worked on a number of problems in algorithms and the intersection between theory and practice. Her most recent work focuses on parallel dynamic and static graph algorithms as well as differentially private graph algorithms. She has earned the Best Paper Award at SPAA 2022, a NSF Graduate Research Fellowship, and participated in the 2021 EECS Rising Stars workshop.