Unleashing Graph Transformers with Green and Martin Kernels

Authors: Yoon Hyeok Lee, Jaemin Park, Taejin Paik, Doyun Kim, Bosun Hwang
Primary area: learning on graphs and other geometries & topologies
Keywords: graph transformers, graph neural networks, structural encodings, green kernel, martin kernel, non-aperiodic substructures, dags

Abstract:
Graph Transformers (GTs) are rapidly emerging as superior models, surpassing traditional message-passing neural networks in graph-level tasks. For optimal performance, it is essential to design GT architectures that embed graph inductive biases and utilize global attention mechanisms through effective structural encodings (SEs). In this work, we introduce novel SEs derived from a rigorous theoretical analysis of random walks (RWs), specifically leveraging the Green and Martin kernels. The Green and Martin kernels are mathematical tools used to observe the long-term behavior of RWs on graphs. By integrating these kernels into the encoding process, we enhance their capability to accurately represent complex graph structures. Our empirical evaluations demonstrate that these approaches enable GTs to achieve state-of-the-art performance on 7 out of 8 benchmark datasets. These include molecular datasets characterized by intricate, non-aperiodic substructures such as benzene rings, and directed acyclic graphs common in the circuit domain. We attribute these performance improvement to the effective capture of the characteristics of non-aperiodic substructures and directed acyclic graphs by our extending encodings. The results not only validate the effectiveness of integrating the Green and Martin kernels into RW-based encodings but also underscore their potential to substantially enhance the learning capabilities of GTs across diverse applications.

Decision: reject
Reviewer scores: 8, 8, 5, 5

Reviews and discussion:
<thread>
creation date:
1730053883471

thread_type:
official_review

<thread_object>
creator: reviewer_ecje

<content>
summary:
Graph Transformers have become very popular in graph-level tasks recently, and their success significantly depends on the employed structural encodings. This paper introduces two new encodings which are derived from the theory of random walks, namely the Green and Martin kernels. The authors define finite-step variants of the two kernels which capture random walk patterns within a limited number of steps. The encodings from the two kernels are integrated into the GRIT model and are evaluated in graph classification and regression tasks. In most cases, the encodings enhance the performance of GRIT and lead to state-of-the-art results.

strengths:
- The paper provides an extensive experimental evaluation of the proposed structural encodings. The evaluation does not only focus on molecules, but also on other types of graphs such as circuits modeled as DAGs and images modeled as graphs.

- The proposed structural encodings seem to lead to performance improvements and to state-of-the-art results. GRIT+GKSE and GRIT+MKSE outperform the baselines on 7 out of the 8 considered benchmark datasets.

- It is shown in the paper that MKSE possess a unique expressiveness independent of RRWP. Thus, MKSE can potentially capture properties of graphs that cannot be captured by RRWP.

weaknesses:
- As discussed above, GRIT+GKSE and GRIT+MKSE outperform the baselines on 7 out of the 8 considered benchmark datasets. However, even though GKSE and MKSE are experimentally shown to perform better than their main competitor (RRWP encodings), it is not clear to me whether the improvements provided by the proposed encodings are statistically significant. On almost all benchmark datasets, the improvement over GRIT+RRWP appears to be minor.

- Some details about the proposed models and the experimental setup are missing from the paper. The values of the different hyperparameters are provided in Tables 6 and 7 in the Appendix, but I could not find any details about the employed architecture. It is mentioned that the proposed encodings are integrated into GRIT, but for the paper to be self-contained, I would suggest the authors add a description of GRIT into the Appendix. More importantly, some details about how the proposed encodings are integrated into the models are also missing from the paper. GKSE and MKSE are defined (in l.216-l.222) over pairs of nodes. Hence, in my understanding, those encodings could not be used as initial node-level structural encodings. They could potentially be utilized as edge-level structural encodings. I would suggest the authors provide more details about the model.

- I would encourage the authors to better motivate the use of the proposed encodings. Since RRWP encodings are also derived from the theory of random walks, why should one prefer the proposed encodings over RRWP encodings? Table 10 shows that computing GKSE and MKSE is computationally more expensive than computing RRWP encodings. Therefore, the authors should justify why one should choose the proposed encodings for a particular application.

- Even though the paper is not hard to read, there exist some typos and other types of errors. For example, in l.126, "matrixwith" should be replaced with "matrix with". Also in l.290 (Theorem 3, part 2) "GKSE" should be replaced with "MKSE".

questions:
The proposed kernels appear to be very similar to the hitting times and commute time distances, two popular tools which are commonly used to analyze the structure of graphs. Is there a connection between the proposed kernels and hitting and commute times? If there is some connection, can you please provide more details?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730408585854

thread_type:
official_review

<thread_object>
creator: reviewer_jhqq

<content>
summary:
The paper introduces novel structural positional encodings (PEs) for graph transformers, based on the Green and Martin kernels. Both capture certain aspects of the long-term behavior of random walks. The former captures the expected number of visits to one node from another, the latter represents the probability that a RW starting from one node will reach another node within finite time. The model is evaluated over a range of graph datasets of different kinds.

(Please note: I did not check the theory in Sec 4.2 in detail)

strengths:
- The paper is well-written and nice to read.
- The motivation and general consideration of the research topic make sense to me.
- The evaluation covers a wide range of datasets of different kind.

weaknesses:
- The performance improvements seem minimal, if existent. Most of the numbers (if I didn't miss anything) are within standard deviation of the next best existing model, which is in several cases +RRWP.
- Given that this seems to be a general PE proposal a consideration of different graph transformers would be more suitable, i.e., beyond just GRIT.
- A suitable baseline on the DAG data would be DAG transformer [1]

I guess I am the last reviewer who focuses on experiments, but in this paper I see quite some potential issues with them. The analysis figure shows potential benefits of the model but, it seems to me, the set of experiments chosen in the submission do not really show them.

[1] Luo et al. Transformers over Directed Acyclic Graphs, NeurIPS'23 https://openreview.net/pdf?id=g49s1N5nmO

questions:
- Why is Table 3 missing the +RRWP baseline?
- The analysis in Fig. 1 is interesting, but the results shown in the tables do not show great differences. The text says "Consequently, RRWP, which is based on these transition probabilities, may fail to capture the structural properties of graphs containing non-aperiodic substructure". Could one maybe select corresponding data (sub)sets to show and test this? 
- Could it make sense to combine RRWP and/or these PEs?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730671060465

thread_type:
official_review

<thread_object>
creator: reviewer_4ima

<content>
summary:
Graph transformers due to their lack of structural awareness, require effective structural encodings. This paper presents two effective structural encodings, called GKSE and MKSE, based on the Green and Martin kernels that can extend the concept of random walks. The authors have supported the effectiveness of GKSE and MKSE via both theoretical and empirical results.

strengths:
- The paper is well-written and well-motivated. The authors provided enough details about the approach that made its understanding simple. 
- The proposed method is intuitive, relatively simple (yet effective), and is a natural extension, which I believe is very important.
- Recently, several approaches have focused on using shortest path encoding, which is very efficient, to better learn the structure of the graph. The authors have provided theoretical results that how GKSE and MKSE are more powerful and expressive than shortest path encoding.

weaknesses:
- My main concern is about the efficiency of the proposed methods: How can GKSE and MKSE affect the memory usage and training time of graph transformers (compared to common structural encodings and shortest path encodings)?  
- Recently, for the sake of efficiency, several GTs have used more complex tokenization (e.g., NAGPhormer). Due to their scalability, they are more practical and also they have a better inductive bias about the graph structure. It would be interesting to see the effect of GKSE and MKSE on these models.
- I believe the current experiments cannot support the effectiveness of GKSE and MKSE as they show the performance gain only on GRIT. Is this performance gain limited to only this model? How can using GKSE and MKSE as the structural encoding for other methods (GPS, NAGphormer, etc.) affect performance?
- Is there any trade-off between GKSE and MKSE? Is there any performance gain if we use both? (e.g., their concatenation)
- (Minor) I suggest using a different citation format (e.g. using [13] instead of (13)). The current format results in confusion whether this is a citation or a reference to an equation (for example lines 222, 274, etc.).

questions:
- Why there are inconsistencies in the chosen baselines across different benchmarks? E.g., why GraphSAGE’s results are not reported for all benchmarks?
- Is there any performance gain if we use both GKSE and MKSE? (e.g., their concatenation)
- How can using GKSE and MKSE as the structural encoding for other methods than GRIT (e.g., GPS, NAGphormer, etc.) affect performance?
- How do GKSE and MKSE affect memory usage and training time?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730695519202

thread_type:
official_review

<thread_object>
creator: reviewer_tzuc

<content>
summary:
The paper proposes two graph structural encodings, GKSE and MKSE, based on Green and Martin kernels, respectively. These encodings are evaluated for their theoretical expressiveness, and also empirical performance on multiple datasets when combined with GRIT. The results demonstrate the advantage of GKSE and MKSE as structural encodings.

strengths:
1. The paper is well-motivated. The authors build upon the known theoretical and practical strengths of RRWP and propose natural extensions (GKSE and MKSE) by considering the steady-state behavior of random walks on graphs.
2. The main claims of the paper are well-supported. The paper provides theoretical analysis on the expressivity of GKSE and MKSE, as well as experimental result demonstrating good performance when combined with GRIT.
3. The paper is self-contained and well-organized. I particularly like how the authors combine mathematical reasoning with intuitive explanations and figures.

weaknesses:
Despite the paper's solid contributions, I find the explanation regarding the efficacy of GKSE and MKSE (lines 479-509) somewhat unconvincing. To demonstrate this, I will present alternative interpretations of examples presented in these paragraphs, to support the opposite argument: RRWP is more preferable.
1. Figure 1 suggests that RRWP provides a more decoupled representation of graph structures compared to GKSE and MKSE. Although RRWP encodings might not visually resemble the original graph (particularly for even $k$), this decoupling could make it easier for the model's learnable linear encoder to extract structural relationships such as multi-hop neighbors. In contrast, GKSE and MKSE encodings across different $k$ values appear more uniform, which may make it more difficult to extract structural features.
2. The non-aperiodic substructures of a graph causes RRWP to oscillate, as evident in Figures 1 and 3. This provides a reliable way for the model to identify non-aperiodic substructures, which is prevalent in molecular graphs. On the contrary, GKSE and MKSE are not as sensitive to non-aperiodic substructures, making it harder for the model to identify them.
3. For DAGs, RRWP naturally produces a sparse, decoupled representation, as illustrated in Figure 2. This sparsity can enhance the model’s capability to identify structural features, with an added advantage of selecting a suitable value of $K$ based on knowledge of the dataset (e.g., $K=4$ in Figure 2). GKSE and MKSE, in contrast, generate dense, often redundant information across different values of $k$ when applied to DAGs.

These arguments are not presented to promote RRWP, but to highlight the need that lines 479-509 be further clarified to convince the reader that your interpretations are preferable to alternative interpretations, like those presented above. If these claims are speculative, they should be framed as such, and additional supporting evidence would be valuable.

Despite this issue, the paper's overall contributions remain valid and meaningful.

questions:
Please see weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732178786123

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Official Comment by Authors to all reviewers

comment:
We sincerely thank the reviewers for their thorough evaluation and thoughtful feedback on our manuscript. Below, we provide a summary of our contributions, clarify key points, and address overarching themes raised in the reviews.

In this work, we proposed novel random-walk-based structural encodings (SEs) for graph transformers, named Green Kernel Structural Encoding (GKSE) and Martin Kernel Structural Encoding (MKSE). These SEs are inspired by stochastic process theory, specifically kernels used to analyze long-term behavior in random walks. While these abstract mathematical tools provide strong theoretical foundations, their direct application to real-world graph data is challenging due to the significant gap between abstract mathematical theory and the practical complexities of real-world graphs. To address this challenge, we carefully designed SEs that retain the mathematical integrity of these kernels while ensuring their adaptability to graph datasets from diverse domains. Moreover, we proposed efficient computational methods for these SEs, making them practical for large-scale applications. In addition to their practicality, we rigorously demonstrated that GKSE and MKSE possess sufficient expressiveness compared to existing SEs, further validating their utility in capturing intricate graph structures effectively.

Our method has demonstrated state-of-the-art (SOTA) performance on 7 out of 8 benchmark datasets across various graph-level tasks, showcasing its versatility. Notably, our approach excels in molecular and circuit graph domains, where it effectively captures intricate graph structural properties. To understand the reasons behind this performance, we explored unique structural characteristics of these graph types using novel observational methods, which we report as part of this work. The performance improvement is especially pronounced in large-scale datasets. For instance, on the PCQM4Mv2 dataset, our SEs exhibited a significant performance gain, highlighting their effectiveness in capturing complex structural information in real-world graph data.

We thank the reviewers for their insightful comments, which have helped us refine our manuscript and identify promising directions for future research. We have made substantial revisions to address specific concerns, clarified our contributions, and added new analyses and citations to strengthen the paper. We believe that our work makes a meaningful contribution to the field by combining rigorous mathematical theory with practical advancements in graph representation learning, and we hope our responses adequately address your concerns.

Once again, we express our gratitude for the opportunity to improve our work through your constructive feedback.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732389716739

thread_type:
official_comment

<thread_object>
creator: area_chair_rd6n

<content>
title:
Reminder: Please Review Author Responses

comment:
Dear Reviewers,

As the discussion period is coming to a close, please take a moment to review the authors’ responses if you haven’t done so already. Even if you decide not to update your evaluation, kindly confirm that you have reviewed the responses and that they do not change your assessment.

Thank you for your time and effort!

Best regards, AC
</content>
</thread_object>

</thread>
<thread>
creation date:
1732782386973

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
We sincerely thank reviewers for their thorough feedback and constructive suggestions, which have been instrumental in refining. Below, we summarize the key aspects of the reviews under major contributions, major concerns, and questions raised, along with the corresponding actions we have taken.

__Major Contributions__

1. __Novel Structural Encodings (GKSE and MKSE):__
Several reviewers appreciated our proposal of GKSE and MKSE as novel structural encodings derived from Green and Martin kernels, adapted from theoretical stochastic processes. These encodings provide a mathematically grounded and unique approach to capturing structural information in graphs.
_(Reviewers tZUc, 4iMa, ecJe)_

2. __Extensive Evaluation Across Diverse Graph Domains:__
The evaluation of GKSE and MKSE on a wide range of datasets, including molecules, circuits, and image-based graphs, was commended. Reviewers noted that our methods demonstrated SOTA performance on seven of the eight benchmark datasets.
_(Reviewers ecJe, 4iMa, jhQq)_

3. __Theoretical and Empirical Validation of Expressiveness:__
Reviewers highlighted our analysis demonstrating that GKSE and MKSE extend the expressiveness of RRWP and shortest path encodings by capturing nuanced graph structural features.
_(Reviewers tZUc, 4iMa)_   


__Major Concerns and Actions Taken__

1. __Persuasiveness of Observations (Reviewer tZUc):__
_Reviewer tZUc_ expressed doubts about whether our empirical observations convincingly explain the performance improvements of GKSE and MKSE over RRWP.

   + __Action Taken:__
   We clarified in the manuscript (Line 504) that our observations are not proofs but empirical insights suggesting possible explanations for performance gains.
   Additional analysis on OCB datasets was included, showing how sparse representations in RRWP for smaller-diameter graphs may weaken performance, whereas GKSE maintains denser representations, leading to improved results.

2. __Efficiency of SEs (Reviewer 4iMa):__
Questions were raised about the memory and computational efficiency of GKSE and MKSE compared to other SEs like RRWP, shortest path encodings (SPD), and Laplacian Eigenvectors (LapEig).

   + __Action Taken:__
   We provided complexity analyses and practical runtime comparisons in Section 5.3. For example, precomputing GKSE is nearly identical to RRWP in time and space complexity, while MKSE has a slightly higher computational cost but delivers richer structural information.
   A comparison table summarizing the computational complexities of GKSE, MKSE, RRWP, SPD, and LapEig was added.

3. __Generality Beyond GRIT (Reviewers 4iMa, jhQq):__
Reviewers questioned whether GKSE and MKSE generalize beyond GRIT, as our experiments initially focused on this architecture.

   + __Action Taken:__
   We integrated GKSE and MKSE into additional architectures like GPS and CKGConv. While results with GPS were comparable, incorporating these SEs into CKGConv showed improvements across multiple datasets.
   These findings demonstrate that GKSE and MKSE are not limited to GRIT.

4. __Practical Applicability and Value of SEs (Reviewer ecJe):__
Why should practitioners prefer GKSE and MKSE over RRWP, especially given marginal improvements on certain datasets?

   + __Action Taken:__
   Experiments on subsets of the PCQM4Mv2 dataset, focusing on graphs with specific structural properties (e.g., benzene rings), showed that GKSE outperforms RRWP in capturing non-aperiodic substructures.

5. __Justification for Computational Costs (Reviewer ecJe):__
Why are GKSE and MKSE worth the slightly higher precomputation costs compared to RRWP?

   + __Action Taken:__
   We emphasized that the precomputation phase minimally impacts overall training time and that GKSE consistently delivers better results on molecular and circuit graphs. Practical runtime data was provided for large-scale datasets, showcasing that GKSE is only marginally slower than RRWP.


__Questions Raised and Responses__

1. __Why Inconsistent Baselines Across Benchmarks? (Reviewer 4iMa):__

   + __Response:__
   Missing results for GraphSAGE stemmed from unavailable hyperparameters in prior works. To address this, we conducted additional experiments for GraphSAGE on peptides and PCQM4Mv2 datasets. Results confirmed that GKSE and MKSE remain competitive.

2. __Can GKSE and MKSE Be Combined? (Reviewer 4iMa):__

   + __Response:__
   Experimental results showed no significant performance gains from combining GKSE and MKSE due to overlapping information. We recommend selecting SEs based on dataset characteristics.

3. __Connections to Hitting and Commute Times? (Reviewer ecJe):__

   + __Response:__
   While traditional Green kernels connect to hitting/commute times, our finite-step adaptations are distinct. We acknowledged this in the manuscript and highlighted it as a promising direction for future work.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper proposes two structural encodings for graph transformers, GKSE and MKSE, derived from Green and Martin kernels. These methods extend the standard form of random walks. The authors analyze some theoretical aspects of these structural encoding and evaluate their performance in combination with GRIT across multiple graph datasets. The results indicate that GKSE and MKSE have potential advantages as structural encodings.

The strengths of this paper cover the rigorous formulation and the clear presentation of the proposed methods. Empirical experiments also show some improvements. The weaknesses of this paper include the limited evaluated backbone (only GRIT), the comparison with existing SE/PE and the marginal improvement compared to the standard random-walk structural encoding RRWP. In the rebuttal, the authors provided the application of other backbones. However, the marginal improvement over the RRWP is still there. 

After carefully reading the paper, I have some similar concerns about the novelty of this work, aligned with two reviewers who recommended a rejection. Let me explain this. 

**Limited Novelty in Structural Encoding**
The GKSE encoding, as defined in Eq. (13), shares the same polynomial basis with RRWP for finite $K$. A linear transformation can map RRWP to GKSE, rendering the latter not fundamentally different, also limited empirical performance gain observed in the experiments. The proposed GKSE follows a formulation similar to PageRank-based random walks (with 0.5 transportation probability), which have already been explored as structural encodings in works like [1]. Consequently, the empirical performance improvements over RRWP are marginal. Even for infinite $K$, GKSE reduces to the pseudo-inverse of the graph Laplacian, effective resistance, a concept utilized as structural encoding in [2, 3]. Hence, the novelty of this contribution is marginal.

**Expressive Power Analysis** Both GKSE and MKSE are spectrum-based encodings, whose upper-limit expressive power has been extensively analyzed. Prior works [4, 5] have shown that spectral invariants are not more expressive than 3-WL, and subsequent research [6] established that they are strictly less powerful than 3-WL. The distance-generalized 1-WL, as outlined in Eq. (19), was first proposed in [1], where RRWP was also firstly introduced as an enhancement for GNNs’ expressive power. Moreover, as spectrum-based encodings, GKSE and MKSE can be seen as mappings of Laplacian PEs, aligning with stable forms proposed in [7]. The above studies [1-7] seemed to be missed in the current work discussion, leaving gaps in the contextualization of this work within the broader literature.


Given the above concerns, I lean towards rejecting this paper. While the authors provide a rigorous exposition and some empirical validation, the lack of substantial novelty, the marginal performance improvements, and the limited contextualization of prior work diminish its overall contribution. My concerns align with the two reviewers who provided weak rejections. Although Reviewer 4iMa increased the score to acceptance after the authors provided experiments on backbones other than GRIT, the performance gains remain minor, reaffirming the theoretical concerns. Moreover, Reviewer 4iMa also raised concerns regarding the computational efficiency of the proposed SEs compared to existing SEs/PEs. The authors presented a table suggesting that Lap PEs and shortest-path distances have a complexity of $O(V^3)$. However, this comparison is unfair. Under their original definitions, which involve infinite steps, GKSE and MKSE also require approximately $O(V^3)$. The reported reduction to $O(K|V||E|)$ arises solely from a $K$-step approximation. If such approximations are permissible, then $K$-step shortest-path distances would also reduce to $O(K|V||E|)$, and Laplacian PEs could achieve the same complexity by using only a subset of eigenvectors.

I still see some valid contributions from this work. However, the above concerns have to be addressed for qualified acceptance, and this may need some major revision of the manuscript. One minor thing is about the reference format which does not follow the template of ICLR. Please kindly fix this too.


[1] Li, et al., Distance encoding: Design provably more powerful neural networks for graph representation learning, NeurIPS 2020.

[2] Velingker, et al., Affinity-Aware Graph Networks, NeurIPS 2023.

[3] Zhang, et al., Nested Graph Neural Networks, NeurIPS 2021.

[4] Lim, et al., Sign and basis invariant networks for spectral graph representation learning, ICLR 2023.

[5] Fürer, On the power of combinatorial and spectral invariants, Linear Algebra and its Applications, 2010.

[6] Zhang, et al., A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Tests, ICML 2023.

[7] Huang, et al., On the Stability of Expressive Positional Encodings for Graphs, ICLR 2024.