HyperSF: Spectral Hypergraph Coarsening via Flow-based Local Clustering

Ali Aghdaei, Zhiqiang Zhao, Zhuo Feng

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

3 Scopus citations

Abstract

Hypergraphs allow modeling problems with multi-way high-order relationships. However, the computational cost of most existing hypergraph-based algorithms can be heavily dependent upon the input hypergraph sizes. To address the ever-increasing computational challenges, graph coarsening can be potentially applied for preprocessing a given hypergraph by aggressively aggregating its vertices (nodes). However, state-of-the-art hypergraph partitioning (clustering) methods that incorporate heuristic graph coarsening techniques are not optimized for preserving the structural (global) properties of hypergraphs. In this work, we propose an efficient spectral hypergraph coarsening scheme (HyperSF) for well preserving the original spectral (structural) properties of hypergraphs. Our approach leverages a recent strongly-local max-flow-based clustering algorithm for detecting the sets of hypergraph vertices that minimize ratio cut. To further improve the algorithm efficiency, we propose a divide-and-conquer scheme by leveraging spectral clustering of the bipartite graphs corresponding to the original hypergraphs. Our experimental results for a variety of hypergraphs extracted from real-world VLSI design benchmarks show that the proposed hypergraph coarsening algorithm can significantly improve the multi-way conductance of hypergraph clustering as well as runtime efficiency when compared with existing state-of-the-art algorithms.

Original languageEnglish
Title of host publication2021 40th IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2021 - Proceedings
ISBN (Electronic)9781665445078
DOIs
StatePublished - 2021
Event40th IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2021 - Munich, Germany
Duration: 1 Nov 20214 Nov 2021

Publication series

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

Conference

Conference40th IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2021
Country/TerritoryGermany
CityMunich
Period1/11/214/11/21

Keywords

  • Graph clustering
  • Hypergraph coarsening
  • Spectral graph theory

Fingerprint

Dive into the research topics of 'HyperSF: Spectral Hypergraph Coarsening via Flow-based Local Clustering'. Together they form a unique fingerprint.

Cite this