Tracing Multi-Cell Signaling Relays with an Expression-Rewarded Graph Walker

Cells in a tissue talk to each other with secreted molecules (ligands) that bind receptors on nearby cells and change which genes those cells switch on. Sometimes the conversation is a relay. Cell A's signal makes cell B produce a second ligand, which then acts on cell C. Current tools that read cell-to-cell communication from spatial gene-expression maps (spatial transcriptomics, which measures gene activity at known positions in a tissue slice) only score single hops, sender to receiver, sometimes extended to the receiver's immediate target genes. They cannot follow a chain that runs from a ligand to a receptor, through the receiver's internal signaling, to a new ligand, and on to a third cell. We propose to find such chains with a reinforcement-learning walker. This is an agent that learns, by trial and reward, which edge to follow next in a graph. Here the graph mixes intercellular edges (ligand in one cell type, receptor in a nearby one) with intracellular edges (receptor to signaling protein to transcription factor to gene). The reward does not come from reaching a labeled answer. It comes from the observed tissue: a path earns credit to the extent that its predicted activity, laid across the slice, explains gene expression that cell identity and single-hop signaling leave unexplained.

In two sentences: we turn relay discovery into a multi-hop walk over a combined cell-type-by-molecule graph, and we reward each walk by how much of the measured expression it explains beyond a spatially shuffled null. The open question we will settle honestly is whether a learned policy beats exhaustive or beam search under the same reward. If it does not, the contribution is the reward and the benchmark, not the reinforcement learning.

Core Claim

The specific claim has three parts. First, multi-cell relays are detectable in existing spatial transcriptomics data once intercellular and intracellular steps are scored jointly. Second, scoring paths against observed expression residuals, with spatially permuted nulls for calibration, turns the main known weakness of reinforcement-learning path finders into usable signal. Third, a policy trained this way recovers planted relays and perturbation-validated targets better than composing single-hop calls or running unguided walks.

The weakness in question is the "one query, many correct answers" problem. MINERVA is the reference agent that walks a knowledge graph with a path-history memory and a binary arrival reward. It reports that an agent reaching a valid but unlabeled endpoint is wrongly given zero reward. Signaling is pleiotropic, meaning one ligand reaches many receptors and targets, so that failure would be severe here. A reward built from expression grants credit to any chain the data supports.

The novelty is narrow, and it should be stated precisely. KGML-xDTD already uses a demonstration-guided actor-critic agent to find three-hop drug mechanism paths. It does so in a static biomedical knowledge graph of 3.6 million nodes, reaches 94.7% mean percentile rank on DrugMechDB against 61.4% for a MultiHop baseline, and never touches expression or space. SpaTalk links spatial ligand-receptor calls to intracellular targets, but with a fixed random walk run as a separate step after the ligand-receptor call. We differ from the first by making the environment a tissue and the reward an expression residual. We differ from the second by optimizing the intercellular and intracellular steps as one sequential decision and by allowing a path to leave the receiver cell again.

Research Program

The environment. We build a typed graph per tissue section. Each node pairs a cell type or spatial niche with a molecule. Intracellular edges come from directed signaling and regulation priors: OmniPath, which merges 168 resources and over 1.4 million interactions, together with SIGNOR, and the receptor-to-transcription-factor and transcription-factor-to-gene layers used by stMLnet. Inside a cell type, an edge is kept only if both endpoints are expressed above a threshold in that type.

Intercellular edges connect a ligand in one cell type to its receptor in another, under two conditions. The two types must be spatially adjacent somewhere in the section. The pairing must also respect the multi-subunit complex rules of CellChat, which reports that modeling heteromeric complexes cuts false positives by roughly 10 to 14%.

Working at the level of cell type by molecule keeps the action space tractable. The relay hypothesis is still tested at individual-cell resolution, because the reward instantiates each path on actual cell positions.

The query and the walk. A query is a pair: a target gene $g$ and a cell type in which $g$ carries a large residual. The residual is what remains after removing two things: the cell-type mean, and the best single-hop ligand-receptor explanation, in the spirit of the baseline-plus-communication split used by HoloNet.

