Graphs for ML & Knowledge Graphs

Every tool in this chapter — BFS, DFS, adjacency lists, edge walks — arrived as a way to solve graph puzzles. It turns out those same plain primitives sit underneath some of the most valuable ML systems running today. This lesson maps the graph ideas you already hold onto their machine-learning counterparts.

Knowledge graphs: facts as triples

A knowledge graph stores the world as triples — (subject, predicate, object). The nodes are entities, and each edge carries a typed label, which is richer than a plain adjacency list:

A language model generates fluent text but has no reliable grip on specific facts — which drug interacts with which, who currently runs a company. GraphRAG (Graph Retrieval-Augmented Generation) grounds it: instead of fetching a flat list of text chunks, the system does a BFS out to two or three hops around the query’s entities and hands the model that structured neighbourhood. The model receives verifiable, related facts rather than ambiguous prose — and the retrieval step is exactly the “print everything within k hops” traversal you already wrote.

Node embeddings: word2vec for graphs

Word2vec learns a vector per word by predicting a word from the words around it. DeepWalk and node2vec take that idea to graphs: run many random walks — a probabilistic stroll along the adjacency list — and treat each walk as a sentence of node IDs. Train word2vec on those sentences, and nodes that keep showing up near each other land close in vector space. Now you can measure similarity between nodes, cluster them, or feed the vectors to a classifier — never touching the raw graph again. The walk is just a randomised neighbour traversal of the structure you already built.

Graph Neural Networks: message passing

A GNN turns “aggregate your neighbours” into a learnable step. Each node starts with a feature vector, and one round of message passing goes: every node sends its vector to its neighbours; each node aggregates what it receives (mean, sum, or max); each node updates itself from its old vector plus that aggregate. Stack k rounds, and a node’s vector carries information from everything within k hops — the same radius idea as BFS depth. Here is the simplest possible layer, mean-aggregation, run twice by hand:

graph = {"A": ["B","C"], "B": ["A","D"], "C": ["A","D","E"], "D": ["B","C"], "E": ["C"]}
features = {"A": 1.0, "B": 3.0, "C": 2.0, "D": 5.0, "E": 4.0}

def message_pass(graph, feat):
    return {node: sum(feat[n] for n in nbrs) / len(nbrs)      # mean of neighbours
            for node, nbrs in graph.items()}

f1 = message_pass(graph, features)
f2 = message_pass(graph, f1)
print("round 0:", features)
print("round 1:", {k: round(v, 3) for k, v in f1.items()})
print("round 2:", {k: round(v, 3) for k, v in f2.items()})

round 0: {'A': 1.0, 'B': 3.0, 'C': 2.0, 'D': 5.0, 'E': 4.0}
round 1: {'A': 2.5, 'B': 3.0, 'C': 3.333, 'D': 2.5, 'E': 2.0}
round 2: {'A': 3.167, 'B': 2.5, 'C': 2.333, 'D': 3.167, 'E': 3.333}

After one round, A holds the average of B and C (its direct neighbours); after two, A’s value has been touched by D and E as well — nodes two hops away. In a real GNN the aggregation is a learned weighted sum with a nonlinearity, but the traversal logic is exactly what you see here.

PageRank: importance flows along links

PageRank scores a node by imagining a random surfer who, at each step, follows a random outgoing edge with probability d (the damping factor, usually 0.85) or teleports to a random node otherwise. The teleport keeps “dangling” nodes from draining all the importance away. The steady-state chance of being at a node is its score, computed by repeating one update — PR(v) = (1−d)/N + d · Σ PR(u)/out_degree(u) over v’s in-neighbours — until the numbers stop moving (power iteration, usually 20-50 rounds). In adjacency-list terms, each round is a single O(V + E) pass over the edges.

Practice