Less but More: Linear Adaptive Graph Learning Empowering Spatiotemporal Forecasting

Thank you very much for your kind recognition. Your time and effort have been invaluable in significantly improving the quality of our paper.

---

W1.

a. The necessity of the kernel-inspired approximation

Our motivation is to design a linear yet expressive adaptive graph structure, and these two goals are achieved through the two components of MAGE (MOE+kernel linear approximation). Specifically, linearity is achieved via a kernel-inspired approximation method, while the subsequent customized sparse and balanced MOE strategy helps restore the model’s rank to its upper bound (full rank), thus enhancing its representational power.

b. Only MAGE simultaneously satisfies both linear and full-rank properties in existing adaptive graphs.

In fact, existing adaptive graph either possess full-rank characteristics (e.g., naive dot-product-based adaptive graph methods) but suffer from quadratic complexity, or emphasize linear complexity (e.g., relying solely on kernel-inspired dot-product approximations) yet are limited by low-rank constraints. Thus, there are another full-rank linear adaptive graph case. However, your question leads to another interesting one: what would happen if MOE were applied to a linear full-rank adaptive graph?

c. What if you directly apply MOE on the linear full-rank adaptive graphs, which completely avoid the low-rank bottleneck?

To address this problem, we designed a MAGE variant called “MOE+ Nai”, where we combine a sparse and balanced MoE strategy with a naive (full-rank) adaptive graph. The hyperparameter for the number of experts is kept the same. We report its performance and efficiency on the SD dataset.

Due to the quadratic complexity of the naive adaptive graph, this variant failed to improve performance and instead increased memory usage and training time. This is because our sparse and balanced MoE strategy is specifically designed for linear kernel adaptive graphs: by combining expert models that can capture different graph patterns, it enhances representational capacity and effectively achieves a full-rank approximation. However, when MoE is applied to a full-rank graph (which has already reached the upper bound of rank), it introduces redundant information, thus degrading learning performance. We provide further explanation in Section d(2).

d. This trade-off should be rigorously discussed and studied in the experiments. What is the Pareto frontier of this trade-off?

(1). To address your question, we designed a set of experiments with 16 fixed graph experts, where each expert corresponds to an adaptive graph. According to the paper, 16 experts can achieve optimal performance. We then varied the mixing ratio of linear kernel adaptive graphs and naive adaptive graphs (full-rank), maintaining the original balanced and sparse expert activation constraints. The experimental results are as follows:

We observed that gradually increasing the proportion of full-rank adaptive graphs does not provide additional performance benefits aside from reducing computational efficiency. Therefore, we believe that the original MAGE module design has achieved a Pareto optimal state.

(2). During this process, we observed an interesting phenomenon regarding the model’s expert selection behavior—its preference for linear adaptive graph experts over naive gadaptive raph experts. We used an 8:8 balanced ratio as a study example. Initially, the balance strategy forced the model to equally activate all 16 experts. In the variant, we introduced the concept of 'Inner Balance', allowing the model to adaptively choose between the linear graph expert family and the full-rank graph expert family, while maintaining balance in the activation of individuals within each family.

The results indicate that the Inner Balance variant not only improved performance but also revealed the model’s strong preference for linear kernel graph expert (94.7% vs. 5.3%). The default global balance (53.1% vs. 46.9%) inadvertently forces the model to retain overfitting full-rank experts, which can harm generalization ability. This further provides evidence of the incompatibility between MOE and full-rank adaptive graphs.

---

W2.

That’s a very innovative question. Using the SD dataset as an example, we integrated MAGE into the following four advanced spatiotemporal learning models: AGCRN, GWNet, STGCN, and STID. We reported their average performance over 12 time steps.

We observe that MAGE is able to improve the performance of these models to varying degrees, which demonstrates the good applicability of our method.

Thank you very much for your kind recognition. Your time and effort have been invaluable in significantly enhancing the quality of our paper. We truly appreciate your support and constructive feedback.

W1. Typos of numerical formatting

Thank you for this valuable suggestion. In the camera-ready version we will perform a meticulous proof-read of every numeric entry in the tables to ensure a uniform, consistent format throughout.

---

---

W2. Experiments of edge noise induced by ReLU

We conducted a comprehensive experimental study (reported in Appendix D6: Experimental Evaluation of the Detrimental Effects of ReLU in Adaptive Graph Learning), which confirms that removing the ReLU activation consistently improves both prediction accuracy and convergence speed. Specifically, we selected four representative models—GWNet, AGCRN, and D$^2$STGNN—that incorporate the adaptive graph convolution module, and evaluated them on four real-world datasets spanning diverse domains. The results provide strong empirical support for our theoretical claims. For your convenience, we reproduce a subset of these results below.

