A node that joined ten seconds ago has no neighbours. That is not a hard case for the standard link-prediction heuristics — it is a case where every one of them returns exactly zero for every candidate, and a ranking of identical zeros is not a ranking.
The scores are not low, they are zero
The classical heuristics all score a candidate pair (u, v) from the overlap of their neighbourhoods. Write Γ(u) for the neighbour set of u. For a new node, Γ(u) is empty, and the consequence is immediate:
common neighbours |G(u) ∩ G(v)| = |{}| = 0
Jaccard |G(u) ∩ G(v)| / |G(u) ∪ G(v)| = 0 / |G(v)| = 0
Adamic-Adar sum over w in G(u) ∩ G(v) of
1 / log|G(w)| = empty sum = 0
preferential att. |G(u)| x |G(v)| = 0 x |G(v)| = 0
personalised
PageRank from u random walk from u = no walk exists
Every candidate v in the graph gets the same score. There is no tie to break, because there is no information in the topology to break it with. Adamic–Adar does not degrade gracefully here; it degrades to a constant. Recognising this changes what you go looking for: the fix is not a better topological score, it is a different input.
The same reasoning applies to a node with one or two edges, which is the far more common case. The scores are no longer identically zero but they are computed from a sample of size one, so their variance swamps their signal. Any system that serves a stream of new entities spends most of its time in this regime, not in the well-connected one the literature is usually evaluated on.
The embedding table has no row either
The obvious upgrade is a learned embedding, but the popular ones are transductive: they learn one vector per node id, as a lookup table, by optimising over walks or over the observed adjacency matrix. Under node2vec and DeepWalk the training signal for a node’s vector is the set of walks that pass through it. A node with no edges is in no walks, so it has no gradient, and its row is whatever the initialiser put there — random noise dressed as an embedding.
Matrix-factorisation recommenders have the same shape of problem: the new node is a row of zeros in the interaction matrix, and the factor model has nothing to reconstruct. Neither family can be fixed by retraining faster. They can only produce a vector for a node after that node has produced edges, and the whole difficulty is the window before that happens.
Encoding attributes instead of topology
The working approach replaces the lookup with a function. Instead of learning a vector per id, learn an encoder that maps a node’s attributes to a vector: profile fields, text, category, registration metadata, whatever exists at creation time. At inference a node that has never been seen still has attributes, so the encoder still produces an embedding.
train on warm nodes:
z_u = encoder(attributes(u)) # shared weights, no per-node table
z_v = encoder(attributes(v))
loss = -log sigma(z_u . z_v) # observed edge -> high score
-log sigma(-z_u . z_neg) # sampled non-edge -> low score
serve a cold node:
z_new = encoder(attributes(new)) # works, nothing was memorised
rank candidates by z_new . z_v
This is why GraphSAGE, from Hamilton, Ying and Leskovec (NeurIPS 2017), is described as inductive: its aggregators are functions of features, so a node absent at training time gets an embedding at inference from its features and whatever neighbours it has — including none. The paper’s framing is generating embeddings for unseen nodes, and that property, not the sampling, is what matters for cold start.
Two practical requirements follow, and both are easy to violate. First, the attributes must be present at creation time. Training an encoder on fields that are only populated after a week of activity produces a model that scores beautifully offline and receives nulls in production. Audit which columns are non-null at t = 0 before you choose the feature set. Second, the encoder must be trained against the objective you serve. An encoder fitted to reconstruct attributes learns an attribute space; you want one fitted to predict edges, so the loss has to involve edges even though the input does not.
Getting cold and warm into one space
A hybrid system usually ends up with two encoders: a strong topology-based one for warm nodes and an attribute-only one for cold nodes. If they are trained separately their outputs live in different spaces, and a dot product between a cold vector and a warm vector is meaningless — similar in the same sense two unrelated random projections are similar. The scores are not comparable, so the ranked list interleaves them arbitrarily.
Two ways out. Train one model with feature dropout: randomly zero the neighbourhood input for a fraction of training examples, so the same encoder learns to produce a usable embedding with and without topology. The cold case is then just the extreme of a distribution it was trained across, rather than an out-of-distribution input. Or distil: train the topological embedding first, then fit the attribute encoder to regress onto it, so the attribute encoder’s output is by construction in the same space. The distillation route is easier to bolt onto an existing system and caps cold-node quality at how predictable the topology is from attributes, which is worth measuring before committing.
Alongside either, keep an explicit exploration budget. A pure exploitation ranker sends every cold node the globally popular candidates, those candidates accumulate more edges, and the popularity signal reinforces itself — the classic feedback loop, in which the system stops learning anything about the long tail because it never shows it. Reserving a small fraction of slots for uncertain candidates is what generates the edges the next model needs.
The split that makes it measurable
Cold-start evaluation is where most reported numbers go wrong, and the mistake is always the same shape: an edge-level random split.
Hold out 10% of edges at random and every node in the test set almost certainly still appears in the training set, with its other edges intact. Your model saw that node, learned its embedding, and is now asked about one more of its edges. That measures warm-node link prediction. It is a legitimate metric and it is not the one you are claiming.
- Split by node, not by edge. Choose a set of nodes, remove them and all of their edges from training, and evaluate only on those nodes. Now the test node genuinely has no training topology.
- Split by time where the data allows. Train on everything before a cutoff and evaluate on nodes that first appear after it. This is the only split that reproduces the production condition, including the fact that the attribute distribution drifts.
- Report warm and cold separately. Pooled, a strong warm result hides a cold result no better than popularity ranking. Two numbers, always.
- Include the popularity baseline. Rank every candidate by global degree, ignore the new node entirely, and report that score next to the model’s. A surprising number of cold-start systems do not beat it, and finding that out early is cheap.
- Sample negatives from a plausible candidate pool. Uniform negatives from all nodes are trivially separable and inflate every metric. Sample from the set the ranker would actually consider.
Top comments (0)