Deep Probabilistic Graph Matching
- URL: http://arxiv.org/abs/2201.01603v1
- Date: Wed, 5 Jan 2022 13:37:27 GMT
- Title: Deep Probabilistic Graph Matching
- Authors: He Liu, Tao Wang, Yidong Li, Congyan Lang, Songhe Feng, and Haibin
Ling
- Abstract summary: 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.
- Score: 72.6690550634166
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Most previous learning-based graph matching algorithms solve the
\textit{quadratic assignment problem} (QAP) by dropping one or more of the
matching constraints and adopting a relaxed assignment solver to obtain
sub-optimal correspondences. Such relaxation may actually weaken the original
graph matching problem, and in turn hurt the matching performance. In this
paper we propose a deep learning-based graph matching framework that works for
the original QAP without compromising on the matching constraints. In
particular, we design an affinity-assignment prediction network to jointly
learn the pairwise affinity and estimate the node assignments, and we then
develop a differentiable solver inspired by the probabilistic perspective of
the pairwise affinities. Aiming to obtain better matching results, the
probabilistic solver refines the estimated assignments in an iterative manner
to impose both discrete and one-to-one 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.
Related papers
- Optimal Partial Graph Matching [2.4378101048225735]
We propose a novel framework for partial graph matching inspired by optimal partial transport.
Our approach formulates an objective that enables partial assignments while incorporating matching biases.
We employ the Hungarian algorithm to achieve efficient, exact solutions with cubic time complexity.
arXiv Detail & Related papers (2024-10-22T05:56:57Z) - 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) - Semisupervised score based matching algorithm to evaluate the effect of public health interventions [3.221788913179251]
In one-to-one matching algorithms, a large number of "pairs" to be matched could mean both the information from a large sample and a large number of tasks.
We propose a novel one-to-one matching algorithm based on a quadratic score function $S_beta(x_i,x_j)= betaT (x_i-x_j)(x_i-x_j)T beta$.
arXiv Detail & Related papers (2024-03-19T02:24:16Z) - Ranking from Pairwise Comparisons in General Graphs and Graphs with
Locality [3.1219977244201056]
This technical report studies the problem of ranking from pairwise comparisons in the classical Bradley-Terry-Luce (BTL) model.
We show that, with sufficiently many samples, maximum likelihood estimation (MLE) achieves an entrywise estimation error matching the Cram'er-Rao lower bound.
We explore divide-and-conquer algorithms that can provably achieve similar guarantees even in the regime with the sparsest samples.
arXiv Detail & Related papers (2023-04-13T21:14:30Z) - On graph-based reentrancy-free semantic parsing [5.228711636020665]
We propose a graph-based approach for semantic parsing that resolves two problems observed in the literature.
We prove that both MAP inference and latent tag anchoring (required for weakly-supervised learning) are NP-hard problems.
We propose two optimization algorithms based on constraint smoothing and conditional gradient to approximately solve these inference problems.
arXiv Detail & Related papers (2023-02-15T14:14:09Z) - Reinforcement Learning Based Query Vertex Ordering Model for Subgraph
Matching [58.39970828272366]
Subgraph matching algorithms enumerate all is embeddings of a query graph in a data graph G.
matching order plays a critical role in time efficiency of these backtracking based subgraph matching algorithms.
In this paper, for the first time we apply the Reinforcement Learning (RL) and Graph Neural Networks (GNNs) techniques to generate the high-quality matching order for subgraph matching algorithms.
arXiv Detail & Related papers (2022-01-25T00:10:03Z) - Bayesian Graph Contrastive Learning [55.36652660268726]
We propose a novel perspective of graph contrastive learning methods showing random augmentations leads to encoders.
Our proposed method represents each node by a distribution in the latent space in contrast to existing techniques which embed each node to a deterministic vector.
We show a considerable improvement in performance compared to existing state-of-the-art methods on several benchmark datasets.
arXiv Detail & Related papers (2021-12-15T01:45:32Z) - 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) - Deep Reinforcement Learning of Graph Matching [63.469961545293756]
Graph matching (GM) under node and pairwise constraints has been a building block in areas from optimization to computer vision.
We present a reinforcement learning solver for GM i.e. RGM that seeks the node correspondence between pairwise graphs.
Our method differs from the previous deep graph matching model in the sense that they are focused on the front-end feature extraction and affinity function learning.
arXiv Detail & Related papers (2020-12-16T13:48:48Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
We consider the problem of ranking $N$ objects starting from a set of noisy pairwise comparisons provided by a crowd of equal workers.
We propose a class of non-adaptive ranking algorithms that rely on a least-squares intrinsic optimization criterion for the estimation of qualities.
arXiv Detail & Related papers (2020-02-26T16:19:09Z)
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.