Untangling the Cross-Lingual Link Structure of Wikipedia

Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 844–853, Uppsala, Sweden, 11-16 July 2010. c⃝2010 Association for Computational Linguistics Untangling the Cross-Lingual Link Structure of Wikipedia Gerard de Melo Max Planck Institute for Informatics Saarbr¨ucken, Germany demelo@mpi-inf.mpg.de Gerhard Weikum Max Planck Institute for Informatics Saarbr¨ucken, Germany weikum@mpi-inf.mpg.de Abstract Wikipedia articles in different languages are connected by interwiki links that are increasingly being recognized as a valu- able source of cross-lingual information. Unfortunately, large numbers of links are imprecise or simply wrong. In this pa- per, techniques to detect such problems are identified. We formalize their removal as an optimization task based on graph re- pair operations. We then present an al- gorithm with provable properties that uses linear programming and a region growing technique to tackle this challenge. This allows us to transform Wikipedia into a much more consistent multilingual regis- ter of the world’s entities and concepts. 1 Introduction Motivation. The open community-maintained en- cyclopedia Wikipedia has not only turned the In- ternet into a more useful and linguistically di- verse source of information, but is also increas- ingly being used in computational applications as a large-scale source of linguistic and encyclope- dic knowledge. To allow cross-lingual navigation, Wikipedia offers cross-lingual interwiki links that for instance connect the Indonesian article about Albert Einstein to the corresponding articles in over 100 other languages. Such links are extraor- dinarily valuable for cross-lingual applications. In the ideal case, a set of articles connected di- rectly or indirectly via such links would all de- scribe the same entity or concept. Due to concep- tual drift, different granularities, as well as mis- takes made by editors, we frequently find con- cepts as different as economics and manager in the same connected component. Filtering out inaccu- rate links enables us to exploit Wikipedia’s multi- linguality in a much safer manner and allows us to create a multilingual register of named entities. Contribution. Our research contributions are: 1) We identify criteria to detect inaccurate connec- tions in Wikipedia’s cross-lingual link structure. 2) We formalize the task of removing such links as an optimization problem. 3) We introduce an algorithm that attempts to repair the cross-lingual graph in a minimally invasive way. This algorithm has an approximation guarantee with respect to optimal solutions. 4) We show how this algorithm can be used to combine all editions of Wikipedia into a single large-scale multilingual register of named entities and concepts. 2 Detecting Inaccurate Links In this paper, we model the union of cross-lingual links provided by all editions of Wikipedia as an undirected graph G = (V, E) with edge weights w(e) for e ∈ E. In our experiments, we simply honour each individual link equally by defining w(e) = 2 if there are reciprocal links between the two pages, 1 if there is a single link, and 0 other- wise. However, our framework is flexible enough to deal with more advanced weighting schemes, e.g. one could easily plug in cross-lingual mea- sures …

Content truncated to 500 words