# Expected graph edit distance between two random graphs

Consider Erdos-Renyi random graphs $$G(n,p)$$. Let us independently sample two graphs $$G_1$$ and $$G_2$$ following $$G(n,p)$$. What is the expected graph edit distance (GED) between $$G_1$$ and $$G_2$$? Since the number of nodes is the same for $$G_1$$ and $$G_2$$, the expected GED is $$\mathbb{E}[\text{GED}(G_1, G_2)] = \min_{G' \simeq G_1} |E(G') \setminus E(G_2)| + |E(G_2) \setminus E(G')|,$$ where $$G' \simeq G_1$$ means $$G'$$ and $$G_1$$ are isomorphic.

A related, and possibly equivalent, question would be, what is the expected number of overlapping edges considering graph isomorphism, i.e., what is $$\mathbb{E}[\text{overlap}(G_1, G_2)] := \max_{G' \simeq G_1} |E(G') \cap E(G_2)|.$$

We have some existing questions w.r.t. cut distance but without answer.

For any fixed choice of $$G'$$ isomorphic to $$G_1$$, the edit distance is $$\text{Binomial}(\binom n2, \frac12)$$, which is $$\frac{n(n-1)}{4}$$ on average.
By a Chernoff bound, for $$0<\delta<1$$, the probability that the edit distance is less than $$(1-\delta)\frac{n(n-1)}{4}$$ is at most $$\exp\left(-\frac{\delta^2 n(n-1)}{8}\right)$$. This is less than $$n^{-n}$$ for $$\delta = \sqrt{\frac{8\log n}{n}}$$, at which point we can simply use the union bound over all $$n!$$ choices of $$G'$$.
Thus, with high probability, the edit distance between $$G_1$$ and $$G_2$$ is at least $$\frac{n^2}{4} - O(n^{3/2} \sqrt{\log n})$$: there is no $$G'$$ isomorphic to $$G_1$$ that we can take which does significantly better than average.
Also, by taking $$\delta = \frac{\log n}{n}$$ in a Chernoff bound facing the other direction, we see that with high probability just $$G_1$$ by itself (without applying any automorphism) does not do significantly worse than average: not worse than $$\frac{n^2}{4} + O(n \log n)$$.
The error probability I hid under the clause "with high probability" is exponentially small in the first case, and $$\exp(-O((\log n)^2))$$ in the second case. But in all cases, the edit distance is going to be between $$0$$ and $$\binom n2$$. Therefore outliers do not contribute anything significant to the expected value: it also lies in the small interval around $$\frac{n^2}{4}$$ described above.
• Thanks a lot for your insightful answer! Is it possible for us to get something better than asymptotic $n^2 (\frac{1}{4} + o(1))$? What kind of tools do you think might be useful to have a tighter bound for small $n$ values? Dec 11, 2023 at 6:42
• I don't know; there's two separate issues. First, it's hard to figure out how to pick $G'$ "intelligently", given that we're choosing between the best of many very bad options. Second, it's hard to understand the expected value of the minimum of $n!$ options. I think we could prove an upper bound of $\frac{n^2}{4}$ with high probability; $O(n \log n)$ could be improved a tiny bit to $o(n\log n)$ just by being more careful with $\delta$, and I think we can win that much by choosing $o(\log n)$ vertices in $G_1$ and $G_2$, and making sure their neighborhoods line up. Dec 11, 2023 at 7:29