Kernelized multi-graph matching

• URL: http://arxiv.org/abs/2210.05206v1
• Date: Tue, 11 Oct 2022 07:22:47 GMT
• Title: Kernelized multi-graph matching
• Authors: Fran\c{c}ois-Xavier Dup\'e (LIS, QARMA), Rohit Yadav, Guillaume Auzias, S. Takerkart
• Abstract summary: We introduce a novel kernelized multigraph matching technique that handles both the attributes of the pair and the edges of the graphs. We propose several projectors leading to improved stability of the results.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multigraph matching is a recent variant of the graph matching problem. In this framework, the optimization procedure considers several graphs and enforces the consistency of the matches along the graphs. This constraint can be formalized as a cycle consistency across the pairwise permutation matrices, which implies the definition of a universe of vertex~\citep{pachauri2013solving}. The label of each vertex is encoded by a sparse vector and the dimension of this space corresponds to the rank of the bulk permutation matrix, the matrix built from the aggregation of all the pairwise permutation matrices. The matching problem can then be formulated as a non-convex quadratic optimization problem (QAP) under constraints imposed on the rank and the permutations. In this paper, we introduce a novel kernelized multigraph matching technique that handles vectors of attributes on both the vertices and edges of the graphs, while maintaining a low memory usage. We solve the QAP problem using a projected power optimization approach and propose several projectors leading to improved stability of the results. We provide several experiments showing that our method is competitive against other unsupervised 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)
• Diff-PCR: Diffusion-Based Correspondence Searching in Doubly Stochastic Matrix Space for Point Cloud Registration [35.82753072083472]
  State-of-the-art methods have employed RAFT-like iterative updates to refine the solution. We propose a novel approach that exploits the Denoising Diffusion Model to predict a searching for the optimal matching matrix. Our method offers flexibility by allowing the search to start from any initial matching matrix provided by the online backbone or white noise.
  arXiv  Detail & Related papers  (2023-12-31T09:24:28Z)
• Random Edge Coding: One-Shot Bits-Back Coding of Large Labeled Graphs [24.761152163389735]
  We present a one-shot method for compressing large labeled graphs called Random Edge Coding. Experiments indicate Random Edge Coding can achieve competitive compression performance on real-world network datasets.
  arXiv  Detail & Related papers  (2023-05-16T12:23:18Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  We propose a novel method named Multi-block-probe Variance Reduced (MSVR) to alleviate the complexity of compositional problems. Our results improve upon prior ones in several aspects, including the order of sample complexities and dependence on strongity.
  arXiv  Detail & Related papers  (2022-07-18T12:03:26Z)
• 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)
• 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)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  We address the non- optimisation problem of finding a matrix on the Stiefel manifold that maximises a quadratic objective function. We propose a simple yet effective sparsity-promoting algorithm for finding the dominant eigenspace matrix.
  arXiv  Detail & Related papers  (2021-09-30T19:17:35Z)
• Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov Random Fields [51.07460861448716]
  This paper presents a convex-analytic framework to learn from data. We show that a triangular convexity decomposition is guaranteed by a transform of the corresponding to its upper part.
  arXiv  Detail & Related papers  (2021-09-17T17:46:12Z)
• Articulated Shape Matching Using Laplacian Eigenfunctions and Unsupervised Point Registration [38.16866987817019]
  Spectral graph theory can be used to map these graphs onto lower dimensional spaces and match shapes by aligning their embeddings. We derive a new formulation that finds the best alignment between two congruent $K$-dimensional sets of points by selecting the best subset of eigenfunctions of the Laplacian matrix.
  arXiv  Detail & Related papers  (2020-12-14T08:49:25Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  We cast a new formulation for the one-to-many graph alignment problem, which aims at matching a node in the smaller graph with one or more nodes in the larger graph. We show that our method leads to significant improvements with respect to the state-of-the-art algorithms for each of these tasks.
  arXiv  Detail & Related papers  (2020-03-12T22:31:59Z)

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.