PaperlayerView exact revision on arXiv

Source-linked AI summary

A Survey on Graph Representation Learning Methods

Shima Khoshraftar, Aijun An

arXiv:2204.01855v2cs.LGcs.SI

TL;DR

Graph representation learning seeks effective vectors that capture graph structure and features for downstream tasks, while existing representations face scalability and information-preservation challenges. This survey reviews non-GNN and GNN-based embedding methods for static and dynamic graphs, synthesizes GNN limitations and solutions, and discusses applications and future directions. It provides a broad overview of methods and identifies ongoing challenges including expressive power, over-smoothing, and scalability.

  • Problem

    Effective graph representations are needed for downstream applications, but large adjacency matrices and time-consuming feature extraction may fail to represent all necessary graph information.

  • Method

    The survey reviews traditional non-GNN and GNN-based graph embedding methods for both static and dynamic graphs.

  • Results

    The survey covers methods across static and dynamic settings and synthesizes GNN limitations, proposed solutions, production applications, and future research directions.

  • Takeaways & Limitations

    The survey provides a consolidated view of graph embedding methods and ongoing research issues across traditional and GNN-based approaches.

  • Takeaways & Limitations

    GNNs have known limitations including expressive power, over-smoothing, and scalability.

Abstract

from arXiv · show

Graphs 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 are proposed for generating effective graph representation vectors. Two of the most prevalent categories of graph representation learning are graph embedding methods without using graph neural nets (GNN), which we denote as non-GNN based graph embedding methods, and graph neural nets (GNN) based methods. Non-GNN graph embedding methods are based on techniques such as random walks, temporal point processes and neural network learning methods. GNN-based methods, on the other hand, are the application of deep learning on graph data. In this survey, we provide an overview of these two categories and cover the current state-of-the-art methods for both static and dynamic graphs. Finally, we explore some open and ongoing research directions for future work.

1 INTRODUCTION

Graph representation learning addresses the need to represent complex, large, static, and evolving graphs effectively for downstream applications. This survey organizes traditional non-GNN and GNN-based embedding methods, reviews their limitations and applications, and identifies future research directions.

  • Graphs represent entities and relationships across domains including social networks, financial transactions, and biological networks.
  • Effective graph representations are important for downstream applications, but adjacency matrices can become very large and feature-extraction methods time consuming.
  • Traditional graph embedding methods use random walks, factorization, and non-GNN deep learning to preserve graph properties in lower-dimensional spaces.
  • GNNs obtain node embeddings by aggregating neighbor embeddings, with convolutional, spatial-temporal, and dynamic variants supporting evolving networks.
  • The survey reviews traditional and GNN-based methods for static and dynamic graphs, covering over 300 papers published since 2017 alongside influential earlier work.
  • It also summarizes GNN limitations, production applications, and future research directions, including expressive power, over-smoothing, scalability, over-squashing, and catastrophic forgetting.

2 GRAPHS

Graphs represent entities and relationships, but their size and application-specific structure make manual feature design and direct matrix representations difficult. Graph embedding addresses this by learning low-dimensional vectors for graph elements that preserve relevant similarities and support downstream tasks.

  • Graph foundations: Graphs model entities and relationships across domains including social networks, E-commerce, and citation networks.Examples include people and friendships in social networks, and users, items, and transactions in E-commerce.
  • Graph foundations: A graph is a tuple G = (V, E), where V contains vertices and E contains edges connecting vertex pairs.Graphs may be directed or undirected, and can be represented with adjacency, degree, and Laplacian matrices.
  • Graph foundations: Adjacency, degree, and Laplacian matrices encode graph connectivity, node degrees, and the relation L = D − A.Adjacency matrices may be weighted, while directed graphs distinguish incoming and outgoing degrees.
  • Graph embedding: Manual feature extraction is time-consuming, and important features may differ across applications or fail to represent the entire graph structure.The survey motivates graph embedding as automatic generation of graph representation vectors from graph structure and properties.
  • Graph embedding: Node, edge, and subgraph embedding map graph elements into low-dimensional vectors while preserving similarities in the embedding space.Node embeddings are the primary building block; edge vectors can be derived from pairs of node vectors, and subgraph vectors can aggregate node embeddings.
  • Applications: These representations support node classification, link prediction, graph classification, and anomaly detection.Applications include predicting node labels, estimating likely edges, and identifying anomalous nodes, edges, graphs, or times.
  • Applications: Anomaly detection often requires true node labels, but datasets containing such labels are scarce.Synthetic datasets that model real-world behavior are one approach described for alleviating this issue.

