<p>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:</p>

<blockquote>
  <p>[AKKV] Arvind, Kobler, Kuhnert, &amp; Vasudev. <a href="https://doi.org/10.1007/978-3-642-32589-2_12" rel="nofollow noreferrer">Approximate graph isomorphism</a>. MFCS '12. (<a href="https://eccc.weizmann.ac.il/report/2012/078/" rel="nofollow noreferrer">freely available ECCC version</a>) </p>
</blockquote>

<p>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.</p>

<blockquote>
  <p>[GRW] Grohe, Rattan, &amp; Woeginger. Graph similarity and approximate isomorphism. <a href="https://arxiv.org/abs/1802.08509" rel="nofollow noreferrer">arXiv:1802.08509 [cs.DS]</a></p>
</blockquote>

<p>[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).</p>

<p>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.</p>

CC BY-SA 3.0
2018-04-30T15:09:52.150Z
2018-04-30T15:09:52.150Z
Joshua Grochow
<p>I wasn't able to figure out whether $\mathrm{GI}(1/2)\in\mathsf P$, but here is a weaker result: <strong>The languages $\mathrm{GI}(1/2)$ and $\mathrm{GI}$ are not $\mathsf P$-inseparable</strong>.</p>

<p>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$.</p>

<p>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.$$</p>

<p>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$</p>

CC BY-SA 3.0
2017-10-08T23:10:50.040Z
I'm not sure what P-inseparability is nor was I able to find the definition online. Could you help me out?
Samuel Schlesinger
CC BY-SA 3.0
2017-10-08T23:22:26.193Z
Oh sorry... I meant $A\subseteq B$ are $P$-inseparable if there is no problem $C$ in $P$ with $A\subseteq C\subseteq B$.
Bjørn Kjos-Hanssen
CC BY-SA 3.0
2017-10-08T23:27:40.550Z
Original definition is: disjoint sets $A$ and $B$ are $P$-inseparable if there is no $C$ in $P$ with $A\subseteq C$ and $C$, $B$ still disjoint.
Bjørn Kjos-Hanssen
CC BY-SA 3.0
2017-10-06T07:35:19.953Z
2017-10-06T08:01:04.750Z
2017-10-06T08:01:04.750Z
Bjørn Kjos-Hanssen
<p>Say I generalize the language which consists of pairs of isomorphic graphs to take the following form:</p>

<p>$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\}$</p>

<p>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</p>

<p>$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 \}$</p>

<p>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.</p>

<graph-theory><graph-algorithms><graph-isomorphism>
One Generalization of Graph Isomorphism Problem
Samuel Schlesinger
# One Generalization of Graph Isomorphism Problem

(Asked by: username_0 on 2017-10-06)

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.

**Tags:** graph-theory, graph-algorithms, graph-isomorphism

---

## 2 answers

### Answer by username_1 on 2018-04-30. Score: 2 | Accepted answer

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](https://doi.org/10.1007/978-3-642-32589-2_12). MFCS '12. ([freely available ECCC version](https://eccc.weizmann.ac.il/report/2012/078/))

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]](https://arxiv.org/abs/1802.08509)

[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 by username_2 on 2017-10-06. Score: 3

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$

> **Comments:**
> **username_0**: I'm not sure what P-inseparability is nor was I able to find the definition online. Could you help me out?  
> **username_2**: Oh sorry... I meant $A\subseteq B$ are $P$-inseparable if there is no problem $C$ in $P$ with $A\subseteq C\subseteq B$.  
> **username_2**: Original definition is: disjoint sets $A$ and $B$ are $P$-inseparable if there is no $C$ in $P$ with $A\subseteq C$ and $C$, $B$ still disjoint.  

---

