# Feasible Flow Matching for Graph Reconstruction via Within-Sampling Primal-Dual Guidance

arXiv: https://arxiv.org/abs/2609.32980 · HTML: https://mlsanity.com/paper/2609.32980/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Flow matching, time series and science, one of 14 directions in Diffusion models.
- Builds on 23 of its 27 references that are in the map.
- First posted on arXiv 26 Sep 2026.

## Placed in

- Diffusion models / [Flow matching, time series and science](https://mlsanity.com/diffusion/flow-matching-time-series-and-science/)

## Builds on (most cited first, 23 of 23)

- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Flow Matching for Generative Modeling](https://mlsanity.com/paper/2210.02747/) (2022)
- [Flow Straight and Fast: Learning to Generate and Transfer Data with Rectified Flow](https://mlsanity.com/paper/2209.03003/) (2022)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [The Perception-Distortion Tradeoff](https://mlsanity.com/paper/1711.06077/) (2017)
- [Constrained Reinforcement Learning Has Zero Duality Gap](https://mlsanity.com/paper/1910.13393/) (2019)
- [Solving 3D Inverse Problems using Pre-trained 2D Diffusion Models](https://mlsanity.com/paper/2211.10655/) (2022)
- [Connecting the Dots: Identifying Network Structure via Graph Signal Processing](https://mlsanity.com/paper/1810.13066/) (2018)
- [Stochastic interpolants with data-dependent couplings](https://mlsanity.com/paper/2310.03725/) (2023)
- [PnP-Flow: Plug-and-Play Image Restoration with Flow Matching](https://mlsanity.com/paper/2410.02423/) (2024)
- [Neural Common Neighbor with Completion for Link Prediction](https://mlsanity.com/paper/2302.00890/) (2023)
- [Network Topology Inference from Spectral Templates](https://mlsanity.com/paper/1608.03008/) (2016)
- [A Theory of the Distortion-Perception Tradeoff in Wasserstein Space](https://mlsanity.com/paper/2107.02555/) (2021)
- [Probably Approximately Correct Constrained Learning](https://mlsanity.com/paper/2006.05487/) (2020)
- [State Augmented Constrained Reinforcement Learning: Overcoming the Limitations of Learning with Rewards](https://mlsanity.com/paper/2102.11941/) (2021)
- [Network Topology Inference with Graphon Spectral Penalties](https://mlsanity.com/paper/2010.07872/) (2020)
- [Joint Network Topology Inference via a Shared Graphon Model](https://mlsanity.com/paper/2209.08223/) (2022)
- [Scalable Implicit Graphon Learning](https://mlsanity.com/paper/2410.17464/) (2024)
- [Graph Guided Diffusion: Unified Guidance for Conditional Graph Generation](https://mlsanity.com/paper/2505.19685/) (2025)
- [Prior-Informed Flow Matching for Graph Reconstruction](https://mlsanity.com/paper/2601.22107/) (2026)
- [Primal-Dual Guided Decoding for Constrained Discrete Diffusion](https://mlsanity.com/paper/2605.09749/) (2026)
- [Dual Ascent Diffusion for Inverse Problems](https://mlsanity.com/paper/2505.17353/) (2025)
- [Constrained Diffusion Models with Primal-Dual Inference](https://mlsanity.com/paper/2606.17192/) (2026)

## Abstract (arXiv)

Graph reconstruction from partial observations often comes with structural side information, such as degree bounds, triangle counts, or an edge-density band. Prior-Informed Flow Matching (PIFM) reconstructs graphs by transporting a local prior toward the graph distribution, but it provides no mechanism to incorporate this side information. We put forth Constrained Primal-Dual PIFM (CPD-PIFM), which augments the sampler with Lagrange multipliers that evolve along each trajectory. The multipliers respond to constraint violations at a predicted endpoint and guide subsequent sampling steps without retraining. We prove that the sampler inherits PIFM's permutation equivariance and bound its expected terminal slack by a term that decays as the inverse square root of the number of steps, plus two approximation terms. On three link-prediction benchmarks and nine combinations of datasets and constraints, CPD-PIFM raises feasibility by 11-26 percentage points and remains competitive with fixed guidance without selecting a separate multiplier for each constraint.