TY - JOUR
T1 - A versatile framework for attributed network clustering via K-nearest neighbor augmentation
AU - Li, Yiran
AU - Guo, Gongyao
AU - Shi, Jieming
AU - Yang, Renchi
AU - Shen, Shiqi
AU - Li, Qing
AU - Luo, Jun
N1 - The work described in this paper was fully supported by grants from the Research Grants Council of the Hong Kong Special Administrative Region, China (No. PolyU 25201221, PolyU 15205224, PolyU 15200023). Jieming Shi is supported by NSFC No. 62202404. Renchi Yang is supported by the NSFC YSF grant (No. 62302414) and Hong Kong RGC ECS grant (No. 22202623). Jun Luo is supported by The Innovation and Technology Fund (Ref. ITP/067/23LP). This work is supported by Tencent Technology Co., Ltd. P0048511. Open access funding provided by The Hong Kong Polytechnic University.
Publisher Copyright:
© The Author(s) 2024.
PY - 2024/11
Y1 - 2024/11
N2 - Attributed networks containing entity-specific information in node attributes are ubiquitous in modeling social networks, e-commerce, bioinformatics, etc. Their inherent network topology ranges from simple graphs to hypergraphs with high-order interactions and multiplex graphs with separate layers. An important graph mining task is node clustering, aiming to partition the nodes of an attributed network 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 for effective clustering on multiple types of attributed networks. In this paper, we first present AHCKA as an efficient approach to attributed hypergraph clustering (AHC). AHCKA includes a carefully-crafted K-nearest neighbor augmentation strategy for the optimized exploitation of attribute information on hypergraphs, a joint hypergraph random walk model to devise an effective AHC objective, and an efficient solver with speedup techniques for the objective optimization. The proposed techniques are extensible to various types of attributed networks, and thus, we develop ANCKA as a versatile attributed network clustering framework, capable of attributed graph clustering, attributed multiplex graph clustering, and AHC. Moreover, we devise ANCKA-GPU with algorithmic designs tailored for GPU acceleration to boost efficiency. We have conducted extensive experiments to compare our methods with 19 competitors on 8 attributed hypergraphs, 16 competitors on 6 attributed graphs, and 16 competitors on 3 attributed multiplex graphs, all demonstrating the superb clustering quality and efficiency of our methods.
AB - Attributed networks containing entity-specific information in node attributes are ubiquitous in modeling social networks, e-commerce, bioinformatics, etc. Their inherent network topology ranges from simple graphs to hypergraphs with high-order interactions and multiplex graphs with separate layers. An important graph mining task is node clustering, aiming to partition the nodes of an attributed network 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 for effective clustering on multiple types of attributed networks. In this paper, we first present AHCKA as an efficient approach to attributed hypergraph clustering (AHC). AHCKA includes a carefully-crafted K-nearest neighbor augmentation strategy for the optimized exploitation of attribute information on hypergraphs, a joint hypergraph random walk model to devise an effective AHC objective, and an efficient solver with speedup techniques for the objective optimization. The proposed techniques are extensible to various types of attributed networks, and thus, we develop ANCKA as a versatile attributed network clustering framework, capable of attributed graph clustering, attributed multiplex graph clustering, and AHC. Moreover, we devise ANCKA-GPU with algorithmic designs tailored for GPU acceleration to boost efficiency. We have conducted extensive experiments to compare our methods with 19 competitors on 8 attributed hypergraphs, 16 competitors on 6 attributed graphs, and 16 competitors on 3 attributed multiplex graphs, all demonstrating the superb clustering quality and efficiency of our methods.
KW - Attributed Graph
KW - Clustering
KW - GPU Computing
KW - KNN
KW - Random Walks
UR - http://www.scopus.com/inward/record.url?scp=85204249290&partnerID=8YFLogxK
U2 - 10.1007/s00778-024-00875-8
DO - 10.1007/s00778-024-00875-8
M3 - Journal article
AN - SCOPUS:85204249290
SN - 1066-8888
VL - 33
SP - 1913
EP - 1943
JO - VLDB Journal
JF - VLDB Journal
IS - 6
ER -