Artikel in einem Konferenzbericht,
Matching Based Kernels for Labeled Graphs
ECML/PKDD Workshop on Mining and Learning with Graphs, (2006)
Zusammenfassung
For various classification problems it is most natural to represent training examples as labeled graphs. As a result several kernel functions over these complex structures have been proposed in the literature so far. Most of them exploit the Cross Product Kernel between two sets resulting from the decompositions of corresponding graphs into subgraphs of a specific type. The similarities between the substructures are often computed using the 0-1 Kronecker Delta Kernel. This approach has two main limitations: (i) in general most of the subgraphs will be poorly correlated with the actual target variable, adversely affecting the generalization of a classifier and (ii) as no graded similarities on subparts are computed, the expressivity of the resulting kernels is reduced. To tackle the above problems we propose here a class of graph kernels based on set distance measures whose computation is based on specific pairs of points from the corresponding graph decompositions. The actual matching of elements from the two sets depends on a graded similarity (standard Euclidean metric in our case) between the elements of the two sets. To make our similarity measure positive semidefinite we exploit the notion of the proximity space induced by a given set distance measure. To practically demonstrate the effectiveness of our approach we report promising experimental results for the task of activity prediction of drug molecules.
