People You May Know: graph features and two-hop candidate generation

The features that matter here belong to pairs, not to people, and the good ones all come from one idea: shared connections mean more when the sharer is selective.

The same structural fact that produces the best features also makes the problem computable. 900 million members give roughly 4 × 10¹⁷ possible pairs, and scoring even a millionth of them is not affordable. This lesson covers the features first and then the candidate generation they make possible.

The two-hop neighbourhood

Almost every real connection is between two people who already share at least one connection. That single empirical regularity organises the whole system.

Common neighbours, and why raw counts are wrong

The naive feature is the count of mutual connections. Its flaw is that it treats every shared connection as equal evidence.

Consider two pairs on Beacon:

• Pair 1 shares 3 mutual connections. All three are people with 40 connections each.
• Pair 2 shares 3 mutual connections. All three are recruiters with 25,000 connections each.

Raw count says these are equally likely. They are not remotely. Sharing a connection with a highly selective person is strong evidence you move in the same circle; sharing one with someone who connects to everybody is almost no evidence at all.

Adamic–Adar and Jaccard

Two standard measures that fix this in different ways.

Adamic–Adar weights each shared connection by the inverse logarithm of that connection's own degree:

AA(u, v) = Σ over shared connections w of  1 / log(degree(w))

The logarithm makes the penalty gentle rather than brutal. Work the example:

• Pair 1: three shared connections with degree 40 each. log(40) ≈ 3.69, so each contributes 1/3.69 = 0.271. AA = 0.813.
• Pair 2: three shared connections with degree 25,000 each. log(25,000) ≈ 10.13, so each contributes 1/10.13 = 0.099. AA = 0.296.

Pair 1 scores about 2.7 times higher on identical raw counts. That is the correction, and it is usually the strongest single feature in the model.

Jaccard similarity normalises by the size of the two neighbourhoods:

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

It answers a different question: what fraction of these two people's worlds overlap? Three mutual connections between two people who each have 20 connections is a very high overlap; three between two people who each have 5,000 is negligible.

The two are complementary. Adamic–Adar corrects for the shared connections' selectivity; Jaccard corrects for the endpoints' connectivity. Use both.

A third worth naming: preferential attachment, the product of the two degrees, which captures that highly-connected people connect more. It is a useful feature and a dangerous objective, since optimising it concentrates suggestions on people who already have the most connections.

Attribute and context features

Graph structure is not everything, and it is useless for new members.

Overlapping employment dates at the same employer deserves emphasis: "we both worked at the same company at the same time" is far stronger than "we both worked there", and computing the date overlap rather than the employer match is a cheap, large improvement.

Profile views are among the strongest behavioural signals and among the most sensitive. If A viewed B's profile, suggesting B to A is helpful. Suggesting A to B may disclose that A was looking — which some products deliberately do and others deliberately do not. Decide it explicitly; it is a product and privacy decision, not a modelling one.

Candidate generation: the reduction

The combinatorial problem, stated plainly: 900 million members give roughly 4 × 10¹⁷ possible pairs. Scoring even a millionth of them is not affordable.

The two-hop restriction does the work:

From 4 × 10¹⁷ to 500. Almost all of the reduction comes from one structural observation about how social graphs grow, which is why the graph features lesson spent so long on it.

Computing the two-hop set efficiently

The naive approach — for each of a member's 180 connections, fetch their connections and union — is 180 lookups returning 180 lists each. At 900 million members computed daily, that is a very large amount of graph traversal.

Four techniques, and naming the supernode problem is the important one:

1. Batch it. Compute two-hop neighbourhoods in a scheduled distributed job rather than per request. The graph changes slowly relative to how often suggestions are viewed — 40 million new connections a day against 900 million members is under 5% of members changing per day — so a daily recomputation with incremental updates for members whose neighbourhood changed is sufficient.

2. Cap the expansion through high-degree nodes. This is the essential trick.

A member connected to one recruiter with 25,000 connections has, through that node alone, 25,000 candidates. A member connected to five such nodes has over 100,000, and the two-hop set becomes useless — it now contains everyone, and the mutual-connection signal through those nodes is worthless anyway, which is exactly what Adamic–Adar told us.

The fix: when expanding, skip nodes above a degree threshold — say 5,000 — or sample a bounded number of their connections. Both bound the work and remove candidates whose evidential value was near zero. Two problems solved by one rule, and it is the answer an interviewer is listening for when they ask "what about someone with 30,000 connections?"

3. Bound the candidate set per member. Take the top N by cheap score rather than the full set. Members with very large neighbourhoods get truncated, and the truncation is by evidence strength, so little is lost.

4. Cheap pre-scoring before the model. Rank the ~9,000 by Adamic–Adar plus two or three other cheap features, and pass the top 500 to the full model. This is the two-stage pattern from Step 6: serving with a hand-built retrieval stage rather than a learned one — appropriate, because the graph features that matter are computable directly and there is nothing an embedding would add at this stage.

The graph storage question

Which is a System Design Interview problem surfacing inside an ML one:

• Adjacency lists in a key-value store, keyed by member ID, holding the connection list. Fast single-hop reads; two-hop requires application-level fan-out.
• A graph database, which makes traversals natural at the cost of harder horizontal scaling at this size.
• Precomputed two-hop sets, materialised in batch and stored per member. Fast reads, stale by up to a day, and large — 900 million members × ~9,000 candidates is a substantial store, so in practice you store the truncated top few hundred with their scores.

Recommendation: adjacency lists in a partitioned key-value store as the source of truth, with precomputed truncated candidate sets refreshed daily and incrementally updated for members whose neighbourhood changed. Partition by member ID, and accept that a two-hop traversal crosses partitions — which is the standard cost of sharding a graph, and worth acknowledging rather than glossing over.

The new-member path

A member who joined an hour ago has an empty two-hop set, and the whole pipeline above returns nothing.

Their candidate set has to come from elsewhere:

• Address-book matches, if uploaded and permitted. The strongest signal available, and it requires explicit consent.
• Attribute matches — current employer, most recent employer with overlapping dates, university with overlapping years, city.
• Registration context — how they arrived. An invitation link from an existing member identifies at least one real relationship and, through it, a partial two-hop set.
• Reverse suggestion. Suggest the new member to established members who match strongly. This is often more effective than suggesting to them, because the established member recognises the name and the new member has no basis to recognise anyone.

That last one is the non-obvious answer and a good one to offer. It also needs the guard from the metrics lesson: suggesting one new member to very many established members is exactly the volume problem, so cap it.