Graph Neural Network: Graph Neural Networks — Complete Guide

Summary

Graph Neural Networks (GNNs) are a family of deep learning architectures specifically designed to process data structured as graphs. Unlike classical neural networks that operate on Euclidean data (images, text sequences), a Graph Neural Network can directly exploit the relational topology between entities. This capability makes GNNs indispensable in fields as varied as bioinformatics, recommendation systems, social network analysis, or computational chemistry. This guide explores in detail the mathematical principle of message passing, the major architectures (GCN, GraphSAGE, GAT), and provides a complete Python implementation with PyTorch Geometric.

What is a Graph?

A graph is a mathematical structure denoted G = (V, E) where V represents the set of nodes (or vertices) and E the set of edges (or links) that connect them. Each node can have a feature vector x ∈ ℝᵈ, and each edge can also carry information in the form of attributes.

In the real world, graphs are everywhere:

• Social networks: users are nodes, friendship relationships are edges.
• Chemical molecules: atoms are nodes, chemical bonds are edges.
• Recommendation systems: users and items form a bipartite graph.
• Citation networks: scientific papers are nodes, mutual citations are edges.
• Transportation networks: stations or airports are nodes, routes or flights are edges.

Classical machine learning methods struggle to handle these structures because they assume that data is independent and identically distributed (the i.i.d. assumption). Yet in a graph, neighboring nodes are strongly correlated. The Graph Neural Network solves this problem precisely by learning both the characteristics of nodes and the structure of connections between them.

Mathematical Principle: Message Passing

The fundamental mechanism of Graph Neural Networks is called message passing. It consists of three iterative steps applied to each node:

Step 1 — Neighbor aggregation

For a node i at layer l, we collect the representations of all its direct neighbors N(i):

AGGREGATE({h_j^(l), ∀ j ∈ N(i)})

where N(i) denotes the set of neighboring nodes of node i in the graph, and h_j^(l) is the representation (embedding vector) of node j at layer l.

Step 2 — Update

The representation of node i is then updated by combining its own representation with the aggregation of received messages:

h_i^(l+1) = UPDATE(h_i^(l), AGGREGATE({h_j^(l), j ∈ N(i)}))

This is the master equation of message passing. Concretely, UPDATE is generally a linear transformation followed by a non-linear activation function (such as ReLU). The AGGREGATE operator can be a sum, a mean, a maximum, or a more sophisticated attention mechanism.

Step 3 — Readout

After several layers of propagation, we can obtain a global representation of the entire graph via a READOUT operator that aggregates the representations of all nodes (e.g., by global sum or mean).

General Message Passing Formula

In formal notation, the generic equation is written:

h_i^(l+1) = UPDATE^(l)(h_i^(l), AGGREGATE^(l)({h_j^(l) : j ∈ N(i)}))

where:
– N(i) = set of neighbors of node i
– h_i^(l) = representation of node i at layer l
– || = concatenation operator (used in certain architectures)
– σ = non-linear activation function

Major Graph Neural Network Architectures

1. GCN — Graph Convolutional Network (Kipf & Welling, 2016)

The GCN is the reference architecture of Graph Neural Networks. It simplifies message passing by using a normalized average of neighboring representations:

h_i^(l+1) = σ(W^(l) · mean_j(h_j^(l), j ∈ N(i) ∪ {i}))

More precisely, the normalized spectral formulation is:

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

where à = A + I is the adjacency matrix with self-loops, D̃ is the corresponding degree matrix, and W^(l) is the learned weight matrix at layer l.

The intuitive idea is simple: each node adopts a representation that is the weighted average of its neighbors’ representations, and this average is then linearly transformed and passed through a non-linearity. GCNs are efficient, easy to implement, and constitute an excellent basis for understanding the principles of Graph Neural Networks.

Advantages of GCN: simplicity, computational efficiency, good empirical performance on many benchmarks.

Limitations of GCN: the normalization is fixed (not learned), the model is transductive (requires the entire graph during training), and mean aggregation gives equal weight to all neighbors.

2. GraphSAGE — Sample and Aggregate (Hamilton et al., 2017)

GraphSAGE addresses a major limitation of GCN: its transductive nature. Indeed, GCN requires knowing the complete graph structure during training, making it unable to generalize to new nodes never before observed.

GraphSAGE solves this problem through two innovations:

• Neighbor sampling: instead of using all neighbors (which can be very numerous), a fixed number of neighbors is sampled at each layer.
• Learned aggregation function: one can use a mean, LSTM, or pooling aggregator, which is learned during training.

The updated equation is:

h_i^(l+1) = σ(W^(l) · CONCAT(h_i^(l), AGGREGATE({h_j^(l), j ∈ S(N(i))})))

where S(N(i)) denotes a sample of node i’s neighbors.

This approach makes GraphSAGE inductive: it can generate embeddings for nodes never seen during training, which is crucial for applications like recommendation where new items constantly appear.

3. GAT — Graph Attention Network (Veličković et al., 2017)

The GAT (Graph Attention Network) introduces an attention mechanism into the aggregation process. Instead of giving equal weight to all neighbors (like GCN) or a sampled weight (like GraphSAGE), GAT learns the relative importance of each neighbor.

The attention coefficient between node i and its neighbor j is computed as:

e_ij = a(W·h_i || W·h_j)
α_ij = softmax_j(e_ij) = exp(e_ij) / Σ_k exp(e_ik)

where:
– a is an attention function (generally a small single-layer neural network)
– || denotes the concatenation of transformed representations
– α_ij is the normalized attention coefficient between i and j

The final representation of node i is then:

h_i' = σ(Σ_j α_ij · W·h_j)

where the sum is over all neighbors j ∈ N(i).

The intuition is powerful: imagine a social network where each person (node) learns opinions from their friends (neighbors). But influential friends — those with whom you interact regularly — weigh more than superficial acquaintances met only once. The attention mechanism does exactly that: it automatically learns which neighbors are most relevant for predicting the properties of each node.

In practice, multi-head attention is often used, where several independent attention heads are computed and then concatenated or averaged. This stabilizes the learning process and allows the model to capture different types of relationships between nodes.

Advantages of GAT: adaptive and weighted aggregation, multi-head attention to capture different types of relationships, applicable to directed and weighted graphs.

Limitations of GAT: higher computational cost (computing attention coefficients for each edge), sensitivity to overfitting on small graphs.

Deep Intuition: How a GNN “Thinks”

To properly understand the intuition behind Graph Neural Networks, imagine the following scene:

Imagine a social network. Each person (node) has their own opinions, skills, and characteristics (feature vector). Friendships between people are the edges of the graph.

Now, what happens when you want to understand a person you don’t know well? You naturally look at their friends. If most of their friends are artificial intelligence researchers, chances are that this person is in that field themselves. This is exactly the principle of graph homophily: connected nodes tend to share similar properties.

But not all friends are equal! A close friend with whom you collaborate daily has much more influence on your opinions than an acquaintance you met once at a conference. The GCN gives all neighbors equal weight (it’s the mean), while the GAT learns to differentiate the importance of each neighbor through attention.

At each propagation layer, information diffuses further:
– Layer 1: a node aggregates information from its direct neighbors.
– Layer 2: information comes from neighbors of neighbors (distance 2).
– Layer L: the node has received information from nodes at a maximum distance of L edges.

This is why the choice of the number of layers is crucial: too few layers and the node doesn’t have enough global context; too many layers and you fall into the over-smoothing phenomenon, where all nodes end up with identical representations.

Python Implementation with PyTorch Geometric

We will now implement a complete GCN for node classification on the Cora dataset, a scientific citation graph containing 2,708 papers (nodes) connected by 5,429 citations (edges). Each paper is labeled in one of 7 thematic categories.

Installing dependencies

pip install torch torchvision torchaudio --index-url https://download.pytorch.org/whl/cu118
pip install torch-scatter torch-sparse torch-cluster torch-spline-conv torch-geometric -f https://data.pyg.org/whl/torch-2.1.0+cu118.html
pip install matplotlib networkx

Complete Graph Neural Network Code

import os
import torch
import torch.nn.functional as F
from torch_geometric.datasets import Planetoid
from torch_geometric.nn import GCNConv
from torch_geometric.utils import to_networkx
import matplotlib.pyplot as plt
import networkx as nx

# --------------------------------------------------------------
# 1. Loading the Cora dataset
# --------------------------------------------------------------
def load_data():
    """Loads the Cora dataset: a scientific citation graph.

    Cora contains 2,708 papers in 7 categories,
    connected by 5,429 citation links.
    Each paper is represented by a vector of 1,433 keywords.
    """
    path = os.path.join(os.path.expanduser("~"), ".pyg", "data", "Cora")
    dataset = Planetoid(root=path, name="Cora")
    data = dataset[0]
    print(f"Number of nodes: {data.num_nodes}")
    print(f"Number of edges: {data.num_edges}")
    print(f"Feature dimensions: {data.num_node_features}")
    print(f"Number of classes: {dataset.num_classes}")
    return data, dataset.num_classes

