Expressiveness.
[1]} and [2]} established the equivalence of message passing GNNs and the first order Weisfeiler-Lehman (1-WL) test. This spurred research into more expressive GNN architectures. [3]} and [4]} proposed to use random node features for unique node identification. As pointed out by [5]}, message passing GNNs with truly unique identifiers are universal. Unfortunately, such methods generalize poorly to new graphs [6]}. [7]} propose propagating matrices of order equal to the graph size as messages instead of vectors to achieve a permutation equivariant unique identification scheme. Other possible expressiveness-improving node feature augmentations include distance encoding [8]}, spectral features [9]} or orbit counts [10]}. However, such methods require domain knowledge to choose what structural information to encode. Pre-computing the required information can also be quite expensive [10]}.
An alternative to this is directly working with higher-order graph representations [2]}, [13]}, which can directly bring \(k\) -WL expressiveness at the cost of operating on \(k\) -th order graph representations. To improve this, methods that consider only a part of the higher-order interactions have been proposed [14]}, [15]}.
Alternatively, extensions to message passing have been proposed, which involve running a GNN on many, slightly different copies of the same graph to improve the expressiveness [6]}, [17]}, [18]}. [19]} provide a theoretical expressiveness comparison of many of these GNN extensions.
[20]} propose the use of tensor languages for theoretical analysis of GNN expressive power.
Interestingly enough, all of these expressive models focus mainly on graph-level tasks. This suggests these are the main tasks to benefit from increased expressiveness.
