acceptodds
Under review as a conference paper at ICLR 2027

Adaptive Bregman Alternating Projections for Feasible Gromov–Wasserstein Learning

Abstract

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) uses inexpensive alternating row and column updates, yet its fixed-penalty relaxation leaves a persistent feasibility gap. We propose Adaptive KL-BAPG (A-KL-BAPG), which combines a finite fixed-penalty burn-in with a guarded increasing-penalty phase. At each tail iteration, the method reuses BAPG’s 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 each iteration and show that the feasibility gap vanishes asymptotically. We further establish a best-iterate 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. This distinguishes A-KL-BAPG from fixed-penalty BAPG, whose stationarity guarantees are given for the relaxed problem. Experiments show that A-KL-BAPG achieves a favorable balance of accuracy, objective value, feasibility, and stationarity relative to BAPG variants, projection-based methods, and task-specific baselines. For synthetic and real graph alignment problems, it closely matches the accuracy and objective value of fixed-penalty KL-BAPG while reducing the marginal feasibility gap by - and the projected stationarity residual by -. Heterogeneous domain adaptation experiments show a similar pattern: A-KL-BAPG maintains comparable target accuracy and objective values while achieving improved feasibility and stationarity than fixed-penalty KL-BAPG.

Primary area:
optimization
Keywords:
Gromov-Wasserstein optimal transport, Bregman alternating projected gradient, adaptive penalty methods, Sinkhorn scaling, nonconvex optimization, graph alignment, domain adaptation

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_PHdNOpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes A-KL-BAPG, an adaptive variant of the KL-BAPG algorithm that solves the Gromov-Wasserstein (GW) Optimal Transport (OT) problem by separating the row and column constraints into two variables for OT. A-KL-BAPG aims to bridge the feasibility gap of KL-BAPG by combining its fixed-penalty iterations with a guarded increasing-penalty phase, which gradually increases the KL penalty between two separated variables. Extensive theoretical analysis regarding the feasibility and stationarity of A-KL-BAPG is included. The proposed A-KL-BAPG is evaluated on 4 different tasks, and the authors report the GW objective, feasibility, stationarity, downstream-task accuracy, and runtime to demonstrate that A-KL-BAPG achieves a favorable balance.

Critical strengths
  • The motivation of A-KL-BAPG, which aims to bridge the feasibility gap of BAPG for solving GW OT, is well-founded. The idea of increasing the KL penalty ρ\rho after a burn-in phase is intuitive and easy to understand.
  • The comprehensive theoretical analysis regarding the feasibility and stationarity of A-KL-BAPG is a major contribution of this paper towards the BAPG family. Compared with the original KL-BAPG, the proposed A-KL-BAPG establishes stronger theoretical guarantees, including vanishing marginal feasibility errors, the existence of a stationary accumulation point, and an explicit convergence rate to the stationary point. More importantly, A-KL-BAPG removes the non-trivial bounded AAE assumption, which is required for the original KL-BAPG for convergence guarantees but is hard to verify in practice.
  • The evaluation tasks and reported metrics are quite comprehensive. A-KL-BAPG is evaluated across 4 different tasks: synthetic graph alignment, real graph alignment, synthetic domain adaptation, and real-world domain adaptation. The authors report several different metrics spanning the GW objective, feasibility, stationarity, downstream-task accuracy, and runtime, providing a comprehensive picture of the empirical performance of A-KL-BAPG.
Critical weaknesses

