KAA: Kolmogorov-Arnold Attention for Enhancing Attentive Graph Neural Networks

Dear reviewer nAy3,
We hope our point-to-point responses can address your concerns and provide you with better clarification of the contributions and value of our work.

1. (Weakness 1) Clarification for insufficiency of existing attention mechanism.

The goal of GAT is to "adaptively" learn the alpha weights of neighboring nodes for a given central node. Our research examines whether GAT's method of learning these weights is sufficiently "adaptive." Why do we consider GAT's scoring function to lack expressiveness and be insufficiently "adaptive"? This is because GAT essentially performs a linear transformation of the features of neighboring nodes to compute their importance scores. Such transformations are not "rich" enough and inherently impose many implicit constraints. A toy example illustrates this limitation: suppose a node has three neighbors, $x_1$, $x_2$, and $x_3$, with feature values of 1, 2, and 3, respectively. Using GAT's linear scoring function $s = ax + b$, regardless of how the learnable parameters $a$ and $b$ are chosen, either $x_1$ or $x_3$ will always receive the highest score, while $x_2$ can never achieve the highest attention score. This demonstrates the lack of expressiveness in the scoring function, as it fails to adaptively assign importance based on the unique characteristics of the features. Of course, real-world problems are far more complex than this toy example. In our paper, we provide a detailed analysis and discussion of these issues. KAA is designed to universally enhance the expressiveness and adaptability of the scoring function, enabling various attentive GNNs to truly learn the alpha weights they aim to capture.

2. (Weakness 2) Comparison with hierarchical attention mechanism.

Most existing methods focus on determining what constitutes important attention information, with advanced techniques excelling at capturing this crucial information through the attention mechanism. The core of these methods lies in guiding the model to focus on what type of information should be captured by the attention mechanism to make it more informative. The hierarchical attention mechanism you mentioned also falls within this category of approaches. KAA, on the other hand, emphasizes the actual learning process and improves the construction of the attention mechanism itself. Our goal is not to prescribe what type of attention should be captured but to use theoretical analysis and experimental results to demonstrate how to design a scoring function when aiming to model a specific attention distribution. This ensures that your model can truly and adaptively capture the desired attention distribution effectively. This means that, regardless of the type of attention distribution being learned, KAA can enhance the success rate of modeling that distribution. As you mentioned, the hierarchical attention mechanism is intuitive and meaningful in its design. KAA can further enhance the practical expressiveness of such methods. We conducted a simple validation on the two methods you referred to, and the results are presented in the table below.

Table. Comparison results of KAA on hierarchical attention methods.

The experimental results show that KAA consistently provides performance gains, highlighting its ability to enable attentive GNNs to more effectively learn the attention weights they aim to capture. In addition, we will include a similar discussion in the paper to clarify the relationship between KAA and other methods.

3. (Question 1) Contributions of our work.

Our paper makes significant contributions to the design and development of attentive GNN models. First, we unify the existing paradigms of attentive GNNs, covering nearly all GAT-based and Transformer-based models. Building on this foundation, we innovatively identify and explore the issue of insufficient ranking expressiveness in attentive GNNs and develop a comprehensive theoretical framework to address this problem. Using our framework, we can not only quantitatively assess the most critical scoring capabilities of attentive GNNs but also intuitively compare the expressiveness across different methods. Ultimately, we find that incorporating a small-scale KAN network effectively resolves this issue and propose the KAA method. The simplicity and efficiency of KAA make it an ideal plug-in, capable of universally enhancing all attentive GNNs to better capture the attention distributions they aim to learn. Our contributions to the KAN field are also notable. We introduce KAN into the scoring function and achieve significant success, offering valuable insights for other researchers on how to apply KAN effectively. More importantly, we innovate by comparing the theoretical expressive capabilities of MLP and KAN. This novel perspective will greatly inspire the KAN community and help researchers determine when to use KAN versus MLP. Therefore, our work has made substantial theoretical contributions to both the attentive GNN and KAN communities. It would be unfair to dismiss the innovation of our paper due to the fundamental nature of our solution.

4. (Question 2) Advanced baselines.

