A Generalization of ViT/MLP-Mixer to Graphs

Xiaoxin HeBryan HooiThomas LaurentAdam PeroldYann LeCunXavier Bresson

article2023ICML135 citations

Generalizes vision transformer and MLP-Mixer architectures to graph representation learning, offering a linear-complexity model that mitigates over-squashing, models long-range dependencies, and achieves 3-WL expressive power.

Listen

Graph Neural Networks (GNNs) are critical tools for modeling relational data in domains such as drug discovery, chemistry, social networks, and computer vision. However, standard message-passing architectures struggle with two significant issues: poor long-range dependency and over-squashing, where exponentially growing neighborhood information is compressed into fixed-size vectors. While Graph Transformers address these challenges using global attention mechanisms, they introduce quadratic computational complexity relative to the number of nodes, making them inefficient and prohibitively expensive for large graphs.

The article evaluates a new framework that adapts vision-based ViT and MLP-Mixer architectures to graph learning, creating the Graph ViT/MLP-Mixer class of models. The primary objective is to demonstrate that this architecture can capture long-range interactions, achieve high expressive power, and maintain linear computational and memory complexity without relying on costly full-graph attention mechanisms.

To achieve this, the approach partitions graphs into overlapping sub-graph patches using a fast clustering algorithm (METIS expanded by one hop) to preserve critical boundary edges. A local message-passing neural network encodes each patch into a vector representation, and explicit node and patch positional encodings maintain spatial relationships. Alternating token-mixing and channel-mixing layers then combine information across all patches and feature dimensions in linear time. The authors validated the framework across four simulated datasets (evaluating graph isomorphism and over-squashing) and seven real-world benchmarks spanning molecular property prediction, image superpixels, and large peptide structures, comparing performance, runtime, and memory usage against standard message-passing and transformer baselines.

The key findings show that the proposed model delivers state-of-the-art accuracy while dramatically reducing computational overhead. First, on the Long Range Graph Benchmark (Peptides-func and Peptides-struct), the model achieved top scores (0.6970 Average Precision and 0.2449 Mean Absolute Error), significantly outperforming standard message-passing baselines. Second, it demonstrated linear scalability, consuming up to 18 to 20 times less memory and running up to 43 times faster per epoch than leading expressive graph models like SUN on large graphs. Third, the framework effectively mitigated over-squashing on the synthetic TreeNeighbourMatch benchmark, generalizing successfully up to a tree depth of seven where standard models failed at depth four. Finally, the architecture achieved 100% accuracy on simulated isomorphism datasets (CSL, EXP, and SR25), demonstrating empirical expressive power at the level of higher-order Weisfeiler-Leman tests.

These results demonstrate that attention mechanisms are not strictly necessary to capture long-range dependencies in graph learning. Organizations can achieve state-of-the-art predictive accuracy with linear resource scaling, substantially reducing hardware requirements, training times, and operational costs for large-scale graph analytics. Furthermore, the framework acts as a versatile plugin, consistently improving the performance of various underlying message-passing encoders.

Organizations evaluating or deploying graph learning models should consider adopting patch-based mixer architectures as a lightweight, scalable alternative to Graph Transformers for long-range reasoning tasks. To implement the method effectively, practitioners should use overlapping patch extraction rather than disjoint partitioning and leverage on-the-fly partition perturbations during training to regularize the model and prevent overfitting.

Confidence in these findings is strong across the evaluated benchmarks, but practical limitations remain. The number of graph clusters must currently be chosen as a fixed parameter, which can cause the model to process graphs of variable sizes at inconsistent structural resolutions. Additionally, the high expressive power demonstrated in the article remains empirical without formal mathematical guarantees, and large-scale pre-training across wider domain benchmarks has yet to be evaluated.

Element, Inc.Loyola Marymount University Meta National University of Singapore New York University computational efficiency computer vision encoder-decoder Graph ViT Graph Transformers MLP-Mixer

arXiv: 2212.13350 XiaoxinHe/Graph-ViT-MLPMixer

Paper: How Powerful are Graph Neural Networks?, Keyulu Xu et al. (2019). This paper establishes the theoretical Weisfeiler-Lehman expressiveness limits of message-passing GNNs, providing the essential foundation for evaluating the 3-WL expressiveness of Graph ViT/MLP-Mixer.
Paper: Do Transformers Really Perform Badly for Graph Representation?, Chengxuan Ying et al. (2021). This work demonstrates how global Transformer architectures overcome message-passing limits on graphs, motivating the need for more efficient ViT- and MLP-Mixer-based graph models.
Paper: Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks, Christopher Morris et al. (2019). It introduces higher-order Weisfeiler-Leman graph neural networks, which define the expressivity benchmarks surpassed or matched by the source paper.
Paper: Benchmarking Graph Neural Networks, Vijay Prakash Dwivedi et al. (2023). It provides the standardized benchmarking suite and experimental protocols used to evaluate the efficiency and expressiveness of new graph architectures.
Paper: Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View, Deli Chen et al. (2019). This study analyzes the over-smoothing bottleneck inherent to deep message passing, highlighting one of the central problems Graph ViT/MLP-Mixer is designed to solve.
Paper: Semi-Supervised Classification with Graph Convolutional Networks, Thomas N. Kipf et al. (2017). It introduces the standard local message-passing graph convolutional network whose structural bottlenecks motivate alternative global mixer architectures.
Paper: Graph Attention Networks, Petar Veličković et al. (2018). It establishes graph attention mechanisms for neighbor aggregation, which serve as a foundational comparison point for global attention and mixing on graphs.

Paper: Specformer: Spectral Graph Neural Networks Meet Transformers, Deyu Bo et al. (2023). This paper explores an alternative spectral-domain attention mechanism that addresses long-range dependencies and over-smoothing in graphs.

Cover for A Generalization of ViT/MLP-Mixer to Graphs

Abstract

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: https://github.com/XiaoxinHe/Graph-ViT-MLPMixer.

Topics

computational efficiency computer vision encoder-decoder graph neural networks multilayer perceptrons representation learning source codes bipartite graphs directed graphs weighted graph

Keywords

Graph ViT Graph Transformers MLP-Mixer graph-level representation graph coarsening graph partitioning expressive GNN models graph data augmentation molecular graphs

