arXiv:2608.22139 2026 Regularization 1 ideas extracted · analyzed Aug 29, 2026
The paper proves a sharp lower bound on the nuclear norm, or spectral energy, of a graph adjacency matrix using its rank and average degree. This suggests a spectral anti-collapse regularizer for learned graphs and sparse attention patterns: a learned adjacency should not become spectrally redundant while retaining substantial connectivity. Because exact rank is nondifferentiable, the theorem can be converted into a practical soft constraint using singular values and an effective-rank surrogate. The weighted-graph extension is a falsifiable heuristic rather than a theorem, so validation should explicitly test both the learned weighted graph and thresholded discrete graphs.
Add a spectral regularizer to a learned graph or sparse attention adjacency that penalizes violation of the paper's energy floor. The regularizer discourages adjacency matrices that retain many edges but collapse into a low-dimensional spectral structure, which may reduce graph-message-passing diversity and worsen oversmoothing.