How to define a similarity between two graphs?

Question

Let's say we have a set of vertices $V$, and two (undirected) graphs over the same set $V$, but not necessarily the same set of edges $G_1 = (V, E_1)$, $G_2 = (V, E_2)$. $\newcommand\mG{\mathbb G}$(Let's denote the set of all graphs over the vertices $V$ with $\mG$, so $G_1, G_2 \in \mG$).

Now I'd like to measure how similar (up to isomorphism) those graphs are, so ideally we'd have a metric

$$d: \mathbb G \times \mathbb G \to \mathbb R_{\geq 0}.$$

This should satisfy all the usual axioms of a metric

1. $d(G, H) = 0 \iff G \simeq H$ (Here we consider isomorphy as equality.)
2. $d(G, H) = d(H, G)$
3. $d(G, H) + d(H, I) \geq d(G, I)$

Is there a "useful" example of such a metric?

I know this is a little bit vague, but what I mean by that is that it should not be the trivial metric, and somehow relate to what we intuitively think would make sense: For example it would be nice if the distance if you remove one edge is smaller than if you remove two or more edges, or (I'm not sure if it actually makes sense, so it certainly is not necessary) that the distance between the empty graph and the complete graph is maximal.

For the sake of simplicty you can assume that $V$ is finite.

Answer 1

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 "edit distance up to isomorphism" as your question seems to indicate you want, but it can of course be adapted in a straightforward way to fit that requirement.

Answer 2

A very natural metric for graphs on the vertex set $[n]$ is $$ d(G,H) = \min_{\sigma \in S_n} |G \Delta H^\sigma|, $$ where $|G \Delta H|$ is the size of the symmetric difference between the edge sets of $G$ and $H$, and $H^\sigma$ is the graph obtained from $H$ by renaming the vertices according to the permutation $\sigma$.

I believe it satisfies all your properties.