---

---

W3. More Spatiotemporal Baselines

In the main experiments, we have already covered 17 open-source and publicly available advanced spatiotemporal models. Unfortunately, the code for LLGformer [1] has not been released. To address your concern, we introduce STGformer [2] as an additional baseline and evaluate it on four datasets across three domains. The results are reported below.

---

---

W4. More discussion about MoE in Spatiotemporal Learnings

• CP-MoE [3] targets the spatiotemporal congestion classification task. Its MoE design relies on two graph experts that separately learn periodic and non-periodic congestion patterns.

• ST-MoE [4] tackles learning imbalance in spatiotemporal tasks by stacking multiple STGNNs into an MoE network, allowing each node to select an appropriate STGNN.

In contrast, our MoE module aims to "restore the rank upper bound of linear adaptive graph convolution": we employ a minimal set of graph convolutions to mitigate the inherent low-rank bottleneck commonly found in linear-complexity designs. Additionally, we introduce a sparse and balanced modulation strategy to regulate the learning behavior of individual experts. As a result, both the objective and mechanism of our approach are fundamentally distinct from those of the aforementioned works. Unfortunately, no open-source implementations of CP-MoE or ST-MoE are currently available, making direct performance comparisons infeasible. We commit to including a detailed discussion of these models in the next version of the manuscript.

---

---

Q1. Avoiding Knowledge Redundant in Experts.

We achieve this goal by integrating a load balancing mechanism to ensure that each graph expert is utilized evenly during training, while sparse gating enables each node to select only the most suitable experts. Together, these mechanisms encourage each expert to focus on capturing distinct underlying patterns. Additionally, based on matrix theory, we carefully control the number of experts to further prevent knowledge redundancy.

Ref:

[1] Jin, D., Huo, C., Shi, J., He, D., Wei, J., & Yu, P. S. (2025, April). Llgformer: Learnable long-range graph transformer for traffic flow prediction. In Proceedings of the ACM on Web Conference 2025 (pp. 2860-2871)

[2] Wang H, Chen J, Pan T, et al. Stgformer: Efficient spatiotemporal graph transformer for traffic forecasting[J]. arXiv preprint arXiv:2410.00385, 2024.

[3] Jiang W, Han J, Liu H, et al. Interpretable cascading mixture-of-experts for urban traffic congestion prediction. Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2024: 5206–5217.

[4] Li S, Cui Y, Zhao Y, et al. ST-MoE: Spatio-temporal mixture-of-experts for debiasing in traffic prediction. Proceedings of the 32nd ACM International Conference on Information and Knowledge Management. 2023: 1208–1217.

Thank you very much for your kind recognition. Your time and effort have been invaluable in significantly improving the quality of our paper. We truly appreciate your support and constructive feedback.

W1. PatchSTG issues

We apologize for any confusion caused. PatchSTG model requires the latitude and longitude information of each node as additional input to determine which patch each node belongs to. However, due to the potential absence of such geographical data in publicly available datasets, the input requirements of the PatchSTG model cannot be met. Consequently, it fails to execute on certain datasets.

---

---

W2. Time series baselines

Time series models perform poorly in spatiotemporal prediction tasks because they only model dependencies between time steps while ignoring the crucial spatial dependencies among nodes [1].

To address your question, we compared the performance of the MAGE model with time series models based on different architectures, including the Transformer-based PatchTST, the convolution-based TimeMixer, and the MLP-based DLinear, on the SD and KnowAir datasets, as shown below.

The results demonstrate that MAGE still exhibits the best performance on the aforementioned datasets, validating the effectiveness of our model.

[1] Shao Z, Wang F, Xu Y, et al. Exploring progress in multivariate time series forecasting: Comprehensive benchmarking and heterogeneity analysis[J]. IEEE Transactions on Knowledge and Data Engineering, 2024.

---

---

W3. Performance of expanding more experts.

Blindly increasing the total number of experts does not improve performance; on the contrary, it may lead to overfitting the training data and result in decreased generalization ability. According to our matrix theory, once the number of experts exceeds a certain threshold, the model’s expressive power reaches its upper limit. As shown in Figure 2(b) in Section 5.3 of this paper, we systematically varied both quantities and reported the corresponding results. The experimental findings indicate that when the number of experts is too large, model performance actually drops.

---

---

Q. Potential for scalability

MAGE exhibits a computational complexity that scales linearly with the number of nodes, demonstrating strong theoretical scalability. Furthermore, we evaluate MAGE on XTraffic—the largest publicly available spatiotemporal dataset to date, containing 16,972 nodes. The results show that MAGE still achieves the best accuracy, further validating its excellent scalability. In contrast, several more complex models fail to run due to their high computational demands. For convenience, we present below the performance comparison with several state-of-the-art models.

We sincerely thank you for your professional advice and the time you have dedicated. We have gained valuable insights, and based on your feedback, we can significantly enhance the quality of our paper.

---

---

W1.

The methods in [1, 2] are computationally efficient variants of the Transformer model, characterized by high model complexity and a large number of parameters. In contrast, the dot-product adaptive graph module requires only two learnable embeddings for pairwise dot-product calculations, making it significantly more lightweight and simplified. This approach also offers good ease of integration and has consequently been widely adopted. For these reasons, we have chosen the dot-product adaptive graph learning method as the foundation of our research.

To demonstrate this through experiments, we addressed a critical limitation: the works [1, 2] focus on graph representation tasks and lack the temporal modeling elements needed for spatiotemporal prediction. To ensure a fair comparison, we integrated the graph learning methods from MAGE and [1, 2] into mature spatiotemporal prediction models GWNet and AGCRN by replacing their adaptive graph modules. We then assessed their performance and complexity, under optimal performance settings, on the SD dataset. The results are summarized below.

We discovered that integrating these Transformer variants into the model actually led to decreased performance, along with a significant increase in the number of parameters and memory usage.

Based on your suggestions, we will integrate these discussions and related recent advancements into the manuscript in future revisions. Thank you again for your advice.

---

---

W2.

Thank you for your valuable insights into graph learning, which will inspire our future research.

Allow me to clarify first: our research is focused solely on the specific downstream task of spatiotemporal prediction, and does not aim to develop a general-purpose GNN applicable to various downstream tasks.

In the field of spatiotemporal forecasting, (1) Datasets often lack essential ancillary information necessary for evaluating properties such as connectivity, which can limit the comprehensive analysis. (2) The effectiveness of traditional GNNs that rely on a shared global graph structure is being questioned. Currently, adaptive graph learning methods dominate the field. The main reasons are as follows:

• Poor-quality or even non-constructable graph topology. Unlike general graph learning settings, graphs in most spatiotemporal prediction datasets are not naturally occurring but are constructed using secondary measures such as geographical proximity. These distance-based graphs fail to capture other critical global properties, such as connectivity, cyclicity, and community structure. In some cases, even global graphs derived from geographic information are unavailable due to privacy concerns.

• There is a lack of relevant prior data to validate the advantages of GNNs with shared global graphs. Most datasets lack the necessary prior knowledge, such as community labels or actual inter-regional connectivity, which hinders the evaluation of the advantages of GNNs with unified global graph in terms of properties like symmetry, normalization, or spectral attributes. These limitations further restrict the direct assessment of model interpretability.

We can take a different perspective: perhaps we can integrate the adaptive graph learning method MAGE into GNNs based on unified global graph.

In this way, it can retain the advantages of MAGE while also inheriting the strengths of traditional GNNs. To explore this possibility, we have incorporated MAGE into GWNet and STGCN by performing multi-graph convolution using both the adaptive adjacency matrix and their global graphs. The following results demonstrate that MAGE can improve the performance of GNNs based on unified global graph, which inspires our future work in designing hybrid graph convolutional networks.

---

---

W3.

The ultimate goal of spatiotemporal forecasting is to improve prediction accuracy. Beyond the core adaptive graph learning component, our MAGE model consists solely of simple fully connected layers; therefore, its performance gains are primarily attributable to the proposed adaptive graph learning method. This is extensively validated by the ablation studies in Figure 2 of the paper. These two evidences directly prove the effectiveness of our graph learning approach.

Thank you for your suggestion to include additional graph evaluations. We appreciate your feedback and would like to provide the following response.

• Experiment

A well-structured graph topology should effectively reflect the similarity among node labels. To evaluate the quality of the learned graph topologies, we first integrate three advanced methods—MAGE, [1, 2], and the original adaptive graph learning—into GWNet, thereby isolating the evaluation from potential difference factors introduced by other model components. We then report the mean squared error (MSE) between the generated adjacency matrices and the similarity matrix derived from node labels, providing a quantitative measure of how well the learned structures capture label coherence.

