Statistical and Machine Learning Approaches for Network Analysis

11.8 Graph Kernel Extensions

The kernel as described so far disregards the position of hyponym and hypernym candidates in the product graph. However, nodes directly connected to hyponym and hypernym candidates or nodes that are located nearby a direct path from the hyponym to the hypernym candidate are usually more important for validating a hyponymy hypothesis. Nodes far away from both nodes could belong to an embedded subclause or a second main clause that is not semantically related to the hyponym and hypernym candidates. Therefore, instead of considering all common walks, two special graph kernels are used, which are extensions of the original approach of Gärtner et al. The first graph kernel counts weighted common walks that pass both hyponym and hypernym candidates. The second graph kernel counts the weighted common walks that pass at least one of the hyponym and hypernym candidates. Both kernels cannot be directly calculated by this approach but obtained by subtracting different numbers of common walks from each other. The weighted number of common walks that pass at least one of the hyponym or hypernym candidate can be obtained by subtracting the number of common walks that pass neither hyponym and hypernym candidate from the number of all common walks.

(11.7)

The weighted number of common walks that do not pass neither a1 nor a2 is fairly easy to determine. It can be done ...