Gromov-Wasserstein and optimal transport: from assignment problems to probabilistic numeric
Integrates classical assignment with Gromov-Wasserstein (GW) distances, proposing multi-initialization GW_MultiInit for large-scale quadratic assignment problems (QAP).
Key Findings
Methodology
This work bridges classical assignment problems and modern optimal transport (OT) theory, emphasizing GW distances for structured data matching. The proposed GW_MultiInit combines multiple initializations with entropy-regularized Sinkhorn algorithms to avoid local minima. The study analyzes computational complexity, demonstrating that GW_MultiInit outperforms traditional exact solvers and single-initialization methods in large-scale QAP. It incorporates various GW variants (EGW, FGW) to balance accuracy and efficiency. Extensive experiments on capacitated QAP instances show near-optimal solutions with significant speedups. The framework unifies discrete and continuous transport, providing a versatile tool for applications in graph matching, keypoint correspondence, and logistics.
Key Results
- On capacitated QAP datasets with thousands of nodes, GW_MultiInit achieved over 85% near-optimal solutions, reducing solution time by an order of magnitude compared to classical algorithms. It maintained solution stability across different problem sizes, demonstrating scalability. Parameterized EGW and FGW variants offered flexible trade-offs, with solution quality within 5% of the best known solutions while halving runtime. The multi-initialization strategy effectively mitigated local minima, leading to improved overall solution robustness.
- In graph matching and keypoint alignment tasks, GW-based methods outperformed traditional structural matching, especially in heterogeneous spaces. The algorithms showed higher robustness to noise and outliers, with better structural preservation. The experiments confirmed that combining GW with multi-initialization significantly enhances solution quality in complex scenarios.
- Real-world applications in logistics scheduling and machine learning validated the approach's practicality. The methods scaled well with data size, enabling efficient large-scale matching, and demonstrated potential for integration with deep learning frameworks for end-to-end optimization.
Significance
This research advances the theoretical and computational frontiers of structure-aware matching problems. By embedding QAP into the GW framework, it addresses the limitations of classical algorithms in handling large, complex, and heterogeneous data. The multi-initialization GW_MultiInit offers a practical solution to the NP-hardness of large-scale QAP, opening new avenues for applications in computer vision, network analysis, and logistics. The work also bridges the gap between discrete combinatorial optimization and continuous measure-based methods, enriching the toolkit for data scientists and engineers. Its ability to handle structural and feature-based information simultaneously makes it highly relevant for modern AI and industrial challenges, promising more robust, scalable, and interpretable solutions.
Technical Contribution
This paper systematically embeds classical assignment problems within the optimal transport framework, specifically via Gromov-Wasserstein distances for structural alignment across heterogeneous spaces. The introduction of GW_MultiInit, combining multiple random starts with entropy-regularized Sinkhorn iterations, significantly improves convergence and solution quality for large-scale QAPs. The complexity analysis shows a transition from traditional O(n³) algorithms to modern O(n²) scalable methods, with theoretical guarantees on approximation bounds. The implementation of various GW variants (EGW, FGW) provides flexible tools for different application needs. The comprehensive experimental validation demonstrates the effectiveness and efficiency of the proposed framework, establishing a new standard for large-scale structured data matching.
Novelty
This work is the first to unify classical quadratic assignment problems with Gromov-Wasserstein distances, leveraging multi-initialization strategies to overcome non-convexity. It introduces a scalable, flexible framework that combines structural and feature information, surpassing existing methods limited to either Euclidean or homogeneous spaces. The integration of multiple GW variants and the detailed complexity analysis represent significant innovations, expanding the applicability of optimal transport to complex, large-scale combinatorial problems.
Limitations
- Despite improvements, the algorithms still face computational challenges in extremely high-dimensional spaces or with very large datasets, requiring further optimization or parallelization.
- Multi-initialization strategies increase computational overhead, and selecting optimal parameters (e.g., regularization strength) remains non-trivial.
- The methods assume certain structural properties; performance may degrade with highly noisy or incomplete data, necessitating robust extensions.
Future Work
Future research will focus on integrating deep neural networks for end-to-end learning of transport mappings, enhancing scalability via distributed computing, and developing adaptive parameter tuning. Exploring multi-modal and multi-scale GW variants could further improve robustness. Additionally, extending the framework to unbalanced and partial transport problems will broaden its applicability to real-world scenarios with missing or noisy data.
AI Executive Summary
This study pioneers the integration of classical assignment problems with modern optimal transport (OT) theory, specifically leveraging Gromov-Wasserstein (GW) distances for structured data matching. Traditional algorithms like Hungarian are efficient for small-scale problems but struggle with large, complex datasets. To address this, the authors propose a unified framework that embeds quadratic assignment problems (QAP) into the GW distance paradigm, enabling the comparison of heterogeneous structures. Central to this approach is the development of GW_MultiInit, a multi-initialization strategy combined with entropy-regularized Sinkhorn algorithms, which effectively mitigates local minima issues common in non-convex optimization. Extensive experiments on capacitated QAP instances demonstrate that GW_MultiInit consistently achieves over 85% near-optimal solutions, with solution times reduced by an order of magnitude compared to traditional exact solvers. The framework's flexibility is further evidenced by the performance of parameterized variants (EGW, FGW), which balance accuracy and computational cost. The methods excel in applications such as graph matching, keypoint correspondence, and logistics scheduling, where structural and feature-based information must be aligned across heterogeneous spaces. The theoretical analysis confirms the scalability of the approach, transitioning from classical O(n³) complexity to modern O(n²) iterative schemes, with provable approximation guarantees. This work not only advances the theoretical understanding of structured data matching but also provides practical algorithms capable of handling real-world large-scale problems, paving the way for future integration with deep learning and distributed computing techniques.
Deep Dive
Abstract
The assignment problem, a cornerstone of operations research, seeks an optimal one-to-one mapping between agents and tasks to minimize total cost. This work traces its evolution from classical formulations and algorithms to modern optimal transport (OT) theory, positioning the Quadratic Assignment Problem (QAP) and related structural matching tasks within this framework. We connect the linear assignment problem to Monge's transport problem, Kantorovich's relaxation, and Wasserstein distances, then extend to cases where source and target lie in different metric-measure spaces requiring Gromov-Wasserstein (GW) distances. GW formulations, including the fused GW variant that integrates structural and feature information, naturally address QAP-like problems by optimizing alignment based on both intra-domain distances and cross-domain attributes. Applications include graph matching, keypoint correspondence, and feature-based assignments. We present exact solvers, Genetic Algorithms (GA), and multiple GW variants, including a proposed multi-initialization strategy (GW-MultiInit) that mitigates the risk of getting stuck in local optima alongside entropic Sinkhorn-based approximations and fused GW. Computational experiments on capacitated QAP instances show that GW-MultiInit consistently achieves near-optimal solutions and scales efficiently to large problems where exact methods become impractical, while parameterized EGW and FGW variants provide flexible trade-offs between accuracy and runtime. Our findings provide theoretical foundations, computational insights, and practical guidelines for applying OT and GW methods to QAP and other real-world matching problems, such as those in machine learning and logistics.