REVIEW 2 cited by
The expressive power of kth-order invariant graph networks
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original abstract
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.
Forward citations
Cited by 2 Pith papers
-
On Universality of Deep Equivariant Networks
Deep equivariant networks are universal over the entry-wise separable regime once depth stabilizes separation or a convolutional readout is added, unifying prior architecture-specific results.
-
On the Expressive Power of Subgraph Graph Neural Networks for Graphs with Bounded Cycles
Under a k-separability condition for k greater than 1, k-hop subgraph GNNs are universal approximators on connected graphs with no cycle longer than 2k+1; k-hop GNNs without subgraph structure get a similar 2k-1 bound.
Discussion (0). Continue with ORCID to comment.