I am reading the paper Neural Message Passing for Quantum Chemistry by Justin Gilmer et al. And I have a question regarding this passage

The message functions $M_t$, vertex update functions $U_t$, and readout function $R$ are all learned differentiable functions. $R$ operates on the set of node states and must be invariant to permutations of the node states in order for the MPNN to be invariant to graph isomorphism.

It is not clear for me, why MPNN have to be invariant to graph isomorphism. Could you please share your thoughts on it?


1 Answer 1


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:

  1. 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.
  2. 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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .