Link prediction asks whether an edge exists between two nodes in a graph, for example whether two authors will collaborate or a user will buy an item. Graph neural networks (GNNs), which build each node's representation by aggregating messages from its neighbors, have a well-documented failure on this task. If the edge being predicted stays in the graph during training, the model learns a trivial rule: "is there a direct message channel between these two nodes?" That rule is useless at test time, because test edges are by definition absent. The community's fix is target-edge exclusion, which means removing the edge being scored from the graph before computing representations. A mixture of experts (MoE) is a model built from several sub-networks, called experts, plus a small gating network, called the router, that decides how much each expert contributes for a given input. MoE link predictors are now appearing. They inherit a second, unexamined path for the same leak. The router usually reads pair-level structural features such as shortest-path distance, node degrees, or path counts. Several of these features change sharply when the target edge is present.
This note proposes to measure and close that second path. The claim is that excluding the target edge inside the experts is not enough. The router can learn to detect the target edge's presence from its own inputs and send leaked pairs to whichever expert profits most from the leak. The router then routes differently at test time, when the edge is gone. The damage should be concentrated where earlier work found GNNs most vulnerable, on pairs of low-degree nodes. The deliverables are a counterfactual audit of router leakage, a cheap leave-target-out correction for router inputs, and a test of whether the most natural MoE design for this problem still helps once the router is leak-free. That design uses experts trained under different exclusion regimes and lets the router learn, per pair, how much exclusion to apply.
Core Claim
Pitfalls in Link Prediction with Graph Neural Networks and its companion SpotTarget set out the motivating facts. The target edge acts as both training label and message conduit. Keeping it causes overfitting, a train/test distribution shift, and, if test edges are allowed into message passing, outright test leakage. On ogbl-collab, Hits@50 is about 99% with leaked test edges and about 57% without. The harm is concentrated at low-degree nodes, where one edge can be half of a node's incoming signal. SpotTarget's remedy is to exclude a training edge only when one endpoint has degree below a hand-tuned threshold δ. Message-passing estimators such as MPLP likewise remove the target link before estimating common neighbors and walk counts.
None of this work covers modular models. The closest MoE link predictor, heuristic-informed MoE for multilayer link prediction, routes each node pair among frozen link-prediction experts. Its router takes classic topological heuristics as input, and the paper reports large relative gains (+60% MRR, +82% Hits@1). It does not discuss whether those router inputs are computed with the target edge present. The leak is heuristic-specific, and that makes it testable. A pair's common-neighbor count does not change when the edge between them is added. Preferential attachment, the product of the two degrees, rises by roughly one per endpoint, which doubles it for a degree-1 pair. Jaccard similarity changes because each endpoint enters the other's neighborhood. Shortest-path distance collapses to 1. Katz-style walk counts gain a direct term. The router therefore receives a near-perfect label signal from some of its inputs and almost none from others.
To quantify this, define router leakage as the counterfactual change in routing when only the target edge is toggled:
$$\Lambda = \mathbb{E}_{(u,v)}\, \mathrm{TV}\big(g(x_{uv}^{G}),\; g(x_{uv}^{G \setminus uv})\big),$$
Here $g$ is the router's output distribution over experts. $x_{uv}^{G}$ are the pair features of nodes $u,v$ computed on graph $G$. $G \setminus uv$ is the graph with that one edge removed, and TV is total variation distance. We predict three things. First, $\Lambda$ will be large for routers that read degree- or path-based features and near zero for routers that read only common-neighbor counts. Second, $\Lambda$ will grow as endpoint degree falls. Third, a large $\Lambda$ will predict the gap between validation and test performance, because validation pairs are usually scored with their edge absent, as test pairs are.
Research Program
The work has three parts, each feeding the next.
The first part is the audit. We reimplement a heuristic-gated MoE in the style of the multilayer MoE paper, and we build an end-to-end MoE GNN whose router reads the same pair features. For each trained model we compute $\Lambda$ overall, by heuristic feature, and by degree bucket. We also measure routing shift, the divergence between the router's expert distribution on training positives (edge present) and held-out positives (edge absent), matched on degree. A linear probe on the router's logits that predicts edge presence gives a second, simpler leakage measure. This part tests the core claim directly. If $\Lambda$ is negligible everywhere, the proposal stops there with a clean negative result.
The second part is the fix: leave-target-out router inputs. Each scored pair's features are computed on $G \setminus uv$, and only for that pair. This avoids the cost the MPLP paper flags, namely rebuilding the whole batch's neighborhoods. Most corrections are closed-form. Degrees drop by one. Jaccard removes $u$ and $v$ from each other's neighbor sets. Common-neighbor and Adamic-Adar counts need no change. Path-based features need a depth-bounded search that ignores one edge. Experts keep whatever exclusion regime they were designed with, so the fix isolates the router's contribution.
The third part is the regime MoE: a learned, per-pair replacement for SpotTarget's threshold. All experts share one backbone (GraphSAGE or GATv2, matching SpotTarget, plus an MPLP-based structural expert). They differ only in how aggressively training target edges are excluded from their message-passing graph, ranging from strict exclusion to SpotTarget-style low-degree exclusion to minimal exclusion. At test time every expert sees the strictly excluded graph, as required. The router decides per pair how much to trust each regime. This is the setting where router leakage should do the most harm. A router that can see the target edge will learn that the minimal-exclusion expert is reliable exactly when the edge is visible, and then misroute every test pair. Following the GraphMETRO result that experts drift into incompatible representation spaces without alignment, which in its ablation dropped WebKB accuracy from 41% to 18%, we add an alignment loss. It ties each expert's pair embedding to the strict-exclusion expert's embedding. GraphMETRO supplies this method piece but addresses covariate shift, not label leakage. MT-CRL prunes non-invariant expert-to-task routes using environment labels. Here the "environments", meaning edge present versus absent, are known by construction, so a cross-environment penalty on the router is available without any environment discovery. We include it as a variant.
Baselines
The naive reference point is a single GNN trained with target edges kept in the graph and evaluated with test edges strictly excluded. It shows how much leakage costs before any remedy. The no-learning reference is the classic heuristics themselves, common neighbors and Adamic-Adar, computed on the leak-free graph.
The strongest existing method is SpotTarget on the same backbone. It is the published answer to exactly the problem the regime MoE targets: deciding how much exclusion each pair needs. On sparse e-commerce data it reported up to 15× higher MRR than standard training, although the file gives only that relative figure and no absolute value. The reference number we will report against is the strict-exclusion ogbl-collab result of about 57% Hits@50 from the Pitfalls paper. No reported result was found on Lacuna for SpotTarget or MPLP on ogbl-citation2 or ogbl-ppa, so on those datasets we will report our own reproductions. SpotTarget gets the same hyperparameter budget as the MoE, and its δ grid counts against that budget. The MoE is compared at matched parameter count and, separately, at matched training FLOPs, since K experts cost more than one model. Beating SpotTarget means a statistically reliable gain in MRR or Hits@k across seeds on at least two datasets, with the gain concentrated in the low-degree buckets where the threshold is supposed to matter.
The second strong competitor is the heuristic-gated MoE in the style of the multilayer MoE paper, run on its six multilayer datasets (Cs-Aarhus, CKM, Lazega, Elegans, DkPol, ArXiv). The file reports only relative gains for it, not absolute scores, so we will reproduce it twice, with and without leave-target-out router inputs. That comparison is the headline ablation. It holds experts, data, and tuning fixed and changes only whether the router can see the target edge. A second ablation removes the alignment loss from the regime MoE. A third trains the regime MoE with a leaky router, which tests the prediction that the learned router collapses onto the minimal-exclusion expert.
Why not just…?
Why not just exclude every target edge everywhere? Removing all training target edges from message passing kills the leak, but the Pitfalls and SpotTarget papers show it disconnects sparse graphs and loses to selective exclusion. Our router fix is not this. It removes only the scored pair's own edge from that pair's router features, which costs nothing in connectivity. The comparison stays in the experiments because a reviewer will rightly ask whether a strictly excluded single model already does as well as any MoE.
Why not just tune SpotTarget's threshold carefully? This is the real threat to the regime-MoE part of the proposal. A well-tuned δ may capture most of the per-pair variation a router could learn, especially on graphs with a single relation type. The experiment settles it. If the regime MoE with a leak-free router does not beat tuned SpotTarget, we report that and keep the audit and the router fix as the contribution. Those parts stand regardless, because they concern MoE models that already exist. We expect any advantage to show up on multilayer and heterogeneous graphs, where one global δ cannot fit layers with very different degree profiles. That limitation is already listed among SpotTarget's open problems.
Why not just give a single GNN the endpoint degrees as an input, or learn a degree-dependent edge-drop probability? Either change could recover the adaptivity of the regime MoE without experts. We run both as non-MoE ablations under the same budget. If a learned drop schedule matches the regime MoE, the expert decomposition is unnecessary and we will say so. Note that the degree-feature variant must itself use leave-target-out degrees. Otherwise it reintroduces the very leak this note is about, which is a useful sanity check in its own right.
Why not just compute router heuristics only from common neighbors, which never leak? That restriction removes the leak at no correction cost. It also discards the degree and path information that makes heuristic gating useful on sparse pairs with zero common neighbors, a weakness of common-neighbor methods noted in the MPLP paper. We train a common-neighbors-only router as a baseline. If it matches the corrected full-feature router, the practical recommendation becomes "use leak-immune router features", which is a simpler and still useful outcome.
Proposed Experiments
The datasets are ogbl-collab, ogbl-citation2, and ogbl-ppa from the Open Graph Benchmark, the six multilayer networks plus synthetic Watts-Strogatz graphs from the multilayer MoE paper, and MovieLens framed as bipartite link prediction, following STAR-GCN's sample-and-remove protocol. Metrics are Hits@50 and MRR, reported overall and by endpoint-degree bucket, together with $\Lambda$, probe accuracy, and train/test routing shift.
Three checks decide the outcome. The first is a planted-shortcut test on Watts-Strogatz graphs. Held-out positives are random pairs with no structural signal, so an honest model must score near chance on them. If a leaky-router MoE scores above chance on validation positives that still have their edge present, while the corrected router does not, the leak is demonstrated in isolation. The second is the leaky-versus-corrected router comparison on the multilayer benchmarks. If the MoE's reported advantage over single experts shrinks substantially once router inputs are computed without the target edge, the field's current MoE numbers need re-examination. If the advantage survives, we have certified them. Either outcome is worth publishing. The third is the degree-bucket breakdown. The leakage theory predicts that $\Lambda$, routing shift, and the benefit of the router fix all peak in the lowest-degree bucket and fade for hubs. Seeing that pattern would tie router leakage to SpotTarget's low-degree mechanism. Not seeing it would mean the leak works through some route other than the one we hypothesize.
References
- Pitfalls in Link Prediction with Graph Neural Networks: Understanding the Impact of Target-link Inclusion & Better Practices
- SpotTarget: Rethinking the Effect of Target Edges for Link Prediction in Graph Neural Networks
- Pure Message Passing Can Estimate Common Neighbor for Link Prediction
- Heuristic-informed mixture of experts for link prediction in multilayer networks
- GraphMETRO: Mitigating Complex Graph Distribution Shifts via Mixture of Aligned Experts
- Improving Multi-Task Generalization via Regularizing Spurious Correlation
- Open Graph Benchmark: Datasets for Machine Learning on Graphs
- STAR-GCN: Stacked and Reconstructed Graph Convolutional Networks for Recommender Systems