The adjacency matrix learned by our model shows the smallest difference with respect to the node label affinity, which provides a solid foundation for accurate prediction by the model.

• Visualization

Due to the NIPS rebuttal policy prohibiting the inclusion of any images, we promise to add more visualizations of generated graphs in the final version. These cases will demonstrate the association between the learned adjacency matrices and the patterns of data distributions.

---

---

W4.

We have done this experiment! As emphasized in line 115 of the manuscript, we provide experimental evidence for this theory, with the results shown in Appendix D.6.

Specifically, we demonstrate across four datasets and multiple models employing the adaptive graph learning module that removing the ReLU activation function improves prediction performance, as shown in Table 6. Furthermore, as illustrated in Table 7, removing ReLU also accelerates model convergence. For convenience, we reproduce a subset of results on the SD dataset below. These findings provide strong empirical evidence supporting the effectiveness of our design choice.

（2）We added the ReLU function to the proposed MAGE model and compared its performance with the original MAGE, as shown in the table below. This result also serves as valid experimental evidence.

---

---

Q1. MAGE has nothing to do with ReLU.

MAGE is Not simply to counteract the side effects introduced by using a kernel-based approximation scheme as a replacement for the ReLU activation function!**

As emphasized in the abstract, introduction, and methods sections, MAGE and the ReLU noise theory improve two distinct components including in adaptive graph learning framework—namely, RuLE and the vector dot product—and represent independent improvements. Therefore, MAGE is not designed to mitigate any side effects that may arise from replacing the ReLU activation function with a kernel-based approximation scheme. Specifically,

• RuLE Noise Theory: This theory reveals that RuLE introduces noise, leading to performance degradation, and thus we remove it. As demonstrated in W4, this modification does not introduce any side effects; on the contrary, it brings performance improvements.

• MAGE: MAGE is designed to address the challenge of high computational complexity in dot product operations. First, we propose kernel-based functions as efficient alternatives to dot products. Then, we introduce a sparse yet balanced mixture-of-experts system to enhance expressive power.

To further avoid confusion, we will revise the last paragraph of the introduction and the methods section to highlight the relationship between the two, namely that we have made independent improvements to the two components of dot-product-based adaptive graph learning.

Ref:

[1] Huang, Siyuan, et al. "Tailoring self-attention for graph via rooted subtrees." Advances in Neural Information Processing Systems 36 (2023): 73559-73581.

[2] Qian, Chendi, et al. "Probabilistic Graph Rewiring via Virtual Nodes." The Thirty-eighth Annual Conference on Neural Information Processing Systems.

Dear Reviewer tEm8,

Thank you very much for your thorough review. If you have any further questions, we would be happy to discuss them with you.

For your convenience, we have summarized our responses as follows:

• For W1. More comparative baselines. We used experiments to demonstrate the superiority of our model compared to the two works you are concerned with.

• For W2. Non-natural spatiotemporal graphs contain limited information. Unlike in graph learning tasks, the graph of most spatiotemporal prediction datasets is constructed based on the geographical locations of nodes (not naturally derived), and therefore contains limited symmetry, normalization, or spectral properties.

• For W2. Lack of spatiotemporal data for evaluating global properties. The lack of prior data in spatiotemporal datasets prevents the evaluation of certain global property advantages of GNNs with shared global graphs, such as community structure or connectivity. And GNNs with shared global graphs are gradually being replaced in the field of spatiotemporal prediction.

• For W3. Graph-level evaluation. We present an experiment that demonstrates a stronger correlation between our generated graph and the node prediction values.

• For W4. Experimental evidence for ReLU theory. We clarified that we have already supported our claims about ReLU with experimental evidence in the paper, please refer to Table 6 in the submission.

• For Q1. MAGE and ReLU noisy theory are independent. We clarify the independent roles of ReLU noise theory and MAGE, which are respectively designed to address the limitations of two components in traditional adaptive graph learning.

Once again, thank you for your professional feedback. Based on your suggestions, we will make dedicated efforts:

(1). Based on your suggestions, we commit to making significant revisions to the paper, including adding more visual examples and analysis of adaptive graphs for graph-level validation and further discussing related works in the field of graph learning.

(2). Your comments have inspired us to collect a new dataset with more spatiotemporal prior data to better align the developments of the spatiotemporal learning domain with the graph learning domain.

We sincerely recognize how valuable your time and attention are, and we are profoundly thankful for any additional insights or advice you may share.

Thank you again for your kindness and support.

Best regards,

The Authors of Submission 425