Graph Neural Networks

Foundations

  • The Graph Neural Network Model - Learns node states from graph structure and attributes through recurrent updates; the original formulation uses a contraction condition to obtain a unique fixed point. Scarselli et al. 2009.
  • Message Passing Neural Networks - Separates local message computation and node updates from a graph-level readout. Unifies several molecular prediction architectures within one framework. Gilmer et al. 2017.
  • Graph networks - Unifies computations on nodes, edges, and global graph attributes through shared update functions and permutation-invariant aggregation; connects graph structure to relational inductive biases. Battaglia et al. 2018.

Random-walk embedding baselines

  • DeepWalk - Treats short random walks as sequences and learns node vectors from their local contexts. Provides a graph-structure embedding baseline without a learned neighborhood feature aggregator. Perozzi et al. 2014.
  • node2vec - Learns node vectors from biased random walks, with parameters controlling which neighborhoods are explored. Changes the context distribution used to train embeddings. Grover and Leskovec 2016.

Neighborhood aggregation

  • Spectral networks - Extends convolution to graphs through filters in the graph Laplacian’s eigenbasis; also studies locally connected architectures based on hierarchical clustering. Bruna et al. 2013.
  • ChebNet - Uses Chebyshev polynomials of the graph Laplacian to construct localized spectral filters, avoiding explicit eigendecomposition during filtering. Defferrard et al. 2016.
  • GCN - Alternates learned feature transformations with degree-normalized neighborhood aggregation, including self-loops. Its semi-supervised setup uses graph structure and features beyond the labeled nodes. Kipf and Welling 2017.
  • GraphSAGE - Samples neighborhoods and learns feature-aggregation functions that can embed unseen nodes or graphs sharing the input feature schema, instead of storing a separate learned vector for each node. Hamilton et al. 2017.
  • GAT - Learns attention weights over graph neighborhoods to combine node features; multi-head attention provides several learned aggregations. The original attention is restricted to graph neighbors. Veličković et al. 2018.
    • GATv2 - Reorders attention operations so neighbor rankings can depend on the query node, addressing the original GAT’s static attention ranking. Brody et al. 2022.
  • Principal Neighbourhood Aggregation - Combines multiple neighborhood statistics with degree-dependent scaling. Addresses information lost when a single aggregator summarizes continuous node features. Corso et al. 2020.

Diffusion and propagation

  • PPNP / APPNP - Separates neural prediction from personalized PageRank propagation. APPNP approximates propagation iteratively, extending information flow without stacking more learned feature transformations. Gasteiger et al. 2019.
  • Graph Diffusion Convolution - Constructs a new graph by sparsifying generalized diffusion, including personalized PageRank or heat kernels. Subsequent message passing uses these diffusion-derived connections. Gasteiger et al. 2019.

Expressivity and higher-order structure

  • GIN and the 1-WL limit - With enough layers and injective aggregation, updates and readout, can match 1-WL. The sum construction assumes countable features and bounded multisets; training need not find these functions, and 1-WL is not a complete isomorphism test. Xu et al. 2019.
  • Higher-order GNNs - Relates GNNs to Weisfeiler-Leman refinement and extends aggregation to sets of nodes. Higher-order representations distinguish structures that ordinary node-level message passing can miss. Morris et al. 2019.
  • Provably Powerful Graph Networks - Uses matrix-valued representations, multilayer perceptrons, and matrix multiplication to exceed standard message-passing expressivity under the paper’s graph-isomorphism analysis. Maron et al. 2019.
  • Equivariant Subgraph Aggregation Networks - Represents a graph as a set of selected subgraphs and aggregates them equivariantly. Subgraph selection affects expressivity; sampling reduces the added computation. Bevilacqua et al. 2022.
  • Graph Substructure Networks - Augments message passing with structural features from subgraph-isomorphism counts. Expressivity depends on the chosen substructures; computing those counts adds preprocessing work. Bouritsas et al. 2023.

Depth and normalization

  • Different limits - 1-WL concerns structural discrimination; oversquashing concerns information transport; oversmoothing concerns representation collapse. Stronger aggregation, rewiring and normalization address different limits. Xu et al. 2019, Alon and Yahav 2021, Li et al. 2018.
  • Oversmoothing - Interprets GCN propagation as Laplacian smoothing; repeated smoothing can make node representations difficult to distinguish. Describes a depth-related failure mechanism, not a universal limit on GNN depth. Li et al. 2018.
  • Jumping Knowledge Networks - Combines representations from different layer depths for each node, allowing the effective neighborhood range to vary instead of using only the final layer. Xu et al. 2018.
  • GCNII - Adds initial residual connections and identity mappings to graph convolution, retaining input information through deep propagation. Studies these mechanisms as remedies for degradation with depth. Chen et al. 2020.
  • DropEdge - Randomly removes graph edges at each training epoch to regularize graph convolution and alter propagation. Restores the input graph for evaluation; analyzes conditions that slow oversmoothing. Rong et al. 2020.
  • PairNorm - Centers and rescales node features to keep their total pairwise squared distance fixed across layers. Counters representation collapse without preserving every individual pairwise distance. Zhao and Akoglu 2020.
  • Oversquashing - Studies bottlenecks when messages from expanding neighborhoods are compressed into fixed-size node vectors, hindering long-range signals even when a model can fit local dependencies. Alon and Yahav 2021.
  • GraphNorm - Normalizes features within each graph, with a learnable shift that controls how much mean information is removed. Addresses information loss from ordinary instance normalization on regular graphs. Cai et al. 2021.

Learning and rewiring graph structure

  • Learning Discrete Structures - Jointly learns GCN parameters and a probability distribution over edges through bilevel optimization. Applies when the supplied graph is missing, incomplete, or corrupted. Franceschi et al. 2019.
  • Curvature and oversquashing - Relates graph bottlenecks to message attenuation through an edge-curvature analysis. Proposes curvature-based rewiring to improve information flow across those bottlenecks. Topping et al. 2022.
  • FoSR - Selects added edges using a first-order approximation to spectral-gap improvement. Treats original and added edges as distinct relations so the model can retain information about the input graph. Karhadkar et al. 2023.

Global attention

  • Graphormer - Adds degree-based centrality, shortest-path distances, and path-edge encodings to Transformer attention, allowing graph-wide interactions to depend on graph structure. Ying et al. 2021.
  • GraphGPS - Combines positional or structural encodings, local message passing, and global attention. Scaling depends on the chosen attention mechanism; ordinary dense attention remains quadratic in node count. Rampášek et al. 2022.
  • TokenGT - Treats nodes and edges as tokens, augmenting them with orthonormal node identifiers and trainable type identifiers before a standard Transformer. Encodes graph connectivity through token representations. Kim et al. 2022.
  • SignNet / BasisNet - Encode spectral eigenvectors while respecting sign flips or basis changes within repeated-eigenvalue eigenspaces. Separate graph structure from arbitrary spectral coordinates. Lim et al. 2023.
  • Exphormer - Uses sparse attention with expander edges and virtual global nodes. Adds routes for graph-wide communication without requiring all-pairs attention. Shirzad et al. 2023.
  • PRiSM - Jointly canonicalizes spectral signs and node order. For every fixed k, its k-WL counterexamples are simple-spectrum multigraphs. Canonicalization is discontinuous; repeated-eigenvalue handling is heuristic. Hordan et al. 2026.

Graph pooling

  • DiffPool - Learns soft assignments of nodes to clusters, producing coarsened graphs for subsequent layers. Adds hierarchical representations for graph-level prediction. Ying et al. 2018.
  • Graph U-Nets - Pools by selecting nodes using learned projection scores; unpooling restores their positions. Builds an encoder-decoder architecture for node- and graph-level prediction. Gao and Ji 2019.
  • MinCutPool - Learns soft cluster assignments using a continuous relaxation of normalized min-cut. Produces differentiable graph pooling without recomputing a spectral decomposition for each graph. Bianchi et al. 2020.

Scaling to large graphs

  • FastGCN - Interprets graph convolution as an integral transform and uses Monte Carlo importance sampling to approximate it. Enables minibatch training without expanding every receptive field in full. Chen et al. 2018.
  • SGC - Removes intermediate nonlinearities and collapses weight matrices, yielding fixed graph propagation followed by a linear classifier. A baseline for testing whether learned nonlinear propagation is needed. Wu et al. 2019.
  • Cluster-GCN - Partitions the graph and trains on subgraphs formed from clusters, restricting neighborhood computation within each minibatch to reduce memory and repeated neighbor expansion. Chiang et al. 2019.
  • LADIES - Conditions layer-wise importance sampling on nodes sampled in the next layer. Restricts candidates to their neighbors to preserve connections between sampled layers. Zou et al. 2019.
  • GraphSAINT - Samples subgraphs and reweights aggregation and loss by sampling probabilities. Its unbiasedness analysis treats layers independently; it does not establish unbiased gradients through the nonlinear stack. Zeng et al. 2020.
  • SIGN - Precomputes features using several graph filters and trains a feedforward model on them. Moves graph propagation out of the training loop, trading preprocessing and feature storage for simpler minibatches. Frasca et al. 2020.

Learning under heterophily

  • MixHop - Mixes feature representations from neighborhoods at different distances, enabling operators such as differences between neighborhood scales. Studies how useful mixing patterns vary across graphs. Abu-El-Haija et al. 2019.
  • H2GCN - Separates self and neighbor embeddings, includes higher-order neighborhoods, and combines intermediate representations to handle graphs whose adjacent nodes may have different labels or features. Zhu et al. 2020.
  • GPR-GNN - Learns weights over propagation depths in generalized PageRank, adapting the graph filter to label and feature patterns. Evaluates both homophilous and heterophilous settings. Chien et al. 2021.
  • FAGCN - Uses self-gating to combine low- and high-frequency graph signals. Retains differences between neighboring nodes that low-pass smoothing can suppress. Bo et al. 2021.
  • LINKX - Embeds adjacency information and node features with separate networks before combining them with an MLP; a graph-learning baseline for weak homophily without repeated neighborhood propagation. Lim et al. 2021.
  • Reassessing heterophily benchmarks - Finds duplicate-node leakage in Squirrel and Chameleon; introduces alternative benchmarks where standard GNNs are competitive. Low label homophily alone does not establish a need for a specialized model. Platonov et al. 2023.

Evaluation: HeaRT compares endpoint-specific candidates.

  • Variational Graph Auto-Encoders - Uses a GCN encoder, Gaussian latent node variables, and an inner-product decoder to reconstruct adjacency. An unsupervised baseline for link prediction. Kipf and Welling 2016.
  • SEAL - Predicts links from local enclosing subgraphs with labels marking nodes’ positions relative to the candidate pair. Removes the target edge from positive training subgraphs to avoid exposing the answer. Zhang and Chen 2018.
  • LightGCN - Learns user and item embeddings through linear propagation on the interaction graph and combines layers. Removes feature transformations and nonlinearities from graph convolution for collaborative filtering. He et al. 2020.
  • Neural Bellman-Ford Networks - Learns node-pair representations through generalized Bellman-Ford updates with neural initialization, message, and aggregation operators. Uses path information for link prediction. Zhu et al. 2021.

Directed graph structure

  • MagNet - Uses a complex Hermitian magnetic Laplacian: magnitudes encode undirected structure and phases encode edge direction. Supports spectral learning on directed graphs; symmetrizing adjacency would discard information that this construction retains. Zhang et al. 2021.

Typed graphs

  • R-GCN - Uses relation-specific transformations for multi-relational graphs, with parameter sharing to control model size. Applies the encoder to entity classification and link prediction. Schlichtkrull et al. 2018.
  • Heterogeneous Graph Attention Network - Learns attention over neighbors connected by typed relation paths, then over path types. Separates node-level aggregation from weighting different semantic relationships. Wang et al. 2019.
  • Heterogeneous Graph Transformer - Conditions attention and message transformations on node and edge types; adds relative temporal encoding and heterogeneous graph sampling for large typed networks. Hu et al. 2020.

Temporal graphs

  • TGAT - Combines temporal neighborhood attention with continuous time encodings to produce time-dependent embeddings for observed and previously unseen nodes. Da Xu et al. 2020.
  • Temporal Graph Networks - Represents dynamic graphs as timestamped events; combines node memory with graph-based embedding operators to track evolving interactions. Rossi et al. 2020.
  • DyGFormer / DyGLib - Encodes historical first-hop interactions with neighbor co-occurrence features and sequence patches. Also supplies shared training and evaluation pipelines for comparing dynamic graph models. Le Yu et al. 2023.

Higher-order relations and topology

  • Hypergraph Neural Networks - Incidence-based aggregation reduces to a normalized weighted clique-expansion operator with self-contributions. Encoding group relations alone does not guarantee higher-order expressivity. Feng et al. 2019.
  • Simplicial message passing - Passes messages over simplicial complexes, where edges, triangles and higher-dimensional simplices represent interactions; incorporates topology beyond ordinary node-edge connectivity. Bodnar et al. 2021.

Geometric and molecular graphs

  • Geometric graphs - Positions add Euclidean symmetries beyond node relabeling. See Geometric deep learning for DimeNet, NequIP and MACE; MeshGraphNets below connects message passing to adaptive-mesh simulation.
  • SchNet - Uses continuous-filter convolutions for atoms at continuous positions; learns rotation-invariant energies and a differentiable potential for interatomic forces. Schütt et al. 2017.
  • EGNN - Builds graph layers equivariant to rotations, translations, reflections, and node permutations, using scalar features and coordinate updates without higher-order tensor representations. Satorras et al. 2021.
  • GemNet - Combines directed edge embeddings with two-hop geometric message passing for molecular prediction. Develops the architecture from an analysis of GNNs with spherical representations. Gasteiger et al. 2021.
  • MeshGraphNets - Learns physical dynamics through message passing on meshes, with adaptive discretization. Studies fluid, structural, and cloth simulations on irregular domains. Pfaff et al. 2021.

Self-supervised objectives

  • Deep Graph Infomax - Trains a discriminator to distinguish real node-graph-summary pairs from corrupted pairs, providing a mutual-information-inspired objective for unsupervised node representations. Veličković et al. 2019.
  • GraphCL - Learns graph representations by contrasting augmented views; studies node dropping, edge perturbation, attribute masking, and subgraph sampling as task-dependent augmentation choices. You et al. 2020.
  • GRACE - Contrasts node representations across two graph views formed by corrupting structure and attributes. Encourages agreement for the same node while contrasting other nodes. Zhu et al. 2020.
  • GraphMAE - Masks node features and reconstructs them with a graph autoencoder using scaled cosine error. The pretraining target is feature reconstruction rather than adjacency reconstruction. Hou et al. 2022.
    • GraphMAE2 - Extends masked feature reconstruction with multiple randomly re-masked decoding views and latent representation prediction. Regularizes reconstruction in both feature and embedding spaces. Hou et al. 2023.
  • BGRL - Learns node representations by predicting a target encoder’s output across augmented graph views. Uses a bootstrap objective without explicit negative pairs. Thakoor et al. 2022.

