More Web Proxy on the site http://driver.im/

research-article

Geometric graph matching and similarity: a probabilistic approach

Authors:

Michael GertzAuthors Info & Claims

SSDBM '14: Proceedings of the 26th International Conference on Scientific and Statistical Database Management

Article No.: 27, Pages 1 - 12

https://doi.org/10.1145/2618243.2618259

Published: 30 June 2014 Publication History

Abstract

Finding common structures is vital for many graph-based applications, such as road network analysis, pattern recognition, or drug discovery. Such a task is formalized as the inexact graph matching problem, which is known to be NP-hard. Several graph matching algorithms have been proposed to find approximate solutions. However, such algorithms still face many problems in terms of memory consumption, runtime, and tolerance to changes in graph structure or labels.

In this paper, we propose a solution to the inexact graph matching problem for geometric graphs in 2D space. Geometric graphs provide a suitable modeling framework for applications like the above, where vertices are located in some 2D space. The main idea of our approach is to formalize the graph matching problem in a maximum likelihood estimation framework. Then, the expectation maximization technique is used to estimate the match between two graphs. We propose a novel density function that estimates the similarity between the vertices of different graphs. It is computed based on both 1) the spatial properties of a vertex and its direct neighbors, and 2) the shortest paths that connect a vertex to other vertices in a graph. To guarantee scalability, we propose to compute the density function based on the properties of sub-structures of the graph. Using representative geometric graphs from several application domains, we show that our approach outperforms existing graph matching algorithms in terms of matching quality, runtime, and memory consumption.

References

[1]

CMU house and hotel datasets. http://vasc.ri.cmu.edu/idb/html/motion. Accessed: 03/06/2013.

[2]

Road networks dataset. http://www.cs.utah.edu/~lifeifei/SpatialDataset.htm. Accessed: 14/07/2013.

[3]

A. Armiti and M. Gertz. Efficient Geometric Graph Matching Using Vertex Embedding. In SIGSPATIAL GIS, pages 234--243, 2013.

Digital Library

[4]

T. Caetano, J. McAuley, L. Cheng, Q. Le, and A. Smola. Learning Graph Matching. IEEE Trans. Pattern Anal. Mach. Intell., 31(6):1048--1058, 2009.

Digital Library

[5]

T. S. Caetano, T. M. Caelli, D. Schuurmans, and D. A. C. Barone. Graphical Models and Point Pattern Matching. IEEE Trans. Pattern Anal. Mach. Intell., 28(10):1646--1663, 2006.

Digital Library

[6]

O. Cheong, J. Gudmundsson, H. Kim, D. Schymura, and F. Stehn. Measuring the Similarity of Geometric Graphs. Experimental Algorithms, pages 101--112, 2009.

Digital Library

[7]

M. Cho, J. Lee, and K. M. Lee. Reweighted Random Walks for Graph Matching. In ECCV (5), volume 6315 of LNCS, pages 492--505, 2010.

Digital Library

[8]

D. Conte, P. Foggia, C. Sansone, and M. Vento. Thirty Years Of Graph Matching In Pattern Recognition. IJPRAI, 18(3):265--298, 2004.

[9]

A. Dempster, N. Laird, and D. Rubin. Maximum likelihood from incomplete data via the EM algorithm. J. of the Royal Statistical Society, 39(B):1--38, 1977.

[10]

P. Doshi, R. Kolli, and C. Thomas. Inexact matching of ontology graphs using expectation-maximization. Journal of Web Semantics, 7(2):90--106, 2009.

Digital Library

[11]

D. H. Douglas and T. K. Peuker. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. The Canadian Geographer, 10(2):112--122, 1973.

[12]

X. Gao, B. Xiao, D. Tao, and X. Li. A survey of graph edit distance. Pattern. Anal. Appl., 13(1):113--129, 2010.

Digital Library

[13]

C. Harris and M. Stephens. A combined corner and edge detector. In Fourth Alvey Vision Conference, pages 147--151, 1988.

[14]

M. Kuramochi and G. Karypis. Discovering Frequent Geometric Subgraphs. In ICDM, pages 258--265, 2002.

