- 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 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 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 , which is a major weakness. The only theoretical requirement of 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 using a logarithmically increasing threshold , yet the authors fail to add similar intuitions but instead focus on specific value ranges of, e.g., and , 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 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 ? A parameter study of under different values would also provide more insights into how 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?