Computer Science Mathematics
Computer Science-2021.gz:143269
Computer Science
8380ce56e614d047cf2c5c6106dcfc00beed5b6f
Simple and Effective Graph Autoencoders with One-Hop Linear Models

Graph autoencoders (AE) and variational autoencoders (VAE) recently emerged as powerful node embedding methods, with promising performances on challenging tasks such as link prediction and node clustering. Graph AE, VAE and most of their extensions rely on graph convolutional networks (GCN) encoders to learn vector space representations of nodes. In this paper, we propose to replace the GCN encoder by a significantly simpler linear model w.r.t. the direct neighborhood (one-hop) adjacency matrix of the graph. For the two aforementioned tasks, we show that this approach consistently reaches competitive performances w.r.t. GCN-based models for numerous real-world graphs, including all benchmark datasets commonly used to evaluate graph AE and VAE. We question the relevance of repeatedly using these datasets to compare complex graph AE and VAE. We also emphasize the effectiveness of the proposed encoding scheme, that appears as a simpler and faster alternative to GCN encoders for many real-world applications.


Introduction
Graphs have become ubiquitous, due to the proliferation of data representing relationships or interactions among entities [Hamilton et al., 2017a;Wu et al., 2019b]. Extracting relevant information from these entities, called the nodes of the graph, is crucial to effectively tackle numerous machine learning tasks, such as link prediction or node clustering. While traditional approaches mainly focused on handengineered features [Liben-Nowell and Kleinberg, 2007;Bhagat et al., 2011], significant improvements were recently achieved by methods aiming at directly learning node representations that summarize the graph structure (see [Hamilton et al., 2017a] for a review). In a nutshell, these representation learning methods aim at embedding nodes as vectors in a low-dimensional vector space in which nodes with structural proximity in the graph should be close, e.g. by leveraging random walk strategies [Grover and Leskovec, 2016], matrix factorization [Cao et al., 2015] or graph neural networks [Kipf and Welling, 2016a;Hamilton et al., 2017b].
However, despite the prevalent use of GCN encoders in recent literature, the relevance of this design choice has never been thoroughly studied nor challenged. The actual benefit of incorporating GCNs in graph AE/VAE w.r.t. significantly simpler encoding strategies remains unclear. In this paper 1 , we propose to tackle this important aspect, showing that GCN-based graph AE/VAE are often unnecessarily complex for numerous applications. Our work falls into a family of recent efforts questioning the systematic use of complex deep learning methods without clear comparison to less fancy but simpler baselines [Dacrema et al., 2019;Lin, 2019]. More precisely, our contribution is threefold: • We introduce simpler versions of graph AE and VAE, replacing GCNs by linear models w.r.t. the direct neighborhood (one-hop) adjacency matrix of the graph, involving a unique weight matrix to tune, fewer operations and no activation function.
• Through an extensive empirical analysis on 17 realworld graphs with various sizes and characteristics, we show that our models consistently reach competitive performances w.r.t. GCN-based graph AE and VAE on link prediction and node clustering tasks. We identify settings where simple linear encoders appear as a suitable alternative to GCNs and a first relevant baseline to implement before diving into more complex models, and we question the relevance of current benchmark datasets used to evaluate and compare graph AE and VAE. • We publicly release the code 2 of these experiments, for reproducibility and easier future usages.
This paper is organized as follows. After reviewing key concepts in Section 2, we introduce our simplified graph AE and VAE models in Section 3. We present and interpret our experiments in Section 4, and we conclude in Section 5.

Preliminaries
We consider an undirected graph G = (V, E) with |V| = n nodes and |E| = m edges. A is the direct neighborhood (i.e. one-hop) adjacency matrix of G, and is binary or weighted.