Digital Library

[15]

B. Luo and E. R. Hancock. Structural graph matching using the EM algorithm and singular value decomposition. IEEE Trans. Pattern Anal. Mach. Intell., 23(10):1120--1136, 2001.

Digital Library

[16]

M. Maes. On a cyclic string-to-string correction problem. Inform. Process. Lett., 35(2):73--78, 1990.

Digital Library

[17]

J. Munkres. Algorithms for the assignment and transportation problems. Journal of the Society for Industrial and Applied Mathematics, 5(1):32--38, 1957.

[18]

S. A. Nene, S. K. Nayar, and H. Murase. Columbia Object Image Library (COIL-100). Technical report, Columbia University, Feb 1996.

[19]

L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank citation ranking: Bringing order to the Web. In WWW, pages 161--172, 1998.

[20]

K. Riesen and H. Bunke. IAM Graph Database Repository for Graph Based Pattern Recognition and Machine Learning. In S+SSPR, pages 287--297, 2008.

Digital Library

[21]

K. Riesen and H. Bunke. Approximate graph edit distance computation by means of bipartite graph matching. Image and Vision Computing, 27(7):950--959, 2009.

Digital Library

[22]

Y. Rubner, C. Tomasi, and L. Guibas. A metric for distributions with applications to image databases. In ICCV, pages 59--66, 1998.

Digital Library

[23]

C. Sanderson. Armadillo: An Open Source C++ Linear Algebra Library for Fast Prototyping and Computationally Intensive Experiments. Technical report, NICTA, Australia, October 2010.

[24]

G. Sanromà, R. Alquézar, and F. Serratosa. A new graph matching method for point-set correspondence using the EM algorithm and Softassign. Comput. Vis. Image Und., 116(2):292--304, 2012.

Digital Library

[25]

G. L. Scott and H. C. L. Higgins. An algorithm for associating the features of two images. Proceedings of Royal Society of London, B-244:21--26, 1991.

[26]

R. Sinkhorn. A Relationship Between Arbitrary Positive Matrices and Doubly Stochastic Matrices. Ann. Math. Stat., 35(2):876--879, 1964.

[27]

J. Tang, B. Jiang, A. Zheng, and B. Luo. Graph matching based on spectral embedding with missing value. Pattern Recognition, 45(10):3768--3779, 2012.

Digital Library

[28]

S. Umeyama. An eigendecomposition approach to weighted graph matching problems. IEEE Trans. Pattern Anal. Mach. Intell., 10(5):695--703, 1988.

Digital Library

[29]

R. Wagner and M. Fischer. The string-to-string correction problem. JACM, 21(1):168--173, 1974.

Digital Library

[30]

Z. Zeng, A. K. H. Tung, J. Wang, J. Feng, and L. Zhou. Comparing Stars: On Approximating Graph Edit Distance. PVLDB, 2(1):25--36, 2009.

Digital Library

Cited By

Deng LLiu SXu WLin X(2024)Similarity measurement for graph data: an improved centrality and geometric perspective-based approachBig Data Research10.1016/j.bdr.2024.100462(100462)Online publication date: Apr-2024
https://doi.org/10.1016/j.bdr.2024.100462
Dwivedi S(2022)Approximate Bipartite Graph Matching by Modifying Cost MatrixInternational Conference on Artificial Intelligence and Sustainable Engineering10.1007/978-981-16-8546-0_34(415-422)Online publication date: 8-Apr-2022
https://doi.org/10.1007/978-981-16-8546-0_34
Pavithra RPriyadharshini.P SHemanandhini I(2021)Image Matching using Weighted Graph Matching Algorithm2021 7th International Conference on Advanced Computing and Communication Systems (ICACCS)10.1109/ICACCS51430.2021.9442037(1-5)Online publication date: 19-Mar-2021
https://doi.org/10.1109/ICACCS51430.2021.9442037
Show More Cited By

Index Terms

Geometric graph matching and similarity: a probabilistic approach
1. Information systems
  1. Information systems applications
    1. Data mining
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms

Recommendations

Efficient geometric graph matching using vertex embedding
SIGSPATIAL'13: Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems

For many applications such as road network analysis and image processing, it is critical to study spatial properties of objects in addition to object relationships. Geometric graphs provide a suitable modeling framework for such applications, where ...
Error-tolerant geometric graph similarity and matching
Highlights
- An intuitive approach to graph similarity and matching using geometric graphs.
- ...
Abstract
Geometric graph matching is the process of evaluating the similarity between geometric graphs, where each vertex has an associated coordinate point in a plane. Exact matching computes a strict correspondence between two geometric ...
Error-Tolerant Geometric Graph Similarity
Structural, Syntactic, and Statistical Pattern Recognition
Abstract
Graph matching is the task of computing the similarity between two graphs. Error-tolerant graph matching is a type of graph matching, in which a similarity between two graphs is computed based on some tolerance value whereas within exact graph ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

SSDBM '14: Proceedings of the 26th International Conference on Scientific and Statistical Database Management

June 2014

417 pages

ISBN:9781450327220

DOI:10.1145/2618243

Editors:
Christian S. Jensen
Aalborg University
,
Hua Lu
Aalborg University
,
Torben Bach Pedersen
Aalborg University
,
Christian Thomsen
Aalborg University
,
Kristian Torp
Aalborg University

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 June 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SSDBM '14

SSDBM '14: Conference on Scientific and Statistical Database Management

June 30 - July 2, 2014

Aalborg, Denmark

Acceptance Rates

SSDBM '14 Paper Acceptance Rate 26 of 71 submissions, 37%;

Overall Acceptance Rate 56 of 146 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
322
Total Downloads

Downloads (Last 12 months)17
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Deng LLiu SXu WLin X(2024)Similarity measurement for graph data: an improved centrality and geometric perspective-based approachBig Data Research10.1016/j.bdr.2024.100462(100462)Online publication date: Apr-2024
https://doi.org/10.1016/j.bdr.2024.100462
Dwivedi S(2022)Approximate Bipartite Graph Matching by Modifying Cost MatrixInternational Conference on Artificial Intelligence and Sustainable Engineering10.1007/978-981-16-8546-0_34(415-422)Online publication date: 8-Apr-2022
https://doi.org/10.1007/978-981-16-8546-0_34
Pavithra RPriyadharshini.P SHemanandhini I(2021)Image Matching using Weighted Graph Matching Algorithm2021 7th International Conference on Advanced Computing and Communication Systems (ICACCS)10.1109/ICACCS51430.2021.9442037(1-5)Online publication date: 19-Mar-2021
https://doi.org/10.1109/ICACCS51430.2021.9442037
Akitaya HBuchin MKilgus BSijben SWenk C(2021)Distance Measures for Embedded GraphsComputational Geometry10.1016/j.comgeo.2020.101743(101743)Online publication date: Jan-2021
https://doi.org/10.1016/j.comgeo.2020.101743
Agarwal SDutta SBhattacharya A(2020)ChiSeLProceedings of the VLDB Endowment10.14778/3401960.340196413:10(1654-1668)Online publication date: 1-Jun-2020
https://dl.acm.org/doi/10.14778/3401960.3401964
Dwivedi SSingh R(2018)Error-Tolerant Geometric Graph SimilarityStructural, Syntactic, and Statistical Pattern Recognition10.1007/978-3-319-97785-0_32(337-344)Online publication date: 2-Aug-2018
https://doi.org/10.1007/978-3-319-97785-0_32
Armiti AGertz M(2016)Geometric Graph Indexing for Similarity Search in Scientific DatabasesProceedings of the 28th International Conference on Scientific and Statistical Database Management10.1145/2949689.2949691(1-12)Online publication date: 18-Jul-2016
https://dl.acm.org/doi/10.1145/2949689.2949691
Uysal MBeecks CSchmücking JSeidl T(2015)Efficient similarity search in scientific databases with feature signaturesProceedings of the 27th International Conference on Scientific and Statistical Database Management10.1145/2791347.2791384(1-12)Online publication date: 29-Jun-2015
https://dl.acm.org/doi/10.1145/2791347.2791384

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents