Multiple Graph Matching and Clustering via Decayed Pairwise Matching Composition


  • Tianzhe Wang Shanghai Jiao Tong University
  • Zetian Jiang Shanghai Jiao Tong University
  • Junchi Yan Shanghai Jiao Tong University



Jointly matching of multiple graphs is challenging and recently has been an active topic in machine learning and computer vision. State-of-the-art methods have been devised, however, to our best knowledge there is no effective mechanism that can explicitly deal with the matching of a mixture of graphs belonging to multiple clusters, e.g., a collection of bikes and bottles. Seeing its practical importance, we propose a novel approach for multiple graph matching and clustering. Firstly, for the traditional multi-graph matching setting, we devise a composition scheme based on a tree structure, which can be seen as in the between of two strong multi-graph matching solvers, i.e., MatchOpt (Yan et al. 2015a) and CAO (Yan et al. 2016a). In particular, it can be more robust than MatchOpt against a set of diverse graphs and more efficient than CAO. Then we further extend the algorithm to the multiple graph matching and clustering setting, by adopting a decaying technique along the composition path, to discount the meaningless matching between graphs in different clusters. Experimental results show the proposed methods achieve excellent trade-off on the traditional multi-graph matching case, and outperform in both matching and clustering accuracy, as well as time efficiency.




How to Cite

Wang, T., Jiang, Z., & Yan, J. (2020). Multiple Graph Matching and Clustering via Decayed Pairwise Matching Composition. Proceedings of the AAAI Conference on Artificial Intelligence, 34(02), 1660-1667.



AAAI Technical Track: Constraint Satisfaction and Optimization