Isomorphism - Two graphs are isomorphic if there is a mapping between their nodes in which we can conclude that these graphs are in fact the same
Two graphs \(H\) and \(G\) are isomorphic if and only if, for any pair of nodes \(u\) and \(v\) from H that are adjacent, there is a transformation \(f\) where \(f(u)\) is adjacent to \(f(v)\) in \(G\)
No polynomial-time solution and the problem may as well be considered NP-Complete
Example
Tests
Weisfeiler-Lehman Test
Tests if two graphs are isomorphic or not
H0: Not Isomorphic; Ha: May be Isomorphic
Given that the problem might be NP-Complete, the test can fail in many situations
Example: Non-Isomorphic but passes WL Test
Process
We start by setting an initial value to every node on the graph. Let’s say ‘1’.
For each node, we get the value of every neighbor and concatenate it together with the node value
We take the hash of this value to set the new value of the node
We repeat the process until there is no further change in the distribution of the values (not the values themselves)
If the distribution of the values is the same for both graphs, H0 is rejected
GNNs are, at most (which means that they can be worse) as powerful as a WL-Test on its ability to tell if two graphs are isomorphic
k-Weisfeiler-Lehman Test
For a 2-WL Test:
Let [K] be the set of nodes from K. Let now K² be the set of tuples of size 2 comprised of every permutation of nodes from [K]
Repeat the WL-Test, but with these 2-tuples instead of the nodes
Neighbors are tuples with at least 2 common node with the original tuple
