Graph reconstruction method improves constraint satisfaction and prediction
Feasible Flow Matching for Graph Reconstruction via Within-Sampling Primal-Dual Guidance
Machine Learning
Summary
Reconstructing graphs from incomplete data can be tricky, especially when certain rules like how many connections a node has or how densely connected parts are need to be followed. The authors improved an existing graph-building technique by adding a way to enforce these rules during the reconstruction process without needing to retrain the method from scratch. Their approach uses a guiding mechanism that adjusts sampling based on how well the current guess meets the rules. Tests on multiple datasets showed that this new method makes graphs that better respect the constraints while still predicting links accurately.
What this means in practice
- •For data engineers: Generate realistic network structures that satisfy specific constraints like degree distributions or edge densities for testing and modeling.
- •For network analysts: Improve link prediction accuracy while ensuring reconstructed networks adhere to known structural properties.
Authors
Haoming Chen, Nicolas Zilberstein, Santiago Paternain, Santiago Segarra
Abstract
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.