The DOI matches its Crossref record; 39 of the 39 references it cites were found in a registry or an index.
Structural graph matching using the EM algorithm and singular value decomposition
Open accessAbstract
This paper describes an efficient algorithm for inexact graph matching. The method is purely structural, that is, it uses only the edge or connectivity structure of the graph and does not draw on node or edge attributes. We make two contributions: 1) commencing from a probability distribution for matching errors, we show how the problem of graph matching can be posed as maximum-likelihood estimation using the apparatus of the EM algorithm; and 2) we cast the recovery of correspondence matches between the graph nodes in a matrix framework. This allows one to efficiently recover correspondence matches using the singular value decomposition. We experiment with the method on both real-world and synthetic data. Here, we demonstrate that the method offers comparable performance to more computationally demanding methods.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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
Maximum Likelihood from Incomplete Data Via the EM Algorithm
Dempster, A. P., Laird, N. M., & Rubin, D. B. (1977) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1977.tb01600.x · Cited by 50,444
Neural networks for pattern recognition
(1994) · Choice Reviews Online · doi:10.5860/choice.31-5500 · Cited by 18,538
Neural Networks for Pattern Recognition
Bishop, C. M. (1995) · doi:10.1093/oso/9780198538493.001.0001 · Cited by 12,287
Pattern Recognition and Neural Networks
Ripley, B. D. (1996) · Cambridge University Press eBooks · doi:10.1017/cbo9780511812651 · Cited by 6,459
Chung, F. (1996) · CBMS Regional Conference Series in Mathematics · doi:10.1090/cbms/092 · Cited by 5,524
An Algorithm for Subgraph Isomorphism
Ullmann, J. R. (1976) · Journal of the ACM · doi:10.1145/321921.321925 · Cited by 2,277
Mixture models : inference and applications to clustering
McLachlan, G. J., & Basford, K. E. (1988) · M. Dekker eBooks · Cited by 2,094
The Representation and Matching of Pictorial Structures
Fischler, M. A., & Elschlager, R. A. (1973) · IEEE Transactions on Computers · doi:10.1109/t-c.1973.223602 · Cited by 1,322
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
Mixture Models: Inference and Applications to Clustering.
Lindsay, B., McLachlan, G. L., Basford, K. E., & Dekker, M. (1989) · Journal of the American Statistical Association · doi:10.2307/2289892 · Cited by 1,062
A distance measure between attributed relational graphs for pattern recognition
Sanfeliu, A., & Fu, K.-S. (1983) · IEEE Transactions on Systems, Man, and Cybernetics · doi:10.1109/tsmc.1983.6313167 · Cited by 999
A graph distance metric based on the maximal common subgraph
Bunke, H., & Shearer, K. (1998) · Pattern Recognition Letters · doi:10.1016/s0167-8655(97)00179-7 · Cited by 754
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
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
Inexact graph matching for structural pattern recognition
Bunke, H., & Allermann, G. (1983) · Pattern Recognition Letters · doi:10.1016/0167-8655(83)90033-8 · Cited by 487
Pairwise data clustering by deterministic annealing
Hofmann, T., & Buhmann, J. M. (1997) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.566806 · Cited by 451
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 443
An algorithm for associating the features of two images
(1991) · Proceedings of the Royal Society of London. Series B: Biological Sciences · doi:10.1098/rspb.1991.0045 · Cited by 440
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
Matching hierarchical structures using association graphs
Pelillo, M., Siddiqi, K., & Zucker, S. W. (1999) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.809105 · Cited by 394
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
Self-citationEntropy and Distance of Random Graphs with Application to Structural Pattern Recognition
Wong, A. K. C., & You, M. (1985) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1985.4767707 · Cited by 291
Error correcting graph matching: on the influence of the underlying cost function
Bunke, H. (1999) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.790431 · Cited by 229
Graph matching with a dual-step EM algorithm
Cross, A. D. J., & Hancock, E. R. (1998) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.730557 · Cited by 216
Self-citationAn Image Understanding System Using Attributed Symbolic Representation and Inexact Graph-Matching
Eshera, M. A., & Fu, K.-S. (1986) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1986.4767835 · Cited by 179
Replicator Equations, Maximal Cliques, and Graph Isomorphism
Pelillo, M. (1999) · Neural Computation · doi:10.1162/089976699300016034 · Cited by 166
Indexing using a spectral encoding of topological structure
Shokoufandeh, A., Dickinson, S., Kaleem Siddiqi, A., & Zucker, S. W. (2003) · 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.1999.784726 · Cited by 156
A versatile system for computer-controlled assembly
Ambler, A. P., Barrow, H. G., Brown, C. M., Burstall, R. M., & Popplestone, R. J. (1975) · Artificial Intelligence · doi:10.1016/0004-3702(75)90006-5 · Cited by 128
Statistical Physics Algorithms That Converge
Yuille, A., & Kosowsky, J. J. (1994) · Neural Computation · doi:10.1162/neco.1994.6.3.341 · Cited by 125
A versatile computer-controlled assembly system
Ambler, A. P., Barrow, H. G., Brown, C. M., Burstall, R. H., & Popplestone, R. J. (1973) · International Joint Conference on Artificial Intelligence · Cited by 123
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 97
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
Pattern 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 78
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
Deterministic search for relational graph matching
Williams, M., Wilson, R. C., & Hancock, E. R. (1999) · Pattern Recognition · doi:10.1016/s0031-3203(98)00152-6 · Cited by 56
Self-citationIndexing based on edit-distance matching of shape graphs
Tirthapura, S., Sharvit, D., Klein, P. N., & Kimia, B. B. (1998) · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · doi:10.1117/12.325825 · Cited by 49
Corner detection via topographic analysis of vector-potential
Luo, B., Cross, A. D. J., & Hancock, E. R. (1999) · Pattern Recognition Letters · doi:10.1016/s0167-8655(99)00028-8 · Cited by 40
Self-citationAn Energy Function and Continuous Edit Process for Graph Matching
Finch, A. M., Wilson, R. C., & Hancock, E. R. (1998) · Neural Computation · doi:10.1162/089976698300017188 · Cited by 30
Self-citationFinch, A., Wilson, R. C., & Hancock, E. R. (1996) · neural information processing systems · Cited by 10
Self-citation
Cited by
Point Set Registration: Coherent Point Drift
Myronenko, A., & Song, X. (2010) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2010.46 · Cited by 2,762
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
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
Machine learning and radiology
Wang, S., & Summers, R. M. (2012) · Medical Image Analysis · doi:10.1016/j.media.2012.02.005 · Cited by 697
Ma, J., Qiu, W., Zhao, J., Ma, Y., Yuille, A. L., & Tu, Z. (2015) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2014.2388434 · Cited by 280
Metadata
- Authors
- Luo, B., & Hancock, E. R.
- Venue
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- Published
- 2001
- Volume
- 23
- Issue
- 10
- Pages
- 1120-1136
- ISSN
- 0162-8828 (ISSN-L)
- OpenAlex
- W2152132697
- Cited by
- 345
- References
- 39
- FWCI
- 22.87
- 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.