论文标题
Hyperef：通过有效抗性聚类结块的光谱超图
HyperEF: Spectral Hypergraph Coarsening by Effective-Resistance Clustering
论文作者
论文摘要
本文通过利用超边缘有效的电阻，引入了一种可扩展的算法框架（Hyperef），用于大规模超图的光谱（分解）。 Hyperef的旨在将大型超图将大型超图分解为仅具有少数群间间超蛋白质的多个节点簇的最新理论框架，旨在将大型超图分解为多个节点簇。 Hyperef中的关键成分是用于估算超边缘有效电阻的近几条时间算法，该算法允许在超图上定义的最新基于基于扩散的非线性二次操作员。为了达到良好的运行时可伸缩性，Hyperef在Krylov子空间（或近似eigensubspace）内进行了搜索，以识别几乎最佳的向量，以近似超过有效的电阻。此外，已经引入了用于达到更大的节点变高比的多级光谱超图分解的节点重量传播方案。与最先进的超图解（聚类）方法相比，对现实世界VLSI设计的广泛实验结果表明，Hyperef可以更有效地更加粗糙（分解）超图（分解）超图，而不会丢失原始超级差异的关键结构（光谱）特性，而是超过70美元的$ 70 \ times $ $速度超过了$ 20的$ 20 $ 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\times$ runtime speedups over hMetis and $20\times$ speedups over HyperSF.
