How to design connection recommendations

People You May Know (PYMK) suggests other members you might want to connect with. In this lesson, we’ll design that system for a professional network with one billion registered members and 1.6 x 10^11 connections between them.

The thing being ranked is a person, and the hard parts follow from that. A bad suggestion costs three things at once: the viewer loses a slot, the recipient gets an unwanted invitation, and the suggestion can disclose a relationship neither party chose to make public.

The candidate set comes from walking the graph and enumerating everyone reachable, not from a retrieval index. That creates an arithmetic problem with no analogue in the feed-ranking chapter or the video-recommender chapter: the pool of plausible candidates for one member can exceed twenty-five million and must be cut to twenty.

Four things drive the design, and this lesson takes them in turn:

• Why one member can have twenty-five million plausible candidates, and how to cut that to twenty without discarding good ones.
• How to weight a shared connection by the evidence it carries, and why the textbook weighting is too gentle.
• The class of privacy failure that a more accurate model makes worse.
• Every model in the design, and the number that measures whether each one works.

By the end you’ll be able to size the candidate funnel from the degree distribution, name the metric that decides each stage, and defend the privacy and feedback-loop choices in an interview.

The graph vocabulary, defined once

Everything here happens on a graph: a set of nodes (members) joined by edges (accepted connections).

• Degree d is how many connections a member has. d_w is node w’s degree.
• A neighbor of u is anyone u connects to directly; N(u) is that set. The stored list of u’s neighbors is u’s adjacency list.
• A hub is a node with unusually large degree: a recruiter, a celebrity, an account that accepts everything.
• A common neighbor of u and v is someone connected to both. CN(u, v) is how many there are.
• A second-degree connection (a 2-hop candidate, or friend-of-a-friend, FoF) is someone u is not connected to but shares at least one common neighbor with. A 2-path is one route u -> w -> v through a common neighbor w; a single candidate may be reachable by many 2-paths.
• Triadic closure is the event this system is built around: two people who share a common neighbor connect to each other, completing a triangle.
• A random walk from u starts at u and repeatedly steps to a random neighbor. It explores a graph without loading it into memory, and two models below rest on it.

Two more terms recur throughout.

AUC (area under the ROC curve) is the probability that a randomly chosen pair that really did connect scores above a pair that did not. It runs from 0.5 (a coin flip) to 1.0 (perfect ordering), and it is the offline quality number for every model below.

A prior is the fraction of positives in a population. This design carries three populations with very different priors, so a prior quoted without its population is not usable.

The eight pieces, and how you know each one works

PYMK is not one model. It is eight pieces: a graph traversal that enumerates candidates, two things that summarize the network’s shape without ever seeing what a good suggestion looks like, a cheap cut that discards most of what the traversal found, one ranker trained on outcomes, a second scoring head for a different question, and two small corrections because the ranker’s raw score is not on a usable scale.

Three things in that roster matter most.

Privacy lives in the generator, not the ranker. Rows one and two decide which pairs come into existence at all, and a candidate that reaches the ranker can leak through ordering even when it is never displayed. The hard privacy gate therefore sits between generation and scoring.

Two of the three most valuable signals are not learned. Personalized PageRank and the activity prior are the top standalone AUC and the largest single shipped gain, and neither has a training label. The learned ranker combines; it does not discover.

Most subtle of all, the accept ranker’s label is manufactured by the previous accept ranker, which is what the next section is about.

The label problem: a connection that was never suggested cannot be accepted

The accept ranker learns P(accept | sent). To observe that label for a pair (u, v), three things must have happened, in order:

1. The generator produced v as a candidate for u.
2. The ranker put v in one of twenty slots.
3. u chose to send.

Every one of those is a decision by the deployed system. So the training set is not a sample of possible connections. It is a sample of the connections the previous model liked, filtered again by what it ranked highly, filtered again by what users did.

flowchart TD
    GEN["Generator proposes v"] --> RANK["Ranker puts v in top 20"]
    RANK --> USER["User sends, then accept observed"]
    USER --> LOG["Impression / send / accept log"]
    LOG -->|becomes next model's labels| GEN
    RANK -.->|ranked below 20: no label at all| ABSENT["Absent, not negative"]

Three consequences follow.

The labels are missing not at random, and the model causes the missingness. Pairs the old ranker scored low have no label at all, not a negative, an absence. Train only on observed rows and the new model inherits the old model’s blind spots as facts about the world: whatever it never showed, the new model never learns to score, so it keeps not showing it. That closed loop reappears later as degree concentration and cross-group narrowing.

The negatives are therefore constructed, not collected. Half are sampled from candidates that were shown and declined (these teach the boundary the system currently sits on); half are random admissible 2-hop pairs never shown to anyone. The second half is the only place the model sees the region its predecessor ignored.

The value metric, finally, needs a permanent holdout of 0.5% of members for whom PYMK is switched off entirely. Inside the loop, “connections formed” is unattributable, because the system’s own history determines what could have formed. The holdout is the one population the loop never touched.

The full label is therefore: accept within 14 days of send, generated by last week’s model, plus a deliberate sample of pairs it never showed anyone.

What goes in and what comes out

Three assumptions are load-bearing; the rest can move by a factor without changing an argument.

• The degree distribution is heavy-tailed. A small share of members have enormous degree, so degree variance dwarfs its mean. Nearly every number in candidate generation is this one fact compounding. On a graph with mild degree variance, half the design decisions reverse.
• The training labels come from the previous version of the system. If labels arrived from a randomized policy, the easy-negative half of the training set and the permanent holdout would both be optional. They are not.
• An unwanted invitation has a real cost, taken as c ≈ 0.3 V where V is the value of an accepted one. Set c = 0 and the economic gate vanishes and the design collapses into “maximize accepts”. The value 0.3 is estimated from decline-and-block rates; that it is non-zero is the load-bearing part.

One thing is assumed instead of derived, and worth flagging: that a reliable “sensitive category” flag exists on a profile. In a real system it is itself a classifier with an error rate, and its false negatives are exactly the disclosure risk below.

What are we actually predicting?

The obvious target, P(u knows v), is close to worthless. Here are seven candidates for one viewer:

Four rows have P(knows) = 1 and value ranging from strongly negative to high. Knowing someone is nearly uninformative about whether the suggestion is good.

