Does the Weisfeiler-Lehman Isomorphism Test end?

Question

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)?

Answer 1

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.