  Graph Neural Networks (GNNs) have shown great potential in the field of graph
representation learning. Standard GNNs define a local message-passing mechanism
which propagates information over the whole graph domain by stacking multiple
layers. This paradigm suffers from two major limitations, over-squashing and
poor long-range dependencies, that can be solved using global attention but
significantly increases the computational cost to quadratic complexity. In this
work, we propose an alternative approach to overcome these structural
limitations by leveraging the ViT/MLP-Mixer architectures introduced in
computer vision. We introduce a new class of GNNs, called Graph ViT/MLP-Mixer,
that holds three key properties. First, they capture long-range dependency and
mitigate the issue of over-squashing as demonstrated on Long Range Graph
Benchmark and TreeNeighbourMatch datasets. Second, they offer better speed and
memory efficiency with a complexity linear to the number of nodes and edges,
surpassing the related Graph Transformer and expressive GNN models. Third, they
show high expressivity in terms of graph isomorphism as they can distinguish at
least 3-WL non-isomorphic graphs. We test our architecture on 4 simulated
datasets and 7 real-world benchmarks, and show highly competitive results on
all of them. The source code is available for reproducibility at:
\url{https://github.com/XiaoxinHe/Graph-ViT-MLPMixer}.
