Reviews: On the equivalence between graph isomorphism testing and function approximation with GNNs

The paper targets the problem of measuring the representation power of Graph neural networks (GNNs), an interesting and important topic, that has become popular recently (partially due to two prominent works (Xu et al. There are three main contributions: 1. Establishing the equivalence between two methods for measuring GNN representation power: (i) their ability to approximate permutation invariant functions (ii) their ability to distinguish non-isomorphic graphs. Although not very surprising, this is a nice observation. The authors show that these sigma algebras are an equivalent way to measure representation power of GNNs, for instance, the inclusion of sigma algebras originating from two models is equivalent to saying one model is more powerful than the other. This is a potentially useful observation.