nach oben

Artificial Intelligence Review

Erschienen in:

27.02.2020

An overview of distance and similarity functions for structured data

verfasst von: Santiago Ontañón

Erschienen in: Artificial Intelligence Review | Ausgabe 7/2020

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The notions of distance and similarity play a key role in many machine learning approaches, and artificial intelligence in general, since they can serve as an organizing principle by which individuals classify objects, form concepts and make generalizations. While distance functions for propositional representations have been thoroughly studied, work on distance functions for structured representations, such as graphs, frames or logical clauses, has been carried out in different communities and is much less understood. Specifically, a significant amount of work that requires the use of a distance or similarity function for structured representations of data usually employs ad-hoc functions for specific applications. Therefore, the goal of this paper is to provide an overview of this work to identify connections between the work carried out in different areas and point out directions for future work.

Vorheriger Artikel Deep hashing for multi-label image retrieval: a survey

Nächster Artikel A deep granular network with adaptive unequal-length granulation strategy for long-term time series forecasting and its industrial applications

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Notice that in the description logics notation, subsumption is written in the reverse order since it is seen as “set inclusion” of their interpretations. Here, $x_1 \sqsubseteq x_2$ means that $x_1$ is more general than $x_2$, while in description logics it has the opposite meaning.

Interestingly, the Weisfeiler–Lehman test is related to the expressive power of Graph Neural Networks (discussed in Sect. 3.5), as it has been shown that a some classes of GNNs are at least as powerful as the Weisfeiler–Lehman in detecting graph isomorphism (Xu et al. 2018).

Aamodt A, Plaza E (1994) Case-based reasoning: foundational issues, methodological variations, and system approaches. Artif Intell Commun 7(1):39–59

Abu-Khzam FN, Samatova NF, Rizk MA, Langston MA (2007) The maximum common subgraph problem: faster solutions via vertex cover. In: IEEE/ACS international conference on computer systems and applications, 2007. AICCSA’07. IEEE, pp 367–373

Agrawal R, Faloutsos C, Swami A (1993) Efficient similarity search in sequence databases. In: International conference on foundations of data organization and algorithms. Springer, pp 69–84

Aha DW, Kibler D, Albert MK (1991) Instance-based learning algorithms. Mach Learn 6(1):37–66

Almohamad H, Duffuaa SO (1993) A linear programming approach for the weighted graph matching problem. IEEE Trans Pattern Anal Mach Intell 15(5):522–525

Armengol E, Plaza E (2001) Similarity assessment for relational cbr. In: International conference on case-based reasoning. Springer, pp 44–58

Armengol E, Plaza E (2002) Similarity of structured cases in CBR. In: Proceedings from the CCIA held in Castellon, Spain

Assali AA, Lenne D, Debray B (2009) Case retrieval in ontology-based cbr systems. In: Annual conference on artificial intelligence. Springer, pp 564–571

Baader F, Calvanese D, McGuinness DL, Nardi D, Patel-Schneider PF (eds) (2003) The description logic handbook: theory, implementation, and applications. Cambridge University Press, CambridgeMATH

Baader F, Horrocks I, Sattler U (2005) Description logics as ontology languages for the semantic web. In: Hutter D, Stephan W (eds) Mechanizing mathematical reasoning. Springer, pp 228–248

Babai L (2018) Groups, graphs, algorithms: the graph isomorphism problem. In: Proceedings of international congress of mathematicians 2018

Badea L, Nienhuys-Cheng SH (1999) A refinement operator for description logics. In: Cussens J, Frisch A (eds) Inductive logic programming, no. 1866 in Lecture notes in computer science. Springer, pp 40–59

Battaglia PW, Hamrick JB, Bapst V, Sanchez-Gonzalez A, Zambaldi V, Malinowski M, Tacchetti A, Raposo D, Santoro A, Faulkner R et al (2018) Relational inductive biases, deep learning, and graph networks. arXiv:180601261

Bellet A, Habrard A, Sebban M (2012) Good edit similarity learning by loss minimization. Mach Learn 89(1–2):5–35MathSciNetMATH

Bellet A, Habrard A, Sebban M (2013) A survey on metric learning for feature vectors and structured data. arXiv:13066709

Bergmann R, Stahl A (1998) Similarity measures for object-oriented case representations. In: Advances in case-based reasoning, pp 25–36

Bergmann R, Gil Y (2014) Similarity assessment and efficient retrieval of semantic workflows. Inf Syst 40:115–127

