Skip to main content

2016 | OriginalPaper | Buchkapitel

Refinement-Based Similarity Measures for Directed Labeled Graphs

verfasst von : Santiago Ontañón, Ali Shokoufandeh

Erschienen in: Case-Based Reasoning Research and Development

Verlag: Springer International Publishing

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

search-config
loading …

Abstract

This paper presents a collection of similarity measures based on refinement operators for directed labeled graphs (DLGs). We build upon previous work on refinement operators for other representation formalisms such as feature terms and description logics. Specifically, we present refinement operators for DLGs, which enable the adaptation of three similarity measures to DLGs: the anti-unification-based, \(S_{\lambda }\), the property-based, \(S_{\pi }\), and the weighted property-based, \(S_{w\pi }\), similarities. We evaluate the resulting measures empirically comparing them to existing similarity measures for structured data.

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!

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!

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!

Fußnoten
1
A Refinement-Operator Library for Directed Labeled Graphs: https://​github.​com/​santiontanon/​RHOG.
 
2
A graph trivially subsumes itself with the mapping \(m(v) = v\).
 
3
If a graph \(g_1\) subsumes \(g_2\) through a mapping \(m_1\), and \(g_2\) subsumes \(g_3\) through a mapping \(m_2\), then we know \(g_1\) subsumes \(g_3\) via the mapping \(m(v) = m_2(m_1(v))\).
 
4
Notice that it is possible to compute the remainder without the need to actually perform any type of unification operation, which can be computationally expensive.
 
5
Datasets can be downloaded in dot, GML and GraphML format from https://​github.​com/​santiontanon/​RHOG.
 
