k (s) denote the color ofs in G[1 ] assigned attth iteration,and let

Such a perspective has been explored in Chen et al.[8], for instance, to build an equivalence between function approximation and graph isomorphism testing by GNNs. Forexample, consider FMPNN, the family of all Message Passing Neural Networks onG. Similar holds for the family of allk-Invariant Graph Functions (k-IGNs). Two k-typles, (ii,...,ik),(j1,...,jk) Vk are said to be in the same equivalent class if a permutation π on V such that (π(ii),...,π(ik)) = (j1,...,jk). Thus, both(10) and (11) can be proved analogously to how(11) is provedforcase2.