Simple Path Structural Encoding for Graph Transformers

Thank you for your thoughtful and constructive review. We're glad that the clarity of our claims, the robustness of our experimental design, and the correctness of our theoretical contributions were appreciated. While no major concern was raised, we would like to contextualize the following point below:

Q1. Although SPSE performs better than RWSE in most cases, the improvement is only slight.

R1. We completely agree that, although the performance gains over RWSE-based methods are statistically significant on 4 out of 7 datasets, they can sometimes appear modest. However, we would like to highlight that these results were obtained only by replacing walk probabilities by path counts, with no further alteration to the model input or architecture. That said, we believe there is still untapped potential in SPSE, as suggested in Section 5.3 ("Path Count Sensitivity to Hyperparameters"). Furthermore, additional performance gains may be possible through more extensive tuning of SPSE's three key hyperparameters.

We respectfully acknowledge the reviewer’s comments, and hereby attempt to address the different points that were raised.

Q1. Distinction of graphs A vs. B using RWSE / RWSE is not limited to a single value of k…

R1. We'd be happy to clarify. In Figure 1, the objective is not to differentiate between entire graphs (e.g., Graph A vs. Graph B), but rather to compare how individual edges are represented under different encoding methods. Taking the concrete example of edge (0,1) in both Graph A and Graph B, the random walk probability of travelling from node 0 to node 1 in $k$ steps is exactly 0.5 if $k$ is odd and 0 if $k$ is even, and this holds for any $*k* \in \mathbb{N}^*$. This implies that RW-based structural encoding cannot distinguish between edges (0,1) in Graph A and Graph B. This property of RWSE is formalized in Proposition 1 of the manuscript, which we prove in Appendix B.1. We also sketch the manual derivation of the random walk probabilities of edge (0,1) of graphs A to D in Figure 7 (Appendix C).

Q3. How to get the approximated simple path count?

R3. Thank you for pointing this out. The details about the operation done in line 9 of Algorithm 1 (how the running path count is updated for each new node ordering) are given in the full path counting algorithm, in Appendix D: powers of the adjacency matrix given by the new DAG yield new path counts, and running counts are updated by taking the element-wise maximum across all node pairs and path lengths between the new path counts and the current running values. This will be made more explicit in the main text.

Q4. Error bound of the approximate counting algorithm

R4. Deriving the error bound is an intricate task, which would require identifying the failure cases and estimating their prevalence. It is however possible to empirically quantify this bound by running exact path counts on various graph topologies, within the runtime limits of these algorithms (i.e. largest possible value of maximum path length $K$, shown below for the NetworkX implementation).

For ZINC, MNIST and PATTERN, which contain graphs of respective average densities of 0.09, 0.23 and 0.43, we report below the proportion of paths discovered by our approximate path counting method.

We observe from experiments that trading path count precision for longer path length can improve overall performances, but the precise interplay between exact path count (when they are affordable), maximum path length $K$ and model accuracy would require further study.

Q5. Reason behind $log$ in Equation (4)

R5. The only constraint on the encoding function of Equation 4 is injectivity. The use of logarithm composition was empirically driven by the need to reduce the very high magnitudes of total path counts reached for several graph collections (up to $10^{13}$ for $k=16$ on CLUSTER).

Q6. Differences between Table 1 results and original works

R6. Differences between results originally reported by the authors in CSA / GRIT and GPS and the ones in Table 1 are due to the fact that all models were re-trained (using publicly released code and configurations) on 10 random seeds, instead of 4, as is usually done. Retraining was important to compare RWSE and SPSE performances all things being equal, while running experiments on 10 seeds yielded much stronger results. For the large PCQM4Mv2 on which a single experiment was run, we found a MAE of 0.0838 for GRIT-RWSE, improving the reported value of 0.0859: this highlights the need for retraining, even when using the same number of seeds as the original work. The reason for the observation of such differences (be it better or worse) will be made very clear in the final version of the manuscript.

Thank you for the detailed and constructive review. We appreciate your recognition of SPSE’s novelty, and of the clarity and comprehensiveness of our experimental validation. We're also glad you found the theoretical contributions, algorithmic details, and supplementary material valuable. We address the questions below.

Q1. Addressing the computational cost of SPSE for large-scale graphs

R1. As the computational complexity of path counting incurs a cubic dependency with the number of nodes, scaling to large-scale graphs is a challenge. One possible solution is to apply pooling techniques [1] to reduce the graph size: computing simple paths between communities in a pooled graph would become manageable, and this could be followed by separate path discovery within each community. This shares links with the discussion in the answer to the next question. That being said, accurately combining path counts within and between communities presents new and interesting challenges, constituting an avenue for future research.

[1] Bianchi, F. M., & Lachi, V. The expressive power of pooling in graph neural networks. NeurIPS 2023.

Q2. Plans to combine SPSE with other SEs?

