Independent-Set Neural Output Head

Integrate this at the final output layer of a multilabel predictor, graph action policy, or MoE router. Let the neural representation be $h\in\mathbb{R}^d$ and let each graph vertex $v$ have logit $z_v=w_v^\top h+b_v$. Construct an undirected incompatibility graph $G=(V,E)$; an output vector $n\in\{0,1\}^{|V|}$ is feasible only when $n_in_j=0$ for every edge $(i,j)\in E$. The forward pass is: (1) compute all logits $z_v$; (2) build unary factors $\phi_v(n_v)=\exp(z_vn_v)$ and edge factors $\psi_{ij}(n_i,n_j)=\mathbf{1}[n_in_j=0]$; (3) run sum-product variable elimination on a junction tree of $G$ to obtain $\log Z=\log\sum_{n\text{ feasible}}\exp(\sum_vn_vz_v)$ and node marginals $\mu_v=\mathbb{E}[N_v]$; (4) train with negative log likelihood $\mathcal{L}=\log Z-\sum_vn_vz_v$. Pseudocode: z = W @ h + b; unary[v] = exp(z[v] * state[v]); edge[i,j] = indicator(state[i]*state[j] == 0); logZ, marginals = junction_tree_sum_product(unary, edge); loss = logZ - dot(y,z); backprop(loss). The exact gradient is $n_v-\mu_v$, so no Monte Carlo estimate is needed when the graph has small treewidth. For larger-treewidth graphs, use loopy belief propagation or beam enumeration only as an explicitly approximate ablation. Start with a 20-vertex synthetic incompatibility graph and a 2-layer MLP, then test on multilabel classification or an MoE router where co-activating adjacent experts is undesirable. Compare unconstrained sigmoid outputs, post-hoc greedy independent-set projection, and a soft edge-penalty loss. Success means zero invalid predictions by construction, better constrained-set exact match or NLL at equal parameter count, and more stable training than penalty-based constraints; also report wall-clock overhead as treewidth increases.