Is there a graph neural network algorithm that can deal with a different number of input and output nodes?
I suggest you look into link prediction. I have had good luck with the StellarGraph library. They have several algorithms implemented, including GCN.
Link prediction is a binary classification problem. Given two nodes, $v_i$ and $v_j$, does there exist a link between them? Using a library like StellarGraph will also produce node embeddings while performing link prediction.
For you scenario I'm picturing a three step process:

Link prediction and node embeddings on $G$.
Link prediction and node embeddings on $G'$.
Link prediction reusing existing embeddings where each link is between the two graphs. So each link is a tuple of the form: $(v_i, v_j')$ where $v_i \in V$ and $v_j' \in V'$. If there were no links predicted from $v_i$ to $v_j'$ then that might suggest to remove $v_j'$.

In the link prediction tasks that I've outlined, you can use GCN with StellarGraph. So there should be no problems in terms of the number of nodes.