Graphite: Iterative Generative Modeling of Graphs

Introduction

Latent variable generative modeling is an effective approach for unsupervised representation learning of high-dimensional data (Loehlin, 1998). In recent years, representations learned by latent variable models parameterized by deep neural networks have shown impressive performance on many tasks such as semi-supervised learning and structured prediction (Kingma et al., 2014; Sohn et al., 2015). However, these successes have been largely restricted to specific data modalities such as images and speech. In particular, it is challenging to apply current deep generative models for large scale graph-structured data which arise in a wide variety of domains in physical sciences, information sciences, and social sciences.

To effectively model the relational structure of large graphs for deep learning, prior works have proposed to use graph neural networks (Gori et al., 2005; Scarselli et al., 2009; Bruna et al., 2013). A graph neural network learns node-level representations by parameterizing an iterative message passing procedure between nodes and their neighbors. The tasks which have benefited from graph neural networks, including semi-supervised learning (Kipf & Welling, 2017) and few shot learning (Garcia & Bruna, 2018), involve encoding an input graph to a final output representation (such as the labels associated with the nodes). The inverse problem of learning to decode a hidden representation into a graph, as in the case of a latent variable generative model, is a pressing challenge that we address in this work.

We propose Graphite, a latent variable generative model for graphs based on variational autoencoding (Kingma & Welling, 2014). Specifically, we learn a directed model expressing a joint distribution over the entries of adjacency matrix of graphs and latent feature vectors for every node. Our framework uses graph neural networks for inference (encoding) and generation (decoding). While the encoding is straightforward and can use any existing graph neural network, the decoding of these latent features to reconstruct the original graph is done using a multi-layer iterative procedure. The procedure starts with an initial reconstruction based on the inferred latent features, and iteratively refines the reconstructed graph via a message passing operation. The iterative refinement can be efficiently implemented using graph neural networks. In addition to the Graphite model, we also contribute to the theoretical understanding of graph neural networks by deriving equivalences between message passing in graph neural networks with mean-field inference in latent variable models via kernel embeddings (Smola et al., 2007; Dai et al., 2016), formalizing what has thus far has been largely speculated empirically to the best of our knowledge (Yoon et al., 2018).

In contrast to recent works focussing on generation of small graphs e.g., molecules (You et al., 2018; Li et al., 2018), the Graphite framework is particularly suited for representation learning on large graphs. Such representations are useful for several downstream tasks. In particular, we demonstrate that representations learned via Graphite outperform competing approaches for graph representation learning empirically for the tasks of density estimation (over entire graphs), link prediction, and semi-supervised node classification on synthetic and benchmark datasets.

Preliminaries

The “$k$-dim” WL algorithm extends the 1-dim algorithm above by simultaneously passing messages of length $k$ (each initialized with some isomorphism invariant scheme). A positive test for isomorphism requires equality in all $k$ dimensions for nodes in $G$ and $G^{\prime}$ after the termination of message passing. This algorithmic test is a heuristic which guarantees no false negatives but can give false positives wherein two non-isomorphic graphs can be falsely declared isomorphic. Empirically, the test has been shown to fail on some regular graphs but gives excellent performance on real-world graphs (Shervashidze et al., 2011).

2 Graph neural networks

Intuitively, the WL algorithm encodes the structure of the graph in the form of messages at every node. Graph neural networks (GNN) build on this observation and parameterize an unfolding of the iterative message passing procedure which we describe next.

with the base cases $\mathbf{H}^{(0)}=\mathbf{X}$ and $d_{0}=m$. Here, $m$ is the feature dimensionality. If there are no explicit node features, we set $\mathbf{H}^{(0)}=\mathbf{I}_{n}$ (identity) and $d_{0}=n$. Several variants of graph neural networks have been proposed in prior work. For instance, graph convolutional networks (GCN) (Kipf & Welling, 2017) instantiate graph neural networks with a permutation equivariant propagation rule:

Generative Modeling via Graphite

For generative modeling of graphs, we are interested in learning a parameterized distribution over adjacency matrices $\mathbf{A}$. In this work, we restrict ourselves to modeling graph structure only, and any additional information in the form of node features $\mathbf{X}$ is incorporated as conditioning evidence.

