  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.
