A graph is a matrix, and its paths are its powers

Nodes, edges, and a grid of zeros and ones

A graph is a set of things and a set of connections between them: pages and links, users and follows, papers and citations, atoms and bonds. Write the things down the side and across the top of a grid, put a 1 wherever two are connected and a 0 elsewhere, and you have the adjacency matrix. Everything in module 2 now applies to it.

Four nodes in a square, 1 joined to 2, 2 to 3, 3 to 4, 4 to 1:

      1  2  3  4
  1 [ 0  1  0  1 ]
  2 [ 1  0  1  0 ]
  3 [ 0  1  0  1 ]
  4 [ 1  0  1  0 ]

The row sums are the degrees, how many neighbours each node has: 2 each. For a directed graph the matrix need not be symmetric; a link from 1 to 2 puts a 1 in row 1, column 2, and nothing in row 2, column 1.

Paths are powers

Multiply the matrix by itself. Entry (i, j) of A² is the dot product of row i with column j, which counts the nodes k such that i connects to k and k connects to j: the number of two-step paths from i to j. For the square:

        1  2  3  4
  1  [  2  0  2  0 ]
  2  [  0  2  0  2 ]
  3  [  2  0  2  0 ]
  4  [  0  2  0  2 ]

Two two-step paths from 1 to 3, via 2 and via 4; two from 1 back to itself, out and back along either edge; none from 1 to 2, which is an odd number of steps away. A³ counts three-step paths, and in general A^k counts walks of length k. Whether two nodes are connected at all is whether any power has a non-zero entry between them. That is how "friends of friends" and "papers citing papers that cite this one" are computed: one matrix multiply per hop.

Random walks and the vector that stops changing

Divide each row by its degree and the matrix becomes a transition matrix P: entry (i, j) is the probability that a walker at i steps to j. Multiply a probability vector by P and you get where the walker is expected to be one step later. Do it again and again, and for most graphs the vector settles to one that no longer changes, the stationary distribution: the fraction of time a long random walk spends at each node.

Three pages: A links to B and C, B links to C, C links to A.

start:   (1/3, 1/3, 1/3)
step 1:  (0.333, 0.167, 0.500)
step 2:  (0.500, 0.167, 0.333)
step 3:  (0.333, 0.250, 0.417)
   ...
limit:   (0.400, 0.200, 0.400)

The walker spends 40 per cent of its time at A and at C and 20 per cent at B. That vector is the eigenvector of P with eigenvalue 1, module 2's "direction the matrix does not turn", and repeated multiplication finds it because every other component decays.

This is PageRank, before its one refinement: with probability 0.15 per step the walker jumps to a random page, which stops it being trapped in a page with no outgoing links or circling forever in a closed loop. The refinement changes the matrix slightly and the arithmetic not at all. Google's original ranking was the stationary distribution of a random walk on the web, computed by repeated multiplication of a matrix with a few billion rows.

Sparse, or it does not exist

A graph with a billion nodes has an adjacency matrix with 10^18 entries. Nobody stores that; as float32 it is four million terabytes. But the web has perhaps a hundred links per page, so only 10^11 entries are non-zero, a ten-millionth of the matrix. Store the edge list, (from, to) pairs, and multiply by iterating the edges: the cost is the number of edges, not the square of the nodes. Module 1's sparse-versus-dense distinction is the whole difference between a computation that takes a minute and one that cannot start.

A graph neural network is one matrix multiply

Give each node a feature vector and stack them as rows of a matrix X. Then A X replaces each node's features with the sum of its neighbours' features, and D^(−1) A X, dividing by degree, with the average. Follow that with a weight matrix and a nonlinearity:

X_next = ReLU( D^(−1) A X W )

That is a graph convolution layer: average your neighbours, then apply a learned linear map. Stack k of them and each node has seen information from k hops away, which is A^k again. The models that predict molecular properties, detect fraud rings and recommend friends are variations on this one line, and the adjacency matrix is the part that makes them graph models rather than ordinary ones.

Doing it yourself

import numpy as np
A = np.array([[0,1,0,1],[1,0,1,0],[0,1,0,1],[1,0,1,0]])
print(A @ A)                                 # two-step path counts
P = A / A.sum(axis=1, keepdims=True)         # transition matrix
v = np.ones(4) / 4
for _ in range(50): v = v @ P                # random walk
print(v)                                     # stationary distribution

The networkx library does all of this for real graphs, free, on a laptop, and its pagerank function is the loop above with the jump added. The value of having done it by hand once is that every graph algorithm you meet afterwards reads as a matrix operation you already know.