Learning Interpretable Metric between Graphs: Convex Formulation and Computation with Graph Mining
Lists
Only you see this
Abstract
Graph is a standard approach to modeling structured data. Although many machine learning methods depend on the metric of the input objects, defining an appropriate distance function on graph is still a controversial issue. We propose a novel supervised metric learning method for a subgraph-based distance, called interpretable graph metric learning (IGML). IGML optimizes the distance function in such a way that a small number of important subgraphs can be adaptively selected. This optimization is computationally intractable with naive application of existing optimization algorithms. We construct a graph mining based efficient algorithm to deal with this computational difficulty. Important advantages of our method are 1) guarantee of the optimality from the convex formulation, and 2) high interpretability of results. To our knowledge, none of the existing studies provide an interpretable subgraph-based metric in a supervised manner. In our experiments, we empirically verify superior or comparable prediction performance of IGML to other existing graph classification methods which do not have clear interpretability. Further, we demonstrate usefulness of IGML through some illustrative examples of extracted subgraphs and an example of data analysis on the learned metric space.
BibTeX
@inproceedings{yoshida2019learning,
author = {Tomoki Yoshida and Ichiro Takeuchi and Masayuki Karasuyama},
title = {{Learning Interpretable Metric between Graphs: Convex Formulation and Computation with Graph Mining}},
booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
year = {2019},
doi = {10.1145/3292500.3330845},
}Loading related content...