Acknowledgments

The author acknowledges partial support from European Union FP7-ICT programme (PASCAL2), Deutsche Forschungsgemeinschaft (DFG grant MU 987/4-2), and Institute for Pure and Applied Mathematics (IPAM, UCLA, long program on “navigating chemical compound space for materials and bio design”).

Notes

1. This is possible because the inner product encodes geometrical information about the distance and angle between two vectors.

2. Note that for many specialized graph classes, graph isomorphism is in P [59,60]. Also, for a suitable distribution on graphs, graph isomorphism is efficiently solvable in expected polynomial time [61].

3. Structured data kernels also relate to work by Watkins on dynamic alignment kernels [63], also in 1999, although his work is not as directly related to graph kernels.

4. This problem is related to another open problem, the graph reconstruction problem, which asks whether a graph can be reconstructed from the multiset of all of its subgraphs obtained by deleting one vertex. For graphs up to size |V| = 11, this has been verified [77], and it has been shown that almost every (random) graph can be reconstructed from three such subgraphs [78]. Note, however, that normally k < |V|.

5. The idea of “aligning” two graphs has been rediscovered in various contexts, for example, in cheminformatics [80], bioinformatics [81], and applied mathematics [82].

6. Note that we allow to depend on G and G ′.

7. Note that the ISOAK graph kernel has been shown empirically to be positive definite on many data sets of molecular structure graphs for α → 1 [37,41].