RWR-GAE: Random Walk Regularization for Graph Auto Encoders

2019·Arxiv

Abstract

Abstract

Node embeddings have become an ubiquitous technique for representing graph data in a low dimensional space. Graph autoencoders, as one of the widely adapted deep models, have been proposed to learn graph embeddings in an unsupervised way by minimizing the reconstruction error for the graph data. However, its reconstruction loss ignores the distribution of the latent representation, and thus leading to inferior embeddings. To mitigate this problem, we propose a random walk based method to regularize the representations learnt by the encoder. We show that the proposed novel enhancement beats the existing state-of-the-art models by a large margin (upto 7.5%) for node clustering task, and achieves state-of-the-art accuracy on the link prediction task for three standard datasets, cora, citeseer and pubmed. Code available at https:// github.com/MysteryVaibhav/DW-GAE.

1 Introduction

Analysis of graph data plays an important role in various data mining tasks including node classification [Kipf and Welling, 2016a], link prediction [Wang et al., 2017b], and node clustering [Wang et al., 2017a]. These tasks are useful for various kinds of graph data including protein-protein interaction networks, social media, and citation networks. However, it is known that working with graph data is a challenging task because of its high computational cost and low parallelizability. Further, the inapplicability of machine learning methods [Cui et al., 2018] to such data aggravates the problem.

Recent developments in graph embeddings have emerged as a boon for dealing with complex graph data. The general idea behind learning a graph embedding is to learn a latent, low-dimensional representation of network vertices, while preserving network topology structure, vertex content, and other information. [Perozzi et al., 2014] proposed a DeepWalk model to learn node embeddings by reducing the problem to a skipgram formulation [Mikolov et al., 2013b] used to learn word embeddings. Recent works [Kipf and

Figure 1: Node embeddings learned by two different architectures. Left: Generated by an autoencoder model Right: Generated by the proposed model. We see that the embeddings on the left have dense representations for nodes belonging to the same cluster whereas the embeddings on the right have an even intra-cluster spread which reduces the potential loss in clustering accuracy across boundaries. See 8.1 for a detailed discussion.

Welling, 2016b] show that graph autoencoder in conjunction with Graph Convolutional networks [Kipf and Welling, 2016a] are even more effective in learning low dimensional representations of the nodes. However, there are a few shortcomings in using autoencoders for learning graph embeddings. First, there is no restriction on the distribution of the latent representation learnt by the encoder which might result in inefficient embeddings [Pan et al., 2018]. Second, the reconstruction loss might not be a strong signal to capture the local graph topology [Goyal et al., 2018]. Figure 1 shows the effect of these problems on Cora.

[Pan et al., 2018] tried to address the first shortcoming by applying a Gaussian prior on the distribution of node representations. We argue that enforcing Gaussian prior on the latent code of node embeddings might not be the best option and propose a random walk based regularization technique which tries to enforce a restriction on the representation such that the embeddings learn to predict their context nodes. This is achieved by adding an additional training objective. This serves two purpose at once, first, instead of adding a prior on the latent representation of the nodes, we provide additional supervision for improving the quality of each node embedding. Second, the node embeddings are forced to capture the local network topology since the added objective is maximized when the node embeddings correctly predict their context embeddings. The proposed model allows for a natural graph regularization on the embeddings, whilst providing additional training signals to improve individual embeddings.

Through our experiments, we show that the proposed random walk regularization is superior to all other methods at

unsupervised clustering task. The contributions of this paper are two fold, • We propose a novel technique of using random walks for regularizing the node representations learned by a Graph autoencoder. • We show that the proposed regularization technique is effective at unsupervised clustering and outperforms all the other methods. Further, we show that the resulting embeddings are general in nature and achieve state of the art accuracy on the link prediction task as well.

2 Related Work

Learning node embeddings for networks has been a long standing problem. Conventionally, learning node embeddings was seen as either a feature engineering task or a dimentionality reduction task. [Tang and Liu, 2011] and [Henderson et al., 2011] proposed to use hand-crafted features based on the network properties. On the other hand, [Belkin and Niyogi, 2002] and [Roweis and Saul, 2000] used linear algebra tools to reduce the adjaceny matrix of a graph to a lower dimension.

