# AnchorGAE: General Data Clustering via O(n) Bipartite Graph Convolution

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 74 references that are in the map.
- First posted on arXiv 12 Nov 2021.

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

- [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)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [Unsupervised Deep Embedding for Clustering Analysis](https://mlsanity.com/paper/1511.06335/) (2015)
- [Contrastive Multi-View Representation Learning on Graphs](https://mlsanity.com/paper/2006.05582/) (2020)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling](https://mlsanity.com/paper/1801.10247/) (2018)
- [Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1905.07953/) (2019)
- [Adversarial Autoencoders](https://mlsanity.com/paper/1511.05644/) (2015)
- [Contrastive Clustering](https://mlsanity.com/paper/2009.09687/) (2020)
- [Spatial-Temporal Fusion Graph Neural Networks for Traffic Flow Forecasting](https://mlsanity.com/paper/2012.09641/) (2020)
- [Joint Unsupervised Learning of Deep Representations and Image Clusters](https://mlsanity.com/paper/1604.03628/) (2016)
- [Learning Discrete Representations via Information Maximizing Self-Augmented Training](https://mlsanity.com/paper/1702.08720/) (2017)
- [Attributed Graph Clustering: A Deep Attentional Embedding Approach](https://mlsanity.com/paper/1906.06532/) (2019)
- [Structural Deep Clustering Network](https://mlsanity.com/paper/2002.01633/) (2020)
- [GraphNorm: A Principled Approach to Accelerating Graph Neural Network Training](https://mlsanity.com/paper/2009.03294/) (2020)
- [Deep Clustering via Joint Convolutional Autoencoder Embedding and Relative Entropy Minimization](https://mlsanity.com/paper/1704.06327/) (2017)
- [Attributed Graph Clustering via Adaptive Graph Convolution](https://mlsanity.com/paper/1906.01210/) (2019)
- [SpectralNet: Spectral Clustering using Deep Neural Networks](https://mlsanity.com/paper/1801.01587/) (2018)
- [Symmetric Graph Convolutional Autoencoder for Unsupervised Graph Representation Learning](https://mlsanity.com/paper/1908.02441/) (2019)
- [Deep Spectral Clustering using Dual Autoencoder Network](https://mlsanity.com/paper/1904.13113/) (2019)

## Built on by (most cited first, 1 of 1)

- [GNN-LoFI: a Novel Graph Neural Network through Localized Feature-based Histogram Intersection](https://mlsanity.com/paper/2401.09193/) (2024)

## Abstract (arXiv)

Since the representative capacity of graph-based clustering methods is usually limited by the graph constructed on the original features, it is attractive to find whether graph neural networks (GNNs) can be applied to augment the capacity. The core problems mainly come from two aspects: (1) the graph is unavailable in the most clustering scenes so that how to construct high-quality graphs on the non-graph data is usually the most important part; (2) given n samples, the graph-based clustering methods usually consume at least mathcal O(n2) time to build graphs and the graph convolution requires nearly mathcal O(n2) for a dense graph and mathcal O(|E|) for a sparse one with |E| edges. Accordingly, both graph-based clustering and GNNs suffer from the severe inefficiency problem. To tackle these problems, we propose a novel clustering method, AnchorGAE, with the self-supervised estimation of graph and efficient graph convolution. We first show how to convert a non-graph dataset into a graph dataset, by introducing the generative graph model and anchors. We then show that the constructed bipartite graph can reduce the computational complexity of graph convolution from mathcal O(n2) and mathcal O(|E|) to mathcal O(n). The succeeding steps for clustering can be easily designed as mathcal O(n) operations. Interestingly, the anchors naturally lead to siamese architecture with the help of the Markov process. Furthermore, the estimated bipartite graph is updated dynamically according to the features extracted by GNN, to promote the quality of the graph. However, we theoretically prove that the self-supervised paradigm frequently results in a collapse that often occurs after 2-3 update iterations in experiments, especially when the model is well-trained. A specific strategy is accordingly designed to prevent the collapse.