# Cycle-Basis Flip Sampler for Matching Latents

- ID: 1003
- Canonical URL: https://synthcore.org/idea/1003/cycle-basis-flip-sampler-for-matching-latents
- API JSON: https://synthcore.org/api/idea/1003.json
- API Markdown: https://synthcore.org/api/idea/1003.md
- Verification status: unverified
- Source: [arXiv:2607.16101](https://arxiv.org/abs/2607.16101)
- Category: sampling
- Solves: sample-efficiency, stability
- ML areas: graph-nn, sampling, world-model
- Math tags: combinatorics, graph-theory, probability
- Ratings: usefulness 5/10; difficulty 5/10; novelty 8/10

## Idea description

Replace single-edge or arbitrary alternating-cycle proposals in a neural matching sampler with flips restricted to a precomputed bounded set of alternating cycles induced by a cycle basis of the underlying graph. For clique-decorated graphs whose underlying graph has all vertex degrees of the same parity, the paper guarantees that these bounded-length flips connect every perfect matching, preventing disconnected proposal components even when decorations are large. A neural energy or policy network can score candidate flips, while Metropolis-Hastings correction preserves the target matching distribution.

## Mathematical statement

A perfect matching M of a graph H is a set of pairwise vertex-disjoint edges covering every vertex. If C is an even cycle whose edges alternate between M and E(H)\setminus M, the flip map is M' = M \    riangle E(C), where \    riangle denotes symmetric difference; M' is again a perfect matching. Theorem 1 states that if G is a graph whose vertex degrees all have the same parity, then the perfect-matching space \\mathcal{M}(G_{\\mathrm{clique}}) of its clique-decorated graph is flip-connected using cycles of length at most L = \\max_{1\\le i\\le k}3|C_i|, where C_1,\\ldots,C_k is any cycle basis of the underlying graph G and |C_i| is the number of edges in basis cycle C_i. Flip-connected means every pair M_0,M_1 \\in \\mathcal{M}(G_{\\mathrm{clique}}) can be joined by a finite sequence of such flips. The transferable property is irreducibility of a local proposal chain, not a mixing-time guarantee: bounded cycles suffice even if each clique decoration is much larger than the underlying graph.

## Key formulas

- $$M' = M \triangle E(C), \qquad C\text{ is an even cycle with }E(C)\cap M\text{ alternating with }E(C)\setminus M.$$
- $$\mathcal{M}(G_{\mathrm{clique}})\text{ is flip-connected on cycles of length at most }L,\qquad L=\max_{1\leq i\leq k}3|C_i|.$$
- $$\alpha(M\to M')=\min\left\{1,\frac{\pi_\theta(M')q(M'\to M)}{\pi_\theta(M)q(M\to M')}\right\},\qquad M'=M\triangle E(C).$$

## Implementation notes

1. Integration point: use this as the proposal kernel inside a neural sampler for perfect-matchings, such as a graph-matching latent-variable model, a neural combinatorial optimizer, or an energy-based model whose state is a binary edge-incidence vector M. Keep the neural network responsible for the target energy or proposal scores, and use the flip dynamics to define legal state transitions. Begin with an underlying graph G satisfying the theorem's equal-degree-parity condition and construct its clique decoration H.

2. Pseudocode:
```text
precompute cycle basis C[1:k] of G
L = max(3 * len(C[i]) for i in 1..k)
M = any initial perfect matching of H
repeat:
    candidates = []
    enumerate even simple cycles C in H with len(C) <= L
    for C in candidates:
        if edges(C) alternate in/out of M:
            M2 = symmetric_difference(M, edges(C))
            score = neural_energy(M2) - neural_energy(M)
            add (C, M2, score)
    sample C using q_theta(C | M)
    accept M2 with alpha = min(1, exp(-E_theta(M2)+E_theta(M)) * q_theta(C_reverse | M2)/q_theta(C | M))
```
The paper supplies the legal alternating-cycle update, the bound L, and the connectivity guarantee. Compute the cycle basis using a graph-library routine; enumerate short cycles by bounded-depth DFS, or use decorated lifts of the basis cycles to reduce cost. Estimate mixing empirically using edge autocorrelation, effective sample size, acceptance rate, and the number of distinct matchings visited. The theorem proves reachability, not rapid mixing. For a first cheap experiment, use 4x4 and 8x8 grid-derived graphs with several clique-decoration sizes. Compare single-cycle local proposals, unrestricted short-cycle proposals, and theorem-guided bounded-cycle proposals under the same small GNN energy. Measure effective samples per 1,000 neural evaluations, cross-state reachability, and autocorrelation. Success is guaranteed reachability on theorem-valid instances and improved effective samples as decorations grow.

## Disclaimer

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