We have presented the performance results of KAA on advanced attentive GNNs in the Global Response. The experimental results demonstrate that KAA consistently provides significant performance gains, even when applied to advanced models. Additionally, a comparison with other KAN-based baselines has already been provided in Appendix B.3. This comparison includes all existing KAN variants for which we are able to collect either code or results applicable to graph data.

We hope our explanation can dispel your concerns and motivate you to reconsider the value of our paper. If you have any other questions or concerns, please feel free to let us know.

Dear reviewer nAy3,
As there is only one day remaining to submit the revised paper, we would greatly appreciate it if you could kindly take some time to respond to our rebuttal. We would also like to confirm whether our explanations have adequately addressed your questions and concerns. Thank you for your time and consideration.

Dear reviewer nWMV,
We hope our point-to-point responses can address your concerns and provide you with better clarification of the contributions and value of our work.

1. (Weakness 1) Impact and comparison with advanced techniques.

In recent years, GNNs have been continuously evolving toward greater generalization and robustness. One popular direction is the development of graph foundation models (GFM) [1,2] that can adapt to various tasks, similar to large language models. Most existing GFM models [3,4,5] adopt attentive GNNs. From the success of large language models, the attention mechanism appears to be important for modeling cognition [6]. Therefore, we can believe that as GNNs evolve toward greater generalization, attentive GNNs will continue to play a crucial role. In addition, the attention mechanism often has an orthogonal relationship with other techniques, and combining these techniques can often lead to better downstream performance. As mentioned in papers [7,8], high-order cooperation is one such example, and many improved attentive GNNs [9,10] have also adopted similar ideas, achieving promising results. KAA strengthens the foundation of attentive GNNs and will play a significant role in paving the way for GNNs to achieve greater generalization and enhanced cognition.

Your suggestion to incorporate advanced technologies is very reasonable. In fact, the KAA technique is not in conflict with other non-attention techniques, but these orthogonal methods are difficult to compare directly. Therefore, we select several of the most advanced and sophisticated GNN models and demonstrate that KAA consistently provides stable and satisfactory improvements when applied to these SOTA techniques. We have presented the performance results of KAA on advanced attentive GNNs in the Global Response. The experimental results show that KAA consistently provides significant performance gains even on advanced models.

2. (Weakness 2 & Question 1) Empirical guarantee of MRD.

Thanks for your valuable suggestions, and the experimental validation of MRD's effectiveness is highly meaningful. To achieve this target, we design a synthetic node regression task to validate this. Specifically, we first construct an Erdős-Rényi (ER) random graph $G(N, p)$ with $N$ nodes and an edge probability $p$. Next, we randomly generate $d$-dimensional Gaussian features $x_i \in \mathcal{N}(0, 1)^d$ for each node. For a node $v_i$ with $n_i$ neighbors, we randomly assign a target permutation $\pi_i: \{1,...,n_i\} \to \{1,...,n_i\}$ to its neighbors, serving as the target ranking for $v_i$ as well as the target scores of its neighbors relative to $v_i$. After normalizing the target scores, we obtain the target aggregation coefficients $\alpha_{i,j}$ for the neighbor node $v_j$ of the central node $v_i$. Finally, we assume the regression value for each node to be $h_i = \sum \alpha_{i,j} x_j$. We use GAT (representing Linear Transformation-Based Attention), GATv2 (representing MLP-Based Attention), and KAA-GAT (representing Kolmogorov-Arnold Attention) to perform single-layer node value regression prediction. The structural difference between them lies only in the scoring functions: Linear Transformation, MLP, and KAN, respectively. Their MRD satisfies the inequality $MRD_{KAA-GAT} < MRD_{GATv2} < MRD_{GAT}$. On a graph with $d = 10$, $N = 100$, and $p = 0.1$, the relative values of the actual RD and error $E$ for each method are shown in the table below.

Table. Relative error on $G(100, 0.1)$.

On a graph with $d = 10$, $N = 1000$, and $p = 0.01$, the relative values of the actual RD and error $E$ for each method are shown in the table below.

Table. Relative error on $G(1000, 0.01)$.

