Efficient Redundancy-Free Graph Networks: Higher Expressiveness and Less Over-Squashing

We express our sincere gratitude to the reviewer for their constructive review. We highly value their feedback and have diligently addressed their concerns by extensively revising the entire manuscript to ensure that the manuscript meets the standards of a qualified and reader-friendly publication.

We ask the reviewers for their patience and kindness in dealing with this revised manuscript.

[W1]

We have already discussed how our models can reduce the over-squashing problem in Appendix C of our previous manuscript. That message passing with redundancy can lead to the over-squashing problem was discussed in the Introduction section (in the middle of the first paragraph on page 2). Chen et al. ¹ show that a redundancy-free message passing scheme can ensure that only one message passing path captures each path, thus addressing the imbalance in the number of message passing paths generated from different paths and mitigating the over-squashing problem. For the same reason, our ERFGN model can mitigate the over-squashing problem. Our experiments demonstrate that DLGN outperforms typical MPNNs, higher order MPNNs, and graph transformers on MNIST, CIFAIR10, and Peptides-func. While DLGN cannot achieve higher expressiveness because it doesn't address the message confusion problem caused by native cycles, it still benefits from the reduced over-squashing problem. These experimental results support the advantages of mitigating over-squashing.

We agree that it is important to include a clear explanation of how to reduce over-squashing. We incorporated a detailed explanation of how our models mitigate over-squashing in Section2.7 of the revised manuscript. Additionally, we discussed the benefits of mitigating over-squashing in the Experiments section (experiments on MNIST, CIFAR10, Peptides-func and Peptides-struc).

[W2]

We appreciate the reviewer's comment on the comparison with conventional GNNs using k-WL. In the revised version of our manuscript, we have included a lemma in Section 2.6 that highlights the increased power of our model compared to the 3-WL test. We have also provided proof in the appendix (on page 21) to support this claim.

[W3]

We appreciate the feedback and have diligently rewritten the entire manuscript to ensure its correctness and clarity.

[Q1]

In the revised manuscript, we have included a detailed explanation of how our models mitigate over-squashing in Section2.7 and discussed the benefits of mitigating over-squashing in the Experiments section.

[Q2]

We apologize for the confusion caused by our incorrect presentation. Actually, the graph radius determines the minimum number of message passing iterations required to transfer information from all nodes in a connected graph to a certain node and to express all paths of the connected graph. It also determines the minimum number of layers of DLGN or ERFGN to achieve their full potential expressiveness, respectively. We have corrected this error in our revised manuscript.

[Q3]

We aim to propose an efficient method to achieve redundancy-free message passing. It has been discussed in Introduction (first paragraph on page 2) that RFGNN[1] is the first previous work that achieves redundancy-free, but it faces complexity challenges. Our proposed methods offer improved efficiency compared to RFGNN.

We have added a checklist row to Table 1 to indicate whether or how well a method can address redundancy. In addition, we have made our motivation and contributions more clear in the revised manuscript.

[W1]

We sincerely appreciate the reviewer's suggestion to discuss and compare alternative approaches for reducing message redundancy. We have included a brief discussion and a comprehensive discussion of alternative approaches in Introduction (2nd paragraph of page 2) and in the related works section (Appendix A). This addition strengthens the context and significance of our research.

The experimental results of PathNNs have been included in our experimental section and compared with other methods. However, SPAGAN focuses on node classification tasks, which are quite different from ours, i.e., graph-level predictions. And their codes could not be used directly for graph-level predictions. Therefore, SPAGAN is not compared in our experiments.

[W2]

We have thoroughly revised and expanded the proofs in Appendix C.2 of our revised paper to ensure they are detailed and complete.

[W3]

The complexity analysis we performed considered the worst-case scenario, assuming that the cyclic subgraph is a complete graph. So $|V_C|$ path trees are extracted, each root node has $|V_C|-1$ child nodes, and each child node has $(|V_C|-2)$ 2-order child nodes, and so on.