The advancement of feature learning in other domains, particularly the SkipGram model [Mikolov et al., 2013b], proposed to learn word embeddings opened ways to learn node features as well. [Perozzi et al., 2014] proposed a DeepWalk model which used random walk [Pan et al., 2004] for learning graph embeddings. Their proposed objective was similar to the SkipGram [Mikolov et al., 2013b] model. They used nodes obtained from a random walk as the context nodes and tried to predict the context nodes using the node on which the walk was performed. This work exploited the graph structure to learn the embeddings. [Yang et al., 2015] proposed an extension to the DeepWalk model which enhanced the node representations by additionally incorporating the node features available from other sources, like the text features for each node. Since then, a number of probabilistic models have been proposed including [Grover and Leskovec, 2016] and [Tang et al., 2015], which try to map the nodes to a low-dimensional space of features that maximizes the likelihood of preserving network neighborhoods of nodes.

In the current research where deep learning is taking control over everything, Graph autoencoders have emerged as the go-to method for embedding graphs, mostly because of its good performance, efficiency and ease of use. The idea of integrating graph with neural models was first introduced by [Kipf and Welling, 2016a], who proposed Graph Convolution Networks (GCN) which could effectively encode graphs. GCNs can naturally incorporate node features, which significantly improves predictive performance on various tasks. Inspired by the autoencoder frameworks [Kingma and Welling, 2013], Kipf et al. proposed Graph autoencoder framework [Kipf and Welling, 2016b] which used GCNs as encoder and simple inner product as decoder. [Pan et al., 2018] identified that the graph autoencoders don’t put any restriction on the distribution of latent representation which could possibly lead to inferior embeddings. To address this problem, they proposed an adversarially regularized graph auto encoder which puts a Gaussian prior on the latent distribution. Our work is motivated from this work, and we argue that Gaussian prior might not be the most natural distribution for a node’s latent representation. We instead propose a random walk based regularization method which doesn’t enforce any prior on the latent representation but regularizes the representations in such a way that they learn the network’s local topology.

3 Problem Deﬁnition

We consider a general problem of learning unsupervised graph embeddings for any graph G. A graph G = (V, E) can be represented in terms of its vertices and edges s.t an edge between the nodes and . To efficiently represent the graph topology for computational use, we represent the edges using an adjacency matrix , where if else . Depending on the nature of the graph, we might have an additional node feature matrix , where each row of the matrix represents a h-dimensional content vector for each node in the graph.

Given a graph G, we want to learn a d-dimension vector for each node such that d << n. Putting everything together, we want to learn a function F such that , where Z is an embedding matrix in . We want Z to capture the node content as well as the topological structure in a continuous low dimensional space.

4 Proposed Model

4.1 Graph Convolutional Networks

Here, , where I is the identity matrix, is the diagonal node degree matrix of and is the activation function.

4.2 Graph Autoencoder

Graph autoencoders are an extension to the autoencoder framework consisting of an encoder and a decoder network. We use a 2-layer GCN as the encoder and inner product as the decoder. The encoder output is given by

Figure 2: Random Walk Regularized Graph Autoencoder. Top half of the network corresponds to the Graph Auto-Encoder. Bottom half shows the proposed Random Walk Regularization network.

The obtained node embeddings are then used in the decoder to reconstruct the graph ( ),

Note that we can reconstruct both A and X. However for our method, we just reconstruct the adjacency matrix as it is more flexible for graphs which don’t have content information. The network is trained using a reconstruction loss ,

4.3 Variational Graph Autoencoder

Variational Graph autoencoders are defined by an inference model,

Here, is a matrix of mean vectors is the covariance matrix. The decoder model remains roughly the same and the adjacency matrix can be reconstructed using the mean vectors,

For training the variational graph autoencoder, we optimize the variational lower bound as follows,

Here, denotes the Kullback-Leibler divergance and denotes the Guassian prior for the latent data distribution. We perform the reparameterization trick [Kingma and Welling, 2013] to train the variational model.

4.4 Random Walk Regularization

The main contribution of our model is the proposed regular- ization technique which forces the latent representation of the nodes to inherently capture the information of their immediate context nodes. We argue that using a Graph autoencoder with reconstruction loss for learning the node embeddings doesn’t force the latent representations of the nodes to necessarily capture the local context information present at vari- ous locations in the network. Thus, we add an extra objective while training to enforce this restriction. Inspired from DeepWalk [Perozzi et al., 2014], we leverage local information obtained from truncated random walks to learn latent representations by treating walks as the equivalent of sentences. Figure 2 shows the overall architecture of our proposed network. The lower half of the figure represents the regularization network. There are two main components of the regularization network, (a) Random Walk with Restarts and (b) SkipGram model.

