acceptodds
Under review as a conference paper at ICLR 2027

Relaxing Permutation Equivariance in Graph Neural Networks

Abstract

Graph Neural Networks (GNNs) have been established as powerful methods for learning functions on graph-structured data, in which nodes carry no canonical ordering. Permutation equivariance to node index relabelling is therefore a defining inductive bias of GNNs. We argue that the representation of nodes in sets is limiting. We propose an alternative approach that represents and learns on observed graphs, in which nodes are augmented with one or several partial orders. Leveraging the equivalence between partially ordered sets and Directed Acyclic Graphs (DAGs), we introduce a new data structure called Partially Ordered Graphs (POGs). Building on theoretical work defining convolution operators on DAGs, we construct the Partially Ordered GNN (POGNN) architecture which combines trainable convolutions on both the node partially ordered sets and the underlying observed graph. We also prove that our POGNNs relax the permutation equivariance assumption of traditional GNNs in a tunable manner by being equivariant to the automorphism of the poset. The choice of partial order allows us to cover the full spectrum from node sets to node sequences. In practice, we demonstrate that our model improves the performance of traditional GNN approaches on several graph-level biochemical benchmark datasets.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Neural Networks, Permutation Equivariance, Symmetry Breaking, Partially Ordered Sets

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_8MFKOpenReview ↗
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
  1. 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.
  2. 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.
  3. 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
  1. 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.
  2. 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.
  3. 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.

1 comment

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.

ModelMUTAG (ACC ↑)ENZYMES (ACC ↑)PROTEINS (ACC ↑)OGBG-MolHIV (ROC-AUC ↑)Peptides-func (AP ↑)Peptides-struct (MAE ↓)
GIN / GINE82.11 ± 3.4959.33 ± 5.0171.88 ± 3.0776.8 ± 1.00.6612 ± 0.0067 (*)0.2473 ± 0.0017 (*)
(+) Virtual Node81.05 ± 6.7465.83 ± 6.1172.14 ± 3.14 †77.1 ± 1.70.6576 ± 0.00940.2570 ± 0.0029
GatedGCN85.26 ± 3.16 †64.83 ± 4.3170.00 ± 5.1976.2 ± 0.90.6765 ± 0.0047 (*)0.2477 ± 0.0009 (*)
(+) Virtual Node85.26 ± 5.6763.17 ± 4.5071.96 ± 4.8979.1 ± 0.90.6822 ± 0.0052 (*) †0.2458 ± 0.0006 (*)
GPS85.26 ± 3.9462.50 ± 7.6171.51 ± 3.4078.8 ± 1.00.6534 ± 0.0091 (*)0.2509 ± 0.0014 (*)
GRIT83.16 ± 5.6767.50 ± 3.59 †73.35 ± 1.8277.4 ± 1.10.6988 ± 0.0082 (*)0.2460 ± 0.0012 (*) †
POGIN / POGINE84.73 ± 4.9767.83 ± 5.6871.9 ± 2.077.3 ± 3.80.6610 ± 0.00490.2469 ± 0.0029
↳ selected orderelectronegativitySSE typeSSE typeelectronegativityelectronegativityelectronegativity
POGatedGCN84.73 ± 4.3768.33 ± 5.9671.1 ± 4.679.7 ± 2.30.6829 ± 0.00400.2451 ± 0.0017
↳ selected orderelectronegativitySSE typeSSE typeelectronegativityelectronegativityelectronegativity
POGPS84.73 ± 6.4266.17 ± 6.1573.39 ± 2.5578.9 ± 3.2 †0.6741 ± 0.00310.2591 ± 0.0047
↳ selected orderelectronegativitymedium polaritySSE typeatomic numberelectronegativityatomic number

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

Reviewer_atjMOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes Partially Ordered Graphs, which augment an observed graph with an auxiliary partial order over its nodes. Its POGNN architecture combines conventional graph layers with DAG convolutions derived from this order, using feature-conditioned filters that support graphs of different sizes. Theorem 1 characterizes the guaranteed equivariance group when the partial order is held fixed. Experiments evaluate chemically motivated orders on six biochemical graph benchmarks, alongside graph neural networks, graph transformers, alternative symmetry-breaking methods, and alternative DAG layers. Reporting the best-performing order for each dataset, the paper finds POGNN ahead of GIN/GINE and GatedGCN on all six datasets and best overall on PROTEINS, ogbg-molhiv, and Peptides-struct.

Critical strengths

