Beyond Reachability: When Edit Order Preserves Couplings in Graph Flow Matching
Abstract
Shortest-path optimality does not guarantee that a memoryless graph generator preserves a prescribed source-target correspondence. We study whether reordering legal shortest edits can retain this correspondence without changing the pairing, mandatory edits, or sampling budget. Under a common Poisson clock, we establish an exact criterion for endpoint coupling recoverability: the source-blind Markov projection attains the unavoidable clock-error floor if and only if routes to distinct targets do not share graph states. Routes to the same target may merge without sacrificing endpoint fidelity. This characterization leads to an exact finite-state routing formulation and a legality-preserving scheduling procedure with recovery certificates. A marker-free construction demonstrates how shared edge structure can retain source distinctions, while a capacity-constrained family exhibits a sharp separation in paired error between edit orders with identical marginal error. Finally, a target-conditioned aliasing bound connects structural route design to the terminal fidelity of a learned graph-only generator. These results characterize when legal edit ordering can preserve a prescribed coupling under fixed operational costs.
Related
- Generalized Wasserstein Flow Matching: Nested Couplings for Point Cloud Generation
- Matrix-Free Moment-Matching Method for Reduced-Order Modeling of Quadratic-Bilinear Descriptor Systems with Multiple Inputs
- Matching Randomized First-Order Bounds for Higher-Order Smooth Nonconvex Optimization
- Flow Matching under Noisy Latent Structure: Beyond Exact Low-Dimensional Support
- Matching Complexity for Second-Order Stationary Point with Sample Reuse
BibTeX
@misc{li2026beyond,
title = {{Beyond Reachability: When Edit Order Preserves Couplings in Graph Flow Matching}},
author = {Zilin Li and Zixing Song},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.38486},
eprint = {2610.38486},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.38486},
}
RIS
TY - UNPB
TI - Beyond Reachability: When Edit Order Preserves Couplings in Graph Flow Matching
AU - Zilin Li
AU - Zixing Song
PY - 2026
DA - 2026/10/28
PB - arXiv
DO - 10.48550/arxiv.2610.38486
UR - https://arxiv.org/abs/2610.38486
AB - Shortest-path optimality does not guarantee that a memoryless graph generator preserves a prescribed source-target correspondence. We study whether reordering legal shortest edits can retain this correspondence without changing the pairing, mandatory edits, or sampling budget. Under a common Poisson clock, we establish an exact criterion for endpoint coupling recoverability: the source-blind Markov projection attains the unavoidable clock-error floor if and only if routes to distinct targets do not share graph states. Routes to the same target may merge without sacrificing endpoint fidelity. This characterization leads to an exact finite-state routing formulation and a legality-preserving scheduling procedure with recovery certificates. A marker-free construction demonstrates how shared edge structure can retain source distinctions, while a capacity-constrained family exhibits a sharp separation in paired error between edit orders with identical marginal error. Finally, a target-conditioned aliasing bound connects structural route design to the terminal fidelity of a learned graph-only generator. These results characterize when legal edit ordering can preserve a prescribed coupling under fixed operational costs.
ER -