PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph Representation Learning: A Survey

Fenxiao Chen, Yuncheng Wang, Bin Wang, C. -C. Jay Kuo

arXiv:1909.00958v1cs.LGcs.SIstat.ML

TL;DR

Graph representation learning addresses the challenge of representing irregular, high-dimensional graph data in compact vectors that preserve intrinsic properties. This survey reviews graph embedding techniques, evaluates them across small and large datasets, and provides a unified library. In the reported evaluations, random-walk methods perform strongly across several tasks, while performance can depend substantially on embedding dimension and computational demands.

  • Problem

    Irregular, high-dimensional graph data are difficult to analyze, motivating representations that preserve intrinsic graph properties in lower-dimensional vectors.

  • Method

    The paper surveys classical, neural-network-based, hypergraph, and attention graph embedding methods and evaluates several state-of-the-art approaches on small and large datasets.

  • Results

    Random-walk-based methods are top performers for vertex classification on Cora and Wiki and provide the best clustering results on the evaluated large graph datasets.

  • Takeaways & Limitations

    The survey offers comparative guidance on graph embedding methods and a unified open-source library for the methods discussed and evaluated.

Abstract

from arXiv · show

Research on graph representation learning has received a lot of attention in recent years since many data in real-world applications come in form of graphs. High-dimensional graph data are often in irregular form, which makes them more difficult to analyze than image/video/audio data defined on regular lattices. Various graph embedding techniques have been developed to convert the raw graph data into a low-dimensional vector representation while preserving the intrinsic graph properties. In this review, we first explain the graph embedding task and its challenges. Next, we review a wide range of graph embedding techniques with insights. Then, we evaluate several state-of-the-art methods against small and large datasets and compare their performance. Finally, potential applications and future directions are presented.

I. INTRODUCTION

Graph representation learning maps graph data into lower-dimensional vectors while preserving structural properties, enabling downstream analysis. The survey introduces the task, its challenges, embedding objectives, and supporting computational techniques.

  • I. INTRODUCTION: Real-world graph data are challenging to represent because choosing an appropriate embedding dimension is difficult.The introduction identifies embedding dimension as one of three challenges in obtaining an accurate graph representation.
  • I. INTRODUCTION: The survey reviews a wide range of graph embedding methods and evaluates them systematically on small and large datasets.It aims to provide newcomers with a global perspective and compares methods under common settings.
  • I. INTRODUCTION: The Graph Representation Learning Library provides a unified interface for the graph embedding methods discussed and evaluated in the paper.The authors describe GRLL as covering the largest number of graph embedding techniques up to that time.
  • I. INTRODUCTION: Graph representation learning maps graph data into vectors that preserve relationships or structural properties for downstream machine-learning tasks.Applications include node classification, link prediction, clustering, community detection, and behavior analysis.
  • I. INTRODUCTION: Graph embedding objectives include preserving first-order proximity between directly connected vertices and second-order proximity between vertices with similar neighborhoods.First-order proximity uses edge relationships, whereas second-order proximity captures shared neighborhood structure.
  • I. INTRODUCTION: Negative sampling reduces large-scale optimization cost by contrasting observed neighbors with sampled negative examples.It avoids summing over the entire vertex set during graph optimization.

B) Graph Input

Graph embedding methods accept several graph types, ranging from homogeneous and heterogeneous graphs to graphs enriched with auxiliary information. Feature matrices and similarity matrices can supplement structural input for graph classification.

  • B) Graph Input: Homogeneous graphs contain one node type and one edge type, with nodes and edges treated equally.This is the basic graph-input setting described by the survey.
  • B) Graph Input: Heterogeneous graphs contain multiple edge types representing different relations among entities or categories.Examples include community-based question answering sites, multimedia networks, and knowledge graphs.
  • B) Graph Input: Graphs with auxiliary information include labels, attributes, node features, or dynamic information propagation beyond basic structure.Labels indicate categories, attributes add discrete or continuous information, and node features may be textual.
  • B) Graph Input: A feature matrix X ∈ R^|V|×N stores an N-dimensional feature vector for each training instance, while S can encode pairwise feature similarity.The similarity matrix is described for graph-classification tasks.

C) Graph Output

Graph embedding outputs are task-dependent vector representations, while the survey organizes methods by dimensionality reduction, random walks, and classical linear or nonlinear techniques. These approaches preserve variance, distances, local structure, or graph-context information in different ways.

  • C) Graph Output: Graph embedding outputs may represent nodes, edges, combinations of graph elements, or whole graphs, depending on the application and task.Node embeddings support clustering and classification, while edge embeddings support link prediction.
  • C) Graph Output: The survey traces graph embedding from early planar-graph embedding problems to methods designed for general real-world graphs.Most real-world graphs are not planar, motivating broader approaches.
  • C) Graph Output: Dimensionality-reduction methods map high-dimensional graph data into lower-dimensional spaces, although classical dimensionality reduction is less scalable.Classical methods are categorized into linear and nonlinear approaches.
  • C) Graph Output: Random walks generate paths that expose connected-vertex context and can capture both local and global graph structure.Later probability models such as skip-gram use these contextual sequences for embedding.
  • C) Graph Output: PCA finds a linear transformation maximizing data variance, while LDA maximizes the ratio between inter-class and intra-class scatter.MDS instead preserves pairwise spatial dissimilarities in a lower-dimensional mapping.
  • C) Graph Output: Linear subspace-learning methods may fail when the underlying data are highly nonlinear, motivating nonlinear dimensionality reduction for manifold learning.NLDR methods aim to learn nonlinear topology automatically.
  • C) Graph Output: Isomap preserves pairwise geodesic distances, whereas LLE preserves the local linear structure of nearby feature vectors.Isomap constructs a neighborhood graph, computes shortest paths, and applies MDS.

