PaperlayerView exact revision on arXiv

Source-linked AI summary

Machine Learning on Graphs: A Model and Comprehensive Taxonomy

Ines Chami, Sami Abu-El-Haija, Bryan Perozzi, Christopher Ré, Kevin Murphy

arXiv:2005.03675v3cs.LGcs.NEcs.SIstat.ML

TL;DR

Graph representation learning spans several growing but weakly unified method families for learning from graph structure. The paper introduces GRAPHEDM and a taxonomy that organizes these families, covering over thirty methods, while identifying open theoretical and scalability challenges.

  • Problem

    Graph representation learning methods span disparate unsupervised, supervised, and semi-supervised approaches, while existing surveys generally focus on specific subfields rather than connecting them.

  • Method

    The paper introduces GRAPHEDM, a unified encoder-decoder framework, alongside a graph convolution framework and taxonomy for comparing graph representation learning methods.

  • Results

    The framework encapsulates over thirty graph embedding methods, while graph neural networks and graph convolution models achieve strong empirical performance across node-classification tasks.

  • Takeaways & Limitations

    The unified formalization helps readers reason about similarities, differences, potential extensions, and limitations among graph learning methods.

  • Takeaways & Limitations

    The paper identifies limited understanding of theoretical guarantees and limitations for graph embedding models as an open research challenge.

Abstract

from arXiv · show

There has been a surge of recent interest in learning representations for graph-structured data. Graph representation learning methods have generally fallen into three main categories, based on the availability of labeled data. The first, network embedding (such as shallow graph embedding or graph auto-encoders), focuses on learning unsupervised representations of relational structure. The second, graph regularized neural networks, leverages graphs to augment neural network losses with a regularization objective for semi-supervised learning. The third, graph neural networks, aims to learn differentiable functions over discrete topologies with arbitrary structure. However, despite the popularity of these areas there has been surprisingly little work on unifying the three paradigms. Here, we aim to bridge the gap between graph neural networks, network embedding and graph regularization models. We propose a comprehensive taxonomy of representation learning methods for graph-structured data, aiming to unify several disparate bodies of work. Specifically, we propose a Graph Encoder Decoder Model (GRAPHEDM), which generalizes popular algorithms for semi-supervised learning on graphs (e.g. GraphSage, Graph Convolutional Networks, Graph Attention Networks), and unsupervised learning of graph representations (e.g. DeepWalk, node2vec, etc) into a single consistent approach. To illustrate the generality of this approach, we fit over thirty existing methods into this framework. We believe that this unifying view both provides a solid foundation for understanding the intuition behind these methods, and enables future research in the area.

1 Introduction

Graph-structured data is difficult to model because graph topology is irregular, motivating graph representation learning and a unified framework spanning major method families.

  • Graphs represent complex relational data across domains, but their arbitrary and varying structures make structural priors and direct convolution difficult to define.
  • Graph representation learning learns low-dimensional continuous embeddings for graph-structured data.
  • GRL includes unsupervised structure-preserving learning and supervised or semi-supervised learning for downstream node or graph prediction tasks.
  • Existing surveys typically focus on individual GRL subfields rather than connecting them.
  • GRAPHEDM unifies shallow embeddings, auto-encoding methods, graph regularization methods, and graph neural networks within one framework.
  • The survey provides a taxonomy covering over thirty graph representation learning methods and releases an open-source library for GRL methods and applications.

2 Preliminaries

The preliminaries define graph representations, proximity concepts, and learning settings that organize how network embedding methods preserve structure and generalize.

  • Definitions: A graph consists of vertices and edges, with adjacency, degree, and Laplacian matrices providing standard structural representations.
  • Definitions: Graph distance is the shortest-path length between nodes, while first- and second-order proximity capture edge strength and neighborhood similarity.
  • Definitions: The graph Laplacian is a key graph operator whose eigenspace captures properties such as cut information and provides a basis for smooth functions.
  • Network embedding: Network embedding maps a discrete graph into a continuous domain while preserving important graph properties in low-dimensional node vectors.
  • Node and edge fields: Node features can add semantic information, whereas featureless embeddings preserve only graph structure.
  • Transductive and inductive learning: Transductive methods use observed nodes in a fixed graph and may fail to generalize to new nodes or graph instances; inductive methods target unseen nodes, edges, or graphs.
  • Transductive and inductive learning: The transductive–inductive distinction is incomplete because theoretical results indicate that some models can operate in both settings.

