Design a Friend / Connection Recommendation System
ML project loop
Data·Hypothesis space·Objective·Optimization·Evaluation·Deployment feedback

Design a Friend / Connection Recommendation System

Track

ML System Design

Inspired by

LinkedIn / Meta

Scale

billion-node graph · link prediction · <200ms

Difficulty

Advanced

"People You May Know" is the canonical graph ML interview: the data is a social graph, and the task is link prediction, which edge (friendship) is most likely to form and be accepted. The structure of the graph is the signal, so candidate generation and graph features dominate. The feature was invented at LinkedIn, which credits PYMK with building more than 50% of its professional graph (LinkedIn Engineering); Twitter and Facebook have both published their versions too. Walk it through the ML project loop.

1. Clarify the problem

  • Goal: recommend people a user is likely to connect with and who will accept — a two-sided outcome, not just similarity.
  • Signal: mutual connections, shared schools/employers/groups, co-location, interaction history — mostly graph-structural.
  • Guardrails: avoid creepy recommendations (revealing sensitive relationships), and avoid degenerate feedback (only recommending the already-popular).
  • Scope: candidate generation + ranking over the graph. Adjacent: the graph storage/serving infra.

Interview signal

Frame it as link prediction on a graph, and note the objective is P(connect AND accept): recommending someone who ignores the invite is a failure. This two-sided framing is the differentiator.

Think firstThe degree distribution is power-law: most members have a few hundred connections, a few have millions. Which end of that distribution breaks your system, and how?Commit to an answer, then reveal

Both ends, differently. The sparse end has almost no graph signal — cold start, so side features must carry it. The hub end breaks the machinery: connect to one celebrity and your 2nd-degree neighborhood explodes to millions of nodes, so naive friends-of-friends enumeration melts. Real systems cap and sample per-source, and treat high-degree nodes specially in both candidate generation and training. Any design that assumes an "average" member is wrong for the users at both tails.

2. Requirements & scale

DimensionTargetConsequence
Graph sizeBillions of nodes/edgesCan't score all pairs: candidate generation first
Latency< 200 msPrecomputed embeddings + bounded candidate set
FreshnessNew users/edges matter fastIncremental graph + embedding updates
SparsityMost users have few edgesCold-start handling, side features
Think firstScoring every user pair is quadratic in a billion nodes — a non-starter. What cheap structural heuristic generates most of the good candidates?Commit to an answer, then reveal

Friends of friends. The overwhelming majority of new connections form within the 2nd-degree neighborhood, which is enumerable per user with a cheap graph traversal. That single heuristic collapses the candidate space from billions to hundreds, and everything fancier (embeddings, shared attributes) just supplements it.

3. ML problem framing

Link prediction, structured as a funnel like every large recommender:

  1. Candidate generation (hypothesis space): cheaply propose plausible connections. The workhorse heuristic: "friends of friends" (2nd-degree), plus shared-attribute candidates. LinkedIn's production PYMK blends exactly these source types — random-walk / n-hop graph sources, embedding-based retrieval, and plain heuristics like "new members near you" — then ranks in two stages, an L0 that emits a few thousand candidates and an L1 that calibrates them down to a few hundred (LinkedIn Engineering).
  2. Ranking: score candidates on P(connect & accept) with graph + profile features.

What was breaking before? Scoring all node pairs is quadratic and impossible; pure profile similarity ignores the graph structure that actually predicts connection. Twitter's original Who-to-Follow service is a useful data point for how far structure alone goes: it held the entire follow graph in memory on a single server (Cassovary) and ranked by random-walk algorithms (personalized PageRank/SALSA), creating millions of follows per day (Gupta et al., WWW 2013).

4. Data & features (spine: data)

  • Labels: sent invites, accepted invites (positive), ignored/declined (hard negatives), impressions without action (weak negatives).
  • Graph features: number of mutual connections (the single strongest feature), common neighbors / Adamic-Adar, shared communities, path distance. The classic way to fuse structure with attributes is supervised random walks — learn edge strengths from node/edge features so the walk drifts toward people you'll actually befriend, which beat both unsupervised walks and pure feature models on the Facebook graph (Backstrom & Leskovec, WSDM 2011).
  • Node embeddings: learned so structurally/behaviorally similar users are close (node2vec-style or GNN embeddings), used for candidate retrieval.
Deep dive
Serving node embeddings for candidate retrieval
Includes runnable notebook
Think firstBefore any GNN — what's the single strongest feature, and what baseline would you build first?Commit to an answer, then reveal

Mutual-connection count. On its own it's an embarrassingly strong predictor, and a GBDT over it plus a handful of graph features (Adamic-Adar, shared communities, path distance) is the baseline every neural model must beat. If your GNN doesn't clear it, the GNN isn't learning graph structure — it's overhead.

