Efficient and Effective Attributed Hypergraph Clustering via K-Nearest Neighbor Augmentation

Yiran Li, Renchi Yang, Jieming Shi*

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review


Hypergraphs are an omnipresent data structure used to represent high-order interactions among entities. Given a hypergraph H wherein nodes are associated with attributes, attributed hypergraph clustering (AHC) aims to partition the nodes in H into k disjoint clusters, such that intra-cluster nodes are closely connected and share similar attributes, while inter-cluster nodes are far apart and dissimilar. It is highly challenging to capture multi-hop connections via nodes or attributes on large attributed hypergraphs for accurate clustering. Existing AHC solutions suffer from issues of prohibitive computational costs, sub-par clustering quality, or both. In this paper, we present AHCKA, an efficient approach to AHC, which achieves state-of-the-art result quality via several algorithmic designs. Under the hood, AHCKA includes three key components: (i) a carefully-crafted K-nearest neighbor augmentation strategy for the optimized exploitation of attribute information on hypergraphs, (ii) a joint hypergraph random walk model to devise an effective optimization objective towards AHC, and (iii) a highly efficient solver with speedup techniques for the problem optimization. Extensive experiments, comparing AHCKA against 15 baselines over 8 real attributed hypergraphs, reveal that AHCKA is superior to existing competitors in terms of clustering quality, while often being up to orders of magnitude faster.
Original languageEnglish
Article number116
Number of pages23
JournalProceedings of the ACM on Management of Data
Issue number2
Publication statusPublished - Jun 2023

User-Defined Keywords

  • hypergraph
  • random walk
  • clustering
  • eigenvector


Dive into the research topics of 'Efficient and Effective Attributed Hypergraph Clustering via K-Nearest Neighbor Augmentation'. Together they form a unique fingerprint.

Cite this