Learning for Graph Matching and Related Combinatorial Optimization Problems

This survey gives a selective review of recent development of machine learning (ML) for combinatorial optimization (CO), especially for graph matching. The synergy of these two well-developed areas (ML and CO) can potentially give transformative change to artificial intelligence, whose foundation relates to these two building blocks. For its representativeness and wide-applicability, this paper is more focused on the problem of weighted graph matching, especially from the learning perspective. For graph matching, we show that many learning techniques e. g. convolutional neural networks, graph neural networks, reinforcement learning can be effectively incorporated in the paradigm for extracting the node features, graph structure features, and even the matching engine. We further present outlook for the new settings for learning graph matching, and direction towards more integrated combinatorial optimization solvers with prediction models, and also the mutual embrace of traditional solver and machine learning components.

Authors

• Junchi Yan School of Artificial Intelligence & Department of CSE & MoE Lab of AI, Shanghai Jiao Tong University
• Shuang Yang
• Edwin Hancock Department of Computer Science, University of York, York, United Kingdom

Keywords

• Constraints and Satisfiability: general
• Machine learning: General
• Planning and scheduling: General