The real target is three terms multiplied, minus a fourth:

Value(u, v)  =  P(u sends an invite | shown)
             ·  P(v accepts | sent)
             ·  E[ engagement created by the edge, over 90 days ]
             -  (1 - P(accept)) · recipient_cost

Three properties of that expression drive everything downstream.

Only the first two terms are learnable from logs. Sends and accepts are events that get written down, but “engagement created by the edge” is a counterfactual: you would need the viewer’s next 90 days without the edge, and the edge exists. It has no per-pair label, ever, and is estimable only as a difference between two populations, one with the feature off (the holdout), so it can inform the weights you choose but can never be a training target.

The subtracted term makes the problem two-sided. At scale that cost is not rounding error: 6 x 10^8 slots/day at a 4.2% send rate is 25.2 M invitations, of which 59.5% accept, leaving 10.2 M declined or ignored invitations per day, people who received something they did not act on. A ranker that counts only accepts treats those as free.

“Value” for a professional network is not engagement. If connections drive referrals, job discovery, and information flow, then who gets connected is an economic outcome, and the system moves that distribution measurably in the wrong direction without any demographic feature present anywhere in it (shown later).

Candidate generation: the 2-hop explosion

Empirically, 60-80% of new edges close a triangle. That makes the 2-hop neighborhood the candidate source, and everything else (contact imports, shared workplace, embeddings) a supplement. The trouble is its size: the 2-hop neighborhood of an active member runs to tens of millions.

Why d^2 is the wrong estimate

The naive estimate of a 2-hop neighborhood is d^2, your d connections times their d connections. It is badly low, because of how sampling works on a graph:

When you reach a node by following an edge, you sample nodes in proportion to their degree. So the expected degree of a random neighbor is not E[d], it is E[d^2] / E[d] = E[d] + Var(d)/E[d].

This is the friendship paradox: your friends have more friends than you do, on average, and the excess is exactly Var(d)/E[d]. Not because you are unpopular, but because a popular person is somebody’s friend more often, so popular people are over-represented among the people you arrive at by following an edge.

Measuring a real degree distribution in buckets (instead of assuming a shape) gives the inputs the identity needs:

Averaging across the population (a share times each bucket mean, summed):

E[d]    =  316        median = 89        (mean and median are not interchangeable)
E[d^2]  =  1.30e6     Var(d) = 1.20e6    sd(d) = 1,094

expected degree of a random neighbor  =  E[d^2] / E[d]  =  4,110

Your average connection has 4,110 connections while the average member has 316, a factor of 13, driven entirely by the tail. The last table row dominates: 0.6% of members contribute 74% of E[d^2].

Now the 2-hop counts, for three members. Multiply the member’s own degree by 4,110 (2-paths, not people), then divide by the average number of 2-paths that land on the same person (~4 for a typical member, ~5 at the cap where neighborhoods overlap more):

median member,  d = 89:     89 x 4,110    ~ 366,000 2-paths  / ~4  =  ~91,000 candidates
budgeted member, d = 240:   240 x 4,110   ~ 987,000 2-paths  / ~4  =  ~250,000 candidates
cap-degree member, d = 30k: 30,000 x 4,110 ~ 1.2e8 2-paths   / ~5  =  ~25,000,000 candidates

That is twenty-five million distinct candidates, 2.5% of the entire network, for one impression of twenty slots. Such members number in the hundreds of thousands: recruiters, salespeople, public figures.

The global identity, and the retrieval base rate

Counting candidate pairs the whole platform can produce: each member w puts C(d_w, 2) ≈ d_w^2 / 2 pairs on the table, and summing over all N members gives N · E[d^2] / 2:

candidate pairs  ~  N · E[d^2] / 2  =  6.5 x 10^14
existing edges   =  N · E[d]   / 2  =  1.6 x 10^11
ratio            =  E[d^2] / E[d]   =  4,110

The candidate space is exactly the friendship-paradox mean, 4,110x, larger than the edge set. Out of all those pairs, what share are real connections? The stock ratio (edges that exist now over candidate pairs) is 1.6e11 / 6.5e14 = 2.5 x 10^-4; the flow (new edges per year over candidate pairs) is ~5.6 x 10^-5. Both are order 10^-4.

Write it P(edge | candidate pair) ~ 10^-4 and keep the conditioning visible. About one candidate pair in ten thousand is a real connection, which makes generation an extreme-imbalance retrieval problem, positives so rare that finding them at all is the hard part.

This is not the accept ranker’s prior. That model’s label is accept within 14 days of send, so it lives on the population of sent invitations, where the positive rate is 59.5%, about 2,400 times higher. Confusing the two is a costly mistake: a gate stated in the sent population’s units, applied to a retrieval-population score, rejects everything.

What that forces: capping and sampling

E[d^2] is dominated by its tail (the top 0.6% of nodes are 74% of it), so capping the degree of the intermediate node is the whole cost model, not a heuristic. Refuse to walk through anyone with more than 1,000 connections:

skip hubs (`if d_w > 1,000: continue`)      23.5x fewer candidate pairs, 95.7% of work removed
min-cap instead (count min(d_w, 1000)^2)    only 11.2x

The two rules are 2x apart. This design skips, so the saving is 23.5x. Quoting one number while shipping the other gives a figure nobody can reproduce from the code.

Skipping hubs costs almost no quality: a common neighbor of degree 2,100 carries about 1/2,100 the evidence of a degree-1 common neighbor under any defensible weighting (derived next). The nodes that generate the most candidates are the nodes whose candidates are worth the least.

The full per-user budget, from the viewer’s connections down to twenty suggestions:

flowchart TD
    A["Viewer's own neighbors<br/>240 sampled, weighted 1/log(d)"] --> B["2-hop expansion<br/>skip hubs above degree 1,000<br/>sample 200 per intermediate"]
    B --> C["Raw 2-paths<br/>48,000"]
    C --> D["Distinct candidates<br/>~30,000"]
    D --> E["Cheap-score cut<br/>common neighbors, resource allocation, activity prior<br/>5,000 kept"]
    E --> F["GBDT ranker<br/>graph + non-graph features<br/>5,000 scored"]
    F --> G["Slate<br/>diversity, caps, privacy<br/>20 shown"]

The budget is sized at d = 240 (about the 74th percentile), not the median d = 89, so it covers well over half the traffic: the median member’s ~91,000-person neighborhood sits comfortably inside it. Five thousand is where an exhaustive scan lands, and the cut from 30,000 to 5,000 does more for cost than the ranker does for quality. That is the two-stage pattern (a cheap model narrows a huge pool, an expensive model orders the survivors) with the usual retrieval stage replaced by a graph traversal.

Graph features

A feature is one number computed about a candidate pair. The graph features measure the shape of the network around u and v.

Common neighbors, and why raw counting fails

CN(u, v) = |N(u) ∩ N(v)| (the number of shared connections) is the best single predictor computable in one line. Its failure is specific:

pair (u, v1):  3 common neighbors, degrees      14,     22,     31
pair (u, v2):  3 common neighbors, degrees   8,400, 12,000, 26,000
CN = 3 for both.

The first pair shares three people from a tight cluster (a team, a class, a family). The second both follow three famous accounts they share with millions of others. Counting calls these the same evidence.

Adamic-Adar, resource allocation, and the null model

The fix is to weight each shared connection by its rarity instead of counting it. Adamic-Adar (AA) weights each shared neighbor by 1/log(d_w), so a low-degree connection counts for more than a celebrity:

AA(u, v)  =  sum over w in CN(u,v)  of  1 / log(d_w)

This is the same shape as IDF (inverse document frequency) in text search: common words like “the” count for less than rare ones. It is a reasonable instinct, but it is not derived, and it turns out to be far too gentle.

Deriving the right weight needs a null model: a randomized graph that keeps the properties you do not care about and destroys the ones you do. The configuration model cuts every edge in half and rewires the halves at random, preserving every node’s degree exactly while destroying all real structure. Under it, the probability that w is a neighbor of u is d_u · d_w / 2m (where m is the edge count), so the expected number of common neighbors is:

E[CN(u,v)]  =  (d_u d_v / (2m)^2) · sum_w d_w^2

A node w contributes to the null expectation in proportion to d_w^2. A log-odds score divides observed by expected-under-null, so the evidence a common neighbor provides should be down-weighted by 1 / d_w^2.

Resource allocation (RA) sits between AA and the null: weight by 1/d_w, on the picture that a shared connection has one unit of attention to divide among all their connections. Putting the four weightings side by side, the only comparable row is the last, each column’s discount across a 6,000-fold degree range:

Across a 6,000-fold difference in the common neighbor’s degree, counting applies no discount, Adamic-Adar applies 6.4x, resource allocation 6,000x, and the null says 36 million. On the worked pair, AA rates the two candidates 3.2x apart (0.994 vs 0.315), RA rates them 619x apart (0.149 vs 2.4e-4). The correct answer is nearer the last, because “we both follow three famous accounts” is not evidence. Use Adamic-Adar when the degree distribution is mild and resource allocation when it has a heavy tail, which any real social graph does.

Generate with the cap, but score without it. The cap skips v2 at generation (all three of its common neighbors are hubs), which is correct: paying to enumerate it is exactly the hub tail the cap declines to pay. But the cap is a generation rule, not a feature definition, and the two must not share code. If v2 arrives from another generator (an embedding, a shared workplace, a contact import), its features must be computed over every shared neighbor, uncapped. Drop the hub witnesses at scoring time and RA has nothing left to down-weight: the pair reaches the ranker with CN = 0, looking like two strangers, not a weak match.

Jaccard corrects a different thing

The Jaccard coefficient asks what share of the two people’s combined social worlds is shared, not the absolute count:

J(u, v)  =  |N(u) ∩ N(v)| / |N(u) ∪ N(v)|

AA and RA normalize by the degree of the intermediate (the shared connection). Jaccard normalizes by the degrees of the endpoints (u and v themselves). They fix different biases. A viewer with 500 connections might share 8 with v1 (who has 450) and 5 with v2 (who has 30): counting prefers v1, but Jaccard prefers v2, because 5 of 30 is a much larger share of v2’s world than 8 of 450. Jaccard is orthogonal to AA, not a refinement, so the model gains from having both.

Personalized PageRank, cheaper than it sounds

Personalized PageRank (PPR) from u measures how much of a random walker’s time is spent at each node, when the walker starts at u and at every step either steps to a random neighbor or teleports back to u with probability alpha. Because it keeps restarting at u, it stays in u’s vicinity. It sees paths of every length and rewards many short paths, capturing “we are embedded in the same dense region”, which no 2-hop statistic can express.

Computing the exact stationary distribution means solving a billion-unknown linear system per user, infeasible. So sample it instead: run the walk many times and count where it lands (a Monte Carlo estimate). Priced for the whole platform:

2,000 walks/source, expected length 1/alpha = 6.7 hops  ->  1.34 x 10^13 hops for the full graph
at ~1e6 hops/s/core (adjacency reads are cache-hostile) ->  ~45 minutes on 5,000 cores

The catch is precision, not cost. A node visited 3 times out of 2,000 walks has a relative standard error of 1/sqrt(3) = 58%, because counting random events gives an error that grows like the square root of the count. Monte Carlo PPR is therefore excellent for generating the top few thousand candidates and poor as a fine-grained ranking feature. Use the visit count as a coarse bucket (0 / 1-5 / 6-50 / more), not a continuous score.

Embeddings, and what a low-rank factorization cannot keep

An embedding is one vector of 128 numbers per member, learned so that members near each other in the graph get similar vectors. node2vec runs random walks, treats each as a sentence and each node as a word, and fits a skip-gram model with negative sampling on the graph. Graph neural networks instead compute each node’s vector by repeatedly aggregating its neighbors’ vectors. Either way you get a vector per node and cheap ANN (approximate nearest neighbor) retrieval over it.

Pricing the representation is a one-line counting argument:

1e9 nodes x 128 dims x 2 bytes (fp16)  =  256 GB
edges being represented                =  1.6 x 10^11
parameters per edge                    =  0.8

That is fewer than one learned number per edge, so the embedding must compress. It cannot store the graph, only summarize it. That summary is a low-rank factorization, which by construction keeps the smooth, global structure (communities, industries, geographies) and discards the idiosyncratic single path. But the thing PYMK has to decide is exactly the fine structure: not “are these two in the same community” (they are, along with four million others) but “is there a specific reason these two should connect.”

