Graph Neural Network-Informed Predictive Flows for Faster Ford-Fulkerson and PAC-Learnability

• URL: http://arxiv.org/abs/2604.21175v1
• Date: Thu, 23 Apr 2026 00:45:32 GMT
• Title: Graph Neural Network-Informed Predictive Flows for Faster Ford-Fulkerson and PAC-Learnability
• Abstract summary: We propose a learning-augmented framework for accelerating max-flow and image segmentation by integrating Graph Neural Networks (GNNs) with the Ford-Fulkerson algorithm.<n>We introduce a Message Passing GNN (MPGNN) that jointly learns node and edge embeddings through coupled updates.<n>We also outline a hybrid extension combining flow warm-starting with edge-priority prediction, establishing a foundation for learning-guided optimization in image segmentation.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We propose a learning-augmented framework for accelerating max-flow computation and image segmentation by integrating Graph Neural Networks (GNNs) with the Ford-Fulkerson algorithm. Rather than predicting initial flows, our method learns edge importance probabilities to guide augmenting path selection. We introduce a Message Passing GNN (MPGNN) that jointly learns node and edge embeddings through coupled updates, capturing both global structure and local flow dynamics such as residual capacity and bottlenecks. Given an input image, we propose a method to construct a grid-based flow network with source and sink nodes, extract features, and perform a single GNN inference to assign edge probabilities reflecting their likelihood of belonging to high-capacity cuts. These probabilities are stored in a priority queue and used to guide a modified Ford-Fulkerson procedure, prioritizing augmenting paths via an Edmonds-Karp-style search with bottleneck-aware tie-breaking. This avoids repeated inference over residual graphs while leveraging learned structure throughout optimization. We further introduce a bidirectional path construction strategy centered on high-probability edges and provide a theoretical framework relating prediction quality to efficiency via a weighted permutation distance metric. Our method preserves max-flow/min-cut optimality while reducing the number of augmentations in practice. We also outline a hybrid extension combining flow warm-starting with edge-priority prediction, establishing a foundation for learning-guided combinatorial optimization in image segmentation.

Related papers

• Unrolled Neural Networks for Constrained Optimization [83.29547301151177]
  Our framework comprises two coupled neural networks that jointly approximate the saddle point of the Lagrangian.<n>We numerically evaluate the framework on mixed-integer quadratic programs and power allocation in wireless networks.
  arXiv  Detail & Related papers  (2026-01-24T03:12:41Z)
• Unrolled Graph Neural Networks for Constrained Optimization [83.29547301151177]
  We study the dynamics of the dual ascent algorithm in two coupled graph neural networks (GNNs)<n>We propose a joint training scheme that alternates between updating the primal and dual networks.<n>Our numerical experiments demonstrate that our approach yields near-optimal near-feasible solutions.
  arXiv  Detail & Related papers  (2025-09-21T16:55:41Z)
• Sparse Decomposition of Graph Neural Networks [20.768412002413843]
  We propose an approach to reduce the number of nodes that are included during aggregation.<n>We achieve this through a sparse decomposition, learning to approximate node representations using a weighted sum of linearly transformed features.<n>We demonstrate via extensive experiments that our method outperforms other baselines designed for inference speedup.
  arXiv  Detail & Related papers  (2024-10-25T17:52:16Z)
• Scalable Graph Compressed Convolutions [68.85227170390864]
  We propose a differentiable method that applies permutations to calibrate input graphs for Euclidean convolution. Based on the graph calibration, we propose the Compressed Convolution Network (CoCN) for hierarchical graph representation learning.
  arXiv  Detail & Related papers  (2024-07-26T03:14:13Z)
• Memory-aware Scheduling for Complex Wired Networks with Iterative Graph Optimization [4.614780125575351]
  We propose an efficient memory-aware scheduling framework based on iterative graph optimization. Our framework features an iterative graph fusion algorithm that simplifies the graph while preserving the scheduling optimality.
  arXiv  Detail & Related papers  (2023-08-26T14:52:02Z)
• Stochastic Unrolled Federated Learning [85.6993263983062]
  We introduce UnRolled Federated learning (SURF), a method that expands algorithm unrolling to federated learning. Our proposed method tackles two challenges of this expansion, namely the need to feed whole datasets to the unrolleds and the decentralized nature of federated learning.
  arXiv  Detail & Related papers  (2023-05-24T17:26:22Z)
• DAG Matters! GFlowNets Enhanced Explainer For Graph Neural Networks [30.19635147123557]
  We propose a generative structure -- GFlowNets-based GNN Explainer (GFlowExplainer) Our GFlowExplainer aims to learn a policy that generates a distribution of subgraphs for which the probability of a subgraph is proportional to its' reward. We conduct extensive experiments on both synthetic and real datasets, and both qualitative and quantitative results show the superiority of our GFlowExplainer.
  arXiv  Detail & Related papers  (2023-03-04T16:15:25Z)
• EGRC-Net: Embedding-induced Graph Refinement Clustering Network [66.44293190793294]
  We propose a novel graph clustering network called Embedding-Induced Graph Refinement Clustering Network (EGRC-Net) EGRC-Net effectively utilizes the learned embedding to adaptively refine the initial graph and enhance the clustering performance. Our proposed methods consistently outperform several state-of-the-art approaches.
  arXiv  Detail & Related papers  (2022-11-19T09:08:43Z)
• Graph-based Algorithm Unfolding for Energy-aware Power Allocation in Wireless Networks [27.600081147252155]
  We develop a novel graph sumable framework to maximize energy efficiency in wireless communication networks. We show the permutation training which is a desirable property for models of wireless network data. Results demonstrate its generalizability across different network topologies.
  arXiv  Detail & Related papers  (2022-01-27T20:23:24Z)
• Generalizable Cross-Graph Embedding for GNN-based Congestion Prediction [22.974348682859322]
  We propose a framework that can directly learn embeddings for the given netlist to enhance the quality of our node features. By combining the learned embedding on top of the netlist with the GNNs, our method improves prediction performance, generalizes to new circuit lines, and is efficient in training, potentially saving over $90 %$ of runtime.
  arXiv  Detail & Related papers  (2021-11-10T20:56:29Z)
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks [50.42141893913188]
  We study a distributed variable for large-scale AUC for a neural network as with a deep neural network. Our model requires a much less number of communication rounds and still a number of communication rounds in theory. Our experiments on several datasets show the effectiveness of our theory and also confirm our theory.
  arXiv  Detail & Related papers  (2020-05-05T18:08:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.