Positive Spectral-Energy Budget for Learned Graphs

Integrate this at the learned-adjacency stage of a GNN or graph transformer. Let node features be H in R^{n x d}; construct nonnegative edge scores with S=softplus(H Q (H K)^T / sqrt(d)), symmetrize W=(S+S^T)/2, and optionally zero the diagonal. Use W in message passing, for example H_next=sigma(W H V), while adding beta times L_PSE to the task loss. Here n is the number of nodes in the graph and r is a chosen complexity budget: r=2 is a strong low-clique constraint, while larger r permits more positive spectral energy. For small graphs, compute all eigenvalues of W with a symmetric eigensolver each training step. For larger graphs, estimate the top k positive eigenvalues using k-step Lanczos on W; use s_plus_hat=sum_{j=1}^k max(theta_j,0)^2 and stop increasing k when the residual energy estimate is below a tolerance. Pseudocode is: construct W; theta=Lanczos(W,k); s=sum(max(theta,0)^2); penalty=relu(sqrt(s)-tau)^2; loss=task_loss+beta*penalty; backpropagate. The theorem supplies the target scale and explains why positive, rather than absolute, eigenvalues are penalized; the eigenvalues and gradients are estimated numerically. First test on Cora or a synthetic stochastic-block graph with a 2-layer GCN whose adjacency is learned from node features. Compare no spectral penalty, a largest-eigenvalue penalty, and PSE at matched parameter count and FLOPs. Measure validation accuracy, oversmoothing via pairwise cosine similarity of final node embeddings, spectral energy, and training stability. Success means lower embedding collapse and comparable or better accuracy at the same message-passing depth; a stronger result is improved accuracy when increasing depth from 2 to 6 layers without exploding positive spectral energy.