People You May Know (PYMK) is the feature that suggests new connections on social and professional networks. It looks simple on the surface: show a list of names the user might want to add. Under the hood it is one of the hardest ranking problems in production ML, because the data is a billion-node graph, the right answer is a mutual acceptance, and a wrong suggestion can feel creepy rather than helpful.

Clarifying Questions

Before writing anything down, a candidate should spend a few minutes pinning scope. PYMK at a place like LinkedIn looks different from PYMK on a friendship-first network, and the ranker changes depending on what counts as success.

Candidate: "When you say People You May Know, do you mean the dedicated PYMK page, the onboarding suggestion screen, or the sidebar module on the home feed?"

Interviewer: "Let's design a single ranking service that powers all three surfaces, but optimize for the PYMK page first. The onboarding and sidebar modules call the same API with a different surface tag."

Candidate: "Is a connection always reciprocal, like LinkedIn's connect flow, or is this a follow model where user A can follow user B without B's consent?"

Interviewer: "Reciprocal. The inviter sends a request, the invitee accepts or ignores. That's important for the label."

Candidate: "How big is the network, and how many daily active users are we serving?"

Interviewer: "About 1 billion registered users, ~500 million DAU. Average user has 200 connections, though the distribution is heavy-tailed."

Candidate: "How many suggestions do we return per request, and what's the latency budget?"

Interviewer: "K = 20 suggestions per page view, p99 under 150ms end to end."

Candidate: "Do we need to explain each suggestion with something like 'you have 12 mutual connections'?"

Interviewer: "Yes. The reason string drives a lot of the click-through, so it has to be attached to each candidate at serving time."

Candidate: "What signals are off-limits? Blocked users, reported accounts, ex-partners if the platform exposes relationship status, anything contact-book based?"

Interviewer: "Blocks and reports are hard filters. Contact-book candidates are allowed only when both sides have uploaded their contacts, and the reason string can never reveal the contact that triangulated the match. Relationship-status edges aren't used."

Candidate: "What's the north-star metric? Invites sent, invites accepted, or something downstream like retained connections?"

Interviewer: "We've learned the hard way that optimizing for invites sent creates spam. Treat accepted invites that still exist after 28 days as the north star."

Requirements

Functional Requirements:

Non-Functional Requirements:

ML Problem Framing

PYMK is a link prediction problem on a heterogeneous graph. For a given source user u, the system must pick a small set of candidate nodes v such that an edge (u, v) is likely to be created and sustained.

There are two ways to frame this. The naive framing is a pointwise binary classifier: P(invite_sent | u, v). It is easy to train because every invite in the logs is a positive, but it optimizes the wrong thing. The goal is not to nudge the user into sending an invite, it is to suggest people who will accept and stay connected.

The better framing is a multi-task classifier with three heads:

The serving score blends the three with a reciprocity floor. Candidate generation is a separate problem: retrieve a few thousand plausible vs from a billion-node graph in tens of milliseconds. That stage runs against embedding indices and graph walks, not the ranker.

Metrics

Invite send rate is the easiest metric to move and the most misleading. A redesigned PYMK module with a louder CTA will increase send rate and tank accept rate. Always pair them.

The system has three cooperating planes: an online path that serves a ranked list in under 150ms, an offline path that trains models and refreshes embeddings daily, and a streaming path that keeps the graph and its derived features current within minutes of a new edge.

The online path is dominated by two costs: generating a few thousand candidates from a billion-node graph without scanning the graph, and scoring those candidates with a ranker that actually uses graph structure. The offline path does the heavy lifting: it trains a two-tower model for ANN retrieval and a GraphSAGE-style GNN for node embeddings, then publishes both to serving indices. The streaming path is what keeps PYMK from feeling stale. A user who accepts an invite expects their suggestions to shift within minutes, not overnight.

Data Flow

The same Kafka stream feeds both the warehouse (for training labels and batch features) and the online feature store (for freshness). This dual-write pattern is worth the complexity because training on yesterday's features while serving with today's is the single most common source of training-serving skew in PYMK systems.

Back-of-Envelope Numbers

Twenty trillion scoring operations per day is an arresting number. It rules out any ranker that does anything expensive per (u, v) pair. That is why production systems do most of the work on the tower side: per-user embeddings are computed once per session, per-candidate embeddings are precomputed daily, and the ranker itself touches only a small slice of cross features at request time.

Data Sources

PYMK data falls into five categories. Each feeds a different part of the system.

Profile graph. The connection graph itself: existing edges, pending invites, dismissed suggestions, blocks, mutes, reports. This is the primary source of graph features and the source of positive labels.

Profile attributes. Declared metadata on each user: current and past companies, schools, locations, skills, industry. These drive the two-tower model and most of the reason strings.

Activity edges. Implicit signals that are not formal connections: profile views, message exchanges, reactions on shared content, group co-membership. These are weak but useful, especially for cold-start users where the connection graph is sparse.

Contact book overlap. When a user uploads their contacts with consent, the platform can detect that two users share the same phone number or email in each other's address books. This is an extremely strong predictor of reciprocity, and the single most privacy-sensitive signal in the system.

Context. Surface (PYMK page vs onboarding vs sidebar), session (time of day, device, locale), and short-term state (the user just accepted three invites from the same company, so boost that cohort for this session).

Feature Engineering

Features for PYMK naturally split into pair features, node features, and context features. The pair features do most of the work.

Pair/graph features describe the relationship between u and v in the graph itself:

Node embeddings compress a user's position in the graph and their attributes into a single vector:

Per-user node features are about the requester or the candidate individually:

Context features cover the request:

Negative signals explicitly encode what the user has told the system not to do:

Feature Table

Freshness is the field candidates forget to discuss. Mutual connection count needs to be near-real-time because a user who just accepted a request expects their mutual-count-based suggestions to update within minutes. Shared company can update daily without anyone noticing. Two-tower embeddings can also update daily for most users but need a fast-path refresh for users whose graph just changed significantly.

Baseline Approach

The surprising thing about PYMK is how far a pure heuristic gets. A weighted blend of four features captures most of the signal:

Tuned on held-out data, this baseline lands around 70% of the Recall@20 of a production GNN ranker. That is because the mutual-friend signal is extraordinarily strong: if two people share 15 connections, the probability they want to be connected is an order of magnitude higher than a random pair. Shared company and school are weaker but near-zero in cost to compute.

The baseline breaks down in three places. It cannot rank users with zero mutuals (cold-start). It treats all mutual connections as equal, ignoring that a mutual friend who is a close collaborator is worth more than a mutual who is a celebrity with a million followers. And it has no way to handle reciprocity: it will surface high-degree users who accept almost no invites.

Advanced Approach

The production system is a multi-stage pipeline. Candidate generation unions three retrieval sources, then a GNN-powered ranker scores the union.

Candidate generation runs four sources in parallel and unions their top-K results:

Each source returns 200-500 candidates. The union is typically 1,000-1,500 after deduplication.

The ranker is where reciprocity is modeled. It takes the union of candidates and scores each one with a GNN-derived embedding plus cross features.

The GNN is trained offline. A GraphSAGE-style architecture aggregates features from the 2-hop neighborhood of each node using mean pooling at the first layer and attention at the second. Embeddings are precomputed daily for the full user base and refreshed within minutes for users whose neighborhood changed significantly.

The three heads share a trunk MLP and split for the last two layers. Sharing the trunk matters because the three tasks are correlated (invite implies accept sometimes, accept implies retention usually) and a shared representation regularizes the rarer signals.

Training

Labels come from the activity log, joined with a 28-day lookback:

Each label is defined only on the conditional population, which matters for the loss.

Negatives need care. The graph is sparse and in-batch random negatives are almost always easy: a random pair shares zero mutuals and has trivially low score. The model learns nothing. The fix is two-source negative sampling: half of the negatives are in-batch random (cheap, prevents collapse), and half are hard negatives drawn from 2-hop non-connected pairs with at least 3 mutual connections but no invite in the last 90 days. Hard negatives are what teach the model to separate "this person is reachable" from "this person is wanted."

Cadence. Full retraining runs daily on a rolling 30-day window. Embedding refresh for hot users runs within minutes. Every model version is shadow-scored against the current production traffic for 24 hours before any live ramp.

Loss. A masked, weighted BCE across the three heads:

The mask is what keeps the accept head from training on impressions where no invite was sent, and the retained head from training on invites that were never accepted. Without the mask, the conditional heads see almost only zeros and collapse to predicting the base rate.

The serving path is a short pipeline with tight latency budgets at every stage. A request arrives with a user ID and a surface tag. A response has to leave in 150ms with 20 candidates, a reason string for each, and a fresh dedup footprint so the same candidates do not reappear on the next refresh.

Inference Pipeline

Candidate union is the first real work. Four retrieval calls fan out in parallel: the FoF walk service, the ANN index, the cohort lookup, and the contact-book service. Each has its own timeout and degrades independently. If the ANN index is slow, the request still returns with FoF and cohort candidates rather than waiting.

The filter stack is where safety lives. It runs before feature fetching because it is cheaper to drop a candidate than to compute 30 features on it and then drop it. The order matters: blocks and reports are checked first because they are hard rules, then already-connected, then dismissals within the 90-day window, then rate limits on how often a single candidate can be shown across sessions.

