This report  https://www.cs.cmu.edu/~jingx/docs/DBreport.pdf proposes a method based on Belief Propagation but it also covers previous work, and the authors classify the techniques into 

Edit distance/graph isomorphism, Feature extraction, and Iterative Methods 

Cheers

https://www.cs.cmu.edu/~jingx/docs/DBreport.pdf

Thank your Mr. Denis Parra!

you can refer to http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.81.2343&rep=rep1&type=pdf for your work 

Dear,

i suggest you to read the following publication

THIRTY YEARS OF GRAPH MATCHING IN PATTERN RECOGNITION

D. CONTE et al, Int. J. Patt. Recogn. Artif. Intell. 18, 265 (2004). DOI: 10.1142/S0218001404003228

http://www.worldscientific.com/doi/abs/10.1142/S0218001404003228

You already seem to have several helpful answers. Anyway, your subject is "inexact graph matching". You will find lots of papers on this. This is quite popular nowadays for example to match images since an image structure can be described as a graph, and small differences are not important. Google search through images might be a sign of this area's actuality. However, if you want to know if two graphs are exactly the same this is the graph isomorphism problem, which is something else.

Dear Mr. Denis Parra, Chandra Prakash, Antonio Parziale and Fernando Lobo Pimentel I appreciate by the attention and useful answers!

There is also graph edit distance. See http://link.springer.com/article/10.1007%2Fs10044-008-0141-y#page-1 for details

I found this site. It may be helpful.     http://www.google.com/m?hl=en-US&ie=UTF-8&q=graph+similarity+algorithm