8.2 Convolution Kernels

Many kernels for structured data, including, but not limited to graphs, are based on the idea of convolution kernels introduced by Haussler in 1999 [62].³

8.2.1 Definition

Assume that a sample can be decomposed into parts , for example, a decomposition of a graph into subgraphs. Here, are nonempty, separable metric spaces. The relation R indicates possible decompositions, where R(x, x₁, . . ., x_d) is true if and only if x can be decomposed into x₁, . . ., x_d. Given positive definite kernels , 1 ≤ i ≤ d, the convolution kernel

(8.4)

is positive definite for finite R[62]. The sum runs over all decompositions of x and x ' into d parts for which R is true; if a sample cannot be decomposed, the sum is zero. Random walk kernels, path-based kernels, tree kernels, and cyclic pattern kernels are convolution kernels.

8.2.2 Variants and Extensions

Vishwanathan et al. [64] point out that “there have been a few attempts to extend R-convolution kernels to abstract semirings.” A semiring (S, ⊕, ⊗, 0, 1) is an algebraic structure that consists of a set S, a commutative associative addition ⊕ with identity element 0, and an associative multiplication ⊗ with identity element 1, where multiplication distributes over addition, and 0 ⊗ a = a ⊗ 0 = 0 for all a S. In a semiring, Equation 8.4 becomes

(8.5)

See Section 8.8.3 for an example.