B) Random-Walk-Based Methods

Random-walk methods sample paths from random starting nodes to capture local and global graph structure, then learn node vectors from path contexts. Related matrix-factorization methods preserve proximity, high-order transitions, text features, or structural homophily through factorization objectives.

  • Random-walk embedding: Random walks generate paths whose neighboring-vertex contexts support skip-gram or bag-of-words models for learning node representations.Randomness enables exploration of both local and global structure.
  • Random-walk embedding: DeepWalk defines a vertex’s context using nodes within a window in randomly sampled sequences and maximizes the average logarithmic probability of context pairs.
  • Random-walk embedding: DeepWalk is equivalent to factoring a matrix whose entries encode logarithmic average reachability probabilities, while W represents the vertices.
  • Random-walk embedding: node2vec balances depth-first and breadth-first exploration using return parameter p and in-out parameter q to trade off local and global structure.Small p can trap walks in loops, while small q makes walks more DFS-like.
  • Matrix-factorization-based methods: Matrix-factorization methods include graph factorization, proximity-preserving approaches, text-enhanced TADW and HSCA, and GraRep’s high-order transition matrices.TADW incorporates vertex text features, HSCA adds homophily-related modeling, and GraRep multiplies the adjacency matrix to obtain k-th order transitions.
  • Matrix-factorization-based methods: Regularized factorization objectives can constrain embedding rank, preserve structural homophily, or make connected nodes close in the learned representation.

A) Neural-Network-Based Methods

Neural-network-based graph embedding adapts ideas from RNNs and CNNs to learn representations directly from graph structure and node features. The reviewed methods include convolutional, autoencoding, signed-graph, inductive, and proximity-preserving models.

  • Overview: Neural graph embedding was inspired by RNN and CNN representation learning, including Word2Vec and skip-gram neighborhood-preserving objectives.
  • Graph convolutional methods: GCN performs iterative neighbor aggregation with graph convolutions and supports end-to-end learning on graphs of arbitrary size and shape.It is widely used for semi-supervised learning on graph-structured data.
  • Graph convolutional methods: GCN includes self-loops and degree normalization, and its spectral formulation connects it to the Graph Laplacian on non-Euclidean domains.
  • Specialized neural models: SGCN extends graph convolution to signed links, while VGAE uses a GCN encoder and inner-product decoder to reconstruct neighborhood information.
  • Proximity-preserving methods: SDNE learns low-dimensional structure-preserving representations by modeling both first-order and second-order vertex proximities with CNNs.Its objective includes an L2 regularizer to reduce overfitting.

B) Large Graph Embedding Methods

Large-graph methods address scalability through memory-reducing subgraph selection and feature aggregation, while hypergraph methods represent higher-order relations among multiple nodes. The survey reviews spectral, neural, and autoencoder approaches for hypergraph embedding and highlights their modeling flexibility and challenges.

  • Large graph embedding methods: Large-graph embedding methods are introduced specifically to address scalability issues.
  • Large graph embedding methods: LGCL ranks neighboring features independently for each dimension, forms a (k + 1) × n grid with the target node, and applies a conventional CNN.For k = 4, the four largest neighbor values 9, 6, 5, and 3 are selected in the example.
  • Large graph embedding methods: LGCL uses subgraph selection to reduce memory and resource requirements when embedding large-scale graphs.The process begins from Ninit = 3 randomly sampled central nodes in the described example.
  • Hypergraph embedding: Hypergraphs connect more than two nodes through hyperedges, which can also be viewed as supernodes, enabling richer community and multimodal-data modeling than simple graphs.Their multiple-node relationships also make hypergraphs more challenging to represent.
  • Hypergraph embedding: A hypergraph is represented by an incidence matrix H of dimension |V| × |E|, with entries indicating vertex–hyperedge incidence.
  • Hypergraph embedding: Reviewed hypergraph embeddings include spectral Laplacian eigenvector methods, HGNN spectral convolution, and DHNE autoencoding with second-order and N-tuplewise structural preservation.

D) Attention Graph Embedding