3 TRADITIONAL GRAPH EMBEDDING

Traditional graph embedding methods map nodes into lower-dimensional representations using approaches such as random walks, factorization methods, and temporal point processes. The survey organizes these methods across static and dynamic settings alongside GNN-based categories.

  • 3 TRADITIONAL GRAPH EMBEDDING: Traditional graph embedding maps nodes into lower dimensions using random walks, factorization methods, and temporal point processes.The survey reviews these methods in both static and dynamic graph settings.
  • 3 TRADITIONAL GRAPH EMBEDDING: Figure 2 categorizes static and dynamic traditional embedding methods.The figure presents the categories covered in this part of the survey.
  • 3 TRADITIONAL GRAPH EMBEDDING: Table 1 lists graph embedding methods in traditional and GNN-based categories.The table uses “Trad” for Traditional and “GNN” for GNN-based graph embedding.

3.1 Traditional Static Graph Embedding

Traditional static graph embedding methods represent fixed graphs by preserving structural properties such as node proximity. The survey groups them into factorization-based, random-walk-based, and non-GNN deep-learning methods.

  • Traditional static graph embedding methods target graphs with fixed nodes and edges and preserve properties such as node proximities.
  • The survey categorizes traditional static methods into factorization-based, random-walk-based, and non-GNN deep-learning approaches.
  • Factorization based: Factorization-based methods construct proximity matrices and apply dimension reduction, although fixed proximity measures may limit representation power.
  • Random walk based: Random-walk methods generate node sequences and train SkipGram models so nodes co-occurring in walks receive similar embeddings.
  • Random walk based: Node2vec controls random-walk behavior with p and q, combining breadth-first and depth-first exploration before SkipGram training.
  • Random walk based: DeepWalk and Node2vec reduce SkipGram computation through hierarchical softmax and negative sampling, respectively.
  • Non-GNN based deep learning: Non-GNN deep-learning methods include autoencoder approaches such as SDNE, which reconstruct adjacency information while capturing first- and second-order proximities.

3.2 Traditional Dynamic Graph Embedding

Traditional dynamic graph embedding methods model graphs that evolve through node and edge changes over time. The survey organizes them into aggregation-based, random-walk-based, non-GNN deep-learning, and temporal-point-process-based categories.

  • Dynamic graphs are modeled either as discrete-time snapshot sequences or as continuous-time edge and event sequences.
  • Dynamic graph embedding maps nodes into a lower-dimensional space, while graph evolution makes the task more challenging than static embedding.
  • The survey categorizes dynamic embedding methods as aggregation-based, random-walk-based, non-GNN deep-learning, and temporal-point-process-based.
  • Aggregation based: Temporal aggregation collapses graph evolution into one graph, but this loses timing information such as when an edge was created.
  • Aggregation based: Static-embedding aggregation applies embeddings to each snapshot and combines them, sometimes weighting older graphs less or predicting future embeddings with ARIMA.
  • Random walk based: Temporal random-walk methods select time-respecting edges and feed generated walks into SkipGram to produce temporal node representations.
  • Random walk based: DynNode2vec reuses and updates previous random walks and initializes common-node representations from earlier time points, saving time and aligning embeddings across snapshots.
  • Random walk based: EvoNRL updates affected walks after edge or node changes and uses indexing because walk updates are time consuming on large graphs.

4 GNN BASED GRAPH EMBEDDING

GNN-based graph embedding methods employ graph neural networks to generate embeddings. The survey distinguishes static, spatial-temporal, and dynamic GNN approaches and discusses their advantages and limitations.

  • GNN-based graph embedding methods use graph neural networks to generate graph embeddings.
  • Compared with traditional methods, GNN-based methods generalize well to unseen nodes and can better use node and edge attributes.
  • The survey covers static, spatial-temporal, and dynamic GNN methods and their real-world applications.
  • The section concludes by summarizing GNN limitations and proposed solutions to those limitations.

4.1 Introduction to GNNs

