Technical Deep Dives

Graph Neural Networks: Theory and Applications

A comprehensive exploration of graph neural networks covering message passing, spectral methods, GATs, and real-world applications in social networks, molecules, and recommendation systems.

Gabriele Masetti · 2026-08-12

Why graphs resist ordinary deep learning

Convolutional networks assume a grid; recurrent and transformer networks assume a sequence. Graphs offer neither. Nodes have no canonical ordering, neighborhoods vary in size from node to node, and the same graph can be represented by many different adjacency matrices depending on how nodes are indexed — a property called permutation invariance (for graph-level outputs) or permutation equivariance (for node-level outputs).

Any architecture that operates on graphs has to respect this: relabeling the nodes must not change the answer. This single constraint rules out naively flattening an adjacency matrix into a fixed-size vector and feeding it to an MLP, and it is the reason graph neural networks (GNNs) evolved a distinct computational primitive: message passing.

Message passing as the unifying abstraction

Justin Gilmer and coauthors (Gilmer et al., "Neural Message Passing for Quantum Chemistry," ICML 2017) formalized message passing neural networks (MPNNs) as a common framework subsuming most graph convolution variants proposed up to that point. The forward pass decomposes into two phases. In the message-passing phase, each node repeatedly updates a hidden state by aggregating messages from its neighbors:

m_v^(t+1) = AGGREGATE({ M_t(h_v^t, h_w^t, e_vw) : w in N(v) })
h_v^(t+1) = UPDATE(h_v^t, m_v^(t+1))

After T rounds, a readout function pools all final node states into a graph-level representation for tasks like molecular property prediction. The framework is deliberately generic: M_t, UPDATE, and the pooling function are learnable, and the aggregation operator (sum, mean, max) is chosen for the invariances it enforces. Sum aggregation, for instance, is the most expressive under the Weisfeiler-Leman graph isomorphism test lens later formalized by the GIN architecture (Xu et al., 2019), because sums preserve multiset cardinality information that mean and max discard.

Every architecture discussed below is a specific instantiation of this template — they differ mainly in how they define the message function and the neighborhood aggregation weights.

Spectral roots: from graph Fourier transforms to GCN

The earliest rigorous formulation of convolution on graphs came from spectral graph theory. A graph convolution is defined by taking the eigendecomposition of the graph Laplacian L = D − A (D the degree matrix, A the adjacency matrix), transforming node signals into the "graph Fourier domain" via the Laplacian's eigenvectors, applying a filter, and transforming back. This is elegant but has two practical problems: eigendecomposition is O(n^3), and filters learned in the spectral domain of one graph do not transfer to a differently structured graph, breaking inductive generalization.

Defferrard et al. (ChebNet, NeurIPS 2016) addressed the cost problem by approximating spectral filters with Chebyshev polynomials of the Laplacian, avoiding explicit eigendecomposition and making the filters K-localized (only depending on nodes within K hops).

Thomas Kipf and Max Welling then took the further step of truncating this expansion to first order (K=1) and tying parameters, producing the Graph Convolutional Network (GCN) in "Semi-Supervised Classification with Graph Convolutional Networks" (ICLR 2017). The resulting layer-wise propagation rule is strikingly simple:

H^(l+1) = σ( D̃^(-1/2) Ã D̃^(-1/2) H^(l) W^(l) )

where à = A + I adds self-loops so a node's own features survive the convolution, and D̃ is the degree matrix of Ã. This symmetric normalization prevents the scale of node representations from exploding or vanishing as a function of node degree. Despite its simplicity — it is essentially one matrix multiplication and one learned linear projection per layer — GCN matched or beat considerably more complex spectral methods on citation-network benchmarks (Cora, Citeseer, Pubmed) and knowledge-graph classification, and it scales linearly in the number of edges rather than cubically.

GCN's practical effect was to reframe graph convolution as a spatial, neighborhood-averaging operation rather than a spectral-domain one — the layer can be read directly as "each node's new representation is a normalized weighted average of its neighbors' representations, followed by a linear transform and nonlinearity," with no reference to eigenvectors required to implement it.

Spatial approaches: sampling and attention

GCN, as originally formulated, is transductive: it requires the full graph (all nodes, including test nodes) present at training time, because the normalized adjacency matrix is baked into the propagation rule. This is unworkable for graphs like production social networks or e-commerce catalogs where new nodes appear continuously.

William Hamilton, Rex Ying, and Jure Leskovec addressed this with GraphSAGE ("Inductive Representation Learning on Large Graphs," NeurIPS 2017). Instead of using the full adjacency structure, GraphSAGE samples a fixed-size neighborhood for each node and learns aggregator functions (mean, LSTM, or max-pooling aggregators were all evaluated) that combine a node's own features with sampled neighbor features:

h_v^(l+1) = σ( W^(l) · CONCAT(h_v^l, AGGREGATE({h_u^l : u ∈ sample(N(v))})) )

Because the aggregator is a learned function rather than a graph-specific matrix, it generalizes to nodes and even entire graphs never seen during training — genuinely inductive representation learning. Neighborhood sampling also bounds the computational cost per node regardless of degree, which is what made GraphSAGE practical for graphs with millions of nodes.

Petar Veličković and coauthors took a different approach to the same underlying problem — the fact that GCN treats every neighbor with a fixed, structurally-determined weight — with the Graph Attention Network (GAT), "Graph Attention Networks" (ICLR 2018, arXiv:1710.10903). GAT replaces the fixed normalization with a learned, content-dependent attention coefficient for each edge:

e_ij = LeakyReLU(a^T [W h_i || W h_j])
α_ij = softmax_j(e_ij) = exp(e_ij) / Σ_{k∈N(i)} exp(e_ik)
h_i' = σ( Σ_{j∈N(i)} α_ij W h_j )

The attention coefficients α_ij are computed with a shared, learnable attention mechanism applied to every edge and normalized via softmax over each node's neighborhood, so nodes learn to weight structurally similar neighbors differently based on their features — a self-attention mechanism restricted to the graph's actual edges rather than computed densely over all node pairs (which is what distinguishes GAT from a plain Transformer applied to a fully connected node set).

GAT also uses multi-head attention, concatenating (or averaging, in the final layer) several independent attention heads to stabilize training, mirroring the multi-head design of standard Transformer self-attention. Crucially, because attention weights are computed from node features rather than the fixed graph Laplacian, GAT is also inductive and does not require access to the full graph structure at training time.

The over-smoothing problem

Stacking more graph-convolutional layers should, by analogy with CNNs, let a network capture increasingly long-range dependencies. In practice, GCN-style architectures degrade sharply beyond 2-4 layers. Qimai Li, Zhichao Han, and Xiao-Ming Wu diagnosed why in "Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning" (AAAI 2018): they showed that the GCN propagation rule is mathematically a special case of Laplacian smoothing, an operation that averages a node's features with its neighbors'.

A single layer of smoothing is beneficial — it's exactly why GCN works better than treating nodes independently — but repeated smoothing across many layers drives node representations toward each other, and in the limit toward a value determined only by node degree and connected-component membership, erasing the distinguishing information a classifier needs. This is over-smoothing: as depth increases, node embeddings become statistically indistinguishable, and downstream task accuracy collapses even though the model has strictly more representational capacity on paper.

Over-smoothing is the central reason most successful GNN architectures remain shallow (2-4 layers) relative to the 50-100+ layer depths common in vision and language models, and it has motivated an entire subfield of remedies: residual/skip connections that let a layer's output blend with its input (borrowed directly from ResNet), DropEdge-style stochastic removal of edges during training, PairNorm and other normalization schemes that explicitly penalize representation collapse, and initial-residual/identity-mapping tricks (e.g., APPNP, GCNII) that separate the "how many hops of neighborhood information" from "how many nonlinear transformation layers," so a network can propagate information over long graph distances without proportionally deepening the learned transformation and triggering collapse.

Spectral vs. spatial: two lenses, converging methods

