Symmetric Graph Convolutional Autoencoder for Unsupervised Graph Representation Learning

Introduction

A graph, which consists of a set of nodes and edges, is a powerful tool to seek the geometric structure of data. There are various applications using graphs in the machine learning and data mining fields such as node clustering , dimensionality reduction , social network analysis , chemical property prediction of a molecular graph , and image segmentation . However, conventional methods for analyzing a graph have several problems such as low computational efficiency due to eigendecomposition or singular value decomposition, or only showing a shallow relationship between nodes.

In recent years, an emerging field called geometric deep learning , generalizes deep neural network models to non-Euclidean domains such as meshes, manifolds, and graphs . Among them, finding deep latent representations of geometrical structures of graphs using an autoencoder framework is getting growing attention. The first attempt is VGAE which consists of a Graph Convolutional Network (GCN) encoder and a matrix outer-product decoder as shown in Figure 1 (a). As a variant of VGAE, ARVGA has been proposed by incorporating an adversarial approach to VGAE. However, VGAE and ARVGA were designed to reconstruct the affinity matrix $A$ instead of node feature matrix $X$. Hence, the decoder part cannot be learnable, therefore, the graphical feature cannot be used at all in the decoder part. These facts can degrade the capability of graph learning. Following that, MGAE has been proposed, which uses stacked single layer graph autoencoder with linear activation function and marginalization process as shown in Figure 1 (b). However, since the MGAE reconstructs the feature matrix of nodes without hidden layers, it cannot manipulate the dimension of the latent representation and performs a linear mapping. This is a distinct limitation in finding a latent representation that clearly reveals the structure of the graph.

To overcome the limitation of the existing graph convolutional autoencoders, in this paper, we propose a novel graph convolutional autoencoder framework which has symmetric autoencoder architecture and uses both graph and node attributes in both the encoding and decoding processes as illustrated in Figure 1 (c). Our design of the decoder part is motivated from the analysis in a recent paper , that the encoder of VGAE can be interpreted as a special form of Laplacian smoothing that computes the new representation of each node as a weighted local average of neighbors and itself. This interpretation has inspired us to design a decoder to perform Laplacian sharpening, which is a counterpart of Laplacian smoothing. To realize a decoder to do Laplacian sharpening, we express Laplacian sharpening in the form of Chebyshev polynomial and newly reformulate it in a numerically stable form by utilizing a signed graph .

In computer vision fields, there is a popular assumption that, even though image datasets are high-dimensional in their ambient spaces, they usually reside in multiple low-dimensional subspaces . Thus, especially for image clustering tasks, we apply the concept of subspace clustering, which has such an assumption about the input data in its own definition, to our graph convolutional autoencoder framework. Specifically, to find a latent representation and a latent affinity matrix simultaneously, we merge a subspace clustering cost function into the reconstruction cost of the autoencoder. Contrary to the conventional subspace clustering cost function , we could derive a computationally efficient cost function.

The main contributions of this paper are summarized as follows:

We propose the first completely symmetric graph convolutional autoencoder which utilizes both the structure of the graph and node attributes through the whole encoding-decoding process.

We derive a new numerically stable form of decoder preventing the numerical instability of the neural network.

We design a computationally efficient subspace clustering cost to find both latent representation and a latent affinity matrix simultaneously for image clustering tasks.

In experiments, the validity of the proposed components is shown by doing ablation experiments on our architecture and cost function. Also, the superior performance of the proposed method is validated by comparing it with the state-of-the-art methods and visualizing the graph clustered by our framework.

Preliminaries