GNNs generate node embeddings by repeatedly aggregating neighborhood information, then use these representations for node-, edge-, or graph-focused prediction tasks. Their expressive power is bounded by the Weisfeiler–Lehman test, and graph-level implementations can face memory limitations.

  • Architecture: GNN layers update each node representation by applying learnable functions to its current embedding and aggregated neighbor embeddings.The neighborhood is defined by N(i), and stacking layers expands the node’s receptive field.
  • Training frameworks: GNNs support supervised, semi-supervised, and unsupervised training for node, edge, and graph prediction tasks.Unsupervised training can use node similarities obtained from random-walk co-occurrences.
  • Prediction tasks: Node-focused tasks use final-layer node representations, while edge-focused tasks compare pairs of node representations.Graph-focused tasks apply a readout or pooling operation to node representations to produce a graph vector.
  • Training frameworks: Supervised GNN training computes predictions from embeddings and uses labeled training nodes in the loss function.Transductive test nodes participate in GNN computation without contributing labels, whereas inductive test nodes are excluded from both computation and loss.
  • Implementation: Graph-level implementations reduce redundant neighbor computations and benefit from matrix multiplication, but operating on the whole graph may cause memory limitations.Methods to alleviate GNN memory complexity are discussed elsewhere in the survey.
  • Expressiveness: Message-passing GNNs are upper bounded by the Weisfeiler–Lehman test and therefore fail on some graph-isomorphism corner cases.Early GCN and GraphSAGE models also fail to distinguish some non-isomorphic graphs.

4.2 Static Graph Neural Nets

Static GNN methods learn representations for graphs that do not change over time, primarily through recurrent or convolutional architectures. Convolutional methods include spectral and spatial approaches, while recurrent methods iteratively update node states.

  • Overview: Static GNN-based graph embedding methods target graphs that do not change over time and comprise recurrent and convolutional GNNs.Convolutional GNNs use CNN-based layers, whereas recurrent GNNs use RNN-based layers.
  • Recurrent GNNs: Recurrent GNNs exchange information among neighboring nodes through repeated updates until a fixed point or bounded recurrence is reached.GGNN uses GRUs with a fixed number of recurrence steps, while IGNN iterates until convergence without limiting neighbor hops.
  • Recurrent GNNs: The original recurrent GNN can be time consuming for large iteration counts and produces representations described as overly smooth for node-level use.Its outputs are considered more suitable for graph representation than node representation.
  • Convolutional GNNs: Convolutional GNNs are divided into spectral methods based on graph signal processing and spatial methods based on message passing.The survey describes spatial methods as more preferred because of efficiency and flexibility.
  • Spectral methods: Spectral methods use graph filters derived from Laplacian eigenvectors, but eigenvalue decomposition creates computational complexity that later approximations address.GCN uses a first-order localized spectral-convolution approximation and a renormalized propagation rule.
  • Convolutional GNNs: Cardinality-preserved attention introduces neighbor-count information through Additive and Scaled models, and both models improve the representation.The cardinality value is mapped to a non-zero vector used in the Scaled model.

4.3 Spatial-Temporal Graph Neural Net (STGNN)

Spatial-temporal GNNs model graph structure and temporal behavior jointly for dynamic forecasting and classification. They combine graph convolutions or spatial layers with CNN-, RNN-, GRU-, or transformer-based temporal processing.

  • Overview: Spatial-temporal GNNs capture spatial and temporal properties by modeling dependencies between connected nodes over time.Applications include traffic-flow forecasting, epidemic forecasting, and sleep-stage classification.
  • Architectures: Most spatial-temporal GNNs combine graph convolution with either CNN-based or RNN-based temporal architectures.GCRN combines graph convolution with LSTM, while other models integrate graph convolution into CNNs or RNNs.
  • Architectures: Some models process graph sequences with a spatial GNN layer followed by GRU and transformer layers to capture temporal relations.The spatial layer captures relations within each graph, while subsequent layers process the sequence over time.
  • Traffic prediction: Traffic-prediction inputs contain feature matrices for previous time steps, with the goal of predicting feature matrices at future steps.Each feature matrix is N × d, where rows represent traffic features of sensors or roads.
  • Representative methods: Graph WaveNet uses a graph convolution block with diffusion convolution and self-adaptive adjacency, plus a gated dilated causal temporal convolution.The self-adaptive adjacency is learned from randomly initialized source and target node embeddings.
  • Fusion methods: Spatial-temporal fusion methods construct a combined graph to model spatial and temporal correlations rather than treating them separately.One described fusion graph uses spatial-neighbor, temporal-similarity, and temporal-connectivity matrices.

4.4 Dynamic Graph Neural Net (DGNN)