Graph Autoencoders
Graph autoencoders (AE) [Tian et al., 2014;Wang et al., 2016;Kipf and Welling, 2016b] are a family of models aiming at mapping (encoding) each node i ∈ V of the graph to a low-dimensional vector z i ∈ R d , with d n, from which reconstructing (decoding) the graph should be possible. The intuition of this encoding-decoding scheme is the following: if, starting from the node embedding, the model is able to reconstruct an adjacency matrixÂ close to the true one, then the low-dimensional vectors z i should capture some important characteristics of the original graph structure.
Formally, the n × d matrix Z, whose rows are the z i vectors, is usually the output of a graph neural network (GNN) [Bruna et al., 2014;Defferrard et al., 2016;Kipf and Welling, 2016a] processing A. To reconstruct the graph, most models [Kipf and Welling, 2016b] stack an inner product decoder to this GNN, i.e. we haveÂ ij = σ(z T i z j ) for all node pairs (i, j), with σ(·) denoting the sigmoid function: σ(x) = 1/(1 + e −x ). Therefore, the larger the inner product z T i z j in the embedding, the more likely nodes i and j are connected in G according to the AE. In a nutshell, we have: Several recent works [Grover et al., 2019;Salha et al., 2019c;Shi et al., 2020] considered other decoders, that we also implement in Section 4. GNN weights are tuned by gradient descent, to minimize a reconstruction loss capturing the similarity of A andÂ, formulated as a weighted cross entropy loss [Kipf and Welling, 2016b].

Graph Variational Autoencoders
[Kipf and Welling, 2016b] also extended the variational autoencoder (VAE) framework [Kingma and Welling, 2014] to graph structures. Authors designed a probabilistic model involving a latent variable z i of dimension d n for each node i ∈ V, interpreted as node representations in a d-dimensional embedding space. The inference model, i.e. the encoding part of the VAE, is defined as: Gaussian means and variances parameters are learned using a GNN for each one, i.e. µ = GNN µ (A), with µ the matrix stacking up mean vectors µ i ; likewise, log σ = GNN σ (A). Latent vectors z i are samples drawn from these distributions. Then, a generative model aims at reconstructing (decoding) A, leveraging inner products: . During training, GNN weights are tuned by maximizing a tractable variational lower bound (ELBO) of the model's likelihood [Kipf and Welling, 2016b]: by gradient descent, with a Gaussian prior on the distribution of latent vectors, and using the reparameterization trick from [Kingma and Welling, 2014]. D KL (·||·) denotes the Kullback-Leibler divergence.

Graph Convolutional Networks
While the term GNN encoder is generic, a majority of successful applications of graph AE and VAE actually relied andÃ is therefore its symmetric normalization. At each layer, each node averages representations from its neighbors (that, from layer 2, have aggregated representations from their own neighbors), with a ReLU activation: ReLU(x) = max(x, 0). Matrices W (0) , ..., W (L−1) , whose dimensions can vary, are weight matrices to tune.
GCNs became a popular encoding scheme for graph AE and VAE, thanks to its reduced complexity w.r.t. other GNNs [Bruna et al., 2014;Defferrard et al., 2016], and notably the linear time complexity w.r.t. m of evaluating each layer [Kipf and Welling, 2016a]. Last, GCN models can also leverage node-level features, summarized in an n × f matrix X, in addition to the graph structure. In such setting, the input layer becomes H (0) = X instead of the identity matrix I n .
Graph AE and VAE emerged as powerful node embedding methods with promising performances. However, while almost all recent efforts from the literature implement GCN (or an other GNN) encoders, the question of the actual benefit of such complex encoding schemes w.r.t. much simpler strategies remains widely open. In the following two sections, we tackle this important problem,, arguing that GCN encoders often bring unnecessary complexity and redundancy. We propose alternative versions of graph AE and VAE, learning node embeddings from linear models, i.e. from significantly simpler and more interpretable encoders, involving fewer parameters, fewer computations and no activation function.

