Graph-Based Mixers primarily focus on finding efficient surrogates to approximate self-attention. Those include: \((i)\)  sparse attentions that promote predefined sparse patterns; see e.g., sparse transformer [1]}, image transformer [2]}, axial
transformer [3]}, and longformer [4]}; \((ii)\)  low-rank attention that use linear sketching such as linformers [5]}, long-short transformers [6]},
Nyströmformer [7]}; \((iii)\)  kernel methods that approximate attention with ensemble of kernels such as performer [8]}, linear
transformer [9]}, and random feature attention [10]}; and \((iv)\)  clustering-based methods such as reformer [11]}, routing transformer [12]}, and Sinkhorn transformer [13]}. These surrogates however compromise accuracy for efficiencyy.
