Daniel Boudreau · Graph lab

The Lab · Latent space

Graph lab

Models do better when they can see who depends on whom. Six exhibits put graph structure to work on ordinary data: query a service dependency graph, run a graph neural network layer by hand, learn node embeddings from random walks, retrieve facts by following links instead of matching words, find the single points of failure in a platform, and measure the three ways graph learning most often goes wrong.

Everything runs in this tab: every algorithm on the page is implemented here, with a seeded generator so every visitor sees the same numbers. Northwind Cloud, its services, teams, incidents and facts are fictional. Zachary's karate club (W. W. Zachary, 1977) is the classic public toy graph of 34 club members. Only your progress is saved.

Exhibit I · A graph you can query

The service dependency graph of Northwind Cloud

A property graph stores typed nodes (teams, services, databases, queues, libraries, regions, dashboards) and typed, directed edges with properties (latency, calls per second, criticality). A pattern such as the one below is answered by following edges hop by hop.

(Team)-[OWNS]->(*)-[READS]->(Database)

Pick a preset question or build a pattern of up to 3 hops. Every matching path is highlighted on the drawing and listed underneath.

Preset questions

Your pattern

Hops

Start at

End at

No pattern run yet.

Inspect a node (the list view of the drawing)

The maths

Number the n nodes and write the adjacency matrix A with A_ij = number of edges from i to j. For one hop of a typed pattern keep only the edges of that type between nodes of those types, giving A₁, A₂, A₃.

(A^k)_ij = number of walks of length k from i to j, typed: (A₁A₂⋯A_k)_ij

Why. (A²)_ij = ∑_m A_imA_mj counts every middle node m with an edge in and an edge out, which is a walk of length 2; induction on k gives the rest. Walks against paths. A walk may revisit a node; a path may not. The matrix counts walks, so on graphs with cycles it can exceed the number of paths a query returns.

Degree and density. Out-degree is the row sum of A, in-degree the column sum; a directed graph with m edges has density m / (n(n − 1)).

Your settings, worked through

Try this

In practiceGraph databases answer exactly these patterns (Cypher and GQL write them almost as drawn here). Platform teams keep a service catalogue like this one to answer "what breaks if this library has a flaw" in seconds instead of a week of grep.

Watch outVariable-length patterns grow as the branching factor to the power of the hops, so cap the hops and forbid repeated nodes unless you want walks. A catalogue that is not generated from real deployments drifts from the truth within weeks.

Exhibit II · Message passing by hand

One graph neural network layer, in the open

A GCN layer replaces each node's features by a weighted average of its own and its neighbours', then applies a weight matrix: H′ = σ(ÂHW). The graph is Zachary's karate club, whose 34 members split into two factions (the colours of the rings). Each node starts with three features: its degree scaled to 1, a constant 1, and seeded noise.

Step through the layers and watch the two factions first separate, then blur together as every node's features converge. The activation here is the identity (a linear GCN, as in SGC), so the analysis below is exact; the fixed weights are seeded orthonormal matrices.

Layers applied 0

Aggregator

Self-loops (use A + I)

Read one node's update

Pick a node (or click one on the drawing) to see its neighbours, their weights and the arithmetic of its update.

The maths

With Ã = A + I and D̃ its diagonal degree matrix (d̃_i = d_i + 1), the GCN layer is

H^(l+1) = σ(Â H^(l) W^(l)), Â = D̃^−1/2 Ã D̃^−1/2, Â_ij = 1 / √(d̃_i d̃_j)

Why the symmetric normalisation. Plain ÃH sums neighbours, so high-degree nodes grow without bound (try Sum). Dividing by √d̃ on both sides keeps Â symmetric with eigenvalues in (−1, 1], so repeated layers neither explode nor vanish.

Why it over-smooths. Â √d̃ = D̃^−1/2Ã1 = √d̃, so u ∝ √(d + 1) is an eigenvector with eigenvalue 1, the largest. Writing H in the eigenbasis, Â^kH keeps the u component and shrinks the others by λ_i^k: every row becomes a multiple of the same vector, and the rows' directions merge at the rate ρ = max_i≥2 |λ_i|.

