acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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 , the cluster masses, and the prototype relation . 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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Gromov--Wasserstein Clustering, Optimal Transport, Bregman Divergence, Nonconvex Optimization, Initialization Sensitivity

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_rZBTOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This manuscript introduces a new graph node clustering method based on the Gromov-Wasserstein (GW) framework. The study introduces trainable weight parameters related to intra-cluster relationships into an existing GW model and develops an optimization algorithm for the extended model. Furthermore, the convergence of the algorithm is theoretically analyzed. Numerical experiments using real datasets demonstrate the superior performance of the proposed method over existing baseline methods.

Critical strengths

The extension of the conventional GW model is reasonable. Additionally, the discussion on the theoretical connection among previous models is interesting.

Critical weaknesses

Although the proposed method is strongly affected by the hyper-parameters (ρ\rho and ww of the MixGSP initialization defined in line 364), their effect is not validated in the numerical experiments. Performance results using the best hyper-parameter for each dataset do not provide a fair comparison with existing methods. Furthermore, because the initialization depends on the previous models (GWL and SpecGWL), the effectiveness of the extended parameter is not confirmed from the current experimental results.

Questions for authors
  1. How were the MixGSP weights (ρ\rho and ww) adjusted? This is essential in practice to evaluate the performance.
  2. Does Table 8 demonstrate that the proposed optimization does not work without manually adjusted initialization? This might indicate some mistakes in the algorithm derivation or existence of serious local minima in the parameter space.

Minor comments:

  1. In Figure 1(b), The locations of variables are unnatural.
  2. In line 149, why did you define another variable?
  3. The sentence in line 327-328 includes a grammatical mistake.
2 comments

Thank you for the constructive review and minor corrections. We address your questions below.

1. Selection of the MixGSP weights, fairness, and what is isolated (W1 & Q1)

  • How the weights are adjusted. The weights are not set by hand for each dataset and are not tuned with labels. They are searched jointly with the other solver parameters in a fifty-trial TPE run, using the graph-assigned internal criterion in Table 24; labels are used only for the final AMI report (Algorithm 2, Appendix E). Table 25 separates the selector result from the highest AMI in the same search pool, so Table 1 does not report the best-AMI trial.
  • Budget size. The fifty-trial budget was adopted as a conservative common budget for comparability across graphs and baselines. The same unsupervised selector protocol also applies at smaller budgets, with the usual increase in selection variability.
  • Fairness of the GW comparison. Appendix L.2 reruns EGW, BAPG, and srGW on the same heat kernels with the same fifty-trial budget (Table 26); the BGW selector assignment and the baseline selection protocol are documented in Tables 24 and 26. This controls input and search budget for the solver comparison.
  • Sensitivity boundary. We did not run a standalone two-dimensional grid over the two MixGSP weights. The ablation in Table 8 and the alternative starts in Tables 9, 13, and 14 show how the endpoint changes when components or start families change, but they do not isolate a continuous joint effect of the two weights. We therefore do not claim that this specific sensitivity has been separately validated.
  • Effect beyond the two constituent starts. BGW is not tied to those starts alone: from Spectral or k-means++ starts it reaches 0.917 and 0.895 on Amazon (Table 13). For the separate question of what prototype learning itself adds, we use the controlled Fixed/Diagonal and generator-scale analysis in our response to Reviewer j82N (Q2), including its stated boundary.

2. Does Table 8 indicate derivation mistakes or serious local minima? (Q2)

It is the second case: there are no derivation mistakes, and the issue is uninformative local minima and stationary points—in nonconvex GW optimization, a point optimized to a local minimum (or stationary point) of the objective does not necessarily match a high-quality clustering partition.

  • Exact solver and derivation: Appendix G (Tables 5–6) verifies that the closed-form D~\tilde{D} update has zero residual (rD~=0r_{\tilde{D}}=0), the Stage II descent condition holds at every step (RII,T<1R_{\mathrm{II},T}<1), and FλF_\lambda decreases monotonically.
  • Why local minima need not match good partitions: The fourth-order GW objective is nonconvex with numerous suboptimal stationary points and local minima (Peyré et al., 2016; Li et al., 2023), which is why existing GW partitioners also rely on structured starts such as kk-means or degree-ordered priors (Xu et al., 2019; Chowdhury & Needham, 2021; Vincent-Cuaz et al., 2022). In Table 8, turning MixGSP off sets π0=pspt⊤\pi^0=p_s p_t^\top. In Table 14 (Appendix I.3), our solver converges cleanly from Product and 150 random seeds (Dir, Logit-normal, Stick-breaking) to exact stationary points with machine-zero residuals (1.6×10−161.6\times 10^{-16} to 4.1×10−164.1\times 10^{-16} on Amazon—smaller than high-AMI solutions), yet their partitions have AMI=0.000\mathrm{AMI}=0.000. Even among structured starts, lower FλF_\lambda need not mean higher AMI (on Wiki(dir), SpecGWL-as-π0\pi^0 reaches Fλ=−7.04×10−4F_\lambda = -7.04\times 10^{-4} with AMI 0.2260.226, whereas Mixed+noise has Fλ=−3.11×10−4F_\lambda = -3.11\times 10^{-4} with AMI 0.3230.323).
  • No manual adjustment needed: In Tables 13–14, off-the-shelf starts with zero manual weights (Spectral 0.9170.917, $k$-means++ 0.8950.895 on Amazon) directly reach high-AMI solutions, and in Table 1 MixGSP selects (w,ρ)(w,\rho) automatically via unsupervised criteria (Table 24).

