# Simplicial Ky-Fan Spectral Budget

- ID: 1206
- Canonical URL: https://synthcore.org/idea/1206/simplicial-ky-fan-spectral-budget
- API JSON: https://synthcore.org/api/idea/1206.json
- API Markdown: https://synthcore.org/api/idea/1206.md
- Verification status: unverified
- Source: [arXiv:2607.20910](https://arxiv.org/abs/2607.20910)
- Category: regularization
- Solves: stability, accuracy, generalization
- ML areas: graph-nn, regularization, training-dynamics
- Math tags: spectral-theory, graph-theory, combinatorics, linear-algebra
- Ratings: usefulness 6/10; difficulty 6/10; novelty 7/10

## Idea description

Use the conjugate degree sequence of codimension-one faces as a mathematically justified upper envelope for the spectrum of a simplicial up-Laplacian. Penalize violations of the corresponding top-k eigenvalue budgets in a simplicial message-passing layer, discouraging a few dominant propagation modes that cause oversmoothing or unstable amplification.

## Mathematical statement

Let K be a pure r-dimensional simplicial complex, let F_{r-1}(K) be its oriented (r-1)-faces, and let F_r(K) be its r-faces. The boundary matrix B_r is the signed incidence matrix from r-faces to (r-1)-faces, with entries in {0,+1,-1}; the up-Laplacian on (r-1)-chains is L^{\operatorname{up}}_{r-1}=B_rB_r^*. For each (r-1)-face \sigma, define its degree d(\sigma) as the number of r-faces containing \sigma. Sort the degrees in nonincreasing order and define the conjugate degree sequence d^    op_j=|{\sigma\in F_{r-1}(K):d(\sigma)\ge j}|. The paper proves the majorization relation \boldsymbol{\lambda}_{r-1}(K)\preccurlyeq\mathbf d_{r-1}^{    op}(K), meaning that for every k, the sum of the k largest eigenvalues satisfies \sum_{i=1}^k\lambda_i\le\sum_{j=1}^k d_j^    op, with equality at the full dimension because both totals equal the trace. For a learnable weighted incidence matrix \widetilde B_r, estimate its top-k eigenvalues and penalize excess over these degree-derived budgets. The original theorem applies exactly to unweighted signed incidence, so the learned-weight version is an empirical extension rather than a theorem.

## Key formulas

- $$L^{\operatorname{up}}_{r-1}(K)=\partial_r\partial_r^*=B_rB_r^*.$$
- $$d_{r-1,j}^{\top}(K)=\left|\left\{\sigma\in F_{r-1}(K):d(\sigma)\ge j\right\}\right|,\qquad d(\sigma)=\left|\left\{\tau\in F_r(K):\sigma\subset\tau\right\}\right|.$$
- $$\boldsymbol{\lambda}_{r-1}(K)\preccurlyeq\mathbf d_{r-1}^{\top}(K),\qquad \sum_{i=1}^{k}\lambda_{r-1,i}(K)\leq\sum_{j=1}^{k}d_{r-1,j}^{\top}(K).$$
- $$\mathcal L_{\mathrm{budget}}=\sum_{k\in\mathcal K}\left[\sum_{i=1}^{k}\widehat\lambda_i(\widetilde B_r\widetilde B_r^*)-\sum_{j=1}^{k}d_{r-1,j}^{\top}(K)\right]_+^2.$$

## Implementation notes

Integrate this into a simplicial or hypergraph message-passing layer whose propagation matrix is P=\widetilde B_r\widetilde B_r^*, acting on features X\in\mathbb R^{|F_{r-1}|    imes c}. Start with the exact signed incidence matrix B_r, optionally multiply each incidence column or nonzero entry by a learned positive gate g, and define \widetilde B_r=B_r\operatorname{diag}(g) or a symmetrically normalized variant. Precompute every codimension-one-face degree d(\sigma), construct the sorted conjugate sequence d^    op, and select a small set \mathcal K such as {1,2,4,8}. During each training step, estimate the largest k eigenvalues of P using k-step Lanczos or simultaneous power iteration; do not form P densely, and implement matrix-vector products as v\mapsto\widetilde B_r(\widetilde B_r^*v). Add \alpha\mathcal L_{\mathrm{budget}} to the task loss. Pseudocode: compute X_next=activation(XW+\beta PX); for k in \mathcal K, run Lanczos(P,k) to obtain \widehat\lambda_1,\ldots,\widehat\lambda_k; compute budget_k=\sum_{j=1}^k d_j^    op; add relu(\sum_i \widehat\lambda_i-budget_k)^2. The mathematical budget is computed exactly from the input complex; eigenvalues are estimated numerically, and the theorem is a certificate only when g=1. First test on a small synthetic simplicial classification benchmark, comparing a 4-layer simplicial GNN against the same model without the penalty. Measure validation accuracy, feature Dirichlet energy, largest propagation eigenvalue, gradient norm, and oversmoothing as depth increases. Success is a lower top-eigenvalue tail and stable accuracy at 8-16 layers without increasing per-epoch cost by more than the Lanczos overhead.

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.