Post #159

On the universal equivariant functions Yesterday's post was followed by a conversation with Andreas Loukas on the power of graph neural networks. There is one detail about the current analysis of GNN, which I didn't pay much attention before, even though I encountered it (it's a recurring phenomenon for me, when some major insight is given one sentence in the paper and is not highlighted in CAPITAL letters). The insight is that there are two types of GNN, anonymous and non-anonymous. Anonymous case means you are invariant to the order of nodes, for example when you use the sum aggregation over nodes. It was shown that anonymous case is equivalent to WL algorithm and therefore has a lot limitations such as not being able to count subgraphs or distinguish graphons, etc. So the current anonymous models are not universal: they cannot compute all the functions of the inputs. It's a weaker model than non-anonymous case, when you give some orderings to the nodes and then you iterate over all orderings. Non-anonymous models have additional node features, for example one-hot encodings of their position in adjacency matrix, which is one of the sufficient conditions for GNN to be universal. There are then two scenarios. Either you consider all possible permutations, in which case it grows in factorial terms and essentially it's a cheat. Or you resort to a single permutation, but then do not enjoy the invariance property of GNN, i.e. for different orderings it can give different set of embeddings for the same nodes. So it's interesting to see if there are universal equivariant functions that do not use all node permutations, which is still an open question.