NSF Award to streamline graph analysis of large networks

Prof. Greg Bodwin has received an NSF Award for his project exploring the unanswered mathematical and algorithmic problems regarding sketching distance-based properties of graphs. Graph sketching, a method of representing networks on a smaller, more convenient scale, represents an alternative to the classical algorithms for graph analysis, which have lost effectiveness as networks continue to grow.

“Modern computer science is dominated by enormous networks like the internet, social network graphs, neural nets, and so forth,” said Bodwin. “These networks are expensive to store and maintain, and often they can be analyzed only by people with access to industrial levels of computing power.”

In pursuit of cheaper, faster, and more accessible methods of graph analysis, Bodwin’s project aims to determine the efficacy of graph spanners, which are sketches of shortest path distances and which have enjoyed successful applications in areas like robotics, distributed computing, and circuit design, to classify the sketching problems for which more involved constructions of data structures can or cannot outperform simpler sketching methods like taking subgraphs, and to find the most relevant structural parameters of graphs, like expansion, highway dimension, etc. that control the difficulty of building a sketch of that graph.

“My goal is to design small sketches of these networks, which are cheaper to store, faster to analyze, or which can be handled with only a reasonable amount of compute. I specifically work on the theory and math behind these sketches,” said Bodwin. “I want to know which networks can or can’t be effectively sketched, how similar our sketches can be to the original network, and how different kinds of sketches relate to each other.”

The project’s focus will be to lower the barrier to entry for those interested in practical application of sketching and further research, as many publicly-available resources for this area are currently out of date or otherwise insufficient.