Deep graph matching meets mixed-integer linear programming: Relax at your own risk ?
Graph matching is an important problem that has received widespread attention, especially in the field of computer vision. Recently, state-of-the-art methods seek to incorporate graph matching with deep learning. However, there is no research to explain what role the graph matching algorithm plays in the model. Therefore, we propose an approach integrating a MILP formulation of the graph matching problem. This formulation is solved to optimal and it provides inherent baseline. Meanwhile, similar approaches are derived by releasing the optimal guarantee of the graph matching solver and by introducing a quality level. This quality level controls the quality of the solutions provided by the graph matching solver. In addition, several relaxations of the graph matching problem are put to the test. Our experimental evaluation gives several theoretical insights and guides the direction of deep graph matching methods.
Code (2)
Tasks
Graph MatchingSimilar Papers 제목 키워드 기반
Molecular Design Based on Artificial Neural Networks, Integer Programming and Grid Neighbor Search
A novel framework has recently been proposed for designing the molecular structure of chemical compounds with a desired chemical property using both artificial neural networks and mixed integer linear programming. In the…
Convex mixed-integer optimization with Frank-Wolfe methods
Mixed-integer nonlinear optimization encompasses a broad class of problems that present both theoretical and computational challenges. We propose a new type of method to solve these problems based on a branch-and-bound a…
Information-Theoretic Abstractions for Resource-Constrained Agents via Mixed-Integer Linear Programming
In this paper, a mixed-integer linear programming formulation for the problem of obtaining task-relevant, multi-resolution, graph abstractions for resource-constrained agents is presented. The formulation leverages conce…
Graph-based Reinforcement Learning meets Mixed Integer Programs: An application to 3D robot assembly discovery
Robot assembly discovery is a challenging problem that lives at the intersection of resource allocation and motion planning. The goal is to combine a predefined set of objects to form something new while considering task…
global-optimizationMotion PlanningQ-LearningReinforcement Learning (RL)Graph4BiLO: Graph Neural Network Approximation for Bilevel Mixed-Integer Linear Optimization
Bilevel mixed-integer linear optimization problems model hierarchical decision processes in which a leader anticipates the optimal response of a follower. Although expressive, these problems are computationally challengi…
Graph Neural Network