Breaking Cycles via Graph Hierarchy

Taxonomy graphs that capture hyponymy or meronymy relationships through directed edges are expected to be acyclic. In practice, however, they have thousands of cycles, since they are created in a crowd-sourced way. Computation of a maximal directed acyclic subgraph of graphs, with inherent hierarchy, can benefit many applications. In this paper, we address the problem of breaking cycles while preserving the logical structure (hierarchy) of the directed graph as much as possible. Existing approaches either need manual intervention or cannot guarantee optimality. In contrast, our approach infers graph hierarchy by a Bayesian skill rating system and social agony. We also devise several strategies to select edges to be removed based on corresponding nodes' ranking scores in the hierarchy. Extensive experiments demonstrate the effectiveness of our approach.