# Graph Quotient Minibatch Coupling

- ID: 218
- Canonical URL: https://synthcore.org/idea/218/graph-quotient-minibatch-coupling
- API JSON: https://synthcore.org/api/idea/218.json
- API Markdown: https://synthcore.org/api/idea/218.md
- Verification status: mechanism_failed
- Source: [arXiv:2608.26961](https://arxiv.org/abs/2608.26961)
- Category: training
- Solves: accuracy, sample-efficiency, scalability
- ML areas: graph-nn, diffusion, training, batching
- Math tags: optimal-transport, geometry, group-theory, combinatorics
- Ratings: usefulness 7/10; difficulty 7/10; novelty 7/10

## Idea description

Use a minibatch-level transport plan that jointly decides which source graph should be paired with which target graph and how each target should be node-aligned. This can reduce total flow-matching displacement beyond per-example matching, producing shorter and less conflicting training trajectories without modifying the architecture.

## Mathematical statement

Let source graphs be X_1,...,X_B and target graphs be Y_1,...,Y_B, each represented as an N x N x C tensor. For every source-target pair define the quotient cost C_{ab} = min_{sigma in S_N} ||X_a - rho_N^graph(sigma)Y_b||_F^2, where rho_N^graph is the simultaneous permutation action on both edge indices. A relaxed outer coupling P in R_+^{B x B} is computed by entropic optimal transport with uniform marginals P 1 = 1/B and P^T 1 = 1/B: P = argmin_{P >= 0} <P,C> + epsilon sum_{a,b} P_{ab}(log P_{ab}-1). The inner minimization gives an aligned target Y_{ab}^* = rho_N^graph(sigma_{ab}^*)Y_b. Use pair weights B P_{ab} and the flow-matching loss L = B sum_{a,b} P_{ab} ||v_theta((1-t)X_a+tY_{ab}^*,t) - (Y_{ab}^*-X_a)||_F^2. The transferable property is simultaneous optimization over graph relabelings and graph-pair assignments in quotient geometry.

## Key formulas

- $$C_{ab}=\min_{\sigma\in\mathfrak{S}_N}\left\|X_a-\rho_N^{\rm graph}(\sigma)Y_b\right\|_F^2$$
- $$P^*=\arg\min_{P\geq 0}\ \langle P,C\rangle+\varepsilon\sum_{a,b}P_{ab}(\log P_{ab}-1),\qquad P\mathbf{1}=\frac{1}{B}\mathbf{1},\quad P^\top\mathbf{1}=\frac{1}{B}\mathbf{1}$$
- $$Y_{ab}^*=\rho_N^{\rm graph}(\sigma_{ab}^*)Y_b,\qquad \sigma_{ab}^*=\arg\min_{\sigma\in\mathfrak{S}_N}\|X_a-\rho_N^{\rm graph}(\sigma)Y_b\|_F^2$$
- $$\mathcal{L}_{\rm batch}=B\sum_{a=1}^{B}\sum_{b=1}^{B}P^*_{ab}\left\|v_\theta\bigl((1-t)X_a+tY_{ab}^*,t\bigr)-\bigl(Y_{ab}^*-X_a\bigr)\right\|_F^2$$

## Implementation notes

Integrate this into the minibatch sampler immediately before flow-matching target construction. For each batch, compute a B-by-B cost matrix. For every pair (a,b), obtain an approximate node permutation with a cheap graph matcher; for an MVP, initialize node correspondences from degree and node-feature similarity, run 5-20 Sinkhorn iterations on an edge-consistency objective, and round the resulting soft matrix to a permutation with the Hungarian algorithm. Set C[a,b] to the aligned squared edge-tensor distance. Compute the outer coupling P with Sinkhorn iterations using uniform source and target marginals and entropy epsilon. Stop gradients through P and the discrete permutations initially. Either train on all B-squared pairs with weights B*P[a,b], or sample pairs from the normalized P distribution to preserve model-evaluation cost. For each selected pair, permute Y_b, sample t, construct Z=(1-t)*X_a+t*Y_aligned, and regress to Y_aligned-X_a. The paper-derived quantities are quotient pair costs and the doubly stochastic coupling; matching quality and epsilon are empirical approximations. Begin with B=16 or 32, N<=32, a small equivariant graph flow model, and a molecular dataset. Compare random pairings, independently nearest-neighbor pairings, and quotient coupling at equal compute. Measure displacement, gradient cosine similarity, validation loss, and generated validity under 4/8/16-step Euler sampling. Success means lower displacement and gradient conflict with improved sample quality; if O(B^2) matching dominates, retain only top-k candidates per source.

## Verification

- Status: mechanism_failed
- Mechanism evidence: yes
- Mechanism confirmed: no
- Verdict: The MVP passed the Sinkhorn marginal checks and showed that quotient alignment improves random pairing, but balanced OT did not outperform independent nearest-neighbor matching on the tested synthetic one-to-one graphs.

### Mechanism check

- Verdict: The MVP passed the Sinkhorn marginal checks and showed that quotient alignment improves random pairing, but balanced OT did not outperform independent nearest-neighbor matching on the tested synthetic one-to-one graphs.
- Confidence: 9/10
- Limitations: Only tiny synthetic N=5 graphs with exact permutation search were tested; no scalable matcher, GNN, generation, molecular validity, or larger stress test.

## Artifacts

- [check_results.py](https://synthcore.org/code/47/check_results.py)
- [quotient_coupling.py](https://synthcore.org/code/47/quotient_coupling.py)
- [report.md](https://synthcore.org/code/47/report.md)
- [results.json](https://synthcore.org/code/47/results.json)
- [Download all files as ZIP](https://synthcore.org/download/47)

## Disclaimer

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