Induced-Star-Free Stable Graph Propagation

Integrate this into a sparse graph neural network or a hard top-r attention router. Represent the graph by a binary adjacency matrix A, with self-loops excluded when computing neighborhoods; use the symmetrized edge set if the original router is directed. At each training step, construct the current graph, compute degrees d(v), and set \(\Delta=\max_v d(v)\). Choose a fixed k such as 3 or 4. Add a local independent-set violation penalty. For sampled k-tuples T contained in \(N(v)\), define \(q(T)=\prod_{\{i,j\}\subseteq T}(1-A_{ij})\); q(T)=1 exactly when T is independent, so penalize \(R_{\mathrm{star}}=\sum_v\sum_{T\subseteq N(v),|T|=k}q(T)\), using random tuple sampling for large neighborhoods. For soft attention weights, replace Aij by a sigmoid edge probability and use the same product as a differentiable surrogate, but treat the theorem as a certificate only after thresholding the graph and checking violations. In the forward pass use Laplacian residual propagation: compute \(Z=L_GH\), then \(H_{new}=\sigma(W H-\eta Z)\), with \(\eta=\rho\,2/[(2-2/k)(\Delta+1)]\) and swept \(\rho\in[0,1]\). The theorem supplies the bound; empirical code estimates the actual \(\lambda_{\max}\) by 10-step power iteration and measures the fraction of violated neighborhoods. First experiment: compare a 6-layer GCN on Cora or OGBN-Arxiv against the same model with unconstrained sparse edges, using equal hidden size and FLOPs. Test whether the constrained model permits larger stable \(\eta\), has fewer exploding activations, and improves validation accuracy at equal depth; also compare the certified bound with the measured Laplacian spectral radius.