PaperlayerView exact revision on arXiv

Source-linked AI summary

SqLinear: Balanced Square Partitioning Makes Linear Interaction Sufficient for Large-Scale Traffic Forecasting

Yongfeng Su, Hongwen Li, Zijian Zhang, Ziquan Fang, Lu Chen, Christian S. Jensen, Hong Gao, Yinjun Han

arXiv:2606.21072v2cs.LGcs.AI

TL;DR

Traffic models face scalability challenges on networks with thousands of sensors, and existing partitioning can produce imbalanced or irregular patches. SqLinear pairs geometry-adaptive Square Partition with Hierarchical Linear Interaction. The paper reports state-of-the-art accuracy across four large-scale datasets and 11 baselines, with a limitation for abrupt, highly nonlinear dynamics.

  • Problem

    Neural traffic models face scalability pressure on real-world sensor networks, while existing partitioning can yield imbalanced or irregular patches.

    Source: §1 · pp. 1–2

  • Method

    SqLinear combines geometry-adaptive Square Partition with Hierarchical Linear Interaction for global inter-patch communication and per-node refinement.

    Source: §1 · pp. 2–3

  • Results

    SqLinear achieves state-of-the-art accuracy across four large-scale datasets and 11 competitive baselines, with favorable accuracy-efficiency trade-offs and superiority when scaling sensor-network size and prediction length.

    Source: §1 · p. 3

  • Takeaways & Limitations

    SqLinear is designed to capture complex spatio-temporal dependencies while avoiding the quadratic overhead of existing methods.

    Source: §6 · p. 9

    The linear interaction module may have limited capacity for abrupt, highly nonlinear dynamics such as those caused by traffic accidents.

    Source: §D.6 · p. 16

Abstract

from arXiv · show

Traffic prediction is a core task in intelligent transportation systems and urban-scale decision making. Despite the effectiveness of mainstream neural network-based methods, their deployment in real-world settings with thousands of traffic sensors is severely jeopardized by their poor computational scalability. To address this, the community has attempted to incorporate spatial database partitioning techniques to improve model scalability. However, these approaches rely on handcrafted geometric heuristics and often produce irregular or imbalanced data partitions, leading to boundary fragmentation, excessive padding overheads, and degraded model accuracy. In this paper, we propose SqLinear, an efficient and effective architecture for large-scale traffic prediction. First, we design Square Partition, a geometry-adaptive algorithm that partitions massive traffic sensors into balanced, non-overlapping, and compact spatial regions. Unlike existing heuristic-based designs, Square Partition is theoretically grounded and provides provable guarantees on partition utilization and split balance, establishing a high-quality foundation for downstream spatio-temporal modeling. Next, we propose a Hierarchical Linear Interaction (HLI) module that abandons the costly attention mechanisms commonly used in Transformer-based spatio-temporal models. HLI efficiently propagates global inter-region dependencies and refines them at the node level through a lightweight linear interaction scheme, enabling effective spatio-temporal modeling with linear computational complexity. Extensive experiments on four large-scale traffic datasets and 11 baselines show that SqLinear reduces MAE by 2.30% on average under the standard setting and by up to 6.78% under extreme scalability settings, while reducing training runtime by 13.27%--30.84% in spatial- and horizon-scaling scenarios.

1 Introduction

Traffic forecasting models face deployment challenges at city scale, while existing spatial partitions can be imbalanced or geometrically irregular. SqLinear combines geometry-adaptive partitioning with linear interaction to support scalable spatio-temporal modeling.

