<i>k</i> ‐wise multi‐graph matching

Abstract Multi‐graph matching (MGM), which aims to find correspondences among multiple graphs, is an extension of conventional two‐graph matching. Existing MGM methods fall into two categories: pairwise based and tensor based. Pairwise‐based methods consider similarities between every two features; while tensor‐based methods consider the overall similarity among all features, offering much more flexibility similarity measurements and less information loss, but at the cost of exorbitant computational demands. Here, a fresh perspective on MGM task is delivered, that is, matching based on any k features. It enables the consideration of more complex affinity relationship beyond pairwise while keeping computational demands within a manageable threshold. Furthermore, a factorization technique for the k ‐wise global affinity matrix is proposed, significantly reducing space complexity. This approach unifies existing MGM methods and inspires future research focusing on k ‐wise affinity relationship, showcasing both theoretical and practical advancements in the field. Experiments on synthetic and real‐world datasets demonstrate the superiority of our method.