- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper addresses the computational cost of entropic Gromov-Wasserstein when intra-space costs are geodesic distances on meshes or graphs. In this setting, standard solvers have cubic complexity, while existing accelerations designed for Euclidean or low-rank costs do not directly apply. The authors propose EGGroW, which avoids explicitly constructing dense geodesic distance matrices by exploiting fast matrix-vector products involving shortest-path distances, together with a random-feature approximation of the Sinkhorn kernel. The main contributions are near-quadratic exact and approximate solvers for geodesic GW and fused GW, as well as a GW-based formulation for partial 3D template detection. The method is evaluated on shape correspondence and template matching tasks, with comparisons against dense GW solvers and Euclidean and low-rank baselines in terms of accuracy and runtime.
Critical strengths
Relevant problem. Scaling GW to geodesic costs is an important challenge in 3D applications, where intrinsic distances are often more appropriate than Euclidean distances.
Effective exact speedup. DET-EGGroW eliminates the cubic complexity while producing the same results as dense FGW in the experiments.
Practical solver formulation. The generalized Sinkhorn update for the KL-regularized semi-relaxed problem is clearly derived and works with both variants.
Critical weaknesses
As far as I understand the main algorithmic contribution appears to be an incremental extension of GenusSink with limited practical gains. DET-EGGroW is only about 1.5× faster than dense GW at n = 2000 and is slower for smaller problems. The approximate variant comes at a substantial cost in accuracy and performs poorly on the template matching experiment. The hardware is not specified, and it is unclear whether the reported runtimes include the computation of geodesic distance matrices.
I was expecting more comparisons. Relevant baselines are absent (not all are needed):
- Detection and registration: ICP, RANSAC + FPFH, TEASER++, and point-pair features. Partial and semi-relaxed GW methods (Chapel et al. Neurons 2020, Vincent-Cuaz et al. ICLR 2022) are also missing, although the proposed formulation builds on this line of work.
- Correspondence: The comparisons are limited to nearest neighbors and Euclidean OT, which are relatively weak baselines. Established mesh correspondence methods such as functional maps and ZoomOut, as well as entropic GW on meshes (Solomon et al., Siggraph 2016), are not considered. Moreover, the FAUST evaluation includes only three pairs from a single subject.
- Scalability: There is no comparison with other scalable GW approaches, including low-rank GW with factorized geodesic costs, or quantized and sampled GW.
Insufficient evaluation of detection. Despite being presented as a detection method, the quantitative template experiments only consider full-to-full matching between synthetically deformed copies, without clutter or occlusion. Localization, pose estimation, and visibility are illustrated qualitatively on a single scene, with no quantitative detection metrics such as localization accuracy or pose error. The two-stage approach is also not ablated.
Questions for authors
Which hardware was used, and do the reported runtimes include computing the geodesic matrices for the dense baselines? Why does dense GW take about 900s at n = 2000, and what share of the time is spent in the inner Sinkhorn iterations rather than the cubic term?
How does EGGroW compare with low-rank GW (Scetbon et al., 2022) using a low-rank factorization of the geodesic matrices (e.g. landmarks or Nyström), and with quantized or sampled GW?
Can you report quantitative detection results on real scenes with clutter and occlusion (pose error, localization accuracy), against ICP, RANSAC + FPFH or TEASER++, and against partial or semi-relaxed GW?
How much does each component contribute: Stage II compared with Stage I alone, the KL visibility prior, and the parameters ρ_s and τ?
The exact algorithm assumes separators of size O(log log n), but triangle meshes usually have separators of size about √n. Which algorithm is used on the meshes in the experiments, the exact one or GenusSink’s approximate extension, and what is its actual complexity in that setting?
2 comments
I thank the authors for the clarifications in their rebuttal regarding the experimental hardware, timing protocol, and theoretical assumptions. They address some of the questions raised, though most of my main concerns remain. No additional experimental evidence is provided in the rebuttal, and while the authors acknowledge the need for stronger validation of the detection approach, the limited practical gains, missing comparisons, and unclear complexity guarantees for triangle meshes remain unresolved. I still believe that the paper would benefit from major revisions, and I therefore maintain my original rating.
We thank the reviewer for the detailed comments. The experiments were run on an Intel Xeon Platinum 8460Y+ processor. Note that as specified in Appendix B.2, the reported timings include method-specific setup and solving, excluding shared calibration, input loading, and post-solve scoring. The FAUST experiments used 50 outer updates with 500 inner Sinkhorn iterations per update. The reported timings combine setup and optimization, so they do not provide a separate allocation between inner Sinkhorn iterations and structural matrix products. We will clarify the timing description, particularly the treatment of geodesic preprocessing!
Our evaluation includes comparisons with dense GWD/FGWD and Euclidean baselines, together with random-feature ablations. The dense FGWD comparison directly examines whether computational savings preserve the correspondence quality of the underlying formulation. In Table 2, DET-EGGroW matches the reported dense FGWD errors on all three pairs. For example, on 004 → 003, runtime decreases from 1077.2 s to 587.0 s while retaining an error of 0.166. APP-EGGroW with r=64 reduces runtime further to 320.8 s, with an error of 0.240, illustrating the additional accuracy-runtime tradeoff. The suggested low-rank, quantized, and sampled GW methods offer other approaches to scalability, and we will discuss their relationship to our geodesic-operator approach more clearly.
As for detection, Figure 3 provides a qualitative scene-localization example, while Appendix B.3 describes controlled correspondence experiments between deformed shapes. We will make this distinction clearer in Section 5.2 and present the scene example as a proof of concept for the two-stage formulation. We agree that a dedicated evaluation of localization and pose accuracy under clutter and occlusion as the reviewer had mentioned, including the suggested registration and partial-GW baselines, would be a good extension of this study.
Moreover, the component questions are also useful for identifying what such an evaluation should measure. Stage I selects scene support and provides an initial alignment, while Stage II refines template visibility and correspondence with that alignment fixed. Comparing Stage I alone with the complete pipeline, varying the visibility prior, and examining sensitivity to ρs and τ would definitely help quantify their respective contributions as the reviewer mentioned. We will clarify these component roles and identify these ablations as directions for further evaluation.
Finally, the near-quadratic guarantee in Section 3 relies on the stated small-separator assumption. Triangle-mesh structure alone does not establish that condition, and Table 1 separately makes DET’s exactness conditional on exact operators. We will make these assumptions more prominent in the camera-ready version and distinguish the conditional complexity result from the empirical mesh timings.