Machine Learning on Graphs: A Model and Comprehensive Taxonomy

Introduction

Learning representations for complex structured data is a challenging task. In the last decade, many successful models have been developed for certain kinds of structured data, including data defined on a discretized Euclidean domain. For instance, sequential data, such as text or videos, can be modelled via recurrent neural networks, which can capture sequential information, yielding efficient representations as measured on machine translation and speech recognition tasks. Another example is convolutional neural networks (CNNs), which parameterize neural networks according to structural priors such as shift-invariance, and have achieved unprecedented performance in pattern recognition tasks such as image classification or speech recognition. These major successes have been restricted to particular types of data that have a simple relational structure (e.g. sequential data, or data following regular patterns).

In many settings, data is not nearly as regular: complex relational structures commonly arise, and extracting information from that structure is key to understanding how objects interact with each other. Graphs are a universal data structures that can represent complex relational data (composed of nodes and edges), and appear in multiple domains such as social networks, computational chemistry , biology , recommendation systems , semi-supervised learning , and others. For graph-structured data, it is challenging to define networks with strong structural priors, as structures can be arbitrary, and can vary significantly across different graphs and even different nodes within the same graph. In particular, operations like convolutions cannot be directly applied on irregular graph domains. For instance in images, each pixel has the same neighborhood structure, allowing to apply the same filter weights at multiple locations in the image. However in graphs, one can’t define an ordering of node since each node might have a different neighborhood structure (Fig. 1). Furthermore, Euclidean convolutions strongly rely on geometric priors (e.g. shift invariance) which don’t generalize to non-Euclidean domains (e.g. translations might not even be defined on non-Euclidean domains).

These challenges led to the development of Geometric Deep Learning (GDL) research which aims at applying deep learning techniques to non-Euclidean data. In particular, given the widespread prevalence of graphs in real-world applications, there has been a surge of interest in applying machine learning methods to graph-structured data. Among these, Graph Representation Learning (GRL) methods aim at learning low-dimensional continuous vector representations for graph-structured data, also called embeddings.

Broadly speaking, GRL can be divided into two classes of learning problems, unsupervised and supervised (or semi-supervised) GRL. The first family aims at learning low-dimensional Euclidean representations that preserve the structure of an input graph. The second family also learns low-dimensional Euclidean representations but for a specific downstream prediction task such as node or graph classification. Different from the unsupervised setting where inputs are usually graph structures, inputs in supervised settings are usually composed of different signals defined on graphs, commonly known as node features. Additionally, the underlying discrete graph domain can be fixed, which is the transductive learning setting (e.g. predicting user properties in a large social network), but can also vary in the inductive learning setting (e.g. predicting molecules attribute where each molecule is a graph). Finally, note that while most supervised and unsupervised methods learn representations in Euclidean vector spaces, there recently has been interest for non-Euclidean representation learning, which aims at learning non-Euclidean embedding spaces such as hyperbolic or spherical spaces. The main motivations for this body of work is to use a continuous embedding space that resembles the underlying discrete structure of the input data it tries to embed (e.g. the hyperbolic space is a continuous version of trees ).

Given the impressive pace at which the field of GRL is growing, we believe it is important to summarize and describe all methods in one unified and comprehensible framework. The goal of this survey is to provide a unified view of representation learning methods for graph-structured data, to better understand the different ways to leverage graph structure in deep learning models.

A number of graph representation learning surveys exist. First, there exist several surveys that cover shallow network embedding and auto-encoding techniques and we refer to for a detailed overview of these methods. Second, Bronstein et al. also gives an extensive overview of deep learning models for non-Euclidean data such as graphs or manifolds. Third, there have been several recent surveys covering methods applying deep learning to graphs, including graph neural networks. Most of these surveys focus on a specific sub-field of graph representation learning and do not draw connections between each sub-field.

In this work, we extend the encoder-decoder framework proposed by Hamilton et al. and introduce a general framework, the Graph Encoder Decoder Model (GraphEDM), which allows us to group existing work into four major categories: (i) shallow embedding methods, (ii) auto-encoding methods, (iii) graph regularization methods, and (iv) graph neural networks (GNNs). Additionally, we introduce a Graph Convolution Framework (GCF), specifically designed to describe convolution-based GNNs, which have achieved state-of-the art performance in a broad range of applications. This allows us to analyze and compare a variety of GNNs, ranging in construction from methods operating in the Graph FourierAs defined by the eigenspace of the graph Laplacian. domain to methods applying self-attention as a neighborhood aggregation function . We hope that this unified formalization of recent work would help the reader gain insights into the various learning methods on graphs to reason about similarities, differences, and point out potential extensions and limitations. That said, our contribution with regards to previous surveys are threefold:

We introduce a general framework, GraphEDM, to describe a broad range of supervised and unsupervised methods that operate on graph-structured data, namely shallow embedding methods, graph regularization methods, graph auto-encoding methods and graph neural networks.

Our survey is the first attempt to unify and view these different lines of work from the same perspective, and we provide a general taxonomy (Fig. 3) to understand differences and similarities between these methods. In particular, this taxonomy encapsulates over thirty existing GRL methods. Describing these methods within a comprehensive taxonomy gives insight to exactly how these methods differ.

We release an open-source library for GRL which includes state-of-the-art GRL methods and important graph applications, including node classification and link prediction. Our implementation is publicly available at https://github.com/google/gcnn-survey-paper.

We first review basic graph definitions and clearly state the problem setting for GRL (Section 2). In particular, we define and discuss the differences between important concepts in GRL, including the role of node features in GRL and how they relate to supervised GRL (Section 2.2.1), the distinctions between inductive and transductive learning (Section 2.2.2), positional and structural embeddings (Section 2.2.3) and the differences between supervised and unsupervised embeddings (Section 2.2.4). We then introduce GraphEDM (Section 3) a general framework to describe both supervised and unsupervised GRL methods, with or without the presence of node features, which can be applied in both inductive and transductive learning settings. Based on GraphEDM, we introduce a general taxonomy of GRL methods (Fig. 3) which encapsulates over thirty recent GRL models, and we describe both unsupervised (Section 4) and supervised (Section 5) methods using this taxonomy. Finally, we survey graph applications (Section 6).

Preliminaries

Here we introduce the notation used throughout this article (see Table 1 for a summary), and the generalized network embedding problem which graph representation learning methods aim to solve.

(Graph). A graph $G$ given as a pair: ${G}=(V,E)$, comprises a set of vertices (or nodes) $V=\{v_{1},\dots,v_{|V|}\}$ connected by edges $E=\{e_{1},\ldots,e_{|E|}\}$, where each edge $e_{k}$ is a pair $(v_{i},v_{j})$ with $v_{i},v_{j}\in V$. A graph is weighted if there exist a weight function: $w:(v_{i},v_{j})\rightarrow w_{ij}$ that assigns weight $w_{ij}$ to edge connecting nodes $v_{i},v_{j}\in V$. Otherwise, we say that the graph is unweighted. A graph is undirected if $(v_{i},v_{j})\in E$ implies $(v_{j},v_{i})\in E$, i.e. the relationships are symmetric, and directed if the existence of edge $(v_{i},v_{j})\in E$ does not necessarily imply $(v_{j},v_{i})\in E$. Finally, a graph can be homogeneous if nodes refer to one type of entity and edges to one relationship. It can be heterogeneous if it contains different types of nodes and edges.

For instance, social networks are homogeneous graphs that can be undirected (e.g. to encode symmetric relations like friendship) or directed (e.g. to encode the relation following); weighted (e.g. co-activities) or unweighted.

(Path). A path $P$ is a sequence of edges $(u_{i_{1}},u_{i_{2}}),(u_{i_{2}},u_{i_{3}}),\ldots,(u_{i_{k}},u_{i_{k+1}})$ of length $k$. A path is called simple if all $u_{i_{j}}$ are distinct from each other. Otherwise, if a path visits a node more than once, it is said to contain a cycle.

(Distance). Given two nodes $(u,v)$ in a graph $G$, we define the distance from $u$ to $v$, denoted $d_{G}(u,v)$, to be the length of the shortest path from $u$ to $v$, or $\infty$ if there exist no path from $u$ to $v$.

The graph distance between two nodes is the analog of geodesic lengths on manifolds.

The name random walk comes from the fact that $D^{-1}W$ is a stochastic transition matrix that can be interpreted as the transition probability matrix of a random walk on the graph. The graph Laplacian is a key operator on graphs and can be interpreted as the analogue of the continuous Laplace-Beltrami operator on manifolds. Its eigenspace capture important properties about a graph (e.g. cut information often used for spectral graph clustering) but can also serve as a basis for smooth functions defined on the graph for semi-supervised learning . The graph Laplacian is also closely related to the heat equation on graphs as it is the generator of diffusion processes on graphs and can be used to derive algorithms for semi-supervised learning on graphs .

(First order proximity). The first order proximity between two nodes $v_{i}$ and $v_{j}$ is a local similarity measure indicated by the edge weight $w_{ij}$. In other words, the first-order proximity captures the strength of an edge between node $v_{i}$ and node $v_{j}$ (should it exist).

(Second-order proximity). The second order proximity between two nodes $v_{i}$ and $v_{j}$ is measures the similarity of their neighborhood structures. Two nodes in a network will have a high second-order proximity if they tend to share many neighbors.

Note that there exist higher-order measures of proximity between nodes such as Katz Index, Adamic Adar or Rooted PageRank . These notions of node proximity are particularly important in network embedding as many algorithms are optimized to preserve some order of node proximity in the graph.

2 The generalized network embedding problem

In other scenarios, node features might be unavailable or not useful for a given task: network embedding can be featureless. That is, the goal is to learn graph representations via mappings:

Note that depending on whether node features are used or not in the embedding algorithm, the learned representation could capture different aspects about the graph. If nodes features are being used, embeddings could capture both structural and semantic graph information. On the other hand, if node features are not being used, embeddings will only preserve structural information of the graph.

