# HyperEF: Spectral Hypergraph Coarsening by Effective-Resistance Clustering

arXiv: https://arxiv.org/abs/2210.14813 · HTML: https://mlsanity.com/paper/2210.14813/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 41 references that are in the map.
- First posted on arXiv 26 Oct 2022.

## Builds on (most cited first, 19 of 19)

- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Multipole Graph Neural Operator for Parametric Partial Differential Equations](https://mlsanity.com/paper/2006.09535/) (2020)
- [GCN-RL Circuit Designer: Transferable Transistor Sizing with Graph Neural Networks and Reinforcement Learning](https://mlsanity.com/paper/2005.00406/) (2020)
- [GraphZoom: A multi-level spectral approach for accurate and scalable graph embedding](https://mlsanity.com/paper/1910.02370/) (2019)
- [Spectrally approximating large graphs with smaller graphs](https://mlsanity.com/paper/1802.07510/) (2018)
- [Learning continuous-time PDEs from sparse data with graph neural networks](https://mlsanity.com/paper/2006.08956/) (2020)
- [Graph coarsening: From scientific computing to machine learning](https://mlsanity.com/paper/2106.11863/) (2021)
- [Graph Clustering using Effective Resistance](https://mlsanity.com/paper/1711.06530/) (2017)
- [Spectral Sparsification of Hypergraphs](https://mlsanity.com/paper/1807.04974/) (2018)
- [An SDP-Based Algorithm for Linear-Sized Spectral Sparsification](https://mlsanity.com/paper/1702.08415/) (2017)
- [GRASS: Graph Spectral Sparsification Leveraging Scalable Spectral Perturbation Analysis](https://mlsanity.com/paper/1911.04382/) (2019)
- [Spectral Hypergraph Sparsifiers of Nearly Linear Size](https://mlsanity.com/paper/2106.02353/) (2021)
- [SF-GRASS: Solver-Free Graph Spectral Sparsification](https://mlsanity.com/paper/2008.07633/) (2020)
- [Towards Tight Bounds for Spectral Sparsification of Hypergraphs](https://mlsanity.com/paper/2011.06530/) (2020)
- [HyperSF: Spectral Hypergraph Coarsening via Flow-based Local Clustering](https://mlsanity.com/paper/2108.07901/) (2021)
- [Similarity-Aware Spectral Sparsification by Edge Filtering](https://mlsanity.com/paper/1711.05135/) (2017)

## Built on by (most cited first, 6 of 6)

- [inGRASS: Incremental Graph Spectral Sparsification via Low-Resistance-Diameter Decomposition](https://mlsanity.com/paper/2402.16990/) (2024)
- [A Spectral Framework for Evaluating Geodesic Distances Between Graphs](https://mlsanity.com/paper/2406.10500/) (2024)
- [SGM-PINN: Sampling Graphical Models for Faster Training of Physics-Informed Neural Networks](https://mlsanity.com/paper/2407.07358/) (2024)
- [SHyPar: A Spectral Coarsening Approach to Hypergraph Partitioning](https://mlsanity.com/paper/2410.10875/) (2024)
- [T2T-LA: A Topology-to-Topology LLM Agent for Graph Learning with Neither Feature Access nor Task Knowledge](https://mlsanity.com/paper/2512.08964/) (2025)
- [Anchor-guided Hypergraph Condensation with Dual-level Discrimination](https://mlsanity.com/paper/2605.10001/) (2026)

## Abstract (arXiv)

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.