Random Walk with Restarts

We leverage the idea of Random Walk with Restarts (RWR) [Pan et al., 2004] to obtain context nodes from any given node. denotes a set of context nodes obtained using RWR from the start node . Algorithm 1 defines a procedure to obtain .

SkipGram Once we obtain a set of context nodes, we use a SkipGram [Mikolov et al., 2013a] type model which has two embedding layers corresponding to the nodes and context nodes. Originally, SkipGram was designed as a language model that maximizes the co-occurrence probability among the words that appear within a window in a sentence. For this graph setting, we borrow the idea from [Perozzi et al., 2014], and use the set of nodes obtained from the random walk as our sentence and maximize the co-occurrence probability of the nodes. The objective function used to train this model is given

by the equation below,

Here, and denotes the latent representation for the node generated by the encoder.

Our model Algorithm 2 is our overall proposed framework. We train the entire network in an end-to-end fashion. An important consideration while training the network was choosing the order of the back-propagated gradients. We experimented with all

Figure 3: Forward and backward propagation in order for training the model. Green arrow denotes the forward propagation and red denotes backward.

possibilities and picked the one which gave best performance as per Figure 3.

Based on the type of encoder-decoder framework used, we present two kinds of regularized network,

• Random Walk Regularized Graph Autoencoder (RWR-GAE), for this model we use Eq. 6 to update the decoder and encoder parameters.

• Random Walk Regularized Variational Graph Eutoencoder (RWR-VGAE), the encoder in this model is based on the variational inference model, and we use Eq. 10 to update the decoder and encoder weights.

For both the models, we additionally use Eq. 11 for updating the skipgram model and encoder parameters.

Algorithm 2 Regularization through Random Walk for Graph Autoencoders

Input: Graph G(V, X, A), window size w, walks per epoch , walk length t, restart probability

5 Baselines

A rich line of work has been done for learning graph embeddings in an unsupervised setting. We briefly summarize some of the recent approaches used as our baseline, • DeepWalk [Perozzi et al., 2014]: is a network representation approach which encodes social relations into a continuous vector space by learning structural regularities present within short random walks. • Spectral Clustering [Tang and Liu, 2011]: is an effective approach for learning social embedding. This method generates a representation in from the d-smallest eigenvectors of L, the normalized graph Laplacian of G. • GAE [Kipf and Welling, 2016b]: is the most recent autoencoder-based unsupervised framework for graph data, which naturally leverages both topological and content information. • VGAE [Kipf and Welling, 2016b]: is a variational graph autoencoder approach for graph embedding with both topological and content information. • ARGA [Pan et al., 2018]: is an adversarially regularized autoencoder algorithm which uses graph autoencoder. • ARVGA [Pan et al., 2018]: is also an adversarially regularized autoencoder, which uses a variational graph autoencoder.

Table 1: Statistics about different training datasets.

6 Experimental Details

6.1 Datasets

We report results on three benchmark graph datasets [Sen et al., 2008], Cora, Citeseer and pubMed. Each dataset is sep-

Table 2: Performance comparison of different models on the Link Prediction task across various datasets. We conduct each experiment 10 times and report the mean values with the standard deviation.

Table 3: Performance comparison of different models for the Clustering task on Cora.

Table 4: Performance comparison of different models for the Clustering task on Citeseer.

arated into a training, testing set and validation set. The validation set consists of 5% citation edges for hyper-parameter tuning, the test set contains 10% citation edges for reporting the final performance, and the rest are used for training. Table 1 contains the training data statistics for each of the datatset.

6.2 Tasks and Evaluation metric

We evaluate the quality of the learned embeddings by analyzing the performance on two downstream tasks, Node clustering and Link Prediction. • Node Clustering, unsupervised clustering based on the

Table 5: Performance comparison of different models for the Clustering task on PubMed.

node embeddings. After learning the embeddings, we do K-means clustering to get the final clusters. Following [Xia et al., 2014], we use five metrics to validate the clustering results: accuracy (Acc), normalized mutual information (NMI), precision, F-score (F1) and average rand index (ARI).

