From Theory to Practice: Rethinking Green and Martin Kernels for Unleashing Graph Transformers

We sincerely thank the reviewer for the constructive and encouraging feedback. We are glad that the mathematical rigor, clarity, and structure of our paper were positively noted. Below, we address each comment in detail.

---

1. Motivation and Problem Statement

We appreciate the suggestion to clarify our motivation. Our goal is to connect theoretical kernels from stochastic process theory with structural encodings (SEs) in graph neural networks.

Classical kernels such as Green and Martin kernels capture long-term behavior of random walk and global structural properties. While widely used in potential theory, they are often inapplicable in graph learning due to assumptions like non-finiteness or transience of the graph. As explained in Section 3.3, many such kernels do not extend directly to real-world graphs.

Our contribution lies in reformulating these kernels into scalable and adaptable encodings—GKSE and MKSE—which preserve theoretical grounding while enabling practical use as absolute and relative SEs. This reformulation retains the theoretical meaning while making them usable in practice.

---

2. Broader Applicability Beyond GRIT

Our main experiments use GRIT because it separates the effect of SEs and supports both absolute and relative encodings. This makes it ideal for isolating the impact of replacing RRWP with our proposed SEs.

To demonstrate generality, we also applied our SEs to CKGConv, a different GNN architecture (Appendix B.2). These results show consistent gains, indicating our SEs are not GRIT-specific. We plan to expand to more architectures in future versions.

---

3. Hyperparameter Sensitivity and Fairness

We agree that the number of steps $K$ is a key hyperparameter. For the OCB datasets (Ckt-Bench101, Ckt-Bench301), we reused hyperparameters from ZINC due to their similar size and structure (see Tables 6 and 8). We varied $K$ linearly and presented results in Table 11, which show meaningful performance changes and confirm that an optimal $K$ exists.

Importantly, even when $K$ is not finely tuned, our SEs achieve performance comparable to strong baselines, suggesting that they exhibit enough performance without extensive hyperparameter search. This also implies that using smaller $K$ can reduce precomputation time without sacrificing much performance.

We also evaluated whether similar trends hold for RRWP, a structurally comparable SE. However, we observed that RRWP does not yield the same level of performance as our proposed SEs under similar conditions, further validating the effectiveness of our kernel-based approach. These details will be added to Appendix B.3.

---

4. Clarification of SPD (l.253)

SPD stands for Shortest Path Distance, defined earlier in line 248. We will ensure the abbreviation is properly introduced upon first use to improve clarity.

---

5. Comparison with Prior Work and RRWP

We appreciate the reviewer’s summary that positions our work within the broader literature on random walk-based SEs. As noted, our method extends this line of research by connecting SEs to well-established mathematical kernels. Unlike methods such as RRWP, which compute expected walk counts over fixed-length paths, GKSE and MKSE derive from limiting behaviors of Markov chains, capturing deeper global structure.

The instability of RRWP in non-aperiodic or DAG-like graphs is discussed in our experimental results and qualitative analyses (e.g., Figure 1 and 2). These issues are theoretically motivated and practically observable in molecular and circuit datasets.

Additionally, prior works like [Dwivedi et al. 2022a, Geisler et al. 2023, Zhou et al. 2024] mainly design absolute SEs without supporting relative SEs—a key distinction from our approach.

---

6. Summary of Contributions

To summarize:

• We introduce GKSE and MKSE, novel SEs grounded in Green and Martin kernels with strong theoretical backing.
• These SEs are efficiently computable and compatible with both absolute and relative forms.
• We show empirical gains in datasets where global or asymmetric structures are important (e.g., PCQM4Mv2, Ckt-Bench101).

We appreciate the reviewer’s recognition of the mathematical contributions and clarity of our work. We will revise the introduction and implementation sections to better communicate our motivation and ensure reproducibility.

---

Conclusion

We thank the reviewer once again for the detailed and constructive feedback. Your comments have helped refine both our presentation and experimental justification. We are encouraged by your evaluation and will incorporate all suggestions in the final version.

We thank the reviewer for the positive comments on our theoretical development, writing quality, and comprehensive benchmarking. We also appreciate the thoughtful concerns raised regarding statistical significance and generalization. Below, we respond to each point in detail.

---

1. Clarification on SOTA Claims and Statistical Significance

We fully agree that our previous statement claiming “SOTA on 7 benchmarks” was overstated. Since many improvements fall within the margin of error (N = 4), we will remove all such claims from the paper.

Regarding (a), we used N = 4 to match the experimental setup in GRIT and ensure consistent comparisons. However, we acknowledge this is insufficient for statistical rigor. We are currently running additional trials with a larger number of seeds across datasets and will include extended results in the final version.

Regarding (b), we conducted t-tests and observed statistically significant improvements (p < 0.05) in PCQM4Mv2 and OCB (results in Table 3, 4). Other cases did not show significance, likely due to small sample size. We agree that larger N is needed to draw solid conclusions, and will re-run all key experiments with more seeds.