While the paper provides strong theoretical results, it suffers from several weaknesses in justifying its design choices, experimental design, and presentation. Specifically,

  • The burn-in k0k_0 is a critical hyperparameter for A-KL-BAPG that decides when to switch from the fixed-penalty burn-in phase (KL-BAPG) to the guarded increasing-penalty tail phase (A-KL-BAPG). However, the authors provide neither theoretical analysis or empirical study regarding the sensitivity of A-KL-BAPG to k0k_0, which is a major weakness. The only theoretical requirement of k0k_0 seems to be larger than zero and smaller than infinity, which is less informative.
  • While the authors include the total runtime in the current experimental results, a detailed runtime breakdown of different components in A-KL-BAPG is missing. As A-KL-BAPG consists of multiple different components, e.g., fixed-penalty burn-in, guarded increasing-penalty tail, and backtracking, a detailed runtime breakdown would help clarify the efficiency and computational trade-off of these design choices.
  • While the projective-diameter safeguard is the key to the theoretical feasibility and stationarity of A-KL-BAPG, the authors fails to include empirical ablation of this mechanism, making its practical effect unclear.
  • The core contribution of this paper is the guarded increasing-penalty tail, which is introduced in the paragraph starting line 133. However, I find the presentation of this paragraph poor. The authors prioritize mathematical details over explaining the intuition behind the proposed mechanisms and how they correspond to Algorithm 1, making the core contribution of this paper harder to understand. For example, the left part of equation (3) essentially introduces a projective-diameter safeguard mechanism, which controls the projective diameter of ωt+1\omega^{t+1} using a logarithmically increasing threshold Γt+1\Gamma_{t+1}, yet the authors fail to add similar intuitions but instead focus on specific value ranges of, e.g., α\alpha and β\beta, which can be delayed. I believe explicitly connecting each mechanism of the guarded increasing-penalty tail to the corresponding steps in Algorithm 1 and providing simple intuitions in this paragraph would significantly improve the clarity of this paragraph.
Questions for authors
  • How does k0k_0 affect the GW objective, feasibility, and stationarity of A-KL-BAPG? Can you provide some in-depth theoretical analysis on how to select the optimal k0k_0? A parameter study of k0k_0 under different values would also provide more insights into how k0k_0 affects the objective value, feasibility, and stationarity of A-KL-BAPG.
  • The runtime benefit of A-KL-BAPG over KL-BAPG seems inconsistent. A-KL-BAPG outperforms KL-BAPG on synthetic graph alignment in runtime, but is outperformed by KL-BAPG on real graph alignment and real-world domain adaptation. Particularly, Table 4 in Appendix B.4 shows that A-KL-BAPG is more than 5 times slower than KL-BAPG on real-world domain adaptation. Can you provide an explanation regarding the observed latency?
  • How does the projective-diameter safeguard affect the empirical feasibility and stationarity of A-KL-BAPG?
  • The accuracy of POT CG in Table 1 exceeds 1.0 (5.39). Why is this possible? How is accuracy defined in Table 1?
Reviewer_fWgFOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper proposes Adaptive KL-BAPG (A-KL-BAPG) to address the persistent feasibility gap caused by the fixed-penalty relaxation of BAPG. The method combines a fixed-penalty burn-in phase with an increasing-penalty schedule and a projective-diameter-based backtracking safeguard. The authors establish asymptotic feasibility, absolute summability of asymmetric Bregman errors, and an O(1/log⁡N)O(1/\log N) best-iterate bound for the weighted squared corrected residual. Under an additional support regularity assumption, they further prove the existence of a stationary accumulation point for the original constrained GW problem.

Critical strengths
  1. The connection between alternating KL-BAPG updates and Sinkhorn's projective contraction provides an interesting motivation for the proposed safeguard.

  2. The theoretical analysis goes beyond the relaxed fixed-penalty formulation by establishing asymptotic feasibility and, under an inactive-support nonnegative-residual assumption, the existence of a stationary accumulation point for the original constrained GW problem.