1 Introduction

  • Mainstream graph and Transformer models face computational scalability pressure across sensor count and forecasting horizon, complicating deployment in city-scale systems.California’s monitoring system has nearly 20,000 sensors; global quadratic interactions at that scale entail hundreds of millions of pairwise interactions per time step.Source: §1 · p. 1
  • Grid and Quadtree partitions can be imbalanced with empty regions, while K-D Tree partitions can be elongated and fail to preserve traffic-node neighborhoods.These deficiencies can reduce computational benefits and the ability to capture complex spatial dependencies.Source: §1 · p. 2
  • Traffic-oriented partitioning must balance patch node counts, avoid padding, and preserve compact spatial layouts that retain short-range locality.The introduction notes that PatchSTG requires padding 8,600 CA-dataset nodes across 512 patches to size 24, adding 43% computational overhead.Source: §1 · p. 2
  • After partitioning, models must recover cross-patch information without costly graph computation or quadratic attention, while retaining per-node dynamics and handling longer prediction horizons.For 512 patches, quadratic attention computes and stores 262,144 pairwise scores per layer.Source: §1 · p. 2
  • SqLinear combines balanced, compact spatial partitioning with hierarchical linear interaction, and is reported to achieve state-of-the-art accuracy across four large-scale datasets and 11 competitive baselines.The introduction also reports favorable accuracy-efficiency trade-offs and superiority when scaling sensor-network size and prediction length.Source: §1 · pp. 2–3

2 Related Work

The paper defers its comprehensive review of spatio-temporal prediction and deep-learning patching strategies to Appendix A, while Table 1 provides a quick comparison with closely related methods.

2 Related Work

  • A comprehensive review of spatio-temporal prediction and deep-learning patching strategies is deferred to Appendix A.Table 1 highlights distinctions between SqLinear and closely related methods for quick comparison.Source: §2 · p. 3

3 Preliminaries

The preliminaries describe traffic sensors and their spatio-temporal observations, then formulate prediction as mapping historical observations to future traffic states for each sensor.

3 Preliminaries

  • A traffic monitoring system contains fixed sensor nodes distributed over a road network, each representing a physical observation point.Examples include loop detectors, camera stations, and road-segment sensors.Source: §3 · p. 3
  • Spatio-temporal observations are represented as X ∈ R^(T×N×D), with each sensor recording D traffic variables at each time step.The variables include traffic flow, average speed, and occupancy; each node has latitude and longitude coordinates.Source: §3 · p. 3
  • Traffic prediction maps H historical time steps to F future time steps, forecasting each sensor node’s state rather than an aggregate for a road network or area.The mapping function is parameterized by learnable parameters θ.Source: §3 · p. 3

4 Methodology

SqLinear combines spatio-temporal embeddings, geometry-adaptive square partitioning, and hierarchical linear interaction for traffic forecasting. Its partitioning balances compact spatial regions, while HLI exchanges global patch context and refines node representations.

4.1 Spatio-Temporal Embedding Layer

  • Temporal convolution and time-of-day, day-of-week, and node-identity embeddings are concatenated into each node’s spatio-temporal representation.The temporal embedding uses the most recent input step’s time indices.Source: §4.1 · p. 3

4.2 Geometry-Adaptive Square Partition

  • Square Partition recursively splits along the longer coordinate span, choosing capacity-aware split positions until each region contains at most C nodes.Nodes are sorted by coordinate along the selected axis before splitting.Source: §4.2 · p. 4
  • Longest-axis splitting and capacity-aware positions guarantee bounded partition imbalance and padding-free tensorization without forced shorter-axis cuts.The stated imbalance bound is at most C.Source: §4.2 · p. 5

4.3 Hierarchical Linear Interaction

  • HLI first communicates across patches, then refines each node with global context; its factorized inter-patch projection has complexity linear in P for fixed rank r.Per-node refinement uses position-wise transformations, while the low-rank projection models patch relationships.Source: §4.3 · p. 5, §4.3.1 · p. 5

4.3.1 Inter-Patch Communication.

  • HLI differs from dense all-token mixing by using geometry-adaptive patches and decoupling global communication from local refinement; training-data measurements motivate its low-rank patch model.The leading component captures 97.3%–98.0% of cumulative Frobenius energy across four datasets, and rank 1 reaches both the 90% and 95% thresholds.Source: §4.3.1 · pp. 5–6

4.4 Output Layer

  • The output layer reverses the patching permutation and applies regression convolution to predict traffic features for the next F time steps.Unpatching restores node representations to their original indexing.Source: §4.4 · p. 6

4.5 Topology-Aware Extension

  • For road-aware partitioning, constraining each patch to one Road ID lets the geometry-first strategy recursively divide long roads into balanced segments.This avoids mixing sensors from different highways and prevents contamination from geometrically adjacent but topologically distinct roads.Source: §4.5.1 · p. 6, §4.5 · p. 6

4.5.2 Topology-First Road Grouping.

  • When topological continuity takes priority over geometric proximity, topology-first grouping assigns all nodes with the same road ID to one group without further geometric subdivision.The strategy is intended for short, uniformly structured roads or settings prioritizing topological coherence.Source: §4.5.2 · p. 6

5 Experiments

Experiments compare SqLinear with 11 baselines on four large-scale traffic benchmarks, covering standard and extended horizons, computational efficiency, ablations, and additional analyses. SqLinear achieves the best reported standard-setting performance and maintains strong accuracy and efficiency as forecasting horizons and sensor scales increase.

5.1 Experimental Setup

  • The experiments cover four large-scale benchmarks and 11 baselines spanning graph-based, transformer-based, and linear forecasting paradigms.The standard setting uses 12 historical steps to predict 12 future steps.Source: §5.1 · p. 6, Table 2 · p. 7

5.2 Overall Performance Comparison (RQ1)

  • SqLinear reduces MAE by an average of 2.30% and MAPE by 5.89% against the strongest competing method on each dataset under the standard 12-step setting.It consistently achieves the best performance across all datasets and evaluation metrics; Table 2 compares graph-based, attention-based, and linear models.Source: §5.2 · p. 6, Table 2 · p. 7

5.3 Long-Horizon Generalization (RQ2)

  • Across 16 dataset–horizon combinations, SqLinear achieves the lowest MAE, reducing it by an average of 3.17% and up to 6.78% versus the strongest competitor.The evaluation uses 96 historical observations and forecast horizons of 48, 96, 192, and 672 steps; the performance gap generally remains stable as the horizon increases.Source: §5.3 · p. 7, Figure 4 · p. 7

5.4 Efficiency and Scalability Evaluation (RQ3)

  • Under the standard setting, SqLinear occupies a favorable accuracy-efficiency region, with the lowest forecasting error, low runtime, and moderate peak GPU memory.Figure 5 plots runtime against MAE, with bubble size indicating peak GPU memory.Source: §5.4 · p. 7, Figure 5 · p. 8
  • On the largest CA dataset, SqLinear reduces per-sample training time by 46.78% on average versus the most efficient baseline in each long-horizon setting.At 672 steps, it ranks first across all datasets and achieves an average speedup of 17.04%; its memory use on 672-step CA is 31.4GB, lower than PatchSTG and RPMixer while supporting a larger batch size than PatchSTG.Source: §5.4 · p. 8, Figure 6 · p. 8, Table 4 · p. 8

5.5 Ablation Study (RQ4)

  • Replacing Square Partition with Grid, Quadtree, or K-D Tree degrades performance, as do alternating-axis and median split variants.The authors attribute these results to imbalanced or irregular patches, padding, and the importance of selecting both split axis and split point for balanced, padding-free tensorization.Source: §5.5 · pp. 8–9
  • Removing either HLI branch reduces performance, while replacing FeatureMixer with attention adds computational overhead without outperforming HLI.The inter-patch branch communicates across patches; the intra-patch branch refines information at each node.Source: §5.5 · pp. 8–9

5.6 Additional Experiments (RQ5, RQ6, RQ7)

  • Hyperparameter sensitivity, partition-strategy comparisons, and a learned-spatial-dependency case study are deferred to the appendix.These analyses address RQ5, RQ6, and RQ7, respectively.Source: §5 · p. 6, §5.6 · p. 9

6 Conclusion

SqLinear combines adaptive square partitioning with hierarchical linear interaction to model spatio-temporal dependencies while avoiding quadratic overhead. Its workflow embeds and patches sensor representations, processes inter- and intra-patch information, then reconstructs predictions.

6 Conclusion

  • SqLinear combines adaptive square partitioning and hierarchical linear interaction to improve traffic forecasting accuracy and efficiency while avoiding quadratic overhead.The conclusion describes SqLinear as a linear architecture for large-scale traffic forecasting.Source: §6 · p. 9

