# Polyhedral degree-budget regularizer

- ID: 2633
- Canonical URL: https://synthcore.org/idea/2633/polyhedral-degree-budget-regularizer
- API JSON: https://synthcore.org/api/idea/2633.json
- API Markdown: https://synthcore.org/api/idea/2633.md
- Verification status: unverified
- Source: [arXiv:2608.20778](https://arxiv.org/abs/2608.20778)
- Category: regularization
- Solves: memory, generalization, stability
- ML areas: graph-nn, attention, pruning, regularization
- Math tags: graph-theory, combinatorics, convex-analysis, optimization
- Ratings: usefulness 6/10; difficulty 5/10; novelty 6/10

## Idea description

Train a graph neural network with a learnable fractional graph mask constrained toward the tree-double-matching polytope. This gives the model a global connectivity constraint while penalizing attention patterns that concentrate too many incident edges on individual vertices.

## Mathematical statement

The feasible region is Theta(G)=P(G) intersection 2M(G). A point x in P(G) satisfies the spanning-tree mass constraint x(E)=n-1 and rank inequalities x(E(S))<=|S|-1, which discourage allocating all mask mass inside a disconnected or overly concentrated subgraph. Membership in 2M(G) includes the local degree constraints x(E(v))<=2 and scaled matching odd-set constraints. For a neural mask a_e, use a differentiable penalty relaxation: enforce total mask mass near n-1, penalize violated subset rank inequalities, and penalize degree budgets above two. Since enumerating every subset S is infeasible, use an active-set approximation containing neighborhoods, connected components, and empirically discovered violated cuts. This transfers the paper's polyhedral structure directly as a global sparsity-and-connectivity regularizer rather than as an ordinary L1 penalty.

## Key formulas

- $$\Theta(G)=P(G)\cap 2M(G)$$
- $$x(E)=|V|-1,\qquad x(E(S))\le |S|-1\quad(\varnothing\ne S\subsetneq V)$$
- $$x(E(v))=\sum_{e\ni v}x_e\le 2$$
- $$\mathcal{L}_{\mathrm{poly}}(a)=\alpha\left(\sum_{e\in E}a_e-(n-1)\right)^2+\beta\sum_{S\in\mathcal{C}}\left[\sum_{e\in E(S)}a_e-(|S|-1)\right]_+^2+\gamma\sum_{v\in V}\left[\sum_{e\ni v}a_e-2\right]_+^2$$

## Implementation notes

Insert the mask directly before aggregation in a GNN or graph transformer. For each edge e=(u,v), compute a raw score q_e from the endpoint embeddings and set a_e=epsilon+(1-2epsilon)sigmoid(q_e), so every edge remains numerically available while the learned values become sparse. Add L_poly to the task loss. In every minibatch, evaluate the global mass constraint and all vertex degree constraints. Maintain an active subset family C for rank inequalities: initialize C with local neighborhoods and connected components, then every K optimization steps identify the most violated cuts using a min-cut or separation routine, add the five worst violations, and remove constraints that remain inactive for several epochs. Anneal alpha, beta, and gamma from zero during the first 10% of training to avoid early optimization collapse. The exact computed object is a penalty relaxation of Theta(G); the finite active set is an empirical approximation to all cut constraints. Test a 3-layer GraphSAGE and GAT on Cora, PubMed, and ogbn-arxiv against standard attention, L1 edge sparsity, and top-k pruning at matched average edge count. Record accuracy, peak GPU memory, effective edge count, connected components after thresholding, maximum mask degree, and training variance. The target is equal accuracy with n-1 to 2(n-1) effective edges and fewer disconnected supports than L1 or top-k baselines.

## Disclaimer

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