KAA: Kolmogorov-Arnold Attention for Enhancing Attentive Graph Neural Networks
Authors: Taoran Fang
Tianhong Gao
Chunping Wang
YihaoShang
Wei Chow
Lei CHEN
Yang Yang
Venue: ICLR 2025 Poster (2025)
Keywords: Kolmogorov-Arnold Networks
Attentive Graph Neural Networks
Primary area: learning on graphs and other geometries & topologies
TL;DR: We introduce Kolmogorov-Arnold Attention (KAA), which integrates KAN into the scoring functions of existing attentive GNN models.

Abstract: Graph neural networks (GNNs) with attention mechanisms, often referred to as attentive GNNs, have emerged as a prominent paradigm in advanced GNN models in recent years. However, our understanding of the critical process of scoring neighbor nodes remains limited, leading to the underperformance of many existing attentive GNNs. In this paper, we unify the scoring functions of current attentive GNNs and propose Kolmogorov-Arnold Attention (KAA), which integrates the Kolmogorov-Arnold Network (KAN) architecture into the scoring process. KAA enhances the performance of scoring functions across the board and can be applied to nearly all existing attentive GNNs. To compare the expressive power of KAA with other scoring functions, we introduce Maximum Ranking Distance (MRD) to quantitatively estimate their upper bounds in ranking errors for node importance. Our analysis reveals that, under limited parameters and constraints on width and depth, both linear transformation-based and MLP-based scoring functions exhibit finite expressive power. In contrast, our proposed KAA, even with a single-layer KAN parameterized by zero-order B-spline functions, demonstrates nearly infinite expressive power. Extensive experiments on both node-level and graph-level tasks using various backbone models show that KAA-enhanced scoring functions consistently outperform their original counterparts, achieving performance improvements of over 20% in some cases.

Published as a conference paper at ICLR 2025
KAA: KOLMOGOROV-ARNOLE ATTENTION FOR ENHANCING ATTENTIVE GRAPH NEURAL NETWORKS
Taoran Fang Zhejiang University fangt.rfzu..ddu.
Tianhong Gao
Shanghai Jiaotong University gth20022s edu.. .n
Chunping Wang Fin Volution Group
Yihao Shang
Zhejiang University
wangehuunping02exxiyy.ccom com
shang yihaol edu. en
Wei Chow
Lei Chen
Yang Yang"
Zhejiang University 32101037900zju.een edu.
VinVuoution Group
Zhejiang University
chenlei04@e wiiiiye............e...ee com
yangyaāz ju. edu, cn
ABSTRACT
Graph neural networks (GNNs) with attention mechanisms, often referred to as attentive GNNs, have emerged as a prominent paradigm in advanced GNN mod- els in recent years. However, our understanding of the critical process of scoring neighbor nodes remains limited, leading to the underperformance of many existing attentive GNNs. In this paper, we unify the scoring functions of current attentive GNNs and propose Kolmogorov- Kolmogorov- Network (KAN) architecture into the scoring process. KAA enhances the performance of scoring functions across the board and can be ap- plied to nearly all existing attentive GNNs. To compare the expressive power KAA with other scoring functions, we introduce Maximum Ranking Distance (MRD) to quantitatively estimate their upper bounds in ranking errors for node importance. Our analysis reveals that, under limited parameters and constraints width and depth, both linear transformation-bassed and MLP-based scoring functions exhibit finite expressive power. In contrast, our proposed KAA, even with single-layer KAN parameterized by zero-order B-spline functions, demon- strates nearly infinite expressive power. Extensive experiments on both node-level and graph-level tasks using various backbone models show that KAA-enhanced scoring functions consistently outperform their original counterparts, achieving performance improvements of over 20% in some cases. Our code is available https:: http//githb.. com / junet /KAA
Attention (KAA), which integrates the
INTRODUCTION
Graph neural networks (GNNs) have achieved great success in graph data mining (Kipt & Welling
2017 Hamilton et al. 2017 Xu et al. 2019 Wu et al. 2019 Sun et al. (0022) and are widely applied
various downstream tasks, such node classification (hang el al. (2019a Huang et al. 2024). link prediction (Kipf & Welling 2016 Huang et al. 2025), vertex clustering (Ramaswamy et al.) 2005| Sun et al. (204). and recommendation systems (Ying al.) 2018). To further enhance the expressive power of GNNs, attentive GNNs (Sun et al. 2023 Chen et al., 2024) incorporate an attention mechanism (Vaswani et al. (017)) into GNN models, allowing them to adaptively learn the aggregation coefficients between central node and its neighbors. This capability grants attentive
GNNs greater expressive power and superior thcoretical performance in various downstream tasks.
Despite their theoretical advantages, the practical performance of existing attentive GNNs in real- world tasks often falls short of expectations. Even with larger parameter sizes and more flexible
"Coressonning author.

---

Published as a conference paper at ICLR 2025
Symbotic Regression
KAN Approximator
Neighbor Scoring
Multi-Dimensional Input
b
y
Central Neighhor Node
sin
(in na + +cos(c)
Hcat Conduction PDE
Scoring Function
s u o AF xg. Xj)
One-Dim)
(Multi-Dim)
8=u
KAN AF(
0x By a=?
One-Dimensional Output
(a)
(b)
(c)
Figure I: The alignment of our proposed KAA and other applications of KAN. (a) Symbiotic re-
gression and PDE-solving tasks, where KAN achieves strong performance. (b) These tasks utilize KAN to handle multi-dimennional inputs and one-dimensional outputs. (c) Since the score mapping in attentive GNNs follows similar form, replace it with KAN.
architectural designs, attentive GNNs sometimes underperform compared to classical GNNs on cer- tain datasets. Previous studies (Qiu et al. 2018 Brody et al. 2021) suggest that this discrepancy arises from the overly simplistic design of scoring functions attentive GNNs, which introduces substantial inductive bias and limits their expressive power. Specifically, [Brody et al. (202T) ana- lyzed the scoring function in GAT (Veličković et al. (2018) and discovered that all central nodes tend to share the same highest-scoring neighbor, leading to subpar performance in certain scenarios. To address this, they introduced the concepts of static and dynamic atlention to assess the expressive power of attentive GNN models. However, with the rapid evolution of attentive GNNs, we have observed that these analyses are primarily applicable to models with simpler structures, and their methods for evaluating the expressive power of scoring functions are too coarse, lacking the ability to provide a more granular, quantitative comparison.
To improve the effectiveness of attentive GNNs and deepen our understanding of them, two critical issues need to be addressed: how to quantify the expressive power of attentive GNN models, and how to universally enhance this expressive power. Tackling these challenges is far from straightforward. First, attentive GNN models typically involve multiple coupled linear transformations and MIPs, making it difficult to accurately quantify their theoretical expressive power. Second, the diversity in existing attentive GNN architectures makes it challenging to find unified solution.
In our paper, we tackle these two fundamental issues from a fresh perspective. To analyze existing attentive GNN models, we first present a unified framework for their scoring functions, which con- sists of a learnable score mapping and non-learnable alignment function. The scoring functions of nearly all attentive GNN models, including both GAT-based and Transformer-based approaches (Sun) al. 2023). conform this paradigm.
To address the first issue, we introduce Maximum Ranking Distance (MRD) to quantitatively evalu- ate the expressive power of scoring functions. Specifically, MRD computes the upper bound of error in ranking node importance, with smaller MRD values indicating stronger expressive power. Addi- tionally, observe that the expressive power of the MLP module within scoring functions is often overestimated. Although the MLP possesses a universal approximation theorem (Cybenko 1989. Hornik 199T), in practice, limitations in the number of layers and hidden units constrain its actual expressive power. In such cases, the MRD of the scoring function with the MI.P can be calculated to quantify its expressive capability.
To address the second issue, we introduce Kolmogorov-Amol Network (KAN) into the scoring functions of existing attentive GNNs. KAN (Liu et al. 2024b a) is an emerging network archi- tecture that shows promise timize the summation coefficients between neurons during training, KAN focuses on optimizing the mapping between neurons. This novel architecture has garnered significant interest among searchers (Genet & Inziniloo 2024] Abueidda et al. 22244) Bozorgasl & Chen, 2024, Bresson et al, 2024). Inspired by the remarkable success of KAN in symbolic regression (Ranasinghe al. 2024
alternative to traditional MLPs. While existing MLP models op-
2

---

Published as a conference paper at ICLR 2025
Seguel al. 2024 Shi al. 2024) and PDE solving (Wang et al. 2024 Rigas al. 2024 Wu
et al. 2024a). we recognize its substantial potential for modeling mappings with multi-dimensional inputs and -in-dimensional outputs, illustrated in Figure I Similarly, the scoring function of attentive GNN models operates as a function with multi-dimensional inputs (representations) and a one-dimensional output (score). Consequently, we propose Kolmogorov-Arnoke Attention (KAA), which replaces the score mapping in existing scoring functions with KAN, KAA can be adapted nearly all scoring functions of attentive GNNs. With a comparable number of parameters, KAA achieves a lower Maximum Ranking Distance (MRD) compared to other linear transformation-base and MLP-based scoring functions, indicating that KAA possesses stronger expressive power. When the KAN utilized in KAA adheres to specific structure, it can achieve almost any score distribution, even with very limited number of parameters, demonstrating that KAN particularly well-suited for scoring functions. Furthermore, we validate the effectiveness of KAA across various attentive GNN backbone models. The experimental results align with our theoretical findings, showing that KAA-enhanced scoring functions consistently outperform the original scoring functions across all tasks and backbone architectures.
Overall, the contributions of our work can be summarized as follows:
We introduce unified form for the scoring functions of attentive GNN models and propose Maximum Ranking Distance (MRD) to quantitatively measure their expressive power.
Attention (KAA), applicable nearly all attentive GNN models. KAA integrates KAN learner into the scoring function, significantly enhancing expressive power compared to linear transformation-basedd and MI.P-ased attention in practical scenarios.
We propose Kolmogorov-
We conduct extensive experiments to validate the effectiveness of KAA across various backbone models and downstream tasks. The results demonstrate that KAA-enhanced models consistently outperform their original counterparts across all node-level and graph- level tasks, with performance improvements exceeding 20% some cases.
2 RELATED WORK
2.1 ATTENTIVE GRAPH NEURAL NETWORKS
GNNs have garnered significant interest and been widely adopted over the past few years. How- ever, most models (e.g., GCN (Kipf & Welling 2017), GraphSAGE (Hamilton et al. [017]. and GIN (Xu et al. 2019) assign equal importance to each neighbor of the central node, which limits their ability capture the unique local structures of different nodes. In response to this limitation, GAT (Veličković et al. 2018) was the first to introduce a simple layer with an attention mecha- nism to compute weighted average of neighbors' representations. The strong performance of GAT across various downstream tasks has sparked widespread interest among researchers in attentive GNN models. Attentive GNNs can be broadly categorized into two main types: GAT-based mod- els (Veličković et al., 2018 Kim & Oh (02T) and Graph Transformers (Nguyen et al. 2022 Zhang al., 2020). baTeb models assign varying weights nodes during the feature aggregation process based on their respective influences. Since the introduction of GAT, numerous variants have emerged, such as C-GAT (Wang et al. 2019), GATv2 (Brody et al. (02T), )) and SuperGAT (Kim & Ohl 2021) ). Additionally, many models (Jingg et al. 2019a] Cui et al., 2020 Yang et al. 2021: Lin jct al. 2022; Zhang & Gao 2021) have modified how GAT combines node pair representations and also categorized as GAT-based models. Graph Transformers (Rong al. 2020) are class of models based on Transformers (Vaswani et al. (017). which can directly learn higher-order graph representations. In recent years, Graph Transformers have rapidly advanced in the field of graph deep learning. These models (Dwivedi & Bresson 2020 Kreuzer et al. 2021]] Ying et al. [221]] Xia
al. 2021 Shi et al. 2020 Fang et | 20244 typically employ a query- key-vlue structure similar to that of Transformers and demonstrate superior performance on graph-level tasks.
2.2 KOLMOCOROV-ARNOLD NETWORKS
Kolmogorov-Aroot Network (KAN) (Lu et al. 2024b a is a novel neural network architecture inspired by the Kolmogoroy-Aroold representation theorem (Kolmogorov 1957 Braun & Griebel
3

---

Published as a conference paper at ICLR 2025
2009). designed alternative to MLP. Unlike MLP, KAN does not utilize linear weights. In- stead, each weight parameter between neurons is replaced by a univariate function parameterized as spline. Compared to MLPs, KAN demonstrates enhanced generalization ability and interpretabil- ity (Liu et 2024b). However, achieving good performance with KAN in practical applications can
be challenging (Altarabichi 2024a Le al., 2024 Altarabichi (024b). Drawing inspiration from KAN's remarkable success in symbolic regression (Ranasinghe et al. 2024, Seguel et al. 2024 (Shi
al. 2024) and PDE solving (Wang al. 2024 Rigas et 2024 Wu et al. 2024a). we recognize KAN s significant potential for fitting mappings with multi- mulli-diiensional inputs and one-dimensions outputs. Our use of KAN in this work also reflects its empirical effectiveness in these contexts.
PRELIMINARY
Graph Data and Graph Neural Networks. Let (V.E) E G represents graph, where V= {ui, ......, UN): ). & VVV x V denote the node set and edge set respectively. The node features can denoted as a matrix X = {I1, ,2,...,NNN E R where I, IRd is the feature of the node ui, and d is the dimensionality of original node features. A E {0, 1J denotes the adjacency matrix, where A,, = 1 (er, Uy) E E. Given a GNN model f, the node representation h, can be obtained layer by layer using the following expression:
h (++))) UPDATE (h." .AGG
Jero (h2) )n()))
where h: denotes the representation of u; at the I-th layer, with A = x4. AGG(.) denotes an aggregation function, such sum (e.g., GCN) or mean (e.g., GraphS aggregation. UPDATE(-) denotes a feature transformation function, such as a linear transformation or an MLP.
Unified Scoring Functions in Attentive Graph Neural Networks. Attentive GNN models in- troduce an attention mechanism in the aggregation function AGG(-) to adaptively assign different weight coefficient a, to each neighboring node Vy. which can be expressed as:
AGG (he, h,)
Σ anhJ JEN())
where ay obtained by normalizing the result of the scoring function. Here, the scoring function s(-) calculates the importance score of a neighboring node to the central node based on their respec- tive representations. The scoring functions of existing attentive GNN models can be categorized into two types (Sun et al. 2023): GAT-based and Transformer-based Their representative forms of
scoring functions are tollows:
s(h,, h2) LeakyReLU(aa" [Wh,l[Wh,))
(GAT-based)
(3)
s(h,, h1)) = (W,h.) Wwh, (Transformer-basol)
(4)
exp(s(h,,hy)
aj Eyen(o exp(s(h;,hp)) hy.))
(Normalization)
(5)
For GaT-based scoring functions, many variants substitute the concatenation operation of the two representations with alternative operations, such vector addition subtraction. In con- trast, Transformer-bast scoring functions often introduce additional scaling factors, such as / /dimadimk. We find that both types of scoring functions can be unified into the following general form:
s(h,, h2) = v AF)
(6)
where AF(-) Rd x Rdd + Rd is an alignment function without learnable parameters, such as concatenation or dot product. Its purpose is to combine the representations of the central node and the neighboring node. Additionally, ters, typically comprising several linear transformations and potentially some activation functions. Specifically. for the scoring function in Formula 3 the alignment function AF(-) is concatenation, while the score mapping Y consists of two consecutive linear transformations followed by activa- tion function. For the scoring function in Formula 4 the alignment function AF(-) can be expressed AF(hi, hy) hy. and its score mapping is given by v = (W,,), Wt-
Rd4 - R is the score mapping with learnable parame-
4