Here, $p(\mathbf{Z}|\mathbf{X})$ is a fixed prior distribution over the latent features of every node e.g., isotropic Gaussian. If we have multiple graphs in our dataset, we maximize the expected log-likelihoods over all the corresponding adjacency matrices. We can obtain a tractable, stochastic evidence lower bound (ELBO) to the above objective by introducing a variational posterior $q_{\phi}(\mathbf{Z}|\mathbf{A},\mathbf{X})$ with parameters $\phi$:

The lower bound is tight when the variational posterior $q_{\phi}(\mathbf{Z}|\mathbf{A},\mathbf{X})$ matches the true posterior $p_{\theta}(\mathbf{Z}|\mathbf{A},\mathbf{X})$ and hence maximizing the above objective optimizes for the parameters that define the best approximation to the true posterior within the variational family (Blei et al., 2017). We now discuss parameterizations for specifying $q_{\phi}(\mathbf{Z}|\mathbf{A},\mathbf{X})$ (i.e., encoder) and $p_{\theta}(\mathbf{A}|\mathbf{Z},\mathbf{X})$ (i.e., decoder).

Typically we use the mean field approximation for defining the variational family and hence:

Additionally, we would like to make distributional assumptions on each variational marginal density $q_{\phi_{i}}(\mathbf{Z}_{i}|\mathbf{A},\mathbf{X})$ such that it is reparameterizable and easy-to-sample, such that the gradients w.r.t. $\phi_{i}$ have low variance (Kingma & Welling, 2014). In Graphite, we assume isotropic Gaussian variational marginals with diagonal covariance. The parameters for the variational marginals $q_{\phi_{i}}(\mathbf{Z}|\mathbf{A},\mathbf{X})$ are specified using a graph neural network:

where $\boldsymbol{\mu}$ and $\boldsymbol{\sigma}$ denote the vector of means and standard deviations for the variational marginals $\{q_{\phi_{i}}(\mathbf{Z}_{i}|\mathbf{A},\mathbf{X})\}_{i=1}^{n}$ and $\phi=\{\phi_{i}\}_{i=1}^{n}$ are the full set of variational parameters.

Decoding using reverse message passing.

For specifying the observation model $p_{\theta}(\mathbf{A}|\mathbf{Z},\mathbf{X})$, we cannot directly use a graph neural network since we do not have an input graph for message passing. To sidestep this issue, we propose an iterative two-step approach that alternates between defining an intermediate graph and then gradually refining this graph through message passing. Formally, given a latent matrix $\mathbf{Z}$ and an input feature matrix $\mathbf{X}$, we iterate over the following sequence of operations:

1 Scalable learning & inference in Graphite

For representation learning of large graphs, we require the encoding and decoding steps in Graphite to be computationally efficient. On the surface, the decoding step involves inner products of potentially dense matrices $\mathbf{Z}$, which is an $O(n^{2}k)$ operation. Here, $k$ is the dimension of the per-node latent vectors $\mathbf{Z}_{i}$ used to define $\widehat{\mathbf{A}}$.

For any intermediate decoding step as in Eq. (8), we propose to offset this expensive computation by using the associativity property of matrix multiplications for the message passing step in Eq. (9). For notational brevity, consider the simplified graph propagation rule for a GNN:

where $\widehat{\mathbf{A}}$ is defined in Eq. (8).

Instead of directly taking an inner product of $\mathbf{Z}$ with itself, we note that the subsequent operation involves another matrix multiplication and hence, we can perform right multiplication instead. If $d_{l}$ and $d_{l-1}$ denote the size of the layers $\mathbf{H}^{(l)}$ and $\mathbf{H}^{(l-1)}$ respectively, then the time complexity of propagation based on right multiplication is given by $O(nkd_{l-1}+nd_{l-1}d_{l})$.

The above trick sidesteps the quadratic $n^{2}$ complexity for decoding in the intermediate layers without any loss in statistical accuracy. The final layer however still involves an inner product with respect to $\mathbf{Z}^{\ast}$ between potentially dense matrices. However, since the edges are generated independently, we can approximate the loss objective by performing a Monte Carlo evaluation of the reconstructed adjacency matrix parameters in Eq. (10). By adaptively choosing the number of entries for Monte Carlo approximation, we can trade-off statistical accuracy for computational budget.

