Algorithm for commonalities across related objects
I came up with the idea of hashing when I just started looking at this, but seems that the range of the input data is not given, so it's very hard to decide on a specific algorithm.

However, there's another idea:


During input, create a table for each id, record all the linkedId of it, and the sum of linkedIds of it.
After recording all the input, you have tons of ways to find those ids whose sum of all linkedIds are the same, put them into groups, like an $O(n^2)$ brute-force or some $O(n\log(n))$ discretization. This step is a kind of classification, all ids in a group may not be the equivalent, but equivalent ids must be in the same group
Traverse through all groups, find those equivalent ids


This is expected to be a lot more efficient than brute-force. Hope it can help you.