Before revision:  Recently the develop of deep learning techniques provide a promising solution for this problem by training a network which is able to encode graphs to  feature vectors and then compute similarity based on feature vectors.
After revision:  Recently the develop of deep learning techniques provide a promising solution for this problem by a data-driven approach which trains a network to encode graphs to feature vectors and then compute similarity based on feature vectors.