Dimension is chosen where recall@k for candidate generation plateaus, not where a classification loss bottoms out. Below ~128 dimensions the smooth structure collides in the ANN index; above it, recall is flat while the store grows linearly (256 dims doubles the store to 512 GB for no measurable gain). So 128 is the smallest dimension that holds the smooth structure, and more is waste, because the fine structure is not recoverable at any feasible dimension.

So embeddings generate the ~15% of candidates FoF traversal cannot reach (same field, same alumni cohort, zero common neighbors) while the sparse path features decide: common neighbors, resource allocation, PPR, shared workplace, contact provenance. Each of those is a statement about one specific path between two specific people, which is exactly what a compressed vector cannot hold.

The comparison, with cost

Freshness is how stale a feature can be before it stops being useful. Standalone AUC is its quality used alone.

Adding a fifth graph feature moves AUC by thousandths, while adding the non-graph block moves it by 0.035. The graph features are all measuring the same underlying quantity through slightly different lenses and correlate at 0.7-0.9 with each other. Spend the effort beyond the graph.

Every AUC here is a temporal-split (train on the past, test on the future, not a random shuffle) and de-sampled (the deliberate over-representation of positives in training corrected out), against a 14-day label. Quoted any other way it is not comparable to the online accept-of-sent rate it predicts: a random split would read near 1.0 offline and collapse in production.

The load-bearing assumption under this whole section is that the graph is a fair record of who knows whom. Every feature reads structure and infers intent from it. A tie somebody deliberately severed leaves exactly the same structural fingerprint as their closest tie. No graph feature can fix that, because the assumption, not the feature, is what broke.

Beyond the graph, and the privacy constraint

The next 0.035 of AUC is outside the graph, and the strongest signals are also the ones that can hurt people.

The strongest signal in the table is also the riskiest, which the next two sections explain.

The address-book asymmetry

The central privacy idea: the evidence that justifies a suggestion can itself be private information about a third party. Provenance, the record of where a piece of evidence came from, is the only thing that can express that.

Alice imports her phone contacts. Bob's number is among them.
Bob has never used this feature.

Surfacing Bob to Alice   discloses that Bob is a member.
Surfacing Alice to Bob   discloses that ALICE HAS BOB'S PHONE NUMBER.

The second direction is the leak: evidence obtained from one party must not be surfaced to the other, because the evidence itself is private information about the first party. The worst version:

Carol is a therapist. She imports 300 patients in her contacts.
For every pair of patients (A, B):
  - both are neighbors of Carol in the contact-provenance channel
  - Carol's degree there is 300 -- small enough that RA and AA rate her a STRONG common neighbor
  - A and B are geographically co-located
The ranker scores (A, B) highly and suggests A to B.

The prediction is correct: A and B genuinely have a person in common. And surfacing it discloses that both see the same therapist, a fact neither disclosed, inferred from a third party’s phone. The failure is not a false positive; it is a true positive that must not be shown. No amount of model quality fixes it; only a rule about provenance does. Same structure elsewhere: a pseudonymous account surfaced to the holder’s real-world contacts via a shared device; someone who left an abusive relationship surfaced to the person they left because forty mutual connections survive; members of a recovery or health group surfaced to each other because the group is a small, high-precision common neighbor.

Co-location: the precision and the harm are the same quantity

The signal “you were in the same place at the same time” is rejected outright, and the argument is a derivation. Its precision (the share of flagged pairs that really know each other) goes as k / n in n, the number of people at the venue at that moment:

airport terminal,   n ~ 8,000  ->  precision ~ 0.001
office floor,        n ~ 300    ->  precision ~ 0.05
conference room,     n ~ 12     ->  precision ~ 0.6
clinic waiting room, n ~ 6      ->  precision ~ 0.7

The co-locations with usable precision are exactly the small private venues, and the identity of a small private venue is the sensitive attribute: a clinic, courthouse, shelter, place of worship, support meeting. The signal’s usefulness and its capacity for harm are literally the same number; no threshold separates them. So do not use fine-grained co-location as evidence at all. Coarse self-declared location (city, region) is fine as a filter on candidates generated by other means, which narrows a pool instead of creating an edge.

The mechanisms

Privacy here is a constraint on the generator, not a filter on the output, for two reasons. Ordering leaks: a candidate scored and then suppressed still shifted everything below it, so the slate is evidence about the candidate the viewer did not see. And soft penalties become training data: a model retrained on logs produced under a post-hoc penalty learns to route around it, producing the candidates the penalty does not catch.

The controls, all code, not policy:

1. Provenance on every candidate, with two kinds of bit. Each candidate carries a mask of which evidence sources produced it (FoF, contact import in each direction, workplace, school, embedding). Separately, the mask records which flags the evidence carries: is the lone common neighbor in a sensitivity-flagged category? Is it a common neighbor only because someone’s address book made it one? Sources justify surfacing; flags never do.

2. Directional rules on one-way evidence. A candidate whose only justifying source is “they imported me” is generated for the importer and never for the imported party. This must be tested as a mask (“does this candidate have any other justifying source”), never as provenance == CONTACT_THEIRS: an equality test on a bitmask is defeated by any extra bit, including a flag, which is not a source and justifies nothing.

3. An evidence-count floor, applied narrowly. A global “at least two common neighbors” rule is unaffordable: 62% of the pool has exactly one common neighbor and produces 30% of all accepts. Applied only where the lone common neighbor’s evidence is contact-import-only, it touches 4.1% of the pool and 1.2% of accepts.

4. A second witness cures contact-manufactured evidence but not a flagged category. Two people whose address books independently hold the same pair is ordinary evidence. Two clinicians at the same practice is a stronger inference about the same sensitive fact. So the flagged branch ignores witness count and requires a justifying source from outside the witness set, the only thing that gives the suggestion a reason that is not the clinic.

5. Blocks and mutes are symmetric, propagating, and unobservable. If u blocked v: suppress both directions and do not use their shared neighbors as evidence for each other. A slate visibly shrinking from 20 cards to 19 is itself a signal, so the absence must not be inferable.

6. Explanations are a separate disclosure surface. “You have 3 mutual connections” is an aggregate over a set the viewer may not be entitled to see. Rank on all evidence; explain only on evidence visible under both parties’ settings. If the visible set is empty, show a generic string or suppress the card, which happens on about 7% of otherwise-eligible impressions, a real recall cost.

