Breaking cycles in noisy hierarchies

Files in This Item:
File Description SizeFormat 
ajwani_webscience17.pdf4.3 MBAdobe PDFDownload
Title: Breaking cycles in noisy hierarchies
Authors: Sun, Jiankai
Ajwani, Deepak
Nicholson, Patrick K.
et al.
Permanent link:
Date: 28-Jun-2017
Online since: 2019-04-24T12:54:01Z
Abstract: Taxonomy graphs that capture hyponymy or meronymy relationships through directed edges are expected to be acyclic. However, in practice, they may have thousands of cycles, as they are often created in a crowd-sourced way. Since these cycles represent logical fallacies, they need to be removed for many web applications. In this paper, we address the problem of breaking cycles while preserving the logical structure (hierarchy) of a directed graph as much as possible. Existing approaches for this problem either need manual intervention or use heuristics that can critically alter the taxonomy structure. In contrast, our approach infers graph hierarchy using a range of features, including a Bayesian skill rating system and a social agony metric. We also devise several strategies to leverage the inferred hierarchy for removing a small subset of edges to make the graph acyclic. Extensive experiments demonstrate the effectiveness of our approach.
Type of material: Conference Publication
Publisher: ACM
Start page: 151
End page: 160
Copyright (published version): 2017 the Authors
Keywords: Directed Acyclic GraphGraph HierarchyTrueSkillSocial AgonyCycle Edges
DOI: 10.1145/3091478.3091495
Other versions:
Language: en
Status of Item: Not peer reviewed
Is part of: WebSci 2017 - Proceedings of the 2017 ACM Web Science Conference
Conference Details: 9th International ACM Web Science Conference 2017, held from June 26 to June 28, 2017 in Troy, NY (USA)
ISBN: 9781450348966
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.