A graph is represented as $\mathcal{G}=(\mathcal{V},\mathcal{E},A)$, where $\mathcal{V}$ denotes the node set with $v_{i}\in\mathcal{V}$ and $|\mathcal{V}|=n$, $\mathcal{E}$ denotes the edge set with $(v_{i},v_{j})\in\mathcal{E}$, and $A\in{\rm I\!R}^{n\times n}$ denotes an affinity matrix which encodes pairwise affinities between nodes. $D\in{\rm I\!R}^{n\times n}$ denotes a degree matrix which is a diagonal matrix with $D_{ii}=\sum_{j}A_{ij}$. Unnormalized graph Laplacian $\Delta$ is defined by $\Delta=D-A$ . Symmetric graph Laplacian $L$ and random walk graph Laplacian $L_{rw}$ are defined by $L=I_{n}-D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$ and $L_{rw}=I_{n}-D^{-1}A$ respectively, where $I_{n}\in{\rm I\!R}^{n\times n}$ denotes an identity matrix. Note that the $\Delta$, $L$ and $L_{rw}$ are positive semidefinite matrices.

2 Spectral convolution on graphs

A spectral convolution on a graph is the multiplication of an input signal $x\in{\rm I\!R}^{n}$ with a spectral filter $g_{\theta}=diag(\theta)$ parameterized by the vector of Fourier coefficients $\theta\in{\rm I\!R}^{n}$ as follows:

where $U$ is the matrix of eigenvectors of the symmetric graph Laplacian $L=U\Lambda U^{T}$. $U^{T}x$ is the graph Fourier transform of the input $x$, and $g_{\theta}$ is a function of the eigenvalues of $L$, i.e., $g_{\theta}(\Lambda)$, where $\Lambda$ is the diagonal matrix of eigenvalues of $L$. However, this operation is inappropriate for large-scale graphs since it requires an eigendecomposition to obtain the eigenvalues and eigenvectors of $L$. To avoid computationally expensive operations, the spectral filter $g_{\theta}(\Lambda)$ was approximated by $K^{th}$ order Chebyshev polynomials in previous works . By doing so, the spectral convolution on the graph can be approximated as

In the GCN , the Chebyshev approximation model was simplified by setting $K=1$, $\lambda_{max}\approx 2$ and $\theta=\theta_{0}^{\prime}=-\theta_{1}^{\prime}$. This makes the spectral convolution simplified as follows:

However, repeated application of $I_{n}+D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$ can cause numerical instabilities in neural networks since the spectral radius of $I_{n}+D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$ is $2$, and the Chebyshev polynomials form an orthonormal basis when its spectral radius is $1$. To circumvent this issue, the GCN uses renormalization trick:

Finally, the forward-path of the GCN can be expressed by

3 Laplacian smoothing

where $x_{i}^{(m+1)}$ is the new representation of $x_{i}^{(m)}$, and $\gamma$ $(0<\gamma\leq 1)$ is a regularization parameter which controls the importance between itself and its neighbors. We can rewrite the above equation in a matrix form as follows:

The proposed method

In this section, we propose a novel graph convolutional autoencoder framework, named as GALA (Graph convolutional Autoencoder using LAplacian smoothing and sharpening). In GALA, there are $M$ layers in total, from the first to $\tfrac{M}{2}$th layers for the encoder and from the $\left(\tfrac{M}{2}+1\right)$th to $M$th layers for the decoder where $M$ is an even number. The encoder part of GALA is designed to perform the computationally efficient spectral convolution on the graph with a numerically stable form of Laplacian smoothing in the Eq. (7) . Along with this, its decoder part is designed to be a special form of Laplacian sharpening , unlike the existing VGAE-related algorithms. By this decoder part, GALA reconstructs the feature matrix of nodes directly, instead of yielding an affinity matrix as in the existing VGAE-related algorithms whose decoder parts are incomplete. Furthermore, to enhance the performance of image clustering, we devise a computationally efficient subspace clustering cost term which is added to the reconstruction cost of GALA.

Because the encoder performs Laplacian smoothing that makes the latent representation of each node similar to those of its neighboring nodes, we design the decoder part to perform Laplacian sharpening as the counterpart of Laplacian smoothing. Laplacian sharpening is a process that makes the reconstructed feature of each node farther away from the centroid of its neighbors, which accelerates the reconstruction along with the reconstruction cost and is governed by

where $x_{i}^{(m+1)}$ is the new representation of $x_{i}^{(m)}$, and $\gamma$ is the regularization parameter which controls the importance between itself and its neighbors. The matrix form of Eq. (10) is given by

Analogous to the encoder, we set $\gamma=1$ and replace $L_{rw}$ with $L$. Similar to Eq. (3), we can express Laplacian sharpening in the form of Chebyshev polynomial and simplify it with $K=1$, $\lambda_{max}\approx 2$, and $\theta=\frac{1}{2}\theta_{0}^{\prime}=\theta_{1}^{\prime}$. Then, a decoder layer can be expressed by

where $H^{(m)}$ is the matrix of the activation in the $m^{th}$ layer, $2I_{n}-D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$ is a special form of Laplacian sharpening, $\xi(\cdot)$ is the nonlinear activation function like ReLU($\cdot$) = $\max(0,\cdot)$, and $\Theta^{(m)}$ is a trainable weight matrix. However, since the spectral radius of $2I_{n}-D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$ is $3$, repeated application of this operator can be numerically instable. Hence, as GCN finds a numerically stable form of Chebyshev polynomials, we have to find a numerically stable form of Laplacian sharpening while maintaining its meaning.

2 Numerically stable Laplacian sharpening

To find a new representation of Laplacian sharpening whose spectral radius is 1, we use a signed graph . A signed graph is denoted by $\Gamma=(\mathcal{V},\mathcal{E},\hat{A})$ which is induced from the unsigned graph $\mathcal{G}=(\mathcal{V},\mathcal{E},A)$, where each element in $\hat{A}$ has the same absolute value with $A$, but its sign is changed into minus or keeps plus. The degree matrix of the signed graph $\Gamma$ is denoted by $\hat{D}$ which is obtained from $\hat{A}$. In the signed graph, a problem occurs when calculating the degree matrix $\hat{D}$ by the conventional way that may cancel the mixed signed weights in summation and so fails to yield the degree value representing the connectivity of a node to its neighbors. Thus, by following the practice for signed graphs, we calculate the degree of each node by $\hat{D}_{ii}=\sum_{j}|\hat{A}_{ij}|$ that has the same value (degree of connectivity) as in the unsigned graph. By using $\hat{A}$ and $\hat{D}$, we can construct an unnormalized graph Laplacian $\hat{\Delta}=\hat{D}-\hat{A}$ and symmetric graph Laplacian $\hat{L}=I_{n}-\hat{D}^{-\frac{1}{2}}\hat{A}\hat{D}^{-\frac{1}{2}}$ of the signed graph. From Theorem 1 of , the range of the eigenvalue of $\hat{L}$ is $$, thus the spectral radius of$\hat{D}^{-\frac{1}{2}}\hat{A}\hat{D}^{-\frac{1}{2}}$is 1 for any choice of$\hat{A}$. Using this result, instead of Eq. (12), we use a numerically stable form of Laplacian sharpening with spectral radius of 1, given by

The remaining issue is to choose $\hat{A}$ induced from $A$ so that $\hat{D}^{-\frac{1}{2}}\hat{A}\hat{D}^{-\frac{1}{2}}$ maintains the meaning of each element of $2I_{n}-D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$ in Eq. (12). To achieve this, we map all weights of the unsigned $A$ to negative weights and adding a self-loop with a weight value $2$ to each node, that is, $\hat{A}=2I_{n}-A$ and $\hat{D}=2I_{n}+D$. Then, each element of $\hat{D}^{-\frac{1}{2}}\hat{A}\hat{D}^{-\frac{1}{2}}$ is obtained by

which has the same meaning with the original one given by

From Eqs. (13), (14) and (15), the numerically stable decoder layer of GALA is given as

where $\hat{A}=2I_{n}-A$ and $\hat{D}=2I_{n}+D$. The encoder part of GALA is constructed by using Eq. (7) as in GCN as

