A graph is nodes and edges. Write it as a matrix and every question about its shape becomes linear algebra: A[i][j] = 1 moves information one hop, the Laplacian counts the pieces, and a GNN is neighbor-averaging with learned weights.
Nodes hold the things (people, atoms, pages) and edges hold the relationships. The adjacency list stores a neighbour set per node — cheap for sparse graphs. The adjacency matrix stores every pair in an n × n grid — memory-hungry, but now every graph question is a matrix operation.
A[i][j] = 1 ⇔ edge i–jBFS keeps a queue: it finishes every node at distance d before touching distance d + 1, so first discovery is a shortest path in hops. DFS keeps a stack: it follows one branch to its end before backtracking, which is what finds components, cycles and topological order. Give the edges weights and Dijkstra is BFS with a priority queue.
queue → hop counts · stack → connectivityL = D − A is the matrix whose eigenvalues read structure without a single traversal: the number of zero eigenvalues equals the number of connected components, and the Fiedler vector splits the graph at its weakest seam. A GNN layer is the same adjacency multiply with learned weights: collect neighbours, average, transform, repeat — K layers, K hops.
L = D − A · Hᵏ⁺¹ = σ(A_norm Hᵏ W)Write a graph as a matrix (who connects to whom) and every question about its shape becomes linear algebra: multiplying by the adjacency matrix moves information one hop along the edges, and the eigenvectors of the Laplacian reveal how many pieces the graph has and where it is weakest. Graph neural networks are that matrix multiply with learned weights.
By the end you will be able to read a graph as a list or a matrix, run BFS and DFS and say what each one finds, compute shortest paths on weighted graphs with Dijkstra, read a Laplacian’s eigenvalues as components and bottlenecks, split a graph with the Fiedler vector, and explain a GNN layer as neighbor aggregation with learned weights.
When the connections between examples carry the signal, a flat table throws that signal away. A graph keeps it — and one matrix makes it computable.
A graph G = (V, E) is a set of nodes (or vertices) V and a set of edges E. Each edge joins two nodes. With a graph you can ask questions a table cannot answer: who is central, what is connected to what, how few hops between two things, where does the network fall apart.
Edges come in four flavours. They can be undirected (friendship — symmetric) or directed (a follow — one way only), and unweighted (the edge exists or it does not) or weighted (each edge carries a number: a distance, a cost, a strength).
| Graph type | What the edges mean | Example |
|---|---|---|
| Undirected, unweighted | Friendship: either you are friends or you are not | |
| Directed, unweighted | Following: one arrow, no obligation to follow back | X / Twitter |
| Undirected, weighted | Distances: each road has a length or travel time | Road map |
| Directed, weighted | Web links: a page points at another, with link strength | PageRank |
The core representation is the adjacency matrix A. For a graph with n nodes, A is n × n with A[i][j] = 1 when there is an edge from node i to node j, and 0 otherwise. For a weighted graph, A[i][j] is the weight. For an undirected graph, A is symmetric: A[i][j] = A[j][i]. The number of edges touching a node is its degree, and the degree matrix D is diagonal with those counts:
In code you often store the same graph as an adjacency list — a dictionary from each node to its neighbours. The two are interchangeable, and each wins in a different job:
| Operation | Adjacency list | Adjacency matrix |
|---|---|---|
| Walk a node’s neighbours | O(degree) — only real edges | O(n) — scans the whole row |
| Test whether edge u–v exists | O(degree) | O(1) — one lookup |
| Memory | O(V + E) — great for sparse graphs | O(V²) — mostly zeros in practice |
| Matrix operations / message passing | Needs conversion first | Natural: A @ H mixes neighbours |
Toggle any cell of the adjacency matrix to add or remove an edge. Click a node (or its button) to highlight its neighbours. Undirected graphs always keep A symmetric.
A list stores only real neighbours and is cheap for sparse graphs; the matrix spends n² cells but turns “is there an edge?” and every spectral operation into linear algebra.
A single matrix power answers “in how many ways can information travel from i to j in m steps?” That question is the bridge between graph structure and linear algebra.
A walk is any sequence of edges where each edge starts where the last one ended; nodes and edges may repeat. A path is a walk that never repeats a node. Every path is a walk, but a walk can loop forever without ever becoming a path. The triangle below shows why the distinction matters for counting — walks multiply, paths need care.
A graph is connected when every node can reach every other by some walk; a connected component is a maximal connected piece. Two triangles with no bridge are two components: no walk crosses from one to the other, so the adjacency matrix splits into two blocks and never mixes them.
This is the sentence to remember from the chapter: multiplying by A moves information one hop. A GNN layer does exactly this multiply, then learns which neighbour information to keep.
In the triangle graph, (A²)[0][0] = 2. What does that 2 count?
Breadth-first search grows in rings and finds fewest-hop routes. Depth-first search dives to the end of one branch and finds structure. The difference is one data structure: queue versus stack.
Breadth-first search (BFS) keeps a queue — first in, first out. It visits every node at distance 0, then every node at distance 1, then distance 2, and so on. Because discovery order is distance order, the first time BFS touches a node it has found a shortest path in hops. This is why hop counts in social networks (“how many introductions away?”) are a BFS question.
Depth-first search (DFS) keeps a stack — last in, first out. It follows one branch as far as it can before backtracking. The route it takes to a node is not the shortest one, but the shape of its exploration is exactly what finds connected components, detects cycles, and produces a topological ordering (the order backpropagation runs in). Both visit every node and edge once: O(V + E).
| Algorithm | Data structure | Finds | Use case |
|---|---|---|---|
| BFS | Queue (FIFO) | Shortest paths in unweighted graphs | Social distance, knowledge-graph traversal |
| DFS | Stack (LIFO) or recursion | Components, cycles, topological order | Connectivity, dependency ordering |
Run both algorithms from the same source. BFS keeps a queue and grows in rings; DFS keeps a stack and dives until it hits a dead end. The tree edges are the ones each algorithm actually used.
Both run in O(V + E). The difference is what they are for: BFS answers “how few hops?”, DFS answers “what is connected?” and produces cycle and ordering information.
The moral: “has been visited” and “is at its true distance” are different facts. Only BFS can claim the second one every time it visits.
from collections import deque
graph = {0: {1, 2}, 1: {0, 3}, 2: {0, 3, 5}, 3: {1, 2, 4},
4: {3, 6}, 5: {2, 6}, 6: {5, 4}}
def bfs(graph, start):
visited = {start}
order, dist = [], {start: 0}
queue = deque([start]) # FIFO
while queue:
node = queue.popleft()
order.append(node)
for neighbor in sorted(graph[node]):
if neighbor not in visited:
visited.add(neighbor)
dist[neighbor] = dist[node] + 1
queue.append(neighbor)
return order, dist
def dfs(graph, start):
visited, order = set(), []
stack = [start] # LIFO
while stack:
node = stack.pop()
if node in visited:
continue
visited.add(node)
order.append(node)
for neighbor in reversed(sorted(graph[node])):
if neighbor not in visited:
stack.append(neighbor)
return order
print(bfs(graph, 0)) # (order, {distances}) — shortest hops
print(dfs(graph, 0)) # order only — connectivity, cycles, orderingsFriendship edges all count one hop. You want the fewest introductions between two people. Which traversal gives the answer, and why?
Give every edge a cost and “shortest” stops meaning “fewest hops”. Dijkstra’s algorithm settles the cheapest node first and never has to reconsider.
A weighted graph attaches a number to every edge: a distance, a travel time, a price, a strength. Now the length of a route is the sum of its weights, and two routes with the same number of edges can cost wildly different amounts. BFS cannot tell them apart — it treats every edge as length 1.
Dijkstra’s algorithm is the fix. Keep a tentative distance for every node, ∞ except the source at 0. Repeatedly pick the unsettled node with the smallest tentative distance, declare it final, and relax its edges: for each neighbour, if going through the settled node is cheaper than the current best, update it. With a priority queue the whole thing runs in O((V + E) log V).
Weighted roads, cheapest route first. At each step Dijkstra settles the node with the smallest tentative distance, then relaxes its edges. Try comparing the final weights with the plain hop counts.
All weights equal → Dijkstra is BFS. Negative weights break it: the “settled can never improve” promise needs weights ≥ 0.
Every line is one settle plus the relaxations it causes. The bracket is the distance table (node 0 → node 5); bold marks what changed.
Why settling is safe. When u has the smallest tentative distance, every other route from the source must first reach some unsettled node x. That x already has d[x] ≥ d[u], and the rest of the route adds only non-negative weights — so no route through x can beat d[u]. The settling step is permanent, which is why each node is processed once.
One matrix built from the degrees and the edges. Its eigenvalues count the pieces of the graph and measure how close it is to falling apart — with no traversal at all.
The graph Laplacian is L = D − A: put each node’s degree on the diagonal, subtract the adjacency matrix, and every edge becomes a −1 in two symmetric spots. For the triangle:
Those eigenvalues are not decoration. They encode four facts worth memorising:
| Property | Plain English |
|---|---|
| All eigenvalues ≥ 0 | L is positive semi-definite — a sum of squares can never go negative. |
| Zero eigenvalues = connected components | One zero for a connected graph, k zeros for k separate pieces. |
| Smallest nonzero eigenvalue γ (the Fiedler value) | Algebraic connectivity: small γ means a bottleneck, a single weak seam holding the graph together. |
| Signs of the Fiedler vector | The natural two-way split: nodes on either side of the seam get opposite signs. |
Two triangles (nodes 0–2 and 3–5) joined by adjustable bridges. L is computed live, its Fiedler vector colours every node, and the dashed edges are the ones the sign split cuts. Add bridges and watch γ rise.
One bridge: λ₂ ≈ 0.438 and the cut is exactly that bridge. More bridges raise λ₂ (1, 2, 2.268 …) and make the two communities harder to separate — spectral clustering is a relaxation of minimum cut.
Second fully worked example — the 4-node path. Nodes 0–1–2–3 in a line have L = [[1,−1,0,0],[−1,2,−1,0],[0,−1,2,−1],[0,0,−1,1]]. Its exact eigenvalues are 0, 2 − √2, 2, 2 + √2 ≈ 0, 0.586, 2, 3.414, and the Fiedler vector is proportional to (1, √2 − 1, −(√2 − 1), −1):
A graph has two connected components. What does the spectrum of its Laplacian contain?
Signs of the Fiedler vector split a graph in two. The stationary distribution of a random walk with restart ranks its nodes. Both come from the same idea: an eigenvector is a fixed shape of a repeated operation.
Spectral clustering turns the Laplacian’s eigenvectors into coordinates. The recipe: build L, take the k smallest eigenvectors (skipping the trivial all-ones one for a connected graph), use each node’s eigenvector values as its new coordinates, then run k-means — or for k = 2, just split by the sign of the Fiedler vector. The eigenvectors of L are the smoothest functions on the graph: nodes joined by many edges get similar values, so the first non-trivial one changes sign exactly where the graph is easiest to cut. Spectral clustering is a relaxation of the minimum-cut problem.
PageRank points the same machinery at directed graphs. Imagine a surfer on the web graph: with probability d they follow a random outgoing link; with probability 1 − d they get bored and restart on a uniformly random page. The long-run fraction of time spent on each page is its PageRank — the stationary distribution of a random walk with restart. Writing it out for one page v:
A surfer follows a random link with probability d, and restarts on a random page with probability 1 − d. Run the power iteration and watch the scores settle. Bigger node = more important.
Converged values here are ≈ 0.364, 0.192, 0.325, 0.119: node 0 beats the busier node 2 because the most important page links to it — rank is recursive. At d → 1 the walk trusts links almost fully; at d → 0 everyone is equal.
The lab graph is 0 → 1, 2 · 1 → 2, 3 · 2 → 0 · 3 → 0, 2, with out-degrees (2, 2, 1, 2). Start uniform and apply the formula with d = 0.85, so the restart term is (1 − 0.85)/4 = 0.0375.
Notice the surprise: node 2 receives links from three pages, yet node 0 finishes on top. Node 2 is the hub everyone points at, and the hub itself points at node 0 — importance is recursive, which is exactly the property that made PageRank beat counting in-links. Power iteration converges because the restart term keeps rank from getting stuck in cycles; each round is one matrix–vector multiply, and a network with billions of pages still needs only a few dozen rounds.
The same picture for clustering, with exact numbers. Take two triangles joined by a single bridge (the lab above with one bridge): eigenvalues 0, (5 − √17)/2 ≈ 0.438, 3, 3, 3, (5 + √17)/2 ≈ 4.562. The Fiedler vector is proportional to (0.465, 0.465, 0.261, −0.261, −0.465, −0.465): positive on one triangle, negative on the other, with the smallest magnitudes at the two bridge endpoints. The sign split cuts exactly the bridge — the minimum cut. Add bridges and γ rises (≈ 1, 2, 2.268 for two, three, four bridges), and the two communities become harder to separate.
A graph neural network is one operation repeated: every node collects its neighbours’ features, aggregates them, transforms them with shared learnable weights, and does it again. K rounds reach K hops.
The core operation of a Graph Neural Network (GNN) is message passing. Each node v holds a feature vector h_v — its current description. One round replaces it with a function of its neighbourhood:
Each node averages its neighbours’ feature vectors (its own too, with self-loops), multiplies by a shared weight matrix W, and applies ReLU. Step the rounds and watch colour diffuse along the path.
After 1 round, node 0 holds information from nodes {0, 1} — its 1-hop neighbourhood. A K-layer GNN has a K-hop receptive field; too many rounds blend every colour into the same average.
The source example: three fully connected nodes A, B, C with features h_A = [1, 0], h_B = [0, 1], h_C = [1, 1]. Every node has degree 2, so A_norm is the adjacency matrix with each row divided by 2.
Self-loops and symmetric normalization. The classic GCN adds the node’s own feature by setting  = A + I, then divides each entry by √(dᵢdⱼ) instead of the row sum: A_norm = D̂^(−1/2)  D̂^(−1/2). On the triangle every degree becomes 3, so the operator is a plain average over the closed neighbourhood — a node keeps a third of itself:
Why not just sum the neighbours? A hub with 1,000 neighbours would hand back a vector 1,000× larger than a leaf, and after a few layers the largest-degree node would dominate every number. Dividing by degree — and symmetrically by √(dᵢdⱼ) — makes every node’s update comparable, the same trick normalization layers use elsewhere.
import numpy as np
def message_pass(A, H, W, self_loops=True):
"""One GNN layer: aggregate neighbours, transform, activate."""
if self_loops:
A = A + np.eye(A.shape[0]) # GCN-style A_hat = A + I
d = A.sum(axis=1)
A_norm = A / np.sqrt(np.outer(d, d)) # D^-1/2 A D^-1/2
else:
row_sums = A.sum(axis=1, keepdims=True)
A_norm = A / np.maximum(row_sums, 1) # plain mean over neighbours
return np.maximum(0, A_norm @ H @ W) # ReLU(A_norm @ H @ W)
A = np.array([[0, 1, 1], [1, 0, 1], [1, 1, 0]], float)
H = np.array([[1, 0], [0, 1], [1, 1]], float) # one feature vector per node
W = np.array([[1, 0.5], [0.5, 1]], float) # learned: trains like any layer
for round_number in range(1, 4):
H = message_pass(A, H, W)
print(f"round {round_number}:")
print(np.round(H, 3)) # each round: one more hopYou run two rounds of mean-aggregation message passing on a connected graph. Whose original features can influence a given node now?
Answer before you look. The Laplacian and message-passing questions are the ones that turn “I’ve seen a graph” into “I can use one”.
0 / 5 answered · 0 correct
01What does an entry A[i][j] = 1 in the adjacency matrix represent?
02What data structure does BFS use, and what does it find?
03The Laplacian L = D − A of a connected graph has how many zero eigenvalues?
04In GNN message passing, h_v^(k+1) = σ(W · mean{h_u^(k) : u ∈ neighbours(v)}) computes…
05How does spectral clustering use the Fiedler vector (the eigenvector of L's second-smallest eigenvalue)?
Click a card to swap the lazy description for what it actually means.
Five problems, all fully worked with numbers you can check by hand. Try first; the answer is one click away.
With n = 4 the restart term is 0.0375 per round. Round 1: π(0) = 0.0375 + 0.85·(0.25 + 0.125) = 0.35625; π(1) = 0.0375 + 0.85·0.125 = 0.14375; π(2) = 0.0375 + 0.85·0.375 = 0.35625; π(3) = 0.14375. Sum = 1 ✓. Round 2: π(0) = 0.0375 + 0.85·(0.35625 + 0.071875) = 0.40141; π(1) = 0.0375 + 0.85·0.178125 = 0.18891; π(2) = 0.0375 + 0.85·0.321875 = 0.31109; π(3) = 0.0375 + 0.85·0.071875 = 0.09859. Continuing to convergence gives (0.3640, 0.1922, 0.3246, 0.1192). Node 0 finishes above node 2 even though node 2 has more in-links: node 2 is the hub, and the hub links to node 0 — rank is recursive. At every round Σπ = 1 because the restart term injects exactly (1−d) and the d part only moves rank along edges.
L is block diagonal except the 2–3 entries: degrees are (2,2,3,3,2,2), so the diagonal is 2,2,3,3,2,2 and off-diagonal entries are −1 per edge. Eigenvalues: 0, (5−√17)/2 ≈ 0.438, 3, 3, 3, (5+√17)/2 ≈ 4.562. Check the trace: the eigenvalues sum to 14 = 2 + 2 + 3 + 3 + 2 + 2 (sum of degrees = 2 × 7 edges) ✓. The Fiedler vector is proportional to (0.465, 0.465, 0.261, −0.261, −0.465, −0.465): positive on triangle A, negative on triangle B, smallest magnitude at the two bridge endpoints. Splitting by sign cuts only edge 2–3 — the minimum cut. Adding bridges raises λ₂ (≈ 1 for two bridges, 2 for three, 2.268 for four in the lab), because the two communities are now genuinely better connected and harder to separate. Bonus check: the product of the nonzero eigenvalues divided by n equals the number of spanning trees: (0.438·3·3·3·4.562)/6 = 54/6 = 9 = 3 trees per triangle × the one mandatory bridge ✓.
Trace: settle 0 (0), relax 1←4, 2←1; settle 2 (1), relax 1←1+2=3, 3←9, 4←11; settle 1 (3), relax 3←3+5=8; settle 3 (8), relax 4←8+2=10, 5←14; settle 4 (10), relax 5←10+3=13; settle 5 (13). Final distances [0, 3, 1, 8, 10, 13] with the route to 5 being 0 → 2 → 1 → 3 → 4 → 5 (1+2+5+2+3 = 13 ✓). With all weights 1, Dijkstra's priority queue settles in nondecreasing hop order and the distances become the BFS hop counts [0, 1, 1, 2, 2, 3] — the two algorithms agree exactly, so BFS is the special case of Dijkstra where every edge costs the same. Note the disagreement on weights: nodes 1 and 2 are both one hop away, but node 2 costs 1 and node 1 costs 3.
Round 1: A_norm = A/2 (each node has degree 2), so A_norm @ H = [[0.5, 1], [1, 0.5], [0.5, 0.5]]; multiplying by W₁ = I and ReLU leaves it unchanged. Round 2: A_norm @ H₁ = [[0.75, 0.5], [0.5, 0.75], [0.75, 0.75]] — node A averaged B's and C's round-1 vectors, which already contained A's original feature, so all three original features are present. Then W₂: h_A = [0.75 + 0.25, 0.375 + 0.5] = [1.0, 0.875], h_B = [0.875, 1.0], h_C = [1.125, 1.125] (ReLU changes nothing). Check the two-hop claim directly: on this graph every node is within 2 hops of every other (the diameter is 1), so the second round places the whole graph's information in each node — the general statement is that K rounds collect the K-hop neighbourhood.
L = [[1, −1, 0, 0], [−1, 2, −1, 0], [0, −1, 2, −1], [0, 0, −1, 1]]. Exact eigenvalues: 0, 2 − √2 ≈ 0.5858, 2, and 2 + √2 ≈ 3.4142. Trace check: their sum is 6 = 1 + 2 + 2 + 1 ✓. Fiedler vector (unnormalised, sign fixed by the first entry): v = (1, √2 − 1, −(√2 − 1), −1) ≈ (1, 0.414, −0.414, −1). First row of Lv: 1·1 − (√2 − 1) = 2 − √2 = λ₂·1 ✓. Second row: −1 + 2(√2 − 1) − (−(√2 − 1)) = 3√2 − 4 ≈ 0.243, and λ₂·(√2 − 1) = (2 − √2)(√2 − 1) = 3√2 − 4 ✓. The sign split cuts the middle edge 1–2: positive {0, 1}, negative {2, 3} — the only cut of a path that splits it into two pieces of equal size. Spanning trees: the product of nonzero eigenvalues divided by n is (2 − √2)·2·(2 + √2)/4 = (2 · (4 − 2))/4 = 1, and a path has exactly one spanning tree ✓.
You do not need to master these here. Each one gets a proper treatment in its own lesson; the one-line meaning is enough to keep reading. Orange dotted underlines in the prose point back to this list.
This lesson is a port of an open course. Everything here traces back to it — and the next step is running the code yourself.
Lesson text adapted from AI Engineering from Scratch (Phase 01, Lesson 21) and the Math Foundations Notebook reference build. The graph builder, BFS/DFS stepper, Dijkstra stepper, PageRank lab, Laplacian/Fiedler lab and message-passing lab are original to this page, as are the exact (5 ± √17)/2 dumbbell eigenvalue, the 4-node-path worked eigendecomposition, the second worked message-passing round, the Matrix-Tree spanning-tree checks and the fully worked exercise answers. Every displayed number is computed in your browser from the values shown. All labs run in your browser.