Graph coarsening: from scientific computing to machine learning
Graph coarsening: from scientific computing to machine learning
复制标题
DOI：
10.1007/s40324-021-00282-x
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Jie Chen;Y. Saad;Zecheng Zhang
中科院分区：
文献类型：
--
作者：
Jie Chen;Y. Saad;Zecheng Zhang
图粗化或图约简的一般方法在科学计算中一直是非常有用和普遍存在的工具，现在它刚刚开始在机器学习中产生类似的影响。本文的目标是广泛研究已成功部署在科学计算中的粗化技术，并了解类似的原理如何在与机器学习相关的最新应用中找到自己的方式。在科学计算中，粗化在代数多重网格方法以及相关的多级不完全LU分解类中起着核心作用。在机器学习中，图粗化有各种名称，例如，图形下采样或图形缩减。在大多数情况下，它的目标是用一个节点数较少，但结构和特征与原始图相似的图来替换原始图。如将看到的，这些方法中的常见策略是依赖于谱特性来定义粗略图。
The general method of graph coarsening or graph reduction has been a remarkably useful and ubiquitous tool in scientific computing and it is now just starting to have a similar impact in machine learning. The goal of this paper is to take a broad look into coarsening techniques that have been successfully deployed in scientific computing and see how similar principles are finding their way in more recent applications related to machine learning. In scientific computing, coarsening plays a central role in algebraic multigrid methods as well as the related class of multilevel incomplete LU factorizations. In machine learning, graph coarsening goes under various names, e.g., graph downsampling or graph reduction. Its goal in most cases is to replace some original graph by one which has fewer nodes, but whose structure and characteristics are similar to those of the original graph. As will be seen, a common strategy in these methods is to rely on spectral properties to define the coarse graph.