• Link Prediction, predict the edges and non-edges among the test set nodes. For doing such a prediction, we simply use Eq. 5 to get the reconstructed graph from the node embeddings. Following [Kipf and Welling, 2016b], we report the AUC score (the area under a receiver operating characteristic curve) and average precision (AP) score.

6.3 Hyper-parameters

We use the hyper-parameters provided by [Kipf and Welling, 2016b] for the autoencoder related hyper-parameters of our model. For the hyper-parameters related to the Random Walk Regularization network, we set the number of walks to 50, window size to {30, 20} and walk length to {30, 20}. In our experiments, we find that the best performing model uses 50 walks with a window size and walk length of either 30 or 20 depending on the dataset and the kind of autoencoder.

7 Results

We now present quantitative results of our model on the node clustering task. Tables 3, 4 and 5 contain the results for the datasets, cora, citeseer and pubmed respectively. We see that our proposed random walk regularization consistently outperforms all other baselines for all evaluation metrics. For

Figure 4: Visualization using node embeddings generated by different hyperparameters using RWR-GAE on Cora. Left-to-right: number of walks = walk length = window size = {5, 20, 30}, and accuracy = {0.34, 0.56, 0.64}

the Cora dataset, we find that RWR-based methods improve the accuracy by 41.5% when compared to DeepWalk and by 12.4% when compared to Variational Graph Autoencoder. On the Citeseer dataset, we find that RWR-GAE beats the adversarially regularized autoencoder method by 7.5% on accuracy and by 7.1% on F1 score. For the PubMed dataset which has the largest number of nodes but the smallest number of clusters, we find that our method improves upon the GAE by 18.3% on ARI and by 7.5% on NMI.

Result for the link prediction task can be found in Table 2. We find that our proposed method performs at par with the existing baselines. It is interesting to note that the random walk regularized autoencoder convincingly outperforms the DeepWalk method, indicating that the random walk is very well complemented by the autoencoder methods.

8 Analysis

8.1 Graph Visualization

Figure 1 shows the quality of the embeddings using 2-d tsne [Van Der Maaten, 2014] plots. The left plot is obtained by using the node embeddings learned by GAE and the right plot shows the graph embeddings learned by our RWR-GAE model. We observe that both the methods do a good job of identifying clusters based on the node embeddings. However, if we look closely at the embeddings generated by the GAE model, we find that the representation of the intra-cluster nodes are quite similar in nature but are not equally distant from the cluster centroid. Where as the embeddings generated by our RWR-GAE model have a more even spread within the cluster i.e the embeddings within a cluster are similar to each other. To measure this property, we define intra-cluster distance as the sum of euclidean distance of each node in the cluster to its centroid, averaged across all the clusters. We find that the embeddings generated by our model have less intra-cluster distance (0.64) compared to embeddings generated by GAE (0.99). We argue that this property is induced by the random walk regularization as the individual node embeddings need to predict the context nodes within a neighborhood, thus during training phase, the node embedding will prefer to converge to a representation such that it’s informative of its context nodes. This results in improved embeddings for the clustering task, as a slight overlap among nodes of different clusters will now have relatively less impact on the clustering accuracy compared to the case when the intra-cluster embeddings are too close to each other and not evenly spread.

8.2 Study using different hyper-parameters

In this study, we try to understand how random walk helps in regularizing the embeddings. The left most embeddings in Figure 4 are generated by our model with window size, number of walks and walk length set to 5. We observe that for this case, some of the clusters are subsumed into other clusters and thus achieve a very low clustering accuracy. We believe that this happens because of the extremely low values of walk length and window size. An intuitive explanation for this is that a low window size limits a nodes capability to look at enough nodes to decide its cluster candidacy. As we increase the window size, we observe that the clusters start to get more distinct from each other.

8.3 Side-effects of random walk regularization

We list down two critical observations about our model. First, from Table 2, we observe that our proposed model has a considerably higher variance in scores. We attribute this behaviour to the introduced randomness while selecting nodes for random walk during the training phase. Second, from Algorithm 2, we see that the number of updates made to the encoder weights are considerably higher than the GAE model, as a result our proposed model converges to the best accuracy in fewer pass over the entire data. We consistently see the best results at around 100 epochs as opposed to 200 epochs for GAE.

9 Conclusion

