- Rating
- 1
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper builds on results by Arvind et al. (2015) and proposes to use amenability for measuring for how much expressivity is needed on a graph dataset. If all graphs in a specific dataset are amenable, sufficiently expressive MPNNs can distinguish all non-isomorphic graphs within that dataset (and also distinguish them from non-isomorphic graphs outside of the dataset) in theory. It is shown that in three molecule datasets almost all graphs are amenable. And that a 1-WL approximation of random walk encodings gives the same gain as the encodings themselves, suggesting that the gain comes from the inductive bias.
Critical strengths
The paper is well written and easy to follow for the most parts.
Critical weaknesses
The contribution of the paper is very limited. For most parts it is also not clear what the contribution is: The paper mainly builds on [Arvind et al., 2015], where amenability and the running time for testing amenability are already established, yet the paper claims this as their contribution.
While the paper itself is well written, I find the structure strange, it is not motivated why Sections 3.2 and Section 4 are part of the paper, especially since Section 4 seems to contain only results from Arvind et al., 2015. There is also a justification paragraph at the end of many sections which could be integrated into the text more naturally.
Questions for authors
Q1: Can you state for the contributions of your paper how they differ from [Arvind et al., 2015]?
Q2: Even if not all graphs in a dataset are amenable, it could be that no confusers are present in the dataset, and thus MPNNs can distinguish all graphs (and in practice this is often the case [Zopf, 2022]). Therefore, looking just at "can 1-WL distinguish all graphs in the dataset", we can determine that accuracy gains only come from modeling choices and not from expressivity gains. If we, however, look at amenability, could we not be misled to think that more expressivity is needed for that dataset (as not all graphs in the dataset are amenable), while it is not, making it actually harder to attribute accuracy gains?
Response to Rebuttal
I thank the reviewers for their answers. However, they do not address my concerns regarding novelty and presentation of the contributions beyond from Arvind et al.:
In the paper, the algorithm is present as in a way that makes it seem like a new contribution. Although the authors mention that the algorithm was proposed by Arvind et al., I do not think this sufficiently distinguishes their contributions from the existing results. If the algorithm and its theoretical properties are already established in Arvind et al. (2015), I do not see why they need to be presented as a contribution of the paper and even listed in the contribution section.
Also, my second question is not answered. Consider a dataset, in which 1-WL can distinguish all graphs (in both train and test set), while not all graphs in the dataset are amenable. Looking only at amenability, could we not incorrectly conclude that a method performs better because it is more expressive? I agree that only looking at collisions in the training set is also problematic, but my above concern is different from this problem.
Based on your answer, another question came to my mind: Are there actually real-world examples of confusers in test set? The existence of possible confusers does not necessarily imply that they will likely occur in the underlying data distribution. I think this important, since amenability is motivated as a measure for guiding design choices.
Having read also the concerns of the other reviewers, I will keep my score.