1. Message-Passing GNNs and the Limitations
2. Generalizing ViT/MLP-Mixer to Graphs
3. Generalization Challenges
4. Proposed Architecture
4.1. Overview
4.2. Patch Extraction
4.3. Patch Encoder
4.4. Positional Information
4.5. Mixer Layer
4.6. Data augmentation
5. Experiments
5.1. Comparison with MP-GNNs
5.2. Comparison with SOTAs
5.3. Graph ViT/MLP-Mixer can mitigate over-squashing
5.4. Graph ViT/MLP-Mixer can achieve empirical high expressivity
5.5. Ablation Studies
6. Conclusion
Acknowledgments
References
A. Related Work
B. Datasets Description
C. Experiment Details
D. Studies on Patch Extraction Module
D.1. Effect of Patch Extraction
D.2. Effect of Graph Partition Algorithm
D.3. Effect of Number of Patches
D.4. Effect of Patch Overlapping
D.5. Patch Size and WL Expressivity
E. Studies on Positional Encoding
E.1. Effect of Positional Encoding
E.2. Positional Encoding and Patch Size
F. Study on Different Designs of Graph-Based MHA
G. Effect of Data Augmentation
H. Long Range Graph Benchmark
I. Mitigating Oversquashing in TreeNeighbourMatch
J. Complexity Analysis
K. Limitations

Knowls

Knowl 1 — Graph ViT/MLP-Mixer Architecture Overview
model/method
Graph ViT/MLP-Mixer is a deep learning architecture designed to generalize Vision Transformer (ViT) and MLP-Mixer architectures to graph-structured data. Given an input graph $G = (\mathcal{V}, \mathcal{E})$ with $N = |\mathcal{V}|$ nodes, $E = |\mathcal{E}|$ edges, node feature matrix, and edge feature matrix, the pipeline operates in four main stages:
1. Patch Extraction: Partitions the graph $G$ into a fixed number of $P$ overlapping subgraphs (patches) $\{G_1, \dots, G_P\}$ using the METIS clustering algorithm followed by 1-hop neighborhood expansion.
2. Patch Embedding (Encoder): Encodes each patch $G_p = (\mathcal{V}_p, \mathcal{E}_p)$ into a fixed $d$ -dimensional token vector $x_{G_p} \in \mathbb{R}^d$ using a message-passing graph neural network (MP-GNN) followed by patch-level readout.
3. Mixer / Transformer Layers: Stacks $L_{\text{mix}}$ layers that alternate between mixing token representations across the $P$ patches (via token-mixing MLPs or graph-based multi-head attention) and channel representations within each token (via channel-mixing MLPs).
4. Graph-Level Pooling and Readout: Computes the final graph embedding by masked average pooling over valid non-empty patch tokens: $h_G = \frac{\sum_{p=1}^P m_p \cdot x_{G_p}}{\sum_{p=1}^P m_p} \in \mathbb{R}^d$ where $m_p \in \{0, 1\}$ indicates whether patch $p$ is non-empty, followed by an MLP classifier/regressor head $y_G = \text{MLP}(h_G)$ .
Knowl 2 — Overlapping Graph Patch Extraction via METIS and 1-Hop Expansion
model/method
Graph patch extraction decomposes an irregular input graph $G = (\mathcal{V}, \mathcal{E})$ into $P$ graph tokens $\{G_1, \dots, G_P\}$ . To preserve edge connectivity that would otherwise be discarded across cluster boundaries, extraction proceeds in two steps:
1. METIS Partitioning: The METIS graph clustering algorithm partitions $\mathcal{V}$ into $P$ disjoint subsets $\{\mathcal{V}_1, \dots, \mathcal{V}_P\}$ such that $\mathcal{V} = \bigcup_{p=1}^P \mathcal{V}_p$ and $\mathcal{V}_i \cap \mathcal{V}_j = \emptyset$ for all $i \neq j$ , maximizing within-cluster links and minimizing between-cluster cuts in $O(E)$ runtime.
2. 1-Hop Overlapping Expansion: Each partition $\mathcal{V}_p$ is extended to include the 1-hop neighbors of all its constituent nodes: $\mathcal{V}_p \leftarrow \mathcal{V}_p \cup \left\{ \mathcal{N}_1(j) \mid j \in \mathcal{V}_p \right\}$ where $\mathcal{N}_1(j)$ is the 1-hop neighborhood of node $j$ . The induced subgraph patch $G_p = (\mathcal{V}_p, \mathcal{E}_p)$ contains all nodes in the expanded subset $\mathcal{V}_p$ and all original edges whose endpoints both belong to $\mathcal{V}_p$ .
Knowl 3 — Graph Patch Encoder Module
model/method
The patch encoder transforms each extracted graph patch $G_p = (\mathcal{V}_p, \mathcal{E}_p)$ into a fixed $d$ -dimensional token embedding $x_{G_p} \in \mathbb{R}^d$ through three steps:
1. Linear Feature Projection and Node Positional Encoding: Raw node features $\alpha_i \in \mathbb{R}^{d_n}$ , edge features $\beta_{ij} \in \mathbb{R}^{d_e}$ , and node positional encodings $p_i \in \mathbb{R}^K$ are linearly projected into $d$ -dimensional space: $h_i^0 = T^0 p_i + U^0 \alpha_i + u^0 \in \mathbb{R}^d, \quad e_{ij}^0 = V^0 \beta_{ij} + v^0 \in \mathbb{R}^d$ where $T^0 \in \mathbb{R}^{d \times K}$ , $U^0 \in \mathbb{R}^{d \times d_n}$ , $V^0 \in \mathbb{R}^{d \times d_e}$ are learnable projection matrices, and $u^0, v^0 \in \mathbb{R}^d$ are learnable biases.
2. Local Message Passing with Overlap Averaging: Over $L$ MP-GNN layers, node and edge features are updated within each patch $G_p$ : $h_{i,p}^{\ell+1} = f_{\text{node}}\left(h_{i,p}^\ell, \{h_{j,p}^\ell \mid j \in \mathcal{N}(i) \cap \mathcal{V}_p\}, e_{ij,p}^\ell\right) + g_{\text{patch-node}}(h_p^\ell)$ $e_{ij,p}^{\ell+1} = f_{\text{edge}}\left(h_{i,p}^\ell, h_{j,p}^\ell, e_{ij,p}^\ell\right) + g_{\text{patch-edge}}(e_p^\ell)$ where $h_p^\ell = \frac{1}{|\mathcal{V}_p|} \sum_{i \in \mathcal{V}_p} h_{i,p}^\ell$ , $e_p^\ell = \frac{1}{|\mathcal{E}_p|} \sum_{ij \in \mathcal{E}_p} e_{ij,p}^\ell$ , and $g_{\text{patch-node}}, g_{\text{patch-edge}}$ are MLPs acting on the patch-level means. Node and edge representations shared across overlapping patches are averaged across all patches containing them: $h_{i,p}^{\ell+1} \leftarrow \frac{1}{|\{k \mid i \in \mathcal{V}_k\}|} \sum_{k: i \in \mathcal{V}_k} h_{i,k}^{\ell+1}, \quad e_{ij,p}^{\ell+1} \leftarrow \frac{1}{|\{k \mid ij \in \mathcal{E}_k\}|} \sum_{k: ij \in \mathcal{E}_k} e_{ij,k}^{\ell+1}$
3. Patch Readout: Representations from layer $L$ are mean-pooled across $\mathcal{V}_p$ to obtain $h_p = \frac{1}{|\mathcal{V}_p|} \sum_{i \in \mathcal{V}_p} h_{i,p}^L$ , and passed through an MLP to generate $x_{G_p} = \text{MLP}(h_p) \in \mathbb{R}^d$ .
Knowl 4 — Graph Mixer Layer and Hadamard Graph Multi-Head Attention
model/method
Given patch embedding matrix $X \in \mathbb{R}^{P \times d}$ , inter-token representations are updated using either an MLP-Mixer block or a Graph Vision Transformer (ViT) block:

Graph MLP-Mixer Layer: Alternates token mixing across the $P$ patch tokens and channel mixing across the $d$ feature dimensions: $U = X + \left(W_2 \, \sigma\left(W_1 \, \text{LayerNorm}(X)\right)\right) \in \mathbb{R}^{P \times d}$ $Y = U + \left(W_4 \, \sigma\left(W_3 \, \text{LayerNorm}(U)^T\right)\right)^T \in \mathbb{R}^{P \times d}$ where $\sigma$ is the GELU activation function, $\text{LayerNorm}(\cdot)$ denotes layer normalization, $W_1 \in \mathbb{R}^{d_s \times P}$ , $W_2 \in \mathbb{R}^{P \times d_s}$ , $W_3 \in \mathbb{R}^{d_c \times d}$ , and $W_4 \in \mathbb{R}^{d \times d_c}$ , with $d_s$ and $d_c$ being the hidden dimensions of the token-mixing and channel-mixing MLPs.

Graph ViT Layer (gMHA): Replaces token mixing with a topology-aware graph multi-head self-attention module: $U = X + \text{gMHA}(\text{LayerNorm}(X)) \in \mathbb{R}^{P \times d}$ $Y = U + \text{MLP}(\text{LayerNorm}(U)) \in \mathbb{R}^{P \times d}$ where $\text{gMHA}$ incorporates the coarsened patch adjacency matrix $A^P \in \mathbb{R}^{P \times P}$ via Hadamard product: $\text{gMHA}(X) = \left( A^P \odot \text{softmax}\left(\frac{Q K^T}{\sqrt{d}}\right) \right) V$ where $Q = X W_Q, K = X W_K, V = X W_V$ are linear projections for queries, keys, and values.
Knowl 5 — Two-Level Positional Encodings for Graphs
model/method
To inject geometric and structural ordering into unordered graph patches and nodes, Graph ViT/MLP-Mixer employs a two-level positional encoding (PE) framework:
1. Node Positional Encoding (Node PE): Augments node feature inputs in the patch encoder with absolute positional vectors $p_i \in \mathbb{R}^K$ . Molecular graphs employ Random Walk Structural Encodings (RWSE), while superpixel graphs employ Laplacian Eigenvector Positional Encodings (LapPE) with random sign flips applied during training.
2. Patch Positional Encoding (Patch PE): Computes relative positional encodings between graph patches using a coarsened adjacency matrix $A^P \in \mathbb{R}^{P \times P}$ : $A^P_{ij} = \text{Cut}(\mathcal{V}_i, \mathcal{V}_j) = \sum_{k \in \mathcal{V}_i} \sum_{l \in \mathcal{V}_j} A_{kl}$ where $A \in \mathbb{R}^{N \times N}$ is the original adjacency matrix, and $\text{Cut}(\mathcal{V}_i, \mathcal{V}_j)$ counts connecting edges between clusters $\mathcal{V}_i$ and $\mathcal{V}_j$ . Patch-level positional encodings $\hat{p}_i \in \mathbb{R}^{\hat{K}}$ (e.g., RWSE computed from $A^P$ ) are added to patch embeddings $x_i \in \mathbb{R}^d$ entering the first mixer block: $x_i^0 = \hat{T}^0 \hat{p}_i + \hat{U}^0 x_i + \hat{u}^0 \in \mathbb{R}^d$ where $\hat{T}^0 \in \mathbb{R}^{d \times \hat{K}}, \hat{U}^0 \in \mathbb{R}^{d \times d}$ , and $\hat{u}^0 \in \mathbb{R}^d$ are learnable parameters.
Knowl 6 — Dynamic Patch Perturbation Data Augmentation
model/method
To prevent overfitting in Graph ViT/MLP-Mixer models, dynamic graph patch perturbation is performed at every training epoch:
1. A perturbed graph $G' = (\mathcal{V}, \mathcal{E}')$ is created by randomly dropping a small subset of edges from the original graph $G = (\mathcal{V}, \mathcal{E})$ .
2. The METIS graph partitioning algorithm is executed on the perturbed graph $G'$ to generate stochastic partition clusters $\{\mathcal{V}_1, \dots, \mathcal{V}_P\}$ .
3. The actual patches $\{G_1, \dots, G_P\}$ are extracted as induced subgraphs of the original unperturbed graph $G$ using these partitions (followed by 1-hop expansion).
This produces distinct patch configurations across epochs while retaining all original nodes and edges, acting as effective regularizing data augmentation without altering the underlying graph data.

Knowl 7 — Performance Improvement over Base MP-GNNs on Benchmark Datasets

data/table

Applying Graph MLP-Mixer and Graph ViT architectures over baseline MP-GNN encoders (GCN, GatedGCN, GINE, GraphTrans) consistently improves test performance across diverse benchmark tasks.

Model	ZINC	MNIST	CIFAR10	MolTOX21	MolHIV	Peptide-func	Peptide-struct
	MAE $\downarrow$	Accuracy $\uparrow$	Accuracy $\uparrow$	ROCAUC $\uparrow$	ROCAUC $\uparrow$	AP $\uparrow$	MAE $\downarrow$
GCN	$0.1952 \pm 0.0057$	$0.9269 \pm 0.0023$	$0.5423 \pm 0.0056$	$0.7525 \pm 0.0031$	$0.7813 \pm 0.0081$	$0.6328 \pm 0.0086$	$0.2758 \pm 0.0012$
GCN-MLP-Mixer	$0.1347 \pm 0.0020$	$0.9516 \pm 0.0027$	$0.6111 \pm 0.0017$	$0.7816 \pm 0.0075$	$0.7929 \pm 0.0111$	$0.6832 \pm 0.0061$	$0.2486 \pm 0.0041$
GCN-ViT	$0.1688 \pm 0.0095$	$0.9600 \pm 0.0015$	$0.6367 \pm 0.0027$	$0.7820 \pm 0.0096$	$0.7780 \pm 0.0120$	$0.6855 \pm 0.0049$	$0.2468 \pm 0.0015$
GatedGCN	$0.1577 \pm 0.0046$	$0.9776 \pm 0.0017$	$0.6628 \pm 0.0017$	$0.7641 \pm 0.0057$	$0.7874 \pm 0.0119$	$0.6300 \pm 0.0029$	$0.2778 \pm 0.0017$
GatedGCN-MLP-Mixer	$0.1244 \pm 0.0053$	$0.9832 \pm 0.0004$	$0.7060 \pm 0.0022$	$0.7910 \pm 0.0040$	$0.7976 \pm 0.0136$	$0.6932 \pm 0.0017$	$0.2508 \pm 0.0007$
GatedGCN-ViT	$0.1421 \pm 0.0031$	$0.9846 \pm 0.0009$	$0.7158 \pm 0.0009$	$0.7857 \pm 0.0028$	$0.7734 \pm 0.0114$	$0.6942 \pm 0.0075$	$0.2465 \pm 0.0015$
GINE	$0.1072 \pm 0.0037$	$0.9705 \pm 0.0023$	$0.6131 \pm 0.0035$	$0.7730 \pm 0.0064$	$0.7885 \pm 0.0034$	$0.6405 \pm 0.0077$	$0.2780 \pm 0.0021$
GINE-MLP-Mixer	$0.0733 \pm 0.0014$	$0.9809 \pm 0.0004$	$0.6833 \pm 0.0022$	$0.7868 \pm 0.0043$	$0.7997 \pm 0.0102$	$0.6970 \pm 0.0080$	$0.2494 \pm 0.0007$
GINE-ViT	$0.0849 \pm 0.0047$	$0.9820 \pm 0.0005$	$0.6967 \pm 0.0040$	$0.7851 \pm 0.0077$	$0.7792 \pm 0.0149$	$0.6919 \pm 0.0085$	$0.2449 \pm 0.0016$
GraphTrans	$0.1230 \pm 0.0018$	$0.9782 \pm 0.0012$	$0.6809 \pm 0.0020$	$0.7646 \pm 0.0055$	$0.7884 \pm 0.0104$	$0.6313 \pm 0.0039$	$0.2777 \pm 0.0025$
GraphTrans-MLP-Mixer	$0.0773 \pm 0.0030$	$0.9742 \pm 0.0011$	$0.7396 \pm 0.0033$	$0.7817 \pm 0.0040$	$0.7969 \pm 0.0061$	$0.6858 \pm 0.0062$	$0.2480 \pm 0.0013$
GraphTrans-ViT	$0.0960 \pm 0.0073$	$0.9725 \pm 0.0023$	$0.7211 \pm 0.0055$	$0.7835 \pm 0.0032$	$0.7755 \pm 0.0208$	$0.6876 \pm 0.0059$	$0.2455 \pm 0.0027$

All baseline architectures were augmented with the same positional encodings for fair comparison. The results demonstrate large improvements on the Long Range Graph Benchmark (LRGB), showing an average gain of $0.056$ Average Precision on Peptides-func and an average reduction of $0.028$ MAE on Peptides-struct.

Knowl 8 — Empirical Isomorphism Expressivity on 1-WL, 2-WL, and 3-WL Benchmarks

data/table

Standard MP-GNNs are theoretically bounded by the 1-Weisfeiler-Leman (1-WL) isomorphism test and fail to distinguish non-isomorphic regular graphs. Graph MLP-Mixer was evaluated on three synthetic benchmark datasets: CSL (150 4-regular graphs, 1-WL failure), EXP (600 graph pairs, 1-WL and 2-WL failure), and SR25 (15 strongly regular graphs with 25 nodes, 3-WL failure).

Model	CSL (ACC $\uparrow$ )	EXP (ACC $\uparrow$ )	SR25 (ACC $\uparrow$ )
GCN	$10.00 \pm 0.00$	$51.90 \pm 1.96$	$6.67 \pm 0.00$
GatedGCN	$10.00 \pm 0.00$	$51.73 \pm 1.65$	$6.67 \pm 0.00$
GINE	$10.00 \pm 0.00$	$50.69 \pm 1.39$	$6.67 \pm 0.00$
GraphTrans	$10.00 \pm 0.00$	$52.35 \pm 2.32$	$6.67 \pm 0.00$
GCN-MLP-Mixer	$100.00 \pm 0.00$	$100.00 \pm 0.00$	$100.00 \pm 0.00$
GatedGCN-MLP-Mixer	$100.00 \pm 0.00$	$100.00 \pm 0.00$	$100.00 \pm 0.00$
GINE-MLP-Mixer	$100.00 \pm 0.00$	$100.00 \pm 0.00$	$100.00 \pm 0.00$
GraphTrans-MLP-Mixer	$100.00 \pm 0.00$	$100.00 \pm 0.00$	$100.00 \pm 0.00$

While all baseline MP-GNN models perform at chance level ( $10.00\%$ on CSL, $\approx 51\%$ on EXP, and $6.67\%$ on SR25), all Graph MLP-Mixer variants achieve $100.00\%$ test accuracy, empirically demonstrating expressivity capable of distinguishing at least 3-WL non-isomorphic graphs.

Knowl 9 — Over-Squashing Mitigation on TreeNeighbourMatch
empirical result
The TreeNeighbourMatch benchmark tests an architecture's susceptibility to over-squashing as the tree depth (problem radius $r$ ) increases. Each instance is a binary tree of depth $r$ where a target node must be assigned an alphabetical label identical to the leaf node having the same degree as the target node.

Standard MP-GNNs (GCN, GatedGCN, GAT, GIN) fail completely to generalize for $r \ge 4$ because they are forced to compress exponentially growing leaf information ( $O(2^r)$ ) into a fixed-length target node embedding. In contrast, Graph MLP-Mixer and Graph ViT maintain near $100\%$ classification accuracy from $r = 2$ up to $r = 6$ , and achieve robust generalization at $r = 7$ , before dropping at $r = 8$ . This demonstrates that passing patch-level tokens directly through mixer and attention layers bypasses the localized information bottleneck of message-passing.

Knowl 10 — Comparison of Attention Formulations in Graph ViT

data/table

Five different graph-based multi-head attention (gMHA) formulations were evaluated within the Graph ViT transformer layer on the ZINC (molecular regression) and Peptides-func (long-range functional classification) datasets.

gMHA Formulation	Attention Equation	ZINC (MAE $\downarrow$ )	Peptides-func (AP $\uparrow$ )
Standard / Full Attention	$\text{softmax}\left(\frac{Q K^T}{\sqrt{d}}\right) V$	$0.1784 \pm 0.0238$	$0.6778 \pm 0.0039$
Graph Attention	$\text{softmax}\left(A^P \odot \frac{Q K^T}{\sqrt{d}}\right) V$	$0.1527 \pm 0.0067$	$0.6795 \pm 0.0070$
Kernel Attention	$\text{softmax}\left(\text{RW}(A^P) \odot \frac{Q K^T}{\sqrt{d}}\right) V$	$0.1010 \pm 0.0031$	$0.6844 \pm 0.0102$
Additive Attention	$\left(\text{softmax}\left(\frac{Q K^T}{\sqrt{d}}\right) + \text{LL}(A^P)\right) V$	$0.1632 \pm 0.0063$	$0.6842 \pm 0.0057$
Hadamard Attention	$\left(A^P \odot \text{softmax}\left(\frac{Q K^T}{\sqrt{d}}\right)\right) V$	$0.0849 \pm 0.0047$	$0.6919 \pm 0.0085$

Hadamard Attention—where the full attention distribution is weighted via an elementwise Hadamard product with the coarsened patch adjacency matrix $A^P$ —achieved the best performance on both datasets ( $0.0849$ MAE on ZINC and $0.6919$ AP on Peptides-func).

Knowl 11 — Computational Time and Memory Complexity
theoretical result
For a graph $G = (\mathcal{V}, \mathcal{E})$ with $N = |\mathcal{V}|$ nodes and $E = |\mathcal{E}|$ edges partitioned into $P$ overlapping patches $\{G_1, \dots, G_P\}$ :
1. Patch Extraction: METIS partitioning executes in $O(E)$ time.
2. Patch Embedding Module: With total patch nodes $N' = \sum_{p=1}^P |\mathcal{V}_p| \le P N$ and total patch edges $E' = \sum_{p=1}^P |\mathcal{E}_p| \le P E$ , the MP-GNN patch encoder operates in $O(N' + E')$ runtime and memory, preserving linear $O(N + E)$ complexity with a constant overhead proportional to neighborhood overlap.
3. Mixer Layers: Operating on $P$ tokens per graph requires $O(P)$ memory and computation per layer for Graph MLP-Mixer, avoiding the quadratic $O(N^2)$ scaling of dense Graph Transformers.
On the Peptides-func dataset, Graph MLP-Mixer achieves competitive or superior accuracy while requiring $43.8\times$ less training time and $18.8\times$ less GPU memory than expressive subgraph networks (SUN), and $9.4\times$ less training time and $12.4\times$ less memory than spectral Graph Transformers (SAN+LapPE).

Knowl 12 — Ablation of Patch Extraction and Overlapping Hop Radius

data/table

Ablation experiments evaluate the impact of using graph patch extraction versus treating each individual node as a patch, and the effect of varying the neighborhood expansion hop radius $k$ .

Model	Patch Extraction	ZINC (MAE $\downarrow$ )	Peptides-func (AP $\uparrow$ )
GCN-MLP-Mixer	No	$0.2495 \pm 0.0040$	$0.6341 \pm 0.0139$
	Yes	$0.1347 \pm 0.0020$	$0.6832 \pm 0.0061$
GatedGCN-MLP-Mixer	No	$0.2521 \pm 0.0084$	$0.6230 \pm 0.0110$
	Yes	$0.1244 \pm 0.0053$	$0.6932 \pm 0.0017$
GINE-MLP-Mixer	No	$0.2558 \pm 0.0059$	$0.6350 \pm 0.0038$
	Yes	$0.0733 \pm 0.0014$	$0.6970 \pm 0.0080$
GraphTrans-MLP-Mixer	No	$0.2538 \pm 0.0067$	$0.6224 \pm 0.0112$
	Yes	$0.0773 \pm 0.0030$	$0.6858 \pm 0.0062$

Extracting patches using METIS with 1-hop overlap ( $k=1$ ) significantly outperforms the unpartitioned baseline across all base models. Extending patch overlap from 0-hop (non-overlapping) to 1-hop produces a large performance gain by restoring cut edge connectivity, with performance plateauing or decreasing for $k \ge 2$ .

Knowl 13 — Limitations of Graph ViT/MLP-Mixer
limitation
The Graph ViT/MLP-Mixer framework has three identified limitations:
1. Pre-defined Static Patch Count: The number of clusters $P$ in METIS is chosen as a fixed hyperparameter ( $P=32$ by default). Applying a constant $P$ to graphs of widely varying sizes forces the model to process subgraphs at differing spatial resolutions.
2. Empirical Nature of Expressivity Bounds: High isomorphism expressivity (surpassing 3-WL) is demonstrated through empirical experiments on synthetic datasets (CSL, EXP, SR25), but lacks a formal mathematical proof due to non-local inter-layer feature mixing.
3. Absence of Large-Scale Pre-training: The architecture was not evaluated on large-scale self-supervised graph pre-training or on very large datasets such as PCQM4Mv2 and MalNet.

Coverage note — None omitted; all core architectural components, empirical comparisons on benchmarks, expressivity analyses, synthetic tests, ablations, complexity bounds, and limitations are fully represented.

References

