Teaching Cold-Start Link Prediction Which Context a Link Belongs To

When a new node joins a network with a profile but no connections, such as a new paper, a new researcher, or a new user, any system that recommends its first links has to guess from the profile alone. Current approaches learn one mapping from a node's features to a single vector and then score candidate partners by proximity. Real nodes have several distinct roles, though. A researcher publishes in networking and in databases, and the word "routing" in their abstract means a great deal for one set of collaborators and nothing for the other. Link-based community detection, which groups the edges of a graph rather than its nodes on the view that a node has many identities while a single interaction usually has one, gives exactly the missing signal. Each existing edge can be labelled with the one context it lives in. This proposal uses those edge labels, computed offline on the warm part of the graph, to supervise a content-only model. The model learns to predict both whether a cold node will link to a candidate and which context that link would belong to.

The core claim is concrete. A cold-start link predictor is trained with an extra loss that forces its internal "which community explains this pair" posterior to match a link-community teacher on observed edges. We claim this model will beat both single-vector content models and mixture models whose contexts are learned without that teacher. We further claim the gain will concentrate on cold nodes whose true future links span several contexts. The link-community algorithm never has to see the cold node. This matters because line-graph and edge-generative methods cannot represent a node with no edges at all.

What exists and what is missing

Three pieces of prior work set up the gap.

The first is the work that joins overlapping communities to cold-start link prediction. On Learning Community-specific Similarity Metrics for Cold-start Link Prediction shows that feature relevance shifts across communities. It predicts links for zero-edge vertices by weighting feature similarity with the product of the two endpoints' soft community probabilities, which come from a logistic-regression classifier on node content. This paper motivates the proposal and is also its closest competitor. Its community signal is node-level, the number of communities is fixed by hand, and nothing tells the model which community a particular observed edge came from. We keep its intuition that similarity should depend on community. We change the supervision from node-level memberships to per-edge context labels, and we replace the fixed feature weighting with learned per-community embeddings.

The second is the link-based detectors, which supply the teacher. vGraph is a generative model in which each edge $(w,c)$ draws its own community $z$. It yields an edge-level posterior $q(z\mid w,c)$ and beat BigCLAM and CESNA on 11 of 14 overlapping benchmarks. Mixed-Membership Community Detection via Line Graph Curvature partitions the line graph, a graph whose vertices are the original edges, by Ricci curvature flow. Ricci curvature flow is a geometric procedure that stretches bottleneck edges until they can be cut. On DBLP it reached a Normalized Mutual Information (NMI) of 0.60, against 0.24 for Louvain on the same line graph. Both methods are transductive and structural. vGraph stores a lookup vector per node and ingests no features. The line graph contains no vertex at all for a degree-0 node. Our design sidesteps both limits by using these methods only as offline teachers on the warm graph.

The third is the cold-start methods, which supply the training tricks and the baselines. DropoutNet zeroes preference vectors during training so the network learns to work from content alone. Contrastive Learning for Cold-Start Recommendation (CLCRec) aligns content and collaborative embeddings with a contrastive objective. Privileged Graph Distillation distills an interaction-rich teacher into an attribute-only student, and its ablation found that embedding distillation mattered more than score distillation. Node Duplication Improves Cold-start Link Prediction (NodeDup) gives low-degree nodes a self-twin so that graph neural networks have something to aggregate. All four treat a node's behavior as one vector. Distillation in PGD transfers a representation, not a context assignment.

Distilling edge-context labels into a content-only student for zero-edge nodes appears to be unstudied in this file. The research file identifies the same gap (its Gap 5).

Core Mechanism

A content encoder maps node features $x$ to two outputs. The first is a membership vector $\pi(x)$ on the $K$-simplex, meaning nonnegative weights over $K$ communities that sum to one. The second is a set of community-specific embeddings $h_1(x),\dots,h_K(x)$. For a candidate pair $(u,v)$ the model scores

$$ s(u,v)=\log\sum_{k=1}^{K}\pi_k(x_u)\,\pi_k(x_v)\,\exp\!\big(h_k(x_u)^\top h_k(x_v)\big), $$

which reads as "some shared community $k$ explains this link." The normalized terms of this sum form the student's context posterior $r_k(u,v)$. Training combines three pieces. The first is a standard link loss on observed and negative pairs. The second is a context-distillation term. The third is DropoutNet-style removal of any structural input, so that the encoder must work from features alone. The context-distillation term is

$$ \mathcal{L}=\mathcal{L}_{\text{link}}+\beta\sum_{(u,v)\in E_{\text{train}}}\mathrm{KL}\big(q(\cdot\mid u,v)\,\|\,r(\cdot\mid u,v)\big), $$

where $q$ is the teacher's per-edge community distribution, $E_{\text{train}}$ is the set of warm training edges, and $\beta$ weights the distillation term. Each training edge therefore teaches the encoder which of the endpoints' features matter in that context. That is the signal a node-level membership label cannot give.

For a cold node, only $x$ is needed at test time. The teacher runs once, offline, on the training graph. This avoids line-graph blow-up and curvature cost at inference. The teacher's community labels are permuted to align with the student's slots, which the KL term does automatically as long as $K$ is matched.

We use a plain softmax for $\pi$. The Aitchison simplex parameterization of AICoG, a geometry for proportions under which dropping one community leaves the ratios among the others unchanged, will be tried as a secondary variant. It is not part of the central claim.

Research Program