From the experimental table, we can observe that KAA-GAT achieves the smallest MRD, with the smallest actual RD and error as well. GATv2 has the second-lowest MRD, and its results also rank second in terms of RD and error. Next, we base our modifications on KAA-GAT, reducing the hidden layer dimensions of KAN to half and a quarter of the original size to decrease its MRD. The results for these three models on two graphs are shown below:

Table. Relative error on $G(100, 0.1)$.

Table. Relative error on $G(1000, 0.01)$.

At this point, it can be observed that all models with smaller MRD achieve better performance, which demonstrates the effectiveness of the MRD metric. This supports the idea that minimizing MRD directly correlates with improved model performance. We will provide a more detailed description of this synthetic experiment, including a comprehensive set of results, in the appendix later.

We hope our explanation can dispel your concerns. If you have any other questions or concerns, please feel free to let us know.

Reference

[1] Towards Graph Foundation Models: A Survey and Beyond.

[2] A Survey on Self-Supervised Pre-Training of Graph Foundation Models: A Knowledge-Based Perspective.

[3] Graphany: A Foundation Model for Node Classification on Any Graph.

[4] Building Transportation Foundation Model via Generative Graph Transformer.

[5] GOFA: A Generative One-For-All Model for Joint Graph Language Modeling.

[6] Attention Mechanism in Neural Networks: Where It Comes and Where It Goes.

[7] Training Graph Neural Networks with 1000 Layers.

[8] Link Prediction Based on Graph Neural Networks.

[9] Multi-Hop Attention Graph Neural Networks.

[10] Inductive Link Prediction with Interactive Structure Learning on Attributed Graph.

Dear reviewer kkV1,
We hope our point-to-point responses can address your concerns and provide you with better clarification of the contributions and value of our work.

(Weakness 1) Potential impact for GNN community.

Your interpretation of the development of the entire GNN community is very reasonable. However, overall, attentive GNN models are still widely applied in various scenarios. In recent years, GNNs have been continuously evolving toward greater generalization and robustness. One popular direction is the development of graph foundation models (GFM) [1,2] that can adapt to various tasks, similar to large language models. Most existing GFM models [3,4,5] adopt attentive GNNs. From the success of large language models, the attention mechanism appears to be important for modeling cognition [6]. Therefore, we can believe that as GNNs evolve toward greater generalization, attentive GNNs will continue to play a crucial role. Our work strengthens the foundation of attentive GNNs, and we hope that KAA can serve as an optional learner in the future, easily integrated into various existing attentive GNN models.

(Weakness 2) Advanced baselines.

We have presented the performance results of KAA on advanced attentive GNNs in the Global Response. Experimental results show that KAA consistently provides significant performance gains even on advanced models. Moreover, for Graph Transformers, the number of layers often exceeds 4 in many scenarios, especially in graph-level tasks. This indicates that the results and conclusions of the paper are not limited to shallow models.

We hope our explanation can dispel your concerns. If you have any other questions or concerns, please feel free to let us know.

Reference

[1] Towards Graph Foundation Models: A Survey and Beyond.

[2] A Survey on Self-Supervised Pre-Training of Graph Foundation Models: A Knowledge-Based Perspective.

[3] Graphany: A Foundation Model for Node Classification on Any Graph.

[4] Building Transportation Foundation Model via Generative Graph Transformer.

[5] GOFA: A Generative One-For-All Model for Joint Graph Language Modeling.

[6] Attention Mechanism in Neural Networks: Where It Comes and Where It Goes.

Dear authors,

Thanks for your responses. For weakness 1, I understood your claim, and admit your contribution. However, I would like to keep my point due to that the attention mechanism relating to KAA is not that convincing in terms of performance of graph problems considering so many GNN architectures have been proposed.

Best,

Reviewer

Dear reviewer w7oB,
We hope our point-to-point responses can address your concerns and provide you with better clarification of the contributions and value of our work.

1. (Weakness 1) Motivations to design attentive GNNs with KAN.

