Graphs are highly versatile data structures  that are used in a wide range of research areas. Consequently, the comparison of two graphs is a problem with many applications. Examples include cheminformatics [2,3], bioinformatics , sociology [5,6], telecommunication (e.g., the internet), computer vision , and natural language processing .
Typical approaches for comparing two graphs are based on
Another possibility  is to categorize graph (dis)similarity measures into those based on (sub)graph isomorphism [10,11] (e.g., Zelinka distance , or, distances based on largest common subgraph and smallest common supergraph ), graph transformations (e.g., edit distance ), adjacency matrices , grammars , and others. Yet another view is to distinguish between the approaches that construct explicit features, such as graph invariants, and those that perform implicit comparisons, such as graph kernels. The latter are thus a special case of graph similarity measures.
Informally, a graph kernel is a function defined directly on two graphs that corresponds to an inner ...