EUVIMEDSkopri EUVIMED
Crossref

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

Yiran Li, Renchi Yang, Jieming Shi

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.

AstrattDettalji biblijografiċiCiteRelated studies

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}
}
Start for free →