# --------------------------------------------------------------
# 2. GCN model definition
# --------------------------------------------------------------
class GCN(torch.nn.Module):
    """Graph Convolutional Network (GCN) with two layers.

    Architecture:
        Layer 1: GCNConv(in_channels → hidden_channels) + ReLU + Dropout
        Layer 2: GCNConv(hidden_channels → num_classes)

    Message passing works by averaging neighbor representations
    then applying a linear transformation.
    """

    def __init__(self, in_channels, hidden_channels, num_classes, dropout=0.5):
        super().__init__()
        self.conv1 = GCNConv(in_channels, hidden_channels, cached=True)
        self.conv2 = GCNConv(hidden_channels, num_classes, cached=True)
        self.dropout = dropout

    def forward(self, x, edge_index):
        # First layer: projection + aggregation + ReLU
        x = self.conv1(x, edge_index)
        x = F.relu(x)
        x = F.dropout(x, p=self.dropout, training=self.training)

        # Second layer: projection to classes
        x = self.conv2(x, edge_index)

        return x

# --------------------------------------------------------------
# 3. Model training
# --------------------------------------------------------------
def train(model, data, epochs=200, lr=0.01, weight_decay=5e-4):
    """Trains the GCN using the provided training mask.

    Args:
        model: GCN instance
        data: PyG object containing x, edge_index, train_mask, y
        epochs: number of training iterations
        lr: learning rate
        weight_decay: L2 regularization

    Returns:
        loss and accuracy histories
    """
    optimizer = torch.optim.Adam(
        model.parameters(), lr=lr, weight_decay=weight_decay
    )

    history = {"train_loss": [], "train_acc": [], "val_acc": []}

    for epoch in range(epochs):
        model.train()
        optimizer.zero_grad()

        # Forward pass
        out = model(data.x, data.edge_index)

        # Loss computation (only on training nodes)
        loss = F.cross_entropy(out[data.train_mask], data.y[data.train_mask])

        # Backpropagation
        loss.backward()
        optimizer.step()

        # Evaluation
        acc_history = evaluate(model, data)
        history["train_loss"].append(loss.item())
        history["train_acc"].append(acc_history["train"])
        history["val_acc"].append(acc_history["val"])

        if (epoch + 1) % 20 == 0:
            print(f"Epoch {epoch+1:04d} | Loss: {loss.item():.4f} | "
                  f"Training accuracy: {acc_history['train']:.4f} | "
                  f"Validation accuracy: {acc_history['val']:.4f}")

    return history

def evaluate(model, data):
    """Evaluates model accuracy on training and validation masks."""
    model.eval()
    with torch.no_grad():
        out = model(data.x, data.edge_index)
        preds = out.argmax(dim=1)

    mask_train = data.train_mask
    mask_val = data.val_mask
    mask_test = data.test_mask

    acc_train = (preds[mask_train] == data.y[mask_train]).sum().item() / mask_train.sum().item()
    acc_val = (preds[mask_val] == data.y[mask_val]).sum().item() / mask_val.sum().item()
    acc_test = (preds[mask_test] == data.y[mask_test]).sum().item() / mask_test.sum().item()

    return {"train": acc_train, "val": acc_val, "test": acc_test}

# --------------------------------------------------------------
# 4. Graph and embedding visualization
# --------------------------------------------------------------
def visualize_graph(data, title="Cora Graph (200-node subsample)"):
    """Visualizes a subset of the graph with NetworkX and Matplotlib.

    Colors represent the different paper classes.
    This citation graph clearly shows the community structure:
    papers from the same thematic area form dense clusters.
    """
    G = to_networkx(data.cpu())

    # Subsample for readability
    import random
    random.seed(42)
    selected_nodes = random.sample(list(G.nodes), min(200, G.number_of_nodes()))
    G_sub = G.subgraph(selected_nodes)

    color_map = {i: data.y[n].item() for n in G_sub.nodes}
    colors = [color_map.get(n, 0) for n in G_sub.nodes]

    fig, ax = plt.subplots(figsize=(14, 10))
    pos = nx.spring_layout(G_sub, seed=42, k=0.3)

    nx.draw_networkx_nodes(G_sub, pos, node_size=30,
                          node_color=colors, cmap=plt.cm.tab10, ax=ax)
    nx.draw_networkx_edges(G_sub, pos, alpha=0.15, edge_color="gray",
                          width=0.5, ax=ax)

    ax.set_title(title, fontsize=16, fontweight="bold")
    ax.axis("off")
    plt.tight_layout()
    plt.savefig("cora_graph_visualization.png", dpi=150, bbox_inches="tight")
    plt.close()
    print("Visualization saved: cora_graph_visualization.png")

