One Generalization of Graph Isomorphism Problem

Question

Say I generalize the language which consists of pairs of isomorphic graphs to take the following form:

$GI(f) = \{ (G, H) \mid \exists \psi : V_G \rightarrow V_H, Pr_{a, b \in V_G} ((a, b) \in E_G \Longleftrightarrow (\psi(a), \psi(b)) \in E_H) \geq f\}$

Is there any work on this language? The obvious question is whether there exists $f$ such that $GI(f) \in P$. The funny counterpart to this language is

$IG(f) = \{ (G, H) \mid \forall \psi : V_G \rightarrow V_H, Pr_{a, b \in V_g}((a, b) \in E_G \Longleftrightarrow (\psi(a), \psi(b)) \in E_H) \leq f \}$

Just wanted to hear the thoughts of anyone who wanted to have a go at constructing algorithms for different constant values of $f$ or perhaps for $f$ as a function of the size of the vertex sets or something.

Answer 1

This is the decision version of what is sometimes called "Approximate Graph Isomorphism." While I won't say it's been studied a lot, it has been studied. See, for example:

[AKKV] Arvind, Kobler, Kuhnert, & Vasudev. Approximate graph isomorphism. MFCS '12. (freely available ECCC version)

In particular, [AKKV] show that one can approximate the maximum (over bijections $V(G) \to V(H)$) of the number of matches to any constant factor in $n^{O(\log n)}$ time, but that any constant-factor approximation to the minimum number of mismatches is $\mathsf{NP}$-hard.

[GRW] Grohe, Rattan, & Woeginger. Graph similarity and approximate isomorphism. arXiv:1802.08509 [cs.DS]

[GRW] show that computing the minimum number of mismatches is $\mathsf{NP}$-hard even on trees. They also show that in the weighted case, it is $\mathsf{NP}$-hard if either weighted adjacency matrix has unbounded rank or negative eigenvalues (so the easy cases are a subset of PSD matrices of bounded rank).

This problem is also sometimes called "graph similarity" (which I consider a much more general term) or "graph matching" (which you'll have a hard time Googling because you'll get a lot of stuff about matchings), and has apparentely been studied more in the ML and data mining literature.

Answer 2

I wasn't able to figure out whether $\mathrm{GI}(1/2)\in\mathsf P$, but here is a weaker result: The languages $\mathrm{GI}(1/2)$ and $\mathrm{GI}$ are not $\mathsf P$-inseparable.

Proof: It suffices to show the first reverse inclusion in $$\mathrm{GI}(1/2)\supseteq\{(G,H): |V_G|=|V_H|, |E_G|=|E_H|\} \supseteq \mathrm{GI}(1)=\mathrm{GI}.$$ Let $p$ be the probability that $(a,b)\in E_G$ for uniformly random $a$, $b$.

Let $\Psi:V_G\to V_H$ be a uniformly random function and also let $a$ and $b$ be selected randomly, with $\Psi$, $a$, $b$ mutually independent. Then the two events $$\mathscr U = \{(a,b)\in E_G\}\text{,}\quad \mathscr V=\{(\Psi(a),\Psi(b))\in E_H\}$$ are independent. Therefore $$\Pr_{\Psi,a,b}(\mathscr U\leftrightarrow\mathscr V)=p^2+(1-p)^2\ge 1/2.$$

So by Fubini's Theorem there is some $\psi$ such that $\Pr_{a,b}(\mathscr U\leftrightarrow\mathscr V\mid \Psi=\psi)\ge 1/2.\qquad\Box$