Unsupervised Learning for Optimal Transport plan prediction between unbalanced graphs

• URL: http://arxiv.org/abs/2506.12025v3
• Date: Tue, 08 Jul 2025 11:47:25 GMT
• Title: Unsupervised Learning for Optimal Transport plan prediction between unbalanced graphs
• Abstract summary: Optimal transport between graphs is a powerful tool for comparing and aligning graph structures.<n>We present Unbalanced Transport (ULOT) as a method to solve this problem.
• Score: 43.98782445210996
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Optimal transport between graphs, based on Gromov-Wasserstein and other extensions, is a powerful tool for comparing and aligning graph structures. However, solving the associated non-convex optimization problems is computationally expensive, which limits the scalability of these methods to large graphs. In this work, we present Unbalanced Learning of Optimal Transport (ULOT), a deep learning method that predicts optimal transport plans between two graphs. Our method is trained by minimizing the fused unbalanced Gromov-Wasserstein (FUGW) loss. We propose a novel neural architecture with cross-attention that is conditioned on the FUGW tradeoff hyperparameters. We evaluate ULOT on synthetic stochastic block model (SBM) graphs and on real cortical surface data obtained from fMRI. ULOT predicts transport plans with competitive loss up to two orders of magnitude faster than classical solvers. Furthermore, the predicted plan can be used as a warm start for classical solvers to accelerate their convergence. Finally, the predicted transport plan is fully differentiable with respect to the graph inputs and FUGW hyperparameters, enabling the optimization of functionals of the ULOT plan.

Related papers

• Graph Matching Relaxations and Amortization for Supervised Graph Prediction [11.692215143424976]
  End-to-end Supervised Graph Prediction (SGP) requires a permutation-invariant loss to compare predicted and target graphs with arbitrary node orderings.<n>We first study three Optimal Transport relaxations of this problem and show, theoretically and empirically, that the Gromov-Wasserstein (GW) objective is the most suitable for SGP.<n>To avoid solving the resulting inner optimization for every training example, we propose to amortize the graph matching (node alignment) problem.
  arXiv  Detail & Related papers  (2026-09-14T12:00:52Z)
• Accelerating Mixed Discrete-Continuous Motion Planning via Neural Graphs of Convex Sets [4.288763738857392]
  Motion planning problems such as collision-free navigation and contact-rich manipulation can be naturally formulated as optimization problems.<n>The Graphs of Convex Sets (GCS) framework offers a practical solution.<n>We replace the costly convex relaxation step required by nominal GCS with a single forward pass through a Graph Attention Network.<n>A ranking network then orders these candidates by their estimated cost.
  arXiv  Detail & Related papers  (2026-08-15T22:51:56Z)
• Multi-fidelity graph-based neural networks architectures to learn Navier-Stokes solutions on non-parametrized 2D domains [0.6554302736811937]
  We propose a graph-based, multi-fidelity learning framework for the prediction of stationary Navier--Stokes solutions in non-parametrized two-dimensional geometries.<n>The method is designed to guide the learning process through successive approximations, starting from reduced-order and full Stokes models.
  arXiv  Detail & Related papers  (2026-01-05T14:35:59Z)
• Towards Pre-trained Graph Condensation via Optimal Transport [52.6504753271008]
  Graph condensation aims to distill the original graph into a small-scale graph, mitigating redundancy and accelerating GNN training.<n> conventional GC approaches heavily rely on rigid GNNs and task-specific supervision.<n>Pre-trained Graph Condensation (PreGC) via optimal transport is proposed to transcend the limitations of task- and architecture-dependent GC methods.
  arXiv  Detail & Related papers  (2025-09-18T08:13:24Z)
• CombAlign: Enhancing Model Expressiveness in Unsupervised Graph Alignment [19.502687203792547]
  Unsupervised graph alignment finds the node correspondence between a pair of graphs attributed by only exploiting graph structure and node features.<n>One category of recent studies first computes the node representation and then matches nodes with the largest embedding-based similarity.<n>The other category reduces the problem to optimal transport (OT) via Gromov-Wasserstein learning.<n>We investigate the model's discriminative power in distinguishing matched and unmatched node pairs across two graphs.<n>Motivated by our theoretical analysis, we put forward a hybrid approach named CombAlign with stronger expressive power.
  arXiv  Detail & Related papers  (2024-06-19T04:57:35Z)