5. Model (spine: hypothesis space + objective)

  • Baseline: logistic/GBDT on graph features (mutual-connection count alone is remarkably strong) — the benchmark to beat.
  • Graph neural network: a GraphSAGE/GCN encoder learns node embeddings by sampling and aggregating neighborhood features (Hamilton et al., NeurIPS 2017); the edge score is a function of the two node embeddings. GNNs capture higher-order structure the hand-built heuristics miss.
  • Objective: ranking / binary acceptance with hard negatives from ignored invites.

Message passing on a graph

0.050.950.500.200.800.35
round0
spread0.900
selectednode 4

Each node's colour is its feature value. One step replaces every node's value with the mean of itself and its neighbours — a single GCN-style round. Click a node to highlight its incoming messages; keep stepping and watch all nodes converge to the same colour (over-smoothing).

Message passing is the heart of the GNN: each node's representation is built from its neighbors', so two users embedded near each other share graph context — the essence of "you may know them."

Think firstGraphSAGE learns an aggregator function over sampled neighborhoods instead of an embedding per node. Why is that distinction — not the accuracy — the reason it's the production choice here?Commit to an answer, then reveal

Because the graph won't sit still. A per-node ("transductive") embedding table is stale the moment a member joins or an edge forms, and refreshing it means re-running the factorization. An inductive model is a function — feed it any node's features and sampled neighborhood and it emits an embedding, so new members get embeddings on day one and edge churn is absorbed by re-running a cheap forward pass, not retraining. Neighborhood sampling is the second half: it bounds compute per node, which is what makes hubs tractable.

6. Serving & scaling

Offline: compute node embeddings + candidate lists (2nd-degree neighborhoods) in a batch graph job. Online: fetch the user's candidates, rank with the model + fresh features, apply guardrail filters (blocked, sensitive), return the top-k under 200ms. Update embeddings incrementally as the graph evolves. Candidate generation itself can go online too: LinkedIn moved part of PYMK's graph work to online traversal (its Gaia service) so freshly formed edges surface without waiting for the next batch job.

Think firstYou hold out 10% of edges at random for the test set. Why are your metrics about to look better than they should?Commit to an answer, then reveal

Because edges aren't independent in time: a random holdout trains the model on edges that formed after the ones it's tested on, and the surrounding graph context effectively gives the answer away. The honest protocol is a temporal split — train on the graph up to time T, predict which edges form after T — which is also the deployment reality.

7. Evaluation (spine: evaluation)

  • Offline: ranking metrics (AUC, Recall@k, MAP) on held-out future edges — a temporal split (predict edges that form next), never random, to avoid leaking the future.
  • Online: invite send rate, acceptance rate (the key two-sided metric), and long-term network growth / engagement, with guardrails on complaints.
Think firstYour A/B test wins: invites +8%, acceptance rate flat. Six months later, is the network better — and what could this launch have quietly made worse?Commit to an answer, then reveal

Not necessarily better. Impressions concentrate on high-degree nodes (they appear in the most 2nd-degree neighborhoods), so a send-rate win can mean the model got better at pushing already-popular people — a rich-get-richer loop that compounds every retrain, since today's recommendations create tomorrow's edges and training data. Watch degree-distribution drift, exposure concentration (what fraction of impressions the top 1% of nodes absorb), and new-member connection rates — the six-month metrics your two-week A/B can't see.

8. Monitoring & feedback (spine: feedback)

  • Evolving graph: the graph changes constantly; embeddings and candidates must refresh, or recommendations go stale.
  • Feedback loops & fairness: guard against only surfacing popular nodes (rich-get-richer) and against revealing sensitive connections; monitor diversity and complaint signals.

9. Tradeoffs & alternatives

ChoiceAlternativeWhy
Candidate gen + rankScore all pairsAll-pairs is quadratic: impossible at billions
GNN embeddingsProfile-only similarityGraph structure is the dominant signal
Temporal eval splitRandom splitRandom splits leak future edges → inflated metrics
P(connect & accept)P(similar)An ignored invite is a bad recommendation

10. Interviewer follow-ups

A brand-new user has no connections. What do you recommend?

Fall back on side features — imported contacts, shared email domain/employer/ school, co-location, and content interactions — to seed the first candidates, plus popular-in-network suggestions. The graph signal grows once they make a few connections; until then it's a cold-start problem.

The system keeps recommending already-popular people. Why, and fix?

A feedback loop: popular nodes get more impressions, more connections, more recommendations. Add diversity/novelty terms, cap exposure of high-degree nodes, and calibrate on acceptance (not raw connection count) so it optimizes good matches, not popularity.

Why is a random train/test split wrong here?

It leaks the future: a random split can put an edge's endpoints' other future edges in the training set, so the model 'predicts' connections it effectively already saw. Use a temporal split — train on the graph up to time T, predict edges forming after T.

Key takeaways

  • Friend recommendation is link prediction on a graph — a candidate- generation → ranking funnel, since scoring all pairs is impossible.
  • Graph-structural features (mutual connections) and GNN embeddings carry the model; profile similarity alone is weak.
  • Optimize the two-sided P(connect & accept), evaluate on a temporal split, and guard against popularity feedback loops and sensitive reveals.

References