A.1 Spatio-Temporal Prediction

  • Prior traffic models include statistical and deep-learning approaches; STGNNs are prominent, while attention-based methods carry high computational costs.Efficiency-oriented methods can also sacrifice explicit spatial reasoning for non-local dependencies.Source: §A.1 · p. 11

A.2 Patching Strategies in Deep Learning

  • Square Partition targets traffic forecasting with capacity-aware splits, coordinate-adaptive axis selection, and padding-free patch representations.The cited work contrasts this design with patching strategies for other modalities and general spatial indexing.Source: §A.2 · p. 11

B Algorithm

  • Square Partition selects a split axis by comparing coordinate spans, then chooses a capacity-aware split point and recursively partitions the node set.The final patches are the recursively partitioned subsets.Source: B Algorithm · p. 12
  • The workflow embeds historical, temporal, and spatial features, groups node representations into patches, and reconstructs predictions from final patch representations.The final reconstruction uses Unpatch followed by reverse convolution.Source: B Algorithm · p. 12
  • Each HLI layer first communicates across patches, then refines each node representation using that context.The model repeats this inter-patch communication and intra-patch refinement across L layers.Source: B Algorithm · p. 12

C Theoretical Analysis

  • Square Partition is analyzed for capacity-bounded tensor units, high utilization, controlled split imbalance, and distribution-dependent compactness.The theoretical analysis also considers low-rank projection capacity and model complexity.Source: C Theoretical Analysis · p. 12

C.1 Analysis of Spatial Partition

Square Partition is assessed by whether it avoids padding, balances recursive splits, and creates compact spatial neighborhoods. Its guarantees address patch utilization and split balance, while compactness is evaluated empirically.

C.1 Analysis of Spatial Partition

  • When C divides N, Square Partition creates full patches with no padding; otherwise, at most C−1 padded entries are required in total.The divisible case has P = N/C patches, each containing C nodes, and utilization η = 1.Source: §C.1 · p. 13
  • For every split of a region with more than C nodes, the node imbalance δ is at most C.The bound is tight when the region contains 3C nodes.Source: §C.1 · p. 13
  • Square Partition selects the axis with the longest span, whereas depth-alternating K-D Tree has no such per-region guarantee and can increase a child’s aspect ratio when it splits the shorter axis.In the stated K-D Tree case, the aspect ratio increases from α to α/ρ.Source: §C.1 · p. 13
  • Because a region’s bounding box also depends on its selected nodes’ spatial support, the paper evaluates compactness empirically in Table 7.Region aspect ratio, defined from longitude and latitude spans, serves as the compactness diagnostic.Source: §C.1 · p. 13

C.2 Analysis of Low-rank Projection

The analysis characterizes the approximation capacity and cost of SqLinear’s factorized inter-patch projection, then describes model complexity and the experimental dataset and forecasting setup.

C.2 Analysis of Low-rank Projection

  • The best rank-r approximation error for an ideal dependency matrix is determined by its discarded singular-value tail, which is small when the empirical spectrum decays rapidly.The factorized projection can represent the best rank-r approximation of the matrix.Source: §C.2 · p. 13
  • Under the stated shared-factor assumptions, the inter-patch projection uses 2Pr parameters, has rank at most Cr, and costs O(Nr) operations per feature channel without materializing an N×N matrix.The rank bound applies to the isolated bias-free projection before residual addition; residual additions and nonlinear feature transformations are not rank-bounded by that statement.Source: §C.2 · pp. 13–14

C.3 Complexity Analysis

  • With r ≤ d in the reported settings, the HLI block has O(N·d^2) time and O(N·d) space complexity.The time bound follows from the FeatureMixer operations and low-rank communication cost.Source: §C.3 · p. 14

D.1 Detailed Experimental Setup

  • Experiments cover four datasets with 716–8,600 sensors; the standard protocol uses 12 historical steps to predict 12, with longer horizons also tested.The long-horizon study uses 96 historical steps and forecasts 48, 96, 192, or 672 steps across the datasets.Source: §D.1.1 · p. 14

D.1.1 Datasets Description.

SqLinear is compared with 11 standard-setting baselines, and its long-horizon results are best across all reported dataset-horizon combinations and metrics.