Dynamic GNNs represent graphs whose nodes, edges, or interactions evolve over time. Surveyed approaches model this evolution with temporal attention, recurrent updates, historical neighborhoods, memory modules, replay, or motif-based representations.

  • Overview: Dynamic GNNs model changing graph behaviors, including node and edge additions or deletions over time.They may represent dynamics as graph snapshots, edge streams, or incremental graph changes.
  • Snapshot-based methods: DySAT applies a structural attention block to each graph snapshot and a temporal self-attention block over historical node representations.Its final embedding is generated by attending to earlier representations of the same node.
  • Historical neighborhoods: EHNA captures node evolution by generating weighted temporal random walks, encoding each walk with LSTM, and aggregating the walk encodings.Walk transition probabilities depend on edge weight and time.
  • Memory-based methods: TGN models dynamic graphs as edge streams using node memory, message functions, message aggregation, memory updates, and temporal embedding modules.Memory stores compressed node history and is updated when new edges occur; the embedding module can update nodes even without new interaction.
  • Streaming methods: Streaming GNN training combines a new-change loss with an existing-information loss to learn from graph updates while preserving prior information.Influenced nodes and important historical nodes are replayed, and parameters are constrained not to deviate drastically from the previous time.
  • Temporal attention: TGAT adds temporal ordering to attention by assuming more recent neighbors are likely to have greater influence and concatenating time vectors with node features.Its time features map time into R^d using learnable parameters.
  • Temporal motifs: CAW-N predicts future link probability from anonymized temporal walks that encode motif evolution and are aggregated before an MLP.Its assumption is that nodes whose motif structures interact over time have higher future-link probability.
  • Temporal motifs: MTSN combines a motif-preserving encoder with a temporal shift component to preserve high-order similarity and capture temporal evolution.The encoder combines outputs from simplified GCNs applied separately to adjacency and motif matrices.

4.5 GNN-based method’s real-world applications

The survey identifies real-world production applications of graph neural nets across several domains.

  • Table 3 presents real-world applications of graph neural nets deployed in production across several domains.

4.6 The limitation of GNNs and the proposed solutions

The survey organizes major GNN limitations and reviews proposed solutions, covering expressive power, depth-related issues, scalability, and long-range dependencies.

  • Overview: GNNs face limitations in expressive power, oversmoothing, and scalability.
  • Expressive power: Common GNNs have expressive power bounded by the WL test and may fail to distinguish certain non-isomorphic substructures.
  • Expressive power: GIN increases expressive power by using sum aggregation, which can distinguish neighbor multiplicities that mean and max aggregation may merge.
  • Oversmoothing: Oversmoothing causes local node information to be lost as additional layers propagate representations across increasingly distant neighbors.
  • Scalability: Scalability is constrained because large neighborhood counts reduce training speed and increase memory consumption.
  • Scalability: Sampling neighbors or subgraphs, removing nonlinearities, reversible connections, and graph-model sparsification are proposed to reduce GNN cost.
  • Long-range dependencies: Increasing GNN depth to capture long-range dependencies encounters oversmoothing, motivating transformer modules and alternative propagation designs.

5 OPEN ISSUES AND ONGOING RESEARCH

The survey identifies open issues in GNN theory, limitation mitigation, data scarcity, domain knowledge, cross-domain transfer, and broader applications.

  • GNN limitations: Future work includes developing solutions for GNN limitations, especially because over-squashing solutions remain preliminary and dynamic settings are underexplored.
  • Theory: Theoretical analyses of GNN optimization properties and generalization across graph sizes remain less understood.
  • New GNN designs: PDE-based GNNs have been used to model graph information propagation and can address oversmoothing limitations.
  • Domain knowledge: Domain knowledge can be incorporated through the input, loss function, or model architecture, but this area remains new.
  • Training data: Limited labels motivate further study of self-supervised learning, data augmentation, and contrastive learning for static and dynamic GNNs.
  • Broader directions: Future directions include transferring advances from computer vision and natural language processing, studying dynamic graphs, and expanding GNN applications.

6 CONCLUSION

The survey reviews traditional and GNN-based node and graph embedding methods across static and dynamic graphs, summarizes GNN limitations and solutions, and identifies future research directions.

  • Scope: The survey divides node and graph embedding methods into traditional and GNN-based approaches.
  • Traditional methods: Traditional static methods include factorization, random walks, and non-GNN deep learning, while dynamic methods model evolving node histories.
  • GNN methods: GNNs generate node representations by aggregating neighboring node embeddings.
  • Limitations: The survey summarizes nine GNN limitations, including expressive power, oversmoothing, scalability, over-squashing, long-range dependencies, and catastrophic forgetting.
  • Future directions: It identifies future directions involving limitation mitigation, limited-label learning, transfer from deep learning, and GNN theory.
  • Conclusion: The authors position the survey as up-to-date additional information for researchers in graph representation learning.
Loading 2204.01855v2…