{"title":"Design People You May Know","description":"","content":"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.\n\n---\n\n# 1. Problem Formulation\n\n### Clarifying Questions\n\nBefore 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.\n\n**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?\"\n\n**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.\"\n\n**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?\"\n\n**Interviewer:** \"Reciprocal. The inviter sends a request, the invitee accepts or ignores. That's important for the label.\"\n\n**Candidate:** \"How big is the network, and how many daily active users are we serving?\"\n\n**Interviewer:** \"About 1 billion registered users, ~500 million DAU. Average user has 200 connections, though the distribution is heavy-tailed.\"\n\n**Candidate:** \"How many suggestions do we return per request, and what's the latency budget?\"\n\n**Interviewer:** \"K = 20 suggestions per page view, p99 under 150ms end to end.\"\n\n**Candidate:** \"Do we need to explain each suggestion with something like 'you have 12 mutual connections'?\"\n\n**Interviewer:** \"Yes. The reason string drives a lot of the click-through, so it has to be attached to each candidate at serving time.\"\n\n**Candidate:** \"What signals are off-limits? Blocked users, reported accounts, ex-partners if the platform exposes relationship status, anything contact-book based?\"\n\n**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.\"\n\n**Candidate:** \"What's the north-star metric? Invites sent, invites accepted, or something downstream like retained connections?\"\n\n**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.\"\n\n### Requirements\n\n**Functional Requirements:**\n\n- Return K = 20 ranked candidates per request for a given (user, surface) pair.\n- Attach a human-readable reason string to every candidate (mutual connections, shared company, shared school, same city).\n- Never surface users the requester has blocked, reported, muted, or already connected with.\n- De-duplicate across recent sessions so the same candidate is not shown 10 times in a week.\n- Support cold-start users with zero connections by falling back on profile attribute similarity and contact-book overlap.\n- Honor a \"not interested\" signal: dismissed candidates must not reappear for at least 90 days.\n\n**Non-Functional Requirements:**\n\n- p99 latency under 150ms for the ranking service.\n- Freshness: new edges should affect suggestions within 5 minutes for 95% of users.\n- Scale to 500M DAU, billions of candidate scoring operations per day.\n- Fairness across network size: users with 10 connections should receive as much acceptance rate lift as users with 1000.\n- Privacy: contact-book signals must not leak the identity of the underlying contact.\n\n### ML Problem Framing\n\nPYMK 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.\n\nThere 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.\n\nThe better framing is a multi-task classifier with three heads:\n\n- P(invite_sent | u, v, shown)\n- P(accepted | u, v, invite_sent)\n- P(still_connected_28d | u, v, accepted)\n\nThe serving score blends the three with a reciprocity floor. Candidate generation is a separate problem: retrieve a few thousand plausible `v`s from a billion-node graph in tens of milliseconds. That stage runs against embedding indices and graph walks, not the ranker.\n\n### Metrics\n\n\n| Type | Metric | Why It Matters |\n|---|---|---|\n| Offline | Recall@20 on future edges | Fraction of true future connections appearing in the top 20 |\n| Offline | MRR | How high the true future connection ranks on average |\n| Offline | AUC of P(accept) head | Calibration of the reciprocity model |\n| Offline | Calibrated accept rate | Predicted vs observed accept probability per decile |\n| Online | Invite send rate | Guardrail, not a north star. Overshooting here usually means spam |\n| Online | Invite accept rate | Directly tied to reciprocity |\n| Online | 28-day retained connections | The north star. Low-variance once rolled up weekly |\n| Online | Block/report rate from PYMK candidates | Guardrail against creepy suggestions |\n| Online | Downstream feed engagement | Longer-horizon value of a new connection |\n\n\nInvite 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.\n\n---\n\n# 2. System Architecture\n\nThe 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.\n\n\n```mermaid\nflowchart TD\n subgraph Online[Online Path]\n REQ[Request
user_id + surface]:::primary\n CG[Candidate
Generation]:::orange\n FILT[Filter Stack
blocks, dismisses]:::orange\n FEAT[Feature Fetch]:::teal\n RANK[GNN + Multi-task
Ranker]:::primary\n RR[Diversity
Re-rank]:::teal\n REASON[Reason String
Attacher]:::teal\n RESP[Response
K = 20]:::green\n end\n\n subgraph Offline[Offline Path]\n GW[Graph
Warehouse]:::orange\n TRAIN[Daily Training
two-tower + GNN]:::primary\n EMB[Embedding
Index Build]:::orange\n LABEL[Label Pipeline
invite, accept, 28d]:::teal\n end\n\n subgraph Stream[Streaming Path]\n EVT[Edge Events
Kafka]:::red\n DELTA[Edge Delta
Service]:::orange\n HOT[Hot User
Embedding Refresh]:::teal\n end\n\n REQ --> CG\n CG --> FILT\n FILT --> FEAT\n FEAT --> RANK\n RANK --> RR\n RR --> REASON\n REASON --> RESP\n\n GW --> TRAIN\n LABEL --> TRAIN\n TRAIN --> EMB\n EMB --> CG\n EMB --> FEAT\n\n EVT --> DELTA\n DELTA --> GW\n DELTA --> CG\n DELTA --> HOT\n HOT --> FEAT\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n```\n\n\nThe 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.\n\n### Data Flow\n\n\n```mermaid\nflowchart LR\n A[Edge Events
invite, accept, dismiss]:::red --> B[Kafka]:::orange\n C[Profile Updates]:::orange --> B\n B --> D[Graph
Warehouse]:::teal\n B --> E[Online Feature
Store]:::primary\n D --> F[Feature
Pipelines]:::orange\n F --> G[Training
Dataset]:::teal\n G --> H[Trainer]:::primary\n H --> I[Two-tower
Embeddings]:::teal\n H --> J[GNN
Embeddings]:::teal\n H --> K[Ranker
Model]:::orange\n I --> L[ANN Index]:::green\n J --> E\n K --> M[Model
Serving]:::green\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n```\n\n\nThe 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.\n\n### Back-of-Envelope Numbers\n\n\n| Quantity | Estimate | Notes |\n|---|---|---|\n| Registered users | 1B | Node count in the graph |\n| Average degree | 200 | Right-skewed, top 1% have 5,000+ |\n| Total edges | 200B | Directed edges; roughly 100B connections |\n| DAU | 500M | ~50% of registered users active daily |\n| PYMK impressions per DAU per day | 40 | Two surfaces, average two pages each |\n| Candidates scored per impression | 1,000 | After retrieval, before ranking |\n| Scoring ops per day | 20T | 500M x 40 x 1,000 |\n| User embedding size | 128-dim fp16 | 256 bytes per user |\n| Total embedding storage | ~256 GB | Fits in a sharded in-memory ANN index |\n| Online edge update rate | 50K/s peak | Invites, accepts, dismisses combined |\n\n\nTwenty 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.\n\n---\n\n# 3. Data\n\n### Data Sources\n\nPYMK data falls into five categories. Each feeds a different part of the system.\n\n**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.\n\n**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.\n\n**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.\n\n**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.\n\n**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).\n\n### Feature Engineering\n\nFeatures for PYMK naturally split into pair features, node features, and context features. The pair features do most of the work.\n\n**Pair/graph features** describe the relationship between `u` and `v` in the graph itself:\n\n- Mutual connection count\n- Adamic-Adar score (weighted by inverse log degree of mutuals)\n- Jaccard similarity of 1-hop neighborhoods\n- Common neighbor count at 2 hops\n- Shortest path length in the connection graph\n- Count of shared companies, shared schools, shared cities\n- Number of times `u` viewed `v`'s profile in the last 30 days\n- Whether `u` and `v` share contact-book overlap\n\n**Node embeddings** compress a user's position in the graph and their attributes into a single vector:\n\n- Two-tower user embedding (from profile attributes + declared features)\n- GNN node embedding (GraphSAGE-style, aggregates from 2-hop neighborhood)\n- Affinity cluster ID (coarse cohort, from something like SimClusters)\n\n**Per-user node features** are about the requester or the candidate individually:\n\n- Account age in days\n- Current network size (connection count)\n- Activity level in the last 28 days\n- Signup-cohort bucket\n\n**Context features** cover the request:\n\n- Surface\n- Session freshness (minutes since last PYMK interaction)\n- Locale and device\n- Hour of day (connection acceptance has strong diurnal patterns)\n\n**Negative signals** explicitly encode what the user has told the system not to do:\n\n- Number of prior dismissals of this candidate (must be zero after the 90-day window clears)\n- Prior block or report on any adjacent account\n\n### Feature Table\n\n\n| Feature | Type | Source | Freshness | Description |\n|---|---|---|---|---|\n| mutual_connection_count | Int | Graph walk service | Near-real-time | Number of shared 1-hop neighbors |\n| adamic_adar_score | Float | Graph walk service | Near-real-time | Sum of 1/log(degree) across shared neighbors |\n| jaccard_1hop | Float | Batch + delta | 5 minutes | Jaccard of neighborhood sets |\n| shortest_path_len | Int | Graph walk service | Hourly | Capped at 4 for latency |\n| shared_company_count | Int | Profile service | Daily | Current and past companies |\n| shared_school_count | Int | Profile service | Daily | Declared schools with overlapping years |\n| shared_city | Bool | Profile service | Daily | Same declared city |\n| profile_view_count_30d | Int | Activity pipeline | Hourly | `u` viewed `v` in last 30 days |\n| contact_book_overlap | Bool | Contact service | Daily | Both uploaded, mutual match |\n| two_tower_user_emb | Vec128 | Batch trainer | Daily | User tower output |\n| gnn_node_emb | Vec128 | Batch + hot refresh | Daily, 5 min for hot | GraphSAGE 2-hop embedding |\n| account_age_days | Int | Profile service | Daily | Days since signup |\n| network_size | Int | Graph warehouse | Hourly | Connection count |\n| activity_level_28d | Float | Activity pipeline | Daily | Normalized session count |\n| surface | Enum | Request context | Real-time | PYMK page, onboarding, sidebar |\n| hour_of_day | Int | Request context | Real-time | Local hour bucket |\n| prior_dismissals | Int | Negative-signal store | Real-time | Count within 90-day window |\n| blocked_or_reported | Bool | Safety store | Real-time | Hard filter |\n\n\nFreshness 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.\n\n---\n\n# 4. Model\n\n### Baseline Approach\n\nThe surprising thing about PYMK is how far a pure heuristic gets. A weighted blend of four features captures most of the signal:\n\n\n```shell\nscore = w1 * log(1 + mutual_connections)\n + w2 * shared_company\n + w3 * shared_school\n + w4 * same_city\n```\n\n\nTuned 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.\n\nThe 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.\n\n### Advanced Approach\n\nThe production system is a multi-stage pipeline. Candidate generation unions three retrieval sources, then a GNN-powered ranker scores the union.\n\n**Candidate generation** runs four sources in parallel and unions their top-K results:\n\n1. **Friend-of-friend walk.** A 2-hop walk from `u` with early termination. For each 1-hop neighbor `w`, expand to `w`'s neighbors and keep the top-N by a cheap pair score (mutual count + shared company). Cached per user and refreshed by edge-delta events.\n2. **Two-tower ANN retrieval.** Embed the requester with a user tower over profile attributes, retrieve the top-M nearest candidates from a HNSW index over the candidate tower. Handles users where the graph is sparse.\n3. **Cohort retrieval.** Look up coarse clusters (SimClusters or similar) and pull high-acceptance candidates within the same cluster. Good for new users who have attributes but no edges yet.\n4. **Contact-book candidates.** Direct lookup against the contact-overlap table, filtered by mutual consent.\n\nEach source returns 200-500 candidates. The union is typically 1,000-1,500 after deduplication.\n\n\n```mermaid\nflowchart LR\n U[User Request]:::primary --> UTW[User Tower
profile attrs]:::orange\n UTW --> UEMB[User Emb
128-dim]:::teal\n UEMB --> ANN[(HNSW
ANN Index)]:::green\n CTW[Candidate Tower
batch embed]:::orange --> CEMB[Candidate
Emb Index]:::teal\n CEMB --> ANN\n ANN --> TOP[Top-M
Candidates]:::green\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\n**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.\n\n\n```mermaid\nflowchart TD\n UN[Candidate Union
~1,200 pairs]:::orange --> GF[GNN Feature Fetch
u_emb, v_emb]:::teal\n UN --> PF[Pair Feature Fetch
mutual, adamic-adar, jaccard]:::teal\n UN --> CF[Context Features
surface, hour]:::teal\n GF --> CONCAT[Concat
+ cross layer]:::orange\n PF --> CONCAT\n CF --> CONCAT\n CONCAT --> MLP[Shared MLP]:::primary\n MLP --> H1[P invite]:::teal\n MLP --> H2[P accept given invite]:::teal\n MLP --> H3[P retained 28d]:::teal\n H1 --> BLEND[Blended Score
reciprocity floor]:::green\n H2 --> BLEND\n H3 --> BLEND\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\nThe 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.\n\nThe 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.\n\n### Training\n\n**Labels** come from the activity log, joined with a 28-day lookback:\n\n- `y_invite`: did `u` send an invite to `v` within 7 days of impression?\n- `y_accept`: given an invite was sent, did `v` accept within 14 days?\n- `y_retained`: given accepted, did the edge still exist at T+28?\n\nEach label is defined only on the conditional population, which matters for the loss.\n\n**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.\"\n\n**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.\n\n**Loss.** A masked, weighted BCE across the three heads:\n\n\n```python\ndef pymk_loss(y, logits, mask, w):\n # y: (B, 3) binary labels for invite, accept, retained\n # logits: (B, 3) model outputs\n # mask: (B, 3) 1 if the label is defined for this row\n # w: (3,) task weights; retained weighted highest\n per_task = F.binary_cross_entropy_with_logits(\n logits, y.float(), reduction=\"none\"\n )\n masked = per_task * mask\n per_task_loss = masked.sum(dim=0) / mask.sum(dim=0).clamp(min=1.0)\n return (per_task_loss * w).sum()\n```\n\n\nThe 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.\n\n---\n\n# 5. Serving\n\nThe 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.\n\n### Inference Pipeline\n\n\n```mermaid\nflowchart LR\n REQ[Request
user_id, surface]:::primary --> CG[Candidate Union
FoF + ANN + cohort + contacts]:::orange\n CG --> DEDUP[Dedup]:::teal\n DEDUP --> FILT[Filter Stack
blocks, connected, dismissed]:::red\n FILT --> FEAT[Feature Fetch
GNN emb + pair + context]:::teal\n FEAT --> RANK[Multi-task Ranker]:::primary\n RANK --> RR[Diversity
Re-rank]:::orange\n RR --> REASON[Reason String
Attacher]:::teal\n REASON --> RESP[Response
K = 20]:::green\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n```\n\n\nCandidate 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.\n\nThe 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.\n\nFeature 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.\n\nDiversity 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.\n\nThe serving score blends the three heads with a reciprocity floor:\n\n\n```python\ndef blended_score(p_invite, p_accept, p_retained,\n min_accept=0.25, w_invite=0.1,\n w_accept=0.3, w_retained=0.6):\n # Hard floor: don't surface candidates likely to ignore\n if p_accept < min_accept:\n return float(\"-inf\")\n # Weighted log-combination gives stable ranks across surfaces\n eps = 1e-6\n return (\n w_invite * math.log(p_invite + eps) +\n w_accept * math.log(p_accept + eps) +\n w_retained * math.log(p_retained + eps)\n )\n```\n\n\nThe 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.\n\n### Batch vs Real-Time\n\n\n| Component | Mode | Freshness | Why |\n|---|---|---|---|\n| Two-hop walk index | Batch nightly + streaming delta | 5 minutes | Cache 2-hop neighborhoods per user; delta events invalidate affected slices |\n| ANN index (candidate tower) | Batch with incremental adds | 1 hour | Full rebuild weekly, incremental adds for new users |\n| GNN node embeddings | Batch daily + hot refresh | Daily, 5 min for hot users | Full population nightly; recompute on significant neighborhood change |\n| Pair features | On-demand | Near-real-time | Computed at request time from the walk cache |\n| Ranker | Real-time | N/A | Stateless inference |\n| Filter stack | Real-time | Near-real-time | Blocks and dismissals must take effect immediately |\n| Reason-string rules | Real-time | N/A | Deterministic from pair features |\n\n\nThe 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.\n\n### Latency Budget\n\n\n| Stage | p99 Budget | Notes |\n|---|---|---|\n| Candidate union (parallel fanout) | 35ms | Dominated by slowest of four retrieval sources |\n| Filter stack | 10ms | Bloom filters for blocks and prior dismissals |\n| Feature fetch | 25ms | Batched lookups to GNN and pair feature stores |\n| Ranker inference | 40ms | MLP over 1,200 candidates, CPU or small GPU |\n| Diversity re-rank | 10ms | Rule-based, in-process |\n| Reason-string attach | 5ms | Table lookup |\n| Network and serialization | 20ms | Internal RPCs and response build |\n| Total | 145ms | Target: p99 < 150ms |\n\n\nThe 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.\n\n### Streaming Graph Updates\n\n\n```mermaid\nflowchart LR\n EVT[Edge Event
invite, accept, dismiss]:::red --> KAFKA[Kafka]:::orange\n KAFKA --> DELTA[Edge Delta
Service]:::primary\n DELTA --> WC[2-hop Walk
Cache]:::teal\n DELTA --> NEG[Negative
Signal Store]:::teal\n DELTA --> HOT{Significant
Change?}:::orange\n HOT -->|Yes| EMB[Trigger Hot
Embedding Refresh]:::teal\n HOT -->|No| DONE[No-op]:::green\n EMB --> STORE[GNN Embedding
Store]:::teal\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n```\n\n\nEvery 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.\n\n---\n\n# 6. Deep Dives\n\n### Graph Representation: FoF Walks, GNN Embeddings, and Two-Tower\n\nThe 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.\n\n**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.\n\n**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.\n\n**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.\n\n\n| Approach | Cold Start | Captures Graph | Scales to 1B | Reason String |\n|---|---|---|---|---|\n| FoF walks | Poor | Yes, explicitly | With cache | Trivial |\n| GNN embeddings | OK via attributes | Yes, learned | Yes | Hard |\n| Two-tower | Strong | No | Yes, ANN | Moderate |\n\n\nThe 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.\n\n### Reciprocity Prediction and Label Design\n\nThe label choice is the single most important design decision in this system, and it is where the most experience matters.\n\nThe 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.\n\nThe 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.\n\nThe 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.\n\n\n| Label | Noise | Delay | Alignment with Value |\n|---|---|---|---|\n| P(invite_sent) | High | 0-7 days | Weak; rewards spammy candidates |\n| P(accepted) | Medium | 7-14 days | Good; production minimum |\n| P(retained_28d) | Low | 28-35 days | Best; matches north-star metric |\n| Blend of all three | Calibrated | Mixed | Strongest; via multi-task loss |\n\n\nThe 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.\n\n### Privacy, Blocks, and Sensitive Edges\n\nPYMK 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.\n\n\n```mermaid\nflowchart TD\n IN[Candidate Union]:::orange --> F1{Blocked or
Reported?}:::red\n F1 -->|Yes| DROP1[Drop]:::red\n F1 -->|No| F2{Already
Connected?}:::red\n F2 -->|Yes| DROP2[Drop]:::red\n F2 -->|No| F3{Recently
Dismissed?}:::red\n F3 -->|Yes| DROP3[Drop]:::red\n F3 -->|No| F4{Sensitive
Edge?}:::orange\n F4 -->|Yes| DROP4[Drop]:::red\n F4 -->|No| F5{Rate Cap
Per Session?}:::orange\n F5 -->|Exceeded| DROP5[Drop]:::red\n F5 -->|OK| OUT[Pass to Ranker]:::green\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n```\n\n\nSensitive-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.\n\nThe 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.\n\n### Diversity, Fairness, and the Rich-Get-Richer Problem\n\nThe 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.\n\nThis 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.\n\n\n| Degree Bucket | Surface Probability (Uncorrected) | Accept Rate | Action |\n|---|---|---|---|\n| 0-50 | Very low | High | Boost when predicted P(accept) is high |\n| 50-200 | Moderate | Moderate | Neutral |\n| 200-1,000 | High | Moderate | Mild dampening |\n| 1,000-5,000 | Very high | Low | Strong dampening via accept floor |\n| 5,000+ | Dominant | Very low | Cap impressions per day |\n\n\nThe 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.\n\nFairness 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.\n\n---\n\n# 7. Evaluation and Iteration\n\n### Offline Evaluation\n\nThe 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.\n\nThe 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.\n\n\n```mermaid\nstateDiagram-v2\n [*] --> SPLIT: Snapshot at T-7\n SPLIT --> TRAIN: edges in T-37..T-7\n SPLIT --> EVAL: edges in T-7..T\n TRAIN --> MODEL: Fit\n MODEL --> SCORE: Score eval pairs\n EVAL --> SCORE\n SCORE --> METRICS: Recall@20, MRR, AUC\n METRICS --> CALIB: Accept-rate calibration\n CALIB --> [*]\n\n classDef start fill:#00ceff,stroke:#000,color:#000\n classDef proc fill:#ffa94d,stroke:#000,color:#000\n classDef done fill:#69db7c,stroke:#000,color:#000\n\n class SPLIT start\n class TRAIN proc\n class EVAL proc\n class MODEL proc\n class SCORE proc\n class METRICS proc\n class CALIB done\n```\n\n\nCalibration 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.\n\nCounterfactual 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.\n\n### Online Evaluation\n\nOffline 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.\n\n\n```mermaid\nstateDiagram-v2\n [*] --> SHADOW: Shadow 24h\n SHADOW --> RAMP1: 1 percent DAU\n RAMP1 --> RAMP5: 5 percent DAU\n RAMP5 --> RAMP50: 50 percent DAU\n RAMP50 --> LAUNCH: Full ramp\n RAMP1 --> ROLLBACK: Guardrail breach\n RAMP5 --> ROLLBACK: Guardrail breach\n RAMP50 --> ROLLBACK: Guardrail breach\n LAUNCH --> [*]\n ROLLBACK --> [*]\n\n classDef start fill:#00ceff,stroke:#000,color:#000\n classDef ramp fill:#ffa94d,stroke:#000,color:#000\n classDef good fill:#69db7c,stroke:#000,color:#000\n classDef bad fill:#ff8787,stroke:#000,color:#000\n\n class SHADOW start\n class RAMP1 ramp\n class RAMP5 ramp\n class RAMP50 ramp\n class LAUNCH good\n class ROLLBACK bad\n```\n\n\nThe 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.\n\nA 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.\n\n### Monitoring\n\nProduction 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.\n\nThe 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.\n\n---\n\n# Summary\n\n- PYMK is link prediction on a billion-node heterogeneous graph. The social graph is the data, not a feature bolted onto a general recommender.\n- Optimize for reciprocity, not invite clicks. Label on accepted connections at minimum, and on 28-day retained connections where variance allows.\n- Retrieval unions three sources: friend-of-friend walks for dense networks, GNN embeddings for structural matches, and two-tower ANN for cold-start coverage. Each covers a failure mode of the others.\n- The ranker is a multi-task model sharing a trunk across invite, accept, and retention heads. A masked BCE loss keeps the conditional heads honest.\n- The reciprocity floor on P(accept) is the single biggest lever against surfacing celebrities and other high-degree low-acceptance candidates.\n- Filter stacks run before the ranker, in the order blocks, connected, dismissed, sensitive-edge, rate cap. Contact-book overlap can influence rank but can never appear in a reason string.\n- Rich-get-richer dynamics are structural and must be corrected at both the retrieval cap and the re-ranker. Audit fairness weekly across degree deciles.\n- Retrain daily on a 30-day window, refresh GNN embeddings within minutes for hot users, and keep a 1% permanent holdout to measure long-horizon effects.\n\nThe 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.\n\n---\n\n# References\n\n- Hamilton et al., \"Inductive Representation Learning on Large Graphs\" (GraphSAGE). https://arxiv.org/abs/1706.02216\n- Ying et al., \"Graph Convolutional Neural Networks for Web-Scale Recommender Systems\" (PinSage). https://arxiv.org/abs/1806.01973\n- LinkedIn Engineering, \"Quasi-succinct indices\" and the PYMK architecture posts. https://engineering.linkedin.com/\n- Huang et al., \"Embedding-based Retrieval in Facebook Search.\" https://arxiv.org/abs/2006.11632\n- Satuluri et al., \"SimClusters: Community-Based Representations for Heterogeneous Recommendations at Twitter.\" https://dl.acm.org/doi/10.1145/3394486.3403370\n- Backstrom and Leskovec, \"Supervised Random Walks: Predicting and Recommending Links in Social Networks.\" https://arxiv.org/abs/1011.4071","pageType":"ml-system-design"}

Design People You May Know

Ashish Pratap Singh

Get Premium