The expressive power of kth-order invariant graph networks
  The expressive power of graph neural network formalisms is commonly measured
by their ability to distinguish graphs. For many formalisms, the k-dimensional
Weisfeiler-Leman (k-WL) graph isomorphism test is used as a yardstick. In this
paper we consider the expressive power of kth-order invariant (linear) graph
networks (k-IGNs). It is known that k-IGNs are expressive enough to simulate
k-WL. This means that for any two graphs that can be distinguished by k-WL, one
can find a k-IGN which also distinguishes those graphs. The question remains
whether k-IGNs can distinguish more graphs than k-WL. This was recently shown
to be false for k=2. Here, we generalise this result to arbitrary k. In other
words, we show that k-IGNs are bounded in expressive power by k-WL. This
implies that k-IGNs and k-WL are equally powerful in distinguishing graphs.