3 A Taxonomy of Graph Embedding Models

GRAPHEDM provides a unified taxonomy for supervised and unsupervised graph representation learning, describing over thirty methods through shared encoder-decoder components and objectives.

  • Taxonomy: GRAPHEDM describes over thirty graph representation learning methods within a comprehensive taxonomy using shared notations and block diagrams.The framework covers both unsupervised and supervised methods and is intended to clarify their similarities and differences.
  • Framework scope: GRAPHEDM extends an encoder-decoder perspective beyond unsupervised network embedding to also encapsulate supervised graph embedding methods.This broader scope distinguishes it from earlier unsupervised encoder-decoder frameworks.
  • Framework components: The framework combines a graph encoder with graph, classification, or both decoders, depending on the available supervision.The encoder produces node embeddings; graph decoding reconstructs pairwise similarity or dissimilarity, while classification decoding predicts labels.
  • Supervision: Supervision may be provided at the node, edge, or graph level, supporting tasks including node classification, link prediction, and graph classification.Graph-level prediction uses pooling to convert node embeddings into a graph label.
  • Objectives: GRAPHEDM optimization can combine supervised prediction loss with graph regularization that measures decoded versus target similarity or dissimilarity.The regularization target may capture higher-order proximities beyond the adjacency matrix.
  • Training perspective: Supervised methods generally outperform two-step approaches that first learn unsupervised embeddings and then train a supervised model.The paper describes joint learning of representations and decision rules as the supervised alternative.

4 Unsupervised Graph Embedding

Unsupervised graph embedding methods learn continuous representations without task-specific labels, typically preserving graph structure through encoder-decoder objectives. The section organizes shallow methods by how their decoders measure node relationships and discusses manifold-based and non-Euclidean alternatives.

  • Overview: Unsupervised graph embedding maps graphs, nodes, or edges into continuous vector spaces without task-specific labels.Objectives may preserve structure by reconstructing node-to-node similarity or dissimilarity information.
  • Shallow embedding methods: Shallow methods use a transductive embedding lookup, with one learnable low-dimensional vector assigned to each node.Their encoder is a simple lookup rather than a learned graph transformation.
  • Distance-based methods: Distance-based methods keep graph-neighboring points close in embedding space by decoding pairwise distances.They include Euclidean and non-Euclidean embedding variants.
  • Outer product-based methods: Outer product-based methods decode pairwise dot products to represent node similarities, while graph regularization trains embeddings against graph-derived targets.Distance decoders interpret larger values as less similarity, whereas outer-product decoders interpret larger values as more similarity.
  • Nonlinear dimensionality reduction: IsoMap preserves graph-geodesic distances but is computationally expensive because it computes all pairs of shortest-path lengths.LLE instead uses local manifold geometry and sparse matrix operations to improve computational complexity.
  • Euclidean methods: Laplacian Eigenmaps preserve local distances by representing nodes with eigenvectors of the graph Laplacian associated with smaller eigenvalues.Its smooth eigenvectors encourage nearby manifold or graph points to receive similar representations.
  • Non-Euclidean methods: Hyperbolic space provides a non-Euclidean alternative that is well-suited to representing hierarchical data.The section notes that graph embeddings need not be restricted to conventional Euclidean geometry.
  • Random-walk methods: Random-walk methods are sensitive to sampling choices because some graphs favor local information while others favor global structure.DeepWalk and node2vec expose walk-length or exploration-balance hyperparameters to control this trade-off.

4.2 Auto-encoders

