# Collision-Aware Graph Edge Router

- ID: 1597
- Canonical URL: https://synthcore.org/idea/1597/collision-aware-graph-edge-router
- API JSON: https://synthcore.org/api/idea/1597.json
- API Markdown: https://synthcore.org/api/idea/1597.md
- Verification status: unverified
- Source: [arXiv:2607.29409](https://arxiv.org/abs/2607.29409)
- Category: architecture
- Solves: accuracy, scalability, generalization
- ML areas: graph-nn, attention, moe-routing
- Math tags: stochastic-processes, probability, graph-theory, optimization
- Ratings: usefulness 5/10; difficulty 5/10; novelty 7/10

## 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.

## 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.

## Key formulas

- $$\mathbb P^{\mathrm{ZIM}}_{\lambda,G_1,x}(\eta_t(y)=I\text{ for some }t>0)=p,\qquad p=\frac{\lambda}{1+\lambda}.$$
- $$\mathbb P^{\mathrm{ZIM}}_{\lambda,G_2,x}(\eta_t(y)=I\text{ for some }t>0)=\frac p2(1+p)<p.$$
- $$c_i=\sum_jq_{ij}s_j,\qquad \widetilde P_{ij}=\frac{q_{ij}}{q_{ij}+\mu c_i}\left(1-e^{-q_{ij}}\right).$$
- $$\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},\qquad g_{ij}=\operatorname{sigmoid}(u_{ij}/\tau).$$

## 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.

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.