11 — People You May Know

People You May Know — abbreviated PYMK from here on — is the feature that suggests other members you might want to connect with. The worked example is a professional network with one billion registered members and 1.6 x 10^11 connections between them.

This design covers four things:

• Why one member can have twenty-five million plausible candidates, derived from the shape of the network alone, and how to cut that to twenty without discarding good candidates.
• 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.

The object being ranked is a person, and the hard parts follow from that. A bad connection 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 here comes from a combinatorial rule — walk the graph and enumerate everyone reachable — rather than from a retrieval index. This creates an arithmetic problem with no analogue in ml-system-design/10 or ml-system-design/06: the pool of plausible candidates for a single user can exceed twenty million and must be cut to twenty.

ml-system-design/01 gives the general framework for a machine-learning system design answer; the links out are for extra depth, not prerequisites.

The graph vocabulary, defined once

Everything here happens on a graph: a set of nodes (here, members) joined by edges (here, accepted connections). The terms below are used with these meanings throughout.

• Degree, written d, is how many connections a member has. d_w is node w’s degree.
• A neighbor of u is anyone u is directly connected to. N(u) is that set.
• The adjacency list of u is the stored list of u’s neighbors — the row you fetch from the database when you want to know who u knows. Reading it is called an adjacency fetch.
• A hub is a node with an unusually large degree: a recruiter, a celebrity, an account that accepts everything.
• A common neighbor of u and v is somebody connected to both of them — a mutual connection. CN(u, v) is how many there are.
• A second-degree connection of u, also called a 2-hop candidate or a friend-of-a-friend (FoF), is someone u is not connected to but who shares at least one common neighbor with u. Two edges away, hence “2-hop”.
• A 2-path is one concrete route u -> w -> v through a common neighbor w. A single second-degree candidate v may be reachable by many 2-paths, one per shared connection.
• Triadic closure, or “closing a triangle”, is the event this system is built around: two people who already share a common neighbor become connected to each other, completing a triangle of three edges.
• A random walk from u is a process that starts at u and repeatedly steps to a randomly chosen neighbor. It explores a graph without loading it all into memory, and two of the models below are built on it.

Two more terms recur outside the graph, and both appear in the next table.

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

A prior is the fraction of positives in a population. It always belongs to a named population, and this chapter carries three of them with very different priors, so a prior quoted without its population is not usable.

The models in this design, 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 shape of the network without ever being told what a good suggestion looks like,
• a cheap cut that throws away most of what the traversal found,
• one ranker that is trained on outcomes,
• a second scoring head for a different question,
• and two small corrections that exist because the ranker’s raw score is not on a usable scale.

The table below is the roster, stated before the arguments that justify it. Every row answers the same five questions: what the thing is, what goes in and comes out, where its training labels come from, the number that says it works, and whether it runs on the live request path (online) or on a schedule over logs (offline). Every cell links to its derivation later in the chapter.

Three things in that table matter most.

The generator is where privacy lives, not the ranker. Rows one and two decide which pairs ever come into existence, and The mechanisms argues that a candidate which 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 at all. Personalized PageRank and the activity prior are the top standalone AUC and the largest single shipped gain respectively, and neither has a training label. The learned ranker’s contribution is combining, not discovering.

The accept ranker’s label is manufactured by the previous version of the accept ranker. The next subsection unpacks this.

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 high enough to occupy one of twenty slots.
3. u chose to send.

Every one of those three is a decision made by the deployed system.

So the training set is not a sample of the space of possible connections. It is a sample of the connections the previous model liked, filtered again by what that model ranked highly, filtered again by what users did about it.

Three consequences follow.

The labels are missing not at random, and the missingness is caused by the model. Pairs the old ranker scored low have no label at all — not a negative, an absence. Train on the observed rows only and the new model inherits the old model’s blind spots as if they were facts about the world: whatever the old model never showed, the new model never learns to score, so it keeps not showing it. That is a closed loop, and it is the same loop as Rich get richer’s degree concentration and Demographic effects and the counterintuitive part’s cross-group narrowing, seen from the label side instead of the feature side.

Which is why the negatives are constructed rather than collected. The ranker model label and the training split that earns the auc samples half its negatives from candidates that were shown and declined — those teach the boundary the system currently sits on — and half from random admissible second-degree pairs that were never shown to anyone. The second half is the part that breaks the loop: it is the only place the model sees the region of the space the previous version chose to ignore.

And it is why the value tier of The metric stack requires a permanent holdout — a slice of members, 0.5%, for whom PYMK is switched off entirely. Inside the loop, “connections formed” is unattributable, because the system’s own history determines what could have been formed. The holdout is a population the loop never touched, and differencing against it is the only measurement in the chapter that is not conditioned on the system’s past decisions.

The complete statement of the 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

The interface of the whole system, in one table. The two rows to slow down on are Candidate funnel, which is the arithmetic problem the next section derives, and Base rate, which lists three different numbers that all get called “the accept rate” and differ from each other by a factor of up to 2,400.

Assumptions this chapter runs on, and the three that are load-bearing. Most of the figures above are stated by the interviewer and can move by a factor without changing an argument. Three cannot.

• Load-bearing: the degree distribution is heavy-tailed — a small share of members have enormous degree, so the variance of degree is far larger than its mean. Everything in Candidate generation the 2 hop explosion derived is this assumption compounding: it is why the candidate count is 4,110 times the edge count rather than 316 times, why skipping intermediates above degree 1,000 buys 23x, and why Adamic adar and the derivation of the down weight ships resource allocation instead of the textbook Adamic-Adar. On a graph with mild degree variance, half this chapter’s design decisions reverse.
• Load-bearing: the training labels come from the previous version of the system. Stated above and threaded through The ranker model label and the training split that earns the auc, The metric stack, Rich get richer and Demographic effects and the counterintuitive part. If labels arrived from a randomized policy, the easy-negative half of the training set and the permanent suppression holdout would both be optional. They are not.
• Load-bearing: an unwanted invitation has a real cost, taken here as c ≈ 0.3 V where V is the value of an accepted one. This is the assumption that makes the objective two-sided and produces the 23% break-even of Why optimizing acceptance produces low value suggestions. Set c = 0 and the economic gate vanishes, The people the user is deliberately avoiding’s impression-decay policy loses its justification, and the design collapses into “maximize accepts”. The value 0.3 is an estimate from decline-and-block rates; the fact that it is not zero is the load-bearing part.
• Not load-bearing, though the numbers are large: 1 B members, 400 M monthly active, 6 x 10^8 daily slots, and the 30,000 connection cap. They scale every cost figure and therefore the dollar value of every optimization, but no design decision flips if they are wrong by 30%.
• Assumed rather than derived, and worth flagging as such: that a reliable “sensitive category” flag exists for a member’s profile (The mechanisms). The chapter treats it as a lookup. In a real system it is itself a classifier with its own error rate, and its false negatives are exactly the The address book asymmetry which is the one to be able to derive disclosure.

1. What are we actually predicting?

The objective comes first, because the obvious answer is misleading: “does this person know that person” is close to worthless as a target, the right target contains four terms, and only some of its pieces can be learned from logs.

The obvious target is P(u knows v) — the probability that viewer u already knows candidate v in real life. It is wrong, and the ways it is wrong define the framing.

Here are seven concrete candidates for one viewer. Compare the first numeric column, P(knows), against the last: a P(knows) of 1.00 repeatedly sits next to a value of zero or worse.

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

The product target is three terms multiplied together, minus a fourth that is subtracted — and the third of the multiplied terms is where the value is:

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

Read that as four separate questions about one candidate. Will the viewer send? If they send, will the other person accept? If they accept, does anything come of it? And what does the invitation cost the recipient if they do not accept?

Three properties of that expression drive the rest of the chapter: only the first two terms are learnable, the subtracted term makes the problem two-sided, and “value” for a professional network is not engagement.

The first two terms are learnable from logs and the third is not. Sends and accepts are events, and an event that happened is written down. “Engagement created by the edge” is a counterfactual — a statement about a world that did not happen. You would need to know what the viewer’s next 90 days looked like without the edge, and you cannot, because the edge exists. There is no per-pair label for it, ever. It is estimable only as a difference between two populations, one of which has the feature switched off — a holdout (The metric stack) — which means it can inform the weights you choose and can never be a training target.

The subtracted term makes this two-sided. A suggestion imposes a cost on someone who did not ask for it. At platform scale that cost is not rounding error:

6 x 10^8 suggestion slots/day  ->  4.2 % send rate  ->  25.2 M invitations/day
                                   59.5 % accept    ->  10.2 M declined or ignored

Ten million people per day receive an invitation they do not act on. A ranker that counts only accepts treats those as free. (These two numbers, and every “accept rate” in the chapter, come from the one funnel defined in The funnel defined once cited everywhere.)

And “value” for a professional network is not the same as engagement. If connections drive referrals, job discovery, and information flow, then the distribution of who gets connected is an economic outcome, not a product metric. Demographic effects and the counterintuitive part shows the system moves that distribution measurably in the wrong direction without any demographic feature being present anywhere in it.

2. Candidate generation: the 2-hop explosion, derived

How many people could plausibly be suggested to a single member, and what does that number force the system to do? The obvious estimate is badly wrong, the true size is far larger, and the fix — refusing to walk through popular people — costs almost nothing in quality.

2.1 Why friends-of-friends dominates

Empirically, 60-80% of new edges close a triangle: u connects to v and they already had a neighbor in common. That single fact makes the 2-hop neighborhood — everyone reachable in exactly two steps — the candidate source, and everything else (contact imports, shared workplace, learned embeddings) a supplement that fills the remainder.

The trouble is its size: the 2-hop neighborhood of an active member runs not to thousands of people but to tens of millions, and the next two subsections derive why the naive d^2 count understates it and what that forces on the generator.

2.2 The friendship paradox is why d^2 is the wrong estimate

The true size of a member’s second-degree neighborhood turns on one fact about how sampling works on a graph.

The naive estimate of a 2-hop neighborhood is d^2 — your d connections times their d connections. It is badly low, and the reason is a fact about sampling:

When you reach a node by traversing 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].

Two pieces of notation first. E[d] is the expected value, the plain average of degree across all members. Var(d) is the variance, the average squared distance from that mean — a measure of how spread out the degrees are — and sd(d), the standard deviation, is its square root.

The identity above has a name: the friendship paradox. Your friends have more friends than you do, on average, and the size of the excess is exactly Var(d)/E[d].

The reason is not that you are unpopular. It is that a popular person is, by definition, somebody’s friend more often. So popular people are over-represented among the people you arrive at by following an edge.

To put numbers on that, measure a real degree distribution in buckets rather than assuming a shape for it.

Each row of the table is one band of connection counts. Share of nodes is the fraction of members in that band, Mean d is their average degree, and Mean d^2 is the average of their squared degree, which the friendship-paradox identity needs. The last row dominates: 0.6% of members, with a mean d^2 of 1.6e8 — thirty times the row above it, and 320,000 times the top row.

Now average those columns across the whole population. 0.42(18) below means “42% of nodes, each contributing 18” — a share times a bucket mean, summed over the five rows. That is all an expected value is: a weighted average.

E[d]    =  0.42(18) + 0.31(110) + 0.21(450) + 0.054(2100) + 0.006(11000)  =  316
E[d^2]  =  0.42(5e2) + 0.31(1.5e4) + 0.21(2.4e5) + 0.054(5.2e6) + 0.006(1.6e8)
        =  210 + 4,650 + 50,400 + 280,800 + 960,000  =  1.30e6

Var(d)  =  1.30e6 - 316^2  =  1.20e6        sd(d) = 1,094

expected degree of a random neighbor  =  1.30e6 / 316  =  4,110

the MEDIAN is a different question, and the same table answers it: 42 % of
nodes sit below d = 50 and 42 + 31 = 73 % below d = 200, so the 50th
percentile lands inside the 50-200 bucket, (0.50 - 0.42)/0.31 = 25.8 % of
the way through it:

median d  =  50 + 0.258 x 150  =  89

Mean 316, median 89. The gap is the tail again, and the two are not interchangeable: the mean is what the friendship-paradox identity is built from and the median is what a typical request costs.

Your average connection has 4,110 connections, while the average member has 316. That is a factor of 13, and it is not a quirk of this table — it is Var/mean, and social degree distributions have enormous variance.

Now the 2-hop counts, in two steps and for three different members.

Step one: multiply the member’s own degree by 4,110, the expected degree of each neighbor. That gives the number of 2-paths — routes u -> w -> v, not people.

Step two: divide by the average number of 2-paths that land on the same person, because a candidate reachable through four shared connections is still one candidate. That divisor is measured at about 4 for a typical member and about 5 at the connection cap, where the neighborhoods overlap more.

median member, d = 89:
    raw 2-paths     89 x 4,110    =  366,000
    distinct nodes  / ~4 paths each  =  ~91,000

the member the generation budget is sized for, d = 240 (about the 74th
percentile of degree, not the median):
    raw 2-paths     240 x 4,110   =  987,000
    distinct nodes  / ~4 paths each  =  ~250,000

member at the connection cap, d = 30,000:
    raw 2-paths     30,000 x 4,110  =  1.23 x 10^8
    distinct nodes  / ~5             =  ~25,000,000

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 and are not a pathological construction — recruiters, salespeople, and public figures sit at the cap.

2.3 The global number, and an identity worth knowing

Scaling the per-member number up to the whole platform gives an identity that converts one quantity you already have into another.

Count the candidate pairs the whole platform can produce by triangle closure. Do it by walking over every member w in turn and asking how many pairs that member alone puts on the table.

w puts one candidate pair on the table for every two of their neighbors, so w contributes C(d_w, 2) — “d_w choose 2”, the number of ways to pick two things from d_w. That equals d_w(d_w - 1)/2, which for large d_w is close enough to d_w^2 / 2. Sum it over all N members and the average of d_w^2 is exactly E[d^2], so the total is N · E[d^2] / 2:

candidate pairs  =  sum_w  C(d_w, 2)  ~=  N · E[d^2] / 2  =  1e9 x 1.30e6 / 2  =  6.5 x 10^14
existing edges   =  N · E[d] / 2      =  1e9 x 316 / 2    =  1.6 x 10^11

ratio  =  E[d^2] / E[d]  =  4,110

The ratio of the 2-hop candidate space to the edge set is exactly the friendship-paradox mean. The same quantity that makes your friends more popular than you also gives how many times larger the candidate space is than the graph.

Now the base rate: out of all those candidate pairs, what share are real connections?

There are two honest ways to ask that, and they are not the same question. A stock counts what exists right now — the edges already in the graph. A flow counts what arrives per unit time — the edges formed today. Both are computed below so the difference is visible:

STOCK   existing edges / candidate pairs
        1.6e11 / 6.5e14  =  2.46 x 10^-4          pairs that ARE already edges

FLOW    new edges / candidate pairs
        1.0e8 per day / 6.5e14  =  1.5 x 10^-7 / day
        over a year              =  5.6 x 10^-5   pairs that BECOME edges

Both land on the order of 10^-4, which is all this number is ever asked to do. Write it as P(edge | candidate pair) ~ 10^-4 and keep the conditioning visible, because the chapter carries three different populations and this is only the first of them. About one candidate pair in ten thousand is a real connection, which makes generation an extreme-imbalance retrieval problem — one where the positives are so rare that finding them at all is the hard part — and is why What that forces capping and sampling has to cut before anything is scored.

It is not the accept ranker’s training prior, and confusing the two is a costly mistake. 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% (The funnel defined once cited everywhere) — about 2,400 times higher. The ranker model label and the training split that earns the auc is where the difference decides how the training set is built and de-sampled, and Why optimizing acceptance produces low value suggestions’s 23% gate is stated in the second population’s units, never the first’s.

2.4 What that forces: capping and sampling

The arithmetic now becomes the generator’s actual rules, and the cheapest saving also costs the least quality.

E[d^2] is dominated by the tail: the average of d^2 is driven almost entirely by the few members with huge degree, because squaring exaggerates them. From the table, the top 0.6% of nodes contribute 960,000 / 1,296,060 = 74% of E[d^2]. So capping the degree of the intermediate node — refusing to walk through anyone with more than D connections when enumerating 2-paths — is not a heuristic, it is the whole cost model:

cap intermediates at D = 1,000 by SKIPPING them.  The rule the generator runs
is `if d_w > 1,000: continue` -- the hub is not walked at all, so it puts no
2-paths on the table:

E[d^2] enumerated  =  210 + 4,650 + 50,400                =  5.53e4
E[d^2] skipped     =  0.054(5.2e6) + 0.006(1.6e8)
                   =  280,800 + 960,000                   =  1.24e6

reduction  =  1,296,060 / 55,260  =  23.5 x fewer candidate pairs
work removed  =  1 - 55,260/1,296,060  =  95.7 %

A 23x reduction in the entire candidate space by skipping 6% of nodes.

Skipping versus min-capping, which differ by 2x

A gentler rule prices out differently. Quote the one that matches the code.

Min-capping means: walk the hub anyway, but pretend its degree is 1,000 — count min(d_w, 1000)^2 instead of d_w^2. The two heavy buckets then contribute 0.054 x 1,000,000 = 54,000 and 0.006 x 1,000,000 = 6,000 instead of 280,800 and 960,000:

min-cap E[d^2]  =  210 + 4,650 + 50,400 + 54,000 + 6,000  =  1.15e5
reduction       =  1,296,060 / 115,260                    =  11.2 x

That is the rule you would price if you wanted the hub’s candidates at a discount rather than not at all. This design skips, so the saving is 23.5x and not 11.2x. The two are far enough apart that quoting one while shipping the other gives a number nobody can reproduce from the code.

Why the cap costs almost no quality

Skipping hubs throws away candidates. It is worth almost nothing, and Adamic adar and the derivation of the down weight derives why: a common neighbor of degree 2,100 carries about 1/2,100 the evidence of a common neighbor of degree 1, under any statistically defensible weighting.

The nodes that generate the most candidates are the nodes whose candidates are worth the least.

The generation budget

The table below is the full per-user budget, from the viewer’s own connections down to the twenty suggestions shown. The two right-hand columns show the count rising to 100,000 and then falling to 20.

Three abbreviations appear in it and are derived in Graph features: CN is the common-neighbor count, RA is resource allocation, a version of that count where each shared connection is weighted by one over its degree, and GBDT is the gradient-boosted decision tree ranker described in The ranker model label and the training split that earns the auc. A slate is the final list of suggestions shown in one impression.

The same budget as a funnel, for the d = 240 member:

flowchart TD
    A["Viewer's own neighbors<br/>240 sampled"] --> 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/>CN, RA, activity prior<br/>5,000"]
    E --> F["GBDT ranker<br/>graph + non-graph features<br/>5,000 scored"]
    F --> G["Slate<br/>diversity, caps, privacy<br/>20 shown"]

Why is the budget column sized at d = 240 rather than at the median d = 89 derived in The friendship paradox is why d2 is the wrong estimate? Because a generation budget has to cover well over half the traffic it will meet. The median member’s own 2-hop neighbourhood is ~91,000 people and sits comfortably inside a budget sized for 240.

Five thousand is where the exhaustive-scan budget lands, and the cheap-score cut from 30,000 to 5,000 is doing more work for cost than the ranker is doing for quality.

That is the two-stage pattern — a cheap model that narrows a huge pool, then an expensive model that orders what survives — from ml-system-design/01, with the usual retrieval stage replaced by a graph traversal.

Assumptions in this section, and the load-bearing one. The bucketed degree table is a measurement, so what is assumed around it is narrower than it looks.

The load-bearing assumption is that degree variance is enormous relative to the mean — Var(d) = 1.20e6 against E[d] = 316. Every number downstream is that one fact compounding: it is why a neighbor’s expected degree is 4,110 rather than 316, why the global candidate space is 4,110 times the edge set, and why skipping 6% of nodes removes 96% of the work. On a graph where degree were tightly clustered around its mean, d^2 would be roughly right, the cap would save almost nothing, and this section would be two paragraphs.

Two secondary assumptions carry much less. The deduplication factors (~4 paths per distinct candidate at median degree, ~5 at the cap) move the candidate counts but not the design. And the cap value D = 1,000 is a dial: its existence is forced by the tail, but its value trades recall against cost smoothly and could be 500 or 2,000 without changing a conclusion.

3. Graph features

A feature is one number computed about a candidate pair and handed to the model. The graph features are what you can measure about u and v from the shape of the network around them: four families, a derived weighting that separates the good ones from the textbook one, and what each costs and what each is worth.

3.1 Common neighbors, and why raw counting fails

The simplest graph feature breaks in one specific way.

CN(u, v) = |N(u) intersect N(v)| — the number of connections u and v share, written as the size of the intersection of their two neighbor sets. It is fast and 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(u,v1)  =  3        CN(u,v2)  =  3        identical

The first pair shares three people from a tight cluster — a team, a class, a family. The second pair both follow three well-known accounts, which they share with several million other people. Common-neighbor counting says these are the same amount of evidence.

3.2 Adamic-Adar, and the derivation of the down-weight

The fix for Common neighbors and why raw counting fails’s failure is to weight each shared connection instead of counting it. The real question is how strong that weighting should be — and the standard answer gets it wrong by about seven orders of magnitude.

Adamic-Adar (AA) — named for Lada Adamic and Eytan Adar, who proposed it — weights each shared neighbor by one over the logarithm of that neighbor’s degree, so that a shared connection with few connections of their own counts for more than a celebrity does:

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

The original argument is an information one.

Adamic and Adar were matching web pages by shared features. They weighted a shared feature by its rarity: a feature that appears on almost every page is nearly uninformative, one that appears on three pages is decisive. The natural rarity weight is inverse frequency, softened by a log so the weight falls off gently rather than collapsing.

That is the same shape as IDF, inverse document frequency — the standard trick in text search for making common words like “the” count for less than rare ones. Translate “feature” to “common neighbor” and “frequency” to “degree”, and you have AA.

What the statistically correct weight would be

The log weight is a reasonable instinct. It is not a derivation. Deriving the right weight needs a null model: a randomized version of the graph that keeps the properties you are not interested in and destroys the ones you are, so you can ask how surprising a real observation is.

The null model to use here is the configuration model, and the block below derives it in three steps: the probability of an edge under the null, the expected number of common neighbors that follows, and the down-weight that implies.

Under a configuration model — cut every edge in half and rewire the halves at random, which preserves every node’s degree exactly while destroying all real structure — the probability that node w is a neighbor of u is d_u · d_w / 2m, where m is the edge count and 2m is therefore the total number of edge-ends in the graph. So the expected number of common neighbors of u and v under the null is