Literatur
1.
Zurück zum Zitat Aamodt, A., Plaza, E.: Case-based reasoning: foundational issues, methodological variations, and system approaches. Artif. Intell. Commun. 7(1), 39–59 (1994) Aamodt, A., Plaza, E.: Case-based reasoning: foundational issues, methodological variations, and system approaches. Artif. Intell. Commun. 7(1), 39–59 (1994)
2.
Zurück zum Zitat Armengol, E., Plaza, E.: Relational case-based reasoning for carcinogenic activity prediction. Artif. Intell. Rev. 20(1–2), 121–141 (2003)CrossRef Armengol, E., Plaza, E.: Relational case-based reasoning for carcinogenic activity prediction. Artif. Intell. Rev. 20(1–2), 121–141 (2003)CrossRef
3.
Zurück zum Zitat Bergmann, R., Stahl, A.: Similarity measures for object-oriented case representations. In: Smyth, B., Cunningham, P. (eds.) EWCBR 1998. LNCS, vol. 1488, pp. 25–36. Springer, Heidelberg (1998). doi:10.1007/BFb0056319 CrossRef Bergmann, R., Stahl, A.: Similarity measures for object-oriented case representations. In: Smyth, B., Cunningham, P. (eds.) EWCBR 1998. LNCS, vol. 1488, pp. 25–36. Springer, Heidelberg (1998). doi:10.​1007/​BFb0056319 CrossRef
5.
Zurück zum Zitat Bisson, G.: Learing in FOL with a similarity measure. In: Proceedings of AAAI 1992, pp. 82–87 (1992) Bisson, G.: Learing in FOL with a similarity measure. In: Proceedings of AAAI 1992, pp. 82–87 (1992)
6.
Zurück zum Zitat d’Amato, C.: Similarity-based learning methods for the semantic web. Ph.D. thesis, Università degli Studi di Bari (2007) d’Amato, C.: Similarity-based learning methods for the semantic web. Ph.D. thesis, Università degli Studi di Bari (2007)
7.
Zurück zum Zitat Emde, W., Wettschereck, D.: Relational instance based learning. In: Saitta, L. (ed.) Machine Learning - Proceedings 13th International Conference on Machine Learning, pp. 122–130. Morgan Kaufmann Publishers (1996) Emde, W., Wettschereck, D.: Relational instance based learning. In: Saitta, L. (ed.) Machine Learning - Proceedings 13th International Conference on Machine Learning, pp. 122–130. Morgan Kaufmann Publishers (1996)
8.
Zurück zum Zitat Fanizzi, N., d’Amato, C., Esposito, F.: Induction of optimal semi-distances for individuals based on feature sets. In: Proceedings of 2007 International Workshop on Description Logics, CEUR-WS (2007) Fanizzi, N., d’Amato, C., Esposito, F.: Induction of optimal semi-distances for individuals based on feature sets. In: Proceedings of 2007 International Workshop on Description Logics, CEUR-WS (2007)
9.
Zurück zum Zitat Fanizzi, N., d’Amato, C., Esposito, F.: Learning with Kernels in description logics. In: Železný, F., Lavrač, N. (eds.) ILP 2008. LNCS (LNAI), vol. 5194, pp. 210–225. Springer, Heidelberg (2008). doi:10.1007/978-3-540-85928-4_18 CrossRef Fanizzi, N., d’Amato, C., Esposito, F.: Learning with Kernels in description logics. In: Železný, F., Lavrač, N. (eds.) ILP 2008. LNCS (LNAI), vol. 5194, pp. 210–225. Springer, Heidelberg (2008). doi:10.​1007/​978-3-540-85928-4_​18 CrossRef
10.
Zurück zum Zitat Ferilli, S., Fanizzi, N., Di Mauro, N., Basile, T.M.: Efficient theta-subsumption under object identity. In: Workshop AI*IA 2002, pp. 59–68 (2002) Ferilli, S., Fanizzi, N., Di Mauro, N., Basile, T.M.: Efficient theta-subsumption under object identity. In: Workshop AI*IA 2002, pp. 59–68 (2002)
11.
Zurück zum Zitat Gabel, T.: Learning similarity measures: strategies to enhance the optimisation process. Diploma thesis, kaiserslautern university of technology (2003) Gabel, T.: Learning similarity measures: strategies to enhance the optimisation process. Diploma thesis, kaiserslautern university of technology (2003)
12.
Zurück zum Zitat Gärtner, T., Lloyd, J.W., Flach, P.A.: Kernels for structured data. In: Matwin, S., Sammut, C. (eds.) ILP 2002. LNCS (LNAI), vol. 2583, pp. 66–83. Springer, Heidelberg (2003). doi:10.1007/3-540-36468-4_5 CrossRef Gärtner, T., Lloyd, J.W., Flach, P.A.: Kernels for structured data. In: Matwin, S., Sammut, C. (eds.) ILP 2002. LNCS (LNAI), vol. 2583, pp. 66–83. Springer, Heidelberg (2003). doi:10.​1007/​3-540-36468-4_​5 CrossRef
13.
Zurück zum Zitat González-Calero, P.A., Díaz-Agudo, B., Gómez-Albarrán, M.: Applying DLs for retrieval in case-based reasoning. In: Proceedings of the 1999 Description Logics Workshop (DL 1999) (1999) González-Calero, P.A., Díaz-Agudo, B., Gómez-Albarrán, M.: Applying DLs for retrieval in case-based reasoning. In: Proceedings of the 1999 Description Logics Workshop (DL 1999) (1999)
15.
Zurück zum Zitat Kashima, H., Tsuda, K., Inokuchi, A.: Marginalized Kernels between labeled graphs. In: Proceedings of the Twentieth International Conference (ICML 2003), pp. 321–328. AAAI Press (2003) Kashima, H., Tsuda, K., Inokuchi, A.: Marginalized Kernels between labeled graphs. In: Proceedings of the Twentieth International Conference (ICML 2003), pp. 321–328. AAAI Press (2003)
16.
Zurück zum Zitat van der Laag, P.R.J., Nienhuys-Cheng, S.H.: Completeness and properness of refinement operators in inductive logic programming. J. Logic Program. 34(3), 201–225 (1998)MathSciNetCrossRefMATH van der Laag, P.R.J., Nienhuys-Cheng, S.H.: Completeness and properness of refinement operators in inductive logic programming. J. Logic Program. 34(3), 201–225 (1998)MathSciNetCrossRefMATH
17.
Zurück zum Zitat Larson, J., Michalski, R.S.: Inductive inference of VL decision rules. SIGART Bull. 63(63), 38–44 (1977)CrossRef Larson, J., Michalski, R.S.: Inductive inference of VL decision rules. SIGART Bull. 63(63), 38–44 (1977)CrossRef
18.
Zurück zum Zitat Levenshtein, V.I.: Binary codes capable of correcting deletions, insertions, and reversals. Sov. Phys. Dokl. 10, 707–710 (1966)MathSciNetMATH Levenshtein, V.I.: Binary codes capable of correcting deletions, insertions, and reversals. Sov. Phys. Dokl. 10, 707–710 (1966)MathSciNetMATH
19.
Zurück zum Zitat Nienhuys-Cheng, S.-H.: Distance between herbrand interpretations: a measure for approximations to a target concept. In: Lavrač, N., Džeroski, S. (eds.) ILP 1997. LNCS, vol. 1297, pp. 213–226. Springer, Heidelberg (1997). doi:10.1007/3540635149_50 CrossRef Nienhuys-Cheng, S.-H.: Distance between herbrand interpretations: a measure for approximations to a target concept. In: Lavrač, N., Džeroski, S. (eds.) ILP 1997. LNCS, vol. 1297, pp. 213–226. Springer, Heidelberg (1997). doi:10.​1007/​3540635149_​50 CrossRef
22.
Zurück zum Zitat Ontañón, S., Plaza, E.: Refinement-based disintegration: an approach to re-representation in relational learning. AI Commun. 28(1), 35–46 (2015)MathSciNet Ontañón, S., Plaza, E.: Refinement-based disintegration: an approach to re-representation in relational learning. AI Commun. 28(1), 35–46 (2015)MathSciNet
23.
Zurück zum Zitat Ramon, J.: Clustering and instance based learning in first order logic. AI Commun. 15(4), 217–218 (2002) Ramon, J.: Clustering and instance based learning in first order logic. AI Commun. 15(4), 217–218 (2002)
24.
Zurück zum Zitat Sánchez, D., Batet, M., Isern, D., Valls, A.: Ontology-based semantic similarity: a new feature-based approach. Expert Syst. Appl. 39(9), 7718–7728 (2012)CrossRef Sánchez, D., Batet, M., Isern, D., Valls, A.: Ontology-based semantic similarity: a new feature-based approach. Expert Syst. Appl. 39(9), 7718–7728 (2012)CrossRef
25.
Zurück zum Zitat Sánchez-Ruiz, A.A., Ontañón, S.: Least common subsumer trees for plan retrieval. In: Lamontagne, L., Plaza, E. (eds.) ICCBR 2014. LNCS (LNAI), vol. 8765, pp. 405–419. Springer, Heidelberg (2014). doi:10.1007/978-3-319-11209-1_29 Sánchez-Ruiz, A.A., Ontañón, S.: Least common subsumer trees for plan retrieval. In: Lamontagne, L., Plaza, E. (eds.) ICCBR 2014. LNCS (LNAI), vol. 8765, pp. 405–419. Springer, Heidelberg (2014). doi:10.​1007/​978-3-319-11209-1_​29
26.
Zurück zum Zitat Sánchez-Ruiz, A.A., Ontañón, S., González-Calero, P.A., Plaza, E.: Refinement-based similarity measure over DL conjunctive queries. In: Delany, S.J., Ontañón, S. (eds.) ICCBR 2013. LNCS (LNAI), vol. 7969, pp. 270–284. Springer, Heidelberg (2013). doi:10.1007/978-3-642-39056-2_20 CrossRef Sánchez-Ruiz, A.A., Ontañón, S., González-Calero, P.A., Plaza, E.: Refinement-based similarity measure over DL conjunctive queries. In: Delany, S.J., Ontañón, S. (eds.) ICCBR 2013. LNCS (LNAI), vol. 7969, pp. 270–284. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-39056-2_​20 CrossRef
27.
Zurück zum Zitat Wolf, M., Petridis, M.: Measuring similarity of software designs using graph matching for CBR. In: Workshop Proceedings of AISEW 2008 at ECAI 2008. IOS Press (2008) Wolf, M., Petridis, M.: Measuring similarity of software designs using graph matching for CBR. In: Workshop Proceedings of AISEW 2008 at ECAI 2008. IOS Press (2008)
Metadaten
Titel
Refinement-Based Similarity Measures for Directed Labeled Graphs
verfasst von
Santiago Ontañón
Ali Shokoufandeh
Copyright-Jahr
2016
DOI
https://doi.org/10.1007/978-3-319-47096-2_21