Chapter13: Graph Neural Networks: Graph Matching

Xiang Ling, Zhejiang University, lingxiang@zju.edu.cn
Lingfei Wu, JD.COM Silicon Valley Research Center, lwu@email.wm.edu
Chunming Wu, Zhejiang University, wuchunming@zju.edu.cn
Shouling Ji, Zhejiang University, sji@zju.edu.cn

Abstract

The problem of graph matching that tries to establish some kind of structural correspondence between a pair of graph-structured objects is one of the key challenges in a variety of real-world applications. In general, the graph matching problem can be classified into two categories: i) the classic graph matching problem which finds an optimal node-to-node correspondence between nodes of a pair of input graphs and ii) the graph similarity problem which computes a similarity metric between two graphs. While recent years have witnessed the great success of GNNs in learning node representations of graphs, there is an increasing interest in exploring GNNs for the graph matching problem in an end-to-end manner. This chapter focuses on the state of the art of graph matching models based on GNNs. We start by introducing some backgrounds of the graph matching problem. Then, for each category of graph matching problem, we provide a formal definition and discuss state-of-the-art GNN-based models for both the classic graph matching problem and the graph similarity problem, respectively. Finally, this chapter is concluded by pointing out some possible future research directions.

Contents

  • Introduction
  • Graph Matching Learning
    • Problem Definition
    • Deep Learning based Models
    • Graph Neural Networks based Models
  • Graph Similarity Learning
    • Problem Definition
    • Graph-Graph Regression Tasks
    • Graph-Graph Classification Tasks
  • Summary

Citation

@incollection{GNNBook-ch13-ling,
author = "Ling, Xiang and Wu, Lingfei and Wu, Chunming and Ji, Shouling",
editor = "Wu, Lingfei and Cui, Peng and Pei, Jian and Zhao, Liang",
title = "Graph Neural Networks: Graph Matching",
booktitle = "Graph Neural Networks: Foundations, Frontiers, and Applications",
year = "2022",
publisher = "Springer Singapore",
address = "Singapore",
pages = "277--295",
}

X. Ling, L. Wu, C. Wu, and S. Ji, “Graph neural networks: Graph matching,” in Graph Neural Networks: Foundations, Frontiers, and Applications, L. Wu, P. Cui, J. Pei, and L. Zhao, Eds. Singapore: Springer Singapore, 2022, pp. 277–295.