Statistical and Machine Learning Approaches for Network Analysis

8.8 Optimal Assignment Kernels

Optimal assignment kernels were proposed in the context of cheminformatics⁵ [34]. Their idea is to optimally assign vertices between graphs based on pairwise vertex similarities. Variants of these kernels differ in the type of pairwise vertex similarity used.

8.8.1 Definition

Let G = (V, E) and G ' = (V ', E ') be two graphs, and assume without loss of generality that |V| ≤ |V ' |. Based upon a measure k_G,G' of similarity⁶ between the vertices of G and G ', the optimal assignment kernel injectively assigns the vertices of V to vertices of V ' such that the total similarity between the assigned vertices is maximized (Fig. 8.5):

(8.23)

The maximum is over all possible assignments π of the vertices in V to vertices in V ', that is, all prefixes of length |V| of permutations of size |V ' |. To prevent the value of the kernel depending on the size |V| of the smaller graph, one uses the normalized optimal assignment kernel

(8.24)

Whether or not k _oa is positive definite depends on the underlying vertex similarity k_G,G'[38].

Figure 8.5 The ISOAK optimal assignment kernel [37] between the molecular structure graphs of glycine (a) and serine (b). Vertex assignments are shown boxed. Note how pairwise vertex similarities are highest in the identical parts of ...