---

Published as a conference paper at ICLR 2025
Kolmogorov-Arnold Networks. The Kolmogorov-Amoll Amolld Representation theorem (Braun & Griebel 2009) states that, for a smooth function f [0, 1] +R
2x++1
[1 Fnd
pgp()p))
where Φ4 [0. R, and 0. : R This formulation illustrates that multivariate functions essentially be decomposed into well-defined composition of univariate functions, where the combination involves only simple addition. [iu et al. (2024b) extended the above expression into single-layer KAN, enabling it be stacked layer by layer like regular neural network. For single-layer KAN & with an input dimension of Tij and an output dimension of Nour
Vj E [1, Mout]
I
out
Di (2.")
where x; is the value corresponding to the i-th dimension of x. and di.j a learnable nonlinear func- tion, usually parameterized by B-spline functions (Liu et al. 2224bb radial basis functions (Li
2024 At this point, KAN is considered an alternative to MLPs and is applied to various tasks.
4 METHODOLOGGY
4.1
KOLMOCOROV-ARNOLJ ATTENTION
Inspired by the remarkable success of KAN in symbolic regression (Ranasinghe et al. [024 Seguel et al. 2024 Shi et al. 2024), which typically involves multi-dimensional inputs and one-dimensional outputs, as well as PDE solving (Wang al., 2024 Rigas al. 2024 Wu et 2024a), where common PDEs such as the heat equation or wave equation also feature multi- molli--dmensionall inputs and one-dimensional outputs, we find that KAN demonstrates significant potential for fitting mappings of the form f R - R with multi-dimensional inputs and one-dimensional outputs.
According to Formula the score mapping + also conforms this form. Therefore, we propose Kolmogorov-Amold Attention (KAA), which replaces V in the original scoring function with KAN, expressed as:
s(h,, hy) = KAN AF(h,, hy)
(9)
After obtaining the scores for node pairs, we compute the specific weight coefficients according to Formula 3 and perform the GNN aggregation as outlined in Formula 2 This design is highly flexible, allowing KAA be applied to nearly all existing attentive GNN models.
Building Multi-Head Attention. KAA can also be extended multi-head attention (Vaswani et al. 2017] Veličković et al. 2018), further enhancing its performance. When the number of heads K, we apply K independent KANs of the same scale (KAN' .... KAN*) to obtain K differ- ent weight coefficients according Formula g and 5] The resulting K representations then concatenated to form the final representations.
4.2 COMPARISON OF EXPRESSIVE POWER
In this section, we analyze the expressive power of different scoring functions. The primary purpose of designing the scoring function is to enable the model to adaptively assign varying aggregation coefficients to different nodes. This means that the scoring function should be capable of ranking the importance of neighboring nodes, allowing the central node to receive more valuable information. According to the unified form of scoring functions presented in Formula 6 AF(h,, h2) is derived from predefined alignment function AF(-) and the inherent inputs (h; and hy). which cannot be modified during training. Consequently, the expressive power the scoring functioo hinges on whether the learnable score mapping Vi can effectively map the various AF(h,, h2)) values to any desired importance ranking. We conduct quantitative analysis and comparison of the expressive power of different forms of scoring functions. First. we examine the limitations of existing standards used to evaluate the expressive power of score functions. Next, we introduce a more comprehensive evaluation metric: Maximum Ranking Distance. Finally, we quantitatively compare the maximum
5

---

Published as a conference paper at ICLR 2025
ranking distance of various scoring functions in practical scenarios. Through rigorous analysis, demonstrate that the application of KAA can significantly enhance the practical expressive power of the scoring function.
4.2.1 LIMITATION OF EXISTING MEASUREMENT
Many existing works QQuu et al.) 2018 Brody et al. 2021) have explored the expressive power of scoring functions in attentive GNNs. Brody et al. (2021) initiated this line of inquiry by analyzing the scoring function of GAT and proposed two standards for evaluating the expressive power of scor- ing functions: static and dynamic attention. Specifically, if the scoring function assigns the highest score the same neighboring node (key) for all central nodes (queries), it is said compute static attention. On the other hand, if the scoring function can assign different neighboring nodes (keys) the highest score for different central nodes (queries), it computes dynamic attention. More formal and detailed definitions of these two attention types are provided in Appendix A.2] Clearly, scoring functions that compute dynamic attention have stronger expressive power. However, applying this standard to evaluate the scoring functions of various existing attentive GNNs presents several chal- lenges. First, most existing scoring functions already compute dynamic attention, making it difficult to differentiate their expressive power using this criterion. Second, scoring functions that compute static attention can easily be adjusted compute dynamic attention. For example, the GAT scoring function in Formula 3 initially computes static attention, but by modifying it to the following form, can be converted to compute non-static attention:
s(h,, h2) = LeakyReLU(Abs(aa T. [Wh, Wh;l))
(10)
where we only add a negative sign and an absolute value function Abs(.). These limitations make the existing measurements for evaluating various scoring functions overly simplistic and imprecise.
4.2.2 DESIGNING COMPREHENSIVE MEASUREMENT
We observe that existing measurements are too coarse because they focus solely on the neighbor node with the highest score. In reality, the scoring function assigns scores to all neighboring nodes, forming an importance ranking of the neighbors, which we define as follows:
Definition 1 (Importance Ranking). Given a scoring function s(.), central node with representa- tion hi and all its neighbor nodes with representations {hyli E (i)),, an importance ranking is
a permutation of (i)), where a is bijective mapping [l, (W(I) + (1, (1)) that satisfies:
((h,,har)) S sh,, h((2)) ... S s(h,, ho(())))
(11)
In contrast to static and dynamic attention, which only focus on identifying the most important neighbor, importance ranking captures the relative importance of all neighboring nodes, offering a more comprehensive evaluation. In practice, scoring functions may not always achieve the optimal importance ranking under ideal conditions; instead, they approximate it as closely as possible. To quantitatively assess the difference between two rankings, we define the ranking distance as follows:
Definition 2 (Ranking Distance). Given two rankings, 01 and d2 of N nodes, the ranking distance RD between them can be calculated using the following formula:
N
RD( 02) = 11r
(12)
where o a- indicates the concrete rank of node i.
In real-world scenarios, the optimal ranking can be any permutation of neighboring nodes. There- fore, the expressive power of a scoring function lies in its ability to produce any possible ranking. Building on this, we introduce the concept of maximum ranking distance, which quantitatively mea- sures the expressive power of different scoring functions:
Definition 3 (Maximum Ranking Distance). Given family of scoring functions S. central node with representation h, and neighbor nodes with representations {hylū E (i),, any s E S, we denote the obtained importance ranking as as Meanwhile, the set of all permutations of (i) is

---

Published as a conference paper at ICLR 2025
denoted as II = { (I,..,,((()) - (1,..., (W) is bijection). The maximun ranking
distance (MRD) is expressed as below:
MRD(S, h,, (hyli (o))))
max min RD(ay, (0)
(13)
r'eft s'ES
4.2.3 THEERRETICAL COMPARISON
In this section, we delve into the analysis of the MRD for various scoring functions, specifically ex- amining three types: linear transformation-basedd attention, MLP-based attention, and our proposed KAA. These correspond to cases where the score mapping in Formula is a linear transformation, MLP, and KAN, respectively. Without loss generality, we assume that the selected central node is connected to all other nodes in the graph (as many graph transformers do), and that AF(,; h2) E Rd. We denote the alignment matrix of all AF(h, h2) as P E RNxd, where N is the number of nodes. For analytical simplification, we assume P is derived from the first d columns of a full-rank circulant A
matrix C E RNNN with N = d² (i.e., N > d). A more detailed and specific elaboration can be found in Appendix A.4
Linear Transformation-aale Based Attention. This type of scoring function is the most common, and the majority of existing attentive GNNs (Sun et al.] (003) can be classified under this category. Many practical implementations of scoring functions employ multiple consecutive learnable linear transformations (as seen in Formulas 3 and 4), but in theory, this does not enhance the expressive power compared to using a single fully learnable linear transformation, as multiple transformations are equivalent to single transformation equal to their product. Furthermore, scoring functions like the one in Formula B often include non-linear activation function. However, since most common non-linear activation functions are monotonic (e.g.. ReLU family and tanh), they do not alter the ranking of the scores. Therefore, we calculate the MRD for single linear transformation as:
Proposition 1 (MRD of Linear Transformation -asde Attention). Given the alignment matrix P E N xd. for a scoring function the form of s(hs; ht) W AF(hs, where W E TRdx1, its MRD satisfies the following inequality:
PR 1 ( 3d2 2d)
(14)
where Sur is the set of all candidate linear transformation-bar scoring functions.
We have established a lower bound for the MRD of the scoring function when the score mapping is a linear transformation. A more detailed derivation can be found Appendix A.5
MLP-Based Attention. To address the limitations of linear transformations in scoring functions, Brody et al. 2021) utilized a multi-layer perceptron (MLP) as the score mapping. While an MLP is universal approximator in ideal conditions (Cybenko 1989 Hornik 1991). its expressive power is often constrained by its limited width and depth in practical applications. Increasing the width and depth excessively can lead challenges in model convergence and may result significant overfitting (Oyedotun et al., (0177). To ensure consistency with the MLP size used by Brody et al. (202T) ,, we calculate the MRD for the scoring function where the score mapping consists of a two- layer equal-width MIP:
Proposition 2 (MRD of MLP-Based Attention). Given the alignment matrix P E Nxd, for scoring function in the form of s(h;, h2) W2 (ReL.U(W, AF(h, h2))), where W, E Rdxd and W2 E d its MRD satisfies the following inequality:
A) N MRD(SMLP. P) V (CN -d -NN---------- d)
NN3 N
(15)
12
where X = d3 3d + 2d and SMLP is the set of all candidate MLP-based scoring functions.
For MLP-based scoring functions, we have established both upper and lower bounds for their MRD. A more detailed derivation can be found in Appendix A.6
Kolmogorov-Arnol Attention. Finally, we calculate the MRD of our proposed KAA. The score mapping in KAA is KAN, which possesses representation theorem similar that of MLP. To ensure a fair comparison, we utilize a single-layer KAN with a comparable number of parameters to those in Proposition 2 as the score mapping:
7

---

Published as a conference paper at ICLR 2025
Proposition 3 (MRD of Kolmogorov-Amold Attention). Given the alignment matirx P R for scoring in the form of s(hs, h2) Σ (AF(F h2)x), where each @u is composed of d modified zero-order B-spline functions (x( = Ei= OKa Bx) its MRD satisfies the following inequality:
MRD(SKAA: P) 56, for for where SKAA is the set of all candidate KAA scoring functions.
(16)
A more detailed derivation can be found in Appendix A.7 The single-layer KAN scoring function contains df learnable parameters, which is slightly fewer than the (df + d) learnable parameters in the MLP from Proposition 2 Despite having fewer parameters, KAA maintains nearly unlimited ranking capability, establishing as the most expressive scoring function paradigm.
Theorem 1. Under non degenereee conditions, given the alignment matrix P E RR Nxd we have:
MRD(SKAA: P) S MRD(SMLP. P) S MRD(SLT: P)
(17)
From Theorem we can conclude that in practical scenarios with limited parameters, our proposed KAA exhibits the strongest expressive power. In contrast, MLP--asee attention also demonstrates notable improvement in expressive capability compared to linear transformation-base attention.
EXPERIMENT
In this section, we systematically evaluate the effectiveness of KAA across various tasks, including node-level tasks such as node classification and link prediction, as well as graph-level tasks like graph classification and graph regression.
5.1 EXPERIMENT SETUP
Backbone Models. Our proposed KAA can be applied to both GAT-based scoring functions, as shown in Formula 33 and Transformer-bawe scoring functions, as shown in Formula 4 Conse- quently, select three classical GAT-hased attentive GNN models with varying alignment func- tions as our backhone models: GAT (Veličković et al., 2018), GLCCN (Jiang et al.) (019h), and CFGAT (Cui et al. 2020). Additionally, we choose two Transformer-baut
models with distinct scoring functions as our backbone models: GT (Dwivedi & Bresson 2020) and SAN (Kreuzer al. 2021). The specific forms of the scoring functions are detailed Table
Table 1: A summary of the original scoring functions for various attentive GNN models and their KAA-enhanced counterparts. The central node representation denoted as h4, while the neighbor node representation is denoted as hj.
s(h,, hz)
Original Version
KAA Version
GAT
LeakyReLU((" [Wh,) ReL.U(a)
KAN(heellbs)) KAN( [h; - hu)) cos Cos(KAN(T)) (ha). KAN(H)))
GLCN CPGAT
hy))
LeakyReLU(coss/ (cos,Whh, Why))
GT
va (W,h) Wahy
KAN(h.) -hs KAN(k)) -
SAN
(W (W .uhh
Vd(++1)
Va(y+13
Implementations. For all models, we apply the dropout technique with dropout rates selected from [0. 0.1, 0.3, 0.5, 0.8). Additionally, we utilize the Adam optimizer, choosing learning rates from [10-3.5 x 10-3 10-2] and weight decay values from [0, 5 10-4]. Regarding model ar- GNN layers is selected from 2, 3, 4, 5,5 the hidden dimension from [8, 16, 32, 64, 128, 256]. and the number of heads from [1, 2, 4, 8]. For the KAN and MLP modules, we adopt an wiuhh-width structure across all models, with the number of layers chosen from [2, 3, 4]. In the KAN modules, B B-spline functions serve the base functions, with the grid size selected from [1, 2, 4, 8) and the spline order chosen from [1, 2, 3]. We conduct five rounds of experiments with different random seeds for each setting and report the average results.
chitecture, the number
8

---

Published as a conference paper at ICLR 2025
Table 2: Results of node-level tasks on various datasets. (The optimal results are in bold. "\
indicates out of memory limits, preventing full-batch training. "Avg Imp" calculates the average relative improvement of all KAA-enhanced models compared to their original versions.)
Task
Node Classification (Accuracy %)
Link Prediction (ROC-AUC %)
Model
Cora
CiteSeer
PubMed
oghn-arxiv
Photo
Computers
Cora
CiteSeer
PubMed
81,99
71.36
78.03
68.80
92.90
89,45
92.02
91,00
94,62
GCN
10.70
+0.57
+0.21
+0.44
10.12
40.22
20,73
40.40
20.06
81.48
69.70
77.50
68.68
93.26
88.84
91.28
87.65
91.62
GraphSAGE
10.41
10.63
40.23
10.34
20.15
20.54
10.35
20.23
79.85
77.89
85,34
89.27
85.84
91.31
GIN
#0.70
+0.89
#0.39
#0.56
#0.18
#1.30
#1.34
11.80
#1.09
82.76
72.34
77.50
68.62
92.87
89.76
91.48
90.28
94.03
GAT
10.74
1:0
a0.41
83,80
73.10
78.60
69.02
93.46
90.36
92.67
91.48
94.87
KAA-GAT
#0.49
#0.61
+0.50
+:0.49
2:.23
20.18
=0.35
10.71
20.19
82,26
71.76
78.10
68.37
92.70
88.98
91.60
90.36
94.34
GLCN
#0.89
+0.53
+0.1
#0. +0.60
#0.13
=0,10
=0.17
#0.79
#0.19
83.50
72.78
78.42
68.80 80
93.90
89.44
92.57
91.93
95.09
KAA-GICN
#0.70
+0.50
+0.1
#0.17
+0.30
=0.20
#0.43
#0.17
81.42
71.52
78.94
68.34
93.12
89.34
91.85
90.49
94.06
CEGAT
#0.70
+0.76
+0.333
+0.75
#0.17
#0.32
#0.35
#0.37
#0.06
83.72
72.66
79.04
69.59
93.33
89.71
92.58
91.45
94.71
KAA-CFGAT
#0.61
+0.78
+0.32
#0.59
+0.18
+0.15
=0.40
#0.50
=0.08
70.16
58.12
74.38
89.65
80.25
86.37
81.64
84,63
GT
#1.80
+1.52
+1.23
+1.54
+3.93
=0.81
#0.99
#4.32
71.86
61.92
75.16
92.82
89.05
86.97
82.35
88.38
KAA-GT
#1.34
+1.55
+0.80
40.22
40.30
=0.87
#1.74
#1.32
71.72
63.18
72.44
90.39
84,50
81.33
84.22
90.78
SAN
12,10
10.48
40.94
22.29
10.45
72.98
64.06
73.24
90.92
85,42
86.35
84.23
91.28
KAA-SAN
10.48
20.86
+1.30
20.86
20.58
=1.15
11.84
20.33
Avg 1mp1 (%)
+1.95
+2.39
+0.82
+1.01
+1.25
+2.73
+2.00
+1.00
+1.47
5.2 PERFORMANCE ON NODE-LEVEL TASKS
Datasets Involved. We conduct node classification and link prediction tasks to validate the effec- tiveness of KAA in node-level applications. For the node classification task, select four citation network datasets (Sen et al.) 2008 Hu et al., 2020) of varying scales: Cora, CiteSeer, PubMed, and ogbn-arxiv, along with product network datasets (Shchur et al.; 2018), Amazon-Computers and Amazon-Photo. The objective for the citation networks is to determine the research area of the papers, while the product networks involve categorizing products. For the link prediction task, we select three citation network datasets: Cora, CiteSeer, and PubMed, to predict whether an edge exists between pairs of nodes. More details and statistical information about these datasets can found in Appendix B.I Additionally, for all tasks, we employ three classical GNN models: GCN (Kipf & Welling 201 7), GraphSAGE (Hamilton et al. 2017). and GIN (Xu et al. 2019), as baselines.
Experimental Results. The results of KAA node-level tasks are presented in Table 2 The experimental findings indicate that KAA-enhanced models achieve superior experimental results compared the original models across all datasets, with an average improvement of 1.63%. This clearly demonstrates the enhancements that KAA provides to attentive GNN models in node-level tasks. For GAT-based models, none of the original attentive models outperform non-attention models on any dataset or task. This phenomenon suggests that the additional parameters in the ex- isting scoring functions do not effectively enhance performance. However, after applying KAA to these models, their performance improves significantly. All KAA-enhanced GAT- models out- perform non-attention models across all tasks and datasets. In contrast, Transformer-basse models do not perform as well on the involved node-level tasks. In these cases, the benefits from K.A. are even more pronounced. Specifically, KAA-enhanced models demonstrate an average performance improvement of 2.70% compared the original models. Overall, KAA can universally enhance the performance of attentive GNN models on node-level tasks, with improvements that can even bridge the performance gap between different models.

---

Published as a conference paper at ICLR 2025
Table 3: Results of graph-level tasks various datasets. (The optimal results are in bold. "Avg Imp" calculates the average improvement of all KAA-enhanced models compared to original ones.)
Task
Graph Classification (Accuracy %)
Graph Regression (MAE 4
Model
PPI (F1)
MUTAG
ENZYMES
PROTEINS
ZINC
QM9
GCN
60.48 +0.79
95.78 a5.15
29.33
45.58
71.71 +1.67
0.6863 40.0011
0.2715 +0.0080
GraphSAGE
77.95 =0.25
94.73
+5.76
24.67
+2.79
70.09
#2.44
0.6173
#0.0162
0.2733
#0.0030
GIN
70.29 +2.78
96.84
+4.21
33.34
+2.90
71.53 #2.64
0.4759 #0.0172
0.2524
#0.0035
GAT
83.84 =2.09
94.73
+4.70
29.23
#5.29
70.09
+2.50
0.6711
#0.0111
0,4749
#0.0158
KAA-GAT
86.62 #1.11
97.89
+2.57
34,46
#1.08
72.43
+1.67
0.5247 #0.0145
0.2124
#0.0085
GLCN
74.86 #1.15
96.84
14.21
31.35
+:439
71.17 11.88
0.6716
#0.0031
0.2716 #0.0168
KAA-GICCN
94.96 =0.26
98.94
#2.10
33.67
#2.03
72.25 #1.05
0.6351
=0.0202
0,2684
#0 +0.0205
CEGAT
75.90 #0.87
95.78
43.93
28.33
#3.37
70.27
+1.70
0.6779
#0.0031
0.2624
#0.0082
KAA-CRGAT
77.70 =0.57
98.94
#2.11
37.00
#3.58
72.79
#0.88
0.6726 #0.0045
0.2398
#0.0012
GT
94,50 #0.36
89.47
#3.33
50.33
+3.23
72.43
#1.22
0.5084
#0.0190
0.1067
#0.0128
KAA-GT
97.93 =0.17
91.58
#4.21
51.00
+5.73
72.75
#1.17
0.5042 #0.0240
0.1056
#0.0144
SAN
94.47 #0.21
90.53
+6.99
45,50
#5.06
71.89
#2.64
0.4935
#0.0252
0.1145
#0.0119
KAA-SAN
97.84 #0.14
90.79 26.84
49.00
#7.86
72.07
#2.05
0.4675
#0.0434
0.1076 +0.0049
Avg Imp (%)
+7.94
+2.28
+12.98
+1.82
+6.82
+14.42
5.3 PERFORMANCE ON GRAPH-LEVEL TASKS
Datasets Involved. We conduct graph classification and graph regression tasks to validate the effectiveness of KAA in graph-level applications. For the graph classification task, we select four datasets (Ivanov et al. 2019| Zitnik& & Leskovee (017) from bioinformatics and cheminformatics: PPI, MUTAG, ENZYMES, and PROTEINS. The downstream tasks for these datasets involve predict- ing the properties of proteins or molecules. For the graph regression tasks, we select two datasets: ZINC (Gómez-Bombarel) et al. 2018)) and QM9 (Wu et al. 2018). Both ZINC and QM9 are molec- ular datasets. The task for ZINC is to predict the constrained solubility of molecules, while QM9 involves regression tasks for 19 different molecular properties. More details and statistical informa- tion about these datasets can be found in Appendix [..] We also employ GCN (Kipf' & Welling 2017). GraphSAGE (Hamilton et al. 2017), and GIN (tu al. 2019) as baseline models.
Experimental Results. The results of KAA on graph-level tasks are shown in Table 3 The exper- imental findings indicate that KAA-enhanced models consistently outperform the original models across all datasets. Notably, the performance improvement of KAA in graph-level tasks is more pronounced than in node-level tasks. Specifically, KAA achieves an average performance enhance- ment of 7.71% across all graph-level tasks, with over 10% improvement observed in one-third of the tasks and more than 5% improvement in two-thirds of the tasks. This remarkable performance underscores the effectiveness of KAA in graph-level tasks. For GAT-based models, observe substantial performance gains in certain datasets with KAA, such as the enhancement of GLCN on the PPI dataset and GAT on the QM9 dataset. In these instances, KAA results in a qualitative leap in the performance of attentive GNN models, achieving improvements exceeding 20%. For Transformer-basee models, which generally perform better on graph-level tasks, KAA still yields an average performance improvement of 2.72%. Overall, the outstanding performance of KAA in graph-level tasks further demonstrates the significant enhancement in model performance achieved by incorporating KAN into the scoring function.
6 CONCLUSION AND OUTLOOK
In our paper, we introduce Kolmogorov-Armold Attention (KAA), which integrates KAN into the scoring functions of existing attentive GNN models. Through thorough theoretical and experimen- tal validation, we demonstrate that KAN is highly effective for the scoring process, significantly enhancing the performance of K.A.A Furthermore, our successful implementation of KAN in atten- tive GNNs may inspire advancements in KAN in other domains. Our comparative analysis of the theoretical expressive power of KAN-based learners versus MLP-based learners under constrained parameters offers valuable insights for future research.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
This work supported by NSFC (No. 62322606), Zhejiang NSF (LR22F020005), and CCF-Zhipu Large Model Fund.
REFERENCES
Diab W Abucidda, Panos Pantidis, and Mostafa E Mobasher. Deepokan: Deep operator network based on kolmogorov arnold networks for mechanics problems. arXiv preprint arXiv:2405. 2024.
Mohammed Ghaith Altarabichi. Dropkam: Regularizing kans by masking post-activations. arXiv preprint arXiv:2407.13044 2024a.
Mohammed Ghaith Altarabichi. Rethinking the function of neurons in kans. arXiv preprint arXiv:2407.20667, 2024b.
Zavareh Bozorgasl and Hao Chen. Wav-kan: Wavelet kolmogonov-amold networks. arXiv preprint arXiv:2405. /2832, 2024.
Jürgen Braun and Michael Griebel. On constructive proof kolmogorov's superposition theorem. Constructive approximation, 30:653-675, 2009.
Roman Bresson, Giannis Nikolentzos, George Panagopoulos, Michail Chatzianastasis, Jun Pang. and Michalis Vazirgiannis. Kagnns: Kolmogorov- arnold networks meet graph learning. arXiv preprint arXiv:2406.18380 2024.
Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? arXiv preprint arXiv:2105. Stti:::000..4491,, /4491, 2021.
Chaoqi Chen, Yushuang Wu, Qiyuan Dai, Hong- Yu Zhou, Mutian Xu, Sibei Yang. Xiaoguang Han, and Yizhou Yu. A survey graph neural networks and graph transformers in computer vision: A task-oriented perspective. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024.
Jinsong Chen, Kaiyuan Gao, Gaichao Li, and Kun He. Nagphormer: A tokenized graph transformer for node classification in large graphs. arXiv preprint arXi::2206.049100 2022.
Dongmei Cui, Fusheng Jin, Rong- Hua Li, and Guoren Wang. Cfgat: A coarse-to- fine graph attention network for semi-supervised node classification. In 2020 JEEE 32nd International Conference on Tools with Artificial Intelligence (ICTAI), pp. 1020-1027. IEEF, 2020.
George Cybenko. Approximation by superpositions sigmoidal function. Mathematics of control, signals and systems, 2(4):303-314, 1989.
P.J. Davis. Circulant Matrices. Monographs and textbooks in pure and applied mathematics. Wiley, 1979. ISBN 9780471057710.
Gianluca De Carlo, Andrea Mastropictro, and Aris Anagnostopoulos. Kolmogorov-arrold graph neural networks. arXiv preprint arXiv:2406. 18354, 2024.
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. arXiv preprint arXiv:2012.09699 2020.
Taoran Fang, Wei Zhou, Yifei Sun, Kaiqiao Han, Lvbin Ma, and Yang Yang. Exploring correlations of sele-super tasks for graphs. arXiv preprint 040.22400.04245,, 2024.
Remi Genet and Hugo Inzirillo. Tkan: Temporal Himnoorov-arnoke networks. arXiv preprint arXiv:2405.07344, 2024.
Rafael KömezzBBombaree Jennifer Wei, David Duvenaud, José Miguel Hernández-Lobato, Benjamín Sänchez-LLngeliing Dennis Sheberla, Jorge Aguilera-Ipanl Iparraguirre, Timothy D Hirzel, Ryan P Adams, and Alán Aspuru-Guza Guzik. Automatic chemical design using a data-driven contin- representation of molecules. ACS central science, 4(2):268-21) 276, 2018.

---

Published as a conference paper at ICLR 2025
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. Advances in neural information processing systems, 30, 2017.
Kurt Hormik. Approximation capabilities of multilayer feedforward networks. Neural networks, 4 (2):251-257, 1991.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:221 18 18-1822-22 22133, 2020.
Renhong Huang, Jiarong Xu, Xin Jiang, Ruichuan An, and Yang Yang. Can modifying data address graph domain adaptation? In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 1131-1142, 2024.
Renhong Huang, Jiarong Xu, Zhiming Yang, Xiang Si, Xin Jiang, Hanyang Yuan, Chunping Wang, and Yang Yang. Extracting training data from molecular pre-trained models. Advances in Neural Information Processing Systems, 012997948-977777 2025.
Sergei Ivanov, Sergei Sviridov, and Evgeny Burnaev. Understanding isomorphism bias in graph data sets. arXiv preprint arXiv:I910. 000.9100..2.,,11 12091, 2019.
Bo Jiang, Ziyan Zhang. Doudou Lin, Jin Tang, and Bin Luo. Semi-supervised learning with graph leaming--onvolutional networks. 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 11305-11312, 2019a.
Bo Jiang, Ziyan Zhang, Doudou Lin, Jin Tang, and Bin Luo. Semi-supervised learning with graph networks. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 11313-1320., 2019b.
Mehrdad Kiamari, Mohammad Kiamari, and Bhaskar Krishnamachari. Gkan: Graph kolmogorov- arnold networks. arXiv preprint arXiv:2406.0644 2024.
Dongkwan Kim and Alice Oh. How find your friendly neighborhood: Graph attention design with self-supervision. ICLR, 2021.
Thomas N Kipf and Max Welling. Variational graph auto-encoders. 0ass/6111.03000 2016.
In ArXiv, volume
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations, 2017.
Andrei Nikolaevich Kolmogorov. On the representation of continuous functions of many variables by superposition of continuous functions of one variable and addition. In Doklady Akademii Nauk, volume 114, pp. 953-956. Russian Academy of Sciences. 1957.
Irwin Kra and Santiago R Simanca. On circulant matrices. Notices of the AMS, 59(3):66--377, 2012.
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Re- thinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 111166111629,,,, 2021.
Tran Xuan Hieu Le, Thi Diem Tran, Hoai Luan Pham, Vu Trung Duong Le, Tuan Hai Vu, Van Tinh Nguyen, Yasuhiko Nakashima, et al. Exploring the limitations of kolmogorov-arrold networks in classification: Insights to software training and hardware implementation. arXiv preprint 1771v:2407.17799. 2024.
Ziyao Li. Kolmogonov-arnold networks are radial basis function networks. arXiv:2405.06721, 2024.
arXiv preprint
Lu Lin, Ethan Blaser, and Hongning Wang. Graph embedding with hierarchical attentive member- ship. In Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining, pp. 582-590, 2022.
12

---

Published as a conference paper at ICLR 2025
Ziming Liu, Pingchuan Ma, Yixuan Wang, Wojeiech Matusik, and Max Tegmark. Kan 2.0:
Kolmogorov-aroon armold networks meet science. arXiv preprint 3.Xi::2408..0205. 2024a.
Ziming Liu, Yixuan Wang, Sachin Vaidya, Fabian Ruchle, James Halverson, Marin Soljačíć, Thomas Y Hou, and Max Tegmark. Kan: Kolmogorov-arnold networks. arXiv preprint arXiv:2404. 19756, 2024b.
Dai Quoc Nguyen, Tu Dinh Nguyen, and Dinh Phung. Universal graph transformer self-attention the Web Conference 2022, pp. 193-196, 2022.
networks. In Companion Proceedings the
Oyebade K Oyedotun, Ebenezer O Olaniyi, and Adnan Khashman. simple and practical review of over-fitting in neural network learning. International Journal of Applied Pattern Recognition, 4(4):307-328, 2017.
Jiezhong Qiu, Jian Tang, Hao Ma, Yuxiao Dong, Kuansan Wang, and Jie Tang. Deepinf: Social influence prediction with deep learning. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 2110-2119, 2018.
Lakshmish Ramaswamy, Bugra Gedik, and Ling Liu. A distributed approach to node clustering in decentralized peer-to-peer networks. In TPDS, volume 16, pp. 814-829, 2005.
Nisal Ranasinghe, Yu Xia, Sachith Seneviratne, and Saman Halgamuge. Ginn-kan: Inter- pretability pipelining with applications in physics informed neural networks. arXiv preprint arXiv:2408. 14780, 2024.
Spyros Rigas, Michalis Papachristou, Theofilos Papadopoulos, Fotios Anagmostopoulos, and Geor- gios Alexandridis. Adaptive training of grid-dependent physics- -inforsdd kolmogorov-armol net- works. arXiv preprint arXiv:2407. 1, 2024.
Yu Rong, Yatao Bian, Tingyang Xu, Weiyang Xie, Ying Wei, Wenbing Huang, and Junzhou Huang. Self-supervised graph transformer on large-scale molecular data, Advances in neural information processing systems, 33: 1 2020.
Fabian Seguel, Driton Salihu, Stefan Hägele, and Eckehard Steinbach. VIp-kan: Low-complexity and interpretable rss-based vlp using kolmogorov-ammol networks. 2024.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al magazine, 29(3):93-93 93,, 2008.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv: 1.05868, 2018.
Yunsheng Shi, Zhengjie Huang, Shikun Feng, Hui Zhong, Wenjin Wang, and Yu Sun. Masked label prediction: Unified message passing model for semi-supervised classification. arXiv preprint arXiv:2009.03509, 2020.
Yunxiao Shi, Wujiang Wu, Mingyu Jin, Haimin Zhang, Qiang Wu, Yongfeng Zhang, and Min Xu. Beyond kan: Introducing karsein for adaptive high-order feature interaction modeling in ctr pre- diction. arXiv preprint arXiv:2408.088 08713, 2024.
Chengcheng Sun, Chenhao Li, Xiang Lin, Tianji Zheng, Fanrong Meng, Xiaobin Rui, and Zhixiao Wang. Attention-based graph neural networks: a survey. Artificial Intelligence Review, 56(Suppl 2):2263-2310, 2023.
Yifei Sun, Haoran Deng, Yang Yang, Chunping Wang, Jiarong Xu, Renhong Huang, Linfeng Cao, Yang Wang, and Lei Chen. Beyond homophily: Structure-awant path aggregation graph neural network. IJCAI, pp. 2233-2240. 2022.
Yifei Sun, Qi Zhu, Yang Yang, Chunping Wang, Tianyu Fan, Jiajun Zhu, and Lei Chen. Fine- tuning graph neural networks by preserving graph generative pattern.. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 9053-9061, 2024.
Ashish Vaswani, Noam M. Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In NIPS, 2017.
13

---

Published as a conference paper at ICLR 2025
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Guangtao Wang, Rex Ying, Jing Huang, and Jure Leskovec. Improving graph attention networks with large margin-based constraints. arXiv preprini arXiv: 1X10v1990..1944 11945, 2019.
Yizheng Wang, Jia Sun, Jinshuai Bai, Cosmin Anitescu, Mohammad Sadegh Eshaghi, Xiaoying Zhuang, Timon Rabezuk, and Yinghua Liu. Kolmogorov arnold informed neural network: A physics-informed deep learning framework for solving pdes based on kolmogorov arnold net- works. arXiv preprint arXiv:2406. 1045, 2024.
Haixu Wu, Huakun Luo, Yuezhou Ma, Jianmin Wang, and Mingsheng Long. Ropinn: Region optimized physics-informed neural networks. arXiv preprint urXiv:2405. 14369, 2024a.
Qitian Wu, Wentao Zhao, Chenxiao Yang, Hengrui Zhang, Fan Nie, Haitian Jiang, Yatao Bian, and Junchi Yan. Simplifying and empowering transformers for large-graph representations. Advances in Neural Information Processing Systems, 36, 2024b.
Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh Pappu, Karl Leswing, and Vijay Pande. Moleculenet: benchmark for molecular machine learn- ing. Chemical science, 9(2):513-5300 2018.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey graph neural networks. IEEE Transactions Neural Networks and Learning Systems, 32:4-24, 2019.
Lianghao Xia, Chao Huang. Yong Xu, Peng Dai, Xiyue Zhang, Hongsheng Yang, Jian Pei, and Liefeng Bo. Knowledge-enhanced hierarchical graph transformer network for multi-behavior recommendation. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pp. 4486-4493, 2021.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? ICLR, 2019.
Liang Yang, Mengzhe Li, Liyang Liu, Chuan Wang, Xiaochun Cao, Yuanfang Guo, al. Diverse message passing for attribute with heterophily, Advances in Neural Information Processing Sys- tems, 34:4751-4763 2021.
Chengxuan Ying. Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yan Liu. Do transformers really perform badly for graph representation? Advances in neural information processing systems, 01128877-28888 2021.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatehai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems, In SIGKDD, pp. 974- 983, 2018.
Chengkun Zhang and Junbin Gao. Hype-han: Hyperbolic hierarchical attention network for seman- tic embedding. Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence, pp. 3990-3996, 2021.
Fan Zhang and Xin Zhang. Graphkan Enhancing feature extraction with graph kolmogorov arnold networks. arXiv preprint arXiv:2406. 13597, 2024.
Jiawei Zhang, Haopeng Zhang, Congying Xia, and Li Sun. Graph-bert: Only attention is needed for learning graph representations. arXiv preprint arXiv:2001.05140, 2020.
Yiding Zhang, Xiao Wang. Chuan Shi, Xunqiang Jiang, and Yanfang Ye. Hyperbolic graph attention network. IEEE Transactions on Big Data, 8(6): 1690-1101 2021.
Marinka Zitnik and Jure Leskovec. Predicting multicellular function through multi-layer tissue networks. Bioinformatics, 33( 3311411110--1198, 2017.
14

---

Published as a conference paper at ICLR 2025
A EXTRA MATERIALS FOR SECTION 4
A.1 CONNECTION BETWEEN KAA AND EXISTING ATTENTIVE TECHNIQUES
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 distri- bution. Therefore, despite the significant advancements in existing attentive GNNs, KAA can still provide performance improvements, it represents enhancement from different perspective.
A.2 DETAILS OF EXISTING MEASUREMENT
A pioneering work (Brody et al. 2021) defines static and dynamic attention. Here, we excerpt their formal definitions from the original text understand the differences between static and dynamic attention and our defined MRD.
(Static Attention) A (possibly infinite) family of scoring functions F (R* x F + R) com- putes static scoring for a given set of key vectors K = [kk,,... kn} C Rd and query vectors Q= {9....., 4m) CRd, if for every f E F there exists "highest scoring" key jy E [n] such that for every query i [m]] and key j E [n]] it holds that f (q., k3,) 2 (qs, kz) We say that family of attention functions computes static attention given I and Q if its scoring function computes static scoring, possibly followed by monotonic normalization such softmax.
(Dynamic Attention) A (possibly infinite) family of scoring functions F (RRd x R + R) com- putes dynamic scoring for a given set of key vectors IK = (ki,.... kn CR and query vectors such that for any query E [m]] and any key }tr(1) [[n]: f (() > ff (q:, ky). We say that family of atten- tion functions computes dynamic attention for K. and Q, if its scoring function computes dynamic scoring, possibly followed by monotonic normalization such as softmax.
Q (q,,,,,,, [m) } R2. if for any mapping yp: [m]] > [r]] there exists ʃ
A.3 TRANSFORMING GAT INTO NON-STATIC ATTENTION
According to Formula 10 we add negative sign and an absolute value function to the original scoring function of GAT, which can be expanded as follows:
s(h,, h2)
LeakyReLLUAbbsaa
(18)
LeakyReL.U((o, Wh, + ax: Whyl)
(19)
LeakyReLUU((]) h, + bj h2l)
(20)
E 2g x1 and a.d represents the vector composed of the first d' dimensions, while aæ; represents the vector composed of the last d' dimensions. In Formula 20 we have 6, T W and by ag':" W. Here, we can consider b1, by E Rx as two free, learnable linear a
where W E Idd''e xd
transformations. For a specific central node h;, neighbor node h, with higher score needs to make |oT +h,+ -hyl as close to zero as possible, rather than maximizing it. Therefore, for different center nodes (queries) h;, there theoretically exist different neighbor nodes (keys) h; that can achieve the highest scores. It conflicts with the definition of static attention. Thus, the scoring function of the form in Formula I0 belongs non-static attention.
A.4 ASSUMPTIONS AND SETUP FOR THEORETICAL ANALYSIS
In this section, we elaborate on the theoretical setup and assumptions, as well as some simplifica- assume that the selected central node is connected all other
tions. Without loss of generality, nodes in the graph (as most graph transformers compute the relationships between all nodes this
way). Additionally, for clarity in notation, we assume that AF(hi, hy) Rd, and denote the align- ment matrix composed of all AF(h;, h2) E IRd values as P. Nxxd where N is the number of
15

---

Published as a conference paper at ICLR 2025
involved nodes. In fact, the composition of the matrix has significant impact subsequent anal- ysis. For example, if P = Nxå, then regardless of the form of the scoring function, all nodes will receive the same score. We can that if two nodes ji and have the same representations in P (i.e., Pj = P ).)) they are bound to receive the same score. Therefore, the distinguishability of P is crucial. To define a sufficiently distinguishable P, we first provide the circulant matrix C E IR NNN, which can be expressed
1
2
3
N
1
N
N
1
3
4
5
1
2
C
E ERRN
(21)
"
N N
1 N
N
3
2 N
N
2 N
-
C is a circulant matrix, so C is full-rank (Kra & Simanca 2012). Additionally, C is sufficiently distinguishable. Specifically, the elements in each column of C are all different, and the arrangement of the relationships between the elements in different columns is also unique. Ideally. if P = C, the scoring function will have sufficient representations to generate a variety of rankings. In our assumption, the width of P is d, which is much smaller than N. For analytical simplification, we assume that consists of the first columns of C, and has the following form:
2
3
d 1
d
2
3
4
d ++1
4
5
d+1
d+2
P
E exd
(22)
-
1
d
d d-2
N
2
d
d-1/
Such P will as the input for the respective scoring functions discussed later. In addition, make an assumption regarding the magnitudes of N and d: is much greater than d (N > d), and assume N = d². Finally, assume that to obtain importance ranking a, the scoring function s(-) must satisfy:
E []. =(
(23)
Here, we use s(P;) to replace s(h,, )t , as they convey the same meaning. Formula 23 establishes the connection between the score and the ranking, which is natural and fair. Based on this require- ment, the MRD Formula 13 can be specifically calculated as follows:
N Σ e'ell S'ES
MRD(S, P) max min
-s
(24)
where S is the of all candidate scoring functions, and 11 is the of all permutations N. The MRD of various scoring functions discussed later will all be calculated as Formula 24
A.5 DETAILS FOR MRD OF LINEAR TRANSFORMATION BASED ATTENTION
In this section, we provide a detailed proof of Proposition
Proposition 1 (MRD of Linear moansformation-Basee Attention). Given the alignment matirx P E xd for a scoring function the form of s(h,, hy) = W. AF hy), where W E Rdxx! its
MRD satisfies the following inequality:
M)
(N3 - -3 3d2 2d)
where Syy is the set of all candidate linear transformation-bar scoring functions.
Proof. For linear transformation-based scoring functions, they can linearly combine the column
vectors of P in Formula 22 obtain the final scores. Therefore, need to consider the range
16

---

Published as a conference paper at ICLR 2025
space of the linear combinations of P. In this case, series of column operations P will not affect the final result. First, starting from the second column P, we subtract the values of the previous column from each column to obtain P' as follows:
2
1
P
3
1
1 N
R
(25)
-
1
1
1-N
1
N
1-N
P', except for the first column, which remains =
[1,2,3 NNT, the other column vectors
consist of (N 1) ones and an (1 N) that gradually changes position. Then, starting from the third column of P', we again subtract the values of the previous column from each column and divide the resulting vectors by N obtain P follows:
1
1
2
3
1
0
0
0
1
P
E -
(26)
N
3
1
0
-
1
N N
1
1- N
The elements in P are composed in regular pattern, allowing it to be divided into two parts. The upper part consists of the first (N d) rows, denoted P :(++1-d) as shown below:
1
1
0
0
2
0
0
3
1
0
0
O
P (N+1--d)
0
0
E (N(+++-))xdd
(27)
7.
N +1
The scores of the first (N + 1 - d) nodes will be formed by linear combinations of the column
vectors of P :1y+1-d The lower part of P consists of the last (d 1) rows, denoted P as shown below:
(N+1-d);
N + N + d
0
P (1+))
p(d
(28)
- N-
-1
N
1-
The scores the last (d nodes will be formed by linear combinations the column vectors of PiN-1-d) According to Formula 24 the MRD can be split into two parts for calculation, as shown below:
N
MRD(S.r, P) max min r'ell S'E
Σ -
(29)
N+1-d
max min r'ell S'E
Σ (s'(P.) - -'' -
Σ (s'(P,) x1) (30)
j N
17

---

Published as a conference paper at ICLR 2025
In Formula 30 the calculation of the entire MRD is divided into two parts. The first part includes the scores of the first (N + 1 - d) nodes determined by P. ((++1dd) and the second part includes the scores of the last (d-1) 1) nodes determined by P [NN (1+1-d): According to Formula 27 the scores of the first (N++1 - d) nodes are composed of only two non-zero column vectors, [1, 2, 3,...... N 1-
R(N+1-d)x1 and E RNN-1-d)x1 Therefore, the score s(P;) satisfies the following equation:
vi [1, + d], s(P.) ai +
(31)
where a, b E R are two learnable parameters. According to Formula 28 the column rank of P I-d): is (d-1), 1), which means that P (N+1-dd) is full column-rank matrix. Therefore, Formula 30 can be scaled as follows:
N+1-d Σ -
MRD P) max min
Σ
(((P)) (32)
x x'Ell S'E
j=N+2-d
N+1-d
min E
max T'Ell
Σ
(s((P.) -'
Σ ( (33)
N+1-d Σ -
min S'E
max r'Ell
(34)
N+I-d
min
max E'Ell
Σ
(ai + b - b
(35)
a.BER
To maximize the term under the square root in Formula 35 the first (N -d) -d) elements of x''
should be uniformly distributed (i.e,,'=1(1) = 1, 2) = N, N (3) =2,x'-(44) =
1,...) Davis 1979.. In this case, the minimum value is obtained when a = 0 and N+1
Therefore, MRD P) has the following lower bound:
N+1-d Σ
MRD(SET: P) 2 min a.bER
max R'Ell
(ai + b b- (1)
(36)
2((N
N+1 )a (N - N+1
12
+
())
d
(37)
2
2
(N3 -
d 3d2 2d)
(38)
12
Now, we have completed the derivation of Proposition I
A.6 DETAILS FOR MRD OF MLP-BASED ATTENTION
In this section, we provide a detailed proof of Proposition 2
Proposition 2 (MRD of MLP-Based Attention). Given the alignment matirx P E Nxd for scoring function in the form of s(h,, h2) W2 (ReLU(W, AF(h,, hy))), where W1 E Rdxd and Wa dx its MRD satisfies the following inequality:
/ ((N d)3 (N d) x)
V
(N3 - N A) MRD(SMLP. P) V 12 12
where A = d3 3d + 2d and SMIP is the set of all candidate MI.P-based scoring functions.
Proof. We decompose the scoring process of the two-layer MLP-based scoring function into three parts: the first linear transformation W1. the nonlinear activation ReLU(-), and the second linear transformation W.. First, the initial linear transformation W, transform P. As in Appendix A.5 can also convert P from Formula 22 into the more analytically convenient form P Formula
18

---

Published as a conference paper at ICLR 2025
26
Additionally, P can still be divided into the upper part ((N-1-d) in Formula 27 and the
lower part P (N+1-dj: as in Formula 28 Next, we consider the impact of ReLU(.)) on the obtained scores. Specifically, ReL.U(-) is defined as follows:
ReIUU(x)) max(0,
(39)
The linear transformation produces a linear combination of the original column vectors, but ReLU(-)
will generate series of new column vectors. These newly generated column vectors serve as the basis for the second linear transformation, which then performs another linear combination. Pt (1+1-d) contains only two non-zero column vectors, and their linear combination, after applying ReLU((), results in the following set of column vectors C:
c caReLU [1,2,3, .... N. +1 d + 1) EC
(40)
C= [cl 3c 3 + c la 2a + b,.., ia + b, 0.. 0]
= 0, 0, ia (i 1)a b, .... (N + 1 d)a +b+
(41)
Next, we analyze the column vectors of ((++1dd): after the linear transformation and ReLU(.). Here, we focus on the last (d 2) columns of P (N+1-d):> which can be expressed as:
P
((++1-d):2-
0
:
E Rdd-1)x(d-2
(42)
-1
-1
0
By applying ReI.U(.) and the linear transformation, we obtain the following matrix M:
M =
[ReLU(P
(N+1-4):.2 (x+1-4)..))/ |ReLU(-PP J
(N+11-d):.)
(43)
0
0
0 0
1
0
"t.
:
(ddd-1)x(d-1)
(44)
0
0 1
0
0
0
M has ones on one diagonal, while all other elements are zero. Clearly, M is of full rank. Next, we will begin calculating the upper and lower bounds of MRD(SMLP P). First, we consider its upper bound. We assume that after the first linear transformation W1 and ReLU(-), obtain the following intermediate representations H:
(1
H
E Nxd
(45)
1 I-N N
M
H composed of the second column from P and M, and can be obtained through the linear transformation and ReLU(-) according Formula 43 Thus, MRD(SMLP, P) is transformed into
MRD(S H), which can be calculated as follows:
MRD(SMEP, P) <MRD(SIT, H)
(46)
N+1-d Σ
N Σ
max min e'ell S'Eu
2H +
(s'(H)) - x1)1
N=N+2-d
(47)
N+1-d
max min w'lll aeR
Σ a (-)'
(48)
In this case, the scores for the first (N + d) nodes are all the same, while the scores for the last
(d 11) nodes take any value due to the full rank of M. Therefore, compute Formula 48
19

---

Published as a conference paper at ICLR 2025
the first (N + d) elements of n' should be uniformly distributed (i.e,,T''(())
(1) =1,
N' (3) = 2, n' (4) = - ....) Davis 1979). In that case, a should be a+1 Thus, we can
obtain the upper bound of MRD
N+1-d
MRD(SMIP, P) S max min x x'ell aeR
Σ a- i=1
(49)
N+ )2 (N -
N +
d
2((N
)2 +
(2)
(50)
(N3 - d3 3d -2d)
(51)
12
Next, we calculate the lower bound of MRI((SMLP, P). Similar to Formula 30 have:
N
MRD(SMIP. P) = max min
Σ (s(P))
(52)
r'Ell S'SWa
N+1-d
N Σ -(P))-+''((1)
Σ (
max min
T' e'Ell S'ESUP
j=N+2-d
(53)
N+1-d Σ
max min r'ell S'EHUPP
(54)
To compute the lower bound of Formula 54 the intermediate representations H' should be entirely composed of the column vectors from the set C in Formula 41 Since the intermediate layer dimen- sion of the two-layer MLP is d. we can select at most d different column vectors to include in H'. To obtain the lower bound of MRD we expand the intermediate representations H' to retain the original column vectors [1. 2, 2, N + 1- d] E (N+1-4))x and E [(N-1-4)x1 from P (N++1dd)- while additionally selecting d column vectors from C that have all their zero values at the beginning. This simplification does not affect the results because the column vectors with zero values at the end can be derived from 3, N + d) by subtracting the vectors with zero values at the beginning, thus not affecting the range space. We denote the expanded intermediate representations as H E ((N+1-d)x(d+2) and denote its candidate set as H:
1
1
2
1
H
E H
(55)
:
:
C1
C2
Cd
N + d
Thus, can further expand Formula 54 as follows:
N+1-d
MRD(SMIP P) 2 max min E'E S'ES
Σ
-
(56)
N+I-d
max min min e'lll E'E E'ER
Σ -HH))-''111))
(57)
we have transformed the MRD of the MLP back into the MRD of a linear transformation. To reach the extremum, the first (N +1 d) elements of x' should also be uniformly distributed (11) = 1, (2) = N₂ (3) = 2, (4) = - 1,...) (Davis) 1979). In this case, any e; (including [1, 2, 3, N - d] is less effective than simply retaining the column vector z; with its first non-zero element:
According to Formula 57
[0. 0, ja + b, (j + + (
(58)
z, [0..... 0, b,0. 0 -11jsN+111
(59)
20

---

Published as a conference paper at ICLR 2025
Therefore, by replacing all c, with 2; (replacing 3.., d] with zo), construct new
intermediate representations Z' R [NN+1-d) and its candidate set is denoted as Z:
1
D'
E
(60)
20
21
22
2d
Then, we continue to calculate the lower bound of MRD (MMP, P):
N+1-d
MRI(SMLL. P)
max min x'ell s'ESa H
min
Σ
(s((H)) w7))
(61)
N+1-d d
min min e'Euu H
Σ -
(62)
N+1-d
min min S'Eu E
Σ (Z)
(63)
According to Formula 60 each 2; can provide an accurate score for a certain node. The (d + 1) column vectors from to zu should eliminate errors for the (d + 1) points that farthest from the mean, in order to achieve global optimality. Therefore, we have:
N+1-4 d
MRD(SMIP.) P) > min min
Σ
(64)
S'ESin EZ
=
N+1-d- 4M Σ i=1+41 1+1
min eER
(a-
(65)
12 ((N d)3 (N d)
d3 3d 2d)
(66)
Now, we have derived both the upper and lower bounds for MRD(SMLP. P) and completed the derivation of Proposition] 2
A.7 DETAILS MRD KOLMOGOROV-ARNOLD ATTENTION
In this section, we provide a detailed proof of Proposition 3
Proposition 3 (MRD of Kolmogorov- Attention). Given the alignment matirx Nxd for a scoring function in the form of s(h,, h2) Σd (AF((,, h2)k), where each on is composed of d modified zero-order B-spline functions dh (x) Σi_ Oea Bx)()), its MRD satisfies the
following inequality:
MRD(SKAA. P) 28, fo
(67)
where SKAA is the set of all candidate KAA scoring functions.
First, we present the specific expression for the modified zero-order B-spline functions B" (.) as follows:
0,
4 イ 1j+1 -
(x)
1. 1 S tj+1
(68)
0, otherwise
The modified (+) is not significantly different from the standard zero-order B-spline function, except that it reduces the domain where the function takes non-zero values. For each non-linear
21

---

Published as a conference paper at ICLR 2025
mapping function d()), it consists of d modified (+), shown below:
d
<<x)
a (T
(69)
In our assumption, have N = d,, and according to Formula 22 the elements in P take values from [1. Therefore, the grid size of (.) we used is also d, and its specific form is as follows:
0, (1 1)d $ 1
VIE [1 (x
1, 1 ld
(70)
0, otherwise
Then, we can express the scores of Pj E R lxd in the form consisting of B*(+) and learnable parameters as follows:
s(P,) Σ
ΦF (P 2.
(71)
d
CK BE, (P
(72)
k=
1=1
where Pj. E R is the k-th dimension value of Pj. According to Formula 70 we can observe that (-)-) only produces a non-zero value for integer input z E N when is divisible by d. For any
Pj. its d-dimensional values are composed of d consecutive integers, so there exists exactly one E [1,d] that satisfies d j.u. Therefore, only one (.).) activated. Specifically, we have:
Vj N and S S N, 3a, 3 N, 0 Sa, 3 < d-1, s.t. j ad B+1
(73)
By converting the row index j corresponding to P, into the form in Formula 73 we can obtain the value of s(P)) as:
s(P))
Cra B. (P
(74)
Jmn
-Cd-9,0+1
(75)
Therefore, MRD(SKAA, P) can be calculated follows:
N
MRD(SKAA P) = max min #'e E'SRAA
Σ (s(()))
(76)
1-1--1
max min e'eft s'ESKA
ss' Pad+0+1) - -'- - 8 1))²
(77)
0
d-1d-1 ΣΣ a= 8=0
max min
(ca- (cd 1))²
(78)
x'ell S'ES
According to Formula 78 for any permutation II. find group of ca-0,
a1 0. n (ad+
33 + 1) such that MRD P) can be made arbitrarily small. Thus, Proposition proven.
B MORE INFORMATION ON EXPERIMENTS
B. DETAILED DESCRIPTIONS OF DATASETS
Node-level datasets We employ 6 datasets for node-level tasks, which includes 4 citation network datasets Cora. CiteSeer, PubMed, ogbn-arxiv and product network datasets Amazon- Computers, Amazon-Photo. The statisties of above datasets presented in Table
22

---

Published as a conference paper at ICLR 2025
Cora, CiteSeer: PubMed, ogbn-arxiv: These 4 widely used graph datasets (Sen et al. 2008 Hu et al. 2020) represent the citation network, where nodes correspond to research papers. and edges indicate citation relationships. The downstream tasks typically involve classifying the research area of papers/researchers, and predicting the citation relationships.
Tanazon-Compucee Amazon- Photo: These are product networks (Shchur et al. 2018) from Amazon, where nodes represent goods and edges indicate that two goods fre- quently purchased together. The downstream task is to categorize goods to their corre- sponding product category.
Table 4: Statistics of node-level datasets.
Dataset
Nodes
Edges
Feature
Classes
Train/Val/Tess
Cora
2708
5429
1433
7
140 / 500 1000
CiteSeer
3327
4732
3703
6
120 / 500 / 1000
PubMed
19717
44338
500
3
60 500 1000
ogbn-arxiv
169343
1166243
128
40
90941 29799 48603
Amazon-Computers
13752
491722
767
10
10% 10% 80%
Amazon-Photo 7650
238162
745
8
10% 10% 80%
Graph-level datasets We employ another graph datasets for our graph-level tasks, which includes biological network dataset PPI, 2 chemical compound graph datasets MUTAG, ZINC, protein structure datasets PROTEINS, ENZYMES, and 1 quantum chemistry dataset QM9. The statistics of above datasets are presented in Table
PPI: This dataset Zitnik & Leskoved 2017) is a collection of biomedical system graphs, where each node represents protein, and each edge represents the protein-protein interac- tion. The downstream tasks often involves graph classification on the protein's 's properties.
MUTAG, ZINC: These datasets belong to chemical compound graphs, where nodes are atoms and edges chemical bonds. MUTAG (Ivanov et al. 2019) focuses on classifying compounds as mutagenic or non-mutagenic, while ZINC (Gómez- Glomez-Bombarelle et al.) 2018 focuses on predicting molecule properties related drug discovery.
PROTEINS, ENZYMES: These are 2 protein structure datasets (Ivanov al. 2019). The nodes here represent secondary structure elements in the protein and edges represent the interaction between them. PROTEINS is used to classify proteins enzymes enzymes, while ENZYMES categorizes the proteins into one of six enzyme types.
QM9: This dataset (Wu et al. 2018) is a collection small organic molecules. Nodes in the graph represent atoms, and edges represent chemical bonds. The dataset is used for predicting several quantum mechanical properties of a molecule.
Table 5: Statistics of graph-level datasets.
Dataset
Graphs
Nodes (avg)
Edges (avg)
Feature
Classes
Train/Val/Test
PPT
24
2414
33838
50
121
80%
10% 10%
MUTAGG
188
17.93
19.76
2
80%
10% 10%
ENZYMES
600
32,82
62.60
3
6
80%
10%
10%
PROTEINS
1113
39,72
74.04
80%
10% 10%
ZINC
12000
23.15
24.91
10000
1000 1000
QM9
130831
18.03
18.66
11
12
80%
10% 10%
B.2 COMPARISON WITH MLP-BASED ATTENTION
In this section, we compare the performance between our proposed KAA and the MLP-based based scoring function. The
scoring function is formally defined and analyzed by Brody et al. (222)) They proposed GATv2, which introduces an MLP into the scoring function based on GAT. We com- pare the performance of GAT, GATv2, and KAA-GAT four datasets: Cora, CiteSeer, PubMed,
23

---

Published as a conference paper at ICLR 2025
and ogbn-arxiv, with the results shown in Table 6 The experimental results show that KAA-GAT achieves the best performance on all datasets. Furthermore, although GATv2 has a stronger theo- retical expressive capability, it does not outperform GAT half of the datasets. These results also demonstrate that our proposed KAA not only possesses stronger theoretical expressiveness but also exhibits better performance downstream tasks.
Table 6: Results of accuracy (%) comparison between GAT, GATv2, and our proposed KAA-GAT.
Dutasct
Cora
CiteSeer
PubMed
ogbn-arxiv
Model
GAT
82.76 +0.74
72.34 #0.44
77.50 +0.75
68.62 #0.68
GATv2
82.95 +0.69
72.03 #0.66
78. 14 #0.38
68.31 #0.18
KAA-GAT
83.80 40.49
73.10 20.61
78.60 40.50
69.02 #0.49
B.3 COMPARISON WITH OTHER KAN-GNN VARIANTS
With the advent of the KAN architecture, some pioneering works (Kiamari et al. 2024 Zhang & Zhang 2024, Bresson et al. 2024| De Carlo al. 2024) have combined KAN with GNNs, leading to the development of various KAN-GNN variants. These works adopt similar approach by using KAN as a feature transformation function within GNNs. The specific implementations and complete experimental results of these works have generally not been made public by the authors. We gather the existing experimental results to compare them with our proposed KAA, as shown Table 7 The experimental results indicate that our proposed KAA-GAT achieves the optimal performance on these two node classification datasets Cora and CiteSeer. Additionally, KAA-GAT is the only model among these KAN-GNN variants that consistently outperforms classic GNN models.
Table 7: Results of accuracy (%) comparison between existing KAN-GNN variants and our pro- posed KAA-GAT.
Dataset
Cora
CiteSeer
Model
GCN
81.99 #0.70
71.36
#0.57
GraphSAGE
81,48 #0.41
69.70
#0.63
GIN
79.85
#0.70
69.60
#0.89
KAGIN
76.20 +0.77
68.37
#1.17
KAGCN
78.26 #1.77
64.09
#1.85
GKAN
81.20
69.40
KAA-GAT
83.80 #0.49
73.10 #0.61
B.4
TIME AND SPACE ANALYSES
Cora
CiteSeer
PubMed
(k)
t (ms)
(k)
(ms)
(k)
(ms)
GAT KAA-GAT
92.3
677.1
237.5
684.9
32.3
683.6
92.8
682.0
238.0
690.3
32.8
692.0
Table 8: Statistics of time and space cost.
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 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 required for each training epoch for both GAT and KAA-GAT on the Cora, CiteSeer, and PubMed
24

---

Published as a conference paper at ICLR 2025
datasets. The results in Table 3 show that most of the parameters in GNNs 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.
B.5 KAA ON ADVANCED ATTENTIVE GNNS
To verify whether KAA remains effective on SOTA attentive GNNs, we select two advanced GAT- based models (SuperGAT (Kim & Oh) 2021 and HAT (Zhang et al.) (021)) and two advanced Transformer-basee based models (NAGformer (Chen al. 2022) and SCFoorme (Wu et al., (024b))- These models integrate multiple techniques and feature relatively complex computation pipelines. We evaluate the effectiveness KAA on these advanced attentive GNNs and present a comparison of the results between the original models and the KAA-enhanced models node classification tasks. From 9 we can observe that even for various gegh-performance attentive GNN models, KAA still achieves significant performance improvements. KAA consistently delivers performance gains across all scenarios and achieves remarkable results on certain datasets. For instance, KAA enhances HAT's performance the ogbn-arxiv dataset by approximately 3%, which is quite impres- sive. In many cases, the performance gains brought by KAA surpass the performance differences between different models, highlighting the value of incorporating KAA.
Cora
CiteSeer
PubMed
ogbn-arxiv
Computers
Photo
SuperGAT
84,27 #0.53
72.71
#0.65
81.63 #0.55
71.55
#0.43
94.05 #0.49
91.77 #0.32
KAA-Supen AAp-SupeTGAT
84.45 =0.23
73.08
+0.28
81.72
#0.43
74.01
#0.67
94.65 +0.78
92.20 #0.22
HAT
83.67 #0.39
72.31
+0.23
79.67
#0.45
70.87
#0.65
93.77 #0.66
90.55 #0.34
KAA-HAT
84.01 +0.40
72.55 +0.64
79.90
#0.42
73.55
#0.76
93.80 #0.37
91.65 #0.40
NAGphormer
74.22 20.89
63.68
+0.85
76.34
20.76
91.23 +0.78
90.04
#0.22
KAA-NAGphormer
77.01
#0.91
#0.67 64.04
78.30 =0.55
91.42 #0.81
91.00 #0.45
SGFormer
75.46
#0.78
67.79
#0.26
79.89 #0.64
92.97 #0.44
91.06 #0,54
KAA-SGFormer
77.45
20.80
68.08 #0.77
80.03 20.97
93.08 #0.79
91.33 #0.59
Table 9: Accuracy (%) of KAA cooperated with advanced attentive GNNs on node classification.
25


Reviews:
[{"review_id": "JUQ7fFIoCH", "reviewer": "Reviewer_w7oB", "summary": "This paper introduces Kolmogorov-Arnold Attention (KAA), with a novel scoring method for graph attention. KAA enhances the performance of scoring functions and can be applied to nearly all existing attentive GNNs. To further analyze the expressive power of scoring functions in various graph attention mechanism, this paper introduces Maximum Ranking Distance (MRD) to quantitatively estimate their upper bounds in ranking errors. Extensive experiments on both node-level and graph-level tasks show the KAA can outperforms their original counterparts.", "questions": "Please refer to Weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Exploring KAN for graph attention is novel.\n2. Based on the analysis tool of graph attention in GATv2 [1], this paper proposes more powerful tools, Importance Ranking and Ranking Distance, to analyze the expressive power of graph attention.\n3. The KAA is extensively evaluated in various downstream tasks.", "weaknesses": "1. The motivation to redesign the graph attention with KAN is not convincing. Current graph attention and graph Transformer have provided very good performance. The authors are encouraged to illustrate when the proposed KAN will significantly outperform current graph attention, including GATv2 [1], and graph Transformer.\n2. I am confused by MRD theory. If there exists an optimum ranking for each node, and KAA always provides a good ranking that is very close to the optimum ranking, does KAA still needs multi-head attention? It seems that different attention heads will provide very similar attention. However, multi-head attention has been proven to be a very successful tech in attention.\n3. The assumption that \"the selected central node is connected to all other nodes in the graph\" is not realistic. Even graph Transformers [3] are trying to incorporate various graph structures, which violate the assumption.\n4. As claimed by the authors, the expressive power of KAA is much better than GAT and GATv2. However, better expressive power could result in severe overfitting [1]. I wonder how the authors tackle the severe overfitting issue in KAA.\n5. The inclusion of KAN would significantly increase the computational cost. Thus the authors are encouraged to compare its computational cost (, including both time and space) with current graph attention and graph Transformer.\n6. The comparisons with baselines could be unfair. The authors do not choose the recommended hyper-parameters as in the original paper or tune better results. For example, the dropout ratio in the GAT [2] paper is 0.6, and [2] achieves better results than the scores reported in this paper, under the same data split settings.\n\nI will raise my score if my concerns are properly addressed.\n\n---\n\n[1] How Attentive are Graph Attention Networks? In ICLR 2022.\n\n[2] Graph Attention Networks. In ICLR 2018.\n\n[3] Do Transformers Really Perform Bad for Graph Representation? In NeurIPS 2021", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6ggCDrMmk9", "reviewer": "Reviewer_kkV1", "summary": "This paper introduces a novel scoring function, Kolmogorov-Arnold Attention (KAA), which integrates the Kolmogorov-Arnold Network (KAN) architecture to enhance the performance of scoring functions in attentive Graph Neural Networks (GNNs). The authors propose a unified framework for scoring functions and introduce the Maximum Ranking Distance (MRD) to quantitatively measure their expressive power. Extensive experiments demonstrate that KAA-enhanced models outperform their original counterparts across various tasks and backbone architectures, with significant improvements in some cases.", "questions": "Check the questions below.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "### Strengths:\n\n1. The paper presents a creative approach to enhancing GNNs by integrating the Kolmogorov-Arnold Network into the scoring process, which is a novel contribution to the field of graph neural networks.\n\n2. The authors not only propose a new model but also provide a rigorous theoretical analysis of its expressive power compared to existing methods, backed by extensive experimental results that validate the effectiveness of KAA.\n\n3. The paper demonstrates substantial performance improvements over some baselines on both node-level, link-level, and graph-level tasks, highlighting the practical applicability and benefits of the proposed KAA framework.", "weaknesses": "### Weaknesses:\n\n1. I have one concern that despite the interesting introduction of KAA into the scoring function in graph attention networks, it is not that big to modify the architecture of attention computing mechanism for existing GNN community since there have been various GNN architectures beyond attention functions in the past years.\n\n2. Then in the experiments, the authors only compare with some **old and weak** baselines with shallow layers ( $\\le$ 4 layers), which further support my claim in the first concern.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ytCblhSg53", "reviewer": "Reviewer_nWMV", "summary": "leveraging Kolmogorov-Arnold Network (KAN), the authors proposed to use the KA attention to enhance attention-based GNN architectures. The paper provides extensive experiments to show that attention-based GANs are enhanced on both node-level and graph-level tasks across a wide range of benchmarks.", "questions": "1. Could you provide an empirical ablation study over the ranking methods proposed in section 4.2.2 to demonstrate the effectiveness of proposed MRD?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The authors provides a thorough analysis and recap over KAN and its application and components on attention-based GNNs, for example the expressive power of scoring functions and theoretical bounds of transform-based attention, MLP-based attention, and the proposed KAA. The theoretical analysis shows that KAA exhibits the strongest expressive power.\n2. Extensive experiments across a wide range of benchmarks for node-level and graph-level tasks show that KAA could provide moderate and consistent improvements.", "weaknesses": "1. The author provides a very interesting plugins for attention-based GNNs and shows relatively good improvement. I personally like this idea and it shows potential of KAA on graph applications. however, one major concern is that nowadays, attention is still considered not necessary for GNN architectures and many SOTA architectures did not utilize attention mechanism within their architecture design, e.g. [1] for node classification and [2] for link prediction. As a result, it would be better if there were more comparison with other SOTA GNN models who did not include attention mechanisms. This is a kind suggestion and new experimental results is not necessary.\n2. There seems to be lack of empirical analysis/ablation studies for different ranking methods proposed in section 4.2.2.\n\n[1] Li, Guohao, et al. \"Training graph neural networks with 1000 layers.\" International conference on machine learning. PMLR, 2021.\n[2] Zhang, Muhan, and Yixin Chen. \"Link prediction based on graph neural networks.\" Advances in neural information processing systems 31 (2018).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "c6fAG5Igtl", "reviewer": "Reviewer_nAy3", "summary": "In this paper, the authors unify scoring functions of current attentive GNNs and propose Kolmogorov-Arnold Attention (KAA), which integrates the Kolmogorov-Arnold Network (KAN) architecture into the scoring process. KAA enhances the performance of scoring functions across the board and can be applied to nearly all existing attentive GNNs. They also introduce Maximum Ranking Distance (MRD) to quantitatively estimate upper bounds in ranking errors for node importance. Experiments are provided on both node-level and graph-level tasks using various backbone models including KAA-enhanced scoring functions.", "questions": "I have a concern that the novelty of the work is limited as it seems to be mainly using KAN (already proposed), with other already proposed components such as multi-head attention, and MLP like components. Can the authors more clearly distinguish their contributions from prior works? \n\nTable 1 on the formulas are informative with many experiment benchmarks evaluated against. However, the GNN models seem to be quite outdated, and even the other benchmarks are mostly variant models of the author’s proposed KAA. Other KAN based benchmarks should also be provided.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The Architecture of the proposed model is overall clearly written, and the background on KAN is well introduced. \n\nTable 1 on the formulas are informative with many experiment benchmarks evaluated against.", "weaknesses": "Can the authors more clearly indicate why GAT’s attention mechanism which uses a learnable alpha weight via local neighborhoods is insufficient in terms of expressive power?  \n\nHow does KAA attention compare to the more informative hierarchical attention mechanisms? The author should discuss this in the Related Work section. Here are recent relevant papers on this topic: \n\n[WWW 2019] Heterogeneous Graph Attention Network. In The World Wide Web Conference (WWW '19). Association for Computing Machinery, New York, NY, USA, 2022–2032. https://doi.org/10.1145/3308558.3313562\n\n[IEEE ICDM 2021] \"Bi-Level Attention Graph Neural Networks,\" in 2021 IEEE International Conference on Data Mining (ICDM), Auckland, New Zealand, 2021 pp. 1126-1131.\ndoi: 10.1109/ICDM51629.2021.00133", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)