Feature fetching pulls the GNN embedding for each candidate from an in-memory store, joins pair features from the graph walk cache, and attaches context from the request. The ranker is a small MLP; the expensive part is the feature fetch, not the model.

Diversity re-rank runs after scoring and before response. It enforces caps like "no more than 3 candidates from the same company in a single list" and boosts low-degree candidates whose predicted accept rate exceeds a threshold. The reason string attacher is a rule-based lookup over the pair features, producing strings like "12 mutual connections" or "You both worked at Acme" in rank order of signal strength.

The serving score blends the three heads with a reciprocity floor:

The floor on P(accept) is the knob that stops the system from recommending celebrities. A user with a million connections has a high P(invite | shown) because people want to be connected to them, but a very low P(accept | invite) because they do not accept most requests. Without the floor, the ranker learns to surface them anyway because the invite-click reward is large.

Batch vs Real-Time

The interesting line in this table is the GNN embedding row. Recomputing a 128-dim embedding for a user whose 2-hop neighborhood changed is not cheap, but it matters. A user who just joined a new company's employee network expects their PYMK suggestions to shift toward that company within the hour, not next day.

Latency Budget

The ranker budget is tight because scoring 1,200 candidates in 40ms leaves about 33 microseconds per candidate. That rules out a deep ranker at this stage; most production systems use a two-layer MLP with 256 hidden units and rely on the GNN embeddings to carry the complex graph reasoning.

Streaming Graph Updates

Every edge event flows through Kafka to an edge-delta service that updates three caches. The 2-hop walk cache is the hottest one: an accepted invite invalidates the walk caches of both endpoints and all their existing neighbors. The negative-signal store absorbs dismissals and blocks and propagates them to the filter stack. The embedding refresh is triggered only when the change is significant (for example, joining a connection who has more than 500 neighbors). That gating is what prevents the refresh workload from tracking every casual edge.

Graph Representation: FoF Walks, GNN Embeddings, and Two-Tower

The first real design decision is how to represent the graph. There are three competing approaches, and the production answer is almost always to union all of them.

Friend-of-friend walks are the oldest and simplest approach. Walk from u, collect 1-hop neighbors, expand to their neighbors, aggregate mutual counts. The signal is transparent (the reason string is just "you share N mutual connections"), and the system is easy to debug. The weakness is cold start: if u has no connections, the walk returns nothing.

Graph neural networks learn a dense embedding per node by aggregating features from the local neighborhood. GraphSAGE is the common choice because it supports inductive inference on new nodes, which matters for PYMK where new users join every second. The strength is that GNN embeddings capture structural similarity that raw mutual counts miss: two users with no shared neighbors but who both sit in tightly connected subgraphs of the same industry will have similar embeddings. The weakness is opacity; the reason string still has to come from explicit features.

Two-tower retrieval builds a dense vector per user from their profile attributes and retrieves by ANN. This works for users with no edges at all, because the user tower depends only on declared attributes. It scales to billions of candidates cheaply. The weakness is that it cannot see graph structure; two users with identical resumes but in different clusters of the network will look identical to the two-tower model.

The production answer is to union all three at candidate generation and let the ranker sort them out. FoF contributes dense-graph candidates with good reason strings. GNN contributes structural candidates the walk misses. Two-tower contributes cold-start coverage. On a platform with 1B users, dropping any one of these sources costs several points of Recall@20.

Reciprocity Prediction and Label Design

The label choice is the single most important design decision in this system, and it is where the most experience matters.

The naive label is P(invite_sent | shown). It is abundant: every impression either results in an invite or does not. Teams that optimize this label often see invite send rate triple and user complaints about spam triple alongside. The root cause is that P(invite_sent | shown) is correlated with but not equal to connection value.

The next step is P(accepted | shown), which conditions on the invite happening and the invitee accepting. This is much better, and it is the minimum bar for a production PYMK system. The downside is that the label is delayed by up to 14 days (the typical acceptance window), so the training data lags serving by two weeks.

The best label is retention-anchored: P(still_connected_28d | shown). It ignores accepted connections that get removed shortly after, which is a common pattern for accidental accepts and stale professional obligations. The downside is a longer delay and lower label density.

The blend strategy used in the production architecture is what makes this work. The invite head has dense labels and helps the model converge. The accept head conditions on invites. The retained head does the final reshaping. By the time the blend is applied at serving, the model has learned to suppress candidates that look like they would generate an invite but not an accept or a retained edge.

Privacy, Blocks, and Sensitive Edges

PYMK lives closer to the privacy line than almost any other recommendation system. The data is about human relationships, the errors feel intrusive, and the user's trust is directly at stake. The filter stack is where this shows up.

