Graph Matching Networks for Learning the Similarity of Graph Structured Objects

By Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, Pushmeet Kohli. 2019

685 citations recorded by the source corpus.

This paper addresses the challenging problem of retrieval and matching of graph structured objects, and makes two key contributions. First, we demonstrate how Graph Neural Networks (GNN), which have emerged as an effective model for various supervised prediction problems defined on structured data, can be trained to produce embedding of graphs in vector spaces that enables efficient similarity reasoning. Second, we propose a novel Graph Matching Network model that, given a pair of graphs as input, computes a similarity score between them by jointly reasoning on the pair through a new cross-graph attention-based matching mechanism. We demonstrate the effectiveness of our models on different domains including the challenging problem of control-flow-graph based function similarity search that plays an important role in the detection of vulnerabilities in software systems. The experimental analysis demonstrates that our models are not only able to exploit structure in the context of similarity learning but they can also outperform domain-specific baseline systems that have been carefully hand-engineered for these problems.

Subfields: Artificial Intelligence, Materials Chemistry

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Materials Chemistry

Citations in the corpus

EquiBind: Geometric Deep Learning for Drug Binding Structure Prediction (2022, methodology): “Inspired by Ganea et al. (2021a), we exploit graph matching networks (GMN) (Li et al., 2019) and E(3)-equivariant graph neural networks (E(3)-GNN) (Satorras et al., 2021) to perform a direct prediction of the ligand-receptor complex structure without relying on heavy sampling as prior work, thus ach”
Combinatorial optimization and reasoning with graph neural networks (2021, methodology): “Speciﬁcally, Li et al. [2019] use a GNN architecture that learns node embeddings for each node in the two graphs and an attention score that reﬂects the similarity between two nodes across the two graphs.”
Knowledge Graph Alignment Network with Gated Multi-hop Neighborhood Aggregation (2019, methodology): “We also notice the recent work (Li et al. 2019) that uses GNNs for comparing the similarity of two graphs.”
Detecting Code Clones with Graph Neural Network and Flow-Augmented Abstract Syntax Tree (2020, methodology): “2) Graph Matching Networks: Graph Matching Networks (GMN) framework defined by [8] can jointly learn embeddings for a pair of graphs.”
Graph Optimal Transport for Cross-Domain Alignment (2020, methodology): “Considering VQA as an example, in order to understand the contexts in the image and the question, a model needs to interpret the latent alignment between regions in the input image and words in the question.”
Graph Representation Learning (2020, methodology): “Or, we might want to build a classification model to detect whether a computer program is malicious by analyzing a graph-based representation of its syntax and data flow [Li et al., 2019].”
Rethinking the Item Order in Session-based Recommendation with Graph Neural Networks (2019, background): “Additionally, the graph level feature representation learning is essential for graph level tasks, for example, graph classification and graph isomorphism [17, 39].”
Lifelong Person Re-Identification via Adaptive Knowledge Accumulation (2021, background): “Such design is distinct different from the graph matching network [20] that shares same weights of two graphs like a Siamese network.”
Independent SE(3)-Equivariant Models for End-to-End Rigid Protein Docking (2021, background): “IEGMNs satisfy the pairwise independent SE(3)-equivariance property in Eq.”
A large-scale benchmark for few-shot program induction and synthesis (2021, background): “G RES facilitates the evaluation of Graph Neural Networks (Scarselli et al., 2009; Bronstein et al., 2017; Battaglia et al., 2018) for code analysis at scale, an approach that has already shown promise (Li et al., 2019).”
Contrastive Multi-View Representation Learning on Graphs (2020, methodology): “To address this, unsupervised approaches such as reconstruction based methods (Kipf & Welling, 2016) and contrastive methods (Li et al., 2019) are coupled with GNNs to allow them learn representations without relying on supervisory data.”