7. Rate limits, because the surface is an oracle. Upload a million phone numbers and observe which produce suggestions and the product becomes a membership oracle. Cap import volume and frequency, require reciprocal or secondary evidence before an imported contact is surfaced, and never let the absence of a suggestion be a reliable negative.

The gate itself is a few lines, and the two subtle parts are that sources are tested as a mask and that the flagged-category branch thresholds on the sensitivity of the shared context, never on witness count:

justifying = the source bits set in prov, from a fixed list that EXCLUDES CONTACT_THEIRS
if blocked_either_way:                      drop
if not justifying:                          drop   # one-way evidence only
if SENSITIVE_CN set and len(justifying) < 2: drop  # a 2nd witness does NOT cure this
if CONTACT_CN_ONLY set and cn_count < 2 and len(justifying) < 2: drop  # a 2nd witness DOES cure this
otherwise:                                  admissible

Something has to set those flags, and that computation is the real control: at generation time, take the candidate’s common-neighbor set and flag it only when every witness is in a sensitive category (or, separately, when every witness is a common neighbor solely because it imported both sides). A single clean witness makes the candidate ordinary, because then the card can be explained without naming the flagged context. The guarantee is therefore narrower than “never”: no candidate is surfaced when every witness is flagged and there is no justifying source outside that set. A two-therapist practice is still dropped; a pair who also share one ordinary mutual connection is shown.

The ranker: model, label, and the training split

Every feature and the gate are now defined, so the ranker can be assembled.

The ranker is a gradient-boosted decision tree ensemble (GBDT): ~400 short trees, depth 8, each correcting the previous ones’ errors, summed. It is deliberately not a deep network, for three reasons. The features are already engineered (a few hundred dense, heterogeneous signals: there is no raw input for a network to learn a representation from, which is the regime where trees win). The strongest features are sharply non-linear and interaction-heavy (RA down-weights by 1/d; the activity prior gates multiplicatively), and trees split on exactly that without hand-built feature crosses. And it retrains daily on fresh edges, hours of ordinary compute for a tree ensemble. The one learned representation, node2vec, sits upstream as a generator, not inside the ranker.

Every feature is computed as of the candidate’s generation time and never later. A feature that peeked at the edge it is trying to predict is a temporal leak, and here it is catastrophic, not merely optimistic: the label is an edge and half the features are functions of edges, so a common-neighbor count computed after the fact already contains the very edge being predicted and teaches the model nothing.

The label is accept within 14 days of send, not “an edge ever formed.” Fourteen days, not forever, because an accept on day 30 is a positive the model could not have seen at send time; 14 days captures the bulk (accepts are front-loaded) and closes the loop fast enough to retrain daily. Impressions that never became a send are not negatives for this model. They belong to the send head, and conflating the two trains the accept head on the send head’s decisions.

As established earlier, that label exists only for pairs the system already chose to show, so it is manufactured by the previous version of this exact system. Left alone this is a ratchet: each generation narrows the region it has evidence about. The escape hatch is the two-part negative sample:

• Hard negatives: shown and declined. Real sent-population rows; they teach the current boundary.
• Easy negatives: random admissible 2-hop pairs, never shown to anyone. The only view the model gets of the space its predecessor ignored.

Negatives are over-represented at 20 per positive against a 59.5%-positive serving population, which deflates every predicted probability. Undo it with two steps.

First, de-sampling (Elkan’s correction): with a known kept-negative fraction, the map back to the serving prior is closed-form. At a training prior of 1-in-21 the correction factor is beta ≈ 29.4, and:

p_sampled = 1 / (1 + 20)                                       # training prior, 1-in-21
beta      = (0.595 / 0.405) · ((1 - p_sampled) / p_sampled)    # ≈ 29.4
desample(p) = beta·p / (beta·p - p + 1)                         # -> P(accept | sent)

De-sampling is monotone: it never reverses the order of two scores, so the ranking survives the raw scores uncorrected. Sort by raw score and you get the same list. Only the decision does not survive, because the 23% economic break-even is a statement about P(accept | sent), and the raw score is on the wrong prior until corrected.

Second, calibration. Elkan’s correction is exact only for negatives subsampled from the serving population, and half of these are not (the easy half is imported from the candidate-pair pool). So de-sampling removes the known, closed-form part and an isotonic map removes the rest: a staircase fitted from raw score to observed accept rate on held-out sent traffic, allowed to bend anywhere but never to go down, so it fixes the levels without touching the order. Calibration is the discipline of the calibration and drift chapter.

The split respects time because the graph does. Train on edges and sends before a cutoff T, evaluate on [T, T+14 days], compute every feature as of its own row’s timestamp. A random 80/20 shuffle leaks future edges into features, reads near 1.0 offline, and collapses online. That is why 0.945 is a temporal-split, de-sampled, 14-day-label number.

The load-bearing assumption of this section is the label one: that training on rows manufactured by the previous model, plus an un-selected easy-negative sample, plus a permanent holdout, is enough to bound the feedback loop. The honest position is that it bounds the loop instead of removing it. A second assumption is easier to check: that 14 days captures the bulk of accepts. If accepts were spread uniformly over 90 days, daily retraining would be training on noise.

Serving: precompute, invalidate, recompute lazily

The model is defined; what remains is when it runs. Both obvious answers fail.

Full online traverses the graph at request time, one adjacency fetch per connection, 89 at the median and 240 at the budgeted member. The fan-in latency argument from the feed-ranking chapter applies with force: the request waits for the slowest sub-request, not the average. At a 5 ms per-fetch p99 and independent fetches, the chance a whole request avoids the slow tail is 0.995 raised to the number of fetches:

median member,  89 fetches:   0.995^89   =  0.64
d = 240 member, 240 fetches:  0.995^240  =  0.30

So 36% of median requests and 70% of the d=240 member’s contain at least one p99 fetch, and latency is the max, not the mean. Plus 142-384 KB of adjacency per request, which at 20 k requests/s is 2.8-7.7 GB/s of random access. Not viable as the whole design.

