Learning Graph Representations with Embedding Propagation

Introduction

Graph-structured data occurs in numerous application domains such as social networks, bioinformatics, natural language processing, and relational knowledge bases. The computational problems commonly addressed in these domains are network classification , statistical relational learning , link prediction , and anomaly detection , to name but a few. In addition, graph-based methods for unsupervised and semi-supervised learning are often applied to data sets with few labeled examples. For instance, spectral decompositions and locally linear embeddings (LLE) are always computed for a data set’s affinity graph, that is, a graph that is first constructed using domain knowledge or some measure of similarity between data points. Novel approaches to unsupervised representation learning for graph-structured data, therefore, are important contributions and are directly applicable to a wide range of problems.

Ep learns vector representations (embeddings) of graphs by passing messages between neighboring nodes. This is reminiscent of power iteration algorithms which are used for such problems as computing the PageRank for the web graph , running label propagation algorithms , performing isomorphism testing , and spectral clustering . Whenever a computational process can be mapped to message exchanges between nodes, it is implementable in graph processing frameworks such as Pregel , GraphLab , and GraphX .

Graph labels represent vertex attributes such as bag of words, movie genres, categorical features, and continuous features. They are not to be confused with class labels of a supervised classification problem. In the Ep learning framework, each vertex $v$ sends and receives two types of messages. Label representations are sent from $v$’s neighboring nodes to $v$ and are combined so as to reconstruct the representations of $v$’s labels. The gradients resulting from the application of some reconstruction loss are sent back as messages to the neighboring vertices so as to update their labels’ representations and the representations of $v$’s labels. This process is repeated for a certain number of iterations or until a convergence threshold is reached. Finally, the label representations of $v$ are used to compute a representation of $v$ itself.

Despite its conceptual simplicity, we show that Ep generalizes several existing machine learning methods for graph-structured data. Since Ep learns embeddings by incorporating different label types (representing, for instance, text and images) it is a framework for learning with multi-modal data .

Previous Work

There are numerous methods for embedding learning such as multidimensional scaling (MDS) , Laplacian Eigenmap , Siamese networks , IsoMap , and LLE . Most of these approaches construct an affinity graph on the data points first and then embed the graph into a low dimensional space. The corresponding optimization problems often have to be solved in closed form (for instance, due to constraints on the objective that remove degenerate solutions) which is intractable for large graphs. We discuss the relation to LLE in more detail when we analyze our framework.

Graph neural networks (GNN) is a general class of recursive neural networks for graphs where each node is associated with one label. Learning is performed with the Almeida-Pineda algorithm . The computation of the node embeddings is performed by backpropagating gradients for a supervised loss after running a recursive propagation model to convergence. In the Ep framework gradients are computed and backpropagated immediately for each node. Gated graph sequence neural networks (GG-SNN) modify GNN to use gated recurrent units and modern optimization techniques. Recent work on graph convolutional networks (GCNs) uses a supervised loss to inject class label information into the learned representations . GCNs as well as GNNs and GG-SNNs, can be seen as instances of the Message Passing Neural Network (Mpnn) framework, recently introduced in . There are several significant differences between the Ep and Mpnn framework: (i) all instances of Mpnn use a supervised loss but Ep is unsupervised and, therefore, classifier agnostic; (ii) Ep learns label embeddings for each of the different label types independently and combines them into a joint node representation whereas all existing instances of Mpnn do not provide an explicit method for combining heterogeneous feature types. Moreover, Ep’s learning principle based on reconstructing each node’s representation from neighboring nodes’ representations is highly suitable for the inductive setting where nodes are missing during training.

Most closely related to our work is DeepWalk which applies a word embedding algorithm to random walks. The idea is that random walks (node sequences) are treated as sentences (word sequences). A SkipGram model is then used to learn node embeddings from the random walks. Node2vec is identical to DeepWalk with the exception that it explores new methods to generate random walks (the input sentences to word2vec), at the cost of introducing more hyperparamenters. Line optimizes similarities between pairs of node embeddings so as to preserve their first and second-order proximity. The main advantage of Ep over these approaches is its ability to incorporate graph attributes such as text and continuous features. Planetoid combines a learning objective similar to that of DeepWalk with supervised objectives. It also incorporates bag of words associated with nodes into these supervised objectives. We show experimentally that for graph without attributes, all of the above methods learn embeddings of similar quality and that Ep outperforms all other methods significantly on graphs with word labels. We can also show that Ep generalizes methods that learn embeddings for multi-relational graphs such as TransE .

