Answers.Body: <p>Notice that a partition (set of nodes with the same label) can never get combined with another partition during an iteration. If two nodes are in different partitions, they stay in different partitions. If two nodes are in the same partition, they might stay in the same partition or get split up into different partitions. Therefore, the number of partitions increases with every iteration (except for the last one which signals the end). There can't be more partitions than nodes, therefore the algorithm eventually doesn't split any more partitions, and stops.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-10-07T15:03:36.130Z
Answers.Text: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/130322/discussion-on-answer-by-user253751-does-the-weisfeiler-lehman-isomorphism-test-e).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-10-04T16:29:52.767Z
Answers.LastActivityDate: 2021-10-22T09:25:37.497Z
Answers.LastEditDate: 2021-10-22T09:25:37.497Z
Answers.UserDisplayName: Criticize SE actions means ban
Body: <p>I am studying GNNs. I am interested in the <strong>Weisfeiler-Lehman Isomorphism Test</strong> (WL-Test).</p>
  <p>I was looking for information about whether the test always ends or not, but I didn't find a definitive answer.</p>
  <p>I know that we can choose how many iterations can be done, or the test is finished if the iteration makes the same result.</p>
  <p>My question is: <em>What if we don't choose how many iterations should be done and the iterations don't make the same result between two graphs? Will the iterations keep going on (i.e. infinitely)?</em></p>
  
Tags: <graph-neural-networks><graph-theory>
Title: Does the Weisfeiler-Lehman Isomorphism Test end?
UserDisplayName: JAEMTO
ThreadText: # Does the Weisfeiler-Lehman Isomorphism Test end?
  
  (Asked by: username_0 on 2021-10-04)
  
  I am studying GNNs. I am interested in the **Weisfeiler-Lehman Isomorphism Test** (WL-Test).
  
  I was looking for information about whether the test always ends or not, but I didn't find a definitive answer.
  
  I know that we can choose how many iterations can be done, or the test is finished if the iteration makes the same result.
  
  My question is: *What if we don't choose how many iterations should be done and the iterations don't make the same result between two graphs? Will the iterations keep going on (i.e. infinitely)?*
  
  **Tags:** graph-neural-networks, graph-theory
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-10-04. Score: 1 | Accepted answer
  
  Notice that a partition (set of nodes with the same label) can never get combined with another partition during an iteration. If two nodes are in different partitions, they stay in different partitions. If two nodes are in the same partition, they might stay in the same partition or get split up into different partitions. Therefore, the number of partitions increases with every iteration (except for the last one which signals the end). There can't be more partitions than nodes, therefore the algorithm eventually doesn't split any more partitions, and stops.
  
  > **Comments:**
  > **username_2**: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/130322/discussion-on-answer-by-user253751-does-the-weisfeiler-lehman-isomorphism-test-e).  
  
  ---
  
  