Graph Neural Networks: Taxonomy, Advances and Trends

In plain words

Graphs are data made of things and the links between them: people and their friendships, molecules and their bonds, roads and their junctions. A graph neural network is a neural network that learns a vector for every node (or edge, or whole graph) by repeatedly letting each node gather information from its neighbours. Many such networks exist, and they are described in different ways across papers.

This survey is a map of that field. It groups the networks into families (ones that filter signals in the graph's frequency domain, ones that pass messages between neighbours, ones that weight neighbours with attention, and ones that run recurrent updates), then covers the add-ons and uses built on top of them. It also reviews how the networks are benchmarked and where they fall short, and it ends with open problems: scaling to very large graphs, robustness to attacks, going beyond the limits of the classic graph isomorphism test, and interpretability.

TL;DR

A taxonomy-and-review survey of graph neural networks, covering architectures, extensions, applications, benchmarks, evaluation pitfalls and future work. It reports no new experiments and no reproducible method. Use it to find the right family of models and the paper that introduces each one. Its numbers and claims are the authors' summaries of other work, and the card does not restate them.

Problem

Standard deep learning assumes regular inputs such as grids or sequences. Graph data has irregular neighbourhoods and no fixed node ordering, so the paper frames the task as extending deep architectures to non-Euclidean domains §1. The authors name four open challenges: the cost of large graphs, sharp performance drops under perturbation of structure or features, the limits set by the Weisfeiler-Leman (WL) isomorphism test, and the lack of interpretability §1. It says earlier surveys each emphasised different angles and left out capability, interpretability, probabilistic inference and adversarial attacks §1.

Method

The survey itself has no algorithm. Its method is the taxonomy. The paper states three levels: architectures, benchmarks with evaluation pitfalls, and applications. Architectures are split into 9 categories, benchmarks and pitfalls into 2, applications into 10, and graph convolution networks into 6 subcategories §1, contributions. fig. 1 gives the layout of this structure. The paper says it refers to up to 400 works, each placed in one category [abstract]. The taxonomy is:

1. Preliminaries §2. A graph has N nodes and M edges, with adjacency matrix A. The normalised Laplacian is L = I − D^(−1/2) A D^(−1/2). Its eigenvectors are the graph Fourier basis, and its eigenvalues measure how smooth each basis vector is over the graph [§2, eqs. for smoothness and Fourier transform].

2. Graph convolutional networks §3.1:

   • Spectral: convolution is defined as filtering in the Fourier domain. Directly this needs an eigendecomposition, which the paper puts at O(N³) time and O(N²) space for large graphs §3.1. The alternatives are K-localised polynomial filters, Chebyshev filters, and the first-order simplification that gives the GCN layer §3.1.
   • Spatial: the generic message-passing framework with graph network blocks (edge, node and global updates) §3.1. Named variants are MPNN, the non-local neural network (NLNN, with Gaussian, embedded Gaussian, dot-product and concatenation affinities), and GraphSAGE §3.1. Also covered: hyperbolic GCN, a k-WL higher-order variant, and aggregation choices for permutation invariance §3.1.
   • Depth: the paper attributes the drop in performance with depth to overfitting, gradient vanishing or explosion, and over-smoothing §3.1. It names residual and dense connections, jumping knowledge, and DeepGCN as remedies §3.1.
   • Wavelet: graph wavelet neural networks, built on a spectral graph wavelet kernel §3.1.

3. Graph pooling §3.2. Global pooling reduces a graph to one vector. Hierarchical pooling coarsens the graph by clustering (EigenPooling, H-GCN), learned soft assignment (StructPool, DiffPool), or top-k node selection (SAGPool, gPool and gUnpool) §3.2.

4. Graph attention §3.3: concatenation-based (GAT-style softmax weights), similarity-based (cosine similarity with a learned scale, AGNN-style), spectral attention over low- and high-frequency components (SpGAT), and attention-guided walks §3.3.

5. Graph recurrent networks §3.4: graph LSTM, GRNNs for dynamic graphs, and models built on vanilla RNNs over random-walk or BFS node sequences §3.4.

6. Extensions and applications §4:

   • GCNs on special graphs: heterogeneous graphs (HetGNN, meta-path attention), spatio-temporal graphs (STGCN), and hypergraphs (HGNN, HNHN) §4.1.
   • Capability and interpretability: the 1-GCN ≈ 1-WL equivalence, GIN §4.2; gradient-based and decomposition-based explanations, and GNNExplainer §4.2.
   • Deep graph representation learning: GNN-based network embedding, such as VGAE §4.3.
   • Deep graph generative models §4.4.
   • Probabilistic inference combined with GNNs (CRF layers, GCNN-based Gaussian processes) §4.5.
   • Adversarial attacks and defences §4.6.
   • Graph neural architecture search §4.7, graph reinforcement learning §4.8.
   • Applications §4.9: described in prose only.

7. Benchmarks and evaluation pitfalls §5: open benchmarking infrastructure with medium-scale datasets §5, Benchmarks; OGB with standard splits §5; and a study showing that split choice can change model rankings and that simpler GCNs can win when tuning is fair [§5, Evaluation Pitfalls].

8. Future directions §6: scalable GNNs for huge dynamic graphs, robust GNNs, GNNs beyond the WL test, and interpretable GNNs §6.

Conclusions are in §7.

The standard spectral GCN layer that the survey presents §3.1, in pseudocode:

# Spectral-approximation GCN layer  [§3.1]
# Input:  X (N, d_in) node features; A (N, N) adjacency
# Output: H (N, d_out)

def gcn_layer(X, A, Theta):
    # Add self-loops, then normalise symmetrically  [§3.1]
    A_tilde = A + identity(N)                    # (N, N)
    D_tilde = diagonal_row_sums(A_tilde)         # (N, N)
    A_norm = D_tilde^(-1/2) @ A_tilde @ D_tilde^(-1/2)
    # Mix neighbours, project, apply activation  [§3.1]
    H = relu(A_norm @ X @ Theta)                 # (N, d_out)
    return H

Hyperparameters

Not applicable. The paper is a survey and states no training setup of its own §1. Hyperparameters of the cited methods are not restated here. Look them up in the paper that introduces each method.

Results

Author-reported. The paper has no experiments of its own and no results table. The benchmark and pitfall material in §5 is qualitative and gives no numbers. There is no headline metric to quote.

Paper vs code

No official code. The paper links no code repository. A GitHub repository search for the title and related phrases returned no results. The authors have no official repository for this survey.

Pitfalls

• No code, no numbers. The survey can tell you which family a model belongs to, but it can't tell you how to implement or tune it. Go to the primary paper for any equation you need to implement.
• Taxonomy counts are the authors' claims. The contributions list the category counts (9, 2, 10 and 6) §1, contributions. The text says the survey "refers to up to 400" works [abstract]. Nothing in the paper shows how the works were selected or that the counts are complete.
• Notation inconsistency in §3.3. The concatenation-attention softmax uses a term W_k that the text never defines; it appears to mean W x_j §3.3, softmax-based attention equation. Treat the attention equations as a sketch and check the source paper before implementing.
• Spectral filter approximation. The Chebyshev-to-GCN step assumes λ_max ≈ 2 and θ = θ_0 = −θ_1, and adds renormalisation §3.1. These are simplifications from the original GCN work, not general facts about spectral filters.
• Spectral limits. The paper says the linear mapping of the spectrum into [−1, 1] makes low-frequency bands hard to specialise, which motivates Cayley filters §3.1.
• Applications are prose only. The source contains a commented-out table of applications, and the compiled paper has no such table. Applications are described in text §4.9.
• Count mismatch in §3.1. The text says GCNs are covered from "6 aspects" but names four §3.1. Do not rely on that count.
• Benchmark claims rest on other work. The benchmark and pitfall sections summarise other studies and cite them rather than reporting new runs §5. Their numbers are not in this card.
• Over-smoothing and depth. The depth-trap explanation §3.1 is the authors' summary. Check the cited sources before relying on a specific mechanism.

Lineage

• Builds on: nothing specific. The paper frames itself against earlier GNN surveys by Bronstein et al., Cui et al., Sun et al., Yu et al. and Bacciu et al., named in the introduction §1. None of those surveys has a card here.
• Compared against: the same surveys, on coverage of capability, interpretability, probabilistic inference and adversarial attacks §1.
• Superseded by: not stated.