The DOI matches its Crossref record; 34 of the 34 references it cites were found in a registry or an index.
A Path Following Algorithm for the Graph Matching Problem
Open accessAbstract
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 matrices and relaxing it to two different optimization problems: a quadratic convex and a quadratic concave optimization problem on the set of doubly stochastic matrices. The concave relaxation has the same global minimum as the initial graph matching problem, but the search for its global minimum is also a hard combinatorial problem. We, therefore, construct an approximation of the concave problem solution by following a solution path of a convex-concave problem obtained by linear interpolation of the convex and concave formulations, starting from the convex relaxation. This method allows to easily integrate the information on graph label similarities into the optimization problem, and therefore, perform labeled weighted graph matching. The algorithm is compared with some of the best performing graph matching methods on four data sets: simulated graphs, QAPLib, retina vessel images, and handwritten Chinese characters. In all cases, the results are competitive with the state of the art.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Boyd, S., & Vandenberghe, L. (2004) · doi:10.1017/cbo9780511804441 · Cited by 56,601
(1979) · Cited by 43,841
The Hungarian method for the assignment problem
Kuhn, H. W. (1955) · Naval Research Logistics Quarterly · doi:10.1002/nav.3800020109 · Cited by 13,120
Bertsekas, D. P. (1997) · Journal of the Operational Research Society · doi:10.1038/sj.jors.2600425 · Cited by 11,726
Rockafellar, R. T. (1970) · Princeton University Press eBooks · doi:10.1515/9781400873173 · Cited by 10,801
Shape matching and object recognition using shape contexts
Belongie, S., Malik, J., & Puzicha, J. (2002) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.993558 · Cited by 6,306
Golub, G. H., & Loan, C. F. V. (1996) · Johns Hopkins University Press eBooks · Cited by 6,027
Chung, F. (1996) · CBMS Regional Conference Series in Mathematics · doi:10.1090/cbms/092 · Cited by 5,524
Principal warps: thin-plate splines and the decomposition of deformations
Bookstein, F. L. (1989) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.24792 · Cited by 4,913
Random graphs with arbitrary degree distributions and their applications
Newman, M. E. J., Strogatz, S. H., & Watts, D. J. (2001) · Physical Review E · doi:10.1103/physreve.64.026118 · Cited by 3,648
An algorithm for quadratic programming
Frank, M., & Wolfe, P. (1956) · Naval Research Logistics Quarterly · doi:10.1002/nav.3800030109 · Cited by 3,030
An Algorithm for Subgraph Isomorphism
Ullmann, J. R. (1976) · Journal of the ACM · doi:10.1145/321921.321925 · Cited by 2,277
Blake, A., & Zisserman, A. (1987) · The MIT Press eBooks · doi:10.7551/mitpress/7132.001.0001 · Cited by 2,105
Parlar, M. (2000) · Interactive Operations Research with Maple · doi:10.1007/978-1-4612-1356-7_5 · Cited by 1,741
Topology from the Differentiable Viewpoint.
Brown, E. H., & Milnor, J. W. (1967) · The American Mathematical Monthly · doi:10.2307/2314613 · Cited by 1,418
THIRTY YEARS OF GRAPH MATCHING IN PATTERN RECOGNITION
CONTE, D., FOGGIA, P., SANSONE, C., & VENTO, M. (2004) · International Journal of Pattern Recognition and Artificial Intelligence · doi:10.1142/s0218001404003228 · Cited by 1,370
Numerical Continuation Methods
Allgower, E. L., & Georg, K. (1990) · Springer Series in Computational Mathematics · doi:10.1007/978-3-642-61257-2 · Cited by 1,269
A graduated assignment algorithm for graph matching
Gold, S., & Rangarajan, A. (1996) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.491619 · Cited by 1,090
Convex Analysis and Nonlinear Optimization
Borwein, J. M., & Lewis, A. S. (2006) · CMS books in mathematics · doi:10.1007/978-0-387-31256-9 · Cited by 780
Inparanoid: a comprehensive database of eukaryotic orthologs
O'Brien, K. P. (2004) · Nucleic Acids Research · doi:10.1093/nar/gki107 · Cited by 742
An eigendecomposition approach to weighted graph matching problems
Umeyama, S. (1988) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.6778 · Cited by 727
QAPLIB – A Quadratic Assignment Problem Library
Burkard, R. E., Karisch, S. E., & Rendl, F. (1997) · Journal of Global Optimization · doi:10.1023/a:1008293323270 · Cited by 654
Feature-based correspondence: an eigenvector approach
Shapiro, L. S., & Michael Brady, J. (1992) · Image and Vision Computing · doi:10.1016/0262-8856(92)90043-3 · Cited by 427
Convex Analysis and Nonlinear Optimization
Borwein, J. M., & Lewis, A. S. (2000) · Springer eBooks · doi:10.1007/978-1-4757-9859-3 · Cited by 394
Pairwise Global Alignment of Protein Interaction Networks by Matching Neighborhood Topology
Singh, R., Xu, J., & Berger, B. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-71681-5_2 · Cited by 286
A linear programming approach for the weighted graph matching problem
Almohamad, H. A., & Duffuaa, S. O. (1993) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.211474 · Cited by 241
Performance evaluation of the VF graph matching algorithm
Cordella, L. P., Foggia, P., Sansone, C., & Vento, M. (2003) · Proceedings 10th International Conference on Image Analysis and Processing · doi:10.1109/iciap.1999.797762 · Cited by 226
An eigenspace projection clustering method for inexact graph matching
Caelli, T., & Kosinov, S. (2004) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2004.1265866 · Cited by 204
Spectral correspondence for point pattern matching
Carcassoni, M., & Hancock, E. R. (2003) · Pattern Recognition · doi:10.1016/s0031-3203(02)00054-7 · Cited by 175
Probabilistic Subgraph Matching Based on Convex Relaxation
Schellewald, C., & Schnörr, C. (2005) · Lecture Notes in Computer Science · doi:10.1007/11585978_12 · Cited by 162
Correspondence matching using kernel principal components analysis and label consistency constraints
Wang, H. F., & Hancock, E. R. (2005) · Pattern Recognition · doi:10.1016/j.patcog.2005.05.013 · Cited by 26
Schellewald, C., Roth, S., & Schnörr, C. (2001) · Lecture notes in computer science · doi:10.1007/3-540-45404-7_48 · Cited by 20
Alignment and Correspondence Using Singular Value Decomposition
Luo, B., & Hancock, E. R. (2000) · Lecture notes in computer science · doi:10.1007/3-540-44522-6_24 · Cited by 8
Cited by
Image Matching from Handcrafted to Deep Features: A Survey
Ma, J., Jiang, X., Fan, A., Jiang, J., & Yan, J. (2021) · International Journal of Computer Vision · doi:10.1007/s11263-020-01359-2 · Cited by 990
A review of multimodal image matching: Methods and applications
Jiang, X., Ma, J., Xiao, G., Shao, Z., & Guo, X. (2021) · Information Fusion · doi:10.1016/j.inffus.2021.02.012 · Cited by 532
Intelligent Reflecting Surface: A Programmable Wireless Environment for Physical Layer Security
Chen, J., Liang, Y.-C., Pei, Y., & Guo, H. (2019) · IEEE Access · doi:10.1109/access.2019.2924034 · Cited by 507
A Tensor-Based Algorithm for High-Order Graph Matching
Duchenne, O., Bach, F., Kweon, I.-S., & Ponce, J. (2011) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2011.110 · Cited by 358
Self-citationZhou, F., & De la Torre, F. (2012) · 2012 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2012.6247667 · Cited by 272
Metadata
- Authors
- Zaslavskiy, M., Bach, F., & Vert, J.-P.
- Venue
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- Published
- 2009-12
- Volume
- 31
- Issue
- 12
- Pages
- 2227-2242
- ISSN
- 0162-8828 (ISSN-L)
- OpenAlex
- W2166524953
- Cited by
- 385
- References
- 34
- FWCI
- 10.98
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.