• Two Trades is not Baffled: Condensing Graph via Crafting Rational Gradient Matching [50.30124426442228]
  Training on large-scale graphs has achieved remarkable results in graph representation learning, but its cost and storage have raised growing concerns. We propose a novel graph method named textbfCraftextbfTing textbfRationatextbf (textbfCTRL) which offers an optimized starting point closer to the original dataset's feature distribution.
  arXiv  Detail & Related papers  (2024-02-07T14:49:10Z)
• On the Optimal Recovery of Graph Signals [10.098114696565865]
  We compute regularization parameters that are optimal or near-optimal for graph signal processing problems. Our results offer a new interpretation for classical optimization techniques in graph-based learning. We illustrate the potential of our methods in numerical experiments on several semi-synthetic graph signal processing datasets.
  arXiv  Detail & Related papers  (2023-04-02T07:18:11Z)
• Fine-Tuning Graph Neural Networks via Graph Topology induced Optimal Transport [28.679909084727594]
  GTOT-Tuning is required to utilize the property of graph data to enhance the preservation of representation produced by fine-tuned networks. By using the adjacency relationship amongst nodes, the GTOT regularizer achieves node-level optimal transport procedures. We evaluate GTOT-Tuning on eight downstream tasks with various GNN backbones and demonstrate that it achieves state-of-the-art fine-tuning performance for GNNs.
  arXiv  Detail & Related papers  (2022-03-20T04:41:17Z)
• Learning to Predict Graphs with Fused Gromov-Wasserstein Barycenters [2.169919643934826]
  We formulate the problem as regression with the Fused Gromov-Wasserstein (FGW) loss. We propose a predictive model relying on a FGW barycenter whose weights depend on inputs.
  arXiv  Detail & Related papers  (2022-02-08T12:15:39Z)
• FGOT: Graph Distances based on Filters and Optimal Transport [62.779521543654134]
  Graph comparison deals with identifying similarities and dissimilarities between graphs. A major obstacle is the unknown alignment of graphs, as well as the lack of accurate and inexpensive comparison metrics. In this work we introduce the filter graph distance approximation.
  arXiv  Detail & Related papers  (2021-09-09T17:43:07Z)
• Neural Weighted A*: Learning Graph Costs and Heuristics with Differentiable Anytime A* [12.117737635879037]
  Recent works related to data-driven planning aim at learning either cost functions or planner functions, but not both. We propose Neural Weighted A*, a differentiable anytime planner able to produce improved representations of planar maps as graph costs and planners. We experimentally show the validity of our claims by testing Neural Weighted A* against several baselines, introducing a novel, tile-based navigation dataset.
  arXiv  Detail & Related papers  (2021-05-04T13:17:30Z)
• SGCN:Sparse Graph Convolution Network for Pedestrian Trajectory Prediction [64.16212996247943]
  We present a Sparse Graph Convolution Network(SGCN) for pedestrian trajectory prediction. Specifically, the SGCN explicitly models the sparse directed interaction with a sparse directed spatial graph to capture adaptive interaction pedestrians. visualizations indicate that our method can capture adaptive interactions between pedestrians and their effective motion tendencies.
  arXiv  Detail & Related papers  (2021-04-04T03:17:42Z)
• Optimal Transport Graph Neural Networks [31.191844909335963]
  Current graph neural network (GNN) architectures naively average or sum node embeddings into an aggregated graph representation. We introduce OT-GNN, a model that computes graph embeddings using parametric prototypes.
  arXiv  Detail & Related papers  (2020-06-08T14:57:39Z)
• Hallucinative Topological Memory for Zero-Shot Visual Planning [86.20780756832502]
  In visual planning (VP), an agent learns to plan goal-directed behavior from observations of a dynamical system obtained offline. Most previous works on VP approached the problem by planning in a learned latent space, resulting in low-quality visual plans. Here, we propose a simple VP method that plans directly in image space and displays competitive performance.
  arXiv  Detail & Related papers  (2020-02-27T18:54:42Z)
• A Near-Optimal Gradient Flow for Learning Neural Energy-Based Models [93.24030378630175]
  We propose a novel numerical scheme to optimize the gradient flows for learning energy-based models (EBMs) We derive a second-order Wasserstein gradient flow of the global relative entropy from Fokker-Planck equation. Compared with existing schemes, Wasserstein gradient flow is a smoother and near-optimal numerical scheme to approximate real data densities.
  arXiv  Detail & Related papers  (2019-10-31T02:26:20Z)

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.