CAREER: Sublinear Graph Algorithms: New Insights for Foundational Problems

Graphs are one of the most natural ways to represent relationships between data and are used to model a wide variety of settings: social networks, the communication infrastructure, the interconnections of financial markets, metabolic processes, and the wiring of the human brain, to name a few. Processing such graphs has long been a cornerstone of computer science research, but the rise of big data poses unique computational challenges, as the scale of the graphs in these applications has far outpaced available computing power.

The goal of this project is to develop a new toolkit for processing massive graphs. This project studies a novel set of research questions in the analysis of big data, and the new tools developed can be applied to foundational optimization problems such as shortest paths and matching that are central to applications in computer science, social networks, biology, and computational economics.

The focus on foundational problems allows the project to bring together undergraduate and graduate students from a wide range of backgrounds. In additional to PhD mentoring and high-school outreach, the education plan includes research opportunities for undergraduates and the development of a new course in sublinear graph algorithms at Rutgers University.

This project centers on three major challenges to processing massive graphs. The first is that such graphs are too large to fit in the memory of a computer, so the data must be compressed on the fly. The second is that it would take too long for a single computer to process the graph, so the computation is distributed over many machines.

The third that is that in many applications the underlying graph is changing over time and it is necessary to respond to these changes locally. The project develops novel tools for tackling each individual challenge. At the same time, the project introduces general frameworks that connect the studies of these different challenges and lead to tools that can overcome a broad set of obstacles simultaneously.

More specifically, what unifies the above challenges is the need to extrapolate global information about the entire graph from local information computed in small regions. For example, can one detect overloaded vertices from a small random sample of the graph? How can shortest paths in different regions be patched together to form a path from one end of the graph to another?

How can a graph be compressed to only retain the most relevant edges? By answering these and related questions, the research will help extend the motivating applications to significantly larger scales and will lead to new mathematical insights into the structure of graphs.

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.