Transfer across graphs

  • Strategies for Pre-training GNNs - Combines node- and graph-level pretraining to learn local and global representations. Shows cases where pretraining at only one level causes negative transfer. Hu et al. 2020.
  • ULTRA - Conditions relation representations on relation interactions, enabling a pretrained link predictor to transfer across knowledge graphs with different entity and relation vocabularies. Galkin et al. 2024.
  • GraphAny - Combines analytical linear graph predictors with learned attention across new feature and label spaces. Inference still uses a labeled subset of the target graph; no target gradient updates are required. Zhao et al. 2025.

Graph generation

Evaluation: graph-statistic and kernel choices affect generator rankings.

  • GraphRNN - Decomposes graph generation into autoregressive node and edge decisions conditioned on the graph built so far. Evaluates generated graph sets through distributions of structural statistics. You et al. 2018.
  • GraphAF - Uses an autoregressive normalizing flow to generate molecular graphs. Combines parallel likelihood training with sequential sampling that can check atom valence as atoms and bonds are added. Shi et al. 2020.
  • DiGress - Learns to reverse discrete noise on categorical node and edge attributes with a graph Transformer. Generates molecular and other graphs through successive denoising steps. Vignac et al. 2023.
  • DeFoG - Applies discrete flow matching to graph generation. Separates the training objective from sampling choices, allowing generation procedures to be changed without retraining the predictor. Qin et al. 2025.

Benchmarks and evaluation

  • Evaluation pitfalls - Shows that data splits, hyperparameter tuning, and early stopping can change GNN rankings. Compares architectures under shared protocols rather than inherited results on a single split. Shchur et al. 2018.
  • Open Graph Benchmark - Provides node, link, and graph prediction tasks with application-specific splits and metrics. Includes large graphs and distribution shifts beyond small citation-network benchmarks. Hu et al. 2020.
  • Long Range Graph Benchmark - Introduces five tasks intended to test long-range graph interactions across molecular and image-derived graphs, with message-passing and Transformer baselines. Dwivedi et al. 2022.
    • Reassessing LRGB - With roughly 500k parameters, tuned GCN/GINE/GatedGCN beat retuned GPS on both peptide tasks; a deeper prediction head explains much of the gain. GPS still leads these baselines on both superpixel tasks. Tönshoff et al. 2023.
    • LRGB protocol - Input normalization improves the compared vision results. The 2023 audit found raw rather than specified filtered MRR in PCQM-Contact code. Filtering other positive tails and self-loops changes scores. Tönshoff et al. 2023.
  • Graph-generation evaluation - MMD rankings can reverse with descriptor, kernel, bandwidth or histogram choices. Matching degree or clustering summaries does not establish matching graph distributions; record metric settings. O’Bray et al. 2022.
  • HeaRT - Ranks links against 500 endpoint-specific negatives selected by heuristics with random fill. Changing validation/test negatives, not training, changes rankings across seven graphs and makes simple baselines more competitive; this is not full-catalog retrieval. Li et al. 2023.
  • Temporal Graph Benchmark - Moving averages beat TGN/DyRep on four node-affinity tasks (NDCG@10); persistence leads on trade. TGN leads mean link-prediction MRR on coin, comment and flight; CAWN, TCL and GraphMixer exhaust GPU memory. Huang et al. 2023.
  • Classic GNNs as strong baselines - Reassesses GCN, GAT, and GraphSAGE against graph Transformers; tuning normalization, dropout, residual connections, and depth changes the comparison on studied node-classification datasets. Luo et al. 2024.

Software

  • PyTorch Geometric - Graph data containers, message-passing layers, pooling operators, sampling, and dataset utilities for PyTorch. docs.
  • DGL - Graph computation and message-passing APIs, heterogeneous graph support, sampling, and distributed graph-learning tools. docs.
  • OGB tools - Dataset loaders, prescribed splits, evaluators, and baseline implementations. Use each task’s specified metric and candidate-set protocol when comparing link predictors. docs.