Linear Graph AE
In this paper, we propose to replace the GCN encoder by a simple linear model w.r.t. the normalized one-hop adjacency matrix of the graph. In the AE framework, we have: We refer to this model as linear graph AE. Embedding vectors are obtained by multiplying the n × n normalized adjacency matrixÃ by a unique n × d weight matrix W . We tune this matrix in a similar fashion w.r.t. graph AE [Kipf and Welling, 2016b], i.e. by iteratively minimizing a weighted cross-entropy loss capturing the quality of the reconstruction A w.r.t. the original matrix A, by gradient descent.
This encoder is a straightforward linear mapping. Each element of z i is a weighted average from node i's direct onehop connections. Contrary to GCN encoders (as L ≥ 2), it ignores higher-order (k-hop with k > 1) information. Also, the encoder does not include any non-linear activation function. In Section 4, we will highlight the very limited impact of these two restrictions on empirical performances.
Our encoder runs in a linear time w.r.t. m using a sparse representation forÃ, and involves fewer operations than a GCN. It includes nd parameters i.e. slightly fewer than the nd + (L − 1)d 2 parameters required by a L-layer GCN with d-dim layers. However, we stress out that, as for standard graph AE, the inner-product decoder has a quadratic O(dn 2 ) complexity, as it involves the multiplication of the two dense matrices Z and Z T . We discuss scalability strategies in Section 4, where we also implement two alternative decoders.
Our linear graph AE can also leverage graph datasets that include node-level features vectors of dimension f , stacked up in the n × f matrix X. The encoding step becomes: where the weight matrix W is then of dimension f × d.

Linear Graph VAE
We adopt the same approach to replace the two GCNs of graph VAE by: µ =ÃW µ and log σ =ÃW σ , with n × d weight matrices W µ and W σ . Then:

Empirical Analysis and Discussion
In this section, we propose an in-depth experimental evaluation of our simplified graph AE and VAE models.

Experimental Setting
Tasks. We consider two learning tasks. Firstly, we focus on link prediction, as in [Kipf and Welling, 2016b] and most subsequent works. We train models on incomplete versions of graphs where 15% of edges were randomly removed. Then, we create validation and test sets from removed edges (resp. from 5% and 10% of edges) and from the same number of randomly sampled pairs of unconnected nodes. We evaluate the model's ability to classify edges from non-edges, using the mean Area Under the Receiver Operating Characteristic (ROC) Curve (AUC) and Average Precision (AP) scores on test sets, averaged over 100 runs with random train/validation/test splits. As a second task, we perform node clustering from z i vectors. When datasets include nodelevel ground-truth communities, we train models on complete graphs, then run k-means algorithms in embedding spaces. We compare output clusters to communities via the mean Adjusted Mutual Information (AMI) scores over 100 runs.
Datasets. We provide experiments on 17 publicly available real-world graphs. For each graph, Tables 1 and 2 report the number of nodes n, the number of edges m, and the dimension f of node features (when available): • We first consider the Cora, Citeseer and Pubmed citation graphs 3 , with and without node features corresponding to f -dimensional bag-of-words vectors. These three graphs , 2020], becoming the de facto benchmark datasets for evaluating graph AE and VAE. Therefore, comparing linear and GCN-based models on these graphs was essential.
• We also report results on 14 alternative graphs. We consider four other citations networks: DBLP 5 , Arxiv-HepTh 4 , Patent 4 and a larger version of Cora 5 , that we denote Cora-larger. We add the WebKD 3 , Blogs 5 and Stanford 5 web graphs, where hyperlinks connect web pages, as well as two Google web graphs (a mediumsize one 5 , denoted Google, and a larger one 4 , denoted Google-large). We complete the list with two social networks (Hamsterster 5 and LiveMocha 5 ), the Flickr 5 image graph (nodes represent images, connected when sharing metadata), the Proteins 5 network of proteins interactions and the Amazon 5 products co-purchase network. We span a wide variety of real-world graphs of various natures, characteristics and sizes (from 877 to 2.7 million nodes, from 1 608 to 13.9 million edges). Models. In all experiments, we compare our models to 2layer and 3-layer GCN-based graph AE/VAE. We do not report performances of deeper models, due to significant scores deterioration. For a comparison to non-AE/VAE methods, which is out of the scope of this study, we refer to [Kipf and Welling, 2016b;Salha et al., 2019a]. All models were trained for 200 epochs (resp. 300 epochs) for graphs with n < 100 000 (resp. n ≥ 100 000). We thoroughly checked the convergence of all models for these epochs numbers. As [Kipf and Welling, 2016b], we ignored edges directions when initial graphs were directed. For Cora, Citeseer and Pubmed, we set identical hyperparameters w.r.t. [Kipf and Welling, 2016b] to reproduce their results, i.e. we had d = 16, 32-dim hidden layer(s) for GCNs, and we used Adam optimizer [Kingma and Ba, 2015] with a learning rate of 0.01. For other datasets, we tuned hyperparameters by performing grid search on the validation set. We adopted a learning rate of 0.1 for Arxiv-HepTh, Patent and Stanford ; of 0.05 for Amazon, Flickr, LiveMocha and Google-large, of 0.01 for Blogs, Cora-larger, DBLP, Google and Hamsterster and Proteins (AE models) ; of 0.005 for WebKD (except linear AE and VAE where we used 0.001 and 0.01) and Proteins (VAE models). We set d = 16 (but we reached similar conclusions with d = 32 and 64), with 32-dim hidden layer(s) and without dropout. Last, due to the prohibitive quadratic cost of reconstructing (decoding) the exactÂ for large graphs (with n ≥ 100 000), we adopted a simple stochastic sampling strategy for these graphs: at each training iteration, we estimated losses by reconstructing a subgraph of 10 000 randomly picked nodes.