Embedding Propagation

A graph $G=(V,E)$ consists of a set of vertices $V$ and a set of edges $E\subseteq\{(v,w)\mid v,w\in V\}$. The approach works with directed and undirected edges as well as with multiple edge types. $\mathbf{N}(v)$ is the set of neighbors of $v$ if $G$ is undirected and the set of in-neighbors if $G$ is directed. The graph $G$ is associated with a set of $k$ label classes $\mathbf{L}=\{L_{1},...,L_{k}\}$ where each $L_{i}$ is a set of labels corresponding to label type $i$. A label is an identifier of some object and not to be confused with a class label in classification problems. Labels allow us to represent a wide range of objects associated with the vertices such as words, movie genres, and continuous features. To illustrate the concept of label types, Figure 1 depicts a fragment of a citation network. There are two label types. One representing the unique article identifiers and the other representing the identifiers of natural language words occurring in the articles.

The functions $\mathtt{l}_{i}:V\rightarrow 2^{L_{i}}$ map every vertex in the graph to a subset of the labels $L_{i}$ of label type $i$. We write $\mathtt{l}(v)=\bigcup_{i}\mathtt{l}_{i}(v)$ for the set of all labels associated with vertex $v$. Moreover, we write $\mathtt{l}_{i}(\mathbf{N}(v))=\{{\mathtt{l}_{i}(u)}\mid u\in\mathbf{N}(v)\}$ for the multiset of labels of type $i$ associated with the neighbors of vertex $v$.

We begin by describing the general learning framework of Ep which proceeds in two steps.

Second, EP computes a vector representation for each vertex $v$ from the vector representations of $v$’s labels. We write $\mathbf{v}$ for the current vector representation of a vertex $v$.

The first learning procedure is driven by the following objectives for each label type $i\in\{1,...,k\}$

where $\mathtt{d}_{i}$ is some measure of distance between $\mathbf{h}_{i}(v)$, the current representation of label type $i$ for vertex $v$, and its reconstruction $\widetilde{\mathbf{h}}_{i}(v)$. Hence, the objective of the approach is to learn the parameters of the functions $\mathtt{g}_{i}$ and $\widetilde{\mathtt{g}}_{i}$ (if such parameters exist) and the vector representations of the labels such that the output of $\widetilde{\mathtt{g}}_{i}$ applied to the type $i$ label embeddings of $v$’s neighbors is close to the output of $\mathtt{g}_{i}$ applied to the type $i$ label embeddings of $v$. For each vertex $v$ the messages passed to $v$ from its neighbors are the representations of their labels. The messages passed back to $v$’s neighbors are the gradients which are used to update the label embeddings. The gradients also update $v$’s label embeddings. Figure 2 illustrates the first part of the unsupervised learning framework for a part of a citation network. A representation is learned both for the article identifiers and the words occurring in the articles. The gradients are computed based on a loss between the reconstruction of the label type embeddings and their current values.

Due to the learning principle of Ep, nodes that do not have any labels for label type $i$ can be assigned a new dummy label unique to the node and the label type. The representations learned for these dummy labels can then be used as part of the representation of the node itself. Hence, Ep is also applicable in situations where data is missing and incomplete.

The embedding functions $\mathtt{f}_{i}$ can be initialized randomly or with an existing model. For instance, embedding functions for words can be initialized using word embedding algorithms and those for images with pretrained CNNs . Initialized parameters are then refined by the application of Ep. We can show empirically, however, that random initializations of the embedding functions $\mathtt{f}_{i}$ also lead to effective vertex embeddings.

