Modularity-based Hypergraph Clustering: Random Hypergraph Model, Hyperedge-cluster Relation, and Computation
Proceedings of the ACM on Management of Data · 13.11.2023 · 1 (3) · 1-25
DOI: 10.1145/3617335 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 13.11.2023. Verfasst von Zijin Feng und 2 weiteren Autor:innen. Die Arbeit wurde bisher 12-mal zitiert (Crossref) und nennt 60 Literaturangaben. Gefördert von: Marsden Fund, National Natural Science Foundation of China, The Shun Hing Institute of Advanced Engineering, The Chinese University of Hong Kong.
Abstract (Originalsprache)
A graph models the connections among objects. One important graph analytical task is clustering which partitions a data graph into clusters with dense innercluster connections. A line of clustering maximizes a function called modularity. Modularity-based clustering is widely adopted on dyadic graphs due to its scalability and clustering quality which depends highly on its selection of a random graph model. The random graph model decides not only which clustering is preferred - modularity measures the quality of a clustering based on its alignment to the edges of a random graph, but also the cost of computing such an alignment. Existing random hypergraph models either measure the hyperedge-cluster alignment in an All-Or-Nothing (AON) manner, losing important group-wise information, or introduce expensive alignment computation, refraining the clustering from scaling up. This paper proposes a new random hypergraph model called Hyperedge Expansion Model (HEM), a non-AON hypergraph modularity function called Partial Innerclusteredge modularity (PI) based on HEM, a clustering algorithm called Partial Innerclusteredge Clustering (PIC) that optimizes PI, and novel computation optimizations. PIC is a scalable modularity-based hypergraph clustering that can effectively capture the non-AON hyperedge-cluster relation. Our experiments show that PIC outperforms eight state-of-the-art methods on real-world hypergraphs in terms of both clustering quality and scalability and is up to five orders of magnitude faster than the baseline methods.
Förderung
- Marsden Fund
- National Natural Science Foundation of China
- The Shun Hing Institute of Advanced Engineering, The Chinese University of Hong Kong
- Ministry of Business, Innovation and Employment, New Zealand
- Research Grants Council, University Grants Committee, Hong Kong
Zitieren
APA
Feng, Z., Qiao, M., & Cheng, H. (2023). Modularity-based Hypergraph Clustering: Random Hypergraph Model, Hyperedge-cluster Relation, and Computation. Proceedings of the ACM on Management of Data, 1(3), 1-25. https://doi.org/10.1145/3617335
Vancouver
Feng Z, Qiao M, Cheng H. Modularity-based Hypergraph Clustering: Random Hypergraph Model, Hyperedge-cluster Relation, and Computation. Proceedings of the ACM on Management of Data. 2023;1(3):1-25. doi:10.1145/3617335
BibTeX
@article{Feng2023,
author = {Feng, Zijin and Qiao, Miao and Cheng, Hong},
title = {Modularity-based Hypergraph Clustering: Random Hypergraph Model, Hyperedge-cluster Relation, and Computation},
journal = {Proceedings of the ACM on Management of Data},
year = {2023},
volume = {1},
number = {3},
pages = {1--25},
doi = {10.1145/3617335}
}
EUVIMED