3. Minor comments

We fixed all three in the revised PDF: (i) repositioned d3d_3 and padded δφ\delta_\varphi labels in Figure 1(b); (ii) removed redundant sks_k (Line 149) in favor of νk\nu_k; and (iii) fixed the grammar at Lines 327–328.

Reviewer_rZBTOpenReview ↗

No changes to scores

Thank you for your response. However, I still have concerns regarding the second point. The proposed optimization method relies heavily on the MixGSP initialization, which is a combination of existing methods. It remains unclear how the proposed optimization improves performance over this initialization. Based on the numerical results, the improvement appears to be limited.

Reviewer_KofJOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

The authors introduce Bregman–Gromov–Wasserstein (BGW) clustering, an extension of Gromov–Wasserstein (GW) clustering where the cluster self-similarity is learned. For an input a graph GG (given as an N×NN \times N similarity matrix DD), node weights μi\mu_i, and number of clusters KK, the algorithm learns soft assignments πi,k\pi_{i,k}, where πi,k/μi\pi_{i,k}/\mu_i gives the fractional assignment node ii to cluster kk, as well as the cluster self-similarities dkd_k, which defines what the similarity of nodes assigned to cluster kk should be. For example, if nodes ii and jj are assigned to cluster kk, then Di,jD_{i,j} should be near dkd_k.

The authors analyze the optimization dynamics and convergence, as well as the dependence on the initial values. Experiments complement the analysis and evaluate BGW clustering across multiple datasets and against various other methods.

Critical strengths

(1) The analysis of convergence and initialization dependence is good. It is more substantial than simply showing that the objective is monotonic.

Critical weaknesses

(1) The proposed method of learning the cluster self-similarities is unmotivated and has no established benefit. What problem does BGW solve? Why learn the cluster self-similarities? The introduction observes that prior methods fix these values, and that they can be learned. However, there is no convincing motivation, explanation, or evidence for learned self-similarities actually producing better clusterings. Section 4.1 states "learning the diagonal does not consistently improve AMI over the fixed-diagonal variant"; then what is the point? Among its 51 pages, the submission leaves its central modeling question unanswered.

(2) The presentation is exceptionally difficult to follow, even with careful reading. The authors delay the clustering interpretation to page 9, which was necessary to even understand the objective in Section 2.1. Figure 1 is incomprehensible until the reader already knows what is happening. φ′\varphi' is used to mean the derivative of φ\varphi, which is incredibly confusing given that D′D' is used to mean the "prototype" analogue of DD in the same context. The context keeps switching between the more general model and the clustering restriction.

(3) The "supplementary artifact" claimed in the reproducibility statement is not attached in OpenReview.

Questions for authors

(1) What are the concrete benefits of learning the cluster self-similarities?

1 comment

Thank you for recognizing the substance of our convergence and initialization analyses (Soundness: 3). Your review helped us see how our framing in Sections 1 and 4.1 could give a misleading impression of the paper's central claim, and your critiques on notation and presentation were well taken.

1. Role of learning the cluster self-similarities and concrete benefits (W1 & Q1)

We agree that iterative Stage II updates alone do not establish the benefit. The detailed answer is in our response to Reviewer j82N (Q2): at a fixed generator, with the same start and budget, per-cluster Diagonal updates give no validated notable AMI gain over Fixed.

The concrete problem addressed by learning is narrower. A prescribed prototype fixes one target scale before the partition is known, while clusters in a multi-scale heat kernel can have very different internal similarities and masses. Learning sets each prototype scale from the current transport through the Bregman barycenter, and the generator determines which scale is emphasized. Our response to Reviewer j82N (Q2) gives the benchmark evidence and its boundary: KL/IS recover small or uneven allocation structure missed by the L2/fixed-scale runs, while recovering a small family need not raise global AMI. The supported benefit is automatic scale and allocation adaptation, together with calibration of the initial prototype.

2. Presentation, notation, and early clustering explanation (W2)

