Graph Representation Learning and Its Applications: A Survey

Abstract

Graphs are data structures that effectively represent relational data in the real world. Graph representation learning is a significant task since it could facilitate various downstream tasks, such as node classification, link prediction, etc. Graph representation learning aims to map graph entities to low-dimensional vectors while preserving graph structure and entity relationships. Over the decades, many models have been proposed for graph representation learning. This paper aims to show a comprehensive picture of graph representation learning models, including traditional and state-of-the-art models on various graphs in different geometric spaces. First, we begin with five types of graph embedding models: graph kernels, matrix factorization models, shallow models, deep-learning models, and non-Euclidean models. In addition, we also discuss graph transformer models and Gaussian embedding models. Second, we present practical applications of graph embedding models, from constructing graphs for specific domains to applying models to solve tasks. Finally, we discuss challenges for existing models and future research directions in detail. As a result, this paper provides a structured overview of the diversity of graph embedding models.

Keywords: graph embedding; graph neural networks; graph representation learning; graph transformer.

Figure 1

The popularity of graph representation learning models in the Scopus database. The line plot shows changes in the number of publications in different types of graph representation learning models from 2010 to 2022. The y-axis denotes the number of publications on the popularity of graph representation learning models over the years. There are seven keywords, including graph representation learning (GRL), graph kernels (GK), matrix factorization-based graph embedding (MF), graph neural networks (GNNs), graph autoencoder (GAE), graph convolution networks (GCNs), graph transformer (GT), and non-Euclidean graph embedding (NEGE). There are nineteen representative models, including DeepWalk [14], Grarep [15], LINE [16], GGCN [17], GCN [18], HOPE [5], Node2Vec [4], GAT [19], Metapath2Vec [20], Struc2Vec [21], GraphSage [22], G2G [23], GIN [24], HGAT [25], DGI [26], HGNN [27], GCNII [28], GT [29], and EGT [30].

Figure 2

A comprehensive view of graph embedding. Given a spare, high-dimensional graph $G=(V,E)$ where V and E denote the set of nodes and edges. Graph embedding learning aims to find a function $\varphi$ that maps nodes from graph space to d-dimensional vector space with $d\ll \left|V\right|$.

Figure 3

Methods for modeling dynamic graphs over time. (a) The representation of a dynamic graph by a series of snapshots; (b) The evolution of edges and nodes in the dynamic graph from time t to $t+1$. In (a), the graph G is the collection of $G\left(t\right)$ (i.e., $G=\left\{G\right(1),G(2),\cdots ,G(t\left)\right\}$) which t is the time span, and the entities of G change from time t to $t+1$. (b) depicts the evolution of edges in the same dynamic graph from (a) which each edge contains the series of the time spans from t to $t+1$. At time t, the graph has five nodes ($v_1$, $v_2$, $v_3$, $v_4$, $v_5$) and five edges $\left(e_{13}{e}_{15}{e}_{34}{e}_{45}{e}_{23}\right)$. However, at time $t+1$, the edge $e_{23}$ and node $v_2$ are removed, and a new node $v_6$, a new edge $e_{56}$ are added in the graph.

Figure 4

The proposed taxonomy for graph representation learning models.

Figure 5

The Weisfeiler–Lehman isomorphism test. (a) Original labels, $i=0$; (b) Relabeled labels, $i=1$. There are two interactions of WL relabeling for the graph with five nodes $\left\{v_1,v_2,v_3,v_4,v_5\right\}$. In (a), labels of nodes are initialized consisting of 5 nodes. In (b), in the first iteration, new labels of the nodes will be reassigned and calculated based on the connection information to its adjacent nodes. For example, node $v_1$ is adjacent to node $v_2$ and node $v_3$, therefore the new label of $v_1$ is calculated as $\left\{v_1,〈v_2,v_3〉\right\}$ and resigned as new label $v_6$. The same steps are repeated until a steady state for the nodes is reached.

Figure 6

Node sampling techniques. (a) k-hop sampling; (b) Random-walk sampling. The source node $v_s$ and the target node $v_t$ are taken as the source node and the target node in the graph. In (a), the k-hop proximity sampling strategy begins from source node $v_s$, and the green nodes are considered to be the $1st$-hop proximity of node $v_s$. The blue and the black nodes are considered 2nd-hop and 3rd-hop proximity of node $v_s$, respectively. In (b), the random-walk sampling strategy takes a random walk (red arrow) from the source node $v_s$ to the target node $v_t$.

Figure 7

Sampling strategy in Node2Vec and WalkLets model. (a) Sampling strategy in Node2Vec model; (b) Sampling strategy in WalkLets model. In (a), assume a random path from the DeepWalk model is of the form: $(v_1\to v_2\to v_3\to v_4)$, then the corpus of random walk pairs at scale $k=3$ is: $A_1=\{(v_1,v_2),(v_2,v_3),(v_3,v_4)\}$, $A_2=\{(v_1,v_3),(v_2,v_4)\}$, and $A_3=\left\{(v_1,v_4)\right\}$. In (b), there are two parameters: The return parameter p and the in–out parameter q. Parameters $1,1/p$, and $1/q$ are conditional probabilities. Starting at node u and now at v, the random walk looks at the next node based on the probabilities $1/p$ and $1/q$.