1.Abboud, R., Ceylan, I. I., Grohe, M., and Lukasiewicz, T. The surprising power of graph neural networks with random node initialization. arXiv preprint arXiv:2010.01179, 2020.
2.Alon, U. and Yahav, E. On the bottleneck of graph neural networks and its practical implications. arXiv preprint arXiv:2006.05205, 2020.
3.Alsentzer, E., Finlayson, S., Li, M., and Zitnik, M. Subgraph neural networks. Advances in Neural Information Processing Systems, 33:8017–8029, 2020.
4.Arnaiz-Rodr'ıguez, A., Begga, A., Escolano, F., and Oliver, N. M. Diffwire: Inductive graph rewiring via the lovasz bound. In The First Learning on Graphs Conference, 2022.
5.Azizian, W. and Lelarge, M. Expressive power of invariant and equivariant graph neural networks. arXiv preprint arXiv:2006.15646, 2020.
6.Ba, J. L., Kiros, J. R., and Hinton, G. E. Layer normalization. arXiv preprint arXiv:1607.06450, 2016.
7.Bahdanau, D., Cho, K., and Bengio, Y. Neural machine translation by jointly learning to align and translate. arXiv preprint arXiv:1409.0473, 2014.
8.Balcilar, M., Heroux, P., Gauzere, B., Vasseur, P., Adam, S., and Honeine, P. Breaking the limits of message passing graph neural networks. In International Conference on Machine Learning, pp. 599–608. PMLR, 2021.
9.Bapst, V., Keck, T., Grabska-Barwinska, A., Donner, C., Cubuk, E. D., Schoenholz, S. S., Obika, A., Nelson, A. W., Back, T., Hassabis, D., et al. Unveiling the predictive power of static structure in glassy systems. Nature Physics, 16(4):448–454, 2020.
10.Belkin, M. and Niyogi, P. Laplacian eigenmaps for dimensionality reduction and data representation. Neural computation, 15(6):1373–1396, 2003.
11.Berg, R. v. d., Kipf, T. N., and Welling, M. Graph convolutional matrix completion. arXiv preprint arXiv:1706.02263, 2017.
12.Bodnar, C., Frasca, F., Otter, N., Wang, Y., Lio, P., Montufar, G. F., and Bronstein, M. Weisfeiler and lehman go cellular: Cw networks. Advances in Neural Information Processing Systems, 34:2625–2640, 2021.
13.Bouritsas, G., Frasca, F., Zafeiriou, S. P., and Bronstein, M. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
14.Bresson, X. and Laurent, T. Residual gated graph convnets. arXiv preprint arXiv:1711.07553, 2017.
15.Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. Language models are few-shot learners. Advances in neural information processing systems, 33: 1877–1901, 2020.
16.Bulu¸, A., Meyerhenke, H., Safro, I., Sanders, P., and Schulz, C. Recent advances in graph partitioning. Algorithm engineering, pp. 117–158, 2016.
17.Chen, D., O’Bray, L., and Borgwardt, K. Structure-aware transformer for graph representation learning. In International Conference on Machine Learning, pp. 3469–3489. PMLR, 2022a.
18.Chen, J., Gao, K., Li, G., and He, K. Nagphormer: Neighborhood aggregation graph transformer for node classification in large graphs. arXiv preprint arXiv:2206.04910, 2022b.
19.Chen, Z., Chen, L., Villar, S., and Bruna, J. On the equivalence between graph isomorphism testing and function approximation with gnns. Advances in neural information processing systems, 2019.
20.Chen, Z., Chen, L., Villar, S., and Bruna, J. Can graph neural networks count substructures? Advances in neural information processing systems, 33:10383–10395, 2020.
21.Chung, F. R. Spectral graph theory, volume 92. American Mathematical Soc., 1997.
22.Cranmer, M. D., Xu, R., Battaglia, P., and Ho, S. Learning symbolic physics with graph networks. arXiv preprint arXiv:1909.05862, 2019.
23.Cubuk, E. D., Zoph, B., Shlens, J., and Le, Q. V. Randaugment: Practical automated data augmentation with a reduced search space. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition workshops, pp. 702–703, 2020.
24.Deac, A., Lackenby, M., and Velickovič, P. Expander graph propagation. In The First Learning on Graphs Conference, 2022.
25.Defferrard, M., Bresson, X., and Vandergheynst, P. Convolutional neural networks on graphs with fast localized spectral filtering. In NIPS, 2016.
26.Derrow-Pinion, A., She, J., Wong, D., Lange, O., Hester, T., Perez, L., Nunkesser, M., Lee, S., Guo, X., Wiltshire, B., et al. Eta prediction with graph neural networks in google maps. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pp. 3767–3776, 2021.
27.Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805, 2018.
28.Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., et al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010.11929, 2020.
29.Duvenaud, D. K., Maclaurin, D., Iparraguirre, J., Bombarell, R., Hirzel, T., Aspuru-Guzik, A., and Adams, R. P. Convolutional networks on graphs for learning molecular fingerprints. Advances in neural information processing systems, 28, 2015.
30.Dwivedi, V. P. and Bresson, X. A generalization of transformer networks to graphs. In AAAI Workshop on Deep Learning on Graphs: Methods and Applications, 2021.
31.Dwivedi, V. P., Joshi, C. K., Laurent, T., Bengio, Y., and Bresson, X. Benchmarking graph neural networks. arXiv preprint arXiv:2003.00982, 2020.
32.Dwivedi, V. P., Luu, A. T., Laurent, T., Bengio, Y., and Bresson, X. Graph neural networks with learnable structural and positional representations. In International Conference on Learning Representations, 2021.
33.Dwivedi, V. P., Rampa'sek, L., Galkin, M., Parviz, A., Wolf, G., Luu, A. T., and Beaini, D. Long range graph benchmark. arXiv preprint arXiv:2206.08164, 2022.
34.Feng, J., Chen, Y., Li, F., Sarkar, A., and Zhang, M. How powerful are k-hop message passing graph neural networks. arXiv preprint arXiv:2205.13328, 2022.
35.Fey, M. and Lenssen, J. E. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv:1903.02428, 2019.
36.Frasca, F., Bevilacqua, B., Bronstein, M. M., and Maron, H. Understanding and extending subgraph gnns by rethinking their symmetries. arXiv preprint arXiv:2206.11140, 2022.
37.Freitas, S., Dong, Y., Neil, J., and Chau, D. H. A large-scale database for graph representation learning. arXiv preprint arXiv:2011.07682, 2020.
38.Gaudelet, T., Day, B., Jamasb, A. R., Soman, J., Regep, C., Liu, G., Hayter, J. B., Vickers, R., Roberts, C., Tang, J., et al. Utilising graph machine learning within drug discovery and development. arXiv preprint arXiv:2012.05716, 2020.
39.Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E. Neural message passing for quantum chemistry. In International Conference on Machine Learning, pp. 1263–1272. PMLR, 2017.
40.Hamilton, W. L., Ying, R., and Leskovec, J. Inductive representation learning on large graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 1025–1035, 2017.
41.Han, K., Wang, Y., Guo, J., Tang, Y., and Wu, E. Vision gnn: An image is worth graph of nodes. arXiv preprint arXiv:2206.00272, 2022a.
42.Han, X., Jiang, Z., Liu, N., and Hu, X. G-mixup: Graph data augmentation for graph classification. arXiv preprint arXiv:2202.07179, 2022b.
43.Hendrycks, D. and Gimpel, K. Gaussian error linear units (gelus). arXiv preprint arXiv:1606.08415, 2016.
44.Hochreiter, S. and Schmidhuber, J. Long short-term memory. Neural computation, 9(8):1735–1780, 1997.
45.Hu, W., Liu, B., Gomes, J., Zitnik, M., Liang, P., Pande, V., and Leskovec, J. Strategies for pre-training graph neural networks. arXiv preprint arXiv:1905.12265, 2019.
46.Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., and Leskovec, J. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:22118–22133, 2020.
47.Irwin, J. J., Sterling, T., Mysinger, M. M., Bolstad, E. S., and Coleman, R. G. Zinc: a free tool to discover chemistry for biology. Journal of chemical information and modeling, 52(7):1757–1768, 2012.
48.Karypis, G. and Kumar, V. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on scientific Computing, 20(1):359–392, 1998.
49.Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
50.Kipf, T. N. and Welling, M. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.
51.Kreuzer, D., Beaini, D., Hamilton, W., L'etourneau, V., and Tossou, P. Rethinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 34:21618–21629, 2021.
52.Kuang, W., WANG, Z., Li, Y., Wei, Z., and Ding, B. Coarformer: Transformer for large graph via graph coarsening, 2022. URL https://openreview.net/forum?id=fkjO_FKVzw.
53.Kwon, J., Kim, J., Park, H., and Choi, I. K. Asam: Adaptive sharpness-aware minimization for scale-invariant learning of deep neural networks. arXiv preprint arXiv:2102.11600, 2021.
54.Landrum, G. et al. Rdkit: Open-source cheminformatics. 2006, 2006.
55.Li, P., Wang, Y., Wang, H., and Leskovec, J. Distance encoding: Design provably more powerful neural networks for graph representation learning. Advances in Neural Information Processing Systems, 33, 2020a.
56.Li, X., Zhou, Y., Dvornek, N., Zhang, M., Gao, S., Zhuang, J., Scheinost, D., Staib, L. H., Ventola, P., and Duncan, J. S. Braingnn: Interpretable brain graph neural network for fmri analysis. Medical Image Analysis, 74:102233, 2021.
57.Li, Y., Qian, B., Zhang, X., and Liu, H. Graph neural network-based diagnosis prediction. Big Data, 8(5):379–390, 2020b.
58.Lim, D., Robinson, J., Zhao, L., Smidt, T., Sra, S., Maron, H., and Jegelka, S. Sign and basis invariant networks for spectral graph representation learning. arXiv preprint arXiv:2202.13013, 2022.
59.Liu, H., Dai, Z., So, D., and Le, Q. V. Pay attention to mlps. Advances in Neural Information Processing Systems, 34: 9204–9215, 2021.
60.Loukas, A. What graph neural networks cannot learn: depth vs width. In International Conference on Learning Representations, 2020.
61.Maron, H., Ben-Hamu, H., Shamir, N., and Lipman, Y. Invariant and equivariant graph networks. arXiv preprint arXiv:1812.09902, 2018.
62.Maron, H., Ben-Hamu, H., Serviansky, H., and Lipman, Y. Provably powerful graph networks. arXiv preprint arXiv:1905.11136, 2019.
63.Mialon, G., Chen, D., Selosse, M., and Mairal, J. Graphit: Encoding graph structure in transformers. arXiv preprint arXiv:2106.05667, 2021.
64.Min, E., Chen, R., Bian, Y., Xu, T., Zhao, K., Huang, W., Zhao, P., Huang, J., Ananiadou, S., and Rong, Y. Transformer for graphs: An overview from architecture perspective. arXiv preprint arXiv:2202.08455, 2022.
65.Monti, F., Bronstein, M., and Bresson, X. Geometric matrix completion with recurrent multi-graph neural networks. Advances in neural information processing systems, 30, 2017.
66.Morris, C., Ritzert, M., Fey, M., Hamilton, W. L., Lenssen, J. E., Rattan, G., and Grohe, M. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4602–4609, 2019.
67.Murphy, R., Srinivasan, B., Rao, V., and Ribeiro, B. Relational pooling for graph representations. In International Conference on Machine Learning, pp. 4663–4673. PMLR, 2019.
68.Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
69.Rampa'sek, L., Galkin, M., Dwivedi, V. P., Luu, A. T., Wolf, G., and Beaini, D. Recipe for a general, powerful, scalable graph transformer. arXiv preprint arXiv:2205.12454, 2022.
70.Rong, Y., Huang, W., Xu, T., and Huang, J. Dropedge: Towards deep graph convolutional networks on node classification. arXiv preprint arXiv:1907.10903, 2019.
71.Schlichtkrull, M., Kipf, T. N., Bloem, P., Berg, R. v. d., Titov, I., and Welling, M. Modeling relational data with graph convolutional networks. In European semantic web conference, pp. 593–607. Springer, 2018.
72.Shirzad, H., Velingker, A., Venkatachalam, B., Sutherland, D. J., and Sinop, A. K. Exphormer: Sparse transformers for graphs. arXiv preprint arXiv:2303.06147, 2023.
73.Singh, S., Chaudhary, K., Dhanda, S. K., Bhalla, S., Usmani, S. S., Gautam, A., Tuknait, A., Agrawal, P., Mathur, D., and Raghava, G. P. Satpdb: a database of structurally annotated therapeutic peptides. Nucleic acids research, 44(D1):D1119–D1126, 2016.
74.Stokes, J. M., Yang, K., Swanson, K., Jin, W., Cubillos-Ruiz, A., Donghia, N. M., MacNair, C. R., French, S., Carfrae, L. A., Bloom-Ackermann, Z., et al. A deep learning approach to antibiotic discovery. Cell, 180(4): 688–702, 2020.
75.Szklarczyk, D., Gable, A. L., Lyon, D., Junge, A., Wyder, S., Huerta-Cepas, J., Simonovic, M., Doncheva, N. T., Morris, J. H., Bork, P., et al. String v11: protein–protein association networks with increased coverage, supporting functional discovery in genome-wide experimental datasets. Nucleic acids research, 47(D1):D607–D613, 2019.
76.Tolstikhin, I. O., Houlsby, N., Kolesnikov, A., Beyer, L., Zhai, X., Unterthiner, T., Yung, J., Steiner, A., Keysers, D., Uszkoreit, J., et al. Mlp-mixer: An all-mlp architecture for vision. Advances in Neural Information Processing Systems, 34:24261–24272, 2021.
77.Topping, J., Di Giovanni, F., Chamberlain, B. P., Dong, X., and Bronstein, M. M. Understanding over-squashing and bottlenecks on graphs via curvature. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022, 2022.
78.Touvron, H., Bojanowski, P., Caron, M., Cord, M., El-Nouby, A., Grave, E., Izacard, G., Joulin, A., Synnaeve, G., Verbeek, J., et al. Resmlp: Feedforward networks for image classification with data-efficient training. arXiv preprint arXiv:2105.03404, 2021.
79.Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, Ł., and Polosukhin, I. Attention is all you need. Advances in neural information processing systems, 30, 2017.
80.Velickovič, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., and Bengio, Y. Graph attention networks. In International Conference on Learning Representations, 2018.
81.Wang, Z., Jiang, W., Zhu, Y. M., Yuan, L., Song, Y., and Liu, W. Dynamixer: a vision mlp architecture with dynamic mixing. In International Conference on Machine Learning, pp. 22691–22701. PMLR, 2022.
82.Weisfeiler, B. and Leman, A. The reduction of a graph to canonical form and the algebra which appears therein. NTI Series, 2(9):12–16, 1968.
83.Wu, L., Chen, Y., Shen, K., Guo, X., Gao, H., Li, S., Pei, J., and Long, B. Graph neural networks for natural language processing: A survey. arXiv preprint arXiv:2106.06090, 2021a.
84.Wu, Z., Jain, P., Wright, M., Mirhoseini, A., Gonzalez, J. E., and Stoica, I. Representing long-range context for graph neural networks with global attention. Advances in Neural Information Processing Systems, 34:13266–13279, 2021b.
85.Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
86.Ying, C., Cai, T., Luo, S., Zheng, S., Ke, G., He, D., Shen, Y., and Liu, T.-Y. Do transformers really perform badly for graph representation? Advances in Neural Information Processing Systems, 34:28877–28888, 2021.
87.Yu, W., Luo, M., Zhou, P., Si, C., Zhou, Y., Wang, X., Feng, J., and Yan, S. Metaformer is actually what you need for vision. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 10819–10829, 2022.
88.Zhang, H., Cisse, M., Dauphin, Y. N., and Lopez-Paz, D. mixup: Beyond empirical risk minimization. arXiv preprint arXiv:1710.09412, 2017.
89.Zhang, M. and Li, P. Nested graph neural networks. Advances in Neural Information Processing Systems, 34: 15734–15747, 2021.
90.Zhang, Z., Liu, Q., Hu, Q., and Lee, C.-K. Hierarchical graph transformer with adaptive node sampling. arXiv preprint arXiv:2210.03930, 2022.
91.Zhao, L., Jin, W., Akoglu, L., and Shah, N. From stars to subgraphs: Uplifting any gnn with local structure awareness. In International Conference on Learning Representations, 2021.
92.Zhao, T., Liu, Y., Neves, L., Woodford, O. J., Jiang, M., and Shah, N. Data augmentation for graph neural networks. CoRR, abs/2006.06830, 2020.
93.Zheng, D., Song, X., Ma, C., Tan, Z., Ye, Z., Dong, J., Xiong, H., Zhang, Z., and Karypis, G. Dgl-ke: Training knowledge graph embeddings at scale. In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 739–748, 2020.
94.Zopf, M. 1-wl expressiveness is (almost) all you need. arXiv preprint arXiv:2202.10156, 2022.

