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.
Zhen Zhang (WASHINGTON UNIVERSITY IN ST.LOUIS)
Yijian Xiang (Washington University in St. Louis)
Lingfei Wu (IBM Research AI)
Dr. Lingfei Wu earned his Ph.D. degree in computer science from the College of William and Mary in 2016. He is a research staff member at IBM Research and is leading a research team (10+ RSMs) for developing novel Graph Neural Networks for various tasks, which leads to the #1 AI Challenge Project in IBM Research and multiple IBM Awards including Outstanding Technical Achievement Award. He has published more than 70 top-ranked conference and journal papers and is a co-inventor of more than 30 filed US patents. Because of the high commercial value of his patents, he has received several invention achievement awards and has been appointed as IBM Master Inventors, class of 2020. He was the recipients of the Best Paper Award and Best Student Paper Award of several conferences such as IEEE ICC’19, AAAI workshop on DLGMA’20 and KDD workshop on DLG'19. His research has been featured in numerous media outlets, including NatureNews, YahooNews, Venturebeat, and TechTalks. He has co-organized 10+ conferences (AAAI, IEEE BigData) and is the founding co-chair for Workshops of Deep Learning on Graphs (with AAAI’21, AAAI’20, KDD’20, KDD’19, and IEEE BigData’19). He has currently served as Associate Editor for IEEE Transactions on Neural Networks and Learning Systems, ACM Transactions on Knowledge Discovery from Data and International Journal of Intelligent Systems, and regularly served as a SPC/PC member of the following major AI/ML/NLP conferences including KDD, IJCAI, AAAI, NIPS, ICML, ICLR, and ACL.
Bing Xue (Washington University in St. Louis)
Arye Nehorai (WASHINGTON UNIVERSITY IN ST.LOUIS)
Related Events (a corresponding poster, oral, or spotlight)
2019 Spotlight: KerGM: Kernelized Graph Matching »
Fri Dec 13th 12:40 -- 12:45 AM Room West Ballroom A + B
More from the Same Authors
2020 Poster: Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddings »
Yu Chen · Lingfei Wu · Mohammed Zaki
2018 Poster: RetGK: Graph Kernels based on Return Probabilities of Random Walks »
Zhen Zhang · Mianzhi Wang · Yijian Xiang · Yan Huang · Arye Nehorai