Optimal Assignment Kernel

The Optimal Assignment Kernel can be regarded as a special similarity measure for molecular graphs. The intuition is that two molecules are more similar the more certain substructural elements, e.g. rings, donors, acceptors, etc., and the way they are connected in both graphs fit together. On an atomic level this leads to the idea that, given we have some kernel function k that compares two atoms with regard to their chemical properties and their neighborhood, we are looking for the maximum weighted bipartite matching of the two molecular graphs. It can be shown, that the resulting Optimal Assignment Kernel is indeed a positive definite and symmetric Mercer kernel and can thus be used in combination with any kernel based learning algorithm.

Matching regions of two molecular graphs.
Possible assignments of atoms from molecule 2 to those of molecule 1. The goal is to find the optimal assignment of all atoms from molecule 2 to those of molecule 1, which maximizes the overall similarity score, i.e. the sum of edge weights in the bipartite graph, where each edge can be used at most once.
Two molecules and the optimal assignment computed by our method.
Experimental evaluations of our approach show a significant improvement compared to classical descriptor based models while at the same time the computational burden is very low. The idea of Optimal Assignment Kernels is fairly general and can be also used in very different domains, like kernel based clustering of genes according to their function.



  • H. Fröhlich, J. Wegner, F. Sieker, A. Zell, Optimal Assignment Kernels for Attributed Molecular Graphs, Proc. Int. Conf. Machine Learning, 2005.
  • H. Fröhlich, J. Wegner, F. Sieker, A. Zell, Kernel Functions for Attributed Molecular Graphs - A New Similarity Based Approach to ADME Prediction in Classification and Regression, QSAR & Comb. Sci., 2005.


Lars Rosenbaum, Tel.: (07071) 29-77174, lars.rosenbaum at uni-tuebingen.de