Answers.Body: <p>Firstly, as already stated in the Wikipedia quote: Observing that a type of GNN is as expressive as the Weisfeiler–Lehman (WL) Test, means in practice that two graphs <span class="math-container">$\mathcal{G}_1$</span> and <span class="math-container">$\mathcal{G}_2$</span> cannot be differentiated by the GNN, if the 1-WL Test cannot differentiate them. Therefore, if <span class="math-container">$\mathcal{G}_1$</span> and <span class="math-container">$\mathcal{G}_2$</span> are labelled differently, your model cannot ever learn to classify both correctly.</p>
  <p>In real life applications, this often doesn't matter too much and <a href="https://ieeexplore.ieee.org/document/9892655" rel="nofollow noreferrer">Zopf et al.</a> provide a nice analysis of that and there you can see that most datasets contain 100% distinguishable graphs. But the 1-WL-Test struggles with the Molecular data of the MUTAG dataset (s. Table II). However, it seems that most of the time 1-WL expressivity will be enough.</p>
  <p>There is another distinction to be made here: In real-world applications, we want encodings of graphs that reflect their similarity, meaning two similar graphs <span class="math-container">$\mathcal{G}_1$</span> and <span class="math-container">$\mathcal{G}_2$</span> should be encoded as similar vectors in the embedding space. If <span class="math-container">$\mathcal{G}_1$</span> and <span class="math-container">$\mathcal{G}_2$</span> are very slightly different, the vectors should still be close by. This then provides a tool that generalizes to unseen graphs. The WL-Test cannot do this kind of encoding but the GNN can.
  Here it makes sense to think about expressivity of GNNs as the ability to do this smooth encoding. And one aspect of that is this upper bound of expressivity as stated by the quote you provide.</p>
  <p>I hope that was understandable, feel free to follow up on that.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-10T17:03:26.520Z
Answers.LastActivityDate: 2023-02-10T17:03:26.520Z
Answers.UserDisplayName: Chillston
Body: <p><a href="https://en.wikipedia.org/wiki/Graph_neural_network" rel="nofollow noreferrer">Graph Neural Networks</a> power is limited by the power of Weisfeiler–Lehman Graph Isomorphism algorithm.
  Quoting wikipedia:</p>
  <blockquote>
  <p>It has been demonstrated that GNNs cannot be more expressive than the
  Weisfeiler–Lehman Graph Isomorphism Test. In practice, this
  means that there exist different graph structures (e.g., molecules
  with the same atoms but different bonds) that cannot be distinguished
  by GNNs.</p>
  </blockquote>
  <p>What are the practical implications of this limitation? Is it an academic example providing no obstacle in real-life applications of GNNs (e.g. to drug discovery) or are there any instances in which it plays a big role? If the latter, please provide an example of such a limitation.</p>
  
Tags: <graph-neural-networks><geometric-deep-learning><graphs><graph-isomorphism-network>
Title: Relevance of Weisfeiler–Lehman Graph Isomorphism Test limitation for Graph Neural Networks
UserDisplayName: Rexcirus
ThreadText: # Relevance of Weisfeiler–Lehman Graph Isomorphism Test limitation for Graph Neural Networks
  
  (Asked by: username_0 on 2023-02-09)
  
  [Graph Neural Networks](https://en.wikipedia.org/wiki/Graph_neural_network) power is limited by the power of Weisfeiler–Lehman Graph Isomorphism algorithm.
  Quoting wikipedia:
  
  > It has been demonstrated that GNNs cannot be more expressive than the
  > Weisfeiler–Lehman Graph Isomorphism Test. In practice, this
  > means that there exist different graph structures (e.g., molecules
  > with the same atoms but different bonds) that cannot be distinguished
  > by GNNs.
  
  What are the practical implications of this limitation? Is it an academic example providing no obstacle in real-life applications of GNNs (e.g. to drug discovery) or are there any instances in which it plays a big role? If the latter, please provide an example of such a limitation.
  
  **Tags:** graph-neural-networks, geometric-deep-learning, graphs, graph-isomorphism-network
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2023-02-10. Score: 2 | Accepted answer
  
  Firstly, as already stated in the Wikipedia quote: Observing that a type of GNN is as expressive as the Weisfeiler–Lehman (WL) Test, means in practice that two graphs $\mathcal{G}\_1$ and $\mathcal{G}\_2$ cannot be differentiated by the GNN, if the 1-WL Test cannot differentiate them. Therefore, if $\mathcal{G}\_1$ and $\mathcal{G}\_2$ are labelled differently, your model cannot ever learn to classify both correctly.
  
  In real life applications, this often doesn't matter too much and [Zopf et al.](https://ieeexplore.ieee.org/document/9892655) provide a nice analysis of that and there you can see that most datasets contain 100% distinguishable graphs. But the 1-WL-Test struggles with the Molecular data of the MUTAG dataset (s. Table II). However, it seems that most of the time 1-WL expressivity will be enough.
  
  There is another distinction to be made here: In real-world applications, we want encodings of graphs that reflect their similarity, meaning two similar graphs $\mathcal{G}\_1$ and $\mathcal{G}\_2$ should be encoded as similar vectors in the embedding space. If $\mathcal{G}\_1$ and $\mathcal{G}\_2$ are very slightly different, the vectors should still be close by. This then provides a tool that generalizes to unseen graphs. The WL-Test cannot do this kind of encoding but the GNN can.
  Here it makes sense to think about expressivity of GNNs as the ability to do this smooth encoding. And one aspect of that is this upper bound of expressivity as stated by the quote you provide.
  
  I hope that was understandable, feel free to follow up on that.
  
  
  ---
  
  