Graph representation learning has been a very active research area in recent years. The goal of graph representation learning is to generate graph representation vectors that capture the structure and features of large graphs accurately. This is especially important because the quality of the graph representation vectors will affect the performance of these vectors in downstream tasks such as node classification, link prediction and anomaly detection. Many techniques have been proposed for generating effective graph representation vectors, which generally fall into two categories: traditional graph embedding methods and graph neural network (GNN)–based methods. These methods can be applied to both static and dynamic graphs. A static graph is a single fixed graph, whereas a dynamic graph evolves over time and its nodes and edges can be added or deleted from the graph. In this survey, we review the graph-embedding methods in both traditional and GNN-based categories for both static and dynamic graphs and include the recent papers published until the time of submission. In addition, we summarize a number of limitations of GNNs and the proposed solutions to these limitations. Such a summary has not been provided in previous surveys. Finally, we explore some open and ongoing research directions for future work.

Graph Neural Networks (GNNs) have been proposed to learn graph representations for various graph mining tasks such as link prediction and node classification. These methods aggregate information from neighbors of a node to generate the node representation vector. Temporal GNN models consider the temporal and neighborhood information of nodes. However, few temporal GNN methods consider network substructures such as triads and cliques. In this paper, we present a temporal GNN-based method that generates node embeddings by aggregating neighbors of a node that exist in the maximal cliques of the graph containing the node. The reason for considering neighbors that form a maximal clique with the target node is that nodes in a maximal clique are highly connected to each other and most likely share similar characteristics. In addition, we consider the time dependency of nodes by generating temporal walks on the cliques such that in these walks the time order of the nodes is respected. The node embedding is based on the aggregation of the node’s temporal walks. Our experiments on seven datasets show the effectiveness of our method in both link prediction and node classification tasks. Furthermore, our method is faster than other baselines we evaluate.

Many real-world data are considered as graphs, such as computer networks, social networks and protein-protein interaction networks. Graph embedding methods are powerful tools for representing large graphs in various domains. A graph embedding method projects the components of a graph, such as its nodes or edges, into a vector space with a lower dimensionality than the adjacency matrix of the graph, and aims to preserve the characteristics of the graph. The generated embedding vectors have been utilized in various graph mining applications such as node classification, link prediction and anomaly detection. Despite the wide success of the graph embedding methods, little study has been done to facilitate a better understanding of the graph embeddings. In this paper, inspired by advancements in interpreting word embeddings, we propose two interpretability measures to quantify the interpretability of graph embeddings by leveraging useful network centrality properties and perform comparisons of different graph embedding methods. Using these scores, we can provide insights into the representational power of graph embedding methods.

Many real world networks are very large and constantly change over time. These dynamic networks exist in various domains such as social networks, traffic networks and biological interactions. To handle large dynamic networks in downstream applications such as link prediction and anomaly detection, it is essential for such networks to be transferred into a low dimensional space. Recently, network embedding, a technique that converts a large graph into a low-dimensional representation, has become increasingly popular due to its strength in preserving the structure of a network. Efficient dynamic network embedding, however, has not yet been fully explored. In this paper, we present a dynamic network embedding method that integrates the history of nodes over time into the current state of nodes. The key contribution of our work is 1) generating dynamic network embedding by combining both dynamic and static node information 2) tracking history of neighbors of nodes using LSTM 3) significantly decreasing the time and memory by training an autoencoder LSTM model using temporal walks rather than adjacency matrices of graphs which are the common practice. We evaluate our method in multiple applications such as anomaly detection, link prediction and node classification in datasets from various domains.

Network representation learning in low dimensional vector space has attracted considerable attention in both academic and industrial domains. Most real-world networks are dynamic with addition/deletion of nodes and edges. The existing graph embedding methods are designed for static networks and they cannot capture evolving patterns in a large dynamic network. In this paper, we propose a dynamic embedding method, dynnode2vec, based on the well-known graph embedding method node2vec. Node2vec is a random walk based embedding method for static networks. Applying static network embedding in dynamic settings has two crucial problems: 1) Generating random walks for every time step is time consuming 2) Embedding vector spaces in each timestamp are different. In order to tackle these challenges, dynnode2vec uses evolving random walks and initializes the current graph embedding with previous embedding vectors. We demonstrate the advantages of the proposed dynamic network embedding by conducting empirical evaluations on several large dynamic network datasets.