Summary ======= The paper studies how to implement the well-known k-WL algorithm, which is a well-investigated heuristic for the graph isomorphism problem, in the language of linear algebra. Consequently, the authors introduce so-called $k$-order graph networks, an extension of GNNs, that have the same power as the k-WL. Specifically, they show how express the $3$-WL (or equiv. the $2$-FWL), and then sketch how their techniques can be used to show the general case. The experimental results indicate that the new layer provides some benefits over the well-known baselines as well as the $k$-GNN layer (Morris, 2018). Assessment ========= Interesting work that extend/sheds a different light on the work of Maroon et al 2019, and Morris et al, 2018. I didn't check the proofs in detail, although the results and high-level ideas seem logical and plausible. As the work is similar to the one of Morris et al, 2018, the authors should put more work in making their contribution clear. Discussion of related work is good.

This is a nice theoretical paper that clearly states the mentioned contributions. It is proven that a neural networks augmented with matrix multiplication is proved it achieves 3-WL expressiveness. The quantifying of the generalization ability of these models seems to be very important.

The paper puts k-order networks introduced previously in relation to the k-WL test for graph isomorphism. The paper is on a high technical level, but clearly written and generally comprehensible. The results are closely related to two recent papers (Morris et al, 2018, Xu et al., 2019), which are prominently cited and discussed in the abstract and introduction. The paper presents a different formalism based in k-order networks and introduces techniques to obtain models that are as expressive as the k-WL test. In this technical part the relation to the two other papers is less clear. For example, multiset representations have also been proposed by Xu et al., 2019 for a similar task. Why is a different PMP based method introduced by the authors? The advantages of the introduced techniques should be stated more clearly. The contribution of section 6 is more clear, where a 3-WL equivalent model is proposed, which emulates the folklore 2-WL. The approach is claimed to be more efficient than the approach of Morris et al. with the same expressive power. The argument is understandable, but a result in terms of computational complexity or experimental running time is missing. This would strengthen the contribution. Minor remarks: * Section 3.1: Graphs and possible attributes should be introduced. * p6, l.205 ".5" should be removed ===== Edit ===== The authors have provided complexity results with their rebuttal. I have increased my score by one point.