PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph Neural Networks: Taxonomy, Advances and Trends

Yu Zhou, Haixia Zheng, Xin Huang, Shufeng Hao, Dengao Li, Jumin Zhao

arXiv:2012.08752v4cs.LG

TL;DR

Existing GNNs face challenges from graph complexity, perturbations, limited WL-test expressiveness, and opaque mechanisms. This survey organizes GNN research through a taxonomy spanning architectures, extensions and applications, benchmarks and evaluation pitfalls, and future directions, synthesizing findings including capability limits and evaluation sensitivity.

  • Problem

    GNNs face expensive computation on large graphs, sharp performance decay under structural or feature perturbations, limitations from the WL test, and opaque mechanisms that hinder safe deployment.

  • Method

    The survey develops a taxonomy and expands its coverage across architectures, extensions and applications, benchmarks and evaluation pitfalls, and future research directions.

  • Results

    The survey synthesizes findings that spatial GCNNs can be universal approximators under sufficient conditions but have limited power when depth and width are restricted.

  • Takeaways & Limitations

    Fairly standardized training and hyper-parameter tuning are important because dataset splits can change model rankings and simpler architectures can outperform sophisticated ones.

  • Takeaways & Limitations

    Hypergraph neural networks that represent each hyperedge as a complete graph incur expensive computational cost, motivating approximation approaches.

Abstract

from arXiv · show

Graph neural networks provide a powerful toolkit for embedding real-world graphs into low-dimensional spaces according to specific tasks. Up to now, there have been several surveys on this topic. However, they usually lay emphasis on different angles so that the readers can not see a panorama of the graph neural networks. This survey aims to overcome this limitation, and provide a comprehensive review on the graph neural networks. First of all, we provide a novel taxonomy for the graph neural networks, and then refer to up to 400 relevant literatures to show the panorama of the graph neural networks. All of them are classified into the corresponding categories. In order to drive the graph neural networks into a new stage, we summarize four future research directions so as to overcome the facing challenges. It is expected that more and more scholars can understand and exploit the graph neural networks, and use them in their research community.

1 INTRODUCTION

The survey presents a panorama of graph neural networks through a taxonomy spanning architectures, extensions and applications, benchmarks, evaluation pitfalls, and future directions. It also reviews the literature comprehensively and identifies four research directions addressing current challenges.

  • Motivation: GNNs learn task-specific node, edge, and graph representations through hierarchical iterative operators for graph-related learning tasks.Examples include node classification, graph classification, link prediction, and clustering.
  • Related surveys: The review aims to provide a comprehensive panorama because prior surveys emphasize different angles and omit several GNN topics.The omitted topics include capability and interpretability, probabilistic inference combinations, and adversarial attacks.
  • Survey scope: The survey organizes GNN research into four perspectives: architectures, extensions and applications, benchmarks and evaluation pitfalls, and future research directions.The architecture perspective covers graph convolutions, pooling, attention, and recurrent neural networks.
  • Taxonomy: The proposed three-level taxonomy classifies architectures, benchmarks and evaluation pitfalls, and applications into 9, 2, and 10 categories, respectively.Graph convolutional neural networks are further divided into 6 categories.
  • Future directions: The survey summarizes four future research directions according to challenges facing GNNs, including computational cost, perturbation sensitivity, limited expressiveness, and interpretability concerns.These challenges arise in large-graph computation, graph or feature perturbations, the Weisfeiler–Leman test, and black-box deployment.

2 PRELIMINARIES

The preliminaries define graph notation, adjacency and neighborhood structures, node feature matrices, graph signals, Laplacians, and graph Fourier representations used to describe GNN models.

  • Graph notation: A simple graph is represented as G = (V, E), with V containing N nodes and E containing M edges.Nodes and edges are indexed as v_1, …, v_N and e_1, …, e_M.
  • Graph structure: The adjacency matrix A_G records edge existence or edge weights between node pairs, while neighborhoods and degrees describe local connectivity.For directed graphs, incoming and outgoing neighbors and degrees are distinguished.
  • Graph signals: A node feature matrix X ∈ R^(N×d) is a d-dimensional graph signal whose rows represent node feature vectors.Individual columns are one-dimensional graph signals on G.
  • Graph Laplacian: For undirected graphs, the Laplacian is L_G = D_G − A_G, where D_G is the degree matrix.The Laplacian is real, symmetric, and semipositive definite, with ordered non-negative eigenvalues.
  • Graph Fourier analysis: The Laplacian eigenvectors form graph Fourier bases, enabling graph Fourier transforms of graph signals.The eigenvalue λ_n measures the smoothness of the corresponding graph Fourier mode.