Citation

MLA

He, X., et al. “A Generalization of ViT/MLP-Mixer to Graphs”. International Conference on Machine Learning, vol. 202, 2023, pp. 12724–45, https://proceedings.mlr.press/v202/he23a.html.

APA

He, X., Hooi, B., Laurent, T., Perold, A., Lecun, Y., & Bresson, X. (2023). A Generalization of ViT/MLP-Mixer to Graphs. International Conference on Machine Learning, 202, 12724–12745. https://proceedings.mlr.press/v202/he23a.html

Chicago

He, X., B. Hooi, T. Laurent, A. Perold, Y. Lecun, and X. Bresson. 2023. “A Generalization of ViT/MLP-Mixer to Graphs”. International Conference on Machine Learning 202: 12724–45. https://proceedings.mlr.press/v202/he23a.html.

Harvard

He, X. et al. (2023) “A Generalization of ViT/MLP-Mixer to Graphs”, International Conference on Machine Learning. PMLR, pp. 12724–12745. Available at: https://proceedings.mlr.press/v202/he23a.html.

Vancouver

1. He X, Hooi B, Laurent T, Perold A, Lecun Y, Bresson X (2023) A Generalization of ViT/MLP-Mixer to Graphs. In: International Conference on Machine Learning. PMLR, pp 12724–12745

