Multilevel Graph-Based Methods for Efficient Data Exploration

图论帮助科学家和工程师对集合中实体之间的各种类型的关系进行建模，无论是社会网络的成员，还是化合物中的分子。毫不奇怪，随着基于数据的方法的出现，图论工具通过揭示和利用数据项之间的关系，在非常广泛的应用中找到了自己的方式。这个项目的主要目标是研究一类操作图的方法，特别是通过开发有效的多级算法来利用分治法。在多层技术中，从一些原始图中提取越来越小的图，目标是尽可能多地保留其内在信息。然后使用这些较小的图来代替原始图，从而显著提高性能。该项目解决了与许多当前基于数据的方法非常相关的问题，并将适用于各个学科。因此，它将有助于促进对当前向这种方法转变的相关问题的兴趣，因为它的研究主题融合了数学方法、算法创新和应用。在教育方面，将为希望探索数据科学研究的其他学科领域的研究生提供特殊课程和教程。该项目每年将资助一名研究生，为期三年。机器学习方法迅速扩展到各种学科，推动了对能够有效处理大型数据集的数值方法的需求。在这些方法中，以数据的图形表示为基础的方法占有突出地位。该项目的目标是开发基于图论方法的有效多层算法，用于执行各种机器学习任务。计划研究的主要焦点是“图粗化”，这是一种技术，通过将附近的节点聚集在一起，大大减少原始图的大小，以产生原始图的忠实代表。该项目将开发一类基于多级粗化的方法，其中粗化递归地应用于几个级别。多层粗化方法的最终目标是使用小得多的粗化图执行繁重的计算成为可能，从而在精度损失最小的情况下产生更快的处理速度。粗化是随机抽样的一种有效替代方法，随机抽样是一种成熟的方法，它由随机或准随机选择的列或行的子集替换原始数据。本项目将从实证和理论两方面研究各种粗化策略。例如，将从近似特征向量的投影方法的角度研究粗化。我们还将研究如何精确地保留特征向量的粗化方法。在图粗化的许多可能应用中，该项目将特别考虑它们在加速被称为图卷积网络（GCNs）的一类神经网络的训练中的应用。许多其他的研究问题，都在基于图的方法的总主题下，也将被调查。例如，该项目将研究如何使用一种形式的超图粗化来解决“图稀疏化”问题，即寻找给定图的稀疏版本，或解决“列子集选择问题”，即从给定数据矩阵中选择重要的行（或列）。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Graph theory helps scientists and engineers model various types of relations between entities in a set, whether members of a social network, or molecules in a chemical compound for example. Not surprisingly, with the advent of data-based methodologies that work by unraveling and exploiting relations between data items, graph theory tools are finding their way in a very broad range of applications. The primary goal of this project is to examine a class of methods that manipulate graphs, specifically by developing effective multilevel algorithms that take advantage of divide and conquer approaches. In multilevel techniques, smaller and smaller graphs are extracted from some original graph with the goal of keeping as much of its intrinsic information as possible. These smaller graphs are then employed instead of the original ones, resulting in significant gains in performance. This project addresses issues that are of great relevance to many current data-based methodologies and will be applicable across various disciplines. As such it will help promote interest in problems related to the current shift toward such methodologies because its research theme blends mathematical methods, innovations in algorithms, and applications. On the educational side, special courses and tutorials will be offered to graduate students from other disciplinary fields who wish to explore research in data sciences. This project will support one graduate student per year for each of the three years.The rapid expansion of machine learning methodologies into a great variety of disciplines is pushing the demand for numerical methods that can effectively deal with large datasets. Among these methods, those based on graph representations of data figure prominently. The goal of this project is to develop effective multilevel algorithms that are rooted in graph theoretical approaches, for performing various machine learning tasks. A primary focus of the planned research is that of "graph coarsening", a technique whereby an original graph is substantially reduced in size by agglomerating nearby nodes together, to produce a faithful representative of the original graph. The project will exploit a class of methods based on multilevel coarsening, in which coarsening is applied recursively for a few levels. The ultimate goal of a multilevel coarsening approach is to make it possible to perform the heavy computations with the coarsened graph which is much smaller, resulting in much faster processing, with minimal loss in accuracy. Coarsening is an effective alternative to random sampling, a well-established method that consists of replacing the original data by a subset of its columns or rows that are selected at random or quasi- randomly. This project will study, both empirically and theoretically, various coarsening strategies. For example, coarsening will be studied from the angle of a projection method for approximating eigenvectors. Coarsening methods that try to preserve the eigenvectors exactly will also be studied. Among the many possible applications of graph coarsening the project will specifically consider their use in speeding up the training of a class of neural networks known as Graph Convolutional Networks (GCNs). A number of other research issues, all under the general theme of graph-based methods, will also be investigated. For example, the project will study how a form of hypergraph coarsening can be used to provide a solution to the "graph sparsification" problem, whereby a sparser version of a given graph is sought, or to the "column subset selection problem" which consists of selecting important rows (or columns) from a given data matrix.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.