Full nightly precompute stores the top candidates per member, so a request is a lookup. Storage is unremarkable (9.6 TB for active members across three replicas, 24 TB for everyone) and the scoring and I/O (960 TB read nightly, ~11 GB/s) are affordable. The problem is freshness:

time from the triggering graph event to the suggestion   accept-of-sent (diagnostic)
< 1 h                                                          24.1 %
1 - 24 h                                                       14.8 %
1 - 7 d                                                         9.2 %
> 7 d                                                           6.8 %

A suggestion is worth 3.5x more in the hour after you joined a company or added five colleagues than a week later, and a nightly job forfeits essentially all of it. The high-value moments (a job change, a contact import, an accepted invitation opening a new neighborhood) are exactly when the precomputed set is most wrong.

Invalidate eagerly, recompute lazily

The payoff separates two things people conflate: noticing a stored answer is stale (invalidation), and computing the new one. Invalidation is thousands of times cheaper.

A new edge (u, v) creates 2-paths for every neighbor of u and v, so it staleness-marks d_u + d_v ≈ 632 members:

new edges/day       100 M   ->  invalidations   6.3 x 10^10/day  =  731 k/s
surface loads/day    30 M   ->  recomputes             30 M/day  =  347/s   (~70 cores)

Invalidation turns a 731,000-per-second problem into a 347-per-second problem, and the entire trick is a dirty bitmap: one bit per member (“stale?”), a billion bits in 125 MB, on a single host. Then:

• Lazy path: on surface load, if the dirty bit is set, recompute; else serve the stored set with a light online re-rank against session context.
• Eager path, narrowly: on a high-value trigger (accepted invitation, job change, contact import, new group) recompute immediately without waiting for a visit (~8 M events/day, 93/s) because the next hour is worth 3.5x.
• Floor: recompute anything untouched for 30 days.

Invalidate eagerly, recompute lazily, escalate on a small set of high-value triggers: that answers almost every “precompute or online” question. The load-bearing assumption is the 2,100-fold gap between how often the stored answer goes stale (731 k/s) and how often anyone reads it (347/s), which comes from one fact: about 3% of members open a PYMK surface on a given day. If the product moved suggestions somewhere every member sees on every visit, the ratio would collapse and lazy recomputation would stop being an optimization.

Architecture

The whole system on one page. The ordering of three boxes carries the argument, not just the implementation: the provenance gate sits before scoring (a dropped candidate that reached the ranker would still have moved everything below it), and the economic gate sits after de-sampling (it is a decision about a calibrated probability, which the raw score is not).

flowchart TD
    subgraph OFF["Offline / streaming"]
        GE["Graph events<br/>new edge · job change<br/>contact import · block"]
        GE --> DIRTY["Dirty bitmap<br/>1 B bits · 125 MB<br/>731 k marks/s"]
        GE --> HV{"High-value<br/>trigger?"}
        HV -->|yes · 93/s| GEN
        GRAPH[("Adjacency store<br/>sharded by node")] --> GEN
        GEN["Candidate generation<br/>degree cap 1,000<br/>sample 200 · 30 k distinct"]
        GEN --> PRIV{"Provenance gate<br/>one-way evidence<br/>blocks · sensitive CN"}
        PRIV -->|drop| DROPPED(["Never scored"])
        PRIV -->|pass| CHEAP["Cheap score<br/>CN · RA · activity prior<br/>30 k -> 5 k"]
        CHEAP --> RANK["GBDT ranker<br/>graph + non-graph<br/>5 k scored"]
        RANK --> STORE[("Candidate store<br/>500/member · 16 B<br/>9.6 TB x 3")]
    end

    REQ(["PYMK surface load"]) --> CHK{"Dirty?"}
    CHK -->|yes · 347/s| GEN
    CHK -->|no| STORE
    STORE --> RR["Online re-rank<br/>session context<br/>recent views · fresh invites"]
    RR --> CAL["De-sample + calibrate<br/>Elkan β · isotonic<br/>raw score → P(accept | sent)"]
    CAL --> ACT["Activity prior<br/>× P(active in 28 d)<br/>multiplicative, not a feature"]
    ACT --> ECON["Economic gate<br/>drop p_accept < 0.23<br/>recipient cost priced in"]
    ECON --> SLATE["Slate assembly<br/>exposure cap 50/day<br/>diversity reservation<br/>dismissal suppression"]
    SLATE --> EXPL{"Visible explanation<br/>exists?"}
    EXPL -->|no| SUPPRESS(["Suppress card · 7 %"])
    EXPL -->|yes| OUT(["20 suggestions"])

    OUT --> LOG[("Impression · send · accept<br/>+ provenance of each")]
    LOG --> GEN

The offline half is everything that happens without a user waiting. A graph event marks the dirty bitmap and, if high-value, fires an immediate recompute. Generation reads the adjacency store (sharded by node, so one member’s neighbor list is one machine’s local read), produces ~30,000 candidates, passes them through the provenance gate (dropped candidates leave no trace downstream), cheap-scores 30,000 to 5,000, ranks those, and stores the survivors.

The request half checks the dirty bit and either regenerates or reads the store, then re-ranks online. De-sample + calibrate maps the raw score onto P(accept | sent). The activity prior then multiplies by P(active in 28 d), a separate box, not one of 200 features, because the graph features and the liveness signal point in opposite directions exactly in the tail that matters, so a near-zero liveness has to send the whole product to near zero. Only then does the economic gate drop anything below the 0.23 break-even. Slate assembly applies the exposure cap, diversity reservation, and dismissal suppression, and each surviving card is shown only if a visible explanation exists.

The last edge closes the loop: the impression/send/accept log flows straight back into generation as tomorrow’s training data. That arrow is why the labels are the previous system’s opinion.

Metrics

The phrase “accept rate” means three different things here, and they differ by up to a factor of twenty-five. The funnel is defined once and everything cites it.

Per 100 impressions of the shipped, fully-ranked system:

100 impressions
  ->  4.2  invitations sent           send rate         4.2 % of impressions
  ->  2.5  accepted                   accept-of-sent   59.5 % of sent
  ->  0.9  produce >= 1 interaction within 28 days
  ->  0.31 produce a sustained tie    >= 3 interactions in 90 days
  and 1.7  declined or ignored -- a cost imposed on someone else

One hundred impressions produce 0.31 relationships and 1.7 unwanted messages, and both belong on the dashboard. The three “accept rates”:

• send rate = P(send | impression) = 4.2%
• accept-of-sent = P(accept | sent) = 59.5%, the shipped ranker’s number
• accept-per-impression = send × accept-of-sent = 2.5%, the primary metric

The bucketed tables elsewhere (by common-neighbor count, by recipient last-active, by event lag) report a diagnostic accept rate on an unranked send, used to size one feature’s effect in isolation. Those sit below 59.5% on purpose; lifting accept-of-sent above the diagnostic baseline is exactly what the ranker is for.

Why optimizing acceptance produces low-value suggestions

The most natural metric fails in three ways that compound.

It selects for people who accept everything. An account with 24,000 connections and an accept-all policy sits at P(accept | sent) = 0.94 against a 0.60 baseline. Ranking on acceptance puts it near the top of every slate, growing its degree, raising its common-neighbor count with everyone, raising its rank further, the degree-concentration loop, entered through the metric.

It selects for the already-obvious. Your desk neighbor has 40 common connections and a 0.95 accept rate, and its incremental value (how much better off the world is because you showed it) is approximately zero, because that connection was happening anyway. Incrementality is not a label; it is a difference between two populations, which is why it can only come from the holdout.

It ignores the recipient. Price the externality. Let V be the value of an accepted connection and c ≈ 0.3 V the cost of an unwanted invitation. The expected value of showing a suggestion with acceptance probability p is zero when:

p·V - (1 - p)·c = 0   ->   p* = c / (V + c) = 0.3 / 1.3 = 0.23

Suggestions with predicted acceptance below about 23% are net negative once the recipient’s time is priced at all. This is the standard construction of a decision threshold from a cost matrix; the only unusual part is that the cost falls on someone who is not the user being served.

The metric stack

A single metric cannot carry a two-sided product, so the dashboard is tiered. Gini below is the Gini coefficient (0 if every member had equal degree, 1 if one member had all connections).

The value tier requires a holdout kept switched off permanently: suppress PYMK for 0.5% of members and difference the two populations on 90-day engagement, connections formed by other paths, and retention. Without it, “connections formed” is unattributable, because people form connections anyway. The holdout is also the only population never shaped by an earlier version of the model.

One thing makes this harder than a normal experiment: interference, a suppressed member’s connections are not suppressed, so the treatment leaks along the very graph edges you are trying to measure (A/B testing). Two partial answers: cluster-randomize on graph communities where you can, and read the number as a lower bound where you cannot.

Report rate by provenance is the cheapest audit: if contact-import suggestions carry a 0.31% “I do not know this person” rate against 0.05% for FoF ones, you have located a precision problem and a privacy problem in one column, without a single label.

The load-bearing assumption here is c ≈ 0.3 V, which produces the 23% threshold the serving path enforces on every request. It is at once the most consequential estimate in the chapter and the least directly measurable, inferred from decline and block behavior. Hold it as: the sign is certain, the value is not. At c = 0.1 V the threshold falls to 9%; at c = 0.5 V it rises to 33%; the design is unchanged in shape either way.

Failure modes

Five ways a system built exactly as specified still does the wrong thing. None are bugs. Two of them are the label feedback loop appearing in production.

The people the user is deliberately avoiding

Here is one candidate’s full feature row. The first four lines are graph features, all near the top; the next five all say the opposite:

common neighbors            118       99.7th percentile
Adamic-Adar                 12.4      99.9th percentile
resource allocation          0.94     99.9th percentile
personalized PageRank        0.031    rank 1 of 247,000 candidates
workplace overlap            none
messages exchanged, ever     0
last mutual interaction      3 years ago
U unfollowed V               14 months ago
impressions of V shown to U  9 in 6 weeks, 0 actions

V is a former spouse. The signature of your closest tie and the signature of the tie you most deliberately severed are the same, because the graph is the same in both cases. No better graph feature fixes it; the information is in the behavioral channel: explicit unfollow/mute/block, impressions without action (the under-used signal), and an anomalous absence of messages (118 common connections and zero messages is a strong negative).

Impression decay, where the chance of acting falls each time the same person reappears:

impression #      1      2      3      5      8     12
P(invite)      4.2 %  2.8 %  1.9 %  0.9 %  0.4 %  0.3 %

Crossed with the 23% threshold, the expected value of showing V again falls below the slot’s opportunity cost after roughly the fifth impression. The system should stop showing someone before the user has to dismiss them. Policy: suppress 90 days after 6 no-action impressions, 180 days after 2 dismissals, permanently after 3; treat unfollow/mute/block as hard, symmetric, permanent.

Dormant accounts

The largest single improvement in the design involves no graph modelling, and the graph features work against it. Split the candidate pool by when the candidate was last active:

last active       share of pool   accept-of-sent (diagnostic)
< 7 d                 34 %              41 %
8 - 30 d              21 %              22 %
31 - 180 d            24 %               6 %
> 180 d               21 %             1.1 %

Averaged over the whole pool the diagnostic accept-of-sent is 20.2%; restricted to last-active within 30 days it is 33.7%. An activity prior alone raises it from 20.2% to 33.7% (a 67% relative gain) with no graph modelling, which means forty-five percent of slots were being spent on people who will never see the invitation. (Stacked on the full feature set, the shipped ranker reaches 59.5%.)

It is easy to miss because graph features love dormant accounts: an account registered nine years ago has accumulated connections, so its degree, common-neighbor counts, and PPR mass are all high. The graph score and the liveness score point in opposite directions exactly where it matters, which is why P(active in 28 d) must be a multiplicative term, not one feature among two hundred the trees can average away.

Rich-get-richer

The recommender does not merely observe that some members are popular; it makes them more so:

flowchart TD
    D["Higher degree d"] --> CN["Higher CN with everyone"]
    CN --> RANK["Higher rank in more slates"]
    RANK --> IMP["More impressions"]
    IMP --> INV["More invitations, more accepts"]
    INV --> D

P(shown) increases in d while P(accept | shown) is roughly flat, so degree grows faster the more you already have, preferential attachment, except the recommender is the mechanism. It is worse than the usual feedback loop because the amplified quantity is a property of a person and is permanent: a member whose degree doubled keeps it. Simulating 12 months:

