HyperEF: Spectral hypergraph coarsening by effective-resistance clustering

Ali Aghdaei, Zhuo Feng

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publicationProceedings of the 41st IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2022
ISBN (Electronic)9781450392174
DOIs
StatePublished - 30 Oct 2022
Event41st IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2022 - San Diego, United States
Duration: 30 Oct 20224 Nov 2022

Publication series

NameIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
ISSN (Print)1092-3152

Conference

Conference41st IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2022
Country/TerritoryUnited States
CitySan Diego
Period30/10/224/11/22

Keywords

  • effective resistance
  • graph clustering
  • hypergraph coarsening
  • spectral graph theory

Fingerprint

Dive into the research topics of 'HyperEF: Spectral hypergraph coarsening by effective-resistance clustering'. Together they form a unique fingerprint.

Cite this