Source-linked AI summary
Graph Neural Networks: A Review of Methods and Applications
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, Maosong Sun
TL;DR
Graph learning tasks require models that capture rich dependencies in graph and extracted relational data, but existing approaches and evaluations have important limitations. This survey organizes GNN design, model variants, applications, and open problems. It concludes that GNN research spans diverse computational modules, graph types, training settings, and application scenarios while requiring further work on evaluation, robustness, and interpretability.
Problem
Graph learning needs models that represent dependencies in graph data, while fair evaluation remains necessary to determine whether GNNs work and which components drive performance.
Method
The survey presents a general GNN design pipeline, reviews variants by computational modules, graph types, and training settings, and systematically categorizes applications.
Results
The survey synthesizes GNN models, theoretical analyses, and applications across structural, non-structural, and other scenarios.
Takeaways & Limitations
The survey identifies four open problems, including robustness, interpretability, and the need for rigorous evaluation strategies.
Takeaways & Limitations
GNNs remain vulnerable to adversarial attacks and lack explanations, with only a few methods generating example-level explanations.
Abstract
from arXiv · showhide
Lots of learning tasks require dealing with graph data which contains rich relation information among elements. Modeling physics systems, learning molecular fingerprints, predicting protein interface, and classifying diseases demand a model to learn from graph inputs. In other domains such as learning from non-structural data like texts and images, reasoning on extracted structures (like the dependency trees of sentences and the scene graphs of images) is an important research topic which also needs graph reasoning models. Graph neural networks (GNNs) are neural models that capture the dependence of graphs via message passing between the nodes of graphs. In recent years, variants of GNNs such as graph convolutional network (GCN), graph attention network (GAT), graph recurrent network (GRN) have demonstrated ground-breaking performances on many deep learning tasks. In this survey, we propose a general design pipeline for GNN models and discuss the variants of each component, systematically categorize the applications, and propose four open problems for future research.
1. Introduction
GNNs address the challenge of learning from graph-structured and extracted relational data, extending neural representation learning beyond conventional domains. This survey reviews GNN variants, organizes their applications, and identifies future research directions.
- Graphs represent objects and their relationships across domains including social networks, physical systems, protein interactions, and knowledge graphs.
- Early graph neural methods used state-transition systems iterated until convergence, which constrained extendability and representation ability.
- Graph convolution is difficult to transfer from Euclidean data because localized filters and pooling operators are hard to define on graphs.
- GNNs combine CNN-inspired computation and graph embedding to aggregate information from graph structure and model dependencies among elements.
- The survey reviews GNN models through a general design pipeline, categorizes applications across graph types and scenarios, and proposes four open problems.
2. General design pipeline of GNNs
The proposed GNN design pipeline begins by identifying graph structure and type, then selects the task loss and computational modules. It distinguishes graph-learning settings and combines propagation, sampling, and pooling components to build models.
- The pipeline has four steps: find graph structure, specify graph type and scale, design the loss function, and build the model with computational modules.
- Applications use explicit graphs in structural scenarios or construct implicit graphs from tasks such as text or image understanding.
- Graph types vary by direction, node and edge homogeneity, and temporal dynamics, with these categories usable in combination.
- A graph is treated as large-scale when its adjacency matrix or graph Laplacian, with O(n^2) space complexity, cannot be stored and processed by the device.
- Graph-learning tasks operate at node, edge, or graph level and use supervised, semi-supervised, or unsupervised training settings.
- Models combine propagation, sampling, skip connections, and pooling to aggregate feature and topological information, scale graph computation, and extract higher-level representations.
3. Instantiations of computational modules
This section surveys computational modules for GNNs, covering propagation, sampling, and pooling, with convolution operators divided into spectral and spatial approaches. It highlights representative spectral, spatial, attention-based, and general-framework methods alongside their design trade-offs and limitations.
- Computational modules: GNN computational modules comprise propagation, sampling, and pooling, with propagation including convolution, recurrent, and skip-connection operators.These modules are combined into layered architectures to propagate information and extract high-level representations.
- Spectral approaches: Spectral convolution transforms graph signals into the spectral domain, applies a filter, and transforms the result back.The graph Fourier transform uses Laplacian eigenvectors, while ChebNet obtains K-localized filters through Chebyshev polynomials without computing Laplacian eigenvectors.
- Spectral approaches: Spectral methods include learnable filters, ChebNet, GCN, adaptive and dual graph convolutions, and graph wavelet networks.Their design choices range from polynomial filters and renormalization to learned graph relations, local/global consistency, and wavelet transforms.
- Spectral approaches: Because learned spectral filters depend on graph structure, most spectral approaches support only transductive graph tasks.The survey notes this as a limitation when applying models across graphs with different structures.
- Spatial approaches: Spatial approaches define convolutions directly from graph topology, but must handle differently sized neighborhoods while preserving local invariance.Attention-based methods address varying neighbor weights and degrees; GAT also supports parallel computation and inductive learning.
- General frameworks: General frameworks such as MPNN, NLNN, and GN unify multiple graph-learning variants, with GN learning node-, edge-, and graph-level representations.These frameworks organize diverse message-passing and attention-style models under broader computational abstractions.
3.2. Propagation modules - recurrent operator
Recurrent propagation methods update node states iteratively with shared weights, extending recurrent architectures to graph and tree structures while introducing convergence and efficiency trade-offs.
- Recurrent operators: Recurrent operators share weights across layers, unlike convolutional operators whose layers use different weights.
- Convergence-based methods: GNN computes node states from local neighborhood information through shared transition and output functions, with the state defined as a fixed point.The fixed point is uniquely defined when the global transition function is contractive.
- Convergence-based methods: The iterative GNN update converges exponentially fast from any initial value under the stated contraction assumption.
- Convergence-based methods: Convergence-based GNNs require a contraction map, making iterative updates inefficient and potentially producing overly smooth, less informative node representations.
- Gate-based methods: Gate-based methods use GRU- or LSTM-like propagation for a fixed number of steps, reducing convergence constraints while forfeiting guaranteed convergence.
- Gate-based methods: Tree-LSTM variants aggregate children using child-specific forget gates, while Graph LSTM variants adapt recurrent updates to graph relations or node-ordering schemes.
3.3. Propagation modules - skip connection
Skip connections address degradation in deeper GNNs by controlling information flow across layers, while sampling and pooling modules manage expanding neighborhoods and graph-level representation.
- Motivation: Deeper GNNs can propagate noise from exponentially expanding neighborhoods, so additional layers may fail to improve performance or even worsen it.
- Skip connections: Highway GCN combines each layer’s output with its input using learned gating weights, and its performance peaks at four layers in one reported problem.
- Skip connections: Jump knowledge networks select intermediate representations adaptively for each node, allowing the effective neighborhood size to vary across nodes.
- Skip connections: Residual and dense connections in DeepGCNs target vanishing gradients and over-smoothing, with the best reported point-cloud segmentation result using 56 layers.
- Sampling: Neighbor sampling limits receptive-field growth and memory demands through fixed, importance-based, adaptive, layer-wise, or subgraph sampling strategies.
- Pooling: Pooling modules obtain graph representations either directly from node features or hierarchically by selecting or clustering nodes across layers.
4. Variants considering graph type and scale
GNN variants adapt propagation and scaling to directed, heterogeneous, relational, multiplex, dynamic, hypergraph, signed, and large-scale graph settings.
- Graph types: Directed-graph methods model forward and reverse edge directions differently because direction can encode information such as partial order.
- Graph types: Heterogeneous-graph methods represent multiple node and edge types using meta-paths, meta-relations, or type-specific sampling, encoding, and aggregation.
- Graph types: Relational-graph approaches address richly typed edges with transformations such as basis combinations or block-diagonal decompositions.
- Graph types: Multiplex graphs represent multiple relation types between node pairs as layers or views, with dimension-specific representations projected and aggregated into general representations.
- Graph types: Dynamic-graph models combine graph neural networks with sequence models, or jointly collect spatial and temporal information, to handle changing graph structure.
- Graph types: Hypergraph convolution models high-order interactions, while signed-graph methods use balance theory to represent positive and negative edge interactions.
- Scale: Large-scale graph methods use sampling, approximate personalized PageRank, or precomputed filters to reduce propagation and training costs.
5. Variants for different training settings
Unsupervised GNN training primarily uses graph auto-encoders or contrastive learning to learn representations without labels, with methods differing in their reconstruction or mutual-information objectives.
- Unsupervised training: Unsupervised graph learning designs losses from graph features or topology rather than labeled samples.
- Graph auto-encoders: Graph auto-encoders encode nodes with GCNs and decode embeddings to reconstruct the adjacency matrix or feature matrix.
- Graph auto-encoders: Variational and adversarially regularized graph auto-encoders extend the basic auto-encoder framework with variational training or GAN-based regularization.
- Graph auto-encoders: AGE replaces reconstruction losses with adaptive learning for pairwise node similarity and reports state-of-the-art performance on node clustering and link prediction.
- Contrastive learning: Contrastive methods learn representations by maximizing mutual information between node, graph, and multiscale substructure representations.
6. A design example of GNN
The survey illustrates GNN design with GPT-GNN for heterogeneous graph pretraining, applying the pipeline from graph structure and scale through unsupervised pretraining, supervised finetuning, and computational modules.
- GPT-GNN illustrates the design process for heterogeneous graph pretraining.
- The example covers academic knowledge graphs and recommendation systems, where graph structures are explicit or readily constructed from entities and interactions.
- Pretraining uses a self-supervised graph generation task without labeled data, while finetuning applies each task’s supervised loss.
- The model uses HGT as its propagation module, incorporating node and edge types into propagation.
7. Analyses of GNNs
The survey reviews theoretical, empirical, and data-related analyses of GNNs, showing limits in smoothing, expressivity, generalization, label efficiency, and evaluation reliability.
- Theoretical analyses: Graph convolution is analyzed as Laplacian smoothing and low-pass filtering, making nearby nodes’ hidden representations similar.
- Theoretical analyses: Graph convolution mainly denoises input features, while over-smoothing depends critically on the information-to-noise ratio.
- Theoretical analyses: Attention can help GNNs generalize to larger and noisy graphs, while stability depends on the largest eigenvalue of the filters.
- Theoretical analyses: Existing GCNs and GraphSAGE are less discriminative than the Weisfeiler-Leman test, and locally dependent variants cannot learn some global graph properties.
- Empirical analyses: Selecting informative nodes, such as high-degree or uncertain nodes, can dramatically improve labeling efficiency in supervised and semi-supervised learning.
- Evaluation: Different dataset splits can produce dramatically different model rankings, and simple models may outperform complicated ones under proper settings.
- Benchmarks: Graph benchmarks are problematic because many node-classification datasets are small relative to real-world graphs and experimental protocols are not unified.
8. Applications
GNN applications span structural and non-structural settings, including graph mining, physical and chemical systems, biology, generative modeling, combinatorial optimization, and few-shot image classification.
- Application scenarios: Applications cover structural graphs with explicit relational structure and non-structural data whose graphs must first be constructed.
- Graph mining: Graph mining uses GNNs for tasks including graph matching, clustering, classification, and other downstream structural analysis.
- Physical systems: Physical systems are represented with objects as nodes and pair-wise interactions as edges to support learning system dynamics and future states.
- Physical systems: GNNs support physical reasoning by inferring interaction graphs from object trajectories and generating trajectory predictions from those graphs.
- Chemistry and biology: Molecular graphs represent atoms as nodes and chemical bonds as edges, enabling GNN-based molecular fingerprints beyond conventional hand-made fixed fingerprints.
- Chemistry and biology: Protein interface prediction models residues as graph nodes because a residue’s prediction depends on neighboring residues.
- Generative models: Generative graph models address applications such as social interaction modeling, new chemical-structure discovery, and knowledge-graph construction.
- Combinatorial optimization: In combinatorial problems, attention-based encoder-decoder systems and GNN-enhanced methods achieve better performance than previous algorithms.
9. Open problems
The survey identifies open problems because GNNs do not yet provide satisfying solutions for every graph and condition, emphasizing robustness, interpretability, pretraining, and complex structures.
- Scope: GNNs remain unable to offer satisfying solutions for every graph under every condition.
- Robustness: Graph models are vulnerable to adversarial attacks that manipulate structural information as well as features.
- Interpretability: GNNs lack explanations, and only a few methods generate example-level explanations for real-world applications.
- Graph pretraining: Graph pretraining aims to reduce reliance on costly human-labeled data by learning from abundant unlabeled data through self-supervised methods.
- Complex graph structures: Dynamic and heterogeneous graphs remain challenging because real-world graph structures are flexible and complex.
10. Conclusion
The survey reviews GNNs through their computation modules, graph and training types, theoretical frameworks, and application scenarios, then identifies four major future challenges.
- The survey categorizes GNN variants by computation modules, graph types, and training types.
- It summarizes general GNN frameworks and presents theoretical analyses.
- Applications are organized into structural, non-structural, and other scenarios for detailed review.
- The survey proposes four open problems: robustness, interpretability, pretraining, and complex structure modeling.
Appendix A. Datasets
The appendix identifies commonly used graph-learning datasets and broader repositories that collect additional graph datasets.
- Commonly used datasets support tasks designed to evaluate various graph neural networks.
- Table A.4 lists datasets commonly used in graph-related tasks.
- Broader open-source repositories provide additional graph datasets.
Appendix B. Implementations
The appendix lists platforms for graph computing, source-code implementations of GNN models, and a research-paper list for following developments.
- The appendix lists platforms that provide code for graph computing.
- It provides hyperlinks to open-source implementations of several well-known GNN models.
- The authors recommend GNNPapers as a paper list for recent research in the rapidly growing field.