We now introduce Ep-B, an instance of the Ep framework that we have found to be highly effective for several of the typical graph-based learning problems. The instance results from setting $\mathtt{g}_{i}(\mathbf{H})=\widetilde{\mathtt{g}}_{i}(\mathbf{H})=\frac{1}{|\mathbf{H}|}\sum_{\mathbf{h}\in\mathbf{H}}\mathbf{h}$ for all label types $i$ and all sets of embedding vectors $\mathbf{H}$. In this case we have, for any vertex $v$ and any label type $i$,

In conjunction with the above functions $\mathtt{g}_{i}$ and $\widetilde{\mathtt{g}}_{i}$, we can use the margin-based ranking loss Directly minimizing Equation (1) could lead to degenerate solutions.

where $\mathtt{d}_{i}$ is the Euclidean distance, $[x]_{+}$ is the positive part of $x$, and $\gamma>0$ is a margin hyperparameter. Hence, the objective is to make the distance between $\widetilde{\mathbf{h}}_{i}(v)$, the reconstructed embedding of label type $i$ for vertex $v$, and $\mathbf{h}_{i}(v)$, the current embedding of label type $i$ for vertex $v$, smaller than the distance between $\widetilde{\mathbf{h}}_{i}(v)$ and $\mathbf{h}_{i}(u)$, the embedding of label type $i$ of a vertex $u$ different from $v$. We solve the minimization problem with gradient descent algorithms and use one node $u$ for every $v$ in each learning iteration. Despite using only first-order proximity information in the reconstruction of the label embeddings, this learning is effectively propagating embedding information across the graph: an update of a label embedding affects neighboring label embeddings which, in other updates, affects their neighboring label embeddings, and so on; hence the name of this learning framework.

Finally, a simple instance of the function $\mathtt{r}$ is a function that concatenates all the embeddings $\mathbf{h}_{i}(v)$ for $i\in\{1,...,k\}$ to form one single vector representation $\mathbf{v}$ for each node $v$

Figure 3 illustrates the working of this particular function $\mathtt{r}$. We refer to the instance of the learning framework based on the formulas (2),(3), and (4) as Ep-B. The resulting vector representation of the vertices can now be used for downstream learning problems such as vertex classification, link prediction, and so on.

Formal Analysis

We now analyze the computation and model complexities of the Ep framework and its connection to existing models.

Let $G=(V,E)$ be a graph (either directed or undirected) with $k$ label types $\mathbf{L}=\{L_{1},...,L_{k}\}$. Moreover, let $\mathtt{lab}_{\max}=\max_{v\in V,i\in\{1,...,k\}}|\mathtt{l}_{i}(v)|$ be the maximum number of labels for any type and any vertex of the input graph, let $\mathtt{deg}_{\max}=\max_{v\in V}|\mathbf{N}(v)|$ be the maximum degree of the input graph, and let $\tau(n)$ be the worst-case complexity of computing any of the functions $\mathtt{g}_{i}$ and $\widetilde{\mathtt{g}}_{i}$ on $n$ input vectors of size $d_{i}$. Now, the worst-case complexity of one learning iteration is

For an input graph without attributes, that is, where the only label type represents node identities, the worst-case complexity of one learning iteration is $\mathcal{O}(|V|\tau(\mathtt{deg}_{\max}))$. If, in addition, the complexity of the single reconstruction function is linear in the number of input vectors, the complexity is $\mathcal{O}(|V|\mathtt{deg}_{\max})$ and, hence, linear in both the number of nodes and the maximum degree of the input graph. This is the case for most aggregation functions and, in particular, for the functions $\widetilde{\mathtt{g}}_{i}$ and $\mathtt{g}_{i}$ used in Ep-B, the particular instance of the learning framework defined by the formulas (2),(3), and (4). Furthermore, the average complexity is linear in the average node degree of the input graph. The worst-case complexity of Ep can be limited by not exchanging messages from all neighbors but only a sampled subset of size at most $\kappa$. We explore different sampling scenarios in the experimental section.

In general, the number of parameters and hyperparameters of the learning framework depends on the parameters of the functions $\mathtt{g}_{i}$ and $\widetilde{\mathtt{g}}_{i}$, the loss functions, and the number of distinct labels of the input graph. For graphs without attributes, the only parameters of Ep-B are the embedding weights and the only hyperparameters are the size of the embedding $d$ and the margin $\gamma$. Hence, the number of parameters is $d|V|$ and the number of hyperparameters is $2$. Table 2 lists the parameter counts for a set of state of the art methods for learning embeddings for graphs without attributes.

