PaperlayerView exact revision on arXiv

Source-linked AI summary

Representation Learning on Graphs: Methods and Applications

William L. Hamilton, Rex Ying, Jure Leskovec

arXiv:1709.05584v3cs.SIcs.LG

TL;DR

Learning from graph-structured data requires representations that machine-learning models can use; this review unifies approaches for embedding nodes and subgraphs in a conceptual framework. It reports that representation-learning methods have consistently pushed the state of the art on node classification and link prediction.

  • Problem

    Machine-learning applications use graph-structured data for prediction and pattern discovery, making representations of graph structure that models can exploit a central challenge.

    Source: §1 · p. 1

  • Method

    The review synthesizes node- and subgraph-embedding methods in a unified conceptual framework that organizes approaches and highlights their conceptual distinctions.

    Source: §1 · pp. 2–3

  • Results

    Representation-learning approaches have consistently pushed the state of the art on node classification and link prediction.

    Source: §4 · p. 20

  • Takeaways & Limitations

    Representation learning offers an alternative to traditional feature engineering for machine learning on graphs.

    Source: §4 · p. 20

    The field still lacks a consistent theoretical framework or set of frameworks that precisely delineate the goals of representation learning on graphs.

    Source: §4.1 · p. 20

Abstract

from arXiv · show

Machine learning on graphs is an important and ubiquitous task with applications ranging from drug design to friendship recommendation in social networks. The primary challenge in this domain is finding a way to represent, or encode, graph structure so that it can be easily exploited by machine learning models. Traditionally, machine learning approaches relied on user-defined heuristics to extract features encoding structural information about a graph (e.g., degree statistics or kernel functions). However, recent years have seen a surge in approaches that automatically learn to encode graph structure into low-dimensional embeddings, using techniques based on deep learning and nonlinear dimensionality reduction. Here we provide a conceptual review of key advancements in this area of representation learning on graphs, including matrix factorization-based methods, random-walk based algorithms, and graph neural networks. We review methods to embed individual nodes as well as approaches to embed entire (sub)graphs. In doing so, we develop a unified framework to describe these recent approaches, and we highlight a number of important applications and directions for future work.

1 Introduction

Graph machine learning must encode high-dimensional, non-Euclidean graph structure for prediction and pattern discovery. Representation learning instead learns low-dimensional embeddings of nodes or subgraphs, and this review organizes recent approaches in a unified framework.

1 Introduction

  • Graph-structured data supports tasks such as protein-role classification, friend recommendation, and predicting therapeutic uses of drugs, but its structure is difficult to encode as model features.Relevant structural information can include pairwise properties, a node’s global position, and its local neighborhood structure.Source: §1 · pp. 1–2
  • Traditional graph statistics [6], kernels, and engineered local features are inflexible and costly to design, whereas representation learning optimizes low-dimensional embeddings to encode graph structure.The learned node or subgraph embeddings can then serve as feature inputs for downstream machine learning tasks.Source: §1 · p. 2
  • The review covers recent node- and subgraph-representation methods, unifies research across subfields, and focuses on scalable, deep-learning-inspired approaches rather than several related research areas.It emphasizes conceptual distinctions and does not review in detail latent space models, statistical relational learning, manifold learning, or geometric deep learning.Source: §1 · pp. 2–3

1.1 Notation and essential assumptions

  • Most reviewed methods map nodes or subgraphs to vectors z ∈ R^d from an undirected graph’s adjacency matrix A and optionally node attributes X; most are unsupervised, while some use node- or subgraph-level labels.The embedding dimension satisfies d << |V|; labels can be classification or regression targets for supervised approaches.Source: §1.1 · p. 3

2 Embedding nodes

Node embedding represents each graph node as a low-dimensional vector summarizing its position and local neighborhood. The vectors’ geometric relations can encode graph interactions such as edges.

2 Embedding nodes

  • Node embeddings are low-dimensional vectors that summarize each node’s graph position and local neighborhood structure.They can be viewed as projecting nodes into a latent space.Source: §2 · p. 4
  • In the latent space, geometric relations between node embeddings correspond to interactions such as edges in the original graph.Source: §2 · p. 4
  • Figure 2 visualizes two-dimensional embeddings of Zachary’s Karate Club network, capturing its implicit community structure.Source: §2 · p. 4

2.1 Overview of approaches: An encoder-decoder perspective

The section introduces a unified encoder-decoder framework for organizing node embedding methods. It frames their methodological differences in terms of how they define similarity, encoding, decoding, and loss.

2.1 Overview of approaches: An encoder-decoder perspective

  • The framework maps nodes to low-dimensional embeddings and decodes graph structure from them, with methods distinguished mainly by their definitions of similarity, encoder, decoder, and loss.The embeddings are intended to retain information useful for downstream machine learning when graph information can be decoded from them.Source: §2.1 · pp. 4–5
  • Most approaches train embeddings by minimizing reconstruction error for pairwise node similarities, which may represent adjacency or random-walk co-occurrence [28, 47].A user-specified loss compares decoded similarity estimates with graph-based target values over training node pairs.Source: §2.1 · pp. 4–5
  • After optimization, the trained encoder produces node embeddings that can serve as features for downstream machine learning tasks.Examples include community classification and friendship-link recommendation [3] [28].Source: §2.1 · p. 5

2.1.1 Notes on optimization and implementation details

  • Methods generally optimize encoder parameters with a loss analogous to the framework objective, usually using stochastic gradient descent, while some allow closed-form matrix-decomposition solutions.The review emphasizes high-level methodological differences rather than optimization specifics; some methods also add auxiliary objectives or regularizers or optimize decoder parameters.Source: §2.1.1 · p. 5

2.2 Shallow embedding approaches

Shallow graph embeddings learn a vector for each node by optimizing an embedding matrix directly. Their methods include matrix-factorization approaches based on deterministic similarities and random-walk approaches based on stochastic co-occurrence.

2.2 Shallow embedding approaches

  • Shallow embedding methods map each node to a learned vector through an embedding lookup, with the embedding matrix itself as the trainable parameters.The encoder selects a column of Z using the node’s one-hot indicator vector.Source: §2.2 · p. 6

2.2.1 Factorization-based approaches

  • Matrix-factorization methods use inner-product decoders and MSE losses, with Graph Factorization, GraRep, and HOPE differing chiefly in their node-similarity measures.Graph Factorization uses adjacency, GraRep uses powers of adjacency to capture higher-order similarity, and HOPE supports general measures such as Jaccard neighborhood overlap.Source: §2.2.1 · p. 7

2.2.2 Random walk approaches

  • DeepWalk and node2vec optimize inner-product embeddings to reflect stochastic, asymmetric probabilities of visiting nodes on short random walks, typically of length 2–10.DeepWalk uses unbiased walks; node2vec’s p and q parameters tune revisiting and neighborhood exploration, trading off community structure against local structural roles [28]. DeepWalk uses hierarchical softmax, whereas node2vec uses negative sampling to approximate its loss.Source: §2.2.2 · pp. 8–9
  • LINE combines probabilistic objectives for first-order adjacency similarity and second-order two-hop neighborhood similarity, optimized with KL-divergence-derived losses.Unlike DeepWalk and node2vec, LINE explicitly factorizes first- and second-order similarities rather than combining them in fixed-length random walks.Source: §2.2.2 · p. 9
  • HARP [13] coarsens a graph, embeds the resulting supernodes with DeepWalk, node2vec, or LINE, then uses those embeddings to initialize finer-level optimization.The hierarchical process can repeat at different coarseness levels and has consistently improved the performance of those methods [13].Source: §2.2.2 · p. 9
  • Other random-walk extensions use skip- or hop-based walks to learn GraRep-like similarity [48], or replace node2vec’s Euclidean inner-product decoder with a hyperbolic distance [11].Source: §2.2.2 · p. 9

