Design People You May Know

The ask

The service shows a list of suggested people on a social app.

A good suggestion is someone the user knows in life and would welcome as a connection.

The first questions fix the evidence allowed. Work, school, place and shared friends are the usual sources.

A suggestion must never fight a block. Blocked or removed people stay out, whatever the score.

Estimate the scale

The service has 2,000,000,000 users. The average user has 300 friends.

2,000,000,000 users × 300 friends = 600,000,000,000 counted friendships.

Each friendship joins two people, so that count names every friendship twice. 600,000,000,000 ÷ 2 = 300,000,000,000 friendship edges counted once.

Suggestions are recomputed once a day for every user.

2,000,000,000 computations ÷ 86,400 seconds = 23,148 computations per second.

That steady offline rate replaces a graph search at request time.

Data and features

Link prediction is the task of guessing which unconnected pairs are likely to connect.

The friendship graph is the main data source. Graph search over it finds the pairs worth scoring.

Features describe the pair. Mutual friends, shared school or work, and shared place are the core facts.

Labels come from suggestions already shown. An accepted suggestion is a positive label, and a dismissed one is a negative.

Features must respect privacy settings. A fact a user has hidden is not a feature, whatever it would add.

High-level design

A daily job walks the graph for every user and gathers candidate pairs.

Candidates come mostly from friends of friends. Shared groups and shared places add smaller streams.

Hard filters remove existing friends, blocked people and the user.

The ranking model orders the pairs, and the top suggestions are stored per user.

The design stores the top 20 suggestions for each user. 2,000,000,000 users × 20 suggestions = 40,000,000,000 stored suggestions.

Training the model

Training examples are past suggestions with known outcomes. Accepted suggestions are positives, and dismissed ones are negatives.

Only shown suggestions leave outcomes. Unexplored pairs stay unknown, not negative.

Features are frozen as they stood when the suggestion was shown. Later friendships must not leak into old examples.

The model retrains as new outcomes land. Graph features refresh with the daily recompute.

Accepted suggestions are rare beside dismissals. Training weighs the positives so the model does not learn to dismiss everyone.

Serving predictions

Serving reads the stored suggestions for the user. No graph walk happens at request time.

A cache holds the stored lists for fast reads.

New friendships update suggestions between daily runs. A just-added friend leaves the list at once.

Blocks and removals apply at serving time too. A stored suggestion can go stale within a day.

An empty list is acceptable. A short honest list beats a full list of strangers.

Deep dive: friends of friends

At the average, one user has 300 friends. Each of those friends has 300 friends of their own.

300 friends × 300 friends each = 90,000 friends of friends at most.

Duplicates fill that bound. The same person appears through many mutual friends.

2,000,000,000 users × 90,000 candidates = 180,000,000,000,000 candidate checks at the bound. No design scores all of them raw.

Counting mutual friends prunes first. Pairs below a small shared count are dropped before scoring.

Mutual friend count is also the strongest single feature. The pruning count and the ranking feature are the same fact used twice.

Deep dive: unwanted suggestions

A correct guess can still be unwelcome. Some connections carry history the graph cannot see.

A former partner can be predicted well and still cause real distress.

Dismissals are collected with a reason where one is offered. A not-again signal for a pair is permanent.

Sensitive sources stay out of features. Viewing a profile often must not by itself create a suggestion.

Some accounts are excluded by product rule, whatever the score.

Evaluation and trade-offs

Offline tests hide known friendships and check whether scoring finds them. A found hidden friendship counts as a hit.

Offline success flatters the model. Hidden friendships are the easy pairs, since they formed already.

Online experiments compare acceptance and dismissal rates on a small share of users. Blocks and reports count as hard failures.

Long-term value matters more than fast accepts. Suggestions that end in removal weeks later were bad suggestions.

The trade-off is reach against restraint. Scoring more pairs finds more real friends and more unwelcome names.

The graph in numbers