Auto-encoders use deep encoder and decoder networks to model nonlinear graph structure, while graph neural networks incorporate both adjacency and node features. Unsupervised variants reconstruct graph structure or maximize information-based objectives without node or graph labels.

  • Auto-encoders address the limited ability of shallow embeddings to capture nonlinear graph structures by using deep encoder and decoder functions.
  • SDNE encodes adjacency-matrix rows into node embeddings and decodes them to reconstruct the original adjacency matrix while preserving first- and second-order proximity.
  • DNGR encodes and decodes a random-surfing similarity matrix, allowing deep auto-encoders to capture higher-order graph dependencies.
  • VGAE uses graph convolutions to compute node embeddings, an outer-product decoder, and a variational latent representation optimized through a negative evidence lower bound.
  • Graphite extends graph auto-encoders with an iterative decoder alternating pairwise decoding and graph convolutions, producing more expressive decoders than non-parametric pairwise decoding.
  • Unsupervised graph neural networks use graph structure and input features in an encoder, while DGI maximizes a lower bound on mutual information between node and graph representations.

5 Supervised Graph Embedding

Supervised graph embedding addresses the limitation that unsupervised embeddings may omit graph properties useful for downstream prediction. The paper therefore describes approaches that jointly learn embeddings and node or graph labels.

  • A two-step supervised pipeline first learns unsupervised node embeddings and then predicts labels, but those embeddings may not preserve useful node labels or attributes.
  • Joint methods combine embedding learning with node or graph label prediction instead of separating the two stages.

5.1 Shallow embedding methods

Supervised shallow embedding methods use node embedding look-ups for downstream prediction, while label propagation smooths label distributions over graph structure under a neighbor-label consistency assumption.

  • Supervised shallow embeddings use look-ups to map nodes into vectors optimized for downstream tasks such as node or graph classification.
  • Label propagation directly learns embeddings in label space because its supervised decoder is the identity function.
  • Label propagation regularizes predictions by smoothing label distributions across neighboring nodes, assuming connected nodes tend to have similar labels.
  • Label propagation updates unlabeled nodes iteratively using weighted averages of their neighbors’ labels.
  • The supervised loss uses labeled nodes, whereas graph regularization uses all nodes, making these methods suited to graphs with label-consistent proximity.

5.2 Graph regularization methods

Graph regularization methods learn parametric embeddings from node features while combining downstream supervised losses with graph-structure regularization. The section covers Laplacian, neural, and random-walk-based approaches, including Planetoid’s joint use of labels and graph information.

  • Graph regularization methods learn embeddings as parametric functions of node features and combine graph-regularization and supervised losses.
  • The reviewed approaches include Laplacian-based regularization and random-walk-based regularization for semi-supervised learning.
  • ManiReg smooths label distributions with Laplacian Eigenmaps while using support vector machines to predict labels from node features.
  • SemiEmb extends ManiReg with feed-forward neural networks, distance-based graph decoders, and regularization of intermediate or auxiliary representations.
  • Neural Graph Machines generalize the regularization objective to architectures such as LSTMs and CNNs, using cross-entropy for classification.
  • Planetoid incorporates node-label information into random-walk embedding, using structural and feature embeddings with transductive and inductive variants.

5.3 Graph convolution framework

The Graph Convolution Framework (GCF) organizes convolution-based graph neural networks around graph-specific patch functions, filter weights, and merging functions. It complements broader graph neural-network frameworks by emphasizing geometric properties and connections to grid convolutions.

  • Related frameworks: Message passing frameworks describe fixed-depth graph networks in which neighbor messages are computed and aggregated at each layer.After L message-passing layers, node representations encode structural information within L-hop neighborhoods.
  • GCF: The proposed GCF focuses on convolution-based GNNs and provides a geometric basis for comparing state-of-the-art graph convolution methods.It does not include sophisticated message-passing models whose messages use edge features.
  • GCF: GCF initializes node embeddings from input features and updates them through multiple graph-convolution layers before decoding node or graph labels.The final node representation is Z = H^L.
  • GCF: Graph convolution layers generalize standard grid convolutions to graph-structured data through four components: patch functions, filter weights, merging functions, and nonlinear transformations.Patch functions specify which nodes interact, while merging functions combine outputs from multiple convolution steps.
  • GCF: Patch functions define graph filter neighborhoods, which may be specified spectrally or spatially and may be fixed or learned parametrically.Attention-based methods learn patches with parametric functions, whereas most methods use non-parametric patches.

