BIGDATA: F: Graph Sketching and Optimization Problems

University Of Pennsylvania, Philadelphia PA

Investigators

Abstract

Connections between computers on the internet, between people on social media, between cell regulation mechanisms and diseases: each of these networks is represented in the computer as an abstraction called a graph. Questions about connections - shortest or least congested paths between computers, clusters of friends or people with influence, best location to disrupt or promote cell growth - become graph optimization questions and need algorithms for their repeated solution. For huge graphs, optimization algorithms may demand more time and memory than is available. The past decade has seen significant advances in processing huge lists or tables of numbers (vectors and matrices) as more compact "sketches." (One technique for "linear sketches" takes inner products with pseudorandom matrices to make them smaller: this keeps similar data similar, and mathematical analysis shows that disparate data has a good chance of remaining separate.) There has not been similar progress for processing graphs, and converting graph data to vectors or matrices increases their size and/or loses their structure. This project extends the concept of linear sketches for graphs, and develops methods for solving large scale convex optimization problems using linear sketches. Most computational platforms easily calculate inner products, and the linearity allows data updates by algorithms that are naturally parallel or distributed, and that use simple communication. Development of algorithms and insights using linear sketching are intellectually compelling, and useful in practice. There has been nascent progress towards linear-sketch-based graph algorithms, however much more algorithmic development is necessary. The goal is to design algorithms that operate in small space and have provable guarantees and efficient implementations. The specific problems targeted are clustering, matching and assignment problems, and their generalizations to stochastic input. The project seeks to develop iterative algorithms that are easily adapted to a variety of computational models, to implement and validate the new algorithms on publicly available datasets, and to make the algorithms widely available.