8.9 Other Graph Kernels

Several other approaches to graph kernels have been proposed.

Neighborhood hash kernels [57] use binary representations of discrete vertex labels. In consecutive rounds, the labels of the neighbors of each vertex and the vertex itself are combined using hash functions based on the exclusive-or and left-shift operations. This has the effect of propagating information about neighborhood structure throughout the graph. The hashed labels generated in each round are used to calculate a kernel function based on the Jaccard–Tanimoto coefficient. The procedure takes time in , where D is the bit length of the used binary representations, R is the number of rounds, and is the average vertex degree, making it an essentially linear algorithm applicable to graphs with several thousand vertices.

The edit distanced(G, G ') [87,88] is the minimum number of vertex and edge insertions, deletions, and substitutions required to transform G into G ' or vice versa. It requires computation time exponential in the number of vertices, but can be efficiently approximated [89]. The kernel

(8.25)

where G₀ is fixed and takes the role of origin, is positive definite if −d² is conditionally positive definite [14]. An advantage of edit distances is their robustness against noise in the input graphs.

Complement graph kernels are random walk kernels k that use both the graph G = (V, E) itself and its complement graph [49]. Through this, they also take the absence of an edge in both graphs into account. This is relevant, for example, for the comparison of protein–protein interaction networks.

Other kernels include fingerprint kernels [42,43] which extract fingerprints from graphs, for example, based on common walks of length up to d, matching-based kernels [46] which decompose graphs into walks of fixed length, compared using set distances and the proximity space representation, convolution kernels augmented by the context of a substructure [45], and kernels based on spatial alignments, vertex matching, and the Jaccard index [90]. The latter are not positive definite.