Efficient and Effective Attributed Hypergraph Clustering via K-Nearest Neighbor Augmentation
Proceedings of the ACM on Management of Data · 13.06.2023 · 1 (2) · 1-23
DOI: 10.1145/3589261 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 20.06.2023. Verfasst von Yiran Li und 2 weiteren Autor:innen. Die Arbeit wurde bisher 19-mal zitiert (Crossref) und nennt 49 Literaturangaben. Gefördert von: Hong Kong RGC, Tencent, RGC Direct Allocation Grant.
Abstract (Originalsprache)
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.
Förderung
- Hong Kong RGC
- Tencent
- RGC Direct Allocation Grant
- National Natural Science Foundation of China
- A*STAR
Zitieren
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