# Submetry-Lifted Relational Alignment

- ID: 2140
- Canonical URL: https://synthcore.org/idea/2140/submetry-lifted-relational-alignment
- API JSON: https://synthcore.org/api/idea/2140.json
- API Markdown: https://synthcore.org/api/idea/2140.md
- Verification status: mech_ok_no_baseline
- Source: [arXiv:2608.11680](https://arxiv.org/abs/2608.11680)
- Category: geometry
- Solves: accuracy, generalization, stability
- ML areas: graph-nn, attention, loss, regularization
- Math tags: metric-geometry, optimal-transport, measure-theory, geometry
- Ratings: usefulness 7/10; difficulty 5/10; novelty 5/10

## Idea description

Represent a graph, set, or attributed network as a measurable Z-valued kernel and train on lifted representatives while explicitly minimizing over node couplings. The quotient objective is invariant to relabeling by construction, while the lifted loss gives a dense correspondence signal that can stabilize graph attention and relational encoders.

## Mathematical statement

Let Omega=[0,1] with Lebesgue measure lambda, let (Z,d_Z) be the feature or edge-attribute metric space, and let omega,eta:Omega^2->Z be measurable kernels. The quotient map Q sends a kernel to its equivalence class under measure-preserving reparameterizations. A finite-sample quotient distance is d_Q(omega,eta)^p = inf_Pi sum_{i,j,k,l} Pi_{ik}Pi_{jl}d_Z(omega_{ij},eta_{kl})^p, where Pi is a coupling between node-weight vectors a and b, Pi 1=b and Pi^T 1=a (transpose convention may be swapped). The submetry property means quotient distances and metric balls can be realized by suitable lifted representatives rather than arbitrary quotient-level searches. Use the same coupling to compare relational inputs and predictions. The paper also gives an isometric embedding iota:(P_p(Z),(1/2)W_p^Z)->(M_p(Z),GW_p^Z), with E composed with iota equal to the identity, showing that ordinary Wasserstein-distributed features are a consistent special case.

## Key formulas

- $$\mathrm{W}_{p}^{Z}(\mu,\mu^{\prime})=\inf_{\pi\in\Pi(\mu,\mu^{\prime})}\left(\int_{Z\times Z}d_{Z}(z,z^{\prime})^{p}\,d\pi(z,z^{\prime})\right)^{1/p}.$$
- $$d_{Q}(\omega,\eta)^{p}=\inf_{\pi\in\Pi(\lambda,\lambda)}\int_{\Omega^{2}\times\Omega^{2}}d_Z\!\left(\omega(x,x^{\prime}),\eta(y,y^{\prime})\right)^{p}\,d\pi(x,y)\,d\pi(x^{\prime},y^{\prime}).$$
- $$\iota:\left(\mathcal{P}_{p}(Z),\tfrac{1}{2}\cdot\mathrm{W}_{p}^{Z}\right)\hookrightarrow\left(\mathcal{M}_{p}(Z),\mathrm{GW}_{p}^{Z}\right),\qquad E\circ\iota=\mathrm{id}_{\mathcal{P}_{p}(Z)}.$$
- $$\mathcal{L}_{\mathrm{align}}=\left[\sum_{i,j,k,l}\Pi_{ik}\Pi_{jl}\,d_Z\!\left(\omega_{ij},\eta_{kl}\right)^{p}\right]^{1/p},\qquad \Pi\mathbf{1}=a,\ \Pi^{\mathsf T}\mathbf{1}=b.$$

## Implementation notes

Integrate this at the input-to-encoder boundary for graph or network batches. Each sample should expose node weights a,b and an edge or relational tensor omega[i,j] in Z; the encoder may produce node states, a predicted relational tensor eta[k,l], or two augmented views whose tensors are compared. For every pair of views, form the cost tensor C[i,k,j,l]=d_Z(omega[i,j],eta[k,l])^p. Compute a soft node coupling Pi with 20-50 Sinkhorn iterations under Pi 1=a and Pi^T 1=b, using entropic regularization epsilon; begin with epsilon=0.1 times the median cost and optionally anneal to 0.01 times that median. Add lambda_align times the p-root of sum Pi[i,k]Pi[j,l]C[i,k,j,l] to the task loss. Stop gradients through Pi in the first MVP, then compare with differentiating through Sinkhorn. The exact mathematical component is the coupling-based quotient objective and its marginal constraints; finite graph size, entropic regularization, and the ground metric are engineering approximations. Start with a 3-6 layer GIN or graph transformer on MUTAG, ZINC, or synthetic attributed graphs. Compare against cross-entropy plus random node-permutation augmentation. Success means invariant predictions under arbitrary node permutations, lower prediction variance across permutations, and higher validation accuracy at equal training FLOPs; report Sinkhorn time and coupling entropy.

## Verification

- Status: mech_ok_no_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: inconclusive
- Verdict: Built a finite lifted relational alignment MVP with Sinkhorn node couplings, marginal checks, exact relabeling reference, entropy measurement, and a synthetic graph classifier comparison. The toy predictions manifested: identity/exact relabeling distance was 0, noisy lifted distance scaled approximately linearly with noise (slope 0.758), and coupling entropy increased monotonically with epsilon from 1.792 to 2.641. The classifier had equal accuracy (1.00) but alignment was slower (2.03s vs 0.18s) and slightly increased permutation prediction variance (0.000516 vs 0.000321), so there was no practical task-level win in this toy setup.

### Mechanism check

- Verdict: Built a finite lifted relational alignment MVP with Sinkhorn node couplings, marginal checks, exact relabeling reference, entropy measurement, and a synthetic graph classifier comparison. The toy predictions manifested: identity/exact relabeling distance was 0, noisy lifted distance scaled approximately linearly with noise (slope 0.758), and coupling entropy increased monotonically with epsilon from 1.792 to 2.641. The classifier had equal accuracy (1.00) but alignment was slower (2.03s vs 0.18s) and slightly increased permutation prediction variance (0.000516 vs 0.000321), so there was no practical task-level win in this toy setup.
- Confidence: 8/10
- Limitations: Only a small synthetic graph dataset and shallow row-wise relational encoder were tested; no MUTAG/ZINC benchmark, GPU run, larger graphs, differentiable Sinkhorn, annealing, weighted nodes, or FLOP-normalized comparison was performed. The approximate entropic alternating coupling did not recover exact zero distance for relabeled graphs, unlike the explicitly constructed exact permutation coupling.

### Practical benchmark

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

## Artifacts

- [bench_report.json](https://synthcore.org/code/858/bench_report.json)
- [bench_run.py](https://synthcore.org/code/858/bench_run.py)
- [experiment.py](https://synthcore.org/code/858/experiment.py)
- [graph_track.py](https://synthcore.org/code/858/graph_track.py)
- [report.md](https://synthcore.org/code/858/report.md)
- [report_bench_2026-09-01T125006.md](https://synthcore.org/code/858/report_bench_2026-09-01T125006.md)
- [results.json](https://synthcore.org/code/858/results.json)
- [Download all files as ZIP](https://synthcore.org/download/858)

## Disclaimer

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