Graph Classification with Mapping Distance Graph Kernels
| Autor: | Tetsuya Kataoka, Eimi Shiotsuki, Akihiro Inokuchi |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Graph kernel
Theoretical computer science Computer science Small number 0102 computer and information sciences 02 engineering and technology 01 natural sciences Graph Vertex (geometry) Knowledge extraction 010201 computation theory & mathematics Graph classification 0202 electrical engineering electronic engineering information engineering Graph edit distance 020201 artificial intelligence & image processing Assignment problem MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | Lecture Notes in Computer Science ISBN: 9783319936468 ICPRAM (Revised Selected Papers) |
| DOI: | 10.1007/978-3-319-93647-5_2 |
| Popis: | Graph mining is of great interest because knowledge discovery from structured data can be applied to real-world datasets. Recent improvements in system throughput have led to the need for the analysis of a large number of graphs using methods such as graph classification, the objective of which is to classify graphs of similar structures into the same class. Existing methods for representing graphs can result in difficulties such as the loss of structural information, which can be overcome using specifically designed graph kernels. In this paper, we propose two novel graph kernels, mapping distance kernel with stars (MDKS) and mapping distance kernel with vectors (MDKV), to classify labeled graphs more accurately than existing methods. The MDKS is based on the graph edit distance using star structures, and the MDKV is based on the graph edit distance using the linear sum assignment problem and graph relabeling. Because MDKS uses only small local structures that consist of adjacent vertices of each vertex in graphs, it is not substantially superior to conventional graph kernels. However, the MDKV uses local structures that consist of vertices that are reachable within a small number of steps from each vertex in graphs and, unlike existing methods, do not require isomorphism matching. In addition, we investigate a framework for computing the approximate graph edit distance between two graphs using the linear sum assignment problem (LSAP), because the proposed graph kernels are related to methods for computing the graph edit distance using LSAP. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|