Experimental Evaluation

We evaluate Graphite on tasks involving entire graphs, nodes, and edges. We consider two variants of our proposed framework: the Graphite-VAE, which corresponds to a directed latent variable model as described in Section 3 and Graphite-AE, which corresponds to an autoencoder trained to minimize the error in reconstructing an input adjacency matrix. For unweighted graphs (i.e., $\mathbf{A}\in\{0,1\}^{n\times n}$), the reconstruction terms in the objectives for both Graphite-VAE and Graphite-AE minimize the negative cross entropy between the input and reconstructed adjacency matrices. For weighted graphs, we use the mean squared error. Additional hyperparameter details are described in Appendix B.

In the first set of tasks, we evaluate learning in Graphite based on held-out reconstruction losses and log-likelihoods estimated by the learned Graphite-VAE and Graphite-AE models respectively on a collection of graphs with varying sizes. In direct contrast to modalities such as images, graphs cannot be straightforwardly reduced to a fixed number of vertices for input to a graph convolutional network. One simplifying modification taken by Bojchevski et al. (2018) is to consider only the largest connected component for evaluating and optimizing the objective, which we appeal to as well. Thus by setting the dimensions of $\mathbf{Z}^{*}$ to a maximum number of vertices, Graphite can be used for inference tasks over entire graphs with potentially smaller sizes by considering only the largest connected component.

We create datasets from six graph families with fixed, known generative processes: the Erdos-Renyi, ego-nets, random regular graphs, random geometric graphs, random Power Law Tree and Barabasi-Albert. For each family, 300 graph instances were sampled with each instance having $10-20$ nodes and evenly split into train/validation/test instances. As a benchmark comparison, we compare against the Graph Autoencoder/Variational Graph Autoencoder (GAE/VGAE) (Kipf & Welling, 2016). The GAE/VGAE models consist of an encoding procedure similar to Graphite. However, the decoder has no learnable parameters and reconstruction is done solely through an inner product operation (such as the one in Eq. (8)).

The mean reconstruction errors and the negative log-likelihood results on a test set of instances are shown in Table 1. Both Graphite-AE and Graphite-VAE outperform AE and VGAE significantly on these tasks, indicating the usefulness of learned decoders in Graphite.

2 Link prediction

The task of link prediction is to predict whether an edge exists between a pair of nodes (Loehlin, 1998). Even though Graphite learns a distribution over graphs, it can be used for predictive tasks within a single graph. In order to do so, we learn a model for a random, connected training subgraph of the true graph. For validation and testing, we add a balanced set of positive and negative (false) edges to the original graph and evaluate the model performance based on the reconstruction probabilities assigned to the validation and test edges (similar to denoising of the input graph). In our experiments, we held out a set of $5\%$ edges for validation, $10\%$ edges for testing, and train all models on the remaining subgraph. Additionally, the validation and testing sets also each contain an equal number of non-edges.

We compared across standard benchmark citation network datasets: Cora, Citeseer, and Pubmed with papers as nodes and citations as edges (Sen et al., 2008). The node-level features correspond to the text attributes in the papers. The dataset statistics are summarized in Table 2.

Baselines and evaluation metrics.

We evaluate performance based on the Area Under the ROC Curve (AUC) and Average Precision (AP) metrics. We evaluated Graphite-VAE and Graphite-AE against the following baselines: Spectral Clustering (SC) (Tang & Liu, 2011), DeepWalk (Perozzi et al., 2014), node2vec (Grover & Leskovec, 2016), and GAE/VGAE (Kipf & Welling, 2016). SC, DeepWalk, and node2vec do not provide the ability to incorporate node features while learning embeddings, and hence we evaluate them only on the featureless datasets.

Results.

The AUC and AP results (along with standard errors) are shown in Table 3 and Table 4 respectively averaged over 50 random train/validation/test splits. On both metrics, Graphite-VAE gives the best performance overall. Graphite-AE also gives good results, generally outperforming its closest competitor GAE.

