I am interested in the following decision problem:

> Given descriptions of two graphs $G,H$ which interpret in the pure set $\mathbb N=(\{0,1,2,\ldots\},=)$, decide whether $G$ and $H$ are isomorphic.

The question is: is this problem decidable at all?

(A graph $G$ is represented by a triple of formulas $(\phi_{\text{dom}},\phi_{\sim},\phi_E)$ describing the interpretation in the usual way (namely, $\phi_{\text{dom}}$ is a formula with $d$ free variables for some $d\in\mathbb N$, defining a set  $V\subset \mathbb N^d$, $\phi_{E}$ has $2d$ free variables and defines a symmetric binary relation $E\subset V\times V\subset \mathbb N^{2d}$, and $\phi_\sim$ is a formula with $2d$ free variables defining a binary relation $\sim\subset V\times V$ which is a congruence of the graph $(V,E)$ (i.e. the edge relation is invariant under $\sim$). The graph $G$ is defined as the quotient graph $(V,E)/\sim$ with vertices $V/\sim$ and edges $\{[v],[w]\}$ such that $(v,w)\in E$.)

The graphs $G,H$ are ω-categorical and therefore, whenever they are non-isomorphic, there is a sentence $\phi$ which distinguishes $G$ from $H$. Since it can be effectively tested whether $\phi$ holds in $G$ and in $H$,
it follows that non-isomorphicity is recursively enumerable. 
Therefore, the question which remains is whether there is an effective witness of isomorphicity, which would probably require some form of structure theorem for these graphs.

These graphs are ω-categorical, ω-stable, and moreover they are coordinatized by indiscernible sets, as in the eponymous paper by Lachlan,
so perhaps the structure theory developed in this paper could be of use.
(In this question I ask if those two classes coincide:https://mathoverflow.net/questions/231791/%CF%89-categorical-%CF%89-stable-structure-with-trivial-geometry-not-definable-in-the-pur?noredirect=1#comment573324_231791).

My question could be generalized to graphs which interpret in other structures with decidable first order theory, e.g., the dense linear order.



----------
Edit 1: I modified the question so that it talks about graphs rather than arbitrary structures. Those two questions are easily seen to be equivalent. 

----------
Edit 2: I wrote down some preliminary observations concerning this problem here: http://atoms.mimuw.edu.pl/?p=1063