Cycle-Basis Flip Sampler for Matching Latents

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:

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.