Tumors survive single drugs because their signaling networks are redundant. When one route to "keep growing" is blocked, another carries the signal. Engineers who build fault-tolerant hardware and distributed systems have exact tools for this kind of redundancy: count the independent routes between two points and you know how many failures the system can absorb. Drug-combination prediction mostly does not use these tools. It relies on smooth diffusion scores or black-box neural predictors instead. We propose to learn, from genome-wide knockout data, a small discrete model of each cancer's signaling logic. Each gene either fires or stays silent depending on whether its weighted inputs cross a threshold. We then search that learned model for the smallest set of genes whose simultaneous inhibition shuts off the survival readout.
The discreteness is what makes this work, and it is also what makes it hard. A thresholded model supports exact, checkable statements such as "no set of fewer than three inhibitions silences this cell line's survival output." It also captures AND-like dependencies that path-counting cannot. But thresholds have zero gradient almost everywhere. We borrow the fix from spiking neural networks, the surrogate gradient: a smooth stand-in derivative used only in the backward pass, while the forward pass stays binary. This lets us fit the model to data and optimize the knockout set end to end. At deployment, the model is still an exact Boolean object that a solver can certify.
Core Claim
Learning the network's parameters and choosing a combination of targets can both be done by gradient descent through a binary threshold model. Doing so should predict combination effects better than linear diffusion or classical vertex cuts, specifically when the network contains conjunctive dependencies, where a node needs several inputs to activate. The claim is falsifiable in a clean way. If the learned thresholds collapse to "any single active input suffices," then tumor resilience reduces to Menger's theorem. Menger's theorem says the number of independent paths equals the size of the smallest node set whose removal separates the endpoints. In that case a polynomial-time max-flow computation would do everything our method does, and we would report that.
Research Program
The model is a directed graph over genes, with a source layer of driver and receptor nodes and a sink node representing proliferation or survival. At each of $T$ synchronous update steps, gene $v$ is active according to
$$a_v^{t+1} = \Theta\Big(\sum_{u \to v} w_{uv}\, a_u^{t} - \theta_v\Big)\,(1 - m_v),$$
Here $\Theta$ is the Heaviside step function, $w_{uv}$ are signed learnable edge weights, $\theta_v$ is a learnable firing threshold, and $m_v \in \{0,1\}$ marks whether gene $v$ is knocked out or inhibited. This is a leaky integrate-and-fire neuron with the leak removed, unrolled in time exactly as in Spatio-Temporal Backpropagation. That paper trains discrete-time spiking units with surrogate gradients through both layers and time steps, and shows that dropping the temporal unrolling hurts. We reuse that training recipe. We replace $\partial\Theta/\partial x$ with a fast-sigmoid surrogate, as reviewed in Surrogate Gradient Learning in Spiking Neural Networks. We are constrained by the known bias of this approach: Hybrid Macro/Micro Level Backpropagation documents that a mismatch between forward and backward passes can trap training in poor minima. This is why we pair gradient search with an exact solver rather than trusting the gradient's answer.
The graph skeleton comes from a physical interaction network such as STRING. It is restricted to genes expressed in a cell line, so each cell line gets its own graph. Weights and thresholds are fit to single-gene CRISPR knockout effects across the DepMap cell lines used by A Co-essentiality Network of Cancer Driver Genes Better Prioritizes Anticancer Drugs. The training signal is that knocking out gene $v$ in cell line $c$ should reduce sink activity in proportion to its measured essentiality.
Weighted gene co-expression network analysis (WGCNA) enters as a prior, and we treat that role skeptically. WGCNA clusters genes into modules of co-varying expression and scores gene pairs by shared neighbors through the topological overlap matrix. We use those scores to regularize which interaction edges keep nonzero weight, and module eigengenes (each module's first principal component) to gate cell-line-specific edges. Lee et al. found plain co-expression networks weakly enriched for cancer pathways, with an odds ratio of 0.49 versus 4.27 for co-essentiality. That result argues against expecting much from this prior. We therefore compare three priors: co-expression, co-essentiality, and none.
Once the model is fit, combination search optimizes a relaxed mask. The mask is also passed through a thresholded unit with a surrogate backward pass, so that the chosen set is binary in the forward pass:
$$\min_{m}\; \mathbb{E}_{c}\big[a_{\text{sink}}^{T}(m; c)\big] + \lambda \sum_v m_v,$$
where $c$ ranges over cell lines of a cancer type and $\lambda$ sets the budget on the number of targets. We restrict $m$ to genes targeted by existing drugs, so that proposed sets map to real compounds.
For the top candidates we then compute an exact certificate: the minimum knockout number of the learned discrete network, restricted to the neighborhood that feeds into the sink. We formulate it as an integer linear program, in the spirit of the node-splitting flow formulation that Adaptive 3D-IC TSV Fault Tolerance Structure Generation used to compute exact repair capacity. The certificate tells us whether gradient search found the true minimum and how large the tumor model's "fault tolerance" is. Under OR-logic, that fault tolerance equals the sink's vertex connectivity. Under learned thresholds it can be smaller, because a combination can starve an AND-node without severing every path to it. That gap is the scientific quantity of interest.
Baselines
The naive reference is top-$k$ degree or betweenness centrality on the same expression-restricted interaction network. This is the standard hub-ranking pipeline of network pharmacology, as in CENPL, ISG20L2, LSM4, MRPL3 are four novel hub genes, which used nine centrality algorithms. A pair scores as synergistic if both drugs hit high-centrality targets. It needs no training, and it establishes whether any structure beyond hub-ness matters.
The strongest mechanism-based competitor is random walk with restart (RWR) diffusion with module separation, from Diffusion mapping of drug targets on disease signaling network elements. RWR spreads a perturbation from each drug's targets across the network, and pairs are scored by how separate their affected modules are. On a 131-gene BRAF-mutant melanoma network it recovered 76% of validated combinations within the top 30% of predictions, versus 69% for SynGeNet. We rerun it on the identical network and drug-target mapping, and we also run it on our learned signed graph so that edge weights are not the differentiator. Beating it means exceeding 76% top-30% recovery on the same melanoma evaluation, and ranking better on the larger screens.
The strongest learned competitors are DeepSynergy and CongFu. DeepSynergy is a feed-forward network on chemical descriptors and cell-line expression, reporting MSE 255, Pearson 0.73, and ROC AUC 0.90 on the Merck/O'Neil screen of 23,062 samples. CongFu uses conditional message passing on molecular graphs and reports the best results on 11 of 12 DrugComb datasets. The file does not give its absolute AUPRC, only gains of 0.036–0.061. Both are trained on combination labels, which our model never sees. We expect them to win in-distribution. The fair test is the leave-drug-out split, where DeepSynergy's authors report that performance drops considerably. No reported leave-drug-out number for DeepSynergy was found on Lacuna, so we rerun both with their published hyperparameter search at matched tuning budget. Beating them means higher leave-drug-out AUC and AUPRC while using zero combination labels, or matching them when given the same labels as fine-tuning signal.
Two structural baselines isolate our ingredients. The first is exact minimum vertex cut from sources to sink via max-flow with node splitting, which is OR-logic fault tolerance. The second is the same architecture with a continuous sigmoid forward pass, trained identically and then rounded to a binary network afterward. That second baseline is the key ablation for whether the binary forward pass matters.
Why not just…?
Why not just compute a minimum vertex cut with max-flow? It is exact, fast, and has solid theory behind it, from Menger's theorem through the connectivity results of On atomic registers and randomized consensus in M&M systems. But it assumes a node stays alive if any input survives. If real signaling contains conjunctive requirements, a cut over-counts the targets needed and misranks combinations that exploit them. This is a genuine threat. If the learned thresholds concentrate at single-input activation, or if the min-cut baseline matches our model on combination recovery, then conjunction is not doing work and the simpler method wins. We report the learned threshold distribution and the gap between the cut and our certified minimum for exactly this reason.
Why not just use RWR or heat diffusion? Diffusion is linear and passive. It cannot represent inhibitory edges, saturation, or the fact that removing one input may leave a node fully active while removing two shuts it off. Xu et al.'s own finding, that 16 of 17 validated combinations spanned different functional communities, is consistent with both diffusion and threshold logic, so it does not decide between them. The head-to-head on the melanoma network and on held-out pairs settles it. If RWR on our learned signed graph matches the threshold model, then the learned weights help but the discrete dynamics do not.
Why not just train a continuous model and round it? This is the likeliest serious competitor, because continuous training avoids the forward-backward mismatch. Our hypothesis is that a continuous forward pass lets partial activations leak through bypass routes. That leakage makes the model mis-estimate how much redundancy remains, and the rounded network then disagrees with the one that was actually optimized. The ablation measures this directly: agreement between predicted and certified sink silencing after rounding, and downstream combination accuracy. If rounding loses nothing, the spiking surrogate is unnecessary machinery and we would say so.
Why not just use DeepSynergy or CongFu? They need combination labels, which is exactly what is scarce for novel drugs. They also yield no mechanistic statement about which redundancy a combination removes. Our model is trained only on single knockouts, so its combination predictions are genuine extrapolations. If it cannot approach the supervised models' leave-drug-out performance, its interpretability is not worth much.
Proposed Experiments
We fit per-cancer-type models on DepMap single-gene essentiality and hold out 20% of genes. The first check is whether held-out single-knockout effects are predicted better than by RWR-based guilt-by-association on the co-essentiality network of Lee et al. That paper reports higher PRISM IC50 correlation in 13 of 15 cancer types; we match its evaluation protocol and cancer types.
The central test is combination extrapolation. We map drugs in the O'Neil screen and in DrugComb to their targets. For cell lines present in both DepMap and the screens, we predict synergy from the model's two-target knockout response relative to the two single knockouts, a Bliss-style excess computed on sink activity. We evaluate with ROC AUC and AUPRC under leave-drug-out and leave-cell-line-out splits. Separately, we reproduce the melanoma evaluation of Xu et al. and report top-30% recovery against their 76%.
The decisive mechanistic check has three parts. On each learned network we compute the certified minimum knockout number and compare it with the min-vertex-cut size. We ask whether combinations where the two differ, meaning combinations that exploit conjunctive nodes, are where our model gains over the cut and RWR baselines. We also measure how often gradient search recovers the ILP optimum, as a function of network size, to quantify the cost of surrogate bias.
Finally, we compare co-expression, co-essentiality, and no prior on the edges. Lee et al.'s results predict that co-expression will be the weakest of the three. If our results show otherwise, that would itself be informative about when co-expression modules carry functional signal.
References
- Spatio-Temporal Backpropagation for Training High-Performance Spiking Neural Networks
- Surrogate Gradient Learning in Spiking Neural Networks
- Hybrid Macro/Micro Level Backpropagation for Training Deep Spiking Neural Networks.
- A Co-essentiality Network of Cancer Driver Genes Better Prioritizes Anticancer Drugs
- Adaptive 3D-IC TSV Fault Tolerance Structure Generation
- CENPL, ISG20L2, LSM4, MRPL3 are four novel hub genes and may serve as diagnostic and prognostic markers in breast cancer
- Diffusion mapping of drug targets on disease signaling network elements reveals drug combination strategies
- DeepSynergy: predicting anti-cancer drug synergy with Deep Learning
- CongFu: Conditional Graph Fusion for Drug Synergy Prediction
- On atomic registers and randomized consensus in M&M systems