(cvpr) Package cvpr Warning: Package ‘hyperref’ is not loaded, but highly
recommended for camera-ready version

# G-MSM: Unsupervised Multi-Shape Matching with Graph-based Affinity Priors

Marvin Eisenberger, Aysim Toker, Laura Leal-Taixé†, Daniel Cremers
Technical University of Munich

###### Abstract

We present G-MSM (Graph-based Multi-Shape Matching), a novel unsupervised
learning approach for non-rigid shape correspondence. Rather than treating a
collection of input poses as an unordered set of samples, we explicitly model
the underlying shape data manifold. To this end, we propose an adaptive multi-
shape matching architecture that constructs an affinity graph on a given set
of training shapes in a self-supervised manner. The key idea is to combine
putative, pairwise correspondences by propagating maps along shortest paths in
the underlying shape graph. During training, we enforce cycle-consistency
between such optimal paths and the pairwise matches which enables our model to
learn topology-aware shape priors. We explore different classes of shape
graphs and recover specific settings, like template-based matching (star
graph) or learnable ranking/sorting (TSP graph), as special cases in our
framework. Finally, we demonstrate state-of-the-art performance on several
recent shape correspondence benchmarks, including real-world 3D scan meshes
with topological noise and challenging inter-class pairs.

††† Currently at NVIDIA

i Shape graph $\mathcal{G}$

ii Affinity edge weights

\begin{overpic}[width=433.62pt]{figures/teaser/teaser_002.png}
\put(15.0,28.0){Source} \put(41.0,26.0){$\mathbf{\Pi}^{(1,2)}$}
\put(74.0,26.0){$\mathbf{\Pi}^{(1,3)}\circ\mathbf{\Pi}^{(3,2)}$} \end{overpic}
iii Putative correspondences $\mathbf{\Pi}^{(1,2)}$ vs multi-matching
$\mathbf{\Pi}^{(1,3)}\circ\mathbf{\Pi}^{(3,2)}$

Figure 1: For a given collection of 3D meshes $\\{\mathcal{X}^{(i)}|1\leq
i\leq N\\}$, (i) our method constructs, in a fully unsupervised manner, a
shape graph $\mathcal{G}$ which approximates the underlying shape data
manifold. (ii) Its edge weights (affinity scores) are derived from a putative
pairwise correspondence loss signal. (iii) During training, we enforce cycle-
consistency by propagating maps along shortest paths in the graph
$\mathcal{G}$. As shown for the sample pair above $(\mathcal{X}^{(1)}$,
$\mathcal{X}^{(2)})$, the resulting multi-matching
$\mathbf{\Pi}^{(1,3)}\circ\mathbf{\Pi}^{(3,2)}$ is significantly more accurate
than the pairwise map $\mathbf{\Pi}^{(1,2)}$.

##  1 Introduction

Shape matching of non-rigid object categories is a central problem in 3D
computer vision and graphics that has been studied extensively over the last
few years. Especially in recent times, there is a growing demand for such
algorithms as 3D reconstruction techniques and affordable scanning devices
become increasingly powerful and broadly available. Classical shape
correspondence approaches devise axiomatic algorithms that make specific
assumptions about the resulting maps, such as near-isometry, area
preservation, approximate rigidity, bounded distortion, or commutativity with
the intrinsic Laplacian. In contrast, real-world scan meshes are often subject
to various types of noise, including topological changes [16, 32], partial
views [2], general non-isometric deformations [17, 64], objects in clutter
[12], and varying data representations [56]. In this work, we address several
of the aforementioned challenges and demonstrate that our proposed method
achieves improved stability for a number of 3D scan mesh datasets.

The majority of existing deep learning methods for shape matching [2, 15, 20,
19, 23, 38, 50, 55] treat a given set of meshes as an unstructured collection
of poses. During training, random pairs of shapes are sampled for which a
neural network is queried and a pairwise matching loss is minimized. While
this approach is straightforward, it often fails to recognize commonalities
and context-dependent patterns which only emerge from analyzing the shape
collection as a whole. _Not all samples of a shape collection are created
equal._ In most cases, some pairs of poses are much closer than others. Maps
between similar geometries are inherently correlated and convey relevant clues
to one another. This is particularly relevant for challenging real-world
scenarios, where such redundancies can help disambiguate noisy geometries,
non-isometric deformations, and topological changes. The most common approach
of existing multi-matching methods is to learn a canonical embedding per pose,
either in the spatial [10] or Laplace-Beltrami frequency domain [27, 25]. This
incentivizes the resulting matches to be consistent under concatenation.
However, such approaches are in practice still trained in a fully pairwise
manner for ease of training. Furthermore, relying on canonical embeddings can
lead to limited generalization for unseen test poses. Concrete approaches
often assume a specific mesh resolution and nearly-isometric poses [10], or
require an additional fine-tuning optimization at test time [25, Sec. 5].

Rather than interpreting a given training set as a random, unstructured
collection of shapes, our approach explicitly models the underlying shape
manifold. To this end, we define an affinity graph $\mathcal{G}$ on the set of
input shapes whose edge weights (i.e. affinity scores) are informed by the
outputs of a pairwise matching module. We then devise a novel adaptive multi-
matching architecture that propagates matches along shortest paths in the
underlying shape graph $\mathcal{G}$. The resulting maps are topology-aware,
i.e., informed by geometries from the whole shape collection. An example is
shown in Figure 1, where the multi-matching
$\mathbf{\Pi}^{(1,3)}\circ\mathbf{\Pi}^{(3,2)}$ obtained by our approach is
significantly more accurate than the naive, pairwise map
$\mathbf{\Pi}^{(1,2)}$. During training, we promote cycle-consistency of
shortest paths in the shape graph. In summary, our contributions are as
follows:

  1. 1.

Introduce the notion of an edge-weighted, undirected shape graph $\mathcal{G}$
to approximate the underlying data manifold for an unordered collection of 3D
meshes.

  2. 2.

Propose a novel, adaptive multi-shape matching approach that enforces cycle-
consistency for optimal paths in the shape graph $\mathcal{G}$ in a self-
supervised manner.

  3. 3.

Demonstrate state-of-the-art performance for a range of challenging non-rigid
matching tasks, including non-isometric matching due to topological noise [16,
32] and inter-class pairs [17, 64].

##  2 Related work

##### Axiomatic correspondence methods

Shape matching is an extensively studied topic with a variety of different
approaches and methodologies. We summarize references relevant to our approach
here and refer to recent surveys [53, 59] for a more complete picture.
Classical methods for non-rigid matching often devise optimization-based
approaches that minimize some type of distortion metric [7, 61, 48, 63]. A
common prerequisite of many such methods is the extraction of hand-crafted
local descriptors that are, in approximation, preserved under non-rigid shape
deformations. Common definitions include histogram-based statistics [58] or
fully intrinsic features based on the eigenfunctions of the Laplace-Beltrami
operator [3, 52, 57]. Over the last few years, functional maps [43] have
become a central paradigm in shape matching. The core idea is to reframe the
pairwise matching task from functions (points to points) to functionals
(functions to functions). There are several extensions of the original
framework to allow for partial matching [34, 35, 49], orientation preservation
[47], iterative map upsampling [18, 41] and conformal maps [14]. Our approach
utilizes functional maps as a fundamental building block within the
differentiable matching layer.

##### Learning-based methods

More recently, several approaches emerged that aim at extending the power of
deep feature learning to deformable 3D shapes. Many such methods fall under
the umbrella term ‘geometric deep learning’ [9], with analogous applications
on different classes of non-Euclidean data like graphs or general manifold
data. One class of approaches are charting-based methods [6, 39, 42, 45, 51]
which imitate convolutions in Euclidean space with parameterized, intrinsic
patch operators. Likewise, [56] proposed a learnable feature refinement module
based on intrinsic heat diffusion. We employ the latter as the backbone of our
pipeline.

The pioneering work of [33] proposes a differentiable matching layer based on
functional maps [43], in combination with a deep feature extractor with
several consecutive ResNet layers [24]. Numerous extensions of this paradigm
were proposed over the last few years to allow for unsupervised loss functions
[23, 50], learnable basis functions [38], point cloud feature extractors [15,
25, 55] or partial data [2]. Similarly, DeepShells [20] learns functional maps
in an end-to-end trainable, hierarchical multi-scale pipeline. We adapt parts
of its differentiable matching layer in our network. Other approaches [4, 22,
37] learn correspondences for a specific class of deformable objects by
including additional domain knowledge, like a deformable human model [36].
Finally, [19] jointly learns to predict correspondences and a smooth
interpolation between pairs of shapes.

##### Multi-shape matching

Classical axiomatic multi-shape matching approaches devise optimization-based
pipelines that enforce cycle-consistent maps. Specific solutions include
semidefinite programming [26], convex relaxations of the corresponding
quadratic assignment problem [29], graph cuts [54], as well as evolutionary
game theory [11]. Such optimization-based approaches are computationally
costly and therefore limited to matching sparse landmarks. Furthermore, there
are a number of optimization frameworks that compute synchronized, cycle-
consistent functional maps [21, 27, 28]. Notably, such approaches are often
limited to nearly-isometric poses [21, 28] or require high-quality
initializations [27]. More recent learning-based approaches promote cycle-
consistency by predicting a canonical embedding for each observed pose [10,
25]. However, obtaining stable embeddings is often difficult when generalizing
to unseen test poses. Moreover, such approaches assume a specific mesh
resolution and nearly-isometric poses [10] or require an additional fine-
tuning optimization at test time to obtain canonical embeddings [25, Sec. 5].

##  3 Method

###  3.1 Problem formulation

In the following, we consider a collection of 3D shapes
$\mathcal{S}=\bigl{\\{}\mathcal{X}^{(1)},\dots,\mathcal{X}^{(N)}\bigr{\\}}$
from non-rigidly deformable shape categories. Each such shape
$\mathcal{X}^{(i)}$ is a discretized approximation of a 2D Riemannian
manifold, embedded in $\mathbb{R}^{3}$. Specifically, we define
$\mathcal{X}^{(i)}=\bigl{(}\mathbf{V}^{(i)},\mathbf{T}^{(i)}\bigr{)}$, where
$\mathbf{V}^{(i)}\in\mathbb{R}^{m\times 3}$ and
$\mathbf{T}^{(i)}\subset\mathbf{V}^{(i)}\times\mathbf{V}^{(i)}\times\mathbf{V}^{(i)}$
are sets of vertices and triangular faces, respectively. The goal is then to
construct an algorithm that computes dense correspondence mappings
$\mathbf{\Pi}^{(i,j)}$ between any two surfaces $\mathcal{X}^{(i)}$ and
$\mathcal{X}^{(j)}$ from the shape collection $\mathcal{S}$. Specifically,
such correspondences are represented by sparse assignment matrices
$\mathbf{\Pi}^{(i,j)}\in\\{0,1\\}^{m\times n}$, where
${\mathbf{\Pi}^{(i,j)}}\mathbf{1}_{n}=\mathbf{1}_{m}$ and
$\mathbf{\Pi}^{(i,j)}_{i^{\prime},j^{\prime}}=1$ indicates a match between the
$i^{\prime}$-th vertex of $\mathcal{X}^{(i)}$ and the $j^{\prime}$-th vertex
of $\mathcal{X}^{(j)}$.

##### Scope

Our method is unsupervised and thereby requires no additional inputs, like
landmark annotations or ground-truth correspondences, beyond the raw input
geometries $\mathcal{X}^{(i)}$. Following similar approaches in this line of
work [4, 19, 38, 55], we assume that the shapes
$\mathcal{X}^{(1)},\dots,\mathcal{X}^{(N)}$ have an approximately canonical
orientation. In the literature, this setting is commonly referred to as
‘weakly supervised’, see [55] and later [19]. Existing approaches often make
additional assumptions about the input data $\mathcal{S}$, focusing on nearly-
isometric correspondences [33, 50], maps with bounded distortion [19, 20] or
partial views of the same non-rigid object [2, 49]. Others specialize in
distinct classes of shapes like deformable human bodies [4, 22, 37]. In
contrast, we demonstrate in our experiments that our proposed multi-matching
approach excels at a broad range of challenging settings, including non-
isometric pairs, poses with topological noise from self-intersections, and
inter-class matching.

Figure 2: Pipeline overview. For a collection of shapes
$\mathcal{S}=\bigl{\\{}\mathcal{X}^{(1)},\dots,\mathcal{X}^{(N)}\bigr{\\}}$,
I. feature embeddings are extracted with DiffusionNet [56] and II. pairwise
correspondences $\mathbf{\Pi}^{(i,j)}$ are predicted via an iterative,
differentiable matching layer [20]. III. The pairwise matches are utilized to
construct a shape graph $\mathcal{G}=\bigl{(}\mathcal{S},w\bigr{)}$ with
affinity edge weights
$w\bigl{(}\mathcal{X}^{(i)},\mathcal{X}^{(j)}\bigr{)}\geq 0$. During training,
we minimize the pairwise matching loss $\ell_{\mathrm{match}}^{(i,j)}$, as
well as the cycle consistency loss $\ell_{\mathrm{cyc}}^{(i,j)}$ between the
pairwise registrations $\mathbf{V}^{(i,j)}$ and multi-matches
$\mathbf{\Pi}^{(i,j)}_{\mathrm{mult}}$.

###  3.2 Network architecture

We now define the neural network architecture that forms the basis of our
proposed approach. It consists of three separate components I-III, see also
Figure 2 for an overview. The first two modules are standard components found
in most learning-based shape matching approaches [2, 15, 20, 19, 23, 38, 50,
55], namely a learnable feature backbone I and a differentiable, pairwise
matching layer II. We briefly outline these here and provide additional
details in Section A.2. The multi-matching architecture III is introduced in
Section 3.3.

##### Feature extractor

The first component I of our model is a standard, learnable feature extraction
backbone for representation learning, defined as

$\Phi_{\mathrm{feat}}:\mathcal{X}^{(i)}~{}\mapsto~{}\mathbf{F}^{(i)}\in\mathbb{R}^{m\times
l}.$ (1)

For a given input shape
$\mathcal{X}^{(i)}=\bigl{(}\mathbf{V}^{(i)},\mathbf{T}^{(i)}\bigr{)}$, the
mapping $\Phi_{\mathrm{feat}}$ produces an $l$-dimensional feature embedding
$\mathbf{F}^{(i)}$ per vertex $\mathbf{V}^{(i)}\in\mathbb{R}^{m\times 3}$.
While other choices are possible, we base $\Phi_{\mathrm{feat}}$ on the off-
the-shelf feature backbone DiffusionNet [56]. This network refines features
via intrinsic heat-diffusion operators. Such operators are agnostic to the
input discretization, thereby extremely robust to varying mesh resolutions and
sampling densities. At the same time, it is computationally lightweight. For
more details on the choice of backbone, see Section A.2.

##### Pairwise matching

The second component II of our network is a differentiable, multi-scale
matching scheme based on the recent pairwise shape matching method DeepShells
[20]. The basis of this approach is the energy function

$E_{\mathrm{match}}\bigl{(}\mathbf{F},\mathbf{G};\mathbf{\tilde{\Pi}}\bigr{)}:=\sum_{i^{\prime}=1}^{m}\sum_{j^{\prime}=1}^{n}\mathbf{\tilde{\Pi}}_{i^{\prime},j^{\prime}}\bigl{\|}\mathbf{F}_{i^{\prime}}-\mathbf{G}_{j^{\prime}}\bigr{\|}_{2}^{2}$
(2)

which has its roots in the theory of optimal transport. For a given transport
plan $\mathbf{\tilde{\Pi}}\in[0,1]^{m\times n}$, the energy
$E_{\mathrm{match}}$ specifies the distance between the discrete measures
associated with two arbitrary $l$-dimensional feature embeddings
$\mathbf{F}=\bigl{(}\mathbf{F}_{1},\dots,\mathbf{F}_{m}\bigr{)}\in\mathbb{R}^{m\times
l}$ and
$\mathbf{G}=\bigl{(}\mathbf{G}_{1},\dots,\mathbf{G}_{n}\bigr{)}\in\mathbb{R}^{n\times
l}$. Taking the minimum over all possible transport plans
$\arg\min_{\mathbf{\tilde{\Pi}}}E_{\mathrm{match}}\bigl{(}\mathbf{F},\mathbf{G};\mathbf{\tilde{\Pi}}\bigr{)}$
results in the Kantorovich formulation of optimal transport [44, 62].
Following the approach described in [20], we obtain a multi-scale shape
matching scheme that minimizes Equation 2 in an iterative optimization. For a
given pair of shapes $\mathcal{X}^{(i)}$ and $\mathcal{X}^{(j)}$, this scheme
defines a mapping

$\Phi_{\mathrm{match}}:\bigl{(}\mathbf{F}^{(i)},\mathbf{F}^{(j)}\bigl{)}~{}\mapsto~{}\bigl{(}\mathbf{\Pi}^{(i,j)},\mathbf{V}^{(i,j)},\ell_{\mathrm{match}}^{(i,j)}\bigr{)}.$
(3)

We provide further details on the exact update steps of the optimization
scheme $\Phi_{\mathrm{match}}$ in Section A.2. From a high-level perspective,
$\Phi_{\mathrm{match}}$ is defined as a deterministic, differentiable function
that takes local feature encodings $\mathbf{F}^{(i)}\in\mathbb{R}^{m\times l}$
and $\mathbf{F}^{(j)}\in\mathbb{R}^{n\times l}$ as input and predicts a set of
correspondences $\mathbf{\Pi}^{(i,j)}\in\\{0,1\\}^{m\times n}$. Additionally,
$\Phi_{\mathrm{match}}$ outputs a deformed embedding
$\mathbf{V}^{(i,j)}\in\mathbb{R}^{m\times 3}$ of the vertices of
$\mathcal{X}^{(i)}$. These coordinates specify a registered version of the
first input shape $\mathcal{X}^{(i)}$ that closely aligns with the pose of the
second input shape $\mathcal{X}^{(j)}$. The third output
$\ell_{\mathrm{match}}^{(i,j)}>0$ is a training loss signal.

###  3.3 Graph-based multi-shape matching

##### Shape graph

We now provide details on our multi-shape matching architecture III. To this
end, we start by defining an affinity graph

$\mathcal{G}:=(\mathcal{S},w),~{}~{}~{}\text{with}~{}~{}~{}w:\mathcal{S}\times\mathcal{S}\to[0,\infty]$
(4)

on the set of training shapes
$\mathcal{S}=\bigl{\\{}\mathcal{X}^{(1)},\dots,\mathcal{X}^{(N)}\bigr{\\}}$,
see III in Figure 2 for a visualization. W.l.o.g., we construct $\mathcal{G}$
as a complete graph (i.e. undirected, fully connected), where a missing edge
between $\mathcal{X}^{(i)}$ and $\mathcal{X}^{(j)}$ can be specified
equivalently by setting the corresponding edge weight to
$w(\mathcal{X}^{(i)},\mathcal{X}^{(j)})=\infty$.

We define the pairwise edge weights
$w(\mathcal{X}^{(i)},\mathcal{X}^{(j)})\in[0,\infty]$ such that they represent
affinity scores between pairs of shapes $\mathcal{X}^{(i)}$ and
$\mathcal{X}^{(j)}$. By convention, small values
$w(\mathcal{X}^{(i)},\mathcal{X}^{(j)})\approx 0$ reflect that
$\mathcal{X}^{(i)}$ and $\mathcal{X}^{(j)}$ have a comparably similar
geometric structure. Since our method is fully unsupervised, we have no a
priori knowledge of such affinities and thereby have to infer them directly
from the geometries $\mathcal{X}^{(i)}$ and $\mathcal{X}^{(j)}$. To this
effect, we propose a simple heuristic for a given pair of shapes
$\mathcal{X}^{(i)}=\bigl{(}\mathbf{V}^{(i)},\mathbf{T}^{(i)}\bigr{)}$ and
$\mathcal{X}^{(j)}=\bigl{(}\mathbf{V}^{(j)},\mathbf{T}^{(j)}\bigr{)}$ and
define the (symmetric) affinity score $w$ as

$w\bigl{(}\mathcal{X}^{(i)},\mathcal{X}^{(j)}\bigr{)}:=\min\biggl{\\{}E_{\mathrm{match}}\bigl{(}\mathbf{V}^{(i,j)},\mathbf{V}^{(j)};\mathbf{\Pi}^{(i,j)}\bigr{)},\\\
E_{\mathrm{match}}\bigl{(}\mathbf{V}^{(j,i)},\mathbf{V}^{(i)};\mathbf{\Pi}^{(j,i)}\bigr{)}\biggr{\\}}.$
(5)

