### Skapa referens, olika format (klipp och klistra)

**Harvard**

Kilhamn, J. (2015) *Fast shortest-path kernel computations using aproximate methods*. Göteborg : Chalmers University of Technology

** BibTeX **

@mastersthesis{

Kilhamn2015,

author={Kilhamn, Jonatan},

title={Fast shortest-path kernel computations using aproximate methods},

abstract={The shortest-path kernel is frequently seen in the context of graph classification, which shows up in various subjects, for example bioinformatics. However, it is not
efficient enough to be applicable in practice if the graphs are too large. The purpose of this thesis is to explore the possibilities of computing the shortest-path kernel approximately, taking shorter time at the cost of a limited error.<br><br>
This thesis proves a theoretical error bound for a class of kernel function approximations, applicable to the shortest-path kernel but further generaliseable as well. We also present two specific approximations of the shortest-path kernel.<br><br>
Firstly, we define an approximate kernel based on the idea of sampling node pairs in a graph to approximate its shortest-path length distribution. Secondly, we define a kernel computing approximate shortest-path lengths in a graph using its graph Voronoi dual. We provide algorithms to compute both of these, and prove that their runtime complexities are better than the shortest-path kernel they approximate. Finally, we evaluate these kernel approximations empirically, comparing them to the full shortest-path kernel as well as other reference kernels.},

publisher={Institutionen för data- och informationsteknik (Chalmers), Chalmers tekniska högskola},

place={Göteborg},

year={2015},

keywords={graph kernels, Voronoi, shortest paths},

note={64},

}

** RefWorks **

RT Generic

SR Electronic

ID 215958

A1 Kilhamn, Jonatan

T1 Fast shortest-path kernel computations using aproximate methods

YR 2015

AB The shortest-path kernel is frequently seen in the context of graph classification, which shows up in various subjects, for example bioinformatics. However, it is not
efficient enough to be applicable in practice if the graphs are too large. The purpose of this thesis is to explore the possibilities of computing the shortest-path kernel approximately, taking shorter time at the cost of a limited error.<br><br>
This thesis proves a theoretical error bound for a class of kernel function approximations, applicable to the shortest-path kernel but further generaliseable as well. We also present two specific approximations of the shortest-path kernel.<br><br>
Firstly, we define an approximate kernel based on the idea of sampling node pairs in a graph to approximate its shortest-path length distribution. Secondly, we define a kernel computing approximate shortest-path lengths in a graph using its graph Voronoi dual. We provide algorithms to compute both of these, and prove that their runtime complexities are better than the shortest-path kernel they approximate. Finally, we evaluate these kernel approximations empirically, comparing them to the full shortest-path kernel as well as other reference kernels.

PB Institutionen för data- och informationsteknik (Chalmers), Chalmers tekniska högskola,

LA eng

LK http://publications.lib.chalmers.se/records/fulltext/215958/215958.pdf

OL 30