---

2. Empirical Justification for Theoretical Advantages

We appreciate the reviewer’s acknowledgment of the connection between theory and empirical results. PCQM4Mv2 and Ckt-Bench101, with non-aperiodic and DAG-like structures, clearly demonstrate the strengths of our SEs.

We agree that additional evidence would be valuable. While benchmarks with similar structure are limited, we are exploring domains such as knowledge graphs and program analysis, where our methods may further excel.

---

3. Evaluation Beyond GRIT

The reviewer highlights the need to evaluate the generality of our SEs on other architectures. GRIT was selected because it cleanly isolates the effect of SEs by explicitly using both absolute and relative encodings. This allowed us to assess the performance impact of replacing RRWP with our SEs in a controlled setting.

Nonetheless, our SEs are not limited to GRIT. As shown in Appendix B.2, we applied them to CKGConv—a different architecture—and observed consistent gains. We plan to extend evaluations to additional GNNs in future versions.

---

4. Relationship Between GKSE and RRWP

As noted in Appendix D.4, GKSE can be expressed as a linear transformation of RRWP under specific conditions. However, despite this theoretical link, our experiments show that initializing with GKSE leads to better empirical performance.

This mirrors known results in deep learning: different initializations (e.g., Xavier vs. He) can lead to distinct learning behaviors, even when functionally equivalent in theory. Thus, GKSE and RRWP differ in practice in meaningful ways.

---

5. Experimental Scope

We thank the reviewer for acknowledging our broad experimental coverage. While gains vary across datasets, our SEs provide consistent improvements, particularly in graphs with structural complexity. Even when improvements are small, our SEs offer a principled, scalable, and interpretable alternative to existing approaches.

Their effectiveness is most pronounced in domains where global structure and asymmetry matter—settings that standard benchmarks may not fully reflect. We believe our work lays the foundation for broader adoption of mathematically grounded SEs.

---

6. Summary of Actions

• Removed all exaggerated SOTA claims.
• Expanded experiments with more seeds for reliable significance testing.
• Clarified the theoretical and empirical differences between GKSE and RRWP.
• Demonstrated broader applicability through CKGConv results (Appendix B.2).

---

Conclusion

We thank the reviewer again for the constructive and fair evaluation. Your feedback has helped us refine our claims and improve the clarity and rigor of the paper. We believe the theoretical insights, along with targeted empirical results and ongoing evaluations, support the relevance and contribution of this work.

We appreciate the reviewer’s detailed feedback and critical questions, which allow us to clarify both the motivation and contributions of our work. Below, we address the main concerns.

---

1. Limitations of Existing Random Walk-Based SEs

We agree that random walk (RW)-based SEs, such as RRWP, are already effective in many graph transformer models. Our work does not claim these methods are flawed; rather, we aim to reformulate the concept of structural encoding through a more mathematically grounded lens. Existing SEs are typically designed heuristically based on the network centrality theory, or with limited theoretical support beyond local transition statistics.

Our SEs—GKSE and MKSE—are derived from stochastic process theory. Green and Martin kernels arise in the asymptotic analysis of random walks and are widely used in potential theory to describe the global behavior of Markov chains on graphs. They can uniquely encode specific structural information, such as non-aperiodic and DAG-like structures. As shown in Section 5.2, the values produced by our SEs differ significantly from RRWP across various graph topologies, highlighting their distinct representational properties.

---

2. Difference Between Green Kernel and PageRank

Although Green kernels are algebraically similar to Generalized PageRank (GPR) [1], they differ in key ways:

• Mathematical Origin: GPR focuses on signal smoothing and centrality, while Green kernels emerge from the resolvent of the Laplacian and describe expected visit counts in infinite random walks. This gives them a formal stochastic interpretation, which we rigorously connect to structural encoding via Theorem 4.1 and 4.2.

• Usage in GNN: GPR is typically used as a node feature or precomputation step. In contrast, we use Green and Martin kernels as absolute and relative SEs that directly guide attention in graph transformers.

To our knowledge, this is the first work to adapt Green and Martin kernels as structural encodings in GNNs.

---

3. Why Use These SEs Despite Marginal Gains?

We agree that performance differences can be small on standard benchmarks, which often favor architectures over SE design. Still, our SEs show meaningful gains on topology-sensitive datasets like OCB (Ckt-Bench101, 301) and PCQM4Mv2, which contain DAG and non-aperiodic structures.

More importantly, our methods:

• Are model-agnostic and plug into any transformer architecture
• Are computationally efficient, computing recursively and avoiding eigendecomposition
• Are theoretically grounded, derived from stochastic process theory

Even modest gains can be impactful when combined with scalability and theoretical robustness, making these SEs useful in large-scale, real-world settings.

---

4. Theoretical Contributions of GKSE and MKSE

Our work provides several new theoretical insights:

• We connect Green and Martin kernels to SEs with provable structural meanings
• We establish formal results (Theorems 4.1–4.5) showing their expressiveness
• We show MKSE captures non-linear random walk behavior distinct from both RRWP and GKSE (Theorem D.3)

To the best of our knowledge, these are the first such results making these stochastic tools directly applicable to GNNs while preserving their mathematical essence.

---

5. Summary of Key Contributions

To summarize:

• Theoretical Innovation: Reformulating classical random walk kernels into structural encodings
• Architectural Generality: Easily applicable to transformer architectures
• Efficiency: No eigendecomposition, scalable to large graphs
• New Direction: Enables broader use of mathematical kernels in GNNs

We also acknowledge the reviewer’s note about wording in the abstract and will revise it to avoid vague phrases like “AI-ready” or “promise,” in favor of more precise claims.

---

6. Final Remarks

We appreciate the reviewer’s critical perspective and hope this rebuttal clarifies our contributions. Although the gains may be modest in some benchmarks, we believe the theoretical foundation, practical utility, and extensibility of our SEs make a compelling case.

We will revise the manuscript to clarify our distinctions from existing methods, including [1], and better communicate our theoretical and empirical contributions.

Thank you again for your thoughtful and constructive feedback.

We sincerely thank the reviewer for the detailed and thoughtful feedback. Below, we clarify the key motivations, contributions, and empirical implications of our work, while responding to specific concerns regarding novelty, positioning, and evaluation scope.

---

1. Novelty Beyond RRWP and Value of Kernel-based SEs

While our proposed SEs share a random-walk foundation with RRWP, they originate from Green and Martin kernels, classical constructs from potential theory and stochastic processes. These kernels reflect asymptotic behaviors of random walks, capturing structural phenomena such as non-aperiodicity, absorbing components, and hierarchical depth—aspects that finite-length walk-based encodings like RRWP may overlook.

Our contribution lies not in incremental variation, but in reformulating these kernels into scalable encodings for modern graph transformers, retaining their mathematical meaning. We believe this offers a new direction for structural encoding design, grounded in well-established theory.

---

2. Empirical Gains and Practical Implications

We agree that performance gains on standard benchmarks may seem modest overall, which reflects the nature of these datasets where local attention often dominates. However, we observe notable improvements in datasets with more complex global structures—PCQM4Mv2 (molecules) and Ckt-Bench101 (circuits)—where the structural sensitivity of GKSE and MKSE becomes evident (Table 3, 4; Appendix B.4–B.5).

Crucially, these gains are obtained without changing model architecture, demonstrating the practicality of our SEs as drop-in modules. Even small but consistent improvements from theoretically grounded, efficient encodings can accumulate meaningfully across applications in circuits, molecules, or program graphs.

---

3. Positioning Relative to Recent Literature ([1], [2])

We thank the reviewer for referencing [1] Recurrent Distance Filtering and [2] Graph as Point Set. These represent powerful yet fundamentally different approaches:

• [1] adapts message passing using learned filters based on node distance.
• [2] maps graphs to sets via spectral regularization and permutation-invariant networks.

Both methods involve architecture-level changes and rely on eigendecomposition, which can hinder scalability. In contrast, our SEs are model-agnostic, require no spectral operations, and target transformer-style models that lack native graph inductive bias.

Though our work differs in intent and scope, we agree that comparing across such methods adds valuable context. We are preparing further experiments and will include comparative discussion in the final version.

---

4. Experimental Scope and Use of GRIT

We chose GRIT as our primary architecture because it provides an explicit SE framework, including both absolute and relative positional encoding. It also uses RRWP as a core module, making it a natural baseline for assessing our SEs under controlled conditions.

Nonetheless, our SEs are not limited to GRIT. In Appendix B.2, we apply them to CKGConv, a structurally different graph transformer, and observe consistent improvements. This supports the general applicability of our method. We plan to expand these evaluations to additional models in future work.

---

5. Broader Relevance and Future Directions

Our work aims to bridge mathematical theory with practical GNN design. Reformulating Green and Martin kernels into usable SEs represents a principled step toward designing structural encodings with formal guarantees.

This approach opens promising future directions:

• Exploring other theoretical kernels (e.g., hitting time, diffusion).
• Applying to domains with structured topology (e.g., program graphs, knowledge graphs).
• Integrating with adaptive architectures like [1] for further synergy.

We hope this inspires more mathematically grounded exploration in GNN research.

---

Conclusion

We thank the reviewer again for their valuable insights. In response, we will:

• Clarify the novelty of GKSE and MKSE versus RRWP.
• Highlight broader architectural compatibility beyond GRIT.
• Expand the discussion to include recent related works and future directions.

We hope these clarifications address the reviewer’s concerns and underscore the contribution and relevance of our work.