2 Comparison to Existing Models

Ep-B is related to locally linear embeddings (LLE) . In LLE there is a single function $\widetilde{\mathtt{g}}$ which computes a linear combination of the vertex embeddings. $\widetilde{\mathtt{g}}$’s weights are learned for each vertex in a separate previous step. Hence, unlike Ep-B, $\widetilde{\mathtt{g}}$ does not compute the unweighted average of the input embeddings. Moreover, LLE does not learn embeddings for the labels (attribute values) but directly for vertices of the input graph. Finally, LLE is only feasible for graphs where each node has at most a small constant number of neighbors. LLE imposes additional constraints to avoid degenerate solutions to the objective and solves the resulting optimization problem in closed form. This is not feasible for large graphs.

In several applications, the nodes of the graphs are associated with a set of words. For instance, in citation networks, the nodes which represent individual articles can be associated with a bag of words. Every label corresponds to one of the words. Figure 1 illustrates a part of such a citation network. In this context, Ep-B’s learning of word embeddings is related to the CBoW model . The difference is that for Ep-B the context of a word is determined by the neighborhood of the vertices it is associated with and it is the embedding of the word that is reconstructed and not its one-hot encoding.

For graphs with several different edge types such as multi-relational graphs, the reconstruction functions $\widetilde{\mathtt{g}}_{i}$ can be made dependent on the type of the edge. For instance, one could have, for any vertex $v$ and label type $i$,

where $\mathbf{r}_{(u,v)}$ is the vector representation corresponding to the type of the edge (the relation) from vertex $u$ to vertex $v$, and $\mathbf{h}_{i}(v)$ could be the average embedding of $v$’s node id labels. In combination with the margin-based ranking loss (3), this is related to embedding models for multi-relational graphs such as TransE .

Experiments

The objectives of the experiments are threefold. First, we compare Ep-B to the state of the art on node classification problems. Second, we visualize the learned representations. Third, we investigate the impact of an upper bound on the number of neighbors that are sending messages.

We evaluate Ep with the following six commonly used benchmark data sets. BlogCatalog is a graph representing the social relationships of the bloggers listed on the BlogCatalog website. The class labels represent user interests. PPI is a subgraph of the protein-protein interactions for Homo Sapiens. The class labels represent biological states. POS is a co-occurrence network of words appearing in the first million bytes of the Wikipedia dump. The class labels represent the Part-of-Speech (POS) tags. Cora, Citeseer and Pubmed are citation networks where nodes represent documents and their corresponding bag-of-words and links represent citations. The class labels represents the main topic of the document. Whereas BlogCatalog, PPI and POS are multi-label classification problems, Cora, Citeseer and Pubmed have exactly one class label per node. Some statistics of these data sets are summarized in Table 2.

The input to the node classification problem is a graph (with or without node attributes) where a fraction of the nodes is assigned a class label. The output is an assignment of class labels to the test nodes. Using the node classification data sets, we compare the performance of Ep-B to the state of the art approaches DeepWalk , Line , Node2vec , Planetoid , GCN , and also to the baselines wvRN and Majority. wvRN is a weighted relational classifier that estimates the class label of a node with a weigthed mean of its neighbors’ class labels. Since all the input graphs are unweighted, wvRN assigns the class label to a node $v$ that appears most frequently in $v$’s neighborhood. Majority always chooses the most frequent class labels in the training set.

