Mapping Distance Graph Kernels using Bipartite Matching

Tetsuya Kataoka, Eimi Shiotsuki, Akihiro Inokuchi

2017

Abstract

The objective of graph classification is to classify graphs of similar 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 instead of feature vectors. In this paper, we propose two novel and efficient graph kernels called Mapping Distance Kernel with Stars (MDKS) and Mapping Distance Kernel with Vectors (MDKV). MDKS approximately measures the graph edit distance using star structures of height one. The method runs in $O(\upsilon^3)$, where $\upsilon$ is the maximum number of vertices in the graphs. However, when the height of the star structures is increased to avoid structural 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(\upsilon^3 +|\Sigma|\upsilon^2))$, where $\Sigma$ is a set of vertex labels and graphs are iteratively relabeled $h$ times. We verify the computational efficiency of the proposed graph kernels on artificially generated datasets. Further, results on three real-world datasets show that the classification accuracy of the proposed graph kernels is higher than three conventional graph kernel methods.

Paper Citation

in Harvard Style

Kataoka T., Shiotsuki E. and Inokuchi A. (2017). Mapping Distance Graph Kernels using Bipartite Matching . In Proceedings of the 6th International Conference on Pattern Recognition Applications and Methods - Volume 1: ICPRAM, ISBN 978-989-758-222-6, pages 61-70. DOI: 10.5220/0006112900610070

in Bibtex Style

@conference{icpram17,
author={Tetsuya Kataoka and Eimi Shiotsuki and Akihiro Inokuchi},
title={Mapping Distance Graph Kernels using Bipartite Matching},
booktitle={Proceedings of the 6th International Conference on Pattern Recognition Applications and Methods - Volume 1: ICPRAM,},
year={2017},
pages={61-70},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0006112900610070},
isbn={978-989-758-222-6},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 6th International Conference on Pattern Recognition Applications and Methods - Volume 1: ICPRAM,
TI - Mapping Distance Graph Kernels using Bipartite Matching
SN - 978-989-758-222-6
AU - Kataoka T.
AU - Shiotsuki E.
AU - Inokuchi A.
PY - 2017
SP - 61
EP - 70
DO - 10.5220/0006112900610070