It's worth being precise about a distinction that gets blurred in casual usage. Spectral methods (the original spectral CNN, ChebNet, and GCN in its derivation) define convolution via the graph Laplacian's eigenbasis, and inherit that basis's dependence on the specific graph — a filter learned on one graph is not, strictly, transferable to another graph with a different Laplacian, unless heavy approximations decouple the filter from the eigenbasis (as ChebNet's Chebyshev polynomials and GCN's first-order truncation both do).

Spatial methods (GraphSAGE, GAT, and the MPNN framework generally) define the update directly as a function over a node's local neighborhood in the original graph domain, with no reference to spectral theory at all. The historically interesting fact is that GCN sits at the hinge: it was derived as a first-order spectral approximation, but the resulting layer is spatial in every way that matters for implementation and generalization — it can be, and is, implemented and understood purely as neighborhood averaging.

In practice, essentially all GNN architectures used in production today (GraphSAGE, GAT, and their many descendants) are spatial/message-passing methods, because they support minibatching, sampling, and inductive generalization that pure spectral approaches structurally cannot.

Real applications

Protein structure prediction. DeepMind's AlphaFold2 is not a graph neural network in the GCN/GAT sense, but its core Evoformer module operates on a pair representation — a residue-by-residue matrix that is naturally a graph over amino acids — using triangular self-attention updates that propagate geometric consistency constraints between residue pairs, conceptually continuous with the graph-attention idea of learning edge-dependent weights rather than fixed structural ones.

The downstream Structure Module then converts this representation into 3D coordinates using Invariant Point Attention, an attention mechanism built to respect the rotational and translational invariances of physical structures — again, attention computed over a graph-like set of residues rather than over a grid or sequence.

Drug discovery and molecular property prediction. Message passing neural networks, following directly from Gilmer et al.'s framework, are a standard tool for predicting molecular properties (solubility, toxicity, binding affinity) by treating a molecule as a graph with atoms as nodes and bonds as edges. This graph-native representation avoids the information loss of fixed-length molecular fingerprints and has been applied to tasks spanning drug-target interaction prediction, drug-drug interaction modeling, and drug repositioning.

Recommender systems at scale. Pinterest's PinSage (Ying et al., "Graph Convolutional Neural Networks for Web-Scale Recommender Systems," KDD 2018) extended GraphSAGE-style localized convolutions with importance-based neighbor sampling (using random walks to weight which neighbors matter most) and producer-consumer minibatch construction to train on a graph with billions of nodes and edges — reported at roughly 3 billion nodes and 18 billion edges, several orders of magnitude larger than the citation-network benchmarks GCN was originally evaluated on.

This demonstrated that graph convolutions could move from academic benchmarks to production-scale industrial systems, generating pin embeddings for recommendation directly from the bipartite pin-board graph plus visual and text features.

Libraries and practical tooling

Two open-source libraries dominate applied GNN work. PyTorch Geometric (PyG) is built directly on PyTorch and provides implementations of GCN, GraphSAGE, GAT, and dozens of other published architectures, along with sparse-tensor operations, mini-batch loaders for both many small graphs and single giant graphs, and a large collection of benchmark datasets.

The Deep Graph Library (DGL) provides a backend-agnostic (PyTorch or TensorFlow) message-passing API and is often preferred for heterogeneous graphs — graphs with multiple node and edge types, common in knowledge graphs and molecular data — where its more general graph data structure gives extra flexibility. Both libraries implement neighbor sampling schemes derived from GraphSAGE's approach, making it practical to train on graphs too large to fit densely in GPU memory.

Where this leaves the field

Message passing gives GNNs a principled, permutation-equivariant way to learn from relational structure, and GCN, GraphSAGE, and GAT trace a clear arc from spectral-theoretic origins to increasingly general, inductive, sampling-friendly spatial formulations. The over-smoothing result is the field's central cautionary finding: depth is not free on graphs the way it is on grids or sequences, because repeated neighborhood averaging is mathematically a smoothing operator with a fixed point.

The architectures that have made it into production — PinSage's sampled convolutions, AlphaFold's graph-structured pair attention, MPNN-based molecular models — share a common thread: they treat the graph's connectivity as the inductive bias worth encoding explicitly, rather than something to be inferred implicitly from a denser, structure-agnostic model.