How to define a similarity between two graphs?
One such metric which is very useful is the graph edit distance. In a nutshell, you are allowed a certain number of operations, each with a cost, such as edge insertion or edge deletion (depending on the context you may also add, relabel, remove vertices) to transform one graph into another. The distance between any two graphs is then the minimum total cost of a transformation from one to the other (the costs need to be symmetrical for this to be a distance, e.g. the cost of deleting is equal to the cost of adding, and are usually taken to be unitary).
There are applications outside of pure graph theory such as pattern recognition or in bioinformatics (generalisations of string edit distance useful for DNA analysis).
Note that usually we don't consider &quot;edit distance up to isomorphism&quot; as your question seems to indicate you want, but it can of course be adapted in a straightforward way to fit that requirement.