Asking Experts About the Edges That Matter: Budgeted Verification of Missing Interactions for Network-Based Gene Prioritization

Many computational biology methods find disease genes by "spreading" a signal across a map of protein interactions. The signal starts at a few known genes and flows along the map's edges, and genes that receive a lot of signal are ranked as candidates. The map is badly incomplete, and the gaps are not random. Interactions are recorded where researchers have already looked, so poorly studied proteins sit isolated, and signal cannot reach them. Filling the gaps needs expert curation or experiments, and both are scarce. Our proposal is simple: do not try to fill the whole map. For a given disease query, compute which unconfirmed edges would most change the final ranking if they turned out to be real. Spend the small expert budget confirming or rejecting only those edges.

The bet is that only a small fraction of missing interactions matter for any particular question. Medical imaging already works this way: a few scribbles placed where the model is uncertain can stand in for full pixel masks. Interaction maps lack a spatial grid, but propagation-based ranking has its own structure. Its sensitivity to adding a single edge can be computed exactly and cheaply. That gives a principled way to decide where an expert's limited time goes. If the bet holds, a few hundred verified edges per query should recover most of the ranking accuracy lost to missing interactions. Edges picked because a link predictor is unsure, or edges imputed wholesale with no expert at all, should do worse at the same budget.

Core Claim

Missing edges hurt network propagation in a known way. PONYTA states that absent interactions stop signal from reaching true phenotype genes. TSNBA shows that signal pools in over-studied hubs. GhostBuster shows that literature-dense networks give inflated benchmark scores (ROC-AUC around 0.88) while failing on understudied "ghost genes." These papers motivate the work.

None of them treats the incomplete graph as something a scarce oracle can query. PONYTA handles unlabeled genes with positive-unlabeled learning but keeps the STRING v12.0 graph fixed at score > 0.700. GhostBuster avoids the biased graph by switching to tumor expression data (TCGA) rather than repairing it. We claim that propagation-aware selection of edges for verification beats the alternatives at an equal budget. It should beat uncertainty-driven selection, degree-driven selection, and expert-free imputation, and the advantage should be largest for understudied genes.

Research Program

The method has three parts.

Prior over candidate edges. First, we put a probability $q_e$ on every candidate edge $e$ absent from the high-confidence graph. A link predictor produces it from channels that do not depend on literature density. These are expression co-variation, following GhostBuster's evidence that such data carries less study bias, and the lower-confidence STRING evidence. Monte Carlo dropout gives a calibrated uncertainty. This reuses the uncertainty gating that Can et al. found was the main driver of stability in scribble-supervised segmentation.

Influence of each edge on the ranking. Second, we score how much each candidate edge would change the ranking. Random walk with restart scores genes as

$$p = (1-\alpha)(I - \alpha W)^{-1} s,$$

where $W$ is the column-normalized adjacency matrix, $s$ is the seed vector and $\alpha$ is the restart parameter. Adding edge $e$ changes two columns of $W$. A Woodbury low-rank update therefore gives the new scores $p^{(e)}$ without re-solving the system. We define the influence $\Delta_e$ as the number of genes that cross the top-$k$ boundary when $e$ is added. The query score is

$$a_e = q_e (1 - q_e)\, \Delta_e,$$

so an edge is worth asking about when its existence is genuinely uncertain and its answer would reorder the candidates experts will actually look at.

Query loop. Third, a loop queries the top-scoring edges in batches and adds confirmed edges with weight 1. Rejected edges are excluded. Unqueried edges are either ignored or added at weight $q_e$ only if their uncertainty is low, which is the self-training ingredient. Then the loop recomputes.

The same loop can wrap PONYTA's belief-propagation and graph-attention model in place of the random walk. In that case $\Delta_e$ is estimated by finite differences on a shortlist preselected by random-walk influence.

Evaluation Design

The oracle is the hard part, because real curators cannot be queried thousands of times. We use three oracles of increasing realism.

Study-biased masking. We remove high-confidence STRING edges with probability inversely related to how studied their endpoints are, mimicking the bandwagon effect. The removed edges answer queries.

Evidence-based oracle. Candidates are STRING edges below the 0.700 cutoff. The oracle answers "yes" only when the edge has non-text-mining evidence. This tests whether queries can promote real edges without importing literature bias.

Small curator pilot. Domain curators verify a few hundred edges proposed for the Sarm1 query. We measure agreement with the automated oracles and the curator time spent per edge.

Baselines

