HyperSF: Spectral Hypergraph Coarsening via Flow-based Local Clustering
HyperSF: Spectral Hypergraph Coarsening via Flow-based Local Clustering
复制标题
DOI：
10.1109/iccad51958.2021.9643555
复制
发表时间：
2021-08
期刊：
影响因子：
--
通讯作者：
Ali Aghdaei;Zhiqiang Zhao;Zhuo Feng
中科院分区：
文献类型：
--
作者：
Ali Aghdaei;Zhiqiang Zhao;Zhuo Feng
超图允许用多路高阶关系建模问题。然而，大多数现有的基于超图的算法的计算成本可以严重依赖于输入超图的大小。为了解决日益增长的计算挑战，图粗化可以潜在地应用于通过积极地聚集其顶点（节点）来预处理给定的超图。然而，结合启发式图粗化技术的最先进的超图分区（聚类）方法并没有优化用于保持超图的结构（全局）属性。在这项工作中，我们提出了一个有效的谱超图粗化计划（HyperSF），以及保持原有的谱（结构）超图的属性。我们的方法利用最近的强本地最大流为基础的聚类算法检测超图顶点集，最大限度地减少比率削减。为了进一步提高算法的效率，我们提出了一个分而治之的计划，利用谱聚类的二分图对应的原始超图。我们的实验结果表明，从现实世界中的VLSI设计基准提取的各种超图，所提出的超图粗化算法可以显着提高超图聚类的多路电导以及运行时的效率相比，现有的国家的最先进的算法。
Hypergraphs allow modeling problems with multiway high-order relationships. However, the computational cost of most existing hypergraph-based algorithms can be heavily dependent upon the input hypergraph sizes. To address the ever-increasing computational challenges, graph coarsening can be potentially applied for preprocessing a given hypergraph by aggressively aggregating its vertices (nodes). However, state-of-the-art hypergraph partitioning (clustering) methods that incorporate heuristic graph coarsening techniques are not optimized for preserving the structural (global) properties of hypergraphs. In this work, we propose an efficient spectral hypergraph coarsening scheme (HyperSF) for well preserving the original spectral (structural) properties of hypergraphs. Our approach leverages a recent strongly-local max-flow-based clustering algorithm for detecting the sets of hypergraph vertices that minimize ratio cut. To further improve the algorithm efficiency, we propose a divide-and-conquer scheme by leveraging spectral clustering of the bipartite graphs corresponding to the original hypergraphs. Our experimental results for a variety of hypergraphs extracted from real-world VLSI design benchmarks show that the proposed hypergraph coarsening algorithm can significantly improve the multi-way conductance of hypergraph clustering as well as runtime efficiency when compared with existing state-of-the-art algorithms.