The Gromov-Wasserstein (GW) problem compares structured distributions without requiring a shared feature space or known correspondences, but its nonconvex objective and coupled marginal constraints make computation challenging. Bregman alternating projected gradient (BAPG) uses inexpensive alternating row and column updates, yet its fixed-penalty relaxation leaves a persistent feasibility gap. We propose Adaptive KL-BAPG (A-KL-BAPG), which combines a finite fixed-penalty burn-in with a guarded increasing-penalty phase. At each tail iteration, the method reuses BAPG's alternating updates and backtracks a delayed-power step until a Sinkhorn-inspired projective-diameter safeguard is satisfied. We prove finite termination of the backtracking at each iteration and show that the feasibility gap vanishes asymptotically. We further establish a best-iterate O(1/logN) bound for the weighted squared corrected residual and, under a support regularity condition, the existence of a stationary accumulation point for the original GW problem. This distinguishes A-KL-BAPG from fixed-penalty BAPG, whose stationarity guarantees are given for the relaxed problem. Experiments show that A-KL-BAPG achieves a favorable balance of accuracy, objective value, feasibility, and stationarity relative to BAPG variants, projection-based methods, and task-specific baselines. For synthetic and real graph alignment problems, it closely matches the accuracy and objective value of fixed-penalty KL-BAPG while reducing the marginal feasibility gap by 62-99% and the projected stationarity residual by 28-98%. Heterogeneous domain adaptation experiments show a similar pattern: A-KL-BAPG maintains comparable target accuracy and objective values while achieving better feasibility and stationarity than fixed-penalty KL-BAPG.
Figures & tables
Figure 1: Boundary effect of the Descent. At an inactive entry, an outward descent direction is blocked (black), while an inward direction might remain feasible (red).
Method
Accuracy
GW objective
Feasibility
Stationarity Residual
Runtime (s)
KL-BAPG
0.966
−0.034
0.098
0.470
278.981
KL-BAPG + Sinkhorn
0.966
−0.034
0.005
0.140
279.987
A-KL-BAPG
0.966
−0.034
5.524×10−6
0.011
225.242
1/k schedule
0.022
−0.003
1.430×10−7
0.204
54.171
Pure power
0.022
−0.003
1.110×10−6
0.205
51.926
POT CG
0.015
−0.017
2.390×10−17
7.730×10−4
5.390
Table 1: Synthetic Graph Alignment Results.
Figure 2: Iteration convergence comparison.
Table 2: ENZYMES and PROTEINS graph alignment performance.
Figure 3: Optimization diagnostics of synthetic domain adaptation experiment. Outward is better, i.e., lower in values.
Appendix figures & tables3 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 4: Bipartite Active-Support Graph. Each edge represents (ia,jb)∈S . Fixing pi0=0 , the bounded edge sums propagate boundedness along the blue alternating path; gray lines denote the remaining active-support edges.
Figure 5: Visualization of heterogeneous domain adaptation for seed 0. Left: labeled source samples plotted by their single observed common feature; the vertical displacement of source points is jitter for visualization only and is not used as method input. Middle: target samples in the common and target-only features, colored by ground-truth labels hidden during training. Right: the same target samples colored by A-KL-BAPG predictions. Quantitative comparisons with other baselines are reported in Table 3 (a).
Method
Accuracy
Runtime (s)
KL–BAPG
0.880±0.074
11.739±7.283
KL–BAPG + Sinkhorn
0.880±0.074
11.967±7.531
1/k
0.662±0.068
11.635±7.216
Pure power
0.741±0.068
11.627±7.215
A-KL-BAPG
0.880±0.074
67.665±58.035
POT OT
0.827±0.079
0.008±0.006
Appendix
Table 4: Complete HAR70+ domain adaptation results. Accuracy values are retained from the previous experiments. Runtimes are updated using 54 jobs and reported as mean ± standard deviation. All values are rounded to three decimal places. A dash indicates an unavailable updated runtime.
Gromov--Wasserstein optimal transport (GWOT) aligns metric measure spaces by matching their within-domain relational structures, but large-scale GWOT remains challenging because its objective is nonconvex and projection onto the transport polytope is often solved only approximately in practice. This leads to a gap between practical projected-gradient implementations and convergence theory, which typically assumes exact projections. For squared-loss GWOT, we propose an inexact projected-gradient framework with a verifiable feasibility-residual-based inexact condition for the projection subproblem. This condition is directly computable and avoids unknown quantities such as the exact projection point. Under this implementable condition, we prove subsequential convergence to stationary points and, with a mild tolerance-decay condition, convergence of the whole sequence. The resulting method retains the simplicity and sparsity of projected-gradient schemes while providing rigorous convergence guarantees, turning projected-gradient methods into a principled and scalable approach for GWOT with provable reliability.
Ling Liang, Lei Yang
Department of Mathematics The University of Tennessee Knoxville, TN 37916, USA · School of Computer Science and Engineering Guangdong Province Key Laboratory of Computational Science Sun Yat-sen University Guangzhou, Guangdong 510275, China
The Gromov-Wasserstein (GW) distance measures the discrepancy between metric measure (mm) spaces and identifies optimal alignments between them based solely on their intrinsic structure. Since it identifies isomorphic mm spaces, it provides a natural notion of distance for heterogeneous datasets which may admit isomorphic representations. In order to accelerate computation of GW distances, many practitioners employ entropic regularization to obtain an Entropic GW (EGW) problem. The most popular EGW solver is the Mirror Descent (MD) algorithm, which reduces EGW computations to an iterative process where an entropic optimal transport (EOT) problem is solved at each iteration. Despite its widespread use, the convergence of MD for this problem has only been established for restricted classes of costs. On the other hand, a recently proposed dual gradient method is available for general costs, but requires a choice of step size which depends on the regularization parameter. To address these two issues, we introduce Averaged Mirror Descent (AMD), which averages consecutive MD steps, and prove its convergence for arbitrary costs. Then, we establish that the dual gradient method with a fixed step size also converges for arbitrary costs at the cost of a more complicated iteration. In both cases, we also account for inexact iterations which are inescapable in practice. We compare the empirical performance of these methods across various settings and, in particular, show that AMD and the dual gradient method both converge on an example where classical MD fails.
Covariance matrices serve as compact descriptors of feature distributions in many machine-learning pipelines, including domain adaptation and Gaussian embeddings. Under a centered Gaussian approximation, the unregularized Wasserstein-2 optimal-transport (OT) discrepancy admits a closed form on covariances given by the Bures-Wasserstein (BW) objective on the symmetric positive definite (SPD) cone. We propose ITSPACE (Iterative Transport for Stable Proximal Alignment of Covariance Embeddings), a proximal majorization-minimization method that directly optimizes this exact BW objective through closed-form updates in a square-root factorization. In exact arithmetic, each iteration satisfies a sufficient-decrease inequality for the BW objective; under inexact polar computations, we provide an explicit certificate-gap bound controlling deviations from exact descent. The resulting iterations preserve PSD structure by construction and naturally support rank-restricted factors, making ITSPACE well-suited as a lightweight inner-loop primitive in settings where adaptation must be performed from unlabeled target batches under strict step and compute budgets. Across real-world covariance-alignment benchmarks, ITSPACE reaches low-BW-gap solutions substantially faster than BW-gradient descent, methods based on other covariance geometries, and entropically regularized sample-OT baselines.
Woojoo Na, Jennifer Dy
Department of Computer Engineering, Northeastern University, Boston, USA.