Do-nothing reference. Random walk with restart on STRING v12.0 at score > 0.700, with the same seeds and no edge changes. This sets the floor and the gap to close. Under masking, the same walk on the unmasked graph sets the ceiling.

Strongest graph method. PONYTA, run on its own five mouse knockout datasets (Nkx2-1, Nr5a1, Tcf4 single-cell; Pax6, Sarm1 bulk) with its published seed rule and graph. PONYTA reports beating random walk with restart and DIAMOnD on partial AUC, but no reported result was found on Lacuna for its numeric partial AUC values. We will therefore rerun it ourselves and report its partial AUC alongside ours. PONYTA is also wrapped by our loop, so any gain over it comes from the queried edges and not from a different learner.

Expert-free imputation. A graph convolutional link predictor in the style of Graph GhostBuster adds its top predicted edges with no verification. It is given the same total number of added edges as our method has queries, plus a version that adds edges at every confidence level.

Threshold relaxation. The STRING score cutoff is swept from 0.700 down to 0.400. This is the natural "just add more edges" baseline.

Expression-only route. A GhostBuster-style tabular model on TCGA expression, which ignores the graph entirely. GhostBuster reports test ROC-AUC of 0.80–0.95 and 2–3× better recovery of 2022–2025 annotations than literature-trained models, so this is the baseline most likely to embarrass us.

Ablations of the selection rule. Each keeps everything else fixed and changes only how queries are chosen:

  • random queries;
  • uncertainty-only queries, scored by $q_e(1-q_e)$;
  • influence-only queries, scored by $\Delta_e$;
  • degree-targeted queries, which pick edges at the least-studied nodes.

Fairness. All arms share the link predictor, the seeds, the oracle budget (0.1%, 0.5% and 2% of masked edges) and a matched hyperparameter search.

What counts as beating them. We require two things. First, the propagation-aware rule must close at least half of the masked-to-full partial AUC gap at the 0.5% budget. Second, it must beat uncertainty-only selection on at least four of five knockout datasets, with a paired test across 20 masking seeds.

Why not just…?

Why not just drop the graph and use expression data, as GhostBuster and Tissue-guided LASSO do? Tissue-guided LASSO found that simple regularized models beat neural networks on noisy drug-response data. GhostBuster shows that expression-only models recover recent annotations better than literature-trained models. This is a real threat. Our answer is empirical: run the time-split test described under Proposed Experiments. If expression-only matches us on newly annotated genes, the honest conclusion is that verification is only worth it when the output must be a pathway-level explanation, and we will report that.

Why not just lower the STRING cutoff? PONYTA itself describes the trade-off: strict cutoffs lose true genes, while loose ones flood propagation with noise. COSSY and Lahti et al. show that uncurated edges distort module density. The threshold sweep tests this directly. We expect a single global cutoff to do worse than targeted verification, because it adds edges everywhere rather than where the ranking is sensitive.

Why not just impute predicted edges and self-train, with no expert at all? Self-training stabilized by uncertainty and prototype constraints works in imaging: the multi-constraint cardiac method reaches a Dice score of 0.730 with 5% of annotations, versus 0.711 for Deep Co-Training. Here, though, the link predictor's errors share the same study bias as the graph. The imputation baseline and the "unqueried edges at weight $q_e$" ablation measure how much of our gain survives without the oracle. If imputation alone closes most of the gap, the expert budget is unnecessary, and we would say so.

Why not just use standard uncertainty sampling? This is the uncertainty-only ablation. The uncertainty term ignores whether an edge changes anything downstream. Our hypothesis is that most uncertain edges sit far from the seed neighborhood. The influence-only ablation separates the two factors in $a_e$.

Proposed Experiments

Main comparison. We run all arms on the five PONYTA knockout datasets under study-biased masking, reporting partial AUC on the top-ranked region and recall@100. We break results down by how studied each gene is, to test whether gains concentrate in poorly studied genes.

Disease-gene benchmark. On the OMIM and HumanNet setting of PGCN, we repeat the masking protocol with disease seeds. PGCN reports AUPRC about 10% above its runner-up, with no absolute figure in the file. We will rerun PGCN as the learned-embedding comparator.

Decisive time-split test. We seed propagation with genes annotated to each GO term before 2022 and score recovery of genes annotated in 2022–2025, using GhostBuster's evaluation split. This tests whether verified edges help find genuinely new biology rather than masked edges. The expression-only baseline runs on exactly this test.

Cost check. We report curator minutes per verified edge and the budget needed to reach 90% of the full-graph ceiling. This turns the claim into a concrete statement of how much expert time a query is worth.