Revisiting Modularity Maximization for Graph Clustering: A Contrastive Learning Perspective
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909228136923136 |
|---|---|
| author | Liu, Yunfei Li, Jintang Chen, Yuehe Wu, Ruofan Wang, Ericbk Zhou, Jing Tian, Sheng Shen, Shuheng Fu, Xing Meng, Changhua Wang, Weiqiang Chen, Liang |
| author_facet | Liu, Yunfei Li, Jintang Chen, Yuehe Wu, Ruofan Wang, Ericbk Zhou, Jing Tian, Sheng Shen, Shuheng Fu, Xing Meng, Changhua Wang, Weiqiang Chen, Liang |
| contents | Graph clustering, a fundamental and challenging task in graph mining, aims to classify nodes in a graph into several disjoint clusters. In recent years, graph contrastive learning (GCL) has emerged as a dominant line of research in graph clustering and advances the new state-of-the-art. However, GCL-based methods heavily rely on graph augmentations and contrastive schemes, which may potentially introduce challenges such as semantic drift and scalability issues. Another promising line of research involves the adoption of modularity maximization, a popular and effective measure for community detection, as the guiding principle for clustering tasks. Despite the recent progress, the underlying mechanism of modularity maximization is still not well understood. In this work, we dig into the hidden success of modularity maximization for graph clustering. Our analysis reveals the strong connections between modularity maximization and graph contrastive learning, where positive and negative examples are naturally defined by modularity. In light of our results, we propose a community-aware graph clustering framework, coined MAGI, which leverages modularity maximization as a contrastive pretext task to effectively uncover the underlying information of communities in graphs, while avoiding the problem of semantic drift. Extensive experiments on multiple graph datasets verify the effectiveness of MAGI in terms of scalability and clustering performance compared to state-of-the-art graph clustering methods. Notably, MAGI easily scales a sufficiently large graph with 100M nodes while outperforming strong baselines. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_14288 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Revisiting Modularity Maximization for Graph Clustering: A Contrastive Learning Perspective Liu, Yunfei Li, Jintang Chen, Yuehe Wu, Ruofan Wang, Ericbk Zhou, Jing Tian, Sheng Shen, Shuheng Fu, Xing Meng, Changhua Wang, Weiqiang Chen, Liang Machine Learning Artificial Intelligence Graph clustering, a fundamental and challenging task in graph mining, aims to classify nodes in a graph into several disjoint clusters. In recent years, graph contrastive learning (GCL) has emerged as a dominant line of research in graph clustering and advances the new state-of-the-art. However, GCL-based methods heavily rely on graph augmentations and contrastive schemes, which may potentially introduce challenges such as semantic drift and scalability issues. Another promising line of research involves the adoption of modularity maximization, a popular and effective measure for community detection, as the guiding principle for clustering tasks. Despite the recent progress, the underlying mechanism of modularity maximization is still not well understood. In this work, we dig into the hidden success of modularity maximization for graph clustering. Our analysis reveals the strong connections between modularity maximization and graph contrastive learning, where positive and negative examples are naturally defined by modularity. In light of our results, we propose a community-aware graph clustering framework, coined MAGI, which leverages modularity maximization as a contrastive pretext task to effectively uncover the underlying information of communities in graphs, while avoiding the problem of semantic drift. Extensive experiments on multiple graph datasets verify the effectiveness of MAGI in terms of scalability and clustering performance compared to state-of-the-art graph clustering methods. Notably, MAGI easily scales a sufficiently large graph with 100M nodes while outperforming strong baselines. |
| title | Revisiting Modularity Maximization for Graph Clustering: A Contrastive Learning Perspective |
| topic | Machine Learning Artificial Intelligence |
| url | https://arxiv.org/abs/2406.14288 |