In this context, $E_{\mathrm{match}}$ is the (self-supervised) matching energy
defined in Equation 2, while $\mathbf{\Pi}^{(i,j)}$ and $\mathbf{V}^{(i,j)}$
are the putative correspondences and registrations produced by Equation 3,
respectively. The intuition behind this choice of edge weights $w$ is that a
small matching energy $E_{\mathrm{match}}$ implies a high correspondence
accuracy, which is in turn indicative of a high geometric similarity between
the input poses $\mathcal{X}^{(i)}$ and $\mathcal{X}^{(j)}$.

##### Multi-matching

Since we define the edge weights $w$ according to the self-supervised matching
score $E_{\mathrm{match}}$, small weights
$w(\mathcal{X}^{(i)},\mathcal{X}^{(j)})$ generally correlate with a high
correspondence accuracy of $\mathbf{\Pi}^{(i,j)}$. Based on this assumption,
we obtain multi-shape matches from the putative correspondences
$\mathbf{\Pi}^{(i,j)}$ via the following expression

$\bigl{(}i,s_{1},\dots,s_{M-1},j\bigr{)}:=\mathrm{Dijkstra}\bigl{(}\mathcal{X}^{(i)},\mathcal{X}^{(j)};\mathcal{G}\bigr{)}$
(6a)
$\mathbf{\Pi}^{(i,j)}_{\mathrm{mult}}:=\mathbf{\Pi}^{(i,s_{1})}\circ\mathbf{\Pi}^{(s_{1},s_{2})}\circ\dots\circ\mathbf{\Pi}^{(s_{M-1},j)}.$
(6b)

Rather than matching a pair of shapes $\mathcal{X}^{(i)}$ and
$\mathcal{X}^{(j)}$ directly, the multi-shape correspondence maps are passed
along shortest paths
$\mathcal{X}^{(i)},\mathcal{X}^{(s_{1})},\dots,\mathcal{X}^{(s_{M-1})},\mathcal{X}^{(j)}$
in the graph $\mathcal{G}$. The approach thereby favors edges with a close
affinity, i.e., a small pairwise matching cost
$w\bigl{(}\mathcal{X}^{(s_{k})},\mathcal{X}^{(s_{k+1})}\bigr{)}$. In our
experiments, we demonstrate that this simple heuristic yields significant
empirical improvements for a broad range of non-rigid matching tasks.

In practice, we utilize the multi-matching from Equation 6 for two distinct
use-cases: For once, we can directly query the improved maps
$\mathbf{\Pi}^{(i,j)}_{\mathrm{mult}}$ at test time. Additionally, we promote
cycle-consistency during training via the following loss term

$\ell_{\mathrm{cyc}}^{(i,j)}:=E_{\mathrm{match}}\bigl{(}\mathbf{V}^{(i,j)},\mathbf{V}^{(j)};\mathbf{\Pi}^{(i,j)}_{\mathrm{mult}}\bigr{)}.$
(7)

This loss $\ell_{\mathrm{cyc}}^{(i,j)}$ imposes a soft penalty on
inconsistencies between the registration $\mathbf{V}^{(i,j)}$ produced by the
pairwise matching module $\Phi_{\mathrm{match}}$, and the multi-shape
correspondences $\mathbf{\Pi}^{(i,j)}_{\mathrm{mult}}$ from Equation 6. As
before, $E_{\mathrm{match}}$ is the matching energy defined in Equation 2.

###  3.4 Training protocol

The overall loss function that we minimize during training consists of two
individual components

$\ell:=\mathbb{E}_{\mathcal{X}^{(i)},\mathcal{X}^{(j)}\sim\mathcal{S}}\biggl{[}\ell_{\mathrm{match}}^{(i,j)}+\lambda_{\mathrm{cyc}}\ell_{\mathrm{cyc}}^{(i,j)}\biggr{]}.$
(8)

Our complete pipeline is depicted in Figure 2. The whole network is trained
end-to-end. In each training iteration, the backbone I and pairwise matching
module II are queried in sequence to produce a pairwise matching for a pair of
shapes $\mathcal{X}^{(i)}$ and $\mathcal{X}^{(j)}$. The shape graph module III
then produces the cycle-consistency loss $\ell_{\mathrm{cyc}}^{(i,j)}$. The
shape graph $\mathcal{G}$ is updated regularly after a fixed number of epochs,
taking into account the pairwise matches $\mathbf{\Pi}^{(i,j)}$ for all
$i,j=1,\dots,N$. For more details on the training schedule and choices of
hyperparameters, see Section A.1.

##  4 Experiments

We provide various benchmark evaluations for non-rigid shape matching. We
consider classical nearly-isometric datasets in Section 4.1, as well as more
specialized benchmarks for matching with topological changes in Section 4.2
and inter-class pairs in Section 4.3. In Section 4.4, we compare different
types of shape graph topologies. In Section 4.5, we provide an ablation study
of our model, assessing the significance of individual network components.

##### Baselines

We compare G-MSM to existing deep learning approaches for unsupervised,
deformable 3D shape correspondence. To this end, we consider both standard
pairwise matching [23, 50, 55, 56, 20, 19] and multi-matching approaches [10,
25]. Since there are, to date, only very few learning-based multi-matching
approaches, we additionally include Consistent ZoomOut [27] as a recent
axiomatic multi-matching approach.

##### Evaluation

For each experimental setting, we report the mean geodesic correspondence
error over all pairs of a given test set category. All evaluations are
performed in accordance with the standard Princeton benchmark protocol [30].

Method | FAUST | SCAPE |  F on S |  S on F | SUR | SH’19
---|---|---|---|---|---|---
UFM [23] |  05.7 | 10.0 | 12.0 |  09.3 |  09.2 | 15.5
SURFM [50] |  07.4 |  06.1 | 19.0 | 23.0 | 38.9 | 37.7
WFM [55] |  01.9 |  04.9 |  08.0 |  04.3 | 38.5 | 15.0
DiffNet [56] |  01.9 |  02.6 |  02.7 |  01.9 |  08.8 | 11.0
DS [20] |  01.7 |  02.5 |  05.4 |  02.7 |  02.7 | 12.1
NM [19] |  01.5 |  04.0 |  06.7 |  02.0 |  09.7 |  02.8
1-7 CZO [27] |  02.2 |  02.5 |  0– |  0– |  02.2 |  06.3
UDM [10] |  01.5 |  02.0 |  03.2 |  03.2 |  03.1 | 22.8
SyNoRiM [25] |  07.9 |  09.5 | 21.9 | 24.6 | 12.7 |  07.5
Ours w/o III |  01.7 |  03.3 |  04.2 |  01.7 |  08.1 |  06.2
Ours |  01.5 |  01.8 |  02.1 |  01.5 |  02.1 |  02.7

Table 1: Nearly isometric matching. A quantitative comparison on four nearly-
isometric human shape benchmarks, FAUST [5], SCAPE [1], SURREAL [60] and
SHREC’19 [40]. Following prior work [15, 55, 56], we additionally show
generalization results when training on FAUST and testing on SCAPE (F on S),
and vice versa. We consider both standard, pairwise baselines [23, 50, 55, 56,
20, 19] and multi-matching approaches [10, 27, 25].

|  | Method | SH’Iso | KIDS
---|---|---|---|---
|  | UFM [23] | 13.4 | 38.5
|  | SURFM [50] | 45.6 | 48.6
|  | WFM [55] | 38.0 | 47.9
|  | DiffNet [56] | 26.5 | 35.7
|  | DS [20] |  06.3 | 13.7
|  | NM [19] |  07.7 | 13.8
1-5 |  | CZO [27] |  07.6 | 39.3
|  | UDM [10] | 23.6 | 18.2
|  | SyNoRiM [25] |  06.2 | 13.8
|  | Ours w/o III |  06.3 | 12.0
|  | Ours |  05.2 |  07.9

Figure 3: Matching with topological noise. A summary of our quantitative
comparisons on the topology benchmarks SHREC’Isometry [16] and TOPKIDS [32].
For both benchmarks, we show the cumulative error curves of our approach (red)
and all considered baselines. Additionally, we provide the mean geodesic
errors, averaged over all pairs of shapes, respectively (table, right).
\begin{overpic}[width=390.25534pt]{figures/qual_comparison/hand_012_018_005.png}
\put(6.0,26.0){Target}
\put(24.0,25.0){UFM~{}\cite[cite]{[\@@bibref{}{halimi2019unsupervised}{}{}]}}
\put(36.0,25.0){CZO~{}\cite[cite]{[\@@bibref{}{huang2020consistent}{}{}]}}
\put(49.5,25.0){DS~{}\cite[cite]{[\@@bibref{}{eisenberger2020deep}{}{}]}}
\put(62.0,25.0){NM~{}\cite[cite]{[\@@bibref{}{eisenberger2021neuromorph}{}{}]}}
\put(72.0,25.0){SyNoRiM~{}\cite[cite]{[\@@bibref{}{huang2022multiway}{}{}]}}
\put(88.0,25.0){Ours} \end{overpic} Figure 4: Qualitative baseline comparison.
We consider a pair of real 3D scan meshes from SHREC’Iso [16], corresponding
to the quantitative experiments shown in Figure 3. The two geometries are
subject to topological merging due to self-contact of different fingers and
parts of the hand. Correspondences are shown via a colormap for our method, as
well as several baseline approaches. For this example, the best results are
achieved by [20], [25] and our method. However, for both [20] and [25], the
front part of the index and middle fingers are erroneous (tip of index finger
should be bright green). See our supplementary material for additional
qualitative examples.

###  4.1 Nearly isometric matching

##### Datasets

We evaluate our method on four classical, nearly-isometric datasets. FAUST [5]
contains 10 humans in 10 different poses each and SCAPE [1] contains 71
diverse poses of the same individual. We follow the standard benchmark
protocol from existing work [15, 55, 56]. Specifically, we consider the more
challenging remeshed geometries from [47] to avoid overfitting to a particular
triangulation. SURREAL [60] consists of synthetic SMPL [36] meshes fit to raw
3D motion capture data. The last benchmark, which is the most challenging
among the four, is SHREC’19 Connectivity [40]. It contains human shapes in
different poses with significantly varying sampling density and quality, as
well as a small number of non-isometric poses.

##### Discussion

