.png){kind=icon}
.png){kind=icon}
Return
Graph node matching for edit distance
.png){kind=icon}
PRE
AI
DOI：10.1016/j.patrec.2024.05.020.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Graphs are commonly used to model interactions between elements of a set, but computing the Graph Edit Distance between two graphs is an NP -complete problem that is particularly challenging for large graphs. To address this problem, we propose a supervised metric learning approach that combines Graph Neural Networks and optimal transport to learn an approximation of the GED in an end -to -end fashion. Our model consists of two siamese GNNs and a comparison block. Each graph pair's nodes are augmented by positional encoding and embedded by multiple Graph Isomorphism Network layers. The obtained embeddings are then compared through a Multi -Layer Perceptron and Linear Sum Assignment Problem solver applied on a nodewise Euclidean metric defined in the embedding space. We show that our approach achieves state-of-the-art results on benchmark datasets and outperforms other similar works in the domain. Our approach also provides explainability through the extraction of an edit path from one graph to another and guarantees metric properties conservation during training and inference.
Keywords:
Graph Neural Network
Graph Edit Distance
Metric learning
Linear Sum Assignment
Node embedding
Siamese architectures
Journal
IF:
3.3
Papers:
7.9K
Citations:
1.6W