Dirichlet energy contracts. E(H) = tr(H^T(I − Â)H) = ½ ∑_ij Ã_ij ‖h_i/√d̃_i − h_j/√d̃_j‖² = ∑_i (1 − λ_i)‖c_i‖², so E(ÂH) = ∑ (1 − λ_i)λ_i²‖c_i‖² ≤ ρ² E(H); an orthonormal W cannot raise it.

Your settings, worked through

Try this

In practiceTwo or three layers is the common depth for GCN-style models; deeper models add residual connections, normalisation between layers or attention (GAT) to keep node features apart.

Watch outA falling training loss with more layers can hide over-smoothing: check the spread of node representations per layer, not only the accuracy, and prefer the mean or symmetric normalisation over plain sums on graphs with hubs.

Exhibit III · Node embeddings from walks

node2vec, trained in this tab

Treat random walks on the graph as sentences and nodes as words, then train skip-gram with negative sampling: nodes that appear near each other on walks get similar vectors. The return parameter p and the in-out parameter q bias each step: a low q pushes the walk outward (depth first), a high q keeps it near home (breadth first).

Twenty percent of the karate club's friendships are held out before any walk is taken. After training, each held-out pair is scored by the dot product of its two vectors and compared with random non-friends: that is the link-prediction AUC.

Return p

In-out q

Walk length

Walks per node

Window

Dimension

No walks yet.

Nearest neighbours of

Scored runs
p	q	length	walks	window	dim	AUC

The maths

The walk. Having stepped from t to v, the next node x is drawn with weight 1/p if x = t, 1 if x is also a neighbour of t, and 1/q otherwise, normalised over v's neighbours.

loss = −log σ(u·v) − ∑_n log σ(−u·n), ∂loss/∂u = (σ(u·v) − 1)v + ∑_n σ(u·n)n

The update the code performs. For each (node, context) pair and 5 negatives drawn in proportion to count^0.75, with g = (σ(z) − label)·lr: the context vector moves by −g·u and the node vector by −∑ g·v. The learning rate decays linearly to zero.

AUC as a probability. AUC = P(score of a random held-out edge > score of a random non-edge), ties counting half. Ranking all scores together, AUC = U / (n₁n₂) with U = R₁ − n₁(n₁ + 1)/2, the Mann-Whitney statistic from the rank sum R₁ of the positives.

Your settings, worked through

Try this

In practiceWalk embeddings are cheap features for recommendation, fraud rings and entity resolution; GNNs trained end to end usually beat them when node features exist, but walks still win on huge graphs with no features at all.

Watch outHold the test edges out before generating any walk. A single seed on a 34-node graph is noisy: compare settings on several seeds before believing a difference of a few AUC points.

Exhibit IV · Graph retrieval against vector search

Multi-hop questions over 60 facts

A retrieval step feeds facts to a model. Vector search ranks facts by the cosine of hashed TF-IDF vectors, so it finds facts that share words with the question. Graph retrieval links the entities named in the question, expands a few hops along the facts' (entity, relation, entity) triples, and ranks what it reached by personalised PageRank from the linked entities.

Each question lists the gold facts a complete answer needs, so recall and precision are measured, and every miss is explained.

Question

Top k

Graph hops

Or write your own question

Vector search (TF-IDF cosine)

Graph retrieval (links, then PageRank)

Gold facts, and why each was missed

The maths

TF-IDF and cosine. A term w in a fact of length |d| weighs tf × idf = (count / |d|) × (ln((N + 1)/(df_w + 1)) + 1); each term is hashed into one of 1,024 buckets. Similarity is cos(q, d) = q·d / (‖q‖ ‖d‖), zero when no word is shared.

r = αs + (1 − α) P^Tr so r = α(I − (1 − α)P^T)⁻¹s, ‖r_t − r‖₁ ≤ 2(1 − α)^t

Why it converges. P^T preserves the L1 norm of a probability vector, so each iteration shrinks the error by the factor (1 − α). A fact is scored by the rank of its two entities. Why hops multiply. With average degree d, h hops reach about d^h entities, so the candidate set, and the noise in it, grows geometrically.

