Statistical and Machine Learning Approaches for Network Analysis

11.7 Graph Kernel

A graph kernel is a kernel function that compares different graphs. We use such a graph kernel to compare two hyponymy hypotheses with each other. In particular, we compare by means of a graph kernel the SNs with each other from which the hypotheses were extracted from. There exist a lot of different types of graph kernels. The graph kernel of Borgwardt and Kriegel [27] compares the shortest paths in both graphs. These paths are determined for each graph separately. Two comparison functions were tested to compare the graph lengths: the product of the lengths and the function that takes the value of one if both lengths are identical and zero otherwise. The graph kernel value is then given by the sum of all such comparison function values iterating over all possible pairs of nodes in the two graphs. Kashima et al. [28] generate randomly common walks on the two graphs and count the number of walks that both graphs have in common. Another approach of Kashima, which he devised together with Hido, is to compare special kind of hash values computed for each graph [29].

Our work is based on the graph kernel as proposed by Gärtner et al. Like the approach of Kashima et al., the idea of this graph kernel is that graphs are similar if they share a lot of walks. Let us review some graph definitions before further explanations. A directed nonuniquely labeled graph is given by a set of nodes and arcs: G = (V, E). Each node and arc is assigned a label: label: G ∪ E → A^* where ...