The results on these four benchmarks are summarized in Table 1. Our method
obtains state-of-the-art performance in all considered settings. Remarkably,
these results were achieved directly through querying our network, whereas
many baselines require correspondence postprocessing [10, 19, 23, 50, 55, 56].
Furthermore, the results underline that the shape graph module III plays a
critical role in our pipeline for optimal performance.

|  |  SH’20 on |  SH’20 on TOSCA
---|---|---|---
| SH’20 | SMAL | Cat | Centaur | Dog | Horse | Human | Wolf
UFM [23] | 39.8 | 32.9 | 39.4 | 39.2 | 37.5 | 34.1 | 49.6 |  04.4
SURFM [50] | 53.4 | 37.7 | 54.0 | 57.7 | 57.9 | 57.0 | 65.8 | 55.3
WFM [55] | 31.4 | 20.2 | 20.6 | 21.9 | 16.7 | 22.4 | 38.1 |  05.7
DiffNet [56] | 40.5 | 18.2 | 14.2 |  08.3 | 13.6 |  09.1 | 24.5 |  02.6
DS [20] | 35.0 | 10.8 |  07.6 |  09.1 |  05.5 |  02.5 | 10.1 |  02.1
NM [19] | 10.0 |  09.9 | 16.8 | 12.7 | 14.6 | 11.2 | 29.7 |  01.5
1-9 CZO [27] | 21.7 |  0– |  0– |  0– |  0– |  0– |  0– |  0–
UDM [10] | 52.6 | 25.5 | 40.7 | 34.3 | 43.6 | 43.0 | 45.8 | 34.3
SyNoRiM [25] | 10.4 |  05.7 | 12.8 | 11.6 | 10.6 |  07.1 | 28.2 |  02.0
Ours w/o III | 11.1 |  03.4 |  06.3 |  06.0 |  04.9 |  02.6 | 20.1 |  02.2
Ours | 10.6 |  02.6 |  05.2 |  02.0 |  03.0 |  02.2 |  08.3 |  01.4

Figure 5: Inter-class matching. (left) A comparison of our approach to the
considered baselines on SHREC’20 [17]. We further assess the generalization
from training on SHREC’20 to two different synthetic datasets, SMAL [64] and
TOSCA [8]. (right) Additionally, we visualize the shape graph node embeddings
of our approach on TOSCA [8] through 2D multi-dimensional scaling. Since the
learned edge weights express affinity scores, shapes with similar geometries
tend to cluster together. The three human classes (shades of blue) form one
big cluster, which indicates that the intra-category pose variety is higher
than geometric differences between subjects. Shapes with four legs (orange
$\hateq$ horse, red $\hateq$ cat, …) and two legs (blue $\hateq$ human, green
$\hateq$ gorilla) are linearly separable in the 2D MDS space. Interestingly,
the centaur classes’ embedding (purple) lies exactly between these two
categories.

###  4.2 Matching with topological changes

##### Datasets

The benchmarks SHREC’Isometry [16] and TOPKIDS [32] focus on matching with
topological noise. This is a common phenomenon when working with real scans,
where the mesh topology is often corrupted by self-contact of separate parts
of the scanned objects. Such topological merging severely affects the
correspondence estimation since it distorts the intrinsic shape geometry non-
isometrically. The first benchmark SHREC’Isometry [16] contains real scans of
different humanoid puppets and hand models. A majority of poses in their
‘heteromorphic’ test set are subject to topological changes, see also Figure 4
for an example. The TOPKIDS [32] dataset contains synthetic shapes of human
children where topological merging is emulated by computing the outer hull of
intersecting geometries, see Figure 1 for an example.

##### Discussion

Quantitative results are shown in Figure 3. We observe that topological
merging commonly leads to unstable behavior for methods that rely on intrinsic
priors like preservation of the Laplace-Beltrami operator [10, 27, 50, 55, 56]
or pairwise geodesic distances [23]. It further inhibits approaches that learn
to morph input geometries [19, 25] with explicit deformation priors, since
merged regions tend to adhere to each other, see, e.g., the discussion on
failure cases in [25, Sec. 7]. Our pipeline decreases the correspondence error
by a decisive margin of $19\%$ for SHREC’Iso and $73\%$ for TOPKIDS. We
provide a qualitative comparison in Figure 4, as well as additional examples
in Appendix D.

###  4.3 Inter-class matching

##### Datasets

The SHREC’20 [17] challenge contains real scans of various four-legged animal
models, including: elephant, giraffe, bear, and many more. These geometries
were obtained from inhomogeneous acquisition sources, i.e., different types of
scanners and 3D reconstruction pipelines. Sparse ground-truth correspondences
were obtained through manual annotation. We further assess the generalization
to additional test sets from the synthetic SMAL [64] and TOSCA [8] datasets.
SMAL contains inter-class pairs between different animal classes, whereas
TOSCA contains nearly-isometric pairs with both animal and human classes.

##### Discussion

The resulting accuracies are summarized in Figure 5. Our approach yields the
most stable results overall. Several baselines suffer from unstable behavior
for animals from SHREC’20, because they depend on either noisy SHOT [58] input
features [20], intrinsic priors that favor near isometries [27, 55, 56], or
both [10, 23, 50]. While methods with an explicit deformation prior [19, 25]
perform well on SHREC’20, they do not generalize well to unseen test poses
from SMAL and TOSCA. Our method learns a topology-aware shape graph prior and
thereby gets the best out of both worlds, i.e., robustness to inter-class
pairs and strong generalization to unseen test pairs.

SH’Iso | Train on
---|---
Full | MST | TSP | Star | w/o
Test on | Full | 5.16 | 5.09 | 5.20 | 5.90 | 5.17
MST | 5.68 | 5.49 | 5.50 | 6.36 | 5.49
TSP | 6.08 | 5.62 | 5.80 | 6.94 | 6.51
Star | 5.54 | 5.26 | 5.44 | 6.71 | 6.02
w/o | 5.32 | 5.27 | 5.42 | 6.33 | 6.27

TOPKIDS | Train on
---|---
Full | MST | TSP | Star | w/o
Test on | Full |  07.92 |  08.13 |  08.44 | 11.03 |  09.13
MST |  08.56 |  08.62 |  09.39 | 10.57 |  09.98
TSP | 13.18 | 12.33 | 13.10 | 19.72 | 15.07
Star |  08.61 |  08.84 |  08.34 | 11.92 |  09.63
w/o | 10.62 | 10.64 | 11.61 | 13.62 | 12.02

Table 2: Graph topology comparison. We compare the quantitative performance of
our model for different graph topologies $\mathcal{G}$. Specifically, we
revisit the experiment from Figure 3 and report the mean geodesic error on
SHREC’Iso [16] and TOPKIDS [32]. The standard ‘full’ graph is compared to
three sparse topologies ‘MST’, ‘TSP’, ‘star’ graph, as well as the ‘w/o III’
variant of our pipeline.

###  4.4 Sparse graph topologies

Throughout our experiments, we use complete shape graphs $\mathcal{G}$ with a
full set of $\frac{N(N-1)}{2}$ edges, as specified in Section 3.3. Here, we
explore a few alternative graph topologies with sparse connectivity patterns,
i.e., $\mathcal{O}(N)$ edges: (ii) Minimal spanning trees (MST), (iii) minimal
paths solving the traveling salesman problem (TSP) and (iv) star graphs, where
all nodes are connected to one center node. For a detailed discussion and
visualizations of these graph types, see Appendix B. We compare (ii)-(iv) to
(i) the standard full graph and (v) our pipeline without the graph module III.
A given graph type can be employed either for the cycle consistency loss in
Equation 7 during training or for map refinement at test time. For a complete
picture, we report results for all $5\times 5=25$ possible combinations of
training/evaluation graph types.

Our results in Table 2 indicate that, while the full graph is generally the
most accurate, the sparse topologies often perform comparably, especially MST.
This makes them a viable alternative to the full graph in certain scenarios
with limited resources, both in terms of the required memory and query time.
We provide a comprehensive cost analysis in Appendix C. In most cases, using
the shape graph during training is beneficial, even when no graph is available
at test time (Table 2, bottom row). This makes it relevant for online
applications where not all test pairs are available at once. Regardless of the
graph type, it is generally preferable to include some version of our graph
module III rather than directly using the pairwise correspondences ‘w/o’.

|  | TOPKIDS | SHREC’20
---|---|---|---
|  _with_ III | ✓ | ✗ | ✓ | ✗
Feature I |  I.a SpecConv [20] |  08.53 | 13.68 | 28.54 | 34.99
I.b SHOT [58] |  07.93 | 13.66 | 22.74 | 29.81
I.c ResNet [33] |  07.94 | 13.14 | 39.69 | 40.66
I.d PointNet [46] |  08.78 | 14.10 | 11.01 | 11.54
I.e GraphNN [19] | 14.18 | 25.57 | 14.53 | 18.33
Match II |  II.a FM [43] | 39.12 | 40.66 | 50.58 | 51.37
II.b Sinkhorn [13] | 12.25 | 14.81 | 11.58 | 12.66
II.c Softmax [19] | 12.78 | 13.46 | 11.49 | 13.47
| G-MSM (ours) |  07.92 | 12.02 | 10.65 | 11.06

Table 3: Ablation network architecture. We compare several off-the-shelf
network architectures for the feature backbone I and matching module II to our
full model, as defined in Section 3.2. For each setting, we contrast the
results obtained with (✓) and without (✗) the graph-based multi-matching
module III.

###  4.5 Ablation study

Our proposed architecture consists of several basic building blocks I-III, as
defined in Section 3.2 and Section 3.3. While the shape-graph module III is
unique to our approach, the feature backbone I and matching module II can, in
principle, be replaced by any analogous off-the-shelf architectures. We
compare several popular alternatives: For the feature backbone, we consider
I.a the spectral convolution architecture from [20], I.b our network with SHOT
[58] input features, I.c the ResNet architecture from [33], I.d PointNet [46],
as well as I.e the message passing architecture from [19]. For the
differentiable matching module, we compare II.a a functional map layer [43],
II.b a single Sinkhorn layer [13] and II.c a standard per-point Softmax [19].

We then replace either the feature backbone I.a-I.e or matching module
II.a-II.c in our method and observe how it affects the accuracy on TOPKIDS
[32] and SHREC’20 [17] from Section 4.2 and Section 4.3, respectively. The
results are summarized in Table 3. Replacing either module I or II in our
approach leads to a drop in performance. Moreover, we see that, regardless of
the concrete architecture, our multi-matching approach III (✓in Table 3)
improves the performance over the pairwise matches (✗).

##  5 Conclusion

We propose G-MSM, a novel multi-matching approach for non-rigid shape
correspondence. For a given collection of 3D meshes, we define a shape graph
$\mathcal{G}$ which approximates the underlying shape data manifold. Its edge
weights $w$ are extracted from putative pairwise correspondence signals in a
self-supervised manner. Our network promotes cycle-consistency of optimal
paths in $\mathcal{G}$. Thus, it produces context-aware multi-matches that are
informed by commonalities and salient geometric features across all training
poses. In our experiments, we demonstrate that this simple strategy yields
significant improvements in correspondence accuracy on a wide range of
challenging, real-world 3D mesh benchmarks.

##### Limitations & future work

Our method can effectively learn the underlying canonical shape topology from
a collection of 3D meshes. On the other hand, it naturally relies on at least
some of the poses to convey this latent topology. In the extreme case, if,
instead of a shape collection, we only have $N=2$ poses available, our multi-
shape pipeline does not yield an improvement over the naive pairwise maps.

Since our affinity weights $w$ are constructed through a self-supervised
heuristic, it is difficult to provide theoretical guarantees that the multi-
matching is, without fail, always superior to the putative pairwise
correspondences. However, our model has an in-built robustness to this type of
error: If the pairwise putative correspondences are very accurate, its
corresponding edge weights are low and the network tends to favor the direct
connections. Empirically, we observe that the multi-matching III consistently
improves the accuracy over the putative matches.

Another potential direction for future research is extending our framework to
allow for partial views, e.g., by leveraging recent advances on learnable
partial functional maps [2].

##### Societal impact

Advancing the robustness and accuracy of shape correspondence methods has the
potential to open up new avenues for future applications based on 3D scan
data. Our algorithm constitutes one small advancement in this effort of
extending computer vision algorithms to the 3D domain. Since our algorithm is
fully unsupervised, it can directly reduce deployment costs as no manual
correspondence annotations are required to train our model. Shape
correspondence is a fundamental building block at the heart of many 3D vision
algorithms and we do not anticipate any immediate risk of misuse associated
with this work.

## Acknowledgements

We acknowledge support by the ERC Advanced Grant SIMULACRON and the Munich
School for Data Science.

## References

  * [1] Dragomir Anguelov, Praveen Srinivasan, Daphne Koller, Sebastian Thrun, Jim Rodgers, and James Davis.  Scape: shape completion and animation of people.  In ACM SIGGRAPH 2005 Papers, pages 408–416, 2005.
  * [2] Souhaib Attaiki, Gautam Pai, and Maks Ovsjanikov.  Dpfm: Deep partial functional maps.  In 2021 International Conference on 3D Vision (3DV), pages 175–185. IEEE, 2021.
  * [3] Matthieu Aubry, Ulrich Schlickewei, and Daniel Cremers.  The wave kernel signature: A quantum mechanical approach to shape analysis.  IEEE International Conference on Computer Vision (ICCV) - Workshop on Dynamic Shape Capture and Analysis, 2011.
  * [4] Bharat Lal Bhatnagar, Cristian Sminchisescu, Christian Theobalt, and Gerard Pons-Moll.  Loopreg: Self-supervised learning of implicit surface correspondences, pose and shape for 3d human mesh registration.  Advances in Neural Information Processing Systems, 33:12909–12922, 2020.
  * [5] Federica Bogo, Javier Romero, Matthew Loper, and Michael J. Black.  FAUST: Dataset and evaluation for 3D mesh registration.  In Proceedings IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), Piscataway, NJ, USA, June 2014. IEEE.
  * [6] Davide Boscaini, Jonathan Masci, Emanuele Rodolà, and Michael Bronstein.  Learning shape correspondence with anisotropic convolutional neural networks.  In Advances in neural information processing systems, pages 3189–3197, 2016.
  * [7] Alexander M Bronstein, Michael M Bronstein, and Ron Kimmel.  Generalized multidimensional scaling: a framework for isometry-invariant partial surface matching.  PNAS, 103(5):1168–1172, 2006.
  * [8] Alexander M Bronstein, Michael M Bronstein, and Ron Kimmel.  Numerical geometry of non-rigid shapes.  Springer, 2008.  http://tosca.cs.technion.ac.il/book/resources_data.html.
  * [9] Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst.  Geometric deep learning: going beyond euclidean data.  IEEE Signal Processing Magazine, 34(4):18–42, 2017.
  * [10] D. Cao and F. Bernard.  Unsupervised deep multi-shape matching.  In European Conference on Computer Vision (ECCV), 2022.
  * [11] Luca Cosmo, Emanuele Rodola, Andrea Albarelli, Facundo Mémoli, and Daniel Cremers.  Consistent partial matching of shape collections via sparse modeling.  In Computer Graphics Forum, volume 36, pages 209–221. Wiley Online Library, 2017.
  * [12] Luca Cosmo, Emanuele Rodola, Jonathan Masci, Andrea Torsello, and Michael M Bronstein.  Matching deformable objects in clutter.  In 2016 Fourth International Conference on 3D Vision (3DV), pages 1–10. IEEE, 2016.
  * [13] Marco Cuturi.  Sinkhorn distances: Lightspeed computation of optimal transport.  In Advances in neural information processing systems, pages 2292–2300, 2013.
  * [14] Nicolas Donati, Etienne Corman, Simone Melzi, and Maks Ovsjanikov.  Complex functional maps: a conformal link between tangent bundles.  arXiv preprint arXiv:2112.09546, 2021.
  * [15] Nicolas Donati, Abhishek Sharma, and Maks Ovsjanikov.  Deep geometric functional maps: Robust feature learning for shape correspondence.  arXiv preprint arXiv:2003.14286, 2020.
  * [16] Roberto Dyke, Caleb Stride, Yukun Lai, and Paul Rosin.  Shrec-19: Shape correspondence with isometric and non-isometric deformations.  Eurographics Workshop on 3D Object Retrieval, 2019.
  * [17] Roberto M Dyke, Yu-Kun Lai, Paul L Rosin, Stefano Zappalà, Seana Dykes, Daoliang Guo, Kun Li, Riccardo Marin, Simone Melzi, and Jingyu Yang.  Shrec’20: Shape correspondence with non-isometric deformations.  Computers & Graphics, 92:28–43, 2020.
  * [18] Marvin Eisenberger, Zorah Lahner, and Daniel Cremers.  Smooth shells: Multi-scale shape registration with functional maps.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 12265–12274, 2020.
  * [19] Marvin Eisenberger, David Novotny, Gael Kerchenbaum, Patrick Labatut, Natalia Neverova, Daniel Cremers, and Andrea Vedaldi.  Neuromorph: Unsupervised shape interpolation and correspondence in one go.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 7473–7483, 2021.
  * [20] Marvin Eisenberger, Aysim Toker, Laura Leal-Taixe, and Daniel Cremers.  Deep shells: Unsupervised shape correspondence with optimal transport.  arXiv preprint, 2020.
  * [21] Maolin Gao, Zorah Lahner, Johan Thunberg, Daniel Cremers, and Florian Bernard.  Isometric multi-shape matching.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 14183–14193, 2021.
  * [22] Thibault Groueix, Matthew Fisher, Vladimir G. Kim, Bryan C. Russell, and Mathieu Aubry.  3d-coded: 3d correspondences by deep deformation.  In The European Conference on Computer Vision (ECCV), September 2018\.
  * [23] Oshri Halimi, Or Litany, Emanuele Rodola, Alex M Bronstein, and Ron Kimmel.  Unsupervised learning of dense shape correspondence.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 4370–4379, 2019.
  * [24] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * [25] Jiahui Huang, Tolga Birdal, Zan Gojcic, Leonidas J Guibas, and Shi-Min Hu.  Multiway non-rigid point cloud registration via learned functional map synchronization.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022\.
  * [26] Qi-Xing Huang and Leonidas Guibas.  Consistent shape maps via semidefinite programming.  In Computer graphics forum, volume 32, pages 177–186. Wiley Online Library, 2013.
  * [27] Ruqi Huang, Jing Ren, Peter Wonka, and Maks Ovsjanikov.  Consistent zoomout: Efficient spectral map synchronization.  In Computer Graphics Forum, volume 39, pages 265–278. Wiley Online Library, 2020.
  * [28] Faria Huq, Adrish Dey, Sahra Yusuf, Dena Bazazian, Tolga Birdal, and Nina Miolane.  Riemannian functional map synchronization for probabilistic partial correspondence in shape networks.  arXiv preprint arXiv:2111.14762, 2021.
  * [29] Itay Kezurer, Shahar Z Kovalsky, Ronen Basri, and Yaron Lipman.  Tight relaxation of quadratic matching.  In Computer graphics forum, volume 34, pages 115–128. Wiley Online Library, 2015.
  * [30] Vladimir G Kim, Yaron Lipman, and Thomas A Funkhouser.  Blended intrinsic maps.  Transactions on Graphics (TOG), 30(4), 2011.
  * [31] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980, 2014.
  * [32] Zorah Lähner, Emanuele Rodolà, Michael M Bronstein, Daniel Cremers, Oliver Burghard, Luca Cosmo, Andreas Dieckmann, Reinhard Klein, and Yusuf Sahillioglu.  Shrec’16: Matching of deformable shapes with topological noise.  Proceedings of Eurographics Workshop on 3D Object Retrieval (3DOR), 2:11, 2016.
  * [33] Or Litany, Tal Remez, Emanuele Rodolà, Alex Bronstein, and Michael Bronstein.  Deep functional maps: Structured prediction for dense shape correspondence.  In Proceedings of the IEEE International Conference on Computer Vision, pages 5659–5667, 2017.
  * [34] Or Litany, Emanuele Rodolà, Alex Bronstein, and Michael Bronstein.  Fully spectral partial shape matching.  Computer Graphics Forum, 36(2):1681–1707, 2017.
  * [35] Or Litany, Emanuele Rodolà, Alex M Bronstein, Michael M Bronstein, and Daniel Cremers.  Non-rigid puzzles.  Computer Graphics Forum (CGF), Proceedings of Symposium on Geometry Processing (SGP), 35(5), 2016.
  * [36] Matthew Loper, Naureen Mahmood, Javier Romero, Gerard Pons-Moll, and Michael J. Black.  SMPL: A skinned multi-person linear model.  ACM Trans. Graphics (Proc. SIGGRAPH Asia), 34(6):248:1–248:16, Oct. 2015.
  * [37] Riccardo Marin, Simone Melzi, Emanuele Rodolà, and Umberto Castellani.  FARM: functional automatic registration method for 3d human bodies.  CoRR, abs/1807.10517, 2018.
  * [38] Riccardo Marin, Marie-Julie Rakotosaona, Simone Melzi, and Maks Ovsjanikov.  Correspondence learning via linearly-invariant embedding.  Advances in Neural Information Processing Systems, 33:1608–1620, 2020.
  * [39] Jonathan Masci, Davide Boscaini, Michael Bronstein, and Pierre Vandergheynst.  Geodesic convolutional neural networks on riemannian manifolds.  In Proceedings of the IEEE international conference on computer vision workshops, pages 37–45, 2015.
  * [40] Simone Melzi, Riccardo Marin, Emanuele Rodolà, and Umberto Castellani.  Matching humans with different connectivity.  Proceedings of Eurographics Workshop on 3D Object Retrieval (3DOR), 2019.
  * [41] Simone Melzi, Jing Ren, Emanuele Rodolà, Abhishek Sharma, Peter Wonka, and Maks Ovsjanikov.  Zoomout: Spectral upsampling for efficient shape correspondence.  ACM Transactions on Graphics (TOG), 38(6):155, 2019.
  * [42] Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein.  Geometric deep learning on graphs and manifolds using mixture model cnns.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5115–5124, 2017.
  * [43] Maks Ovsjanikov, Mirela Ben-Chen, Justin Solomon, Adrian Butscher, and Leonidas Guibas.  Functional maps: a flexible representation of maps between shapes.  ACM Transactions on Graphics (TOG), 31(4):30, 2012.
  * [44] Gabriel Peyré, Marco Cuturi, et al.  Computational optimal transport: With applications to data science.  Foundations and Trends® in Machine Learning, 11(5-6):355–607, 2019.
  * [45] Adrien Poulenard and Maks Ovsjanikov.  Multi-directional geodesic neural networks via equivariant convolution.  ACM Transactions on Graphics (TOG), 37(6):1–14, 2018.
  * [46] Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas.  Pointnet: Deep learning on point sets for 3d classification and segmentation.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 652–660, 2017.
  * [47] Jing Ren, Adrien Poulenard, Peter Wonka, and Maks Ovsjanikov.  Continuous and orientation-preserving correspondences via functional maps.  ACM Trans. Graph., 37(6):248:1–248:16, Dec. 2018.
  * [48] Emanuele Rodola, Samuel Rota Bulo, Thomas Windheuser, Matthias Vestner, and Daniel Cremers.  Dense non-rigid shape correspondence using random forests.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4177–4184, 2014.
  * [49] Emanuele Rodolà, Luca Cosmo, Michael Bronstein, Andrea Torsello, and Daniel Cremers.  Partial functional correspondence.  Computer Graphics Forum (CGF), 2016.
  * [50] Jean-Michel Roufosse, Abhishek Sharma, and Maks Ovsjanikov.  Unsupervised deep learning for structured shape matching.  In Proceedings of the IEEE International Conference on Computer Vision, pages 1617–1627, 2019.
  * [51] Klaus Hildebrandt Ruben Wiersma, Elmar Eisemann.  Cnns on surfaces using rotation-equivariant features.  Transactions on Graphics, 39(4), July 2020.
  * [52] Raif M Rustamov et al.  Laplace-beltrami eigenfunctions for deformation invariant shape representation.  In Symposium on geometry processing, volume 257, pages 225–233, 2007.
  * [53] Yusuf Sahillioğlu.  Recent advances in shape correspondence.  The Visual Computer, pages 1–17, 2019.
  * [54] Frank R Schmidt, Eno Töppe, Daniel Cremers, and Yuri Boykov.  Intrinsic mean for semi-metrical shape retrieval via graph cuts.  In Joint Pattern Recognition Symposium, pages 446–455. Springer, 2007.
  * [55] Abhishek Sharma and Maks Ovsjanikov.  Weakly supervised deep functional map for shape matching.  arXiv preprint arXiv:2009.13339, 2020.
  * [56] Nicholas Sharp, Souhaib Attaiki, Keenan Crane, and Maks Ovsjanikov.  Diffusionnet: Discretization agnostic learning on surfaces.  ACM Transactions on Graphics (TOG), 41(3):1–16, 2022.
  * [57] Jian Sun, Maks Ovsjanikov, and Leonidas Guibas.  A concise and provably informative multi-scale signature based on heat diffusion.  In Computer graphics forum, volume 28, pages 1383–1392. Wiley Online Library, 2009.
  * [58] Federico Tombari, Samuele Salti, and Luigi Di Stefano.  Unique signatures of histograms for local surface description.  In Proceedings of European Conference on Computer Vision (ECCV), 16(9):356–369, 2010.
  * [59] Oliver van Kaick, Hao Zhang, Ghassan Hamarneh, and Daniel Cohen-Or.  A survey on shape correspondence.  Computer Graphics Forum, 30(6):1681–1707, 2011.
  * [60] Gul Varol, Javier Romero, Xavier Martin, Naureen Mahmood, Michael J Black, Ivan Laptev, and Cordelia Schmid.  Learning from synthetic humans.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 109–117, 2017.
  * [61] Matthias Vestner, Zorah Lähner, Amit Boyarski, Or Litany, Ron Slossberg, Tal Remez, Emanuele Rodolà, Alex M. Bronstein, Michael M. Bronstein, Ron Kimmel, and Daniel Cremers.  Efficient deformable shape correspondence via kernel matching.  In International Conference on 3D Vision (3DV), October 2017.
  * [62] Cédric Villani.  Topics in optimal transportation.  American Mathematical Soc., 2003.
  * [63] Thomas Windheuser, Ulrich Schlickwei, Frank R Schimdt, and Daniel Cremers.  Large-scale integer linear programming for orientation preserving 3d shape matching.  In Computer Graphics Forum, volume 30, pages 1471–1480. Wiley Online Library, 2011.
  * [64] Silvia Zuffi, Angjoo Kanazawa, David W Jacobs, and Michael J Black.  3d menagerie: Modeling the 3d shape and pose of animals.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 6365–6373, 2017.

##  Appendix A Implementation details

###  A.1 Training details

In the following, we provide additional details on our training protocol and
choice of parameters. Throughout our experiments, our model was trained on a
single NVIDIA Quadro RTX 8000 graphics card with 48GB VRAM.

##### Data preprocessing

For a given shape collection $\mathcal{S}$, we apply a few data
standardization steps to ensure training stability. For each
$\mathcal{X}^{(i)}$, we normalize the scale of the shape by setting the
approximate geodesic diameter to a constant value
$\sqrt{\mathrm{area}(\mathcal{X}^{(i)})}=\frac{2}{3}$. The pose is further
centered around the origin by setting the mean vertex position to
$0\in\mathbb{R}^{3}$. The eigenvalues and eigenvectors required for our method
are precomputed prior to training our model. Otherwise, our method is directly
applicable to any collection of shapes that fulfill the weak pose alignment as
discussed in Section 3.1.

##### Training scheduling

Our general training protocol is outlined in Section 3.4 and illustrated
visually in Figure 2 of the main paper.

In each forward pass, we first query the DiffusionNet backbone
$\Phi_{\mathrm{feat}}$ to obtain sets of local features
$\mathbf{F}^{(i)}:=\Phi_{\mathrm{feat}}\bigl{(}\mathcal{X}^{(i)}\bigr{)}$ and
$\mathbf{F}^{(j)}:=\Phi_{\mathrm{feat}}\bigl{(}\mathcal{X}^{(j)}\bigr{)}$ for
a pair of input shapes $\mathcal{X}^{(i)}$ and $\mathcal{X}^{(j)}$. In the
second step, the matching module
$\bigl{(}\mathbf{\Pi}^{(i,j)},\mathbf{V}^{(i,j)},\ell_{\mathrm{match}}^{(i,j)}\bigr{)}:=\Phi_{\mathrm{match}}\bigl{(}\mathbf{F}^{(i)},\mathbf{F}^{(j)}\bigl{)}$
computes a set of putative correspondences $\mathbf{\Pi}^{(i,j)}$, registered
vertices $\mathbf{V}^{(i,j)}$ and the corresponding matching loss
$\ell_{\mathrm{match}}^{(i,j)}$. Finally, Equation 6 produces the multi-shape
correspondences $\mathbf{\Pi}^{(i,j)}_{\mathrm{mult}}$, which then allows us
to compute the loss $\ell_{\mathrm{cyc}}^{(i,j)}$ through Equation 7.

As stated in Section 3.4, the shape graph $\mathcal{G}$ is updated regularly
after a fixed number of epochs. This interval is chosen in dependence of the
number of training shapes as a round figure that results in around $10k-15k$
training iterations per update. To reduce the computational load, the pairwise
correspondences between all pairs of training shapes
$\mathbf{\Pi}^{(i,j)}_{\mathrm{mult}}$ are precomputed and stored each time
the shape graph is constructed. Additionally, we wait for $5$ shape graph
update cycles before activating the cycle-consistency loss. This burn-in
period allows the feature extractor and putative correspondence modules to
converge to a certain degree which facilitates a stable training and reduces
stochasticity.

##### Learning

Our model is trained in an end-to-end manner with the Adam optimizer [31],
using standard parameters. All the learnable weights are contained in the
DiffusionNet backbone I. The DeepShells pairwise matching module II and multi-
matching module III convert the learned features into correspondences, but
these maps themselves are fully deterministic. The backward pass updates the
DiffusionNet weights both in terms of the pairwise alignment loss
$\ell_{\mathrm{match}}^{(i,j)}$ and the cycle-consistency loss
$\ell_{\mathrm{cyc}}^{(i,j)}$. The former stems from Equation 3 and the latter
term is defined in Equation 7. The cycle-consistent correspondences themselves
$\mathbf{\Pi}^{(i,j)}_{\mathrm{mult}}$ are obtained from non-differentiable
operations, since they are the quantized outputs from DeepShells concatenated
via Dijkstra’s algorithm in Equation 6a. Instead, the gradients from
$\ell_{\mathrm{cyc}}^{(i,j)}$ pass information back to the DeepShells layer II
through the registrations $\mathbf{V}^{(i,j)}$.

##### Hyperparameters

We set the cycle-consistency loss weight to $\lambda_{\mathrm{cyc}}=0.5$. The
number of latent dimensions of the DiffusionNet encodings is chosen as $l=128$
and the architecture comprises $4$ consecutive DiffusionNet blocks. For the
DeepShells matching layer, we directly use the hyperparameters specified by
the original publication and the corresponding source code [20]. Specifically,
the number of eigenfunctions used to compute the smooth shell product space
poses (see Section A.2.2) is upsampled on a log-scale between
$k_{\mathrm{min}}=6$ and $k_{\mathrm{max}}=21$.

###  A.2 Architecture details

####  A.2.1 Feature backbone

Our network proposed in Section 3.2 leverages the recent DiffusionNet [56]
backbone for local feature extraction. We outline the basic architecture of
this module here and refer to [56, Sec. 3] for further technical details.

The core motivation is to model feature propagation of signals $f(x,t)$ on the
surface of a shape $\mathcal{X}^{(i)}$ as heat diffusion, governed by the
standard heat equation

$\frac{\partial}{\partial t}f(x,t)=\Delta f(x,t).$ (9)

In this context, $\Delta$ is the intrinsic Laplace-Beltrami operator on the
surface $\mathcal{X}^{(i)}$. In the discrete case, a common approximation is
the cotangent Laplacian
$\mathbf{L}:=-\mathbf{M}^{-1}\mathbf{S}\in\mathbb{R}^{m\times m}$, where
$\mathbf{M}$ and $\mathbf{S}$ are the mass matrix and stiffness matrix,
respectively. We further consider the truncated basis of eigenfunctions
$\mathbf{\Psi}\in\mathbb{R}^{m\times k}$ and corresponding diagonal matrix of
eigenvalues $\mathbf{\Lambda}\in\mathbb{R}^{k\times k}$ of the discretized
Laplacian. For a given signal $\mathbf{f}\in\mathbb{R}^{m}$ on
$\mathcal{X}^{(i)}$, the heat propagation for a time-interval $t>0$ according
to Equation 9 then results in the approximate solution

$H_{t}(\mathbf{f}):=\mathbf{\Psi}\exp(t\mathbf{\Lambda})\mathbf{\Psi}^{\dagger}\mathbf{f}.$
(10)

For a given feature matrix $\mathbf{F}\in\mathbb{R}^{m\times l}$, an
individual operator $H_{t}$ is applied separately to each channel with
different learnable time step weights $t$. A key benefit of such propagation
operators is that they are indifferent to the sampling density and therefore
robust to remeshing and local noise. On the other hand, pure heat diffusion is
spatially isotropic and therefore not sufficiently expressive. To break radial
symmetry, DiffusionNet additionally leverages a gradient-based feature
refinement layer. At every point on the surface, it computes inner products
between spatial gradients of the (scalar) feature signals on the tangent
plane.

Putting everything together, an individual DiffusionNet block takes a set of
features $\mathbf{F}$, propagates information both via a spatial diffusion and
a spatial gradient layer, and feeds them to a per-point multilayer perceptron
(MLP). The first layer is initialized by the input features, defined as the
vertex coordinates $\mathbf{V}^{(i)}$. For further technical details, we refer
the interested reader to the original publication [56].

####  A.2.2 Hierarchical pairwise matching

In Section 3.2, we further introduced our differentiable matching layer
$\Phi_{\mathrm{match}}$ based on DeepShells [20]. The final map is fully
specified by Equation 3. In the following, we provide additional technical
details required to derive the exact optimization steps and compute
$\Phi_{\mathrm{match}}$ in practice.

Following [20, Sec. 3], we first introduce the following latent feature
representation of a shape $\mathcal{X}^{(i)}$ that is used within each
DeepShells layer

$\mathbf{F}^{(k)}_{\mathcal{X}^{(i)}}:=\biggl{(}\mathbf{\Psi}^{(k)}~{},~{}S^{(k)}\bigl{(}\mathbf{V}^{(i)}\bigr{)}~{},~{}\mathbf{N}^{(k)}\biggr{)}\in\mathbb{R}^{m\times(k+6)}$
(11)

where $\mathbf{\Psi}^{(k)}$ are the first $k$ eigenfunctions of the intrinsic
Laplace-Beltrami operator on $\mathcal{X}^{(i)}$, corresponding to the
smallest eigenvalues. The operator $S^{(k)}$ is the smoothing map initially
proposed in [18, Eq. (8)]. The matrix $\mathbf{N}^{(k)}$ denotes the outer
normals of the (smoothed) input geometry.

Overall, the resulting feature tensor $\mathbf{F}^{(k)}_{\mathcal{X}^{(i)}}$
yields a $(k+6)$-dimensional embedding per vertex
$\mathbf{V}^{(i)}\in\mathbb{R}^{m\times 3}$, depending on the number of
eigenfunctions $k$. In order to align two shapes in this embedding space, an
affine transformation is proposed

$\hat{\mathbf{F}}^{(k)}_{\mathcal{X}^{(i)}}\bigl{(}\mathbf{C}^{(k)},\mathbf{\tau}^{(k)}\bigr{)}:=\biggl{(}\mathbf{\Psi}^{(k)}{\mathbf{C}^{(k)}}^{\dagger}~{},~{}S^{(k)}\bigl{(}\mathbf{V}^{(i)}\bigr{)}+\\\
\mathbf{\Psi}^{(k)}\mathbf{\tau}^{(k)}~{},~{}\hat{\mathbf{N}}^{(k)}\biggr{)}\in\mathbb{R}^{m\times(k+6)},$
(12)

that deforms the input shape $\mathcal{X}^{(i)}$ in the $(k+6)$-dimensional
embedding space. This deformation is parameterized with a functional map
$\mathbf{C}^{(k)}\in\mathbb{R}^{k\times k}$ [43] and displacement coefficients
$\mathbf{\tau}^{(k)}\in\mathbb{R}^{k\times 3}$. The outer normals of the
deformed pose are denoted as $\hat{\mathbf{N}}^{(k)}$.

As we discussed in Section 3.2, the correspondence task in our framework is
fully specified by the optimal transport energy Equation 2. To make the
resulting update steps differentiable, an additional entropy regularization
term is added to the energy

$E_{\mathrm{match,reg}}\bigl{(}\mathbf{F},\mathbf{G};\mathbf{\tilde{\Pi}}\bigr{)}=E_{\mathrm{match}}\bigl{(}\mathbf{F},\mathbf{G};\mathbf{\tilde{\Pi}}\bigr{)}+\\\
\lambda_{\mathrm{ent}}\sum_{i^{\prime},j^{\prime}}\mathbf{\tilde{\Pi}}_{i^{\prime},j^{\prime}}\log\mathbf{\tilde{\Pi}}_{i^{\prime},j^{\prime}}.$
(13)

This is a common approach that was initially proposed by the seminal work of
Cuturi et al. [13]. One compelling implication is that
$E_{\mathrm{match,reg}}$ can be minimized efficiently with respect to the
transport plans $\mathbf{\tilde{\Pi}}\in[0,1]^{m\times n}$ through Sinkhorn’s
algorithm. Moreover, each individual update step of this algorithm is
differentiable which makes it viable for standard gradient-based optimization.
The resulting map $\Phi_{\mathrm{match}}$ is specified by the following
alternating scheme of optimization steps

$\displaystyle\bigl{(}\mathbf{C}^{(k)},\mathbf{\tau}^{(k)}\bigr{)}\mapsto$
$\displaystyle\underset{\begin{subarray}{c}\mathbf{\tilde{\Pi}}^{(k)}\in\\\
\mathcal{T}(\mathcal{X}^{(i)},\mathcal{X}^{(j)})\end{subarray}}{\arg\min}E_{\mathrm{match,reg}}\biggl{(}\hat{\mathbf{F}}^{(k)}_{\mathcal{X}^{(i)}},\mathbf{F}^{(k)}_{\mathcal{X}^{(j)}};\mathbf{\tilde{\Pi}}^{(k)}\biggr{)},$
(14a) $\displaystyle\mathbf{\tilde{\Pi}}^{(k)}\mapsto$
$\displaystyle~{}~{}\underset{\mathbf{C}^{(k)},\mathbf{\tau}^{(k)}}{\arg\min}~{}~{}E_{\mathrm{match,reg}}\biggl{(}\hat{\mathbf{F}}^{(k)}_{\mathcal{X}^{(i)}},\mathbf{F}^{(k)}_{\mathcal{X}^{(j)}};\mathbf{\tilde{\Pi}}^{(k)}\biggr{)},$
(14b)

Through this scheme, the minimization of the energy $E_{\mathrm{match,reg}}$
is decoupled into two separate update steps, each of which can be solved
efficiently in closed form. The first expression is minimized via Sinkhorn’s
algorithm to obtain an optimal transport plan $\mathbf{\tilde{\Pi}}^{(k)}$
from the transportation polytope
$\mathcal{T}(\mathcal{X}^{(i)},\mathcal{X}^{(j)})$. The second update results
in a standard linear least squares problem, see [20, Sec. 3] for additional
details. For the initial step, we replace the $(k+6)$-dimensional feature
embeddings with the learned features $\mathbf{F}^{(i)}$ and $\mathbf{F}^{(j)}$
produced by the DiffusionNet backbone. The map $\Phi_{\mathrm{match}}$ then
alternates between the minimization steps Equation 14a and Equation 14b while
increasing the number of eigenfunctions $k$ after each step. The final outputs
are defined as

$\displaystyle\mathbf{\Pi}^{(i,j)}:=$
$\displaystyle\underset{\mathbf{\Pi}}{\arg\min}~{}~{}~{}E_{\mathrm{match}}\biggl{(}\hat{\mathbf{F}}^{(k_{\mathrm{max}})}_{\mathcal{X}^{(i)}},\mathbf{F}^{(k_{\mathrm{max}})}_{\mathcal{X}^{(j)}}~{};~{}\mathbf{\Pi}\biggr{)}$
(15a) $\displaystyle\mathbf{V}^{(i,j)}:=$
$\displaystyle\mathbf{V}^{(i)}+\mathbf{\Psi}^{(k_{\mathrm{max}})}\mathbf{\tau}^{(k_{\mathrm{max}})},$
(15b) $\displaystyle\ell_{\mathrm{match}}^{(i,j)}:=$
$\displaystyle\sum_{k}E_{\mathrm{match}}\biggl{(}\hat{\mathbf{F}}^{(k)}_{\mathcal{X}^{(i)}},\mathbf{F}^{(k)}_{\mathcal{X}^{(j)}}~{};~{}\mathbf{\tilde{\Pi}}^{(k)}\biggr{)}.$
(15c)

The matches $\mathbf{\Pi}^{(i,j)}\in\\{0,1\\}^{m\times n}$, with
${\mathbf{\Pi}^{(i,j)}}\mathbf{1}_{n}=\mathbf{1}_{m}$, produced by
$\Phi_{\mathrm{match}}$ are thereby the outputs of the final optimization
layer $k_{\mathrm{max}}$. In practice, they are obtained as the hard nearest-
neighbor assignment between the final obtained shape embeddings
$\hat{\mathbf{F}}^{(k_{\mathrm{max}})}_{\mathcal{X}^{(i)}}$ and
$\mathbf{F}^{(k_{\mathrm{max}})}_{\mathcal{X}^{(j)}}$.

i Full graph.

ii MST graph.

iii TSP graph.

iv Star graph.

Figure 6: An overview of different shape graph topologies $\mathcal{G}$. We
consider graphs that are (i) fully connected, (ii) minimal spanning trees,
(iii) minimal Hamiltonian paths, specified by the traveling salesman problem
and (iv) star graphs centered around one canonical pose. We provide a detailed
discussion in Appendix B. Unless stated otherwise, the full graph (i) is the
default for our approach.

##  Appendix B Shape graph topology

We explore the following classes of graph topologies for the shape graph
$\mathcal{G}$, see also Figure 6 for a visualization:

  1. i.

Full graph. The default setting for our method is the fully connected graph
with the edge weights defined in Equation 5.

  2. ii.

MST graph. We consider the minimal spanning tree corresponding to the full
graph $\mathcal{G}$. This graph topology is a minimal choice, in the sense
that it has the smallest total edge weight among all subgraphs of
$\mathcal{G}$ that span the set of nodes $\mathcal{S}$.

  3. iii.

TSP graph. Based on the traveling salesman problem, we predict a Hamiltonian
path of minimal total edge weight. This effectively defines an optimal
ordering of the input set $\mathcal{S}$.

  4. iv.

Star graph. We define a complete, bipartite graph which connects one specific
center node with all $N-1$ remaining nodes. The idea is to imitate template-
based shape matching methods such as [4, 22] where all training poses are
matched to a canonical shape.

Unless stated otherwise, we use the fully connected graph (i) by default in
our experiments in Section 4. Choosing the number of retained edges is
generally subject to a trade-off between accuracy and efficiency. Using (i)
all $\frac{N(N-1)}{2}$ edges often yields the most accurate matching
$\mathbf{\Pi}^{(i,j)}_{\mathrm{mult}}$, since this leads to the shortest
possible path lengths in Equation 6a. Nevertheless, the sparse graph
topologies (ii)-(iv) might be preferable for specific applications. All three
definitions (ii)-(iv) specify variants of spanning trees with exactly $N-1$
edges. This means, that the memory complexity for storing the graph, as well
as the full query runtime cost is in $\mathcal{O}(N)$, see Appendix C for a
cost analysis. Thus, they are more suitable for very large training sets or in
scenarios where computational resources are scarce. See Section 4.4 in the
main paper for an empirical comparison of the different topologies (i)-(iv).

##### Discussion

Each of the variants (ii)-(iv) has interesting properties that might give rise
to potential new avenues of applications in future work: (ii) Removing the
(k-1) largest edges in the MST graph yields a subdivision of $\mathcal{G}$
into k optimal clusters (MST clustering). (iii) The TSP graph orders the input
shapes into a sequence, i.e., predicts a canonical ordering. (iv) Choosing an
optimal star graph automatically selects one of the shapes in the collection
$\mathcal{S}$ as the canonical pose. By comparing the set of all possible star
graphs, we can in principle rank all input poses in terms of how
representative they are of the underlying shape manifold.

| $\\#\mathrm{pairs}=10^{2}$ | $20^{2}$ | $50^{2}$ | $100^{2}$
---|---|---|---|---
Epoch training time ($s$) | $37.85\pm 2.48$ | $174.82\pm 8.31$ | $921.23\pm 25.56$ | $4192.91\pm 142.03$
Graph construction ($s$) | $36.04\pm 1.95$ | $157.30\pm 7.04$ | $893.23\pm\phantom{0}9.05$ | $3814.96\pm\phantom{0}44.48$
Required RAM ($\mathrm{GB}$) | $3.57\pm 0.02$ | $3.96\pm 0.04$ | $5.81\pm 0.28$ | $9.02\pm 1.73$

Table 4: Empirical training cost. We quantify the computation cost of our
pipeline for different training set sizes. For a given number of shapes
$N=|\mathcal{S}|$, one epoch consists of
$\\#\mathrm{pairs}=N^{2}\in\\{10^{2},\dots,100^{2}\\}$ optimization steps that
each match a pair of shapes
$\mathcal{X}^{(i)},\mathcal{X}^{(j)}\in\mathcal{S}$.

|  | $\\#\mathrm{pairs}=10^{2}$ | $20^{2}$ | $50^{2}$ | $100^{2}$
---|---|---|---|---|---
Total query | Full graph | $41.00\pm 3.32$ | $166.91\pm 9.54$ | $1077.06\pm 28.35$ | $4370.36\pm 115.00$
time ($s$) | MST graph | $\phantom{0}3.62\pm 0.29$ | $\phantom{0}\phantom{0}8.10\pm 0.36$ | $\phantom{0}\phantom{0}22.48\pm\phantom{0}0.90$ | $\phantom{0}\phantom{0}50.98\pm\phantom{0}\phantom{0}2.57$
Graph storage | Full graph | $10.66\pm 0.00$ | $42.64\pm 0.01$ | $266.47\pm 0.08$ | $1065.89\pm 0.33$
($\mathrm{MB}$) | MST graph | $\phantom{0}0.96\pm 0.00$ | $\phantom{0}2.03\pm 0.00$ | $\phantom{0}\phantom{0}5.22\pm 0.00$ | $\phantom{0}\phantom{0}10.55\pm 0.00$

Table 5: Total query cost. We report the computation cost of our pipeline at
test time. Note, that these results only apply to the specific setting where
all pairs of a given set of shapes are queried and the graph $\mathcal{G}$ is
_precomputed_. Under these circumstances, the MST graph proves to be superior
as its computation cost increases linearly $\mathcal{O}(N)$ in the number of
shapes $N$. For pairwise matching at test time, or when the graph
$\mathcal{G}$ needs to be extracted on the fly, the advantages of MST are less
prominent.

##  Appendix C Empirical computation cost

##### Training

We empirically measure the computation cost of our full pipeline. To this end,
we choose a training set of $\\{10^{2},20^{2},50^{2},100^{2}\\}$ pairs from
the SURREAL [60] dataset with a fixed mesh resolution of $6890$ vertices,
which is common for SMPL [36] meshes. The resulting training runtime and
memory costs are summarized in Table 4. Averaged over all samples, our model
takes around $\approx 0.4s$ per training pair. The majority of the cost for
constructing the graph $\mathcal{G}$ results from querying all sample pairs,
which is equivalent to the epoch training cost minus the backward pass. The
remaining cost stems from precomputing the concatenated, pairwise matches as
discussed in Section A.1.

##### Query time

We additionally compare the required cost for querying our model. Aside from
our main pipeline, we also consider the sparse ‘MST’ graph type introduced in
Appendix B. The resulting costs are summarized in Table 5. For a given set of
query shapes, one has to distinguish whether the graph $\mathcal{G}$ is
precomputed or needs to be predicted on the fly. In the latter case, an
additional cost of constructing the graph is added, see the second row of
Table 4. Notably, this cost does not depend on the test graph topology. This
also means that the main computational advantages of the MST graph are less
prevalent when no offline graph precomputation is possible, e.g., for a pair
of unseen test poses. When the unseen pose is supposed to be added to an
existing graph in an online fashing, only $N$ pairs between the old training
set and the new pose need to be computed. This, however, again entails the
same cost for either the full graph or MST. On the other hand, MST is much
faster for precomputed graphs. Also, the storage cost of the MST graph is
always more efficient than the dense ‘full’ setting. This makes sparse graph
topologies relevant when memory is limited or for very large training sets,
since the required memory of the full graph grows quadratically
$\mathcal{O}(N^{2})$ with the number of training shapes $N=|\mathcal{S}|$.

##  Appendix D Qualitative results

For a more complete picture, we provide several additional qualitative
comparisons. Figure 7 and Figure 8 show results corresponding to the benchmark
comparisons from Section 4.2 and Section 4.3 of the main paper.

\begin{overpic}[width=433.62pt]{figures/qualitative_appendix/topkids_supp_qual_001.png}
\put(5.5,25.0){Target}
\put(21.0,25.0){UDM~{}\cite[cite]{[\@@bibref{}{cao2022unsupervised}{}{}]}}
\put(39.0,25.0){DS~{}\cite[cite]{[\@@bibref{}{eisenberger2020deep}{}{}]}}
\put(55.0,25.0){NM~{}\cite[cite]{[\@@bibref{}{eisenberger2021neuromorph}{}{}]}}
\put(71.0,25.0){SyNoRiM~{}\cite[cite]{[\@@bibref{}{huang2022multiway}{}{}]}}
\put(91.0,25.0){Ours} \end{overpic}

Figure 7: Topological noise qualitative. We compare the quality of the
predicted correspondences on three pairs from TOPKIDS [32], corresponding to
the quantitative results from Figure 3. All three pairs are corrupted by
topological noise in places of self-contact, e.g., where the child’s arms
touch its upper body or head.

\begin{overpic}[width=433.62pt]{figures/qualitative_appendix/smal_supp_qual_001.png}
\put(7.0,19.0){Target}
\put(26.5,19.0){DS~{}\cite[cite]{[\@@bibref{}{eisenberger2020deep}{}{}]}}
\put(47.0,19.0){NM~{}\cite[cite]{[\@@bibref{}{eisenberger2021neuromorph}{}{}]}}
\put(65.0,19.0){SyNoRiM~{}\cite[cite]{[\@@bibref{}{huang2022multiway}{}{}]}}
\put(87.0,19.0){Ours} \end{overpic}

Figure 8: Inter-class texture transfers. We assess the map smoothness of
several baseline approaches, in comparison to our proposed method. The five
sample pairs are taken from the SMAL [64] test set corresponding to our
benchmark comparison in Figure 5. In each case, the obtained matches are
visualized via a texture map.