Source-linked AI summary
Representation Learning on Graphs: Methods and Applications
William L. Hamilton, Rex Ying, Jure Leskovec
TL;DR
Graph machine learning requires encoding high-dimensional, non-Euclidean graph structure into feature vectors for downstream prediction and pattern discovery. This review unifies representation-learning methods for nodes and subgraphs through an encoder-decoder framework, and reports that these approaches have consistently pushed the state of the art on node classification and link prediction.
Problem
Graph machine learning lacks a straightforward way to encode high-dimensional, non-Euclidean graph structure into feature vectors, despite applications including node classification and link prediction.
Method
The review unifies methods for representing nodes and subgraphs around encoder-decoder mappings that learn low-dimensional embeddings and reconstruct graph structural information.
Results
Representation-learning approaches have consistently pushed the state of the art on node classification and link prediction tasks.
Takeaways & Limitations
The review provides a unified conceptual framework for comparing representation-learning approaches across graph machine-learning methods and applications.
Takeaways & Limitations
The field still lacks a consistent theoretical framework that precisely delineates the goals of graph representation learning, while disparate benchmarks and conceptual models risk hindering future progress.
Abstract
from arXiv · showhide
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
Graphs support machine learning across many domains, but their high-dimensional, non-Euclidean structure is difficult to encode for prediction. Representation learning addresses this challenge by learning low-dimensional graph embeddings, and this review unifies major approaches while defining their scope.
- Graph-structured data supports tasks including protein-role classification, collaboration-role prediction, friend recommendation, and drug-application prediction.
- The central challenge is encoding global position, local neighborhoods, or pairwise relationships into feature vectors usable by machine learning models.
- Traditional graph methods use statistics, kernels, or engineered neighborhood features, but these features are inflexible and costly to design.
- Representation learning instead learns mappings from nodes or subgraphs to low-dimensional vectors whose geometric relationships reflect graph structure.
- The review surveys node and subgraph representations, unifies node embeddings and graph convolutional networks, and emphasizes their conceptual distinctions.
- The review focuses on recent, scalable, deep-learning-inspired methods and excludes several related areas, including latent-space, relational-learning, manifold-learning, and geometric-deep-learning approaches.
2 Embedding nodes
Node embedding methods encode nodes as low-dimensional vectors that summarize graph position and local neighborhood structure. These embeddings provide a latent space in which geometric relations correspond to interactions in the original graph.
- Node embedding encodes each node as a low-dimensional vector summarizing its graph position and local neighborhood structure.
2.1 Overview of approaches: An encoder-decoder perspective
The paper organizes diverse node-embedding methods through an encoder-decoder framework that learns low-dimensional node vectors by reconstructing graph-based similarities. These embeddings can then serve as features for downstream machine-learning tasks.
- The framework maps each node to a low-dimensional embedding and decodes graph structure from those embeddings.The decoder can reconstruct global graph information or local neighborhood structure.
- Training optimizes the encoder-decoder model by minimizing reconstruction loss between decoded and graph-based similarity values.Most reviewed methods use stochastic gradient descent, while some admit closed-form matrix-decomposition solutions.
- The pairwise decoder reconstructs the similarity between two nodes from their embeddings.The target similarity may encode adjacency or co-occurrence probability on a fixed-length random walk.
- After training, node embeddings can be used as feature inputs for tasks such as community prediction and friendship recommendation.The framework separates representation learning from downstream prediction tasks.
- Methods differ primarily in their similarity function, encoder, decoder, and loss function.The loss evaluates how closely decoded similarities match graph-defined similarities.
2.2 Shallow embedding approaches
Shallow embedding methods map nodes directly to low-dimensional vectors and train those vectors to reconstruct graph-based similarities. They include matrix-factorization methods using deterministic similarities, random-walk methods using stochastic co-occurrence, and LINE’s first- and second-order objectives.
- Shallow embedding: Shallow embedding uses an embedding lookup that directly maps each node to a trainable low-dimensional vector.The embedding matrix Z contains vectors for all nodes, and Z is optimized directly.
- Factorization-based approaches: Laplacian eigenmaps is an early matrix-factorization-inspired shallow embedding method.The review places it within the encoder-decoder framework for node representation learning.
- Factorization-based approaches: Matrix-factorization methods use inner products to approximate deterministic node-similarity measures.These methods differ mainly in whether similarity represents adjacency, higher-order adjacency, or general neighborhood overlap.
- Random walk approaches: Random-walk methods optimize embeddings so nodes co-occurring on short walks have similar representations.They use stochastic rather than deterministic node similarity, and the review associates this flexibility with superior performance in some settings.
- Random walk approaches: DeepWalk and node2vec encode length-T random-walk visiting probabilities, typically using T ∈ {2, ..., 10}.Their loss is trained on random-walk samples, while naive evaluation is O(|D||V|), motivating computational approximations.
- Random walk approaches: Node2vec biases walks with p and q, trading emphasis between community structures and local structural roles.p controls immediate revisits, whereas q controls revisiting a node’s one-hop neighborhood; LINE instead combines first- and second-order objectives.
2.3 Generalized encoder-decoder architectures
Generalized encoders replace node-specific lookup tables with models that use graph neighborhoods and, in some cases, node attributes. Neighborhood autoencoders compress high-dimensional neighborhood vectors, while neighborhood aggregation methods address scalability and generalization limitations.
- Shallow embeddings assign each node an independent vector, so their parameter count grows as O(|V|) and they share no encoder parameters.
- Shallow methods also ignore node attributes and cannot generate embeddings for unseen nodes without additional optimization.
- Neighborhood autoencoder methods: Neighborhood autoencoders compress each node’s high-dimensional similarity vector si ∈R|V| into a lower-dimensional embedding zi using stacked encoder-decoder layers.
- Neighborhood autoencoder methods: DNGR constructs neighborhood vectors from pointwise mutual information of random-walk co-occurrences, whereas SDNE uses adjacency vectors and adds a Laplacian eigenmaps objective.
- Neighborhood autoencoder methods: Autoencoder approaches remain costly for million-node graphs because their input dimension is |V|, and their fixed architecture is strictly transductive.
- Neighborhood aggregation and convolutional encoders: Neighborhood aggregation methods recursively combine neighbor embeddings with node attributes through differentiable aggregators and shared neural parameters.
- Neighborhood aggregation and convolutional encoders: These encoders consistently outperform shallow embedding counterparts on node classification and link prediction while supporting sub-linear parameter dimensions and unseen nodes.
2.4 Incorporating task-specific supervision
Node embeddings can be optimized with task-specific supervision rather than, or alongside, unsupervised reconstruction objectives. For binary node classification, a sigmoid prediction layer and cross-entropy loss provide the supervised training signal.
- The encoder-decoder framework is usually unsupervised, but node embedding methods can incorporate supervision from node classification or related task labels.
- For binary node classification, embeddings zi are passed through a sigmoid function with trainable parameter vector θ to predict class probabilities.
- Task-specific supervision can replace the decoder reconstruction loss or be combined with it during encoder optimization.
2.5 Extensions to multi-modal graphs
Graph representation methods can be extended to heterogeneous and multi-layer graphs by using type-specific encoders or decoders, restricting random walks, and sharing information across layers. Multi-layer methods can regularize embeddings across related graph layers and exploit layer hierarchies.
- Heterogeneous graphs contain multiple node or edge types, such as users and content in recommender systems or diseases, genes, and drugs in biological networks.
- Dealing with different node and edge types: A general strategy uses different encoders for different node types and type-specific parameters in pairwise decoders.
- Dealing with different node and edge types: For edge type τ, a bilinear decoder uses a learned matrix Aτ to model type-specific interactions, with optional regularization when many edge types exist.
- Dealing with different node and edge types: Random walks on heterogeneous graphs can be restricted to transitions between selected node types, allowing random-walk embedding methods to operate on heterogeneous data.
- Tying node embeddings across layers: OhmNet ties embeddings for the same node across layers with a regularization penalty, allowing information from one layer to inform another.
- Tying node embeddings across layers: Hierarchical multi-layer graphs support learning embeddings at multiple levels while applying regularization only between parent-child layers.
2.6 Embedding structural roles
Structural-role embeddings aim to represent nodes by their graph position within structural patterns rather than only by proximity. struc2vec compares k-hop neighborhood structures, while GraphWave uses spectral graph wavelets and heat kernels to capture role information.
- Structural-role representations target node roles independent of global graph positions, which is useful in communication and transportation networks.The focus shifts from nearby-node similarity toward structural equivalence.
- struc2vec builds weighted auxiliary graphs whose edges encode structural similarities between nodes’ k-hop neighborhoods.The method compares ordered degree sequences at each hop distance.
- struc2vec runs biased random walks on the auxiliary graphs and feeds those walks into node2vec optimization.
- GraphWave uses spectral graph wavelets and heat kernels derived from the graph Laplacian to represent structural information.Its construction uses Laplacian eigenvectors, eigenvalues, and a predefined heat-kernel scale.
- With an appropriate scale, GraphWave captures structural roles, and Figure 9 compares its projected outputs with RolX and struc2vec on a synthetic barbell graph.The barbell graph assigns colors from degree patterns across neighborhoods up to |V|-hop distances.
2.7 Applications of node embeddings
Node embeddings support visualization, clustering, node classification, and link prediction across social-science and biological applications. They provide low-dimensional representations that help expose patterns and support predictions about nodes and relationships.
- Node embeddings are commonly used for visualization, clustering, node classification, and link prediction.
- Visualization and pattern discovery: Visualization and pattern discovery use node embeddings to display graph structure in a two-dimensional interface.
- Node classification: Inductive node classification predicts labels for nodes unseen during training, including new documents or unseen protein-interaction networks.
- Link prediction: Link prediction uses node embeddings as features for predicting missing relationships between nodes.
3 Embedding subgraphs
Subgraph and graph embeddings encode sets of nodes and edges into vectors for tasks such as subgraph classification, especially molecular property prediction. Reviewed approaches aggregate node representations, use graph coarsening, or perform message passing with neural networks.
- Subgraph embedding learns a vector zS for an induced subgraph G[S], covering both proper subgraphs and entire graphs.
- Most subgraph embedding approaches are fully supervised and use the resulting representations for subgraph classification.
- Convolutional approaches generate node embeddings through neighborhood aggregation and then aggregate the embeddings belonging to a subgraph.Aggregation can use sums, fuzzy histograms, edge-embedding layers, or ordered node representations.
- Graph-coarsening methods repeatedly cluster nodes, combine clustered embeddings with element-wise max-pooling, and process the resulting coarser graph.
- Naive graph-Fourier convolution requires O(|V|3) computation, whereas Chebyshev-polynomial approximations provide more practical spectral approaches.
- Graph neural networks: Original GNNs iteratively update node states until convergence and require the update function to be a contraction map.The final node embeddings are computed from the converged states.
- Graph neural networks: Gated Graph Neural Networks remove convergence iterations by using gated recurrent units and backpropagation through time.They also initialize states from node attributes and can use intermediate subgraph embeddings.
- Graph neural networks: Message Passing Neural Networks compute differentiable neighbor messages and node updates, generalizing several graph neural network and convolutional approaches.They can incorporate edge features and are used for predicting molecular properties.
4 Conclusion and future directions
The review presents graph representation learning as an alternative to traditional feature engineering and reports progress on node classification and link prediction. It concludes that stronger theory, realistic scalability, higher-order decoding, and temporal modeling remain important priorities.
- Graph representation learning offers an alternative to traditional feature engineering and has consistently advanced node classification and link prediction.
- The field lacks a consistent theoretical framework specifying representation goals, encoding mechanisms, and constraints on learned latent spaces.
- More developed theory could support meaningful benchmarks and help domain experts choose among methods for focused applications.
- Scalability: Most evaluation setups assume that training and testing attributes, embeddings, and edge lists fit in main memory, unlike massive evolving distributed graphs.
- Decoding higher-order motifs: Many methods use pairwise decoders that ignore higher-order motifs involving more than two nodes.
- Modeling dynamic, temporal graphs: Existing embedding approaches lack mechanisms for dynamic graphs where timing information is critical, such as messaging and financial-transaction networks.