Exploiting Multi-layer Graph Factorization for Multi-attributed Graph Matching
This work addresses scalability and accuracy issues in graph matching for applications like computer vision and network analysis, but it is incremental as it builds on prior multi-layer approaches.
The paper tackles the problem of multi-attributed graph matching, where existing methods oversimplify attributes and face scalability issues, by proposing a multi-layer graph factorization algorithm that achieves better performance than state-of-the-art single-layer methods.
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.