  In this work, we present the Bregman Alternating Projected Gradient (BAPG)
method, a single-loop algorithm that offers an approximate solution to the
Gromov-Wasserstein (GW) distance. We introduce a novel relaxation technique
that balances accuracy and computational efficiency, albeit with some
compromises in the feasibility of the coupling map. Our analysis is based on
the observation that the GW problem satisfies the Luo-Tseng error bound
condition, which relates to estimating the distance of a point to the critical
point set of the GW problem based on the optimality residual. This observation
allows us to provide an approximation bound for the distance between the
fixed-point set of BAPG and the critical point set of GW. Moreover, under a
mild technical assumption, we can show that BAPG converges to its fixed point
set. The effectiveness of BAPG has been validated through comprehensive
numerical experiments in graph alignment and partition tasks, where it
outperforms existing methods in terms of both solution quality and wall-clock
time.
