In English

Entity Disambiguation in Anonymized Graphs Using Graph Kernels

Linus Hermansson ; Tommi Kerola
Göteborg : Chalmers tekniska högskola, 2013. 76 s.
[Examensarbete på avancerad nivå]

In recent years, the explosion of available online information has brought forth new data mining applications into the spotlight, such as automated querying about realworld entities. This requires extraction of identi ers such as names and places from text. The problem, however, is complicated by the non-uniqueness of identi ers. A motivating example is the name Chris Anderson, which could either refer to Chris Anderson, the curator of TED Talks, or Chris Anderson, the former editor-in-chief of WIRED Magazine. Both individuals work in overlapping elds, and deciding whom is referred to could be a dicult task, even when considering context. Correctly identifying and resolving such ambiguous identi ers is crucial for enabling such applications to advance from the research lab into practical usage. This master's thesis presents a novel method for entity disambiguation in anonymized graphs based on local neighborhood structure. Most existing approaches leverage node information, which might not be available in several contexts due to privacy concerns, or information about the sources of the data. We consider this problem in the supervised setting where we are provided only with a base graph and a set of nodes labeled as ambiguous or unambiguous. We characterize the similarity between two nodes based on their local neighborhood structure using graph kernels; and e-ciently solve the resulting classi cation task using a support vector machine (SVM), a standard machine learning technique. Leveraging kernels is a powerful method for extending linear SVM classi ers to nonlinear classi cation tasks. Recently, a number of graph kernels have been proposed for classifying graph structures. In this thesis, we present extensions of two existing graphs kernels, namely, the direct product kernel and the shortest-path kernel, with signi cant improvements in accuracy. For the direct product kernel, our extension also provides signi cant computational bene ts. A key concern today is scalability of algorithms to web-scale datasets. This poses new challenges for designing new machine learning methods. We use GraphLab, a framework for distributed computing, to allow our extended kernels to be computed in parallel. This ensures scalability and allows our method to handle large-size data. We test our method on two real-world datasets, comparing our approach to a stateof-the-art method. We show that using less information, our method is signi cantly better in terms of either speed or accuracy or both.

Publikationen registrerades 2013-10-01.

CPL ID: 184373

Detta är en tjänst från Chalmers bibliotek