We have revised the manuscript to address each readability issue:

  • Disambiguated D′D' vs. φ′\varphi': We replaced the prototype matrix D′D' with D~\tilde{D} throughout the main text, appendices, and Figure 4 legend, so primes denote only derivatives φ′,φ′′\varphi',\varphi''. We also removed the redundant symbol sks_k in favor of νk=∑iπik\nu_k=\sum_i\pi_{ik}.
  • Explained why this is graph clustering directly in Sections 1 & 2.1–2.2: We updated Section 1 to explain the core idea of GW clustering and why D~\tilde{D} must be learned on page 1, defined all symbols in Figure 1 at the start of Section 2, and revised Section 2.1 (around Eqs. (4)–(5)) to explain directly—without waiting for Section 5—why matching GG to the block-structured prototype D~\tilde{D} clusters the graph: assigning nodes i,ji,j to the same cluster kk matches DijD_{ij} to dkd_k, whereas assigning them to different clusters k≠lk\neq l matches DijD_{ij} to the background level δφ(D)\delta_\varphi(D), while −λ∥π∥F2-\lambda\Vert\pi\Vert_F^2 promotes crisp row assignments. We also cleaned up label placement in Figure 1(b).
  • Full D~\tilde{D} vs. diagonal dkd_k: Section 2 opens by explaining that we state the updates and convergence theory for a full K×KK\times K matrix D~\tilde{D} and specialize them to the diagonal clustering structure (Eqs. (6)–(7), Corollary 2), so the same framework serves community detection while extending directly to unrestricted coarse-grained kernels in dimensionality reduction (Appendix M).

3. Supplementary artifact (W3)

We apologize for the confusion. All proofs, solver protocols, and full numerical tables are contained in Appendices A-M of the submission PDF, and references to a separate external artifact archive have been removed from the revised text.

Reviewer_j82NOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The authors also study initialization sensitivity and propose a start-lock phenomenon, which motivates MixGSP, an initialization strategy which mixes existing GW clustering-methods. Experiments on graph-clustering benchmarks suggest improvements upon some GW-based baselines, but with results showing that initialization has more effect on the clustering result than prototype adaptation.

Critical strengths
  1. Rigorous optimization analysis: the paper establishes finite-length whole-sequence convergence of the alternating transport-prototype optimization under appropriate assumptions. The treatment of the vanishing transport floor also nicely connects to the theory to practice.

  2. Systematic analysis of the initialization: the analysis of initialization sensitivity and the observation of empirical start-lock phenomenon provides an interesting insight into the nature of the nonconvex optimization dynamics. In particular, the paper reveals that finding a stationary point does not necessarily correspond to finding a meaningful clustering solution.

Critical weaknesses

1. Limited demonstrable benefit of prototype learning.

While learning the prototype relation is a core motivation of the method, the ablative studies show that prototype adaptation does not consistently improve clustering performance, with initialization appearing to dominate the process. This makes it challenging to evaluate the practical value of the novel formulation.

2. Questionable scientific value beyond optimization guarantees.

While the convergence analysis is a technically interesting result, it is unclear what new insight into graph clustering it provides; finding a critical point does not explain when communities will be recovered, while the initialization sensitivity identified empirically is not explained by the theory. Meanwhile, the method provides no demonstrable improvement over the best existing clustering baselines. Thus, the paper does not demonstrate either major new insight into the clustering problem, or significant practical benefit.

Questions for authors

1. Scientific implications of the convergence results. Other than demonstrating that one can obtain whole-sequence convergence under the KL framework, what insight on graph clustering or optimization landscape does the analysis provide? Can the authors identify the set of conditions under which the theoretical results help understand the quality of the recovered partitions?

2. Contribution of prototype learning. Since the ablations show limited improvement by learning prototype relation, can the authors identify scenarios in which prototype adaptation provide notable improvement over a fixed-prototype approach with the same initialization and optimization budget?

3. Initialization robustness. To what extent the finite-horizon Lipschitz continuity result explain the observed start-lock phenomenon? Furthermore, since MixGSP combines transport plans of different clustering algorithms, how is the ambiguity of prototype-label permutations dealt with?

2 comments

Thank you for the careful review. We address your questions in order.

1. Scientific implications of convergence and partition quality (Q1 & W2)

Theorems 1–2 and Propositions 1–2 are optimization/stability guarantees rather than statistical recovery theorems (Table 14: unstructured starts reach 10−1610^{-16} residuals at AMI=0\mathrm{AMI}=0). They inform clustering in two ways:

  • Objective structure (Sections 2.1 & 5, Eqs. (10)–(12)): At dk=hk(π)d_k=h_k(\pi), Ψ\Psi splits into within-cluster Bregman clustering around dkd_k and inter-cluster contrast against δφ(D)\delta_\varphi(D). For φ(x)=x2/2\varphi(x) = x^2 / 2, minimizing Ψ\Psi maximizes mass-normalized affinity (νk=∑iπik\nu_k=\sum_i\pi_{ik}):