Bergmann R, Kolodner J, Plaza E (2005) Representation in case-based reasoning. Knowl Eng Rev 20(3):209–213

Bille P (2005) A survey on tree edit distance and related problems. Theor Comput Sci 337(1):217–239MathSciNetMATH

Bisson G (1990) Kbg: a knowledge based generalizer. In: Porter B, Mooney R (eds) Machine learning proceedings 1990. Elsevier, Amsterdam, pp 9–15

Bisson G (1992) Learing in FOL with a similarity measure. In: Proceedings of AAAI, vol 1992, pp 82–87

Borgida A, Walsh TJ, Hirsh H et al (2005) Towards measuring similarity in description logics. Descr Log 147

Bournaud I, Courtine M, Jean-Daniel Z (2002) Propositionalization for clustering symbolic relational descriptions. In: International conference on inductive logic programming. Springer, pp 1–16

Bunke H (1997) On a relation between graph edit distance and maximum common subgraph. Pattern Recogn Lett 18(8):689–694

Bunke H (1999) Error correcting graph matching: on the influence of the underlying cost function. IEEE Trans Pattern Anal Mach Intell 21(9):917–922

Bunke H (2000) Graph matching: theoretical foundations, algorithms, and applications. Proc Vis Interface 2000:82–88

Bunke H, Shearer K (1998) A graph distance metric based on the maximal common subgraph. Pattern Recogn Lett 19(3):255–259MATH

Carpenter B (1992) The logic of typed feature structures. Cambridge University Press, New YorkMATH

Champin PA, Solnon C (2003) Measuring the similarity of labeled graphs. In: International conference on case-based reasoning, ICCBR. Springer

Chen PPS (1988) The entity-relationship model—toward a unified view of data. Readings in artificial intelligence and databases. Elsevier, Amsterdam, pp 98–111

Church A (1940) A formulation of the simple theory of types. J Symb Log 5(2):56–68MathSciNetMATH

Cilibrasi R, Vitányi PM (2005) Clustering by compression. IEEE Trans Inf Theory 51(4):1523–1545MathSciNetMATH

Collins M, Duffy N (2002) Convolution kernels for natural language. In: Becker S, Thrun S, Obermayer K (eds) Advances in neural information processing systems. Vancouver, Canada, pp 625–632

Conte D, Foggia P, Sansone C, Vento M (2004) Thirty years of graph matching in pattern recognition. Int J Pattern Recogn Artif Intell 18(03):265–298

Cover T, Hart P (1967) Nearest neighbor pattern classification. IEEE Trans Inf Theory 13(1):21–27MATH

d’Amato C, Fanizzi N, Esposito F (2006) A dissimilarity measure for alc concept descriptions. In: Proceedings of the 2006 ACM symposium on applied computing. ACM, pp 1695–1699

d’Amato C, Staab S, Fanizzi N (2008) On the influence of description logics ontologies on conceptual similarity. In: Proceedings of the 16th international conference on knowledge engineering. Lecture notes in computer science, vol 5268. Springer, pp 48–63

Datar M, Immorlica N, Indyk P, Mirrokni VS (2004) Locality-sensitive hashing scheme based on p-stable distributions. In: Proceedings of the twentieth annual symposium on computational geometry. ACM, pp 253–262

de Vries GKD, de Rooij S (2015) Substructure counting graph kernels for machine learning from rdf data. Web Semant Sci Serv Agents World Wide Web 35:71–84

Dempster AP, Laird NM, Rubin DB (1977) Maximum likelihood from incomplete data via the EM algorithm. Journal R Stat Soc Ser B (Methodol) 39:1–38MathSciNetMATH

Dobrushin RL (1970) Prescribing a system of random variables by conditional distributions. Theory Probab Appl 15(3):458–486MathSciNetMATH

Doyle PG, Snell JL (1984) Random walks and electric networks, vol 22. American Mathematical Society, ProvidenceMATH

Emde W, Wettschereck D (1996) Relational instance based learning. In: Saitta L (ed) Machine learning—proceedings 13th international conference on machine learning. Morgan Kaufmann Publishers, pp 122–130

Emele MC, Zajac R (1990) Typed unification grammars. In: Proceedings of the 13th conference on computational linguistics, vol 3. Association for Computational Linguistics, pp 293–298

