# Fundamental-Cycle Compatibility Basis

- ID: 2954
- Canonical URL: https://synthcore.org/idea/2954/fundamental-cycle-compatibility-basis
- API JSON: https://synthcore.org/api/idea/2954.json
- API Markdown: https://synthcore.org/api/idea/2954.md
- Verification status: mech_ok_no_baseline
- Source: [arXiv:2608.31120](https://arxiv.org/abs/2608.31120)
- Category: scalability
- Solves: scalability, speedup, stability
- ML areas: loss, regularization, graph-nn, inference-speedup
- Math tags: graph-theory, topology, linear-algebra, algebra
- Ratings: usefulness 7/10; difficulty 5/10; novelty 8/10

## Idea description

For sparse conditional supports, replace enumeration of all possible four-cycles with a graph-theoretic cycle basis. Construct the bipartite support graph, choose a spanning forest, and penalize one residual for each non-tree edge and its induced fundamental cycle. In log space, every other cycle constraint is a linear combination of these basis constraints, yielding a principled sparse regularizer.

## Mathematical statement

Let G=(V,E) be the bipartite support graph: V contains all X-values and Y-values, and an edge (x,y) belongs to E when both conditional probabilities on that pair are positive or allowed by the support mask. Define the edge field a_xy = log q_theta(x|y) - log r_phi(y|x). If the conditionals come from a compatible joint with positive margins, then a_xy = u_x - v_y for node potentials u_x and v_y. Consequently, the signed sum of a_xy around every closed graph cycle C is zero. If G has |V| vertices, |E| edges, and C connected components, its cycle-space dimension is |E|-|V|+C. Choose a spanning forest T. Each non-tree edge e creates a fundamental cycle C_e by adding e to the unique path in T joining its endpoints. Penalize R_basis = sum over non-tree edges of rho(sum over cycle edges of s_xy a_xy), where s_xy is +1 or -1 according to the orientation of that edge in the cycle and rho is squared or Huber loss. Vanishing on a cycle basis implies vanishing on every cycle because cycle sums are additive over the graph cycle space.

## Key formulas

- $$a_{xy}=\log q_\theta(x|y)-\log r_\phi(y|x)$$
- $$a_{xy}=u_x-v_y\quad\Longrightarrow\quad \sum_{(x,y)\in C}s_{xy}a_{xy}=0\ \text{for every closed cycle }C$$
- $$\dim\mathcal{C}(G)=|E|-|V|+C$$
- $$R_{\mathrm{basis}}=\sum_{e\in E\setminus T}\rho\left(\sum_{(x,y)\in C_e}s_{xy}a_{xy}\right)$$

## Implementation notes

Integrate this as a sparse-support regularizer for graph generative models, constrained discrete diffusion, masked categorical transformers, or bidirectional imputers. Build the bipartite graph G from the known legality mask or empirical nonzero transitions. Compute a spanning forest with DFS or union-find. For each edge not in the forest, store the tree path connecting its endpoints and the orientation sign of every edge in the resulting fundamental cycle. During each forward pass, compute log-softmax probabilities only on allowed edges, form a_xy = log_q[x,y] - log_r[y,x], and evaluate each stored signed path sum. Pseudocode: `T, non_tree = spanning_forest(G)`; `cycles = [tree_path(e.u,e.v)+[e] for e in non_tree]`; `a = log_q - log_r`; `residual[e] = sum(sign(edge,cycle)*a[edge] for edge in cycle)`; `loss = task_loss + lambda * mean(huber(residual))`; update both networks. The support graph, forest, cycle paths, and cycle rank |E|-|V|+C are computed exactly; only neural probabilities are estimated. First use synthetic sparse n-by-n conditionals with chain, grid, and random supports. Compare exhaustive cycle enumeration, random cycle sampling, the basis method, and no regularizer at equal steps and model size. Measure regularizer wall-clock time, held-out residuals over randomly generated cycles, and recovery error for a known compatible joint. Pre-register that the basis should match exhaustive constraints within 5% in held-out 95th-percentile residual while using only |E|-|V|+C constraints, and should provide at least 2x lower regularizer time on sparse graphs. Include random equal-count cycles as an ablation. Falsification occurs if basis residuals vanish but unseen cycle residuals remain large, or if its cost is not lower than exhaustive enumeration at the intended sparsity.

## Verification

- Status: mech_ok_no_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: no_effect
- Verdict: Built a spanning-forest fundamental-cycle basis for bipartite support graphs, with correctly oriented signed cycle coefficients, cycle-rank verification, exhaustive simple-cycle comparison, and compatible/perturbed edge-field checks. Compatible node-potential fields produced near-zero residuals for both basis and exhaustive cycles (maximum about 2e-15), while the basis used exactly the cycle rank and was 68x–2520x faster than exhaustive evaluation in the tested graphs. This validates the mathematical and computational claim, but not downstream neural-network training gains.

### Mechanism check

- Verdict: Built a spanning-forest fundamental-cycle basis for bipartite support graphs, with correctly oriented signed cycle coefficients, cycle-rank verification, exhaustive simple-cycle comparison, and compatible/perturbed edge-field checks. Compatible node-potential fields produced near-zero residuals for both basis and exhaustive cycles (maximum about 2e-15), while the basis used exactly the cycle rank and was 68x–2520x faster than exhaustive evaluation in the tested graphs. This validates the mathematical and computational claim, but not downstream neural-network training gains.
- Confidence: 8/10
- Limitations: No neural conditional models, optimization, held-out data, GPU execution, Huber loss, or task-loss comparison was tested. Exhaustive cycle enumeration is capped at 5000 cycles for dense supports, and timing is a small NumPy regularizer-cost proxy rather than an end-to-end training benchmark.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 1
- Paired wins: 0/8
- Benchmark verdict: no measurable effect

## Artifacts

- [bench_report.json](https://synthcore.org/code/1147/bench_report.json)
- [custom_cycle_track.py](https://synthcore.org/code/1147/custom_cycle_track.py)
- [experiment.py](https://synthcore.org/code/1147/experiment.py)
- [report.md](https://synthcore.org/code/1147/report.md)
- [report_bench_2026-09-02T123039.md](https://synthcore.org/code/1147/report_bench_2026-09-02T123039.md)
- [run_bench.py](https://synthcore.org/code/1147/run_bench.py)
- [Download all files as ZIP](https://synthcore.org/download/1147)

## Disclaimer

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