## 2 Registration Algorithms Based on Hierarchical Optimization
### Graph Matching (GM)-Based
Accordingly, the final solution in practical applications needs to be further discretized, such as the Hungarian algorithm and the greedy selection algorithm, to obtain the final solution of the problem. In recent years, one of the most concerned problems in the field of graph matching has been the investigation of optimization methods under double random constraint relaxation. Since the double random constraint is a convex hull representation of the permutation constraint, the permutation matrix constraint is relaxed to a double random constraint. The graph matching problem can be regarded as a non-convex quadratic programming problem with convex constraints, making it a continuous optimization problem. For the past few years, scholars have developed various continuous optimization strategies to get local optimal solutions to this problem. [PERSON] and [PERSON] [52] devised a graduated assignment (GA) algorithm that obtains the final outcome by tackling a series of approximate linear matching problems. [PERSON] et al. [70] proposed a novel gradual assignment algorithm by further analyzing the convergence of GA algorithm. The experiments indicated that the technique outperforms existing methods in the presence of outliers and deformations, especially when the number of graph nodes is considerable. [PERSON] et al. [53] addressed the problem with a complicated graph matching objective function and a dual decomposition energy optimization approach. [PERSON] and [PERSON] [54] developed a factorized graph matching (FGM) in which the large pairwise affinity matrix is decomposed into smaller matrices and then a path tracking optimization algorithm is provided to increase the  
Figure 3: An example of a Graph-Matching problem. matching performance. [PERSON] et al. [55] suggested a methodology for LaGrange relaxation graph matching. The approach first embeds the matching problem's double random constraints into the optimized matching objective function via LaGrange relaxation and then utilizes the multi-multiplier optimization method to establish the relaxation model. [PERSON] et al. [56] originally suggested exploiting depth map matching to overcome the point cloud registration problem. The algorithm consists of four parts: local feature extractor, edge generator, map feature extractor, and AIS module and LAP SVD. During training, we extract local features by a shared local feature extractor for each point in \(X\) and \(Y\) and take these local features as the node features \(F\) of the initial graph; then, we introduce the AIS module to build the reliable correspondence between the nodes of two given graphs. The method achieves state-of-the-art performance on clean, noisy, part-to-part datasets and unknown category datasets. [PERSON] et al. [71] introduced a framework that efficiently and economically extracts dense features using a graph attention network for point cloud matching and registration (DFGAT). Another method for approximating the QAP solution is semidefinite programming (SDP) relaxation. The SDP method employs convex semidefinite to slacken the non-convex constraint. [PERSON] et al. [57] were the first to apply the semidefinite programming relaxation algorithm to register point clouds, and in the relaxation gap of the semidefinite programming, the characteristic noise threshold is almost zero (i.e., we are able to solve the original non-convex least squares problem). All in all, the semidefinite programming algorithm outperforms the double stochastic relaxation and spectral relaxation algorithms. [PERSON] et al. [58] achieved better efficiency by minimizing the dimension of semidefinite constraints. However, they only handle medium-sized point cloud registration, and efficiency is still a problem to be studied. [PERSON] et al. [59] regarded the point cloud registration as a special case of graph matching and employed a positive semi-definite relaxation principle.