GrokFormer: Graph Fourier Kolmogorov-Arnold Transformers

We sincerely appreciate your constructive and positive comments on the filter design. Please see our response to your comments one by one below.

Question #1 In Specformer, MLP applied to each eigenvalue $\lambda$, which can learn to output for $\lambda^k$ theoretically.

We appreciate your insightful comment. While applying MLP to $\lambda$ in Specformer can help theoretically capture frequency information about $\lambda^k$, it does not necessarily enable the MLP in Specformer to effectively model spectral information across arbitrary filter orders $k$ due to its limited parameters and the lack of explicit learning for unknown $\lambda^k$. In contrast, our GrokFormer explicitly captures a diverse range of frequencies across different filter orders, ensuring a more expressive representation in the spectral domain.

Question #2 In multi-head attention, the residual connection might generate band/high-pass filters.

We really appreciate your comments. We'd like to clarify that [Ref1] has shown that although multi-head, FFN, and skip connection all help preserve the high-frequency signals, none would change the fact that MSA block as a whole only possesses the representational power of low-pass filters (see page 5 of [Ref1]). The theory is further supported by the experiments on the ZINC dataset in [Ref2]. These findings confirm that Transformer is essentially a low-pass filter, motivating our development of expressive spectral filters for graph Transformers.

• [Ref1] Anti-Oversmoothing in Deep Vision Transformers via the Fourier Domain Analysis: From Theory to Practice. ICLR, 2022.

• [Ref2] How Expressive are Transformers in Spectral Domain for Graphs? TMLR, 2022

Question #3 How necessary for the attention modules in the work? (Lack of statistical analysis from t-test).

In Table A1, we include a new dataset, Penn94 in ablation study and report the $p$-Value using t-tests on all datasets.

Table A1. Additional ablation study on Penn94.

Self-attention-E can generally capture global spatial relationships, preserving the similarity of node features. However, on the large-scale dataset penn94 with a low homophily level, relying solely on spectral information from Graph Fourier KAN may not be sufficient. Only when both Graph Fourier KAN and self-attention are integrated, GrokFormer can achieve consistently improved performance, with statistically significant differences ($p$ < 0.05) on the ablated GrokFormer models. This demonstrates that our GrokFormer is more than just a simple combination of self-attention and Graph Fourier KAN.

Question #4 The theoretical discussion of strong expressivity on WL test.

Please see our detailed response to Reviewer axD1's Weakness #3.

Question #5 and Question #6 Some expressive graph Transformers like GraphGPS and GRIT are overlooked in comparisons.

Please see our detailed response to Reviewer axD1's Weakness #1 and #2.

Question #7 The filter fitting experiments do not include graph Transformers in comparisons.

Both Polyformer and Specformer design filter functions h($\lambda$) in the spectral domain, which can be regarded as spectral graph Transformers based on a Transformer architecture. Besides Specformer, we added the Polyformer in filter fitting experiments to further verify the learning capability of our filter. Please refer to Table A3 in our response to Reviewer axD1's Weakness #4.

Question #8 'order-adaptive' and 'spectrum-adaptive' are vague. The term 'graph order' is used mistakenly.

We would like to clarify the "order-adaptive" in this paper is actually 'filter order-adaptive' in the spectral domain, rather than the spatial-domain order or 'graph order'. It refers to using the $k$-power of eigenvalues to approximate filters, analogous to polynomial filter approximation in the spectral domain. 'spectrum-adaptive' indicates that a full (or subset of) spectrum (eigenvalues) is used to approximate spectral filters, similar to the ability of the filter in Specformer. We will give a clear description to avoid the misunderstanding in our final version.

Question #9 Complexity claim

The overall forward complexity of GrokFormer is $O(N(Nq+d^2)+KqM)$, where we have $q=N$ on small-scale datasets. It is lower than that of related methods, e.g., Specformer with a complexity of $O(N^2(q+d)+Nd^2)$.

Question #10 Why not use full (regular) self-attention?

We replaced linear self-attention with regular attention (G-Reg) and conducted experiments, which show that both achieve comparable performance (Table A2), as they both capture non-local spatial features. We chose linear attention for its better efficiency.

Table A2. Accuracy comparison on attention type.

We sincerely appreciate your constructive and positive comments on methodology and experiment designs. Please see our response to your comments one by one below.

Weakness #1 The time consumption of preprocessing should be included in Table 8, and whether the proposed method achieves a trade-off between computational cost and expressiveness.

Thanks for your valuable suggestion. Following your suggestions, we measured the computational overhead (including preprocessing) on the small-scale dataset Squirrel and the large-scale dataset Penn94, with the results summarized in Table A1 below.

Table A1. The computational cost in terms of GPU memory required in MB, training runtime, and pre-processing time (s) on two datasets.

It is clear that our GrokFormer and Specformer are comparably fast, both of which requires much less computational cost than PolyFormer. Additionally, accuracy results of node classification on Squirrel show that spectral decomposition methods, such as GrokFormer and SpecFormer, achieve approximately a 20% improvement over the polynomial filtering model PolyFormer. On the large-scale graph dataset Penn94, while preprocessing takes some time, the forward-pass complexity can be reduced using truncated spectral decomposition. Moreover, since spectral decomposition is computed only once and reused during training, its cost becomes a minor one compared to the forward-pass cost when training for many iterations.

Weakness #2 and Question #1 Clarification from the authors about some guidelines to selecting order $K$ could be helpful.

Please see our detailed response to Reviewer Cg7z’s Suggestion #1 and Question #3, where we clarified the concern regarding the selection about filter order $K$.

Weakness #3 A deeper discussion between GrokFormer, PolyFormer, and Specformer should be included.

Specformer designs a learnable filter by performing self-attention on each eigenvalue (spectrum), which is a spectrum-adaptive spectral method. PolyFormer designs an adaptive filter by performing self-attention on $K$ bases with fixed filter order. Different from these two methods, GrokFormer meticulously designs a universal order- and spectrum-adaptive filter within a Transformer architecture to capture diverse frequency components in graphs. We will add this comparison in the related work section.

Question #2 How to understand the benefits of the higher-order filter base?

Higher-order filter bases can result in the following two benefits: (1) enrich the spectral representation through additional frequency components, and (2) strengthen the approximation power. These advantages facilitate more accurate signal distribution modeling in diverse graphs of various complexities. Our method leverages these advantages through an adaptive order selection mechanism that dynamically optimizes filter orders for datasets with varying properties, achieving large performance improvement over existing SOTA filters, e.g., achieving 21% improvement over the baseline PolyFormer with fixed-order filter bases on the Squirrel dataset.

We sincerely appreciate your constructive and positive comments on methodology design and theoretical analysis. Please see our response to your comments one by one below.

Weakness #1 Limited discussion on potential limitations or failure cases.

Thank you very much for the suggestion and question. We will provide a more comprehensive discussion of GrokFormer's potential limitations. One limitation is that when learning optimal spectral filters that requires the complete spectrum, the full spectral decomposition may lead to a huge computational cost on very large datasets, but this limitation do not affect the detection effectiveness of GrokFormer on a variety of real-world graph datasets. Please also find another limitation in our response to Reviewer axD1's Weakness #1 and #2, where we discuss that our spectral graph filter may miss some spatial structure information in some datasets.

Weakness #2, Question #2, and Suggestion #2 Can the model's efficiency be improved further by avoiding spectral decomposition entirely? Include runtime comparisons on larger-scale graphs beyond Penn94 for broader scalability insights.

Thank you for your insightful suggestion. Avoiding spectral decomposition entirely can further enhance the model's efficiency. To reduce computational costs, we can employ truncated spectral decomposition to compute only the top-$p$ eigenvalues in large-scale graphs. As shown in Table A1, we provide runtime comparisons on the arXiv dataset, which contains 169,343 nodes (larger than Penn94). By considering only the smallest 5,000 eigenvalues, our model remains computationally efficient even on large-scale datasets.

Table A1. The training cost in terms of GPU memory (MB) and running time (in seconds) on arXiv. 

Suggestion #1 and Questions #3 Clarify how hyperparameters like $K$ (order) affect performance across different datasets. How sensitive is the performance to hyperparameters like $K$ or the number of Fourier terms ($M$)?

Thank you for the valuable comments. In our model, both filter order $K \in [1,6]$ and Fourier terms $M \in [32,64]$ can empower the filter to include richer frequency components and enhance the fitting capability of filter. From the datasets description in Table 6 and the experimental results regarding the filter order $K$ in Figures 3 and 7, we can observe that (1) A smaller $K$ value is suitable for homophilic datasets and small-scale heterophilic datasets with sparse edges; (2) A larger $K$ value is suitable for large-scale heterophilic datasets and heterophilic datasets with dense edges. Similar observations can be obtained for Fourier terms ($M$), too.