degree Gini, 12 months
un-normalized ranker                                0.61 -> 0.68
RA + Jaccard normalization                          0.61 -> 0.655
+ per-candidate exposure cap of 50 impressions/day  0.61 -> 0.63

The degree normalization chosen earlier for accuracy slows the loop as a side effect but does not stop it. A cap does: an equal share of exposure is 6e8 slots / 4e8 members = 1.5 impressions/member/day, so a cap at 50/day is 33x an equal share and still bounds the top account at 50 instead of a hundred thousand, generous enough to cost almost nothing in acceptance, tight enough to remove the runaway branch. Add a new-member reservation (2 of 20 slots for members with fewer than 10 connections), because the same loop runs in reverse at the bottom: a member with 3 connections generates almost no 2-paths.

Cross-group narrowing

A fairness harm can be located precisely, and not where most expect. Take a graph with two groups where 88% of edges are within-group and 12% cross. Walk a 2-path u -> w -> v from a u in group A; each edge is same-group with probability 0.88:

w in A, v in A   0.88 x 0.88  =  0.7744    same group
w in A, v in B   0.88 x 0.12  =  0.1056    cross
w in B, v in A   0.12 x 0.12  =  0.0144    same group
w in B, v in B   0.12 x 0.88  =  0.1056    cross
cross-group share of 2-paths  =  0.2112

The candidate pool is 21% cross-group while the graph is 12%, nearly twice as diverse, because one cross-group tie opens a door to that whole neighborhood. Then ranking takes it back:

cross-group share, by funnel stage
existing edges         12.0 %
2-hop candidate pool   21.1 %   <- the pool is diverse
top-20 slate            6.4 %   <- ranking removes it
invitations sent        5.6 %
accepted                5.1 %

The pool is twice as diverse as the graph and the output is less than half as diverse. The ranker is a filter that removes diversity the generator had already found, with no demographic feature anywhere, because every graph feature measures shared context and cross-group pairs have less of it by construction. And because the labels come from what the system showed, this narrowing writes itself into the next model’s training data: ranked-out cross-group pairs never generate a send or accept, so they look to the next model like territory with no evidence. If the network drives referrals and job discovery, the cross-group accept rate is an economic-mobility number in ranking metric’s clothing.

The fix, with its cost, is to reserve 3 of 20 slots for candidates with below-median shared context:

cross-group accepted share   5.1 %  ->  8.9 %    (nearly double)
accept-of-sent              59.5 %  ->  58.4 %   (-1.1 pp)

That is a 1.1-point cost in accept-of-sent to nearly double cross-group tie formation, a decision a human should make with the number in front of them, not one a loss function should make silently. The load-bearing assumption here is that a two-group graph with a single 88% within-group probability models homophily well enough to reason from. The digits would move under a richer model; the shape survives, a candidate pool strictly more diverse than the graph, for any within-group probability short of 1.

Summary of failure modes

Scale numbers

Every figure in one place.

members                          1 B registered, 400 M monthly active
edges                            1.6 x 10^11
mean degree                      316        median 89         cap 30,000
E[d^2]                           1.30 x 10^6
friendship-paradox mean          4,110      = E[d^2]/E[d]
2-hop candidate space            6.5 x 10^14 pairs  =  4,110 x the edge set
P(edge | candidate pair)         2.5 x 10^-4  (stock; the RETRIEVAL base rate)
P(accept | impression)           2.5 %        (the primary online metric)
P(accept | sent)                 59.5 %       (the RANKER's prior and its gate)

new edges                        100 M/day
invalidations                    6.3 x 10^10/day  =  731 k/s  (bitmap marks)
on-demand recomputes             30 M/day         =  347/s    (real work)
high-value eager recomputes      8 M/day          =  93/s

candidate store                  400 M x 500 x 16 B  =  3.2 TB, x3 =  9.6 TB
dirty bitmap                     1 B bits            =  125 MB
node2vec embeddings              1 B x 128 x fp16    =  256 GB
full PPR refresh                 1.34 x 10^13 hops   =  ~45 min on 5,000 cores
nightly graph I/O                960 TB               =  11 GB/s sustained

suggestion slots served          6 x 10^8/day
invitations sent                 25.2 M/day
declined or ignored              10.2 M/day

Two lines are the design. 4,110 x the edge set is why generation has to cap and sample. 731 k/s of marks versus 347/s of work is why serving is a dirty bitmap and not a pipeline.

Alternatives considered and rejected

Each with the reason it is appealing and the specific number that kills it.

Conclusion

The design turns on a handful of load-bearing facts.

• The heavy-tailed degree distribution makes a member’s 2-hop pool the friendship-paradox mean (4,110x) larger than the edge set, forces the intermediate-degree cap, and makes resource allocation the right down-weight, not the textbook Adamic-Adar.
• Generation is retrieval, ranking is classification. They live on different populations (10^-4 vs 59.5% positive), and confusing the two produces gates that reject everything. Generate with the degree cap; score without it.
• The training labels are manufactured by the previous version of the system. That closes a feedback loop, which is why the design needs easy negatives drawn from never-shown pairs and a permanent suppression holdout. The same loop reappears as degree concentration and cross-group narrowing.
• The product is two-sided. Pricing the recipient at c ≈ 0.3 V yields a 23% break-even the serving path enforces on every request.
• Privacy is a generation constraint, not an output filter, because ordering leaks and soft penalties become training data, and the sharpest failure is a correct prediction that must not be shown.
• Serving is invalidate-eagerly, recompute-lazily, because stale marks outnumber reads 2,100 to 1.

One line to remember: in connection recommendations the thing you rank is a person, so the heavy-tailed graph, the two-sided cost, and the third party whose evidence you hold decide the design long before the ranker does.

Further reading

• Feld, “Why Your Friends Have More Friends Than You Do” (1991). The friendship paradox.
• Adamic and Adar, “Friends and Neighbors on the Web” (2003). The log down-weight.
• Zhou, Lü, and Zhang, “Predicting Missing Links via Local Information” (2009). The resource-allocation index.
• Liben-Nowell and Kleinberg, “The Link Prediction Problem for Social Networks” (2007). A survey of graph link-prediction features.
• Grover and Leskovec, “node2vec: Scalable Feature Learning for Networks” (2016).
• Elkan, “The Foundations of Cost-Sensitive Learning” (2001). The de-sampling correction.