Maximally Expressive GNNs for Outerplanar Graphs

Thank you very much for your review and comments.

Weakness 1:

Authors only compare the CAT with the non-CAT version on MPNN. I believe more baseline models need to be included for completeness. It would be great to see pre-processing cost + training/inference cost + performance comparison on different baseline methods like subgraph-based GNNs and high-order GNNs.

Please refer to the global response regarding additional experiments. We intend to include at least one additional baseline and include these metrics.

Weakness 2:

Authors claim CAT can help alleviate the problem of over-squashing and improve the performance of long-range tasks. However, no evaluations are performed. I believe some experiments should be conducted, like datasets in Long-Range Benchmarks [1].

In the current submission, we focus on maximizing the expressivity on outerplanar graphs. In Table 3 we provide first evidence that $\text{CAT}$ typically reduces the diameter and the effective resistance of the graphs. However, as $\text{CAT}$ is not designed specifically for this, we see further investigation into whether $\text{CAT}$ can help reduce oversquashing and long range tasks in general as future work.

Question 1:

Can the authors explain why the CAT achieved worse performance than the original one in MOLLIPO and MOLTOX21?

Unfortunately, we do not have insights on why $\text{CAT}$ performs worse on these datasets. Overall it is difficult to say why certain models do not perform well on certain datasets and it often requires more insight in both the dataset and the task at hand, as well as the strengths and weaknesses of the model. Our goal was not to achieve state-of-the-art performance on all datasets. Instead we show that $\text{CAT}$ in most cases increases the performance for commonly used datasets with outerplanar graphs (ZINC and the $8$ MOL- datasets from OGB).

Thank you very much for your review.

Weakness Scholarship:
We address [1] in an answer to all reviewers, but we would be happy to address any further comments you may have. We would like to emphasize that while we focus on the smaller group of outerplanar graphs, our pre-processing works in linear time.

Weakness Technically Incorrect Statements:

Technically incorrect statements: There are many hand-wavy and sometimes incorrect statements.

We are happy to clarify any issues and provide more details if some statements were unclear. Please point us to additional statements you find hand-wavy or even incorrect, besides the one regarding the WL-dimension.

Regarding the latter statement, we have to disagree. There seems to be a small misunderstanding between the WL-dimension of outerplanar graphs and the WL-dimension of planar graphs. We purposely cited Kiefer's PhD thesis [2] instead of [3], as only her thesis contains a result specifically for outerplanar graphs. In particular, Corollary $7.40$ [2] states that the WL-dimension of outerplanar graphs is $2$. Note that what Kiefer calls WL is in the GNN literature typically called FWL (folklore WL). This means that $2$-FWL is necessary (i.e., $1$-WL / color refinement is not enough) and sufficient ($3$-FWL is not required) for outerplanar graphs. Furthermore, 2-FWL is equivalent to what the GNN community calls 3-WL. By the known equivalence of, e.g., $3$-WL-GNNs / $3$-IGN to $3$-WL and hence $2$-FWL, we see that the two mentioned GNNs are the $k$-IGN / $k$-WL-GNNs variants with minimum $k$ that one would need to distinguish all outerplanar graphs. Note that they have a runtime of roughly $\mathcal{O}(n^3)$.

By contrast, [3] shows that the WL-dimension of planar graphs is at most $3$ (and it is still open whether it could be $2$). Hence $3$-FWL and $4$-WL are sufficient to distinguish all planar graphs. By the previous explanation, this would require (as long as it remains open whether the WL-dimension is $2$ or $3$) to use $4$-IGNs / $4$-WL-GNNs, with an impractical runtime of roughly $\mathcal{O}(n^4)$.

Weakness Significance and Novelty:

My biggest concern is that there are complete neural models on planar graphs, which are also very scalable.

To the best of our knowledge, there are no linear-time complete models for outerplanar graphs except $\text{CAT}$. PlanE requires quadratic time preprocessing (see global response).

The other technical contributions amount to arguing about shortening the propagation distance in the graph for better information flow. I find this analysis somewhat weak, because this effect can be trivially achieved by adding a virtual node or alike. It appears tangential to the study.

This can indeed be trivially achieved with a virtual node or with other graph rewiring methods. However, the main goal of $\text{CAT}$ was to improve expressivity. As $\text{CAT}$ adds nodes and edges to the graph, we wanted to analyze how this affects other graph properties important for learning. As such, we believe that showing that $\text{CAT}$ does not increase the diameter arbitrarily (and actually decreases diameter and average effective resistance in practice) is a useful result. After all, our analysis shows that it is not necessary to employ methods like virtual nodes in conjunction with $\text{CAT}$.

Weakness Baselines:
We are in the process of conducting additional experiments (see global response).

[1] Dimitrov et al., PlanE: Representation Learning over Planar Graphs. NeurIPS 2023.
[2] Sandra Kiefer, Power and limits of the Weisfeiler-Leman algorithm, PhD Thesis at RWTH Aachen, 2020.
[3] Kiefer et al., The Weisfeiler-Leman Dimension of Planar Graphs is at most 3, LICS 2017

Thanks again for the feedback on our submission. We hope we addressed your concerns and are happy to discuss or clarify further. In particular, we discussed PlanE and added a dataset with over 250k molecules (ZINC 250k) in our global reply above.

Thank you very much for your review and remarks, which we are happy to discuss.

Weakness 1. Improve presentation:

We will improve the presentation as suggested and motivate the two theorems better.

Weakness 2. Discuss more (theoretical) limitations. Does Theorem 2 hold true for general planar graphs, why or why not?

Currently, we have not investigated whether planar graphs in general can be distinguished by $\text{CAT}$. However, we conjecture that WL+$\text{CAT}$ cannot, since the biconnected components in general planar graphs do not necessarily have a unique Hamiltonian cycle. However, $\text{CAT}$ can also be applied to non-outerplanar graphs and potentially increase the expressivity. Additionally, we have first ideas how to generalize $\text{CAT}$ to distinguish all ($k$-outer)planar graphs (see answer to Reviewer DwdD, Weakness 3.).

Thank you again for your review! We hope that we could resolve all of your questions.

Thank you very much for the review. We address some of your remarks in our global reply to all reviewers, but we would be very happy to discuss any additional comments you may have.

Weakness 1. (Theoretical) comparison to PlanE: We address the PlanE paper in detail in our answer to all reviewers and will include it in the related work in the final submission.

Weakness 2. More experiments: We will include further experiments in the final version, please also refer to the answer to all reviewers regarding additional experiments.

In Table 4, GAT+$\text{CAT}$ consistently underperforms GAT on most datasets. Such a degrade performance brought by $\text{CAT}$ is strange compared to that in GIN/GCN. Could you provide further explanation on this phenomenon?

We are also surprised of the performance of GAT+$\text{CAT}$ on these datasets. Note however, that we could significantly boost the performance of GAT on ZINC. In particular, commonly reported test MAE values for ZINC are around $0.475$ [1]. By contrast we achieve a performance of $0.375$ for GAT alone and of $0.201$ for GAT+$\text{CAT}$. We leave further investigation for future work.

In recent years, there exist advanced GNN variants with linear complexity.

We would be happy to discuss these GNNs in our work. However, we are not aware of such GNNs. Most recent GNNs that we are aware of, in particular ones that are more expressive than MPNNs (e.g. ESAN, CIN, subgraph based GNNs, ...), have superlinear complexity for pre-processing and/or message passing. Could you please tell us what you had in mind?

The scale of chosen benchmarks is limited. From Table 1, we can see that there also exist large-scale molecule datasets (>100k) suitable to verify the approach for outplanar graphs. It is highly recommended to conduct more experiments on more large-scale datasets to see whether the proposed approach can consistently bring gains in this setting.

We are in the process of implementing further experiments on this (see global response) and will let you know once we have results.

[1] Dwivedi et al., Benchmarking Graph Neural Networks, JMLR 2022.

Thank you again for your review! We hope that we could resolve all of your questions. In particular, we discussed PlanE and added experiments on a larger dataset with over 250k molecules (ZINC 250k) in our global reply above.

Thank you very much for the review and remarks, which we are happy to discuss.

Weakness 1. Related Work: Thank you for your remarks regarding [1]. Yes, we are happy to extend our discussion of [1] in the related work in the final version of our submission. Most importantly note that all GNNs discussed in [1] have a time complexity of roughly $\mathcal{O}(n^2)$, while our approach has linear time complexity for both pre-processing and message passing. Additionally, we would like to point out that merely identifying block and cut vertices (and edges etc.) is not enough to distinguish outerplanar graphs. For example, the two non-isomorphic biconnected outerplanar graphs in our Figure 1 (as undirected graphs) have the same block-cut-vertex-trees (actually just one node).

Moreover, it is worth noting that [1] proposes an architecture that relies on a transformer backbone, while $\text{CAT}$ is a graph transformation (i.e., a simple pre-processing), which allows for maximally expressive MPNNs (and any GNN that has at least WL expressivity) on outerplanar graphs. We address the relation to the PlanE paper in our answer to all reviewers and will include a discussion thereof in the related work section of our final submission.

Weakness 2. Intuition: We will add a thorough description of the intuition of $\text{CAT}$ to the appendix and include further examples.

While it has indeed shown that the separation power is improved, significantly changing the structure of the input graph may result in some drawbacks.

One possible drawback we considered was that $\text{CAT}$ might reduce graph connectivity. That is why we included an empirical analysis (Table 3) plus some theoretical guarantees (Proposition 1). We prove that even in the worst case $\text{CAT}$ never increases the diameter by more than 7. In the empirical analysis we actually observe that connectivity (in terms of average pairwise effective resistance and diameter) decreases in almost all cases. Could you please clarify which other drawbacks are meant here?

Can the approach be extended to node classification?

Yes, there is a straightforward extension of our approach to node classification: after the message passing of the MPNN it suffices to apply a multilayer-perceptron to the node representation of the node we want to classify. This has not impact on the theoretical guarantees of $\text{CAT}$. For the two example graphs from Figure $1$, $1$-WL cannot distinguish the nodes of degree $3$ between the two graphs. With $\text{CAT}$, however, these nodes can be distinguished.

Thank you again for your review! We hope that we could resolve all of your questions. In particular, we discussed PlanE and added experiments on a larger dataset with over 250k molecules (ZINC 250k) in our global reply above.