We have presented the performance results of KAA on advanced attentive GNNs in the Global Response. A comparison between KAA and GATv2 has already been provided in Table 6 of the paper's appendix. In all cases, KAA demonstrates superior performance. In fact, KAA is not at odds with advanced attentive GNN techniques and does not lose effectiveness due to their strong performance. This is because existing methods focus more on determining what constitutes important attention information, and advanced methods often excel at capturing such crucial information through the attention mechanism. KAA, on the other hand, enhances the actual construction process of the attention mechanism. This means that regardless of the type of attention distribution being learned, KAA can improve the success rate of accurately modeling that distribution. Therefore, despite the significant advancements in existing attentive GNNs, KAA can still universally provide performance improvements, as it represents an enhancement from a different perspective.

2. (Weakness 2) Multi-head attention with MRD theory.

The impact of multi-head attention on the theoretical expressive power of a model depends on the specific model architecture [1]. However, in most practical cases, it generally has a positive effect on downstream tasks. A toy example illustrating this is when we disregard the normalization of attention scores in GAT. If there are two attention heads with coefficients $W_1$ and $W_2$, producing results $H_1$ and $H_2$, respectively, and the final result is $H = H_1 + H_2$, we can equivalently find a single-head attention coefficient $W_3 = W_1 + W_2$ that directly yields $H$. This suggests that, in the context of attentive GNNs, multi-head attention is often used more as a practical trick. It helps reduce task complexity and alleviates the optimization process [2]. Your understanding of KAA and our proposed MRD framework is absolutely correct. While multi-head attention offers little enhancement in theoretical expressive power, it remains a valuable practical trick to improve downstream results [2]. This is why we still employ multi-head attention in KAA.

3. (Weakness 3) Question about the assumption.

The reason we assume that the central node is connected to all other nodes is to ensure simplicity in expression and to minimize the introduction of new symbols. We apologize if this assumption seemed overly strong. In reality, our theoretical analysis only imposes certain requirements on the size of the alignment matrix $P$. As referenced in Formula 27 in the Appendix, the result holds as long as the number of rows in $P$ exceeds the number of columns. This implies that the error bounds in our analysis hold as long as the central node has more neighbors at a given layer than its hidden dimension, which is easily satisfied in real-world scenarios. For instance, the Bio and Chem datasets inherently have only 2-dimensional features, and on the Cora dataset, GAT uses a hidden dimension of 8. Therefore, the theoretical analysis presented in the paper is much more broadly applicable than the conditions assumed for simplicity. The seemingly strong assumptions were made solely to facilitate easier reading and understanding. Thank you for your suggestion, and we have included additional clarifications in our latest revision.

4. (Weakness 4) Solution to overfitting.

Your concern about more expressive models being more prone to overfitting is very reasonable. KAA not only has a strong theoretical upper bound but also leverages simple techniques in downstream tasks to mitigate overfitting, thereby achieving robust performance. In our experiments, we found that simply increasing the dropout rate and appropriately reducing the hidden layer dimension can yield excellent results with KAA, without requiring additional regularization. This indicates that KAA is not only a method with a high theoretical ceiling but also one that is simple to implement and easy to tune, making it highly adaptable to a wide range of real-world scenarios.

5. (Weakness 5) Time and space cost of KAA.

Unlike KAN-based methods in other domains, KAA introduces a relatively small-scale KAN only in the scoring function part, which makes its time and space costs more manageable. In most cases in our experiments, the KAN we used consists of a single layer, with the spline order of the B-spline function set to 1 and a grid size of 1. This simple structure is sufficient to achieve satisfactory downstream results. Specifically, we collect statistics on the number $n$ of parameters and the time $t$ required for each training epoch for both GAT and KAA-GAT on the Cora, CiteSeer, and PubMed datasets. The results are shown in the table below.

Table. Statistics of time and space cost.

The results in the table show that most of the parameters in GNNs are used for feature transformation, allowing KAA to add less than 2% additional parameters. Moreover, the runtime increase is also under 2%. This indicates that in scenarios where KAA is applied, both the time and space costs are highly acceptable.

6. (Weakness 6) Baseline setting.

In Table 1, the performance of GAT on some datasets is slightly lower than the results reported in the original paper. This discrepancy arises because we standardized the selection of hidden layer dimensions for all models from the range [32, 64, 128, 256] (as mentioned in Line 427 of the original paper). Most existing models use hidden layer dimensions within this range. However, GAT's optimal hidden layer dimension on Cora, CiteSeer, and PubMed is 8. To address this issue, we expanded the hidden layer dimension selection to include [8, 16] and re-tuned the parameters for all models. We found that only GAT and KAA-GAT achieved better results on some node classification datasets with these additional dimensions. The updated results are provided in the table below.

Table. Updated experimental results.

This adjustment leads to comparable performance improvements for both GAT and KAA-GAT, reinforcing the consistency of our previous experimental conclusions that KAA continues to deliver performance gains across all cases. Thank you for your detailed feedback. We have thoroughly rechecked the baseline results from our experiments against those reported in the original paper and can confirm that our results consistently outperform the originals. (Note that the specialized tricks of each baseline model have been removed, so the comparison is based solely on the results that include only the core model.)

We hope our explanation can dispel your concerns. If you have any other questions or concerns, please feel free to let us know.

Reference

[1] Repulsive Attention: Rethinking Multi-head Attention as Bayesian Inference.

[2] On the Optimization and Generalization of Multi-head Attention.

Dear reviewer w7oB,
As there is only one day remaining to submit the revised paper, we would greatly appreciate it if you could kindly take some time to respond to our rebuttal. We would also like to confirm whether our explanations have adequately addressed your questions and concerns. Thank you for your time and consideration.

Dear reviewer w7oB,
We apologize for any misunderstanding caused by our unclear responses. Regarding your further concerns, we would like to clarify the following points.

1. (Weakness 1) Motivations to design attentive GNNs with KAN.

Regarding the improvement of KAA over existing attentive GNNs, we have demonstrated its effectiveness from three perspectives: intuition, theory, and experiments. First, from an intuitive perspective, existing attentive GNN methods (both GAT-based and Transformer-based) focus primarily on identifying what constitutes important attention information. Advanced methods often excel at capturing such crucial information through the attention mechanism. These methods define what good attention looks like. KAA, on the other hand, takes a different approach. Once the model has identified the type of attention to learn, KAA allows the model to better capture this attention distribution. As a result, KAA can universally enhance the performance of existing methods. Second, from a theoretical perspective, regardless of how complex the logic and ideas behind existing methods are, their scoring functions will always take the unified form as shown in Equation 6 of the original paper. The real challenge in training then becomes how to enable this scoring function to learn the attention distribution we want. Section 4.2 of the paper rigorously proves, from a theoretical standpoint, why KAA leads to improvements across various forms of scoring functions. Thus, KAA is also theoretically effective for attentive GNNs. Finally, we have validated the effectiveness of KAA through experiments. Whether in the experiments presented in the main body of the paper or the additional experiments on advanced baselines provided in the rebuttal, KAA consistently improves the original model across all settings. In some cases, the improvement is even significant, reaching up to 20%. In summary, the effectiveness of KAA for attentive GNNs, whether classical or advanced, has been demonstrated comprehensively through intuition, theory, and experiments.

2. (Weakness 2) Multi-head attention with MRD theory.

We apologize for the lack of clarity in our response and for the inappropriate example we provided regarding GAT. We fully agree with your understanding of multi-head attention, as it enhances the model's expressive power. Our theoretical analysis is also consistent with the general understanding of multi-head attention. The original question you raised concerns whether, given KAA's strong theoretical expressive power, it still requires multi-head attention to further enhance its expressiveness, and whether the attention distributions learned by different heads will be very similar. We will answer this question from two perspectives. First, while KAA has strong theoretical expressive power, fully realizing this capability requires certain conditions on the dimensionality of KAA’s hidden layers. However, in practical training, to prevent overfitting or to accelerate convergence, the hidden layer dimensionality may not meet the theoretical requirements. In this case, multi-head attention can be used to enhance KAA’s expressive power and improve the performance of downstream tasks. Second, like all other learning models, there is a gap between KAA’s theoretical expressive power and its actual performance. In this context, multi-head attention helps to reduce task complexity and alleviate the optimization process [1]. In our practical training, multi-head attention indeed provides a performance boost to KAA, and the attention distributions learned by different heads are distinct. That is why we apply the multi-head technique to KAA.