Qualitative evaluation.

We visualize the embeddings learned by Graphite and given by a 2D t-SNE projection (Maaten & Hinton, 2008) of the latent feature vectors (given as rows for $\mathbf{Z}$ with $\lambda=0.5$) on the Cora dataset in Figure 2. Even without any access to label information for the nodes during training, the name models are able to cluster the nodes (papers) as per their labels (paper categories).

3 Semi-supervised node classification

Given labels for a subset of nodes in an underlying graph, the goal of this task is to predict the labels for the remaining nodes. We consider a transductive setting, where we have access to the test nodes (without their labels) during training.

Closest approach to Graphite for this task is a supervised graph convolutional network (GCN) trained end-to-end. We consider an extension of this baseline, wherein we augment the GCN objective with the Graphite objective and a hyperparameter to control the relative importance of the two terms in the combined objective. The parameters $\phi$ for the encoder are shared across these two objectives, with an additional GCN layer for mapping the encoder output to softmax probabilities over the requisite number of classes. All parameters are learned jointly.

The classification accuracy of the semi-supervised models is given in Table 5. We find that Graphite-hybrid outperforms the competing models on all datasets and in particular the GCN approach which is the closest baseline. Recent work in Graph Attention Networks shows that extending GCN by incoporating attention can boost performance on this task (Veličković et al., 2018). Using GATs in place of GCNs for parameterizing Graphite could yield similar performance boost in future work.

Theoretical Analysis

In this section, we derive a theoretical connection between message passing in graph neural networks and approximate inference in related undirected graphical models.

Kernel methods can be used to specify embeddings of distributions of arbitrary objects (Smola et al., 2007; Gretton et al., 2007). Formally, we denote these functional mappings as $T_{\psi}:\mathcal{P}\rightarrow\mathcal{H}$ where $\mathcal{P}$ specifies the space of all distributions on $\mathcal{Z}$. These mappings, referred to as kernel embeddings of distributions, are defined as:

2 Connections with mean-field inference

Locality preference for representational learning is a key inductive bias for graphs. We formulate this using an (undirected) graphical model $\mathcal{G}$ over $\mathbf{X}$, $\mathbf{A}$, and $\{\mathbf{Z}_{1},\cdots,\mathbf{Z}_{n}\}$. As in a GNN, we assume that $\mathbf{X}$ and $\mathbf{A}$ are observed and specify conditional independence structure in a conditional distribution over the latent variables, denoted as $r(\mathbf{Z}_{1},\cdots,\mathbf{Z}_{n}|\mathbf{A},\mathbf{X})$. We are particularly interested in models that satisfy the following property.

The edge set $E$ defined by the adjacency matrix $\mathbf{A}$ is an undirected I-map for the distribution $r(\mathbf{Z}_{1},\cdots,\mathbf{Z}_{n}|\mathbf{A},\mathbf{X})$.

In words, the above property implies that according to the conditional distribution over $\mathbf{Z}$, any individual $\mathbf{Z}_{i}$ is independent of all other $\mathbf{Z}_{j}$ when conditioned on $\mathbf{A}$, $\mathbf{X}$, and the neighboring latent variables of node $i$ as determined by the edge set $E$. See Figure 3 for an illustration.

A mean-field (MF) approximation for $\mathcal{G}$ approximates the conditional distribution $r(\mathbf{Z}_{1},\cdots,\mathbf{Z}_{n}|\mathbf{A},\mathbf{X})$ as:

where $\phi_{i}$ denotes the set of parameters for the $i$-th variational marginal. These parameters are optimized by minimizing the KL-divergence between the variational and the true conditional distributions:

Using standard variational arguments (Wainwright et al., 2008), we know that the optimal variational marginals assume the following functional form:

with an appropriate base case for $\boldsymbol{\mu}^{(0)}_{i}$. We then have the following result:

Let $\mathcal{G}$ be any undirected latent variable model such that the conditional distribution $r(\mathbf{Z}_{1},\cdots,\mathbf{Z}_{n}|\mathbf{A},\mathbf{X})$ expressed by the model satisfies Property 1.

