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.


1 Answer 1


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.

  • $\begingroup$ 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? $\endgroup$
    – Vezen BU
    Dec 11, 2023 at 6:42
  • 2
    $\begingroup$ 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. $\endgroup$ Dec 11, 2023 at 7:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .