# Caveman-calibrated resolution schedule

- ID: 2912
- Canonical URL: https://synthcore.org/idea/2912/caveman-calibrated-resolution-schedule
- API JSON: https://synthcore.org/api/idea/2912.json
- API Markdown: https://synthcore.org/api/idea/2912.md
- Verification status: unverified
- Source: [arXiv:2608.30934](https://arxiv.org/abs/2608.30934)
- Category: training
- Solves: accuracy, generalization, stability
- ML areas: graph-nn, loss, scheduler
- Math tags: graph-theory, combinatorics, optimization
- Ratings: usefulness 5/10; difficulty 3/10; novelty 8/10

## Idea description

Use the paper's analytic merging threshold to choose the Scaled-NAP exponent from an intended community size rather than treating alpha as an arbitrary hyperparameter. A warm-started schedule can begin with persistence-like fine structure and increase alpha only when the model has learned reliable local groups.

## Mathematical statement

In a connected Caveman graph with q caves, each cave formed from a clique of p>=3 vertices by rewiring one internal edge, the paper states that as q tends to infinity, the adjacent-cave merging threshold converges to T_alpha^bin=[p(p-1)-2](2^(1-alpha)-1). Two adjacent caves merge if and only if alpha>alpha*, where alpha*=1-log_2((p(p-1)-1)/(p(p-1)-2)). Here p is the desired local group size and alpha* is the resolution boundary at which two such groups become preferable to keeping them separate. For a neural model, estimate a target size p_hat from the median predicted cluster size or domain metadata, then initialize alpha just below the boundary so communities of size p_hat are not immediately merged. A differentiable schedule can increase alpha toward one as training progresses.

## Key formulas

- $$T_{\alpha}^{\mathrm{bin}}\xrightarrow[q\to\infty]{}\bigl(p(p-1)-2\bigr)\left(2^{1-\alpha}-1\right).$$
- $$\alpha^*(p)=1-\log_2\left(\frac{p(p-1)-1}{p(p-1)-2}\right),\qquad\text{merge adjacent caves iff }\alpha>\alpha^*(p).$$
- $$\alpha_t=\operatorname{clip}\left(\alpha_0+(\alpha_{max}-\alpha_0)\left(\frac{t}{T}\right)^\gamma,\,0,\,1\right),\qquad \alpha_0=\max\{0,\alpha^*(\hat p)-\delta\}.$$

## Implementation notes

Use this at the Scaled-NAP loss layer rather than in the encoder's message-passing operation. Choose a target group size p_target from graph metadata; if unavailable, use p_hat=n/R, where R is the desired number of pools, or recompute the median nonempty soft-cluster size every few epochs. Evaluate alpha*(p_hat)=1-log_2((p_hat(p_hat-1)-1)/(p_hat(p_hat-1)-2)), clamp p_hat to at least 3, and initialize alpha_0=max(0, alpha*-0.05). During the first T optimizer steps, update alpha_t with the displayed power schedule toward alpha_max=1; use gamma=1 for a linear schedule or gamma=2 for a slower initial increase. At every step compute Q_alpha_t from the soft assignments using the formulas in the first idea. The Caveman formula is a calibration heuristic derived under clique-like assumptions, so test it rather than assuming that its guarantee transfers to arbitrary graphs. Run a cheap synthetic experiment with 1,000-node planted-partition graphs containing community sizes 8, 16, 32, and a four-size heterogeneous mixture. Compare fixed alpha values with the calibrated schedule in a GCN community-classification model. Measure ARI, NMI, premature cluster merging, final cluster-size error, and training variance across seeds. Success is fewer early merges and higher recovery on heterogeneous graphs at equal final cluster count; failure is no improvement over a fixed alpha=0.5 baseline.

## Disclaimer

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