3.1 Graph Convolutional Neural Networks (GCNNs)

GCNNs generalize convolutional architectures to graph data through spectral and spatial operators, with variants addressing representation, pooling, attention, and recurrent processing. Their main challenges include computational cost and degradation with depth.

  • Overview: GCNNs learn hierarchical representations of irregular graph data by extending convolutional ideas to graph and manifold domains.The survey distinguishes spectral, spatial, wavelet, and related graph convolution approaches.
  • Spectral GCNNs: Spectral graph convolution filters graph signals in the graph Fourier domain, producing output feature channels through learnable spectral filters.For multi-dimensional signals, each output channel combines filtered input channels before applying a nonlinearity.
  • Spectral GCNNs: O(N^3) time and O(N^2) space are required for Laplacian eigendecomposition in the basic spectral graph convolution layer.Polynomial spectral filters, including Chebyshev filters, are introduced to circumvent eigendecomposition and use information from nodes up to K hops away.
  • Challenges: GCNN training on huge sparse graphs is expensive because feed-forward computation expands neighborhoods and stores intermediate results, motivating sampling and decomposition.Increasing depth also creates a depth trap involving overfitting, gradient instability, and oversmoothing; skip, residual, dense, and dilated connections are described as responses.
  • Spatial GCNNs: Spatial GCNNs use transition and update functions to propagate information over graph neighborhoods, with aggregation functions invariant to node and edge permutations.The framework includes graph-network variants such as MPNNs, NLNNs, and GraphSAGE.
  • Extensions: Graph scattering networks are reported to provide covariance, approximate permutation invariance, and stability to graph operations.The survey also notes capsule-inspired GNNs and other alternative GCNN perspectives.

3.2 Graph Pooling Operators

Graph pooling converts node-level representations into graph-level embeddings or coarsens graphs hierarchically. The survey covers global pooling and several hierarchical strategies based on clustering, learned assignments, and top-ranked node selection.

  • Global graph pooling: Global graph pooling aggregates all node representations into a universal representation for graph-level tasks.Examples include max, average, concatenation, and relational pooling.
  • Global graph pooling: Relational pooling aggregates node and edge information with a learnable function and is described as having maximal representation power under mild conditions.Its formulation constructs a permutation-invariant graph representation from node embeddings and graph structure.
  • Hierarchical graph pooling: Hierarchical pooling groups proximal nodes into super-nodes, coarsening the original graph while aggregating their representations with functions such as max or average pooling.Existing clustering algorithms such as spectral clustering and Graclus can provide the clusters.
  • Hierarchical graph pooling: StructPool learns a soft cluster-assignment matrix from node features and adjacency information using conditional random field inference.Mean-field approximation yields the most probable assignment, which produces coarsened adjacency and feature matrices.
  • Hierarchical graph pooling: DiffPool differentiably maps an adjacency matrix and embedding matrix to coarsened adjacency and feature matrices in an end-to-end GCNN framework.The coarsened features and adjacency are computed using the learned assignment matrix M.
  • Node-selection pooling: SAGPool and gPool select top-ranked nodes to form coarsened graphs, while gUnpool restores selected nodes to their original positions.gPool and gUnpool support encoder-decoder architectures by pairing down-sampling with structure restoration.

3.3 Graph Attention Mechanisms

Graph attention mechanisms assign importance to task-relevant graph information through neighborhood relevance, feature similarity, spectral frequency weighting, or guided walks. The survey organizes these mechanisms into four main categories.

  • Overview: Graph attention mechanisms help models focus on task-relevant input information for graph prediction and inference.The survey categorizes them as softmax-based, similarity-based, spectral, and attention-guided-walk mechanisms.
  • Softmax-based attention: Softmax-based attention uses learnable weights to measure neighbor relevance and update a pivot node’s feature vector.Multi-head attention can stabilize learning, while gated variants assign different weights to attention heads.
  • Softmax-based attention: Graph Transformer and Graph2Seq models use softmax-based attention to capture long-range dependencies or compute context vectors for sequence decoding.Graph2Seq combines a graph encoder, sequence decoder, and node attention mechanism.
  • Similarity-based attention: Similarity-based attention computes neighbor weights from cosine similarities between a pivot node and its neighbors.AGNN uses this mechanism to construct a propagation matrix that captures neighbor relevance across layers.
  • Spectral graph attention: Spectral graph attention learns separate importance weights for low- and high-frequency graph components.The components can be represented with graph Fourier bases or spectral graph wavelet operators, with softmax normalization making the weights positive and comparable.
  • Attention-guided walk: Attention-guided walks use a ranking network to prioritize neighbors for subsequent steps and a predicting network to guide the walk.The walker updates hidden representations as it moves through the graph.

