Spectral Graph Partitioning Using Geodesic Distance-based Projection
Spectral Graph Partitioning Using Geodesic Distance-based Projection
复制标题
使用基于测地距离的投影进行谱图划分
DOI：
10.1109/hpec49654.2021.9622831
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Sakurai Tetsuya
中科院分区：
文献类型：
--
作者：
Futamura Yasunori;Wakaki Ryota;Sakurai Tetsuya
图划分问题是最基本的组合问题之一，有着广泛的应用。在本文中，我们提出了一个有效的方法来实现谱图划分，有一个坚实的理论基础，但实际上是效率低于标准的多级分区。所提出的方法是基于一个图形拉普拉斯矩阵的特征向量的近似使用测地线距离为基础的方法，而不是一个标准的线性代数方法的基础向量。这种基于测地线距离的方法是使我们的方法与多级分区相比具有竞争力的关键。我们的方法的主要组成部分是广度优先搜索和稀疏矩阵向量积，这是在高性能计算领域深入研究的主要内核。在共享内存并行设置的性能评估的基础上，我们证明了我们的方法是可比的标准分区的质量和速度。我们还表明，我们的方法有可能促进可再生性感知的并行分区。
The graph partitioning problem is one of the most fundamental combinatorial problems with a wide variety of applications. In this paper, we propose an efficient approach for implementing spectral graph partitioning that has a solid theoretical foundation but is practically less efficient than standard multilevel partitioners. The proposed method is based on the approximation of the eigenvectors of a graph-Laplacian matrix derived using the basis vectors by geodesic distance-based approach, instead of a standard linear algebraic approach. This geodesic distance-based approach is the key to making our method competitive in comparison to the multilevel partitioners. The primary building blocks of our method are the breadth-first search and the sparse matrix-vector product, which are the main kernels intensively studied in the high-performance computing field. Based on a performance evaluation in the shared-memory parallel setting, we demonstrate that our method is comparable to standard partitioners in terms of both quality and speed. We also show that our method has the potential to facilitate reproducibility-aware parallel partitioning.