Skip to content
Multigrid

Machine learning on graphs

Embeddings, GNNs, sampling and link prediction — modelling data whose structure is the signal.

Most machine learning assumes your rows are independent. Graph machine learning is what you do when they are not — when the interesting thing about a record is not its own columns but who it is connected to, and who they are connected to. A payment is unremarkable; a payment between two accounts that share a device fingerprint with four others is not. Flattening that into a feature table destroys exactly the signal you came for, because the useful structure lives two and three hops out and there is no column for it.

These pages work from the structure inward. Each one is built on a graph small enough to draw and arithmetic small enough to redo by hand, because the algorithms here are short and the intuitions people carry about them are frequently wrong in a specific, checkable way. Where a published paper defines a parameter, the parameter is named and the paper is linked. Where a method has a failure mode that a demo will never show you — a bipartite graph where every common-neighbour score is zero, a random walk that never converges, a pooling layer that cannot tell a molecule from two copies of it — that failure mode is the point of the page, not a footnote.

Link Prediction in a Graph, Explained

How neighbourhood-overlap scores rank missing edges, worked by hand on an eight-edge graph, and why the obvious evaluation metric lies.

9 min read

Node Embeddings: node2vec and DeepWalk Explained

The random-walk-then-skip-gram pipeline worked end to end, including the exact p and q transition probabilities on a five-node example.

10 min read

Graph Classification With Graph Neural Networks

How a GNN turns a variable-size graph into one label, why the pooling choice decides what the model can distinguish, and where the whole approach hits a proven ceiling.

10 min read

Detecting Fraud Rings With Graph Analysis

How shared attributes turn independent-looking accounts into a dense subgraph, with the projection and density calculation worked on six accounts.

10 min read

Recommendation Systems Built on Graph Embeddings

What treating the interaction matrix as a bipartite graph adds over classical collaborative filtering, worked on a three-user example, plus the propagation rule LightGCN actually uses.

10 min read

Detecting Bot Networks With Graph Analysis

The full detection pipeline — building a co-activity graph, layering behavioural signals on topology, and the base-rate arithmetic that decides whether it is usable.

10 min read

Knowledge Graph Embeddings: TransE and How Entities Become Vectors

How a relation becomes a translation vector, with the scoring function, the ranking loss and a gradient step worked on a two-dimensional triple.

10 min read

Graph Attention Networks Explained

What GAT computes that a graph convolution cannot, with the attention coefficients for one node's neighbourhood calculated end to end.

9 min read

Supply Chain Risk Mapped as a Network

How to find a single point of failure in a supplier network, with degree, betweenness and articulation points computed on the same seven-node graph — and why they disagree.

10 min read

Citation Network Analysis Explained

Why citation counts and network centrality rank papers differently, derived exactly on a nine-node network where the two orderings invert.

10 min read

Random Walk Algorithms on Graphs, Explained

The transition matrix, the stationary distribution and the two conditions it needs — with a worked five-node graph that satisfies one of them and not the other.

10 min read

Graph-Based Anomaly Detection for Transaction Networks

How a transaction pattern that is unremarkable at every individual account becomes obvious once you score the subgraph it forms.

9 min read

Scaling a GNN to a Billion-Node Graph

Derives the memory a billion-node graph actually needs from its node count, feature dimension and sampling fan-out, and shows which number is the wall.

10 min read

Temporal Graph Networks: Modelling a Graph That Changes Over Time

The architecture for graphs where edges appear and disappear, and why a per-node memory vector is what makes it work.

10 min read

Heterogeneous Graphs: When Nodes and Edges Are Not All One Type

Why a single GNN layer cannot aggregate over two node types and two edge types at once, and what the standard architectures do instead.

10 min read

Graph Sampling Strategies for Graphs Too Large to Fit in Memory

Neighbour sampling and subgraph sampling produce different memory curves and different biases; this works both and says when each one is wrong.

10 min read

Detecting Cycles and Loops in a Dependency Graph

A depth-first cycle detector that reports the actual cycle path, why the obvious visited-set version is wrong, and what to use when there are many cycles.

9 min read

Measuring Graph Density and What It Predicts About a Network

How density is computed, why it is nearly useless for comparing graphs of different sizes, and what to report instead.

9 min read

Cold-Start Link Prediction for a New Node With No Edges

Every topological link-prediction score is identically zero for a node with no edges; here is what replaces it and how to evaluate it honestly.

10 min read

Building a Graph From Tabular Relationship Data

Turning foreign-key tables into an edge list and a feature matrix, including the id remapping that every graph library requires and no CSV has.

10 min read

Why a Graph Neural Network Gets Worse With More Layers

Oversmoothing, derived from a four-node graph where the node features converge to a single value, plus the mitigations that actually work.

11 min read

What Training a GNN on a Real-World Graph Actually Costs

Derives the compute, the data movement and the GPU-hour bill for one training run from a stated graph size, epoch count and hourly price.

11 min read

Other topics