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 training a network which is able to encode graphs to their own feature vectors and then compute similarity based on feature vectors.