Figure 8

Sampling strategy in Sub2Vec model. Assume that there are two subgraphs $G_1=\left\{v_1,v_2,v_3,v_4\right\}$, and $G_2=\left\{v_5,v_6,v_7,v_9\right\}$. For neighborhood properties, the model uses random-walk sampling on all nodes in subgraphs $G_1$ and $G_2$ to capture the subgraph structure. For structural properties, they introduced a ratio of node degree when sampling. With the length of the random-walk path is 3, then the degree path for $G_1$ is $0.75\to 0.75\to 0.75$, while the degree path from node $v_5$ to $v_9$ is: $0.25\to 0.75\to 0.25$.

Figure 9

The random-walk sampling based on motif. (a) Random-walk sampling; (b) Motif-based random-walk sampling. (a) presents a random-walk path from node $v_1$ to $v_7$: $v_1\to v_3\to v_4\to v_5\to v_7$. In (b), the motif-based path is: $〈v_1,v_2,v_3〉\to 〈v_2,v_3,v_4〉\to 〈v_2,v_4,v_5〉\to 〈v_4,v_5,v_6〉$.

Figure 10

Updating random-walk paths to the corpus on dynamic graphs. At time t, the graph has 3 nodes: $v_1,v_2,v_3$ with two edges:$(v_1,v_2)$ and $(v_2,v_3)$. Assuming the length of the random walk is 3, then the set of random walks: $〈v_1,v_2,v_1〉$, $〈v_1,v_2,v_3〉$, $〈v_2,v_1,v_2〉$, $〈v_2,v_3,v_2〉$, $〈v_3,v_2,v_1〉$, $〈v_3,v_2,v_3〉$. At the time $t+1$: The graph has a new node $v_4$ and a new edge $(v_2,v_4)$. Then, new random walks will be updated on the corpus are: $〈v_4,v_2,v_1〉$, $〈v_4,v_2,v_3〉$, and $〈v_4,v_2,v_4〉$.

Figure 11

The strategy of edge and node collapsing of HARP model. (a) Edge compression; (b) Node compression. In (a), the super nodes $〈v_1,v_2〉$ and $〈v_3,v_4〉$ are formed by merging edges $e_{12}$ and $e_{34}$, respectively. In (b), the super nodes $〈v_1,v_2〉$ and $〈v_3,v_4〉$ are formed by merging node pairs $(v_1,v_2)$ and $(v_3,v_4)$, respectively.

Figure 12

The self-centered network of NEWEE model. For instance, the self-centered of node $v_2$ could be defined as $G^{\prime }=\left(V^{\prime },E^{\prime }\right)$ where $V^{\prime }=\left(v_1,v_2,v_3,v_4,v_5\right)$ and $E^{\prime }$ is the set of edges in $G^{\prime }$.

Figure 13

The architecture of SDNE model. The features of nodes $x_i$ and $x_j$ are the inputs of the SDNE model. The encoder layer compresses the feature data $x_i$ and $x_j$ into vectors $Z_i$ and $Z_j$ in the latent space. The decoder layer aims to reconstruct the node features.

Figure 14

The architecture of DynGEM model. Similarity to the SDNE model, the DynGEM model could capture the 1st-order and 2nd-order proximity between two nodes in graphs with the encoder and decoder layers. The difference is vector embedding ${\theta }_t$ parameters at time t are updated from vector embedding ${\theta }_{t-1}$ at time $t-1$.

Figure 15

An example of the Topo-LSTM model. Given by a cascade sequence $S=\{(v_1,1),(v_2,2),(v_3,3),(v_4,4)\}$, the model first takes features of each node $x_1$, $x_2$, $x_3$, $x_4$ as inputs and then infers embeddings via Topo-LSTM model.

Figure 16

The sampling strategy of [57]. The model lists all the node pairs in respective weights as input of the autoencoder model.

Figure 17

The temporal random-walk sampling strategy of LSTM-Node2Vec model during the graphs’ evolution. (a) t; (b) $t+1$; (c) $t+2$. At the time t, the graph has four nodes and four edges between nodes. At the time $t+1$ and $t+2$, the graph has new nodes $v_5$ and $v_6$, respectively. A temporal random walk for node $v_1$ with length $L=3$ could be: $P=\{(v_2,v_3,v_4),(v_3,v_2,v_5),(v_3,v_5,v_6),\cdots \}$.

Figure 18

An example of the GraphSAINT model. (a) A subgraph has five nodes $v_1$, $v_2$, $v_3$, $v_4$, and $v_5$; (b) A full GCN has three layers. (a) presents a subgraph with nodes. In the subgraph, there are 3 nodes $(v_1$, $v_2$, $v_3)$ with higher order than the other two nodes ($v_4$, $v_5$). (b) presents a full CGNN-based model with three layers. Three nodes with higher degrees should be sampled from each other in the next layers.

Figure 19

The architecture of GAE and VGAE model. The model adopts the adjacency matrix A and the feature matrix X as inputs. The encoder part includes two convolutional GNN layers. In the GAE model, the decoder part adopts the embedding matrix Z as input and reconstructs the adjacency matrix A using an inner product. In the VAGE model, the output of GNN could be represented as a Gaussian distribution.