acceptodds
Under review as a conference paper at ICLR 2027

Unlocking Geodesic Gromov-Wasserstein Distances for 3D Modeling

Abstract

(GWDs) provide quantitative ways of comparing probabilistic distributions defined on different metric spaces by applying techniques from the optimal transport theory. As such, GWD can be potentially useful in a large variety of applications ranging from graph matching problems to 3D object detection. However its practical use at scale is significantly limited by cubic time complexity computations involving dense intra-space distance matrices. Even though in the Euclidean metric spaces several techniques (e.g. involving scalable kernel methods) were proposed to address it, to the best of our knowledge, analogous techniques for general geodesic distances on manifolds, or shortest-path distance on graphs in their discretized variants, were not developed. In this paper, we present fficient eodesic mov-asserstein methods (EGGroW), a new class of efficient algorithms designed to calculate geodesic Gromov-Wasserstein distances with entropic Sinkhorn-like approaches, leveraging recently introduced methods and the theory of random features. We provide important downstream applications, namely: 3D pose estimation and 3D template detection. In the latter setting, we formulate a partial 3D template recovery as a staged problem: capacity-constrained scene selection is followed by semi-relaxed recovery of template visibility and correspondence. Our empirical findings show that EGGroW provides accurate solutions when standard Euclidean-based techniques fail and is characterized by light computational footprint, as our theoretical analysis predicts.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
optimal transport, random features

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_obt6OpenReview ↗
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

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=64r=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\rho_s and τ\tau 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.

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.

Reviewer_NZNEOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The authors tackle the problem of compute the Gromov Wasserstein (GW) geodesic distance on 3D shapes and computing time-wise efficient implementations. The authors extend and existing line of works and derive with minimal changes and combinations of existing works 2 approximations, one deterministic exact and a faster one using random low rank projections. The authors evaluate their GW calculators on 3D shape correspondence and 3D template detection.

Critical strengths
  • The paper explores GW for 3D shapes. Generally speaking, I believe GW in 3D deserves more attention. Making it faster can only help to boost its popularity.

  • The implementation does seem faster than naive core optimal-transport/GW-based implementations, which is always a good thing.

Critical weaknesses
  • In my opinion, if you can compute the GW distance, then you have also found the matching between both shapes. So GW is somewhat equivalent conceptually to solving the shape matching problem. Thus, in my opinion, the authors should compare their method with established methods and baselines in the shape matching community on shape matching performance. Yet the authors fail to do so and only compare to pure OT/GW methods and naive nearest neighours. No ICP [1] or spectral ICP [2], no functional maps [2], no advanced shape matching papers either without GW (eg ULRSSM [3]) or using GW (eg the Wormhole [4,5,6]) as a loss in the pipeline. Comparison should compare the quality of the matching, in terms of PCK performance (mean and full curves) and also inference time (not training as training can be considered a long preprocessing). A lot of effort has been put in learning to solve shape matching (on full, partial, non-isometric shapes etc), so I have doubts that the proposed GW method leads to better matchings, and it is probably much slower (320+ seconds in Table 2) compared to almost instant inference (couple seconds) of feed-forward neural networks (eg based on DiffusionNet) to solve the matching. So if the proposed method were to be both less accurate and slower, it would drastically lower the usefulness of the paper as a whole. I need to see these results.

  • The submission seems to be of very limited novelty. It essentially builds on 3x Choromanski et al. works (2021, 2023, and 2026). For instance, the randomised speedup is just using Choromanski et al. 2021 features maps (l246), and the efficient compute in the deterministic case for C and C^2 come essentially from Choromanski et al. 2026. It is not clear from reading the method section what is the actual difference and what the contributions and novelties are compared to existing works. Surprisingly, this is not explained in the related works section, where only Choromanski et al. 2026 is mentioned quickly in passing. The authors should very clearly discuss exising works, especially very close ones, and very clearly position themselves with respect to them and show very precisely what is novel and what is not. As is currently written, I do not see much novelty, at least not something sufficient justifying a publication in a top conference venue.

  • I have concerns regarding the quality of the evaluation, which I believe is subpar for a top conference submission.

    • For shape correspondence:
      • The evaluation is done on just 3 shapes out of the Faust dataset only, and only 1 visualisation of a single pair is provided in the main manuscript (two others in the supplementary). It is impossible to reach any general conclusion on just 3 pairs of shapes, all from the same dataset as well! The authors should evaluate on the full dataset, and test different shape matching datasets, like Tosca, Scape, Topkids, Shrec16, Shrec19, Shrec20, Smal, pFaust, Becos... It is of particular interest to investigate non-full shapes (partial: Shrec16, pFaust, Becos) and highly non-isometrics (Shrec20) datasets as there the concept of dense groundtruth matching is by definition ill-defined, but the GW is not, and thus GW is an ideal setting and tool for these shapes.
      • Additionally, the authors use the original Faust dataset, which is not remeshed: all shapes have the same sampled vertices, which makes the shape matching problem artificially much simpler than it truly is. The authors should investigate the remeshed version, as is good practice for quite some years now in the field.
      • Regarding the computation of geodesics in this experiments, it seems that the authors live on the graph given by the mesh, which makes me think that they used Dijkstra's algorithm. However, this algorithm is known to be a poor approximation of the underlying smooth manifold goedesic distances, and it is considered good practice in the field to do Fast marching instead, which is computationally as expensive while being significantly more accurate due to first order approximation.
      • The visual results display a point cloud. Yet it seems from the text that the authors use the mesh graph (l358), and thus the mesh. As matching point clouds is a much harder problem than matching meshes, since the connecting graph is not provided, displaying results as point clouds is misleading. Instead, the authors should display the results as (coloured) meshes, as is the good practice for mesh-based methods. In addition, the authors should investigate compute the GW on the pointcloud that can be obtained from the mesh, where edges have been deleted and a proximity graph (commonly kNN) is computed and used instead. It would be worthwhile to compare the difference obtained for GW in the pointcloud setting, seeing if the method is robust to the connectivity or not. If it is, I highly recommend evaluating the GW on different remeshings (different triangles, same vertices) of the same shapes, to study the robustness to remeshing (while preserving an ok connectivity compared to potentially incaccurate pointcloud connectivity which often joins points that are far away goedesically but close in ambient space).
      • Table 2 and Figure 2 do not report runtime for some baselines (NN and OT), which is very odd. The authors change terminology for acronyms between the main text, the table, and the figure, being consistent would help and adding the wording (Ours) would make it more clear which methods are proposed by the authors.
      • Additionally some of the results there are not of high interest (three plots of constant overlapping constant curves are not interesting in Fig 2 top), and the results of the approximation variant are not impressive: even when increasing the number of projections, quality does not increase and does not converge towards the deterministic variant: the error is twice as large between them. For a speed-up that is not even half and twice the error, it is not clear if the approximation variant is of practical usefulness.
      • Authors fail to report results accurately: standard deviations are missing (Table 2, Figure 2), PCK at given % are missing yet it is common to report that score, and the full PCK curves are not provided.
      • The experimental setup for the template detection experiments is highly unclear. A major issue that the flow is broken: the experiment is described in Section 4, then Section 5 "Experiments" describest the experiments on Shape matching and its results and then results are provided for the template matching. The authors should consider moving Section 4 into the experiments section as it describes the experiment performed using the method. If the authors instead argue that this forms the core of their method, then the authors should clearly emphasise better and improve the writing and flow, along with positioning this experimental appraoch to existing works in template matching and clearly describing what is novel in Section 4 beyond using their GW estimates.
      • Only 1 scene with 1 template to find is provided in the main manuscript. This is clearly not enough in order to draw any intuition or conclusion. Many more scenes and templates seem to be investigated, but the description of this is very unclear and confusing.
      • The authors do not properly discuss limitations and failure cases. I highly recommend the authors to provide visual examples of failure cases in the main submission, not the appendix, in addition to successful results, and provide a substantial discussion of the limitations of the work in a dedicated limitations paragraph or section. There is a 5 line discussion hidden at the end of the supplementary, but that is both clearly neither enough nor at the right place.
      • The template detection experiments use RGB-D data, yet none of these images and depth maps are provided, neither in the main or supplementary material. The authors should provide them to let the reader see what the input data is.
      • Design choices are not fully explained or motivated, or lack ablations. For example, the 98%/2% split of qrayq_{ray}/bb (l325) is just dropped without justification.
  • I have a concern regarding theoretical guarantees. Note that I am aware that there are often discrepancies between theory and practice. The authors claim that the computation is exact for graph with separators of O(log(log(n)))O(log(log(n))). If this means balanced separators, this implies that the considered graphs should be extremely sparse. However, in practice for 3D shapes, shapes often have much much larger separators, eg O(n)O(\sqrt{n}) for topological spheres, like human shapes (as in FAUST). Thus my concern is that the "exact" thus never applies for 3D graphs, which are those the users are investigating in this work (the title is "Unlocking GW distances for 3D modeling").

[1] Besl & McKay, Method for registration of 3-D shapes, Sensor fusion IV, 1992

[2] Ovsjanikov, Functional maps: a flexible representation of maps between shapes, ToG, 2012

[3] Cao et al., Unsupervised learning of robust spectral shape matching, ToG, 2023

[4] Halimi et al., Unsupervised learning of dense shape correspondence, CVPR, 2019

[5] Bracha et al., On unsupervised partial shape correspondence, ACCV, 2024

[6] Bracha et al., Wormhole Loss for Partial Shape Matching, NeurIPS, 2024

Questions for authors

See comments above.

I would strongly encourage to clearly position the work with respect to the existing literature, especially the line of work of Choromanski et al., and clearly phrasing what is novel and what is novel.

I would also strongly encourage to strongly motivate why compute the GW in the proposed ways is a good idea, and to experimentally provide strong compelling arguments why it is beneficial in 3D applications like shape matching and how it overcomes (or fails) compares to existing advanced methods solving the same (or equivalent problem of the matching itself). What is really the benefit of the work?

2 comments

We sincerely thank the reviewer for the thoughtful comments, especially the suggestion to test highly non-isometric shapes and partial correspondences.

Comparisons with established shape-matching methods would complement our solver evaluation and help assess its practical value for correspondence. Our FAUST experiments use dense FGWD as the reference to examine the computational savings while preserving correspondence accuracy. At 2,000 vertices, DET-EGGroW matches its reported mean geodesic error on all three pose pairs and runs faster on each. For example, on 004→007, both achieve an error of 0.223, with runtimes of 585.0 s for DET-EGGroW and 996.5 s for dense FGWD. Moreover, the same pair illustrates APP-EGGroW's accuracy–runtime tradeoff: increasing the feature count from 64 to 1,024 reduces the error from 0.281 to 0.237, while increasing runtime from 322.7 s to 531.3 s.

We will clarify the contribution relative to the earlier graph-operator and random-feature work. The within-shape distances remain fixed, while the coupling and associated Sinkhorn kernel change across GW iterations. Section 3.1 adapts the GenusSink machinery to products involving the graph-distance matrix and its elementwise square. Section 3.2 expresses the iteration-dependent kernel in a form that admits a positive random-feature approximation. Sinkhorn scaling preserves the factorization, allowing the approximate coupling to remain in low-rank form across updates. We will distinguish these steps explicitly from the operators and feature constructions inherited from previous work.

On the separator question, numerical exactness and computational complexity require separate qualifications. DET-EGGroW reproduces the dense update when its distance operators are exact, while the runtime bound in Lemma 3.1 additionally assumes small separators. Mesh structure or bounded genus alone does not establish that assumption. We will make this distinction more prominent and clarify the conditions attached to the complexity claim.

We will also clarify the experimental inputs and presentation. The FAUST figures display sampled vertices, but the distances are computed through the full triangle-mesh graph. We will update the captions to explain that use of mesh connectivity explicitly. The reviewer’s suggestions concerning remeshed FAUST, alternative geodesic constructions, and partial or non-isometric datasets would help assess sensitivity to discretization and broaden the correspondence evaluation. We have some preliminary results here and can add it to the camera-ready version. Specifically, we tested Dense FGWD with mesh shortest paths on all low-resolution SHREC20 pairs. It outperformed ICP, functional maps and pretrained ULRSSM in mean landmark PCK at both 5% and 10%.

For template detection, Figure 3 illustrates localization in one room, while Figure 4 evaluates correspondence under controlled deformations. We will separate these settings more clearly and present the scene example as a proof of concept. The 2% surface-area term in the visibility prior gives positive reference mass to vertices missed by the initial raycast, allowing them to receive correspondence mass during optimization. This motivates including the term. We agree that sensitivity to its weight, together with the contributions of the two stages, remains an important direction for further evaluation.

I thank the authors for their response, that tries to address some of my concerns.

The authors did not update the revised manuscript in colour, making it difficult to know what has changed there. For sure though, no new visual qualitative result has been provided, so the manuscript is still stuck with 1 Faust pair and 1 scene. This on its own is grounds for clear rejection.

Overall, my concerns still remain and I strongly advise the authors to follow all my recommendations to drastically improve the quality of this manuscript in the future. In particular, the authors need to do the required experiments, and properly motivate with lots of supporting evidence the benefits of their method over the rich shape matching community, and they also need to much more clearly position their work with respect to the line of works of Choromanski et al.

I will not change my score.

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