The agent walks upstream along inverted edges, the way MINERVA uses inverse relations, and stops with a no-op action. The policy is MINERVA's: a recurrent memory of the path so far, scoring the outgoing edges. MINERVA's ablation on KINSHIP showed a 27% drop in HITS@1 without that memory, which motivates keeping it.

To fight sparse rewards early in training, we copy KGML-xDTD's recipe. Curated KEGG and Reactome receptor-to-transcription-factor cascades serve as demonstration paths, and a discriminator rewards plausible patterns of relation types. These demonstrations cover only the intracellular segments. No curated relay chains exist to imitate.

The reward. A finished path $\tau$ is laid out across the slice to give a predicted activation $a_\tau(c)$ for every cell $c$ of the query type. Each intercellular hop contributes the ligand expression of nearby sender cells weighted by reciprocal distance (the decay stMLnet adopts). Each intracellular hop contributes the expression of the corresponding node in the cell where that step takes place. The reward is a calibrated correlation:

$$R(\tau) = \frac{\rho\left(a_\tau, r_g\right) - \mu_{\text{null}}(\tau)}{\sigma_{\text{null}}(\tau)}$$

Here $r_g$ is the vector of residuals of gene $g$ across those cells, and $\rho$ is Spearman correlation. $\mu_{\text{null}}$ and $\sigma_{\text{null}}$ are the mean and standard deviation of $\rho$ when sender positions are randomly rotated within the section, which preserves expression but breaks spatial alignment.

The null matters. Without it, the agent would learn to route through highly variable genes, or through cell types that simply sit next to each other everywhere. The null is computed per path, so long paths do not gain credit just by having more factors to multiply.

What we deliver. The outputs are four. The first is a ranked set of discrete paths per query; entropy regularization keeps many distinct chains rather than one. The second is per-section relay calls, meaning paths that contain at least two intercellular hops. The third is an open synthetic benchmark with planted relays. The fourth is a clear statement of when the learned policy is, and is not, needed.

Baselines

The do-nothing reference predicts $g$ from cell-type means alone, so every path scores zero. Any relay claim must first beat this floor.

The natural relay baseline composes single-hop calls. It runs COMMOT, which solves a collective optimal transport problem for ligand-receptor flow under competition between partner molecules and distance costs, on every ligand-receptor pair. It also runs CellChat at the cell-type level. Whenever a significant call $A \to B$ is followed by a ligand of a significant call $B \to C$, and that ligand appears among the receptor's downstream targets in the stMLnet or NicheNet priors, the baseline declares a relay. This baseline uses the same priors and the same sections as our method. A gain over it would show that joint scoring adds something beyond chaining pairwise outputs.

The unguided-walk baselines run on our exact graph. One is SpaTalk's random walk. The other is an expression-weighted personalized PageRank, a random walk that repeatedly restarts at the query node and has its edge weights set by node expression. Both rank paths by visit probability.

The learned-predictor baseline trains HoloNet's attention graph network to predict $g$. It then extracts paths by tracing the attention weights of each view backward through the intracellular prior.

The decoupled multilayer baseline is stMLnet itself. It scores the same layers with random-forest importances.

The ablation that isolates the policy is exhaustive enumeration up to the same path length where that is feasible, and beam search where it is not. It uses exactly our reward, the same compute budget in reward evaluations, and the same graph. A second ablation replaces the expression reward with MINERVA's binary arrival reward, using a single held-out prior target as the label. A third removes the path memory.

All methods get the same sections, graphs, and priors. Hyperparameter search is limited to 50 configurations each, tuned on a held-out section.

Reported numbers. No reported result was found on Lacuna for relay detection, or for any quantitative cell-communication metric on the spatial datasets listed. IGAN, SpaTalk, spARC and HoloNet report qualitative or unnumbered superiority. The only reported numbers for a comparable agent are KGML-xDTD's 94.7% versus 61.4% MultiHop on DrugMechDB, and MINERVA's HITS@10 of 0.83 on NELL-995. We will use them only to verify our agent implementation. Our main baselines' numbers will therefore be produced in this work.

What counts as beating a baseline. On planted relays, we must achieve higher recall at a 10% false discovery rate than composed single-hop calls. On the perturbation data, we must achieve higher precision at the top 50 predicted responders than SpaTalk and stMLnet.

Why not just…?

Why not just use an expression-weighted random walk, as SpaTalk effectively does? It conditions on expression without any training. On short intracellular segments it may be competitive. A walk has no memory and no goal, however, so it cannot express the requirement that a path leave the receiver cell through a newly induced ligand that is then matched to an adjacent receptor. MINERVA's memory ablation is indirect evidence that memoryless walks lose accuracy on compositional queries. The direct test is the comparison on planted relays, separated by path length. If PageRank matches us at two intercellular hops, we will report that.

Why not just enumerate or beam-search all paths under the same reward? This is the real threat. The cell-type-by-molecule graph is modest, and if the reward were a sum of per-edge scores, exact dynamic programming would make reinforcement learning pointless. Our reward is not decomposable: the correlation and its null depend on the whole path. That only means search must evaluate full paths. It does not mean a policy is needed. The case for the policy is amortization: one trained policy proposes paths for thousands of query genes, and for a new section, without re-searching from scratch. The causal question answering agent cut the explored search space by over 99%, which suggests this kind of saving is achievable. We will measure two things against beam search at equal quality: reward evaluations used, and transfer to held-out sections. If beam search matches the policy at equal compute, we will drop the reinforcement-learning claim and present the reward-plus-search method.

Why not just train a graph network like HoloNet and read paths from its attributions? HoloNet predicts expression changes well, but its message passing covers one or two spatial hops, and its attention weights are per ligand-receptor view rather than chains through intermediate proteins. Attribution can produce paths after the fact, and we include that as a baseline. A predictor can also fit residuals through confounded neighbors, which is why our reward uses spatial rotation nulls. If attribution-derived paths score as well on the planted and perturbation checks, the walker adds nothing over it.

Why not just compose single-hop calls from COMMOT or CellChat? Composition at the cell-type level never checks that the cells of type B receiving signal one are the same cells producing ligand two. Composition is cheap and transparent, though, so it is the bar to clear rather than a straw man. The co-localization test below targets exactly this difference.

Proposed Experiments

Implementation check. We first verify the agent against reported numbers: NELL-995 HITS@10 near MINERVA's 0.83, and DrugMechDB mean percentile rank in the range of KGML-xDTD's 94.7%. This separates implementation bugs from failures of the idea.

Synthetic planted relays. We take real Slide-seqV2 and STARmap sections, keep their cell positions and baseline expression, and plant relays $A \to B \to C$ of known molecular identity. Each planted relay perturbs the expression of an induced ligand in B and of a target in C, with a distance-dependent effect. We sweep effect size, dropout, and the fraction of B cells that both receive and secrete.

A decisive variant plants "decoy" structures in which the B cells that receive signal one and the B cells that secrete ligand two are spatially disjoint. A cell-type-level composition calls these relays; a correct method should not. Metrics are recall at fixed false discovery rate, and the decoy rejection rate.

Perturbation validation of intracellular segments. The stMLnet datasets cover TGFB1 and IL6 stimulation, NRP1 knockout, and CXCR4 mutation in breast cancer lines. Using them, we score whether each method's paths from the perturbed ligand or receptor recover the genes that actually respond, measured by precision at top k and area under the precision-recall curve. No published number exists on Lacuna for these datasets, so all methods are run by us under identical priors.

Real tissue. We apply the method to the ten Visium gliomas from spARC, the breast and liver Visium sets used by HoloNet, and human dorsolateral prefrontal cortex. Here there is no ground truth, so the checks are three. Relay calls must reproduce across adjacent sections of the same tumor. Their null-calibrated rewards must hold up on held-out sections the policy never saw. Their false discovery, estimated by running the full pipeline on sections with globally shuffled positions, must stay below 10%.

What would sink the proposal. The idea fails if composed single-hop calls match us on the decoy test, since then joint scoring adds nothing. It also fails if relay calls do not replicate across adjacent sections. The reinforcement-learning component specifically fails if beam search matches the policy at equal compute and on transfer.