Timezone: »

KerGM: Kernelized Graph Matching
Zhen Zhang · Yijian Xiang · Lingfei Wu · Bing Xue · Arye Nehorai

Thu Dec 12 04:40 PM -- 04:45 PM (PST) @ West Ballroom A + B

Graph matching plays a central role in such fields as computer vision, pattern recognition, and bioinformatics. Graph matching problems can be cast as two types of quadratic assignment problems (QAPs): Koopmans-Beckmann's QAP or Lawler's QAP. In our paper, we provide a unifying view for these two problems by introducing new rules for array operations in Hilbert spaces. Consequently, Lawler's QAP can be considered as the Koopmans-Beckmann's alignment between two arrays in reproducing kernel Hilbert spaces (RKHS), making it possible to efficiently solve the problem without computing a huge affinity matrix. Furthermore, we develop the entropy-regularized Frank-Wolfe (EnFW) algorithm for optimizing QAPs, which has the same convergence rate as the original FW algorithm while dramatically reducing the computational burden for each outer iteration. We conduct extensive experiments to evaluate our approach, and show that our algorithm significantly outperforms the state-of-the-art in both matching accuracy and scalability.

Author Information

Yijian Xiang (Washington University in St. Louis)
Teddy Wu (IBM Research AI)

Lingfei Wu is a Research Staff Member in the IBM AI Foundations Labs, Reasoning group at IBM T. J. Watson Research Center. He earned his Ph.D. degree in computer science from College of William and Mary in August 2016, under the supervision of Prof. Andreas Stathopoulos. His research interests mainly span in Machine Learning, Deep Learning, Representation Learning, Natural Language Processing, and Numerical Linear Algebra.

Bing Xue (Washington University in St. Louis)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors