Graph Neural Networks and DGL: A Beginner's Guide
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.
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:
- Message: Every node sends information along its edges, usually just its current feature vector or a transformed version of it.
- Aggregate: Every node collects the messages arriving from its neighbors and combines them, commonly by summing, averaging, or taking the maximum.
- 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.
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:
- 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.
The DGL GraphBolt framework implements this pipeline:
- An
ItemSamplerselects target nodes. - A
SubgraphSamplerextracts local neighborhoods. - A
FeatureFetcherretrieves corresponding node and edge attributes. - The result is a
MiniBatchobject 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. |