Emmert-Streib F, Dehmer M, Shi Y (2016) Fifty years of graph matching, network alignment and network comparison. Inf Sci 346:180–197MathSciNetMATH

Ester M, Kriegel HP, Sander J, Xu X et al (1996) A density-based algorithm for discovering clusters in large spatial databases with noise. Kdd 96:226–231

Falkenhainer B, Forbus KD, Gentner D (1989) The structure-mapping engine: algorithm and examples. Artif intell 41(1):1–63MATH

Fanizzi N, d’Amato C (2006) A declarative kernel for $\cal{ALC}$ concept descriptions. In: International symposium on methodologies for intelligent systems. Springer, pp 322–331

Fanizzi N, d’Amato C, Esposito F (2008) Learning with kernels in description logics. In: Zelezny F, Lavrac N (eds) Inductive logic programming. Springer, pp 210–225

Fernández ML, Valiente G (2001) A graph distance metric combining maximum common subgraph and minimum common supergraph. Pattern Recognition Letters 22(6):753–758MATH

French RM (2002) The computational modeling of analogy-making. Trends Cogn Sci 6(5):200–205

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

Gärtner T (2003) A survey of kernels for structured data. ACM SIGKDD Explor Newsl 5(1):49–58

Gärtner T, Lloyd JW, Flach PA (2002) Kernels for structured data. Springer, BerlinMATH

Gärtner T, Flach P, Wrobel S (2003) On graph kernels: Hardness results and efficient alternatives. In: Schölkopf B, Warmuth MK (eds) Learning theory and kernel machines. Springer, Berlin, pp 129–143MATH

Gärtner T, Lloyd JW, Flach PA (2004) Kernels and distances for structured data. Mach Learn 57(3):205–232MATH

Gentner D (1983) Structure-mapping: a theoretical framework for analogy. Cogn Sci 7(2):155–170

Getoor L, Taskar B (2007) Introduction to statistical relational learning. MIT Press, CambridgeMATH

Göker MH, Roth-Berghofer T (1999) The development and utilization of the case-based help-desk support system homer. Eng Appl Artif Intell 12(6):665–680

Goldstone RL, Medin DL, Gentner D (1991) Relational similarity and the nonindependence of features in similarity judgments. Cogn Psychol 23(2):222–262

Gollery M (2005) Bioinformatics: sequence and genome analysis. Clin Chem 51(11):2219–2219

Golub GH, Van Loan CF (2012) Matrix computations, vol 3. JHU Press, BaltimoreMATH

González-Calero PA, Díaz-Agudo B, Gómez-Albarrán M et al (1999) Applying dls for retrieval in case-based reasoning. In: In Proceedings of the 1999 description logics workshop (Dl’99). Linkopings Universitet, Citeseer

Haussler D (1999) Convolution kernels on discrete structures. Technical report, Department of Computer Science, University of California at Santa Cruz

Hearst MA, Dumais ST, Osuna E, Platt J, Scholkopf B (1998) Support vector machines. IEEE Intell Syst Their Appl 13(4):18–28

Heckerman D, Meek C, Koller D (2007) Probabilistic entity-relationship models, prms, and plate models. In: Getoor L, Taskar B (eds) Introduction to statistical relational learning, MIT Press, pp 201–238

Holyoak KJ, Koh K (1987) Surface and structural similarity in analogical transfer. Mem Cogn 15(4):332–340

Horváth T, Wrobel S, Bohnebeck U (2001) Relational instance-based learning with lists and terms. Mach Learn 43(1–2):53–80MATH

Horváth T, Gärtner T, Wrobel S (2004) Cyclic pattern kernels for predictive graph mining. In: Proceedings of the tenth ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 158–167

Hu B, Kalfoglou Y, Alani H, Dupplaw D, Lewis P, Shadbolt N (2006) Semantic metrics. In: International conference on knowledge engineering and knowledge management. Springer, pp 166–181

Hutchinson A (1997) Metrics on terms and clauses. In: ECML ’97: proceedings of the 9th European conference on machine learning. Lecture notes in computer science, vol 1224. Springer, pp 138–145

Itakura F (1975) Minimum prediction residual principle applied to speech recognition. IEEE Trans Acoust Speech Signal Process 23(1):67–72

Jaakkola T, Haussler D (1999) Exploiting generative models in discriminative classifiers. In: Solla SA, Leen TK, Müller K-R (eds) Advances in neural information processing systems. MIT Press, Denver, Colarado, pp 487–493

Janowicz K (2006) Sim-dl: towards a semantic similarity measurement theory for the description logic $\cal{ALCNR}$ in geographic information retrieval. In: OTM confederated international conferences “on the move to meaningful internet systems. Springer, pp 1681–1692

Jeh G, Widom J (2002) Simrank: a measure of structural-context similarity. In: Proceedings of the eighth ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 538–543

Jiang JJ, Conrath DW (1997) Semantic similarity based on corpus statistics and lexical taxonomy. arXiv:cmp-lg/9709008

Kalfoglou Y, Schorlemmer M (2003) Ontology mapping: the state of the art. Knowl Eng Rev 18(1):1–31MATH

Kashima H, Koyanagi T (2002) Kernels for semi-structured data. ICML 2:291–298

Kashima H, Tsuda K, Inokuchi A (2003) Marginalized kernels between labeled graphs. In: Proceedings of the twentieth international conference (ICML 2003). AAAI Press, pp 321–328

Katz L (1953) A new status index derived from sociometric analysis. Psychometrika 18(1):39–43MATH

Kaufman L, Rousseeuw P (1987) Clustering by means of medoids. North-Holland, Amsterdam

Keogh E, Kasetty S (2003) On the need for time series data mining benchmarks: a survey and empirical demonstration. Data Min Knowl Discov 7(4):349–371MathSciNet

Klein PN (1998) Computing the edit-distance between unrooted ordered trees. In: European symposium on algorithms. Springer, pp 91–102

Kok S, Domingos P (2007) Statistical predicate invention. In: Proceedings of the 24th international conference on machine learning. ACM, pp 433–440

Kolmogorov AN (1965) Three approaches to the quantitative definition of information. Probl Inf Transm 1(1):1–7MathSciNet

Kramer S, Lavrač N, Flach P (2001) Propositionalization approaches to relational data mining. In: Dzeroski S, Lavrac N (eds) Relational data mining. Springer, pp 262–291

Krieger HU, Schäfer U (1995) Efficient parameterizable type expansion for typed feature formalisms

Krogel MA, Rawles S, Železnỳ F, Flach PA, Lavrač N, Wrobel S (2003) Comparative evaluation of approaches to propositionalization. In: International conference on inductive logic programming. Springer, pp 197–214

Kulis B, et al (2013) Metric learning: a survey. Found Trends® Mach Learn 5(4):287–364

Kullback S, Leibler RA (1951) On information and sufficiency. Ann Math Stat 22(1):79–86MathSciNetMATH

Larson J, Michalski RS (1977) Inductive inference of VL decision rules. SIGART Bull 63(63):38–44. https://doi.org/10.1145/1045343.1045369CrossRef

Lavrac N, Dzeroski S (1994) Inductive logic programming. In: Fuchs NE, Gottlob G (eds) WLP. Springer, Berlion, pp 146–160

Lehmann J, Hitzler P (2007) A refinement operator based learning algorithm for the LC description logic. In: Blockeel H, Ramon J, Shavlik JW, Tadepalli P (eds) ILP. Lecture notes in computer science, vol 4894. Springer, Berlin, pp 147–160

Lehmann J, Haase C (2009) Ideal downward refinement in the EL description logic. In: Raedt LD (ed) ILP. Lecture notes in computer science, vol 5989. Springer, Berlin pp 73–87

Leishman D (1989) Analogy as a constrained partial correspondence over conceptual graphs. In: KR, pp 223–234

Levenshtein VI (1966) Binary codes capable of correcting deletions, insertions, and reversals. Sov Phys Dokl 10:707–710MathSciNet

Levi G (1973) A note on the derivation of maximal common subgraphs of two directed or undirected graphs. Calcolo 9(4):341MathSciNetMATH

Li Y, Gu C, Dullien T, Vinyals O, Kohli P (2019) Graph matching networks for learning the similarity of graph structured objects. arXiv preprint arXiv:190412787

Lü L, Zhou T (2011) Link prediction in complex networks: a survey. Phys A Stat Mech Its Appl 390(6):1150–1170

Luss R, d’Aspremont A (2008) Support vector machine classification with indefinite kernels. In: Advances in neural information processing systems, pp 953–960

Mahé P, Ueda N, Akutsu T, Perret JL, Vert JP (2005) Graph kernels for molecular structure–activity relationship analysis with support vector machines. J Chem Inf Model 45(4):939–951