Since the complexity is linear in the number of edges in the graph, the proposed algorithm is computationally efficient (given the assumption that $A$ is sparse). Also, from Eq. (17), since GALA decodes the latent representation using both the graph structure and node features, the enhanced decoder of GALA can help to find more distinct latent representation.

In Table 1, we show the reason why the Laplacian smoothing is not appropriate to the decoder and the necessity of numerically stable Laplacian sharpening by node clustering experiments (the higher values imply the more correct results). Laplacian smoothing decoder (Eq. 7) shows the lowest performances, since Laplacian smoothing which makes the representation of each node similar to those of its neighboring nodes conflicts with the purpose of reconstruction cost. A numerically instable form of Laplacian sharpening decoder (Eq. 12) shows higher performance compared to smoothing decoder because the role of Laplacian sharpening coincide with reconstructing the node feature. The performance of proposed numerically stable Laplacian sharpening decoder (Eq. 16) significantly higher than others, since it solves instability issue of neural network while maintaining the meaning of original Laplacian sharpening.

The basic cost function of GALA is given by

where $\bar{X}$ is the reconstructed feature matrix of nodes, the column of $\bar{X}$ corresponds to the output of the decoder for an input feature of a node, and ${\|\cdot\|}_{F}$ denotes the Frobenius norm.

3 Subspace clustering cost for image clustering

It is a well-known assumption that image datasets are often drawn from multiple low-dimensional subspaces, although their data dimensions are high. Accordingly, subspace clustering, which has such an assumption about the input data in its own definition, has shown prominent clustering performance on various image datasets. Hence, we add an element of subspace clustering to the proposed method in the case of image clustering tasks. Among the various subspace clustering models, we add Least Squares Regression (LSR) model for computational efficiency. Then the cost function for training of GALA becomes

where $H\in{\rm I\!R}^{k\times n}$ denotes the latent representations (i.e., the output of the encoder), $A_{H}\in{\rm I\!R}^{n\times n}$ denotes the affinity matrix which is a new latent variable for subspace clustering, and $\lambda,\mu$ are the regularization parameters. The second term of Eq. (19) aims at the self-expressive model of subspace clustering and the third term of Eq. (19) is for regularizing $A_{H}$. If we only consider minimizing $A_{H}$, the problem becomes:

We can easily obtain the analytic solution $A_{H}^{*}=(H^{T}H+\frac{\mu}{\lambda}I_{n})^{-1}H^{T}H$ by the fact that LSR model is quadratic on the variable $A_{H}$. By using this analytic solution and singular value decomposition, we derive a computationally efficient subspace clustering cost function as follows (The details are reported in the supplementary material):

where $tr(\cdot)$ denotes the trace of the matrix. The above problem can be solved by $k\times k$ matrix inversion instead of $n\times n$ matrix inversion. Since the dimension of latent representation ($k$) is much smaller than the number of nodes ($n$), this simplification can reduce the computational burden significantly from $\mathcal{O}(n^{3})$ to $\mathcal{O}(k^{3})$.

4 Training

We train GALA to minimize Eq. (18) by using the ADAM algorithm . We train GALA deterministically by using the full batch in each training epoch and stop when the cost is converged, so the number of epochs of each dataset varies. Note here that using the full batch during training is a common approach in neural networks based on spectral convolution on graph. Specifically, we set the learning rate to $1.0\times 10^{-4}$ for training and train GALA in an unsupervised way without any cluster labels. When the subspace clustering cost is added to reconstruction cost for image clustering tasks, we use pre-training and fine-tuning strategies similar to the ones in to train GALA. First, in the pre-training stage, the training method is the same as that of minimizing Eq. (18). After pre-training, we fine-tune GALA to minimize Eq. (21) using ADAM. As in the pre-training, we train GALA deterministically by using full batch in each training epoch, and we set the number of epochs of the fine-tuning stage as 50 for all dataset. We set the learning rate to $1.0\times 10^{-6}$ for fine-tuning.

