HyperEF: Spectral Hypergraph Coarsening by Effective-Resistance Clustering
This work addresses the need for scalable hypergraph coarsening in applications like VLSI design, though it appears incremental as it builds on existing graph decomposition frameworks.
The paper tackles the problem of spectral coarsening of large-scale hypergraphs by introducing HyperEF, a framework that uses hyperedge effective resistances to decompose hypergraphs into clusters with few inter-cluster hyperedges, achieving over 70x runtime speedups compared to hMetis and 20x speedups compared to HyperSF in experiments on VLSI designs.
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.