Answers.Body: <p>It is necessary for GCNs / MPNNs to be <strong>invariant to node permutations</strong> in order to generalize properly. Firstly, <em>node permutation</em> 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.</p>
  <p>The above is related to <strong>isomorphic graphs</strong>, 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 <a href="https://en.wikipedia.org/wiki/Graph_isomorphism#Isomorphism_of_labeled_graphs" rel="nofollow noreferrer">two definitions for graph isomorphism</a>:</p>
  <ol>
  <li>Structure and Feature preserving: This is basically the same as node permutations and I'm sure this is also what <a href="https://arxiv.org/abs/1704.01212" rel="nofollow noreferrer">Gilmer et al.</a> mean in their paper.</li>
  <li>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.</li>
  </ol>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-04-21T19:00:29.793Z
Answers.LastActivityDate: 2023-04-21T19:00:29.793Z
Answers.UserDisplayName: Chillston
Body: <p>I am reading the paper Neural Message Passing for Quantum Chemistry by Justin Gilmer et al. And I have a question regarding this passage</p>
  <blockquote>
  <p>The message functions <span class="math-container">$M_t$</span>, vertex update functions <span class="math-container">$U_t$</span>, and
  readout function <span class="math-container">$R$</span> are all learned differentiable functions.
  <span class="math-container">$R$</span> 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.</p>
  </blockquote>
  <p>It is not clear for me, why MPNN have to be invariant to graph isomorphism. Could you please share your thoughts on it?</p>
  
Tags: <deep-learning><graph-neural-networks><graph-theory><graph-isomorphism-network>
Title: Why readout operation in message passing graph neural nets have to be invariant to node permutations?
UserDisplayName: dmasny
ThreadText: # Why readout operation in message passing graph neural nets have to be invariant to node permutations?
  
  (Asked by: username_0 on 2023-04-20)
  
  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?
  
  **Tags:** deep-learning, graph-neural-networks, graph-theory, graph-isomorphism-network
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2023-04-21. Score: 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](https://en.wikipedia.org/wiki/Graph_isomorphism#Isomorphism_of_labeled_graphs):
  
  1. Structure and Feature preserving: This is basically the same as node permutations and I'm sure this is also what [Gilmer et al.](https://arxiv.org/abs/1704.01212) 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.
  
  
  ---
  
  