# Computing the Gromov-Wasserstein Distance between Two Surface Meshes Using Optimal Transport
## 5 Computational Experiments
### Shape Correspondence: Synthetic Data from SHREC19
In contrast, Algorithm 2 is based on an annealing plan \begin{table}
\begin{tabular}{l c c c c c} \hline \hline
**Method a** & **Test-Set 0** & **Test-Set 1** & **Test-Set 2** & **Test-Set 3** & **All Test Sets** \\ \hline RPTS [40] & 0.920 b  & 0.926 & 0.824 & 0.929 & 0.899 \\ NRP [41] & 0.878 & 0.899 & 0.801 & 0.858 & 0.862 \\ WRAP & 0.853 & 0.920 & 0.772 & 0.870 & 0.856 \\ KM [42] & 0.760 & 0.865 & 0.757 & 0.799 & 0.804 \\ FreeGW d  & 0.706 & 0.879 & 0.550 & 0.320 & 0.588 \\ Algo1 e  & 0.666 & 0.846 & 0.490 & 0.338 & 0.548 \\ GISC [43] & 0.565 & 0.659 & 0.674 & NA c  & NA c  \\ \hline \hline \end{tabular}  
* Rows are in descending order of score over all test sets. b Area under the curve (AUC) for the cumulative distribution functions of the normalized geodesic errors in the correspondences. Results for the first five methods are derived from Ref. [39]. c Not Available in Ref. [39]. d Our results based on Algorithm 2 that consider an annealing procedure in the regularization parameters. e Our results based on Algorithm 1.  
\end{table} 
Table 1: Quality of different methods for computing correspondence between 3D shapes. Figure 3: Examples of shapes in each group of the SHREC19 benchmark [39]. with respect to the parameter \(\beta\), such that when \(\beta\) is large, the outputs of the program are guaranteed to match the actual GW results. In each experiment, a pair of shapes \(i\) and \(j\) is represented with their complete sets of vertices, \(S_{i}\) and \(S_{j}\), and the geodesic distance matrices between those vertices, \(d_{i}\) and \(d_{j}\). The masses of the vertices are set uniform. The GW problem is solved using the two algorithms mentioned above. Both derive a transport plan \(G\). For each vertex \(x\) on \(i\), its correspondence \(y\) on \(j\) is set to the index of the maximum value on the row corresponding to \(x\) in \(G\). Figure 4 shows the corresponding cumulative geodesic errors for the two algorithms for the four test sets in SHREC19. We observed that Algorithm 2 as implemented in FreeGW performs better for shape correspondence than the simpler Algorithm 1, on all test sets, and significantly better from shapes with isometric deformations (test set 1). The SHREC19 dataset was originally used as a benchmark for a competition on comparing 3D shape registration that was part of the Workshop on 3D Object Retrieval that was held in Genova, Italy in may 2019. Several groups entered in this competition; results were published in Ref. [39]. Here we compare results based on the GW framework, as presented above, with results from the five top methods that were part of this competition. We briefly describe those five methods below. In the first method, dubbed RTPS, the correspondence map between the template shape and the target shape is computed iteratively. Each iteration is built from two successive steps. In the first step, the vertices estimated to be in correspondence between the template and target shapes are derived from the registration result obtained from the previous iteration. These computed correspondences are used to derive a correspondence mapping. In the second step, the mapping is updated by using the closest points between  
Figure 4: Cumulative distribution functions for the geodesic errors for the correspondence computed with FreeGW (red), which implements an annealing procedure in the regularization parameter \(\beta\), and computed with Algorithm 1 (blue), that only considers one regularization value (see text for details). Results are shown for all four test sets in SHREC19, that consider articulated deformations (test set 0), isometric deformations (test set 1), non-isometric deformations (test set 2), and topological or geometric deformations (test set 3). template and target shapes identified by the mapping to find additional points that are in correspondence [40]. The second method, NRPA, is also based on registration.