R2. Yes, one particularly promising direction is [2], which is complementary to our work and can also be used as a plug-in module within existing architectures. In particular, we expect that our two offline preprocessing workflows can be efficiently combined: mining paths at higher hierarchy levels can be done more easily because of simpler topologies, while capturing valuable long-range structural information. This will be mentioned in the discussion on future research direction.

[2] Luo et al., Enhancing Graph Transformers with Hierarchical Distance Structural Encoding, NeurIPS 2024

Q3. SPSE for directed/weighted graphs

R3. The only difference that arises in our algorithm when the input graph is directed is that one must account for the fact that the adjacency matrix is no longer symmetric. This case is addressed in the attached Python file by setting the directed boolean to True. This prevents the summation with the transposed adjacency matrix in line 16 of the full algorithm (Algorithm 3 in Appendix D). In the special case of a DAG input graph, the DAGDecompose step will be skipped. It is also possible to use different edge attribute values (i.e. weights) inside the adjacency matrices, although the interpretation might be more intricate and calls for closer scrutiny.

Q4. Contextualization with hierarchical encoding / spectral attention

R4. Thank you for the suggestion. Adding a discussion —aligned with our response to Q2— on the potential synergies with hierarchical methods, especially, would help strengthen the future research directions section. Spectral attention, meanwhile, is natively used within both GRIT and CSA frameworks.

Q5. Further improvement with hyperparameter tuning

R5. We acknowledge that hyperparameter tuning could further improve SPSE's performance. Here, we intentionally chose not to alter the provided configurations for a transparent and fair comparison with existing structural encodings (a procedure that Reviewer wLjL also acknowledged), but future exploration of full SPSE capabilities will likely require adjusting model and optimization parameters.

Thank you for your thorough and thoughtful review. We are glad that you found the theoretical claims convincing and appreciated the clarity of our method and the rigor of our experimental setup.

Bellow we report the answers to the comments and questions.

Q1. Aspect contributing to runtime of path mining algorithm

R1. In the cases considered here, where the number of nodes does not exceed a few hundred, the critical aspect is graph density. From the algorithmic point of view, the parameters that impact the most the computation time are the fraction of selected root nodes, $R$, the number of trials per depth $N$, and to a lesser extent the maximum DFS depth $D_\text{DFS}$, as can be seen in Figure 5. Although the worst-case complexity scales linearly with $D_\text{DFS}$ and $N$, their contributions are most of the time smaller: we suspect that the sparser the input graph, the lesser the contributions of $D_\text{DFS}$ and $N$ are (may it be at least as $N$ cannot exceed node degree), although this would require further and thorough analysis.

Q2: Similarity with Node2Vec

R2. A given DAG decomposition could be interpreted as an attempt to characterize the neighborhood of a root node in the sense of Node2Vec, in the limit case where the neighborhood is the whole graph. In this sense the two methods indeed share similarities. However, we characterize node pairs instead of single nodes, and rather than listing the neighboring nodes, we focus on the ordering in which the nodes were discovered by the search to unveil graph structures at various scales.

Q3. Choice of datasets used

R3. The practical reason that drove our choice of test datasets was that we looked for existing configurations for the training of GRIT and/or CSA, the two graph transformer methods implementing RWSE, in order to validate our methodology. The exploration of the benefits of SPSE on more diverse graph topologies will be an exciting future research direction.

Q4. Parameter study on $\alpha$, $\beta$ and $n$

R4 Our analysis of the path encoding parameters (Equation 4) revealed two main factors contributing significantly to variations in model performance:

• Compression of the dynamic range of path counts (controlled primarily by parameter $n$).
• Adjustment of the final output range (affected by both parameters $\alpha$ and $n$).

These effects are demonstrated in the tables below, presenting model accuracy for GPS on the PATTERN dataset and GRIT on the MNIST dataset, across various hyperparameter configurations:

In these cases, the large path counts explain why the best results are obtained for a higher $n$ / lower $\alpha$.

Q5. Expressivity regarding WL / RWSE

R5: We provide below an initial discussion about the expressivity of the proposed SPSE encoding as an answer to this insightful comment. A reasoning similar to that employed for Path-WL [1] shows that composing $k$ global attention layers with SPSE results in a model that is strictly more expressive than $k$ iterations of the 1-WL color refinement algorithm. We note also that all properties regarding the expressivity of GRIT remain valid when SPSE replaces RWSE as the chosen structural encoding method. However, comparing the expressivity of SPSE and RWSE through isomorphism tests is more complex. Contrary to WL- / Path-trees introduced in [1] and [2], SPSE and RWSE aggregate information over simple paths and walks without enumerating them, which prevents one from using the strategy of the proof of Theorem 3.3 of [2] to draw any conclusion. A rigorous theoretical analysis is required to characterize the precise relationship between the two encodings within the WL hierarchy, which is left as future work.

[1] Graziani et al., "The Expressive Power of Path-Based Graph Neural Networks." ICML, 2024.

[2] Michel et al., “Path Neural Networks: Expressive and Accurate Graph Neural Networks”, ICML, 2023

Q6. Missing SEs benchmark.

R6. The missing reference will be added to the benchmark.