3.4 Graph Recurrent Neural Networks

Graph recurrent neural networks extend recurrent architectures to graph-structured data, using sequence traversal, attention-guided walks, or recurrent state updates to model static and evolving graphs.

  • GRNNs generalize recurrent neural networks to process graph-structured data.
  • Graph LSTM: Graph LSTM updates node hidden and cell states for general graph-structured data.
  • Graph LSTM: Structure-evolving LSTM progressively merges adjacent nodes with high compatibilities estimated by adaptive forget gates.The resulting graph is produced using Metropolis-Hastings sampling.
  • GRNNs for Dynamic Graphs: Dynamic Graph Neural Networks separate edge-event processing into update and propagation components.For an added edge, the update component models interaction, state updates, and merging, while propagation sends information to influenced neighbors.
  • Sequence-based GRNNs: Vanilla-RNN-based GRNNs first obtain node sequences through random walks or graph traversal, then use LSTM or GRU models to capture dependencies.Examples use collaborative random walks with bidirectional GRUs and pooling, or BFS ordering with GRU-based graph classification.

4 EXTENSIONS AND APPLICATIONS

The survey organizes GNN extensions and applications around specialized graph structures and learning mechanisms, including heterogeneous, spatio-temporal, and hypergraph settings.

  • The survey reviews eight GNN extension aspects and summarizes applications after discussing core architectures.
  • Heterogeneous Graphs: Heterogeneous graphs contain multiple node and edge types, creating challenges for convolutional models that must integrate structural and semantic information.HetGNN samples strongly correlated heterogeneous neighbors, groups them by node type, and aggregates their content information.
  • Heterogeneous Graph Attention Mechanism: Hierarchical attention for heterogeneous graphs combines node-level attention over meta-path neighbors with semantic-level attention over meta-paths.Meta-path-specific representations are weighted to obtain the final node embedding.
  • Spatio-temporal Graphs: Spatio-temporal graphs represent traffic or skeleton networks with spatial and temporal edges.STGCN alternates temporal gated convolution and spatial graph convolution to extract temporal and spatial features.
  • Hypergraphs: Hypergraphs extend pairwise graphs with hyperedges that connect subsets of at least two nodes and can be represented by incidence matrices.Hyperedge weights, node degrees, and hyperedge degrees define the hypergraph structure used by hypergraph convolution methods.
  • Hypergraph Neural Networks: HGNN uses multiple hyperedge-convolution layers, while HNHN alternates updates of node and hyperedge representations.HGNN effectively treats each hyperedge as a complete graph before applying conventional graph processing.

4.2 Capability and Interpretability

The survey examines GNN expressive power, interpretability, representation learning, graph generation, probabilistic integration, and related modeling objectives and constraints.

  • Capability: GCNN expressive power concerns whether node, edge, or graph representations distinguish non-isomorphic graphs.One-hop spatial GCNNs match the distinguishing power of the 1-dimensional Weisfeiler-Leman test.
  • Capability: GIN addresses the limited distinguishing power of general one-hop GCNNs, while injective aggregation and update functions can attain equivalent power to 1-WL.
  • Capability: Spatial GCNNs can be universal approximators under sufficient depth, width, initial features, and layer expressiveness, but restricted depth and width limit their power.
  • Interpretability: Interpretability methods for GNNs include gradient-based explanations and mutual-information-based approaches such as GNNExplainer.GNNExplainer seeks a small computation-graph substructure and feature subset relevant to a prediction, and supports multi-instance explanations.
  • Deep Graph Representation Learning: GNN-based unsupervised representation learning includes VGAE, which uses a GCN encoder and inner-product decoder to learn low-dimensional node representations.Related autoencoders add adversarial regularization or Laplacian smoothing to incorporate structural and attributed information.
  • Deep Graph Generative Models: Deep graph generative models aim to produce complex graphs from latent representations despite high nonlinearity and arbitrary connectivity.GraphRNN decomposes generation into sequential node and edge formations conditioned on the current generated graph.
  • Probabilistic Inference and GNNs: Combining GNNs with probabilistic inference models structural representations alongside dependencies among random variables.Examples integrate GCNNs with CRFs, statistical relational learning, or Gaussian-process inference.
  • Probabilistic Inference and GNNs: GCNN-based Gaussian-process inference uses amortized variational Bayesian inference to approximate the posterior while GCNNs estimate its parameters.