Your settings, worked through

Try this

In practiceProduction systems combine both: dense or lexical search for recall on wording, and an entity graph (built by extraction, then reviewed) for questions that chain facts. Community summaries give a model a map of a large corpus.

Watch outEntity linking by string match misses aliases and typos, and each extra hop brings more unrelated facts; cap the hops, rank inside the neighbourhood, and measure precision as well as recall.

Exhibit V · Graph algorithms as tools

Blast radius, routes and single points of failure

Keep only the running parts of Northwind Cloud (services, databases, queues and dashboards) and draw an edge wherever requests or events flow, weighted by latency in milliseconds. PageRank finds what much of the platform leads to, Dijkstra finds the fastest route, and betweenness finds the parts that many shortest routes pass through: the single points of failure.

Then run an outage: take a part out of service, see how many services can still reach the billing database, and add one redundant link to restore resilience.

Top 5 by betweenness

PageRank

Damping d 0.85

Dijkstra

From

Outage simulation

Take out of service

Resilience fix

The maths

PageRank is the stationary distribution of a random surfer who follows a random out-link with probability d and jumps to a uniform random node otherwise; a node with no out-links (a dangling node, such as a database) jumps uniformly.

r_v = (1 − d)/n + d ∑_u→v r_u/out(u) + d ∑_{u dangling} r_u/n

Dijkstra's invariant. With non-negative weights, the unsettled node with the smallest tentative distance cannot be improved later, because any other route to it would leave the settled set through a node already at least as far. So settling it is final.

C_B(v) = ∑_s≠v≠t σ_st(v)/σ_st, δ_s(v) = ∑_{w: v∈pred(w)} (σ_sv/σ_sw)(1 + δ_s(w))

Brandes' accumulation computes every pair's share in one breadth-first search per source, working back from the farthest nodes, instead of enumerating all shortest paths.

Your settings, worked through

Try this

In practiceSite reliability teams compute exactly this from tracing data: which dependency has the largest blast radius, which route dominates latency, and which single component deserves a replica or a fallback first.

DefenceGive every critical path a second route (a replica, a fallback write path or a queue with retries), test it with a planned outage, and re-run the analysis after every architecture change, since new dependencies quietly create new single points of failure.

Exhibit VI · Where it goes wrong

Hub bias, leakage and over-squashing, measured

Three failure modes that make graph models look better offline than they are, each a live experiment on seeded synthetic graphs.

(a) Hub bias on a preferential-attachment graph

Links per new node m

(b) Leakage in a link-prediction split

AUC of links plus common neighbours
Split	Honest	Leaky	Gap

Bridge edges

Layers k

(d) Name the failure mode

The maths

Preferential attachment. Each new node links to m existing nodes with probability proportional to degree; the degree law is P(k) ≈ 2m²/k³, a power law with exponent 3. The exponent is estimated by maximum likelihood, α = 1 + N / ∑ ln(k_i/(k_min − ½)); small graphs give low estimates.

Degree-product AUC. A random edge's endpoints are picked in proportion to degree while a random non-edge's are not, so d_ud_v ranks edges above non-edges without learning anything about a pair: popularity, not fit.

Why a leak inflates. If features are computed on the graph that still contains the test edge (u, v), then A_uv = 1 is inside the feature: the model reads the answer. Here the score is (A + A²)_uv.

∂h_i^(k) / ∂h_j⁽⁰⁾ = (Â^k)_ij for a linear GNN, R_eff(a, b) = (e_a − e_b)^TL⁺(e_a − e_b)

The bottleneck. Every walk from one half to the other must cross the bridge, so influence across it is limited by the few bridge edges; effective resistance measures the same bottleneck (resistors in parallel), and falls as the bridge widens while the cross influence rises.

Your settings, worked through

Try this

In practiceEvaluate link prediction on a time split with features built only from the past, report results by degree bucket, and add a popularity baseline; for deep GNNs, measure influence across known bottlenecks.

DefenceBuild every feature inside the training fold, compare against a degree-only baseline and a shuffled control, and when information must cross a bottleneck, rewire it (add virtual edges or a global node) rather than stacking more layers.