Critical weaknesses
  1. Theorem 2 requires Assumption 1, which imposes a nonnegative limit inferior of the corrected residual on inactive support entries. This condition is not shown to follow from the algorithmic updates and may be difficult to verify in practical GW problems. Although Proposition 1 provides an a posteriori sufficient condition, its applicability remains unclear. The authors should clarify when this assumption holds and discuss its implications for the stationarity guarantee.

  2. The computational overhead of the proposed method could be further analyzed. In the HAR70+ experiments, the reported mean runtime increases from 11.739 seconds for KL-BAPG to 67.665 seconds for A-KL-BAPG. It would be helpful to clarify the sources of this additional computational cost, particularly the overhead introduced by backtracking and projective-diameter evaluations.

  3. Although several alternative step-size schedules are evaluated, the individual contributions of the fixed-penalty burn-in, delayed-power schedule, and projective-diameter safeguard are not fully isolated. Additional ablations on the burn-in length and safeguard parameters would help clarify which components drive the observed improvements.

Questions for authors
  1. Under what practically verifiable conditions does Assumption 1 hold? Can the authors provide an example where it fails?

  2. What explains the approximately 5.8-fold increase in mean runtime of A-KL-BAPG compared with KL-BAPG on HAR70+ (Table 4), and how does the method compare under matched computational budgets?

  3. Can the authors provide more complete component-wise ablations to clarify the contributions of the burn-in phase and the projective-diameter safeguard?

Reviewer_WHBaOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper addresses a limitation of BAPG for Gromov–Wasserstein optimization: its inexpensive updates can leave persistent violations of the marginal constraints. The proposed A-KL-BAPG first runs with a fixed penalty to make progress on the objective, then increases the penalty while using an adaptive safeguard to control the updates. The authors show that the marginal violations vanish asymptotically and derive a convergence bound for a weighted residual. Under an additional condition on entries that approach zero, they also establish the existence of a stationary accumulation point for the original constrained problem.

Critical strengths

1, The method keeps BAPG's simple updates and proves that errors in the required row and column sums approach zero as iterations continue. It also proves that the accumulated asymmetric Bregman errors remain bounded, rather than assuming this as earlier work did. This is a stronger guarantee on constraint satisfaction. 2, Across graph matching and domain adaptation tasks, the method largely maintains the accuracy of fixed-penalty BAPG while reducing constraint errors. The reported stationarity results also improve.

Critical weaknesses
  1. The accuracy of the stationarity evaluation needs clarification. Section 4.1 and Appendix B.1 evaluate KL-BAPG and its Sinkhorn-postprocessed version after further row/column scaling. If both use the same strictly positive KL-BAPG output, postprocessing only rescales rows and columns, and evaluation scaling converges to the same positive target marginals, the evaluation matrices should coincide. The reported residuals differ (0.470 vs. 0.140 in Table 1; 0.178 vs. 0.417 on ENZYMES). Finite scaling or numerical modifications could explain this. The missing evidence is whether the evaluation is accurate enough to support the reported stationarity gains.

  2. The benefit of the safeguard is not separated from the benefit of burn-in. A-KL-BAPG uses 1000 fixed-step iterations for graph alignment and 500 for domain adaptation, whereas the 1/k1/k and pure-power baselines shrink their steps from the start. Figure 2 shows that much of the objective improvement occurs during burn-in. Without giving the baselines the same start, it is unclear how much the safeguard adds. Corollary 1 provides these feasibility and residual guarantees for a suitably scaled harmonic schedule, but the experiments do not evaluate this schedule after the same burn-in.

Questions for authors
  1. Beyond the a posteriori condition in Proposition 1, are there verifiable conditions on the input data or algorithm parameters that ensure Assumption 1? This would clarify the scope of the stationarity guarantee.

  2. How accurate are the stationarity diagnostics? Please specify how the feasible shadows and Euclidean projections are computed, including their stopping criteria and achieved accuracy. Do A-KL-BAPG’s reported stationarity gains persist when the diagnostic tolerances are tightened?

  3. Does the safeguard help after identical burn-in? Compare the proposed tail with scaled 1/k1/k and unguarded delayed-power schedules under equal runtime budgets. Do the gains in feasibility and stationarity persist without sacrificing objective value or accuracy?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.