# An Application of Manifold Learning in Global Shape Descriptors
## 2 Background
### Spectral Shape Analysis  
The _Laplace-Beltrami operator_\(\Delta\) is a linear differential operator defined on the differentiable manifold \(\mathcal{M}\) as the divergence of the gradient of a function \(f\) in the following form [20; 30]:  
\[\Delta f=div(grad(f)). \tag{1}\]  
[PERSON] [31] noted that the eigenfunctions \(\phi_{i}\) of the continuous LB operator, which are the solution to the following _Laplacian eigenvalue problem_,  
\[\Delta f=-\lambda f \tag{2}\]  
are _the orthogonal_ basis for the space of functions defined on the surface of a manifold. In other words, a function \(f\) on the surface can be expressed as a sum over coefficients of these infinite bases:  
\[f=c_{0}\phi_{0}+c_{1}\phi_{1}+...\]  
Furthermore, the LB operator is positive semi-definite, having non-negative eigenvalues \(\lambda_{i}\) that can be sorted as follows:  
\[0\leq\lambda_{1}\leq\lambda_{2}\leq...\leq\lambda_{i}\leq...\]  
The sequence of eigenvalues of the LB operator is called the _spectrum_ of the LB operator. As it is computed based on the gradient and divergence that depend on the Riemannian structure of the manifold, it possesses the isometry invariant property [20]. These significant features of the LB operator, which include the orthogonal basis and non-negative spectrum, motivated researchers to develop various local and global shape descriptors. Shape-DNA and HKS were developed by considering the heat distribution as the function \(f\) on the surface. The WKS was obtained by solving the Schrodinger wave equation on the surface of the manifold. In addition, it has been shown that the GPS descriptor is in close relation to the Green's function on the surface [23]. To approximate Equation (2), despite the choice of function \(f\), we need a discretization scheme. Different discretization schemas (e.g., Taubin [32] and Mayer [33]) of the LB operator on the triangular meshes are discussed in [34]. A 3D shape, sampled from the surface of a Riemannian manifold \(\mathcal{M}\), is usually presented by a set of vertices \(V\) and their connectivity \(E\) in the form of the graph \(G=(V,E)\). Two vertices \(i,j\in V\) are neighbors if there exists a weighted edge \((i,j)\in E\), represented by \(w_{ij}\). For a surface mesh \(G\), according to [PERSON] et al. [24], Equation (2) can be discretized as:  
\[\mathbf{Af}=\lambda\mathbf{B}\mathbf{f} \tag{3}\]  
where \(\mathbf{A}\) is the _stiffness matrix_ and \(\mathbf{B}\) is the _lumped mass matrix_. One popular approach to constructing the matrix \(\mathbf{A}\), is using edge weights:  
\[w_{ij}=\frac{\cot(\alpha_{ij})+\cot(\beta_{ij})}{2} \tag{4}\]  
where \(\alpha_{ij}\) and \(\beta_{ij}\) are the two angles facing the edge \((i,j)\). Different mass normalization methods using the triangle area or the Voronoi region area are suggested to construct the matrix \(\mathbf{B}\). The cotangent weighting schema and its variants have been utilized in multiple FEM-based discretization methods. Another approach to constructing the matrix \(\mathbf{A}\) is to use the heat kernel weight, as described in [27]. It is known as the _exponential weighting scheme_ and defined as follows:  
\[w_{ij}=e^{-\frac{\|x_{i}-x_{j}\|^{2}}{t}} \tag{5}\]  
where \(\|.\|\) denotes the Euclidean distance between two adjacent nodes \(i\) and \(j\). In [24], several existing discretization methods, including variants of linear FEM [35; 36] and heat kernel weighting proposed in [25] are compared. According to [PERSON] et al. [24] and from the discussion led by [PERSON] in [34; 37], discrete LB operator using cotangent weighting scheme may not converge in all situations, specifically when dealing with non-uniform meshes. However, the heat kernel weighting scheme proposed in [25] does not depend on the peculiarities of the triangulation and outperforms all linear approaches [21; 24]. In addition, concerning the type of the function \(f\), the cotangent scheme only converges for linear functions, while the heat kernel scheme converges well for nonlinear functions as well [25].