A Descriptive Tolerance Nearness Measure for Performing Graph Comparison

Henry, C. J.; Awais, S. A.

doi:10.3233/FI-2018-1746

Artykuł - szczegóły

Tytuł artykułu

A Descriptive Tolerance Nearness Measure for Performing Graph Comparison

Autorzy

Henry C. J. , Awais S. A.

Wybrane pełne teksty z tego czasopisma

https://fi.episciences.org/

Identyfikatory

DOI

10.3233/FI-2018-1746

Warianty tytułu

Języki publikacji

Abstrakty

This article proposes the tolerance nearness measure (TNM) as a computationally reduced alternative to the graph edit distance (GED) for performing graph comparisons. The TNM is defined within the context of near set theory, where the central idea is that determining similarity between sets of disjoint objects is at once intuitive and practically applicable. The TNM between two graphs is produced using the Bron-Kerbosh maximal clique enumeration algorithm. The result is that the TNM approach is less computationally complex than the bipartite-based GED algorithm. The contribution of this paper is the application of TNM to the problem of quantifying the similarity of disjoint graphs and that the maximal clique enumeration-based TNM produces comparable results to the GED when applied to the problem of content-based image processing, which becomes important as the number of nodes in a graph increases.

Słowa kluczowe

graph edit distance graph matching maximal clique enumeration near sets tolerance nearness measure

Wydawca

IOS Press

Czasopismo

Fundamenta Informaticae

Rocznik

2018

Tom

Vol. 163, nr 4

Strony

305--324

Opis fizyczny

Bibliogr. 117 poz., rys., tab., wykr.

Twórcy

autor

Henry C. J.

ch.henry@uwinnipeg.ca

Department of Applied Computer Science, University of Winnipeg, Portage avenue R3B 2E9, Manitoba, Canada

autor

Awais S. A.

Department of Applied Computer Science, University of Winnipeg, Portage avenue R3B 2E9, Manitoba, Canada

Bibliografia

[1] Riesen K. Structural Pattern Recognition with Graph Edit Distance: Approximation Algorithms and Applications. Springer, 2016. ISBN-978-3-319-27251-1. doi:10.1007/978-3-319-27252-8.
[2] Zager LA, Verghese GC. Graph similarity scoring and matching. Applied Mathematics Letters, 2008. 21(1):86-94. URL https://doi.org/10.1016/j.aml.2007.01.006.
[3] Cortés X, Serratosa F. Learning Graph-matching Edit-costs Based on the Optimality of the Oracle’s Node Correspondences. Pattern Recogn. Lett., 2015. 56(C):22-29. URL https://doi.org/10.1016/j.patrec.2015.01.009.
[4] Corts X, Serratosa F. An interactive method for the image alignment problem based on partially supervised correspondence. Expert Systems with Applications, 2015. 42(1):179-192. URL https://doi.org/10.1016/j.eswa.2014.07.051.
[5] Wang JZ, Li J, Wiederhold G. SIMPLIcity: Semantics-sensitive Integrated Matching for Picture Libraries. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2001. 23(9):947-963.
[6] Moreno-García CF, Serratosa F. Correspondence consensus of two sets of correspondences through optimisation functions. Pattern Analysis and Applications, 2017. 20(1):201-213. doi:10.1007/s10044-015-0486-y. URL https://doi.org/10.1007/s10044-015-0486-y.
[7] Li T, Dong H, Shi Y, Dehmer M. A comparative analysis of new graph distance measures and graph edit distance. Information Sciences, 2017. 403404:15-21. URL https://doi.org/10.1016/j.ins.2017.03.036.
[8] Conte D, Foggia P, Sansone C, Vento M. THIRTY YEARS OF GRAPH MATCHING IN PATTERN RECOGNITION. International Journal of Pattern Recognition and Artificial Intelligence, 2004. 18(03):265-298. URL https://doi.org/10.1142/S0218001404003228.
[9] Serratosa F, Cortés X. Interactive graph-matching using active query strategies. Pattern Recognition, 2015. 48(4):1364-1373. URL https://doi.org/10.1016/j.patcog.2014.10.033.
[10] Cortés X, Serratosa F. Learning graph-matching edit-costs based on the optimality of the oracle’s node correspondences. Pattern Recognition Letters, 2015. 56:22-29. URL https://doi.org/10.1016/j.patrec.2015.01.009.
[11] Conte D, Ramel JY, Sidre N, Luqman MM, Gaüzère B, Gibert J, Brun L, Vento M. A Comparison of Explicit and Implicit Graph Embedding Methods for Pattern Recognition. In: Kropatsch WG, Artner NM, Haxhimusa Y, Jiang X (eds.), Graph-Based Representations in Pattern Recognition: 9th IAPR-TC-15 International Workshop, GbRPR 2013, Vienna, Austria, May 15-17, 2013. Proceedings, pp. 81-90. Springer Berlin Heidelberg, Berlin, Heidelberg, 2013. doi:10.1007/978-3-642-38221-5_9.
[12] Fischer A, Suen CY, Frinken V, Riesen K, Bunke H. A Fast Matching Algorithm for Graph-Based Handwriting Recognition, pp. 194-203. Springer Berlin Heidelberg, Berlin, Heidelberg, 2013. doi:10.1007/978-3-642-38221-5_21.
[13] Serratosa F. Speeding up Fast Bipartite Graph Matching Through a New Cost Matrix. International Journal of Pattern Recognition and Artificial Intelligence, 2015. 29(2):1550010-1-1550010-17. URL https://doi.org/10.1142/S021800141550010X.
[14] Riesen K, Bunke H. Reducing the dimensionality of dissimilarity space embedding graph kernels. Engineering Applications of Artificial Intelligence, 2009. 22(1):48-56. URL https://doi.org/10.1016/j.engappai.2008.04.006.
[15] Gaüzère B, Hasegawa M, Brun L, Tabbone S. Implicit and Explicit Graph Embedding: Comparison of Both Approaches on Chemoinformatics Applications. In: Gimelfarb G, Hancock E, Imiya A, Kuijper A, Kudo M, Omachi S, Windeatt T, Yamada K (eds.), Structural, Syntactic, and Statistical Pattern Recognition: Joint IAPR International Workshop, SSPR&SPR 2012, Hiroshima, Japan, November 7-9, 2012. Proceedings, pp. 510-518. Springer Berlin Heidelberg, Berlin, Heidelberg, 2012. doi:10.1007/978-3-642-34166-3_56.
[16] Bunke H, Riesen K. Recent advances in graph-based pattern recognition with applications in document analysis. Pattern Recognition, 2011. 44(5):1057-1067. URL https://doi.org/10.1016/j.patcog.2010.11.015.
[17] Zaslavskiy M, Bach F, Vert JP. Global alignment of proteinprotein interaction networks by graph matching methods. Bioinformatics, 2009. 25(12):i259-1267. URL https://doi.org/10.1093/bioinformatics/btp196.
[18] Cosmo L, Rodola E, Albarelli A, Mmoli F, Cremers D. Consistent partial matching of shape collections via sparse modeling. In: Computer Graphics Forum. Wiley Online Library. 2017.36(1):209-221. doi:10.1111/cgf.12796. doi:10.1111/cgf.12796.
[19] Bergamasco F, Albarelli A, Torsello A. A graph-based technique for semi-supervised segmentation of 3D surfaces. Pattern Recognition Letters, 2012. 33(15):2057-2064. URL https://doi.org/10.1016/j.patrec.2012.03.015.
[20] Sanfeliu A, Fu KS. A distance measure between attributed relational graphs for pattern recognition. IEEE Transactions on Systems, Man, and Cybernetics, 1983. SMC-13(3):353-362. doi:10.1109/TSMC.1983.6313167.
[21] Bunke H, Allermann G. Inexact graph matching for structural pattern recognition. Pattern Recogn. Lett., 1983. 1(4):245-253. URL https://doi.org/10.1016/0167-8655(83)90033-8.
[22] Solé A, Serratosa F, Sanfeliu A. On the graph edit distance cost: properties and applications. International Journal of Pattern Recognition and Artificial Intelligence, 2012. 26(05):24. URL https: //doi.org/10.1142/S021800141260004X.
[23] Gao X, Xiao B, Tao D, Li X. A survey of graph edit distance. Pattern Analysis and Applications, 2010. 13(1):113-129. doi:10.1007/s10044-008-0141-y.
[24] Morgan HL. Spelling correction in systems programs. Commun. ACM, 1970. 13(2):90-94. doi:10.1145/362007.362033.
[25] Wagner RA, Fischer MJ. The String-to-String Correction Problem. J. ACM, 1974. 21(1):168-173. doi:10.1145/321796.321811.
[26] Tai KC. The Tree-to-Tree Correction Problem. J. ACM, 1979. 26(3):422-433. doi:10.1145/322139.322143.
[27] Riesen K, Bunke H. Approximate graph edit distance computation by means of bipartite graph matching. Image and Vision Computing, 2009. 27(7):950-959. URL https://doi.org/10.1016/j.imavis.2008.04.004.
[28] Neuhaus M, Bunke H. An Error-Tolerant Approximate Matching Algorithm for Attributed Planar Graphs and Its Application to Fingerprint Classification. In: Fred A, Caelli TM, Duin RPW, Campilho AC, de Ridder D (eds.), Structural, Syntactic, and Statistical Pattern Recognition: Joint IAPR International Workshops, SSPR 2004 and SPR 2004, Lisbon, Portugal, August 18-20, 2004, pp. 180-189. Springer Berlin Heidelberg, Berlin, Heidelberg, 2004. doi:10.1007/978-3-540-27868-9_18.
[29] Robles-Kelly A, Hancock ER. Graph edit distance from spectral seriation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005. 27(3):365-378. doi:10.1109/TPAMI.2005.56.
[30] Justice D, Hero A. A binary linear programming formulation of the graph edit distance. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006. 28(8):1200-1214. doi:10.1109/TPAMI.2006.152.
[31] Marn RM, Aguirre NF, Daza EE. Graph Theoretical Similarity Approach To Compare Molecular Electrostatic Potentials. Journal of Chemical Information and Modeling, 2008. 48(1):109-118. doi:10.1021/ci7001878.
[32] Ambauen R, Fischer S, Bunke H. Graph Edit Distance with Node Splitting and Merging, and Its Application to Diatom Identification, pp. 95-106. LNCS, vol 2726. Springer Berlin Heidelberg, Berlin, Heidelberg, 2003. doi:10.1007/3-540-45028-9_9.
[33] Zheng W, Zou L, Lian X, Wang D, Zhao D. Graph similarity search with edit distance constraint in large graph databases. In: Proceedings of the 22nd ACM international conference on Conference on information & knowledge management, CIKM ’13. ACM, New York, NY, USA. ISBN 978-1-4503-2263-8, 2013 pp. 1595-1600.
[34] Ibragimov R, Malek M, Guo J, Baumbach J. GEDEVO: An Evolutionary Graph Edit Distance Algorithm for Biological Network Alignment. In: Beißbarth T, Kollmar M, Leha A, Morgenstern B, Schultz AK, Waack S, Wingender E (eds.), German Conference on Bioinformatics 2013, volume 34 of OpenAccess Series in Informatics (OASIcs). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2013 pp. 68-79. doi:10.4230/OASIcs.GCB.2013.68.
[35] Fischer A, Suen CY, Frinken V, Riesen K, Bunke H. Approximation of graph edit distance based on Hausdorff matching. Pattern Recognition, 2015. 48(2):331-343. URL https://doi.org/10.1016/j.patcog.2014.07.015.
[36] Henry CJ. Perceptually Indiscernibility, Rough Sets, Descriptively Near Sets, and Image Analysis. Transactions on Rough Sets, 2012. LNCS 7255:41-121. doi:10.1007/978-3-642-31903-7_3.
[37] Peters JF, Naimpally SA. Applications of near sets. Notices of the American Mathematical Society, 2012. 59(4):536-542. doi:10.1090/noti817.
[38] Peters JF. Near sets. Wikipedia, The Free Encyclopaedia, 2015. Edited by C. J. Henry.
[39] Poincaré H. Science and Hypothesis. The Mead Project, Brock University, 1905. L. G.Ward’s translation.
[40] Benjamin LT Jr. A Brief History of Modern Psychology. Blackwell Publishing, Malden, MA, 2007. ISBN-10:140513206X, 13:978-1405132060.
[41] Hergenhahn BR. An Introduction to the History of Psychology. Wadsworth Publishing, Belmont, CA, 2009.
[42] Fechner GT. Elements of Psychophysics, vol. I. Hold, Rinehart & Winston, London, UK, 1966. H. E. Adler’s trans. of Elemente der Psychophysik, 1860. ASIN-B01JNPJT68.
[43] Poincaré H. Sur la nature of raisonnement mathématique. Revue de métaphysique et de morale, 1894. 2:371-384. URL https://www.jstor.org/stable/40891545.
[44] Poincaré H. L’espace et la géomètrie. Revue de métaphysique et de morale, 1895. 3:631-646.
[45] Poincaré H. Sur certaines surfaces algèbriques; troisième complément a l’analysis situs. Bulletin de la Société de France, 1902. 30:49-70.
[46] Riesz F. Stetigkeitsbegriff und abstrakte mengenlehre. Atti del IV Congresso Internazionale dei Matematici, 1908. II:18-24.
[47] Naimpally SA, Warrack BD. Proximity Spaces. In: Cambridge Tract in Mathematics No. 59. Cambridge University Press, Cambridge, UK, 1970.
[48] Naimpally SA. Near and Far. A centennial Tribute to Frigyes Riesz. Siberian Electronic Mathematical Reports, 2009. 6:A.1-A.10. URL http://www.ams.org/mathscinet-getitem?mr=2586674.
[49] Zeeman EC. The topology of the brain and the visual perception. In: Fort KM (ed.), Topoloy of 3-manifolds and selected topices, pp. 240-256. University of Georgia Institute Conference Proceedings, Prentice Hall, Georgia, 1962.
[50] Sossinsky AB. Tolerance space theory and some applications. Acta Applicandae Mathematicae: An International Survey Journal on Applying Mathematics and Mathematical Applications, 1986. 5(2):137-167. doi:10.1007/BF00046585.
[51] Pawlak Z, Peters JF. Jak blisko (how near). Systemy Wspomagania Decyzji, 2002. I:57-109.
[52] Peters JF. Near Sets: An Introduction. Mathematics in Computer Science, 2013. 7(1):3-9. doi:10.1007/s11786-013-0149-6.
[53] Naimpally SA, Peters JF. Topology with Applications. Topological Spaces via Near and Far. World Scientific, Singapore, 2013. URL https://doi.org/10.1142/8501.
[54] Mozzochi CJ, Naimpally SA. Uniformity and Proximity. In: Allahabad Mathematical Society Lecture Note Series, volume 2. The Allahabad Math. Soc., 2009 p. 153 pp.
[55] Hocking JG, Naimpally SA. Nearness-A Better Approach to Continuity and Limits. In: Allahabad Mathematical Society Lecture Note Series, volume 3. The Allahabad Math. Soc., 2009 p. 153 pp.
[56] Peters JF. Near Sets. General Theory About Nearness of Objects. Applied Mathematical Sciences, 2007. 1(53):2609-2629.
[57] Peters JF. Near sets. Special theory about nearness of objects. Fundamenta Informaticae, 2007. 75(1-4):407-433.
[58] Peters JF. Tolerance near sets and image correspondence. International Journal of Bio-Inspired Computation, 2009. 1(4):239-245. doi:10.1504/IJBIC.2009.024722.
[59] Peters JF. Corrigenda and addenda: Tolerance near sets and image correspondence. International Journal of Bio-Inspired Computation, 2010. 2(5):310-318. URL https://doi.org/10.1504/IJBIC.2010.036157.
[60] Zeeman EC. The topology of the brain and the visual perception. In: Fort KM (ed.), Topoloy of 3-manifolds and selected topices, pp. 240-256. Prentice Hall, New Jersey, 1965.
[61] Peters JF, Wasilewski P. Tolerance spaces: Origins, theoretical aspects and applications. Information Sciences, 2012. 195(0):211-225. doi:10.1016/j.ins.2012.01.023.
[62] Henry C, Peters JF. Perceptual Image Analysis. International Journal of Bio-Inspired Computation, 2010. 2(3-4):271-281. doi:10.1504/IJBIC.2010.033095.
[63] Henry C, Peters JF. Perception-Based Image Classification. International Journal of Intelligent Computing and Cybernetics, 2010. 3(3):410-430. Emerald Literati Network 2011 Award for Excellence. URL https://doi.org/10.1108/17563781011066701.
[64] Henry C, Peters JF. Arthritic hand-finger movement similarity measuresments: Tolerance near set approach. Computational and Mathematical Methods in Medicine, 2011. 2011. Article ID 569898, 14 pp. URL http://dx.doi.org/10.1155/2011/569898.
[65] Henry CJ, Ramanna S. Maximal Clique Enumeration in Finding Near Neighbourhoods, pp. 103-124. LNCS, vol 7736. Springer Berlin Heidelberg, Berlin, Heidelberg, 2013. doi:10.1007/978-3-642-36505-8_7.
[66] Henry CJ, Ramanna S. Signature-based Perceptual Nearness. Application of Near Sets to Image Retrieval. Mathematics in Computer Science, 2013. 7(1):71-85. doi:10.1007/s11786-013-0145-x.
[67] Fernndez ML, Valiente G. A graph distance metric combining maximum common subgraph and minimum common supergraph. Pattern Recognition Letters, 2001. 22(6-7):753-758. URL https://doi.org/10.1016/S0167-8655(01)00017-4.
[68] Bunke H, Shearer K. A graph distance metric based on the maximal common subgraph. Pattern Recognition Letters, 1998. 19(34):255-259. URL https://doi.org/10.1016/S0167-8655(97)00179-7.
[69] Sorlin S, Solnon C. Reactive Tabu Search for Measuring Graph Similarity, pp. 172-182. LNCS, vol 3434. Springer Berlin Heidelberg, Berlin, Heidelberg, 2005. doi:10.1007/978-3-540-31988-7_16.
[70] Champin PA, Solnon C. Measuring the similarity of labeled graphs. LNCS, vol 2689. In: International Conference on Case-Based Reasoning. Springer, 2003 pp. 80-95. doi:10.1007/3-540-45006-8_9.
[71] Shervashidze N, Vishwanathan S, Petri T, Mehlhorn K, Borgwardt K. Efficient graphlet kernels for large graph comparison. In: Artificial Intelligence and Statistics. 2009 pp. 488-495. URL http://proceedings.mlr.press/v5/shervashidze09a.html.
[72] Dehmer M, Emmert-Streib F, Kilian J. A similarity measure for graphs with low computational complexity. Applied Mathematics and Computation, 2006. 182(1):447-459. URL https://doi.org/10.1016/j.amc.2006.04.006.
[73] The mutual information between graphs. Pattern Recognition Letters, 2017. 87:12-19. Advances in Graph-based Pattern Recognition. URL https://doi.org/10.1016/j.patrec.2016.07.012.
[74] Bopche GS, Mehtre BM. Graph similarity metrics for assessing temporal changes in attack surface of dynamic networks. Computers & Security, 2017. 64:16-43. URL https://doi.org/10.1016/j.cose.2016.09.010.
[75] Fujibuchi W, Ogata H, Matsuda H, Kanehisa M. Automatic detection of conserved gene clusters in multiple genomes by graph comparison and P-quasi grouping. Nucleic Acids Research, 2000. 28(20):4029. PMCID:PMC110780.
[76] Serratosa F. Fast computation of Bipartite graph matching. Pattern Recognition Letters, 2014. 45:244-250. URL https://doi.org/10.1016/j.patrec.2014.04.015.
[77] Bunke H. Error correcting graph matching: on the influence of the underlying cost function. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1999. 21(9):917-922. doi:10.1109/34.790431.
[78] Hart PE, Nilsson NJ, Raphael B. A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, 1968. 4(2):100-107. doi:10.1109/TSSC.1968.300136.
[79] Peters JF, Wasilewski P. Foundations of Near Sets. Info. Sci., 2009. 179(18):3091-3109. URL https://doi.org/10.1016/j.ins.2009.04.018.
[80] Pavel M. Fundamentals of Pattern Recognition. Marcel Dekker, Inc., NY, 1993. ISBN-10:0824788834, 13:978-0824788834.
[81] Bron C, Kerbosch J. Algorithm 457: finding all cliques of an undirected graph. Communications of the ACM, 1973. 16(9):575-577. doi:10.1145/362342.362367.
[82] Tomita E, Tanaka A, Takahashi H. The worst-case time complexity for generating all maximal cliques and computational experiments. Theoretical Computer Science, 2006. 363(1):28-42. URL https://doi.org/10.1016/j.tcs.2006.06.015.
[83] Zhou M, Asari VK. A Fast Video Stabilization System Based on Speeded-up Robust Features, pp.428-435. LNCS, vol 6939. Springer Berlin Heidelberg, Berlin, Heidelberg, 2011. doi:10.1007/978-3-642-24031-7_43.
[84] Overmars M, De Berg M, van Kreveld M, Schwarzkopf O. Computational Geometry: Algorithms and Applications. Springer-Verlag, Berlin, Heidelberg, 2008. ISBN-10:3540779736, 13:978-3540779735.
[85] Dai J, Zhou J. Multifeature-Based High-Resolution Palmprint Recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011. 33(5):945-957. doi:10.1109/TPAMI.2010.164.
[86] Yates-Baeza R, Ribeiro-Neto B. Modern Information Retrieval. ACM Pres/Pearson Addison Wesley, New York, 1999. ISBN-020139829X.
[87] Alusaifeer T, Ramanna S, Henry CJ, Peters J. GPU Implementation of MCE approach to Finding Near Neighbourhoods. In: Lingras P., Wolski M., Cornelis C., Mitra S., Wasilewski P. (eds) Rough Sets and Knowledge Technology. RSKT 2013. LNCS, vol 8171, Springer, Berlin, Heidelberg 2013 pp. 251-262.
[88] Basak SC, Magnuson VR, Niemi GJ, Regal RR. Determining structural similarity of chemicals using graph-theoretic indices. Discrete Applied Mathematics, 1988. 19(1):17-44. URL https://doi.org/10.1016/0166-218X(88)90004-2.
[89] Bunke H. Graph matching: Theoretical foundations, algorithms, and applications. In: Proceedings of Vision Interface 2000. 2000 pp. 82-88.
[90] Cantoni V, Cinque L, Guerra C, Levialdi S, Lombardi L. 2-D OBJECT RECOGNITION BY MULTISCALE TREE MATCHING. Pattern Recognition, 1998. 31(10):1443-1454. URL https://doi.org/10.1016/S0031-3203(97)00085-X.
[91] Cook DJ, Holder LB. Substructure discovery using minimum description length and background knowledge. J. Artif. Int. Res., 1994. 1(1):231-255.
[92] Ehrig H, Habel A, Kreowski HJ. Introduction to graph grammars with applications to semantic networks. Computers & Mathematics with Applications, 1992. 23(6):557-572. URL https://doi.org/10.1016/0898-1221(92)90124-Z.
[93] Fernndez ML, Valiente G. A graph distance metric combining maximum common subgraph and minimum common supergraph. Pattern Recognition Letters, 2001. 22(67):753-758. URL https://doi.org/10.1016/S0167-8655(01)00017-4.
[94] Henry CJ. A Parallel GPU Solution to the Maximal Clique Enumeration Problem for CBIR. In: GPU Technology Conference (GTC 2014). 2014.
[95] Irniger C, Bunke H. Theoretical Analysis and Experimental Comparison of Graph Matching Algorithms for Database Filtering. In: Hancock E, Vento M (eds.), Graph Based Representations in Pattern Recognition: 4th IAPR International Workshop, GbRPR 2003 York, UK, June 30 July 2, 2003 Proceedings, LNCS vol 2726, Springer Berlin Heidelberg, 2003 pp. 118-129.
[96] Jonker R, Volgenant A. A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing, 1987. 38(4):325-340. doi:10.1007/BF02278710.
[97] Kuhn HW. The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 1955. 2(1-2):83-97. URL https://doi.org/10.1002/nav.3800020109.
[98] Levi G. A note on the derivation of maximal common subgraphs of two directed or undirected graphs. CALCOLO, 1973. 9(4):341-352. doi:10.1007/BF02575586.
[99] Li J, Wang JZ. Automatic Linguistic Indexing of Pictures by a Statistical Modeling Approach. IEEE Trans. Pattern Anal. Mach. Intell., 2003. 25(9):1075-1088. doi:10.1109/TPAMI.2003.1227984.
[100] Maher PE. A similarity measure for conceptual graphs. International Journal of Intelligent Systems, 1993. 8(8):819-837. URL https://doi.org/10.1002/int.4550080802.
[101] McGregor JJ. Backtrack search algorithms and the maximal common subgraph problem. Software: Practice and Experience, 1982. 12(1):23-34. URL https://doi.org/10.1002/spe.4380120103.
[102] Messmer BT, Bunke H. Automatic learning and recognition of graphical symbols in engineering drawings. In: Kasturi R, Tombre K (eds.), Graphics Recognition Methods and Applications: First International Workshop University Park, PA, USA, August 1011, 1995. Springer Berlin Heidelberg, 1996 pp.123-134. doi:10.1007/3-540-61226-2_11.
[103] Munkres J. Algorithms for the Assignment and Transportation Problems. Journal of the Society for Industrial and Applied Mathematics, 1957. 5(1):32-38. URL https://doi.org/10.1137/0105003.
[104] Raveaux R, Burie JC, Ogier JM. A graph matching method and a graph matching distance based on subgraph assignments. Pattern Recognition Letters, 2010. 31(5):394-406. URL https://doi.org/10.1016/j.patrec.2009.10.011.
[105] Robles-Kelly A, Hancock ER. Graph Matching Using Spectral Seriation and String Edit Distance. In: Hancock E, Vento M(eds.), Graph Based Representations in Pattern Recognition: 4th IAPR International Workshop, GbRPR 2003 York, UK, June 30 July 2, 2003, Springer Berlin Heidelberg, 2003 pp. 154-165. doi:10.1007/3-540-45028-9_14.
[106] Rocha J, Pavlidis T. A shape analysis model with applications to a character recognition system. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1994. 16(4):393-404. doi:10.1109/34.277592.
[107] Sanfeliu A, Alquézar R, Andrade J, Climent J, Serratosa F, Vergés J. Graph-based representations and techniques for image processing and image analysis. Pattern Recognition, 2002. 35(3):639-650. URL https://doi.org/10.1016/S0031-3203(01)00066-8.
[108] Schenker A, Bunke H, Last M, Kandel A. Polynomial Time Complexity Graph Distance Computation for Web Content Mining. In: Basu M, Ho TK (eds.), Data Complexity in Pattern Recognition, Springer London, London, 2006 pp. 197-215. doi:10.1007/978-1-84628-172-3_10.
[109] Schenker A, Last M, Bunke H, Kandel A. Classification of Web documents using a graph model. In: Document Analysis and Recognition, 2003. Proceedings. Seventh International Conference on. 2003 pp.240-244 vol.1. doi:10.1109/ICDAR.2003.1227666.
[110] Schenker A, Last M, Bunke H, Kandel A. CLASSIFICATION OF WEB DOCUMENTS USING GRAPH MATCHING. International Journal of Pattern Recognition and Artificial Intelligence, 2004. 18(03):475-496. URL https://doi.org/10.1142/S0218001404003241.
[111] Serratosa F, Cortés X. Graph Edit Distance: Moving from global to local structure to solve the graphmatching problem. Pattern Recognition Letters, 2015. 65:204-210. URL https://doi.org/10.1016/j.patrec.2015.08.003.
[112] Shearer K, Bunke H, Venkatesh S. Video indexing and similarity retrieval by largest common subgraph detection using decision trees. Pattern Recognition, 2001. 34(5):1075-1091. URL https://doi.org/10.1016/S0031-3203(00)00048-0.
[113] Si Wei L, Ren Y, Suen CY. Hierarchical attributed graph representation and recognition of handwritten chinese characters. Pattern Recognition, 1991. 24(7):617-632. URL https://doi.org/10.1016/0031-3203(91)90029-5.
[114] Wallis WD, Shoubridge P, Kraetz M, Ray D. Graph distances using graph union. Pattern Recognition Letters, 2001. 22(67):701-704. URL https://doi.org/10.1016/S0167-8655(01)00022-8.
[115] Wilson R, Beineke L. Applications of graph theory. Academic Press, 1979.
[116] Wong AKC, You M. Entropy and Distance of Random Graphs with Application to Structural Pattern Recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1985. PAMI-7(5):599-609. doi:10.1109/TPAMI.1985.4767707.
[117] Henry CJ. Near sets: theory and applications. Ph.D. thesis, University of Manitoba, 2010. URL http://hdl.handle.net/1993/4267.

Typ dokumentu

Bibliografia

Identyfikator YADDA

bwmeta1.element.baztech-8ff48b50-43bc-48a5-a382-a4be75db4aed