2.3 Generalized encoder-decoder architectures

Generalized encoder-decoder methods replace node-ID lookup encoders with encoders that use graph structure and, in some approaches, node attributes. Neighborhood autoencoders compress whole-graph similarity vectors, while neighborhood aggregation builds node representations from local neighborhoods.

2.3 Generalized encoder-decoder architectures

  • Shallow embeddings share no encoder parameters across nodes, omit node attributes, and are transductive, limiting their use on evolving or unseen graphs.Their parameter count grows as O(|V|), and unseen nodes require additional optimization.Source: §2.3 · p. 9
  • Generalized approaches retain the encoder-decoder framework but use more complex encoders, often deep neural networks dependent on graph structure and attributes.Neighborhood autoencoders address shallow encoders’ lack of structural input, while aggregation encoders depend on local neighborhoods rather than the entire graph.Source: §2.3 · p. 10, §2.3.1 · p. 10, §2.3.2 · p. 11

2.3.1 Neighborhood autoencoder methods

  • DNGR and SDNE use deep autoencoders to encode each node’s whole-graph neighborhood-similarity vector, reconstructing it through a unary decoder.DNGR derives similarities from pointwise mutual information of random-walk co-occurrences; SDNE uses adjacency vectors and combines reconstruction with the Laplacian eigenmaps objective. Their fixed |V|-dimensional inputs and architectures remain costly and transductive, preventing generalization to evolving or new graphs.Source: §2.3.1 · pp. 10–11

2.3.2 Neighborhood aggregation and convolutional encoders

  • Neighborhood-aggregation encoders initialize node representations from attributes, then iteratively combine each node’s representation with aggregated neighbor representations, compressing information gathered over K iterations.When attributes are unavailable, methods can use graph statistics such as degree [29] or one-hot node indicators [36] [53].Source: §2.3.2 · pp. 11–12
  • GraphSAGE, GCNs, and column networks differ in their aggregation and combination functions: GraphSAGE concatenates representations, while GCNs and column networks use weighted sums.GraphSAGE permits several aggregators; column networks also interpolate to retain local information as aggregation reaches farther through the graph.Source: §2.3.2 · pp. 12–13
  • Neighborhood-aggregation encoders consistently improve on shallow counterparts in node-classification and link-prediction benchmarks while addressing shallow embeddings’ four main limitations.They incorporate graph structure and node attributes, can use sub-linear parameter dimensions, and can embed nodes not seen during training.Source: §2.3.2 · p. 13

2.4 Incorporating task-specific supervision

The default encoder-decoder framework learns unsupervised by reconstructing graph-based pairwise similarities, but node embedding methods can also use task-specific supervision, commonly from node classification.

2.4 Incorporating task-specific supervision

  • Neighborhood-aggregation methods can incorporate task-specific supervision [29] [35] [53], most commonly from node classification tasks.Source: §2.4 · p. 13
  • For binary node labels, embeddings feed a sigmoid classifier with trainable parameters, and cross-entropy compares predicted probabilities with true labels.The setup extends to more complex classification settings.Source: §2.4 · p. 13
  • Task-specific gradients backpropagate through the encoder, and classification loss can replace decoder reconstruction [29] [35] or accompany it.Source: §2.4 · p. 13

2.5 Extensions to multi-modal graphs

Real-world graphs may have heterogeneous node and edge types or multiple layers; this section surveys methods for representing those structures.

2.5.1 Dealing with different node and edge types

  • Different node types can use different encoders, while edge-type-specific bilinear decoders use learned parameters [53] that can be regularized for many relations.The passage notes that regularization can be useful when embedding knowledge graphs with many edge types.Source: §2.5.1 · pp. 13–14
  • Dong et al. sample heterogeneous-graph random walks restricted to transitions between particular node types, complementing type-specific encoders and decoders.This enables methods based on random walks to be applied to heterogeneous graphs.Source: §2.5.1 · p. 14

