Book Deep Read · ML System Design Interview · Chapter 11
Machine Learning System Design Interview · Ch 11 · Ali Aminian & Alex Xu · 2023
You sign up for a social app and fill in nothing but your name. Three days later it hands you a list of "people you may know" — and your college roommate and two former coworkers are actually on it. This chapter is about how it pulls that off.
You'd assume it matches your profile against everyone else's: same school, same employer, same city. Those help, but none of them is the engine.
The real engine is one single clue: how many friends the two of you have in common. That one signal alone surfaces most of the right people. It doesn't even need to know who you are or what you do.
The difficulty isn't the guessing. It's how many guesses you'd have to make.
A platform has a billion people. Taken literally, deciding "who might you know" means pairing every person with every other person — an astronomical number that all the machines on earth couldn't finish. So the first job isn't building a clever model. It's figuring out how to know that almost everybody isn't worth looking at, without looking at them.
Step one: only look at friends of your friends. Almost everyone you meet, you meet through someone you already know. Restricting candidates to friends-of-friends shrinks the pool from a billion to tens of thousands — a hundred-thousand-fold cut.
Step two: discount mutual friends. The naive move is to count them and rank by the count. That has a trap: if the person in the middle is a super-connector with five thousand friends, they are "mutual" with everyone, which tells you nothing. Flip it around — someone with only thirty friends who knows both of you is strong evidence you two really move in the same circle. So: the more friends the middleman has, the less their vote is worth.
Step three: give everyone a position on a social map. Let each person look around at who surrounds them, then at who surrounds those people, and derive a coordinate from that. Two people whose coordinates sit close together should be recommended to each other — this catches the subtler signal of "you two share no friends at all, but your circles look remarkably alike."
What makes this powerful is that it reconstructs real-world social circles from nothing but "who is connected to whom."
And that is exactly the cost: it knows the two of you are connected, but not why you'd rather this person couldn't find you — so it will happily surface an ex-colleague, an ex-partner, or someone from a context you never wanted linked to your name.
Friend recommendation is won or lost before the model: use friends-of-friends to cut a billion candidates down to ten thousand, then count mutual friends and discount each one by how many friends the middleman has — a super-connector's vote is worth far less than that of someone from a small, tight circle.
Want the mechanisms, notation and diagrams? → Switch to the deep read
This chapter translates "friend recommendation" into link prediction on a graph: given today's social graph, predict which two unconnected nodes will connect in the future. You'd think the hard part is model choice. It isn't — a billion users means 1018 candidate pairs, and no model earns the right to score them. The real skeleton of the chapter is: cut candidates to 104 with two-hop neighbors first, then talk features, and only then talk models.
The last of the ten case studies in Part II, and the only one in the book whose input is an entire graph rather than a batch of independent samples. It builds on Ch 9 (learning embeddings from co-occurrence) and Ch 10 (the candidate-plus-ranking funnel), and merges both onto a graph. In the real world it maps to LinkedIn's People You May Know, Facebook's feature of the same name, and X's Who to Follow.
Start with scale. A billion users, a few hundred friends each on average. Pairing everyone with everyone is n(n−1)/2 ≈ 5×1017 pairs; at one microsecond per pair that is over ten thousand years. The "score every pair" framing is wrong from the first line — and that is the structural break from the previous ten chapters, whose candidate pools were naturally bounded (one user's feed, one video library). Here the pool is quadratic in the number of users.
Pressure from the product side points the same way: social products almost universally track "K connections within N days" as their activation metric. A new user who signs up and sees an empty list churns — and new users are precisely the people with no position in the graph at all.
So the chapter has to solve two things at once: how to cut candidates from 1018 to something computable, and how to rank within what's left. The first decides whether the system runs; the second decides whether it works.
The easiest mistake is predicting today's graph from today's graph. If you're predicting whether u and v will become friends but your features were computed on a snapshot that already contains the u–v edge, that's label leakage: offline metrics look magnificent and production is silent.
The correct method is a time slice: compute features on the graph at time t, and take edges newly formed between t and t+Δ (two weeks to a month, say) as positives. Draw negatives from two-hop candidates that had not connected at t — never uniformly from all users. Two random people almost certainly don't know each other, so a model that always says "no" scores 0.99 AUC while learning nothing. Negatives must come from the same pool as positives; these are hard negatives.
The justification is triadic closure: in the real world, most new friendships arrive through existing ones. So take two-hop neighbors as the candidate set. The sizing is straightforward — a user of degree d has on the order of d² two-hop neighbors (fewer after dedup): at d ≈ 300 that is 104–105, more than a dozen orders of magnitude below 1018.
State the cost plainly: anyone with zero mutual friends can never enter the candidate set. People who just moved cities, just switched industries, or just signed up all live in that blind spot. So two-hop is the primary source only, and several non-graph sources must run alongside it: same school and major with overlapping years, same employer with overlapping tenure, contact or email import, same city or group. Their job isn't precision — it's giving an entry point to people the graph hasn't placed yet.
The naive ranking signal is a raw count of mutual friends. It works surprisingly well, and it has one fatal flaw: hub nodes — recruiters, influencers and sales accounts carrying five thousand connections. They hand "one mutual friend" to countless unrelated pairs, diluting the signal into noise.
The fix is Adamic-Adar: AA(u,v) = Σ 1/log(deg(w)), where w ranges over the mutual friends and deg(w) is that middleman's own friend count. In plain words: discount every middleman by the logarithm of their own degree — the more friends they have, the less their vote counts.
Be honest about one thing: the discount is logarithmic, not linear — a 5000-friend hub still contributes 0.12 against 0.29 for a 30-friend node, a factor of 2.4. Hubs are weakened, not eliminated. In practice teams add a hard rule on top: nodes above a degree threshold are excluded from two-hop expansion entirely, or their adjacency lists alone blow up the candidate set.
One level up sits edge weight: friendship is not 0/1 — an edge with real interaction is far stronger than one that went quiet the day it formed. Weighting mutual friends by the strength of both sides usually buys more than swapping in a fancier model.
Generation one, pure rules: rank by AA score. Zero training cost, fully explainable, usable the moment a user has any edge at all. It is the right first version of any PYMK system and the permanent baseline every later model must beat — plenty of teams lost their first A/B to it.
Generation two, pointwise supervised classification: treat each candidate pair (u,v) as one sample and feed three families of features — graph features (mutual count, AA, shortest path, both degrees), attribute features (same school or employer with overlapping years, same city, similar age, language), interaction features (did either visit the other's profile, for how long, were they mentioned by the same person) — into logistic regression or gradient-boosted trees to output P(edge). This is the industry's longest-lived answer: tunable, explainable, shippable. Its ceiling is that graph structure can only enter through hand-crafted features; everything beyond two hops is lost.
Generation three, graph neural networks, the book's destination. In plain terms: everyone writes their attributes onto a card. Round one, everyone sends their card to all their friends, and each person folds the stack they received into a new card. Round two repeats it — and now the card in your hand encodes you, your friends, and your friends' friends. That card is the node embedding z. Prediction is one step: P(u,v) = σ(z_u · z_v), a dot product squashed into a probability.
The costs are equally concrete: the full graph doesn't fit in GPU memory, so training needs neighbor sampling (a random subset of neighbors per layer); inference needs all embeddings precomputed and cached, so the moment the graph changes the embeddings are stale; neighbor sampling on hubs is inherently biased; and when something goes wrong there is no feature-importance readout to fall back on. What it wins is the signal where two people share no mutual friends but their circles have the same shape — exactly generation two's blind spot.
The key observation: the social graph changes very slowly — an active user adds zero to a few edges a day. So the whole pipeline moves offline: a batch job periodically expands two hops per user, computes features, scores, truncates to Top-K, and writes the result into a KV store; online there is one get plus filtering (already friends, dismissed, blocked), returning in tens of milliseconds. Model weight has no effect on serving latency — the cheapest step in the chapter, and the one interviewees most often skip.
There is exactly one exception: users who just signed up, just imported contacts, or just added their first few friends must see results immediately. They go through a triggered incremental recompute — their corner of the graph is tiny, so recomputing it alone is cheap.
The first table answers "where do candidates come from." Note the last column — no single source stands alone, and the highest-coverage one happens to miss exactly the users who need recommendations most.
| Candidate source | Who it covers | Size / cost | Cost and risk |
|---|---|---|---|
| Two-hop (FoF) | Existing users with some friends; highest hit rate | ~10⁴ per user, hours of batch | New users and out-of-circle people can never enter; hubs blow up the expansion |
| Same school / employer with overlapping years | People who moved city or industry but share a résumé overlap | Small, an attribute inverted index suffices | Depends on profile completeness; at large employers it degrades into "random people in town" |
| Contact / email import | Brand-new users — the only source that can fire instantly | Tiny, the user supplies it | The densest privacy minefield: it surfaces relationships the user never meant to expose |
| Same city / same group | People with offline overlap not yet connected online | Medium | Low precision, backstop only, easily surfaces total strangers |
| Embedding ANN retrieval | No mutual friends, but structurally similar communities | Needs full embeddings plus a vector index | Most expensive; useless once embeddings go stale; least explainable |
The second table is model selection: the three generations replace nothing — mature systems run rules as a backstop, supervised as the workhorse, and a GNN to cover the blind spot.
| Approach | When to pick it | Cost |
|---|---|---|
| Rules: AA ranking | Cold start, tight compute budget, full explainability required — any PYMK's v1 and permanent baseline | Uses only structure within two hops; attribute and interaction signals go to waste; obvious ceiling |
| Pointwise supervised (LR / GBDT) | Some log history accumulated, and you want attribute plus interaction features in play — the industry's long-lived workhorse | Graph structure enters only via hand-crafted features; every new structural signal means new feature engineering |
| Graph neural network | A large, dense graph, GPUs and an engineering team, and a need for the "no mutual friends but similar community" signal | Neighbor sampling in training, cached embeddings at serving, stale the moment the graph moves; brutal to debug and attribute |
One more trade-off lives outside the model, and it separates candidates in interviews: should the target be "will they know each other" or "will an invite be sent and accepted". The latter is what the product wants, and it is a two-sided event — recommending accurately but getting ignored buys you invite fatigue: the recipient starts ignoring every invite and the platform-wide acceptance rate drops with them. So the online objective is usually "sent × accepted," checked again two weeks later for whether the edge still shows any interaction.
Saying "use a GNN for link prediction" scores zero in an interview. The points are in four sentences: candidates before models (1018 is unscoreable), labels must be time-sliced (or they leak), negatives must come from the candidate pool (or AUC is fake), and the pipeline is offline by default (the graph moves slowly). Same in an architecture review: the real cost isn't model inference, it's that nightly full two-hop expansion.
① Friend recommendation is link prediction on a graph: given today's social graph, predict which unconnected pair connects next.
② The structural break from the previous ten chapters is that the candidate pool is quadratic in users: 109 users → 5×1017 pairs, so "score every pair" never stood a chance.
③ Triadic closure saves it: take only two-hop neighbors, ~104 per user, cutting more than a dozen orders of magnitude. The cost is that anyone with zero mutual friends never enters, so school/employer, contact import and same-city sources must run alongside.
④ Mutual friends need degree normalization: AA = Σ 1/log(deg(w)), discounting middlemen by their own friend count — but the discount is logarithmic, so hubs still need a hard threshold.
⑤ The three generations stack rather than replace: AA rules (baseline, never skip it) → GBDT pointwise (workhorse; structure only enters via hand-crafted features) → GNN (covers "no mutual friends but similar community," at the price of sampling, caching and staleness).
⑥ Because the graph moves slowly, the pipeline is batch offline plus table lookup online — one KV get and a few filters on the request path; only new signups and fresh contact imports take the triggered incremental path.
⑦ Label by time slice (features at t, new edges in t→t+Δ as positives) and sample hard negatives from the two-hop pool — get either wrong and every offline number is fiction.
⑧ The online objective is not "will they know each other" but "will an invite be sent and accepted"; accuracy that buys invite fatigue is a net loss.