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