Rank-energy anti-collapse regularizer
Implementation & benchmark of arXiv:2608.22139 — Rank-Average Degree Bound for Graph Energy
Source paper: Rank-Average Degree Bound for Graph Energy arXiv:2608.22139 ⓘ · analyzed Aug 29, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
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.
Formulas
Mathematical statement
For a simple undirected graph with adjacency matrix $A\in\mathbb{R}^{n\times n}$, eigenvalues $\lambda_1,\ldots,\lambda_n$, edge count $m$, rank $r=\operatorname{rank}(A)$, and average degree $\bar d=2m/n$, the paper proves for $n\geq5$ that the graph energy satisfies $\mathcal{E}(G)=\sum_{i=1}^n|\lambda_i|\geq r+\bar d-1$. Since $A$ is symmetric, this energy is its nuclear norm, $\|A\|_*=\sum_i\sigma_i(A)$, where $\sigma_i(A)=|\lambda_i|$. For a differentiable nonnegative weighted adjacency $W=W^\mathsf{T}$, define $E(W)=\sum_i\sigma_i(W)$, weighted average degree $\bar d(W)=n^{-1}\mathbf{1}^\mathsf{T}W\mathbf{1}$, and smooth effective rank $r_\tau(W)=\sum_i(1-e^{-\sigma_i(W)/\tau})$, with temperature $\tau>0$. The adapted differentiable floor is $F(W)=r_\tau(W)+\bar d(W)-1$, and the penalty is $L_{RE}=\operatorname{softplus}(F(W)-E(W))^2$. As $\tau\to0$, each nonzero singular value contributes approximately one to $r_\tau$, recovering numerical rank. The exact theorem applies to unweighted simple graphs; applying it to weighted learned adjacencies is an empirical extension that must be tested.
Implementation notes
(1) Integrate the regularizer immediately after the module that constructs a learned graph, graph-attention matrix, or sparse token adjacency. Given node or token features $H\in\mathbb{R}^{n\times d}$, construct a nonnegative symmetric matrix, for example $W=\operatorname{sigmoid}((HH^\mathsf{T}+HH^\mathsf{T\mathsf{T}})/(2\sqrt d))$, then set the diagonal to zero. If the model already produces attention weights, use those weights after symmetrizing them; preserve the existing task loss and add $\lambda_{RE}L_{RE}$. (2) Implement the following loop: S=(W+W.T)/2; S.fill_diagonal_(0); sigma=torch.linalg.svdvals(S); energy=sigma.sum(); effective_rank=(1-torch.exp(-sigma/tau)).sum(); average_degree=S.sum()/n; floor=effective_rank+average_degree-1; penalty=torch.nn.functional.softplus(floor-energy)**2; loss=task_loss+lambda_RE*penalty; loss.backward(). Use full SVD for graphs with at most a few hundred nodes and randomized SVD or a Lanczos approximation for larger graphs. (3) The paper supplies the exact inequality for binary simple graphs. The implementation computes the nuclear norm and smooth rank exactly for the current weighted matrix, while the weighted inequality is only a hypothesis. During evaluation, threshold $W$ at several thresholds, form binary matrices $A_t$, compute $\|A_t\|_*$, numerical rank using singular values above $10^{-6}\|A_t\|_2$, and $2m_t/n$, and measure whether the discrete theorem holds. Also log feature rank after every message-passing layer, adjacency density, singular-value decay, and degree variance. (4) Begin with a cheap experiment on Cora and a synthetic stochastic-block-model dataset using a 3-layer GCN or GAT. Compare the baseline against $\lambda_{RE}\in\{10^{-4},10^{-3},10^{-2}\}$ and $\tau\in\{0.01,0.05,0.1\}$, keeping parameter count and training FLOPs fixed. The primary success signal is higher validation accuracy or macro-F1 at equal compute together with higher post-layer feature rank and reduced oversmoothing. Reject the method if it only increases edge density, destabilizes training, or gives no improvement over a standard entropy or attention-diversity regularizer.
Verification
This idea has not been verified yet.
Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.
Artifacts
Artifacts unavailable.