TY - GEN
T1 - HyperEF
T2 - 41st IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2022
AU - Aghdaei, Ali
AU - Feng, Zhuo
N1 - Publisher Copyright:
© 2022 Association for Computing Machinery.
PY - 2022/10/30
Y1 - 2022/10/30
N2 - This paper introduces a scalable algorithmic framework (HyperEF) for spectral coarsening (decomposition) of largescale hypergraphs by exploiting hyperedge effective resistances. Motivated by the latest theoretical framework for low-resistancediameter 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.
AB - This paper introduces a scalable algorithmic framework (HyperEF) for spectral coarsening (decomposition) of largescale hypergraphs by exploiting hyperedge effective resistances. Motivated by the latest theoretical framework for low-resistancediameter 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.
KW - effective resistance
KW - graph clustering
KW - hypergraph coarsening
KW - spectral graph theory
UR - http://www.scopus.com/inward/record.url?scp=85145652225&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85145652225&partnerID=8YFLogxK
U2 - 10.1145/3508352.3549438
DO - 10.1145/3508352.3549438
M3 - Conference contribution
AN - SCOPUS:85145652225
T3 - IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
BT - Proceedings of the 41st IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2022
Y2 - 30 October 2022 through 4 November 2022
ER -