The DOI matches its Crossref record; 39 of the 39 references it cites were found in a registry or an index.
Learning Graph Matching
Abstract
As a fundamental problem in pattern recognition, graph matching has applications in a variety of fields, from computer vision to computational biology. In graph matching, patterns are modeled as graphs and pattern recognition amounts to finding a correspondence between the nodes of different graphs. Many formulations of this problem can be cast in general as a quadratic assignment problem, where a linear term in the objective function encodes node compatibility and a quadratic term encodes edge compatibility. The main research focus in this theme is about designing efficient algorithms for approximately solving the quadratic assignment problem, since it is NP-hard. In this paper we turn our attention to a different question: how to estimate compatibility functions such that the solution of the resulting graph matching problem best matches the expected solution that a human would manually provide. We present a method for learning graph matching: the training examples are pairs of graphs and the 'labels' are matches between them. Our experimental results reveal that learning can substantially improve the performance of standard graph matching algorithms. In particular, we find that simple linear assignment with such a learning scheme outperforms Graduated Assignment with bistochastic normalisation, a state-of-the-art quadratic assignment relaxation algorithm.
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
Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond
Schölkopf, B., & Smola, A. J. (2001) · The MIT Press eBooks · doi:10.7551/mitpress/4175.001.0001 · Cited by 11,703
Self-citationKernel Methods for Pattern Analysis
Shawe-Taylor, J., & Cristianini, N. (2004) · Cambridge University Press eBooks · doi:10.1017/cbo9780511809682 · Cited by 6,587
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
Combinatorial Optimization: Algorithms and Complexity.
Johnson, D. S., Papadimitriou, C. H., & Steiglitz, K. (1984) · The American Mathematical Monthly · doi:10.2307/2322374 · Cited by 5,942
(1982) · Elsevier eBooks · doi:10.1016/c2009-0-21955-6 · Cited by 4,596
Combinatorial optimization:Algorithms and complexity
Rabiner, L. (1984) · IEEE Transactions on Acoustics, Speech, and Signal Processing · doi:10.1109/tassp.1984.1164450 · Cited by 3,576
(2007) · CaltechAUTHORS (California Institute of Technology) · Cited by 2,274
Training linear SVMs in linear time
Joachims, T. (2006) · Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1150402.1150429 · Cited by 1,920
Large Margin Methods for Structured and Interdependent Output Variables
Tsochantaridis, I., Joachims, T., Hofmann, T., & Altün, Y. (2005) · MPG.PuRe (Max Planck Society) · Cited by 1,879
A shortest augmenting path algorithm for dense and sparse linear assignment problems
Jonker, R., & Volgenant, A. (1987) · Computing · doi:10.1007/bf02278710 · Cited by 1,230
A spectral technique for correspondence problems using pairwise constraints
Leordeanu, M., & Hebert, M. (2005) · Tenth IEEE International Conference on Computer Vision (ICCV'05) Volume 1 · doi:10.1109/iccv.2005.20 · Cited by 1,222
Taskar, B., Guestrin, C., & Koller, D. (2003) · Cited by 1,206
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
A Relationship Between Arbitrary Positive Matrices and Doubly Stochastic Matrices
Sinkhorn, R. (1964) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177703591 · Cited by 1,032
Numerical Geometry of Non-Rigid Shapes
Bronstein, A. M., Bronstein, M. M., & Kimmel, R. (2009) · Monographs in Computer Science · doi:10.1007/978-0-387-73301-2 · Cited by 734
Ahuja, R. K., & Orlin, J. B. (2001) · Operations Research · doi:10.1287/opre.49.5.771.10607 · Cited by 497
Structural matching in computer vision using probabilistic relaxation
Christmas, W. J., Kittler, J., & Petrou, M. (1995) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.400565 · Cited by 495
Cour, T., Srinivasan, P., & Shi, J. (2007) · Advances in Neural Information Processing Systems 19 · doi:10.7551/mitpress/7503.003.0044 · Cited by 443
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
A new algorithm for error-tolerant subgraph isomorphism detection
Messmer, B., & Bunke, H. (1998) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.682179 · Cited by 348
Structural matching by discrete relaxation
Wilson, R. C., & Hancock, E. R. (1997) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.601251 · Cited by 311
Training structural SVMs when exact inference is intractable
Finley, T., & Joachims, T. (2008) · Proceedings of the 25th international conference on Machine learning - ICML '08 · doi:10.1145/1390156.1390195 · Cited by 260
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
A scalable modular convex solver for regularized risk minimization
Teo, C. H., Smola, A., Vishwanathan, S. V. N., & Le, Q. V. (2007) · Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1281192.1281270 · Cited by 171
Self-citationReplicator Equations, Maximal Cliques, and Graph Isomorphism
Pelillo, M. (1999) · Neural Computation · doi:10.1162/089976699300016034 · Cited by 166
Graphical Models and Point Pattern Matching
Caetano, T. S., Caelli, T., Schuurmans, D., & Barone, D. A. C. (2006) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2006.207 · Cited by 130
Self-citationAutomatic learning of cost functions for graph edit distance
Neuhaus, M., & Horst Bunke, A. (2006) · Information Sciences · doi:10.1016/j.ins.2006.02.013 · Cited by 118
Analysis of Two-Dimensional Non-Rigid Shapes
Bronstein, A. M., Bronstein, M. M., Bruckstein, A. M., & Kimmel, R. (2007) · International Journal of Computer Vision · doi:10.1007/s11263-007-0078-4 · Cited by 112
Learning compatibility coefficients for relaxation labeling processes
Pelillo, M., & Refice, M. (1994) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.310691 · Cited by 84
A RKHS interpolator-based graph matching algorithm
van Wyk, M. A., Durrani, T. S., & van Wyk, B. J. (2002) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2002.1017624 · Cited by 65
Caetano, T. S., Cheng, L., Le, Q. V., & Smola, A. J. (2007) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2007.4408838 · Cited by 60
Self-citationSmith, S. F. (1992) · Springer eBooks · doi:10.1007/978-1-4471-3201-1_15 · Cited by 56
Convergence Properties of the Softassign Quadratic Assignment Algorithm
Rangarajan, A., Yuille, A., & Mjolsness, E. (1999) · Neural Computation · doi:10.1162/089976699300016313 · Cited by 52
A Markov random field model for object matching under contextual constraints
Li (1994) · doi:10.1109/cvpr.1994.323915 · Cited by 38
Constellations and the Unsupervised Learning of Graphs
Bonev, B., Escolano, F. J., Lozano, M. Á., et al. (2007) · Lecture notes in computer science · doi:10.1007/978-3-540-72903-7_31 · Cited by 27
Graph-Based Methods for Vision: A Yorkist Manifesto
Hancock, E. R., & Wilson, R. C. (2002) · Lecture notes in computer science · doi:10.1007/3-540-70659-3_3 · Cited by 19
Flexible filter neighbourhood designation
Smith, S. M. (1996) · Proceedings - International Conference on Pattern Recognition/Proceedings/International Conference on Pattern Recognition · doi:10.1109/icpr.1996.546020 · Cited by 18
Graphical models for graph matching
Caetano, T. S., Caelli, T., & Barone, D. A. C. (2004) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2004.1315201 · Cited by 11
Self-citation
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
Optimal Transport for Domain Adaptation
Courty, N., Flamary, R., Tuia, D., & Rakotomamonjy, A. (2017) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2016.2615921 · Cited by 989
A Survey on Shape Correspondence
van Kaick, O., Zhang, H., Hamarneh, G., & Cohen‐Or, D. (2011) · Computer Graphics Forum · doi:10.1111/j.1467-8659.2011.01884.x · Cited by 606
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
Zhou, 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
- Caetano, T. S., McAuley, J. J., Cheng, L., Le, Q. V., & Smola, A. J.
- Venue
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- Published
- 2009-06
- Volume
- 31
- Issue
- 6
- Pages
- 1048-1058
- ISSN
- 0162-8828 (ISSN-L)
- OpenAlex
- W2150760714
- Cited by
- 383
- References
- 39
- FWCI
- 24.92
- Type
- journal article
- Language
- en
- Open access
- closed
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.