People You May Know ranks a person, so a heavy-tailed graph, a two-sided cost, and a third party whose evidence you hold decide the design before the ranker does.
The funnel (one hub, one impression)
~25 M reachable 2-hop -> ~30 k generated -> 5 k cheap-scored -> 20 shown
- 2-hop / FoF is the candidate source: 60-80% of new edges close a triangle.
- Generation is retrieval; ranking is classification. They live on different populations, so never share a threshold.
The three “accept rates” (differ up to 25x)
| Name | Definition | Value | Population |
|---|
| retrieval base rate | P(edge | candidate pair) | 2.5e-4 | all candidate pairs |
| send rate | P(send | impression) | 4.2% | impressions |
| accept-per-impression | send × accept-of-sent | 2.5% | impressions (primary metric) |
| accept-of-sent | P(accept | sent) | 59.5% | sent invites (ranker’s prior + gate) |
- Per 100 impressions: 4.2 sent, 2.5 accepted, 0.31 sustained tie, 1.7 declined/ignored (a cost on someone else).
The friendship paradox sizes the pool
- A random neighbor’s expected degree is
E[d^2]/E[d] = E[d] + Var(d)/E[d], not E[d]: popular people are over-represented among those you reach by an edge.
- Numbers:
E[d]=316, median 89, E[d^2]=1.3e6, paradox mean 4,110 (13x the mean). Top 0.6% of nodes = 74% of E[d^2].
- Candidate pairs
≈ N·E[d^2]/2 = 6.5e14 = 4,110x the edge set (1.6e11).
- Degree cap: skip any intermediate with
d > 1,000. Skipping = 23.5x fewer pairs (95.7% of work); min-capping only 11.2x. Quote the one you ship.
- Generate with the cap; score without it (cap is a generation rule, not a feature def, or a candidate from another generator reaches the ranker with
CN=0).
Weighting a shared connection by rarity
Discount each common neighbor w by its degree d_w. Textbook Adamic-Adar is too gentle on a heavy tail.
| Weighting | Formula | Discount over 6,000x degree range | AUC |
|---|
| Common neighbors | count, no weight | 1x | 0.78 |
| Jaccard | |N∩N|/|N∪N| (normalizes endpoints) | orthogonal to AA | 0.81 |
| Adamic-Adar (AA) | Σ 1/log(d_w) | 6.4x | 0.84 |
| Resource allocation (RA) | Σ 1/d_w | 6,000x | 0.86 |
| Null (configuration model) | 1/d_w^2 | 3.6e7x | — |
- Use RA on a heavy tail, AA only when degree variance is mild.
- PPR (restart prob
alpha): best single feature, AUC 0.88; Monte Carlo, 2,000 walks/source; a node hit 3/2,000 has 1/sqrt(3)=58% error, so use bucketed, not continuous.
- node2vec: 0.8 params/edge forces low-rank smoothing (keeps communities, drops the single path). Its job is reach — the ~15% of good candidates with no common neighbor. AUC 0.83.
- All graph features: AUC 0.91 (they correlate 0.7-0.9); + non-graph: 0.945. Spend effort beyond the graph.
- Every AUC is a temporal split, de-sampled, 14-day label. A random shuffle leaks future edges, reads ~1.0 offline, collapses online.
The label loop (its own worst problem)
- Label = accept within 14 days of send, manufactured by last week’s model, plus a deliberate sample of never-shown pairs.
- Only pairs the old system showed have a label; low-ranked pairs are absent, not negative — a ratchet.
- Negatives are constructed: half hard (shown + declined), half easy (random admissible 2-hop, never shown — the only view of ignored territory).
- Correct the 20:1 over-sampling: de-sample (Elkan,
beta≈29.4, monotone → order survives) then isotonic calibration (staircase, never decreases). Needed because half the negatives aren’t from the serving population.
- Value tier needs a permanent 0.5% suppression holdout — the only population the loop never touched; “connections formed” is otherwise unattributable.
Privacy is a generation constraint, not an output filter
- Ordering leaks (a suppressed card still moved everything below it) and soft penalties become training data. Gate before scoring.
- The hard case is a true positive that must not be shown: two therapy patients share the therapist as a strong common neighbor — correct inference, forbidden disclosure. Model quality never fixes it; a provenance rule does.
- Address-book asymmetry: Alice imports Bob → surfacing Alice to Bob reveals Alice has Bob’s number. One-way evidence is generated only for the importer.
- Co-location rejected: precision
~k/n, so the only usable venues (n~6-12: clinic, shelter) are exactly the sensitive ones — value and harm are the same number.
- Gate logic: test sources as a mask (never
prov == CONTACT_THEIRS); a 2nd witness cures contact-manufactured evidence but not a flagged sensitive category (that needs a justifying source outside the witness set).
Serving: invalidate eagerly, recompute lazily
- A new edge stales
d_u+d_v ≈ 632 members. Stale marks 731 k/s vs reads 347/s — a 2,100x gap (only ~3% of members open PYMK/day).
- Dirty bitmap: 1 bit/member = 125 MB on one host. Lazy recompute on surface load if dirty; eager on high-value triggers (job change, contact import, accepted invite — next hour worth 3.5x); 30-day floor.
- Full online loses to the fan-in straggler (
0.995^240=0.30); full nightly forfeits the 3.5x freshness premium.
Failure modes
| Failure | Mechanism | Control |
|---|
| Deliberately avoided person | Severed and closest ties have identical graph signatures | Behavioral channel: impressions-without-action, unfollow/block as hard symmetric filters |
| Dormant account | Graph features grow with account age, not liveness | Multiplicative P(active 28 d), kept outside the ranker (lifts 20.2%→33.7%) |
| Rich-get-richer | P(shown) rises with d, permanently | RA/Jaccard normalization + 50/day exposure cap + new-member reservation |
| Cross-group narrowing | Every feature measures shared context, which cross-group pairs have less of | Pool is 21% cross vs 12% graph but slate 6.4%; reserve 3/20 slots (5.1%→8.9%, cost -1.1pp) |
- Economic gate: unwanted invite costs
c≈0.3V, so break-even p* = c/(V+c) = 0.3/1.3 = **0.23**. Drop predicted-accept below 23% (applied after calibration). Sign certain, value not.
Ranker
- GBDT: ~400 trees, depth 8. Chosen over a deep net — features are engineered, sharply non-linear/interaction-heavy, retrains daily. node2vec sits upstream as a generator, not inside.
- Every feature computed as of generation time — a post-hoc common-neighbor count contains the edge being predicted (temporal leak).