Graph Partitioning and Graph Neural Network based Hierarchical Graph Matching for Graph Similarity Computation

• URL: http://arxiv.org/abs/2005.08008v3
• Date: Tue, 5 Jan 2021 00:19:12 GMT
• Title: Graph Partitioning and Graph Neural Network based Hierarchical Graph Matching for Graph Similarity Computation
• Authors: Haoyan Xu, Ziheng Duan, Jie Feng, Runjian Chen, Qianru Zhang, Zhongbin Xu, Yueyang Wang
• Abstract summary: Graph similarity aims to predict a similarity score between one pair of graphs to facilitate downstream applications. We propose a graph partitioning and graph neural network-based model, called PSimGNN, to effectively resolve this issue. PSimGNN outperforms state-of-the-art methods in graph similarity computation tasks using approximate Graph Edit Distance (GED) as the graph similarity metric.
• Score: 5.710312846460821
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph similarity computation aims to predict a similarity score between one pair of graphs to facilitate downstream applications, such as finding the most similar chemical compounds similar to a query compound or Fewshot 3D Action Recognition. Recently, some graph similarity computation models based on neural networks have been proposed, which are either based on graph-level interaction or node-level comparison. However, when the number of nodes in the graph increases, it will inevitably bring about reduced representation ability or high computation cost. Motivated by this observation, we propose a graph partitioning and graph neural network-based model, called PSimGNN, to effectively resolve this issue. Specifically, each of the input graphs is partitioned into a set of subgraphs to extract the local structural features directly. Next, a novel graph neural network with an attention mechanism is designed to map each subgraph into an embedding vector. Some of these subgraph pairs are automatically selected for node-level comparison to supplement the subgraph-level embedding with fine-grained information. Finally, coarse-grained interaction information among subgraphs and fine-grained comparison information among nodes in different subgraphs are integrated to predict the final similarity score. Experimental results on graph datasets with different graph sizes demonstrate that PSimGNN outperforms state-of-the-art methods in graph similarity computation tasks using approximate Graph Edit Distance (GED) as the graph similarity metric.

Related papers

• 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)
• Graph Condensation via Receptive Field Distribution Matching [61.71711656856704]
  This paper focuses on creating a small graph to represent the original graph, so that GNNs trained on the size-reduced graph can make accurate predictions. We view the original graph as a distribution of receptive fields and aim to synthesize a small graph whose receptive fields share a similar distribution.
  arXiv  Detail & Related papers  (2022-06-28T02:10:05Z)
• CGMN: A Contrastive Graph Matching Network for Self-Supervised Graph Similarity Learning [65.1042892570989]
  We propose a contrastive graph matching network (CGMN) for self-supervised graph similarity learning. We employ two strategies, namely cross-view interaction and cross-graph interaction, for effective node representation learning. We transform node representations into graph-level representations via pooling operations for graph similarity computation.
  arXiv  Detail & Related papers  (2022-05-30T13:20:26Z)
• 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)
• Multilevel Graph Matching Networks for Deep Graph Similarity Learning [79.3213351477689]
  We propose a multi-level graph matching network (MGMN) framework for computing the graph similarity between any pair of graph-structured objects. To compensate for the lack of standard benchmark datasets, we have created and collected a set of datasets for both the graph-graph classification and graph-graph regression tasks. Comprehensive experiments demonstrate that MGMN consistently outperforms state-of-the-art baseline models on both the graph-graph classification and graph-graph regression tasks.
  arXiv  Detail & Related papers  (2020-07-08T19:48:19Z)
• 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)
• CoSimGNN: Towards Large-scale Graph Similarity Computation [5.17905821006887]
  Graph Neural Networks (GNNs) provide a data-driven solution for this task. Existing GNN-based methods, which either respectively embeds two graphs or deploy cross-graph interactions for whole graph pairs, are still not able to achieve competitive results. We propose the "embedding-coarsening-matching" framework CoSimGNN, which first embeds and coarsens large graphs with adaptive pooling operation and then deploys fine-grained interactions on the coarsened graphs for final similarity scores.
  arXiv  Detail & Related papers  (2020-05-14T16:33:13Z)

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.