Breaking cycles in noisy hierarchies
|Title:||Breaking cycles in noisy hierarchies||Authors:||Sun, Jiankai
Nicholson, Patrick K.
|Permanent link:||http://hdl.handle.net/10197/10131||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 Graph; Graph Hierarchy; TrueSkill; Social Agony; Cycle Edges||DOI:||10.1145/3091478.3091495||Other versions:||http://www.websci17.org/||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
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.