For all data sets and all label types the functions $\mathtt{f}_{i}$ are always linear embeddings equivalent to an embedding lookup table. The dimension of the embeddings is always fixed to 128. We used this dimension for all methods which is in line with previous work such as DeepWalk and Node2vec for the data sets under consideration. For Ep-B, we chose the margin $\gamma$ in (3) from the set of values $$on validation data. For all approaches except Line, we used the hyperparameter values reported in previous work since these values were tuned to the data sets. As Line has not been applied to the data sets before, we set its number of samples to$20$million and negative samples to$5$. This means that Line is trained on (at least) an order of magnitude more examples than all other methods. We did not simply copy results from previous work but used the authors’ code to run all experiments again. For DeepWalk we used the implementation provided by the authors of Node2vec (setting$p=1.0$and$q=1.0$). We also used the other hyperparameters values for DeepWalk reported in the Node2vec paper to ensure a fair comparison. We did 10 runs for each method in each of the experimental set-ups described in this section, and computed the mean and standard deviation of the corresponding evaluation metrics. We use the same sets of training, validation and test data for each method. All methods were evaluated in the transductive and inductive setting. The transductive setting is the setting where all nodes of the input graph are present during training. In the inductive setting, a certain percentage of the nodes are not part of the graph during unsupervised learning. Instead, these removed nodes are added after the training has concluded. The results computed for the nodes not present during unsupervised training reflect the methods ability to incorporate newly added nodes without retraining the model.

For the graphs without attributes (BlogCatalog, PPI and POS) we follow the exact same experimental procedure as in previous work . First, the node embeddings were computed in an unsupervised fashion. Second, we sampled a fraction $T_{r}$ of nodes uniformly at random and used their embeddings and class labels as training data for a logistic regression classifier. The embeddings and class labels of the remaining nodes were used as test data. Ep-B’s margin hyperparameter $\gamma$ was chosen by 3-fold cross validation for $T_{r}=0.1$ once. The resulting margin $\gamma$ was used for the same data set and for all other values of $T_{r}$. For each method, we use 3-fold cross validation to determine the L2 regularization parameter for the logistic regression classifier from the values $[0.01,0.1,0.5,1,5,10]$. We did this for each value of $T_{r}$ and the F1 macro and F1 micro scores separately. This proved to be important since the L2 regularization had a considerable impact on the performance of the methods.

For the graphs with attributes (Cora, Citeseer, Pubmed) we follow the same experimental procedure as in previous work . We sample $20$ nodes uniformly at random for each class as training data, $1000$ nodes as test data, and a different $1000$ nodes as validation data. In the transductive setting, unsupervised training was performed on the entire graph. In the inductive setting, the $1000$ test nodes were removed from the graph before training. The hyperparameter values of GCN for these same data sets in the transductive setting are reported in ; we used these values for both the transductive and inductive setting. For Ep-B, Line and DeepWalk, the learned node embeddings for the $20$ nodes per class label were fed to a one-vs-rest logistic regression classifier with L2 regularization. We chose the best value for Ep-B’s margins and the L2 regularizer on the validation set from the values $[0.01,0.1,0.5,1,5,10]$. The same was done for the baselines DW+BoW and BoW Feat. Since Planetoid jointly optimizes an unsupervised and supervised loss, we applied the learned models directly to classify the nodes. The authors of Planetoid did not report the number of learning iterations, so we ensured the training had converged. This was the case after $5000$, $5000$, and $20000$ training steps for Cora, Citeseer, and Pubmed, respectively. For Ep-B we used Adam to learn the parameters in a mini-batch setting with a learning rate of $0.001$. A single learning epoch iterates through all nodes of the input graph and we fixed the number of epochs to $200$ and the mini-batch size to $64$. In all cases, the parameteres were initilized following and the learning always converged. Ep was implemented with the Theano wrapper Keras . We used the logistic regression classifier from LibLinear . All experiments were run on commodity hardware with 128GB RAM, a single 2.8 GHz CPU, and a TitanX GPU.

2 Results

The results for BlogCatalog, POS and PPI in the transductive setting are listed in Table 4. The best results are always indicated in bold. We observe that Ep-B tends to have the best F1 scores, with the additional aforementioned advantage of fewer parameters and hyperparameters to tune. Even though we use the hyperparameter values reported in Node2vec, we do not observe significant differences to DeepWalk. This is contrary to earlier findings . We conjecture that validating the L2 regularization of the logistic regression classifier is crucial and might not have been performed in some earlier work. The F1 scores of Ep-B, DeepWalk, Line, and Node2vec are significantly higher than those of the baselines wvRN and Majority. The results for the same data sets in the inductive setting are listed in Table 4 for different percentages of nodes removed before unsupervised training. Ep reconstructs label embeddings from the embeddings of labels of neighboring nodes. Hence, with Ep-B we can directly use the concatenation of the reconstructed embedding $\widetilde{\mathbf{h}}_{i}(v)$ as the node embedding for each of the nodes $v$ that were not part of the graph during training. For DeepWalk and Line we computed the embeddings of those nodes that were removed during training by averaging the embeddings of neighboring nodes; we indicate this by the suffix I. Ep-B outperforms all these methods in the inductive setting.

