## 2 Registration Algorithms Based on Hierarchical Optimization
### Graph Matching (GM)-Based  
From the perspective of mathematical optimization, the graph matching problem is a discrete combinatorial optimization problem, which makes the problem essentially a non-deterministic polynomial (NP) problem. Therefore, researchers usually seek approximate solutions to this problem. The majority of these approximation algorithms partly relax the discrete constraints of the matching problem, allowing for the employment of optimization techniques on the relaxed problem. Its central concept is to employ a nonparametric model to handle point cloud registration. Figure 3 is an example of GM. A graph consists of vertices and edges that will be adopted with feature descriptors to identify correspondences between two graphs. In the form of the objective function, GM methods can be divided into three categories: first-order, second-order and higher-order GM methods. First-order GM methods, which are comparable with ICP and its variants, only evaluate local feature descriptors with vertex information. Vertex-to-vertex and edge-to-edge similarities are combined in second-order GM methods. Higher-order GM methods involve information about hypergraphs, which are hyperedges containing the angles of vertex tuples. Second-order or higher-order GM methods are expressed as quadratic assignment problems [69]. Currently, the majority of GM algorithms are second-order or higher-order GM methods. Second-order GM techniques are classified into three categories: spectral relaxations, bi-stochastic relaxations, and semidefinite programming relaxations. The spectral relaxation method primarily relaxes the permutation constraints of the matching problem, yielding the matching problem's spectral characteristic solution. [PERSON] [47] developed a relaxed representation of the weight graph matching problem under orthogonal constraints and obtained the global optimal solution of the relaxed problem by the spectrum of the adjacency matrix. Although this method has the ability to gain the global optimal orthogonal solution of the matching problem, the nonnegativity of the obtained matching solution is often not guaranteed, the ultimate matching solution must be achieved via the discretization procedure. In addition, this method can only deal with graph matching problems of the same size. [PERSON] and [PERSON] [48] suggested a structural graph matching method based on expectation maximum algorithm and singular value decomposition theory. The key benefit is that it can match graphs of different sizes and has strong theoretical support for optimization. [PERSON] and [PERSON] [49] raised a graph-based matching algorithm for adjacency matrix spectral embedding. The vertices of a network are first embedded into the spectrum space of its adjacency matrix, and then the clustering method is adopted to match the vertices in the spectral space, thereby indirectly realizing graph vertex matching. [PERSON] and [PERSON] [50] presented a simple and effective spectral matching (SM) relaxation model to approximate the QAP problem. The method can obtain the global optimal solution of the relaxation model by calculating the principal eigenvector of the affinity matrix of the attribute relationship graph, and the solution also fulfills the criterion of non-negativity. However, throughout the matching process, the one-to-one matching constraint of graph matching is ignored, that is, each vertex can only be matched with one vertex. [PERSON] et al. [51] investigated affine matching constraints on the basis of the previously described spectral relaxation, which evaluated the one-to-one constraint of the matching problem to some extent and may also search for the global optimal solution. Therefore, this relaxation is theoretically closer to the original attribute relation graph matching problem. However, the optimal solution matrix derived by this approach frequently fail to satisfy the non-negativity constraints of the solution.