Transport based Graph Kernels

• URL: http://arxiv.org/abs/2011.00745v1
• Date: Mon, 2 Nov 2020 04:44:27 GMT
• Title: Transport based Graph Kernels
• Authors: Kai Ma, Peng Wan, Daoqiang Zhang
• Abstract summary: Graph kernel is a powerful tool measuring the similarity between graphs. Most of the existing graph kernels focused on node labels or attributes and ignored graph hierarchical structure information. We propose pyramid graph kernel based on optimal transport (OT) We evaluate the proposed graph kernels on several benchmark classification tasks and compare their performance with the existing state-of-the-art graph kernels.
• Score: 30.541423115387097
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph kernel is a powerful tool measuring the similarity between graphs. Most of the existing graph kernels focused on node labels or attributes and ignored graph hierarchical structure information. In order to effectively utilize graph hierarchical structure information, we propose pyramid graph kernel based on optimal transport (OT). Each graph is embedded into hierarchical structures of the pyramid. Then, the OT distance is utilized to measure the similarity between graphs in hierarchical structures. We also utilize the OT distance to measure the similarity between subgraphs and propose subgraph kernel based on OT. The positive semidefinite (p.s.d) of graph kernels based on optimal transport distance is not necessarily possible. We further propose regularized graph kernel based on OT where we add the kernel regularization to the original optimal transport distance to obtain p.s.d kernel matrix. We evaluate the proposed graph kernels on several benchmark classification tasks and compare their performance with the existing state-of-the-art graph kernels. In most cases, our proposed graph kernel algorithms outperform the competing methods.

Related papers

• Graph Parsing Networks [64.5041886737007]
  We propose an efficient graph parsing algorithm to infer the pooling structure, which then drives graph pooling. The resulting Graph Parsing Network (GPN) adaptively learns personalized pooling structure for each individual graph.
  arXiv  Detail & Related papers  (2024-02-22T09:08:36Z)
• Graph Mixup with Soft Alignments [49.61520432554505]
  We study graph data augmentation by mixup, which has been used successfully on images. We propose S-Mixup, a simple yet effective mixup method for graph classification by soft alignments.
  arXiv  Detail & Related papers  (2023-06-11T22:04:28Z)
• Multi-scale Wasserstein Shortest-path Graph Kernels for Graph Classification [24.041871640927738]
  We propose a novel graph kernel called the Multi-scale Wasserstein Shortest-Path graph kernel (MWSP) We show that MWSP achieves state-of-the-art performance on most datasets.
  arXiv  Detail & Related papers  (2022-06-02T10:50:46Z)
• Graph Kernel Neural Networks [53.91024360329517]
  We propose to use graph kernels, i.e. kernel functions that compute an inner product on graphs, to extend the standard convolution operator to the graph domain. This allows us to define an entirely structural model that does not require computing the embedding of the input graph. Our architecture allows to plug-in any type of graph kernels and has the added benefit of providing some interpretability.
  arXiv  Detail & Related papers  (2021-12-14T14:48:08Z)
• Graph Filtration Kernels [3.325932244741268]
  We propose a family of graph kernels that incorporate existence intervals of features. We show that using Weisfeiler-Lehman labels over certain filtrations strictly increases the expressive power over the ordinary Weisfeiler-Lehman procedure.
  arXiv  Detail & Related papers  (2021-10-22T15:51:10Z)
• Neighborhood Preserving Kernels for Attributed Graphs [0.9176056742068812]
  We describe the design of a reproducing kernel suitable for attributed graphs. The similarity between the two graphs is defined based on the neighborhood information of the graph nodes. By incorporating the proposed kernel on support vector machines we analyzed the real-world data sets.
  arXiv  Detail & Related papers  (2020-10-13T09:58:50Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  We propose a novel graph pooling strategy that leverages node proximity to improve the hierarchical representation learning of graph data with their multi-hop topology. Results show that the proposed graph pooling strategy is able to achieve state-of-the-art performance on a collection of public graph classification benchmark datasets.
  arXiv  Detail & Related papers  (2020-06-19T13:09:44Z)
• Graph Neural Networks with Composite Kernels [60.81504431653264]
  We re-interpret node aggregation from the perspective of kernel weighting. We present a framework to consider feature similarity in an aggregation scheme. We propose feature aggregation as the composition of the original neighbor-based kernel and a learnable kernel to encode feature similarities in a feature space.
  arXiv  Detail & Related papers  (2020-05-16T04:44:29Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  We cast a new formulation for the one-to-many graph alignment problem, which aims at matching a node in the smaller graph with one or more nodes in the larger graph. We show that our method leads to significant improvements with respect to the state-of-the-art algorithms for each of these tasks.
  arXiv  Detail & Related papers  (2020-03-12T22:31:59Z)
• Tree++: Truncated Tree Based Graph Kernels [5.819012768798548]
  Graph kernels are often used to decompose graphs into substructures and compare these substructures. To tackle this problem, we propose a new graph kernel called Tree++ in this paper. Tree++ achieves the best classification accuracy compared with previous graph kernels.
  arXiv  Detail & Related papers  (2020-02-23T07:07:10Z)
• A Hierarchical Transitive-Aligned Graph Kernel for Un-attributed Graphs [11.51839867040302]
  We develop a new graph kernel, namely the Hierarchical Transitive-Aligned kernel, by transitively aligning the vertices between graphs. The proposed kernel can outperform state-of-the-art graph kernels on standard graph-based datasets in terms of the classification accuracy.
  arXiv  Detail & Related papers  (2020-02-08T11:46:25Z)

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.