Post #158

How hard is graph isomorphism for graph neural networks? This is a new work by Andreas Loukas that sheds a little bit more light into the theory behind GNN. The analysis relies on the amount of information nodes should exchange in order to detect isomorphism class of each graph. This problem of finding isomorphism class is called graph canonization problem, which is probably even harder than graph isomorphism. As such a GNN model needs to output a number for each possible graph up to isomorphism, and needless to say the number of non-isomorphic graphs grows closely to factorial terms. Hence the experiments, while support the theory, are done only on very small graphs ~10 nodes.