Anchor-aware giant-core regularization
Implementation & benchmark of arXiv:2608.25560 — $(k,n)$-core percolation on hypergraphs with anchor nodes
Source paper: $(k,n)$-core percolation on hypergraphs with anchor nodes arXiv:2608.25560 ⓘ · analyzed Sep 1, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Represent a higher-order neural computation as a bipartite incidence graph between node features and hyperedges, and assign each node-hyperedge incidence an anchor probability or learned anchor score. Add a regularizer that maximizes the predicted size of the surviving (k,n)-core under random node, hyperedge, or token dropout, thereby preventing structured pruning or routing from disconnecting essential higher-order computations. At inference, retain only incidences belonging to the predicted or explicitly computed anchor-aware core.
Formulas
Mathematical statement
The paper's first-neighbor cavity equations define W as the probability that following a random factor-graph link from a hyperedge reaches a node connected to the giant core, and V as the probability that following a link from a node reaches a hyperedge in the giant core. For node-degree distribution P(q), hyperedge-cardinality distribution Q(m), mean node degree <q>, mean hyperedge size <m>, node retention p_N, hyperedge retention p_H, core thresholds k and n, and independent anchor probability theta, the fixed point is W = p_N sum_{q>=k} [qP(q)/<q>] sum_{s=k-1}^{q-1} C(q-1,s)V^s(1-V)^(q-1-s). The hyperedge-to-node recursion is V = p_H sum_{m>=n} [mQ(m)/<m>] sum_{p=0}^{m-1} C(m-1,p) theta^p(1-theta)^(m-1-p) sum_{s=max(0,n-1-p)}^{m-1-p} C(m-1-p,s) W^(s+p)(1-W)^(m-1-s-p). Here p counts anchor incidences and s counts non-anchor incidences that provide support; the lower bound n-1-p expresses that anchors and surviving non-anchors jointly meet the hyperedge threshold. The neural adaptation uses theta_ei = sigmoid(a_ei), p_N and p_H as measured keep probabilities, and maximizes the fixed point or an empirical core-size estimate. Because the formula assumes a locally tree-like random hypergraph and independent incidences, it is an ensemble proxy rather than an exact guarantee for dense neural hypergraphs.
Implementation notes
Integrate this into a hypergraph neural network or grouped higher-order attention layer whose incidence tensor is A[e,i], where e indexes hyperedges and i indexes node or token incidences. Give every incidence a trainable anchor logit a[e,i], with anchor probability theta[e,i] = sigmoid(a[e,i]). During training, use the current binary or soft routing mask to estimate P(q) from node degrees and Q(m) from active hyperedge sizes. Estimate p_N as the mean node keep probability and p_H as the mean hyperedge keep probability. For fixed thresholds k and n, initialize W=V=0.5 and run 10-30 damped fixed-point iterations: W_new=F_W(V), V_new=F_V(W), then W=rho*W_new+(1-rho)*W and V=rho*V_new+(1-rho)*V, with rho between 0.2 and 0.8. Implement binomial sums with log-space binomial coefficients or precomputed tables, and clamp probabilities to [1e-6,1-1e-6]. Define the regularizer as -W*V, or preferably an estimated giant-core fraction computed from node and hyperedge survival probabilities. Add an anchor-budget penalty such as lambda_anchor times the mean theta so the model cannot mark every incidence as an anchor; optionally add the entropy penalty lambda_entropy times theta(1-theta) to encourage decisive roles. Backpropagate through the unrolled iterations, or use stop-gradient on degree histograms if histogram differentiation is unstable. At inference, threshold anchor scores and retain incidences whose cavity messages exceed 0.5, or use the score only to select a global pruning ratio. The fixed-point recursion is taken directly from the paper; the degree histograms and exact-core correlation must be estimated empirically. First test a 2-layer hypergraph neural network on synthetic hypergraph node classification with random incidence dropout and magnitude pruning. Compare no regularizer, degree-preserving pruning, and this regularizer at equal parameter count. Measure validation accuracy after dropout, exact (k,n)-core fraction, and accuracy variance across masks. Success means a larger retained core and lower accuracy variance at equal FLOPs without substantial clean-data accuracy loss.
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.