In this paper we present CrumbTrail, an algorithm to clean large and dense knowledge graphs. CrumbTrail removes cycles, out-of-domain nodes and non-essential nodes, i.e., those that can be safely removed without breaking the knowledge graph’s connectivity. It achieves this through a bottom-up topological pruning on the basis of a set of input concepts that, for instance, a user can select in order to identify a domain of interest. Our technique can be applied to both noisy hypernymy graphs – typically generated by ontology learning algorithms as intermediate representations – as well as crowdsourced resources like Wikipedia, in order to obtain clean, domain-focused concept hierarchies. CrumbTrail overcomes the time and space complexity limitations of current state-of-art algorithms. In addition, we show in a variety of experiments that it also outperforms them in tasks such as pruning automatically acquired taxonomy graphs, and domain adaptation of the Wikipedia category graph.

CrumbTrail: an Efficient Methodology to Reduce Multiple Inheritance in Knowledge Graphs / Faralli, Stefano; Finocchi, Irene; Paolo Ponzetto, Simone; Velardi, Paola. - In: KNOWLEDGE-BASED SYSTEMS. - ISSN 0950-7051. - STAMPA. - 151:(2018), pp. 180-197. [10.1016/j.knosys.2018.03.030]

CrumbTrail: an Efficient Methodology to Reduce Multiple Inheritance in Knowledge Graphs

Stefano Faralli;Irene Finocchi;Paola Velardi
2018

Abstract

In this paper we present CrumbTrail, an algorithm to clean large and dense knowledge graphs. CrumbTrail removes cycles, out-of-domain nodes and non-essential nodes, i.e., those that can be safely removed without breaking the knowledge graph’s connectivity. It achieves this through a bottom-up topological pruning on the basis of a set of input concepts that, for instance, a user can select in order to identify a domain of interest. Our technique can be applied to both noisy hypernymy graphs – typically generated by ontology learning algorithms as intermediate representations – as well as crowdsourced resources like Wikipedia, in order to obtain clean, domain-focused concept hierarchies. CrumbTrail overcomes the time and space complexity limitations of current state-of-art algorithms. In addition, we show in a variety of experiments that it also outperforms them in tasks such as pruning automatically acquired taxonomy graphs, and domain adaptation of the Wikipedia category graph.
File allegati a questo prodotto
File Dimensione Formato  
Faralli_ CrumbTrail_2018.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 2.16 MB
Formato Adobe PDF
2.16 MB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11573/1084789
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 2
social impact