GI-hard graph problem not known to be $NP$-complete Graph Isomorphism ($GI$) is good candidate for $NP$-intermediate problem. $NP$-intermediate problems exist unless $P=NP$. I'm looking for natural problem that is hard for $GI$ under Karp reduction (A graph problem $X$ such that $GI &lt;_p^m X$).


  Is there a natural $GI$-hard graph problem that is neither $GI$-equivalent nor known to be $NP$-complete?
After extensive search, I found the Legitimate Vertex Deck problem (LVD) which is related to the famous Graph Reconstruction conjecture. A deck of graph $G(V, E)$ is a multi-set of graphs $F = \{G_1,G_2, . . . , G_n\}$ such that $G_i$ is isomorphic to $G−v_i$ ($G-v$ is a graph obtained from $G$ by removing $v$ and its incident edges). ($|V|=n$)

The k-LEGITIMATE VERTEX-SUBDECK problem, given multi-set of graphs $F= \{G_1,G_2, . . . , G_k\}$, Decide whether there is a graph $G$ such that $F$ is a subset of its vertex-deck (k-LVD =$ \{[G_1, . . . , G_k]|(∃G)[[G_1, . . . , G_k] ⊆ vertex-deck(G)]\}$) 
where $k \ge 3$

k-LVD problem is $GI$-hard and is not known to be $GI$-equivalent. It is open problem whether k-LVD is $NP$-complete (for $k \ge 3$). See the open problems section of Complexity results in graph reconstruction. 

Also, the paper suggests the existence of a problem of intermediate complexity between $GI$ and k-LVD. The problem is LVD= n-LVD where all $n$ candidate cards are given (Input for LVD is $F= \{G_1,G_2, . . . , G_n \})$.