We began by inspecting the graph embeddings learnt by an autoencoder model. We identified that this model doesn’t enforce any restriction on the latent distribution and just uses a reconstruction loss for training which might result in suboptimal embeddings. Further, we observed how this translated in terms of intra-cluster distances. We proposed a random walk based regularization technique for graph autoencoders which addressed both the shortcomings by adding a skipgram objective, which enforces the latent representations to capture network’s local topology as well as provide additional training signal. We validated the effectiveness of our method by evaluating the performance of the learned embeddings on two different tasks, node clustering and link prediction for three standard datasets, cora, citeseer and pubmed.

References

[Belkin and Niyogi, 2002] Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. In Advances in neural information processing systems, pages 585–591, 2002.

[Cui et al., 2018] Peng Cui, Xiao Wang, Jian Pei, and Wenwu Zhu. A survey on network embedding. IEEE Transactions on Knowledge and Data Engineering, 2018.

[Goyal et al., 2018] Palash Goyal, Homa Hosseinmardi, Emilio Ferrara, and Aram Galstyan. Capturing edge attributes via network embedding. arXiv preprint arXiv:1805.03280, 2018.

[Grover and Leskovec, 2016] Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 855–864. ACM, 2016.

[Henderson et al., 2011] Keith Henderson, Brian Gallagher, Lei Li, Leman Akoglu, Tina Eliassi-Rad, Hanghang Tong, and Christos Faloutsos. It’s who you know: graph mining using recursive structural features. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 663–671. ACM, 2011.

[Kingma and Welling, 2013] Diederik P Kingma and Max Welling. Auto-encoding variational bayes. arXiv preprint arXiv:1312.6114, 2013.

[Kipf and Welling, 2016a] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907, 2016.

[Kipf and Welling, 2016b] Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint arXiv:1611.07308, 2016.

[Mikolov et al., 2013a] Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient estimation of word representations in vector space. arXiv preprint arXiv:1301.3781, 2013.

[Mikolov et al., 2013b] Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed representations of words and phrases and their compositionality. In Advances in neural information processing systems, pages 3111–3119, 2013.

[Pan et al., 2004] Jia-Yu Pan, Hyung-Jeong Yang, Christos Faloutsos, and Pinar Duygulu. Automatic multimedia cross-modal correlation discovery. In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 653–658. ACM, 2004.

[Pan et al., 2018] Shirui Pan, Ruiqi Hu, Guodong Long, Jing Jiang, Lina Yao, and Chengqi Zhang. Adversarially regularized graph autoencoder. arXiv preprint arXiv:1802.04407, 2018.

[Perozzi et al., 2014] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 701–710. ACM, 2014.

[Roweis and Saul, 2000] Sam T Roweis and Lawrence K Saul. Nonlinear dimensionality reduction by locally linear embedding. science, 290(5500):2323–2326, 2000.

[Sen et al., 2008] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. AI magazine, 29(3):93, 2008.

[Tang and Liu, 2011] Lei Tang and Huan Liu. Leveraging social media networks for classification. Data Mining and Knowledge Discovery, 23(3):447–478, 2011.

[Tang et al., 2015] Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Largescale information network embedding. In Proceedings of the 24th international conference on world wide web, pages 1067–1077. International World Wide Web Conferences Steering Committee, 2015.

[Van Der Maaten, 2014] Laurens Van Der Maaten. Acceler- ating t-sne using tree-based algorithms. The Journal of Machine Learning Research, 15(1):3221–3245, 2014.

[Wang et al., 2017a] Chun Wang, Shirui Pan, Guodong Long, Xingquan Zhu, and Jing Jiang. Mgae: Marginalized graph autoencoder for graph clustering. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, pages 889–898. ACM, 2017.

[Wang et al., 2017b] Zhitao Wang, Chengyao Chen, and Wenjie Li. Predictive network representation learning for link prediction. In Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 969–972. ACM, 2017.

[Xia et al., 2014] Rongkai Xia, Yan Pan, Lei Du, and Jian Yin. Robust multi-view spectral clustering via low-rank and sparse decomposition. In AAAI, pages 2149–2155, 2014.

[Yang et al., 2015] Cheng Yang, Zhiyuan Liu, Deli Zhao, Maosong Sun, and Edward Chang. Network representation learning with rich text information. In Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015.

designed for accessibility and to further open science