Distance Metric Learning for Graph Structured Data

Abstract

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.

arXiv comment38 pages, 11 figures. This is a pre-print of an article published in Machine Learning Journal. The final authenticated version is available online at: https://doi.org/10.1007/s10994-021-06009-3

References in corpus (13)

• Crystal Graph Convolutional Neural Networks for an Accurate and Interpretable Prediction of Material Properties
• Pathwise coordinate optimization
• Convolutional Networks on Graphs for Learning Molecular Fingerprints
• Learning Convolutional Neural Networks for Graphs
• graph2vec: Learning Distributed Representations of Graphs
• Diffusion-Convolutional Neural Networks
• Subgraph Matching Kernels for Attributed Graphs
• Optimal Transport for structured data with application on graphs
• Safe Feature Elimination for the LASSO and Sparse Supervised Learning Problems
• The Multiscale Laplacian Graph Kernel
• RetGK: Graph Kernels based on Return Probabilities of Random Walks
• WHInter: A Working set algorithm for High-dimensional sparse second order Interaction models
• Safe Pattern Pruning: An Efficient Approach for Predictive Pattern Mining