The core idea of this approach is to compute a grammar based index on a labeled directed graph to support finding the occurrences of sub-graphs isomorphic to a given pattern?
To appreciate the results, it would be interesting to know what kind of data structures were used, i.e., how did you represent your grammar?
The interesting point is how the predecessors on the sets sim[u] and sim[u'] are computed.
Do you use an FM-index, a hash-table, or an inverted index?
Also, for the experiments, how is the "original" graph represented? Did you use a common graph library for sub-graph search?