However, real-world graphs, such as molecules, are often sparse and consist of small, biconnected components, which would not result in very high complexity.And we have drawn a more precise analysis: Let $V^{\circ}$ be the nodes of the cyclic subgraph, and $d^{\circ}$ be the maximum node degree. The extracted path trees consist of $|V^{\circ}| \times d^{\circ}!$ nodes and edges at worst. Therefore, $|V^{\circ}|$ path trees are extracted, where each root node at worst has $d^{\circ}$ child nodes, and each child node has $(d^{\circ}-1)$ 2-order child nodes, and so on. Thus, for ERFGN, the path tree extraction, as well as the sub-DALG construction, has a complexity of $\mathcal{O}\left(|E|+|V^{\circ}| \times d^{\circ}!\right)$.

[W4]

We appreciate the question regarding our method's suitability for dense graphs. To address this, we are exploring adaptations such as graph decomposition. Following the success of ESAN[^1], we can decompose a dense graph into multiple spanning trees and repeat the process with new spanning trees to obtain topological properties while handling dense graph complexities. We would like to investigate this problem further and welcome any suggestion from the reviewer.

[W5]

Our proposed architectures exhibit complexity due to the need to model global interactions between different pairs of nodes and cycles. To address this complexity, we have developed two global attention schemes: a 1-to-N scheme and a 1-to-1 scheme. These schemes cater to different priorities, either prioritizing efficiency or fine-grained learning.

We have conducted extensive empirical evaluations on diverse datasets to demonstrate the trainability and effectiveness of the proposed schemes. Our experiments show that with appropriate training procedures and hyperparameter tuning, the 1-to-N scheme achieves high efficiency and desirable performance levels on many datasets, while the 1-to-1 scheme also achieves desirable performance levels on some datasets. Detailed experiment results can be found in Appendix E of the revised manuscript.

[W6]

To further support the effectiveness of our model, we have evaluated our methods on a new dataset called QM9, which has 12 tasks, and the experimental results show that our model achieved significantly better results than the benchmark method in multiple tasks.

[Minor point 1]

We have introduced this concept of 'chordless cycles' in Section 2.1 of the revised manuscript.

[Minor point 2] In the 2nd paragraph of the Introduction in the revised manuscript, we present an example where backtracking messages cause message passing redundancy and show that message passing redundancy causes the message confusion problem.

Dear reviewer,

We thank you for your kind feedback.

We hope that you will be able to review the contribution of our work and the practical efficiency of our approach as summarised in our public response.

[W1.3 Minor remarks]

• We represent walks in our study using their label sequences because typical MPNNs construct message passing graphs based on node labels and connections without taking into account the node identities. By denoting walks with their label sequences, we aim to provide a clear understanding of how "message confusion" can occur. In addition, we have made efforts to enhance the clarity of our explanations in the revised manuscript.

• We have rectified the issue by replacing the incorrect sentence with a correct definition of "chordless cycle" in the revised manuscript.

• Test accuracy alone may not fully capture the expressiveness of an approach. As a result, we have made new conclusions in our revised manuscript:

  1. Our models demonstrate higher expressiveness by effectively representing a wide range of subgraphs, including subtrees, subgraphs with cycles, and subgraphs with multiple cycles.

  2. Empirical results strongly support the efficiency and high performance of our models.

In addition, it is worth noting that the high expressiveness of the model is essential for achieving better generalization performance. An ideal approach should effectively capture a wide range of non-isomorphic subgraphs to accurately measure graph similarity and predict graph properties ¹. Conversely, methods lacking sufficient expressiveness for non-isomorphic subgraphs often struggle to measure graph similarity. While such methods may effectively distinguish training graphs, they lack the ability to accurately measure graph similarity, leading to overfitting. Our experimental results fully support this conclusion, demonstrating that our models (ERFGN, ERFGN$^{\circ}$, and ERFGN$^{\circ}$+GlobalAttention) achieve near-perfect performance on training datasets and exhibit improved generalization with higher expressiveness.

[W2]:

Despite the similarities between our method and RFGNN, the differences between us are not negligible. Our method only extracts the path tree rather than the epath tree from the cyclic subgraph rather than the full graph, which makes our method significantly more efficient compared to RFGNN.

We thank the reviewer for providing us with relevant work that we had overlooked. The discussion about these works has been added to the 2nd & 3rd paragraphs on page 2 of the revised manuscript.

Our DLG structure is similar to those directed line graphs used in (Mahé et al; Chen et al.), but with differences. First, the structure used in (Mahé et al.) has a larger size than ours. A directed line graph used in (Mahé et al.) constructs its own node set from the nodes and edges of its source graph. However, our DLG constructs its own node set only from the edges of its source graph. Small-scale surrogate graphs allow for efficient message passing. Therefore, using our DLG structure enables higher efficiency than that used in (Mahé et al.).

In addition, a directed line graph used in (Chen et al.) also constructs its own node set only from the edges of its source graph. However, such a structure is not used to update the node representation. To update node representation, we add additional connections to DLG to line DLG nodes to source nodes, so that message of DLG can be conveyed to source nodes and it is possible to learn source subtrees from DLGs.

We would like to emphasize that the contributions of our study extend beyond the scope of extracting path trees and utilizing directed line graphs. Our study encompasses broader contributions, which are summarized on page 3 of the revised manuscript.

[W3]: We have justified our statements and added a comparison with GNNs using $k$-WL in Section 2.6. We have also carefully rewritten our proofs and proved the double directions of each statement in Lemmas 1 and 2 to ensure their clarity and rigor in Appendix C.2.

[Q1]: Yes, the cyclic subgraph is the union of all biconnected components. We appreciate again the reviewer's suggestion for a linear complexity method for extracting cyclic subgraphs. However, in our approach, we not only partition graphs but also extract cycles to model the cycle-based subgraphs. Therefore, we adopt the process of extracting the cycles and then constructing the cyclic subgraph.

[W]: We deeply apologize for the unclear presentation in the previous version. We have taken this feedback seriously and have carefully rewritten the entire manuscript to ensure that it meets the standards of a qualified and reader-friendly publication.

We kindly ask reviewers to approach the new version with patience and kindness, and we sincerely hope that our efforts have resulted in a truly readable manuscript. Thank you for your understanding and consideration.

[W1.1]:

(clarity): We have made the necessary revisions to clarify the steps involved in the revised manuscript.

(cycle extraction): The complexity of extracting cycles was given in Section 2.8 of the previous version. It is important to note that the purpose of extracting cycles extends beyond graph splitting. The extracted cycles also play a crucial role in cycle modeling, which justifies the necessity of the cycle extraction process. Regarding the time cost of constructing DLGs and DALGs, we conducted experiments on more than 10 datasets. The experiment results presented in Appendix E of our revised manuscript demonstrate that these procedures are efficient.

(relation to RFGNN): RFGNN (Chen et al.) extracts a path tree from each node, so it suffers from a complexity problem. Before our work, there was no solution that allowed efficient redundancy-free message passing. We proposed efficient redundancy-free message passing by extracting path trees rather than epath trees from cyclic subgraphs rather than whole graphs. Our approach is different from that of RFGNN, and ours is more efficient and scalable.

(motivation):

Our revision to the motivation is summarized as follows:

• Redundancy-free message passing is of the utmost importance. RFGNN achieves this goal. However, it suffers from computational and memory complexity, which limits its scalability and applicability. We found that message passing redundancy can be addressed by eliminating cycles. Additionally, extracting path trees only from cyclic subgraphs offers efficiency and scalability over extracting path trees from entire graphs. Therefore, we propose our methods, which only transform the cyclic subgraphs into cycle-free surrogate subgraphs.

• Furthermore, to capture higher-order graph structures like cycle-based subgraphs, we propose two extensions to the ERFGN framework. The first is ERFGN$^{\circ}$, which incorporates a cycle modeling module to represent any subgraph with a cycle. The second extension is ERFGN$^{\circ}$+GloAttNC, which introduces global attentions between nodes and cycles. This enhancement enables the expression of subgraphs consisting of subtrees and subcycles, and facilitates the generation of identifiable representations for nodes and cycles.

[W1.2]:

(complexity):

• The complexity analysis has been updated with clearer and more precise information in Section 2.8. In addition, empirical time costs for constructing the DLGs and DALGs are provided in Appendix E. We have also clarified the limitation of our methods to be suitable for real-world graphs (such as molecules), which are sparse and have small cyclic subgraphs. Compared to RFGNN [^1], which is the first work that achieves the redundancy-free feature, our methods offer obvious efficiency and higher expressiveness.

• While our methods may not have a significant advantage over RFGNN for biconnected graphs, it is worth noting that there exist real-world graphs, such as molecules, which are often sparse and consist of small, biconnected components. Empirically, our methods have shown efficiency across over 10 datasets (see Appendix F), indicating their suitability for real-world scenarios.

(parameter $V_C$):

We have explained the parameter $V_C$ in Section 2.8 of the revised manuscript. Previously, our complexity analysis was based on the worst-case scenario where the cyclic subgraph is a complete graph. However, this scenario is not close to reality. We have revised the analysis to make it more precise. The revised analysis is summarized as belows:

Let $V^{\circ}$ be the node set of the cyclic subgraph, and $d^{\circ}$ be the maximum node degree. The extracted path trees consist approximately of $|V^{\circ}| \times d^{L}$ nodes and edges. Therefore, for ERFGN, the path tree extraction, as well as the sub-DALG construction, has a complexity of $\mathcal{O}\left(|E|+|V^{\circ}| \times d^{L}\right)$ at worst.

[W]: We appreciate the reviewer's feedback and have made thorough revisions to address their comments. The manuscript now provides comprehensive details on both the theoretical and practical aspects of our work. In particular, expressiveness is discussed and compared with other powerful methods in Section 2.7 and proved in Appendix E. Complexity is analyzed in Section 2.8. Empirical results, including prediction performance and efficiency, are given in Section 3 and detailed in Appendix D.

We kindly request that the reviewers approach the new version with patience and kindness. We appreciate your understanding and consideration. In addition, to avoid possible misunderstandings, we would like to point out that DLGN conducts message passing on DLGs while ERFGN conducts message passing on DALGs. 

[Q1]: The empirical time costs of constructing the DLGs and DALGs for different datasets are listed in tables in Appendix E of the revised paper. Please refer to Appendix E for a comprehensive overview of the empirical time costs.

[Q2]: We apologise for the unclear presentation. It is true that DLGN's expressiveness is limited by the 1-WL test due to the message confusion problem caused by cycles. However, DLGN can still outperform 1-WL based GNNs by reducing message passing redundancy and mitigating the over-squashing problem. In addition, we have added an expressiveness ranking of our models and other powerful models in Section 2.6 of the revision paper.

Yes, the interplay of DLGs and cycles can enhance expressiveness. This interplay allows a model to achieve the same level of expressiveness as CIN (Cell Isomorphism Network) ¹, which surpasses the 3-WL test. However, it is worthy to note that such a model suffers from the message redundancy problem, as well as the message confusion and message over-squeezing problems associated with message redundancy.

[Q3]: Actually, the number of parameters will not vary much from model to model; this is because all models follow a parameter budget on most datasets. We have included parameter budgets in Section 3.

[Q4]: The effect of changing tree-height $L$ has been refined in Tables 12, 13 and 17 in Appendix F. In our experiments, increasing $L$ improves performance, but with diminishing returns. Different datasets require different $L$. For example, long-range interaction datasets require large $L$. However, for small molecular datasets, a small value of $L$ is sufficient. In addition, $L$ not need to exceed the radius of the largest graph component. When $L$ is set equal to this maximum radius, our model reaches its full potential expressiveness, allowing it to represent all possible subtrees and subgraphs in the dataset.