Adaptive Bregman Alternating Projections for Feasible Gromov--Wasserstein Learning

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) offers efficient one-marginal-at-a-time updates, yet its fixed-penalty relaxation leaves a persistent feasibility gap. We propose Adaptive BAPG, which combines a finite fixed-penalty burn-in with a guarded increasing-penalty phase. At each tail iteration, the method reuses BAPG’s inexpensive 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 every iteration and show that the feasibility gap vanishes asymptotically. We further establish a best-iterate $O(1/\log N)$ 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. Experiments on synthetic and real graph alignment, as well as heterogeneous domain adaptation, show that Adaptive BAPG achieves a favorable trade-off among objective value, predictive performance, feasibility, and stationarity compared with BAPG variants, projection-based GW solvers, and task-specific baselines.