# An Application of Manifold Learning in Global Shape Descriptors
## 3 Method
### Laplacian Eigenmap-Based Shape Descriptor
Here, we focus on the spectrum of the graph Laplacian and its' properties. Eigenvalues obtained from Equation (10) are real, non-negative, and sorted in increasing order as follows:  
\[0\leq\lambda_{1}\leq\lambda_{2}\leq...\leq\lambda_{n}.\]  
As the row (or column) sum of \(\mathbf{L}\) is equal to zero, eigenvalue \(\lambda=0\) and a corresponding eigenvector \(\mathbf{1}\) are trivial solutions to Equation (10). The multiplicity of eigenvalue zero is associated with the number of connected components of the graph. Eigen-solvers often obtain very small, though not precisely zero, eigenvalues due to the computational approximations. If we may know the number of connected components of \(\mathbf{L}\), we can discard all eigenvalues equal to zero, and form our shape fingerprint using the more informative section of the spectrum. This is easily done by Dulmage-Mendelsohn decomposition [47]. The second smallest eigenvalue, also known as the _Fiedler value_, is a measure of the connectivity within the graph. If the graph has \(c\) connected components, our proposed shape descriptor is a set of \(d\) eigenvalues as:  
\[\text{LESI}\coloneqq(\lambda_{c+1},\lambda_{c+2},\ldots,\lambda_{c+d}) \tag{11}\]  
The LESI descriptor is composed of the spectrum of the LB operator, and, hence, it is isometric invariant, independent of the shape location, and informative. The latter, discussed in spectral graph theory, states that the spectrum of graph Laplacian contains a considerable amount of geometrical and topological information of the graph. Moreover, LESI has the similarity property, caused by the structural equivalence property of Laplacian Eigenmap, meaning that two 3D models from the same class of models have similar fingerprints. Unlike Shape-DNA and other shape descriptors that are based on the cotangent weighting scheme, LESI is not limited to triangulated mesh structures because the Laplacian Eigenmap is capable of dealing with high-dimensional data. For some applications in which scale is not a determinant factor, it is favorable to have a scale-invariant descriptor. A fast and efficient normalization method is presented in Section 3.2. One important matter to consider is the convergence and accuracy of the proposed fingerprint, which ultimately depends on the heat kernel-based discretization of the LB operator. The cotangent weighting scheme and its variants are sensitive to the peculiarities and quality of the particular triangulation of the mesh (refer to Section 2.1). While an exponential weighting scheme has shown accurate performance in dealing with nonlinear functions over the surface and non-uniform mesh representations, it is not clear how this method can handle manifolds with boundaries [24; 25]. It does, however, behave well for interior points of the surface. Therefore, we recommend removing rows and columns of \(\mathbf{L}\) and \(\mathbf{D}\) corresponding to isolated points, before solving Equation (10). The descriptor obtained from the rest of the connected graph is an informative and discriminative descriptor of the graph.