The architecture offers a concrete way to incorporate domain-informed partial orders. Combining an observed graph with an auxiliary DAG allows relational connectivity and ordering information to influence representations through separate branches. The shared, feature-conditioned filter construction makes this approach applicable across graphs with different numbers of nodes.

A useful characterization of guaranteed symmetries for a fixed poset. Theorem 1 addresses both equivariance under Aut(P) and the maximality of this guaranteed group across the architecture family when P is held fixed. This gives a precise account of how the auxiliary order constrains the architecture’s symmetries. The core argument appears repairable through local proof corrections, including the ReLU step in Appendix E. Its relevance to the complete experimental pipeline requires separate clarification.

Critical weaknesses

The central symmetry claim is not established for the complete pipeline used experimentally. Theorem 1 explicitly holds the poset fixed. In the experiments, however, orders are constructed from graph-associated quantities such as atomic number, electronegativity, or SSE type. Under consistent node relabeling, these quantities and the resulting DAG relabel together. The POGNN layer (Eqs. 3–4) is equivariant under that joint transformation; this is the same algebra as the proof of Theorem 1(i), and the form in which Rey et al. (2026) state their equivariance result. Consequently, a pipeline using a permutation-consistent order constructor remains fully permutation equivariant. The fixed-poset characterization therefore does not establish that the experimental pipeline relaxes equivariance to arbitrary node relabeling. A standard GNN given the same attributes as input features already has the same per-input symmetry; the paper’s own Fig. 1 shows this, since panels (b) and (c) admit the same valid permutations. The proposed architecture may still introduce a useful inductive bias, but the paper needs to distinguish that benefit from its claimed relaxation of equivariance. Existing comparisons also do not adequately isolate the effect of the order representation and DAG connectivity from the proposed filtering mechanism.

Partial orders are selected using test performance. Section 6.2, page 9, lines 452–453 explicitly states that the reported order is selected by “best mean test performance.” The order is a consequential model-design choice, so selecting it using test outcomes makes the reported scores optimistically selected estimates. Averaging over five seeds does not remove this bias. Appendix G.3 describes validation-based hyperparameter tuning but does not resolve this separate selection step. Since empirical improvements are a major contribution, validation-based order selection, or selection within the appropriate inner cross-validation loop, is necessary to establish their reliability.

Questions for authors

Q1. What is the group action on the complete experimental input, including the auxiliary order? When an attributed graph is relabeled and its order reconstructed, does the complete pipeline remain fully permutation equivariant? Please reconcile this behavior with the claimed relaxation and the fixed-poset statement of Theorem 1.

Q2. Does “best mean test performance” (Sec. 6.2, L452–453) describe the actual order-selection procedure? If this is a wording error, please provide the validation-based selection rule. Otherwise, how do the results change when orders are selected exclusively using validation data, with selection nested appropriately for the TU datasets? Please also list all candidate orders evaluated for each dataset.

Q3. On a representative subset of the benchmarks, do the gains persist against three controls, all under comparable tuning budgets: models receiving the same ordering quantities as node features, conventional message passing on the same auxiliary DAG, and random orders with matched level sizes? These controls would help establish what the proposed operator contributes.

Q4. Several Table 1 baseline entries coincide exactly, including standard deviations, with published results obtained under other protocols. For example, the GatedGCN and GPS entries on Peptides-func and Peptides-struct match Tönshoff et al. (TMLR 2024, 4 seeds), and the “GatedGCN (+) Virtual Node” row matches the GatedGCN+PE+VN_G variant of Southern et al. (2025). Which baselines were re-run under your protocol, and which were taken from prior work (with source, number of seeds and tuning budget)? Which GNN backbone does POGNN use for each dataset, and does it use positional encodings?

Q5. Luo et al. (2025), which you cite for your hyperparameters, report tuned classic GNNs that match or exceed POGNN on all three large benchmarks (their Tables 3–4):

Peptides-func: GCN+ reaches 0.7261 AP, against POGNN’s 0.6786.

Peptides-struct: GCN+ reaches 0.2421 MAE, against POGNN’s 0.2436.

ogbg-molhiv: GatedGCN+ reaches 80.40 ROC-AUC, against POGNN’s 80.2.

Since these models add residual connections, normalization and positional encodings, could you compare POGNN built on the same enhanced backbone against that backbone alone, under a matched tuning budget? This would show whether the DAG branch adds value beyond a well-tuned baseline.

2 comments

We thank the reviewer for their attentive review. As all critical weaknesses have a corresponding question, we answer the questions only.

