Bregman–Gromov–Wasserstein Clustering: Finite-Length Whole-Sequence Convergence and Local Initialization Consistency

Gromov–Wasserstein (GW) graph clustering methods recover communities from pairwise relations by matching nodes to a prototype graph. We propose Bregman–Gromov–Wasserstein (BGW) clustering, which jointly learns the node–prototype transport $\pi$, the cluster masses, and the prototype relation $D^{\prime }$. The prototype relation admits a closed-form Bregman barycenter update, which we combine with mirror descent on the transport in an alternating solver. We prove finite-length whole-sequence convergence to a constrained critical point and characterize the vanishing-floor limit of the assignment update. We further establish finite-horizon Lipschitz continuity with respect to initialization, showing that the output perturbation is controlled by the initial perturbation up to prototype relabeling. Experiments reveal that different structured initializations can lock BGW into distinct finite-budget solutions, and that their effectiveness varies across graphs. We therefore design MixGSP, combining GWL, SpecGWL, and product plans to broaden the structured solutions explored by BGW, yielding improvements over some existing GW clustering methods across the benchmarks.