The paper proposes EGGroW for entropic Gromov-Wasserstein distance (GWD) and fused Gromov-Wasserstein distance (FGWD) computation with graph shortest-path costs. Deterministic EGGroW (DET-EGGroW) uses GenusSink-based distance operators to accelerate the matrix operations in FGWD iterations, with exact evaluation conditional on the operator assumptions. Approximate EGGroW (APP-EGGroW) approximates the kernel matrix KTK_{T} at each iteration through positive feature maps to trade accuracy for additional speed. The paper also proposes capacity-constrained scene localization followed by template visibility and correspondence estimation. Experiments include FAUST pose correspondence, synthetic mesh correspondence, and a qualitative localization example.

Critical strengths
  1. Useful computational gains for geodesic correspondence.
    Table 2 reports the same mean geodesic error for DET-EGGroW and dense FGWD on all three FAUST pairs, with lower runtime; Figure 2 shows larger gains as the support size increases. Figure 4 likewise shows DET-EGGroW preserving the dense FGWD soft PCK curve. Exploiting graph structure can be valuable even when a generic GW solver accepts geodesic distance matrices, because forming, storing, and applying those matrices can be costly.

  2. A concrete approximate alternative.
    Eqs. (18)-(23) adapt positive-feature methods [4] to the kernel matrix KTK_{T} at each iteration. Figure 2 and Table 2 examine full APP-EGGroW runs with different values of the number of random features rr, and Figure 4 shows similar soft PCK to the plotted Gaussian-feature baseline with lower runtime at larger sizes. The paper acknowledges the approximation tradeoff rather than claiming that APP-EGGroW preserves dense-solver accuracy.

Critical weaknesses
  1. The computational guarantees are not sufficiently connected to the reported implementation.
    Section 3.1 and Table 1 correctly make exactness conditional on exact operators. However, the experimental operator backend and its applicable separator or approximation regime are not specified clearly enough to connect the timing results to those guarantees. A mesh or bounded-genus graph does not by itself establish the small-separator condition. Section 5.1 computes sampled geodesic matrices through the full graph, whereas Table 1 describes operator-based distances; it is unclear whether those matrices are only references or also used by DET-EGGroW/APP-EGGroW. Appendix B.2 states that method-specific setup and solving are timed, but does not resolve the roles and costs of shortest-path computation and operator construction. This is a scope and reproducibility concern, not evidence that the reported operators are necessarily inexact.
  2. The significance of the additional contribution is only partly established.
    The paper acknowledges its use of GenusSink, but the introductory claim that analogous efficient geodesic-GW techniques have not been developed needs qualification: [1, Appendix D.2.3, Algorithm 2] already connects fast graph operators to GW, including shortest-path operators, although its GW experiments use diffusion costs. For APP-EGGroW, useful speedups are demonstrated, but the accuracy cost can be substantial: on 004-to-003, Table 2 reports a runtime of 320.8 s and mean geodesic error of 0.240 for APP64, compared with 587.0 s and 0.166 for DET-EGGroW; Figure 4 gives roughly 30% versus over 99% soft PCK at 10% angular tolerance. Section 5.2 explicitly reports a comparison with [2], but the figure labels it Scetbon-Cuturi (Gaussian features), leaving the implemented baseline and its settings ambiguous. Finally, Figure 3 is qualitative, and Appendix B.3 describes balanced correspondence between point clouds related by deformation and rigid transformations; quantitative validation of the complete two-stage 3D template detection method remains unclear.

References

[1] Krzysztof Marcin Choromanski et al. Efficient Graph Field Integrators Meet Point Clouds. ICML, PMLR 202:5978–6004, 2023. https://proceedings.mlr.press/v202/choromanski23b.html

[2] Meyer Scetbon, Gabriel Peyré, and Marco Cuturi. Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs. ICML, PMLR 162:19347–19365, 2022. https://proceedings.mlr.press/v162/scetbon22b.html

[3] Peter Halmos, Xinhao Liu, Julian Gold, and Benjamin J. Raphael. Low-Rank Optimal Transport through Factor Relaxation with Latent Coupling. NeurIPS, 2024. https://proceedings.neurips.cc/paper_files/paper/2024/hash/cfc1924c62e72e2cb0e0feeecb963241-Abstract-Conference.html

