Cycle-stable graph MoE routing
Source paper: Graph Coloring with Color Preferences arXiv:2609.00569 ⓘ · analyzed Sep 2, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Use the graph-coloring stability concept to route graph nodes to experts. Nodes rank experts by router logits, adjacent nodes are constrained to use different experts, and a blocking cycle is a directed cycle in which every node prefers the expert currently assigned to the next node. Eliminate profitable feasible cycles or penalize their existence so routing reaches a locally stable assignment instead of oscillating between equally plausible expert allocations.
Formulas
Mathematical statement
For a graph G=(V,E), a k-coloring is a map \(\phi:V\to\{1,\ldots,k\}\) with \(\phi(u)\neq\phi(v)\) for every edge \(uv\in E\). Each vertex v has a strict preference relation \(\succ_v\) over colors. A directed cycle \(v_1,\ldots,v_t,v_1\) is blocking when every vertex strictly prefers the color held by the next vertex to its own: \(\phi(v_{i+1})\succ_{v_i}\phi(v_i)\), with \(v_{t+1}=v_1\). The paper defines \(\chi_{\mathrm{stable}}(G,\succ)\) as the minimum k admitting a proper coloring with no blocking cycle, and \(\chi_{\mathrm{stable}}(G)=\sup_{\succ}\chi_{\mathrm{stable}}(G,\succ)\). It also gives an upper bound from any acyclic orientation D of G: if \(R_D(v)\) is the set of vertices reachable from v by directed paths, including v, then \(\chi_{\mathrm{stable}}(G)\leq\max_{v\in V}|R_D(v)|\). In the neural adaptation, router logits \(s_{v,e}\) induce preferences \(e\succ_v e'\iff s_{v,e}>s_{v,e'}\); the implementation uses the stronger practical condition that every applied cycle rotation must remain proper, while separately measuring all blocking cycles whether or not their rotation is feasible.
Implementation notes
Integrate this after router-logit computation in a graph mixture-of-experts GNN. Let x_v be the node representation, s_{v,e}=w_e^ op x_v be the logit for expert e, and let phi(v)=argmax_e s_{v,e} after adding tiny deterministic noise to break ties. First construct a proper initial assignment with a greedy pass over a chosen acyclic orientation of the graph: process vertices in topological order and assign the highest-ranked expert not used by already-colored neighbors. If the number of experts K is smaller than the greedy requirement, start from ordinary top-1 routing and repair conflicts by assigning the least-conflicting available expert. Then run cycle improvement. Build a directed preference graph with an arc v->u whenever v prefers phi(u) to phi(v). Enumerate short simple cycles of length 2 through L, using L=4 or 6 initially; for each cycle, test the rotated assignment phi'(v_i)=phi(v_{i+1}) and accept it only if every node strictly improves and phi' remains proper on all incident edges. Apply a maximal set of vertex-disjoint accepted cycles, recompute affected arcs, and repeat for at most 10 rounds. Every accepted move strictly increases the sum of integer preference ranks, so finite assignment space prevents an infinite sequence, although short-cycle search only approximates full stability. During training use a straight-through estimator for the discrete assignment and add lambda times the sampled blocking-cycle count, normalized by sampled vertex subsets, to the task loss. Estimate the orientation bound by computing reachability on the selected DAG; use it as an expert-count heuristic or diagnostic, not as a guarantee that this implementation attains the theorem. The first experiment should use a 2-layer GraphSAGE or GAT on Cora with K=4 experts, comparing top-1 routing, greedy proper routing, and cycle-stable routing. Measure validation accuracy, expert-load entropy, exhaustively counted blocking cycles on small graphs, routing overhead, and accepted-rotation fraction. A useful signal is at least 30% fewer blocking cycles and lower run-to-run routing variance at equal accuracy with less than 10% extra routing time.
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.