Manago M, Bergmann R, Conruyt N, Traphöner R, Pasley J, Le Renard J, Maurer F, Wess S, Althoff KD, Dumont S (1994) Casuel: a common case representation language. INRECA Consortium Available on the World-Wide Web at http://wwwagr informatik unikl de/bergmann/casuel/CASUEL toc2 4

Marteau PF (2009) Time warp edit distance with stiffness adjustment for time series matching. IEEE Trans Pattern Anal Mach Intell 31(2):306–318

Miller GA (1995) Wordnet: a lexical database for english. Commun ACM 38(11):39–41

Minsky M (1974) A framework for representing knowledge, MIT-AI LAboratory Memo 306

Mishne G, De Rijke M (2004) Source code retrieval using conceptual similarity. In: Coupling approaches, coupling media and coupling languages for information retrieval, pp 539–554

Mitchell TM (1980) The need for biases in learning generalizations. Department of Computer Science, Laboratory for Computer Science Research, Rutgers Univ, New Jersey

Mitchell TM, Keller RM, Kedar-Cabelli ST (1986) Explanation-based generalization: a unifying view. Mach Learn 1(1):47–80

Montani S, Leonardi G, Quaglini S, Cavallini A, Micieli G et al (2015) A knowledge-intensive approach to process similarity calculation. Expert Syst Appl 42(9):4207–4215

Muggleton S, Lodhi H, Amini A, Sternberg MJ (2005) Support vector inductive logic programming. In: International conference on discovery science. Springer, pp 163–175

Munkres J (1957) Algorithms for the assignment and transportation problems. J Soc Ind Appl Math 5(1):32–38MathSciNetMATH

Needleman SB, Wunsch CD (1970) A general method applicable to the search for similarities in the amino acid sequence of two proteins. J Mol Biol 48(3):443–453

Neuhaus M, Bunke H (2006a) A convolution edit kernel for error-tolerant graph matching. In: 18th international conference on pattern recognition, 2006. ICPR 2006, vol 4. IEEE, pp 220–223

Neuhaus M, Bunke H (2006b) Edit distance-based kernel functions for structural pattern classification. Pattern Recogn 39(10):1852–1863MATH

Neuhaus M, Bunke H (2007) Automatic learning of cost functions for graph edit distance. Inf Sci 177(1):239–247MathSciNetMATH

Ng AY, Jordan MI, Weiss Y et al (2002) On spectral clustering: analysis and an algorithm. Adv Neural Inf Process Syst 2:849–856

Nienhuys-Cheng SH (1997) Distance between Herbrand interpretations: a measure for approximations to a target concept. In: Lavrac N, Dzeroski S (eds) Inductive logic programming. Springer, Berlin, pp 213–226MATH

Nikolentzos G, Meladianos P, Limnios S, Vazirgiannis M (2018) A degeneracy framework for graph similarity. Proc IJCAI 2018:2595–2601

Ontañón S, Zhu J (2011) The SAM algorithm for analogy-based story generation. In: Seventh artificial intelligence and interactive digital entertainment conference

Ontanón S, Plaza E (2012) Similarity measures over refinement graphs. Mach Learn 87:57–92MathSciNetMATH

Ontañón S, Shokoufandeh A (2016) Refinement-based similarity measures for directed labeled graphs. In: International conference on case-based reasoning. Springer, pp 311–326

Ontañón S, Montaña JL, Gonzalez AJ (2014) A dynamic-bayesian network framework for modeling and evaluating learning from observation. Expert Syst Appl 41(11):5212–5226

Page L, Brin S, Motwani R, Winograd T (1999) The pagerank citation ranking: bringing order to the web. Technical report, Stanford InfoLab

Plaza E (1995) Cases as terms: a feature term approach to the structured representation of cases. In: International conference on case-based reasoning. Springer, pp 265–276

Plaza E, Armengol E, Ontañón S (2005) The explanatory power of symbolic similarity in case-based reasoning. Artif Intell Rev 24(2):145–161MATH

Plotkin GD (1970) A note on inductive generalization. In: Meltzer B, Michie D (eds) Machine intelligence, vol 5. Edinburgh University Press, Edinburgh, pp 153–163

Pons P, Latapy M (2005) Computing communities in large networks using random walks. In: International symposium on computer and information sciences. Springer, pp 284–293

Poole J, Campbell J (1995) A novel algorithm for matching conceptual and related graphs. In: International conference on conceptual structures. Springer, pp 293–307

