Unsupervised Learning for Graph Matching | International Journal of Computer Vision Skip to main content
Springer Nature Link
Log in

Unsupervised Learning for Graph Matching

  • Published:
International Journal of Computer Vision Aims and scope Submit manuscript

Abstract

Graph matching is an essential problem in computer vision that has been successfully applied to 2D and 3D feature matching and object recognition. Despite its importance, little has been published on learning the parameters that control graph matching, even though learning has been shown to be vital for improving the matching rate. In this paper we show how to perform parameter learning in an unsupervised fashion, that is when no correct correspondences between graphs are given during training. Our experiments reveal that unsupervised learning compares favorably to the supervised case, both in terms of efficiency and quality, while avoiding the tedious manual labeling of ground truth correspondences. We verify experimentally that our learning method can improve the performance of several state-of-the art graph matching algorithms. We also show that a similar method can be successfully applied to parameter learning for graphical models and demonstrate its effectiveness empirically.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  • Bach, F. R., & Jordan, M. I. (2003). Learning spectral clustering. In Neural Information Processing Systems.

    Google Scholar 

  • Baratchart, L., Berthod, M., & Pottier, L. (1998). Optimization of positive generalized polynomials under l p constraints. Journal of Convex Analysis, 5(2), 353–379.

    MATH  MathSciNet  Google Scholar 

  • Belongie, S., Malik, J., & Puzicha, J. (2002). Shape matching and object recognition using shape context. Pattern Analysis and. IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(4), 509–522.

    Article  Google Scholar 

  • Berg, A., Berg, T., & Malik, J. (2005). Shape matching and object recognition using low distortion correspondences. In International Conference on Computer Vision and Pattern Recognition.

    Google Scholar 

  • Besag, J. (1986). On the statistical analysis of dirty pictures. Journal of the Royal Statistical Society, 48(5), 259–302.

    MATH  MathSciNet  Google Scholar 

  • Brendel, W., & Todorovic, S. (2010). Segmentation as maximum-weight independent set. In Neural Information Processing Systems.

    Google Scholar 

  • Caetano, T., Cheng, L., Le, Q. V., & Smola, A. J. (2007). Learning graph matching. In International Conference on Computer Vision.

    Google Scholar 

  • Caetano, T., McAuley, J. J., Cheng, L., Le, Q. V., & Smola, A. J. (2009). Learning graph matching. IEEE Transactions on Pattern Analysis and Machine Intelligence, 31(6), 1048–1058.

    Article  Google Scholar 

  • Carcassoni, M., & Hancock, E. R. (2002). Alignment using spectral clusters. In British Machine Vision Conference.

    Google Scholar 

  • Chertok, M., & Keller, Y. (2010). Spectral symmetry analysis. Pattern Analysis and. IEEE Transactions on Pattern Analysis and Machine Intelligence, 32(7), 1227–1238.

    Article  Google Scholar 

  • Cour, T., & Shi, J. (2007). Solving Markov random fields with spectral relaxation. In International Conference on Artificial Intelligence and Statistics.

    Google Scholar 

  • Cour, T., Shi, J., & Gogin, N. (2005). Learning spectral graph segmentation. In International Conference on Artificial Intelligence and Statistics.

    Google Scholar 

  • Cour, T., Srinivasan, P., & Shi, J. (2006). Balanced graph matching. In Neural Information Processing Systems.

    Google Scholar 

  • de Aguiar, E., Stoll, C., Theobalt, C., Ahmed, N., Seidel, H.-P., & Thrun, S. (2008). Performance capture from sparse multi-view video. In SIGGRAPH.

    Google Scholar 

  • Duchenne, O., Bach, F., Kweon, I., & Ponce, J. (2009). A tensor-based algorithm for high-order graph matching. In International Conference on Computer Vision and Pattern Recognition.

    Google Scholar 

  • Frank, M., & Wolfe, P. (1956). An algorithm for quadratic programming. Naval Research Logistics Quarterly, 3(1–2), 95–110.

    Article  MathSciNet  Google Scholar 

  • Gold, S., & Rangarajan, A. (1996). A graduated assignment algorithm for graph matching. Pattern Analysis and. IEEE Transactions on Pattern Analysis and Machine Intelligence, 18(4), 377–388.

    Article  Google Scholar 

  • Hays, J., Leordeanu, M., Efros, A., & Liu, Y. (2006). Discovering texture regularity as a higher-order correspondence problem. In European Conference on Computer Vision.

    Google Scholar 

  • Huhle, B., Jenke, P., & Straßer, W. (2008). On-the-fly scene acquisition with a handy multi-sensor system. International Journal of Intelligent Systems Technologies and Applications, 5(3–4), 255–263.

    Article  Google Scholar 

  • Kim, G., Faloutsos, C., & Hebert, M. (2008). Unsupervised modeling and recognition of object categories with combination of visual contents and geometric similarity links. In ACM International Conference on Multimedia Information Retrieval.

    Google Scholar 

  • Kim, G., Faloutsos, C., & Hebert, M. (2008). Unsupervised modeling of object categories using link analysis techniques. In International Conference on Computer Vision and Pattern Recognition.

    Google Scholar 

  • Kumar, S. Models for learning spatial interactions in natural images for context-based classification. PhD thesis, The Robotics Institute, Carnegie Mellon University, 2005.

  • Leordeanu, M., Collins, R., & Hebert, M. (2005). Unsupervised learning of object features from video sequences. In International Conference on Computer Vision and Pattern Recognition.

    Google Scholar 

  • Leordeanu, M., & Hebert, M. (2005). A spectral technique for correspondence problems using pairwise constraints. In International Conference on Computer Vision.

    Google Scholar 

  • Leordeanu, M., & Hebert, M. (2006). Efficient MAP approximation for dense energy functions. In International Conference on Machine Learning.

    Google Scholar 

  • Leordeanu, M., & Hebert, M. (2008). Smoothing-based optimization. In International Conference on Computer Vision and Pattern Recognition.

    Google Scholar 

  • Leordeanu, M., & Hebert, M. (2009). Unsupervised learning for graph matching. In International Conference on Computer Vision and Pattern Recognition.

    Google Scholar 

  • Leordeanu, M., Hebert, M., & Sukthankar, R. (2007). Beyond local appearance: Category recognition from pairwise interactions of simple features. In International Conference on Computer Vision and Pattern Recognition.

    Google Scholar 

  • Leordeanu, M., Hebert, M., & Sukthankar, R. (2009). An integer projected fixed point method for graph matching and MAP inference. In Neural Information Processing Systems.

    Google Scholar 

  • Liu, J., Luo, J., & Shah, M. (2009). Recognizing realistic actions from videos “in the wild. In International Conference on Computer Vision and Pattern Recognition.

    Google Scholar 

  • Magnus, J., & Neudecker, H. (1999). Matrix Differential Calculus with Applications in Statistics and Econometrics. New York: Wiley.

    MATH  Google Scholar 

  • Parikh, D., & Chen, T. (2007). Unsupervised identification of multiple objects of interest from multiple images: dISCOVER. In Asian Conference on Computer Vision.

    Google Scholar 

  • Parikh, D., & Chen, T. (2007). Unsupervised learning of hierarchical semantics of objects (hSOs). In International Conference on Computer Vision and Pattern Recognition.

    Google Scholar 

  • Ravikumar, P., & Lafferty, J. (2006). Quadratic programming relaxations for metric labeling and Markov random field MAP estimation. In International Conference on Machine Learning.

    Google Scholar 

  • Ren, X. (2007). Learning and matching line aspects for articulated objects. In International Conference on Computer Vision and Pattern Recognition.

    Google Scholar 

  • Schellewald, C., & Schnorr, C. (2005). Probabilistic subgraph matching based on convex relaxation. In International Conference on Energy Minimization Methods in Computer Vision and Pattern Recognition.

    Google Scholar 

  • Semenovich, D. (2010). Tensor power method for efficient MAP inference in higher-order MRFs. In International Conference on Pattern Recognition.

    Google Scholar 

  • Szummer, M., Kohli, P., & Hoiem, D. (2008). Learning CRFs using graph cuts. In European Conference on Computer Vision.

    Google Scholar 

  • Taskar, B., Guestrin, C., & Koller, D. (2004). Max-margin Markov networks. In Neural Information Processing Systems.

    Google Scholar 

  • Umeyama, S. (1988). An eigen decomposition approach to weighted graph matching problems. In Pattern Analysis and Machine Intelligence.

    Google Scholar 

  • Yan, P., Khan, S. M., & Shah, M. (2008). Learning 4D action feature models for arbitrary view action recognition. In International Conference on Computer Vision and Pattern Recognition.

    Google Scholar 

  • Zaslavskiy, M. Graph matching and its application in computer vision and bioinformatics. PhD thesis, l’Ecole nationale superieure des mines de Paris, 2010.

  • Zaslavskiy, M., Bach, F., & Vert, J.-P. (2009). A path following algorithm for graph matching. IEEE Transactions on Pattern Analysis and Machine Intelligence, 31(12), 2227–2242.

    Article  Google Scholar 

  • Zass, R., & Shashua, A. (2008). Probabilistic graph and hypergraph matching. In International Conference on Computer Vision and Pattern Recognition.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Mathematics of the Romanian Academy, 21 Calea Grivitei, Bucharest, Romania

    Marius Leordeanu

  2. Intel Labs Pittsburgh, Pittsburgh, PA, 15213, USA

    Rahul Sukthankar

  3. Carnegie Mellon University, 5000 Forbes Ave, Pittsburgh, PA, 15213, USA

    Martial Hebert

Authors
  1. Marius Leordeanu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Rahul Sukthankar
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Martial Hebert
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Marius Leordeanu.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Leordeanu, M., Sukthankar, R. & Hebert, M. Unsupervised Learning for Graph Matching. Int J Comput Vis 96, 28–45 (2012). https://doi.org/10.1007/s11263-011-0442-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11263-011-0442-2

Keywords

Search

Navigation