Deep graph matching meets mixed-integer linear programming: Relax at your own risk ?

• URL: http://arxiv.org/abs/2108.00394v1
• Date: Sun, 1 Aug 2021 08:29:55 GMT
• Title: Deep graph matching meets mixed-integer linear programming: Relax at your own risk ?
• Authors: Zhoubo Xu, Puqing Chen, Romain Raveaux, Xin Yang, Huadong Liu
• Abstract summary: We propose an approach integrating a MILP formulation of the graph matching problem. Similar approaches are derived by releasing the optimal guarantee of the graph matching solver and by introducing a quality level. Our experimental evaluation gives several theoretical insights and guides the direction of deep graph matching methods.
• Score: 8.05409526074409
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Differentiable Proximal Graph Matching [40.41380102260085]
  We introduce an algorithm for graph matching based on the proximal operator, referred to as differentiable proximal graph matching (DPGM) The whole algorithm can be considered as a differentiable map from the graph affinity matrix to the prediction of node correspondence. Numerical experiments show that PGM outperforms existing graph matching algorithms on diverse datasets.
  arXiv  Detail & Related papers  (2024-05-26T08:17:13Z)
• The graph alignment problem: fundamental limits and efficient algorithms [0.9246334723892301]
  The noisy version of the graph isomorphism problem aims to find a matching between the nodes of two graphs which preserves most of the edges. This thesis focuses on understanding the fundamental information-theoretical limits for this problem, as well as designing and analyzing algorithms that are able to recover the underlying alignment in the data.
  arXiv  Detail & Related papers  (2024-04-18T15:31:13Z)
• M3C: A Framework towards Convergent, Flexible, and Unsupervised Learning of Mixture Graph Matching and Clustering [57.947071423091415]
  We introduce Minorize-Maximization Matching and Clustering (M3C), a learning-free algorithm that guarantees theoretical convergence. We develop UM3C, an unsupervised model that incorporates novel edge-wise affinity learning and pseudo label selection. Our method outperforms state-of-the-art graph matching and mixture graph matching and clustering approaches in both accuracy and efficiency.
  arXiv  Detail & Related papers  (2023-10-27T19:40:34Z)
• Learning Universe Model for Partial Matching Networks over Multiple Graphs [78.85255014094223]
  We develop a universe matching scheme for partial matching of two or multiple graphs. The subtle logic for inlier matching and outlier detection can be clearly modeled. This is the first deep learning network that can cope with two-graph matching, multiple-graph matching, online matching, and mixture graph matching simultaneously.
  arXiv  Detail & Related papers  (2022-10-19T08:34:00Z)
• Deep Probabilistic Graph Matching [72.6690550634166]
  We propose a deep learning-based graph matching framework that works for the original QAP without compromising on the matching constraints. The proposed method is evaluated on three popularly tested benchmarks (Pascal VOC, Willow Object and SPair-71k) and it outperforms all previous state-of-the-arts on all benchmarks.
  arXiv  Detail & Related papers  (2022-01-05T13:37:27Z)
• Joint Graph Learning and Matching for Semantic Feature Correspondence [69.71998282148762]
  We propose a joint emphgraph learning and matching network, named GLAM, to explore reliable graph structures for boosting graph matching. The proposed method is evaluated on three popular visual matching benchmarks (Pascal VOC, Willow Object and SPair-71k) It outperforms previous state-of-the-art graph matching methods by significant margins on all benchmarks.
  arXiv  Detail & Related papers  (2021-09-01T08:24:02Z)
• Graph Pooling via Coarsened Graph Infomax [9.045707667111873]
  We propose Coarsened GraphPool Infomaxing (CGI) to maximize the mutual information between the input and the coarsened graph of each pooling layer. To achieve mutual information neural, we apply contrastive learning and propose a self-attention-based algorithm for learning positive and negative samples.
  arXiv  Detail & Related papers  (2021-05-04T03:50:21Z)
• Fusion Moves for Graph Matching [35.27002115682325]
  We contribute to approximate algorithms for the quadratic assignment problem also known as graph matching. Inspired by the success of the fusion moves technique developed for multilabel discrete Markov random fields, we investigate its applicability to graph matching. We show how it can be efficiently combined with the dedicated state-of-the-art Lagrange dual methods.
  arXiv  Detail & Related papers  (2021-01-28T16:09:46Z)
• Multilayer Clustered Graph Learning [66.94201299553336]
  We use contrastive loss as a data fidelity term, in order to properly aggregate the observed layers into a representative graph. Experiments show that our method leads to a clustered clusters w.r.t. We learn a clustering algorithm for solving clustering problems.
  arXiv  Detail & Related papers  (2020-10-29T09:58:02Z)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  We consider the graph link prediction task, which is a classic graph analytical problem with many real-world applications. In this formalism, a link prediction problem is converted to a graph classification task. We propose to seek a radically different and novel path by making use of the line graphs in graph theory. In particular, each node in a line graph corresponds to a unique edge in the original graph. Therefore, link prediction problems in the original graph can be equivalently solved as a node classification problem in its corresponding line graph, instead of a graph classification task.
  arXiv  Detail & Related papers  (2020-10-20T05:54:31Z)
• Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time [12.43303621344215]
  We develop a new framework to solve any optimization problem over graphs without expert knowledge. Our method trains a graph neural network using reinforcement learning on an unlabeled training set of graphs. We demonstrate our approach on both NP-hard problems with optimality gaps close to 1, and show that our method is able to generalize well.
  arXiv  Detail & Related papers  (2020-06-06T01:35:45Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.