BibTeX

@InProceedings{pmlr-v202-he23a,
  title = 	 {A Generalization of {V}i{T}/{MLP}-Mixer to Graphs},
  author =       {He, Xiaoxin and Hooi, Bryan and Laurent, Thomas and Perold, Adam and Lecun, Yann and Bresson, Xavier},
  booktitle = 	 {Proceedings of the 40th International Conference on Machine Learning},
  pages = 	 {12724--12745},
  year = 	 {2023},
  editor = 	 {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan},
  volume = 	 {202},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {23--29 Jul},
  publisher =    {PMLR},
  pdf = 	 {https://proceedings.mlr.press/v202/he23a/he23a.pdf},
  url = 	 {https://proceedings.mlr.press/v202/he23a.html},
  abstract = 	 {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: https://github.com/XiaoxinHe/Graph-ViT-MLPMixer.}
}

Metadata:DOI registry

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

A Generalization of ViT/MLP-Mixer to Graphs

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Graph ViT/MLP-Mixer Architecture Overview

Knowl 2 — Overlapping Graph Patch Extraction via METIS and 1-Hop Expansion

Knowl 3 — Graph Patch Encoder Module

Knowl 4 — Graph Mixer Layer and Hadamard Graph Multi-Head Attention

Knowl 5 — Two-Level Positional Encodings for Graphs

Knowl 6 — Dynamic Patch Perturbation Data Augmentation

Knowl 7 — Performance Improvement over Base MP-GNNs on Benchmark Datasets

Knowl 8 — Empirical Isomorphism Expressivity on 1-WL, 2-WL, and 3-WL Benchmarks

Knowl 9 — Over-Squashing Mitigation on TreeNeighbourMatch

Knowl 10 — Comparison of Attention Formulations in Graph ViT

Knowl 11 — Computational Time and Memory Complexity

Knowl 12 — Ablation of Patch Extraction and Overlapping Hop Radius

Knowl 13 — Limitations of Graph ViT/MLP-Mixer

References

Citation

BibTeX

Source Code

Access the Paper