Graph similarity measurement

Isomorphism (NP but probably not NPC)
Editing distance (graph edit distance has been recognized a flexible
error-tolerant mechanism to measure distances between attributed
graphs, Generally, an attributed graph consists of a (directed or undirected) graph and an arbitrary number of node and edge attributes. For example, the nodes of a graph are often assigned attributes such as names, flags, and coordinates, and likewise, the edges are assigned attributes such as lengths, costs, and capacities.)
Maximum sub graph
Minimum super graph
Statistical methods (e.g., measurement of degree distribution)
Iterative methods (two graph elements are similar if their neighborhoods are similar)