Thank you for your efforts in proposing these comments and questions.

Response to the weaknesses

• In response to your concern regarding the evaluation's limitations, we appreciate your feedback and have made enhancements. The evaluation now incorporates results from the large-scale ogbg-molhiv dataset [1], presented in Table 10 on Page 20. We observe consistent performance enhancement on this dataset, aligning with existing results. This additional evaluation would provide more comprehensive and accurate support. | ogbg-molhiv | Valid AUROC | Test AUROC | |---------------------------|-----------------------|-----------------------| | GAT | 77.67 $\pm$ 2.78 | 74.45 $\pm$ 1.53 | | GAT (DEL-F) | 78.99 $\pm$ 1.69 | 75.27 $\pm$ 1.32 | | Graph transformer | 78.20 $\pm$ 1.18 | 76.51 $\pm$ 0.93 | | Graph transformer (DEL-F) | 80.12 $\pm$ 1.39 | 76.86 $\pm$ 0.95 | | GPS | 80.08 $\pm$ 1.39 | 76.71 $\pm$ 1.12 | | GPS (DEL-F) | 82.57 $\pm$ 0.95 | 76.93 $\pm$ 1.00 |

• In real-world applications, computing the graph layout for real-time test data does incur additional overhead. However, this overhead can often be mitigated through distributed computing. It's noteworthy that we report a minimal amount of preprocessing time using CPU threads (one or eight). For datasets other than D&D, our processing speed for a single graph is typically around 0.1 seconds, while for D&D, it is approximately 1 second. Given that the average number of nodes in existing graph classification datasets generally does not exceed that of D&D, our method remains feasible in the majority of scenarios.

• We did not deliberately disregard LapPE; our decision to focus on RWSE in the comparative experiment was guided by the conclusion of the paper [2]: "The benefits of the different encodings are very dataset dependant, with the random-walk structural encoding (RWSE) being more beneficial for molecular data and the Laplacian eigenvectors encodings (LapPE) being more beneficial in image superpixels." Therefore, we opted for the more advantageous RWSE for comparison. We will provide updated results for LapPE in Table 1.

[1] Hu, Weihua, et al. "Open graph benchmark: Datasets for machine learning on graphs." Advances in neural information processing systems 33 (2020): 22118-22133.

[2] Rampášek, Ladislav, et al. "Recipe for a general, powerful, scalable graph transformer." Advances in Neural Information Processing Systems 35 (2022): 14501-14515.

After reading the author's response, some of my concerns (computation efficiency) are addressed. However, the proposed method minimally improves the performance of existing models on a larger dataset, ogbg-molhiv. The proposed method still appears to me as a variant of the preprocessing method, and the paper falls short of explaining why the technique outperforms the existing approach (RWSE), which limits its contribution. Hence, I am keeping my original rating.

Thank you for your support and constructive comments.

Response to the weaknesses

• Theoretical Analysis: Layout algorithms are seldom explored in graph representation learning, and proposing a comprehensive theoretical framework falls somewhat beyond the scope of this article. Nevertheless, DEL holds the potential to connect with certain theoretical frameworks. For instance, in Figure 7 on page 18, it is observed that DEL readily recognizes edges connecting different connected components. This observation could potentially be linked to spectral theory, as such edges often exert a significant influence on spectral distribution [1]. We will investigate more on the theoretical aspect in our future work.

• Sampling Layout Numbers: The determination of the number of sampling layouts is contingent upon the characteristics of specific downstream tasks and datasets. In practical terms, ensuring an adequate number of sampling layouts is essential for the model to capture the potential energy distribution of the graph accurately. However, an excessively high number of layout samples can result in information redundancy and low efficiency, thereby impacting the performance of its practical use.

• Computational Complexity: In real-world applications, graph sizes for graph classification tasks typically do not exceed those of the D&D dataset. If the graph size is stable, the preprocessing overhead of DEL is linearly correlated with the number of graphs. The reported preprocessing times in the paper are based on the utilization of either 1 or 8 CPU threads; employing additional threads would further reduce preprocessing time. Furthermore, for more efficient handling of node classification tasks of large-scale graphs, we can also combine DEL with some more efficient large-scale graph layout algorithms which capable of accommodating millions of nodes [3].

• Regarding dimensionality exploration, Please refer to the 2nd response to the questions part.

Response to the questions

Reviewer 8jRK’s question can be summarized as how DEL theoretically enhances graph representation learning and how to select important hyperparameters of DEL such as the number of samples and the dimension of the graph layout space.

• DEL acquires global information, not attainable by MPNN through the sampling of the layouts based on potential energy distribution. This unique capability positions DEL as a potent enhancer of graph representation learning. In Appendix D, we present some initial analysis, reserving the construction of a more solid and comprehensive theoretical framework for future research.

• Though there is not a ready theory interpreting why 2D and 3D layouts are sufficient to deliver good performance, we can regard graph spectral theory as an analogous counterpart. In graph spectral theory, the majority of Laplacian eigenvalues for a graph are very close to 0, while minor eigenvalues far from 0 are sufficient to depict the overall structure of the graph. This surprisingly aligns with the observation that 2D/3D layouts are adequate for capturing the main structure of the entire graph. Therefore, lacking specific prior knowledge, we prioritize performing DEL in a low-dimensional space. Simultaneously, DEL sampling multiple layouts in a low-dimensional space can further assist DEL in learning a more accurate energy distribution of the graph, leading to performance improvement. However, these are initial analyses, and more solid and comprehensive theoretical analyses will be left to future work.

[1] Spielman, Daniel. "Spectral graph theory." Combinatorial scientific computing 18 (2012): 18.

[2] Lin, Lu, Jinghui Chen, and Hongning Wang. "Spectral augmentation for self-supervised learning on graphs." ICLR 2023.

[3] Zhu, Minfeng, et al. "DRGraph: An efficient graph layout algorithm for large-scale graphs by dimensionality reduction." IEEE Transactions on Visualization and Computer Graphics 27.2 (2020): 1666-1676.

Thank you for your efforts in proposing these comments and questions.

Response to the weaknesses

• We have provided related analysis and discussion about noise injection in our initial submission. We clearly define the preprocessing in Section 4.1 of the article, i.e., we use the standard graph layout algorithm as preprocessing, but we still provide the option to add noise in the code, e.g., you can find the Fruchterman Reingold algorithm with a noisy version in lines 44-61 and 248-308 in the utils.py implementation. In Section 4.1 we discussed that adding noise has little effect on the distribution of the sampled layouts as well as the downstream performance (shown in Table 9 of Appendix F at Page 19). Thus, to reduce the extra computational burden caused by noise, we turn off the noise injection in our implementation. As suggested by the reviewer YS2Q, we have reorganized our submission and discussed it in Appendix G to make this point clear. | ogbg-molhiv | Valid AUROC | Test AUROC | |---------------------------|-----------------------|-----------------------| | GAT | 77.67 $\pm$ 2.78 | 74.45 $\pm$ 1.53 | | GAT (DEL-F) | 78.99 $\pm$ 1.69 | 75.27 $\pm$ 1.32 | | Graph transformer | 78.20 $\pm$ 1.18 | 76.51 $\pm$ 0.93 | | Graph transformer (DEL-F) | 80.12 $\pm$ 1.39 | 76.86 $\pm$ 0.95 | | GPS | 80.08 $\pm$ 1.39 | 76.71 $\pm$ 1.12 | | GPS (DEL-F) | 82.57 $\pm$ 0.95 | 76.93 $\pm$ 1.00 |

• Algorithm 1 must consider the graph's topology, as the elastic force computed using Hooke's law applies only to nodes connected by edges. In response to your concerns, we have provided additional clarification in Algorithm 1, with the modifications highlighted in blue.

• In response to your concern regarding the evaluation's limitations, we appreciate your feedback and have made enhancements. The evaluation now incorporates results from the large-scale ogbg-molhiv dataset [1], presented in Table 10 on Page 20. We observe consistent performance enhancement on this dataset, aligning with existing results. This additional evaluation would provide more comprehensive and accurate support.

Response to the questions

• Please also refer to the 1st response to the weakness part. In practice, when dealing with simple topologies such as molecules and social networks from real-world applications, the layout algorithms tend to produce wide optima [2], which are very close to the layouts sampled using noise-injected versions like Langevin dynamics (see Appendix G and Figure 8 in the manuscript). This allows for the use of standard layout algorithms as an efficient surrogate without the need for intricate noise schemes. In Figure 8 of Appendix G, we present new visualization results that confirm the close similarity of layout distributions obtained with or without noise sampling.

[1] Hu, Weihua, et al. "Open graph benchmark: Datasets for machine learning on graphs." Advances in neural information processing systems 33 (2020): 22118-22133.

[2] Fruchterman, Thomas MJ, and Edward M. Reingold. "Graph drawing by force‐directed placement." Software: Practice and experience 21.11 (1991): 1129-1164.