2.5.2 Tying node embeddings across layers

  • OhmNet augments node2vec’s embedding loss with a penalty tying the same node’s embeddings across layers, then extends regularization recursively across parent-child layers.This approach shares information between a node’s embeddings in different layers and can exploit hierarchies among graph layers.Source: §2.5.2 · p. 15

2.6 Embedding structural roles

Structural-role embeddings capture nodes’ roles independently of their global graph positions, which can matter in communication and transportation networks. The section describes struc2vec’s auxiliary-graph walks and GraphWave’s spectral approach to learning such representations.

2.6 Embedding structural roles

  • Structural roles can matter more than graph proximity in some tasks, and node2vec can better capture roles by biasing its random walks.The section introduces struc2vec and GraphWave [20] as approaches specifically designed to capture structural roles.Source: §2.6 · p. 15
  • struc2vec builds weighted auxiliary graphs from k-hop neighborhood degree-sequence similarities, then runs biased walks over them as input to node2vec.The sequence distance can be computed using dynamic time warping.Source: §2.6 · p. 15
  • GraphWave [20] uses spectral graph wavelets and heat kernels on the graph Laplacian to compute a vector for each node’s structural role.Its vectors implicitly relate to topological quantities including node degree and the number of k-cycles containing that node; an appropriate heat-kernel scale helps capture role information.Source: §2.6 · pp. 15–16
  • On the synthetic barbell graph, RolX [30], struc2vec, and GraphWave distinguish the barbell ends, but only GraphWave correctly differentiates all structural roles.GraphWave maps structurally equivalent nodes to the same embedding position.Source: Figure 9 · p. 16

2.7 Applications of node embeddings

Node embeddings serve four common uses—visualization, clustering, node classification, and link prediction—across domains from computational social science to biology.

Visualization and pattern discovery

  • Embeddings enable 2D graph visualizations with t-SNE or PCA, helping reveal communities and other hidden structures.Because nodes are represented as real-valued vectors, generic high-dimensional visualization methods can be applied.Source: §2.7 · p. 16

Node classification and semi-supervised learning

  • Semi-supervised node classification uses labels from a small seed set to label the graph, while inductive classification targets unseen nodes (Hamilton et al. [29]).Applications include classifying proteins by biological function [28] and documents, videos, web pages, or individuals into categories or communities [28] [35].Source: §2.7 · pp. 16–17

Clustering and community detection

  • Embeddings support clustering with generic algorithms such as k-means or DB-scan, capturing functional or structural roles beyond community structure.Applications include discovering related drugs or products [23].Source: §2.7 · p. 16

Link prediction

  • Link prediction uses embeddings to predict missing or future edges, supporting recommendations and expansion of incomplete biological interaction datasets [3].Examples include predicting friendships, user–movie affinities [56], and missing knowledge-graph relations; biological graphs may be noisy because they rely on costly experiments.Source: §2.7 · p. 17

3 Embedding subgraphs

Subgraph embedding learns a low-dimensional vector for an induced subgraph or an entire graph, enabling predictions about that structure. The section reviews ways to construct these representations, chiefly by aggregating node embeddings or using graph neural networks.

3.1 Sets of node embeddings and convolutional approaches

  • Convolutional subgraph methods build node embeddings through neighborhood aggregation, then add modules to combine the embeddings of nodes in each subgraph.Their main distinction is how they aggregate the node embeddings.Source: §3.1 · p. 17

3.1.1 Sum-based approaches

  • Convolutional molecular fingerprints sum the node embeddings in a subgraph [21], while Dai et al. [16] also use a sum-based encoder and propose a Loopy Belief Propagation alternative.Dai et al. connect their sum-based approach to mean-field inference, viewing neural message passing as a differentiable alternative to graphical-model message passing.Source: §3.1.1 · p. 18

