Graph MLP-Mixer
Authors: Xiaoxin He
Bryan Hooi
Thomas Laurent
Adam Perold
Yann LeCun
Xavier Bresson
Venue: Submitted to ICLR 2023 (2023)

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 consider an alternative approach to overcome these structural limitations while keeping a low complexity cost. Motivated by the recent MLP-Mixer architecture introduced in computer vision, we propose to generalize this network to graphs. This GNN model, namely Graph MLP-Mixer, can make long-range connections without over-squashing or high complexity due to the mixer layer applied to the graph patches extracted from the original graph. As a result, this architecture exhibits promising results when comparing standard GNNs vs. Graph MLP-Mixers on benchmark graph datasets.

Under review as a conference paper at ICLR 2023
GRAPH MLP-MIXER
Anonymous authors Paper under double-blind review
ABSTRACT
Graph Neural Networks (GNNs) have shown great potential in the field of graph representation learning. Standard GNNs define a local message-passing mecha- nism which propagates information over the whole graph domain by stacking mul- tiple layers. This paradigm suffers from two major limitations, over-squashing and poor long-range dependencies, that can be solved using global attention but sig- nificantly increases the computational cost to quadratic complexity. In this work, we consider an alternative approach to overcome these structural limitations while keeping low complexity cost. Motivated by the recent MLP-Mixer architecture introduced in computer vision, we propose to generalize this network to graphs. This GNN model, namely Graph MLP-Mixee without over-squashing or high complexity due to the mixer layer applicd to the graph patches extracted from the original graph. As result, this architecture hibits promising results when comparing standard GNNs vs. Graph MI.P-Mixers on benchmark graph datasets.
make long-range connections
BACKGROUND AND MOTIVATION
In this section, we review the main classes of GNNs with their advantages and their limitations. Then, we introduce the ViT/ML--Mxeer architectures from computer vision which have motivated us to design a new graph network architecture.
PlessagePasssing GNNs (MP-GNNs). GNNs have become the standard learning architectures for graphs based on their flexibility to work with complex data domains s.a. recommendation (Monti
al., [017; van den Berg et al., 20188). chemistry (Duvenaud et al. 22155: Gilmer al. (017).
physics (Cranmer et al. [2019] Bapst et al. (2020), transportation (Derrow- wwww-PPnionnao et al. 2021). vi-
sion (Han et al. 2022). NLP (Wu et al. [0211a), knowledge graphs (Schlichtkrull al. (018). drug
design (Stokes et al. 20220 Gaudelet et al. (2020) and medical domain (Li et al.) 2020b 2021 Most
GNNs are designed to have two core components. First, a structural
cesssag-passsing mechanism
s.a. Defferrard et al. (2016); Kipf & Welling (017); Hamilton et al. (2017); Monti al. (2017);
Bresson & Laurent 2017]; Gilmer et al. (2017) 7); Veličković et al. (2018) that computes node rep-
resentations by aggregating the local h-hop neighborhood information. Second, a stack of L layers that aggregates L-hop neighborhood nodes to increase the expressivity of the network and transmit information between nodes that are I.-hops apart.
Weisfeiler-Leman GNNs (WL-GNNs), One of the major limitations of MP-GNNs is their inability to distinguish (simple) non-isomorphic graphs. This limited expressivity can be formally analyzed with the Weisfeiler-Leman graph isomorphism test (Weisfeiler & Leman 1968), as first proposed in Xu et al. (2019); Morris et al. (2019). Later on, Maron al. (2018) introduced a general class of lo-order WL-GGNs that can be proved to universally represent any class of k-WL graphs (Maron) al. 2019 Chen al. 2019). But achieve such expressivity, this class of GNNs requires using k-tuples of nodes with memory and speed complexities of O(N*), with N being the number of nodes and k (Maron et al.) 2019 Chen al. 2019 Azizian & Lelarge, 2020). it is still computationally costly compared to the linear complexity O(E) MP-GNNs, which often reduces to O for real-world graphs that exhibit sparse structures s.a. molecules, knowledge graphs, transportation networks, gene regulatory networks, to name a few. In order to reduce memory and speed complexities of WL- GNNs while keeping high expressivity, several works have focused on designing graph networks from their sub-structures s.a. sub-graph isomorphism (Bouritsas et al.; (022). sub-graph routing mechanism (Alsentzer al. 2020), cellular WL. sub-graphs (Bodnar et al. 202T). expressive sub-
Although the complexity can be reduced O(N2) and O(N3) respectively

---

Under review as a conference paper at ICLR 2023
graphs (Bevilacqua et al. 2021; Frasca al. 2022). rooted sub-grage sub-graphs (Zhang & Li 2021 and k-hop egonet sub-graphs (Zhao et al. (021a).
Graph Positional Encoding (PE). Another aspect of the limited expressivity of GNNs is their inability to recognize simple graph structures s.a. cycles or cliques, which are often present in molecules and social graphs (Chen et al. 2020). We can consider k-order WL-GNNs with value k to be the length of cycle/clique, but with high complexity O(N*). An alternative approach is to add positional encoding to the graph nodes. It was proved in Murphy et al. (2019); Loukas (2020) that unique and equivariant PE increases the representation power of any MP-GNN while keeping the linear complexity. This theoretical result was applied with great empirical success by Murphh et al. (2019) with index PE, Dwivedi et al. (2020): Dwwivedi & Bresson (2021); Kreuzer et al. (2021))
al. 2 with Laplacian eigenvectors and Li et al. (2020a); Dwivedi et al. (2021) with k-step Random Walk. All these graph PEs lead to GNNs strictly more powerful than the 1-WL test, which seems to be enough expressivity in practice (Zopf) (022). However, none of the PE proposed for graphs can provide global position of the nodes that is unique, equivariant and distance sensitive. This is due to the fact that a canonical positioning of nodes does not exist for arbitrary graphs, as there is notion of up, down, left and right on graphs. For example, any embedding coordinate system like graph Laplacian eigenvectors (Belkin & Niyogi 2003) can flip up-down directions, right-left directions, and would still be valid PE. This introduces ambiguities for the GNNs that require to (learn to) be invariant with respect to the graph or PE symmetries. A well-known example given by the eigenvectors: there exist 2 number of possible sign flips for l cigenvectors that require to be learned by the network.
-quusinus Standard MP-GNNs require L layers to propagate the information from one node to their L-hop neighborhood. This implies that the receptive field size for GNNs can grow exponen- tially, for example with ((2 for binary tree graphs. This causes over-squashing; information from the saaementttaly-growinnn receptive field is compressed into fixed fixed-length vector by the aggregation mechanism (Alon Yahav, 2020; Topping et al., 2022). Consequences of over-squashing are over- fitting and poor long-range node interactions as relevant information cannot travel without being disturbed, Over-squashing is well-known since recurrent neural networks (Hochreiter & Schmidhu- ber 1997). which have led to the development of the (self- and cross- )attenton mechanisms for the translation task (Bahdanau et al. 2014 Vaswani et al. (017) first, and then for more general natural language processing (NLP) tasks (Devlin et al. 2018 Brown et al., 2020). Transformer architectures are the most elaborated networks that leverage attention. Attention is a simple but powerful mecha- nism that solves over-squa and long-range dependencies by making "everything connected to everything" but it also requires to trade linear complexity for quadratic complexity. Inspired by the great successes of Transformers in NLP and computer vision (CV), several works have proposed to generalize the transformer architecture for graphs achieving competitive or superior performance against standard MP-GNNs. We highlight the most recent research works in the next paragraph.
generalize Transformers to graphs, with graph Laplacian eigenvectors as node PE, and incorporating graph structure into the permutation-innariant attention function. SAN and LSPE (Kreuzer et al.) [021 Dwivedi et al.) 202T further improve with PE learned from Laplacian and random walk operators. GraphiT (Mi- alon et al.] 2021) encodes relative PE. derived from diffusion kernels into the attention mechanism. GraphTrans (Wu et al. 2021b) and SAT (Chen et al. 2022) add Transformers on the top of standard GNN layers. Graphormer ( (Ying et al.] (021) introduce three structural encodings, with great suc- cess on large molecular benchmarks. GPS (Rampášek et al. (022) categorizes the different types of PE and puts forward a hybrid MrnN+Transformer architecture. We refer to Min et al.] (2022) for an overview of graph-structured Transformers. Generally, most Graph Transformer architectures address the problems of over-squashing and limited long-range dependencies in GNNs but they also increase significantly the complexity from O(E) to O(N2), resulting in computational bottleneck.
Graph Transformers. Graph Transforrsssmmrrs (Dwivedi & Bresson 2021
VIT and MLP-Mixer. Transformers have gained remarkable success in CV and NLP. most notably with architectures like ViT (Dosovitskiy et al. (0200) and BERT (Devlin et al.] 2018)). The success of transformers has been long attributed to the attention mechanism Vaswani et al. 2017). which is able to model long- long-range dependencies as it does not suffer from squashin...... But recently, this prominent line of networks has been challenged by more cost efficient alternatives. A novel family of models based on the MLP-Mixer introduced by Tolstikhin et al. (202T) has emerged and gained recognition for its simplicity and its efficient implementation. Overall, MLP-Mixer replaces the at- tention module with multi-layer perceptrons (MLPs) which are also not affected by over- werrssuashing
2

---

Under review as a conference paper at ICLR 2023
and poor long-range dependencies. The original architecture is simple TTlstikhin et al. 2021 it takes image patches (or tokens) as inputs, encodes them with a linear layer (equivalent to a convolu- tional layer over the image patches), and updates their representations with series of forwafo layers applied alternatively to image patches (or tokens) and features. The follow-up variants inves- tigate different mixing operations, such as ResMLP (Touvron et al.) (02T). gML. (Liu et al. [00TT) and DynaMixer (Wang et al., (2022). These plain networks can perform competitively with state-of- the-art vision Transformers, which tends to indicate that attention not the only important inductive bias, but other elements like the general architecture of Transformers with patch embedding, resid- ual connection and layer normalization, and carefully-curated data augmentation techniques seem to play essential roles as well (Yu et al., 2022).
I
Main Objective. Motivated by the MI.P-Mixer introduced in CV, our goal is to investigate a gen- eralization of this architecture from grids to graphs. The motivation is clear; MI.P-Mixer offers a low-cost alternative to ViT for images, avoiding the quadratic complexity of the attention mecha- nism while keeping long-range interactions. We wish to transfer these advantages to GNNs. Our contributions are as follows.
We identify the key challenges to generalize MLP-Mixer from images to graphs.
We design new GNN, namely Graph MLP-Mixer, that is not limited by over-squashing and poor long-distance dependencies while keeping the linear complexity of MP-GNNs.
We report extensive experiments analyze the proposed GNN architecture with several datasets from the Benchmarking GNNs (Dwivedi et al. 2020) and the Open Graph Bench- mark (OGB) (Hu et al. 2020).
* Our approach forms bridge between CV, NLP and graphs under unified architecture, that can potentially benefit cross-over domain collaborations to design better networks.
GENERALIZATION CHALLENGES
In the following, we list the main questions when adapting MLP-Mixer from images to graphs.
(1) How to define and extract graph patches/tokens? One notable geometrical property that distinguishes graph-structured data from regular structured data, such as images and sequences, is that there does not exist in general a canonical grid to embed graphs. As shown in Table [ images are supported by regular lattice, which can be easily split into multiple grid-like patches (also referred to as tokens) of the same size via fast pixel reordering. However, graph data is irregular: the number of nodes and edges in different graphs typically different. Hence, graphs cannot be uniformly divided into similar patches across all examples in the dataset. Finally, the extraction process for graph patches cannot be uniquely defined given the lack of canonical graph embedding. This raises the questions of how we identify meaningful graph tokens, and quickly extract them.
(2) How to encode graph patches into a vectorial representation? Since images can be reshaped into patches of the same size, they can be linearly encoded with an MLP, equivalently with con- volutional layer with kernel size and stride values equal to the patch size. However, graph patches not all the same size: they have variable topological structure with different number of nodes, edges and connectivity. Another important difference is the absence of a unique node ordering for graphs, which constrains the process be invariant to node re-indexing for generalization purposes. In summary, we need a process that can transform graph patches into a fixed-length vectorial rep- resentation for arbitrary subgraph structures while being permutation invariant. GNNs are naturally designed to perform such transformations, and as such will be used to encode graph patches.
(3) How preserve positional information for nodes and graph patches? As shown in Table D image patches in the sequence have implicit positions since image data is always ordered the same way due to its unique embedding in the Fuclidean space. For instance, the image patch the upper- left corner is always the first one in the sequence and the image patch at the bottom-right corner is the last one. On this basis, the token mixing operation of the MLP-Mixer is able to fuse the same patch information. However, graphs are therefore unordered. We face a similar issue when we consider the positions of nodes within each graph patch. In images, the pixels in each patch are always ordered the same way; in contrast, nodes in graph tokens are naturally unordered. Thus, how do we preserve local and global positional consistency for graph patches, and nodes in each patch?
naturally not-aligned and the set of graph patches
3

---

Under review as a conference paper at ICLR 2023
Images
Graphs
Regular grid
Irregular domain Variable data structure (# Nodes and Edges)
Input
Same data resolution (Height, Width)
Via pixel reordering
Via graph clustering algorithm Overlapping patches
Patch Extraction
Non-overlapping patches
Same patches at each epoch
Different patches at each epoch
Same patch resolution
Variable patch structure
Patch Encoder
(Patch Height, Patch Width)
(# Nodes and Edges)
MLP (equivalently CNN)
GNN (e.g. GCN, GAT, GT)
Implicitly ordered
No universal ordering
Positional Information
(No need for explicit PE)
Node PE for patch encoder
Patch PE for token mixer
Channel mixer
Channel mixer
MLP-Mixer
Token mixer
Token mixer with patch PE
Table 1: Differences between MLP-Mixer components for images and graphs.
(4) How to reduce over-fitting for Graph MLP-Mixer? Most MLP-variants (Tolstikhin et al., 2021 TTuvroo al., 202T, [Wang et al. (022) first pre-train on large-scale datasets, and then fine-tune on downstream tasks, coupled with rich set of data augmentation and regulariza- tion techniques, e.g. cropping, random horizontal flipping, RandAugment (Cubuk al., 2020)) mixup (Zhang al. 2017). etc. While data augmentation has drawn much attention in CV and NLP, graph data augmentation methods are not yet as effective, albeit interest and works on this topic (Zhao al. 20211b. Variable number of nodes, edges and connectivity make graph augmen- tation challenging. Thus, how do we augment graph-structured data given this nature of graphs?
We summarize the differences between standard MLP-Mixe and Graph MLP-Mixe in Table
PROPOSED ARCHITECTURE
3.1 OVERVIEW
The basic architecture is illustrated in Figure 1 The goal of this section is to detail the choices we made implement each component of the architecture. On the whole, these choices lead simple framework that provides good practice performance.
Notation. Let (V,E)
graph with being the set of nodes and the set of edges. The graph has N = | nodes and E = [E] edges. The connectivity of the graph is represented by the adjacency matrix
N x.N The node features of node are denoted by h,, while the features for an edge between nodes and are indicated by eij. Let (V,..., Vp) be the nodes partition, P be the pre-defined number of patches, and G, = (V,, 3,) be the induced subgraph of G with all the nodes in V4 and all the edges whose endpoints belong V, Let he be the graph- vectorial representation and yo be the graph-level target, which can discrete variable for graph classification problem, scalar for graph regression task.
4

---

Under review as a conference paper at ICLR 2023
Putch Excacion (Genanic P son pacho cadigadd
Euibeddia
Layer
Ye g
Mivel Layer
Fuc Clased Informsionn
Channel Miker
Gouph Encoder (GNNN)
Global Pallin
Groph Levd Prodetion
Palty
Leye
Tokes Miser
1-8p Overapping
Loyel
Node PLS
Potch PE
X A g
Figure I: The basic architecture of the proposed Graph MLP-Mixer. Graph MLP-Mixer consists of a patch extraction module, a patch embedding module. mixer layer, a global average pooling, and classifier head. The patch extraction module partitions graphs into overlapping patches. The patch embedding module transforms these graph patches into corresponding token representations, which are fed into sequence of mixer layers to generate the output tokens. A global average pooling layer followed by fully-connected layer is finally used for prediction. Each Mixer Layer is residual network that alternates between a Token Mixer applied to all patches, and a Channel Mixer applied to each patch independently.
3.2 PATCH EXTRACTION
When generalizing MLP-Mixer to graphs, the first step is to extract patches. This extraction is straightforward for images. Indeed, all image data R#* W are defined on regular grid with the same fixed resolution (H, W), where H and W are respectively the height and the width, and C' is the number of channels. Hence, all images can be easily reshaped into a sequence of flattened patches Tp E (I(()))) where (R, Rt) is the resolution of each image patch, and P = HW/II² is the resulting number of patches, see Table
Unlike images with fixed resolution, extracting graph patches is more challenging. Generally, graphs have different sizes, i.e. number of nodes, and therefore cannot be uniformly divided like image data. Additionally, meaningful sub-graphs must be identified in the sense that nodes and edges composing a patch must share similar semantic or information, s.a. a community of friends sharing biking interest in social network. As such, graph patch extraction process must satisfy the following conditions: (I) The same extraction algorithm can be applied to any arbitrary graph, (2) The nodes in the sub-graph patch must be more closely connected than for those outside the patch, and (3) The extraction complexity must be fast, that is at most linear w.r.t. the number edges, i.e. OEE).
Graph partitioning algorithms have been studied for decades (Buluç et al. 2016 given their im- portance in identifying meaningful clusters. Mathematically, graph partitioning is known to be NP-hard [Chung] 1997). Approximations are thus required. A graph clustering algorithm with one of the best trade-off accuracy and speed is METIS (Karypis & Kumar 1998). which partitions a graph into pre-defined number of clusters/patches such that the number of within-cluster links is much higher than between-cluster links in order to better capture good community structure. For these fine properties, we select METIS our graph patch extraction algorithm.
However, METIS is limited to finding non-overlapping clusters, as visualized in Figure T In this ex- ample, METIS partitions the graph into four non-overlapping parts, i.c. {1, (1,2,3) (4, 5, 6). (7,8, (7, and {10, 11, 12), resulting in 5 edge cuts. Unlike images, extracting non-overlapping patches could imply losing important edge information, i.e. the cutting edges, and thus decreasing the predictive performance, as we will observe experimentally. To overcome this issue and to retain all original edges, we allow graph patches to overlap with each other. For example in Figure [ if the source and destination nodes of an edge are not in the same patch, we assign both nodes to the patches they belong to. As such, node 3 and node 4 are in two different patches, here the blue and red one, but connected with each other. After our overlapping adjustment, these two nodes belong to both the blue and red patches. This practice equivalent to expanding the graph patches to the one-hop neighbourhood of all nodes in that patch. Formally, METIS is first applied to partition graph into
5

---

Under review as a conference paper at ICLR 2023
P overlapppip patches: (Vi..... Vp} such that V/ 11 UV. and Vnv, = vi j. Then, patches are expanded to their one-hop neighbourhood in order to preserve the information of between-patee parecennppcchhhtee links and make use of all graph edges: V; V; U {VG()) I V; where Ny. (1) defines the k-hop neighbourhood of node j.
3.3 PATCH ENCODER
For images, patch encoding can be done with a simple linear transformation given the fixed reso- lution of all image patches. This operation is fast and well-defined. For graphs, the patch encoder network must be able handle complex data structure such as invariance index permutation, heterogeneous neighborhood, variable patch sizes, convolution on graphs, and expressive to differ- entiate graph isomorphisms. a result, the graph patch encoder is GNN, whose architecture designed to best transform a graph token Gp into a fixed-size representation F. E IRd into 3 steps.
Step 1. Raw node and edge linear embedding. The input node features a; R4,x1 and edge features Big E Id x1 are linearly projected into d-dimensional hidden features:
h a, u Rd; ci Vo vd Rd
where Uo E [Rdxds v Rdxd. and u², v0 E Rd are learnable parameters.
Step Graph convolutional layers with (favorite) GNN. We apply series of L. convolutions to improve the patch representation of node and edge features:
h,+1 fr (r, (hğlí E (())),))) 1ft1. h Rd,
(2)
8+1 fe, ofy) ej
Cg ee ER.
where l is the layer index, functions and Se (with learnable parameters) define the specific GNN architecture, and (() is the neighborhood of the node i.
Step 3. Pooling and readout. The final step produces a fixed-size vector representation by mean pooling all node vectors in Gp. and applying small MLP to get the patch embedding IG,-
The patch encoder is GNN, and thus has the same potential limitations of over-squashing and poor long-range dependencies. However, these problems become prominent only for large graphs. But for small patch graphs, such problems do not really exist (or are negligible). Indeed, in practice, the mean number of nodes and the mean diameter for graph patches are around 3.2 and 1.8 respectively for molecular datasets and around 12.0 and 2.7 for image datasets, see Table
3.4 POSITIONAL INFORMATION
Regular grids offer natural implicit arrangement for the sequence of image patches and for the pixels inside the image patches. However, such ordering nodes and patches do not exist for general graphs. This lack of positional information reduces the expressivity of the network. Hence, we use explicitly one absolute PE for the patch nodes and one relative PE for the graph patches. Node PE. Input node features in I are augmented with P; R
h? T + U - n ER,
where 7 E [Rd learnable matrix. The benefits of different PEs are dataset dependent. We follow the strategy in Rampäšek al. (2022) that uses random-wall structural encoding (RWSE) (Dwivedi et al.] 2021) for molecular data and Laplacian cigenvectors encodings (Dwivedi et al. 2020) for image superpixels. Since Laplacian eigenvectors are defined up to sign flips, the sign of the eigenvectors is randomly flipped during training.
Patch PE. Relative positional information between the graph patches be computed from the original graph adjacency matrix A E IR NxN and the clusters (V),.., Vp} extracted by METIS in Section 3.2 Specifically, we capture relative positional information via the 'coarsened adjacency
matrix' E PxPx over the patch graphs:
ALe IVn Cut(V,,V))
= where Cut(V, = Ebev, Eiev, ARI is the standard graph cut operator which counts the number of connecting edges between cluster V; and cluster Vj. We observe that matrix AP is sparse it

---

Under review as a conference paper at ICLR 2023
only connects patches that neighbors on the original graph. This poor long-distance interactions. To avoid this situation, we can simply smooth out the adjacency matrix A with any graph diffusion process. In this work, select the n-step random walk diffusion process:
Ap = "D'"""" E RPx
(5)
3.5 MIXER LAYER
For images, the original mixer layer in Tolstikhin al. (2021) simple network that alternates channel and token mixing steps. The token mixing step is performed over the token dimension, while the channel mixing step carried out over the channel dimension. These two interleaved steps enable information fusion among tokens and channels. The simplicity of the mixer layer has been of great importance to understand that the self-attention mechanism in VIT is not the only critical component to get good performance on visual classification tasks. This has also led to significant reduction in computational cost with little or no sacrifice performance. Indeed, the self- self-attention mechanism in ViT requires (P2) memory and O(P2) computation, while the mixer layer in MI.PMixer needs ((P) memory and (PP) computation.
We modify the original mixer layer introduce positional information between graph tokens. Let X E TR. Pxd be the patch embedding (IG,,... TG. The graph mixer layer can be expressed as
U= X (W2 ( (ayyerorm(AAA))) E Pxxd
Token mixer,
(6)
== (Wa (W3 LayerNorm(U)"))" Pxd
Channel mixer,
where AB TR. PxP is the patch PE from 5q o is GELU nonlinearity (Hendrycks & Gimpel 2016), LayerNorm(.)
layer normalization (Ba et al. 2016). and matrices W1 R W2 R gxxd, W3 E Rdd'dd W1 E Rd where de and de are the tunable hidden widths in the token- mixing and channel-mixing MIPs, and are set following (Tolstikhin et al. (202T).
We generate the final graph-level representation by mean pooling all the non-empty patches:
ha Σ mp IGpl
Σ mp E ERd
Emp
where m, is a binary variable with value for non-empty patches and value 0 for empty patches (since graphs have variable sizes, and thus small graphs can produce empty patches). Finally, apply a small MLP to get the graph-level target:
yG MLP(ha)
(8)
3.6 DATA AUGMENTATION
MLP-Mixer architectures are known to be strong over-fitters (Liu et al. 202I}. In order to reduce this effect, perform data augmentation of graph patches. At each epoch, we randomly drop a few edges before running METIS partitioning, to produce more diverse partitions. This data augmentation process is very fast as METIS graph clustering only amounts to small portion of the data preparation time, therefore adding little extra cost during the training processes.
4 EXPERIMENTS
Graph Benchmark Datasets. We conduct extensive experiments to investigate the proposed method. From the Benchmarking GNNs (Dwivedi et al. 2020). we test on ZINC, MNIST and CI- FARIO. From the open graph benchmark (OGB) (Hu et al. 2020). we test on MolHIV, MoITOX21, and MolPCBA. Summary statistics of datasets reported T Appendix A..
Extraction Step: Study of # patches. We observe in Figure 5 that increasing the number of patches generally improves performance, which is consistent with computer vision (Dosovitskiy al. 2020 Tolstikhin et al. 2021). We set the number of patches to 16/32 by default. The resulting graph patches are of small size; they typically contain 3-12 nodes with value diameter of 2-3, see Table
Extraction Step: Study of k-hop extension. In Figure 2 and Table I0 we observe a clear per- formance increase when graph patches overlapping with each other (0-hop 1-hop), which is
7

---

Under review as a conference paper at ICLR 2023
0.28
0.31
09
0.13
0.66
0.28
sltap Hop
0.01
0.44
GCN
GIN
Gopiiieaa
OCN
GEENDON
GINE
CrapiTora
GCN
GRANOON
GINE
Puach Raooder
Paich Faooder
Piara Fhooder
Figure 2: Effect of the k-hop extension. We expand graph patches extracted by METIS to the k-hop neighbourhood of all nodes in that patch. O-hop means non-overlapping patches without extension.
Model
7INC
MNIST
CIFARIO
MaITOX21
MalHIV
MolPCRA
Pepcide-fune
Pepiide-trict
MAR L
Accuracy 7
Accuracy
ROCAUCT
ROCAUC T
Avg. Procision
Arg. Procision
MAR
GEN
0,1956
0.9574 + 0.0016
0.5976 0.00ES
0.7644 DI0176
0:7065 0.0095
0.0044
0.6376
0.2745 0.0010
GCN-MI MLP Miser
0,1890 0.0067
0,9606 2: 0.0019
0.5892 0,0024
0.7737
& 0.0062
0.7865 = 0.0130
0.2525 0.0015
0.6545
010015
0,2509 2 0.0011
GCN MLP-Mixer Mixer"
0,1352 0.0056
0,9773 à 0,0007
0.6579 0,0042
0,7824 à: 0.0041
0,7849 a: 0.0043
0,2186 0.0016
0.6736 0
0,2488 0.0012
GateOOCN
0.1565 a 0.0023
0.9815 a 0.0010
0,6703 0.00G4
0,7659 0.0061
0,7673 :: 0.0123
0.2721
0.0036
0.6452 0.0111
a 0.0023
GaedOCN MI P-Mixer
0,1540 0.0846
0,9823 a 0.0011
0.6804 IL0043
0U77X3 0.0041
0,7834 0.0062
0.2669 0.0022
0.66%
0L0039
0,2519 + 0.0016
GGDeGGCN-MI P-Mixxx
0,1251 0.0080
0,9831 0.0010
0.68% 0.0021
0.7912 0.0133
0.2649 0.0015
0.0073 0,6790
0.0013
GINE
0,1183 0U0027
0,9740 a: 010013
0.6031
0,0030
0,7669 C.0152
0,7660 0.015
0,3749 0.0021
0.6616 010051
0,2768 010014
GINE
0.0029
0,9778 0,0014
0.6053
0,0082
0.0079
0,7524 0.0131
0.2613 0.0015
0.6627
0.0106
0,2498 0.0028
GINE MLP M-Mixer*
0,0794 0.0028
0,9787 a: 0.0012
0.0064 0.6625
0,7839 & 0.0038
0.7844 & 0.0033
0,2666 0.0029
0,6846 0,0068
0,2478 & 0,0010
GraphTrans
0,1286 0.0029
0,9732 a 0.0014
0.6876 0.0077
0,7672 0.0065
0,7786 0.0089
0,2098
0.0032
0 0.0031
0.2768 0.0014
GraphiTran-M A.T.PMMA P-Miser
0.1190
0.0016
0,979% a 010008
0.7010 a 0.0041
0.774N + 11,079
0.7885 = 0.0182
0.2433
0JM637
0.6585 0.040)
0.2522 0.0025
GraphiTras-MM MoriiTins--LLL ML- MLP-Mixe
0.0831 0.0032
0,9827 + 11,008
0.7023 IL0046
0.7827 0.00K6
0,7823 0.0217
0.2214
010055
0.6814 0.0072
0.24K3 = 0.0013
GNN-free MI P-Mixer
0,1290 0.0045
0.9717 + 0.0008
0 59197 + 0.0009
0.7338 0.0048
0.7852 000151
0.2199- 000066
Table 2: Performance on Benchmarking datasets (Dwivedi et al. 2020), OGB (Hu et al. 2020 and LRGB (Dwivedi et al. 2022). Shown is the mean + s.d. of 4 runs
consistent with our intuition that extracting non-overlapping patches implies losing important edge information. We further expand graph patches to their k-hop neighbourhood. Performance increases first and then flattens out begins to decrease when A 3 for ZINC and k 1/2 for MolHIV.
Encoder Step: GNN-based patch encoder. We evaluate the effect of various GNN models as patch encoder in Table 2, which includes GCN (Kipf & Welling 2017). GatedGCN (Bresson &
Laurent 2017). GINE (Hu et al. 2019) and Graph Transformer (Shi et al. 2020). We find that our GNN- MML--Mixer architecture matches outperforms existing GNNs across different datasets
and patch encoders. These promising results demonstrate the generic nature of the proposed Graph MLP-Mixer architecture which can be applied to any MP-GNNs in practice.
Encoder Step: GNN-free patch encoder. We also investigate a GNN-free patch encoder. For each patch, we embed all node and edge features as bags of nodes and edges, then average and readout, where all transformations are based exclusively on MLPs, see Eq Interestingly. this GNN-free MLP-Mixer produces good results (last row of Table 2) which seems to imply that the GNN-encoder is not critical in this architecture. Even more excitingly. further development of Graph
MLP-Mixer may not need to use specialized GNN librarics like DGL (Wang al. 2019) or PyG
Fey & Lenssen 2019a) to achieve competitive performance with standard MP-GNNs.
Encoder Step: Updated node encoding. We consider a more expressive GNN-MLP-Mixer by updating the node representation with the patch representation coming from the mixer layer. We call this improved version GNN-MLP-Mixen and we present the details in Appendix A.9
Positional Information. We show the effects of two kinds of positional encoding in Figure 3 First, we observe a significant drop in performance when either node PE or patch PE is removed. Besides, it can be observed that the extent of poor performance of models without node PE against using node PE is greater for ZINC than MolHIV. This difference can be explained by the fact that ZINC features purely atom and bond deseriptors whereas MolHIV features consist additional information that is informative of e.g. if an atom is in ring, among others.
Data Augmentation. Then proposed data augmentation (DA) corresponds to newly generated graph patches with METIS at each epoch, while no DA means patches are only generated at the initial epoch and then reused during training. Table 3 presents different results. First, it is clear that DA
8

---

Under review as a conference paper at ICLR 2023
Methods
GCN-ML P-Mixer
SinedGCN-MM..-MMMN
GINE-MUP-MMR
GraphTrans-Mi P-Mixer
ZINC
Qurs
0,1880
0,1540
0,1090
0.1190
node PE
0.4704
0.4611
jwla patch PE
0.1906
0.1634
0.1193
0.1245
Best
MolllV
Methods
GCN-MLP-Misse
GaIeIGCN-MLP-MMeee
GINE-MLP-Mixc
Qurs
0,7865
0,7824
0,7824
0,7808
Wio node PE
0,7700
0.7776
0.7786
0.7773
wil patch
0.7731
0,7661
0.7679
0.763]
Pipbiee fun-
Methods
GCN-MLPP-Mixe
GateGGCN-MLP-MMin
GINE-MLP-Mixer
Graph MruphhTras-MLL....
Ours
0.6736
0.6790
0,0846
0:6814
wio node PE
0.6563
0.6663
0,6801
0.6699
patch
0.66442
Figure 3: Effect of positional information. We study the effects of node PE and patch PE by remov- ing one of them in turn from our model while keeping the other components unchanged.
Dataset
MAEJ/ / ROCAUCT
Time(S/Epoch)
Daraset
Model
MAEL/ ROCAUCT
0.1266
GINE-ML P-Mixer
0.0028
7INC
ZINC
0.1171 0.0029
5,9922
GINE-VIT
0,1066 0.0014
MolHTV
0.7569 0.0281 0,7824 + 0.0131
14.8949
MolHIV
GINE ML P-Mixer GINE-VIT
0.7844 0.0033
15,5889
0.7694 0.0158
Table 3: Effect of data augmentation (DA): X means DA and Vsee DA.
Table 4: Mixer Layer vs. Transformer Layer.
brings an increase in performance. Second, re-generating graph patches only add small amount of training time. Full results are reported in Table T2
ZINC
MolHIV
MolPCBA
Poptides-fune func
Peptides-struct
Model
MAF
ROCAUC
ROCAUCT
Avg. Precision
MAE
GT (Diivedi Bresson
0.014
GraphrT Minion el 274
0,202 0.011
Graphommer (Yin al
2022
0.122 0.006
GPS Rampakek 3l
2076
0,070 0.004
0.7880 : 0.0101
0.2907 0.0028
0.6362 = 0.0115 0.6439 = 0.0075
0,2515 0.0012
SAN (Chnn al 2012
0.139 0.006
0,7775 a 0.0061
0,2765 a 0.0142
0,2545 a 0.0012
GraphITans
2021
0.2761 0.0029
Alsentzer al
0.001
0.0044
0.6480 0.0089
0.2736
SUN (Prash al 2024)
0.084 = 0.002
0,8003 + 0.0055
0,2616 = 0.0049
0.6730 0.0078
0.2498 0.0008
Graph MT P-Mixer* (Ours)
0.0794 + 0.003
0.7912 0.0133
0.2749 0.0021
0.6846 0.0068
0.2478 0.0010
Table 5: Comparison of best results from Table 2 with the state-of-the-art GTs (missing values from literature are indicated with '-'). For ZINC, all models have approximately ~ 5004 parameters.
Mixer Layer: MLP vs. Attention. In Table we replace MLP-Mixer layers with standard Trans- former layers while keeping the rest the components the same. The performance of MLP-Mixer is surprisingly better than the latter despite lower complexity. Full results are reported in Table
Transformer (GT) models. To ensure fair comparison, we did not include Graphormer (Ying et al. 2021) that achieved top score on MolHIV after pre-training on large dataset of 3.8M graphs. Overall, we observe that our Graph MLP-Mixer model achieves competitive performance without making use of the fully-connected attention mech- anism, solely using low-cost mixer operations. Besides, we are more efficient in model parameters and training time. Full comparison with number of training parameters, memory and training time provided Table and Table 15 in the appendix.
State-Of-The-Art. Table presents the SOTA
Expressivity. We experimentally show that Graph MLP-Mixer is strictly more powerful than 1-WL, and not less powerful than 3- WL. Although graph PEs s.a. Laplacian eigenvectors (Belkin & Niyogi 2003) k-step Random Walk PE (Li et al. 2020a Dwivedi et al. 2021) cannot guarantee two

---

Under review as a conference paper at ICLR 2023
graphs generally isomorphic, it was shown in Dwivedi et al. (2021) that they can distinguish non- isomorphic graphs for which the 1-WL test fails. As a consequence, Graph MLP-Mixer is strictly more powerful than 1-WL. We experimentally validate this property by running Graph MLP-Mixer on the highly symmetrie Circulant Skip Link (CSL. dataset Murphy et al. (2019) in Table 16 which requires GNNs to be strietly more expressive than the 1-WL test succeed. Besides, Graph MLP-Mixer reaches perfect accuracy on SR25 (Balcilar et al. 2021j. The SR25 dataset contains 15 strongly regular graphs with 25 nodes each, where no model less powerful 3-WL test can distinguish the pairs in SR25 dataset.
Long Range Graph Benchmark (LRGB). We evaluate our models and compare with the baselines on the LRGB (Dwivedi et al. (022) with 2 graph-level datasets, i.e., Peptides-furg funde and Peptides- struct, that arguably require long-range information reasoning achieve strong performance the given tasks. As shown in Table Table@ante and Table 5 Graph MLP-Mixer performs significantly better than the baselines, especially on Peptides-struct. The improvement can be explained by the nature of these datasets, which is consistent with the empirical findings in (Dwivedi et al. 2022) that simple instances of local MP-GNNs perform poorly on the proposed datasets, More information is provided in Table L5
CONCLUSION
In this work, have proposed novel GNN model directly inspired from ViT/MLP- archi- tectures in computer vision and presented promising results on benchmark graph datasets. Future work will focus further exploring graph networks with the inductive biases of graph tokens and Transformer-like architectures in order to solve fundamental node and link prediction tasks, and potentially without the need of specialized GNN libraries.
10

---

Under review as a conference paper at ICLR 2023
REFERENCES
Uri Alon and Eran Yahav, On the bottleneck of graph neural networks and its practical implications. arXiv preprint arXiv:2006.05200 2020.
Emily Alsentzer. Samuel Finlayson, Michelle Li, and Marinka Zitnik. Subgraph neural networks. Advances in Neural Information Processing Systems, 33:8017-8029, 2020.
Waiss Azizian and Marc Lelarge. Expressive power of invariant and equivariant graph neural net- works. arXiv preprint arXiv:2006. 15646, 2020.
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv preprint 17X1::1607.06450., 2016.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. arXiv preprint arXiv:1409.044 2014.
Muhammet Balcilar, Pierre Héroux, Benoit Gauzere, Pascal Vasseur, Sébastien Adam, and Paul Honeine. Breaking the limits of message passing graph neural networks. In International Con- ference on Machine Learning, pp. 599-608. PMLR, 2021.
Victor Bapst, Thomas Keck, A Grabska- Baooska-Brriiikk,, Craig Donner, Ekin Dogus Cubuk, Samuel S Schoenholz, Annette Obika, Alexander WR Nelson, Trevor Back, Demis Hassabis, et al. Un- veiling the predictive power of static structure in glassy systems. Nature Physics, 16(4):448 2020.
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural computation, 15(6)) 1396, 2003.
Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M Bronstein, and Haggai Maron. Equivariant subgraph aggregation net- works. arXiv preprint arXiv:2110.02911 2021.
Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang, Pietro Lio, Guido F Montufar, and Michael Bronstein. Weisfeiler and lehman go cellular: Cw networks. Advances in Newral Infor- mation Processing Systems, 34:2625-2640, 2021.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos P Zafeiriou, and Michael Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions Pattern Analysis and Machine Intelligence, 2022.
Xavier Bresson and Thomas Laurent.
Residual gated graph convnets.
arXiv preprint
arXiv:1711.07553 2017.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neclakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
Aydin Buluç, Henning Meyerhenke, Ilya Safro, Peter Sanders, and Christian Schulz. Recent ad- vances in graph partitioning. Algorithm engineering, pp. 117-158. 2016.
Dexiong Chen, Leslie O' O'Bray, and Karsten Borgwardt. Structure-aware transformer for graph rep- resentation learning. In International Conference on Machine Learning, pp. 3469-3489, PMLR, 2022.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. Advances in neural information processing systems, 2019.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? Advances in neural information processing systems, 33:10383-10339 10395, 2020.
Fan RK Chung. Spectral graph theory, volume 92, American Mathematical Soc., 1997.

---

Under review as a conference paper at ICLR 2023
Miles D Cranmer, Rui Xu, Peter Battaglia, and Shirley Ho. Learning symbolic physies with graph networks. arXiv preprint 10X.vv1109.0580000 2019.
Ekin D Cubuk, Barret Zoph, Jonathon Shlens, and Quoc V Le. Randaugment: Practical automated data augmentation with a reduced search space. In Proceedings of the IEEE/CVE conference on computer vision and pattern recognition workshops, pp. 702-703, 2020.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In NIPS, 2016.
Austin Derrow-Pinice Jennifer She, David Wong, Oliver Lange, Todd Hester, Luis Perez, Mare Nunkesser, Seongjae Lee, Xueying Guo, Peter W Battaglia, Vishal Gupta, Ang Li, Zhongwen Xu, Alvaro Sanchez-Gonzalez, Yujia Li, and Petar Veličković. Traffic Prediction with Graph Neural Networks in Google Maps. 2021.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.0488) 2018.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, al. An image is worth 16x 16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010. 19929, 1929,
2020.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzz Guzik, and Ryan Adams. Convolutional networks on graphs for learning molecular fingerprints. Advances in neural information processing systems, 28, 2015.
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. In AAA/ Workshop on Deep Learning on Graphs: Methods and Applications, 2021.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.00982 2020.
Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. In International Conference on Learning Representations, 2021.
Vijay Prakash Dwivedi, Ladislav Rampášek, Mikhail Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. arXiv preprint arXiv:2206.088 08164, 2022.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv:
2019a.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint /rXiv:/903.0mm 02428, 2019b.
Fabrizio Frasca, Beatrice Bevilacqua, Michael M Bronstein, and Haggai Maron. Understanding and extending subgraph gnns by rethinking their symmetries. arXiv preprint 220.::2206.111400 2022.
Thomas Gaudelet, Ben Day, Arian Jamasb, Jyothish Soman, Cristian Regep, Gertrude Liu, Jeremy BR Hayter, Richard Vickers. Charles Roberts, Jian Tang, et al. Utilising graph machine learning within drug discovery and development. arXiv preprint arXiv:2012.05716, 2020.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning, pp- 1263-1272. PMLR, 2017.
William I. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 1025-1035, 2017.
Kai Han, Yunhe Wang, Jianyuan Guo. Yehui Tang, and Enhua Wu. Vision gnn: An image is worth graph of nodes. arXiv preprint ar arXiv:2206.00222, 2022.
12

---

Under review as a conference paper at ICLR 2023
Dan Hendrycks and Kevin Gimpel. arXiv:1606.08415. 2016.
Gaussian error
linear units
(gelus).
arXiv preprint
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8):
1735-1780, 1997.
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. arXiv preprint arXiv: 12265, 2019.
Weihua Hu, Matthias Fey, Marinka Zitmik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:221 11211182200 2-1333,, 2020.
John J Irwin, Teague Sterling. Michael Mysinger, Erin Bolstad, and Ryan Coleman. Zine: free tool to discover chemistry for biology. Journal of chemical information and modeling, 52 (7)11777-1768, 2012.
George Karypis and Vipin Kumar. A fast and high quality multilevel scheme for partitioning irreg- ular graphs. SIAM Journal on scientific Computing, 20(1):359-392, 1998.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1412.6980, 2014.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations (ICLR), 2017.
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Re- thinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 34:21618 116229 2021.
Greg Landrum et al. Rdkit: Open-source cheminformatics. 2006, 2006.
Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably
more powerful neural networks for graph representation learning. Advances in Neural Information Processing Systems, 33, 2020a.
Xiaoxiao Li, Yuan Zhou, Nicha Dvomek, Muhan Zhang, Siyuan Gao, Juntang Zhuang, Dustin Scheinost, Lawrence H Staib, Pamela Ventola, and James S Duncan. Braingnn: Interpretable brain graph neural network for fmnr analysis. Medical Image Analysis, 74:102233, 2021.
Yang Li, Buyue Qian, Xianli Zhang, and Hui Liu. Graph neural neteork-based diagnosis prediction. Big Data, 8(5):39--390, 2020b.
Derek Lim, Joshua Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. Sign and basis invariant networks for spectral graph representation learning. arXiv preprint 2rXiv:2202.130111 2022.
Hanxiao Liu, Zihang Dai, David So. and Quoe V Le. Pay attention mlps. Advances in Neural Information Processing Systems, 34:9204-9211 2021.
Andreas Loukas. What graph neural networks cannot learn: depth vs width. In International Con- Serence Learning Representations, 2020.
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. arXiv preprint arXiv:1812.09900 2018.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. arXiv preprint 1rXiv:1905.11136, 2019.
Grégoire Mialon, Dexiong Chen, Margot Selosse, and Julien Mairal. Graphit: Encoding graph structure in transformers. arXiv preprint arXiv:2/06.05667 2021.
13

---

Under review as a conference paper at ICLR 2023
Erxue Min, Runfa Chen, Yatao Bian, Tingyang Xu, Kangfei Zhao, Wenbing Huang, Peilin Zhao, Junzhou Huang. Sophia Ananiadou, and Yu Rong. Transformer for graphs: An overview from architecture perspective. arXiv preprint arXiv:2202.08455. 2022.
Federico Monti, Michael Bronstein, and Xavier Bresson. Geometric matrix completion with current multi-graph neural networks. Advances in neural information processing systems, 30, 2017.
Christopher Morris, Martin Ritzert, Matthias Fey, William I. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. 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.
Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. In International Conference on Machine Learning, pp. 4663-4673. PMLR, 2019.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. Advances neural information processing systems, 32, 2019.
Ladislav Rampášek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do- minique Beaini. Recipe for general, powerful, scalable graph transformer. arXiv preprint arXiv:2205. /2454, 2022.
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In European semantic web conference, pp. 593-607. Springer, 2018.
Yunsheng Shi, Zhengjie Huang, Shikun Feng, Hui Zhong, Wenjin Wang, and Yu Sun. Masked label prediction: Unified message passing model for semi-supervised classification. arXiv preprint MxXiv:00090335000 2020.
Sandeep Singh, Kumardeep Chaudhary, Sandeep Kumar Dhanda, Sherry Bhalla, Salman Sadullah Usmani, Ankur Gautam, Abhishek Tuknait, Piyush Agrawal, Deepika Mathur, and Gajendra PS Raghava. Satpdb: a database of structurally annotated therapeutic peptides. Nucleic acids re- search, 4(DD))D111--D1122 2016.
Jonathan M Stokes, Kevin Yang, Kyle Swanson, Wengong Jin, Andres Cubillos-Ruiz, Nina M Donghia, Craig R MacNair, Shawn French, Lindsey A Carfrae, Zohar Bloom-Ackermann, et al. A deep learning approach to antibiotic discovery. Cell, 180(4))688-702 2020.
Damian Szklarczyk, Annika L Gable, David Lyon, Alexander Junge, Stefan Wyder, Jaime Huerta- Cepas, Milan Simonovic, Nadezhda T Doncheva, John H Morris, Peer Bork, al. String vl I: protein-protein association networks with increased coverage, supporting functional discovery in genome-wiee experimental datasets. Nucleic acids research, 47(D!):D607-DD6 D613, 2019.
Ilya O Tolstikhin, Neil Houlsby, Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Thomas Un- terthiner, Jessica Yung, Andreas Steiner, Daniel Keysers, Jakob Uszkoreit, et al. Mip-mixer: An all-mip architecture for vision. Advances in Neural Information Processing Systems, 34:24261- 24272, 2021.
Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein. Understanding over-squashing and bottlenecks graphs via curvature. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022, 2022.
Hugo Touvron, Piotr Bojanowski, Mathilde Caron, Matthieu Cord, Alaaeldin El-Nouby, Edouard Grave, Gautier Izacard, Armand Joulin, Gabriel Synnaeve, Jakob Verbeek, et al. Resmlp: Feedforward networks for image classification with data-efficient training. arXiv preprint arXiv:2105.03404, 2021.
Rianne van den Berg, Thomas N Kipf, and Max Welling. Graph convolutional matrix completion. 2018.
14

---

Under review as a conference paper at ICLR 2023
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural informa- tion processing systems, 30, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Minjie Wang, Lingfan Yu, Da Zheng, Quan Gan, Yu Gai, Zihao Ye, Mufei Li, Jinjing Zhou, Qi Huang, Chao Ma, et al. Deep graph library; Towards efficient and scalable deep learning on graphs. 2019.
Ziyu Wang, Wenhao Jiang, Yiming M Zhu, Li Yuan, Yibing Song, and Wei Liu. Dynamixer: a vision mip architecture with dynamic mixing. In International Conference Machine Learning, pp. 22691-22701. PMLR, 2022.
Boris Weisfeiler and Andrei Leman. The reduction of a graph to canonical form and the algebra which appears therein. N7I Series, 229):12-16, 1968.
Lingfei Wu, Yu Chen, Kai Shen, Xiaojie Guo, Hanning Gao, Shucheng Li, Jian Pei, and Bo Long. Graph neural networks for natural language processing: A survey. arXiv preprint arXiv:2106.06000 06000000000 2021a.
Zhanghao Wu, Paras Jain, Matthew Wright, Azalia Mirhoseini, Joseph Gonzalez, and Ion Stoica. Representing long-range context for graph neural networks with global attention. Advances in Neural Information Processing Systems, 34:13266-11 13279, 20211,
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? International Conference on Learning Representations, 2019.
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie- Yan Liu. Do transformers really perform badly for graph representation? Advances in Neural 2021.
Information Processing Systems,
Weihao Yu, Mi Luo, Pan Zhou, Chenyang Si, Yichen Zhou, Xinchao Wang, Jiashi Feng, and Shuicheng Yan. Metaformer actually what you need for vision. In Proceedings the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 10819-10829, 2022.
Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. arXiv preprint arXiv: arXiv: 2017.
Muhan Zhang and Pan Li. Nested graph neural networks. Advances Neural Information Process- ing Systems, 34:15734 15747, 2021.
Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars subgraphs: Uplifting any gnn with local structure awareness. In International Conference on Learning Representations, 2021a.
Tong Zhao, Yozen Liu, Leonardo Neves, Oliver Woodford, Meng Jiang, and Neil Shah. Data aug- mentation for graph neural networks. Proceedings of the AAAI Conference on Artificial Intel- ligence, volume 35, pp. 11015-11023, 2021b.
Markus Zopf. 1-wl expressiveness is (almost) all you need, arXiv preprint
2022.
15

---

Under review as a conference paper at ICLR 2023
A EXPERIMENTAL DETAILS
A.1 DATASETS DESCRIPTION
CSL is synthetic dataset introduced in Murphy et al. (2019) to test the expressivity of GNNs. CSL has 150 graphs. Each CSL graph is a 4-regular graph with edges connected to form a cycle and containing skip-links between nodes.
SR25 is another synthetic dataset used to empirically verify the expressive power of Graph MLP- Mixer. SR25 (Balcilar et al. (02TT) has 15 strongly regular graphs (3-WI, failed) with 25 nodes each. SR25 is translated to 15 way classification problem with the goal of mapping cach graph into a different class.
ZINC (Dwivedi et al. 2020) is a subset (12K) of molecular graphs (250K) from free database of commercially-availaa
compounds (Irwin al. 2012). These molecular graphs are between and 37 nodes large. Each node represents a heavy atom (28 possible atom types) and each edge represents bond (3 possible types). The task to regress molecular property known as the constrained solubility. The dataset comes with predefined 10K/IK/IK train/validationntees split.
MNIST and CIFAR1O (Dwivedi et al., 2020) are derived from classical image classification datasets by constructing an 8 nearest-neighhor graph of SLIC superpixels for each image. The resultant graphs are of sizes 40-75 nodes for MNIST and 85-150 nodes for CIFARIO. The 10-class classification tasks and standard dataset splits follow the original image classification datasets, i.e., for MNIST 55K/5K/10K and for CIFAR 45K/5K/10K K/OK train/validation//ee graphs. These datasets sanity-checks, for CIFAR10.
expect most GNNs to perform close to 100% for MNIST and well enough
MolTOX21 and MolHTV (Hu et al. 2020) molecular property prediction datasets adopted from the MoleculeNet (Szklarezyk et al. 2019). All the molecules are pre-processed using RDKit (Lan-) drum et al. 2006). Each graph represents a molecule, where nodes atoms, and edges are chemical bonds. Input node features are 9-dimensional, containing atomic number and chirality, as well as other additional atom features such as formal charge and whether the atom is in the ring or not. The datasets come with predefined scaffold splits based on their two-dimensiona structural frame- works, i.c. for MolTOX21 6K/0.78K/0.788/ and for MolHIV 32K/4K/4K vrain/vliiaaiion/ess.
MolPCBA (Hu et al. 2020) is another real-world molecular graph classification benchmark. MOLTOX21 I and MolHIV are of small and medium scale with 7.8K and 41.1k graphs respectively, whereas MOLPCBA is of large scale with 437.9K graphs, and applies similar scaffold spliting procedure. It consists of multiple, extremely skewed (only 1.4% positivity) molecular classification tasks, and employs Average Precision (AP) over them as metric.
Peptides-fune and Peptides-struct (Dwivedi et al. 2022) are derived from 15,535 peptides with a total of 2.3 million nodes retrieved from SAT-Pab (Singh et al. (016)) Both datasets use the same set of graphs but differ in their prediction tasks. These graphs are constructed in such a way that requires long-range interactions (LRI) reasoning to achieve strong performance in a given task. In concrete terms, they are larger graphs: on average 150.94 nodes per graph, and on average 56.99 graph diameter. Thus, they better suited to benchmarking of graph Transformers or other expressive GNNs that are intended to capture LRI.
Distributions of the graph sizes. We plot of the distributions of the graph sizes (i.e. the number of nodes in each data sample) of these datasets in Figure 4
A.2 HYPERPARAMETERS
We follow the benchmarking protocol introduced in Dwivedi et al. (2020) based on PyTorch (Paszke) ct al. 2019) and PyG (Fey & Lenssen 2019b). We use Adam (Kingma & Ba 2014) optimizer, with the default settings of 3, = 0.9, B2 0.999, and
18 The learning rate is reduced by half if the validation loss does not improve after 10 epochs. The training stops at a point when the learning rate reaches to value of x 10 We use 4 layers of GNN layers for patch encoder and 4 layers of Mixer layers by default. For benchmarking datasets from Dwivedi et al. (2020), the dropout is set to O. For OGB datasets from Hu et al. (2020), tune the dropout [0, 0.1, 0.2, 0.3, 0.4, 0.5)
16

---

Under review as a conference paper at ICLR 2023
Dataset
#Graphs
#Nodes
Avg. #Nodes
Avg. #Edges
Task
Metric
CSL SR25
150
41
41
164
10-class classif.
Accuracy
25
25
300
15-class classif.
Accuracy
ZINC
12,000
9-37
23.2
24.9
regression
MAE
MNIST
70,000
40-75
70.6
564.5
10-class classif.
Accuracy
CIFARIO
60,000
85-150
117.6
941.1
10-class classif.
Accuracy
Mo
7831
1-132
18.57
38.6
12-task classif.
ROCAUC
MolHIV
41,127
2-222
25.5
27.5
binary classif.
ROCAUC
MolPCBA
437,929
1-332
26.0
28.1
28-task classif.
Avg. Precision
Peptides-
15,535
2,344,859
150.94
307.30
10-clas classif.
Avg. Precision
Peptides-struct
15,535
2,344,859
150.94
307.30
regression
MAE
Table 6: Summary statisties of datasets used in this study
1000
130
6000
80
3000
400
6000
330
130
graph
graph
(a) ZINC
(b) MNIST
(c) CIFARIO
2.00
400
3.00
7000
2000
3300
1900
1300
500
0:
(d) M
(c) MolHIV
(f) MolPCBA
140
(g) fuptises-func/struct
Figure 4: Distributions of the graph sizes.
for both the baseline and our methods. We run each experiment 4 times, and report the mean + s.d. performance. Detailed hyperparameters are provided Table and Table
A.3 PATCH EXTRACTION
Study of # patches. We observe in Figure that increasing the number of patches generally im- proves performance.
Patch Size and Diameter. We set the number of patches to 16/32 by default. The resulting graph patches are of small size, shown in Table 9
17

---

Under review as a conference paper at ICLR 2023
Hyperparameter
ZINC
MNIST
CIFARIO
CSL
SR25
# Patch
32
16
16
32
16
# GNN layer
4
4
4
4
4
MLP-Mixer layer
4
4
4
4
Hidden size
128
128
128
128
Learning rate
0.001
0.001
0.001
Se-4
0.002
Batch size
128
128
5
15
Node PE
RWSE-20
LapPE-8
LapPE-8
LapPE 200PS-20
LapPE-8
Table 7: Model hyperparameters for four datasets from
Dwivedi et al.
2020
Hyperparameter
MoTTOX21
MolHIV
MolPCBA
Patch
32
32
32
GNN layer # MLP-Mixer layer
4
Hidden size
128
128
400
Learning rate
0.001
0.001
0.005
Batch size
128
128
512
Node PE
RWSE-16
RWSE-16
Table 8: Model hyper parameeasssssers for three datasets from OGB (Hu al. 2020
0.16
0.79
0.155
0.15
0.785
0.145
ROCAUCC
N.N44
0.3265
0.135
0.4858
0.2097
0.7445 2.
0.12
0.37
0.115
0.11
0.765
24
28
32
Patch
Patch
(a) ZINC
(b) MolHIV
Figure 5: Effect of the number of patches.
# Node
Diameter
Dataset
# Patch
Mcan
Min
Max
Mean
Min
Max
ZINC
3.1495
5
1.8151
2
MNIST
16
10.85
18
2.1240
2
4
CIFARIO
16
11.9163
7
20
2.6413
2
6
MolTox21
3.0272
7
1.7293
0
4
MolHIV
3.1822
1.8362
0
6
MolPCBA
32
3.1905
12
1.8640
0
9
Peptides-func/struet
func/struct
32
5,3943
17
3,4407
1
13
Table Summary statistics of graph patches for different datasets.
Effect of k-hop extension. Table 10 is the full result Figure For other experiments, we set
k by default.
Study of Graph Partitioning Algorithm. We select METIS Karypis & Kumar 1998 as the graph partitioning algorithm. In table 11 provide the ablation study for how many benefits
18

---

Under review as a conference paper at ICLR 2023
# Hop
GCN-MLP-Mixer
GatedGCN-ML
GINE-MLP-Mixer
GraphTrans-MLP-Miieer
0
0.2568 0.0034
0.2642 + 0.0037
0.2462 + 0.0018
0.2602 = 0.0085
0,1880 = 0.0067
0.1540 + 0.0046
0.1171 1 0.0029
0.1190 = 0.0016
ZINC
2
0,1780 = 0.0041
0.1468 = 0.0016
0.1046 + 0.0039
0.1126 = 0.0036
3
0,1820 z 0.0074
0.1443 + 0.0061
0.1009 + 0.0032
0.1072 # 0.0032
4
0.2022 0.0038
0.1473 + 0.0046
0.1072 + 0.0011
0.1174 = 0.0083
MolHIV
0
0.7736 = 0.0106
0.7706 + 0,0162
0.7636 + 0.0118
0.7684 = 0.0176
1
0.7788 0.0191
0.7772 = 0.0118
0.7711 + 0.0124
0.7805 # 0.0182
2
0.7885 0.0103
0.7668 0.0125
0.7797 0.0062
0.7665 = 0.0125
0.7716 0.0015
0.7586 # 0.0162
0.7734 + 0.0096
0.7425 = 0.0086
Table 10: Study of k-hop neighbour on ZINC and MolHIV, corresponding to Fig.
the METIS can provide against random graph partitioning. For random graph partition, nodes are randomly assigned to a pre-defined number of patches. For both METIS and random partition, re-generate graph patches at each epoch. Table TT shows that using METIS as the graph partition algorithm consistently gives better performance than random node partition, which corresponds to our intuition that nodes and edges composing patch should share similar semantic or information. Nevertheless, is interesting see that random graph partitioning still able to achieve reasonable results, which shows that the performance of the model is not solely supported by the quality of the patches.
ZINC
MolHIV
Model
METIS
Random
METIS
Random
GCN-MLP-Mixer+
0.1352 # 0.0056
0.1846 = 0.0042
0.7849 # 0.0043
0.7791 0,0252
0.1251 = 0.0080
0.1619 + 0.0071
0.7912 + 0.0133
0.7721 0.0117
GINE-MLA MLP-Mixer*
0.0794 = 0.0028
0.1057 # 0.0048
0.7844 + 0.0033
0.7676 : 0.0101
GraphTrans-Me
0,0831 # 0.0032
0.1166 = 0.0051
0.7823 + 0.0217
0.7772 + 0.0099
Table 11: Comparison of METIS random graph partitioning.
A.4 PATCH ENCODER
Baselines and GNN-based patch encoder, We use GCN (Kipf & Welling 2017). GatedGCN (Bres-)
son & Laurent 2017), GINE (Hu et al.) 2019) and Graph Transformer (Shi et al. 2020) directly, which also server as the patch encoder of Graph MLP-Mixer to see its general uplift effect. Hyper- parameter and model configuration are described Table 7 and Table g
GNN-free patch encoder. The GNN-free patch encoder reported in Table 2, is all-MLP archi- tecture. For each graph patches, we embed all node features (bag of nodes), all edge features (bag of edges), then average and readout, based exclusively MLPs.
ba, MLP3
MLP (h+) KEV,
Σ MLP2(e8)) Ei
A.5 DATA AUGMENTATION
Table 12 provides the full results of Table
A.6
MIXER LAYER
Twans--rrandeeeee In table 13 GNN-Trans Encoder is the model whose MLP-Mixer layers are replaced with the same number of standard transformer encoder layers. The rest architecture is the same.
19

---

Under review as a conference paper at ICLR 2023
ZINC
MolHTV
Model
DA
MAE
Time(s/epoch)
ROCAUC
Time(s/epoch)
X
0.1983 0.0026
5.6249
0.7765 # 0.0158
13,9986
GCN-MLP-Mixer
V
0,1880 0.0067
5,7604
0.7865 : 0.0130
14.5451
X
0.1625 0.0022
5.9534
0.7642 # 0.0188
16.5646
GatedGCN-MIL MEENN-MP-MxxXE
V
0.1565 0.0023
6.1519
0.7824 + 0.0062
16.9663
X
0.1266 0.0051
5.9216
0.7569 = 0.0281
14.8949
GINE-MLP-Min
/
0.1171 0.0029
5.9922
0.7824 = 0.0131
15.5889
X 0.1316 0.0043
6.3519 6,4986
0.7566 + 0.0260
16,8957
0.1 0.0016
0.7805 = 0.0182
17.2023
Table 12: Effect of data augmentation (DA): X means no DA and uses DA.
ZINC
MolHIV
Model
Graph MLP-Mixer*
Graph VIT
Graph MLP-Mixer
Graph VIT
GCN-
0.1352 0.0056
0.1743 0.0016
0.7849 0.0043
0,7580 0.0247
GatedGCN-
0.1251 + 0.0080
0.1546 = 0.0024
0.7912 i 0.0133
0,7707 4 0.0067
GINE-
0.0794 = 0.0028
0,1060 = 0.0014
0,7844 = 0.0033
0,7694 + 0.0158
GraphTrans-
0.0831 # 0.0032
0.1 = 0.0053
0.7823 0.0217
0,7750 # 0.0224
Table 13: Mixer Layer vs. Transformer Layer
A.7 STATE-OF-THE-A
For ZINC from Dwivedi et al. (2020), all models have approximately ~ 500k parameters. For MolHIV and MolPCBA, there is upper limit on the number of parameters. To enable a fair comparison, we set the batch size to 128 for ZINC and MolHIV, and 256 for MolPCBA for all the SOTA GT models and ours, and all experiments using the same machine.
For SUN (Frasca et al. 2022), due to the huge memory consumption, we use small batch size of 8 with gradient accumulation. Otherwise, any batch size larger than 8 will lead out of memory (OOM).
Modal
ZINC
MolEllV
MolPCBA
MAE
S/Epoch
ROCAUCT
Parum
S/Epoch
ROCAUCT
Param
S/Epoch
0:226
GaphiT
0.202 0.011
8.69
Graphommer
8.122 01006
105.
GPS
0.0025
156
0.0061
0.0043
6,067k
843.02
SAT
0.094 0.008
19.38
GraphTrans
0.2761 0.0029
4,223k
360
GNN AK+
0,080 0.001
8.67
0.7961 : 0.0119
414k
15.20
0.2920
0.0014
8,693k
366.01
0.084
0.0055
32.50
0.2616 0,0149
1776.96
GNN-MI ONN-MI---Mixe* (Oum)
0.0794 0.0028
5.88
0.7912 0.133
412k
14.82
0.2669 0,0022
2,971k
222.72
Table 14: Comparison of our best results from Table 2 with the state-of-the-art Models (missing values from literature are indicated with 1-)). For ZINC, all models have approximately 500k parameters.
A.8 EXPRESSIVITY
We experimentally validate that Graph MLP-Mixer is strictly more powerful than 3-WL by run- ning it the highly symmetric Cireulant Skip Link (CSL) dataset from Murphy et al. (019 and SR25 (Balcilar et al. 202T), which required GNNs to be strictly more expressive than the I-WL test and W-. respectively succeed, see Table
20

---

Under review as a conference paper at ICLR 2023
Pepiiee Fune
Peptide struct
Model
# Params
Arg. Precision 1
TimetS//pochhi
Memary (MB)
MAE
TimetS/ Egpoch)
Memory(MB)
0.30000.0023
3496+6000013
GINE
476k
151910000079
0.251720.00455
GaldGGCN
5091
0. 0.386410.0077
O 0.342010.001
GuIeGGCN
0.606691000055
0.23574000000
Transfonmer LapPE
488K
06626640:1126 26
0.252944200016
LapPE
493k
0.689641.0122
0.268340000043
SAN RWSE
5001
0.639H6000075
01254546.00012
GPS
504k
0.6562 0.0115
11.83
012515 + 0:00122
11:74
GNN-AR+
631k
0.6480 x 0.0089
22,5207
7,855
0.2736 0,0007
22. 22.1169
7,634
SUN
508k
0.6300 0.0078
376.6632
18,941
0.2198 0,0008
384.2098
17,215
GCN ML P-Mixest
447k
0.6736 + 0.0040
18:8352
338
0.2488 D.0012
16,0935
332
GansGGUN Miseer
595k
0.6790 0,0073
1946221
0,0013
16.5547
GINE-MI
497k
0.6846
19:5334
GraphTTrnss- P-Mixer"
645k
0.6814 + 0.0077
18.8322
519
0,343 + 0.0013
16.9987
513
ceptidesffnnc Table 15: Performance on Peptides func and Peptides struct Dwivedi et al.
2022
CSI.
SR25
Model
Accuracy 1
Accuracy 1
GCN-MLP-M
1.0000 = 0.0000
1.0000 = 0.0000
GatedGCN MEENN-MMP-MEE M
1.0000 = 0.0000
1,0000 + 0.0000
WANE-MP-MMieer
0,9800 = 0.0183
1.0000 + 0.0000
GraphTrans MLLIass--PP-AAAA MLP-Mixer*
1.0000 = 0.0000
1.0000 0.0000
Table 16: Results for the CSL
Murphy et al.
2019) dataset and SR25 (Balcilar et al. 2021 dataset.
A.9 GNN-MLP-MIXER
Like MLP-Mixer in Computer Vision, GNN-MLP-Mixer is sequential two-step process. The first step embeds the nodes contained in the graph patches with a MP-GNN and pools the node embed- ding together generate patch representation. The second step combines the patch representations with mixer layer. However, unlike the original MLP-Mixer meaningful node representations are difficult to produce due the high variability of graphs. To improve the expressiveness of GNN- MLP-Mixer, we propose an iterative two-step process by updating alternatively the representation of nodes and patches as follows.
First, the node and edge representations are updated with a MP-GNN applied to each graph patch Gp Ep) separately and independently:
hr
fn(hi, (hioli (((i), 8-1 e Sy ERC
h htt 12d,
(10)
4+1 fg.P
Sa Sa(h.pp (pp)
where f is the layer index, p is the patch index, i,j denotes the nodes, M((i) is the neighborhood of the node and functions fú. and Se (with learnable parameters) define the specific MP-GNN architecture.
Second, fixed-size vector representation of the patch Gp is produced by mean pooling all node vectors in the patch followed by a MLP:
Σ h 141 E
Rdd
"
(11)
H+1
MLP(: I+1 E Rd.
p
Third, the patches represented by X Mixer layer:
(of ...., ,..,, a 1+1]
R Pxd are processed with a ML.P-
U-+ xx+11 (W (W LayerNorm (aatormm(App)) (atnnNormmAhxi)) 1fx(-11))
Pxd
Token mixer,
(12)
y/+ = wi+ + (W!+1 o(W!+1 LayerNorm (nyerNormU!4t1)) ((+))T)) e Pxd
Channel mixer,
21

---

Under review as a conference paper at ICLR 2023
Finally, the node representations updated using both the outputs of the MP-GNN layer and the MLP-Mixer layer:
b M
W + + E Rdd,
h,t1 Mean
441 E ER"
iEG,) Lp
(13)
{p
1+1 M411 Rd
These node embeddings serve as the input of the next layer and the iterative process goes back to the first step above.
A.10 COMPLEXITY ANALYSIS
For each graph G = (V, (V, with = [ being the number of nodes and E = |8| being the number of edges, the METIS patch extraction takes OEE) runtime complexity, and outputs graph patches {GI,..., Gp). with P being the pre-defined number of patches. Accordingly, we denote each graph patch Gp = (vp. Ep), with N, |vpl being the number of nodes and E, = | being the number of edges in Gp- After our one-hop overlapping adjustment, the total number of nodes and edges of all the patches are (Ny = Ep N,,)) I 2.V and (Eg = Ep Ep)) S 2E, respectively. Assuming base GNN has OEE) runtime complexity, our patch embedding module has O(Ev) runtime complexity. For the Mixer Layer, the complexity is O(P).
A.11 OVER- -VUR-SQUASHING
We illustrate experimentally the over-fitting property that can be produced by over-squashing with the synthetic Teghhoigh dataset from (Alon & Yahav 2020) and real-world long-range dataset borrowed from (Dwivedi et al. (022)) in Figure and Table
For the synthetic TreeNeighbour dataset, we run the experiments with GCN, GGCN and Graph MLP-Mixer with the number of layers being the double size as the tree depth and hidden size of 128, and it can be observed that there is issue for the GNNs overfit this dataset. In (Alon & Yahav (2020), the authors use number of layers equal to the tree depth+1 I and small hidden size of 32, which does not provide enough learning capacity to the networks and thus under-fits the dataset.
1.00
1.00
1.00
1.00
1.00
1.00
1.00
0.90
0.80
0.70
0.60
Acc
0.50
GCN (train)
0.40
0.30
GGCN (train)
0.20
0.10
Graph MLPMixer (train)
0.00
3
4
r (the problem radius)
Figure 6: Train Accuracy across problem radius (tree depth) in the NEIGHBORSMATCH prob-
lem Alon & Yahav 2020).
We confirmed this observation with the real-world long-range graph dataset, peptide-fune taken from (Dwivedi et al. 2022) with mean value of 57 for the graph diameter of these large graphs. The same result occurs, the GCN, GGCN and Graph MLP-Mixer are able to over-fit fit the dataset at almost 100%.
Figure presents the generalization performance of GNNs on the TreeNeighbour dataset specifically designed to analyze synthetically the property of datasets with long-range dependencies.
22

---

Under review as a conference paper at ICLR 2023
Model
Training Accurary
GGCN GCN
0,9991
0,9993 Graph MLP-Mixer
0,9993
Table 17: Training Accuracy in the Peptides-fune problem (Dwivedi et al. 2022
- GCN (test)
0.9
0.8
GGCN (test)
0.7
Graph MI PMixer (test)
0.6
0.5
0.4
0.3
0.2
0.1
4
(the problem radius)
Figure 7: Test Accuracy across problem radius (tree depth) in the NEIGHBORSMATCH prob- lem (Alon Yahav 2020).
23


Reviews:
[{"review_id": "zOoEFPFCsP", "reviewer": "Reviewer_Fxzu", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper explores the MLP Mixer based approach on graph learning. It claims that the architecture can get rid of over-squashing or high complexity problem for long-range connections.", "summary_of_the_review": "It is an interesting exploration of the MLP mixer for graph learning and outperforms multiple existing works, but the experiments need to be improved.", "strength_and_weaknesses": "### Strengths\n1. The paper proposes to apply MLP mixer to graph learning.\n2. The authors introduce a method for extracting patches from the graph and adding positional information for the patch.\n3. The experimental results show that the graph MLP-mixer can improve the performance of the existing method.\n\n### Weaknesses\n1. The paper claims that the method can get rid of the over-squashing problem of the GNN model. It would be great to see the larger scale dataset with longer-range connections on the OGB dataset, such as OGBG-code2.\n2. The paper selects METIS as the graph partitioning algorithm to generate patches. It can be interesting to have the ablation study for how many benefits the METIS can provide against random partitioning.\n3. The Molpcba results in Table 5 do not seem very convincing, it would be better to see a fair comparison by having a similar number of parameters. \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "y2j44uiDpG", "reviewer": "Reviewer_jedP", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "While graph neural networks (GNNs) and graph transformers (GTs) have been popular for graph representation learning recently, they have their own limitations: \n* GNNs, especially those based on message passing, are poor at modelling long-range dependencies and\n* GTs suffer from quadratic computation complexity. \n\nThis paper adapts a specialised multi-layer perceptron (MLP) architecture, viz., MLP-Mixer, initially proposed in the image domain [1], to graph-structured data for modelling long-range interactions with linear computational cost.\n\n[1] MLP-Mixer: An all-MLP Architecture for Vision, In NeurIPS'21.\n\nExperiments on benchmark graph datasets demonstrate the effectiveness of the proposed method.\n\n___", "summary_of_the_review": "While the proposed method is potentially promising, more clarity and empirical evaluation are needed in support of the claims made in the paper.\n\n___\n\n\nUpdate:\nI have read all the reviews and their responses. I have raised my score from 5 to 6. ", "strength_and_weaknesses": "\\\n**Strengths**\n\n\\+ The paper is well-organised and Table 1 clearly lists key differences of MLP-mixer for images and the proposed adaptation for graphs.\n\n\\+ The proposed method can potentially address important limitations of both GNNs and GTs.\n\n\n\\\n**Weaknesses**  \n\n\\- The authors claim that GNNs suffering from oversquashing leads to overfitting while existing literature [2] has shown that it actually leads to underfitting.\n\n[2] On the Bottleneck of Graph Neural Networks and its Practical Implications, In ICLR'21.\n\n\\- The authors attribute the poor long-range modelling ability of very deep GNNs to oversquashing but the poor performance could be due to a combined effect of multiple factors (e.g., oversquashing, oversmoothing, vanishing gradients, etc.).\n\n\\- There are no experiments to support the claim that Graph MLP-Mixer can capture long-range interactions in graph datasets.\n\n___", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "nYd2aUHUn4", "reviewer": "Reviewer_BAFm", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a Graph MLP-Mixer model that generalizes the MLP-Mixer from images to graphs. Specifically, it first adopts graph clustering algorithms to split the graph into overlapping patches. And then different GNNs are utilized to get patch embeddings. To encode the positional information in graphs, Node PE and Patch PE are used.  Experimental results show the proposed method can outperform the base GNN encoder. ", "summary_of_the_review": "This paper proposes a Graph MLP-Mixer model that generalizes the MLP-Mixer from images to graphs. The technical details are reasonable. But the authors should demonstrate the superiority of the proposed method and why we should use the MLP-Mixer for the graph classification task. ", "strength_and_weaknesses": "Strength:\n- This paper generalizes MLP-Mixer from images to graphs and demonstrates the improvement in performance.\n- The designs of Graph MLP-Mixer are reasonable. And the authors show the differences between MLP-Mixer for images and graphs\n- This paper is well written and easy to follow. Detailed descriptions of the background are provided to make the paper more understandable.\n\nWeakness:\n- The contributions of this paper are limited. The authors simply move the MLP-mixer from CV domain to graph domain without explaining why this generalization is required for graphs.\n- The motivation of this paper is that GNNs suffer from over-squashing and poor long-range dependencies. But these two issues mainly occur in large graphs. For graph classification task, the graphs are usually small. Can the authors provide some experimental results to demonstrate these two problems?\n- The Positional Encoding and drop edges are  important for Graph MLP-mixer. How about just add these two component into the base models, such as GCN and GatedGCN?\n- The performance is not comparable to the state-of-the-art models, for example, GNN-AK[1] , Graph transformers and other models on  the OGB Leaderboards. Although the performance is not necessary to be very good, the authors should demonstrate the superiority of the Graph MLP-Mixer than other models. For MLP-Mixer in CV domain, it can achieve comparable performance with CNNs and ViT.\n\n[1] Zhao, Lingxiao, et al. \"From stars to subgraphs: Uplifting any GNN with local structure awareness.\" arXiv preprint arXiv:2110.03753 (2021).\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "LMNrR-zzIA", "reviewer": "Reviewer_oFvZ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Message passing-based GNNs suffer from over-squashing and poor long-range dependencies problems. \n\nGraph Transformers have been proposed because the global attention mechanism can alleviate the above problems.\n\nHowever, Graph Transformers have a computational complexity proportional to the square of the number of nodes, just like transformers in other fields.\n\nIn this paper, the authors propose an MLP-Mixer model for graph-structured data to overcome these issues.\n\nThe original MLP-Mixer, which is also unaffected by over-squashing and weak long-range dependencies, takes Multi-layer perceptrons (MLPs) in the place of the attention module.\n\nContrary to visual data, which has a grid structure, graphs have an irregular structure, so they use a clustering algorithm to extract the patches for MLP-Mixer.", "summary_of_the_review": "If the authors provide a clear novel point or analysis on this, I'll raise the score.", "strength_and_weaknesses": "pros:\n\n[+] The paper is well-written and organized.  Related works and the background concepts are described enough to understand the main idea of Graph MLP-Mixer.\n\n[+] The problem definition and the development process are quite logical and straightforward.\n\n\n---\n\ncons:\n\n[-] It would be nice if there were more analyzes or novel modules for graphs.\nIt seems like a simple extension of MLP-Mixer with a little bit classic graph clustering module.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject