Multi-attributed graph matching is a problem of finding correspondences between two sets of data while considering their complex properties described in multiple attributes. However, the information of multiple attributes is likely to be oversimplified during a process that makes an integrated attribute, and this degrades the matching accuracy. For that reason, a multi-layer graph structure-based algorithm has been proposed recently. It can effectively avoid the problem by separating attributes into multiple layers. Nonetheless, there are several remaining issues such as a scalability problem caused by the huge matrix to describe the multi-layer structure and a back-projection problem caused by the continuous relaxation of the quadratic assignment problem. In this work, we propose a novel multi-attributed graph matching algorithm based on the multi-layer graph factorization. We reformulate the problem to be solved with several small matrices that are obtained by factorizing the multi-layer structure. Then, we solve the problem using a convex-concave relaxation procedure for the multi-layer structure. The proposed algorithm exhibits better performance than state-of-the-art algorithms based on the single-layer structure.
The proposed algorithm is inspired by the factorization-based convex-concave relaxation approach @cite_25 @cite_15 . Since multi-attributed graph matching problems that are formulated using a multi-layer structure require a large matrix to describe its structure, the factorization-based relaxation scheme is very useful in resolving the scalability issue.
@cite_15 @cite_25
2949291209 2146130798 2121275167 2336641195
We propose a convex-concave programming approach for the labeled weighted graph matching problem. The convex-concave programming formulation is obtained by rewriting the weighted graph matching problem as a least-square problem on the set of permutation matrices and relaxing it to two different optimization problems: a quadratic convex and a quadratic concave optimization problem on the set of doubly stochastic matrices. The concave relaxation has the same global minimum as the initial graph matching problem, but the search for its global minimum is also a hard combinatorial problem. We therefore construct an approximation of the concave problem solution by following a solution path of a convex-concave problem obtained by linear interpolation of the convex and concave formulations, starting from the convex relaxation. This method allows to easily integrate the information on graph label similarities into the optimization problem, and therefore to perform labeled weighted graph matching. The algorithm is compared with some of the best performing graph matching methods on four datasets: simulated graphs, QAPLib, retina vessel images and handwritten chinese characters. In all cases, the results are competitive with the state-of-the-art. We use convex relaxation techniques to provide a sequence of regularized low-rank solutions for large-scale matrix completion problems. Using the nuclear norm as a regularizer, we provide a simple and very efficient convex algorithm for minimizing the reconstruction error subject to a bound on the nuclear norm. Our algorithm SOFT-IMPUTE iteratively replaces the missing elements with those obtained from a soft-thresholded SVD. With warm starts this allows us to efficiently compute an entire regularization path of solutions on a grid of values of the regularization parameter. The computationally intensive part of our algorithm is in computing a low-rank SVD of a dense matrix. Exploiting the problem structure, we show that the task can be performed with a complexity of order linear in the matrix dimensions. Our semidefinite-programming algorithm is readily scalable to large matrices; for example SOFT-IMPUTE takes a few hours to compute low-rank approximations of a 106 X 106 incomplete matrix with 107 observed entries, and fits a rank-95 approximation to the full Netflix training set in 3.3 hours. Our methods achieve good training and test errors and exhibit superior timings when compared to other competitive state-of-the-art techniques. We study learning formulations with non-convex regularizaton that are natural for sparse linear models. There are two approaches to this problem: • Heuristic methods such as gradient descent that only find a local minimum. A drawback of this approach is the lack of theoretical guarantee showing that the local minimum gives a good solution. • Convex relaxation such as L1-regularization that solves the problem under some conditions. However it often leads to sub-optimal sparsity in reality. This paper tries to remedy the above gap between theory and practice. In particular, we investigate a multi-stage convex relaxation scheme for solving problems with non-convex regularization. Theoretically, we analyze the behavior of a resulting two-stage relaxation scheme for the capped-L1 regularization. Our performance bound shows that the procedure is superior to the standard L1 convex relaxation for learning sparse targets. Experiments confirm the effectiveness of this method on some simulation and real data. In this paper we propose the graduated nonconvexity and concavity procedure (GNCCP) as a general optimization framework to approximately solve the combinatorial optimization problems defined on the set of partial permutation matrices. GNCCP comprises two sub-procedures, graduated nonconvexity which realizes a convex relaxation and graduated concavity which realizes a concave relaxation. It is proved that GNCCP realizes exactly a type of convex-concave relaxation procedure (CCRP), but with a much simpler formulation without needing convex or concave relaxation in an explicit way. Actually, GNCCP involves only the gradient of the objective function and is therefore very easy to use in practical applications. Two typical related NP-hard problems, partial graph matching and quadratic assignment problem (QAP), are employed to demonstrate its simplicity and state-of-the-art performance.