- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper presents a novel method in addressing a critical issue in the expressiveness of GNN (Graph Neural Networks). They introduce the fundamental limits of MPNN (message passing neural networks) in its expressiveness and found out the issue with an existing method in bridging the expressiveness gap (RNI, random node initialization). They then fixed this gap with ICON (ID-Invariance through Contrast), and provided empirical and theoretical analyses on how and why practical models fail to learn invariance with the added expressiveness property and how ICON learns these behaviors.
Critical strengths
- substantial improvements over the baseline RNI results in many axes
- good theoretical analyses
- clean writing
Critical weaknesses
- mixed improvements compared with baseline GNNs (GraphConv, GIN, GAT, TransformerConv, and GraphGPS without RNI and ICON): I am not observing significant improvements to the baseline methods. The performance of the models in table 2 are mostly just matching regular baseline GNNs without the author's methods, and that actually adding the expressive baseline method (RNI) for becoming more expressive hurts most of the time. This entails a question that, if the expressive baseline is significantly worse than the baseline GNNs and the authors just try to fix the expressive baseline to match the baseline GNNs, what's the right interpretation on the benefits that this paper introduces? Why do we need this method if it is a "fix" to a bug in the expressive baseline?
- Convergence and Generalization claims: I am not seeing the matched comparison with baseline GNNs.
Questions for authors
- Can you explain why ICON helps very little with downstream graph task performance (compared with GNN baseline)? I am seeing Table 2 showing mixed improvements on various tasks compared with baseline GNN methods(GraphConv, GIN, GAT, TransformerConv, and GraphGPS). It would also be nice if the authors can report the compute and flop required for training the methods so that we can be certain on the validity on the comparison.
- Regarding the claim on faster convergence: could you also compare with GNN baseline?
- It'd be nice if the authors could justify why it is so critical to be more expressive with a GNN method, when its performance only matches that of the baseline GNN methods. The added benefits are on generalization and convergence speed, but it is not cleanly compared with baseline GNNs.
Thank you for your comment. My concern is that the experimental comparisons primarily rely on RNI (2021) as the node ID-based baseline, while most of the evaluated GNN architectures date back to 2022 or earlier. Both the related work discussed in the manuscript and more recent studies suggest relevant alternatives for comparison, such as A Systematic Approach to Universal Random Features in Graph Neural Networks (TMLR 2023), On the Expressivity and Sample Complexity of Node-Individualized Graph Neural Networks (NeurIPS 2024), and Expressive Graph Neural Networks via Equivariant Use of Noise (ICML 2026).