[Q1] We thank the reviewer for this careful and correct observation. First, the group action considered is π:(X,A,Ar)→(PπX,  PπAPπ⊤,Ar)\pi : (X, A, A_r) \rightarrow (P_\pi X,\; P_\pi A P_\pi^{\top}, A_r). The partial order plays a similar role as positional encodings in Transformers with more flexibility, i.e., it is unaffected by the permutation action. Besides, your feedback has led us to better characterise POGNN: POGNNs guarantee permutation equivariance for permutations in Aut⁡(P)\operatorname{Aut}(\mathcal{P}) and permutations outside Aut⁡(P)\operatorname{Aut}(\mathcal{P}) are not respected.

[Q2] Indeed, there was an error in our experimental protocol which was pointed out to us by a reviewer at a NeurIPS workshop. We reran every experiment now selecting partial order based on validation data. The updated table results are provided in Table 1 of the submission.

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.

ModelMUTAG (ACC ↑)ENZYMES (ACC ↑)PROTEINS (ACC ↑)OGBG-MolHIV (ROC-AUC ↑)Peptides-func (AP ↑)Peptides-struct (MAE ↓)
GIN / GINE82.11 ± 3.4959.33 ± 5.0171.88 ± 3.0776.8 ± 1.00.6612 ± 0.0067 (*)0.2473 ± 0.0017 (*)
(+) Virtual Node81.05 ± 6.7465.83 ± 6.1172.14 ± 3.14 †77.1 ± 1.70.6576 ± 0.00940.2570 ± 0.0029
GatedGCN85.26 ± 3.16 †64.83 ± 4.3170.00 ± 5.1976.2 ± 0.90.6765 ± 0.0047 (*)0.2477 ± 0.0009 (*)
(+) Virtual Node85.26 ± 5.6763.17 ± 4.5071.96 ± 4.8979.1 ± 0.90.6822 ± 0.0052 (*) †0.2458 ± 0.0006 (*)
GPS85.26 ± 3.9462.50 ± 7.6171.51 ± 3.4078.8 ± 1.00.6534 ± 0.0091 (*)0.2509 ± 0.0014 (*)
GRIT83.16 ± 5.6767.50 ± 3.59 †73.35 ± 1.8277.4 ± 1.10.6988 ± 0.0082 (*)0.2460 ± 0.0012 (*) †
POGIN / POGINE84.73 ± 4.9767.83 ± 5.6871.9 ± 2.077.3 ± 3.80.6610 ± 0.00490.2469 ± 0.0029
↳ selected orderelectronegativitySSE typeSSE typeelectronegativityelectronegativityelectronegativity
POGatedGCN84.73 ± 4.3768.33 ± 5.9671.1 ± 4.679.7 ± 2.30.6829 ± 0.00400.2451 ± 0.0017
↳ selected orderelectronegativitySSE typeSSE typeelectronegativityelectronegativityelectronegativity
POGPS84.73 ± 6.4266.17 ± 6.1573.39 ± 2.5578.9 ± 3.2 †0.6741 ± 0.00310.2591 ± 0.0047
↳ selected orderelectronegativitymedium polaritySSE typeatomic numberelectronegativityatomic number

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.

[Q3] We agree, the original comparisons did not isolate the contributions. We add below a table which corresponds to an ablation study on ENZYMES of the following: (a) backbones with the binned order attribute as an explicit node feature; (b) a conventional MPNN on the same auxiliary DAG; (c) POGNN with a random order; (d) POGNN with partial order selected on validation data.

Table: Mean ± standard deviation over 10 folds.

ENZYMES (ACC ↑)GatedGCNGINGPS
Backbone (Table 1)64.83 ± 4.3159.33 ± 5.0162.50 ± 7.61
(a) Backbone + partial-order rank as feature67.50 ± 6.6654.33 ± 8.8963.67 ± 6.45
(b) POGNN with a GNN as DAG layer65.33 ± 7.7065.00 ± 7.0766.00 ± 9.33
(c) POGNN with a random partial order65.50 ± 6.7153.50 ± 6.9763.50 ± 8.35
(d) POGNN, partial order selected on validation68.33 ± 5.9667.83 ± 5.6866.17 ± 6.15

From this comparison, we observe that on ENZYMES (i) the POGNN improves performance against traditional GNNs with access to the same information and that the chosen partial order is responsible for the improved performance, (ii) the DAG layer is a useful inductive bias compared to a GNN working on the DAG branch.

[Q4] This is definitely a point that is not clear in the previous submission. We add a star to illustrate when the results come from original papers and not from our own experiments. Besides, for reproducibility we provide the best hyperparameters for our architecture for each dataset and variant (Table 6-8) in our revised manuscript.

[Q5] To compare GNN+ to our proposed architecture, we run GCN+ for ogbg-molhiv and peptides-func and GatedGCN+ for peptides-struct and then use these same models with the chosen hyperparameters chosen by Luo et al. (2025). The results are summarised in the following table where the partial order is chosen on validation data,

Table: GNN+ is GCN+ on OGBG-MolHIV and Peptides-func, and GatedGCN+ on Peptides-struct, with the hyperparameters of Luo et al. (2025). For POGNN+, the chosen partial order are the one yielding best validation performance for each dataset.

ModelOGBG-MolHIV (ROC-AUC ↑)Peptides-func (AP ↑)Peptides-struct (MAE ↓)
GNN+ (reported, Luo et al., 2025)80.40 ± 1.640.7261 ± 0.00670.2421 ± 0.0016
GNN+ (our reproduction)77.00 ± 0.780.7148 ± 0.00270.2466 ± 0.0025
POGNN+76.58 ± 1.070.7114 ± 0.00530.2499 ± 0.0037

The conclusion from this table can seem negative however the protocol used implied a bias towards GNN+ baseline as their hyperparameters were used also for the DAG layer component (same hidden size, same use of residual connection or feedforward network …). More careful comparisons are needed to tune the hyperparameters for our method carefully as well but the time schedule of the discussions period does not allow it. We will run this experiment in time for the notification date and add it to the manuscript.

Reviewer_VJZJOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

This paper tackles the challenge of devising more powerful Graph Neural Networks by making them equivariant to a smaller symmetry group than the general assumed one (generic node permutations). The main idea is to pick this group as that of the automorphisms of the Directed Acyclic Graph (DAG) resulting by imposing a partial order on nodes. The authors explain this could result from domain or task knowledge, for example, by fixing an ordering of nodes in molecular graphs based on their atomic type or class.

The authors define a Partially Ordered Graph, that is, a graph augmented with DAG connectivity capturing the partial order imposed on nodes. Then, a subsection on learning on DAGs follow, where the authors propose a specific formalisation of a convolution operator beyond the one proposed by Rey at al. (2026) which decouples the number of learnable parameters and of shift operators from the size of the graph. Based upon this, the authors propose POGNN, an architecture to process Partially Ordered Graphs by stacking layers which execute, in parallel, both the aforementioned DAG convolution and standard graph convolution on the original connectivity. The authors show how this architecture is equivariant to DAG automorphisms, but not necessarily to generic node permutations. After noting the computational complexity of the approach, the authors move to test their architecture in practice.

They experiment with six biochemical datasets from the TUDatasets, OGB and LRGB suites, showing how the best variant of their architecture attains superior performance in three out of six cases. They additionally compare against other symmetry breaking approaches which appear not superior to their method and they finally experiment with other previously proposed DAG operators, with mixed results (app. G.4).

Critical strengths
  • (S1) The main idea behind the paper is somewhat interesting per se
  • (S2) The paper invests a good amount of space to present related works and preliminaries, making the manuscript accessible. The writing style is generally pleasant (although see W2.(i) for presentation)
Critical weaknesses
  • (W1) The main idea behind the paper is clear per se, but the authors do not sufficiently discuss (i) what is the expected advantage of accounting for partial orders in a structural manner beyond simple node feature and (ii) the impact of choosing a certain order w.r.t. another if the feature determining it do not naturally come with one.
    • (i) Concretely, as the authors themselves mention around lines 50-53, node features already break some graph symmetries, and, in fact, graph isomorphisms naturally account for them. Standard GNNs are not equivariant to generic permutations of the (unlabelled) adjacency matrix; they are equivariant to permutations of both the adjacency matrix and the feature matrix (see also lines 167 onwards). Hence, it is not clear why imposing an additional partial order on nodes based on node features should yield more expressiveness.
    • (ii) In the case of categorical node features, there is not necessarily a predefined ordering of features entailing a partial order on nodes: any employed partial order is thus arbitrary and could determine a distinct DAG. The authors do not seem to discuss this aspect and its consequences.
  • (W2) From page 4 to page 6, the authors discuss various choices for DAG design and transitive closures (referencing to DAG signal processing), and present a DAG convolutional layer extending one proposed in a previous work.