The results for the data sets Cora, Citeseer and Pubmed are listed in Table 5. Since these data sets have bag of words associated with nodes, we include the baseline method DW+BoW. DW+BoW concatenates the embedding of a node learned by DeepWalk with a vector that encodes the bag of words of the node. Planetoid-T and Planetoid-I are the transductive and inductive formulation of Planetoid . GCN-I is an inductive variant of GCN where edges from training to test nodes are removed from the graph but those from test nodes to training nodes are not. Contrary to other methods, Ep-B’s F1 scores on the transductive and inductive setting are very similar, demonstrating its suitability for the inductive setting. DeepWalk cannot make use of the word labels but we included it in the evaluation to investigate to what extent the word labels improve the performance of the other methods. The baseline Bow Feat trains a logistic regression classifier on the binary vectors encoding the bag of words of each node. Ep-B significantly outperforms all existing approaches in both the transductive and inductive setting on all three data sets with one exception: for the transductive setting on Cora GCN achieves a higher accuracy. Both Planetoid-T and DW+BoW do not take full advantage of the information given by the bag of words, since the encoding of the bag of words is only exposed to the respective models for nodes with class labels and, therefore, only for a small fraction of nodes in the graph. This could also explain Planetoid-T’s high standard deviation since some nodes might be associated with words that occur in the test data but which might not have been encountered during training. This would lead to misclassifications of these nodes.

Figure 4 depicts a visualization of the learned embeddings for the Cora citation network by applying t-sne to the 128-dimensional embeddings generated by Ep-B. Both qualitatively and quantitatively – as demonstrated by the Silhouette score that measures clustering quality – it shows Ep-B’s ability to learn and combine embeddings of several label types.

Up until now, we did not take into account the direction of the edges, that is, we treated all graphs as undirected. Citation networks, however, are intrinsically directed. The right part of Table 5 shows the performance of Ep-B and DeepWalk when the edge directions are considered. For Ep this means label representations are only sent along the directed edges. For DeepWalk this means that the generated random walks are directed walks. While we observe a significant performance deterioration for DeepWalk, the accuracy of Ep-B does not change significantly. This demonstrates that Ep is also applicable when edge directions are taken into account.

For densely connected graphs with a high average node degree, it is beneficial to limit the number of neighbors that send label representations in each learning step. This can be accomplished by sampling a subset of at most size $\kappa$ from the set of all neighbors and to send messages only from the sampled nodes. We evaluated the impact of this strategy by varying the parameter $\kappa$ in Figure 4. The loss is significantly higher for smaller values of $\kappa$. For $\kappa=50$, however, the average loss is almost identical to the case where all neighbors send messages while reducing the training time per epoch by an order of magnitude (from $20$s per epoch to less than $1$s per epoch).

Conclusion and Future Work

Embedding Propagation (Ep) is an unsupervised machine learning framework for graph-structured data. It learns label and node representations by exchanging messages between nodes. It supports arbitrary label types such as node identities, text, movie genres, and generalizes several existing approaches to graph representation learning. We have shown that Ep-B, a simple instance of Ep, is competitive with and often outperforms state of the art methods while having fewer parameters and/or hyperparameters. We believe that Ep’s crucial advantage over existing methods is its ability to learn label type representations and to combine these label type representations into a joint vertex embedding.

Direction of future research include the combination of Ep with multitask learning, that is, learning the embeddings of labels and nodes guided by both an unsupervised loss and a supervised loss defined with respect to different tasks; a variant of Ep that incorporates image and sequence data; and the integration of Ep with an existing distributed graph processing framework. One might also want to investigate the application of the Ep framework to multi-relational graphs.

References