Then there exists a choice of $\eta_{l}$, $\mathcal{F}_{l}$, $\mathbf{W}_{l}$, and $\mathbf{B}_{l}$ such that for all $\{\boldsymbol{\mu}^{(l-1)}_{i}\}_{i=1}^{n}$, the GNN propagation rule in Eq. (2) is computationally equivalent to updating $\{\boldsymbol{\mu}^{(l-1)}_{i}\}_{i=1}^{n}$ via a first order approximation of Eq. (17).

While $\eta_{l}$ and $\mathcal{F}_{l}$ are typically fixed beforehand, the parameters $\mathbf{W}_{l}$, and $\mathbf{B}_{l}$ are directly learned from data in practice. Hence we have shown that a GNN is a good model for computation with respect to latent variable models that attempt to capture inductive biases relevant to graphs, i.e., ones where the latent feature vector for every node is conditionally independent from everything else given the feature vectors of its neighbors (and $\mathbf{A}$, $\mathbf{X}$). Note that such a graphical model would satisfy Property 1 but is in general different from the posterior specified by the one in Figure 1. However if the true (but unknown) posterior on the latent variables for the model proposed in Figure 1 could be expressed as an equivalent model satisfying the desired property, then Theorem 2 indeed suggests the use of GNNs for parameterizing variational posteriors, as we do so in the case of Graphite.

Discussion & Related Work

Our framework effectively marries probabilistic modeling and representation learning on graphs. We review some of the dominant prior works in these fields below.

The earliest probabilistic models of graphs proposed to generate graphs by creating an edge between any pair of nodes with a constant probability (Erdös & Rényi, 1959). Several alternatives have been proposed since; e.g., the small-world model generates graphs that exhibit local clustering (Watts & Strogatz, 1998), the Barabasi-Albert models preferential attachment wherein high-degree nodes are likely to form edges with newly added nodes (Barabasi & Albert, 1999), the stochastic block model is based on inter and intra community linkages (Holland et al., 1983) etc. We direct the interested reader to prominent surveys on this topic (Newman, 2003; Mitzenmacher, 2004; Chakrabarti & Faloutsos, 2006).

Representation learning on graphs.

For representation learning on graphs, there are broadly three kinds of approaches: matrix factorization, random walk based approaches, and graph neural networks. We include a brief discussion on the first two kinds in Appendix C and refer the reader to Hamilton et al. (2017b) for a recent survey.

Graph neural networks, a collective term for networks that operate over graphs using message passing, have shown success on several downstream applications, e.g., (Duvenaud et al., 2015; Li et al., 2016; Kearnes et al., 2016; Kipf & Welling, 2017; Hamilton et al., 2017a) and the references therein. Gilmer et al. (2017) provides a comprehensive characterization of these networks in the message passing setup. We used Graph Convolution Networks, partly to provide a direct comparison with GAE/VGAE and leave the exploration of other GNN variants for future work.

Latent variable models for graphs.

Hierarchical Bayesian models parameterized by deep neural networks have been recently proposed for graphs (Hu et al., 2017; Wang et al., 2017). Besides being restricted to single graphs, these models are limited since inference requires running expensive Markov chains (Hu et al., 2017) or are task-specific (Wang et al., 2017). Johnson (2017) and Kipf et al. (2018) generate graphs as latent representations learned directly from data. In contrast, we are interested in modeling observed (and not latent) relational structure. Finally, there has been a fair share of recent work for generation of special kinds of graphs, such as parsed trees of source code (Maddison & Tarlow, 2014) and SMILES representations for molecules (Olivecrona et al., 2017).

Several deep generative models for graphs have recently been proposed. Amongst adversarial generation approaches, Wang et al. (2018) and Bojchevski et al. (2018) model local graph neighborhoods and random walks on graphs respectively. Li et al. (2018) and You et al. (2018) model graphs as sequences and generate graphs via autoregressive procedures. Adversarial and autoregressive approaches are successful at generating graphs, but do not directly allow for inferring latent variables via encoders. Latent variable generative models have also been proposed for generating small molecular graphs (Jin et al., 2018; Samanta et al., 2018; Simonovsky & Komodakis, 2018). These methods involve an expensive decoding procedure that limits scaling to large graphs. Finally, closest to our framework is the GAE/VGAE approach (Kipf & Welling, 2016) discussed in Section 4. Pan et al. (2018) extends this approach with an adversarial regularization framework but retain the inner product decoder. Our work proposes a novel multi-step decoding mechanism based on graph refinement.

