The objective of graph classification is to classify graphs o f imilar structures into the same class. This problem is of key importance in areas such as cheminformatics and bioinformatics. Support Vector Machines can efficiently classify graphs if graph kernels are used instea d of feature vectors. In this paper, we propose two novel and efficient graph kernels called Mapping Distance Ke rnel with Stars (MDKS) and Mapping Distance Kernel with Vectors (MDKV). MDKS approximately measures th e graph edit distance using star structures of height one. The method runs in O(υ3), whereυ is the maximum number of vertices in the graphs. However, when the height of the star structures is increased to avoid s tructural information loss, this graph kernel is no longer efficient. Hence, MDKV represents star structures of height greater than one as vectors and sums their Euclidean distances. It runs in O(h(υ3 + |Σ|υ2)), whereΣ is a set of vertex labels and graphs are iteratively relabeledh times. We verify the computational efficiency of the propose d graph kernels on artificially generated datasets. Further, results on three real-world datase ts show that the classification accuracy of the proposed graph kernels is higher than three conventional graph kerne l methods.
Paper
Full text
Mapping Distance Graph Kernels using Bipartite Matching
Semantic Scholar · Chemistry · 2017
Abstract
The objective of graph classification is to classify graphs o f imilar structures into the same class. This problem is of key importance in areas such as cheminformatics and bioinformatics. Support Vector Machines can efficiently classify graphs if graph kernels are used instea d of feature vectors. In this paper, we propose two novel and efficient graph kernels called Mapping Distance Ke rnel with Stars (MDKS) and Mapping Distance Kernel with Vectors (MDKV). MDKS approximately measures th e graph edit distance using star structures of height one. The method runs in O(υ3), whereυ is the maximum number of vertices in the graphs. However, when the height of the star structures is increased to avoid s tructural information loss, this graph kernel is no longer efficient. Hence, MDKV represents star structures of height greater than one as vectors and sums their Euclidean distances. It runs in O(h(υ3 + |Σ|υ2)), whereΣ is a set of vertex labels and graphs are iteratively relabeledh times. We verify the computational efficiency of the propose d graph kernels on artificially generated datasets. Further, results on three real-world datase ts show that the classification accuracy of the proposed graph kernels is higher than three conventional graph kerne l methods.