- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper argues that strict permutation equivariance is often overly restrictive, since many real-world graphs carry order information in their nodes. The authors introduce Partially Ordered Graphs (POGs) and propose the Partially Ordered Graph Neural Network (POGNN), which combines conventional graph convolution with a DAG convolution. They theoretically establish that POGNNs are equivariant exactly to the automorphism group of the chosen poset instead of the full symmetric group, enabling a tunable relaxation of permutation equivariance. Experiments on six biochemical graph-level benchmarks show that their performance gains of POGNN depend on the choice of a task-aligned partial order.
Critical strengths
- The paper targets an important and widely recognized limitation: strict permutation equivariance is not always the most appropriate inductive bias. The authors explore posets, which offer a middle ground between unordered node sets and totally ordered node sequences. The proposed POGNN architecture makes a potentially valuable contribution by combining graph and DAG convolutions, supported by a formal characterization of equivariance under poset automorphisms.
- Theorem 1 provides a rigorous guarantee that the relaxation of permutation equivariance is structural and exact, rather than approximate or probabilistic, and its strength is directly controlled by the choice of partial order. This distinguishes the approach from symmetry-breaking techniques and strengthens its theoretical significance.
- The virtual-node comparison in the experiment demonstrates that the performance gains arise from the order-based inductive bias rather than merely from introducing additional long-range shortcuts.
Critical weaknesses
- The authors state that they train "POGNN with every candidate order over five seeds and report the one with the best mean test performance." Selecting the best configuration based on test performance introduces selection bias and potentially leaks information from the test set. Because ordering is central to the proposed method, and the reported improvements over baselines are often modest, it is difficult to determine how much of the observed improvement reflects actual performance gains rather than selection noise.
- The reported standard deviations on the TU datasets are substantial, such as 11.1 for POGNN vs. 5.0 for GRIT on MUTAG, and 9.3 for POGNN vs. 4.2 for GIN/GINE on ENZYMES. Given the small dataset sizes and high result variance, the performance gain is not sufficiently supported from a statistical perspective.
- All orders are based on heuristics (e.g., electronegativity, SSE type, Morgan invariants), and the results on MUTAG illustrate a potential limitation: when none of the candidate orders is well suited to the task, the proposed method may underperform. Furthermore, all six evaluated datasets are biochemical graph-level tasks. The paper does not discuss whether the proposed framework can generalize to other domains and leaves its broader applicability empirically unverified.
Questions for authors
My questions and concerns mainly focus on the experimental part. I believe that the experimental evaluation requires substantial improvement to convincingly support the paper's claims. Please refer to Critical Weaknesses for the specific issues that need to be addressed. If the authors can adequately address these concerns and provide stronger empirical evidence, I would be willing to reconsider and potentially increase my rating.
We thank the reviewer for their feedback. Here, we try to respond to the weaknesses point by point.
[W1] This was definitely an error in our experimental protocol which a reviewer at a NeurIPS workshop pointed out. We were able to rerun all the experiments selecting partial order based on validation data. The updated table results are provided in Table 1 of the revised manuscript (also reproduced below).
Table: Bold: best; italic: second; †: third. Mean ± standard deviation over 5 seeds (10 folds on TU datasets). The partial order for each POGNN variant is selected on validation performance. (*): results taken from the original papers. On MUTAG, three models tie at 85.26 and are ranked by standard deviation.
With the order selected on validation data, a POGNN variant ranks first on four of six datasets (ENZYMES, PROTEINS, OGBG-MolHIV, Peptides-struct) and second on Peptides-func, and POGatedGCN improves over its GatedGCN backbone on five of six datasets.
[W2] With the corrected experimental protocol, the standard deviations have been lowered but they remain high. This is known in the literature for the TU datasets [1, 2, 3, 4, 5] that’s why we focus only on average accuracy for these datasets.
[W3] Indeed, this is a missing discussion in our current submission. Hence, we add the limitations of the proposed approach when no partial order is available in the conclusion of our revised manuscript.
[1] Xu, K., Hu, W., Leskovec, J., & Jegelka, S. (2019). How Powerful are Graph Neural Networks? In International Conference on Learning Representations (ICLR 2019). arXiv:1810.00826
[2] Maron, H., Ben-Hamu, H., Shamir, N., & Lipman, Y. (2019). Invariant and Equivariant Graph Networks. In International Conference on Learning Representations (ICLR 2019). arXiv:1812.09902
[3] Maron, H., Ben-Hamu, H., Serviansky, H., & Lipman, Y. (2019). Provably Powerful Graph Networks. In Advances in Neural Information Processing Systems 32 (NeurIPS 2019). arXiv:1905.11136
[4] Bevilacqua, B., Frasca, F., Lim, D., Srinivasan, B., Cai, C., Balamurugan, G., Bronstein, M. M., & Maron, H. (2022). Equivariant Subgraph Aggregation Networks. In International Conference on Learning Representations (ICLR 2022). arXiv:2110.02910
[5] Papp, P. A., Martinkus, K., Faber, L., & Wattenhofer, R. (2021). DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networks. In Advances in Neural Information Processing Systems 34 (NeurIPS 2021). arXiv:2111.06283