The first stage builds teachers. vGraph runs on every dataset. Line-graph curvature runs on the smaller graphs as a second teacher, which tests whether results depend on the specific detector. $K$ is chosen by sweeping a small grid on validation link performance.

The second stage trains the student with the loss above on attributed graphs under a strict node cold-start protocol. We hold out 15% of nodes, delete every edge incident to them, and ask the model to rank their true partners among all training nodes. We also run a degree-1/2 regime, in which one or two edges are revealed.

The third stage is a mechanism analysis. For each held-out node we count how many distinct teacher communities its hidden edges span, using the teacher run on the full graph after evaluation. We then plot the student's gain over each baseline against that count. On DBLP, where papers carry venues, we also check whether the student's predicted context for a correct link agrees with the venue of the co-authored work. This tests whether the contexts mean anything beyond serving as a regularizer.

Baselines

The naive reference point is the content-only single-vector model. It is a two-tower encoder trained with the same link loss and the same feature dropout, but with $K=1$. This is the proposal with all community machinery removed. Any claimed gain has to exceed it under identical encoders, optimizer, epochs, and a hyperparameter budget matched by number of trials.

The strongest existing structural baseline is NodeDup on GraphSAGE. It is the most direct recent method for isolated-node link prediction and was evaluated on Cora and Citeseer, which we reuse. It reports a 38.49% average relative gain on isolated nodes across seven datasets, measured against the base network (NodeDup). We run the authors' duplication scheme on our exact splits and give it the same tuning budget. Beating it means a statistically reliable improvement in Hits@50 and Mean Reciprocal Rank (MRR) on the isolated-node test set over five seeds.

The closest conceptual baseline is Xu et al.'s community-weighted models, CWR and CWP. We reimplement them with the same number of communities and with the same teacher-derived node memberships as input where that helps them. We found no reported result on Lacuna for CWR or CWP as a textual scalar, so the comparison will rest on our reimplementation.

On CiteULike we add DropoutNet and CLCRec as recommendation-side baselines. DropoutNet reports a 6% Recall@100 improvement over DeepMusic for cold items there (DropoutNet).

Three ablations isolate the key ingredient. The first is the same $K$-component student with $\beta=0$, a latent mixture whose contexts are learned end to end. The second replaces the link-community teacher with edge labels derived from a node partition: Louvain on $G$, with an edge labelled by its endpoints' shared community and marked uncertain otherwise. The third uses a random edge partition with matched community sizes. Only the first comparison tests whether any teacher helps. The second tests whether the link-based teacher specifically is what helps.

Why not just…?

Why not just use a strong single-vector cold-start model like NodeDup, DropoutNet, or CLCRec? These models have large documented cold-start gains and a real chance of matching us. If feature relevance does not actually shift across contexts on these datasets, one vector suffices. Xu et al.'s semantic-shift evidence suggests it does shift, but their numbers are not available to us. The naive $K=1$ baseline and NodeDup settle this directly. The stratified analysis says where to expect a difference: nodes whose hidden links span one community should show no gap, and multi-context nodes should show a clear one. If the gap is absent on multi-context nodes too, the proposal's premise is wrong for these data.

Why not just use node-level soft communities, as Xu et al. do? Node memberships say that a researcher is part networking and part databases. They do not say which of their links came from which side, so the per-community similarity is learned from mixed evidence. The line-graph result on DBLP (NMI 0.60 against 0.24 for Louvain on the line graph, Tian et al.) suggests edge partitions separate overlapping structure far better. The node-partition-teacher ablation and the CWR/CWP comparison test whether that transfers to cold-start accuracy.

Why not just let a multi-component mixture discover its own contexts without a teacher? This is the most serious threat. With enough edges, end-to-end training might find contexts as good as vGraph's. The $\beta=0$ ablation answers it. We expect the teacher to matter most when training edges are scarce, so we repeat that comparison while subsampling training edges to 25%, 50%, and 100%. If the latent mixture matches the distilled one at every level, we will report that explicit link communities are unnecessary and that the mixture scoring alone carries the gain.

Why not just use text-embedding similarity? The file gives PGD's gains from distilling interaction structure over attribute-only models, 6.6% on Yelp and 17.1% on Amazon-Video Games (PGD). It also gives HGNR's finding that similarity-built links help only up to roughly 10–15 per node before adding noise (HGNR). Both suggest raw similarity leaves collaborative structure on the table. We include a frozen Sentence-BERT cosine baseline on datasets with raw text so this is measured, not assumed.

Proposed Experiments

The main benchmarks are the attributed graphs Cora and Citeseer (used by NodeDup), plus DBLP, PubMed, and BlogCatalog (used by Xu et al.). CiteULike serves as the bipartite recommendation check. Metrics are AUC, Hits@50, and MRR for link prediction, and Recall@100 on CiteULike to match DropoutNet's protocol. All results are averaged over five seeds, with paired significance tests on per-node reciprocal ranks.

Three checks decide the claim. First, the distilled student must beat the $\beta=0$ mixture and the node-partition teacher on isolated nodes. Otherwise the link-based ingredient is not doing the work. Second, the gain over the $K=1$ model must grow with the number of distinct contexts a cold node's true links span. A flat curve would mean the benefit is generic regularization rather than context disentanglement. Third, results with the curvature teacher must track those with the vGraph teacher on the smaller graphs. Otherwise the effect belongs to one detector rather than to link communities.

As a cost check, we report teacher preprocessing time against NodeDup's lightweight augmentation. That keeps the comparison honest about the price of the offline stage.