Convolutional Set Matching for Graph Similarity
This addresses a fundamental challenge in graph analysis for applications like bioinformatics or social networks, though it appears incremental as it builds on existing neural network methods.
The paper tackles the NP-hard problem of pairwise graph similarity computation by introducing GSimCNN, a model that achieves state-of-the-art performance on graph similarity search across three real datasets.
We introduce GSimCNN (Graph Similarity Computation via Convolutional Neural Networks) for predicting the similarity score between two graphs. As the core operation of graph similarity search, pairwise graph similarity computation is a challenging problem due to the NP-hard nature of computing many graph distance/similarity metrics. We demonstrate our model using the Graph Edit Distance (GED) as the example metric. Experiments on three real graph datasets demonstrate that our model achieves the state-of-the-art performance on graph similarity search.