# Spectral Transform Forms Scalable Transformer

arXiv: https://arxiv.org/abs/2111.07602 · HTML: https://mlsanity.com/paper/2111.07602/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 42 of its 67 references that are in the map.
- First posted on arXiv 15 Nov 2021.

## Builds on (most cited first, 30 of 42)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Empirical Evaluation of Gated Recurrent Neural Networks on Sequence Modeling](https://mlsanity.com/paper/1412.3555/) (2014)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [On the Properties of Neural Machine Translation: Encoder-Decoder Approaches](https://mlsanity.com/paper/1409.1259/) (2014)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [Learning to Simulate Complex Physics with Graph Networks](https://mlsanity.com/paper/2002.09405/) (2020)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [Speech Recognition with Deep Recurrent Neural Networks](https://mlsanity.com/paper/1303.5778/) (2013)
- [Temporal Graph Networks for Deep Learning on Dynamic Graphs](https://mlsanity.com/paper/2006.10637/) (2020)
- [Geometric deep learning on graphs and manifolds using mixture model CNNs](https://mlsanity.com/paper/1611.08402/) (2016)
- [Inductive Representation Learning on Temporal Graphs](https://mlsanity.com/paper/2002.07962/) (2020)
- [Predicting Dynamic Embedding Trajectory in Temporal Interaction Networks](https://mlsanity.com/paper/1908.01207/) (2019)
- [EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs](https://mlsanity.com/paper/1902.10191/) (2019)
- [Efficient Attention: Attention with Linear Complexities](https://mlsanity.com/paper/1812.01243/) (2018)
- [FNet: Mixing Tokens with Fourier Transforms](https://mlsanity.com/paper/2105.03824/) (2021)
- [Choose a Transformer: Fourier or Galerkin](https://mlsanity.com/paper/2105.14995/) (2021)
- [Structured Sequence Modeling with Graph Convolutional Recurrent Networks](https://mlsanity.com/paper/1612.07659/) (2016)
- [Stacked Attention Networks for Image Question Answering](https://mlsanity.com/paper/1511.02274/) (2015)
- [Diffusion-Convolutional Neural Networks](https://mlsanity.com/paper/1511.02136/) (2015)
- [Deep Convolutional Networks on Graph-Structured Data](https://mlsanity.com/paper/1506.05163/) (2015)
- [CayleyNets: Graph Convolutional Neural Networks with Complex Rational Spectral Filters](https://mlsanity.com/paper/1705.07664/) (2017)
- [Adaptive Sampling Towards Fast Graph Representation Learning](https://mlsanity.com/paper/1809.05343/) (2018)

## Built on by (most cited first, 4 of 4)

- [Generalized energy and gradient flow via graph framelets](https://mlsanity.com/paper/2210.04124/) (2022)
- [Frameless Graph Knowledge Distillation](https://mlsanity.com/paper/2307.06631/) (2023)
- [Revisiting Generalized p-Laplacian Regularized Framelet GCNs: Convergence, Energy Dynamic and Training with Non-Linear Diffusion](https://mlsanity.com/paper/2305.15639/) (2023)
- [Generalized Laplacian Regularized Framelet Graph Neural Networks](https://mlsanity.com/paper/2210.15092/) (2022)

## Abstract (arXiv)

Many real-world relational systems, such as social networks and biological systems, contain dynamic interactions. When learning dynamic graph representation, it is essential to employ sequential temporal information and geometric structure. Mainstream work achieves topological embedding via message passing networks (e.g., GCN, GAT). The temporal evolution, on the other hand, is conventionally expressed via memory units (e.g., LSTM or GRU) that possess convenient information filtration in a gate mechanism. Though, such a design prevents large-scale input sequence due to the over-complicated encoding. This work learns from the philosophy of self-attention and proposes an efficient spectral-based neural unit that employs informative long-range temporal interaction. The developed spectral window unit (SWINIT) model predicts scalable dynamic graphs with assured efficiency. The architecture is assembled with a few simple effective computational blocks that constitute randomized SVD, MLP, and graph Framelet convolution. The SVD plus MLP module encodes the long-short-term feature evolution of the dynamic graph events. A fast framelet graph transform in the framelet convolution embeds the structural dynamics. Both strategies enhance the model's ability on scalable analysis. In particular, the iterative SVD approximation shrinks the computational complexity of attention to O(Ndlog(d)) for the dynamic graph with N edges and d edge features, and the multiscale transform of framelet convolution allows sufficient scalability in the network training. Our SWINIT achieves state-of-the-art performance on a variety of online continuous-time dynamic graph learning tasks, while compared to baseline methods, the number of its learnable parameters reduces by up to seven times.