E[CN(u,v)]  =  sum_w (d_u d_w / 2m)(d_v d_w / 2m)  =  (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 — the logarithm of how much more likely something is than its alternative — divides what you observed by what you expected under the null, so the evidence a common neighbor provides should be down-weighted by 1 / d_w^2.

Now put the four weightings side by side. RA is resource allocation, the third of them: weight each shared neighbor by 1/d_w rather than 1/log(d_w), on the picture that a shared connection has one unit of attention to divide among all their connections, so the amount that flows to you shrinks in proportion to how many of them there are.

Each row of the table is one common neighbor of degree d_w, and each column is how much evidence that neighbor is worth under one weighting. The AA and RA columns are the raw weights, 1/ln d_w and 1/d_w. The last column is 1/d_w^2 rescaled so the d = 5 row reads 1.00, since only its shape matters. The columns are not comparable to each other — only the bottom row is. That row is each column’s own ratio between its d = 5 entry and its d = 30,000 entry — how much discount that weighting applies 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 applies 6,000x, and the configuration-model null says 36 million. The log is a very gentle correction — it is an IDF, not a null-model correction, and it was never claimed to be one.

Back to the worked pair from Common neighbors and why raw counting fails, where counting called both pairs a 3. Score them under AA and under RA and compare the two ratios at the right:

AA(u,v1)  =  1/ln14 + 1/ln22 + 1/ln31       =  0.379 + 0.324 + 0.291  =  0.994
AA(u,v2)  =  1/ln8400 + 1/ln12000 + 1/ln26000 = 0.111 + 0.106 + 0.098  =  0.315
                                                              ratio      3.2 x

RA(u,v1)  =  1/14 + 1/22 + 1/31             =  0.0714 + 0.0455 + 0.0323  =  0.149
RA(u,v2)  =  1/8400 + 1/12000 + 1/26000     =  1.19e-4 + 8.3e-5 + 3.8e-5  =  2.4e-4
                                                              ratio      619 x

Identical to common-neighbor counting, 3.2x apart under Adamic-Adar, 619x apart under resource allocation. The correct answer is closer to the last one, 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.

One reconciliation: generate with the cap, score without it

Two rules in this chapter appear to contradict each other, and the resolution matters.

What that forces capping and sampling caps intermediates at degree 1,000. All three of v2’s common neighbors are above it, so the 2-hop generator never proposes v2 at all.

That is not an inconsistency, it is the cap working. A pair whose only witnesses — the common neighbors that constitute the evidence for suggesting it — are hubs is worth 2.4e-4 of resource allocation against v1’s 0.149. Paying to enumerate it is exactly the hub tail of E[d^2] that What that forces capping and sampling declines to pay.

But the cap is a generation rule, not a feature definition, and the two must not share code. v2 can still arrive from another generator — an embedding neighbour, a shared workplace, a contact import. When it does, its graph features have to be computed over every shared neighbour, 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 rather than like a weak match.

Generate with the cap, score without it.

3.3 Jaccard corrects a different thing

The next feature looks like a competitor to Adamic-Adar but is not one. It corrects a bias the previous two leave untouched, which is why you ship both.

The Jaccard coefficient asks what share of the two people’s combined social worlds is shared, rather than how many shared connections there are in absolute terms: the size of the overlap divided by the size of the union.

J(u, v)  =  |N(u) intersect N(v)| / |N(u) union N(v)|

AA and RA normalize by the degree of the intermediate — the shared connection in the middle of the 2-path. Jaccard normalizes by the degrees of the endpoints — u and v themselves. They fix different biases and you want both.

Here is a case where they disagree. One viewer, two candidates: the first shares more connections in absolute terms, the second shares more as a share of their own small world.

u has 500 connections.

v1:  CN = 8,  |N(v1)| = 450   ->  J = 8 / (500 + 450 - 8)  =  8/942  =  0.00849
v2:  CN = 5,  |N(v2)| =  30   ->  J = 5 / (500 +  30 - 5)  =  5/525  =  0.00952

Counting prefers v1; Jaccard prefers v2, because five of v2’s thirty connections overlapping with you is a much larger share of v2’s world than eight of four hundred and fifty. Which is right depends on the objective: v2 is more likely a genuine close tie, v1 more likely a hub you brush against. Feed both and let the model decide — but know that Jaccard is not a refinement of AA, it is orthogonal to it: the two measure genuinely different things, so knowing one tells you little about the other and the model gains from having both.

3.4 Personalized PageRank, and why it is cheaper than it sounds

One graph feature sees past two hops. The common objection to it — that it must be far too expensive — is wrong; its real limitation is elsewhere.

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.

Formally it is the stationary distribution of that walk — the long-run share of steps spent at each node, once the walk has been running long enough to forget where it began. Because the walk keeps restarting at u, it stays in u’s vicinity, which is what makes it personalized rather than a global measure of importance.

Its value: it sees paths of every length and rewards many short paths rather than one. That captures “we are embedded in the same dense region”, which no 2-hop statistic can express.

The objection is cost. Computing that stationary distribution exactly means solving a system of linear equations with one unknown per node — a billion of them, per user, which is infeasible. So do not solve the linear system; sample it. Run the walk many times and count where it lands. That is a Monte Carlo estimate: approximate a quantity you cannot compute by averaging over random trials of the process that defines it.

Now price it for the whole platform. The chain below goes from walks per member, to hops per member, to hops for the entire graph, to wall-clock time on a cluster:

R = 2,000 walks per source, restart alpha = 0.15
expected walk length  =  1/alpha  =  6.7 hops
hops per user         =  2,000 x 6.7  =  13,400
full refresh          =  1e9 x 13,400  =  1.34 x 10^13 hops

at ~1e6 hops/s/core (adjacency reads are cache-hostile)
                      =  1.34 x 10^7 core-seconds  =  3,722 core-hours
on 5,000 cores        =  ~45 minutes

Each walk restarts with probability alpha at every step, so its length before restarting averages 1/alpha, which is where the 6.7 comes from. Adjacency reads are cache-hostile — each hop lands on an unpredictable node, so the processor’s cache never holds the row it is about to need — which is why the throughput assumption is a modest one million hops per second per core.

A full-graph personalized PageRank refresh is under an hour on a mid-sized cluster.

The catch is precision, not cost. A node visited 3 times out of 2,000 walks has an estimate whose relative standard error — the typical size of the estimate’s own error, expressed as a fraction of the estimate — is 1/sqrt(3) = 58%. Counting random events gives an error that grows like the square root of the count while the count itself grows linearly, so rare nodes are estimated terribly.

So Monte Carlo PPR is excellent for generating the top few thousand candidates and poor as a fine-grained ranking feature. Use the visit count as a coarse bucketed feature — say, “visited 0 times / 1-5 / 6-50 / more” — not as a continuous score. Do not try to distinguish rank 400 from rank 500 with it.

3.5 Embeddings, and what a low-rank factorization cannot keep

Now price the common answer — learn a vector for every member. The arithmetic assigns it a specific and limited job: embeddings are a generator, not a decider, and the reason is a one-line counting argument.

An embedding is a fixed-length list of numbers assigned to an object so that similar objects get nearby lists. Here it is one vector of 128 numbers per member, learned so that members who sit near each other in the graph get similar vectors.

Two families produce them.

node2vec-style methods run random walks over the graph, treat each walk as if it were a sentence and each node as a word, and fit a skip-gram model — the word-embedding recipe that learns a vector for each word by predicting which other words appear near it. Training it requires negative sampling on a graph: for every genuine (node, nearby-node) pair the walk produced, draw a handful of random nodes as counter-examples and push their vectors apart. You need that because scoring against every one of a billion nodes at every step is impossible.

GNN methods — graph neural networks — instead compute each node’s vector by repeatedly aggregating its neighbors’ feature vectors, a procedure called message passing.

Both give you a vector per node, and cheap ANN retrieval over it: approximate nearest neighbor search, an index that finds the closest vectors to a query without comparing against all of them, trading a little recall for orders of magnitude of speed.

The counting argument: 0.8 parameters per edge

Now price the representation. fp16 is half-precision floating point, two bytes per number. The block below computes the storage, then divides the number of learned numbers by the number of connections those numbers have to describe:

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

parameters per edge  =  1.28e11 / 1.6e11  =  0.8

Less than one parameter per edge. There are fewer learned numbers in the whole embedding table than there are connections it has to describe, so the embedding must compress. It cannot store the graph. It can only summarize it.

That kind of summary is a low-rank factorization: reconstructing a huge relationship table from the product of two much smaller ones, which by construction can only express patterns that repeat. What it keeps is the smooth, global structure — communities, industries, geographies. What it discards is the idiosyncratic single path.

The thing People You May Know has to decide is exactly the fine structure: not “are these two people in the same community” (they are, along with four million others) but “is there a specific reason these two particular people should be connected.”

Why 128 dimensions, and not 64 or 512

The dimension is chosen where recall@k for candidate generation plateaus, not where a link-classification loss bottoms out. Recall@k is the share of the candidates you wanted that appear in the top k the index returns, and it is the only thing a retrieval stage is judged on — which is the embedding’s only job here (The comparison with cost).

The smooth structure the vector has to hold is a few thousand communities crossed with industry, geography, and seniority. Below about 128 dimensions those collide in the ANN index, and recall drops for the hard ~15% of candidates that have no 2-hop path. Above 128, recall is flat while the store grows linearly: doubling to 256 dimensions doubles the store to 512 GB and raises the ratio to 1.6 parameters per edge for no measurable recall gain (The ranker model label and the training split that earns the auc prices all three dimensions in code).

So 128 is the smallest dimension that holds the smooth structure, and no more. That is the right target precisely because the fine structure is not recoverable at any feasible dimension — paying for more dimensions is waste, not headroom.

So the correct role is retrieval, not decision. Embeddings generate the candidates friend-of-a-friend traversal cannot reach — same field, same alumni cohort, similar behavior, zero common neighbors. That is a genuinely valuable ~15% of the pool and it has no other source. Then the sparse path features decide: common neighbors, resource allocation, personalized PageRank, 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.

3.6 The comparison, with cost

Every graph feature, in one table, with what it costs and what it is worth. The next point of quality does not come from a fifth graph feature.

Freshness is how stale the feature can be before it stops being useful — how often the pipeline that produces it has to run. Standalone AUC is the quality of that feature used on its own, as the only input to the decision.

The six individual features span 0.78 to 0.88, all of them together reach 0.91, and the largest jump is the last row.

Adding a fifth graph feature moves AUC by thousandths; 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 they are correlated at 0.7-0.9 with each other. Spend the effort on Beyond the graph and the privacy constraint, and on the parts of Beyond the graph and the privacy constraint you are allowed to use.

The “node2vec cosine” row means the cosine similarity between two members’ embedding vectors: the cosine of the angle between them, which runs from 1 for identical directions to 0 for unrelated ones and is the standard way to compare embeddings.

Every AUC in this table is a temporal-split, negative-de-sampled, 14-day-label number — temporal split meaning train on the past and test on the future rather than shuffling rows at random, de-sampled meaning the deliberate over-representation of positives in training has been corrected out — and The ranker model label and the training split that earns the auc is where both are derived. Quoted without that protocol it is not comparable to the online accept-of-sent rate (The funnel defined once cited everywhere) it is meant to predict, and a random split would read near 1.0 offline and collapse in production.

Assumptions in this section, and the load-bearing one. The AUC column is measured, so the assumption is not that the numbers are right but that they are comparable — every one of them comes off the same protocol, and that is stated rather than derived.

The load-bearing assumption is different and sits under the whole section: that the graph is a fair record of who knows whom. Every feature here reads structure and infers intent from it. The people the user is deliberately avoiding is the case where that fails completely — a tie somebody deliberately severed leaves exactly the same structural fingerprint as their closest tie. No graph feature can be built that fixes it, because the assumption, not the feature, is what broke.

Secondary and much weaker: the 0.7-0.9 correlation among the graph features, which explains why a fifth one is not worth building but changes no design if it were 0.5.

The code, and what it is there to prove

The block below is this section’s two rules as running code, plus every number Candidate generation the 2 hop explosion derived and Adamic adar and the derivation of the down weight claimed, recomputed rather than asserted.

The two functions differ deliberately. two_hop_scores generates and applies the degree cap. pair_features scores one pair and does not. The assertions at the bottom check what separates them: v2 never appears in the generator’s output, yet pair_features still scores it correctly when it arrives from somewhere else.

import math
from collections import defaultdict

MAX_INTERMEDIATE_DEGREE = 1_000   # 95.7 % of E[d^2] lives above this
SAMPLE_PER_INTERMEDIATE = 200

def two_hop_scores(u, neighbors, degree, blocked=frozenset()):
    """GENERATE 2-hop candidates with degree capping, scoring CN / AA / RA.

    `neighbors(x)` returns x's adjacency; `degree(x)` its degree. The cap is
    the cost model, not a heuristic: skipping the 6 % of nodes above 1,000
    removes ~96 % of the candidate pairs and, by the null-model argument
    above, discards evidence worth ~1/d_w^2 of a low-degree neighbor's.

    **The cap is a generation rule, not a feature definition.** A pair whose
    only common neighbors are hubs is a pair this function deliberately never
    proposes -- section 3.2's `v2`, three common neighbors of degree 8,400 /
    12,000 / 26,000, is exactly that pair, and it does not appear in the
    output at all. When such a pair arrives from another generator
    (embedding, workplace, contact import), score it with `pair_features`,
    which is uncapped: that is where AA and RA do the down-weighting section
    3.2 is about, and where the worked example is reproducible.
    """
    own = set(neighbors(u))
    acc = defaultdict(lambda: [0, 0.0, 0.0])          # cn, adamic_adar, resource_alloc

    for w in own:
        d_w = degree(w)
        if d_w > MAX_INTERMEDIATE_DEGREE:
            continue
        w_aa = 1.0 / math.log(d_w) if d_w > 1 else 1.0
        w_ra = 1.0 / d_w
        for v in list(neighbors(w))[:SAMPLE_PER_INTERMEDIATE]:
            if v == u or v in own or v in blocked:
                continue
            slot = acc[v]
            slot[0] += 1
            slot[1] += w_aa
            slot[2] += w_ra
    return acc

def pair_features(u, v, neighbors, degree):
    """CN / AA / RA for ONE pair, over the FULL common-neighbor set.

    No degree cap: a candidate that has reached scoring has already paid its
    generation cost, and dropping its hub common neighbors here would throw
    the evidence away rather than down-weight it -- the opposite of section
    3.2's argument. RA does the down-weighting, by a factor of 619 on the
    worked pair below.
    """
    shared = set(neighbors(u)) & set(neighbors(v))
    cn = len(shared)
    aa = sum(1.0 / math.log(degree(w)) if degree(w) > 1 else 1.0 for w in shared)
    ra = sum(1.0 / degree(w) for w in shared)
    return cn, aa, ra

def jaccard(cn, deg_u, deg_v):
    """Endpoint-degree normalization -- orthogonal to AA/RA, not a refinement."""
    union = deg_u + deg_v - cn
    return cn / union if union else 0.0

# --- section 3.2's worked pair, executed --------------------------------
_DEG = {"u": 240, "v1": 60, "v2": 90,
        "a": 14, "b": 22, "c": 31,              # v1's common neighbors
        "x": 8400, "y": 12000, "z": 26000}      # v2's common neighbors
_ADJ = {"u": ["a", "b", "c", "x", "y", "z"],
        "v1": ["a", "b", "c"], "v2": ["x", "y", "z"],
        "a": ["u", "v1"], "b": ["u", "v1"], "c": ["u", "v1"],
        "x": ["u", "v2"], "y": ["u", "v2"], "z": ["u", "v2"]}

def _nb(n):
    return _ADJ[n]

def _dg(n):
    return _DEG[n]

print("pair    CN     AA      RA")
for _v in ("v1", "v2"):
    _c, _a, _r = pair_features("u", _v, _nb, _dg)
    print("  %-4s  %2d   %.3f   %.5f" % (_v, _c, _a, _r))

_cn1, _aa1, _ra1 = pair_features("u", "v1", _nb, _dg)
_cn2, _aa2, _ra2 = pair_features("u", "v2", _nb, _dg)
assert _cn1 == _cn2 == 3                         # counting cannot tell them apart
assert abs(_aa1 - 0.994) < 1e-3 and abs(_aa2 - 0.315) < 1e-3
assert abs(_ra1 - 0.149) < 5e-4 and abs(_ra2 - 2.4e-4) < 5e-6
assert abs(_aa1 / _aa2 - 3.2) < 0.06             # AA is an IDF: 3.2x
assert abs(_ra1 / _ra2 - 619) < 1.0              # RA is the down-weight: 619x

print("exact ratios: AA %.2fx, RA %.0fx  (3.2x and 619x from the rounded terms)"
      % (_aa1 / _aa2, _ra1 / _ra2))

# the cap is a GENERATION control: v1 is proposed, v2 never is.
_acc = two_hop_scores("u", _nb, _dg)
assert "v1" in _acc and "v2" not in _acc
assert _acc["v1"][0] == 3 and abs(_acc["v1"][2] - 0.149) < 5e-4

# --- section 2's degree table, executed: E[d], the median, and BOTH cap rules
BUCKETS = [   # share of nodes, mean d, mean d^2
    (0.42, 18, 5.0e2), (0.31, 110, 1.5e4), (0.21, 450, 2.4e5),
    (0.054, 2100, 5.2e6), (0.006, 11000, 1.6e8),
]
E_d  = sum(s * d for s, d, _ in BUCKETS)
E_d2 = sum(s * q for s, _, q in BUCKETS)
median_d = 50 + (0.50 - 0.42) / 0.31 * (200 - 50)      # inside the 50-200 bucket
print("E[d] %.2f   median %.1f   Var %.3e   sd %.0f   E[d^2]/E[d] %.0f"
      % (E_d, median_d, E_d2 - E_d ** 2, (E_d2 - E_d ** 2) ** 0.5, E_d2 / E_d))
assert abs(E_d - 315.56) < 5e-3
assert abs(E_d2 - 1_296_060) < 1
assert abs((E_d2 - E_d ** 2) ** 0.5 - 1094) < 1
assert abs(E_d2 / E_d - 4107) < 1                      # the friendship-paradox mean
assert 0.42 < 0.50 < 0.73 and abs(median_d - 88.7) < 0.1     # the median is 89, not 240
assert abs(0.006 * 1.6e8 / E_d2 - 0.7407) < 1e-4       # top 0.6 % is 74.07 % of E[d^2]

# The generator SKIPS hubs (`continue` above). Price that rule, and price the
# gentler one next to it, because they are 2x apart and only one ships.
skip_rule   = sum(s * q for s, d, q in BUCKETS if d <= MAX_INTERMEDIATE_DEGREE)
mincap_rule = sum(s * min(q, MAX_INTERMEDIATE_DEGREE ** 2) for s, _, q in BUCKETS)
print("E[d^2] %.0f   skip -> %.0f (%.1fx, %.1f %% removed)   min-cap -> %.0f (%.1fx)"
      % (E_d2, skip_rule, E_d2 / skip_rule, 100 * (1 - skip_rule / E_d2),
         mincap_rule, E_d2 / mincap_rule))
assert abs(skip_rule - 55_260) < 1
assert abs(E_d2 / skip_rule - 23.5) < 0.1              # the rule the code above runs
assert abs(mincap_rule - 115_260) < 1
assert abs(E_d2 / mincap_rule - 11.2) < 0.1            # the rule that was priced
assert abs(1 - skip_rule / E_d2 - 0.957) < 1e-3

# and section 5.1's straggler arithmetic, at the median and at d = 240
print("P(no straggler): median %.2f   d=240 %.2f" % (0.995 ** 89, 0.995 ** 240))
assert abs(0.995 ** 89 - 0.64) < 5e-3
assert abs(0.995 ** 240 - 0.30) < 5e-3

4. Beyond the graph, and the privacy constraint

The comparison with cost showed that the next 0.035 of AUC is outside the graph. The strongest signals available are also the ones that can hurt people. This section covers the privacy failure that a better model makes worse, why the control has to sit at generation rather than at display, and then the ranker itself.

4.1 The other evidence sources

The inventory: what else the platform knows about a pair of members, how much of the membership each signal covers, and its risk. Coverage is the share of members the signal exists for at all — a perfect signal that covers 20% of people can only decide 20% of cases.

The first and last columns move together: the strongest signal in the table is also the riskiest, which the next two subsections explain.

4.2 The address-book asymmetry, which is the one to be able to derive

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, which is why it appears in every later design decision.

Start with the smallest case: two people, one address book. The last two lines look symmetric and are not.

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

The system now holds a directed edge with provenance CONTACT_IMPORT_BY_ALICE.

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, and it is the mechanism behind a whole family of incidents. Evidence obtained from one party must not be surfaced to the other party, because the evidence itself is private information about the first party.

A concrete case:

Carol is a therapist. She imports her phone contacts to find colleagues.
Her contact list contains 300 patients.

For every pair of patients (A, B):
    - both are neighbors of Carol in the contact-provenance channel
    - Carol's degree in that channel is 300 -- small enough that RA and AA
      both rate her a STRONG common neighbor
    - A and B are geographically co-located (same city, same clinic area)

The ranker scores (A, B) highly. PYMK suggests patient A to patient B.

The prediction is correct. A and B genuinely do have a person in common. And surfacing it discloses that both are seeing the same therapist — a fact neither of them disclosed, to a system that inferred it from a third party’s phone.

That is the shape of the whole problem: the failure is not a false positive — a wrong prediction. It is a true positive, a correct prediction, that must not be shown. No amount of model quality fixes it; only a rule about provenance does. Related instances, all with the same structure:

• A pseudonymous account suggested to the holder’s real-world contacts via a shared device fingerprint or a hashed phone number.
• Someone who left an abusive relationship suggested to the person they left, because forty mutual connections survive the separation.
• Members of a recovery, health, or identity support group suggested to each other because the group is a small, high-precision common neighbor.
• A candidate’s current manager suggested to a recruiter the candidate just spoke to.

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

One signal is rejected outright, and the argument is a derivation rather than an assertion of risk: its usefulness and its capacity for harm are the same number, so no threshold can separate them.

The signal is “you were in the same place at the same time.” Derive its precision — the share of the pairs it flags that really do know each other — as a function of n, the number of people at the venue at the same moment.

The four venues below are ordered from largest to smallest. Precision climbs as the venue shrinks, and the small venues are the problem:

P(acquainted | co-located at a venue with n simultaneous people)  ~  k / n

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, a courthouse, a shelter, a place of worship, a support meeting, a lawyer’s office. The signal’s usefulness and its capacity for harm are literally the same number — you cannot keep one and drop the other by tuning a threshold.

So the answer is not “use co-location carefully.” It is: do not use fine-grained co-location as evidence at all. Keep coarse self-declared location (city, region) as a filter on candidates generated by other means, which is a different thing: it narrows a pool rather than creating an edge.

4.4 The mechanisms

The address book asymmetry which is the one to be able to derive’s principle becomes six concrete controls, all of them code rather than policy — including a price on the one that looks free and is not.

Privacy here is a constraint on the candidate generator, not a filter on the output, for two reasons.

Ordering leaks. A candidate that is scored and then suppressed still shifted everything below it. The slate the viewer sees is evidence about the candidate they did not see.

Soft penalties become training data. A model retrained on logs produced under a post-hoc penalty learns to route around it — it produces the candidates the penalty does not catch. That is the label loop of the roster above, biting in the place it does most damage.

A note on bitmasks, since two mechanisms are written as one

A bitmask is a single integer used as a row of yes/no switches. Each power of two is one switch: 1 might mean “friend-of-a-friend”, 2 “I imported their contact”, 4 “they imported mine”. The integer 5 then means the first and third switches are both on.

You test one switch with the bitwise-and operator (prov & FOF), never with ==. Mechanism 2 is where that distinction matters.

1. Provenance on every candidate, and the bitmask has two kinds of bit in it.

Each candidate carries a mask of which evidence sources produced it: friend-of-a-friend, contact import in each direction, workplace, school, embedding.

Separately, the mask records which flags the evidence carries. Is the lone common neighbour in a sensitivity-flagged category? Is that neighbour a common neighbour only because somebody’s address book made them one?

Sources justify surfacing. Flags never do. Keeping both kinds of bit in one integer is fine; keeping them in one test is not.

2. Directional rules on one-way evidence, evaluated as a mask.

A candidate whose only justifying source is CONTACT_IMPORT_BY_OTHER is generated for the importer and never for the imported party. This costs roughly half the yield of contact import and is not negotiable.

It also has to be written as “does this candidate have any other justifying source”, not as provenance == CONTACT_THEIRS. An equality test on a bitmask is defeated by every additional bit — including a sensitivity flag, which is not a source at all and cannot justify anything. So write the list of sources that can justify surfacing down explicitly, once, in a constant, and leave the one-way bit out of it.

3. An evidence-count floor, applied narrowly because a global one is unaffordable.

Suppose you wanted “at least two independent common neighbors”, on the assumption that a pair with only one mutual connection is weak evidence.

Price it first. The table below splits the candidate pool by how many common neighbors each pair has. The first two columns give the size of each slice and how well it converts; the deciding column is the last one, the share of all accepted invitations that slice produces.

One note on the denominator before reading the numbers. The rate column is accepts per pool candidate, which is a third denominator — distinct from The funnel defined once cited everywhere’s accept-of-sent, and weighting to 6.4% rather than 59.5%. Only the share of accepts it implies drives the argument, and that share is the same whichever denominator you pick.

Dropping every single-common-neighbor candidate costs 30% of all accepted invitations. That rule cannot be applied globally.

Apply it only where the common-neighbour evidence is contact-import-only and it touches 4.1% of the pool and 1.2% of accepts — affordable because it is narrow.

The sensitivity-flagged branch is narrower still, and it works differently. A second witness cures contact-manufactured evidence and does not cure a flagged category.

Two people whose address books independently hold the same pair is ordinary evidence — two unrelated third parties happen to know them both. Two clinicians at the same practice is not that. It is a stronger inference about the same sensitive fact, not a weaker one.

So the flagged branch does not look at the witness count at all. It requires a justifying source from outside the witness set, which is the only thing that gives the suggestion a reason that is not the clinic.

3b. Something has to set those two flags, and that computation is the real control.

The gate is three lines of code, and it cannot fire on a bit nobody writes. So the flag computation is the therapist control, not the gate.

At generation time, take the candidate’s common-neighbour set and ask two questions of every witness in it:

1. Is this witness’s own profile in a flagged category — health, recovery, legal, identity support?
2. Is this witness a common neighbour only because they imported both sides, rather than through mutual accepted connections?

Each flag is set only when the answer is yes for every witness. A single clean witness makes the candidate ordinary, because then the card can be explained without naming the flagged context.

Carol in The address book asymmetry which is the one to be able to derive answers yes to both questions for every pair of her patients. So does every clinician in a two-therapist practice.

Then “requires a second independent source” is a count over the sources mask — that is what the INDEPENDENT constant in the code below is for. It is a count over sources, never over witnesses, because adding witnesses inside a flagged context adds evidence for the disclosure rather than an excuse for it.

4. 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. The absence must also not be inferable — if a slate visibly shrinks from 20 cards to 19, that shrinkage is itself a signal.

5. 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 to the viewer under both parties’ settings.

If the visible evidence set is empty, show a generic string or suppress the card entirely. Measure the suppression rate: it runs around 7% of otherwise-eligible impressions, which is a real recall cost.

6. Rate limits, because the surface is an oracle.

An oracle, in security, is any interface that will answer a question you were not supposed to be able to ask. The attack here is simple: upload a million phone numbers and observe which ones produce suggestions.

That turns the product into a membership oracle — a way to test whether an arbitrary phone number belongs to a member of this platform — across the entire user base. Three controls: cap import volume and frequency, require reciprocal or secondary evidence before an imported contact is ever surfaced, and never let the absence of a suggestion be a reliable negative.

The gate in code

The block below is all six mechanisms as running code, and the assertions at the bottom are the cases the prose claimed. Two functions matter: cn_flags computes the flags by scanning the witness set; admissible is the gate that reads them.

Note the pair admissible(FOF | _practice, 2, ...) and admissible(FOF | _practice, 300, ...): both are False, which is the “witness count does not cure a flagged category” rule.

# Provenance bits. Rules operate on these at GENERATION time, because a
# candidate that reaches the ranker can leak through ordering even if it is
# never rendered.
FOF             = 1 << 0
CONTACT_MINE    = 1 << 1     # I imported them
CONTACT_THEIRS  = 1 << 2     # they imported me
WORKPLACE       = 1 << 3
SCHOOL          = 1 << 4
EMBEDDING       = 1 << 5
SENSITIVE_CN    = 1 << 6     # sole common neighbor sits in a flagged category
CONTACT_CN_ONLY = 1 << 7     # the common neighbor is only a common neighbor
                             # because a third party's address book made them one

# Sources that may independently justify SURFACING a candidate. CONTACT_THEIRS
# is a source and is deliberately absent: it is private information about the
# other party (section 4.2), so it can never be the reason we surface them.
INDEPENDENT = (FOF, CONTACT_MINE, WORKPLACE, SCHOOL, EMBEDDING)
# Annotations on the evidence, not sources. Counting them as provenance is
# what let an `==` test on the mask be defeated by ORing in one more bit.
FLAGS = SENSITIVE_CN | CONTACT_CN_ONLY

def cn_flags(shared, sensitive_category, contact_only_edge):
    """Set the evidence FLAGS for a candidate, at generation time.

    `shared` is the common-neighbor set supporting the candidate;
    `sensitive_category(w)` is true when w's own profile sits in a flagged
    category (health, recovery, legal, identity support); `contact_only_edge(w)`
    is true when w is a common neighbor solely because w imported both sides,
    rather than through a mutual accepted connection.

    Both flags are set only when EVERY supporting witness has the property --
    one clean witness is enough to make the candidate ordinary, because then
    the suggestion has an explanation that does not name the flagged context.
    This is the missing half of the therapist control in section 4.2: the gate
    below cannot fire on a bit nobody sets. What the gate then DOES with the
    two flags differs, and that difference is the whole of the fix below:
    sensitivity does not dilute with witness count, and contact-manufactured
    evidence does.
    """
    bits = 0
    if shared and all(sensitive_category(w) for w in shared):
        bits |= SENSITIVE_CN
    if shared and all(contact_only_edge(w) for w in shared):
        bits |= CONTACT_CN_ONLY
    return bits

def admissible(prov, cn_count, blocked_either_way):
    """Hard gate. Returns False to drop the candidate before it is ever scored."""
    if blocked_either_way:
        return False
    justifying = [bit for bit in INDEPENDENT if prov & bit]
    # One-way evidence is private information about the OTHER party, so a
    # candidate with no other justifying source is never surfaced. Tested as
    # a MASK: `prov == CONTACT_THEIRS` is defeated by any other bit, including
    # SENSITIVE_CN, which is a flag and not a source at all.
    if not justifying:
        return False
    # SENSITIVE_CN thresholds on the SENSITIVITY OF THE SHARED CONTEXT, and
    # `cn_count` must not appear in this test. A second flagged witness is a
    # second clinician in the same practice: it makes the inference stronger,
    # not the disclosure weaker, so counting witnesses cannot buy this off.
    # Only a source from OUTSIDE the witness set -- a shared employer, a
    # school -- can justify the candidate, because only that gives the
    # suggestion a reason that is not the flagged context.
    if (prov & SENSITIVE_CN) and len(justifying) < 2:
        return False
    # CONTACT_CN_ONLY is different and count DOES cure it: two people whose
    # address books independently hold this pair is ordinary evidence, where
    # one is a single third party's private list. Narrow floor, so it costs
    # 1.2 % of accepts and not the 30 % a global "CN >= 2" rule would.
    if (prov & CONTACT_CN_ONLY) and cn_count < 2 and len(justifying) < 2:
        return False
    return True

def visible_explanation(shared, viewer_can_see):
    """Explain only on evidence the viewer is entitled to see.

    The count itself is a disclosure, so it is computed over the visible
    subset -- which may be smaller than the set used for ranking.
    """
    visible = [w for w in shared if viewer_can_see(w)]
    if not visible:
        return None                    # suppress the card or use a generic string
    return f"{len(visible)} mutual connection{'s' if len(visible) > 1 else ''}"

# --- every case the prose claims the gate blocks, executed --------------
# Flags are annotations, not sources, and the two bit ranges must stay
# disjoint -- the moment a flag can be read as a source, `justifying`
# starts counting the sensitivity bit as a reason to surface the pair.
assert FLAGS & sum(INDEPENDENT) == 0
assert admissible(FOF, 3, True) is False                        # blocked either way
assert admissible(CONTACT_THEIRS, 3, False) is False            # one-way evidence
assert admissible(CONTACT_THEIRS | SENSITIVE_CN, 3, False) is False   # mask, not ==
assert admissible(CONTACT_THEIRS | CONTACT_CN_ONLY, 3, False) is False
assert admissible(CONTACT_THEIRS | WORKPLACE, 3, False) is True  # a real second source

# the therapist (section 4.2): A and B share exactly one common neighbor,
# Carol, who is a common neighbor only because she imported her address book
# and whose profile category is flagged.
_carol = cn_flags(["carol"], lambda w: True, lambda w: True)
assert _carol == SENSITIVE_CN | CONTACT_CN_ONLY
assert admissible(FOF | _carol, 1, False) is False
assert admissible(FOF | WORKPLACE | _carol, 1, False) is True    # second source

# THE ADVERSARIAL CASE, and the one the guard used to fail: a two-therapist
# practice. Both witnesses are flagged, so cn_count is 2 and a lone-witness
# test waves it straight through -- while the disclosure it makes is strictly
# worse, because now the shared context is a clinic rather than a person.
_practice = cn_flags(["carol", "dan"], lambda w: True, lambda w: True)
assert _practice == SENSITIVE_CN | CONTACT_CN_ONLY
assert admissible(FOF | _practice, 2, False) is False
assert admissible(FOF | _practice, 300, False) is False          # a whole clinic, still dropped
assert admissible(FOF | WORKPLACE | _practice, 2, False) is True # a reason that is not the clinic

# And the bound, stated rather than implied: ONE ordinary witness clears the
# flag entirely, because then the card can be explained without naming the
# clinic. That is the guarantee -- "no candidate whose every witness is
# flagged" -- and it is narrower than "never", so do not claim "never".
_mixed = cn_flags(["carol", "dave"], lambda w: w == "carol", lambda w: w == "carol")
assert _mixed == 0
assert admissible(FOF | _mixed, 2, False) is True

# Contact-manufactured witnesses, by contrast, ARE cured by a second one.
_one_book  = cn_flags(["erin"], lambda w: False, lambda w: True)
_two_books = cn_flags(["erin", "frank"], lambda w: False, lambda w: True)
assert _one_book == _two_books == CONTACT_CN_ONLY
assert admissible(FOF | _one_book, 1, False) is False
assert admissible(FOF | _two_books, 2, False) is True

print("therapist, 1 witness  : admissible? %s" % admissible(FOF | _carol, 1, False))
print("therapist, 2 witnesses: admissible? %s" % admissible(FOF | _practice, 2, False))
print("therapist + workplace : admissible? %s" % admissible(FOF | WORKPLACE | _practice, 2, False))
print("one flagged, one clean: admissible? %s" % admissible(FOF | _mixed, 2, False))
print("two address books     : admissible? %s" % admissible(FOF | _two_books, 2, False))

# and the floor stays narrow: an ordinary single-common-neighbor candidate is
# 62 % of the pool and 30 % of accepts, and must still be admissible.
_ordinary = cn_flags(["dave"], lambda w: False, lambda w: False)
assert _ordinary == 0
assert admissible(FOF | _ordinary, 1, False) is True
assert admissible(EMBEDDING, 0, False) is True                   # no CN, no flags
assert visible_explanation(["a", "b"], lambda w: w == "a") == "1 mutual connection"
assert visible_explanation(["a"], lambda w: False) is None

4.5 The ranker: model, label, and the training split that earns the AUC

Every feature the ranker uses (Graph features, The other evidence sources) and the gate that decides which pairs are allowed to exist (The mechanisms) are now defined, so the ranker can be assembled: the model class and why it is not a neural network, what one row of training data looks like, where the label comes from and why its origin is the subtlest problem in the design, and the evaluation protocol behind the headline AUC. The comparison with cost stopped at AUC 0.945 without saying what produced it; this is where it comes from.

The model class, and why it is not a neural network

The ranker is a gradient-boosted decision tree ensemble (GBDT) — roughly 400 short decision trees, each at most 8 questions deep, each trained to correct the errors the previous ones made, with the final score being their sum. It is the same model priced in The two pure designs’s scoring budget.

It is deliberately not a deep network, for three reasons specific to this problem.

The features are already engineered. The vector is a few hundred dense, heterogeneous signals: common neighbors, Adamic-Adar, resource allocation, Jaccard, a bucketed personalized-PageRank mass, node2vec cosine similarity, workplace/school/tenure overlap, the activity prior, impression-decay counters. That is the regime where gradient-boosted trees beat neural networks — there is no raw input for a network to learn a representation from.

The strongest features are sharply non-linear and interaction-heavy. Resource allocation down-weights by 1/d; the activity prior of Dormant accounts gates multiplicatively rather than additively. Trees split on exactly that kind of structure, without anyone hand-building the feature crosses a linear model would need.

It retrains daily on fresh edges (Invalidation is cheap recomputation should be demand driven). That is a few hours of ordinary processor time for a tree ensemble, against the far longer tuning cycle a deep network needs.

The one learned representation in the design, the node2vec embedding, sits upstream as a candidate generator (Embeddings and what a low rank factorization cannot keep), not inside the ranker.

What it eats, and the one rule about when each feature is computed

Per candidate pair: the graph block (Graph features) plus the non-graph block (The other evidence sources), roughly 200-400 features. Every one 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 the classic temporal leak — training data containing information that did not exist yet at the moment the prediction would have had to be made.

Here that leak is catastrophic rather than merely optimistic, because the label is an edge and half the features are functions of edges. Compute a common-neighbor count after the fact and it already includes the very edge being predicted. It predicts that edge perfectly and teaches the model nothing.

The label

The label is accept within 14 days of send, not “an edge ever formed.”

Why 14 days rather than forever? An accept that lands on day 30 is a positive the model could not have seen when it scored at send time. A 14-day window captures the bulk of eventual accepts, because they are front-loaded, and it 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 stage, which has its own label, and conflating the two trains the accept head on the send head’s decisions.

The part that is easy to state and easy to skip

That label exists only for pairs the system already chose to show.

A connection that was never suggested cannot be sent, and one that was never sent cannot be accepted. So there is no row in the training data for it — not a zero, nothing at all.

The label set is therefore manufactured by the previous version of this exact system. Generator, ranker and slate assembly all had to say yes before a human was given the chance to say anything.

Three things follow, and they shape everything up to the evaluation protocol.

The observed positives and negatives live inside last week’s model’s opinion. Whatever it ranked below position twenty is unlabelled, so a model fitted only to the observed rows learns “the previous model was right about everything it never showed you,” which is not a fact about the world and is not falsifiable from inside the loop. Left alone this is a ratchet: each generation of the model narrows the region it has evidence about, and Rich get richer’s degree concentration and Demographic effects and the counterintuitive part’s cross-group narrowing are what that ratchet looks like from the outside.

So the easy negatives below are not a training convenience, they are the escape hatch. They are drawn from pairs the system never showed anybody, which makes them the only rows in the training set that are not conditioned on a previous model’s decision.

And no offline number can close the loop by itself, which is why the value tier in The metric stack requires a permanent 0.5% holdout with the product switched off. That population is the one place the feedback loop never reached.

Negatives, and the population they are drawn against

Name the population before sampling, because The global number and an identity worth knowing supplies a base rate that is not this model’s.

The label is accept-within-14-days-of-send, so the population this model is served on is sent invitations, where 59.5% of rows are positive (The funnel defined once cited everywhere). P(edge | candidate pair) = 2.5 x 10^-4 is the retrieval rate that forces What that forces capping and sampling’s cut. Putting it in this model’s prior slot is wrong by a factor of about 2,400.

Sent rows in their natural proportion would make a training set that is balanced and useless, because every one of them is a pair the deployed system already liked. So the negatives are deliberately over-represented, at 20 per positive, drawn in two halves:

• Hard negatives — candidates that were shown and declined. Real sent-population rows, and they teach the boundary the system currently sits on.
• Easy negatives — random admissible 2-hop pairs, imported from the candidate-pair population. These are the only view the model gets of the space its predecessor ignored.

Twenty negatives per positive, against a population that is only 40.5% negative, deflates every predicted probability. That deflation has to be undone before any threshold is applied.

The block below does the undoing. Read the printed table of raw -> de-sampled values: a raw score of 0.10 comes back as roughly 0.77, which is the size of the distortion being corrected.

# Three populations. Every probability in this chapter belongs to exactly
# one of them, and the calibration bug this block exists to prevent is
# applying a threshold from one to a score produced on another.
P_EDGE_GIVEN_CANDIDATE    = 1.6e11 / 6.5e14   # 2.46e-4, section 2.3 -- a STOCK ratio
P_ACCEPT_GIVEN_IMPRESSION = 0.025             # section 6.1 -- the primary online metric
P_ACCEPT_GIVEN_SENT       = 0.595             # section 6.1 -- and THIS model's prior

# The ranker's label is `accept within 14 days of SEND`, so its serving
# population is sent invitations and its prior is 0.595 -- not the 2.5e-4
# retrieval rate, which belongs to the pool the generator cuts. De-sampling
# against the wrong one is what turns the 0.23 gate of section 6.2 into a
# rule that rejects every score the model can produce.
SENT_PRIOR  = P_ACCEPT_GIVEN_SENT
NEG_PER_POS = 20                              # half hard (shown & declined), half easy
ECON_GATE   = 0.3 / 1.3                       # section 6.2, in P(accept | sent) units

assert P_EDGE_GIVEN_CANDIDATE < 1e-3          # GENERATION faces extreme imbalance
assert abs(SENT_PRIOR / P_EDGE_GIVEN_CANDIDATE - 2417) < 1     # the ranker does not

# Elkan (2001): with a known kept-negative fraction, the map back to the
# serving prior is closed form. 20:1 negatives against a 40.5 %-negative
# population DEFLATES the scores, so beta > 1 and de-sampling raises them.
p_sampled = 1.0 / (1.0 + NEG_PER_POS)                        # positive prior in the sample
beta      = (SENT_PRIOR / (1 - SENT_PRIOR)) * ((1 - p_sampled) / p_sampled)

def desample(p):
    """Raw score at the training prior -> P(accept | sent) at the serving prior."""
    return beta * p / (beta * p - p + 1)

def passes_gate(raw):
    """Compose the chapter's own two functions, which is the check that was missing."""
    return desample(raw) >= ECON_GATE

print("training prior %.4f   serving prior %.3f   beta %.3f"
      % (p_sampled, SENT_PRIOR, beta))
for _raw in (0.005, 0.01, 0.10, 0.30, 0.50, 0.90, 0.99):
    print("  raw %.3f -> de-sampled %.4f   passes %.3f gate? %s"
          % (_raw, desample(_raw), ECON_GATE, passes_gate(_raw)))
_raw_star = ECON_GATE / (beta * (1 - ECON_GATE) + ECON_GATE)
print("minimum raw score that clears the gate: %.6f" % _raw_star)

assert abs(p_sampled - 1 / 21) < 1e-9
assert abs(beta - 29.3827) < 1e-3
# The correction is an identity at the training prior: de-sampling the prior
# the model was TRAINED at has to return the prior it is SERVED against.
assert abs(desample(p_sampled) - SENT_PRIOR) < 1e-9
assert desample(0.9) > desample(0.5) > desample(0.1)     # monotone: RANKING survives
# The assertion whose absence let the spine break. A mid-range raw score must
# CLEAR the economic gate; de-sampled against 1e-4 instead of 0.595, nothing
# below a 0.9934 raw score did, which is a gate that rejects the whole slate.
assert passes_gate(0.50) and passes_gate(0.30) and passes_gate(0.10)
assert not passes_gate(0.005)                            # and it still bites at the bottom
assert abs(_raw_star - 0.010107) < 1e-5

# section 3.5's embedding dimension, priced across the three obvious choices.
# 128 is chosen where recall@k plateaus, not where a loss bottoms out.
N_NODES, N_EDGES = 1e9, 1.6e11
print("128-d store %.0f GB, %.2f params/edge; 256-d %.2f params/edge"
      % (N_NODES * 128 * 2 / 1e9, N_NODES * 128 / N_EDGES, N_NODES * 256 / N_EDGES))
assert abs(N_NODES * 128 * 2 / 1e9 - 256) < 1     # 256 GB store at 128-d, fp16
assert abs((N_NODES * 128) / N_EDGES - 0.8) < 1e-2   # 0.8 params/edge (section 3.5)
assert abs((N_NODES * 256) / N_EDGES - 1.6) < 1e-2   # doubling dim: 2x store, no recall gain

Two words in that block need pinning down. The training prior is the fraction of positives the model was shown during training — here 1 in 21. And desample is monotone, meaning it never reverses the order of two scores.

Monotone has a consequence worth stating plainly: the ranking survives the raw scores uncorrected. Sort by the raw score and you get the same list you would get after correcting. The decision is what does not survive.

Why optimizing acceptance produces low value suggestions’s 23% break-even is a statement about P(accept | sent). A model trained at a prior of 1 positive in 21, against a population that is 59.5% positive, reports numbers far too small until it is de-sampled — and then calibrated, meaning adjusted so that among all the pairs it scores 0.30, about thirty in a hundred really do accept. Calibration is a completely separate property from ranking, and it is the discipline of ml 07.

De-sampling does the part it can prove and calibration absorbs the rest.

Elkan’s correction is exact for negatives subsampled from the serving population. Half of these negatives are not: the easy half is imported from the candidate-pair pool precisely because nobody ever showed those rows.

So desample removes the known, closed-form part of the distortion, and an isotonic map removes what is left. Isotonic regression fits a staircase — a function that is allowed to bend anywhere but never to go down — from raw score to observed accept rate, on held-out sent traffic. Because it only ever increases, it fixes the levels without touching the order.

Saying which half of the correction is derived and which is fitted is the honest version of “the scores are calibrated”.

One training row, end to end

Here is a single training example: a candidate pair, every feature computed as of generation time, the label, and then the decision chain the same row would meet at serving.

The graph features are recomputed from the witness degrees rather than asserted, so the row is checkable. In the last four lines, the same raw score of 0.31 becomes a SHOW against a live candidate and a DROP against a dormant one, with nothing but the activity prior changed.

# ONE ROW of training data. Features as of GENERATION time and never later:
# a common-neighbour count computed after the fact contains the edge it is
# trying to predict, which is the temporal leak described above.
_ROW_DEG = {"u": 240, "v": 155, "w1": 40, "w2": 85, "w3": 120, "w4": 310}
_ROW_ADJ = {"u": ["w1", "w2", "w3", "w4"], "v": ["w1", "w2", "w3", "w4"],
            "w1": ["u", "v"], "w2": ["u", "v"], "w3": ["u", "v"], "w4": ["u", "v"]}
_cn, _aa, _ra = pair_features("u", "v", lambda n: _ROW_ADJ[n], lambda n: _ROW_DEG[n])
_j = jaccard(_cn, _ROW_DEG["u"], _ROW_DEG["v"])

row = {
    # graph block (section 3), computed UNCAPPED -- witness degrees 40/85/120/310
    "cn": _cn, "adamic_adar": _aa, "resource_alloc": _ra, "jaccard": _j,
    "ppr_visits_bucket": "6-50",          # bucketed, not continuous (section 3.4)
    "n2v_cosine": 0.61, "deg_u": 240, "deg_v": 155,
    # non-graph block (section 4.1)
    "same_school": True, "grad_year_gap": 2, "workplace_overlap_months": 0,
    "email_domain_match": False, "profile_view_recip": False,
    "shared_group": False, "contact_import": "none",
    # provenance (section 4.4) -- sources only, no flags set
    "prov": FOF | SCHOOL, "cn_count": _cn,
    # liveness (section 7.2) and exposure state (section 7.1)
    "p_active_28d": 0.86, "impressions_of_v_to_u": 1, "dismissals": 0,
    # LABEL (section 4.5): accept within 14 days OF SEND. Population: sent.
    "label": 1,
}
for _k, _v in row.items():
    print("  %-24s %s" % (_k, round(_v, 5) if isinstance(_v, float) else _v))

assert (row["cn"], round(row["adamic_adar"], 3), round(row["resource_alloc"], 4)) \
    == (4, 0.879, 0.0483)
assert abs(row["jaccard"] - 4 / (240 + 155 - 4)) < 1e-12
assert admissible(row["prov"], row["cn_count"], False) is True   # it may exist at all

# The decision chain, composed from this chapter's own functions.
raw            = 0.31                              # what the GBDT emits, training units
p_accept_sent  = desample(raw)                     # section 4.5 -> P(accept | sent)
p_final        = p_accept_sent * row["p_active_28d"]   # section 7.2, MULTIPLICATIVE
decision       = "SHOW" if p_final >= ECON_GATE else "DROP"
print("raw %.2f -> P(accept | sent) %.4f -> x activity prior %.2f = %.4f -> %s"
      % (raw, p_accept_sent, row["p_active_28d"], p_final, decision))

assert abs(p_accept_sent - 0.9296) < 1e-4
assert abs(p_final - 0.7994) < 1e-4
assert decision == "SHOW"
# the same row, same raw score, against a dormant candidate: the activity
# prior alone drops it, which is why section 7.2 keeps it outside the trees.
assert desample(raw) * 0.05 < ECON_GATE
print("same raw score, p_active 0.05 -> %.4f -> DROP" % (desample(raw) * 0.05))

The split respects time, because the graph does. Train on edges and sends timestamped before some cutoff T; evaluate on the window [T, T + 14 days]; compute every feature as of its own row’s timestamp. A random 80/20 split — shuffle all rows, keep 80% for training — leaks future edges into features and reads near 1.0 offline before collapsing online. The 0.945 of The comparison with cost is a temporal-split, de-sampled, 14-day-label number — quoted any other way it is not the same quantity as the online accept-of-sent rate it is built to predict, and the offline-online gap of Metrics is precisely that comparison.

Assumptions in this section, and the load-bearing one. The load-bearing assumption is the label one, and it has already had its own paragraphs: that training on rows manufactured by the previous version of the system, plus a deliberately un-selected easy-negative sample, plus a permanent holdout, is enough to keep the feedback loop bounded.

Every part of that sentence is a choice, and the honest position is that it bounds the loop rather than removing it. The hard negatives are still the old model’s opinion. The easy negatives are cheap precisely because nobody ever looked at them, so they carry no human judgement at all.

A second assumption is nearly as heavy and is easier to check: that 14 days captures the bulk of eventual accepts. If accepts were uniformly spread over 90 days instead of front-loaded, the label would be mostly-missing rather than mostly-complete, and daily retraining would be training on noise.

Secondary: the 20-to-1 negative ratio, which is a free choice affecting only the size of the correction, and the 200-400 feature count, which sets the cost of the model and no conclusion.

5. Serving: precompute, invalidate, recompute lazily

The model is now defined; what remains is deciding when it runs. The two obvious answers — compute suggestions when the user asks, or compute everybody’s overnight — both fail, for different reasons, which forces a third answer that generalizes to any “precompute or compute online” question.

5.1 The two pure designs

Price the two extremes first, so that the hybrid in Invalidation is cheap recomputation should be demand driven is forced rather than asserted.

Full online. Traverse the graph at request time. That is one adjacency fetch per connection — 89 for the median member and 240 for the one the generation budget is sized at (The friendship paradox is why d2 is the wrong estimate).

The fan-in latency argument from ml-system-design/10 applies with force. Fan-in means one request must wait for many parallel sub-requests, so its latency is the slowest of them, not the average. p99 is the 99th-percentile latency: the value that only the slowest one percent of fetches exceed.

The 0.995 below is the assumed per-fetch probability of avoiding that slow tail. Fetches are assumed independent, so the chance that every fetch in a request avoids it is 0.995 raised to the number of fetches. Work that out for both members:

per-fetch p99 = 5 ms, fetches independent

median member,  89 fetches:   P(no straggler)  =  0.995^89   =  0.64
d = 240 member, 240 fetches:  P(no straggler)  =  0.995^240  =  0.30
cap-degree member:            off the scale entirely

Thirty-six percent of median requests contain at least one p99 fetch, and seventy percent of the d = 240 member’s do — a straggler being one slow sub-request that holds up the whole response, and the request’s latency being the max rather than the mean. Plus 1.6 KB of adjacency per fetch: 142 KB per median request and 384 KB at d = 240, which at 20 k requests per second is 2.8-7.7 GB/s of random access. Not viable as the whole design.

Full nightly precompute. Run the whole pipeline for everybody overnight and store the top candidates per member, so a request is a single lookup. A replica below is a redundant copy of the data kept on separate hardware, which is why the storage figure triples:

400 M monthly-active members x 500 candidates x 16 B (id + score + provenance + flags)
   =  3.2 TB      x 3 replicas  =  9.6 TB
all 1 B registered members      =  8 TB   x 3  =  24 TB

Storage is not the problem — 24 TB is unremarkable. The I/O — input/output, the work of moving bytes off disk rather than doing arithmetic on them — dominates the compute:

scoring:  5,000 candidates x 400-tree GBDT depth 8  ~=  1.6e7 ops/user
          x 1e9 users  =  1.6e16 ops  =  ~4,400 core-hours

graph I/O: 1e9 users x 48,000 sampled 2-paths x 20 B  =  9.6e14 B  =  960 TB read
          nightly -> 11 GB/s sustained

The problem with nightly is freshness. Each row below is one bucket of lag between a graph event — a job change, a contact import, an accepted invitation — and the suggestion that event should have produced:

time between the triggering graph event and the suggestion   accept-of-sent (diag.)
< 1 h                                                             24.1 %
1 - 24 h                                                          14.8 %
1 - 7 d                                                            9.2 %
> 7 d                                                              6.8 %

These are diagnostic accept-of-sent on the The funnel defined once cited everywhere base — measured on an unranked send so the freshness effect is uncensored — which is why all four sit below the shipped 59.5%; the ranker is what closes that gap, and the point here is the ratio across buckets, not the level. A suggestion is worth 3.5x more in the hour after you joined a company or added five colleagues than it is a week later, and a nightly job forfeits essentially all of that. The high-value moments — a job change, a contact import, an accepted invitation that opens a new neighborhood — are exactly when the precomputed set is most wrong.

5.2 Invalidation is cheap; recomputation should be demand-driven

The payoff rests on separating two things people usually conflate: noticing that a stored answer is out of date, and computing the new one. Invalidation is the first — marking a stored result as no longer trustworthy — and it is thousands of times cheaper than the second.

Start by counting how often a stored answer goes stale. A new edge (u, v) creates new 2-paths for every neighbor of u and every neighbor of v, so every one of those members now has a stale stored candidate set:

new edges/day                      100 M
users invalidated per edge         d_u + d_v  ~=  2 x 316  =  632
invalidations/day                  1e8 x 632  =  6.3 x 10^10   =  731 k/s

Recomputing on every invalidation would mean recomputing the average member’s candidate set 6.3e10 / 1e9 = 63 times a day.

Now count how often anyone actually reads one:

members who load a PYMK surface on a given day    ~30 M      (3 % of 1 B)
on-demand recomputes                              30 M/day  =  347/s
at ~200 ms of graph work each                     ~70 cores

Invalidation turns a 731,000-per-second problem into a 347-per-second problem, and the entire trick is to mark dirty rather than recompute. A dirty bit is one bit per member meaning “this member’s stored answer is stale”; a bitmap is the array holding all of them. One bit each for a billion members is 125 MB, which fits in memory on a single host. Then:

• Lazy path: on surface load, if the member’s dirty bit is set, recompute; otherwise serve the stored set with a light online re-rank against fresh session context.
• Eager path, narrowly: on a high-value trigger — accepted invitation, job change, contact import, new group join — recompute immediately without waiting for a visit, because The two pure designs says the next hour is worth 3.5x. That is roughly 8 M events/day, or 93/s, which is affordable precisely because it is a small, chosen subset.
• Floor: recompute anything untouched for 30 days, so the store does not rot.

The general shape — invalidate eagerly, recompute lazily, escalate on a small set of high-value triggers — answers almost every “precompute or online” question.

Assumptions in this section, and the load-bearing one. The load-bearing assumption is the 2,100-fold gap between how often the stored answer goes stale and how often anyone reads it — 731 k/s of invalidations against 347/s of surface loads. That gap comes from one observation: about 3% of members open a People You May Know surface on a given day.

That single ratio is the entire justification for the dirty-bitmap design. If the product moved suggestions somewhere every member sees on every visit, the ratio would collapse toward one and lazy recomputation would stop being an optimization.

Secondary and much weaker: the 200 ms of graph work per recompute, which sizes the 70-core fleet and nothing else, and the 30-day staleness floor, which is a hygiene choice.

The freshness table is a measurement rather than an assumption, but it does rest on one thing worth naming: that the accept-rate premium in the first hour is caused by the recency of the graph event rather than by who tends to trigger such events. People who just changed jobs are unusual in other ways too, so a clean read of the 3.5x needs the comparison held within a member rather than across members.

5.3 Architecture

The whole system fits on one page. The ordering of three of its boxes carries the argument of the chapter, not just an implementation detail.

Three boxes are coloured: red is the privacy gate, which sits before scoring; green is the economic gate, which sits after it; orange is the dirty bitmap. A walkthrough follows the diagram.

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 given 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

    style PRIV fill:#9d0208,color:#fff
    style ECON fill:#2d6a4f,color:#fff
    style DIRTY fill:#bc6c25,color:#fff

Read it in two halves.

The upper half: offline / streaming. This is everything that happens without a user waiting. It is streaming rather than merely batch because graph events arrive continuously and are consumed as they arrive.

A graph event — a new edge, a job change, a contact import, a block — does two things at once. It sets a bit in the dirty bitmap (the orange box: one billion bits, 125 MB, absorbing 731 thousand marks per second). And if the event is one of the high-value kind, it also fires an immediate recompute, at 93 per second.

Candidate generation reads the adjacency store, which is sharded by node — split across many machines, each holding a slice of the members, so one member’s neighbor list is one machine’s local read. It produces the 30,000 distinct candidates of What that forces capping and sampling.

Those pass through the provenance gate. It either drops a candidate — in which case the candidate is never scored and leaves no trace anywhere downstream — or lets it through to the cheap score that cuts 30,000 to 5,000. The GBDT ranker scores those 5,000 on the graph and non-graph feature blocks together, and the survivors land in the candidate store: 500 per member at 16 bytes each, 9.6 TB across three replicas.

The lower half: the request path. A surface load checks the dirty bit. If set, it goes straight to generation at 347 per second; if not, it reads the candidate store. Either way the result is re-ranked online against session context.

Then come the two boxes that turn a score into a decision.

De-sample + calibrate maps the raw ranker output off its training prior of 1-positive-in-21 and onto P(accept | sent), whose population prior is 0.595. Elkan’s closed-form correction handles the part that is known; an isotonic map fitted on held-out sent traffic handles the part that is not (The ranker model label and the training split that earns the auc).

Activity prior then multiplies by P(active in the next 28 days). It is a separate box rather than one of the ranker’s two hundred features for the reason Dormant accounts gives: the graph features and the liveness signal point in opposite directions exactly in the tail that matters, so a near-zero liveness has to be able to send the whole product to near zero.

Only then does the green economic gate drop anything whose predicted acceptance probability is below the 0.23 break-even derived in Why optimizing acceptance produces low value suggestions — the point at which the recipient’s cost, priced in, exactly cancels the value of an accept. The gate is applied to the output of those two boxes and never to the raw score, which is the whole reason they are on the diagram.

Slate assembly then applies the exposure cap, the diversity reservation and dismissal suppression. Each surviving card is asked whether a visible explanation exists for this particular viewer; if none does, the system takes the suppress card branch rather than showing an unexplained one, on about 7% of otherwise-eligible impressions. What is left is the twenty suggestions.

The last edge closes the loop the roster warned about. The store at the bottom — impression · send · accept + provenance of each — is the event log: one row per suggestion shown, per invitation sent, per invitation accepted, each carrying the provenance of the candidate that produced it. It flows straight back into candidate generation as tomorrow’s training data. That arrow is why the labels are the previous system’s opinion.

Two things about the ordering are load-bearing.

The red provenance gate sits before scoring. It is the only thing standing between a correct model and The address book asymmetry which is the one to be able to derive’s disclosure, and it goes first for the reason given in The mechanisms: a dropped candidate that had reached the ranker would still have moved everything below it.

The green economic gate sits after the ranker rather than inside it. It is a decision about a calibrated probability, and the raw score is not one until The ranker model label and the training split that earns the auc’s de-sampling has been applied.

6. Metrics

Measuring this system takes careful bookkeeping: the phrase “accept rate” can mean three different things here, and they differ by a factor of twenty-five. The funnel is defined once and everything else cites it. The metric most people reach for first is gameable in three separate directions.

6.1 The funnel — defined once, cited everywhere

A funnel is the chain of conditional events between showing something and getting the outcome you wanted, with each stage counted as a share of the one before it.

Every rate in this chapter is one point on a single funnel, and the chapter is only reconstructable if that funnel is defined in one place. Here it is, 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  invitations declined or ignored -- a cost imposed on someone else

One hundred impressions produce 0.31 relationships and 1.7 unwanted messages. Both numbers belong on the dashboard.

Three rates, and they are the only three the chapter treats as “the accept rate”. The vertical bar in P(A | B) reads “given”: the probability of A among the cases where B already happened.

• 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 of The metric stack, “accepts per 100 impressions.”

The bucketed tables elsewhere — by common-neighbour count (The mechanisms), by recipient last-active (Dormant accounts), by event-to-impression lag (The two pure designs) — report accept rates on a diagnostic population: a send that was not ranked, or that came from a holdout slice, used to size one feature’s marginal effect in isolation. Those numbers sit below 59.5% on purpose, because lifting accept-of-sent above the diagnostic baseline is exactly what the ranker is for. Two of them are worth pinning against this definition, and The mechanisms uses a third, explicitly pool-based denominator.

The block below computes all of them from their source tables, so you can see that 20.2% and 59.5% and 6.4% are three different questions rather than three inconsistent answers to one:

# The funnel, computed once. Every accept rate in the chapter is one of these.
impressions     = 100.0
send_rate       = 0.042                        # P(send | impression)
sent            = impressions * send_rate       # 4.2
accept_of_sent  = 0.595                          # P(accept | sent), SHIPPED ranker
accepted        = sent * accept_of_sent          # 2.5
declined        = sent - accepted                # 1.7
accept_per_impr = send_rate * accept_of_sent     # 0.025 = the PRIMARY metric

print("100 impressions -> %.1f sent -> %.3f accepted, %.3f declined"
      % (sent, accepted, declined))
print("send %.1f %%   accept-of-sent %.1f %%   accept-per-impression %.1f %%"
      % (100 * send_rate, 100 * accept_of_sent, 100 * accept_per_impr))
assert abs(sent - 4.2) < 1e-9
assert abs(accepted - 2.499) < 1e-3
assert abs(declined - 1.701) < 1e-3
assert abs(accept_per_impr - 0.025) < 1e-4       # "2.5 accepts per 100 impressions"

# daily, at platform scale (sections 1 and 8 cite these two lines):
slots_per_day    = 6e8
sent_per_day     = slots_per_day * send_rate            # 25.2 M
declined_per_day = sent_per_day * (1 - accept_of_sent)  # 10.2 M
assert abs(sent_per_day - 25.2e6) < 1e3
print("daily: %.1f M slots -> %.1f M sent -> %.1f M declined or ignored"
      % (slots_per_day / 1e6, sent_per_day / 1e6, declined_per_day / 1e6))
assert abs(declined_per_day - 10.2e6) < 1e4

# DIAGNOSTIC base (unranked send), section 7.2, by recipient last-active bucket:
la_share = [0.34, 0.21, 0.24, 0.21]
la_rate  = [0.41, 0.22, 0.06, 0.011]
diag_accept_of_sent = sum(s * r for s, r in zip(la_share, la_rate))     # 0.202
print("diagnostic accept-of-sent %.1f %% -> restricted to last-active <= 30 d %.1f %%"
      % (100 * diag_accept_of_sent,
         100 * sum(s * r for s, r in zip(la_share[:2], la_rate[:2])) / sum(la_share[:2])))
assert abs(diag_accept_of_sent - 0.202) < 1e-3          # NOT 0.595: a different population

# POOL base (accept per pool candidate), section 4.4, by common-neighbour count.
# Only the SHARE OF ACCEPTS it implies drives that argument, not the level.
cn_share = [0.62, 0.19, 0.13, 0.06]
cn_rate  = [0.031, 0.074, 0.132, 0.225]
pool_accept_per_candidate = sum(s * r for s, r in zip(cn_share, cn_rate))   # 0.0639
share_cn1 = cn_share[0] * cn_rate[0] / pool_accept_per_candidate            # 0.30
assert abs(pool_accept_per_candidate - 0.0639) < 5e-4
print("pool accept-per-candidate %.4f; CN=1 is %.0f %% of the pool and %.0f %% of accepts"
      % (pool_accept_per_candidate, 100 * cn_share[0], 100 * share_cn1))
assert abs(share_cn1 - 0.30) < 0.01

# section 7.4's reservation cost is on the SHIPPED accept-of-sent, not a new base:
assert abs(accept_of_sent - 0.011 - 0.584) < 1e-9        # 59.5% -> 58.4%, -1.1 pp
assert 8.9 / 5.1 > 1.7                                    # cross-group accepts nearly double

6.2 Why optimizing acceptance produces low-value suggestions

The most natural metric — the share of invitations that get accepted — fails in three independent ways that compound rather than cancel. The third failure produces a number, 23%, that the serving path in Architecture enforces directly.

It selects for people who accept everything.

account with 24,000 connections, accept-everything policy:  P(accept | sent) = 0.94
population baseline:                                         P(accept | sent) = 0.60

Ranking on P(accept) puts them near the top of every slate on the platform, which grows their degree, which raises their common-neighbor count with everyone, which raises their rank further. This is the degree-concentration loop in Rich get richer, entered through the metric rather than through the features.

It selects for the already-obvious. Your current desk neighbor has 40 common connections and a 0.95 accept rate. The suggestion is correct and its incremental value — how much better off the world is because you showed it — is approximately zero, because that connection was going to happen anyway. The quantity you want is incremental, the difference between showing the suggestion and not showing it, and incrementality is not a label. It is a difference between two populations, which is why it can only come from the holdout of The metric stack.

It ignores the recipient. Price the externality — a cost the decision imposes on somebody who is not party to it. Let V be the value of an accepted connection and c the cost of an unwanted invitation to its recipient. From decline-and-block rates, c ≈ 0.3 V. Then write the expected value of showing a suggestion whose acceptance probability is p, and solve for the p at which it is exactly zero:

E[value]  =  p·V  -  (1 - p)·c
zero when    p(V + c) = c
             p*  =  c / (V + c)  =  0.3 / 1.3  =  0.231

Suggestions with a predicted acceptance probability below about 23% are net negative once the recipient’s time is priced at all, and in a naive slate a large share of positions sit below that line. This is the same construction as deriving a decision threshold from a cost matrix — a table of what each kind of mistake costs, from which the break-even probability follows mechanically (Choosing a threshold from the cost matrix). The only unusual part is that the cost falls on someone who is not the user being served.

6.3 The metric stack

A single metric cannot carry a two-sided product, so the dashboard is arranged in tiers, each with a different job. Gini below is the Gini coefficient, a single number from 0 to 1 measuring how unequally something is distributed — 0 if every member had the same number of connections, 1 if one member had all of them.

Two notes on the value tier, because it is where designs are thin.

It requires a holdout, permanently — kept switched off indefinitely rather than for the length of an experiment. Suppress People You May Know entirely for 0.5% of members and compare the two populations on 90-day engagement, connections formed by other paths, and retention.

Without it, “connections formed” is unattributable. People form connections anyway, so the product’s contribution is the difference between the two populations, not the total in the treated one. The holdout is also, as The ranker model label and the training split that earns the auc argued, the only population in the system whose behaviour was not shaped by an earlier version of the model.

One thing makes this harder than a normal experiment: interference, meaning one user’s treatment affects another user’s outcome, which breaks the independence every standard test assumes. Here it is unavoidable — a suppressed member’s connections are not suppressed, so the treatment leaks along the very graph edges you are trying to measure (Ab testing).

Two partial answers. Cluster-randomize on graph communities where you can: assign whole tightly-connected groups to one arm rather than individuals. Where you cannot, read the number as a lower bound rather than an estimate.

Report rate by provenance is a cheap, high-value audit. If suggestions sourced from contact imports carry a 0.31% “I do not know this person” rate against 0.05% for friend-of-a-friend ones, you have located a precision problem and a privacy problem in one column, without a single label.

Assumptions in this section, and the load-bearing one. The funnel is measured. What is assumed is the exchange rate underneath Why optimizing acceptance produces low value suggestions, and it is load-bearing: c ≈ 0.3 V, that an unwanted invitation costs the recipient about three tenths of what an accepted connection is worth to the sender.

That single ratio produces the 23% threshold, which the serving path enforces on every request. So it is at once the most consequential estimate in the chapter and the least directly measurable — it is inferred from decline and block behaviour, not observed.

The right way to hold it is that the sign is certain and 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.

A second assumption is the holdout’s: that 0.5% suppression is enough to power a 90-day engagement read despite the graph interference above. With interference the measured effect is attenuated, so the honest reading is a lower bound rather than an estimate.

7. Failure modes

Five ways remain in which a system built exactly as specified still does the wrong thing, and none are bugs. Each has a mechanism, a way to detect it, and a control with a price. Two of them — Rich get richer and Demographic effects and the counterintuitive part — are the label feedback loop of The ranker model label and the training split that earns the auc appearing in production.

7.1 The people the user is deliberately avoiding

The feature set built in Graph features has a limit: a case where every graph feature is confidently, unanimously wrong, and where the fix is a different kind of signal rather than a better feature. A percentile below is the share of candidates that score lower — the 99.9th percentile means only one candidate in a thousand scores higher.

The block below is one candidate’s full feature row. The first four lines are graph features, all near the top of the distribution. The next five lines are not graph features, and they all say the opposite.

viewer U, candidate V

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

every graph feature says: strongest candidate in the entire pool

V is a former spouse. The signature of your closest tie and the signature of the tie you most deliberately severed are the same signature, because the graph is the same in both cases. The graph cannot distinguish them and no better graph feature will, because the information is not in the graph. It is in the behavioral channel:

• explicit unfollow, mute, block, or a previous dismissal
• impressions without action, which is the signal most systems under-use
• an absence of messages that is anomalous given the overlap — 118 common neighbors and zero messages is a strong negative, and a feature you have to think to build

Price the impression decay — how the chance of acting falls each time the same person is shown again:

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

Cross that with the 23% economic threshold from Why optimizing acceptance produces low value suggestions: 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 — a dismissal is a failure that already cost the user attention, and here cost more than attention.

Policy: suppress 90 days after 6 no-action impressions; 180 days after 2 dismissals; permanently after 3. And treat unfollow, mute, and block as hard, symmetric, permanent.

7.2 Dormant accounts

The largest single improvement in the chapter involves no graph modelling at all, and the graph features actively work against it.

Split the candidate pool by when the candidate was last active. The two columns are how much of the pool sits in each bucket and how often those candidates accept. The bottom two rows are 45% of the pool:

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

Now average that last column two ways. First over the whole pool, which is what you get with no liveness signal at all. Then over just the top two rows, renormalized by their combined share — which is what you get by suggesting only recently-active people:

accept-of-sent (diagnostic, section 6.1 base), no activity prior:
   0.34(41) + 0.21(22) + 0.24(6) + 0.21(1.1)  =  20.2

accept-of-sent (diagnostic), restricted to last-active <= 30 d:
   [0.34(41) + 0.21(22)] / 0.55  =  18.56 / 0.55  =  33.7

An activity prior alone raises this diagnostic accept-of-sent from 20.2% to 33.7% — a 67% relative gain — with no graph modelling whatsoever. Forty-five percent of slots were being spent on people who will never see the invitation.

The 20.2% is the counterfactual with the liveness term switched off, which is why it reads so far below the funnel headline. Stacked on the graph and non-graph features, the shipped ranker’s accept-of-sent is the 59.5% of The funnel defined once cited everywhere.

The reason this is easy to miss is a negative correlation in the tail: graph features love dormant accounts. An account registered nine years ago has accumulated connections, so its degree, its common-neighbor counts, and its personalized-PageRank mass are all high.

The graph score and the liveness score therefore point in opposite directions exactly where it matters. That is why P(active in 28 d) has to be an explicit multiplicative term — the ranker’s score gets multiplied by it, so a near-zero liveness sends the whole product to near zero — rather than one feature among two hundred that the trees can average away.

7.3 Rich-get-richer

The feedback loop of The ranker model label and the training split that earns the auc also appears in the graph itself: the recommender does not merely observe that some members are popular, it makes them more so.

The loop:

degree d  ->  higher CN with everyone  ->  higher rank in more slates
          ->  more impressions         ->  more invitations
          ->  more accepts             ->  higher degree

Follow the arithmetic of that loop. P(shown) increases in d, and P(accept | shown) is roughly flat. So dd/dt — the rate at which a member’s degree grows over time — is itself increasing in d. The more connections you have, the faster you gain more.

That is preferential attachment, the standard model of how heavy-tailed networks form. The difference here is that the recommender is the mechanism, rather than a bystander observing the phenomenon.

It is the general feedback loop of ml 07 with one aggravating difference: the quantity being amplified is a property of a person, and it is permanent. A video that gets over-recommended stops being recommended when tastes move. A member whose degree doubled keeps the degree.

How much does that loop actually move? Simulate 12 months under three policies and track the degree Gini, where a rise means connections are concentrating in fewer hands:

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 middle row is worth noting: the degree normalization of Adamic adar and the derivation of the down weight and Jaccard corrects a different thing was chosen for accuracy and turns out to slow the loop as a side effect. It does not stop it. Derive the cap that does, starting from what an equal share of exposure would be:

suggestion slots/day  =  30 M surface loads x 20  =  6 x 10^8
active members        =  4 x 10^8
uniform share         =  1.5 impressions/member/day

cap at 50/day  =  33 x uniform

Fifty per day is thirty-three times an equal share and still bounds the top account at fifty impressions instead of a hundred thousand. A cap that generous costs almost nothing in acceptance and removes the runaway branch, which is the right shape for this kind of control: loose enough to be uncontroversial, tight enough to bound the tail.

Add an explicit new-member reservation — 2 of 20 slots for members with fewer than 10 connections — because the same loop runs in reverse at the bottom and a member with 3 connections generates almost no 2-paths to be found through.

7.4 Demographic effects, and the counterintuitive part

A fairness harm can be located precisely here, and not where most expect. Derive what each stage of the pipeline does to the quantity you care about, rather than asserting the system is biased.

The common claim is “triangle closure amplifies homophily” — homophily being the tendency of people to connect with people like themselves. Derive it properly, because the first half of the derivation says the opposite.

Take a graph with two groups, A and B, where 88% of edges join two members of the same group and 12% cross between them.

Now walk a 2-path u -> w -> v, starting from a u in group A. Two edges get walked, and each one is same-group with probability 0.88 and cross-group with probability 0.12. So there are four cases, and each case’s probability is the product of its two edge probabilities.

The label on the right is whether v ends up in the same group as u, which is what you actually care about. Note the third line: two cross-group edges in a row land you back where you started.

w in A (0.88) and v in A (0.88)   =  0.7744    same group
w in A (0.88) and v in B (0.12)   =  0.1056    cross
w in B (0.12) and v in A (0.12)   =  0.0144    same group
w in B (0.12) and v in B (0.88)   =  0.1056    cross

cross-group share of 2-paths  =  0.2112

The 2-hop candidate pool is 21% cross-group while the existing graph is only 12% cross-group — the pool is nearly twice as diverse as the graph that generated it. A single cross-group tie opens a door into the other group’s whole neighborhood.

Then measure what survives ranking. The pool nearly doubles the graph’s diversity, and then a single stage takes it back:

cross-group share, by funnel stage

existing edges in the graph        12.0 %
2-hop candidate pool               21.1 %      <- the pool is diverse
top-20 ranked slate                 6.4 %      <- ranking removes it
invitations sent                     5.6 %
accepted invitations                 5.1 %

The pool is twice as diverse as the graph and the output is less than half as diverse. The ranker is not neutral; it is a filter that removes diversity the candidate generator had already found. The mechanism is mechanical and requires no demographic feature anywhere in the model: cross-group pairs have less shared context by construction — fewer common neighbors, lower Adamic-Adar, lower personalized-PageRank mass, less workplace overlap — and every feature in Graph features is a measure of shared context.

And because The ranker model label and the training split that earns the auc’s labels come from what the system showed, this narrowing writes itself into the next model’s training data: the cross-group pairs that were ranked out never generate a send, never generate an accept, and so appear to the next model as territory with no evidence in it. That is the label loop closing on a fairness outcome rather than on a popularity one.

That matters more than a fairness dashboard line, because if the network drives referrals and job discovery, the cross-group accept rate is an economic-mobility number wearing a ranking metric’s clothes.

What to do, stated with its cost. pp below means percentage points — the arithmetic difference between two percentages, as distinct from a relative change:

reserve 3 of 20 slots for candidates with below-median shared context

cross-group accepted share   5.1 %  ->  8.9 %    (share of accepts; nearly double)
accept-of-sent              59.5 %  ->  58.4 %   (-1.1 pp; the shipped funnel, §6.1)

A 1.1-point cost in accept-of-sent to nearly double cross-group tie formation. That is a decision a human should make with the number in front of them, not one a loss function should make silently.

Assumptions in this section, and the load-bearing one. The load-bearing assumption belongs to this subsection and is a strong one: that a two-group graph with a single within-group edge probability of 88% is a fair enough model of homophily to reason from.

Real networks have many overlapping groups of unequal size, and the 21.1% cross-group figure would move under any richer model. What survives that objection is the shape of the result, not the digits: the enumeration shows a candidate pool strictly more diverse than the graph that produced it, for the simple reason that one cross-group edge exposes an entire foreign neighborhood. That holds for any within-group probability short of 1. The stage-by-stage funnel below it, by contrast, is measured.

Elsewhere in the section, two smaller assumptions. The people the user is deliberately avoiding assumes that repeated inaction means rejection rather than inattention, which is why its policy escalates gradually rather than suppressing on the first miss. And Rich get richer assumes P(accept | shown) is roughly flat in degree, which is what makes the loop’s growth term depend on exposure alone.

7.5 Summary

Every failure above, compressed to one line each: what goes wrong, why, how you would notice, and what you do about it.

8. Scale numbers

Every figure the chapter derived, in one place, so that any argument can be reconstructed from a single screen.

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 of those 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 the serving architecture is a dirty bitmap and not a pipeline.

9. Alternatives considered and rejected

Fifteen designs a reasonable person would propose, each with the reason it is appealing and the specific number that kills it. Rejecting an option with its price is what separates an answer from an opinion.

10. Interviewer pushback

Twelve questions an interviewer actually asks, each with what it is testing and an answer written the way you would say it out loud.

“How big is the candidate set? Just give me the number.” Testing: whether you can derive rather than hand-wave. For the median member the degree table puts at d = 89 it is about 91,000 distinct people, for the d = 240 member the generator is budgeted at it is about 250,000, and for a member at the 30,000 connection cap it is about 25 million, which is 2.5% of the whole network. The reason it is not d^2 is the friendship paradox: traversing an edge samples nodes in proportion to degree, so the expected degree of a random neighbor is E[d^2]/E[d] = E[d] + Var/E[d], which for this graph is 4,110 against a mean degree of 316 — a factor of 13. Globally, sum_w C(d_w,2) is about 6.5 x 10^14 candidate pairs against 1.6 x 10^11 edges, and the ratio is exactly that same 4,110. So P(edge | candidate pair) is around 10^-4, which makes generation an extreme-imbalance retrieval problem before it is a ranking problem. I would keep that conditioning visible, because the accept ranker’s own prior is a different population entirely — its label is accept-within-14-days-of-send, so it lives on sent invitations at a 59.5% positive rate, and de-sampling it against 10^-4 is how you build an economic gate that rejects everything.

“So how do you make that tractable?” Testing: whether the arithmetic produces the design. Cap the degree of the intermediate node. E[d^2] is dominated by its tail — the top 0.6% of nodes contribute 74% of it — so skipping intermediates above degree 1,000 cuts the candidate space 23x while touching 6% of nodes. And the evidence lost is close to nothing: under the configuration-model null, a common neighbor contributes to the null expectation in proportion to d_w^2, so a degree-2,100 intermediate carries about one four-millionth of the evidence a degree-1 intermediate does. The nodes that generate the most candidates are the nodes whose candidates are worth the least, which is why this is the cheapest 23x in the whole design. Then sample 200 neighbors per intermediate, cheap-score the ~30,000 survivors down to 5,000 on CN, RA, and an activity prior, and run the real ranker on those.

“Why Adamic-Adar rather than just counting common neighbors?” Testing: whether you can derive a weighting or only name it. Because counting says that three shared ties from a twelve-person team and three shared celebrity follows are the same evidence, and they are not. Adamic-Adar weights each shared neighbor by 1/log(d_w), which comes from an information argument — a shared feature that everyone has is uninformative, so weight by inverse frequency, softened by a log. But I would push back on Adamic-Adar being the default. Across degrees from 5 to 30,000, counting applies a 1x discount, AA applies 6.4x, resource allocation’s 1/d_w applies 6,000x, and the configuration-model null — where w’s contribution to the expected common-neighbor count scales as d_w^2 — says the right answer is nearer 36 million. On a concrete pair, AA rates two candidates 3.2x apart where RA rates them 619x apart, and 619x is closer to the truth. AA is an IDF, not a null correction, and on a heavy-tailed graph I would ship RA.

“Give me a case where the model is right and you still cannot show the suggestion.” Testing: whether privacy is a mechanism or a disclaimer. A therapist imports her phone contacts, which contain 300 patients. Every pair of her patients now shares a common neighbor whose degree in that provenance channel is 300 — small enough that AA and RA both rate her a strong intermediate — and they are geographically co-located. The ranker scores patient A against patient B highly and suggests them to each other. The prediction is correct: they genuinely do have a person in common. Surfacing it discloses that both are seeing the same therapist, a fact neither disclosed, inferred from a third party’s phone.

This is not a false positive that a better model fixes. It is a true positive that must never be generated — and I would state the bound the code actually delivers rather than the word “never”, because those are not the same sentence. What the gate guarantees is: no candidate is generated when every common neighbour supporting it sits in a flagged category and there is no justifying source outside that witness set. A two-therapist practice is still dropped, and a three-hundred-patient list is still dropped, because sensitivity does not dilute with witness count. What it does not cover is a pair who also share one ordinary mutual connection — there the card is explainable without naming the clinic, and the system shows it. That is a real limit and it belongs in the answer.

The control is provenance, and it has two halves that are easy to ship as one.

Half one is a computation at generation time. For each candidate, look at every common neighbor supporting it, and flag the candidate when all of them sit in a sensitivity-flagged category — and separately when all of them are common neighbors only because a third party’s address book made them one. Carol answers yes to both for every pair of her patients. Without that computation the gate is a rule keyed on a bit nobody ever sets.

Half two is the gate itself. One-way contact evidence is directional, so a candidate with no other justifying source is never generated. That has to be a mask test rather than provenance == CONTACT_THEIRS, because an equality test on a bitmask is defeated by ORing in any other bit — including the sensitivity flag, which is not a source and justifies nothing.

Then, where the flagged-category bit is set, I require a second independent source from outside the witness set before the candidate exists at all. I deliberately do not let a second witness satisfy that, because a second therapist in the same practice makes the inference stronger, not weaker. The address-book bit is the one where a second witness genuinely does cure it.

And I gate at generation, not at ranking, because anything that reaches the ranker leaks through ordering, and a retrained model learns around a soft penalty.

“Why not just require two common neighbors everywhere? Cleaner rule.” Testing: whether you price your own proposals. Because 62% of the pool has exactly one common neighbor and it converts at 3.1%, which is 30% of all accepted invitations. A global CN >= 2 rule costs nearly a third of the product. Applied narrowly — only where the lone common neighbor’s evidence is contact-import-only or sensitivity-flagged — it touches 4.1% of the pool and 1.2% of accepts. Same mechanism, thirtieth of the cost, and the difference between the two versions is entirely in whether you measured before you shipped.

“What about co-location? It seems like great signal.” Testing: whether you can reason about a signal’s structure. I would reject it, and the argument is that its precision and its harm are literally the same quantity. P(acquainted | co-located) goes roughly as k/n in the number of people simultaneously at the venue: an airport terminal at 8,000 people gives you precision around 0.001, an office floor at 300 gives 0.05, a twelve-person conference room gives 0.6, a six-person clinic waiting room gives 0.7. So the co-locations with usable precision are exactly the small private venues — clinics, courthouses, shelters, places of worship, support meetings — and the identity of those venues is the sensitive attribute. You cannot tune a threshold to keep the precision and drop the harm, because they are the same number. Coarse self-declared city stays, as a filter on candidates generated some other way.

“Precompute or compute online?” Testing: whether you can size both and find the third answer. Neither purely. Online means one adjacency fetch per connection — 89 at the median, 240 at the member the budget is sized for — and at a 5 ms p99 per fetch, 0.995^89 = 0.64 and 0.995^240 = 0.30, so 36 to 70% of requests contain a straggler and latency is the max, not the mean. Nightly precompute is only 9.6 TB replicated, so storage is not the issue — freshness is. Accept rate is 24.1% within an hour of the triggering graph event and 6.8% after a week, a 3.5x premium that nightly forfeits entirely. So: precompute the base, but invalidate on graph events and recompute lazily. A new edge dirties d_u + d_v members, which is 6.3 x 10^10 marks a day, 731 k/s — but only about 3% of members load a PYMK surface on a given day, so the actual recompute demand is 30 M/day, 347/s, roughly 70 cores. Invalidation turns a 731,000-per-second problem into a 347-per-second problem, and the whole trick is a 125 MB dirty bitmap. Then escalate eagerly on the ~93/s of high-value triggers — job change, contact import, accepted invitation — because that is where the 3.5x lives.

“Where do your training labels come from?” Testing: whether you notice that the label is produced by the system you are replacing. The label is accept within 14 days of send, but the important half of the answer is what has to happen before that label exists at all. A connection that was never suggested cannot be sent, and one that was never sent cannot be accepted — so every labelled row required the generator to propose the pair, the ranker to put it in one of twenty slots, and the viewer to act. All three are decisions made by the deployed system, which means the training set is a sample of what last week’s model liked, not a sample of the world.

Pairs it ranked low are not negatives, they are absent, and a model fitted only to what is present learns that its predecessor was right about everything it never showed. That is a ratchet, and the degree concentration and cross-group narrowing I would flag as failure modes are what it looks like from the outside.

Three things follow. Half my negatives are hard — shown and declined, which teach the current boundary — and half are easy, random admissible second-degree pairs nobody was ever shown, which are the only rows in the set not conditioned on a previous model’s opinion. I keep a permanent 0.5% suppression holdout, because it is the one population the loop never touched and therefore the only place an incremental effect can be measured. And I split on time rather than at random, both because the graph is temporal and because a random split lets a future edge into a common-neighbour count and reads near 1.0 offline before collapsing in production.

“Acceptance rate is up 8%. Good launch?” Testing: whether you interrogate the primary metric. Not on its own, because acceptance is gameable in three separate directions. It rewards accounts that accept everything — a 24,000-connection account with an accept-all policy sits at 0.94 against a 0.60 baseline, so ranking on acceptance puts it near the top of every slate on the platform and feeds the degree-concentration loop. It rewards the already-obvious, like your current desk neighbor, where the accept rate is 0.95 and the incremental value is zero because that connection was happening anyway. And it prices the recipient at zero: at 4.2% send and 59.5% accept, we generate 10.2 million declined or ignored invitations a day, and if an unwanted invite costs about 0.3 of what an accepted connection is worth, the break-even acceptance probability is 0.3/1.3 = 23% — below which a suggestion is net negative. So I would want the 90-day engagement lift measured against a suppression holdout, the decline and “I do not know this person” rates as independent blockers, and degree Gini on the health tier.

“Your suggestions are less diverse than the network. Is that the model’s fault?” Testing: whether you can locate a fairness effect mechanically. It is, and the interesting part is that the candidate generator is innocent. For a graph with 12% cross-group edges, work out the 2-paths: 0.88 x 0.12 + 0.12 x 0.88 = 21.1% of 2-paths are cross-group, so the candidate pool is nearly twice as diverse as the graph that produced it — one cross-group tie opens a door to that whole neighborhood. But the top-20 slate is 6.4% cross-group and accepted invitations are 5.1%. The ranker removes the diversity the generator found, and it does so with no demographic feature anywhere in the model, because every feature I have — common neighbors, Adamic-Adar, PPR mass, workplace overlap — is a measure of shared context, and cross-group pairs have less shared context by construction. If I reserve 3 of 20 slots for below-median shared context, cross-group accepts go from 5.1% to 8.9% and overall acceptance drops 1.1 points. That is a trade a human should make with the number visible, and my job is to produce the number.

“It keeps suggesting my ex. Fix it.” Testing: whether you know when the answer is not in the model. No graph feature will fix it, because a severed tie and a closest tie have identical graph signatures — 118 common neighbors, Adamic-Adar at the 99.9th percentile, rank 1 of 247,000 by personalized PageRank. The information is not in the graph. It is in the behavioral channel: an unfollow 14 months ago, zero messages ever despite 118 common connections, which is a strongly anomalous absence, and nine impressions in six weeks with no action. That last one is the underused signal — P(invite) goes 4.2%, 2.8%, 1.9%, 0.9%, 0.4%, 0.3% across impressions one through twelve, so by the fifth impression the expected value is below the slot’s opportunity cost. The system should stop showing someone long before the user has to dismiss them, because a dismissal is a failure that already cost the user something, and in this specific case it cost them considerably more than a slot.

“What is the single highest-leverage thing you would ship first?” Testing: whether your analysis produces a priority. The activity prior. Forty-five percent of the candidate pool has not been active in 30 days and converts at 6% or 1.1%; restricting to last-active within 30 days raises the diagnostic accept-of-sent (the The funnel defined once cited everywhere base, liveness term off) from 20.2 to 33.7, a 67% relative gain with no graph modelling at all, before the graph and non-graph features carry the shipped ranker to 59.5%. It is easy to miss because graph features actively prefer dormant accounts — a nine-year-old account has accumulated connections, so its degree, CN counts, and PPR mass are all high — which means the graph score and the liveness score point in opposite directions exactly in the tail that matters. That is why P(active in 28 days) belongs as an explicit multiplicative term rather than as one feature among two hundred, where the model will happily average it away.

Next: the classic system design track (lands in a later batch).