Graph Kernels

Gupta, A (2012) Graph Kernels. Masters thesis, Indian Institute of Technology, Hyderabad.

Preview

Text
CS10M01.pdf - Submitted Version
Download (1MB)

Abstract

Data Mining and Machine Learning are in the midst of a \structured revolution" [1]. As we can represent almost anything using graphs, learning and data mining on graphs have become a challenge in various applications. The main algorithmic diculty in these areas, measuring similarity of graphs, has therefore received signicant attention in recent past. Graph kernels proposes a theoretically sound and promising approach to the problem of graph comparison. These kernels should respect the information represented by the topology of the graphs, while being ecient to compute. Graph kernel are used in elds like machine learning, data mining, language processing and bioinformatics. Some of the existing graph kernel methods doesn't include topological information or have runtime issues or they do not scale to large graphs. The primary goal of this thesis is to propose a graph kernel which is ecient to compute and can work accurately on large graphs. In this thesis we analyze existing graph kernels and their drawbacks. Then we propose a graph kernel, based on counting connected size-k graphlets [2]. We conducted experiments on various graphs to test accuracy of our graph kernel.

[error in script]

IITH Creators: