Design a “People You May Know” feature for LinkedIn using graph neural networks for link prediction over the professional social graph. Given a member and the current graph of connections, the system must recommend people the member likely knows and would connect with, ranking millions of candidates by connection probability.
The graph is massive (hundreds of millions of nodes, billions of edges), sparse for most members, and rich with side features: company, school, job title, location, co-workers, co-alumni. A GNN can propagate information along edges to capture multi-hop structure that simple heuristics (mutual friends, same company) miss, but it must scale to the full graph and stay useful as new connections form every second.
How would you design this model? Cover the candidate GNN architectures (GraphSAGE vs GAT vs PinSage-style random-walk plus convolution), how you handle negative sampling and class imbalance, how you scale training and inference to a graph with hundreds of millions of nodes, how you incorporate node side features, and how you keep recommendations fresh as the graph evolves.
The Problem: a member has a few dozen links inside a graph of hundreds of millions of people, so the model must find the handful of real-world acquaintances hiding in an ocean of strangers.
Answer
The model is a two-layer inductive GraphSAGE encoder trained as a link predictor: for each pair, sample a fixed-fanout neighborhood, aggregate side features along the sampled edges into a 256-dimensional embedding, and score the pair with a dot product. Fixed fanout is the pivotal decision because it makes cost per candidate independent of degree, which matters on a graph where recruiters carry tens of thousands of edges. The second pivotal decision is the negative sampling mixture: random negatives alone make the task trivially easy at a positive rate near 
, so training mixes in hard two-hop negatives (people who share a company or mutual connections but never connected). Attention is added surgically as a last-layer GAT head on high-degree neighborhoods rather than everywhere, and side features enter as the layer-zero representation so a brand-new member gets an embedding without retraining.
(1) GraphSAGE (chosen encoder): uniform neighbor sampling with fanout 
and mean or pooling aggregation, inductive by construction because weights act on features rather than node IDs.
(2) GAT (selective upgrade): learned per-edge attention softmax over neighbors, which can down-weight a recruiter or hiring-manager edge that mean aggregation blends into the signal.
(3) PinSage-style random walk plus convolution: neighborhoods defined by random-walk visit counts instead of the raw adjacency, giving importance weights and a hub-resistant top-T neighbor set.
(4) Heuristic and shallow baselines: common neighbors, Adamic-Adar, and matrix factorization set the accuracy floor the GNN must beat, and remain the cheap candidate generator that feeds it.
Figure 1: One shared encoder, two sampled neighborhoods, one dot product: the whole model is a siamese GNN over a bounded receptive field.
Clarify Before Designing:
(1) Label definition: is a positive an invitation sent, an invitation accepted, or a “we actually know each other” signal, and are dismissals usable as negatives?
(2) Inductive requirement: must a member who joined ten minutes ago and has zero edges get an embedding, or may cold-start fall back to a feature-only model?
(3) Freshness budget: how stale may an embedding be after a new connection forms, minutes or a full day?
(4) Compute and storage budget: how many GPUs for training, and can we store 
embeddings in a serving store?
(5) Graph heterogeneity: do we get typed edges (co-worker, co-alumnus, message, profile view) and reliable side features for all members, or only for complete profiles?
(6) Candidate volume per request: does the GNN score millions of pairs, or a pre-filtered two-hop pool of a few thousand?
Leave a Reply