∑k=1KQk(π)2νk2,Qk(π)=π⋅,k⊤Dπ⋅,k.\sum_{k=1}^K \frac{Q_k(\pi)^2}{\nu_k^2}, \qquad Q_k(\pi) = \pi_{\cdot,k}^\top D \pi_{\cdot,k}.

  • Finite-budget partition retention (Proposition 2 & Corollary 4, Appendix D): If z=(π0,D~0)z=(\pi^0,\tilde{D}^0) has positive JJ-step row margin γJ\gamma_J, any z^\hat{z} within the stability radius (in ∥z∥×=∥π∥F+∥D~∥F\Vert z\Vert_\times = \Vert\pi\Vert_F + \Vert\tilde{D}\Vert_F):

γJ=min⁡i[πi,ki⋆J−max⁡l≠ki⋆πilJ]>0,min⁡σ∥zσ−z^∥×<γJ2LoutJ,\gamma_J = \min_i \left[\pi^J_{i,k_i^\star} - \max_{l\neq k_i^\star}\pi^J_{il}\right] > 0, \qquad \min_\sigma \Vert z^\sigma - \hat{z}\Vert_\times < \frac{\gamma_J}{2L_{\mathrm{out}}^J},

yields the exact same JJ-step hard partition up to relabeling. With Theorem 1, the start selects the endpoint group (Section 4.1) and updates refine it locally.

On baselines (W2): flow/spectral methods lead on Village, EU(sym), and EU(dir); BGW leads GW methods on 4/6 graphs (Table 1) and 5/6 matched heat-kernel TPE runs (Table 26).

2. Contribution of prototype learning at matched initialization and budget (Q2 & W1)

Direct answer. At a fixed generator, with the same start and budget, we currently have no validated scenario in which iterative per-cluster learning (Diagonal) gives a notable AMI improvement over a fixed prototype (Fixed): the 12 cells in Table 9 differ by at most 0.0030.003, apart from the single-scale Shared cell on Amazon SpecGWL (+0.084+0.084).

Where a gain can arise. A prescribed prototype fixes one scale before the partition is known, so it can miss a small or tight family when within-cluster similarities span several scales. Learning instead assigns each prototype scale and cluster mass from the current transport. The generator controls the scale emphasized: L2 is dominated by large entries, whereas KL and IS retain sensitivity to small entries (Appendix J.1, Tables 17-20; Table 18). Large scale separation plus a relative-scale generator is therefore the candidate regime for a notable gain.

Evidence and boundary. On EU(sym) (K=42), KL separates cluster masses from about 0.0001 to 0.135, while L2 keeps every mass near 1/42; on Amazon, KL/IS use 8 nonempty clusters rather than the 12 nearly equal clusters produced by L2/Fixed (Tables 9 and 21). KL/IS therefore recover allocation structure missed at the L2/fixed scale. A small family can change the number of nonempty clusters and allocation while contributing little to global AMI because it contains few nodes: on Wiki(sym), increasing the learned-prototype weight raises the nonempty count from 8 to 12 without raising AMI (Table 27). This supports scale and allocation adaptation, not yet a validated notable global AMI gain at fixed generator.

3. Initialization robustness and prototype-label permutations in MixGSP (Q3)

  • What the finite-horizon bound explains. Proposition 2 is a local persistence statement: after optimal prototype relabeling, the terminal state changes by at most a constant raised to the horizon times the initial change, and Corollary 4 gives the same hard partition when the initial gap is below the terminal row-margin threshold. The perturbation test agrees (Appendix I.2): a small product-plan component leaves terminal labels nearly unchanged, whereas the pure product plan changes about 90 percent. The bound therefore explains why starts near a structured start remain in its endpoint group.
  • What it does not explain. Distinct structured starts are far apart, so the local bound does not prove separate basins or barriers and does not rank AMI. Start-lock is the empirical concentration of each family around its own endpoint group (Section 4.1); theory explains local persistence, while separation and quality of distinct groups remain empirical.
  • Permutation ambiguity in MixGSP. No separate Hungarian matching is applied before mixing. GWL and SpecGWL use the same mass-ordered target marginal q, so their columns enter MixGSP in the common order of decreasing target mass; the product-plan component is label-invariant. Mixing is therefore defined in that shared coordinate order, and endpoint comparisons align labels by permutation. This ordering resolves the coordinate ambiguity operationally, but it is not a semantic guarantee under tied or nearly tied masses; Section 6 states this reliance explicitly.

Thanks to the authors for addressing my questions. While the response clarifies several points, my overall evaluation stands and I will retain my current rating.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.