  Graph neural networks have achieved remarkable success in learning graph
representations, especially graph Transformer, which has recently shown
superior performance on various graph mining tasks. However, graph Transformer
generally treats nodes as tokens, which results in quadratic complexity
regarding the number of nodes during self-attention computation. The graph MLP
Mixer addresses this challenge by using the efficient MLP Mixer technique from
computer vision. However, the time-consuming process of extracting graph tokens
limits its performance. In this paper, we present a novel architecture named
ChebMixer, a newly graph MLP Mixer that uses fast Chebyshev polynomials-based
spectral filtering to extract a sequence of tokens. Firstly, we produce
multiscale representations of graph nodes via fast Chebyshev polynomial-based
spectral filtering. Next, we consider each node's multiscale representations as
a sequence of tokens and refine the node representation with an effective MLP
Mixer. Finally, we aggregate the multiscale representations of nodes through
Chebyshev interpolation. Owing to the powerful representation capabilities and
fast computational properties of MLP Mixer, we can quickly extract more
informative node representations to improve the performance of downstream
tasks. The experimental results prove our significant improvements in a variety
of scenarios ranging from graph node classification to medical image
segmentation.