Rada R, Mili H, Bicknell E, Blettner M (1989) Development and application of a metric on semantic nets. IEEE Trans Syst Man Cybern 19(1):17–30

Ralaivola L, Swamidass SJ, Saigo H, Baldi P (2005) Graph kernels for chemical informatics. Neural Netw 18(8):1093–1110

Ramon J, Bruynooghe M (1998) A framework for defining distances between first-order logic objects. In: International conference on inductive logic programming. Springer, pp 271–280

Ramon J, Gärtner T (2003) Expressivity versus efficiency of graph kernels. In: Proceedings of the first international workshop on mining graphs, trees and sequences, pp 65–74

Ramoni M, Sebastiani P, Cohen P (2002) Bayesian clustering by dynamics. Mach Learn 47(1):91–121MATH

Read RC, Corneil DG (1977) The graph isomorphism disease. J Graph Theory 1(4):339–363MathSciNetMATH

Resnik P (1995) Using information content to evaluate semantic similarity in a taxonomy. arXiv:cmp-lg/9511007

Resnik P et al (1999) Semantic similarity in a taxonomy: an information-based measure and its application to problems of ambiguity in natural language. J Artif Intell Res: JAIR 11:95–130MATH

Riesen K, Bunke H (2008) Iam graph database repository for graph based pattern recognition and machine learning. In: da Vitoria Lobo N, Kasparis T, Roli F, Kwok JT, Georgiopoulos M, Anagnostopoulos GC, Loog M (eds) Structural, syntactic, and statistical pattern recognition. Springer, Orlando, pp 287–297

Riesen K, Bunke H (2009) Approximate graph edit distance computation by means of bipartite graph matching. Image Vis Comput 27(7):950–959

Rubner Y, Tomasi C, Guibas LJ (2000) The earth mover’s distance as a metric for image retrieval. Int J Comput Vis 40(2):99–121MATH

Sánchez-Ruiz AA, Ontañón S, González-Calero PA, Plaza E (2011) Measuring similarity in description logics using refinement operators. In: ICCBR, pp 289–303

Sánchez-Ruiz AA, Ontañón S, González-Calero PA, Plaza E (2016) Measuring similarity of individuals in description logics over the refinement space of conjunctive queries. J Intell Inf Syst 47(3):447–467

Sanfeliu A, Fu KS (1983) A distance measure between attributed relational graphs for pattern recognition. IEEE Trans Syst Man Cybern 3:353–362MATH

Santini S, Jain R (1999) Similarity measures. IEEE Trans Pattern Anal Mach Intell 21(9):871–883

Schaaf JW (1996) Fish and shrink. A next step towards efficient case retrieval in large scaled case bases. In: European workshop on advances in case-based reasoning. Springer, pp 362–376

Schädler K, Wysotzki F (1999) Comparing structures using a hopfield-style neural network. Appl Intell 11(1):15–30

Sebag M (1997) Distance induction in first order logic. In: International conference on inductive logic programming. Springer, pp 264–272

Serra J, Arcos JL (2014) An empirical evaluation of similarity measures for time series classification. Knowl Based Syst 67:305–314

Shapiro LG, Haralick RM (1981) Structural descriptions and inexact matching. IEEE Trans Pattern Anal Mach Intell 5:504–519

Shervashidze N, Schweitzer P, van Leeuwen EJ, Mehlhorn K, Borgwardt KM (2011) Weisfeiler–Lehman graph kernels. J Mach Learn Res 12(1):2539–2561MathSciNetMATH

Shieber SM (2003) An introduction to unification-based approaches to grammar. Microtome Publishing, New YorkMATH

Singhal A (2001) Modern information retrieval: a brief overview. IEEE Data Eng Bull 24(4):35–43

Small H (1973) Co-citation in the scientific literature: a new measure of the relationship between two documents. J Assoc Inf Sci Technol 24(4):265–269MathSciNet

Smola AJ, Vishwanathan S (2003) Fast kernels for string and tree matching. In: Thrun S, Saul LK, Schölkopf B (eds) Advances in neural information processing systems. MIT Press, Vancouver, Canada, pp 585–592

Sørensen TJ (1948) A method of establishing groups of equal amplitude in plant sociology based on similarity of species content. Kongelige Danske Videnskabernes Selskab 5(1–34):4–7

