Multilevel Graph-Based Methods for Efficient Data Exploration

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

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.