An algorithm for weighted sub-graph matching based on gradient flows

作者：Tao, Songqiao; Wang, Shuting^*

来源：Information Sciences, 2016, 340: 104-121.

DOI：10.1016/j.ins.2015.12.033

• Sub-graph matching
• Gradient flow
• Weighted adjacency matrix

An algorithm for matching the weighted sub-graphs based on gradient flows is proposed in this paper. First, the smaller and larger graphs for matching are represented by means of their weighted adjacency matrices. Then, an objective function is introduced to measure the differences between two weighted adjacency matrices. Because the permutation matrix for graph matching is usually relaxed to an orthogonal matrix with non-negative elements, an optimization-based approach is adopted to "navigate" the solution toward an appropriate permutation matrix. To accomplish this goal, two gradient flows in the space of orthogonal matrices are defined in such a way that they minimize the objective functions. One minimizes the objective function in the space of orthogonal matrices, and the other minimizes the distance of an orthogonal matrix from the set of permutations. In addition, two cost functions are introduced to force satisfaction (approximately) of the constraint that a translation matrix must have integer entries of different values. The experimental results show that the proposed sub-graph matching is feasible.

• 出版日期2016-5-1
• 单位华中科技大学