The expressive power of kth-order invariant graph networks
This resolves a theoretical question in graph neural network expressiveness, but it is incremental as it generalizes a known result for k=2 to arbitrary k.
The paper tackled the problem of determining whether kth-order invariant graph networks (k-IGNs) can distinguish more graphs than the k-dimensional Weisfeiler-Leman (k-WL) test, showing that k-IGNs are bounded by k-WL, implying they are equally powerful in graph distinction.
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.