  Graphs are versatile tools for representing structured data. As a result, a
variety of machine learning methods have been studied for graph data analysis.
Although many such learning methods depend on the measurement of differences
between input graphs, defining an appropriate distance metric for graphs
remains a controversial issue. Hence, we propose a supervised distance metric
learning method for the graph classification problem. Our method, named
interpretable graph metric learning (IGML), learns discriminative metrics in a
subgraph-based feature space, which has a strong graph representation
capability. By introducing a sparsity-inducing penalty on the weight of each
subgraph, IGML can identify a small number of important subgraphs that can
provide insight into the given classification task. Because our formulation has
a large number of optimization variables, an efficient algorithm that uses
pruning techniques based on safe screening and working set selection methods is
also proposed. An important property of IGML is that solution optimality is
guaranteed because the problem is formulated as a convex problem and our
pruning strategies only discard unnecessary subgraphs. Furthermore, we show
that IGML is also applicable to other structured data such as itemset and
sequence data, and that it can incorporate vertex-label similarity by using a
transportation-based subgraph feature. We empirically evaluate the
computational efficiency and classification performance of IGML on several
benchmark datasets and provide some illustrative examples of how IGML
identifies important subgraphs from a given graph dataset.
