Exact Shape Correspondence via 2D graph convolution
Authors: Barakeel Fanseu Kamhoua
Lin Zhang
Yongqiang Chen
Han Yang
MA KAILI
Bo Han
Bo Li
James Cheng
Venue: NeurIPS 2022 Accept (2022)
Keywords: Applications
Vision
Shapes
Correspondences

Abstract: For exact 3D shape correspondence (matching or alignment), i.e., the task of matching each point on a shape to its exact corresponding point on the other shape (or to be more specific, matching at geodesic error 0), most existing methods do not perform well due to two main problems. First, on nearly-isometric shapes (i.e., low noise levels), most existing methods use the eigen-vectors (eigen-functions) of the Laplace Beltrami Operator (LBO) or other shape descriptors to update an initialized correspondence which is not exact, leading to an accumulation of update errors. Thus, though the final correspondence may generally be smooth, it is generally inexact. Second, on non-isometric shapes (noisy shapes), existing methods are generally not robust to noise as they usually assume near-isometry. In addition, existing methods that attempt to address the non-isometric shape problem (e.g., GRAMPA) are generally computationally expensive and do not generalise to nearly-isometric shapes. To address these two problems, we propose a 2D graph convolution-based framework called 2D-GEM. 2D-GEM is robust to noise on non-isometric shapes and with a few additional constraints, it also addresses the errors in the update on nearly-isometric shapes. We demonstrate the effectiveness of 2D-GEM by achieving a high accuracy of 90.5$\%$ at geodesic error 0 on the non-isometric benchmark SHREC16, i.e., TOPKIDS (while being much faster than GRAMPA), and on nearly-isometric benchmarks by achieving a high accuracy of 92.5$\%$ on TOSCA and 84.9$\%$ on SCAPE at geodesic error 0.

Exact Shape Correspondence via 2D Graph Convolution
Barakeel Fanseu Kamhoua', Lin Zhang2, Yonggiang Chen', Han Yang', Kaili Ma',
Bo Han Bo Li, James Cheng' The Chinese University of Hong Kong, 'The Hong Kong University of Science and Technology, 'Hong Kong Baptist University
Abstract
For exact 3D shape correspondence (matching alignment), i.e., the task of matching each point on a shape to its exact corresponding point on the other shape (or to be not perform well due to two main problems. First, on nearly-isometric shapes (i.e., low noise levels), most existing methods use the eigen-vectors (eigen-functions) of the Laplace Beltrami Operator (LBO) or other shape descriptors to update initialized correspondence which not exact, leading an accumulation of update errors. Thus, though the final correspondence may generally be smooth, it is generally inexact. Second, on non-isometric shapes (noisy shapes), existing methods are generally not robust to noise as they usually assume near-isometry. In addition, existing methods that attempt to address the non-isometric shape problem (e-g.. GRAMPA) are generally computationally expensive and do not generalise nearly-isometric shapes. address these two problems, we propose a 2D graph convolution- based framework called 2D-GEM. 2D-GEM is robust to noise on non-isometric shapes and with few additional constraints, also addresses the errors in the update nearly-isometric shapes. We demonstrate the effectiveness 2D-GEM by achieving a high accuracy of 90.5% at geodesic error on the non-isometric benchmark SHRECI6, i.e., TOPKIDS (while being much faster than GRAMPA), and on -sommeici benchmarks by achieving a high accuracy 92.5% on TOSCA and 84.9% SCAPE at geodesic error O.
specific, matching geodesic error 0), most existing methods do
Introduction
3D shapes undergo different types of deformations. Deformations be rigid non-righ non-rigid. Rigid deformations include rotations, translations, reflections, or any composition of these resulting in pose changes. They preserve geometric properties of the shape such segment lengths, angles, volumes, sizes, geodesic distances and others. Non-rigid deformations do not preserve geometric properties of the shape, they include dilations, (e.g., stretching, scaling). In this work we focus on non-rigid shapes that are either nearly-isometric (i.e., most geometric properties are preserved), non-isometric (i.e., geometric properties are not preserved, and contain strong topological noise).
composition of dilations and rigid deformations
Non-rigid shape matching is very important task in machine learning, shape analysis and computer vision. It has important applications such as shape registration, comparison, recognition, and retrieval. 3D shapes usually represented as 2D manifolds embedded in R Given two three dimensional shapes Mj and M2 with n vertices each, the goal of non-rigii shape matching is to find meaningful correspondence T MM M2, where T is (a) bijective,
(b) continuous in both directions in the sense that nearby points on Mi should be matched to nearby points on Ma (vice versa), and (c)
*Corresponding author: Ithannbv@@cnnectt.uc
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

similar points should be matched to each other 42 In the discrete setting the correspondence (map
or match) T can be represented as a permutation matrix P
{0, 1] nnx [54
In more details, 3D shapes are usually represented using triangulations (e.g.. the Delauney triangula-
tion (00) and kyz-coordinates representations in IR3 88 42 is hard to utilize these xyz-coordinates and triangulations to directly perform 3D shape matching because of: (a) embedding ambiguities, L.c. shapes sharing the same metric (isometry) or very similar metries (nearly-isometrie) can have drastically different xyz-coordinates representations in I due to pose changes [80], and (b) non- isometric shapes with strong topological noise will have even more different xyz-coordinates and triangulations.
As such, these 3D 3D-coordinates together with the triangulations are usually used extract point- descriptors (which encode the similarity between points), and pair-wise descriptors (which encode global and/or local relations between pairs of points). Once these descriptors are built, the shape matching problem is reduced to an alignment problem over (a) the point-wise descriptors, or (b) the pair-wise descriptors, or (c) both (joint alignment). The joint alignment problem can be written as:
P arg min E(P) = arg min (FP) + (P), Pell
(I)
PEll
where II the set of permutation matrices, the generalised energy, IF is the energy over point- wise descriptors, H is the energy over pair-wise descriptors, and a is trade-off parameter [2)
Several algorithms have been proposed to address point- wise alignment. 44 70 [5555]]]5 64), pair-wise 54 58
alignment 18), as well as joint alignment [59 57 56 2 79
42
Due to space constraints,
see Appendix A for more details on the different alignments as well as related works.
To measure the performance of an algorithm on the 3D shape matching task, the geodesic error usually used as the error metric (20, 80). Given that a point on shape M, mapped by an algorithm to y as its correspondence on shape M2, the geodesic error measures how far the match y is from the true matching position for on M2 i.e., y² (given by the true map). When the map returned by algorithm is exact, it significantly improves performance and efficiency of other tasks such as registration, comparison, motion transfer, style transfer. However, most methods proposed in each of the aforementioned categories for 3D shape matching do not perform well at geodesic error O (i.e., the task of exact matching where y is the same point y"). This is mainly due to two factors.
20 0PM
GRAMPA
ZoweOot
20 CD-
110 2010
(a) Sample map on TOPKIDS
(b) Plot of sample on TOPKIDS
Figure 1: A non-isometric example. Illustrating the performance of 2D-GEM and other methods on a sample shape from the TOPKIDS dataset. For DIR we used 5IR-500 with all LMD thresholds set to 5 since geodesic distances are not conserved on TOPKIDS (note that here, DIR performs much worse with lower thresholds). For ZoomOut we used 200 eigen-values and started from 20 with a step size of 1. For 2D-GEM and GRAMPA we followed the parameters in Section D.4
First, on non-isometric shapes, given that most existing methods assume near-isometry, they cannot handle noisy shapes (e.g., shapes with strong topological noise such mesh "gluing" in areas of contact as in the TOPKIDS dataset (42). since in this case geometric properties such as geodesic distances are not preserved and hence the shapes are not nearly isometric. An illustration can be seen in Figures| (aa and [bb) where the existing methods that assume near-isometry such as ZoomOut [44] and DIR [0] do not perform well at geodesic error on the sample shape from TOPKIDS. They even produce non-smooth map in the case of DIR. Moreover, those methods that try to address shapes,
this noise are computationally very expensive and do not generalize well to nearly-isoment because for nearly-isometre shapes stronger constraints (such as preserving geodesic distances) are needed for the match. To illustrate this point, the spectral method GRAMPA is very expensive as it needs to compute all the eigen-values and eigen- -egeorsectors of the adjacency matrices obtained from the triangulations of each shape (see more details in Appendix [B and time comparison with 2D-GEM in Figures 2(a) and 2(b). Moreover, GRAMPA cannot generalize to cases of near-isometry

---

as illustrated in Figure ((a) which shows the matching of GRAMPA in an example from SCAPE, nearly-isometrit shape dataset).
300
M MW
CRAMPA
VVV
(a) Times TOPKIDS
(b) Times SCAPE
Figure 2: Time taken by 2D-GEM and GRAMPA for each of the 90 shapes on TOPKIDS and 71 on SCAPE.
GHAMPA
1
J0-GEM
DiR
(a) Sample map on SCAPE
(b) Plot of sample on SCAPE
An isometric example. Illustrating the performance of 2D-GEM and other methods on a sample shape from the SCAPE dataset (using same settings as in figure I
Figure 3:
Second, for -earmyiisomttric shapes, most existing methods attempt to first find an initial correspon- dence and then iteratively improve this initial correspondence using all points and the eigen- sigen-vectors corresponding to lower frequencies (eigen-values) of the LBO 4 58 (54) or using other shape descriptors [64]. However, such an approach Icads to accumulation of errors in the correspondence, since the initial correspondence is mostly not accurate. This problem has been discussed in details by Xiang al. 80) which attempted to address this via the Dual Iterative Refinement (DIR). DIR finds well matched points using the notion of Local Mapping Distortion (LMD) to identify points for which the geodesic distances are well preserved by the correspondence, and then use these points to update the correspondences of the other points via the notion of Functional maps [56]. Thus, DIR reduces the error accumulation. However, the DIR approach only works for -early-isometric shapes and not for non-isometric shapes since it is based on the assumption of preserving geodesic distances which are not preserved in the case of non-isometries (see Figure [[a] which shows that DIR does not perform well at geodesic 0 for non non-isometric shapes). Finally, even on yearly-isometrie shapes, DIR, though effective, requires a lot of eigen-vectors of the LBO order to perform well geodesic error
0. This can be seen in Figure 3(b) where using up to 500 eigen-vecton gives only 25% accuracy at geodesic error on the sample shape from SCAPE, and even with up 1000 eigen-vectors vectors it only achieves 69.5% correspondence accuracy on SCAPE and 59.8% on TOSCA at geodesic error 0 (as reported in the experiments in Section 5).
Given these problems, we propose to utilize 2D graph convolution for (a) non-isometric shape matching (since it is de-noising operation), and (b) for isometric shape matching by further constraining our framework to preserve geodesic distances.
To this end:
we show how graph matching can be done via the 2D graph convolution, and re-define noise in the context of graph matching. We further show empirically that this approach can match the recent spectral method GRAMPA on Erdos Regny random graph matching, as well as outperform it in the presence of informative node features (see Appendix D).
we propose a new 2D graph convolution- based approach to shape matching, called 2D-GEM, which is (a) robust to noise, and achieves high accuracy on exact matching of non-isometric shapes while being orders of magnitude faster than GRAMPA, and (b) with some additional constraints also achieves high accuracy on exact matching of nearly-isometric shapes.
3

---

2 2D graph Convolution for Joint Alignment
To the best of our knowledge, are the first to propose 2-D graph convolution for graph alignment and shape matching. The most closely related work is the work that uses graph convolution neural networks for graph alignment [22] (See Appendix A.2) Here, we revisit the traditional graph convolu- tion, show how the joint aligument problem can be done via 2D graph convolution, and finally we re-define noise in the context of graph matching.
2.1 Graph Convolution
From the Graph Signal Processing [67] perspective, graph convolution is regarded as a frequency filtering operator over node attributes. Given a graph, with node attribute matrix X E 1 its normalized symmetric Laplacian (referred to as Laplacian in the rest of the paper) can be eigen- decomposed L UAU*, where A diag(A1,
An) E [n are the eigen-values in increasing order, and = [u,,... un E R=*" are the associated orthogonal eigen-vectors. The graph convolution operation applied to the graph signal x (a column of X) consists of three steps [45] 24, 29 30] (1) transform node attributes into the spectral domain (i.e., z = X)x); (2) remove attribute noise by scaling the spectrum with function defined eigen-values (i.e., R g (()))=)); (3) perform inverse transformation on the scaled spectrum (i.e., X Uz), where ((A) is a scalar-valued function the eigen-values A. In short, graph convolution is able to remove the noisy signals by assigning smaller weight on higher eigen-value spectrum with a well defined function (A). For convenience, we denote (L)) Ug(A)U", so that we have the convolution as X = XL) We refer to (LL as the convolution function and ((A) as the function or simply filter.
2.2 Joint Alignment via 2D graph Convolution
Following previous works [22 and Appendix C the graph convolution is invariant to permutation. As such, given two graphs A and B with graph convolution functions MI A(L)), Myg h hLB)) e Rax", features XA.X, E IRaxd and having the functions and h to be the same function, the joint alignment problem in Equation can instead be performed as:
min , M
see Appendix C for more details. We observe that (2) reduces to the Linear Assignment Problem (LAP):
max P
X
(3)
where Tr(-) is the matrix trace operator, the convolution functions capture the pair-wise descriptors, and the features capture the point-wiss descriptors. The first benefit of the convolution is to help do the joint alignment as a Linear Assignment Problem (LAP), which is much cheaper than the traditional Quadratic Assignment Problem (QAP) (23) used for graph matching. Note that, MI Ug(A)
E, ((Ax)),,u' ui and Mg = Vh(M) V Σj h( where U, V are the orthogonal eigen- vectors of M. and Mn, and A, M are the diagonal matrices of their respective eigen-values. Given these, one can rewrite cost matrix C MI X in 3 as:
C Σ (0(A))(p))aa (...))/uuxXXXXxXX
(4)
When node features are not available, one can initialize all nodes with the same features in (3) i.e.. XA JA E Ra1 xd and X = JB E Raaxd, where n1 may or may not be equal to ny for different size graphs, and J A. JB B are all one rectangular matrices. This equivalent to assuming that nodes have the same probability of being matched to each other. Moreover, to save cost in the case when there no feature, one could simply initialize the similarity matrix X, X JA,B B E T xng (given that JAJT B = J JA.B E R x"1, where J JA,B is scalar matrix with constant [J JA, Σd 1 = d) for all entries. In the case where there is no feature, (4) becomes:
C Σ (((A))(m))uaa J.BVVVJ..
(5)

---

(a) 1 1-hop low-pass
(b) 2 2-hop low-pass
(c) redefining noise
Figure 4: 2D graph filters. Figure ((a) uses the convolution functions g LA) = g (LB) (I L).
Figure 4(b) uses the convolution functions ((a = ((L)) = (I L) and Figure 4(c) uses the noise robust filter defined in Section with
Our cost matrices in equations (4) and 5) can be seen as 2D graph convolution on the 2D graph signals X (or JAB in the case of no features) [46], where we: (1) transform the 2D graph signals into the spectral domain to obtain the 2D graph spectrum (i.e., Z = U XA'AX V or Z U' J A. V) 46 (2) remove noise (de-noise) from the 2D graph signals by scaling the 2D spectrum with function defined on each pair of bagen-values (i.e., Σ,j = w(Ai, My.. M2)2 and (3) perform inverse transformation on the scaled 2D) spectrum (C (C= UZVT). Thus, our cost matrices are 2D filtering operation on the 2D graph signals, where (y),, ggggg((())) ((,))((uz)) is the 2D filter (see Figures 4(a)
4(b) and ((c) for different 2D filters).
3 Redefining Noise in the Context of Graph Matching
In this section, we redefine noise in the context of graph matching and propose suitable filter for graph convolution with regards to the graph matching task can be shown that graph convolution solution to the graph signal de-noising problem [24]. Formally, assuming that (I) the ground-truth node features X are smooth w.r.t. graph G with adjacency A and Laplacian L, and that (2) the node feature noise has small magnitude, then the total variation of X should be small by assumption (1), and || X|| be upper-bounded by assumption (2). Thus, we model the problem of recovering the ground-truth signal as:
X arg min Tr X (TLX)
s.L// XII S E1,
(6)
X
It can clearly be observed that X (I aL) "X, where is hyperparameter. This is graph convolution with graph convolution function given by (I+al) +++a) This function can be decomposed as U(I + -A--"U" As well studied in (45] 78, 36). one can see that the filter (I + aA) is decaying, i.e., (\x)) lower for higher A which will mostly reduce the amplitude 2; of graph signals u; belonging to larger eigen-valuse values A₃ Thus, one can conclude that noise corresponds to higher order frequencies vageen- This kind of filter is commonly known
low-pass filter [45. It can be shown that for the 2D graph convolution, filters of the form w(\i, ())))))) g(),)
where (Aa)
(1 ax and h(u,) (1 a1j)) y* will result in 2D low-pass filter well (see Figures 4(a) and 4b)). These filters are referred to as k-hop low-pass filters (aggregating information from the k- k-hop neighborhood of node).
However, in the context of graph matching, graphs are isomorphic when they have the same eigen- value, and in this case we want to align the eigen-vectors since two graphs A and B are isomorphic iff their eigen-vectors are permutations of each other up a sign [72 37].
This leads us to redefine noise in the graph matching context. Given two graphs A and B, with convolution functions MA. Mg whose values matching corresponds to 2D graph signals ž.j u X V æijj uf J JA.VV, such that A + Ul. i.e., eigen-values that differ. Thus, we should use a filter that kills off these signals corresponding to sigen-valuee that do not match. We choose the filter w(A,, My, = (5-15)+1
X; and My respectively, noise in graph
instead of g( (()))l(u;). This filter exactly kills off these signals corresponding to eigen-values that differ (see Figure 4(c) to see an illustration of its action on signals). A note here is that the amplitude and the width of the filter response Figure 4(c) depends on the spectra the graphs to be matched well as For simplicity, we denote this filter as w w(Xi, M3) in the rest of the paper. Thus,
5

---

Algorithm 1: 2D-GEM
1. input An initial correspondence p", UR. Vk, As, Mg, e, maximum iteration iter, and the LMD error {e: [i] thresholds. while S S iler do
2. one round of the 2-Hop algorithm. i.., set = 1 in Algorithm
3. use the LMD to locate well anchored pairs (landmarks)
4. use these well anchored pairs to update the 2D graph spectrum as in
5. use the updated spectrum for updating the correspondence poorly matched points p:
maxp, Tr(P, p Cp), with C in (10)
end while
Algorithm 2: 2-Hop
1. input An initial correspondence P. 2-hop adjacency matrices A2, B2, maximum iteration t. while 0 < do
2. p GW), where W -2
end while
3. return P
noise robust 2D graph convolution based cost matrix for graph matching given as:
C = Σ ( X X.vVv
Morcover, to reduce the time complexity, one may use the first k eigen-values A₁ = diag(A,, As). M2 diag(ut, (&s) and eigen-vectors U2- [u,.... us]. V = [V...... vuJ. instead of the full spectrum. Doing so, the noise robust 2D graph convolution based cost matrix for graph matching becomes:
k Σ uy X
C =
(8)
Due to space constraints, we refer the reader to Appendix D for the experimental validation of the 2D graph convolution approach for graph matching.
4
Our Algorithm
Having formulated the 2D graph convolution-base approach for graph matching as well as redefined noise the context of graph matching, formulate 2D-GEM (2D Graph convolution- based framework for attempting Exact shape Matching) for non-isometric and nearly-isometric 3D shape matching.
4.1 2D-GEM
For our framework, given the xyz coordinates of two shapes Mj and M2, we build suitable point-wise descriptors X and XB. as well as graph laplacians LA and Lg using their triangulations. We then initialize the correspondence using the point-wise descriptors. Then at each iteration, we first follow GRAMPA and update the correspondence using the 2-hop neighborhood graph matching algorithm 84 which makes use of the Greedy Maximum Weight Matching (GMWM) with computational complexity On log n) (see Algorithm 2 and Appendix B The 2-hop adjacency matrices A₂ and 1 and [B2la, = if i and j are 2-hop neighbors, and 0 otherwise. Second, we use the notion of conservation geodesic distances [64] to further constrain 2D-GEM, we capture this via LMD [8]. Finally, we adopt the 2D graph convolution in Equation 8 to filter the correspondence P rather than the feature similarity matrix X, X T in Equation (8), i.e., use P rather than X &
B2 of the shapes Mi and M2. respectively, are such that [Agla,;
our 2D graph signals. This be seen as de-noine noising the correspondence at each iteration following the state-of-the of-th-o-thheart art Kernel-Matching method [2]
In details (see Algorithm [T. we initialize the correspondence via SHOT 70 (though other descriptors and algorithms could also be used as in Appendices D and and then at each iteration (iter):

---

we update the correspondence using the 2-Hop Algorithm with t= 1,
we find / anchor pairs and non non-anchor pairs via LMD (see Section and use them to update the 2D graph spectrum as
Zi = --UUNPP/V
(9)
where U. V& Bixk and P. E / are the digen-vectors and correspondence of the l-anchor pairs (landmarks) found, and Z is the updated k 2D graph spectrum.
we use the updated spectrum for updating the correspondence of poorly matched points as maxp, Tr(P, pPP)) where
C2= = w bu [p].
(10)
and u.lp], vylp E R2 are the eigen-vectors of the non-landmark points p.
Computation complexity. The complexity for computing & leading eigen-vectors of a n X sparse matrix is O(kn log n). The complexity for checking LMD O(n) following DIR [80]
The GMWM has computational complexity of On logn). Thus, our method is of complexity O((ier)n log n) = O(n² 1)gn), since iter is usually small, e.g., 10 or 60 our experiments.
4.2 Local Mapping Distortion (LMD)
Here, describe the LMD employed by 2D-GEM to get landmarks. The LMD was introduced by [80] and [79] for nearly-isometric shapes. Let T MМ + M2 be a map function between two shapes. The LMD of the map I at the point z; is given follows:
(a)) (1)))))
(T:))(x:)
(1I)
ExyEB, (m.) Ai (j)
where =x) M dm, (x. v) < 7 is the geodessic ball of v. Ai is the area element of the mesh of shape M1, and (FT(1.)) Id,, (x. dm, (T()), T(v)) represents pair-wise distance distortion of mapping nearby points 24 and xj to ((x)) and T(x;). A smaller value of (T)) means better map continuity of T the point xi, other words, the local distance at the point 2; is well preserved. Based on the above definition of LMD, one can check that if T is an isometric map. then (z) O, Va MM 7 > O. Conversely, if D,, = 0, Vr M for some y > 0, then T is isometric. We use the LMD to find well matched pairs, i.e., pairs for which S 4, where e, is a threshold. We call them anchor points (landmarks I), and others non-anchor points (poor ppoor-points p). We use the landmarks to update the 2D graph spectrum Sk,, which we use to update the correspondence of non-landmark points (see Section 4.1). It is important to note that at every iteration we gradually decrease the threshold following Xiang et al. 80), and hence not only is the correspondence T updated, but also the landmarks l. For non-isometric shapes we relax this constraint by setting the thresholds 6; arbitrarily large, such as 100 for 2D-GEM in the experiments (see Section 5.5
((:))
4.3 Relationship Between 2D-GEM and Functional Maps
Here show the relationship between 2D GEM and the popular Functional Map (56]. The notion of Functional Maps (56) was introduced in order to solve the notoriously difficult QAP resulting from pair-wise alignment. Funcitonal Map is map between functional spaces P I. (22 - 1.2 (MM2) which can be discretized as an n X n matrix (assuming that each of the shapes Mi and M2 has n
vertices). Given pair of orthonormal basis U [u,,... u,,] and V [vi..... v,J for (M2 and L (M2,, respectively, we have P = USVT, where acts as a basis transformation matrix. On the other hand, recalling 2D-GEM's cost matrix for iteratively de-noising the Permutation matrix in Al Algorithm i.e.
C= Σ w(Ai, M1 J,,
Σ W(N.nH
(12)

---

where 8tj - = This means that one can interpret the matrix S₃ RR** containing the $1,j 's as low-pass approximation of the permutation matrix P in the truncated Laplacian eigen-basis. i.e. P R US V 42 Equation 12) can thus be interpreted as applying a graph matching-suital
filter to the functional map matrix S& (56 42). 2D-GEM | can thus be regarded as denoising the functional map in the graph laplacian basis while enforcing the preservation of neighborhood using 2-hop witnesses (84). as well as ensuring the preservation of geodesic distances (distortions) via the LMD [80]. This interpretation leads to the beautiful connection between the 2D-graph spectrum and the functional map. Essentially they are the same when we take the 2D-graph signals as the columns of the correspondence matrix. As such the 2D-grapi convolution approach is intricately connected to methods such as ZoomOut [54). ICP [4] and BCICP [58), which use the functional map together with the truncated Laplacian eigen-basis basis update the corresonndence P. Moreover, recent works such as Structured Regularization of Functional Map Computations [59]. and DIR [80] tried to address some problems with the traditional functional map approaches (namely, (a) penalizing the functional map update only when it fails to commute with the LBO's of the source and target shapes often fails to produce a good functional map. (b) accumulation of errors in the map update due to poor initial correspondence) by introducing regularizers in the functional map update step, Following these works, 2D-GEM can also be seen framework for further constraining the functional map and the point-wise map updates using the LMD and the 2-hop neighborhood witnesses. Another line of work, namely Fast Sinkhorn Filters [57] tried to explain functional map based approaches as spectral alignment regularized algorithms, and as such, 2D-GEM can also be viewed as spectral alignment regularized algorithm.
5 Experiments
We report experimental results that validate the effectiveness and efficiency of 2D-GEM on exact matching of non-isometric and nearly-isometric 3D shapes.
5.1
Experimental Set-up
Time comparison between 2D-GEM and GRAMPA is conducted in Matlab Windows 10 system with 16GB RAM and Intel(R) i5 11400 CPU @ 2.60-4.4GHz.
5.2 Datasets
We conduct experiments to evaluate the performance of our method on two nearly isometric bench- mark datasets TOSCA [00, and SCAPE [5], as well as a benchmark non-isometric dataset SHREC 16 (TOPKIDS) 42), TOSCA consists of 80 shapes in 8 different categories (human and animal shapes) with vertex numbers ranging from 4k to 50k. SCAPE has 71 shapes (12,500 vertices for each) of the same person with different poses. TOPKIDS contains 25 shapes of the same class with up to 12K vertices, undergoing near-isometric deformations in addition to large topological shortcuts (noise).
5.3 Evaluation Metrics
We use the geodesic error as our error metric 20 Given that the correspondence of an algorithm maps x E MM to y E M2, and the true correspondence maps x to y", the geodesic error is defined as e(x) dMy (u.a") where d'y, denotes the geodesic distance on M2. and diam (M2) is the geodesic
diam(M,))
diameter of M2.
5.4 Baselines
For non-isometric shape matching, i.e., for matching on the TOPKIDS dataset, we compare 2D-GEM
with the following methods: EM [62], GE [1]. RF [61), PFM 600, FSPM 49), Kemnel-Matchin
42], and GRAMPA 20).
For near-isometric shape matching, i.e., for matching on the SCAPE and TOSCA datasets, we
compare 2D-GEM to the following methods: SGMDS12, FM()6), BIMB4 Mobius Best-
Conformal (34. Kernel-Matchin
[42), DIR-500 [80] which uses 500 eigen- vectors, DIR-1000 [80
8

---

FRB
GSARPA
635
61
815
622
M31
OM
BM
607
grodesic ATA
gRodemc 6197
(a) TOPKIDS
(b) SCAPE
(c) TOSCA
Figure 5: Performance comparison on TOPKIDS 5(a)
SCAPE((() and TOSCA 5(c)
which uses 1000 eigen- digeovvectors, and GRAMPA (on SCAPE, not TOSCA due to its time complexity and the fact that 2D-GEM significantly outperforms it as shown on TOPKIDS and SCAPE).
5.5 Parameter Settings
For 2D-GEM, initialize the correspondence by the GMWM SHOT 77), and e: 10 (see Appendix D for more analysis on e). For nearly-isometric shapes (TOSCA and SCAPE), we use 500 eigen-vectors of the LBO. Following Xiang et [80]. we use the second ring neighborhood size for LMD criterion and set the maximum iteration number to iter = 10. We also set the LMD thresholds, we use [0.5280, 0.4560, 0.3840, 0.3120, 0.2400, 0,16 0. 0.1680, 0.1680, 0.1680, 0. 1680. For non-isometric shapes (TOPKIDS), we set the thresholds to 100 for all iterations, use iter 60. and 10 LBO eigen-vectors.
For other baselines, we report their results as reported in their papers i.e., we use their curves. Except for GRAMPA where we re-run using the 2-hop improvement algorithm instead which performs much better than the 1-hop, i.e., the adjacency. For fair comparison with 2D-GEM, we set = 60 for this improvement on GRAMPA.
5.6 Performance Analysis
Comparison on non-isometric shapes. GRAMPA is the state-of-the-an non- noomisometric shape matching method that achieves an excellent performance on exact matching task on the noisy dataset TOPKIDS (Figure ((a)). It achieves 84.6% on this dataset at geodesic error 0. This shows that GRAMPA is very robust noise as expected (note that this performance much higher than the 60% reported in their original paper because used the 2-hop adjacency instead of the 1-hop for refinement as explained in Appendix B.2). However, our method 2D-GEM further outperforms GRAMPA and all other methods, including GRAMPA at geodesic error 0. As reported in Figure 5(a) where 2D-GEM achieves 90.5% accuracy. Moreover, Figures ((a) and 2(b) show that 2D-GEM significantly faster than GRAMPA since 2D-GEM only needs compute subset of the digen-vectorn
unlike GRAMPA which needs the whole spectrum and thus has a complexity of (n²²).
Comparison on nearly-isometric shapes. DIR is the state-of-the-art model for pearly-isometriy shape matching. DIR outperforms all the other baselines except 2D-GEM. The better DIR-1000 using 1000 cigen-vectors achieves 69.5% accuracy at geodesic error 0 on SCAPE, and 59.8% accuracy geodesic error 0 TOSCA. Using the LMD proposed for the DIR model by Xiang et [80] for extra constraints on 2D-GEM, 2D-GEM not only generalizes to nearly-isomerric shapes, but achieves the state-of-tie of-te-of-the-ar results using only 500 vector, outperforming even DIR-1000. 2D-GEM achieves 92.5% accuracy (outperforming DIR-1000 1000 by more than 40%) at geodesic error 0 on the TOSCA dataset, as well as 84.9% accuracy on the SCAPE dataset (outperforming DIR- 1000 by almost 20%) Note that these 2D-GEM's accuracy improves using more eigen-vectors or increasing iter, but this also increases the running time. Moreover, 2D-GEM's gain over GRAMPA (the state-of- the-art non-isometric shape matching method) can also be seen to extend to nearly-isometric shapes. As noted earlier in Section| GRAMPA does not generalize to nearly-isometric shapes since the
Ablation studies GD-GEM in Appendix E Code at: https://giit comm/Barraeeel/anssu/220-00

---

assumptions for nearly-isometie shape matching are different from those of non non-sometric shape matching given that isometries preserve geometric properties which are lost by non-isometries. This is seen by its poor performance on the SCAPE dataset (Figure 5(b) where even for exact matching. i.e. at geodesic error O, only achieves around 10%). contrast, 2D-GEM (using the LMD for extra constraints) generalizes to nearly-isometric shapes and achieves the state-of-the-art performance. We do not attempt to use the LMD on GRAMPA since (1) not clear how to use GRAMPA in an iterative way it is usually only used an initialization for other algorithms (see Appendix B). (2) 2D-GEM outperforms GRAMPA even without the LMD as shown on the noisy TOPKIDS dataset (Figure 5(a), and (3) GEM with or without the LMD is still faster than GRAMPA without the LMD (see Figures ((a) and 2(b)
5.7
Limitations of 2D-GEM
There are three main limitations to this work. First, for nearly-isometric shapes (shown in Faa) 2D-GEM sometimes produces maps that are not continuous (smooth), though much more accurate than the other baselines. Second, although the time complexity O(n² log n)) of 2D-GEM is much lower than the (n²) of GRAMPA, it much worse than the (n log n) of other methods such as ZoomOut and DIR. Lastly, unlike GRAMPA, we do not provide rigorous theoretical exact recovery guarantees for 2D-GEM on random graph matching.
6 Conclusions
We presented how the 2D graph convolution could be used for graph matching, Using this 2D graph convolution, we re-defined noise the context of graph matching and proposed a model (2D-GEM) that addresses the task of exact 3D shape matching on nearly-isometric datasets. We then showed that 2D-GEM significantly outperforms existing methods on both non-isometric shapes and nearly-isometric shapes. For future work, we propose to address two key limitations of 2D-GEM, i.e., further reducing the time complexity of O(n log and providing theoretical guarantees its exact recovery performance. Moreover, we also propose to explore the generalization of 2D-GEM for correspondence tasks that allow using graph representation such partial shape matching, image matching, and network de-anonymization Besides, it is also promising to consider the potential distribution shifts [12), as well as the optimization trade-offs [3
non-isometric (noisy) datasets well as
Broader Impact
Given that our method needs no training, is unsupervised and based on intrinsic shape properties, it can positively benefit the industry and society as a whole in that; (a) it may be easily generalized, and most importantly (b) it needs no human labels training, which can help reduce the cost and time taken for the shape correspondence problems in different crucial fields such as medicine, and computer graphics.
8 Acknowledgements
We thank the reviewers for their valuable comments. This work was partially supported by GRF 14208318 from the RGC of HKSAR and the CUHK direct grant 4055146. Lin Zhang and Bo Li were supported in part by RGC RIF grant R6021-20 and RGC GRF grant under contracts 16209120 and 16200221. Bo Han was supported by NSFC YSF No. 62006202, RGC ECS No. 22200720, and Guangdong Basic and Applied Basic Research Foundation No. 2022A1515011652.
References
[1] Yonathan Aflalo, Alexander Bronstein, and Ron Kimmel. On convex relaxation of graph isomorphism. Proceedings of the National Academy of Sciences, 112(10):2922-2447, 2015. ISSN 0027-8424. doi: 10. 10.1073/pnas. 1401651112.
[2] Yonathan Aflalo, Anastasia Dubrovina, and Ron Kimmel. Spectral generalized multi- dimensional scaling. International Journal of Computer Vision, 118:380-392, 2016.
10

---

[3] H.A. Almohamad and S.O. Duffuaa. A linear programming approach for the weighted graph matching problem. IEEE Transactions on Pattern Analysis and Machine Intelligence, 15(5): 522-525, 1993. doi: 10. 19.1109/3..21144.
[4] B. Amberg, S. Romdhani, and T. Vetter. Optimal step nonrigid iep algorithms for surface registration. In 2007 IEEE Conference on Computer Vision and Pattern Recognition, pages 1 1-8, June 2007.
[5] Dragomir Anguelov, Praveen Srinivasan, Hoi-Cheung Pang, Daphne Koller, Sebastian Thrun, and James Davis. The correlated correspondence algorithm for unsupervised registration of nonrigid surfaces. In Advances in neural information processing systems, pages 33 40. 2005.
[6] Mathieu Aubry, UIrich Schlickewei, and Daniel Cremers. The wave kernel signature: A quantum mechanical approach to shape analysis. In 20/ IEEE International Conference on Computer Vision Workshops (ICCV Workshops), pages 1626-1633, 2011. doi: 10.110WC 2011.6130444.
[7] László Babai, D. Yu. Grigoryev, and David M. Mount. Isomorphism of graphs with bounded eigenvalue multiplicity. In Proceedings of the Fourteenth Annual ACM Symposium on Theory of New York, NY, USA, 1982. Association for Computing Machinery. ISBN 0897910702. doi: 10. (0.114/800070.802200
Computing. STOC '82, page 310-324,
[8] Yunsheng Bai, Hao Ding, Yizhou Sun, and Wei Wang. Convolutional set matching for graph similarity. In NeurlPS Workshop on Relational Representation Learning, 2018.
[9] Yunsheng Bai, Haoyang Ding, Song Bian, Ting Chen, Yizhou Sun, and Wei Wang. Simgnn: A neural network approach to fast graph similarity computation. Proceedings of the Twelfth ACM International Conference Web Search and Data Mining, 2019.
[10] Alexander M Bronstein. Michael M Bronstein, and Ron Kimmel. Numerical geometry of non-rigid shapes. Springer Science & Business Media, 2008
[11] M. M. Bronstein and Kokkinos. Scale-invariant heat kernel signatures for non-rigid shape recognition. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 1704-1711, 2010.
[12] Yongqiang Chen, Yonggang Zhang, Yatao Bian, Han Yang, Kaili Ma, Binghui Xie, Tongliang Liu, Bo Han, and James Cheng. Invariance principle meets out-of-distribution generalization on graphs. arXiv preprint arXiv:2202.05441 2022.
[13] Yonggiang Chen, Kaiwen Zhou, Yatao Bian, Binghui Xie, Kaili Ma, Yonggang Zhang, Han Yang, Bo Han, and James Cheng. Pareto invariant risk minimization. arXiv preprint 220.::2200.07766,, 2022.
[14] Donatello Conte, Pasquale Foggia, Carlo Sansone, and Mario Vento. Thirty years of graph match- ing in pattern recognition. IJPRAI, 18:265-298, 05 2004. doi: 10.1142/5021800 4040003228
[15] Chris Ding, Tao Li, and Michael I. Jordan. Nonnegative matrix factorization for combinatorial optimization: Spectral clustering, graph matching, and clique finding. In 2008 Eighth IEEE International Conference on Data Mining, pages 183-192, 2008. doi: 10. 1091109/00MM
[16] Jian Ding, Zongming Ma, Yihong Wu, and Jiaming Xu. Efficient random graph matching via degree profiles. Probability Theory and Related Fields, 179:29-115, 2020.
[17] B. Douglas. The weisfeiler-lchman method and graph isomorphism testing. arXiv: Combina- torics, 2011.
[18] Nadav Dym, Haggai Maron, and Yaron Lipman. Ds++: A flexible, scalable and provably tight relaxation for matching problems. ACM Trans. Graph., 36(6), November 2017. ISSN 0770-0301. doi: 10. 145/31 13000003000000080
[19] Frank Emmert-Streib, Matthias Dehmer, and Yongtang Shi. Fifty years of graph matching, network alignment and network comparison. Information Sciences, 1477 02 2016. doi: 10.1016/ 2016.00.
11

---

[20] Zhou Fan, Cheng Mao, Yihong Wu, and Jiaming Xu. Spectral graph matching and regularized quadratic relaxations: Algorithm and theory. In Hal Daumé III and Aarti Singh, editors, Proceed- ings of the 37th International Conference Machine Learning, volume 1 119 of Proceedings of Machine Learning Research, pages 2985-2995, PMLR, 13-18 Jul 2020.
[21] Soheil Feizi, Gerald Quon, Mariana Recamonde-Mendorde Muriel Medard, Manolis Kellis, and Ali Jadbabaie. Spectral alignment of graphs. IEEE Transactions on Network Science and Engineering, (13):1182-11 1197, jul 2020. ISSN 2327-4697. doi: 10. 10.1199/TSEE.22199912222.
[22] Matthias Fey, Jan E. Lenssen, Christopher Morris, Jonathan Masci, and Nils M. Kriege. Deep graph matching consensus. In International Conference on Learning Representations, 2020.
[23] Gerd Finke, Rainer E. Burkard, and Franz Rendl. Quadratic assignment problems. In Silvano Martello, Gilbert Laporte, Michel Minoux, and Celso Ribeiro, editors, Surveys in Combinatorial Optimization, volume 132 of
Mathematics Studies, pages 61-82. North-Holland, 1987. doi: https://doi.org/ 10. (06650000002088088733333333
[24] Guoji Fu, Yifan Hou, Jian Zhang, Kaili Ma. Barakeel Fanseu Kamhoua, and James Cheng. Understanding graph neural networks from graph signal denoising perspectives. ArXiv, abs/2006.04386, 2020.
[25] S. Gold and A. Rangarajan. A graduated assignment algorithm for graph matching. IEEE Transactions on Pattern Analysis and Machine Intelligence, 18(4):377-388 1996. doi: 10.1109/ 34.491619.
[26] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in neural information processing systems, pages 1024-1034, 2017.
[27] Mark Heimann, Haoming Shen, Tara Safavi, and Danai Koutra. Regal: Representation learning- based graph alignment. In Proceedings of the 27th ACM International Conference on Infor- mation and Knowledge Management, CIKM '18, page 117-126, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 97814503600 42. doi: 10. 00011444/262226327777788
[28] Ruqi Huang, Jing Ren, Peter Wonka, and Maks Ovsjanikov. Consistent zoomout: Efficient spectral map synchronization. In Proc. SGP, volume 39, 2020.
[29] Barakeel Fanseu Kamhoua, Lin Zhang, Kaili Ma, James Cheng, Bo Li, and Bo Han. Hyper- graph convolution based attributed hypergraph clustering. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, 2021.
[30] Barakeel Fanseu Kamhoua, Lin Zhang, Kaili Ma, James Cheng, Bo Li, and Bo Han. Grace: general graph convolution framework for attributed graph clustering. ACM Trans. Knowl. Discov. Data jun 2022. ISSN 1556-4681. doi: 10.1 145/3544477
org/
10. 1445/44775447 Just Accepted.
[31] Ehsan Kazemi and Matthias Grossglauser. On the structure and efficient computation of isorank node similarities. ArXiv, abs/1602.00668, 2016.
[32] Ehsan Kazemi, Seyed Hamed Hassani, M. Grossglauser, and H. Modarres. Proper: global protein interaction network alignment through percolation matching. BMC Bioinformatics, 17, 2016.
[33] Itay Kezurer, Shahar Z. Kovalsky, Ronen Basri, and Yaron Lipman. Tight relaxation of quadratic matching. Computer Graphics Forum, 34(5): 15-128, 2015. doi: https://doi.or//11 1 1/cgf. 12701.
[34] Vladimir G. Kim, Yaron Lipman, and Thomas Funkhouser. Blended intrinsic maps. ACM Trans. Graph., 30(4), July 2011. ISSN 0730-0301. doi: 10.1145/2010324.1996 1964974.
[35] Thomas N Kipf and Max Welling. Variational graph auto-encoders. NIPS Workshop on Bayesian Deep Learning, 2016.
[36] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference Learning Representations (ICLR), 2017.
12

---

[37] Stefan Klus and Tuhin Sahai. A spectral assignment approach for the graph isomorphism problem. ArXiv, abs/1441.0969,, 2014.
[38] Oliver Koch, Nils M. Kriege, and Lina Humbeck. Chemical similarity and substructure searches. In Encyclopedia of Bioinformatics and Computational Biology 2019.
[39] Giorgos Kollias, Shahin Mohammadi, and Ananth Grama. Network similarity decomposition (nsd): A fast and scalable approach to network alignment. IEEE Transactions Knowledge and Data Engineering, 24(1)):2232
2012. doi: 10. 10.1 109/199KDE.201111722
[40] Danai Koutra, Hanghang Tong, and David Lubensky. Big-align: Fast bipartite graph alignment. In 2013 IEEE 13th International Conference on Data Mining, pages 389-398, 2013. doi: 10.1 (009///MM.221..1.
[41] Z. Lähner, E. Rodolà, M. M. Bronstein, D. Cremers, O. Burghard, L. Cosmo, Dieckmann, R. Klein, and Y. Sahillioğlu. Matching of deformable shapes with topological noise. In Proceedings of the Eurographics 2016 Workshop on 3D Object Retrieval, 3DOR '16, page 55-60, Goslar, DEU, 2016. Eurographics Association. ISBN 9783038680048.
[42] Zorah Lähner, Matthias Vestner, Amit Boyarski, Or Litany, Ron Slossberg, Tal Remez, Emanuele Rodolà, Alexander M. Bronstein, Michael M. Bronstein, Ron Kimmel, and Daniel Cremers. Efficient deformable shape correspondence via kernel matching. 2017 International Conference on 3D Vision (3DV), pages 517-526, 2017.
[43] M. Leordeanu and M. Hebert. A spectral technique for correspondence problems using pairwise constraints. In Tenth IEEE International Conference on Computer Vision (ICCV'05) Volume I, volume 2, pages 482-14499 Vol. 2, 2005. doi: 10.1 1 109/ICCV.2005.20.
[44] Marius Leordeanu. Spectral Graph Matching, Learning, and Inference for Computer Vision. PhD thesis, Carnegie Mellon University, Pittsburgh, PA, July 2009.
[45] Qimai Li, Xiao-Ming Wu, Han Liu, Xiaotong Zhang, and Zhichao Guan. Label efficient semi- supervised learning via graph filtering. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition, pages 9582-9591, 2019.
[46] Qimai Li, Xiaotong Zhang, Han Liu, Quanyu Dai, and Xiao-Ming Wu. Dimensionwise separable 2-d graph convolution for unsupervised and semi-supervised learning on graphs. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD '21, page 953-963, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781 450383325. doi: 10. (0.1145/4445448.44777
[47] Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli. Graph matching networks for learning the similarity of graph structured objects. In ICMI, 2019.
[48] Yaron Lipman and Thomas Funkhouser. Möbius voting for surface correspondence. ACM Trans. Graph., 28(3), July 2009. ISSN 0730-0301. doi: (0.1145/1331326.5511777
[49] O. Litany, F. Rodolà, A. M. Bronstein, and M. M. Bronstein. Fully spectral partial shape matching. Computer Graphics Forum, 36(2):247-258, 2017. doi: https://doi.or//10.1 1/egf. 13123.
[50] Jingen Liu, Jiebo Luo, and Mubarak Shah. Recognizing realistic actions from videos "in the wild". In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pages 1996-2003, 2009. doi: D..1099CCVPR.220952007444
[51] Vince Lyzinski, Donniell E. Fishkind, and Carey E. Priebe. Seeded graph matching for correlated erdös-rényi graphs. J. Mach. Learn. Res., 1511:335330 January 2014. ISSN 1532-4435.
[52] Vince Lyzinski, Donniell E. Fishkind, Marcelo Fiori, Joshua T. Vogelstein, Carey E. Priebe, and Guillermo Sapiro. Graph matching: Relax at your own risk. IEEE Transactions on Pattern Analysis and Machine Intelligence, 38(1):60-75) 73,60----777 2016. doi: 10. 2000:TPAM..201..2222222
[53] Riccardo Marin, Simone Melzi, Emanuele Rodolà, and Umberto Castellani. Farm: Functional automatic registration method for 3d human bodies. Comput. Graph. Forum, 3901):66-1173, 2020. URLhtttpa :/ttsp:://doi.oo org 10. 1111/cgf..... 13751
13

---

[54] Simone Melzi, Jing Ren, Emanuele Rodolà, Abhishek Sharma, Peter Wonka, and Maks Ovs- janikov. Zoomout: Spectral upsampling for efficient shape correspondence. ACM Transactions on Graphics (TOG), 38(6): 155, 2019.
[55] Maks Ovsjanikov. Jian Sun, and Leo Guibas. Global intrinsic symmetries of shapes. Comp. Graph. Forum, 27( 1341-1388, 2008.
[56] Maks Ovsjanikov, Mirela Ben-Chen, Justin Solomon, Adrian Butscher, and Leonidas Guibas. Functional maps: A flexible representation of maps between shapes. ACM Trans. Graph., 31)),, July 2012. ISSN 0730-0301. doi: 10. 10.214422835 218552.
[57] Gautam Pai, Jing Ren, Simone Melzi, Peter Wonka, and Maks Ovsjanikov. Fast sinkhorn filters: Using matrix scaling for non-rigid shape correspondence with functional maps. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 384-393, June 2021.
[58] Jing Ren, Adrien Poulenard, Peter Wonka, and Maks Ovsjanikov. Continuous and orientation- preserving correspondences via functional maps. ACM Trans. Graph., 37(6), dee 2018. ISSN 0730-0301. doi: 10. 10.1144/772222.3275504
[59] Jing Ren, Mikhail Panine, Peter Wonka, and Maks Ovsjanikov. Structured regularization of functional map computations. Comput. Graph. Forum, 38(5):39-53, 2019. doi: 10.11 l/cgf.
13788. URL http::/::
org/10../... 1111/cgf.f... 13788
[60] E. Rodolà, L. Cosmo, M. M. Bronstein, A. Torsello, and D. Cremers. Partial functional correspondence. Comput. Graph. Forum, 36(1):222-23) 236, January 2017. ISSN 0167-7055. doi: 10.11 http//ffff.2799..
[61] Emanuele Rodolà, Samuel Bulò, Thomas Windheuser, Matthias Vestner, and Daniel Cremers. Dense non-rigid shape correspondence using random forests. In 2014 IEEE Conference on Computer Vision and Pattern Recognition, pages 4177-4184, 2014. doi: 10.1109/CVPR.2014,
532.
[62] Yusuf Sahillioglu and Yücel Yemez. Minimum-dissortion isometric shape correspondence using em algorithm. IEEE Transactions on Pattern Analysis and Machine Intelligence, 34(11); 2203-2215, 2012. doi: 10.1 10.1109/PAM1..202..22
[63] Aliaksei Sandryhaila and José M. F. Moura. Discrete signal processing on graphs. IEEE Transactions on Signal Processing, 6147))1644-1656, 2013. doi: 10.1109/TSPP22132223399
[64] Gil Shamai and Ron Kimmel. Geodesic distance descriptors. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), July 2017.
[65] Tianjia Shao, Wilmot Li, Kun Zhou, Weiwei Xu, Baining Guo, and Niloy J. Mitra. Interpreting concept sketches. ACM Trans. Graph., 32(4), July 2013. ISSN 0730-0301. doi: 10.1145/ 2461912.246200..
[66] Roded Sharan and Trey Ideker. T. modeling cellular machinery through biological network comparison, nat. biotechnol. 24, 427-433. Nature biotechnology. 24:427-33, 05 2006. doi: 10. 10.1038/nbtt199 196.
[67] D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega, and P. Vandergheynst. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE Signal Processing Magazine, 00(3):83-98, 2013. doi: 10.1 109/MSS22012.2231122
[68] Rohit Singh, Jinbo Xu, and Bonnie Berger. Global alignment of multiple protein interaction networks with application to functional orthology detection. Proceedings of the National Academy of Sciences of the United States of America, 105:12763 8, 10 2008. doi: 10.1073/ 105..0806622105.
[69] Justin Solomon, Andy Nguyen, Adrian Butscher, Mirela Ben-Chen, and Leonidas Guibas. Soft maps between surfaces. Comput. Graph. Forum, 316))161771666 August 2012. ISSN 0167-7055. doi: 10. 11111/11477865922001111
14

---

[70] Federico Tombari, Samuele Salti, and Luigi Di Stefano. Unique signatures of histograms for local surface description. In European conference on computer vision, pages 356-369, Springer, 2010.
[71] Huynh Thanh Trung, Tong Van Vinh, Nguyen Thanh Tam, Hongzhi Yin, Matthias Weidlich, and Nguyen Quoe Viet Hung. Adaptive network alignment with unsupervised and multi-order convolutional networks. In 2020 IEEE 36th International Conference on Data Engineering doi: 10.1 (09/CCDE43007 2000488077..20000005
(ICDE), pages 85-96, 2020.
[72] S. Umeyama. An eigendecomposition approach to weighted graph matching problems. IEEE Transactions on Puttern Anulysis and Machine Intelligence, 10(5):695-703, 1988. doi: 10. 109/ 34.6778.
[73] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. International Conference on Learning Representations, 2018. accepted as poster.
[74] Mario Vento and Pasquale Foggia. Graph matching techniques for computer vision. Graph- Based Methods in Computer Vision: Developments and Applications, 1:1-41, 01 2012. doi: 10.4018/978- 1-4666- 1891-6.ch001.
[75] Chun Wang, Shirui Pan, Ruiqi Hu, Guodong Long, Jing Jiang, and Chengqi Zhang. Attributed graph clustering: deep attentional embedding approach. In Proceedings of the Twenty- Eighth International Joint Conference on Artificial Intelligence, pages 6670-3676, 2019. doi:
[76] Runzhong Wang, Junchi Yan, and Xiaokang Yang. Learning combinatorial embedding networks for deep graph matching. 2019 IEEE/CVF International Conference on Computer Vision (ICCV), Oct 2019. doi: 10.11099iccc.2011.0033..
[77] Zhichun Wang, Qingsong Lv, Xiaohan Lan, and Yu Zhang. Cross-lingual knowledge graph alignment via graph convolutional networks. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 349-3---30033 -57,, Brussels, Belgium, 2018. Association for Computational Linguistics. doi: 10.18653/v 1/11-- 1032.
[78] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In Proceedings of the 36th International Conference on Machine Learning, pages 6861-6871. PMLR, 2019.
[79] Rui Xiang, Rongjie Lai, and Hongkai Zhao. Efficient and robust shape correspondence via sparsity-enforced quadratic assignment. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9513-9522, 2020.
[80] Rui Xiang, Rongjie Lai, and Hongkai Zhao. A dual iterative refinement method for non-rigid shape matching. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 15930-15939, June 2021.
[81] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference Learning Representations, 2019.
[82] Lei Xu and Irwin King. A pea approach for fast retrieval of structural patterns in attributed graphs. IEEE transactions on systems, man, and cybernetics. Part B, Cybernetics: a publication of the IEEE Systems, Man, and Cybernetics Society, 31:812-7, 02 2001. doi: 10.1109/3477.95644.
[83] Lyudmila Yartseva and Matthias Grossglauser. On the performance of percolation graph matching. In COSN '13, 2013.
[84] LIREN YU, Jiaming Xu, and Xiaojun Lin. Graph matching with partially-correct seeds. J. Mach. Learn, Res,, 22:280:1-2800 2021.
[85] Andrei Zanfir and Cristian Sminchisescu. Deep learning of graph matching. In 2018 IEEF/CVF Conference on Computer Vision and Pattern Recognition, pages 2684-2693, 2018. doi: 10. 1109/CVPR 20 8.00244.
15

---

[86] Jiawei Zhang and Philip S. Yu. Multiple anonymized social networks alignment. In 2015 IEEE International Conference on Data Mining, pages 599-608, 2015. doi: 10.1109// 2015..11.11114
[87] Xiaotong Zhang, Han Liu, Qimai Li, and Xiao-Ming Wu. Attributed graph clustering via adaptive graph convolution. In IJCAI, 2019.
[88] Zhen Zhang and Wee Sun Lee. Deep graphical feature learning for the feature matching problem. In 2019 IEEE/CVF International Conference on Computer Vision (ICCV), pages 5086-5095, 2019. doi: 10. N0.119///CCV2211.00055
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes] see Sections 3 5 and Appendix D
(b) Did you describe the limitations of your work? [Yes] see Section 5.7
(c) Did you discuss any potential negative societal impacts of your work? [Yes] see
Section 7
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] see Sections
2.2 and Appendix C
(b) Did you include complete proofs of theoretical results? [Yes] see Sections listed in Question 2 (a) above.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material URL)? [Yes] see code in
supplementary material
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] see Section 5.5 amd Appendix [
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] see Section [5.]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] see Section 5.3 and Appendix [.4
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either the supplemental material as URL? [Yes] see code in supplementary material
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [Yes] see Section [5.3aand Appendix [.4]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
16


Reviews:
[{"review_id": "uVzdesfezH", "reviewer": "Reviewer_Y9CP", "summary": "The paper presents a graph matching method using 2D graph convolution. In articular, the proposed method is designed to achieve better accuracy for extract shape matching. The method can be applied to both noisy non-isometric data and nearly-isometric shapes. Evaluations show that the proposed method achieves state of the art performance. ", "questions": "- How sensitive is 2D-GEM to the correspondence initialization? \n- As mentioned, GRAMPA is normally used as initialization, how does 2D-GEM perform if initialized with GRAMPA, instead of using SHOT with GMWM?\n- 2D-GEM could use point features, does this help on SCAPE or TOPKIDS? Intuitively, pointwise features are potentially more noisy than pairwise features? \n- The ablation on non-isometric shapes in Appendix E.2 shows that 2-Hop algorithm is as good as 2D-GEM. I found this disturbing as this effectively invalid the contributions of 2D-GEM. Similarly, in near-isometric case, it seems that LMD is the most important module for the performance gain.   ", "limitations": "- Lack of theoretical support for good performance for exact shape matching. \n- The proposed method borrows various techniques from previous methods in order to tackle both isometric and non-isometric case. It achieves the state of the art performance, but it is clear that these performance gain are not due to the 2D Convolution.   \n", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Shape matching in 3D has been well studied. The paper tackles the case for exact matching, in which previous methods don't perform well. \n- The quality of the evaluation is good. Comparisons to competing methods and self ablations are extensive. \n- The proposed algorithm include multiple steps involving various components, though the authors could well deliver the essential concepts. Notably, the relation between 2D-GEM and GRANMPA helps to understand the novelty.  \n\nWeaknesses:\n- Lack of theoretic foundations, it is not clear why the proposed method achieve excellent performance for exact matching on the selected datasets.\n- Comparing to related works, the proposed pipeline has high similarity with GRAMPA [18], in terms of the use of cost function, 2-hop improvement, etc. LMD [73] is borrowed to adapt to near-isometric case.   ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "YlbQLP-WNit", "reviewer": "Reviewer_HJ7U", "summary": "This paper proposes a novel method for exact shape correspondence based on 2D graph convolution. The main idea is to adapt graph convolution and signal denoising on graphs to the task of shape matching. The proposed pipeline exploits a specific filter inspired by isomorphic graph matching to achieve this goal. The matching results both in the case of near-isometric and non-isometric shapes are accurate. The timing is comparable to and generally faster than the most similar competitors. Furthermore, it reaches a more significant percentage of points for which the geodesic error is 0 compared to alternative approaches.", "questions": "1 - Why, in line 164, is the text referring to z_{i,j} while the discussion is on a single graph and its filter g? It should be z_i, or am I missing anything?\n\n2 - Is Figure 4 (c) generated on two isomorphic graphs? From the shape of the filter, it seems to be the case. If it is the case, it should be reported at least in the caption because this filter is dependent on the graphs (the spectra).\n\n3 - The functional map framework [51] proposes a constraint for shape matching (commutativity with the Laplacian) that corresponds to a mask at least similar to the one suggested as a spectral filter in this paper. The recent work \"Structured Regularization of Functional Map Computations\" by J. Ren et al. (SGP 2019) provides more details on this constraint. Can be any further connection analyzed?\n\n4 - What is the quality of the initialization provided by the proposed pipeline? Adding the evaluation of the initialization (both quantitatively to the curves and qualitatively to the images) will provide a general idea of its quality and highlight the contribution of the proposed pipeline.\n\n5 - Selecting the threshold equal to 100 in the LMD for non-isometric pairs is similar to deactivating this step in the procedure. Is it correct? Or, with this threshold, is the LMD procedure removing any (probably few) matches with a huge error? This last claim seems confirmed by the ablation study in Figure 7 case (3), but this discussion should appear in the main paper.", "limitations": "I do not see any potential negative societal impact. The limitations listed by the authors give a complete analysis of the open problems in the proposed approach. One possible missing scenario is the one in which the two shapes have a completely different discretization. SHREC19 \"Matching Humans with Different Connectivity\" is a possible benchmark to evaluate the performance of the proposed method in this specific case.\nMoreover, some more challenging settings can be discussed, such as partialities, point clouds, and noisy data from real acquisitions. In these cases, where geodesic constraints ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The connection between 2D graph convolution and shape matching is interesting.\n- The paper provides all the necessary background to understand the proposed idea.\n- The performance on the datasets involved in the evaluation is good, and the proposed pipeline improves the state-of-the-art of the competitors considered without training and ground truth data.\n\nWeaknesses:\n- Section 4 is not easy to follow. An image of the pipeline with a visualization of the different steps can help improve the text's clarity.\n- I am not sure about the novelty of the 2D graph convolution as a filter for shape matching. Section 3 should start with a more explicit and precise statement about the originality. Furthermore, a more comprehensive discussion about the connection with related works is missing in the current version. The paper can benefit from a specific paragraph on this discussion that highlights the novelty of the proposed method but in comparison to existing techniques.\n- The pipeline proposed in Section 4 seems a bit incremental. It is given by SHOT+GMWM+[LMD]+refinement. The last part (the last step of the procedure from Algorithm 1) appears to be the main contribution of this paper. If I am not missing something, the first part of the complete pipeline can be composed of existing methods with some modifications on the choice of the parameters to target different settings. This discussion does not invalidate the submission, but the current version of the manuscript should be modified accordingly if correct. If I am wrong, the current version requires a more detailed motivation on the selected solution for step 1,2,3,4 in the Algorithm to clarify why all the procedure is a valid contribution from this work.\n\nSome minor points:\n- In line 113, adding a reference to the normalized symmetric Laplacian at the beginning of section 2 can make the paper self-contained.\n- In line 167, \\mu_i should be \\mu_j.\n- In Figure 4, fewer values on the x and y axes can make the figure clearer.\n- Around line 178, a description of e should be given. From the caption of Figure 4 and section 5, it is possible to deduce that it is a real number (positive? integer?), but it could help to have it explicitly defined in the text.\n- Reference [53] contains a typo: Rodolì should be Rodolà.\n- The text in Figure 2 is too small. The quality of this figure should be improved by using a tikz file or other alternatives. Same for Figures 3 and 5. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "UkeZHBuL3EA", "reviewer": "Reviewer_NtNA", "summary": "This paper proposes a new shape matching method called 2D-GEM, based on 2D graph convolution. The method is straight forward: at each iteration, (1) first find a set of reliable correspondences with small enough local smoothness error (called LMD); (2) use these reliable correspondences to compute/update a k-by-k graph spectrum; (3) use the updated graph spectrum to compute the correspondences for poorly matched points. \n\nThe proposed method achieves the state-of-the-art performance on shape matching on SHREC'16 TOPKIDS dataset and original FAUST/TOSCA dataset; and on graph matching on Erdos Regny random graphs.", "questions": "- As mentioned above, what's the performance of the proposed method on remeshed FAUST/SCAPE with SHOT initialization and other types of initializations (e.g., wave kernel signatures). \n- What's the key difference between 2D-GEM and \"Fast Sinkhorn Filters\": it seems both methods formulate the matching problem as a linear assignment in the spectral space. (of course, 2D-GEM uses a specially chosen filter and only update the correspondences between non-anchor points) it would be nice to know the critical differences in formulation and it might be better to include such a discussion, since: (1) the  2D graph spectrum computed in Eq.(9) seems to be equivalent to computing a functional map using the anchor points correspondences; (2) the correspondences updating in Eq. (10) seems similar to the linear assignment based on the computed functional map formulated in the Fast Sinkhorn Filters. \n- How are the thresholds in L272 chosen? The scales of the thresholds used for different datasets are very different. Is the algorithm sensitive to thresholds?\n- What are the heuristics to choose the number of LBO? Why it is enough to use 10 LBO for TOPKIDS, but 500 LBO for FAUST/SCAPE? Does the algorithm work for 10 LBO for FAUST/SCAPE dataset? Also why 500 LBO is used for the ablation study on TOPKIDS while 10 LBO is used for generating results?", "limitations": "The limitations are adequately addressed. However, it might be worth mentioning the parameter tuning as well since it seems non-trivial. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Clarity*: \n- (++) the paper is well written and easy to follow. The provided code also helps to better understand the algorithm. \n\n*Originality*\n- (++) The proposed method 2D-GEM is a generalization of the GRAMPA method: the mesh Laplacian is used instead of the graph adjacency; it can also incorporate per-vertex features; a different filter is used.  \n- (--) comparison to GRAMPA: though the differences between 2D-GEM and GRAMPA are briefly discussed in Appendix B.3., the novelty seems to be limited. For example, though 2D-GEM is generalized to handle per-vertex features, in the real algorithm, no features are used. Specifically, as described in L205, the correspondence P is used as graph signals (instead of the pre-built descriptors XaXb). It sounds like the newly introduced feature is useless. Also according to the ablation study, the most important or performance-dominant part of the algorithm is the 2-hop initialization, which is proposed by Yu et. al. [77].\n\n*Quality*\n- (++) 2D-GEM achieves higher accuracy on TOPKIDS/FAUST/TOSCA with initializations computed from SHOT descriptors. \n- (++) 2D-GEM is faster than GRAMPA since in each iteration not all vertices are updated, which leads to less and less number of non-anchor points for linear assignment\n- (--) It has been known that the SHOT descriptors can overfit to the uniform triangulation as used in the original FAUST/SCAPE dataset (For example, see discussion in \"DiffusionNet: Discretization Agnostic Learning on Surfaces\"). A more convincing justification would be testing the algorithm (and all the baselines) on remeshed or resampled dataset with different types of initializations (as done in ZoomOut [49]). \n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "3_AgxR74yk", "reviewer": "Reviewer_aRMb", "summary": "The paper proposes a shape-correspondence approach based on combined  spectral-domain filtering of the Laplace-Beltrami operators and the feature assignment in the corresponding spectral embedding space. The ideas per se are not new, but what I believe made a big difference is the adoption of the joint spectral filter $\\omega(\\lambda_i,\\mu_j,e)$ that kills the signal associated to corresponding eigenvalues that are different from one another, thus not using noisy eigenfunctions in the spectral embedding.", "questions": "It might be interesting to learn the joint spectral filter.", "limitations": "Negative societal impacts have not been mentioned, but apart from the use in a futuristic 3D surveillance system, I cannot see one myself.\nThe authors are honest about the extraction of non-smooth solutions, but I think the phenomenon warrants a more in-depth analysis/explanation.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Very strong experimental results\nvery nice idea of adopting the joint spectral filter which I really believe is the key to the performance.\n\nThe paper sees to want to reinvent spectral filtering on graphs and linear assignment on the spectral embedding space with slightly different names.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept