  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(n^2)$ time to build graphs and the graph convolution requires
nearly $\mathcal O(n^2)$ for a dense graph and $\mathcal O(|\mathcal{E}|)$ for
a sparse one with $|\mathcal{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(n^2)$ and $\mathcal O(|\mathcal{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.