After the training process are over, we construct $k$-nearest neighborhood graph using attained latent representations $H^{*}$. Then we perform spectral clustering and get the clustering performance. In the case of image clustering, after all training processes are over, we construct the optimal affinity matrix $A_{H}^{*}$ noted in the previous subsection by using the attained latent representation matrix $H^{*}$ from GALA. Then we perform spectral clustering on the affinity matrix and get the optimal clustering with respect to our cost function.

Experiments

We use four network datasets (Cora, Citeseer, Wiki, and Pubmed) and three image datasets (COIL20, YALE, and MNIST) for node clustering and link prediction tasks. Every network dataset has the feature matrix $X$ and the affinity matrix $A$ and every image dataset has the feature matrix $X$ only. The summary of each dataset are presented in Table 3 and details are reported in the supplementary material. Also, the sample images of each image dataset are described in Figure 2.

2 Experimental settings

To measure the performance of node clustering task, we use three metrics: accuracy (ACC), normalized mutual information (NMI), and adjusted rand index (ARI) as in . We report the mean values of the three metrics for each algorithm after executing 50 times, and the higher values imply the more correct results. For link prediction task, we partitioned the dataset following the work of GAE , and reported mean scores and standard errors of Area Under Curve (AUC) and Average Precision (AP) with 10 random initializations. The implementation details such as hyperparameters are reported in the supplementary material.

3 Comparing methods

We compare the performance of 15 algorithms. Compared algorithms can be categorized into four groups as described below:

i) Using features only. ‘Kmeans’ is the K-means clustering based on only the features of the data, which is the baseline clustering algorithm in our experiment.

ii) Using network structures only. ‘Spectral’ is a spectral clustering algorithm using eigendecomposition on graph Laplacian. ‘Big-Clam’ is a large-scale community detection algorithm utilizing a variant of nonnegative matrix factorization. ‘DeepWalk’ learns the latent social representation of nodes using local information through a neural network. ‘GraEnc’ is a graph-encoding neural network derived from the relation between autoencoder and spectral clustering. ‘DNGR’ generates a low-dimensional representation of each node by using a graph structure and a stacked denoised autoencoder.

iii) Using both. ‘Circles’ is an algorithm which discovers social circles through a node clustering algorithm. ‘RTM’ presents a relational topic model of documents and links between the documents. ‘RMSC’ is a robust multi-view spectral clustering algorithm which can handle noises in the data and recover transition matrix through low-rank and sparse decomposition. ‘TADW’ interprets DeepWalk from the view of matrix factorization and incorporates text features of nodes.

iv) Using both with spectral convolution on graphs. ‘GAE’ is the first attempt to graft the spectral convolution on graphs onto autoencoder framework. ‘VGAE’ is the variational variant of GAE. ‘MGAE’ is an autoencoder which combines the marginalization process with spectral convolution on graphs. ‘ARGA’ learns the latent representation by adding an adversarial model to a non-probabilistic variant of VGAE. ‘ARVGA’ is an algorithm which adds an adversarial model to VGAE.

4 Node clustering results

The experimental results of node clustering are presented in Table 2. It can be observed that for every dataset, the methods which use features and network structures simultaneously show better performance than the methods which use only one of them. Furthermore, among the methods which use both features and network structures, algorithms with neural network models which exploit spectral convolution on graphs present outstanding performance since they can learn deeper relationships between nodes than the methods which do not use spectral convolution on graphs. In every experiments, GALA shows superior performance to other methods. Especially, for the Cora dataset, GALA outperforms VGAE, which is the first graph convolution autoencoder framework, by about 24.39$\%$, 24.75$\%$ and 27.68$\%$, and MGAE, which is the state-of-the-art graph convolutional autoencoder algorithm, by about 6.15$\%$, 6.56$\%$ and 8.68$\%$ on ACC, NMI and ARI, respectively. The better performance of GALA comes from the better decoder design based on the numerically stable form of Laplacian sharpening both and full utilizing of graph structure and node attributes in the whole autoencoder framework.