Conclusion & Future Work

We proposed Graphite, a scalable deep generative model for graphs based on variational autoencoding. The encoders and decoders in Graphite are parameterized by graph neural networks that propagate information locally on a graph. Our proposed decoder performs a multi-layer iterative decoding comprising of alternate inner product operations and message passing on the intermediate graph.

Current generative models for graphs are not permutation-invariant and are learned by feeding graphs with a fixed or heuristic ordering of nodes. This is an exciting challenge for future work, which could potentially be resolved by incorporate graph representations robust to permutation invariances (Verma & Zhang, 2017) or modeling distributions over permutations of node orderings via recent approaches such as NeuralSort (Grover et al., 2019). Extending Graphite for modeling richer graphical structure such as heterogeneous and time-varying graphs, as well as integrating domain knowledge within Graphite decoders for applications in generative design and synthesis e.g., molecules, programs, and parse trees is another interesting future direction.

Finally, our theoretical results in Section 5 suggest that a principled design of layerwise propagation rules in graph neural networks inspired by additional message passing inference schemes (Dai et al., 2016; Gilmer et al., 2017) is another avenue for future research.

Acknowledgements

This research has been supported by Siemens, a Future of Life Institute grant, NSF grants (#1651565, #1522054, #1733686), ONR (N00014-19-1-2145), AFOSR (FA9550-19-1-0024), and an Amazon AWS Machine Learning Grant. AG is supported by a Microsoft Research Ph.D. fellowship and a Stanford Data Science Scholarship. We would like to thank Daniel Levy for helpful comments on early drafts.

References

Appendices

Appendix A Proof of Theorem 2

where $\mathbf{A}_{i}$ denotes the $i$-th row of $\mathbf{A}$ and is non-zero only for entries corresponding to the neighbors of node $i$.

Now, consider the following instantiation of Eq. (20):

$\eta_{l}\leftarrow\mathcal{I}$ (identity function)

With the above substitutions, we can equate the first order approximation in Eq. (18) to the GNN message passing rule in Eq. (20), thus completing the proof. With vectorized notation and use of matrix calculus in Eqs. (18-20), the derivation above also applies to entire vectors of variational marginal embeddings with arbitrary dimensions. ∎

Appendix B Experiment Specifications

We used the SC implementation from (Pedregosa et al., 2011) and public implementations for others made available by the authors. For SC, we used a dimension size of $128$. For DeepWalk and node2vec which uses a skipgram like objective on random walks from the graph, we used the same dimension size and default settings used in (Perozzi et al., 2014) and (Grover & Leskovec, 2016) respectively of $10$ random walks of length $80$ per node and a context size of $10$. For node2vec, we searched over the random walk bias parameters using a grid search in $\{0.25,0.5,1,2,4\}$ as prescribed in the original work. For GAE and VGAE, we used the same architecture as VGAE and Adam optimizer with learning rate of $0.01$.

For Graphite-AE and Graphite-VAE, we used an architecture of 32-32 units for the encoder and 16-32-16 units for the decoder (two rounds of iterative decoding before a final inner product). The model is trained using the Adam optimizer (Kingma & Welling, 2014) with a learning rate of $0.01$. All activations were RELUs.The dropout rate (for edges) and $\lambda$ were tuned as hyperparameters on the validation set to optimize the AUC, whereas traditional dropout was set to 0 for all datasets. Additionally, we trained every model for $500$ iterations and used the model checkpoint with the best validation loss for testing. Scores are reported as an average of 50 runs with different train/validation/test splits (with the requirement that the training graph necessarily be connected).

For Graphite, we observed that using a form of skip connections to define a linear combination of the initial embedding $\mathbf{Z}$ and the final embedding $\mathbf{Z}^{*}$ is particularly useful. The skip connection consists of a tunable hyperparameter $\lambda$ controlling the relative weights of the embeddings. The final embedding of Graphite is a function of the initial embedding $Z$ and the last induced embedding $Z^{*}$. We consider two functions to aggregate them into a final embedding. That is, $(1-\lambda)Z+\lambda Z^{*}$ and $Z+\lambda Z^{*}/\left\lVert Z^{*}\right\rVert$, which correspond to a convex combination of two embeddings, and an incremental update to the initial embedding in a given direction, respectively. Note that in either case, GAE and VGAE reduce to a special case of Graphite, using only a single inner-product decoder (i.e., $\lambda=0$). On Cora and Pubmed final embeddings were derived through convex combination, on Citeseer through incremental update.

We experimented with learning VGAE and Graphite models by subsampling $|E|$ random entries for Monte Carlo evaluation of the objective at each iteration. The corresponding AUC scores are shown in Table 6. The results suggest that Graphite can effectively scale to large graphs without significant loss in accuracy. The AUC results trained with edge subsampling as we vary the subsampling coefficient $c$ are shown in Figure 4.

B.2 Semi-supervised node classification

We report the baseline results for SemiEmb (Weston et al., 2008), DeepWalk (Perozzi et al., 2014), ICA (Lu & Getoor, 2003) and Planetoid (Yang et al., 2016) as specified in (Kipf & Welling, 2017). GCN uses a 32-16 architecture with ReLu activations and early stopping after $10$ epochs without increasing validation accuracy. The Graphite model uses the same architecture as in link prediction (with no edge dropout). The parameters of the posterior distributions are concatenated with node features to predict the final output. The parameters are learned using the Adam optimizer (Kingma & Welling, 2014) with a learning rate of $0.01$. All accuracies are taken as an average of 100 runs.

B.3 Density estimation

To accommodate for input graphs of different sizes, we learn a model architecture specified for the maximum possible nodes (i.e., $20$ in this case). While feeding in smaller graphs, we simply add dummy nodes disconnected from the rest of the graph. The dummy nodes have no influence on the gradient updates for the parameters affecting the latent or observed variables involving nodes in the true graph. For the experiments on density estimation, we pick a graph family, then train and validate on graphs sampled exclusively from that family. We consider graphs with nodes ranging between 10 and 20 nodes belonging to the following graph families :

Erdos-Renyi (Erdös & Rényi, 1959): each edge independently sampled with probability $p=0.5$

Ego Network: a random Erdos-Renyi graph with all nodes neighbors of one randomly chosen node

Random Regular: uniformly random regular graph with degree $d=4$

Random Geometric: graph induced by uniformly random points in unit square with edges between points at euclidean distance less than $r=0.5$

Random Power Tree: Tree generated by randomly swapping elements from a degree distribution to satisfy a power law distribution for $\gamma=3$

Barabasi-Albert (Barabasi & Albert, 1999): Preferential attachment graph generation with attachment edge count $m=4$

We use convex combinations over three successively induced embeddings. Scores are reported over an average of 50 runs. Additionally, a two-layer neural net is applied to the initially sampled embedding $\mathbf{Z}$ before being fed to the inner product decoder for GAE and VGAE, or being fed to the iterations of Eqs. (8) and (9) for both Graphite-AE and Graphite-VAE.

Appendix C Additional Related Work

Factorization based approaches, such as Laplacian Eigenmaps (Belkin & Niyogi, 2002) and IsoMaps (Saxena et al., 2004), operate on a matrix representation of the graph, such as the adjacency matrix or the graph Laplacian. These approaches are closely related to dimensionality reduction and can be computationally expensive for large graphs.

Random-walk methods are based on variations of the skip-gram objective (Mikolov et al., 2013) and learn representations by linearizing the graph through random walks. These methods, in particular DeepWalk (Perozzi et al., 2014), LINE (Tang et al., 2015), and node2vec (Grover & Leskovec, 2016), learn general-purpose unsupervised representations that have been shown to give excellent performance for semi-supervised node classification and link prediction. Planetoid (Yang et al., 2016) learn representations based on a similar objective specifically for semi-supervised node classification by explicitly accounting for the available label information during learning.