Finally, note that edge features are less common than node features in practice, but can also be used by embedding algorithms. For instance, edge features can be used as regularization for node embeddings , or to compute messages from neighbors as in message passing networks .

2.2 Transductive and inductive network embedding

Historically, a popular way of categorizing a network embedding method has been by whether the model can generalize to unseen data instances – methods are referred to as operating in either a transductive or inductive setting . While we do not use this concept for constructing our taxonomy, we include a brief discussion here for completeness.

In transductive settings, it assumed that all nodes in the graph are observed in training (typically the nodes all come from one fixed graph). These methods are used to infer information about or between observed nodes in the graph (e.g. predicting labels for all nodes, given a partial labeling). For instance, if a transductive method is used to embed the nodes of a social network, it can be used to suggest new edges (e.g. friendships) between the nodes of the graph. One major limitation of models learned in transductive settings is that they fail to generalize to new nodes (e.g. evolving graphs) or new graph instances.

On the other hand, in inductive settings, models are expected to generalize to new nodes, edges, or graphs that were not observed during training. Formally, given training graphs $(G_{1},\ldots,G_{k})$, the goal is to learn a mapping to continuous representations that can generalize to unseen test graphs $(G_{k+1},\ldots,G_{k+l})$. For instance, inductive learning can be used to embed molecular graphs, each representing a molecule structure , generalizing to new graphs and showing error margins within chemical accuracy on many quantum properties. Embedding dynamic or temporally evolving graphs is also another inductive graph embedding problem.

There is a strong connection between inductive graph embedding and node features (Section 2.2.1) as the latter are usually necessary for most inductive graph representation learning algorithms. More concretely, node features can be leveraged to learn embeddings with parametric mappings and instead of directly optimizing the embeddings, one can optimize the mapping’s parameters. The learned mapping can then be applied to any node (even those that were not present a training time). On the other hand, when node features are not available, the first mapping from nodes to embeddings is usually a one-hot encoding which fails to generalize to new graphs where the canonical node ordering is not available.

Finally, we note that this categorization of graph embedding methods is at best an incomplete lens for viewing the landscape. While some models are inherently better suited to different tasks in practice, recent theoretical results show that models previously assumed to be capable of only one setting (e.g. only transductive) can be used in both.

2.3 Positional vs structural network embedding

An emerging categorization of graph embedding algorithms is about whether the learned embeddings are positional or structural. Position-aware embeddings capture global relative positions of nodes in a graph and it is common to refer to embeddings as positional if they can be used to approximately reconstruct the edges in the graph, preserving distances such as shortest paths in the original graph . Examples of positional embedding algorithms include random walk or matrix factorization methods. On the other hand, structure-aware embeddings capture local structural information about nodes in a graph, i.e. nodes with similar node features or similar structural roles in a network should have similar embeddings, regardless of how far they are in the original graph. For instance, GNNs usually learn embeddings by incorporating information for each node’s neighborhood, and the learned representations are thus structure-aware.

In the past, positional embeddings have commonly been used for unsupervised tasks where positional information is valuable (e.g. link prediction or clustering) while structural embeddings have been used for supervised tasks (e.g. node classification or whole graph classification). More recently, there has been attempts to bridge the gap between positional and structural representations, with positional GNNs and theoretical frameworks showing the equivalence between the two classes of embeddings .

2.4 Unsupervised and supervised network embedding

Network embedding can be unsupervised in the sense that the only information available is the graph structure (and possibly node features) or supervised, if additional information such as node or graph labels is provided. In unsupervised network embedding, the goal is to learn embeddings that preserved the graph structure and this is usually achieved by optimizing some reconstruction loss, which measures how well the learned embeddings can approximate the original graph. In supervised network embedding, the goal is to learn embeddings for a specific purpose such as predicting node or graph attributes, and models are optimized for a specific task such as graph classification or node classification. We use the level of supervision to build our taxonomy and cover differences between supervised and unsupervised methods in more details in Section 3.

A Taxonomy of Graph Embedding Models

We first describe our proposed framework, GraphEDM, a general framework for GRL (Section 3.1). In particular, GraphEDM is general enough that it can be used to succinctly describe over thirty GRL methods (both unsupervised and supervised). We use GraphEDM to introduce a comprehensive taxonomy in Section 3.2 and Section 3.3, which summarizes exiting works with shared notations and simple block diagrams, making it easier to understand similarities and differences between GRL methods.

The GraphEDM framework builds on top of the work of Hamilton et al. , which describes unsupervised network embedding methods from an encoder-decoder perspective. Cruz et al. also recently proposed a modular encoder-based framework to describe and compare unsupervised graph embedding methods. Different from these unsupervised frameworks, we provide a more general framework which additionally encapsulates supervised graph embedding methods, including ones utilizing the graph as a regularizer (e.g. ), and graph neural networks such as ones based on message passing or graph convolutions .

The GraphEDM framework can be decomposed as follows:

As we shall see next, this node embedding matrix might capture different graph properties depending on the supervision used for training.

Our GraphEDM framework is general (see Fig. 2 for an illustration). Specific choices of the aforementioned (encoder and decoder) networks allows GraphEDM to realize specific graph embedding methods. Before presenting the taxonomy and showing realizations of various methods using our framework, we briefly discuss an application perspective.

The GraphEDM model can return a reconstructed graph similarity or dissimilarity matrix $\widehat{W}$ (often used to train unsupervised embedding algorithms), as well as a output labels $\widehat{y}^{S}$ for supervised applications. The label output space $\mathcal{Y}$ varies depending on the supervised application.

Node-level supervision, with $\widehat{y}^{N}\in\mathcal{Y}^{|V|}$, where $\mathcal{Y}$ represents the node label space. If $\mathcal{Y}$ is categorical, then this is also known as (semi-)supervised node classification (Section 6.2.1), in which case the label decoder network produces labels for each node in the graph. If the embedding dimensions $d$ is such that $d=|\mathcal{Y}|$, then the label decoder network can be just a simple softmax activation across the rows of $Z$, producing a distribution over labels for each node. Additionally, the graph decoder network might also be used in supervised node-classification tasks, as it can be used to regularize embeddings (e.g. neighbor nodes should have nearby embeddings, regardless of node labels).