4.6 Adversarial Attacks for the GNNs

This section surveys adversarial attacks against GNNs, including attack formulations, reinforcement-learning policies, poisoning objectives, and defenses that model or regularize perturbations.

  • Adversarial attacks: Adversarial attacks deliberately modify graph data to mislead GNN node or graph classifiers, making attack and defense an inevitable research concern.The attacks may target graph structure or initial node features.
  • Attack formulations: A graph adversarial attacker modifies G into a semantically equivalent graph while restricting the number or locality of edge changes.The equivalence indicator can encode explicit classification semantics or small modifications within a neighborhood.
  • Attack formulations: Reinforcement-learning attacks model edge additions and deletions as actions in a finite-horizon MDP and optimize a generalizable policy with hierarchical Q-learning.GCNNs parameterize the Q-function.
  • Attack formulations: Nettack seeks constrained graph and feature perturbations that change a target node’s predicted class while maximizing the original-class log-probability or logit.Its classifier is modeled with GCNNs.
  • Defense against attacks: Defensive approaches include Gaussian hidden representations, virtual adversarial regularization, and noise-aware objectives that improve robustness to structure and feature perturbations.The robust GCN absorbs attack effects into Gaussian variances, while other methods minimize losses under perturbations.
  • Graph neural architecture search: Graph neural architecture search uses a designed search space and reinforcement-learning controller, while Graph HyperNetwork amortizes the cost of training many candidate networks.The controller validates generated architectures and receives validation results as feedback.

5 BENCHMARKS AND EVALUATION PITFALLS

Benchmarks provide standardized data and settings for fair GNN comparison, while evaluation studies show that rankings can depend strongly on splits and tuning procedures.

  • Benchmarks: Benchmarks supply ground truth, datasets, coding interfaces, and consistent experimental settings for comparing GNN architectures fairly.The survey identifies benchmarking as necessary for evaluating effectiveness on large datasets.
  • Benchmarks: A reproducible benchmark framework provides 12k-70k graphs with 9-500 nodes and exposes graph convolutions, anisotropic diffusion, residual connections, and normalization layers as building blocks.The framework is open source and based on PyTorch and DGL.
  • Evaluation pitfalls: Different dataset train/validation/test splits can produce dramatically different rankings among GCN, MoNet, GAT, and GraphSAGE variants.The comparison also included logistic regression, multilayer perceptron, and label-propagation baselines.
  • Evaluation pitfalls: Simpler GCNN architectures can outperform more sophisticated ones only when hyperparameters and training procedures are tuned fairly across models.The finding comes from a standardized training and hyperparameter-tuning procedure.

6 FUTURE RESEARCH DIRECTIONS

The survey identifies four future directions for GNNs: scalability, robustness, expressive power beyond WL tests, and interpretability.

  • Highly scalable GNNs: Existing GNN architectures struggle to scale to real-world graphs with hundreds of millions of nodes and edges that evolve dynamically.Future architectures should efficiently learn node, edge, and graph representations on such graphs.
  • Robust GNNs: GNN performance can sharply drop when adversaries perturb input graph structure or initial features, motivating robust architectures with attack-and-defense mechanisms.The proposed direction is to reinforce GNNs against adversarial attacks.
  • Beyond WL tests: Spatial GCNNs are limited by the 1-WL test, while higher-order WL tests are computationally expensive and can leave non-isomorphic graphs indistinguishable.The survey motivates GNN frameworks beyond WL tests or elegant higher-order architectures.
  • Interpretable GNNs: GNNs remain black boxes, and existing interpretability methods cannot explain general GNN models, motivating a unified interpretable framework.The interpretability challenge affects applications to node classification, graph classification, and graph embedding.

7 CONCLUSIONS

The paper organizes GNN research into a taxonomy spanning architectures, extensions and applications, benchmarks and evaluation pitfalls, and future directions.

  • Taxonomy: The survey covers four architectural families: graph convolutional networks, graph pooling operators, graph attention mechanisms, and graph recurrent neural networks.It also expands extensions across eight perspectives, including capability, interpretability, adversarial attacks, architecture search, and graph reinforcement learning.
  • Future directions: The survey proposes four prospective topics: highly scalable GNNs, robust GNNs, GNNs beyond the WL test, and interpretable GNNs.These directions address challenges identified throughout the review.
Loading 2012.08752v4…