Fundamental-Cycle Compatibility Basis

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.