Sensitive-edge detection is the hardest filter. Some sensitive edges are declared (a user reports another user). Some are inferred. A direct report of a skip-level manager, surfaced as PYMK, feels like surveillance even though the graph signal is strong. A recent divorce, inferred from mutual-connection churn, should not drive a recommendation. Production systems typically maintain an allowlist of edge types that can contribute to suggestions, rather than a denylist, because the space of sensitive inferences is open-ended.

The contact-book signal deserves special attention. If user A has user B in their contacts and user B has user A, the system knows they share a phone number or email. That is powerful information, and it leaks. The rule is strict: contact-book overlap can influence ranking and can even generate a candidate, but the reason string can never say "you are in each other's contacts." Users have reverse-engineered weaker hints and concluded that an ex-partner or estranged family member was behind a suggestion, and the reputational cost is severe.

Diversity, Fairness, and the Rich-Get-Richer Problem

The graph has a rich-get-richer dynamic built into the data. A user with 1,000 connections has 1,000 chances to appear in a mutual-friend walk and ends up being surfaced to far more people than a user with 50 connections. They accumulate even more connections. Over time, a small cluster of highly-connected users dominates PYMK suggestions across the entire platform.

This is bad for three reasons. It degrades the long-tail experience because low-connection users are never surfaced. It degrades the high-degree user experience because they get flooded with low-quality invites. And it concentrates network structure in a way that hurts long-term engagement.

The corrections happen in three places. The accept-rate floor in the blended score filters out most of the 5,000+ bucket automatically, because those users accept almost no invites. A daily impression cap per candidate stops individual high-degree users from appearing in millions of lists. And a low-degree boost in the diversity re-ranker gives promising low-connection users a fair share of surface.

Fairness audits run weekly across network-size deciles, ensuring the acceptance rate gap between the bottom decile and the top decile stays within bounds. When the gap widens, the usual cause is a new candidate source that over-retrieves high-degree users, and the fix is either a re-ranker cap or a retrieval-side cap on that source.

Offline Evaluation

The offline evaluation setup for PYMK has one non-obvious rule: the train and eval edges must be split by time, not randomly. A random split leaks future edges into training and produces inflated numbers that do not survive a live A/B.

The standard setup trains on a rolling 30-day window ending at T-7, and evaluates on the edges created between T-7 and T. The held-out edges are the positives. The ranker is asked: given the state of the graph at T-7, would it have surfaced v in the top 20 for u before the connection happened? Recall@20 and MRR are computed on that question.

Calibration matters as much as ranking. The blended score uses predicted probabilities directly in a reciprocity floor, so a model that ranks well but whose P(accept) outputs are miscalibrated will drop the wrong candidates. The standard check is reliability diagrams per decile and an expected calibration error target below 0.03 on the accept head.

Counterfactual evaluation fills the gap that offline metrics cannot. Because users only see what the current ranker surfaced, held-out positives exclude edges the old ranker missed entirely. Inverse propensity weighting using logged impression propensities helps correct this bias and gives a more honest picture of how a new ranker would perform on candidates the old one never showed.

Online Evaluation

Offline wins in PYMK almost always shrink in production. The usual causes are freshness gaps, feedback-loop effects, and novelty decay. An A/B test is the only reliable arbiter.

The ramp runs for two to four weeks at each stage because the 28-day retention metric needs time to stabilize. Guardrails include invite accept rate (primary success metric), block and report rate per PYMK candidate (the creepiness guardrail), daily active session count (long-horizon engagement), and the fairness gap across degree deciles. A 10% relative regression on any guardrail triggers a rollback.

A permanent holdout of 1% of DAU never sees any PYMK experiment. This holdout is what tells the team whether PYMK as a whole is contributing to network growth in year-over-year comparisons. Without it, every launch gets credited with short-term lift and the long-term effect of incremental changes is impossible to measure.

Monitoring

Production PYMK has four monitoring layers. Feature drift tracks whether the distribution of input features matches training: a sudden shift in the degree distribution often signals a bad incremental update to the graph store. Embedding staleness measures the age of GNN embeddings for active users: when p95 staleness climbs above 24 hours, the hot-refresh pipeline is falling behind. Candidate-source mix monitors the share of the top 20 coming from each retrieval source: a collapse to a single source usually means another source is degraded silently. Acceptance rate by segment catches fairness regressions before the weekly audit does.

The alert that fires most often is "invite accept rate down 2% week-over-week." It is almost always caused by one of two things: a ranker regression (caught quickly via offline eval of the current model on recent data) or a surface regression (a UI change that changed click context but not the ranker). Debugging starts by checking which segment regressed, because platform-wide drops are rare and segment-specific drops usually point at a feature pipeline or a safety filter that started over-firing.

The next chapter looks at personalized news feeds, where the ranker combines many objectives (engagement, informativeness, freshness, diversity) across heterogeneous inventory types rather than a single link-prediction objective.