Efficient and Effective Attributed Hypergraph Clustering via K-Nearest Neighbor Augmentation
Proceedings of the ACM on Management of Data · 2023-06-13 · 1 (2) · 1-23
DOI: 10.1145/3589261 ↗At a glance
Journal article in Proceedings of the ACM on Management of Data, published online on 2023-06-20. Written by Yiran Li and 2 co-authors. Cited 19 times so far (Crossref); 49 references. Funded by: Hong Kong RGC, Tencent, RGC Direct Allocation Grant.
Abstract (original language)
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.
Funding
- Hong Kong RGC
- Tencent
- RGC Direct Allocation Grant
- National Natural Science Foundation of China
- A*STAR
Cite
APA
Li, Y., Yang, R., & Shi, J. (2023). Efficient and Effective Attributed Hypergraph Clustering via K-Nearest Neighbor Augmentation. Proceedings of the ACM on Management of Data, 1(2), 1-23. https://doi.org/10.1145/3589261
Vancouver
Li Y, Yang R, Shi J. Efficient and Effective Attributed Hypergraph Clustering via K-Nearest Neighbor Augmentation. Proceedings of the ACM on Management of Data. 2023;1(2):1-23. doi:10.1145/3589261
BibTeX
@article{Li2023,
author = {Li, Yiran and Yang, Renchi and Shi, Jieming},
title = {Efficient and Effective Attributed Hypergraph Clustering via K-Nearest Neighbor Augmentation},
journal = {Proceedings of the ACM on Management of Data},
year = {2023},
volume = {1},
number = {2},
pages = {1--23},
doi = {10.1145/3589261}
}
EUVIMED