Graph theory

The last lesson made a promise it could not keep on a straight line: it claimed the eigenvectors of a graph Laplacian generalise the Fourier basis to networks — yet we had no graph, no Laplacian, not even a definition of either. Time to build them, and in doing so close the whole math chapter where it has secretly been heading all along: turn structure into a matrix, and let linear algebra do the rest.

A graph is the most general way to write down things and the relationships between them — a set of nodes (vertices) joined by edges. Social networks, molecules, the web, knowledge bases, recommendation data: all graphs. And graphs are increasingly the structure ML itself runs on — a graph neural network passes messages along edges, and even attention can be read as a soft, fully-connected graph. The single object that makes all of it computable is the adjacency matrix.

From a graph to a matrix

Number the nodes 0 … n−1. The adjacency matrix A is n × n with A[i, j] = 1 when there’s an edge from i to j (and 0 otherwise; for weighted graphs, the weight). For an undirected graph A is symmetric. A node’s degree — how many edges touch it — is just the sum of its row.

Powers of A count walks

Here’s the payoff of turning the graph into a matrix: (A^k)[i, j] is the number of walks of length k from i to j. Squaring the adjacency matrix counts two-step paths; cubing it (and reading the diagonal) counts triangles:

import numpy as np

A = np.array([[0, 1, 0, 0],     # edges: 0-1, 1-2, 1-3, 2-3
              [1, 0, 1, 1],
              [0, 1, 0, 1],
              [0, 1, 1, 0]])

print("degrees:", A.sum(axis=1))
print("2-step walks (A @ A):")
print(A @ A)
print("triangles per node (diag(A^3)//2):", np.diag(A @ A @ A) // 2)

degrees: [1 3 2 2]
2-step walks (A @ A):
[[1 0 1 1]
 [0 3 1 1]
 [1 1 2 1]
 [1 1 1 2]]
triangles per node (diag(A^3)//2): [0 1 1 1]

A²[1,1] = 3 says there are three two-step walks from node 1 back to itself (out to each neighbor and back). And diag(A³)//2 = [0,1,1,1] says nodes 1, 2, 3 each sit on exactly one triangle — they form one. Matrix algebra is answering graph questions.

The Laplacian and random walks

Two more constructions carry most of graph ML:

• The graph Laplacian L = D − A, where D is the diagonal degree matrix. Its eigenvalues and eigenvectors (eigen-decomposition) encode connectivity: the number of zero eigenvalues equals the number of connected components, and the eigenvector of the second-smallest eigenvalue (the Fiedler vector) splits the graph into two well-separated halves — the basis of spectral clustering.
• Random walks and PageRank. Normalize the adjacency matrix into a transition matrix and you have a Markov chain on the graph. Its stationary distribution is PageRank: a node is important if a random walker spends a lot of time there. The famous web-ranking algorithm is just the stationary distribution of a random surfer.

In one breath

• A graph is nodes + edges; the adjacency matrix A (A[i,j]=1 for an edge, symmetric if undirected) turns it into something you can multiply, and a node’s degree is its row sum.
• Powers of A count walks: (A^k)[i,j] is the number of length-k walks from i to j (so A² counts 2-step paths, diag(A³)/2 counts triangles).
• The graph Laplacian L = D − A has a spectrum that encodes connectivity (zero eigenvalues = components; the Fiedler vector = a 2-way cut) — the engine of spectral clustering.
• A random walk on a graph is a Markov chain; its stationary distribution is PageRank (importance = where a random surfer dwells).
• ML hooks: GNNs (message passing = multiply by adjacency/Laplacian), knowledge graphs, spectral clustering, PageRank ranking, and recommendation.

Practice

A question to carry forward

That closes the whole math chapter — on its quietest, most powerful habit. Take anything — a transformation, a probability cloud, a signal, now a network — turn it into a matrix or an array of numbers, and let linear algebra and calculus do the work. Vectors, gradients, covariance, the Fourier basis, the adjacency matrix: every one was an array, and every worked example in every lesson was computed the same way — import numpy as np.

Which finally exposes the thing we have leaned on in nearly forty lessons and never once examined. We kept writing A @ A, rng.normal(...), np.fft.rfft, .sum(axis=1) as though arrays were free. They are not — a plain Python list of a million numbers is slow and bloated, yet NumPy multiplies a million of them in a blink. So the next section turns to the engine itself. What is a NumPy array, why is it so much faster and leaner than a Python list, and what does “vectorised” actually mean — the foundation that Pandas, scikit-learn, PyTorch, and JAX are every one of them quietly built upon?