Graph Neural Networks and DGL: A Beginner's Guide

Most machine learning models expect data in a grid: rows and columns, or pixels in a fixed layout. A lot of real data doesn’t look like that. Molecules, social networks, citation networks, and road maps are all made of things connected to other things, in no fixed order and no fixed number. That’s a graph, and a Graph Neural Network (GNN) is a model built specifically to learn from that structure instead of forcing it into a grid.

This guide builds up the core ideas from scratch, with diagrams at each step, maps out where to go next in DGL’s official tutorials, and closes with a glossary you can use as a reference.

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.

A few basics worth knowing by name:

• 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 just one where every edge exists in both directions.
• Degree: How many edges touch a node. Node B in the diagram has degree 3.
• Neighborhood: The set of nodes directly connected to a given node. Node A’s neighborhood is $\{B, C\}$.
• Adjacency matrix: The same graph, written as a grid of 0s and 1s instead of a picture. Row $i$, column $j$ is 1 if there’s an edge from node $i$ to node $j$. For large graphs this matrix is mostly zeros, so DGL stores it in a compressed sparse format rather than a dense grid.

Every node and edge can also carry a feature vector, which is just a list of numbers describing it. In DGL, these live in g.ndata for nodes and g.edata for edges. An atom’s feature vector might encode its element type and charge; a bond’s might encode whether it’s single, double, or aromatic.

2. Message passing: how a GNN actually learns

This is the single idea that everything else in GNNs builds on. Every GNN layer runs the same three-step recipe for every node in parallel:

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.

More layers sounds strictly better, but it isn’t. Stack too many, and every node’s neighborhood eventually overlaps with almost the whole graph. All the node representations start to look alike, a problem called over-smoothing. In practice, most GNNs use only 2 to 4 layers.

4. Three ways to combine messages: GCN, GAT, GraphSAGE

The message-and-aggregate recipe is generic. Different GNN architectures mostly differ in how they aggregate:

5. What can you actually predict?

Once you have node representations from message passing, there are three common things to do with them:

• 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.

DGL’s GraphBolt framework is built around exactly this pipeline:

1. An ItemSampler picks target nodes.
2. A SubgraphSampler samples their neighborhoods.
3. A FeatureFetcher pulls in the relevant features.
4. The result is a MiniBatch, a single bundled object that flows through the rest of training.

This is also what makes multi-GPU and multi-machine training possible, as each GPU or machine just handles its own stream of mini-batches.

7. Where to go next: the official tutorial map

Once the ideas above feel solid, the official DGL tutorials go deeper on each one, in this rough order:

Glossary

Core Graph Concepts

GNN Concepts

Training Concepts

DGL-Specific Terms