Sowa JF (1979) Semantics of conceptual graphs. In: Proceedings of the 17th annual meeting on Association for Computational Linguistics. Association for Computational Linguistics, pp 39–44

Spielman DA (2010) Algorithms, graph theory, and linear equations in laplacian matrices. In: Proceedings of the international congress of mathematicians 2010 (ICM 2010) (In 4 Volumes) vol I: plenary lectures and ceremonies vols. II–IV: invited lectures. World Scientific, pp 2698–2722

Sussenguth EH (1964) Structure matching in information processing. Harvard University, CambridgeMATH

Tai KC (1979) The tree-to-tree correction problem. J ACM: JACM 26(3):422–433MathSciNetMATH

Tsai WH, Fu KS (1979) Error-correcting isomorphisms of attributed relational graphs for pattern analysis. IEEE Trans Syst Man Cybern 9(12):757–768MATH

Tsuda K, Kin T, Asai K (2002) Marginalized kernels for biological sequences. Bioinformatics 18(Suppl 1):S268–S275

Tversky A (1977) Features of similarity. Psychol Rev 84:327–352

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

Valls-Vargas J, Ontanón S, Zhu J (2014) Toward automatic character identification in unannotated narrative text. In: Seventh intelligent narrative technologies workshop

van der Laag PRJ, Nienhuys-Cheng SH (1998) Completeness and properness of refinement operators in inductive logic programming. J Log Program 34(3):201–225MathSciNetMATH

Vert JP, Tsuda K, Schölkopf B (2004) A primer on kernel methods. Kernel Methods Comput Biol 47:35–70

Wallis WD, Shoubridge P, Kraetz M, Ray D (2001) Graph distances using graph union. Pattern Recogn Lett 22(6):701–704MATH

Wang Y, Ishii N (1997) A method of similarity metrics for structured representations. Expert Syst Appl 12(1):89–100

Weisfeiler B, Lehman AA (1968) A reduction of a graph to a canonical form and an algebra arising during this reduction. Nauchno-Technicheskaya Informatsia 2(9):12–16

Welch TA (1984) A technique for high-performance data compression. Computer 6(17):8–19

Wess S (1995) Fallbasiertes Problemlösen in wissensbasierten systemen zur entscheidungsunterst ützung und diagnostik

Wettschereck D, Aha DW, Mohri T (1997) A review and empirical evaluation of feature weighting methods for a class of lazy learning algorithms. Artif Intell Rev 11(1–5):273–314

Wolpert DH (1996) The lack of a priori distinctions between learning algorithms. Neural Comput 8(7):1341–1390

Wu Z, Palmer M (1994) Verbs semantics and lexical selection. In: Proceedings of the 32nd annual meeting on Association for Computational Linguistics. Association for Computational Linguistics, pp 133–138

Xu L, King I (2001) A pca approach for fast retrieval of structural patterns in attributed graphs. IEEE Trans Syst Man Cybern Part B (Cybern) 31(5):812–817

Xu K, Hu W, Leskovec J, Jegelka S (2018) How powerful are graph neural networks? arXiv:181000826

Yang L, Jin R (2006) Distance metric learning: a comprehensive survey. Mich State Univ 2(2):4

Zhang K (1989) The editing distance between trees: algorithms and applications. PhD thesis from the New York University

Zhang Z, Wang M, Xiang Y, Huang Y, Nehorai A (2018) Retgk: graph kernels based on return probabilities of random walks. In: Bengio S, Wallach HM, Larochelle H, Grauman K, Cesa-Bianchi N, Garnett R, Neural Information Processing Systems Conference (eds) Advances in neural information processing systems, Vancouver, Canada, pp 3964–3974

Titel: An overview of distance and similarity functions for structured data
verfasst von: Santiago Ontañón
Publikationsdatum: 27.02.2020
Verlag: Springer Netherlands
Erschienen in: Artificial Intelligence Review / Ausgabe 7/2020
Print ISSN: 0269-2821
Elektronische ISSN: 1573-7462
DOI: https://doi.org/10.1007/s10462-020-09821-w

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 7/2020

A comprehensive survey on model compression and acceleration

A systematic review of gamification techniques applied to elderly care

A self-verifying clustering approach to unsupervised matching of product titles

Multiple-criteria decision making method based on the scaled prioritized operators with unbalanced linguistic information

The effect of downsampling–upsampling strategy on foreground detection algorithms

A review for cervical histopathology image analysis using machine vision approaches

Premium Partner