Based on my current understanding of the contribution and the above weaknesses I do not think the paper is ready for this conference round.

  • (i) It is not clear how all the introduced design choices and the references to signal processing are then instrumental to layer design. The authors should make a better presentation effort in linking such concepts to theoretical and practical design choices. Is choosing one particular DAG formulation necessary with respect to another or not? Is the use of AcA_c really important or not given one could apparently approximate it with ARA_R (lines 396-402)?
  • (ii) It is not clear if proposing a new DAG convolutional layer should be a contribution of the present paper, beyond the idea of enforcing node partial order to break symmetries. If that is the case, then the authors should definitely motivate its design better and in context with respect to previous works, such as those cited in the related work and used in ablation studies in G.4. What is the idea behind this new construction compared to other previously proposed approach such as DAGNN (to mention one). Is there any particular feature of this layer that makes it more suitable for the main approach presented in the paper? Results in G.4 seem generally mixed (line 468), so they do not give a practical indication either.
  • (W3) I have reservations on the presented experimental results.
    • (i) The authors only report, in the main Table 1, the best results obtained by their method across various choices of partial orders, selected on the test set. This risks overestimating the performance of the proposed approach, it does not allow to capture general trends that could be useful to readers (e.g. whether a certain ordering tends to work better than others), and conceals whether the approach is robust to these choices or not.
    • (ii) It is not clear if baselines have access to the same information used to break symmetries via partial orders. Connecting to W1, I believe this is very important: the authors should make sure the gain comes from the new structural modelling and not from additional information. If such features are already provided sufficiently and comparably well to all baselines (e.g. by providing binning information when necessary), then they should make this point explicit.
    • (iii) It is not clear if the authors are running the standard or approximated version of their architecture (line 398). This is important because having a quadratic complexity would reframe potential gains over standard message passing networks with linear complexity, and bring to attention cases where the model is outperformed by transformers.
Questions for authors

Please see Weaknesses. Also:

  • (Q1) Is Theorem 1 really informative if the partial order is derived directly from node features? Wouldn't it just recover standard GNN equivariance in that case?
  • (Q2) What is even the point of considering GNNs without node features in Figure 1 and contrasting them with GNNs with node features? Why should one even account for this?
4 comments

We thank the reviewer for carefully analysing our work. Here, we respond to the weaknesses and questions point by point.

[W1 (i) + Q1] An intuitive way to think of what the partial order contributes in our architecture to make an analogy with positional encodings in Transformers. Our partial order “indexes” nodes in the original graph and hence POGNNs are not permutation-equivariant to permutations outside of Aut⁡P\operatorname{Aut}{\mathcal{P}}. Therefore, even if partial order are derived from node features the equivariance is relaxed from SnS_n to Aut⁡P\operatorname{Aut}{\mathcal{P}} (with in this case Aut⁡G⊆Aut⁡P\operatorname{Aut}{\mathcal{G}} \subseteq \operatorname{Aut}{\mathcal{P}}). Ideally one would obtain such partial orders from extraneous sources, not the features. But even when obtaining the orders from the features, one can benefit from our framework by binning continuous features, where the bin width determines the degree to which we allow a given feature to relax permutation-equivariance.

[W1 (ii)] Our proposed approach assumes a partial order on nodes. In our experiments, such partial orders were feature-induced, but categorical features are indeed not order-inducing. In practice, our architecture is well motivated in cases where partial orders are either feature-induced or available from an extraneous source. We have added this point to the conclusions of our revised manuscript.

[W2 (i) + W3 (iii)] We explain our choice of transitive closure, and hence the formulation of AcA_c, in the paragraph Transitive Closure Choice (line 239). We thank the reviewer for pointing out that it is indeed not clear which version of our architecture we use for the experiments, and we have added this to the experiments section (line 396) of our revised manuscript. We are more than happy to further edit the manuscript if the reviewer sees potential for clarification.

[W2 (ii)] Our main contribution is the POG data structure and correspondingly POGNNs, the DAG layer in POGNNs is a sound default with nice theoretical grounding. With it, we contribute a parametrisation independent of graph size. But we cannot claim superiority of the DAG convolution layer over all DAG models, as visible in Appendix G.4 of our submission. We prefer to keep the question of which DAG layer is most appropriate on which dataset out of scope for our submission since it moves away from our central question on permutation relaxation.