Furthermore, we conduct another node clustering experiment on a large network dataset (Pubmed), and the results are reported in Table 5. We can observe that GALA outperforms every baselines and state-of-the-art graph convolution algorithms. Although Kmeans clustering, a baseline algorithm, shows higher performance over several graph convolution algorithms on NMI and ARI, the proposed method presents better performances.

5 Image clustering results

The experimental results of image clustering are presented in Table 4. We report both GALA’s performance of reconstruction cost only case and the subspace clustering cost added case (GALA+SCC). It can be seen that GALA outperforms several baselines and the state-of-the-art graph convolution algorithms for most of the cases. Also, for every case, the proposed subspace clustering cost term contributes to improve the performance of the image clustering. On the YALE dataset, notably, we can observe that the proposed subspace clustering cost term significantly enhances the image clustering performance and achieves nearly perfect accuracy.

6 Ablation studies

We validate the effectiveness of the proposed stable decoder and the subspace clustering cost by image clustering experiments on the three image datasets (COIL20, YALE and MNIST). There are four configurations as shown in Table 6. We would like to note that the reconstruction cost only (Eq. 18) is a subset of subspace clustering cost (Eq. 21), thus the last configuration is the full proposed method. Reported numbers are mean values after executing 50 times. It can be clearly noticed that the numerically stable form of Laplacian sharpening and subspace clustering cost are helpful to find the latent representations which reflect the graph structures certainly and using both components can boost the performance of clustering. In addition, it can be seen that the stable decoder with the reconstruction cost only outperforms the state-of-the-art algorithms in most cases because GALA can utilize the graph structure in the whole processes of the autoencoder architecture.

7 Link prediction results

We provide some results on link prediction task on Citeseer dataset. For link prediction task, we minimized the below cost function that added link prediction cost of GAE to the reconstruction cost, where $H$ is the latent representation, $\hat{A}=$ sigmoid$(HH^{T})$ is the reconstructed affinity matrix and $\gamma$ is the regularization parameter.

The results are shown in Table 7, and our model outperforms the compared methods in terms of the link prediction task as well as the node clustering task.

8 Visualization

One of the key ideas of the proposed autoencoder is that the encoder makes the feature of each node becomes similar with its neighbors, and the decoder makes the features of each node distinguishable with its neighbors using the geometrical structure of the graphs. To validate the proposed model, we visualize the distribution of learned latent representations and the input features of each node in two-dimensional space using t-SNE as shown in Figure 3. From the visualization, we can see that GALA is well-clustering the data according to their corresponding labels even though GALA performs in an unsupervised manner. Also, we can see through the red dotted line in embedding results of the latent representation on YALE that GALA embeds the representation of nodes better than the compared methods by minimizing inter-cluster affinity and maximizing intra-cluster affinity.

Conclusions

In this paper, we proposed a novel autoencoder framework which can extract low-dimensional latent representations from a graph in irregular domains. We designed a symmetric graph convolutional autoencoder architecture where the encoder performs Laplacian smoothing while the decoder performs Laplacian sharpening. Also, to prevent numerical instabilities, we designed a new representation of Laplacian sharpening with spectral radius one by incorporating the concept of the signed graph. To enhance the performance of image clustering tasks, we added a subspace clustering cost term to the reconstruction cost of the autoencoder. Experimental results on the network and image datasets demonstrated the validity of the proposed framework and had shown superior performance over various graph-based clustering algorithms.

Acknowledgement: This work was supported by Next Generation ICD Program through NRF funded by Ministry of S&ICT [2017M3C4A7077582], ICT R&D program of MSIP/IITP [No.B0101-15-0552, Predictive Visual Intelligence Technology], and the Basic Science Research Program through the National Research Foundation of Korea funded by the Ministry of Science and ICT under Grant NRF-2017R1C1B2012277.

References