AF: Small: Massive Graph Analysis via Linear Measurements: Towards a Theory of Homomorphic Co

在存在关于基本实体以及这些实体之间的关系的数据的任何应用中都会出现大量图表，例如，网页和超链接；神经元和突触；论文和引文；IP地址和网络流量；人和他们的友谊。图形已经成为表示许多类型的高度结构化数据的事实上的标准。然而，这些海量图的大小使得传统计算模型中的现有图算法通常不适用。在这个项目中，PI研究了随机线性投影的用途，这种投影将大量的图形压缩到一个更低维的空间，在那里计算变得更容易处理。这种方法的优点是其广泛的适用性；投影的线性导致适合于并行和分布式计算、在线处理和各种压缩传感模型的算法。关于在特征向量和频率计数等数字数据的背景下使用线性投影，存在着大量的分析和经验工作。例如，已经在位置敏感散列和最近邻、指纹、稀疏信号恢复、度量嵌入、空间划分树和低阶矩阵近似的研究的背景下研究了这样的投影。该项目的目标是将这一强大的技术扩展到高度结构化的图形数据中。主要研究内容包括：a)研究可线性测量的图形结构类型。这包括设计新的投影和证明维度界，以保持图的性质，如距离、特征值、割和匹配的大小以及导出子图的频率。B)开发该框架的新应用，包括处理动态图形的快速算法、图形采样和属性测试、图形指纹以及MapReduce式的分布式计算。C)向同态压缩理论迈进。线性投影相对于线性运算是同态的，设计用于图形压缩的投影的主要挑战是将相关的图形运算重塑为线性运算。PI将进一步发展这一想法，并探索压缩方案，在这种方案中，可以直接对压缩数据进行计算，而无需首先解压缩数据。与这些研究目标相结合，该项目包括教育和更广泛的影响倡议，旨在确保研究成果的广泛传播，并培训研究生和本科生。

Massive graphs arise in any application where there is data about both basic entities and the relationships between these entities, e.g., web-pages and hyperlinks; neurons and synapses; papers and citations; IP addresses and network flows; people and their friendships. Graphs have become the de facto standard for representing many types of highly structured data. However, the size of these massive graphs is such that existing graph algorithms in traditional computational models are typically not applicable. In this project, the PI investigates the utility of random linear projections that compress massive graphs into a lower-dimensional space where computation becomes more tractable. An advantage of this approach is its widespread applicability; the linearity of the projection leads to algorithms appropriate for parallel and distributed computation, online processing, and various compressed sensing models. A rich body of analytic and empirical work exists on using linear projections in the context of numerical data such as feature vectors and frequency counts. For example, such projections have been studied in the context of research on locality sensitive hashing and nearest neighbors, fingerprinting, sparse signal recovery, metric embeddings, spatial partition trees, and low-rank matrix approximation. The goal of this project is to extend this powerful technique to highly structured graph data.The main research components are: A) Investigating the types of graph structure that can be measured linearly. This includes designing new projections and proving bounds on the dimensionality required to preserve graph properties such as distances, eigenvalues, the size of cuts and matchings, and the frequency of induced subgraphs. B) Developing new applications of the framework including fast algorithms for processing dynamic graphs, graph sampling and property testing, graph fingerprinting, and MapReduce-style distributed computing. C) Taking steps towards a theory of homomorphic compression. Linear projections are homomorphic with respect to linear operations and the main challenge in designing projections for graph compression is recasting the relevant graph operations as linear operations. The PI will develop this idea further and explore compression schemes where it is possible to compute directly on the compressed data without the need to first uncompress the data.In conjunction with these research goals, the project includes educational and broader impact initiatives that are designed to ensure a wide dissemination of research results and to train graduate and undergraduate students.