5.4 Spectral Graph Convolutions

Spectral graph convolutions generalize Fourier-domain filtering to graphs through the eigendecomposition of the normalized Laplacian. Spectrum-free methods approximate these filters with polynomials, reducing spectral computation but retaining graph-scale memory costs in some models.

  • Spectrum-based methods: Spectrum-based methods explicitly use Laplacian eigenvectors, making their filters domain-dependent and limiting them to transductive settings.Their dependence on the graph spectrum prevents straightforward sharing across different graphs.
  • Spectral foundations: Spectral graph convolutions learn filters in the spectral domain of the graph Laplacian, where graph signals are represented using Laplacian eigenvectors.The normalized Laplacian admits an orthonormal eigendecomposition used to define the graph Fourier transform and spectral filters.
  • Spectrum-based methods: SCNNs implement spectral filtering with trainable multipliers associated with Laplacian eigenvalues and merge filter outputs through summation followed by a nonlinearity.SCNN layers use the top K Laplacian eigenvectors and spectral-domain filter weights.
  • Limitations: Spectrum-based methods require costly eigendecomposition, while spectrum-free GCNs can require storing the entire adjacency matrix, which is expensive for large graphs.These limitations motivate spatial methods for graph convolution.
  • Spectrum-free methods: Spectrum-free methods approximate spectral filters using finite-degree polynomial expansions, yielding parameter counts independent of graph size and k-localized receptive fields.Only nodes within distance k interact for a degree-k localized filter.
  • Spectrum-free methods: ChebNets use Chebyshev polynomial expansions, while GCNs simplify ChebNet with K = 2, weight sharing, and eigenvalue re-normalization.ChebNets rescale the normalized Laplacian; GCN re-normalization maps relevant eigenvalues to [0, 1].

5.5 Spatial Graph Convolutions

Spatial graph convolutions operate directly on graph topology, avoiding spectral eigendecomposition. SAGE samples neighborhoods for inductive scalability, while attention-based methods learn which neighbors receive greater weight.

  • Spatial methods: Spatial methods apply convolution in the graph’s spatial domain, using topology-defined neighborhoods rather than Laplacian eigenvectors.They adapt the locality and weight reuse ideas of standard CNNs to irregular graph structures.
  • GraphSAGE: SAGE learns inductive node embeddings by sampling fixed-size neighborhoods, reducing dependence on a fixed graph and the memory cost of full-graph convolution.At each layer, nodes aggregate information from sampled neighbors using permutation-invariant operators such as mean or max pooling.
  • GraphSAGE: SAGE-mean can be expressed in GCF using an identity patch and a uniformly sampled, row-normalized neighborhood patch.The sampled neighborhood patch propagates information from q sampled neighbors.
  • Attention-based methods: Attention-based graph convolutions learn neighbor importance from node features, providing more flexibility than fixed-weight methods such as GCNs.Attention weights are learned parametrically during message passing.
  • Attention-based methods: GAT attends over every node’s neighborhood and assigns different learned weights to neighbors, supporting both inductive and transductive problems.Unlike SAGE’s fixed-size neighborhoods, GAT can attend over the entirety of each node’s neighbors.
  • Attention-based methods: GAT uses multi-headed attention and combines propagated signals through concatenation or averaging followed by an activation function.Its self-attention scores can be computed in parallel across edges.

5.6 Non-Euclidean Graph Convolutions

Non-Euclidean graph convolutions extend graph neural networks beyond Euclidean embeddings, but require alternatives to ordinary inner products and matrix multiplication. Hyperbolic models use Euclidean tangent spaces to perform convolution while retaining hyperbolic representations.

  • Motivation: Shallow embeddings represent hierarchical graphs with less distortion in hyperbolic space, but they are transductive and cannot generalize to new graphs.Graph neural networks using node features have achieved state-of-the-art performance on inductive graph embedding tasks.
  • Motivation: A central challenge for non-Euclidean graph convolutions is that standard operations such as inner products and matrix multiplications are not defined there.This motivates mapping representations to a Euclidean tangent space for computation.
  • Hyperbolic graph convolutions: HGCN and HGNN map node embeddings to the Euclidean tangent space at the origin, apply graph convolutions there, and map the results back to hyperbolic space.The tangent space provides a first-order approximation of the hyperbolic manifold at a point.
  • Hyperbolic graph convolutions: These hyperbolic graph convolution approaches yield significant improvements on graphs exhibiting hierarchical structure.The paper points to Figure 13 for this outcome.

5.7 Summary of supervised graph embedding

Supervised graph embedding methods differ in whether their encoders use node features and adjacency. Graph convolution models use both and achieve superior empirical performance on many node-classification tasks.

  • Shallow methods omit node features and adjacency from the encoder, using adjacency only to enforce consistency.They suit transductive settings with one featureless graph and partially labeled nodes.
  • Graph regularization methods use node features but exclude adjacency from the encoder.They are generally inductive, requiring a graph during training but not inference, and fit settings with informative features.
  • Graph convolution models use both node features and adjacency in the encoder.
  • Graph convolution models achieve superior empirical performance on many node-classification tasks.

6 Applications

Graph representation learning supports unsupervised and supervised applications including reconstruction, link prediction, clustering, visualization, node classification, and graph classification. The appropriate method depends on the task, available signals, and whether prediction concerns nodes, edges, or whole graphs.

  • Unsupervised graph learning uses the graph as self-supervision to preserve neighborhoods or structural equivalence in learned embeddings.
  • Graph reconstruction learns node representations that preserve graph properties by minimizing error in recovering the original graph.
  • Link prediction estimates missing or unobserved edges, commonly by masking positive and negative edges for training and testing.It differs from graph reconstruction, which seeks embeddings that preserve observed graph structure.
  • Clustering and visualization: Unsupervised embeddings support clustering and visualization through downstream clustering or dimensionality reduction such as t-SNE or PCA.
  • Node classification: Node features can significantly improve node-classification performance when they describe the target labels, whereas random-walk methods do not leverage feature information.
  • Graph classification: Graph classification predicts graph-level labels and requires permutation-invariant pooling to aggregate node-level information.Pooling over arbitrary graphs remains non-trivial and active research.

7 Conclusion and Open Research Directions

The survey unifies graph representation learning methods through GRAPHEDM and a graph convolution framework, organizing more than thirty methods. It also identifies open challenges in scalability, evaluation, fairness, geometry, and theoretical understanding.

  • GRAPHEDM unifies shallow embeddings, graph auto-encoders, graph regularization methods, and graph neural networks.The survey also introduces GCF to compare spatial and spectral graph convolutions.
  • The taxonomy organizes over thirty supervised and unsupervised graph-embedding methods within a unified comparison framework.
  • Practitioners can use the taxonomy to understand available tools and identify methods for particular problems, while researchers can locate baselines and relevant prior work.
  • Evaluation and benchmarks: Standard small node-classification and link-prediction benchmarks can vary substantially with dataset splits and training procedures.
  • Evaluation and benchmarks: Robust unified evaluation should extend beyond small benchmarks through broader graph benchmarks, libraries, and reasoning-oriented tasks.
  • Large and realistic graphs: Graph-learning methods often target smaller datasets, while real-world graphs may contain billions of nodes and require distributed systems to scale.
  • Non-Euclidean embeddings: Non-Euclidean embeddings may represent hierarchical data with less distortion, but face precision, optimization, and geometry-selection challenges.
  • Theoretical guarantees: Graph representation learning still has limited theoretical guarantees, including incomplete understanding of graph neural networks' representational power.
Loading 2005.03675v3…