article

An Extended Path Following Algorithm for Graph-Matching Problem

Authors:

Zhi-Yong Liu,

Hong Qiao,

Lei XuAuthors Info & Claims

IEEE Transactions on Pattern Analysis and Machine Intelligence, Volume 34, Issue 7

Pages 1451 - 1456

https://doi.org/10.1109/TPAMI.2012.45

Published: 01 July 2012 Publication History

Abstract

The path following algorithm was proposed recently to approximately solve the matching problems on undirected graph models and exhibited a state-of-the-art performance on matching accuracy. In this paper, we extend the path following algorithm to the matching problems on directed graph models by proposing a concave relaxation for the problem. Based on the concave and convex relaxations, a series of objective functions are constructed, and the Frank-Wolfe algorithm is then utilized to minimize them. Several experiments on synthetic and real data witness the validity of the extended path following algorithm.

Cited By

View all

Hu YWang WYu Y(2022)Graph matching beyond perfectly-overlapping Erdős–Rényi random graphsStatistics and Computing10.1007/s11222-022-10079-132:1Online publication date: 15-Feb-2022
https://dl.acm.org/doi/10.1007/s11222-022-10079-1
Liu CZhang SYang XYan J(2022)Self-supervised Learning of Visual Graph MatchingComputer Vision – ECCV 202210.1007/978-3-031-20050-2_22(370-388)Online publication date: 23-Oct-2022
https://dl.acm.org/doi/10.1007/978-3-031-20050-2_22
Ma JJiang XFan AJiang JYan J(2021)Image Matching from Handcrafted to Deep Features: A SurveyInternational Journal of Computer Vision10.1007/s11263-020-01359-2129:1(23-79)Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1007/s11263-020-01359-2
Show More Cited By

Recommendations

A Path Following Algorithm for the Graph Matching Problem

We propose a convex-concave programming approach for the labeled weighted graph matching problem. The convex-concave programming formulation is obtained by rewriting the weighted graph matching problem as a least-square problem on the set of permutation ...
Semidefinite programming approach for the quadratic assignment problem with a sparse graph

The matching problem between two adjacency matrices can be formulated as the NP-hard quadratic assignment problem (QAP). Previous work on semidefinite programming (SDP) relaxations to the QAP have produced solutions that are often tight in practice, but ...
A graph matching algorithm based on concavely regularized convex relaxation

In this paper we propose a concavely regularized convex relaxation based graph matching algorithm. The graph matching problem is firstly formulated as a constrained convex quadratic program by relaxing the feasible set from the permutation matrices to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Pattern Analysis and Machine Intelligence

IEEE Transactions on Pattern Analysis and Machine Intelligence Volume 34, Issue 7

July 2012

209 pages

ISSN:0162-8828

Issue’s Table of Contents

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 July 2012

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Hu YWang WYu Y(2022)Graph matching beyond perfectly-overlapping Erdős–Rényi random graphsStatistics and Computing10.1007/s11222-022-10079-132:1Online publication date: 15-Feb-2022
https://dl.acm.org/doi/10.1007/s11222-022-10079-1
Liu CZhang SYang XYan J(2022)Self-supervised Learning of Visual Graph MatchingComputer Vision – ECCV 202210.1007/978-3-031-20050-2_22(370-388)Online publication date: 23-Oct-2022
https://dl.acm.org/doi/10.1007/978-3-031-20050-2_22
Ma JJiang XFan AJiang JYan J(2021)Image Matching from Handcrafted to Deep Features: A SurveyInternational Journal of Computer Vision10.1007/s11263-020-01359-2129:1(23-79)Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1007/s11263-020-01359-2
Yang XLiu ZQiao H(2020)A Continuation Method for Graph Matching Based Feature CorrespondenceIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2019.290348342:8(1809-1822)Online publication date: 1-Aug-2020
https://dl.acm.org/doi/10.1109/TPAMI.2019.2903483
Jiang BTang JLuo B(2019)Efficient Feature Matching via Nonnegative Orthogonal RelaxationInternational Journal of Computer Vision10.1007/s11263-019-01185-1127:9(1345-1360)Online publication date: 1-Sep-2019
https://dl.acm.org/doi/10.1007/s11263-019-01185-1
Yu TYan JWang YLiu WLi B(2018)Generalizing graph matching beyond quadratic assignment modelProceedings of the 32nd International Conference on Neural Information Processing Systems10.5555/3326943.3327023(861-871)Online publication date: 3-Dec-2018
https://dl.acm.org/doi/10.5555/3326943.3327023
He LLiu ZLiu MYang XZhang F(2018)Quadratic Assignment Problem via a Convex and Concave Relaxations ProcedureProceedings of the 3rd International Conference on Robotics, Control and Automation10.1145/3265639.3265665(147-153)Online publication date: 11-Aug-2018
https://dl.acm.org/doi/10.1145/3265639.3265665
Dutta ALlads JBunke HPal U(2018)Product graph-based higher order contextual similarities for inexact subgraph matchingPattern Recognition10.1016/j.patcog.2017.12.00376:C(596-611)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.1016/j.patcog.2017.12.003
Jiang BTang JDing CLuo BSingh SMarkovitch S(2017)Nonnegative orthogonal graph matchingProceedings of the Thirty-First AAAI Conference on Artificial Intelligence10.5555/3298023.3298162(4089-4095)Online publication date: 4-Feb-2017
https://dl.acm.org/doi/10.5555/3298023.3298162
Yang XLiu ZQiao HSu J(2017)Probabilistic hypergraph matching based on affinity tensor updatingNeurocomputing10.1016/j.neucom.2016.12.096269:C(142-147)Online publication date: 20-Dec-2017
https://dl.acm.org/doi/10.1016/j.neucom.2016.12.096
Show More Cited By

Abstract

Cited By

Recommendations

A Path Following Algorithm for the Graph Matching Problem

Semidefinite programming approach for the quadratic assignment problem with a sparse graph

A graph matching algorithm based on concavely regularized convex relaxation

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations