Graph Neural Networks and DGL: A Beginner's Guide

Jul 10, 2026·
Yassir Boulaamane
Yassir Boulaamane
· 8 min read

Most machine learning architectures operate on grid-structured inputs, such as tables or image pixel grids. However, molecular structures, citation networks, social graphs, and transport networks are structured as irregular graphs. Graph Neural Networks (GNNs) learn representation vectors directly from this non-Euclidean topology without requiring grid projection.

This guide provides an overview of GNN concepts, maps these structures to the Deep Graph Library (DGL), and defines key terminology.

1. What is a graph?

A graph is just two things: a set of nodes (the entities) and a set of edges (the connections between them). A citation network is papers connected by “cites” relationships. A molecule is atoms connected by bonds. A social network is people connected by friendships.

Graph Topology A B C D Graph Elements • Nodes (V) = {A, B, C, D} - Represent entities • Edges (E) = {(A,B), (A,C), (B,C), (B,D), (C,D)} - Connections Degree & Neighborhood • Degree: How many edges touch a node (e.g., Node B degree = 3) • Neighborhood: Directly connected nodes (e.g., N(A) = {B, C}) Adjacency Matrix (A) A_ij = 1 if edge exists else 0

Key terminology:

  • Directed vs. undirected: An edge can point one way ($A \rightarrow B$) or both ways. DGL edges are directed by default; an undirected graph is represented by defining edges in both directions.
  • Degree: The number of edges connected to a node (such as Node B degree = 3).
  • Neighborhood: The set of nodes directly connected to a given node. Node A’s neighborhood is $\{B, C\}$.
  • Adjacency matrix: A matrix representation of graph topology where cell $i, j$ is 1 if there is an edge from node $i$ to node $j$, and 0 otherwise. DGL stores this matrix in a compressed sparse format to optimize memory.

Nodes and edges hold associated feature vectors (g.ndata and g.edata). For example, an atomic node feature vector may encode element type and charge, while an edge feature vector represents bond characteristics.

2. Message Passing Workflows

GNN layers update node representations through a three-step message-passing sequence:

GNN Layer Message Passing Recipe 1. Message Step Neighbors send features along edges u₁ u₂ v msg₁ msg₂ 2. Aggregate Step Collect & combine (sum/mean/max) ∑ m_v = Aggregate({msg}) 3. Update Step Compute new target representation v h_v^(l) = Update(h_v^(l-1), m_v) Updated Feature!
  1. Message: Every node sends information along its edges, usually just its current feature vector or a transformed version of it.
  2. Aggregate: Every node collects the messages arriving from its neighbors and combines them, commonly by summing, averaging, or taking the maximum.
  3. Update: Every node combines the aggregated message with its own previous feature to produce a new feature.

In DGL, this whole cycle is executed in a single call to g.update_all(), using either a built-in message/reduce function or ones you write yourself. Stack this three-step recipe into multiple layers, and each node’s final representation encodes information from further and further away in the graph.

3. Stacking layers: how far can a node "see"?

A single message-passing layer only lets a node see its immediate neighbors, its 1-hop neighborhood. Stack a second layer, and information from those neighbors’ neighbors flows in too, representing a 2-hop neighborhood. A GNN with $K$ layers lets every node see $K$ hops away.

GNN Layer Stacking: Receptive Field & Over-smoothing 1-Hop (Layer 1) Can see direct neighbors w₁ w₂ u₁ u₂ u₃ u₄ v 2-Hop (Layer 2) Can see neighbors' neighbors w₁ w₂ u₁ u₂ u₃ u₄ v K-Hop (Over-smoothing) Too many layers = representations merge All nodes look identical!

Stacking GNN layers increases the receptive field but can introduce performance degradation. When layer count ($K$) is high, node representations tend to converge and become indistinguishable, a phenomenon termed over-smoothing. Practical applications typically use 2 to 4 layers.

4. Neighborhood Aggregation Functions: GCN, GAT, GraphSAGE

GNN architectures differ primarily in their neighborhood aggregation functions:

Architecture Aggregation Mechanism Characteristics
GCN (Graph Convolutional Network) Fixed weighting based on node degree; every neighbor contributes proportionally. The classic starting point; strong with just 2 layers.
GAT (Graph Attention Network) Learned attention score per neighbor, so more relevant neighbors count more. Multi-head attention runs several of these in parallel, then combines them.
GraphSAGE Samples a fixed number of neighbors per layer instead of using all of them. Built for huge graphs and for adding new nodes after training (inductive learning).

5. Downstream Prediction Tasks

Node representations support three primary downstream prediction tasks:

Three Core GNN Prediction Tasks Node Classification Predict properties of individual nodes ? Class: Active Link Prediction Predict if edge should exist between nodes p(Edge) = 0.92 Graph Classification Pool all node features for whole-graph label POOL Vector Label: Mutagenic
  • Node classification: Predict a label for each node. Example: Is this citation-network paper about biology or physics?
  • Link prediction: Predict whether an edge should exist between two nodes. It is trained using negative sampling, feeding the model real edges alongside randomly sampled non-edges so it learns to tell them apart.
  • Graph classification: Predict a label for an entire graph. Example: Is this molecule toxic? Since graphs vary in size, you need a readout (or pooling) step, typically summing or averaging all node embeddings into one fixed-size vector before classifying.

6. Training on graphs too big for GPU memory

Real graphs (like a full citation network or a social graph) can have millions of nodes - far more than can fit on a GPU at once. The fix is the same one used everywhere else in deep learning: mini-batches. But you can’t just grab a random slice of a graph, since a node’s prediction depends on its neighbors.

Neighbor sampling solves this: instead of using all of a node’s neighbors, sample a fixed number at each layer. This produces a small, bounded computational subgraph per training step instead of the whole graph.

Neighbor Sampling for Large-Scale Training u₃ u₄ u₅ u₁ u₂ Target How it works: • Mini-batching raw graphs is hard due to dependencies. • Solution: Sample a small, fixed number of neighbors per node (such as sample size = 2). • Unsampled nodes (u₃, u₄, u₅) and their edges are ignored. • This bounds memory size and allows GPU mini-batch training on graphs with billions of nodes.

The DGL GraphBolt framework implements this pipeline:

  1. An ItemSampler selects target nodes.
  2. A SubgraphSampler extracts local neighborhoods.
  3. A FeatureFetcher retrieves corresponding node and edge attributes.
  4. The result is a MiniBatch object that flows through training modules.

This modular design enables parallelized training across multi-GPU and distributed systems.

7. DGL Tutorial Pathways

Official DGL tutorials expand on these methodologies:

Series Scope Target Audience
Blitz Introduction Node classification, the DGLGraph object, writing custom message-passing layers, link prediction, graph classification, custom datasets Introductory reference.
Stochastic Training / GraphBolt Neighbor sampling, mini-batch node and link classification, multi-GPU training, building an OnDiskDataset Large-scale datasets.
Graph Transformer Positional encodings, multi-head attention over graphs Advanced transformer architectures.
dgl.sparse Expressing GNNs as sparse linear algebra, graph diffusion, hypergraphs Matrix-based formulations.
CPU Training Multi-core scaling with ARGO, CPU tuning Hardware-specific optimization.
Multi-GPU Training Distributed training on one machine Multi-GPU scale-up.
Distributed Training Training across multiple machines Multi-machine distributed systems.
Paper Study Faithful DGL implementations of GCN, R-GCN, GAT, Tree-LSTM, DGMG, and Capsule Networks Reference implementations for replication studies.

Glossary

Core Graph Concepts

Term Meaning
Graph Nodes connected by edges, written $G = (V, E)$.
Node / Vertex A single entity in the graph.
Edge A connection between two nodes; directed by default in DGL.
Heterogeneous Graph A graph with more than one type of node and/or edge.
Hypergraph A graph where one edge can connect more than two nodes.
Subgraph A smaller graph formed from a subset of nodes and edges.
Adjacency Matrix The graph written as a grid of 0s and 1s.
Degree How many edges touch a node.
Neighborhood The nodes directly connected to a given node.

GNN Concepts

Term Meaning
Message Passing Send $\rightarrow$ aggregate $\rightarrow$ update; the core GNN computation.
Node/Edge Feature A vector of numbers describing a node or edge.
Embedding A learned vector representation of a node, edge, or graph.
GNN Layer One round of message passing; $K$ layers reach $K$ hops.
Over-smoothing Too many layers make all node representations converge.
GCN / GAT / GraphSAGE Three popular message-passing architectures.
Readout / Pooling Combining all node embeddings into one graph-level vector.
Node / Link / Graph Class The three main prediction tasks on graphs.

Training Concepts

Term Meaning
Mini-batch Training Training on a small random subset instead of the whole graph.
Neighbor Sampling Sampling a fixed number of neighbors per layer to bound batch size.
Negative Sampling Adding fake edges as negative examples for link prediction.
Computational Subgraph The subgraph actually needed to compute one mini-batch.
Positional Encoding Extra node features (such as Laplacian eigenvectors) encoding position in Graph Transformers.

DGL-Specific Terms

Term Meaning
DGLGraph DGL’s core graph object, holding topology plus ndata/edata.
GraphBolt DGL’s pipelined framework for large-graph training.
MiniBatch The bundled object carrying a sampled subgraph through the pipeline.
OnDiskDataset A GraphBolt dataset format for graphs larger than RAM.
dgl.sparse.SparseMatrix DGL’s sparse matrix class for matrix-based graph operations.
update_all() DGL’s batched message-passing call.
DistGraph DGL’s distributed graph object for multi-machine training.
Graph Neural Networks DGL PyTorch Machine Learning Beginner Guide
Yassir Boulaamane
Authors
Yassir Boulaamane
Postdoctoral Researcher