Global Path-Based Refinement of Noisy Graphs Applied to Verb Semantics

R. Dale et al. (Eds.): IJCNLP 2005, LNAI 3651, pp. 792 – 803, 2005. © Springer-Verlag Berlin Heidelberg 2005 Global Path-Based Refinement of Noisy Graphs Applied to Verb Semantics Timothy Chklovski and Patrick Pantel Information Sciences Institute,University of Southern California, 4676 Admiralty Way,Marina del Rey, CA 90292 {timc, pantel}@isi.edu Abstract. Recently, researchers have applied text- and web-mining algorithms to mine semantic resources. The result is often a noisy graph of relations be- tween words. We propose a mathematically rigorous refinement framework, which uses path-based analysis, updating the likelihood of a relation between a pair of nodes using evidence provided by multiple indirect paths between the nodes. Evaluation on refining temporal verb relations in a semantic resource called VERBOCEAN showed a 16.1% error reduction after refinement. 1 Introduction Increasingly, researchers are creating broad-coverage semantic resources by mining text corpora [1][5] and the Web [2][6]. These resources typically consist of a noisy collection of relations between words. The data is typically extracted on a per link basis (i.e., the relation between two nodes is determined without regard to other nodes). Yet, little work has taken a global view of the graph of relations, which may provide additional information to refine local decisions by identifying inconsistencies, updating confidences in specific edges (relations), and suggesting relations between additional pairs of nodes. For example, observing the temporal verb relations “discover happens-before re- fine” and “refine happens-before exploit” provides evidence for the relation “discover happens-before exploit,” because the happens-before relation is transitive. We conceptualize a semantic resource encoding relations between words as a graph where words are nodes and binary relations between words are edges. In this paper, we investigate the refinement of such graphs by updating the confidence in edges using a global analysis relying on link semantics. Our approach is based on the observation that some paths (chains of relations) between a pair of nodes xi and xj imply the presence or absence of a particular direct relation between xi and xj. Despite each individual path being noisy, multiple indirect paths can provide sufficient evidence for adding, remov- ing, or altering a relation between two nodes. As illustrated by the earlier example, inferring a relation based on the presence of an indirect path relies on the semantics of the links that make up the path, like transitivity or equivalence classes. As an evaluation and a sample practical application, we apply our refinement framework to the task of refining the temporal precedence relations in VERBOCEAN, a broad-coverage noisy network of semantic relations between verbs extracted by mining the Web [2]. Examples of new edges discovered (added) by applying the Global Path-Based Refinement of Noisy Graphs Applied to Verb Semantics 793 framework include: “ascertain happens-before evaluate”, “approve happens-before back”, “coat happens-before bake”, “plan happens-before complete”, and “interrogate happens-before extradite”. Examples of edges that are removed by applying our framework include: “induce happens-before treat”, “warm happens-before heat”, “halve happens-before slice”, and “fly happens-before operate”. Experiments show that our framework is particularly good at filtering out the in- …

Content truncated to 500 words