A Convergent Single-Loop Algorithm for Relaxation of Gromov-Wasserstein in Graph Data
This work addresses the efficiency bottleneck in graph matching and partitioning for researchers and practitioners in machine learning, though it is incremental as it builds on relaxation techniques.
The paper tackles the computational challenge of approximating the Gromov-Wasserstein distance for graph data by introducing the BAPG algorithm, which achieves faster convergence and better solution quality in graph alignment and partition tasks compared to existing methods.
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.