Questions #1 How does GrokFormer handle dynamic graphs where the topology changes over time?

Like most competing methods, GrokFormer is designed for static graphs. Dynamic graphs, where the topology evolves over time, are not applicable in the current setting of these methods. We plan to extend GrokFormer to dynamic graphs in our future work.

We sincerely appreciate your constructive and positive comments on the presentation, visualization, and experiment design. Please see our response to your comments one by one below.

Weaknesses #1 and #2 Lack of a few challenging benchmark GNN datasets (datasets in [Ref1] and LRGB datasets [Ref2]) and two recent baseline methods (GraphGRS [Ref3] and GRIT [Ref4]).

Following your suggestion, we conducted the experiments on the two representative datasets, WikiCS and Peptides-func, obtained from [Ref1] and [Ref2] respectively, to further demonstrate the expressiveness of GrokFormer. Additionally, we also added the two new expressive GTs, GraphGPS and GRIT, as our competing methods. The experimental results are shown in Tables A1 and A2.

Table A1. Classification accuracy (in percent) on the WikiCS and Test AP on Peptides-func.

Table A2. Classification accuracy comparison of GRIT, GraphGPS, and GrokFormer.

The experimental results show that GrokFormer consistently outperforms all competing methods, including the newly added expressive GTs, in Table A2 and on WikiCS of Table A1. This is primarily because expressive GTs like GraphGPS and GRIT struggle to capture the underlying label patterns due to the Transformer's low-pass nature, resulting in suboptimal performance. Note that the spectral-based methods slightly underperform the expressive GTs that are specifically designed to capture the major spatial structure information in Peptides-func, which is not modeled by these general spectral methods. Thus, we believe that this suboptimal performance does not diminish our contribution in the proposed expressive spectral graph filters, considering its ability in enhancing the Transformer's capability to capture frequency signals beyond low-pass on graphs.

• [Ref1] Benchmarking Graph Neural Networks. JMLR, 2022.

• [Ref2] Long Range Graph Benchmark. NeurIPS, 2022.

• [Ref3] Recipe for a general, powerful, scalable graph transformer. NeurIPS, 2022.

• [Ref4] Graph Inductive Biases in Transformers without Message Passing. ICML, 2023.

Weakness #3 The theoretical expressivity discussion in terms of WL, and compare and contrast it with existing GTs, e.g. GRIT.

We would like to clarify that the spectral graph filter designed in GrokFormer is not based on the spatial-domain WL test. The GrokFormer is a spectral GT operating in the spectral domain while 1-WL or GD-WL algorithms are essentially spatial methods based on the graph structure. Therefore, GRIT exhibits better localization spatially, while our GrokFormer achieves better localization on frequencies. Although our work lacks a formal theoretical analysis in the spatial domain to discuss strong expressivity like the WL test, we provide theoretical analysis in the spectral domain to justify its advantages over existing advanced filters and show that our filter possesses better universality and flexibility. Moreover, the filter fitting experiment on synthetic datasets and comprehensive empirical comparison on real-world datasets demonstrate the stronger expressivity of our GrokFormer filter.

Weakness #4 Lack of numerical results for the filter design in Eq. (5). What other alternatives were considered? How were those results compared to this version of the filter?

We would like to clarify that we have pre-defined six different filters on the synthetic dataset in Section 5.3.1 to verify the fitting capability of the filter design in Eq.(5) compared to alternative methods. Here we present partial results in Table A3 as follows,

Table A3. Node regression results on two difficult synthetic datasets. 

Note that we use two metrics to evaluate each method: sum of squared error ($R^2$ score). Lower SSE (higher $R^2$) indicates better performance. The effectiveness of joint filter order-adaptive and spectrum-adaptive properties in Eq.(5) is empirically confirmed through its much better performance on such difficult synthetic datasets. Meanwhile, two simplified alternative cases (a) spectrum-only adaptation without high-order filter terms and (b) filter order-only adaptation are considered in the comparison above. Per Propositions 4.2 and 4.3, the filter variant in case (a) can be regarded as the Specformer filter, while the variant in case (b) corresponds to the GPRGNN filter. The results show that heir fitting ability of the GrokFormer filter is much stronger than the two alternatives.