{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,16]],"date-time":"2025-10-16T06:52:30Z","timestamp":1760597550205},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2012,9,25]],"date-time":"2012-09-25T00:00:00Z","timestamp":1348531200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2013,6]]},"DOI":"10.1007\/s00778-012-0292-8","type":"journal-article","created":{"date-parts":[[2012,9,24]],"date-time":"2012-09-24T08:39:28Z","timestamp":1348475968000},"page":"345-368","source":"Crossref","is-referenced-by-count":25,"title":["High efficiency and quality: large graphs matching"],"prefix":"10.1007","volume":"22","author":[{"given":"Yuanyuan","family":"Zhu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lu","family":"Qin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeffrey Xu","family":"Yu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yiping","family":"Ke","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,9,25]]},"reference":[{"key":"292_CR1","doi-asserted-by":"crossref","unstructured":"Abu-Khzam, F.N., Samatova, N.F., Rizk, M.A., Langston, M.A.: The maximum common subgraph problem: faster solutions via vertex cover. In: AICCSA, pp. 367\u2013373 (2007)","DOI":"10.1109\/AICCSA.2007.370907"},{"issue":"5","key":"292_CR2","doi-asserted-by":"crossref","first-page":"522","DOI":"10.1109\/34.211474","volume":"15","author":"HA Almohamad","year":"1993","unstructured":"Almohamad, H.A., Duffuaa, S.O.: A linear programming approach for the weighted graph matching problem. IEEE Trans. Pattern Anal. Mach. Intell. 15(5), 522\u2013525 (1993)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"292_CR3","doi-asserted-by":"crossref","unstructured":"Arora, S., Safra, S.: Approximating clique is np-complete. In: Proceedings of the 33rd IEEE Symposium on Foundations on Computer Science, pp. 2\u201313 (1992)","DOI":"10.1109\/SFCS.1992.267824"},{"key":"292_CR4","doi-asserted-by":"crossref","unstructured":"Bai, X., Yu, H., Hancock, E.: Graph matching using spectral embedding and alignment. In: Proceedings of International Conference on Pattern Recognition, pp. 398\u2013401 (2004)","DOI":"10.5244\/C.18.32"},{"issue":"5439","key":"292_CR5","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"A Barab\u00e1si","year":"1999","unstructured":"Barab\u00e1si, A., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509 (1999)","journal-title":"Science"},{"issue":"6","key":"292_CR6","doi-asserted-by":"crossref","first-page":"1373","DOI":"10.1162\/089976603321780317","volume":"15","author":"M Belkin","year":"2003","unstructured":"Belkin, M., Niyogi, P.: Laplacian eigenmaps for dimensionality reduction and data representation. Neural Comput. 15(6), 1373\u20131396 (2003)","journal-title":"Neural Comput."},{"key":"292_CR7","doi-asserted-by":"crossref","unstructured":"Bernard, M., Richard, N., Paquereau, J.: Functional brain imaging by eeg graph-matching. In: 27th Annual International Conference of the IEEE Engineering in Medicine and Biology Society (EMBC\u201905), pp. 5309\u20135312 (2005)","DOI":"10.1109\/IEMBS.2005.1615679"},{"issue":"4","key":"292_CR8","doi-asserted-by":"crossref","first-page":"647","DOI":"10.1137\/S0036144502415960","volume":"46","author":"V Blondel","year":"2004","unstructured":"Blondel, V., Gajardo, A., Heymans, M., Senellart, P., Van Dooren, P.: A measure of similarity between graph vertices: Applications to synonym extraction and web searching. Siam Rev. 46(4), 647\u2013666 (2004)","journal-title":"Siam Rev."},{"key":"292_CR9","unstructured":"Bonchi, F., Esfandiar, P., Gleich, D.F., Greif, C., Lakshmanan, L.V.S.: Fast matrix computations for pair-wise and column-wise commute times and katz scores. CoRR abs\/1104.3791 (2011)"},{"key":"292_CR10","unstructured":"Caelli, T., Kosinov, S.: An eigenspace projection clustering method for inexact graph matching. IEEE Trans. Pattern Anal. Mach. Intell. 26(4), 515\u2013519 (2004)"},{"issue":"3","key":"292_CR11","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1142\/S0218001404003186","volume":"18","author":"T Caelli","year":"2004","unstructured":"Caelli, T., Kosinov, S.: Inexact graph matching using eigen-subspace projection clustering. Int. J. Pattern Recognit. Artif. Intell. 18(3), 329\u2013354 (2004)","journal-title":"Int. J. Pattern Recognit. Artif. Intell."},{"issue":"8","key":"292_CR12","doi-asserted-by":"crossref","first-page":"939","DOI":"10.1016\/j.patrec.2006.12.009","volume":"28","author":"F Chevalier","year":"2007","unstructured":"Chevalier, F., Domenger, J.P., Benois-Pineau, J., Delest, M.: Retrieval of objects in video by similarity based on graph matching. Pattern Recogn. Lett. 28(8), 939\u2013949 (2007)","journal-title":"Pattern Recogn. Lett."},{"issue":"3","key":"292_CR13","first-page":"265","volume":"18","author":"D Conte","year":"2004","unstructured":"Conte, D., Foggia, P., Sansone, C., Vento, M.: Thirty years of graph matching in pattern recognition. IJPRAI 18(3), 265\u2013298 (2004)","journal-title":"IJPRAI"},{"issue":"4","key":"292_CR14","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1023\/A:1013470632383","volume":"7","author":"KC Foster","year":"2001","unstructured":"Foster, K.C., Muth, S.Q., Potterat, J.J., Rothenberg, R.B.: A faster katz status score algorithm. Comput. Math. Organ. Theory 7(4), 275\u2013285 (2001)","journal-title":"Comput. Math. Organ. Theory"},{"key":"292_CR15","doi-asserted-by":"crossref","unstructured":"Jouili, S., Tabbone, S.: Graph matching based on node signatures. In: GbRPR, pp. 154\u2013163 (2009)","DOI":"10.1007\/978-3-642-02124-4_16"},{"key":"292_CR16","doi-asserted-by":"crossref","unstructured":"Kleinberg, J.M.: Authoritative sources in a hyperlinked environment. J. ACM 46(5), 604\u2013632 (1999)","DOI":"10.1145\/324133.324140"},{"key":"292_CR17","doi-asserted-by":"crossref","unstructured":"Knossow, D., Sharma, A., Mateus, D., Horaud, R.: Inexact matching of large and sparse graphs using laplacian eigenvectors. In: Proceedings of the 7th IAPR-TC-15 International Workshop on Graph-Based Representations in Pattern Recognition, p. 153. Springer (2009)","DOI":"10.1007\/978-3-642-02124-4_15"},{"key":"292_CR18","doi-asserted-by":"crossref","unstructured":"Koch, I.: Enumerating all connected maximal common subgraphs in two graphs. Theor. Comput. Sci. 250(1\u20132), 1\u201330 (2001)","DOI":"10.1016\/S0304-3975(00)00286-3"},{"issue":"6","key":"292_CR19","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1002\/spe.588","volume":"34","author":"E Krissinel","year":"2004","unstructured":"Krissinel, E., Henrick, K.: Common subgraph isomorphism detection by backtracking search. Softw. Practice Experience 34(6), 591\u2013607 (2004)","journal-title":"Softw. Practice Experience"},{"key":"292_CR20","doi-asserted-by":"crossref","unstructured":"Lee, W., Duin, R.: An inexact graph comparison approach in joint eigenspace. In: Proceedings of the 2008 Joint IAPR International Workshop on Structural, Syntactic, and Statistical Pattern Recognition, p. 44. Springer (2008)","DOI":"10.1007\/978-3-540-89689-0_8"},{"issue":"1","key":"292_CR21","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1002\/spe.4380120103","volume":"12","author":"J McGregor","year":"1982","unstructured":"McGregor, J.: Backtrack search algorithms and the maximal common subgraph problem. Softw. Practice Experience 12(1), 23\u201334 (1982)","journal-title":"Softw. Practice Experience"},{"key":"292_CR22","unstructured":"Melnik, S., Garcia-Molina, H., Rahm, E.: Similarity flooding: a versatile graph matching algorithm and its application to schema matching. In: ICDE, pp. 117\u2013128 (2002)"},{"key":"292_CR23","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1080\/00107510500052444","volume":"46","author":"MEJ Newman","year":"2005","unstructured":"Newman, M.E.J.: Power laws, pareto distributions and zipf\u2019s law. Contemp. Phys. 46, 323\u2013351 (2005)","journal-title":"Contemp. Phys."},{"key":"292_CR24","doi-asserted-by":"crossref","unstructured":"Ogata, H., Fujibuchi, W., Goto, S., Kanehisa, M.: A heuristic graph comparison algorithm and its application to detect functionally related enzyme clusters. Nucleic Acids Res. 28(20), 4021\u20134028 (2000)","DOI":"10.1093\/nar\/28.20.4021"},{"issue":"1","key":"292_CR25","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1016\/j.patcog.2005.06.014","volume":"39","author":"H Qiu","year":"2006","unstructured":"Qiu, H., Hancock, E.: Graph matching and clustering using spectral partitions. Pattern Recognit. 39(1), 22\u201334 (2006)","journal-title":"Pattern Recognit."},{"key":"292_CR26","doi-asserted-by":"crossref","unstructured":"Raymond, J., Gardiner, E., Willett, P.: Rascal: Calculation of graph similarity using maximum common edge subgraphs. Comput. J. 45(6), 631 (2002)","DOI":"10.1093\/comjnl\/45.6.631"},{"key":"292_CR27","doi-asserted-by":"crossref","unstructured":"Riesen, K., Jiang, X., Bunke, H.: Exact and inexact graph matching: methodology and applications. In: Managing and Mining Graph Data (Chapter 7) (2010)","DOI":"10.1007\/978-1-4419-6045-0_7"},{"key":"292_CR28","doi-asserted-by":"crossref","unstructured":"Singh, R., Xu, J., Berger, B.: Pairwise global alignment of protein interaction networks by matching neighborhood topology. In: Research in Computational Molecular Biology, pp. 16\u201331. Springer (2007)","DOI":"10.1007\/978-3-540-71681-5_2"},{"key":"292_CR29","doi-asserted-by":"crossref","unstructured":"Suters, W., Abu-Khzam F., Zhang, Y., Symons, C., Samatova, N., Langston, M.: A new approach and faster exact methods for the maximum common subgraph problem. Comput. Comb. 717\u2013727 (2005)","DOI":"10.1007\/11533719_73"},{"issue":"3","key":"292_CR30","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1007\/s10115-007-0094-2","volume":"14","author":"H Tong","year":"2008","unstructured":"Tong, H., Faloutsos, C., Pan, J.-Y.: Random walk with restart: fast solutions and applications. Knowl. Inf. Syst. 14(3), 327\u2013346 (2008)","journal-title":"Knowl. Inf. Syst."},{"issue":"1","key":"292_CR31","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1145\/321921.321925","volume":"23","author":"J Ullmann","year":"1976","unstructured":"Ullmann, J.: An algorithm for subgraph isomorphism. J. ACM (JACM) 23(1), 42 (1976)","journal-title":"J. ACM (JACM)"},{"issue":"5","key":"292_CR32","doi-asserted-by":"crossref","first-page":"695","DOI":"10.1109\/34.6778","volume":"10","author":"S Umeyama","year":"1988","unstructured":"Umeyama, S.: An eigendecomposition approach to weighted graph matching problems. IEEE Trans. Pattern Anal. Mach. Intell. 10(5), 695\u2013703 (1988)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"6684","key":"292_CR33","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1038\/30918","volume":"393","author":"D Watts","year":"1998","unstructured":"Watts, D., Strogatz, S.: Collective dynamics of \u2018small-world\u2019 networks. Nature 393(6684), 440\u2013442 (1998)","journal-title":"Nature"},{"issue":"7","key":"292_CR34","doi-asserted-by":"crossref","first-page":"777","DOI":"10.1016\/j.cviu.2009.01.004","volume":"113","author":"B Xiao","year":"2009","unstructured":"Xiao, B., Hancock, E., Wilson, R.: A generative model for graph matching and embedding. Comput. Vis. Image Underst. 113(7), 777\u2013789 (2009)","journal-title":"Comput. Vis. Image Underst."},{"issue":"5","key":"292_CR35","doi-asserted-by":"crossref","first-page":"812","DOI":"10.1109\/3477.956043","volume":"31","author":"L Xu","year":"2001","unstructured":"Xu, L., King, I.: A PCA approach for fast retrieval of structural patterns in attributed graphs. IEEE Trans. Syst. Man Cybern. B Cybern. 31(5), 812\u2013817 (2001)","journal-title":"IEEE Trans. Syst. Man Cybern. B Cybern."},{"issue":"12","key":"292_CR36","doi-asserted-by":"crossref","first-page":"2227","DOI":"10.1109\/TPAMI.2008.245","volume":"31","author":"M Zaslavskiy","year":"2009","unstructured":"Zaslavskiy, M., Bach, F., Vert, J.: A path following algorithm for the graph matching problem. IEEE Trans. Pattern Anal. Mach. Intell. 31(12), 2227\u20132242 (2009)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"12","key":"292_CR37","doi-asserted-by":"crossref","first-page":"i259","DOI":"10.1093\/bioinformatics\/btp196","volume":"25","author":"M Zaslavskiy","year":"2009","unstructured":"Zaslavskiy, M., Bach, F., Vert, J.: Global alignment of protein-protein interaction networks by graph matching methods. Bioinformatics 25(12), i259 (2009)","journal-title":"Bioinformatics"},{"key":"292_CR38","doi-asserted-by":"crossref","unstructured":"Zhu, Y., Qin, L., Yu, J.X., Ke, Y., Lin, X.: High efficiency and quality: large graphs matching. In: CIKM (2011)","DOI":"10.1145\/2063576.2063831"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-012-0292-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00778-012-0292-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-012-0292-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,29]],"date-time":"2022-01-29T14:26:33Z","timestamp":1643466393000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00778-012-0292-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,9,25]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,6]]}},"alternative-id":["292"],"URL":"https:\/\/doi.org\/10.1007\/s00778-012-0292-8","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,9,25]]}}}