Suppose I have two undirected unweighted graphs $G_1$ and $G_2$, which have the same set of nodes. Let $A_1$ and $A_2$ be their (binary) adjacency matrices, respectively.
I wonder what are the proper ways to quantitatively measure the similarity (or distance) between $G_1$ and $G_2$ (or specifically, $A_1$ and $A_2$).
For example, we can reshape $A_1$ and $A_2$ as vectors and measure the $p$-norm distance. I feel that there should be a correspondence between a metric and a physical meaning (e.g., how many edges we need to move to transform $G_1$ to $G_2$).
I wonder if there is some serious discussion (like papers) on measuring distances between graphs in graph theory literature.
Here's a brainstorm: in biological sequence analysis, there is a function called the "edit distance" that solves an analogous problem: e.g., how far apart are any 2 finite-length DNA sequences? This is defined in terms of the minimum number of "edits" required to convert one sequence into the other, using insertions and deletions.
Maybe we could define a type of "edit distance" for graphs, where we allow node and edge insertion/deletion operations, and count the minimum number of "graph edits" required to convert one graph to another?