  Graph clustering, aiming to partition nodes of a graph into various groups
via an unsupervised approach, is an attractive topic in recent years. To
improve the representative ability, several graph auto-encoder (GAE) models,
which are based on semi-supervised graph convolution networks (GCN), have been
developed and they achieve good results compared with traditional clustering
methods. However, all existing methods either fail to utilize the orthogonal
property of the representations generated by GAE, or separate the clustering
and the learning of neural networks. We first prove that the relaxed k-means
will obtain an optimal partition in the inner-products used space. Driven by
theoretical analysis about relaxed k-means, we design a specific GAE-based
model for graph clustering to be consistent with the theory, namely Embedding
Graph Auto-Encoder (EGAE). Meanwhile, the learned representations are well
explainable such that the representations can be also used for other tasks. To
further induce the neural network to produce deep features that are appropriate
for the specific clustering model, the relaxed k-means and GAE are learned
simultaneously. Therefore, the relaxed k-means can be equivalently regarded as
a decoder that attempts to learn representations that can be linearly
constructed by some centroid vectors. Accordingly, EGAE consists of one encoder
and dual decoders. Extensive experiments are conducted to prove the superiority
of EGAE and the corresponding theoretical analyses.
