CGC: Contrastive Graph Clustering for Community Detection and Tracking
arXiv:2204.08504 · doi:10.1145/3485447.3512160
Abstract
Given entities and their interactions in the web data, which may have occurred at different time, how can we find communities of entities and track their evolution? In this paper, we approach this important task from graph clustering perspective. Recently, state-of-the-art clustering performance in various domains has been achieved by deep clustering methods. Especially, deep graph clustering (DGC) methods have successfully extended deep clustering to graph-structured data by learning node representations and cluster assignments in a joint optimization framework. Despite some differences in modeling choices (e.g., encoder architectures), existing DGC methods are mainly based on autoencoders and use the same clustering objective with relatively minor adaptations. Also, while many real-world graphs are dynamic, previous DGC methods considered only static graphs. In this work, we develop CGC, a novel end-to-end framework for graph clustering, which fundamentally differs from existing methods. CGC learns node embeddings and cluster assignments in a contrastive graph learning framework, where positive and negative samples are carefully selected in a multi-level scheme such that they reflect hierarchical community structures and network homophily. Also, we extend CGC for time-evolving data, where temporal graph clustering is performed in an incremental learning fashion, with the ability to detect change points. Extensive evaluation on real-world graphs demonstrates that the proposed CGC consistently outperforms existing methods.
arXiv commentTheWebConf 2022 Research Track
References in corpus (17)
- Community structure in social and biological networks
- A Simple Framework for Contrastive Learning of Visual Representations
- Representation Learning with Contrastive Predictive Coding
- Maps of random walks on complex networks reveal community structure
- Learning deep representations by mutual information estimation and maximization
- Pitfalls of Graph Neural Network Evaluation
- Towards K-means-friendly Spaces: Simultaneous Deep Learning and Clustering
- Structural Deep Clustering Network
- dyngraph2vec: Capturing Network Dynamics using Dynamic Graph Representation Learning
- Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
- Learning Graph Embedding with Adversarial Training Methods
- DynGEM: Deep Embedding Method for Dynamic Graphs
- Deep Temporal Clustering : Fully Unsupervised Learning of Time-Domain Features
- EvoKG: Jointly Modeling Event Time and Network Structure for Reasoning over Temporal Knowledge Graphs
- K-Core based Temporal Graph Convolutional Network for Dynamic Graphs
- When Does Self-Supervision Help Graph Convolutional Networks?
- Attention-driven Graph Clustering Network