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.