Edge-level supervision, with $\widehat{y}^{E}\in\mathcal{Y}^{|V|\times|V|}$, where $\mathcal{Y}$ represents the edge label space. For example, $\mathcal{Y}$ can be multinomial in knowledge graphs (for describing the types of relationships between two entities), setting $\mathcal{Y}=\{0,1\}^{\textrm{\#(relation types)}}$. It is common to have $\textrm{\#(relation types)}=1$, and this is is known as link prediction, where edge relations are binary. In this review, when $\widehat{y}^{E}=\{0,1\}^{|V|\times|V|}$ (i.e. $\mathcal{Y}=\{0,1\}$), then rather than naming the output of the decoder as $\widehat{y}^{E}$, we instead follow the nomenclature and position link prediction as an unsupervised task (Section 4). Then in lieu of $\widehat{y}^{E}$ we utilize $\widehat{W}$, the output of the graph decoder network (which is learned to reconstruct a target similarity or dissimilarity matrix) to rank potential edges.

Graph-level supervision, with $\widehat{y}^{G}\in\mathcal{Y}$, where $\mathcal{Y}$ is the graph label space. In the graph classification task (Section 6.2.2), the label decoder network converts node embeddings into a single graph labels, using graph pooling via the graph edges captured by $W$. More concretely, the graph pooling operation is similar to pooling in standard CNNs, where the goal is to downsample local feature representations to capture higher-level information. However, unlike images, graphs don’t have a regular grid structure and it is hard to define a pooling pattern which could be applied to every node in the graph. A possible way of doing so is via graph coarsening, which groups similar nodes into clusters to produce smaller graphs . There exist other pooling methods on graphs such as DiffPool or SortPooling which creates an ordering of nodes based on their structural roles in the graph. Details about graph pooling operators is outside the scope of this work and we refer the reader to recent surveys for a more in-depth treatment.

2 Taxonomy of objective functions

We now focus our attention on the optimization of models that can be described in the GraphEDM framework by describing the loss functions used for training. Let $\Theta=\{\Theta^{E},\Theta^{D},\Theta^{S}\}$ denote all model parameters. GraphEDM models can be optimized using a combination of the following loss terms:

where $d_{1}(\cdot,\cdot)$ is a distance or dissimilarity function. Examples for such regularization are constraining neighboring nodes to share similar embeddings, in terms of their distance in L2 norm. We will cover more examples of regularization functions in Section 4 and Section 5.

Finally, models realizable by GraphEDM framework are trained by minimizing the total loss $\mathcal{L}$ defined as:

where $\alpha$, $\beta$ and $\gamma$ are hyper-parameters, that can be tuned or set to zero. Note that graph embedding methods can be trained in a supervised (${\alpha\neq 0}$) or unsupervised (${\alpha=0}$) fashion. Supervised graph embedding approaches leverage an additional source of information to learn embeddings such as node or graph labels. On the other hand, unsupervised network embedding approaches rely on the graph structure only to learn node embeddings.

A common approach to solve supervised embedding problems is to first learn embeddings with an unsupervised method (Section 4) and then train a supervised model on the learned embeddings. However, as pointed by Weston et al. and others, using a two-step learning algorithm might lead to sub-optimal performances for the supervised task, and in general, supervised methods (Section 5) outperform two-step approaches.

3 Taxonomy of encoders

Having introduced all the building blocks of the GraphEDM framework, we now introduce our graph embedding taxonomy. While most methods we describe next fall under the GraphEDM framework, they will significantly differ based on the encoder used to produce the node embeddings, and the loss function used to learn model parameters. We divide graph embedding models into four main categories:

Shallow embedding methods, where the encoder function is a simple embedding lookup. That is, the parameters of the model $\Theta^{E}$ are directly used as node embeddings:

Note that shallow embedding methods rely on an embedding lookup and are therefore transductive, i.e. they generally cannot be directly applied in inductive settings where the graph structure is not fixed.

Graph regularization methods, where the encoder network ignores the graph structure and only uses node features as input:

As its name suggests, graph regularization methods leverage the graph structure through the graph regularization loss term in Eq. 2 ($\beta\neq 0$) to regularize node embeddings.

Graph auto-encoding methods, where the encoder is a function of the graph structure only:

Neighborhood aggregation methods, including graph convolutional methods, where both the node features and the graph structure are used in the encoder network. Neighborhood aggregation methods use the graph structure to propagate information across nodes and learn embeddings that encode structural properties about the graph:

4 Historical Context

In most machine learning applications, models follow a rather simple two-step paradigm. First they automatically extract meaningful patterns from data, without the need for manual feature engineering. This is the so-called representation learning step . Second, they use these representations in downstream applications which can be supervised (e.g. classification) or unsupervised (e.g. clustering, visualization, nearest-neighbor search). This is the so-called downstream task.For supervised tasks, these two steps are often combined into one learning algorithm, which learns both representations and decision rules on top of these representations.

A good data representation should be expressive enough that it preserves meaningful features found in the original data, but simple enough that it makes the downstream task easier. For instance, having low-dimensional representations of high-dimensional datasets can help overcome issues caused by the curse of dimensionality such as overfitting. In the context of GRL, a graph encoder is used to learn representation, and a graph or label decoder is used for downstream tasks (e.g. node classification, link prediction). Historically, the graph encoder-decoder networks were used for manifold learning. When input data lies on a high-dimensional Euclidean space, it is common to assume it sits in an intrinsically low-dimensional manifold. This is known as the standard manifold hypothesis. Methods for manifold learning seek to recover this intrinsically low-dimensional manifold. This is usually done by first building a discrete approximation of the manifold using a graph in which nearby points in the ambient Euclidean space are connected by an edge. Because manifolds are locally Euclidean, graph distances provide a good proxy for both local and global manifold distances. The second step is to “flatten” this graph representation by learning a non-linear mapping from nodes in the graph to points in a low-dimensional Euclidean space, while preserving graph distances as best as possible. These representations are usually easier to work with than the original high-dimensional representations, and can then be used in downstream applications.

In the early 2000s, non-linearThe non-linearity term here comes to contrast with Euclidean dimensionality reduction methods (such as Principal Component Analysis) which rely on linear projections. dimensionality reduction methods were extremely popular to solve the manifold learning problem. For instance, Laplacian Eigenmaps (LE) use spectral techniques to compute embeddings, and IsoMap use a combination of the Floyd–Warshall algorithm and the classical Multi-dimensional scaling algorithm to preserve global graph geodesics. These methods rely on shallow encoders, and we describe some of these in Section 4.1.1.

While manifold dimensionality reduction methods have had critical impact in machine learning applications, they do not scale to large datasets. For instance, IsoMAP requires computing all pairs of shortest paths which takes more than quadratic time. A perhaps more important limitation is their inability to compute embeddings for new datapoints because the mappings from node to embeddings are non-parametric.

In more recent years, many non-shallow network architectures have been proposed for the problem of graph embedding. These include graph regularization networks and graph neural networks which can be described using our GraphEDM framework. Because they leverage the expressiveness of deep neural networks, GRL models often yield more expressive, scalable and generalizable embeddings than classical methods.

In the next sections, we review recent methods for supervised and unsupervised graph embedding techniques using GraphEDM and summarize the proposed taxonomy in Fig. 3.

Unsupervised Graph Embedding

We now give an overview of recent unsupervised graph embedding approaches using the taxonomy described in the previous section. These methods map a graph, its nodes, and/or its edges, onto a continuous vector space, without using task-specific labels for the graph or its nodes. Some of these methods optimize an objective to learn an embedding that preserves the graph structure e.g. by learning to reconstruct some node-to-node similarity or dissimilarity matrix, such as the adjacency matrix. Some of these methods apply a contrastive objective, e.g. contrasting close-by node-pairs versus distant node-pairs : nodes co-visited in short random walks should have a similarty score higher than distant ones; or contrasting real graphs versus fake ones : the mutual information between a graph and all of its nodes, should be higher in real graphs than in fake graphs.

Embeddings of nodes can be learned such that the structure of the data in the embedding space corresponds to the underlying graph structure. At a high level, this is similar to dimensionality reduction methods such as PCA, except that the input data might not have a linear structure. In particular, methods used for non-linear dimensionality reduction often start by building a discrete graph from the data (to approximate the manifold) and can be applied to graph embedding problems. Here, we analyze two major types of shallow graph embedding methods, namely distance-based and outer product-based methods.

These methods optimize embeddings such that points that are close in the graph (as measured by their graph distances for instance) stay as close as possible in the embedding space using a predefined distance function. Formally, the decoder network computes pairwise distance for some distance function $d_{2}(\cdot,\cdot)$, which can lead to Euclidean (Section 4.1.1) or non-Euclidean (Section 4.1.2) embeddings:

These methods on the other hand rely on pairwise dot-products to compute node similarities and the decoder network can be written as:

1.1 Distance-based: Euclidean methods

Most distance-based methods optimize Euclidean embeddings by minimizing Euclidean distances between similar nodes. Among these, we find linear embedding methods such as PCA or MDS, which learn low-dimensional linear projection subspaces, or nonlinear methods such as Laplacian eigenmaps, IsoMAP and Local linear embedding. Note that all these methods have originally been introduced for dimensionality reduction or visualization purposes, but can easily be extended to the context of graph embedding.

(MDS) refers to a set of embedding techniques used to map objects to positions while preserving the distances between these objects. In particular, metric MDS (mMDS) minimizes the regularization loss in Eq. 1 with $s(W)$ set to some distance matrix measuring the dissimilarity between objects (e.g. Euclidean distance between points in a high-dimensional space):

That is, mMDS finds an embedding configuration where distances in the low-dimensional embedding space are preserved by minimizing a residual sum of squares called the stress cost function. Note that if the dissimilarities are computed from Euclidean distances of a higher-dimensional representation, then mMDS is equivalent to the PCA dimensionality reduction method. Finally, there exist variants of this algorithm such as non-metric MDS, when the dissimilarity matrix $s(W)$ is not a distance matrix, or classical MDS (cMDS) which can be solved in closed form using a low-rank decomposition of the gram matrix.

(IsoMap) is an algorithm for non-linear dimensionality reduction which estimates the intrinsic geometry of a data lying on a manifold. This method is similar to MDS, except for a different choice of the distance matrix. IsoMap approximates manifold distances (in contrast with straight-line Euclidean geodesics) by first constructing a discrete neighborhood graph $G$, and then using the graph distances (length of shortest paths computed using Dijkstra’s algorithm for example) to approximate the manifold geodesic distances:

IsoMAP then uses the cMDS algorithm to compute representations that preserve these graph geodesic distances. Different from cMDS, IsoMAP works for distances that do not necessarily come from a Euclidean metric space (e.g. data defined on a Riemannian manifold). It is however computationally expensive due to the computation of all pairs of shortest path lengths in the neighborhood graph.

(LLE) is another non-linear dimensionality reduction technique which was introduced around the same time as IsoMap and improves over its computational complexity via sparse matrix operations. Different from IsoMAP which preserves the global geometry of manifolds via geodesics, LLE is based on the local geometry of manifolds and relies on the assumptions that when locally viewed, manifolds are approximately linear. The main idea behind LLE is to approximate each point using a linear combination of embeddings in its local neighborhood (linear patches). These local neighborhoods are then compared globally to find the best non-linear embedding.

(LE) is a non-linear dimensionality reduction methods that seeks to preserve local distances. Spectral properties of the graph Laplacian matrix capture important structural information about graphs. In particular, eigenvectors of the graph Laplacian provide a basis for smooth functions defined on the graph vertices (the “smoothest” function being the constant eigenvector corresponding to eigenvalue zero). LE is a non-linear dimensionality reduction technique which builds on this intuition. LE first constructs a graph from datapoints (e.g. k-NN graph or $\varepsilon$-neighborhood graph) and then represents nodes in the graphs via the Laplacian’s eigenvectors corresponding to smaller eigenvalues. The high-level intuition for LE is that points that are close on the manifold (or graph) will have similar representations, due to the “smoothness” of Laplacian’s eigenvectors with small eigenvalues. Formally, LE learns embeddings by solving the generalized eigenvector problem:

where the first constraint removes an arbitrary scaling factor in the embedding and the second one removes trivial solutions corresponding to the constant eigenvector (with eigenvalue zero for connected graphs). Further, note that $Z^{\top}L\ Z=\frac{1}{2}\sum_{ij}W_{ij}||Z_{i}-Z_{j}||_{2}^{2}$ and therefore the minimization objective can be equivalently written as a graph regularization term using our notations:

Therefore, LE learns embeddings such that the Euclidean distance in the embedding space is small for points that are close on the manifold.

1.2 Distance-based: Non-Euclidean methods

The distance-based methods described so far assumed embeddings are learned in a Euclidean space. Graphs are non-Euclidean discrete data structures, and several works proposed to learn graph embeddings into non-Euclidean spaces instead of conventional Euclidean space. Examples of such spaces include the hyperbolic space, which has a non-Euclidean geometry with a constant negative curvature and is well-suited to represent hierarchical data.

To give more intuition, the hyperbolic space can be thought of as continuous versions of trees, where geodesics (generalization of shortest paths on manifolds) resemble shortest paths in discrete trees. Further, the volume of balls grows exponentially with radius in hyperbolic space, similar to trees where the number of nodes within some distance to the root grows exponentially. In contrast, this volume growth is only polynomial in Euclidean space and therefore, the hyperbolic space has more “room” to fit complex hierarchies and compress representations. In particular, hyperbolic embeddings can embed trees with arbitrary low distortion in just two-dimensions whereas this is not possible in Euclidean space. This makes hyperbolic space a natural candidate to embed tree-like data and more generally, hyperbolic geometry offers an exciting alternative to Euclidean geometry for graphs that exhibit hierarchical structures, as it enables embeddings with much smaller distortion.

Before its use in machine learning applications, hyperbolic geometry has been extensively studied and used in network science research. Kleinberg proposed a greedy algorithm for geometric rooting, which maps nodes in sensor networks to coordinates on a hyperbolic plane via spanning trees, and then performs greedy geographic routing. Hyperbolic geometry has also been used to study the structural properties of complex networks (networks with non-trivial topological features used to model real-world systems). Krioukov et al. develop a geometric framework to construct scale-free networks (a family of complex networks with power-law degree distributions), and conversely show that any scale-free graph with some metric structure has an underlying hyperbolic geometry. Papadopoulos et al. introduce the Popularity-Similarity (PS) framework to model the evolution and growth of complex networks. In this model, new nodes are likely to be connected to popular nodes (modelled by their radial coordinates in hyperbolic space) as well as similar nodes (modelled by the angular coordinates). This framework has further been used to map nodes in graphs to hyperbolic coordinates, by maximising the likelihood that the network is produced by the PS model . Further works extend non-linear dimensionality reduction techniques such as LLE to efficiently map graphs to hyperbolic coordinates .

More recently, there has been interest in learning hyperbolic representations of hierarchical graphs or trees, via gradient-based optimization. We review some of these machine learning-based algorithms next.

Nickel and Kiela learn embeddings of hierarchical graphs such as lexical databases (e.g. WordNet) in the Poincaré model hyperbolic space. Using our notations, this approach learns hyperbolic embeddings via the Poincaré distance function:

Embeddings are then learned by minimizing distances between connected nodes while maximizing distances between disconnected nodes:

where the denominator is approximated using negative sampling. Note that since the hyperbolic space has a manifold structure, embeddings need to be optimized using Riemannian optimization techniques to ensure that they remain on the manifold.

Other variants of these methods have been proposed. In particular, Nickel and Kiela explore a different model of hyperbolic space, namely the Lorentz model (also known as the hyperboloid model), and show that it provides better numerical stability than the Poincaré model. Another line of work extends non-Euclidean embeddings to mixed-curvature product spaces , which provide more flexibility for other types of graphs (e.g. ring of trees). Finally, Chamberlain et al. extend Poincaré embeddings to incorporate skip-gram losses using hyperbolic inner products.

1.3 Outer product-based: Matrix factorization methods

Matrix factorization methods learn embeddings by minimizing the regularization loss in Eq. 1 with:

That is, $d_{1}(\cdot,\cdot)$ in Eq. 1 is the Frobenius norm between the reconstructed matrix and the target similarity matrix. By minimizing the regularization loss, graph factorization methods learn low-rank representations that preserve structural information as defined by the similarity matrix $s(W)$. We now review important matrix factorization methods.

(GF) learns a low-rank factorization for the adjacency matrix by minimizing graph regularization loss in Eq. 1 using:

Recall that $A$ is binary adjacency matrix, with $A_{ij}=1$ iif $(v_{i},v_{j})\in E$. We can express the graph regularization loss in terms of Frobenius norm:

where $\cdot$ is the element-wise matrix multiplication operator. Therefore, GF also learns a low-rank factorization of the adjacency matrix $W$ measured in Frobenuis norm. Note that the sum is only over existing edges in the graph, which reduces the computational complexity of this method from $O(|V|^{2})$ to $O(|E|)$.

(GraRep) The methods described so far are all symmetric, that is, the similarity score between two nodes $(v_{i},v_{j})$ is the same a the score of $(v_{j},v_{i})$. This might be a limiting assumption when working with directed graphs as some nodes can be strongly connected in one direction and disconnected in the other direction. GraRep overcomes this limitation by learning two embeddings per node, a source embedding $Z^{s}$ and a target embedding $Z^{t}$, which capture asymmetric proximity in directed networks. GraRep learns embeddings that preserve $k$-hop neighborhoods via powers of the adjacency and minimizes the graph regularization loss with:

for each $1\leq k\leq K$. GraRep concatenates all representations to get source embeddings $Z^{s}=[Z^{(1),s}|\ldots|Z^{(K),s}]$ and target embeddings $Z^{t}=[Z^{(1),t}|\ldots|Z^{(K),t}]$. Finally, note that GraRep is not very scalable as the powers of $D^{-1}W$ might be dense matrices.

Similar to GraRep, HOPE learns asymmetric embeddings but uses a different similarity measure. The distance function in HOPE is simply the Frobenius norm and the similarity matrix is a high-order proximity matrix (e.g. Adamic-Adar):

The similarity matrix in HOPE is computed with sparse matrices, making this method more efficient and scalable than GraRep.

1.4 Outer product-based: Skip-gram methods

Skip-gram graph embedding models were inspired by efficient NLP methods modeling probability distributions over words for learning word embeddings . Skip-gram word embeddings are optimized to predict context words, or surrounding words, for each target word in a sentence. Given a sequence of words $(w_{1},\ldots,w_{T})$, skip-gram will minimize the objective:

for each target words $w_{k}$. In practice, the conditional probabilities can be estimated using neural networks, and skip-gram methods can be trained efficiently using negative sampling.

Perozzi et al. empirically show the frequency statistics induced by random walks also follow Zipf’s law, thus motivating the development of skip-gram graph embedding methods. These methods exploit random walks on graphs and produce node sequences that are similar in positional distribution, as to words in sentences. In skip-gram graph embedding methods, the decoder function is also an outer product (Eq. 3) and the graph regularization term is computed over random walks on the graph.

was the first attempt to generalize skip-gram models to graph-structured data. DeepWalk draws analogies between graphs and language. Specifically, writing a sentence is analogous to performing a random walk, where the sequence of nodes visited during the walk, is treated as the words of the sentence. DeepWalk trains neural networks by maximizing the probability of predicting context nodes for each target node in a graph, namely nodes that are close to the target node in terms of hops and graph proximity. For this purpose, node embeddings are decoded into probability distributions over nodes using row-normalization of the decoded matrix with softmax.

To train embeddings, DeepWalk generates sequences of nodes using truncated unbiased random walks on the graph—which can be compared to sentences in natural language models—and then maximize their log-likelihood. Each random walk starts with a node $v_{i_{1}}\in V$ and repeatedly sample next node at uniform: $v_{i_{j+1}}\in\{v\in V\mid(v_{i_{j}},v)\in E\}$. The walk length is a hyperparameter. All generated random-walk can then be passed to an NLP-embedding algorithm e.g. word2vec’s Skipgram model. This two-step paradigm introduced by Perozzi et al. is followed by many subsequent works, such as node2vec .

We note that is common for underlying implementations to use two distinct representations for each node (one for when a node is center of a truncated random walk, and one when it is in the context). The implications of this modeling choice is studied further in .

is a random-walk based approach for unsupervised network embedding, that extends DeepWalk’s sampling strategy. The authors introduce a technique to generate biased random walks on the graph, by combining graph exploration through breadth first search (BFS) and through depth first search (DFS). Intuitively, node2vec also preserves high order proximities in the graph but the balance between BFS and DFS allows node2vec embeddings to capture local structures in the graph, as well as global community structures, which can lead to more informative embeddings. Finally, note that negative sampling is used to approximate the normalization factor $C$ in Eq. 5.

(WYS) Random walk methods are very sensitive to the sampling strategy used to generate random walks. For instance, some graphs may require shorter walks if local information is more informative that global graph structure, while in other graphs, global structure might be more important. Both DeepWalk and node2vec sampling strategies use hyper-parameters to control this, such as the length of the walk or ratio between breadth and depth exploration. Optimizing over these hyper-parameters through grid search can be computationally expensive and can lead to sub-optimal embeddings. WYS learns such random walk hyper-parameters to minimize the overall objective (in analogy: each graph gets to choose its own preferred “context size”, such that the probability of predicting random walks is maximized). WYS shows that, when viewed in expectation, these hyperparameters only correspond in the objective to coefficients to the powers of the adjacency matrix $(W^{k})_{1\leq k\leq K}$. These coefficients are denoted $q=(q_{k})_{1\leq k\leq K}$ and are learned through back-propagation. Should $q$’s learn a left-skewed distribution, then the embedding would prioritize local information and right-skewed distribution will enhance high-order relationships and graph global structure. This concept has been extended to other forms of attention to the ‘graph context’, such using a personalized context distributions for each node .

(LINE) learns embeddings that preserve first and second order proximity. To learn first order proximity preserving embeddings, LINE minimizes the graph regularization loss:

LINE also assumes that nodes with multiple edges in common should have similar embeddings and learns second-order proximity preserving embeddings by minimizing:

Intuitively, LINE with second-order proximity decodes embeddings into context conditional distributions for each node $p_{2}(\cdot|v_{i})$. Note that optimizing the second-order objective is computationally expensive as it requires a sum over the entire set of edges. LINE uses negative sampling to sample negative edges according to some noisy distribution over edges. Finally, as in GraRep, LINE combines first and second order embeddings with concatenation $Z=[Z^{(1)}|Z^{(1)}]$.

(HARP) Both node2vec and DeepWalk learn node embeddings by minimizing non-convex functions, which can lead to local minimas. HARP introduces a strategy that computes initial embeddings, leading to more stable training and convergence. More precisely, HARP hierarchically reduces the number of nodes in the graph via graph coarsening. Nodes are iteratively grouped into super nodes that form a graph with similar properties as the original graph, leading to multiple graphs with decreasing size $(G_{1},\ldots,G_{T})$. Node embeddings are then learned for each coarsened graph using existing methods such as LINE or DeepWalk, and at time-step $t$, embeddings learned for $G_{t}$ are used as initialized embedding for the random walk algorithm on $G_{t-1}$. This process is repeated until each node is embedded in the original graph. The authors show that this hierarchical embedding strategy produces stable embeddings that capture macroscopic graph information.

What if a node is not the correct ‘base unit’ of analysis for a graph? Unlike HARP, which coarsens a graph to preserve high-level topological features, Splitter is a graph embedding approach designed to better model nodes which have membership in multiple communities. It uses the Persona decomposition , to create a derived graph, $G_{P}$ which may have multiple persona nodes for each original node in $G$ (the edges of each original node are divided among its personas). $G_{P}$ can then be embedded (with some constraints) using any of the embedding methods discussed so far. The resulting representations allow persona nodes to be separated in the embedding space, and the authors show benefits to this on link prediction tasks.

As noted by , Skip-gram methods can be viewed as matrix factorization, and the methods discussed here are related to those of Matrix Factorization (Section 4.1.3). This relationship is discussed in depth by , who propose a general matrix factorization framework, NetMF, which uses the same underlying graph proximity information as DeepWalk, LINE, and node2vec. Casting the node embedding problem as matrix factorization can offer benefits like easier algorithmic analysis (e.g., convergence guarantees to unique globally-optimal points), and dense matrix undergoing decomposition can be sampled entry-wise .

2 Auto-encoders

Shallow embedding methods hardly capture non-linear complex structures that might arise in graphs. Graph auto-encoders were originally introduced to overcome this issue by using deep neural network encoder and decoder functions, due to their ability model non-linearities. Instead of exploiting the graph structure through the graph regularization term, auto-encoders directly incorporate the graph adjacency matrix in the encoder function. Auto-encoders generally have an encoding and decoding network which are multiple layers of non-linear layers. For graph auto-encoders, the encoder function has the form:

That is, the encoder is a function of the adjacency matrix $W$ only. These models are trained by minimizing a reconstruction error objective and we review examples of such objectives next.

(SDNE) learns auto-encoders that preserve first and second-order node proximity (Section 2.1). The SDNE encoder takes as input a node vector: a row of the adjacency matrix as they explicitly set $s(W)=W$, and produces node embeddings $Z$. The SDNE decoder return a reconstruction $\widehat{W}$, which is trained to recover the original graph adjacency matrix (Fig. 7). SDNE preserves second order node proximity by minimizing the graph regularization loss:

where $B$ is the indicator matrix for $s(W)$ with $B=1[s(W)>0]$. Note that the second term is the regularization loss used by distance-based shallow embedding methods. The first term is similar to the matrix factorization regularization objective, except that $\widehat{W}$ is not computed using outer products. Instead, SDNE computes a unique embedding for each node in the graph using a decoder network.

(DNGR) Similar to SDNE, DNGR uses deep auto-encoders to encode and decode a node similarity matrix, $s(W)$. The similarity matrix is computed using a probabilistic method called random surfing, that returns a probabilistic similarity matrix through graph exploration with random walks. Therefore, DNGR captures higher-order dependencies in the graph. The similarity matrix $s(W)$ is then encoded and decoded with stacked denoising auto-encoders , which allows to reduce the noise in $s(W)$. DNGR is optimized by minimizing the reconstruction error:

3 Graph neural networks

In graph neural networks, both the graph structure and node features are used in the encoder function to learn structural representations of nodes:

We first review unsupervised graph neural networks, and will cover supervised graph neural networks in more details in Section 5.

Computing the regularization term over all possible nodes pairs is computationally challenging in practice, and the Graph Auto Encoders (GAE) model uses negative sampling to overcome this challenge.

Note that GAE is a deterministic model but the authors also introduce variational graph auto-encoders (VGAE), where they use variational auto-encoders to encode and decode the graph structure. In VGAE, the embedding $Z$ is modelled as a latent variable with a standard multivariate normal prior $p(Z)=\mathcal{N}(Z|0,I)$ and the amortized inference network $q_{\Phi}(Z|W,X)$ is also a graph convolution network. VGAE is optimized by minimizing the corresponding negative evidence lower bound:

(Graphite) extends GAE and VGAE by introducing a more complex decoder, which iterates between pairwise decoding functions and graph convolutions. Formally, the graphite decoder repeats the following iteration:

where $Z^{(0)}$ are initialized using the output of the encoder network. By using this parametric iterative decoding process, Graphite learns more expressive decoders than other methods based on non-parametric pairwise decoding. Finally, similar to GAE, Graphite can be deterministic or variational.

The optimization (Eq. 6) is shown by to maximize a lower-bound on the Mutual Information (MI) between the outputs of the encoder and the graph pooling function. In other words, it maximizes the MI between individual node representations and the graph representation.

Graphical Mutual Information [GMI, 119] presents another MI alternative: rather than maximizing MI of node information and an entire graph, GMI maximizes the MI between the representation of a node and its neighbors.

4 Summary of unsupervised embedding methods

This section presented a number of unsupervised embedding methods. Specifically, the only supervision signal is the graph itself, but no labels for nodes or the graph are processed by these methods.

Auto-encoder methods (Sec. 4.2) are deeper, though they still ignore node feature matrix $X$. These are feed-forward neural networks where the network input is the adjacency matrix $W$. These methods are better suited when new nodes are expected at inference test time.

Finally, Graph neural networks (Sec. 4.3) are deep methods that process both the adjacency $W$ and node features $X$. These methods are inductive, and are generally empericially outperform the above two classes, for node-classification tasks, especially when nodes have features.

Supervised Graph Embedding

A common approach for supervised network embedding is to use an unsupervised network embedding method, like the ones described in Section 4 to first map nodes to an embedding vector space, and then use the learned embeddings as input for another neural network. However, an important limitation with this two-step approach is that the unsupervised node embeddings might not preserve important properties of graphs (e.g. node labels or attributes), that could have been useful for a downstream supervised task.

Recently, methods combining these two steps, namely learning embeddings and predicting node or graph labels, have been proposed. We describe these methods next.

Similar to unsupervised shallow embedding methods, supervised shallow embedding methods use embedding look-ups to map nodes to embeddings. However, while the goal in unsupervised shallow embeddings is to learn a good graph representation, supervised shallow embedding methods aim at doing well on some downstream prediction task such as node or graph classification.

(LP) is a very popular algorithm for graph-based semi-supervised node classification. It directly learns embeddings in the label space, i.e. the supervised decoder function in LP is simply the identity function:

In particular, LP uses the graph structure to smooth the label distribution over the graph by adding a regularization term to the loss function, where the underlying assumption is that neighbor nodes should have similar labels (i.e. there exist some label consistency between connected nodes). The regularization in LP is computed with Laplacian eigenmaps:

LP minimizes this energy function over the space of functions that take fixed values on labelled nodes (i.e. $\hat{y}^{N}_{i}=y^{N}_{i}\ \forall i|v_{i}\in V_{L}$) using an iterative algorithm that updates a unlabelled node’s label distribution via the weighted average of its neighbors’ labels.

There exists variants of this algorithm such as Label Spreading (LS) , which minimizes the energy function:

where $D_{i}=\sum_{j}W_{ij}$ is the degree of node $v_{i}$. The supervised loss in label spreading is simply the sum of distances between predicted labels and ground truth labels (one-hot vectors):

Note that the supervised loss is computed over labeled nodes only, while the regularization term is computed over all nodes in the graph. These methods are expected to work well with consistent graphs, that is graphs where node proximity in the graph is positively correlated with label similarity.

2 Graph regularization methods

Supervised graph regularization methods also aim at learning to predict graph properties such as node labels. Similar to shallow embeddings, these methods compute a graph regularization loss defined over the graph structure, and a supervised loss for the downstream task (Fig. 9). However, the main difference with shallow embeddings lies in the encoder network: rather than using embedding look-ups, graph regularization methods learn embeddings as parametric function defined over node features, which might capture valuable information for downstream applications. That is, encoder functions in these methods can be written as:

We review two types of semi-supervised graph regularization approaches: Laplacian-based regularization methods and methods that use random walks to regularize embeddings.

(ManiReg) builds on the LP model and uses Laplacian Eigenmaps to smoothen the label distribution via the regularization loss in Eq. 7. However, instead of using shallow embeddings to predict labels, ManiReg uses support vector machines to predict labels from node features. The supervised loss in ManiReg is computed as:

where $||\cdot||$ can be the L2 or L1 norm. SemiEmb regularizes intermediate or auxiliary layers in the network using the same regularizer as the LP loss in Eq. 7. SemiEmb uses FF-NN to predict labels from intermediate embeddings, which are then compared to ground truth labels via the Hinge loss in Eq. 10.

Note that SemiEmb leverages multi-layer neural networks and regularizes intermediate hidden representations, while LP does not learn intermediate representations, and ManiReg only regularizes the last layer.

(NGM) More recently, NGM generalize the regularization objective in Eq. 7 to more complex neural architectures than feed-forward neural networks (FF-NN), such as Long short-term memory (LSTM) networks or CNNs . in contrast with previous methods, NGM use the cross entropy loss for classification.

2.2 Skip-gram

The Laplacian-based regularization methods covered so far only capture first order proximities in the graphs. Skip-gram graph regularization methods further extend these methods to incorporate random walks, which are effective at capturing higher-order proximities.

Unsupervised skip-gram methods like node2vec and DeepWalk learn embeddings in a multi-step pipeline where random walks are first generated from the graph and then used to learn embeddings. These embeddings are not learned for a downstream classification task which might be suboptimal. Planetoid extends random walk methods to leverage node label information during the embedding algorithm.

with $\widehat{W}_{ij}=Z_{i}^{\top}Z_{j}$ and $\gamma\in\{-1,1\}$ with $\gamma=1$ if $(v_{i},v_{j})\in E$ is a positive pair and $\gamma=-1$ if $(v_{i},v_{j})$ is a negative pair. The distribution under the expectation is directly defined through a sampling processThere are two kinds of sampling strategies to sample positive pairs of nodes $i,j$: (i.) samples drawn by conducting random walks, similar to DeepWalk and (ii.) samples drawn from the same class i.e. $y_{i}=y_{j}$. These samples are positive i.e. with $\gamma=1$. The negative samples simply replace one of the nodes with another randomly-sampled (negative) node yielding $\gamma=-1$. The ratio of these kinds of samples are determined by hyperparameters. . The supervised loss in Planetoid is the negative log-likelihood of predicting the correct labels:

where $i$ is a node’s index while $k$ indicates label classes, and $\widehat{y}^{N}_{i}$ are computed using a neural network followed by a softmax activation, mapping $Z_{i}$ to predicted labels.

3 Graph convolution framework

We now focus on (semi-)supervised neighborhood aggregation methods, where the encoder uses input features and the graph structure to compute embeddings:

We first review the graph neural network model—which was the first attempt to use deep learning techniques on graph-structured data—and other related frameworks such as message passing networks . We then introduce a new Graph Convolution Framework (GCF), which is designed specifically for convolution-based graph neural networks. While GCF and other frameworks overlap on some methods, GCF emphasizes the geometric aspects of convolution and propagation, allowing to easily understand similarities and differences between existing convolution-based approaches.

(GNN) The first formulation of deep learning methods for graph-structured data dates back to the graph neural network GNN) model of Gori et al. . This formulation views the supervised graph embedding problem as an information diffusion mechanism, where nodes send information to their neighbors until some stable equilibrium state is reached. More concretely, given randomly initialized node embeddings $Z^{0}$, the following recursion is applied until convergence:

where parameters $\Theta^{E}$ are reused at every iteration. After convergence ($t=T$), the node embeddings $Z^{T}$ are used to predict the final output such as node or graph labels:

This process is repeated several times and the GNN parameters $\Theta^{E}$ and $\Theta^{D}$ are learned with backpropagation via the Almeda-Pineda algorithm . Note that by Banach’s fixed point theorem, the iteration in Eq. 12 is guaranteed to converge to a unique solution when the iteration ENC is a contraction mapping. In particular, Scarselli et al. explore maps that can be expressed using message passing networks:

where $f(\cdot)$ is a multi-layer perception (MLP) constrained to be a contraction mapping. On the other hand, the decoder function in GNNs does not need to fulfill any constraint and can be any MLP.

(GGNN) Gated Graph Sequence Neural Networks (GGSNN) or their simpler version GGNN are similar to GNNs but remove the contraction mapping requirement. In GGSNNs, the recursive algorithm in Eq. 12 is relaxed and approximated by applying mapping functions for a fixed number of steps, where each mapping function is a gated recurrent unit with parameters shared for every iteration. The GGSNN model is particularly useful for machine learning tasks with sequential structure (such as temporal graphs) as it outputs predictions at every step.

This framework further extends the MPNN framework to learn representations for edges, nodes and the entire graph using message passing functions. This framework is more general than the MPNN framework as it incorporates edge and graph representations.

3.2 Graph Convolution Framework

We now introduce our Graph Convolution Framework (GCF); and as we shall see, many recent graph neural networks can be described using this framework. Different from the MPNN and GraphNet frameworks, our framework focuses on convolution-based methods, and draws direct connections between convolutions on grids and graph convolutions. While GCF does not include sophisticated message passing networks (e.g. messages computed with edge features), it emphasizes geometric properties of convolution operators, and provides a simple way to understand similarities and differences between state-of-the-art graph convolution methods.

Patch functions, which define the shape of convolutional filters (specifies which nodes interact with each other at every step of convolution), that is matrices of size $|V|\times|V|$:

Merging functions, which combine outputs from multiple convolution steps into one representation:

For instance, $h(\cdot)$ can be averaging or concatenation along the feature dimension followed by some non-linearity. Alternatively, $h(\cdot)$ can also be a more complicated operation parameterized by a neural network.

After $L$ convolution layers, nodes’ embeddings $Z=H^{L}$ can be used to decode node or graph labels. Next, we review state-of-the-art GNNs, including spectral and spatial graph convolution methods using the proposed GCF framework.

4 Spectral Graph Convolutions

Spectral methods apply convolutions in the the spectral domain of the graph Laplacian matrix. These methods broadly fall into two categories: spectrum-based methods, which explicitly compute the Laplacian’s eigendecomposition, and spectrum-free methods, which are motivated by spectral graph theory but do not explicitly compute the Laplacian’s eigenvectors. One disadvantage of spectrum-based methods is that they rely on the spectrum of the graph Laplacian and are therefore domain-dependent (i.e. cannot generalize to new graphs). Moreover, computing the Laplacian’s spectral decomposition is computationally expensive. Spectrum-free methods overcome these limitations by providing approximations for spectral filters.

In non-Euclidean domains, the notion of translation (shift) is not defined and it is not trivial to generalize spatial convolutions operators (${\Theta}$) to non-Euclidean domains. Note that Eq. 15 can be equivalently written as:

Spectral graph convolutions build on this observation to generalize convolutions to graphs, by learning convolution filters in the spectral domain of the normalized Laplacian matrix:

Using GCF, patch functions in spectrum-based methods can be expressed in terms of eigenvectors of the graph normalized Laplacian:

for some function $g_{k}(.).$ Note that this dependence on the spectrum of the Laplacian makes spectrum-based methods domain-dependent (i.e. they can only be used in transductive settings).

In practice, SCNNs can be used for node classification or graph classification with graph pooling. However, SCNNs have two major limitations: (1) computing the eigendecomposition of the graph Laplacian is computationally expensive and (2) this method is domain-dependent, as its filters are eigen-basis dependent and cannot be shared across graphs.

4.2 Spectrum-free methods

(ChebNets) use the Chebyshev expansion to approximate spectral filters. Chebyshev polynomials form an orthonormal basis in $$ and can be computed efficiently with the recurrence:

In order to use Chebyshev polynomials, ChebNets rescale the normalized adjacency martrix $\widetilde{L}$ to ensure that its eigenvalues are in $$. The convolution step in ChebNet can be written as:

where $\lambda_{max}(\widetilde{L})$ is the largest eigenvalue of $\widetilde{L}$.

Furthermore, since $I+D^{-1/2}WD^{-1/2}$ has eigenvalues in $$, applying Eq. 20 multiple times might lead to numerical instabilities or exploding gradients. To overcome this issue, GCNs use a re-normalization trick, which maps the eigenvalues of$I+D^{-1/2}WD^{-1/2}$to$$:

Using GCF notation, GCN patch functions can be written as:

and the graph convolution layer (see 11 for an illustration) is:

This model has been applied to many problems including matrix completion , link prediction in knowledge graphs , and unsupervised graph embedding with variational inference .

Note that in contrast with spectrum-based methods covered in the previous section, both ChebyNet and GCN do not rely on computations of the Laplacian’s eigenvectors. The convolution step is only defined over the local neighborhood of each node (as defined by the adjacency matrix $W$), and therefore we can view these methods as local message passing algorithms (see the Taxonomy in Fig. 3), even though these are motivated by spectral graph theory.

5 Spatial Graph Convolutions

Spectrum-based methods are limited by their domain dependency and cannot be applied in inductive settings. Furthermore, spectrum-free methods such as GCNs require storing the entire graph adjacency matrix, which can be computationally expensive for large graphs.

To overcome these limitations, spatial methods borrow ideas from standard CNNs, where convolutions are applied in the spatial domain as defined by the graph topology. For instance, in computer vision, convolutional filters are spatially localized by using fixed rectangular patches around each pixel. Additionally, since pixels in images have a natural ordering (top, left, bottom, right), it is possible to reuse filters’ weights at every location, significantly reducing the total number of parameters. While such spatial convolutions cannot directly be applied in graph domains, spatial graph convolutions use ideas such as neighborhood sampling and attention mechanisms to overcome challenges posed by graphs’ irregularities.

(SAGE) While GCNs can be used in inductive settings, they were originally introduced for semi-supervised transductive settings, and the learned filters might strongly rely on the Laplacian used for training. Furthermore, GCNs require storing the entire graph in memory which can be computationally expensive for large graphs.

To overcome these limitations, Hamilton et al. propose SAGE, a general framework to learn inductive node embeddings while reducing the computational complexity of GCNs. Instead of averaging signals from all one-hop neighbors using multiplications with the Laplacian matrix, SAGE samples fixed neighborhoods (of size $q$) to remove the strong dependency on a fixed graph structure and generalize to new graphs. At every SAGE layer, nodes aggregate information from nodes sampled from their neighborhood, and the propagation rule can be written as:

Note that SAGE can also be described using GCF. For simplicity, we describe SAGE-mean using GCF notation, and refer to for details regarding other aggregation schemes. In GCF notation, SAGE-mean uses two patch learning functions with $g_{1}(W,D)=I$ being the identity, and $g_{2}(W,D)\sim\mathcal{U}_{\text{norm}}(D^{-1}W,q)$, where $\mathcal{U}_{\text{norm}}(\cdot,q)$ indicates uniformly sampling $q$ nonzero entries per row, followed by row normalization. That is, the second patch propagates information using neighborhood sampling, and the SAGE-mean layer is:

5.2 Attention-based spatial methods

Attention mechanisms have been successfully used in language models, and are particularly useful when operating on long sequence inputs, they allow models to identify relevant parts of the inputs. Similar ideas have been applied to graph convolution networks. Graph attention-based models learn to pay attention to important neighbors during the message passing step. This provides more flexibility in inductive settings, compared to methods that rely on fixed weights such as GCNs.

Broadly speaking, attention methods learn neighbors’ importance using parametric functions whose inputs are node features at the previous layer. Using GCF, we can abstract patch functions in attention-based methods as functions of the form:

where $\cdot$ indicates element-wise multiplication and $\alpha(\cdot)$ is an activation function such as softmax or ReLU.

(GAT) is an attention-based version of GCNs, which incorporate self-attention mechanisms when computing patches. At every layer, GAT attends over the neighborhood of each node and learns to selectively pick nodes which lead to the best performance for some downstream task. The high-level intuition is similar to SAGE and makes GAT suitable for inductive and transductive problems. However, instead of limiting the convolution step to fixed size-neighborhoods as in SAGE, GAT allows each node to attend over the entirety of its neighbors and uses attention to assign different weights to different nodes in a neighborhood. The attention parameters are trained through backpropagation, and the GAT self-attention mechanism is:

where $\oplus$ indicates summation of row and column vectors with broadcasting, and $(b_{0},b_{1})$ and $B$ are trainable attention weight vectors and weight matrix respectively. The edge scores are then row normalized with softmax. In practice, the authors propose to use multi-headed attention and combine the propagated signals with a concatenation of the average operator followed by some activation function. GAT can be implemented efficiently by computing the self-attention scores in parallel across edges, as well as computing the output representations in parallel across nodes.

(MoNet) Monti et al. provide a general framework that works particularly well when the node features lie in multiple domains such as 3D point clouds or meshes. MoNet can be interpreted as an attention method as it learns patches using parametric functions in a pre-defined spatial domain (e.g. spatial coordinates), and then applies convolution filters in the graph domain.

where $\cdot$ is element-wise multiplication and $g_{k}(U^{s})$ are the learned parametric patches, which are $|V|\times|V|$ matrices. In practice, MoNet uses Gaussian kernels to learn patches, such that:

where $\mu_{k}$ and $\Sigma_{k}$ are learned parameters, and Monti et al. restrict $\Sigma_{k}$ to be a diagonal matrix.

6 Non-Euclidean Graph Convolutions

Hyperbolic shallow embeddings enable embeddings of hierarchical graphs with smaller distortion than Euclidean embeddings. However, one major downside of shallow embeddings is that they are inherently transductive and cannot generalize to new graphs. On the other hand, Graph Neural Networks, which leverage node features, have achieved state-of-the-art performance on inductive graph embedding tasks.

Recently, there has been interest in extending Graph Neural Networks to learn non-Euclidean embeddings and thus benefit from both the expressiveness of Graph Neural Networks and hyperbolic geometry. One major challenge in doing so is how to perform convolutions in a non-Euclidean space, where standard operations such as inner products and matrix multiplications are not defined.

(HGCN) and Hyperbolic Graph Neural Networks (HGNN) apply graph convolutions in hyperbolic space by leveraging the Euclidean tangent space, which provides a first-order approximation of the hyperbolic manifold at a point. For every graph convolution step, node embeddings are mapped to the Euclidean tangent space at the origin, where convolutions are applied, and then mapped back to the hyperbolic space. These approaches yield significant improvements on graphs that exhibit hierarchical structure (Fig. 13).

7 Summary of supervised graph embedding

This section presented a number of methods that process task labels (e.g., node or graph labels) at training time. As such, model parameters are directly optimized on the upstream task.

Shallow methods use neither node features $X$ nor adjacency $W$ in the encoder (Section 5.1), but utilize the adjacency to ensure consistency. Such methods are useful in transductive settings, if only one graph is given, without node features, a fraction of nodes are labeled, and the goal is to recover labels for unlabeled nodes.

Graph regularization methods (Section 5.2) utilize node features $X$ but not the adjacency $W$ in the encoder. In general, these methods are inductive (except of one version of planetoid ). In fact, they need only a graph at training time but not at inference (test) time. In general, they can be applied when node features contain rich information.

Finally, graph convolution models (Sections 5.3, 5.4 & 5.5) utilize node features and adjacency in the encoder. At the time of writing, these models acheive superior empirical performance on many node-classification tasks.

Applications

Graph representation learning methods can be applied to a wide range of applications, which can be unsupervised or supervised. In unsupervised applications, task-specific labels are not processed for learning embeddings. Rather, the graph is used as a form of self-supervision. Specifically, one can learn embeddings that preserve the graph (i.e. neighborhoods) or to preserve structural equivalence of nodes (see Section 2.2.3 for distinction), for instance, by applying unsupervised embedding methods (Section 4, upper branch of the Taxonomy in Fig. 3). On the other hand, in supervised applications, node embeddings are directly optimized for some specific task, such as classifying nodes or graphs. In this setting, supervised embedding methods (Section 5, lower branch of the Taxonomy in Fig. 3) can be applied. Table 5 summarizes some popular tasks in GRL, and pairs them with methods frequently used for the tasks. We review common unsupervised and supervised graph applications next.

The most standard unsupervised graph application is graph reconstruction. In this setting, the goal is to learn mapping functions (which can be parametric or not) that map nodes to dense distributed representations which preserve graph properties such as node similarity. Graph reconstruction doesn’t require any supervision and models can be trained by minimizing a reconstruction error, which is the error in recovering the original graph from learned embeddings. Several algorithms were designed specifically for this task, and we refer to Section 4 for some examples of reconstruction objectives. At a high level, graph reconstruction is similar to dimensionality reduction in the sense that the main goal is summarize some input data into a low-dimensional embedding. Instead of compressing high dimensional vectors into low-dimensional ones as standard dimensionality reduction methods (e.g. PCA) do, the goal of graph reconstruction models is to compress data defined on graphs into low-dimensional vectors.

1.2 Link prediction

Link prediction is the task of predicting links in a graph. In other words, the goal in link prediction tasks is to predict missing or unobserved links (e.g. links that may appear in the future for dynamic and temporal networks). Link prediction can also help identifying spurious link and remove them. It is a major application of graph learning models in industry, and common example of applications include predicting friendships in social networks or predicting user-product interactions in recommendation systems.

A common approach for training link prediction models is to mask some edges in the graph (positive and negative edges), train a model with the remaining edges and then test it on the masked set of edges. Note that link prediction is different from graph reconstruction. In link prediction, we aim at predicting links that are not observed in the original graph while in graph reconstruction, we only want to compute embeddings that preserve the graph structure through reconstruction error minimization.

Finally, while link prediction has similarities with supervised tasks in the sense that we have labels for edges (positive, negative, unobserved), we group it under the unsupervised class of applications since edge labels are usually not used during training, but only used to measure the predictive quality of embeddings. That is, models described in Section 4 can be applied to the link prediction problem.

1.3 Clustering

Clustering is particularly useful for discovering communities and has many real-world applications. For instance, clusters exist in biological networks (e.g. as groups of proteins with similar properties), or in social networks (e.g. as groups of people with similar interests).

Note that unsupervised methods introduced in this survey can be used to solve clustering problems: one can run a clustering algorithm (e.g. k-means) on embeddings that are output by an encoder. Further, clustering can be joined with the learning algorithm while learning a shallow or Graph Convolution embedding model.

1.4 Visualization

There are many off-the-shelf tools for mapping graph nodes onto two-dimensional manifolds for the purpose of visualization. Visualizations allow network scientists to qualitatively understand graph properties, understand relationships between nodes or visualize node clusters. Among the popular tools are methods based on Force-Directed Layouts, with various web-app Javascript implementations.

Unsupervised graph embedding methods are also used for visualization purposes: by first training an encoder-decoder model (corresponding to a shallow embedding or graph convolution network), and then mapping every node representation onto a two-dimensional space using, t-distributed stochastic neighbor embeddings (t-SNE) or PCA . Such a process (embedding $\rightarrow$ dimensionality reduction) is commonly used to qualitatively evaluate the performance of graph learning algorithms. If nodes have attributes, one can use these attributes to color the nodes on 2D visualization plots. Good embedding algorithms embed nodes that have similar attributes nearby in the embedding space, as demonstrated in visualizations of various methods . Finally, beyond mapping every node to a 2D coordinate, methods which map every graph to a representation can similarly be projected into two dimensions to visualize and qualitatively analyze graph-level properties.

2 Supervised applications

Node classification is an important supervised graph application, where the goal is to learn node representations that can accurately predict node labels. For instance, node labels could be scientific topics in citation networks, or gender and other attributes in social networks.

Since labelling large graphs can be time-consuming and expensive, semi-supervised node classification is a particularly common application. In semi-supervised settings, only a small fraction of nodes is labelled and the goal is to leverage links between nodes to predict attributes of unlabelled nodes. This setting is transductive since there is only one partially labelled fixed graph. It is also possible to do inductive node classification, which corresponds to the task of classifying nodes in multiple graphs.

Note that node features can significantly boost the performance on node classification tasks if these are descriptive for the target label. Indeed, recent methods such as GCN or GraphSAGE have achieved state-of-the-art performance on multiple node classification benchmarks due to their ability to combine structural information and semantics coming from features. On the other hand, other methods such as random walks on graphs fail to leverage feature information and therefore achieve lower performance on these tasks.

2.2 Graph classification

Graph classification is a supervised application the task is to predict graph-level labels given an input graph. Graph classification tasks are inherently inductive, as new graphs are presented at test time. Many popular tasks are biochemical and some others are online social networks. In the biochemical domain, a common application uses graphs corresponding to molecules. In these graphs, each node represents an atom (e.g. with a feature vector that’s a 1-hot encoding of its atomic number) and an edge between two nodes indicates a bond (feature vector could indicate bond type). The graph-level label is task dependant, e.g., indicating mutagenicity of a drug against bacteria, such as MUTANG . In online social networks, nodes usually correspond to users and edges represent relationships or interactions. For instance, the Reddit graph classification tasks contain many graphs. Each graph corresponds to a discussion thread: user commenting on a user’s comment, an edge will connect the two. The goal is to predict the community (sub-reddit) where discussion took place, given the graph of comments.

Different than tasks of node-level (e.g., node classification) and edge-level (e.g., link prediction) prediction, graph classification tasks require an additional type of pooling, in order to aggregate node-level information into graph-level information. As discussed earlier, generalizing this notion of pooling to arbitrary graphs is non-trivial, and is an active research area. The pooling function should be invariant to the node order. Many methods use simple pooling, such as mean or sum of all graph node-level latent vectors e.g. . Other methods use differentiable pooling .

In addition to these supervised methods, a number of unsupervised methods for learning graph-level representations have been proposed . In fact, a notable class of unsupervised graph-level models are known as graph kernels (GKs), see for reviews.

While GKs are outside our main focus, here we briefly mention connections of GKs to GraphEDM. GKs can be applied to graph-level tasks such as graph classification. GK can implicitly implement a similarity function that maps any two graphs into a scalar. Traditional GKs compute similarity of two graphs by counting how many walks (or paths) the two graphs share in common – e.g., each walk can be encoded as a sequence of node labels. If nodes are not labeled, it is common to use the node degrees as labels. GKs are often analyzed in their ability to detect (sub-)graph isomorphism. Two (sub-)graphs are isomorphic if they are identical when ignoring node ordering. As sub-graph isomorphism is NP-hard, the $1$-dimensional Weisfeiler-Leman ($1$-WL) heuristic deems two sub-graphs as isomorphic as follows. For each graph, node statistics are counted as histograms (e.g., count nodes with label “A”, and how many of those have an edge to nodes with label “B”, etc). The $1$-WL heuristic deems two graphs as isomorphic if their histograms, extracted from 1-hop neighborhood, are identical. Certain GNNs, such as the Graph Isomorphism Network [GIN, 156] have been proven to realize the $1$-WL heuristic i.e. it can map two graphs to the same latent vector if-and-only-if they would be deemed isomorphic by the $1$-WL heuristic. Some recent work combines GKs and GNNs. As examples, Chen et al. extract walk patterns; Du et al. model similarity of two graphs using the similarity of the “tangent space” of the objective w.r.t. the Gaussian-initialized GNN parameters. In both , there is no actual GNN training. The training rather uses kernelized methods such as kernel support vector machines, on the pairwise Gram matrix. As such, these methods cannot be readily plugged into our our frameworks of GCF or GraphEDM. On other hand, other methods explicitly map a graph to the high-dimensional latent space, rather than implicitly compute graph-to-graph similarity scalar score. As an example, the $k$-GNN network of Morris et al. can realize the $k$-WL heuristic (similar to 1-WL, but here histograms are computed up-to $k$-hop neighbors), yet it is explicitly programmed as a GNN. As such, the $k$-GNN model classes can be described in our frameworks of GCF and GraphEDM.

Conclusion and Open Research Directions

In this survey, we introduced a unified framework to compare machine learning models for graph-structured data. We presented a generalized GraphEDM framework, previously applied to unsupervised network embedding, that encapsulates shallow graph embedding methods, graph auto-encoders, graph regularization methods and graph neural networks. We also introduced a graph convolution framework (GCF), which is used to describe and compare convolution-based graph neural networks, including spatial and spectral graph convolutions. Using this framework, we introduced a comprehensive taxonomy of GRL methods, encapsulating over thirty methods for graph embedding (both supervised and unsupervised).

We hope that this survey will help and encourage future research in GRL, to hopefully solve the challenges that these models are currently facing. In particular, practitioners can reference the taxonomy to better understand the available tools and applications, and easily identify the best method for a given problem. Additionally, researchers with new research questions can use the taxonomy to better classify their research questions, reference the existing work, identify the right baselines to compare to, and find the appropriate tools to answer their questions.

While GRL methods have achieved state-of-the-art performance on node classification or link prediction tasks, many challenges remain unsolved. Next, we discuss ongoing research directions and challenges that graph embedding models are facing.

The methods covered in this survey are typically evaluated using standard node classification or link prediction benchmarks. For instance, citation networks are very often used as benchmarks to evaluate graph embedding methods. However, these small citation benchmarks have drawbacks since results might significantly vary based on datasets’ splits, or training procedures (e.g. early stopping), as shown in recent work .

To better advance GRL methods, it is important to use robust and unified evaluation protocols, and evaluate these methods beyond small node classification and link prediction benchmarks. Recently, there has been progress in this direction, including new graph benchmarks with leaderboards and graph embedding libraries . On a similar vein, Sinha et al. recently proposed a set of tasks grounded in first-order logic, to evaluate the reasoning capabilities of GNNs.

The emerging field of Fairness in Machine Learning seeks to ensure that models avoid correlation between ‘sensitive’ features and the model’s predicted output . These concerns can be especially relevant for graph learning problems, where we must also consider the correlation of the graph structure (the edges) in addition to the feature vectors of the nodes with the final output.

The most popular technique for adding fairness constraints to models relies on using adversarial learning to debias the model’s predictions relative to the sensitive feature(s), and can be extended to GRL . However, adversarial methods do not offer strong guarantees about the actual amount of bias removed. In addition, many debiasing methods may not be effective at the debiasing task in practice . Recent work in the area aims to provide provable guarantees for debiasing GRL .

Most learning methods on graphs are applied only on smaller datasets, with sizes of up to hundred of thousands of nodes. However, many real-world graphs are much larger, containing up to billions of nodes. Methods that scale for large graphs require a Distributed Systems setup with many machines, such as MapReduce . Given a large graph that fits on a single hard disk (e.g. with one terabyte size) but does not fit on RAM, how can a researcher apply a learning method on such a large graphs, using just a personal computer? Contrast this with a computer vision task by considering a large image dataset . It is possible to train such models on personal computers, as long as the model can fit on RAM, regardless how large the dataset is. This problem may be particularly challenging for graph embedding models, especially those which have parameters that scale with the number of nodes in the graph.

Sometimes in industry, even choosing the best graph to use as input is difficult. describes Grale, a system at Google used for learning the correct graph from a variety of different features. Grale relies on techniques from similarity search (like locality sensitive hashing) to scale graph learning to extremely large datasets. Recent work extends the Grale model with an attention network to allow end-to-end learning.

We foresee additional engineering and mathematical challenges in learning methods for large graphs, while still being operable on a single machine. We hope that researchers can focus on this direction to expose such learning tools to non-expert practitioners, such as a Neurologist wishing to analyze the sub-graph of the human brain given its neurons and synapses, stored as nodes and edges.

Learning on graphs has a great potential for helping molecular scientists to reduce cost and time in the laboratory. Researchers proposed methods for predicting quantum properties of molecules and for generating molecules with some desired properties . A review of recent methods can be found in . Many of these methods are concerned with manufacturing materials with certain properties (e.g. conductance and malleability), and others are concerned drug design .

Computationally hard problems arise in a broad range of areas including routing science, cryptography, decision making and planning. Broadly speaking, a problem is computationally hard when the algorithms that compute the optimal solution scale poorly with the problem size. There has been recent interest in leveraging machine learning techniques (e.g. reinforcement learning) to solve combinatorial optimization problems and we refer to for a review of these methods.

Many hard problems (e.g. SAT, vertex cover…) can be expressed in terms of graphs and more recently, there has been interest in leveraging graph embeddings to approximate solutions of NP-hard problems . These methods tackle computationally hard problems from a data-driven perspective, where given multiple instances of a problem, the task is to predict whether a particular instance (e.g. node) belongs to the optimal solution. Other work focuses on optimizing graph partitions , finding assignments that aim to fulfill an objective (e.g. the minimum conductance cut).

One motivation for all these approaches is the relational inductive biases found in GNNs which enable them to better represent graphs compared to standard neural networks (e.g. permutation invariance). While these data-driven methods are still outperformed by existing solvers, promising results show that GNNs can generalize to larger problem instances . We refer to the recent survey on neural symbolic learning by Lamb et al. for an extensive review of GNN-based methods for combinatorial optimization.

As we saw in Section 4.1.2 and Section 5.6, an important aspect of graph embeddings is the underlying space geometry. Graphs are discrete, high-dimensional, non-Euclidean structures, and there is no straightforward way to encode this information into low-dimensional Euclidean embeddings that preserve the graph topology . Recently, there has been interest and progress into learning non-Euclidean embeddings such as hyperbolic or mixed-product space embeddings. These non-Euclidean embeddings provide a promise for more expressive embeddings, compared to Euclidean embeddings. For instance, hyperbolic embeddings can represent hierarchical data with much smaller distortion than Euclidean embeddings and have led to state-of-the-art results in many modern applications such as link prediction in knowledge graphs and linguistics tasks .

Two common challenges arise with non-Euclidean embeddings: precision issues (e.g. near the boundary of the Poincaré ball) in hyperbolic space and challenging Riemannian optimization . Additionally, it is also unclear how to pick the right geometry for a given input graph. While there exists some discrete measures for the tree-likeliness of graphs (e.g. Gromov’s four-point condition and others ), an interesting open research direction is how to pick or learn the right geometry for a given discrete graph.

There have been significant advances in the design of graph embedding models, which improved over the state-of-the-art in many applications. However, there is still limited understanding about theoretical guarantees and limitations of graph embedding models. Understanding the representational power of GNNs is a nascent area of research, and recent works adapt existing results from learning theory to the problem of GRL . The development of theoretical frameworks is critical to pursue in order to understand the theoretical guarantees and limitations of graph embedding methods.

Acknowledgements

We thank Meissane Chami, Aram Galstyan, Megan Leszczynski, John Palowitch, Laurel Orr, and Nimit Sohoni for their helpful feedback and discussions. We also thank Carlo Vittorio Cannistraci, Thomas Kipf, Luis Lamb, Bruno Ribeiro and Petar Veličković for their helpful feedback and comments on the first version of this work. We gratefully acknowledge the support of DARPA under Nos. FA86501827865 (SDH) and FA86501827882 (ASED); NIH under No. U54EB020405 (Mobilize), NSF under Nos. CCF1763315 (Beyond Sparsity), CCF1563078 (Volume to Velocity), and 1937301 (RTML); ONR under No. N000141712266 (Unifying Weak Supervision); the Moore Foundation, NXP, Xilinx, LETI-CEA, Intel, IBM, Microsoft, NEC, Toshiba, TSMC, ARM, Hitachi, BASF, Accenture, Ericsson, Qualcomm, Analog Devices, the Okawa Foundation, American Family Insurance, Google Cloud, Swiss Re, the HAI-AWS Cloud Credits for Research program, TOTAL, and members of the Stanford DAWN project: Teradata, Facebook, Google, Ant Financial, NEC, VMWare, and Infosys. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views, policies, or endorsements, either expressed or implied, of DARPA, NIH, ONR, or the U.S. Government.

References