GraSP: Simple yet Effective Graph Similarity Predictions
Lists
Only you see this
Abstract
Graph similarity computation (GSC) is considered one of the essential operations because of its wide range of applications in various fields. Graph Edit Distance (GED) and Maximum Common Subgraph (MCS) are the most popular graph similarity metrics. However, calculating exact GED and MCS is a complex task that falls under the category of NP-hard problems. Consequently, state-of-the-art methodologies learn data-driven models leveraging graph neural networks (GNNs) for estimating GED and MCS values. A perceived limitation of these approaches includes reliance on computationally expensive cross-graph node-level interaction components but to little avail. Instead of building up complicated components, we aim to make the complicated simple and present GraSP, a simple yet highly effective approach for GSC. In particular, to achieve higher expressiveness, we design techniques to enhance node features via positional encoding, employ a graph neural network backbone with a gating mechanism and residual connections, and develop a multi-scale pooling technique to generate meaningful representations. We theoretically prove that our method is more expressive and passes 1-WL test performance capabilities. Notably, GraSP is versatile in accurately predicting GED and MCS metrics. In extensive experiments against numerous competitors on real-world datasets, we demonstrate the superiority of GraSP over prior arts regarding effectiveness and efficiency. The source code is available at https://anonymous.4open.science/r/GraSP.
BibTeX
@inproceedings{zheng2025grasp,
author = {Haoran Zheng and Jieming Shi},
title = {{GraSP: Simple yet Effective Graph Similarity Predictions}},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2025},
doi = {10.1609/aaai.v39i21.34450},
}