Questions for authors
  1. Please specify the operator backend and exact or approximate regime used in each experiment. Clarify whether the geodesic matrices in Section 5.1 are only references, how shortest-path computation, operator construction, and solving enter the reported time, and how full-graph size differs from sampled support size.

  2. Please clarify how the Figure 4 Gaussian-feature baseline corresponds to [2], and report its settings alongside APP-EGGroW's number of random features rr, centering, and diagonal balancing. Identify the accuracy range in which APP-EGGroW offers a useful speed advantage. A representative comparison with a recent scalable GW/FGW alternative, such as FRLC [3], would help assess the benefit of geodesic specialization, accounting for preprocessing costs and differences in the optimized objectives.

  3. Please identify the quantitative evidence for both stages of the proposed two-stage 3D template detection method under clutter and occlusion, including visibility recovery beyond the raycast visibility reference qrayq^{\mathrm{ray}}. Also distinguish the geodesic implementation's additional contribution from the operator-GW framework in [1].

2 comments

We would like to sincerely thank the reviewer for the valuable feedback. We address the comments below.

Operator assumptions and timing:

In Sec. 5.1, nn is the number of sampled vertices used for correspondence. For example, Table 2 uses 2,000 vertices per mesh, but shortest paths can pass through unsampled vertices of the full mesh. In the point-cloud experiment in App. B.3, the shortest-path graph is constructed on the sampled points themselves. Table 1 makes DET-EGGroW’s exactness conditional on exact applications of the distance operators. The operator runtime bound in Lemma 3.1 also assumes separators of size O(log⁡log⁡n)O(\log\log n). Furthermore, we agree that bounded genus alone does not establish this condition. DET-EGGroW and Dense FGWD give the same reported correspondence error on all three FAUST pairs in Table 2 (though that does not verify the runtime bound). As stated in App. B.2, we timed method-specific setup and solving, excluding shared calibration, input loading, and post-solve scoring.

Baseline and accuracy–runtime tradeoff:

We agree with the reviewer about the ambiguity in Fig. 4. The legend identifies the baseline as “Scetbon-Cuturi (Gaussian features),” while Sec. 5.2 cites the low-rank coupling method of Scetbon et al. [2] We agree that the relationship between the Gaussian-feature baseline in Fig. 4 and the method cited in Sec. 5.2 needs clarification. Sec. 3.2 describes centering and diagonal balancing for APP-EGGroW, but we did not report the feature count or the settings for each curve in Fig. 4. The r=512r=512 setting in App. B.1 belongs to a separate FAUST ablation. A direct comparison with [2] or FRLC [3], stating the objective for each method and including preprocessing time, would address this gap. Table 2 gives a concrete example of the tradeoff. We will make sure to add all these relevant changes and ablations in the camera-ready version. Moreover, on FAUST 004→003, APP-EGGroW with r=64r=64 takes 320.8 s with a mean geodesic error of 0.240. Increasing the feature count to 1,024 reduces the error to 0.230 and raises the runtime to 535.1 s. DET-EGGroW takes 587.0 s with an error of 0.166. On this pair, APP-EGGroW offers a shorter runtime given an error of 0.230–0.240.

Template detection and relation to prior work:

Fig. 3 shows the scene density recovered in Stage I for the Octopus example. Fig. 4 measures correspondence between point sets related by a smooth nonrigid deformation followed by a fixed rotation and translation. It does not measure localization under clutter or occlusion. Additionally, in Stage II, we fix the scene distribution from Stage I and learn a template marginal qq. Eq. (28) allows qq to depart from the raycast estimate qrayq_{\rm ray}, but we do not report whether that improves visibility recovery. A direct test would score Stage I against the scene object mask and compare qq and qrayq_{\rm ray} against the same visibility ground truth at the same pose. We also agree that the introduction should give [1] clearer credit. Appendix D.2.3 of [1] already gives an operator formulation of Gromov–Wasserstein that admits shortest-path operators, although its experiments use diffusion costs. Our contribution is to adapt GenusSink to apply the geodesic cost matrix CC and its entrywise square C∘2C^{\circ 2} in the entropic FGWD update. APP-EGGroW then uses positive random features to approximate the kernel as it changes from one update to the next. We will make all relevant clarifications in the camera-ready version.

I thank the authors for the detailed response and for being candid about the open points. Several of my concerns have been clarified, and I appreciate the commitment to revise the paper. However, the main concerns are not yet resolved in the current manuscript.

My central question was whether the reported speed comes from the separator-based operators analyzed in Lemma 3.1. The meshes in the experiments have bounded genus, but this alone does not give the small separators the lemma assumes. Without the operator backend, the separator sizes, and a breakdown of the timing, I cannot tell how much of the theoretical claim applies to the experiments. On the empirical side, the baseline in Fig. 4 is still not specified, and a comparison with scalable GW methods such as low-rank GW would help show where the approximate variant is useful.

Since these issues remain in the current version, I keep my Rating at 2.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.