Results
Cora, Citeseer and Pubmed benchmarks.  AE/VAE, especially on global tasks such as node clustering.
On more complex decoders. So far, we compared different encoders but the (standard) inner-product decoder was fixed. As a robustness check, in On k-hop linear encoders. While we only learn from direct neighbors interactions, variants of our models could capture higher-order links by considering polynomials of the matrix A. For instance, we could learn embeddings from onehop and two-hop links by replacingÃ by the normalized version of A + αA 2 (with α > 0), or simply A 2 , in the linear encoders of Section 3. While our online implementation proposes such alternative, we observed few to no improvement on most of our graphs, consistently with our claim on the effectiveness of simple one-hop strategies. We underline that such variants significantly increase running times w.r.t. our models (see below), as A 2 is usually much denser than A.
On running times. While this work put the emphasis on performance, we also note that linear AE and VAE models are 10% to 15% faster than their GCN-based counterparts. For instance, on an NVIDIA GTX 1080 GPU, we report a 6.03 seconds (vs 6.73 seconds) mean running time for linear graph VAE (vs 2-layer GCN graph VAE) on the featureless Citeseer dataset, and 791 seconds (vs 880 seconds) on the Patent dataset, using our sampling strategy from Section 4.1. This gain comes from the slightly fewer parameters and matrix operations required by our linear encoders and from the sparsity of the one-hop matrixÃ for most real-world graphs. Nonetheless, as an opening, we point out that the problem of scalable graph autoencoders remains quite open. Despite advances on the encoder, the standard inner-product decoder still suffer from a O(dn 2 ) time complexity. Our very simple sampling strategy to overcome this quadratic cost on large graphs (randomly sampling subgraphs to reconstruct) might not be optimal. Future works will tackle these issues, aiming at providing efficient strategies to scale graph AE and VAE.

Conclusion
We highlighted that, despite their prevalent use in recent literature, GCN-based graph AE and VAE are often unnecessarily complex, and that significantly simpler and more interpretable versions of these models achieve comparable performances on numerous real-world datasets. In this direction, we introduced simplified yet effective encoding schemes limiting to one-hop linear strategies, that we recommend to use as baselines to assess the actual benefit of complex encoders.