Collision-Aware Graph Edge Router
Implementation & benchmark of arXiv:2607.29409 — The Zombie Infection Model
Source paper: The Zombie Infection Model arXiv:2607.29409 ⓘ · analyzed Aug 31, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Use the model's non-monotonicity result to make graph connectivity a learned resource rather than assuming that every extra edge helps. An edge router assigns transmission scores but also charges a source-side collision cost for exposing an infected node to many susceptible neighbors. The resulting router can prune edges that increase competition and reduce useful reachability.
Formulas
Mathematical statement
The paper gives a concrete counterexample to monotone connectivity. Let $G_1$ contain only edge $x-y$, and let $G_2$ add node $z$ with edge $z-x$. Starting with $x$ infected and using removal rate $\mu=1$, define $$p=\frac{\lambda}{1+\lambda}.$$ The probability that $y$ is ever infected is $$P_{G_1}=p$$ on $G_1$, but $$P_{G_2}=\frac{p}{2}(1+p)<p$$ on $G_2$. The extra susceptible neighbor creates an additional competing removal opportunity, so more connectivity can reduce target reachability. For a neural edge score $q_{ij}\geq0$, destination susceptibility $s_j\in[0,1]$, and source collision load $$c_i=\sum_jq_{ij}s_j,$$ use the local surrogate $$\widetilde P_{ij}=\frac{q_{ij}}{q_{ij}+\mu c_i}\left(1-e^{-q_{ij}}\right).$$ Here $q_{ij}$ is learned transmission intensity, $\mu c_i$ is competing source removal intensity, and $1-e^{-q_{ij}}$ is a saturating probability of successful transmission. Train with $$\mathcal L_{\mathrm{route}}=\mathcal L_{\mathrm{task}}+\beta\sum_i c_i^2+\gamma\sum_{(i,j)\in E}(1-g_{ij})q_{ij},$$ where $g_{ij}=\operatorname{sigmoid}(u_{ij}/ au)$ is a soft edge gate and $ au$ is its temperature.
Implementation notes
Integrate this into the edge-scoring operation of a graph attention layer or graph-retrieval index. For every candidate edge $(i,j)$, compute an ordinary compatibility logit $u_{ij}=\operatorname{MLP}([x_i,x_j])$, transmission intensity $q_{ij}=\operatorname{softplus}(u_{ij})$, and susceptibility $s_j=\operatorname{sigmoid}(w_s^Tx_j)$. Aggregate the source collision load with c_i = scatter_sum(q_ij * s_j, source=i). Modify the attention score using score_ij = log(q_ij + eps) - alpha * log(q_ij + mu*c_i + eps), where $\alpha\geq0$ controls collision sensitivity. Apply a sigmoid gate, then retain either the top $k$ edges per source or a fixed threshold: g = sigmoid((score - threshold)/tau) and edges = topk(score, k). Normalize retained scores with a per-source softmax and aggregate values. Add the regularizer $\beta\sum_i c_i^2$ and optionally the negative surrogate reachability term $-\sum_{ij}\widetilde P_{ij}$. The paper supplies the exact two-neighbor counterexample and motivates the collision term; $q$, $s$, $\alpha$, $\beta$, and $\mu$ are estimated by backpropagation or validation tuning. Validate the surrogate by randomly ablating edges and correlating ablation benefit with $c_i$. First test a two-layer GAT on Cora and OGB-Arxiv at $k\in\{4,8,16\}$ against dense GAT and ordinary top-$k$ GAT, with 0%, 25%, and 100% random distractor edges. Success is equal-or-better accuracy using two to four times fewer edges and lower accuracy degradation under distractor edges.
Verification
This idea has not been verified yet.
Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.
Artifacts
Artifacts unavailable.