Attention-based graph embedding focuses learning on task-relevant neighboring nodes by assigning normalized attention weights. Reviewed methods apply this idea to graph convolution, random walks, and recursive neural networks, although attention does not always improve accuracy.

  • Attention mechanisms assign weights to neighboring nodes so learning can focus on task-relevant graph regions and reduce noisy information.For a target node t, weights α_i lie in [0, 1] and sum to 1 over its neighbors.
  • Graph Attention Networks use masked self-attention to compute neighbor attention coefficients before transforming and aggregating node features.The transformed neighbor features are concatenated and passed through a LeakyReLU activation.
  • AttentionWalks guides random-walk-based representation learning by steering walks toward broader or narrower neighborhoods through trainable attention parameters.The walk distribution matrix records expected visits between nodes.
  • AGRNN applies soft attention to graph-based recursive neural networks, controlling how information from sampled k-step neighbors reaches a target vertex.Neighbor representations are aggregated to form the target vertex’s hidden state.
  • Attention does not consistently increase graph embedding accuracy across neural network models.

E) Others •

Other graph embedding approaches include adversarial models that learn connectivity distributions and weakly supervised multimodal models for large social knowledge graphs. These methods support different representation-learning and generative objectives.

  • GraphGAN formulates graph representation learning as a minimax game between generative and discriminative models.Its generator models the connectivity probability among vertices connected to a target vertex.
  • GenVector uses large-scale unlabeled data and a multimodal Bayesian embedding model to learn representations for large social knowledge graphs.The approach is framed as weakly supervised learning solved with unsupervised techniques.
  • GenVector can generate continuous word embeddings and graph-based user embeddings using latent discrete topic variables.This combines topic-model and word-embedding advantages in a generative model.

V. EVALUATION

The evaluation compares graph embedding methods primarily through vertex classification, using benchmark citation and social-network datasets spanning small and large scales. Dataset summaries cover graph structure, node attributes, labels, and application settings.

  • The evaluation uses vertex classification to compare graph embedding methods, while link prediction is identified as another common task.Vertex classification assigns node labels from information learned from other labeled nodes.
  • The paper describes benchmark datasets and conducts vertex-classification experiments on both small and large graphs.
  • Benchmark datasets include small citation graphs such as Citeseer, Cora, and PubMed, whose nodes contain paper-content attributes and citation links.Citeseer contains papers from six categories with binary word-vector attributes.
  • Large datasets include BlogCatalog, YouTube, Facebook, and Flickr, representing social relationships, user groups, postings, or links at different scales.YouTube contains 1,157,827 nodes and 4,945,382 edges, while Facebook is used for link prediction.
  • Table 2 summarizes the parameters of the representative graph datasets used in the evaluation.

C) Evaluation Results and Analysis

The survey evaluates graph embedding methods across classification, clustering, training time, and embedding dimension. Random-walk methods generally combine strong performance with lower resource demands, while other methods can be more sensitive to dimensionality or scale.

  • The survey provides a unified evaluation under common settings and releases the Graph Representation Learning Library for the evaluated methods.The library offers a unified interface and covers a large collection of graph embedding techniques.
  • 1) Vertex Classification: DeepWalk and node2vec achieve the highest vertex-classification accuracy on Cora and Wiki, with random-walk methods occupying the top three positions.GraRep is less practical for larger graphs because it usually requires substantially more memory.
  • 2) Clustering Quality: DeepWalk and node2vec provide the best clustering results on YouTube, Flickr, and BlogCatalog using Macro-F1 and Micro-F1 scores.GraRep offers comparable quality on BlogCatalog but has very high memory requirements.
  • 3) Time Complexity: DeepWalk requires significantly less training time than node2vec and LINE on larger datasets such as YouTube and Flickr.The comparison considers training time alongside embedding quality.
  • 4) Influence of Embedding Dimensions: Reducing embedding dimension lowers performance because less input-graph information is preserved.
  • 4) Influence of Embedding Dimensions: About 20% performance degradation occurs for node2vec and DeepWalk when Wiki embedding dimensions decrease from 128 to 4, compared with as much as 45% for LINE, GraRep, and GF.SDNE performance remains about the same across embedding dimensions.

5) Influence of Training Sample Ratio

Graph representation learning supports applications ranging from community detection to multimodal analysis, while the survey evaluates methods, discusses future directions, and examines training-data effects.

  • 5) Influence of Training Sample Ratio: Training-sample ratios between 0.2 and 0.8 yield consistent performance for most methods on Cora.SDNE and GCN are exceptions, with accuracy declining at lower training ratios.
  • 5) Influence of Training Sample Ratio: SDNE and GCN require larger amounts of training data because their accuracy drops when the training ratio is low.The experiment uses a simple linear regression classifier, and the analysis is classifier dependent.
  • Applications: Graph representation learning can model relational data and support community detection, behavior analysis, and node classification.Graph representations store relational knowledge of interacting entities efficiently.
  • Future Research Directions: Deep graph embedding remains challenging because deeper GCNs can suffer significant performance drops from graph Laplacian over-smoothing.The survey notes that shallow GCNs primarily capture one-hop and second-order proximity, making global information difficult to learn.
  • Survey Scope: The survey reviews graph embedding methods, evaluates state-of-the-art techniques on small and large datasets, and presents applications and future research directions.Its coverage includes neural-network-based, hypergraph, and attention graph embedding methods, along with the GRLL library.
Loading 1909.00958v1…