@droslean - You normally search for your node by uid, then get the reverse node uids to delete the inverse relationships. If you model your data correctly, you should not have to delete individual nodes at all. Make sure to use @hasInverse, and delete your nodes through graphql, or add both ends through dql and delete both ends.
If this problem comes up, you are probably not modeling your data as efficiently as possible.
Look into @reverse, as that is one way to solve the problem. Also, here are a couple of threads that you may find useful.