[W3 (i)] Thank you for your observation. Shortly after the submission deadline, a reviewer at a NeurIPS workshop identified this error in our protocol and we reran every experiment. We now select the partial order on the validation set. The updated table results are provided in Table 1 of the submission (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.

ModelMUTAG (ACC ↑)ENZYMES (ACC ↑)PROTEINS (ACC ↑)OGBG-MolHIV (ROC-AUC ↑)Peptides-func (AP ↑)Peptides-struct (MAE ↓)
GIN / GINE82.11 ± 3.4959.33 ± 5.0171.88 ± 3.0776.8 ± 1.00.6612 ± 0.0067 (*)0.2473 ± 0.0017 (*)
(+) Virtual Node81.05 ± 6.7465.83 ± 6.1172.14 ± 3.14 †77.1 ± 1.70.6576 ± 0.00940.2570 ± 0.0029
GatedGCN85.26 ± 3.16 †64.83 ± 4.3170.00 ± 5.1976.2 ± 0.90.6765 ± 0.0047 (*)0.2477 ± 0.0009 (*)
(+) Virtual Node85.26 ± 5.6763.17 ± 4.5071.96 ± 4.8979.1 ± 0.90.6822 ± 0.0052 (*) †0.2458 ± 0.0006 (*)
GPS85.26 ± 3.9462.50 ± 7.6171.51 ± 3.4078.8 ± 1.00.6534 ± 0.0091 (*)0.2509 ± 0.0014 (*)
GRIT83.16 ± 5.6767.50 ± 3.59 †73.35 ± 1.8277.4 ± 1.10.6988 ± 0.0082 (*)0.2460 ± 0.0012 (*) †
POGIN / POGINE84.73 ± 4.9767.83 ± 5.6871.9 ± 2.077.3 ± 3.80.6610 ± 0.00490.2469 ± 0.0029
↳ selected orderelectronegativitySSE typeSSE typeelectronegativityelectronegativityelectronegativity
POGatedGCN84.73 ± 4.3768.33 ± 5.9671.1 ± 4.679.7 ± 2.30.6829 ± 0.00400.2451 ± 0.0017
↳ selected orderelectronegativitySSE typeSSE typeelectronegativityelectronegativityelectronegativity
POGPS84.73 ± 6.4266.17 ± 6.1573.39 ± 2.5578.9 ± 3.2 †0.6741 ± 0.00310.2591 ± 0.0047
↳ selected orderelectronegativitymedium polaritySSE typeatomic numberelectronegativityatomic number

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.

[W3 (ii)] When partial orders are constructed directly from the original feature values, without binning, then the baselines have access to the same information. However, indeed when binning is applied then we run an ablation study on ENZYMES when baselines are provided with an additional feature value that corresponds to the order of the node in the partial order (provided below).

Table: Mean ± standard deviation over 10 folds.

ENZYMES (ACC ↑)GatedGCNGINGPS
Backbone (Table 1)64.83 ± 4.3159.33 ± 5.0162.50 ± 7.61
Backbone + partial-order rank as feature67.50 ± 6.6654.33 ± 8.8963.67 ± 6.45
POGNN variant68.33 ± 5.9667.83 ± 5.6866.17 ± 6.15

Even with the partial order rank provided as a feature to the GNNs baselines, the POGNN approaches still outperform them on average, most clearly for GIN and GPS.

[Q2] We use this figure to illustrate the alternative approaches via features and structure.

Reviewer_VJZJOpenReview ↗

Response to Rebuttal

Thank you for your direct and concise rebuttal. While some points (e.g. experimental details) appears clearer to me, I still believe the points on the relation with node features, and with other DAG layers are to be better discussed and in a more explicit and contextualised way. I believe my current score is still representative of my acceptance recommendation.

Thank you very much for taking the time to consider our revised manuscript and for your clarifications.

Relation to node features. When the order is derived purely from node features as in Figure 1, POGNNs indeed do not relax the symmetry of the input: the automorphism group of the poset is the same as that of the features, so no new symmetry is broken. However, the relaxation is on the network, which only needs to be equivariant to Aut⁡(P)\operatorname{Aut}(\mathcal{P}) instead of SnS_n (Theorem 1). We make this explicit in the introduction (lines 086-090) of our revised manuscript.

Other DAG layers. In our revised manuscript, our DAG layer is presented as a sound default without any claim of superiority, and we leave a systematic comparison of DAG layers to future work in the conclusion. We also added this precision at the beginning of section 5.1 (lines 262-265). We are again more than happy to further edit the manuscript if the reviewer sees potential for clarification.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.