Automated assessment of knowledge hierarchy evolution: comparing directed acyclic graphs

Files in This Item:
Access to this item has been restricted by the copyright holder until:2019-12-17
File Description SizeFormat 
ajwani_ir_journal_18_web.pdf1.65 MBAdobe PDFDownload    Request a copy
Title: Automated assessment of knowledge hierarchy evolution: comparing directed acyclic graphs
Authors: Nayak, Guruprasad
Dutta, Sourav
Ajwani, Deepak
et al.
Permanent link:
Date: 17-Dec-2018
Online since: 2019-04-10T11:28:37Z
Abstract: Automated construction of knowledge hierarchies from huge data corpora is gaining increasing attention in recent years, in order to tackle the infeasibility of manually extracting and semantically linking millions of concepts. As a knowledge hierarchy evolves with these automated techniques, there is a need for measures to assess its temporal evolution, quantifying the similarities between different versions and identifying the relative growth of different subgraphs in the knowledge hierarchy. In this paper, we focus on measures that leverage structural properties of the knowledge hierarchy graph to assess the temporal changes. We propose a principled and scalable similarity measure, based on Katz similarity between concept nodes, for comparing different versions of a knowledge hierarchy, modeled as a generic directed acyclic graph. We present theoretical analysis to depict that the proposed measure accurately captures the salient properties of taxonomic hierarchies, assesses changes in the ordering of nodes, along with the logical subsumption of relationships among concepts. We also present a linear time variant of the measure, and show that our measures, unlike previous approaches, are tunable to cater to diverse application needs. We further show that our measure provides interpretability, thereby identifying the key structural and logical difference in the hierarchies. Experiments on a real DBpedia and biological knowledge hierarchy showcase that our measures accurately capture structural similarity, while providing enhanced scalability and tunability. Also, we demonstrate that the temporal evolution of different subgraphs in this knowledge hierarchy, as captured purely by our structural measure, corresponds well with the known disruptions in the related subject areas.
Type of material: Journal Article
Publisher: Springer
Journal: Information Retrieval Journal
Start page: 1
End page: 29
Copyright (published version): 2018 Springer
Keywords: Knowledge hierarchy matchingDAG similarityConcept trackingSemantic subsumptionTaxonomy evaluation
DOI: 10.1007/s10791-018-9345-y
Language: en
Status of Item: Peer reviewed
Appears in Collections:Computer Science Research Collection

Show full item record

Citations 50

Last Week
Last month
checked on May 17, 2019

Google ScholarTM



This item is available under the Attribution-NonCommercial-NoDerivs 3.0 Ireland. No item may be reproduced for commercial purposes. For other possible restrictions on use please refer to the publisher's URL where this is made available, or to notes contained in the item itself. Other terms may apply.