Convolutional Set Matching for Graph Similarity

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 NPhard nature of computing many graph distance/similarity metrics. We demonstrate our model using the Graph Edit Distance (GED) [2] as the example metric. It is defined as the number of edit operations in the optimal alignments that transform one graph into the other, where an edit operation can be an insertion or a deletion of a node/edge, or relabelling of a node. It is NPhard [3] and costly to compute in practice [4]. The key idea is to turn the pairwise graph distance computation problem into a learning problem.