Your current approach would benefit from sorted inputs.
But an even simpler approach would be to ignore the irrelevant verbs and rephrase the problem like this:
A noun phrase is a pair of nouns. We are given two input sets of noun phrases, and must compute set intersection, using a problem specific notion of "phrase equality".
This implies a linear O(n) input pre-processing pass, where you populate a HashSet with each input phrase, X+" "+Y.
With that in hand, your task is trivial. Scan the other collection of phrases, and make two set membership queries: is X+" "+Y or Y+" "+X present in the set?
BTW, your identifier storeAsserions seems to be a typo for storeAssertions. And please include a space after keywords like if & for.