- Rating
- 4
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
Color refinement separates vertices whenever their numbers of neighbors differ in a class of the current coloring. Message-passing neural networks have the same distinguishing power as color refinement: with t layers, they can distinguish only vertices that are also distinguished after t refinement rounds. Hence, they may require m-1 layers on graphs with m stable coloring classes. With global filters, each layer has access to information from the entire graph. It has been open to which extent global filters reduce the number of layers. This paper proves that they halve it. More precisely, the authors proof that floor(m/2) is an exact worst-case bound.for filters given by polynomials in the adjacency matrix. They further prove that a single fixed Katz filter kept across each layer suffices to reach this bound. They also show that adding layers does not increase the distinguishing power of linear networks with arbitrary polynomial filters. Likewise, after a single global filtering stage, further layers that process vertex features separately cannot add distinguishing power. The authors also prove lower bounds on the number of alternations between filtering and nonlinear operations needed to obtain the full distinguishing power of color refinement.
Critical strengths
The main result is interesting because it contradicts the intuition that global information should remove the need for depth and the explanation through deficiency is elegant. Moreover, the bound is the exact worst-case, (not merely an asymptotic bound), together with a matching lower-bound construction. The lower bound’s strength is that it survives arbitrary polynomial filters, unrestricted width and arbitrary updates. So it identifies a limitation beyond locality.
Critical weaknesses
The paper is well-presented and seems to be sound. There is one minor error in the appendix: On p. 16, lines 819–821, the paper says that on the disjoint union of a triangle and a hexagon the distance-two matrix is J-I-A and is a polynomial in A. Since both statements are fasle, the claim most likely is intended to refer back to the earlier seven vertex graph.
Questions for authors
none
Response to Reviewer jxwb
Thank you for your careful review and for the sharp eye that caught the slip in Appendix B.1. As you suspected, the sentence on page 16, lines 819–821, was meant to refer to the seven-vertex graph introduced earlier in the same paragraph. On that graph the distance-two matrix equals J−I−A, because the graph has diameter two, and J−I−A is a polynomial in A, because the graph is connected and regular.
On the disjoint union of a triangle and a hexagon neither statement holds, as you point out. The corrected passage (page 17, lines 889–894 of the revised paper) now uses this graph to show that the distance-two matrix of a graph need not be a polynomial in A. Indeed, the indicator vectors of the triangle and of the hexagon are eigenvectors of A for the same eigenvalue 2, so every polynomial in A multiplies both by the same number, whereas the distance-two matrix of this graph sends the first to zero and doubles the second. The passage belongs to the discussion of the scope of the model, and the error affects no result or proof in the paper.
Your review also noted that the bound is the exact worst case, with a matching construction. In the revised paper we show that the bound for filters from the degree algebra D, to which the degree-normalized filters belong, is exact as well (Theorem 1(b) and the new Proposition C.3).
We hope that the correction settles the point you raised, and we would be glad to answer any further questions. Thank you again for the effort and expertise that you have devoted to our work in this review. Your comment has made it a better paper.