Distance Metric Learning for Graph Structured Data

• URL: http://arxiv.org/abs/2002.00727v2
• Date: Thu, 17 Jun 2021 06:22:00 GMT
• Title: Distance Metric Learning for Graph Structured Data
• Authors: Tomoki Yoshida, Ichiro Takeuchi, Masayuki Karasuyama
• Abstract summary: 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. We empirically evaluate the computational efficiency and classification performance of IGML on several benchmark datasets.
• Score: 23.3700989820887
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Learning Attributed Graphlets: Predictive Graph Mining by Graphlets with Trainable Attribute [4.14034448023832]
  This paper proposes an interpretable classification algorithm for attributed graph data, called LAGRA (Learning Attributed GRAphlets) LAGRA learns importance weights for small attributed subgraphs, called attributed graphlets (AGs), while simultaneously optimizing their attribute vectors. We empirically demonstrate that LAGRA has superior or comparable prediction performance to the standard existing algorithms.
  arXiv  Detail & Related papers  (2024-02-10T12:10:13Z)
• Bures-Wasserstein Means of Graphs [60.42414991820453]
  We propose a novel framework for defining a graph mean via embeddings in the space of smooth graph signal distributions. By finding a mean in this embedding space, we can recover a mean graph that preserves structural information. We establish the existence and uniqueness of the novel graph mean, and provide an iterative algorithm for computing it.
  arXiv  Detail & Related papers  (2023-05-31T11:04:53Z)
• Localized Contrastive Learning on Graphs [110.54606263711385]
  We introduce a simple yet effective contrastive model named Localized Graph Contrastive Learning (Local-GCL) In spite of its simplicity, Local-GCL achieves quite competitive performance in self-supervised node representation learning tasks on graphs with various scales and properties.
  arXiv  Detail & Related papers  (2022-12-08T23:36:00Z)
• A simple way to learn metrics between attributed graphs [11.207372645301094]
  We propose a new Simple Graph Metric Learning - SGML - model with few trainable parameters. This model allows us to build an appropriate distance from a database of labeled (attributed) graphs to improve the performance of simple classification algorithms.
  arXiv  Detail & Related papers  (2022-09-26T14:32:38Z)
• A Comprehensive Analytical Survey on Unsupervised and Semi-Supervised Graph Representation Learning Methods [4.486285347896372]
  This survey aims to evaluate all major classes of graph embedding methods. We organized graph embedding techniques using a taxonomy that includes methods from manual feature engineering, matrix factorization, shallow neural networks, and deep graph convolutional networks. We designed experiments on top of PyTorch Geometric and DGL libraries and run experiments on different multicore CPU and GPU platforms.
  arXiv  Detail & Related papers  (2021-12-20T07:50:26Z)
• Effective and Efficient Graph Learning for Multi-view Clustering [173.8313827799077]
  We propose an effective and efficient graph learning model for multi-view clustering. Our method exploits the view-similar between graphs of different views by the minimization of tensor Schatten p-norm. Our proposed algorithm is time-economical and obtains the stable results and scales well with the data size.
  arXiv  Detail & Related papers  (2021-08-15T13:14:28Z)
• Structure-Enhanced Meta-Learning For Few-Shot Graph Classification [53.54066611743269]
  This work explores the potential of metric-based meta-learning for solving few-shot graph classification. An implementation upon GIN, named SMFGIN, is tested on two datasets, Chembl and TRIANGLES.
  arXiv  Detail & Related papers  (2021-03-05T09:03:03Z)
• Graph topology inference benchmarks for machine learning [16.857405938139525]
  We introduce several benchmarks specifically designed to reveal the relative merits and limitations of graph inference methods. We also contrast some of the most prominent techniques in the literature.
  arXiv  Detail & Related papers  (2020-07-16T09:40:32Z)
• Unsupervised Graph Embedding via Adaptive Graph Learning [85.28555417981063]
  Graph autoencoders (GAEs) are powerful tools in representation learning for graph embedding. In this paper, two novel unsupervised graph embedding methods, unsupervised graph embedding via adaptive graph learning (BAGE) and unsupervised graph embedding via variational adaptive graph learning (VBAGE) are proposed. Experimental studies on several datasets validate our design and demonstrate that our methods outperform baselines by a wide margin in node clustering, node classification, and graph visualization tasks.
  arXiv  Detail & Related papers  (2020-03-10T02:33:14Z)
• Data-Driven Factor Graphs for Deep Symbol Detection [107.63351413549992]
  We propose to implement factor graph methods in a data-driven manner. In particular, we propose to use machine learning (ML) tools to learn the factor graph. We demonstrate that the proposed system, referred to as BCJRNet, learns to implement the BCJR algorithm from a small training set.
  arXiv  Detail & Related papers  (2020-01-31T09:23:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.