Multi-scale Wasserstein Shortest-path Graph Kernels for Graph Classification

• URL: http://arxiv.org/abs/2206.00979v5
• Date: Mon, 13 May 2024 16:14:12 GMT
• Title: Multi-scale Wasserstein Shortest-path Graph Kernels for Graph Classification
• Authors: Wei Ye, Hao Tian, Qijun Chen,
• Abstract summary: 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.
• Score: 24.041871640927738
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Graph kernels are conventional methods for computing graph similarities. However, the existing R-convolution graph kernels cannot resolve both of the two challenges: 1) Comparing graphs at multiple different scales, and 2) Considering the distributions of substructures when computing the kernel matrix. These two challenges limit their performances. To mitigate both of the two challenges, we propose a novel graph kernel called the Multi-scale Wasserstein Shortest-Path graph kernel (MWSP), at the heart of which is the multi-scale shortest-path node feature map, of which each element denotes the number of occurrences of the shortest path around a node. The shortest path is represented by the concatenation of all the labels of nodes in it. Since the shortest-path node feature map can only compare graphs at local scales, we incorporate into it the multiple different scales of the graph structure, which are captured by the truncated BFS trees of different depths rooted at each node in a graph. We use the Wasserstein distance to compute the similarity between the multi-scale shortest-path node feature maps of two graphs, considering the distributions of shortest paths. We empirically validate MWSP on various benchmark graph datasets and demonstrate that it achieves state-of-the-art performance on most datasets.

Related papers

• InstructG2I: Synthesizing Images from Multimodal Attributed Graphs [50.852150521561676]
  We propose a graph context-conditioned diffusion model called InstructG2I. InstructG2I first exploits the graph structure and multimodal information to conduct informative neighbor sampling. A Graph-QFormer encoder adaptively encodes the graph nodes into an auxiliary set of graph prompts to guide the denoising process.
  arXiv  Detail & Related papers  (2024-10-09T17:56:15Z)
• Edge but not Least: Cross-View Graph Pooling [76.71497833616024]
  This paper presents a cross-view graph pooling (Co-Pooling) method to better exploit crucial graph structure information. Through cross-view interaction, edge-view pooling and node-view pooling seamlessly reinforce each other to learn more informative graph-level representations.
  arXiv  Detail & Related papers  (2021-09-24T08:01:23Z)
• GraphHop: An Enhanced Label Propagation Method for Node Classification [34.073791157290614]
  A scalable semi-supervised node classification method, called GraphHop, is proposed in this work. Experimental results show that GraphHop outperforms state-of-the-art graph learning methods on a wide range of tasks.
  arXiv  Detail & Related papers  (2021-01-07T02:10:20Z)
• LCS Graph Kernel Based on Wasserstein Distance in Longest Common Subsequence Metric Space [22.215852332444904]
  We propose a graph kernel to compute more comprehensive similarity between paths and walks. We also combine it with optimal transport theory to extract more in-depth features of graphs. Our proposed method outperforms many state-of-the-art graph kernel methods.
  arXiv  Detail & Related papers  (2020-12-07T11:59:14Z)
• Partial Gromov-Wasserstein Learning for Partial Graph Matching [28.47269200800775]
  A partial Gromov-Wasserstein learning framework is proposed for partially matching two graphs. Our framework can improve the F1 score by at least $20%$ and often much more.
  arXiv  Detail & Related papers  (2020-12-02T14:56:22Z)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  We consider the graph link prediction task, which is a classic graph analytical problem with many real-world applications. In this formalism, a link prediction problem is converted to a graph classification task. We propose to seek a radically different and novel path by making use of the line graphs in graph theory. In particular, each node in a line graph corresponds to a unique edge in the original graph. Therefore, link prediction problems in the original graph can be equivalently solved as a node classification problem in its corresponding line graph, instead of a graph classification task.
  arXiv  Detail & Related papers  (2020-10-20T05:54:31Z)
• Topology-Aware Graph Pooling Networks [51.9008939769679]
  Pooling operations are effective on computer vision and natural language processing tasks. One challenge of performing pooling operations on graph data is the lack of locality that is not well-defined on graphs. We propose the topology-aware pooling (TAP) layer that explicitly considers graph topology.
  arXiv  Detail & Related papers  (2020-10-19T20:14:30Z)
• 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)
• Wasserstein Embedding for Graph Learning [33.90471037116372]
  Wasserstein Embedding for Graph Learning (WEGL) is a framework for embedding entire graphs in a vector space. We leverage new insights on defining similarity between graphs as a function of the similarity between their node embedding distributions. We evaluate our new graph embedding approach on various benchmark graph-property prediction tasks.
  arXiv  Detail & Related papers  (2020-06-16T18:23:00Z)
• 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)

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.