HyperEF: Spectral Hypergraph Coarsening by Effective-Resistance Clustering
HyperEF: Spectral Hypergraph Coarsening by Effective-Resistance Clustering
复制标题
DOI：
10.1145/3508352.3549438
复制
发表时间：
2022-10
期刊：
影响因子：
--
通讯作者：
Ali Aghdaei;Zhuo Feng
中科院分区：
文献类型：
--
作者：
Ali Aghdaei;Zhuo Feng
介绍了一种利用超边有效电阻对大规模超图进行谱粗化(分解)的可扩展算法框架(HyperEF)。在最新的简单图低阻直径分解理论框架的启发下，HyperEF的目标是将大型超图分解成只有少量簇间超边的多个节点簇。HyperEF的关键部分是用于估计超边有效电阻的近线性时间算法，该算法允许结合定义在超图上的最新的基于扩散的非线性二次算子。为了实现良好的运行时可伸缩性，HyperEF在Krylov子空间(或近似本征子空间)内搜索，以识别近似超边缘有效阻力的近似最优向量。此外，为了获得更高的节点粗化率，还提出了一种用于多层谱超图分解的节点权重传播方案。与最新的超图划分(聚类)方法相比，在实际VLSI设计上的大量实验结果表明，HyperEF可以在不丢失原始超图的关键结构(谱)属性的情况下更有效地粗化(分解)超图，同时在hMetis和HyperSF上分别获得70倍以上和20倍以上的加速比。
This paper introduces a scalable algorithmic framework (HyperEF) for spectral coarsening (decomposition) of large-scale hypergraphs by exploiting hyperedge effective resistances. Motivated by the latest theoretical framework for low-resistance-diameter decomposition of simple graphs, HyperEF aims at decomposing large hypergraphs into multiple node clusters with only a few inter-cluster hyperedges. The key component in HyperEF is a nearly-linear time algorithm for estimating hyperedge effective resistances, which allows incorporating the latest diffusion-based non-linear quadratic operators defined on hypergraphs. To achieve good runtime scalability, HyperEF searches within the Krylov subspace (or approximate eigensubspace) for identifying the nearly-optimal vectors for approximating the hyperedge effective resistances. In addition, a node weight propagation scheme for multilevel spectral hypergraph decomposition has been introduced for achieving even greater node coarsening ratios. When compared with state-of-the-art hypergraph partitioning (clustering) methods, extensive experiment results on real-world VLSI designs show that HyperEF can more effectively coarsen (decompose) hypergraphs without losing key structural (spectral) properties of the original hypergraphs, while achieving over 70× runtime speedups over hMetis and 20× speedups over HyperSF.