BIGDATA: F: Graph Sketching and Optimization Problems

互联网上的计算机之间的联系，社交媒体上的人之间的联系，细胞调节机制和疾病之间的联系：这些网络中的每一个都在计算机中以抽象的图形表示。关于连接的问题——计算机之间最短或最不拥挤的路径，朋友或有影响力的人的集群，破坏或促进细胞生长的最佳位置——成为图形优化问题，需要算法来重复解决它们。对于巨大的图形，优化算法可能需要比可用的更多的时间和内存。在过去的十年中，在将庞大的数字列表或表格（向量和矩阵）处理为更紧凑的“草图”方面取得了重大进展。（“线性草图”的一种技术采用伪随机矩阵的内积，使其更小：这使相似的数据保持相似，数学分析表明，不同的数据很有可能保持分离。）在处理图形方面还没有类似的进展，将图形数据转换为向量或矩阵会增加它们的大小和/或失去它们的结构。本项目扩展了图形线性草图的概念，并开发了使用线性草图解决大规模凸优化问题的方法。大多数计算平台很容易计算内积，线性允许通过自然并行或分布的算法更新数据，并且使用简单的通信。使用线性素描的算法和见解的开发在智力上是引人注目的，并且在实践中是有用的。在基于线性草图的图形算法方面已经取得了初步进展，但是还需要更多的算法开发。目标是设计在小空间中运行的算法，并具有可证明的保证和有效的实现。所针对的具体问题是聚类、匹配和分配问题，以及它们对随机输入的推广。该项目旨在开发易于适应各种计算模型的迭代算法，在公开可用的数据集上实施和验证新算法，并使算法广泛可用。

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.