def visualize_embeddings(out, labels, title="GCN Projections (2 random classes)"):
    """Visualizes embeddings learned by the GCN via dimension reduction."""
    unique_classes = labels.unique().tolist()

    fig, ax = plt.subplots(figsize=(10, 8))
    palette = plt.cm.tab10

    for idx, cls in enumerate(unique_classes):
        mask = (labels == cls)
        out_cls = out[mask]

        # Simple reduction: projection onto first 2 dimensions
        if out_cls.shape[1] >= 2:
            x_proj = out_cls[:, 0].detach().cpu().numpy()
            y_proj = out_cls[:, 1].detach().cpu().numpy()
        else:
            x_proj = out_cls[:, 0].detach().cpu().numpy()
            y_proj = torch.zeros_like(x_proj).numpy()

        ax.scatter(x_proj, y_proj, alpha=0.7, label=f"Class {cls}",
                  color=palette(idx), s=50, edgecolors="white", linewidth=0.3)

    ax.set_xlabel("Embedding Dimension 1", fontsize=12)
    ax.set_ylabel("Embedding Dimension 2", fontsize=12)
    ax.set_title(title, fontsize=14, fontweight="bold")
    ax.legend(fontsize=10)
    ax.grid(True, alpha=0.3)
    plt.tight_layout()
    plt.savefig("cora_embeddings.png", dpi=150, bbox_inches="tight")
    plt.close()
    print("Embeddings saved: cora_embeddings.png")

# --------------------------------------------------------------
# 5. Main pipeline
# --------------------------------------------------------------
if __name__ == "__main__":
    torch.manual_seed(42)

    print("=" * 60)
    print("  Graph Neural Network — GCN Classification on Cora")
    print("=" * 60)

    # Loading
    data, num_classes = load_data()

    # Raw graph visualization
    visualize_graph(data)

    # Model construction
    model = GCN(
        in_channels=data.num_node_features,
        hidden_channels=64,
        num_classes=num_classes,
        dropout=0.5
    )
    print(f"\nGCN model created: {model}")
    n_params = sum(p.numel() for p in model.parameters() if p.requires_grad)
    print(f"Trainable parameters: {n_params}")

    # Training
    print("\n--- Training in progress ---")
    history = train(model, data, epochs=200)

    # Final evaluation
    results = evaluate(model, data)
    print(f"\n{'=' * 60}")
    print(f"  Final Results")
    print(f"{'=' * 60}")
    print(f"  Training accuracy : {results['train']:.4f}")
    print(f"  Validation accuracy: {results['val']:.4f}")
    print(f"  Test accuracy      : {results['test']:.4f}")

    # Embedding visualization
    model.eval()
    with torch.no_grad():
        out_embeddings = model(data.x, data.edge_index)
    visualize_embeddings(out_embeddings, data.y)

    print("\nTraining completed successfully!")

Detailed implementation explanations

This code implements a complete Graph Neural Network following the message passing philosophy:

1. GCNConv from PyTorch Geometric automatically performs normalized mean aggregation of neighbors. Internally, it builds the D̃^(-1/2) Ã D̃^(-1/2) matrix and performs the propagation.
2. Dropout is applied after each layer to regularize the model and prevent overfitting — a frequent problem when graphs are small or noisy.
3. The cached=True parameter tells the GCN to cache the normalized propagation matrix, which considerably speeds up training (the graph structure does not change between epochs).
4. The evaluation function computes accuracy on three distinct sets: training, validation, and test, allowing you to track the model’s generalization ability.

Hyperparameter Guide

Choosing hyperparameters is crucial for achieving good performance with a Graph Neural Network. Here are the most important parameters:

hidden_channels (hidden dimensions)

• Typical: 32 to 256
• Role: defines the dimension of the latent space into which node representations are projected.
• Advice: start with 64 or 128. For graphs with many features (like Cora with 1,433 dimensions), you can compress more. If the graph is rich in complex structural information, increase progressively.

num_layers (number of layers)