D.1.1 Datasets Description.

  • SqLinear uses AdamW with an initial learning rate of 0.001 and weight decay of 0.0001; runtime is measured as training wall-clock time and inference latency as evaluation latency.Experiments use PyTorch on an NVIDIA RTX A40 GPU with 48 GB of memory.Source: §D.1.2 · p. 14

D.1.2 Implementation Details.

  • The standard-setting comparison includes 11 baselines from GNN, linear-model, and attention- and expert-based families.Long-horizon comparisons use STID, RPMixer, BigST, and PatchSTG.Source: §D.1.3 · p. 14

D.2 Long-Horizon Prediction Performance

  • SqLinear achieves the best MAE, RMSE, and MAPE across all 16 dataset-horizon combinations, including the 96⇒672 setting.The reported gains remain stable as prediction length increases.Source: §D.2 · p. 14

D.3 Hyperparameter Study (RQ5)

The study examines how patch size, interaction depth, and low-rank dimension affect SqLinear. Its reported choices reflect trade-offs in spatial granularity, graph scale, and representation capacity.

D.3 Hyperparameter Study (RQ5)

  • Accuracy peaks when patch size C and patch count P are numerically balanced; SqLinear performs best at C=48 on GBA and C=86 on CA.Larger patches span richer local neighborhoods, but overly large patches reduce the granularity of global interaction.Source: §D.3 · pp. 14–15
  • Larger graphs such as CA require deeper interaction layers, while shallower models suffice for smaller graphs; excessive depth can add computation and overfit smaller datasets.Source: §D.3 · p. 15
  • A moderate low-rank dimension r is sufficient for latent spatial relations; larger values can add redundancy and memory use without clear accuracy gains.Source: §D.3 · p. 15

D.4 Partition Strategy Analysis (RQ6)

Square Partition is reported to outperform topology-first partitioning in forecasting accuracy and to achieve full utilization and perfect balance in empirical partition measurements. The case study illustrates its patch structure and examines learned spatial dependencies.

D.4 Partition Strategy Analysis (RQ6)

  • Square Partition achieves better forecasting accuracy than GFRP and TFRG, whose irregular or unbalanced groups are less suited to efficient tensorized modeling.The authors attribute the architecture's flexibility to compact patches providing local context while HLI learns long-range cross-region relations from data.Source: §D.4 · p. 15
  • Table 7 reports full utilization (η=1) and perfect balance (CV=0) for Square Partition on every dataset; its p90 aspect ratio is below K-D Tree's on all four.Examples are 13.47 vs. 21.89 on SD and 5.68 vs. 9.56 on GLA; Grid and Quadtree sometimes achieve lower aspect ratios on small datasets at the cost of balance and utilization.Source: §D.4 · pp. 15–16, Table 7 · p. 16

D.5 Case Study (RQ7)

  • Figure 10 illustrates Square Partition's contiguous, balanced, non-overlapping, approximately square patches without padding, in contrast to Grid, Quadtree, and K-D Tree limitations.Source: Figure 10 · p. 16, §D.5 · p. 16
  • Figure 11 shows high inter-patch importance for the 118th patch and stronger correlation between its central 473rd node and downstream nodes than with others.The authors note that the patch corresponds to a major arterial intersection and interpret the pattern as aligning with real-world traffic propagation dynamics.Source: Figure 11 · p. 16, §D.5 · p. 16

D.6 Limitations and Future Work

SqLinear's linear interaction module is optimized for efficiency but may have limited capacity for abrupt, highly nonlinear traffic dynamics. The authors identify hybrid linear–nonlinear architectures as a future direction.

D.6 Limitations and Future Work

  • The linear interaction module is optimized for efficiency, but may have limited capacity for abrupt, highly nonlinear dynamics.Source: §D.6 · p. 16
  • Traffic accidents are given as an example of abrupt, highly nonlinear dynamics that may challenge the module's capacity.Source: §D.6 · p. 16
  • The authors identify hybrid linear–nonlinear architectures that balance efficiency and expressive power as a future research direction for robustness.Source: §D.6 · p. 16

Related papers

Loading 2606.21072v2…