# Rethinking Graph Auto-Encoder Models for Attributed Graph Clustering

arXiv: https://arxiv.org/abs/2107.08562 · HTML: https://mlsanity.com/paper/2107.08562/

## Key facts

- Cited by 37 papers in the map (data through 14 Oct 2026).
- Builds on 42 of its 64 references that are in the map.
- First posted on arXiv 19 Jul 2021.

## Builds on (most cited first, 30 of 42)

- [A Simple Framework for Contrastive Learning of Visual Representations](https://mlsanity.com/paper/2002.05709/) (2020)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Momentum Contrast for Unsupervised Visual Representation Learning](https://mlsanity.com/paper/1911.05722/) (2019)
- [Bootstrap your own latent: A new approach to self-supervised Learning](https://mlsanity.com/paper/2006.07733/) (2020)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima](https://mlsanity.com/paper/1609.04836/) (2016)
- [Deep Graph Infomax](https://mlsanity.com/paper/1809.10341/) (2018)
- [Co-teaching: Robust Training of Deep Neural Networks with Extremely Noisy Labels](https://mlsanity.com/paper/1804.06872/) (2018)
- [Deep Clustering for Unsupervised Learning of Visual Features](https://mlsanity.com/paper/1807.05520/) (2018)
- [A Closer Look at Memorization in Deep Networks](https://mlsanity.com/paper/1706.05394/) (2017)
- [Learning Representations by Maximizing Mutual Information Across Views](https://mlsanity.com/paper/1906.00910/) (2019)
- [MentorNet: Learning Data-Driven Curriculum for Very Deep Neural Networks on Corrupted Labels](https://mlsanity.com/paper/1712.05055/) (2017)
- [Exploring Generalization in Deep Learning](https://mlsanity.com/paper/1706.08947/) (2017)
- [LINE: Large-scale Information Network Embedding](https://mlsanity.com/paper/1503.03578/) (2015)
- [What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimation](https://mlsanity.com/paper/2008.03703/) (2020)
- [Towards Principled Methods for Training Generative Adversarial Networks](https://mlsanity.com/paper/1701.04862/) (2017)
- [A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks](https://mlsanity.com/paper/1707.09564/) (2017)
- [Parseval Networks: Improving Robustness to Adversarial Examples](https://mlsanity.com/paper/1704.08847/) (2017)
- [Intrinsic dimension of data representations in deep neural networks](https://mlsanity.com/paper/1905.12784/) (2019)
- [A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applications](https://mlsanity.com/paper/1709.07604/) (2017)
- [Estimating the intrinsic dimension of datasets by a minimal neighborhood information](https://mlsanity.com/paper/1803.06992/) (2018)
- [Decoupling "when to update" from "how to update"](https://mlsanity.com/paper/1706.02613/) (2017)
- [struc2vec: Learning Node Representations from Structural Identity](https://mlsanity.com/paper/1704.03165/) (2017)
- [Dimensionality-Driven Learning with Noisy Labels](https://mlsanity.com/paper/1806.02612/) (2018)
- [Attributed Graph Clustering: A Deep Attentional Embedding Approach](https://mlsanity.com/paper/1906.06532/) (2019)
- [A Survey on Network Embedding](https://mlsanity.com/paper/1711.08752/) (2017)
- [When Does Self-Supervision Help Graph Convolutional Networks?](https://mlsanity.com/paper/2006.09136/) (2020)

## Built on by (most cited first, 30 of 37)

- [Hard Sample Aware Network for Contrastive Deep Graph Clustering](https://mlsanity.com/paper/2212.08665/) (2022)
- [Cluster-guided Contrastive Graph Clustering Network](https://mlsanity.com/paper/2301.01098/) (2023)
- [Simple Contrastive Graph Clustering](https://mlsanity.com/paper/2205.07865/) (2022)
- [Graph Anomaly Detection via Multi-Scale Contrastive Learning Networks with Augmented View](https://mlsanity.com/paper/2212.00535/) (2022)
- [Beyond Homophily: Reconstructing Structure for Graph-agnostic Clustering](https://mlsanity.com/paper/2305.02931/) (2023)
- [A Survey of Deep Graph Clustering: Taxonomy, Challenge, Application, and Open Resource](https://mlsanity.com/paper/2211.12875/) (2022)
- [Reinforcement Graph Clustering with Unknown Cluster Number](https://mlsanity.com/paper/2308.06827/) (2023)
- [Improved Dual Correlation Reduction Network](https://mlsanity.com/paper/2202.12533/) (2022)
- [Reliable Node Similarity Matrix Guided Contrastive Graph Clustering](https://mlsanity.com/paper/2408.03765/) (2024)
- [GraphLearner: Graph Node Clustering with Fully Learnable Augmentation](https://mlsanity.com/paper/2212.03559/) (2022)
- [G2uardFL: Safeguarding Federated Learning Against Backdoor Attacks through Attributed Client Graph Clustering](https://mlsanity.com/paper/2306.04984/) (2023)
- [Effective Clustering on Large Attributed Bipartite Graphs](https://mlsanity.com/paper/2405.11922/) (2024)
- [GC-Flow: A Graph-Based Flow Network for Effective Clustering](https://mlsanity.com/paper/2305.17284/) (2023)
- [Provable Filter for Real-world Graph Clustering](https://mlsanity.com/paper/2403.03666/) (2024)
- [A Comprehensive Survey on Graph Summarization with Graph Neural Networks](https://mlsanity.com/paper/2302.06114/) (2023)
- [Self-Contrastive Graph Diffusion Network](https://mlsanity.com/paper/2307.14613/) (2023)
- [A Contrastive Variational Graph Auto-Encoder for Node Clustering](https://mlsanity.com/paper/2312.16830/) (2023)
- [CIMAGE: Exploiting the Conditional Independence in Masked Graph Auto-encoders](https://mlsanity.com/paper/2503.07852/) (2025)
- [Unsupervised Graph Clustering with Deep Structural Entropy](https://mlsanity.com/paper/2505.14040/) (2025)
- [Bridging Academia and Industry: A Comprehensive Benchmark for Attributed Graph Clustering](https://mlsanity.com/paper/2602.08519/) (2026)
- [EGRC-Net: Embedding-induced Graph Refinement Clustering Network](https://mlsanity.com/paper/2211.10627/) (2022)
- [Wasserstein Adversarially Regularized Graph Autoencoder](https://mlsanity.com/paper/2111.04981/) (2021)
- [The Map Equation Goes Neural: Mapping Network Flows with Graph Neural Networks](https://mlsanity.com/paper/2310.01144/) (2023)
- [Block-Diagonal Guided DBSCAN Clustering](https://mlsanity.com/paper/2404.01341/) (2024)
- [Scalable and Adaptive Spectral Embedding for Attributed Graph Clustering](https://mlsanity.com/paper/2408.05765/) (2024)
- [Dual-Optimized Adaptive Graph Reconstruction for Multi-View Graph Clustering](https://mlsanity.com/paper/2410.22983/) (2024)
- [SPARC: Spectral Architectures Tackling the Cold-Start Problem in Graph Learning](https://mlsanity.com/paper/2411.01532/) (2024)
- [HyReaL: Clustering Attributed Graph via Hyper-Complex Space Representation Learning](https://mlsanity.com/paper/2411.14727/) (2024)
- [Beyond the Academic Monoculture: A Unified Framework and Industrial Perspective for Attributed Graph Clustering](https://mlsanity.com/paper/2603.20829/) (2026)
- [Modularity aided consistent attributed graph clustering via coarsening](https://mlsanity.com/paper/2407.07128/) (2024)

## Abstract (arXiv)

Most recent graph clustering methods have resorted to Graph Auto-Encoders (GAEs) to perform joint clustering and embedding learning. However, two critical issues have been overlooked. First, the accumulative error, inflicted by learning with noisy clustering assignments, degrades the effectiveness and robustness of the clustering model. This problem is called Feature Randomness. Second, reconstructing the adjacency matrix sets the model to learn irrelevant similarities for the clustering task. This problem is called Feature Drift. Interestingly, the theoretical relation between the aforementioned problems has not yet been investigated. We study these issues from two aspects: (1) there is a trade-off between Feature Randomness and Feature Drift when clustering and reconstruction are performed at the same level, and (2) the problem of Feature Drift is more pronounced for GAE models, compared with vanilla auto-encoder models, due to the graph convolutional operation and the graph decoding design. Motivated by these findings, we reformulate the GAE-based clustering methodology. Our solution is two-fold. First, we propose a sampling operator Xi that triggers a protection mechanism against the noisy clustering assignments. Second, we propose an operator Upsilon that triggers a correction mechanism against Feature Drift by gradually transforming the reconstructed graph into a clustering-oriented one. As principal advantages, our solution grants a considerable improvement in clustering effectiveness and robustness and can be easily tailored to existing GAE models.