• Typical: 2 to 4 layers
• Role: determines the receptive field of message passing. With 2 layers, each node aggregates information from its neighbors and neighbors of neighbors (maximum distance 2).
• Advice: 2 layers is often optimal for most tasks. Beyond that, the over-smoothing phenomenon tends to equalize the representations of all nodes. If you absolutely need more layers, use residual connections or pair normalization.

dropout

• Typical: 0.3 to 0.6
• Role: regularization to prevent overfitting. Particularly important on small graphs where the model can easily memorize the structure.
• Advice: the smaller the graph, the higher the dropout should be. For Cora (2,708 nodes), 0.5 is a good starting point.

attention_heads (for GAT)

• Typical: 4 to 8 heads in hidden layers, 1 head at output
• Role: each head learns a different attention mechanism, thus capturing different types of relationships between nodes.
• Advice: in the last layer, a single head is generally used and outputs are averaged to obtain classification logits. In intermediate layers, concatenating 4 to 8 heads gives the best results.

Learning rate

• Typical: 0.001 to 0.01
• Advice: 0.01 works well for GCNs, but a scheduler (like ReduceLROnPlateau) can improve convergence on complex graphs.

L2 Regularization (weight_decay)

• Typical: 1e-4 to 5e-4
• Role: penalizes overly large weights, which helps generalize to unobserved nodes.

Advantages and Limitations of Graph Neural Networks

Advantages

1. Native exploitation of relational structure: unlike classical MLPs that treat each node independently, GNNs explicitly capture dependencies between connected nodes.
2. Inductive representation learning: models like GraphSAGE and GAT can generalize to graphs and nodes never observed during training (zero-shot generalization).
3. Architectural flexibility: the message passing paradigm is a general framework that can integrate many variants (attention, spectral convolutions, hierarchical pooling).
4. Relative interpretability: unlike classical deep networks, it is sometimes possible to trace neighbor contributions to understand why a node received a particular prediction, especially with attention mechanisms.
5. Multi-scale compatibility: GNNs work equally well for node classification, entire graph classification, or link prediction.

Limitations

1. Over-smoothing: with too many propagation layers, the representations of all nodes converge to the same value, destroying all discriminative information. This is the fundamental problem of deep GNNs.
2. Computational cost: GNNs require loading the graph (and its neighborhoods) in memory. For graphs with millions of nodes, sampling techniques (neighbor sampling, cluster-GCN) are essential.
3. Sensitivity to structure: performance depends heavily on the quality of the graph. A noisy or poorly constructed graph significantly degrades results.
4. Scaling: training a GNN on a graph of several hundred million nodes remains a major challenge that requires partitioning and distributed computing techniques.
5. Heterophily: the message passing paradigm assumes homophily (similar neighbors share labels). In heterophilous graphs (where neighbors have different labels), classical GNNs can perform poorly.

4 Concrete Use Cases of Graph Neural Networks

1. Drug Discovery

Molecules are naturally representable as graphs: atoms are nodes and chemical bonds are edges. Graph Neural Networks allow predicting the pharmacological properties of molecules (toxicity, binding affinity, solubility) directly from their atomic structure, without manual feature extraction. Companies like DeepMind and Insilico Medicine use GNN architectures to accelerate the discovery of drug candidates, reducing screening time from several months to a few days.

2. Recommendation Systems

E-commerce and streaming platforms build bipartite graphs connecting users to items they have viewed or purchased. A GNN can learn rich representations by propagating information through this graph: if user A and user B have similar tastes (they are connected to the same items), and B liked a new item that A hasn’t seen yet, the GNN can recommend that item to A. Pinterest uses this approach (PinSAGE) with graphs of several billion nodes.

3. Financial Fraud Detection

In financial transactions, bank accounts, merchants, and devices form a relationship graph. Fraudsters often create abnormal structures in this graph (rapid cycles, star-shaped intermediary accounts). Graph Neural Networks can detect these suspicious patterns by learning representations that capture both account attributes and transaction topology. Alipay uses GCNs to detect fraudulent transactions in real time with accuracy 20% higher than traditional methods.

4. Social Network Analysis and Community Detection

Graph Neural Networks excel at identifying communities and predicting links in massive social networks. By learning embeddings that preserve the local and global structure of the graph, GNNs can:
– Detect thematic communities (groups of users sharing interests)
– Predict future connections (link prediction)
– Classify accounts (bots vs authentic users, influencers vs followers)
– Analyze the spread of information or disinformation through the network

See Also

• Demystifying the ‘abc’ Module in Python: Complete Guide with Practical Examples
• Mastering the ‘Lights Out’ Game with Python: Complete Tutorial and Source Code