It is necessary for GCNs / MPNNs to be invariant to node permutations in order to generalize properly. Firstly, node permutation means that you reindex the nodes. The edges also use this new indexing, i.e. the graph remains completely the same. It is just the ordering with which you store the graph in your memory. Would the MPNN we sensitive to that, the same graph may be classified differently simply by assigning different indices to the nodes. That would not be nice.
The above is related to isomorphic graphs, because if two graphs are isomorphic, they have the same structure. This is good for the same reason: Two graphs with the same structure should not yield different MPNN predictions.
Here it is important to note that once you consider nodes with features, there are two definitions for graph isomorphism:
- Structure and Feature preserving: This is basically the same as node permutations and I'm sure this is also what Gilmer et al. mean in their paper.
- Structure-preserving with similar node feature distribution: If you have the same struicture with equivalent node features - in some cases you'd your MPNN to be invariant to that, in others you don't. It depends on your use case.
Therefore, the invariance to node permutations is generally desirable, whereas the invariance to graph isomorphism can be, depending on the exact definition of isomorphism you mean and your use case.
