Holger Fröhlich, Jörg K. Wegner, Florian Sieker and Andreas Zell

**
**

*
Optimal Assignment Kernels For Attributed Molecular Graphs
*

### Abstract

We propose a new kernel function for attributed molecular graphs,
which is based on the idea of computing an optimal assignment from
the atoms of one molecule to those of another one, including information
on neighborhood, membership to a certain structural element and other
characteristics for each atom. As a byproduct this leads to a new
class of kernel functions. We demonstrate how the necessary computations
can be carried out efficiently. Compared to marginalized graph kernels
our method in some cases leads to a significant reduction of the
prediction error. Further improvement can be gained, if expert
knowledge is combined with our method. We also investigate a reduced
graph representation of molecules by collapsing certain structural
elements, like e.g. rings, into a single node of the molecular graph.

**Download**

[pdf]

**BibTeX**

@conference{Froe05OAKernels,
AUTHOR="H. Fröhlich and J. Wegner F. Sieker and A. Zell",
TITLE="{Optimal Assignment Kernels For Attributed Molecular Graphs}",
BOOKTITLE="Proc. Int. Conf. on Machine Learning",
PAGES="225 - 232",
YEAR=2005
}

### Erratum

Theorem 2.3 in the paper contains an error: It is NOT true that each n by n kernel
matrix with the optimal assignment kernel is positive definite (the induction in theorem 2.3 is wrong).
One can, however, fix the problem by substracting from the diagonal of the original kernel matrix the
smallest negative eigenvalue, if it exists (and 0 otherwise).