Spanning-Tree Connectivity Loss

Integrate the loss after any module that produces a soft graph: graph-neural-network edge scores, transformer sparsification masks, or MoE routing links. Let logits s_ij define symmetric nonnegative weights w_ij=softplus((s_ij+s_ji)/2), optionally restricted to candidate edges. Construct L=diag(W1)-W for a batch graph with N nodes. Compute L_tree=-logdet(L+11^T/N)+log N using a Cholesky factorization; the rank-one term shifts the single zero eigenvalue to one while leaving all other eigenvalues unchanged, making the loss equivalent to negative log pseudo-determinant. Minimize task_loss+alpha*L_tree, with alpha swept over {1e-4,1e-3,1e-2}; retain gradients through the Cholesky factor. For large N, use stochastic Lanczos quadrature to estimate logdet, or apply the exact objective independently to graph clusters and combine cluster values using the paper's multiplicative gluing correction when modules share an interface of size l. The theorem supplies the spanning-tree interpretation and interface factor; the weighted extension is an empirical adaptation and must be checked against exact eigendecomposition on small graphs. First test a 6-layer GCN with learned top-k edges on synthetic two-community graphs and ZINC, against no regularizer and a simple degree penalty. Record the Fiedler eigenvalue, number of connected components, validation accuracy, and training variance. Success is zero disconnected predictions, larger minimum algebraic connectivity, and improved accuracy without materially increasing wall-clock time.