# An Application of Manifold Learning in Global Shape Descriptors
## 3 Method
### Laplacian Eigenmap-Based Shape Descriptor  
We treat a global descriptor as a dimensionality reduction problem as it squeezes the latent information of a 3D model into a vector. Since the Laplacian Eigenmap has two properties of structural equivalence and locality preservation [27], we propose a global shape descriptor using the spectrum of graph Laplacian. A graph Laplacian is constructed over an _undirected weighted graph_\(G=(V,E)\) with a set of points \(x_{i}\in V\) and a set \(E\) of edges that connects nearby points (\((i,j)\in E\)). The theory behind finding the optimal embedding in a Laplacian Eigenmap requires an undirected graph. Every 3D model is given in bidirectional connection and, hence, we need to neither examine nor force it to the graph. However, as explained below, we need to remove isolated points. Considering the advantages of the heat kernel weighting scheme, which are summarized in Section 2.1 and discussed in detail in [25], Laplacian Eigenmap suggests constructing the weighted graph as follows:  
\[w_{ij}= \begin{cases}e^{-\frac{\|x_{i}-x_{j}\|^{2}}{t}}&,\text{if }(i,j)\in E\\ 0&,\text{otherwise}\end{cases}  \tag{6}\]  
where \(x_{i}\) and \(x_{j}\) are coordinates of adjacent nodes \(i\) and \(j\), connected with a weighted edge \(w_{ij}\). Figure 1: The block diagram of the proposed Laplacian Eigenmaps based scale-invariant (LESI) global shape descriptor. The only parameter in Equation (6) is \(t\), which defines the extent to which distant neighbors influence the embedding of each point. The choice of parameter \(t\) is data-dependent, and there exists no unique way in the literature to select the proper value, but it can be tuned empirically. The only limitation is that if \(t\) is very small, most edge weights \(w_{ij}\) are close to zero. Then, the Laplacian eigenvalue problem will not converge to a unique solution. If \(t\) is large enough, it has a high impact on neither the final embedding nor the convergence rate of our final derivations. Therefore, we empirically recommend:  
\[t =2d_{max}^{2}\text{ where,} \tag{7}\] \[d_{max} =\max\|x_{i}-x_{j}\|\quad,\forall(i,j)\in E.\]  
Here, weights are bounded as \(0.6\approx e^{-0.5}\leq w_{ij}\leq 1\). We would like to note that another way is to select a constant value for the entire sample set. Laplacian Eigenmap attempts to find a low dimensional dataset that preserves local information. For this purpose, it assumes two neighboring points \(x_{i}\) and \(x_{j}\) stay close after being mapped to \(y_{i}\) and \(y_{j}\). Therefore, it minimizes the following function [27]:  
\[\frac{1}{2}\sum_{ij}(y_{i}-y_{j})^{2}w_{ij}=\mathbf{y}^{T}\mathbf{L}\mathbf{y}. \tag{8}\]  
where \(\mathbf{L}=\mathbf{D}-\mathbf{W}\) is the so called _Laplacian matrix_, \(\mathbf{W}\) is a symmetric _weight matrix_, and \(\mathbf{D}_{ii}=\sum_{j}\mathbf{W}_{ij}\), the _degree matrix_, is a diagonal matrix. The assumption that the graph is undirected yields the symmetric property of \(\mathbf{W}\) and, consequently, \(\mathbf{D}\) and \(\mathbf{L}\). It plays a critical role in deriving Equation (8). By adding the orthogonality constraint \(\mathbf{y}^{T}\mathbf{D}\mathbf{1}=0\) to eliminate the trivial solution and the constraint \(\mathbf{y}^{T}\mathbf{D}\mathbf{y}=1\) for removing an arbitrary scaling factor in the embedding, the minimization problem in Equation (8) simplifies to:  
\[\operatorname*{arg\,min}_{\mathbf{y}}\mathbf{y}^{T}\mathbf{L}\mathbf{y}. \tag{9}\]  
The matrix \(\mathbf{L}\) is real, symmetric, and positive semi-definite. Therefore, the solution vector \(\mathbf{y}\) (in Equation (9)) is obtained by the minimum eigenvalue solution to the generalized eigenvalue problem [27]:  
\[\mathbf{L}\mathbf{y}=\lambda\mathbf{D}\mathbf{y}. \tag{10}\]  
At this point, the optimal low-dimensional embedding, suggested by the Laplacian Eigenmap, is obtained by utilizing the eigenvectors. In addition, the eigenvectors of Equation (10) have application in graph partitioning with relaxed normalized cut [46], which is out of the scope of this manuscript.