A graduated assignment algorithm for graph matching
Abstract
A graduated assignment algorithm for graph matching is presented which is fast and accurate even in the presence of high noise. By combining graduated nonconvexity, two-way (assignment) constraints, and sparsity, large improvements in accuracy and speed are achieved. Its low order computational complexity [O(lm), where l and m are the number of links in the two graphs] and robustness in the presence of noise offer advantages over traditional combinatorial approaches. The algorithm, not restricted to any special class of graph, is applied to subgraph isomorphism, weighted graph matching, and attributed relational graph matching. To illustrate the performance of the algorithm, attributed relational graphs derived from objects are matched. Then, results from twenty-five thousand experiments conducted on 100 mode random graphs of varying types (graphs with only zero-one links, weighted graphs, and graphs with node attributes and multiple link types) are reported. No comparable results have been reported by any other graph matching algorithm before in the research literature. Twenty-five hundred control experiments are conducted using a relaxation labeling algorithm and large improvements in accuracy are demonstrated.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
[65] uses the term to maximize correspondences and bias the objective function towards more matches. This maximizes the overlapping area.
“Maximizing Correspondences: [65] uses the term i j M ij to maximize correspondences and bias the objective function towards more matches (i.e. it favors M ij = 1 over M ij = 0).This maximizes the overlapping area.”
From Registration of 3D Point Clouds and Meshes: A Survey from Rigid to Nonrigid (2013) · cites this paper as [65]
[65] casts registration as a continuous optimization problem that handles both rigid transformation and correspondence determination simultaneously. It uses CPC, and formulates a regularization term based on entropy. This term can be interpreted as equalizing the importances of point matches, forcing them to the same distance and thus causing the surfaces to run parallel, rather than intersecting.
“Equalization: [65] casts registration as a continuous optimization problem that handles both rigid transformation and correspondence determination simultaneously.It uses CPC, and formulates a regularization term based on entropy:i j M ij log M ij where M is the matching probability matrix of all correspondences.When all point matches are equally likely, the entropy reaches a maximum.This term can”
From Registration of 3D Point Clouds and Meshes: A Survey from Rigid to Nonrigid (2013) · cites this paper as [65]
Cites
(1979) · Cited by 43,841 · see citing works
Parallel and Distributed Computation: Numerical Methods
Bertsekas, D. P., & Tsitsiklis, J. N. (1989) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 5,398 · see citing works
Linear and nonlinear programming.
(1986) · Mathematics and Computers in Simulation · doi:10.1016/0378-4754(86)90092-3 · Cited by 4,806 · see citing works
(1982) · Elsevier eBooks · doi:10.1016/c2009-0-21955-6 · Cited by 4,628 · see citing works
Hierarchical Mixtures of Experts and the EM Algorithm
Jordan, M. I., & Jacobs, R. A. (1994) · Neural Computation · doi:10.1162/neco.1994.6.2.181 · Cited by 2,730 · see citing works
(2003) · WORLD SCIENTIFIC eBooks · doi:10.1142/9789812796936_others05 · Cited by 2,465 · see citing works
Blake, A., & Zisserman, A. (1987) · The MIT Press eBooks · doi:10.7551/mitpress/7132.001.0001 · Cited by 2,093 · see citing works
Branch-and-Bound Methods: A Survey
Lawler, E. L., & Wood, D. (1966) · Operations Research · doi:10.1287/opre.14.4.699 · Cited by 2,018 · see citing works
The Traveling Salesman Problem
Snyder, L., & Shen, Z. M. (2019) · doi:10.1002/9781119584445.ch10 · Cited by 1,620 · see citing works
Scene Labeling by Relaxation Operations
Rosenfeld, A., Hummel, R. A., & Zucker, S. W. (1976) · IEEE Transactions on Systems Man and Cybernetics · doi:10.1109/tsmc.1976.4309519 · Cited by 1,402 · see citing works
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 · see citing works
On the Foundations of Relaxation Labeling Processes
Hummel, R. A., & Zucker, S. W. (1983) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1983.4767390 · Cited by 885 · see citing works
Linear and nonlinear programming
Sydsæter, K., Strøm, A., & Berck, P. (1999) · Springer eBooks · doi:10.1007/978-3-662-03995-3_15 · Cited by 864 · see citing works
Black, M. J., & Rangarajan, A. (1996) · International Journal of Computer Vision · doi:10.1007/bf00131148 · Cited by 770 · see citing works
Self-citationAn 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 740 · see citing works
On the stability of the Travelling Salesman Problem algorithm of Hopfield and Tank
Wilson, G., & Pawley, G. S. (1988) · Biological Cybernetics · doi:10.1007/bf00363956 · Cited by 548 · see citing works
Structural Descriptions and Inexact Matching
Shapiro, L. G., & Haralick, R. M. (1981) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1981.4767144 · Cited by 546 · see citing works
Constructing simple stable descriptions for image partitioning
Leclerc, Y. G. (1989) · International Journal of Computer Vision · doi:10.1007/bf00054839 · Cited by 521 · see citing works
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 494 · see citing works
Parallel and deterministic algorithms from MRFs: surface reconstruction
Geiger, D., & Girosi, F. (1991) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.134040 · Cited by 452 · see citing works
A NEW METHOD FOR MAPPING OPTIMIZATION PROBLEMS ONTO NEURAL NETWORKS
Peterson, C., & Söderberg, B. (1989) · International Journal of Neural Systems · doi:10.1142/s0129065789000414 · Cited by 451 · see citing works
Shape Matching Using Relaxation Techniques
Davis, L. S. (1979) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1979.4766876 · Cited by 264 · see citing works
A linear programming approach for the weighted graph matching problem
Al-Mohamad, H. A., & Duffuaa, S. O. (1993) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.211474 · Cited by 244 · see citing works
Graph partitioning using annealed neural networks
den Bout, D. E. V., & Miller, T. K., III (1990) · IEEE Transactions on Neural Networks · doi:10.1109/72.80231 · Cited by 218 · see citing works
Registering Landsat images by point matching
Ton, J., & Jain, A. K. (1989) · IEEE Transactions on Geoscience and Remote Sensing · doi:10.1109/tgrs.1989.35948 · Cited by 190 · see citing works
A graph distance measure for image analysis
Eshera, M. A., & Fu, K. (1984) · IEEE Transactions on Systems Man and Cybernetics · doi:10.1109/tsmc.1984.6313232 · Cited by 186 · see citing works
A New Probabilistic Relaxation Scheme
Peleg, B. (1980) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1980.4767035 · Cited by 185 · see citing works
Improving Consistency and Reducing Ambiguity in Stochastic Labeling: An Optimization Approach
Faugeras, O. D., & Berthod, M.-A. (1981) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1981.4767127 · Cited by 181 · see citing works
A common framework for image segmentation
Geiger, D., & Yuille, A. (1991) · International Journal of Computer Vision · doi:10.1007/bf00115697 · Cited by 181 · see citing works
An Image Understanding System Using Attributed Symbolic Representation and Inexact Graph-Matching
Eshera, M. A., & Fu, K. (1986) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1986.4767835 · Cited by 180 · see citing works
Object recognition using multilayer Hopfield neural network
Young, S. S., Scott, P., & Nasrabadi, N. M. (1997) · IEEE Transactions on Image Processing · doi:10.1109/83.557336 · Cited by 161 · see citing works
The invisible hand algorithm: Solving the assignment problem with statistical physics
Kosowsky, J. J., & Yuille, A. (1994) · Neural Networks · doi:10.1016/0893-6080(94)90081-7 · Cited by 151 · see citing works
A Step Towards Unification of Syntactic and Statistical Pattern Recognition
Fu, K. S. (1986) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1986.4767800 · Cited by 136 · see citing works
Statistical Physics Algorithms That Converge
Yuille, A., & Kosowsky, J. J. (1994) · Neural Computation · doi:10.1162/neco.1994.6.3.341 · Cited by 124 · see citing works
Subgraph error-correcting isomorphisms for syntactic pattern recognition
Tsai, W., & Fu, K. (1983) · IEEE Transactions on Systems Man and Cybernetics · doi:10.1109/tsmc.1983.6313029 · Cited by 122 · see citing works
Matching: Invariant to translations, rotations and scale changes
Li, S. Z. (1992) · Pattern Recognition · doi:10.1016/0031-3203(92)90075-t · Cited by 113 · see citing works
New Algorithms for 2D and 3D Point Matching: Pose Estimation and Correspondence
Gold, S., Lu, C.-P., Rangarajan, A., et al. (1994) · Cited by 109 · see citing works
Self-citationRelaxation Matching Techniques-A Comparison
Price, K. (1985) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1985.4767709 · Cited by 100 · see citing works
Statistical Physics, Mixtures of Distributions, and the EM Algorithm
Yuille, A., Stolorz, P., & Utans, J. (1994) · Neural Computation · doi:10.1162/neco.1994.6.2.334 · Cited by 100 · see citing works
Computing with structured neural networks
Feldman, J. A., Fanty, M., & Goodard, N. H. (1988) · Computer · doi:10.1109/2.34 · Cited by 94 · see citing works
On problem solving with Hopfield neural networks
Kamgar-Parsi, B., & Kamgar-Parsi, B. (1990) · Biological Cybernetics · doi:10.1007/bf00197648 · Cited by 89 · see citing works
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 85 · see citing works
A Novel Optimizing Network Architecture with Applications
Rangarajan, A., Gold, S., & Mjolsness, E. (1996) · Neural Computation · doi:10.1162/neco.1996.8.5.1041 · Cited by 83 · see citing works
Self-citationPattern recognition by graph matching using the Potts MFT neural networks
Suganthan, P. N., Teoh, E. K., & Mital, D. P. (1995) · Pattern Recognition · doi:10.1016/0031-3203(94)00166-j · Cited by 79 · see citing works
Constrained Nets for Graph Matching and Other Quadratic Assignment Problems
Simić, P. (1991) · Neural Computation · doi:10.1162/neco.1991.3.2.268 · Cited by 70 · see citing works
Learning with Preknowledge: Clustering with Point and Graph Matching Distance Measures
Gold, S., Rangarajan, A., & Mjolsness, E. (1996) · Neural Computation · doi:10.1162/neco.1996.8.4.787 · Cited by 69 · see citing works
Self-citationAlgebraic transformations of objective functions
Mjolsness, E., & Garrett, C. (1990) · Neural Networks · doi:10.1016/0893-6080(90)90055-p · Cited by 58 · see citing works
Optimization in Model Matching and Perceptual Organization
Mjolsness, E., Gindi, G. R., & Anandan, P. (1989) · Neural Computation · doi:10.1162/neco.1989.1.2.218 · Cited by 57 · see citing works
Lange, K. L. (2010) · Springer texts in statistics · doi:10.1007/978-1-4419-7165-4_5 · Cited by 51 · see citing works
Relaxation by the Hopfield neural network
Yu, S.-S., & Tsai, W. (1992) · Pattern Recognition · doi:10.1016/0031-3203(92)90101-n · Cited by 50 · see citing works
PATTERN RECOGNITION BY GRAPH MATCHING—COMBINATORIAL VERSUS CONTINUOUS OPTIMIZATION
Kuner, P., & Ueberreiter, B. (1988) · International Journal of Pattern Recognition and Artificial Intelligence · doi:10.1142/s0218001488000303 · Cited by 40 · see citing works
Generalized graduated nonconvexity algorithm for maximum a posteriori image estimation
Rangarajan, A., & Chellappa, R. (2002) · Proceedings - International Conference on Pattern Recognition/Proceedings/International Conference on Pattern Recognition · doi:10.1109/icpr.1990.119342 · Cited by 37 · see citing works
Self-citationA neural network approach to CSG-based 3-D object recognition
Chen, T.-W., & Lin, W. (1994) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.297953 · Cited by 35 · see citing works
On problem solving with Hopfield neural networks
Kamgar-Parsi, & Kamgar-Parsi (1989) · doi:10.1109/ijcnn.1989.118363 · Cited by 23 · see citing works
Object recognition using multi-layer Hopfield neural network
Young, Scott, & Nasrabadi (1994) · doi:10.1109/cvpr.1994.323860 · Cited by 20 · see citing works
Application of genetic algorithms in graph matching
Krcmar, M., & Dhawan, A. P. (1994) · doi:10.1109/icnn.1994.374829 · Cited by 17 · see citing works
Clustering with a Domain-Specific Distance Measure
Gold, S., Mjolsness, E., & Rangarajan, A. (1993) · Cited by 13 · see citing works
Self-citationA Lagrangian relaxation network for graph matching
Rangarajan, A., & Mjolsness, E. (2002) · doi:10.1109/icnn.1994.375022 · Cited by 13 · see citing works
Self-citationDPA: a deterministic approach to the MAP problem
Berthod, M.-A., Kató, Z., & Zerubia, J. B. (1995) · IEEE Transactions on Image Processing · doi:10.1109/83.413175 · Cited by 11 · see citing works
Mean-field phase transitions and correlation functions for Gibbs random fields
Elfadel, I. M., & Yuille, A. (1993) · Journal of Mathematical Imaging and Vision · doi:10.1007/bf01250528 · Cited by 6 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
A new point matching algorithm for non-rigid registration
Chui, H., & Rangarajan, A. (2003) · Computer Vision and Image Understanding · doi:10.1016/s1077-3142(03)00009-2 · Cited by 1,560 · see citing works
Self-citationRegistration of 3D Point Clouds and Meshes: A Survey from Rigid to Nonrigid
Tam, G. K. L., Cheng, Z.-Q., Lai, Y.-K., Langbein, F. C., Liu, Y., Marshall, D., Martin, R. R., Sun, X.-F., & Rosin, P. L. (2013) · IEEE Transactions on Visualization and Computer Graphics · doi:10.1109/tvcg.2012.310 · Cited by 679 · see citing works
Automatic rigging and animation of 3D characters
Baran, I., & Popović, J. (2007) · ACM SIGGRAPH 2007 papers · doi:10.1145/1275808.1276467 · Cited by 495 · see citing works
“We considered adapting an approximate graph matching algorithm, like [Gold and Rangarajan 1996], which would work much faster and enable more complicated reduced skeletons.”
MethodAutomatic rigging and animation of 3D characters
Baran, I., & Popović, J. (2007) · ACM Transactions on Graphics · doi:10.1145/1276377.1276467 · Cited by 455 · see citing works
Opromolla, R., Fasano, G., Rufino, G., & Grassi, M. (2017) · Progress in Aerospace Sciences · doi:10.1016/j.paerosci.2017.07.001 · Cited by 330 · see citing works
Grauman, K., & Leibe, B. (2011) · Synthesis Lectures on Artificial Intelligence and Machine Learning · doi:10.2200/s00332ed1v01y201103aim011 · Cited by 126 · see citing works
Autonomous relative navigation around uncooperative spacecraft based on a single camera
Pesce, V., Opromolla, R., Sarno, S., Lavagna, M., & Grassi, M. (2019) · Aerospace Science and Technology · doi:10.1016/j.ast.2018.11.042 · Cited by 80 · see citing works
Automatic 3d free form shape matching using the graduated assignment algorithm
Liu, Y. (2005) · Pattern Recognition · doi:10.1016/j.patcog.2005.01.008 · Cited by 37 · see citing works
Probabilistic analogical mapping with semantic relation networks.
Lu, H., Ichien, N., & Holyoak, K. J. (2022) · Psychological Review · doi:10.1037/rev0000358 · Cited by 25 · see citing works
- Authors
- Gold, S., & Rangarajan, A.
- Affiliations
- Yale University (US)
- ORCID
- Rangarajan, A.
- Venue
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- Published
- 1996-04
- Volume
- 18
- Issue
- 4
- Pages
- 377-388
- ISSN
- 0162-8828 (ISSN-L)
- OpenAlex
- W2159537329
- Cited by
- 1,090
- References
- 60
- Citations by year
- 2026: 6 · 2025: 10 · 2024: 11 · 2023: 18 · 2022: 26 · 2021: 30 · 2020: 40 · 2019: 37 · 2018: 41 · 2017: 37 · 2016: 56 · 2015: 67 · 2014: 44 · 2013: 35 · 2012: 60
- FWCI
- 31.19
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- IEEE Transactions on Pattern Analysis and Machine Intelligence (publishedVersion)
- Funders
- Yale University
- Office of Naval Research
- Topics
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Graph Theory and Algorithms
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Advanced Image and Video Retrieval Techniques
- Physical Sciences › Mathematics › Geometry and Topology › Graph theory and applications
- Keywords
- graph matching, subgraph isomorphism, attributed relational graphs, sparsity, noise robustness, computational complexity, relaxation labeling, combinatorial optimization
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
