Statistical and Machine Learning Approaches for Network Analysis

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 ...