3.1.2 Graph-coarsening approaches

  • Defferrard et al. [18] and Bruna et al. [8] repeatedly cluster nodes, max-pool their embeddings, and apply convolution to the resulting coarser graph.Their spectral approaches use the graph Fourier transform; naive versions are O(|V|^3), while Chebyshev approximations resemble neighborhood aggregation.Source: §3.1.2 · p. 18

3.1.3 Further variations

  • Kearnes et al. [34] aggregate node embeddings with fuzzy histograms and edge-embedding layers, while Neipert et al. order and concatenate nodes before a CNN.The ordering may be problem-specific or produced by a vertex-coloring algorithm.Source: §3.1.3 · p. 18

3.2 Graph neural networks

  • The original GNN framework recursively passes neighbor messages until embeddings converge, requiring its differentiable update function to be a contraction map.After K iterations, a differentiable function maps the converged node embeddings to output embeddings; the convergence and contraction requirements are limitations.Source: §3.2 · p. 19
  • Gated Graph Neural Networks [39] use recurrent units to avoid convergence iterations, and MPNNs [25] generalize them and earlier convolutional approaches with message and update functions.Gated Graph Neural Networks can initialize from node attributes and use intermediate subgraph embeddings; MPNNs can incorporate edge features. Subgraph embeddings can use earlier aggregation procedures or a connected dummy super-node.Source: §3.2 · p. 19

3.3 Applications of subgraph embeddings

  • Subgraph embeddings are primarily used for classification, especially of molecular properties, and also for image classification, program-property prediction, and logical reasoning.Applications include predicting solar-cell material efficacy [16] and candidate-drug therapeutic effects [34].Source: §3.3 · p. 20

4 Conclusion and future directions

Graph representation learning has advanced node classification and link prediction, but future progress requires improved performance and stronger theoretical foundations. The review also identifies open problems in scalability, higher-order structure, temporal graphs, subgraph search, and interpretability.

4 Conclusion and future directions

  • Graph representation learning has advanced node classification and link prediction, but progress still requires better performance and, especially, consistent theoretical foundations.The review argues that a unified theoretical framework is particularly important for future innovations.Source: §4 · p. 20

4.1 Challenges to future progress

  • The field lacks a precise account of what graph representations should encode, how models should encode it, and what constraints learned latent spaces should satisfy.The proliferation of disparate benchmarks and conceptual models across disconnected subfields risks impeding future progress.Source: §4.1 · p. 20
  • Stronger theory could guide meaningful benchmarks and help experts choose methods suited to focused applications rather than generic usefulness across tasks.Current benchmarks emphasize different graph properties, including community structure, relationship strength, and structural roles.Source: §4.1 · p. 20

4.2 Important open problems

  • Despite theoretical O(|E|) training time for most reviewed methods, scaling to billions of nodes and edges remains difficult because methods store node embeddings and evaluations assume main-memory data.Real-world graphs are often massive, evolving, and distributed, so production-ready scalability is needed to bridge research and application needs.Source: §4.2 · pp. 20–21
  • Most embedding methods use pairwise decoders that ignore higher-order motifs, motivating decoders able to represent structures involving more than two nodes [5].Higher-order motifs are essential to the structure and function of complex networks.Source: §4.2 · p. 21
  • Temporal graph embeddings remain underdeveloped, despite timing being critical in domains such as messaging and financial transactions.A key challenge is incorporating edge timing information; addressing temporal graphs could open new application domains.Source: §4.2 · p. 21
  • Subgraph embedding methods need to reason efficiently over large candidate sets, rather than requiring target subgraphs to be specified before learning.This capability could support discovering central gene-regulatory subgraphs or nefarious social-network sub-communities beyond basic subgraph classification.Source: §4.2 · p. 21
  • Embedding methods need interpretability beyond visualization and benchmarks to reveal their limitations and biases and ensure they learn relevant graph information.Researchers should guard against methods exploiting statistical tendencies of benchmarks instead of representing relevant graph information.Source: §4.2 · p. 21

Related papers

Loading 1709.05584v3…