Exploiting Graph Structure for Accelerating the Calculation of Shortest Paths in Wordnets

Proceedings of the 22nd International Conference on Computational Linguistics (Coling 2008), pages 1001–1008 Manchester, August 2008 Exploiting Graph Structure for Accelerating the Calculation of Shortest Paths in Wordnets Holger Wunsch Collaborative Research Center 441 “Linguistic Data Structures” University of T¨ubingen, Germany wunsch@sfs.uni-tuebingen.de Abstract This paper presents an approach for sub- stantially reducing the time needed to cal- culate the shortest paths between all con- cepts in a wordnet. The algorithm exploits the unique “star-like” topology of word- nets to cut down on time-expensive calcu- lations performed by algorithms to solve the all-pairs shortest path problem in gen- eral graphs. The algorithm was applied to two wordnets of two different languages: Princeton WordNet (Fellbaum, 1998) for English, and GermaNet (Kunze and Lem- nitzer, 2002), the German language word- net. For both wordnets, the time needed for finding all shortest paths was brought down from several days to a matter of minutes. 1 Introduction Significant effort has been devoted in linguistic re- search to the problem of determining the semantic distance1 between two concepts. Many of the ap- proaches that were developed to provide a solution for the task use wordnets as their basic knowledge resource. Budanitsky and Hirst (2006) present an extensive number of approaches for determining lexical semantic relatedness based on the Prince- ton WordNet (Fellbaum, 1998). A large number of these solutions have in common that at some point in the calculation, the length of the shortest path that connects the two concepts in question has c⃝ 2008. Licensed under the Creative Commons Attribution-Noncommercial-Share Alike 3.0 Unported li- cense (http://creativecommons.org/licenses/by-nc-sa/3.0/). Some rights reserved. 1see Budanitsky and Hirst (2006) for a critical discussion of the term “semantic distance”. to be taken into account. The length of the short- est path between two concepts is thus a vital piece of information in virtually any approach for deter- mining their semantic distance. From a computer science perspective, a word- net is a directed graph. The nodes in the graph correspond to the concepts that are stored in the wordnet. Two nodes are connected by an edge if there exists a semantic relation between the two concepts that correspond to the nodes. The edges are directed, reflecting the directedness of seman- tic relations in wordnets, such as the relation of hypernymy. The problem of finding the shortest path between two nodes in a graph has been well studied in computer science. Sedgewick (1990) presents two algorithms: • Dijkstra’s algorithm finds the shortest path between two concepts in quadratic time, and is extensible to find the shortest paths be- tween all concepts in cubic time. • The Floyd-Warshall algorithm, which is very easy to implement, solves the all-pairs short- est path problem in cubic time as well. The Floyd-Warshall algorithm served as the base- line algorithm for this paper. Both algorithms operate on general directed graphs. The structure of a directed graph is sketched in figure 1. Given two nodes, there exist multiple different paths that connect the two nodes. In figure 1, in …

Content truncated to 500 words