Graph Learning2009intermediate11 min read

The Graph Neural Network Model

نموذج الشبكة العصبية البيانية

Scarselli, F. · Gori, M. · Tsoi, A. C. · Hagenbuchner, M. · Monfardini, G. — IEEE Transactions on Neural Networks

The problem

Traditional neural networks assume data lives on a grid — images are pixel grids, sentences are sequences. But many real-world relationships form irregular graphs: molecules are atoms connected by bonds, social networks are people connected by friendships, web pages are documents connected by links. Feeding a graph into a standard means flattening it into a vector and losing all structural information — which bonds connect which atoms, who is friends with whom. The field needed a that could learn directly from graph-structured data while preserving its topology.

The contribution

Scarselli et al. proposed the first formal : each node maintains a vector, updated iteratively by a transition function that aggregates information from its neighbors' states, edge labels, and node labels. The process repeats until to a fixed point — guaranteed by requiring the transition function to be a contraction map (Banach fixed-point theorem). An output function then maps each node's converged state to a . The model handles directed, undirected, cyclic, and acyclic graphs natively, and is trained end-to-end with through the unrolled iterations (Almeida–Pineda algorithm).

The impact

This paper planted the seed of the entire GNN field. It introduced the core paradigm — iterative between neighbors to build node representations — that every modern GNN inherits. GCN simplified the transition function to a single matrix multiply, MPNN generalized the framework, GraphSAGE made it inductive, and GAT added attention. Today GNNs power drug discovery, traffic prediction, recommendation systems, and particle physics. All of them trace back to this 2009 blueprint.

A standard neural network is like a factory assembly line: every piece arrives in the same fixed order, gets the same treatment, and leaves in the same shape. But molecules, friendships, and road maps are not assembly lines — they're webs.

The Graph Neural Network treats data as a neighborhood meeting: each node sits down with its direct neighbors, listens to their current understanding, mixes it with its own features, and updates its summary. After several rounds, a node on one side of the graph has absorbed information from the other side — not by reading the whole graph at once, but by the ripple effect of neighbor-to-neighbor messages.

Think of it as gossip in a village: nobody talks to everyone, but after enough conversations, everyone knows the news.

The problem: neural networks expect grids, but the world is a graph

Before 2009, neural networks had two main data regimes:

Fixed-size vectors — fully connected networks that treat input as a flat list of numbers. A molecule with 20 atoms and one with 50 atoms cannot share the same network without padding and losing structure.
Ordered sequences or grids — CNNs exploit the spatial grid of pixels; RNNs exploit the temporal order of words. Both assume a regular, predictable arrangement that graphs simply do not have.

Graphs break these assumptions: nodes have variable numbers of neighbors, there is no natural "left-to-right" ordering, and the same graph can be described by many different adjacency matrices (just by reordering nodes). The field needed a model whose computation respects the topology of the graph rather than an arbitrary flattening of it.

Open in Lab

Left: data on a grid (image pixels) — every cell has exactly 4 neighbors. Right: graph data — each node has a different number of connections.

The demo wakes as you arrive…

Graphs 101: nodes, edges, and neighborhoods

A graph $G = (V, E)$ is a set of nodes $V$ and edges $E$ connecting them. Each node $v$ can carry a label ( vector) $l_v$ , and each edge $(u,v)$ can carry a label $l_{(u,v)}$ . The neighborhood of a node $\text{ne}[v]$ is the set of nodes directly connected to it.

Graphs come in many flavors: directed (edges have arrows — Twitter follows), undirected (edges go both ways — Facebook friendships), cyclic (you can follow edges and return to the start), and acyclic (no loops — family trees). The GNN model handles all of these natively.

The structure of a graph is fully captured by its $A$ : a square matrix where $A_{ij} = 1$ if nodes $i$ and $j$ are connected. The $D$ is diagonal, with $D_{ii}$ counting node $i$ 's neighbors. These two matrices are the building blocks of every graph computation.

Open in Lab

Click any node to highlight its neighborhood and see the adjacency matrix row.

The demo wakes as you arrive…

The core idea: each node updates by listening to its neighbors

The GNN assigns each node $v$ a state vector $x_v$ — a compact summary of what the node "knows" about its neighborhood and the wider graph. This state is computed by a transition function $f_w$ that looks at four things:

The node's own label $l_v$
The labels of its edges $l_{co[v]}$
The current states of its neighbors $x_{ne[v]}$
The labels of its neighbors $l_{ne[v]}$

Think of each node as a person in a meeting. Their "state" is their current understanding of the discussion. At each round, they listen to their neighbors' current understanding, combine it with their own features, and form a new summary. After enough rounds, each person's understanding reflects the entire room — even people they never talked to directly.

x_v = f_w(l_v, \, l_{co[v]}, \, x_{ne[v]}, \, l_{ne[v]})

State transition function — the heart of the GNN — Each node's state is a function of its own label, its edge labels, its neighbors' states, and its neighbors' labels. The same function f_w is shared across all nodes — parameter sharing, just like a CNN shares its filter.

o_v = g_w(x_v, \, l_v)

Output function — from state to prediction — Once the state has converged, the output function g_w reads the final state and the node label to produce a prediction — a class label, a regression value, or any task-specific output.

Open in Lab

Step through rounds of message passing and watch node states converge.

The demo wakes as you arrive…

Convergence: why the iteration always settles

There is a critical question: does the iterative update ever stop changing? If node states keep oscillating, the model is useless. Scarselli et al. solved this with a classic tool from functional analysis: Banach's fixed-point theorem.

The theorem says: if a function is a contraction map — meaning it always brings outputs closer together than inputs — then repeated application converges to a unique fixed point, regardless of where you start. Formally, $f_w$ must satisfy:

$\|f_w(\mathbf{x}) - f_w(\mathbf{x}')\| \leq \mu \|\mathbf{x} - \mathbf{x}'\|, \quad 0 < \mu < 1$

This is enforced during by penalizing the norm of $f_w$ . The practical effect: no matter how you initialize the states, the iteration $x_v^{(t+1)} = f_w(\ldots)$ converges exponentially fast. It's like a ball rolling into a valley — no matter where you drop it, it always reaches the bottom.

Open in Lab

Drag points to any starting position and watch the contraction map pull them to the same fixed point — convergence is guaranteed.

The demo wakes as you arrive…

Learning: backpropagation through the unrolled graph

Training the GNN means finding weights $w$ for both $f_w$ and $g_w$ that minimize a supervised — for example, cross-entropy for . The challenge is that $f_w$ is applied iteratively until convergence, creating a deep computational graph.

Scarselli et al. used the Almeida–Pineda algorithm: instead of unrolling all iterations and backpropagating through them (expensive in memory), this method computes gradients at the fixed point directly using implicit differentiation. The idea: at the fixed point, $x = f_w(x)$ , so we can differentiate this identity implicitly to get the without storing every intermediate state.

The training loop has two nested phases:

Forward: iterate $f_w$ until states converge (the "state" phase)
Backward: compute gradients of the loss with respect to $w$ using the Almeida–Pineda trick (the "learning" phase)

Both $f_w$ and $g_w$ are implemented as multi- perceptrons. The contraction condition on $f_w$ is encouraged by adding a penalty on the spectral radius of the Jacobian to the loss function.

The same idea in code

GNN forward pass — iterative message passing to fixed pointpython

Simplified to show the idea — not the real implementation.

import numpy as np

def transition(x_v, l_v, neighbors_x, neighbors_l, edge_l, W):
    """f_w: combine node features, neighbor states, edge labels."""
    agg = np.zeros_like(x_v)
    for x_u, l_u, l_e in zip(neighbors_x, neighbors_l, edge_l):
        msg = np.tanh(W['msg'] @ np.concatenate([x_u, l_u, l_e]))
        agg += msg                               # sum over neighbors
    return np.tanh(W['self'] @ np.concatenate([l_v, agg]))

def gnn_forward(graph, W, tol=1e-5, max_iter=50):
    """Iterate f_w until states converge (fixed point)."""
    states = {v: np.zeros(d) for v in graph.nodes}   # random init is fine
    for t in range(max_iter):
        new_states = {}
        for v in graph.nodes:
            nbrs = graph.neighbors(v)
            new_states[v] = transition(
                states[v], graph.label(v),
                [states[u] for u in nbrs],
                [graph.label(u) for u in nbrs],
                [graph.edge_label(v, u) for u in nbrs], W
            )
        # Check convergence: all states changed less than tol
        if all(np.linalg.norm(new_states[v] - states[v]) < tol
               for v in graph.nodes):
            break
        states = new_states
    # Output phase: g_w maps converged state to prediction
    return {v: np.tanh(W['out'] @ np.concatenate([states[v], graph.label(v)]))
            for v in graph.nodes}

The message-passing lens: the paradigm that outlived the paper

Strip away the fixed-point machinery and you see the pattern that every future GNN would inherit:

1. Message — each node creates a message from its current state.

2. Aggregate — each node collects messages from its neighbors (sum, mean, max…).

3. Update — each node combines the aggregated message with its own state to produce a new state.

This is the message-passing framework. Scarselli's original model used a contraction map and iterated to a fixed point. Later models (GCN, MPNN) replaced the fixed-point iteration with a fixed number of layers — each layer is one round of message passing. But the three-step recipe is identical.

The number of layers (or iterations) determines the : after $k$ layers, each node has heard from nodes up to $k$ hops away. This is the graph equivalent of a 's receptive field growing with depth.

Open in Lab

Click a node, then increase the layer count to watch its receptive field grow.

The demo wakes as you arrive…

Limitations: what came next had to fix

The original GNN was groundbreaking, but three limitations shaped the next decade of research:

Contraction constraint — requiring $f_w$ to be a contraction map limits the model's expressiveness. The model cannot capture representations that require expansive transformations. GCN relaxed this by using a fixed number of layers instead of iterating to convergence.
— after many iterations, all node states tend to converge to similar values, washing out the distinctions between nodes. This is the graph equivalent of a blurry image — too much averaging destroys detail.
Computational cost — iterating to convergence at every training step is expensive. Modern GNNs use 2–4 layers of message passing, not dozens of iterations.

What can a GNN do? Three levels of prediction

GNNs can produce outputs at three granularities:

Node-level — classify each node. Example: predict which users in a social network are bots. Each node's converged state is fed to the output function $g_w$ .
Edge-level — predict whether an edge should exist. Example: recommend friends in a social network. Combine the states of two nodes and classify the pair.
Graph-level — classify an entire graph. Example: predict whether a molecule is toxic. Aggregate all node states (by summing, averaging, or ) into a single graph-level vector, then classify.

Scarselli's original model focused on node-level and graph-level tasks. Edge-level predictions and more sophisticated graph-level pooling came with later models.

Open in Lab

Toggle between node, edge, and graph-level tasks to see how GNN outputs are formed.

The demo wakes as you arrive…

Why it mattered

2005
Gori et al. — First GNN concept
Introduced the idea of processing graph-structured data with neural networks via iterative state diffusion. The seed that Scarselli would formalize.
2009
Scarselli et al. — The GNN Model (this paper)
Formalized the GNN with transition functions, fixed-point convergence, and Almeida–Pineda training. The foundation of the field.
2014
Spectral GNNs — Bruna et al.
Applied graph convolutions in the spectral domain using the graph Laplacian eigenbasis. Mathematically elegant but computationally expensive.
2017
GCN — Kipf & Welling
Simplified spectral convolutions to a single matrix multiplication per layer. Made GNNs practical and popular. Two layers, one matrix multiply each.
2017
MPNN — Gilmer et al.
Unified all spatial GNNs under the message-passing framework: message, aggregate, update. Showed that GCN, GraphSAGE, and others are special cases.
2018
GAT — Veličković et al.
Added attention to message passing: each node learns which neighbors to listen to more. Different neighbors get different weights, learned end-to-end.
2020
GNNs enter industry
GNNs deployed at scale: Pinterest (recommendation), Google Maps (ETA prediction), DeepMind (weather forecasting), drug discovery pipelines.

GCN is Scarselli's message passing simplified to a matrix multiply; MPNN is the same three-step loop generalized into a formal framework. The idea that started with "let nodes talk to their neighbors" now powers systems that design drugs, predict traffic, and detect fraud.

CitationScarselli, Gori, Tsoi, Hagenbuchner, Monfardini. The Graph Neural Network Model. IEEE Transactions on Neural Networks, 2009.

Terms in this paper

Graph Neural Network (GNN)الشبكات العصبية الرسومية (البيانية)
Message Passingتمرير الرسائل
Adjacency Matrixمصفوفة التجاور
Node Classificationتصنيف العُقد
Graph Convolutionالالتفاف الرسومي
Over-Smoothingالإفراط في التنعيم
Contraction Mappingالتقليص الانكماشي
Degree Matrixمصفوفة الدرجات
Graph Laplacianلابلاسيان الرسم البياني
Spectral Domainالمجال الطيفي
Transductive Learningالتعلم التبادلي