Adaptive Graph Encoder for Attributed Graph Embedding
Ganqu Cui, Jie Zhou, Cheng Yang, Zhiyuan Liu
Introduction
Attributed graphs are graphs with node attributes/features and are widely applied to represent network-structured data in social networks (Hastings, 2006), citation networks (Kipf and Welling, 2017), recommendation systems (Ying et al., 2018), etc. For tasks analyzing attributed graphs, including node classification, link prediction and node clustering, plenty of machine learning techniques are developed. However, because of the complex high-dimensional non-Euclidean graph structure and various node features, this task imposes the challenge of jointly capturing structure and feature information on machine learning approaches.
Representation learning methods on graphs, also known as graph embedding methods, have emerged as general approaches in graph learning area. This kind of approaches aims to learn low-dimensional representations to encode graph structural information. Early graph embedding approaches are based on Laplacian eigenmaps (Newman, 2006), matrix factorization (Cao et al., 2015; Yang et al., 2015; Li et al., 2018b; Wang et al., 2016b), and random walks (Perozzi et al., 2014; Grover and Leskovec, 2016). However, these methods are also limited because of their shallow architecture.
More recently, there has been a surge of approaches that focus on deep learning on graphs. Specifically, approaches from the family of graph convolutional networks (GCNs) (Kipf and Welling, 2017) have made great progress in many graph learning tasks (Zhou et al., 2018) and strengthen the representation power of graph embedding algorithms. In this paper, we will study the attributed graph embedding problem, which is one of the most important problems in deep graph learning and GCN-based methods have also made great progress on it. Among these methods, most of them are based on graph autoencoder (GAE) and variational graph autoencoder (VGAE) (Kipf and Welling, 2016). As shown in Figure 1, they comprise a GCN encoder and a reconstruction decoder. Nevertheless, these GCN-based methods have three major drawbacks:
Firstly, a GCN encoder consists of multiple graph convolutional layers, and each layer contains a graph convolutional filter ( in Figure 1), a weight matrix ( in Figure 1) and an activation function. However, previous work (Wu et al., 2019) demonstrates that the entanglement of the filters and weight matrices provides no performance gain for semi-supervised graph representation learning, and even harms training efficiency since it deepens the paths of back-propagation. In this work, we further extend this conclusion to unsupervised scenarios by controlled experiments, showing that our disentangled architecture performs better and more robust than entangled models (Section 5.3).
Secondly, considering the graph convolutional filters, previous research (Li et al., 2018a) shows in theory that they are actually Laplacian smoothing filters (Taubin, 1995) applied on the feature matrix for low-pass denoising. But we show that existing graph convolutional filters are not optimal low-pass filters since they can not filter out noises in some high-frequency intervals. Thus, they can not reach the best smoothing effect (Section 3.3.3).
Thirdly, we also argue that training objectives of these algorithms (either reconstructing the adjacency matrix (Pan et al., 2018; Wang et al., 2019) or feature matrix (Wang et al., 2017; Park et al., 2019)) are not compatible with real-world applications. To be specific, reconstructing adjacency matrix literally sets the adjacency matrix as the ground truth pairwise similarity, while it is not proper for the lack of feature information. Recovering the feature matrix, however, will force the model to remember high-frequency noises in features, and thus be inappropriate as well.
Motivated by such observations, we propose Adaptive Graph Encoder (AGE), a unified framework for attributed graph embedding. To disentangle the filters and weight matrices, AGE consists of two modules: (1) A well-designed non-parametric Laplacian smoothing filter to perform low-pass filtering in order to get smoothed features. (2) An adaptive encoder to learn more representative node embeddings. To replace the reconstruction training objectives, we employ adaptive learning (Chang et al., 2017) in this step, which selects training samples from the pairwise similarity matrix and finetunes the embeddings iteratively. The code and data are available on https://github.com/thunlp/AGE.
Our contributions can be summarized as follows:
Analysis: We make a detailed analysis of the mechanism of graph convolutional filters from the perspective of signal smoothing on graphs and Laplacian smoothing. The analysis helps us design a proper Laplacian smoothing filter to better alleviate high-frequency noises.
Model: We propose AGE, a general model for attributed graph embedding. Our two-fold model disentangles the filters and weight matrices. The filters we adopt preserve the optimal low-pass properties. Furthermore, instead of the reconstruction loss, we apply a novel adaptive learning strategy to train node embeddings.
Experiment: We conduct extensive experiments on node clustering and link prediction tasks with real-world benchmark datasets. The results demonstrate that AGE outperforms state-of-the-art attributed graph embedding methods.
Related Work
Early researches on graph embedding merely focus on finding node similarity with graph structure. Methods based on dimension reduction aim to project the high-dimensional adjacency matrix to low-dimensional latent embedding space. Laplacian eigenmaps (Newman, 2006) and matrix factorization (Cao et al., 2015) are two widely used algorithms for these methods. Another line of researches manages to learn node embeddings with a particular objective function. (Perozzi et al., 2014; Grover and Leskovec, 2016) learn node embeddings by generating random walks and input the sequences into SkipGram model (Le and Mikolov, 2014), assuming that similar nodes tend to co-occur in same sequences. Other models (Cao et al., 2016; Wang et al., 2016a; Tang et al., 2015) can be concluded by an encoder-decoder framework (Hamilton et al., 2017), while they differ from model structure and training objectives.
Taking node features into account, there are several works make adjustments to encode structural and content information simultaneously. (Yang et al., 2015; Li et al., 2018b; Wang et al., 2016b) are matrix factorization extensions that add feature-related regularization terms. (Chang and Blei, 2009; Bojchevski and Günnemann, 2018) model features as latent variables in Bayesian networks.
2. GCN-based Graph Embedding
As mentioned in the introduction, due to the strong representation power of graph convolutional networks (GCNs) (Kipf and Welling, 2017), there are several GCN-based approaches for attributed graph embedding and they have achieved state-of-the-art. For unsupervised graph embedding that lacks label information, GCN-based methods can be categorized into two groups by their optimization objectives.
Reconstruct the adjacency matrix. This kind of approaches forces the learned embeddings to recover their localized neighborhood structure. Graph autoencoder (GAE) and variational graph autoencoder (VGAE) (Kipf and Welling, 2016) learn node embeddings by using GCN as the encoder, then decode by inner product with cross-entropy loss. As variants of GAE (VGAE), (Pan et al., 2018) exploits adversarially regularized method to learn more robust node embeddings. (Wang et al., 2019) further employs graph attention networks (Veličković et al., 2018) to differentiate the importance of the neighboring nodes to a target node.
Reconstruct the feature matrix. This kind of models is autoencoders for the node feature matrix while the adjacency matrix merely serves as a filter. (Wang et al., 2017) leverages marginalized denoising autoencoder to disturb the structure information. To build a symmetric graph autoencoder, (Park et al., 2019) proposes Laplacian sharpening as the counterpart of Laplacian smoothing in the encoder. The authors claim that Laplacian sharpening is a process that makes the reconstructed feature of each node away from the centroid of its neighbors to avoid over-smoothing. However, as we will show in the next section, there exists high-frequency noises in raw node features, which harm the quality of learned embeddings.
Proposed Method
In this section, we first formalize the embedding task on attributed graphs. Then we present our proposed Adaptive Graph Encoder (AGE) algorithm. Specifically, we first design an effective graph filter to perform Laplacian smoothing on node features. Given the smoothed node features, we further develop a simple node representation learning module based on adaptive learning (Chang et al., 2017). Finally, the learned node embeddings are used for downstream tasks such as node clustering and link prediction.
The purpose of attributed graph embedding is to map nodes to low-dimensional embeddings. We take as the embedding matrix and the embeddings should preserve both the topological structure and feature information of graph .
For downstream tasks, we consider node clustering and link prediction. The node clustering task aims to partition the nodes into disjoint groups , where similar nodes should be in the same group. The link prediction task requires the model to predict whether there is a potential edge existing between two given nodes.
2. Overall Framework
The framework of our model is shown in Figure 2. It consists of two parts: a Laplacian smoothing filter and an adaptive encoder.
Adaptive Encoder: To get more representative node embeddings, this module builds a training set by adaptively selecting node pairs which are highly similar or dissimilar. Then the encoder is trained in a supervised manner.
After the training process, the learned node embedding matrix is used for downstream tasks.
3. Laplacian Smoothing Filter
The basic assumption for graph learning is that nearby nodes on the graph should be similar, thus node features are supposed to be smooth on the graph manifold. In this section, we first explain what smooth means. Then we give the definition of the generalized Laplacian smoothing filter and show that it is a smoothing operator. Finally, we answer how to design an optimal Laplacian smoothing filter.
This quotient is actually the normalized variance score of . As stated above, smooth signals should assign similar values on neighboring nodes. Consequently, signals with lower Rayleigh quotient are assumed to be smoother.
Eq. (2) indicates that smoother eigenvectors are associated with smaller eigenvalues, which means lower frequencies. Thus we decompose signal on the basis of based on Eq. (1) and Eq. (2):
where is the coefficient of eigenvector . Then the smoothness of is actually
Therefore, to get smoother signals, the goal of our filter is filtering out high-frequency components while preserving low-frequency components. Because of its high computational efficiency and convincing performance, Laplacian smoothing filters (Taubin, 1995) are often utilized for this purpose.
3.2. Generalized Laplacian Smoothing Filter
As stated by (Taubin, 1995), the generalized Laplacian smoothing filter is defined as
Note that the filter is non-parametric at all.
3.3. The Choice of k𝑘k
Notice that if we set , the filter becomes the GCN filter.
Thus should decrease as increases. We denote the maximum eigenvalue as . Theoretically, if , the filter is not low-pass in the interval because increases in this interval; Otherwise, if , the filter can not denoise all the high-frequency components. Consequently, is the optimal choice.
It has been proved that the range of Laplacian eigenvalues is between 0 and 2 (Chung and Graham, 1997), hence GCN filter is not low-pass in the interval. Some work (Wang et al., 2019) accordingly chooses . However, our experiments show that after renormalization, the maximum eigenvalue will shrink to around , which makes not optimal as well. In experiments, we calculate for each dataset and set . We further analyse the effects of different values (Section 5.5).
4. Adaptive Encoder
Filtered by -layer Laplacian smoothing, the output features are smoother and preserve abundant attribute information.
To learn better node embeddings from the smoothed features, we need to find an appropriate unsupervised optimization objective. To this end, we manage to utilize pairwise node similarity inspired by Deep Adaptive Learning (Chang et al., 2017). For attributed graph embedding task, the relationship between two nodes is crucial, which requires the training targets to be suitable similarity measurements. GAE-based methods usually choose the adjacency matrix as true labels of node pairs. However, we argue that the adjacency matrix only records one-hop structure information, which is insufficient. Meanwhile, we address that the similarity of smoothed features or trained embeddings are more accurate since they incorporate structure and features together. To this end, we adaptively select node pairs of high similarity as positive training samples, while those of low similarity as negative samples.
where is the weight matrix. We then scale the embeddings to the $\mathbf{S}$ is given by
Next, we describe our training sample selection strategy in detail.
After calculating the similarity matrix, we rank the pairwise similarity sequence in the descending order. Here is the rank of node pair . Then we set the maximum rank of positive samples as and the minimum rank of negative samples as . Therefore, the generated label of node pair is
In this way, a training set with positive samples and negative samples is constructed. Specially, for the first time we construct the training set, since the encoder is not trained, we directly employ the smoothed features for initializing :
After construction of the training set, we can train the encoder in a supervised manner. In real-world graphs, there are always far more dissimilar node pairs than positive pairs, so we select more than negative samples in the training set. To balance positive/negative samples, we randomly choose negative samples in every epoch. The balanced training set is denoted by . Accordingly, our cross entropy loss is given by
4.2. Thresholds Update
Inspired by the idea of curriculum learning (Bengio et al., 2009), we design a specific update strategy for and to control the size of training set. At the beginning of training process, more samples are selected for the encoder to find rough cluster patterns. After that, samples with higher confidence are remained for training, forcing the encoder to capture refined patterns. In practice, decreases while increases linearly as the training procedure goes on. We set the initial threshold as and , together with the final threshold as and . We have and . Suppose the thresholds are updated times, we present the update strategy as
As the training process goes on, every time the thresholds are updated, we reconstruct the training set and save the embeddings. For node clustering, we perform Spectral Clustering (Ng et al., 2002) on the similarity matrices of saved embeddings, and select the best epoch by Davies–Bouldin index (Davies and Bouldin, 1979) (DBI), which measures the clustering quality without label information. For link prediction, we select the best performed epoch on validation set. Algorithm 1 presents the overall procedure of computing the embedding matrix .
Experimental Settings
We evaluate the benefits of AGE against a number of state-of-the-art graph embedding approaches on node clustering and link prediction tasks. In this section, we introduce our benchmark datasets, baseline methods, evaluation metrics, and parameter settings.
We conduct node clustering and link prediction experiments on four widely used network datasets (Cora, Citeseer, Pubmed (Sen et al., 2008) and Wiki (Yang et al., 2015)). Features in Cora and Citeseer are binary word vectors, while in Wiki and Pubmed, nodes are associated with tf-idf weighted word vectors. The statistics of the four datasets are shown in Table 1.
2. Baseline Methods
For attributed graph embedding methods, we include 5 baseline algorithms in our comparisons:
GAE and VGAE (Kipf and Welling, 2016) combine graph convolutional networks with the (variational) autoencoder for representation learning.
ARGA and ARVGA (Pan et al., 2018) add adversarial constraints to GAE and VGAE respectively, enforcing the latent representations to match a prior distribution for robust node embeddings.
GALA (Park et al., 2019) proposes a symmetric graph convolutional autoencoder recovering the feature matrix. The encoder is based on Laplacian smoothing while the decoder is based on Laplacian sharpening.
On the node clustering task, we compare our model with 8 more algorithms. The baselines can be categorized into three groups:
(1) Methods using features only. Kmeans (Lloyd, 1982) and Spectral Clustering (Ng et al., 2002) are two traditional clustering algorithms. Spectral-F takes the cosine similarity of node features as input.
(2) Methods using graph structure only. Spectral-G is Spectral Clustering with the adjacency matrix as the input similarity matrix. DeepWalk (Perozzi et al., 2014) learns node embeddings by using SkipGram on generated random walk paths on graphs.
(3) Methods using both features and graph. TADW (Yang et al., 2015) interprets DeepWalk as matrix factorization and incorporates node features under the DeepWalk framework. MGAE (Wang et al., 2017) is a denoising marginalized graph autoencoder. Its training objective is reconstructing the feature matrix. AGC (Zhang et al., 2019) exploits high-order graph convolution to filter node features. The number of graph convolution layers are selected for different datasets. DAEGC (Wang et al., 2019) employs graph attention network to capture the importance of the neighboring nodes, then co-optimize reconstruction loss and KL-divergence-based clustering loss.
For representation learning algorithms including DeepWalk, TADW, GAE and VGAE which do not specify on the node clustering problem, we apply Spectral Clustering on their learned representations. For other works that conduct experiments on benchmark datasets, the original results in the papers are reported.
AGE variants. We consider 4 variants of AGE to compare various optimization objectives. The Laplacian smoothing filters in these variants are the same, while the encoder of LS+RA aims at reconstructing the adjacency matrix. LS+RX, respectively, reconstructs the feature matrix. LS only preserves the Laplacian smoothing filter, the smoothed features are taken as node embeddings. AGE is our proposed model with adaptive learning.
3. Evaluation Metrics & Parameter Settings
To measure the performance of node clustering methods, we employ three metrics: Accuracy (ACC), Normalized Mutual Information (NMI), and Adjusted Rand Index (ARI) (Gan et al., 2007). For link prediction, we partition the datasets following GAE, and report Area Under Curve (AUC) and Average Precision (AP) scores. For all the metrics, a higher value indicates better performance.
For the Laplacian smoothing filter, we find the maximum eigenvalues of the four datasets are all around . Thus we set universally. For the adaptive encoder, we train the MLP encoder for 400 epochs with a 0.001 learning rate by the Adam optimizer (Kingma and Ba, 2015). The encoder consists of a single 500-dimensional embedding layer, and we update the thresholds every 10 epochs. We tune other hyperparameters including Laplacian smoothing filter layers , , , and based on DBI. The detailed hyperparameter settings are reported in Appendix.
Experimental Results
In this section, we show and analyse the results of our experiments. Besides the main experiments, we also conduct auxiliary experiments to answer the following hypotheses:
H1: Entanglement of the filters and weight matrices has no improvement for embedding quality.
H2: Our adaptive learning strategy is effective compared to reconstruction losses, and each mechanism has its own contribution.
H3: is the optimal choice for Laplacian smoothing filters.
The node clustering results are presented in Table 2, where bold and underlined values indicate the highest scores in all methods and all baselines respectively. Our observations are as follows:
Algorithms using both feature and graph information usually achieve better performance than methods leveraging information from single source. This investigation demonstrates that features and graph structure contribute to clustering from different perspectives.
AGE shows superior performance to baseline methods by a considerable margin, especially on Cora and Wiki datasets. Competing with the strongest baseline GALA, our model outperforms it by 2.95%, 5.20% and 6.20% on Cora, by 12.29%, 18.45% and 13.11% on Wiki with respect to ACC, NMI and ARI. Such results show strong evidence advocating our proposed framework. For Citeseer and Pubmed, we give further analysis in section 5.5.
Compared with GCN-based methods, AGE has simpler mechanisms than those in baselines, such as adversarial regularization or attention. The only trainable parameters are in the weight matrix of the 1-layer perceptron, which minimizes memory usage and improves training efficiency.
2. Link Prediction Results
In this section, we evaluate the quality of node embeddings on the link prediction task. Following the experimental settings of GALA, we conduct experiments on Cora and Citeseer, removing 5% edges for validation and 10% edges for test. The training procedure and hyper-parameters remain unchanged. Given the node embedding matrix , we use a simple inner product decoder to get the predicted adjacency matrix
The experimental results are reported in Table 3. Compared with state-of-the-art unsupervised graph representation learning models, AGE outperforms them on both AUC and AP. It is worth noting that the training objectives of GAE/VGAE and ARGA/ARVGA are the adjacency matrix reconstruction loss. GALA also adds reconstruction loss for the link prediction task, while AGE does not utilize explicit links for supervision.
3. GAE v.s. LS+RA
We use controlled experiments to verify hypothesis H1, evaluating the influence of entanglement of the filters and weight matrices. The compared methods are GAE and LS+RA, where the only difference between them is the position of the weight matrices. GAE, as we show in Figure 1, combines the filter and weight matrix in each layer. LS+RA, however, moves weight matrices after the filter. Specifically, GAE has multiple GCN layers where each one contains a 64-dimensional linear layer, a ReLU activition layer and a graph convolutional filter. LS+RA stacks multiple graph convolutional filters and after which is a 1-layer 64-dimensional perceptron. Both embedding layers of the two models are 16-dimensional. Rest of the parameters are set to the same.
We report the NMI scores for node clustering on the four datasets with different number of filter layers in Figure 3. The results show that LS+RA outperforms GAE under most circumstances with fewer parameters. Moreover, the performance of GAE decreases significantly as the filter layer increases, while LS+RA is relatively stable. A reasonable explanation to this phenomenon is stacking multiple graph convolution layers makes it harder to train all the weight matrices well. Also, the training efficiency will be affected by the deep network.
4. Ablation Study
To validate H2, we first compare the four variants of AGE on the node clustering task. Our findings are listed below:
(1) Compared with raw features (Spectral-F), smoothed features (LS) integrate graph structure, thus perform better on node clustering. The improvement is considerable.
(2) The variants of our model, LS+RA and LS+RX, also show powerful performances compared with baseline methods, which results from our Laplacian smoothing filter. At the same time, AGE still outperforms the two variants, demonstrating that the adaptive optimization target is superior.
(3) Comparing the two reconstruction losses, reconstructing the adjacency matrix (LS+RA) performs better on Cora, Wiki and Pubmed, while reconstructing the feature matrix (LS+RX) performs better on Citeseer. Such difference illustrates that structure information and feature information are of different importance across datasets, therefore either of them is not optimal universally. Furthermore, on Citeseer and Pubmed, the reconstruction losses contribute negatively to the smoothed features.
Then, we conduct ablation study on Cora to manifest the efficacy of four mechanisms in AGE. We set five variants of our model for comparison.
All five variants cluster nodes by performing Spectral Clustering on the cosine similarity matrix of node features or embeddings. “Raw features” simply performs Spectral Clustering on raw node features; “+Filter” clusters nodes using smoothed node features; “+Encoder” initializes training set from the similarity matrix of smoothed node features, and learns node embeddings via the fixed training set; “+Adaptive” selects training samples adaptively with fixed thresholds; “+Thresholds Update” further adds thresholds update strategy and is exactly the full model.
In Table 4, it is obviously noticed that each part of our model contributes to the final performance, which evidently states the effectiveness of them. Additionally, we can observe that model supervised by the similarity of smoothed features (“+Encoder”) outperforms almost all the baselines, giving verification to the rationality of our adaptive learning training objective.
5. Selection of k𝑘k
As stated in section 3.3.3, we select while is the maximum eigenvalue of the renormalized Laplacian matrix. To verify the correctness of our hypothesis (H3), we first plot the eigenvalue distributions of the Laplacian matrix for benchmark datasets in Figure 4. Then, we perform experiments with different and the results are report in Figure 5. From the two figures,we can make the following observations:
(1) The maximum eigenvalues of the four datasets are around , which supports our selecting .
(2) In Figure 5, it is clear that filters with work best for Cora and Wiki datasets, since all three metrics reach the highest scores at . For Citeseer and Pubmed, there is little difference for various .
(3) To further explain why some datasets are sensitive to while some are not, we can look back into Figure 4. Obviously, there are more high-frequency components in Cora and Wiki than Citeseer and Pubmed. Therefore, for Citeseer and Pubmed, filters with different achieve similar effects.
Overall, for Laplacian smoothing filters, we can conclude that is the optimal choice for Laplacian smoothing filters (H3).
6. Visualization
To intuitively show the learned node embeddings, we visualize the node representations in 2D space using -SNE algorithm (Van Der Maaten, 2014). The figures are shown in Figure 6 and each subfigure corresponds to a variant in the ablation study. From the visualization, we can see that AGE can well cluster the nodes according to their corresponding classes. Additionally, as the model gets complete gradually, there are fewer overlapping areas and nodes belong to the same group gather together.
Conclusion
In this paper we propose AGE, a unified unsupervised graph representation learning model. We investigate the graph convolution operation in view of graph signal smoothing, and then design a non-parametric Laplacian smoothing filter which preserves optimal denoising properties to filter out high-frequency noises. In the encoder part, we find adaptive learning is more appropriate for embedding. Experiments on standard benchmarks demonstrate our model has outperformed state-of-the-art baseline algorithms.
For future work, an intriguing direction is to improve the computational efficiency of adaptive learning by avoiding the full computation of the pairwise similarity matrix.
References
Appendix A More Details About The Experiments
Here we describe more details about the experiments to help in reproducibility.
All experiments are conducted on a server under the same environment.
CPU: Intel(R) Xeon(R) Gold 5218 CPU @ 2.30GHz
A.2. Hyperparameter Settings
We report our hyperparameter settings in Table A.2.