Distinguished In Uniform: Self-Attention Vs. Virtual Nodes
Authors: Eran Rosenbluth
Jan Tönshoff
Martin Ritzert
Berke Kisin
Martin Grohe
Venue: ICLR 2024 poster (2024)
Keywords: Graph Neural Networks
Message Passing
Graph Transformers
Virtual Nodes
Expressivity
Uniform Expressivity
Primary area: learning theory
TL;DR: Graph Transformers and MPGNNs with virtual nodes do not subsume each other in terms of uniform function approximation while neither is "universal" in this setting.

Abstract: Graph Transformers (GTs) such as SAN and GPS are graph processing models that combine Message-Passing GNNs (MPGNNs) with global Self-Attention. They were shown to be universal function approximators, with two reservations: 1. The initial node features must be augmented with certain positional encodings. 2. The approximation is non-uniform: Graphs of different sizes may require a different approximating network.

We first clarify that this form of universality is not unique to GTs: Using the same positional encodings, also pure MPGNNs and even 2-layer MLPs are non-uniform universal approximators. We then consider uniform expressivity: The target function is to be approximated by a single network for graphs of all sizes. There, we compare GTs to the more efficient MPGNN + Virtual Node architecture. The essential difference between the two model definitions is in their global computation method: Self-Attention Vs Virtual Node. We prove that none of the models is a uniform-universal approximator, before proving our main result: Neither model’s uniform expressivity subsumes the other’s. We demonstrate the theory with experiments on synthetic data. We further augment our study with real-world datasets, observing mixed results which indicate no clear ranking in practice as well.

Published as a conference paper at ICLR 2024
DISTINGUISHED IN UNIFORM:
Vs. VIRTUAL NODES
Eran Rosenbluth"', Jan Tönshoff Martin Ritzert" Berke Kisin' & Martin Grohe RWTTH Aachen University, (rosenbluth, wow.soofffeeffooooooooooooo.o wwth-aachen.de
Göttingen, * Equal Contribution
ABSTRACT
Graph Transformers (GTs) such SAN and GPS are graph processing mod- els that combine Message- GNNs (MPGNNs) with global Self-Attention. They were shown to be universal function approximators, with two reservations:
1. The initial node features must be augmented with certain positional encodings.
2. The approximation is non-uniform: Graphs of different sizes may require a different approximating network. We first clarify that this form of universality is not unique to GTs: Using the same positional encodings, also pure MPGNNs and even 2-layer MLPs are non-uniform universal approximators. We then con- sider uniform expressivity: The target function is to be approximated by single network for graphs of all sizes. There we compare GTs to the more efficient MPGNN Virtual Node architecture. The essential difference between the two model definitions is in their global computation method - Self-Attentio Vs Vir- tual Node. We prove that none of the models is uniform-univert approximator, before proving our main result: Neither model's uniform expressivity subsumes the other's. We demonstrate the theory with experiments on synthetic data. We further augment our study with real-world datasets, observing mixed results which indicate no clear ranking in practice as well.
INTRODUCTION
In the field of graph learning, message-passingg GNNs have long been the undisputed model archi- tecture, even though its basic form is upper bounded in expressivity by the 1-dimensional Weisfeiler- Leman algorithm (Morris et al., 2020; Xu et al., 2019). Recently, transformer architectures, prevalent in language (Vaswani et al., 2017) and vision (Dosovitskiy et al., 2021), shook up the graph learning community (Dwivedi & Bresson, 2020; Rampášek et al., 2022). In a graph transformer, every node considered a token and then softmax attention applied between every pair tokens. This way, graph transformers sidestep the graph structure, enabling them exploit long-range interactions, well-known weakness MPGNNs. Within the message-passing framework, virtual nodes (VNs) represent alternative solution incorporate long-range interactions (Gilmer al., 2017). Under- standing the strengths and weaknesses of either approach remains an open problem and is the main focus of this work.
Shortly after the emergence of graph transformers, the expressiveness of such architectures became natural subject of study with early work by Kreuzer et al. (2021). Like most theoretical papers in graph machine learning (including e.g. Morris et al., 2020; Xu et al., 2019; Abboud et al., 2021), ) the analysis uses the non-uniform setting where the size and structure of the neural networks may depend on the size of the input graphs. Kreuzer et al. (2021) prove that graph transformers can approximate every function when provided with precomputed positional encodings such as LapPE (Dwivedi & Bresson, 2020). This makes graph transformers seemingly much more expressive than message- passing GNNs that are bounded by I-WL. We argue that is not the transformer architecture, but rather the combination of positional encoding and non-uniformity that enable universal function approximation and show that the same result holds for shallow MPGNNs and even MLPs. All three architectures are therefore equally expressive in non- mon-uniform setting when given sufficiently powerful PEs. We then proceed to compare the models in the uniform setting where a single network must work for graphs of all sizes. The justification for exploring the uniform setting is two-fold:

---

Published as a conference paper at ICLR 2024
1) From theoretical standpoint, uniform expressivity is significantly stronger notion.
2) Non-um Non-uniform expressivity only guarantees the existence of a model that works well for graphs up to fixed size, while uniform expressivity implies the existence of a model that generalizes to out-of-distribution graph-sizes.
We show that uniform universal approximation is impossible, both for GTs and MPGNN+VNs. We then focus on the differences between the architectures and show that neither can emulate the other, by providing functions that can be expressed by GTs but not by MPGNN+VNs and vice versa. These results focus on model architecture and hold regardless of whether positional encodings like LapPE are used or not. Our theory shows that due to softmax- average, graph transformers cannot uniformly solve tasks that require unbounded aggregation. In contrast, MPGNNs with virtual nodes that internally perform sum aggregation over all nodes can by definition sum over the nodes in graph. Based on this observation, we show that the function (V2 differentiates MPGNNs from GTs. Inversely, we show that a virtual node is not sufficient to emulate the intricate computation of self-attention uniformly, and provide function that GTs can express but MPGNNs with virtual nodes cannot. A fundamental difference between self-attention and VNs is that in self-attention the updating node can access each of the other nodes individually while with VNs it can only access their aggregated value. However, as proven by Grohe & Rosenbluth (2024), that difference alone does not imply an expressivity advantage. Proving that neither MP nor GT subsumes the other is the main technical contribution of this paper.
eventually being a weighted
We complement our theoretical findings with an empirical study on both synthetic and real-world datasets and observe that a unipervly-expresivve model can (sometimes) be learned, and uniform- inexpressive model does not generalize in terms of graph size. On real-world datasets, we observe mixed results when comparing MPGNNs+ VN and GTs, with neither architecture clearly outper- forming the other. This loosely aligns with our main result of both architectures being incomparable.
The paper is structured as follows: In Section 2 we introduce concepts that we work with in the following theoretical sections Section 3 and Section where we show the non-uniform and uniform expressivity results. Finally, in Section 5 we provide both the synthetic and real-world experiments.
1.1 RELATED WORK
We are not the first to explore the difference between graph transformers and message-passing GNNs with virtual nodes. Cai et al. (2023) prove that with only constant blowup in depth, MPGNN+VN can approximate linear GT's such as Performer. They also show that with constant number of very wide (i.e. O(n")) layers, MPGNN+VN can approximate full self-attention layer. Furthermore, they present an explicit construction using O(n) MPGNN+VN layers of constant width to simulate self-attention layer, albeit with strong assumptions on the node features. Our theoretical results are perpendicular to theirs. While Cai et al. (2023) aim to mimic one architecture with the other in the non-uniform setting, we analyze the architectures in the uniform setting. We note that their first result about linear graph transformers also holds in the uniform setting, implying that MPGNN+VN architectures subsume linear graph transformers.
Major works in function approximation of transformers are (Yun et al., 2020) for general transform- ers and (Kreuzer et al., 2021) for graph transformers. Both prove universal function approximation in a non-uniform setting. Kim et al. (2022) show that using (orthogonal) random node identifiers and encoding both nodes and edges as tokens, a standard transformer subsumes 2- WL and thus most pure MPGNN architectures. Note that MPGNNs with random node identifiers are universal approximators for probabilistic functions on graphs (Abboud et al., 2021).
There are few works that analyze expressiveness in the uniform setting. In Barceló et al. (2020) and Barceló et al. (2021) they characterize the expressive power of GNNs in terms of logic and in the second paper take homomorphism counts structural encodings into account. Rosenbluth et al. (2023) show that sum-aggregation GNNs do not subsume other aggregations in the uniform setting as opposed to the non-uniform setting where sum-aggregation GNNs can express anything a GNN can express. Morris et al. (2023) analyze the VC dimension of GNNs in the uniform setting. Other than that, essentially all theoretical papers (silently) assume the non-uniform setting.
In our theoretical analysis and on the synthetic data we compare MPGNNs to GPS (Rampášek et al., 2022) prototypical Graph Transformer that works well in practice. Many variations of Graph
2

---

Published as a conference paper at ICLR 2024
X
b)
X
Legend
MP
MP: Message Passing
MP
San
VN: Virtual Node
FF
Sunthen
SA: Self-Attention
SA
MP
FP:: Feodforward
FF
Swather
PH: Prediction Head
PH
PH
PH
PH
Figure I: a) A stack of MPGNN layers with skip connections b) GNN with a Virtual Node e) The Transformer architecture d) The GPS architecture as proposed by Rampášek et al. (2022)
Transformers have been proposed and refer to Müller al. (2023) for comprehensive overview. In our worldwrldd experiments, we extend the MPGNN architectures GCN (Kipf & Welling, 2017), GIN/GINE (Xu al., 2019; Hu al., 2020b), and GatedGCN (Bresson & Laurent, 2017) with virtual nodes. In addition to GPS, we compare to the graph transformers SAN (Kreuzer et al., 2021), LGI-GT (Yin & Zhong, 2023), and Exphormer (Shirzad et al., 2023).
2 PRELIMINARIES
By N, N Rn we denote the sets of nonnegative integers, positive integers, and real numbers, re- spectively. For N2 use the notation [n]] N N n). For a, b R2
use the notation (a, b] = (r R I r bj by Ja, bj. For vectors v = (vi,..., Pa) E Rd we let [e| == ma (sjja) That is, we use the & -norm as our standard vector norm. A (verte)) graph over feature domain 5d, for some set S and d N, is tuple G (V(G), E(G), Z(G)) consisting of a set of vertices V(G), a set E(G) S {(u, f} u, v E VGG) of (undirected) edges, and feature map Z()): V(G)- + St mapping vertices to vectors in Sd. For convenience, we sume that the vertices in V(G) are named 1..... [VG)]. Then, we may denote (t)) by Z()), and in general, for every mapping of the vertices f(G) we may denote f(G) by f(G), For vertex E V(G) we denote by N(v) == (w E (GG) (w, v) E E(G)) its neighborhood in G. Throughout the paper, A formal definition of the model can be found in Appendix A.I. For convenience, we will define some operations on a feature map (G) as matrix operations. When doing so we view the map as matrix by stacking all vertex features along the first dimension.
denote the ReI.U-activated Multi Layer Perceptron model by MIP.
Message Passing A message passing gadget MPG M (U, AGG) of dimension d consists of trainable MLP U with I/O dimensions 2d; d and a multiset-to aggregates d-dimensional vectors over I.. In this paper we only consider pointwise Sum, Mean, and Max aggregation functions they are the most common choices. The MPG computes function from a featured graph to new feature map:
aggregation function AGG that
M(G), U (Z(G) AGG((IZ(G)
No(c)))).
A skip connection follows the pattern X' = =((X) + X and empirically facilitates training deep networks. By wrapping an MPG into a skip connection, we get a message-pasiee passing layer MP which computes MP (G)), + Z(G)..
order to perform graph-level predictions. we use a readout gadget = (F, AGG) consisting of an MLP F with I/O dimensions d; and AGG aggregation above. The readout operation maps a feature map Z (G) a graph G a q-dimensional vector:
R(Z(G)) = F( AGG(([ : uEE V()))))
By combining multiple message-pussing passing layers and readout gadget, get Message- Passing Graph Neural Network (MPGNN) which is illustrated in Figure la. An MPGNN of dimen- sion pr d; g is tuple N (P, .,,..., Lx, R) where P is an initial MLP of I/O dimensions p;
MPGNN:
3

---

Published as a conference paper at ICLR 2024
(mapping initial features to d-dimensional vectors). Li...., Lx are k paassagg--ssingg layers of di- mension d, and R is a final readout gadget of dimensions d; q performing graph pooling and (graph- level) prediction. For an input graph G, we first apply to have G == (V) B(G), (G))) where P(Z(G) denotes the application of P in separate to each vertex's initial feature. Then, for each i E [A] we apply L; to have G = (V(G), E(G), L.(())-)))) Finally, apply R to have the final output of the network N(G) (()()()))
The concept of Virtual Node (VN) was suggested by Gilmer al. (2017) to allow for global information exchange in each layer of a GNN, matching the "intermediate global readout" from Barceló et al. (2020). Formally, a meessage-passing layer with VN (MP+V) of dimension is given MPV (MP, R) where MP is message-passing layer (a message- passing gadget wrapped in a xxip-connection of dimension and a readout gadget also of dimension d. The virtual node then effectively performs intermediate aggregation after round of message passing and adds the result to all nodes. Formally, MPV(G), = R MP(G)) + MP(G)e-
Virtual Node:
MPGNN VN: A message-passinng GNN with virtual node (MPGNN+VN) N = =P, Li,.... LR, R) is defined identically to an MPGNN with the only difference that the layers Li..... La are now MP+V layers that include a virtual node. We illustrate MPGNN+VNs in Figure 1b.
Transformer Layer;
An attention head H is function parameterized by three matrices Wo. WK. Wv E Rdxds, where d is the input dimension and d, is the hidden dimension. For an in- put matrix X E Rund (e.g. the matrix of node features in a graph) the function H Rad - Baxdd is defined as
(xXQQ)(XW)) XWV
((X) softmax
vdh
where the softmax function is applied row-wise. A self-attention module SA consists of k attention heads HI,..., H4 and a weight matrix Wo E kdd xd and computes the function
= =A(X)=[[((X))... (4,(X)...,,(())]]) (X)]
where [-] denotes row-wise concatenation. A Transformer layer TL FF) consists of a self- attention module SA and an MLP FF and applies to an input matrix X E Raad,
Y normi (X + +A(X)))
and
Z = norm2 (Y FF(Y),
where RRadd is the output matrix of the Transformer layer (of dimension d) and norm,, normg are optional normalization layers such as LayerNorm (Ba et al., 2016) or BatchNorm (loffe & Szegedy, 2015) and are applied after skip connections.
Graph Transformer: A Graph Transformer (GT) stacks Transformer layers to iteratively refine set embeddings of the vertices which is illustrated Figure Ic. Formally, a GT of dimension p, d, is tuple N- (P, Li..... Lg, R) similar to the other networks with the only difference being that all layers LI...., Lk are Transformer layers of dimension d.
GPS: A GPS Layer extends the Transformer layer by message passing module MP (Equation (1)) which is applied in parallel to the self-attention: Formally, a GPS layer I. = (SA, AP,, FF) of dimension d consists of a self-attention module SA and peessage-passingg layer MP both of dimen- sion and an MLP F with I/O dimensions d; d. It then computes (again in matrix notation):
Y 1 (X SA(X)) + norma (X + MP(X)) and
Z norms (Y + FF(Y))
Similar to the transformer layer, we transform the feature map Z(G of the input graph into matrix X and interpret the computed matrix Z as the resulting feature map.
Finally, a GPS network N = (P, LI........ Lg, R) of dimensions pt q is given similar to the other networks with the only difference that this time the layers LI..... Lb are all GPS layers. We illus- trate a GPS network in Figure 1d.
Positional Encodings Graph Transformers typically rely on positional or structural encodings (PE/SE) to inject information about graph structure. Rampášek et al. (2022) provide an overview over common PEs and SEs while new effective encodings are active field of research (Shiv & Quirk, 2019; Ngo et al., 2023). Formally, a positional encoding (G)) : V(G) + E is a special feature map assigning k-dimensional vector to each vertex in graph based on its local and/or
4

---

Published as a conference paper at ICLR 2024
global structure. In practice, PEs are precomputed before training and combined with the graph's original node features through concatenation or addition.
A common choice is LapPE which is based on the eigendecomposition (A) of the graph Lapla- cian, thus exploiting spectral graph features. In LapPE, the first m cigenvalues À and eigenvectors 2 accumulated through a learnable function ENC such as Transformer (in Kreuzer et al., 2021) or DeepSet (Zaheer et al., 2017) as used by Rampášek et al. (2022):
T(G ENC(E, u)
Let Ma.G = ([T(G, u) : v E B be the multiset of vectors that x assigns to the vertices of G. We say that n is injective up to isomorphism and order if for all graphs G, H of order at most it holds that:
G#H Ma,G + Mn.H.
That is, two graphs only map to the same multiset of vertex embeddings if they are isomorphic. It has been shown that LapPE as defined by Kreuzer al. (2021) has this property when considering the first n cigenvalues. We describe this positional encoding formally in the appendix and state why it is not equivariant. Note that the converse of Equation (3) is not required to hold as PEs, such as LapPE, are often not equivariant.
3 NON-UNIFORM FUNCTION APPROXIMATION ON GRAPHS
In this section, we present universality results that are more or less immediate consequences of MLPs being universal function approximators. Nevertheless, we believe that it is important to discuss these results to clarify that the universality stated in the graph transformer literature is not a unique property of transformers. This has also been briefly discussed by Müller et al. (2023).
Based on the the positional encoding LapPE being injective up to isomorphism and order n. Kreuzer et al. (2021) proved that there exists transformer network T that maps the positional encodings of graphs G, H of order at most to the same output if and only if G and H are isomorphic. This is a consequence of the injectivity of the positional encoding т combined with the universality of transformer networks (Yun et al., 2020). Having realized this, it is clear that the existence of a such an "isomorphism network" is not unique to transformer networks, but shared by other sufficiently powerful architectures including MPGNNs.
Proposition 3.1. 2-layer MLPs and I-layer MPGNNs are universal function approxinators when given access to positional encoding IT that is injective up to isomorphism and order n.
We give formal statements and proofs for both architectures in the appendix. As research on the expressiveness of GNNs has often focused on the power of GNNs to distinguish graphs, we note that universal function approximation and graph isomorphism testing have been shown to be equiv- alent (Chen et al., 2019). Thus, both 2-layer MLPs and l-layer MPGNNs with injective positional encodings are able to distinguish all pairs of graphs. This fact does not contradict the well known limitation of MPGNNs to be at most as powerful as the Weisfeiler-Leman algorithm for distinguish- ing graphs (Morris et al., 2019; Xu al., 2019). To the contrary, Corollary B.3 aligns with the fact that if the positional encoding is used as an initial coloring for each graph, then Weisfeiler-Leman distinguishes any two non-isomorphic graphs instantly after zero rounds of refinement. The caveat here is that the algorithm also distinguishes isomorphic graphs G, H whenever Mr,G + M2.H-
Note that the proofs for Proposition 3.1 as well as the proof of the universality of graph transformers (Kreuzer et al., 2021) share the same principle: Essentially they just implement giant look-up tables for finitely many inputs. Hence, they do not provide any deep insights into the relative strengths and weaknesses of Graph Transformers and MPGNNs.
4 UNIFORM EXPRESSIVITY OF GPS AND MPGNN+VNS
We begin with formally defining the terminology and notations related to expressivity.
Expressivity We denote the set of graphs featured over Sd by G5a, we define Gs UseN Gse, and denote the set of all featured graphs by G.. The special set of graphs featured over (1) is denoted
5

---

Published as a conference paper at ICLR 2024
G1- We denote the set of all feature maps that map S by 2ga, denote USeN Zςa by Zg, and we denote the set of all feature maps by Z.. A mapping f Gga - Z, from featured-grape to new feature maps is called a feature transformation.
Let p. E N. and a set S. Let - (f: f: + Z } be a set of feature transformations, and let h G5> Zgu be feature transformation. We say that F uniformly additively approximates h, denoted by F zs h, if and only
vA > 2 E F VG E 950 Vu EVG) (S()) ((G)
The essence of uniformity is that a single function "works" for graphs of all sizes, unlike non- uniform approximation which allows having different functions for graphs of different sizes, In this section, approximation always means uniform additive approximation and we use the term "ap- proximates" synonymously with expresses. The expressivity of model then is the set of functions approximable by a realization of that model.
Let F {f: f: G5p + Z be sets of feature transformations, we say that F subsumes H, notated F2 H and only if for every : GS- + ZR holds that H h + F x i.e. everything that can be approximated by functions in H can also be approximated by functions in F. the subsumption holds only for graphs featured with a subset TP C. SP we notate as F 2n H, if it does not hold already for graphs featured with a subset T C SP we notate it as F L H.
We call a mapping / GS= + I2, from featured graphs to g-tuples, a graph embedding. We use the approximation terms and notations defined above for feature transformations, for graph embeddings as well.
Prelude In the following subsections prove models' inability to uniformly express various func- tions. We show that the inexpressivity holds even when the models have reasonable PEs at their disposal e.g. LapPE and RWSE. Such PEs commonly used in practice and have the following properties: They are polynomial-time computable and their range is bounded. The former as- sumed in Theorem 4.1 and the latter in Theorem 4.3. Unlike in Section in the uniform setting injectiveness (of PEs) does not guarantee expressivity. Clearly, the proof logic based on memorizing all inputs is not applicable in an infinite input-domain setting. In addition, commonly used PEs like LapPE and RWSE are not injective for input graphs of unbounded size.
Note that throughout the section we consider a GPS model whose transformer modules incorporate neither BatchNorm nor LayerNorm (see preliminaries). BatchNorm does not increase GPS expres- sivity, and Layer-Norm would not help GPS in the tasks we define, hence, the lack of them does not affect our inexpressivity results concerning GPS.
The complete proofs of the lemmas and theorems in this section can found in Appendix C.
4.1 GPS AND MPGNN+ ARE NOT UNIVERSAL APPROXIMATORS
First, we prove that in the uniform setting, none of the models we consider is a universal approxi- mator.
Theorem 4.1. Let h be the characteristic function of an NP-hard problem on graphs, for example: h(G) 1 if is 3-colorable and h(G) 0 otherwise. Let Enc: G. - Z, a positional encoding function that is computable in polynomial time. Then, assuming PTIME + NPTIME we have that GPS * and MPGNN+VNG & even when the input graph is featured with positional encodings computed by Enc.
functiion Corollary 4.2. GPS and MPGNN+ VNs cannot approximate every computable function on graphs, not even every graph-function in NPTIME, even when the input graph is featured with PTIME- computable positional encodings.
4.2 GPS Do NOT SUBSUME MPGNN+
Next, we prove that there is target function that is expressible by certain MPGNN+VN and is not expressible by any GPS even when the input graphs to the GPS include bounded PEs.
Let Enc: Gh + Z1-1.1j be positional encoding function with bounded range [-1, for some E N. Define a parameterized, no edges, graph G... n E Nyn. featured with PEs according to Enc: V(G.)) = (wi,..-, vn); F.G..) = 0: Ve E ((G)) Z(G.) (v) = En)(G.)(v).

---

Published as a conference paper at ICLR 2024
Theorem 4.3. Let f 91 - R graph embedding such that every n it holds that f(G.. n Then, no GPS can approximate f for all graphs {Gn]. Formally, GPS ş
The proof's main argument is that for every GPS B, if the input graphs are of bounded degree and bounded features, then the output of B is bounded no matter the imput graph's 's size, unlike f fG, Combining Theorem 4.3 with the description of MPGNN+VN that computes f exactly, we arrive at our main conclusion.
Corollary 4.4. GPS L I VNs.
4.3 MPG Do NOT SUBSUME GPS
Lastly, we prove that there a target function that is expressible by a certain GPS and is inexpress- ible by any MPGNN+VN. We define parameterized, no edges, featured graph G1, Lr E N as follows: V(Gi,r = (u1, Mi w1...., Wtrr;; F(Gi,r) = 0; ((r,,) {mu,, (2, 1)) U {ww,, (2, 2e)
Note that all u, are identical and all wy are identical, hence we can omit the index when referring to vertex. Let an MPGNN+VN
(P, Bi..... Bm R) of dimensions pt d; q, where B; (M,, R,) is an MP+V. We first characterize the functions that B can compute for Gt.r-
Lemma 4.5. There exists a finite set of functions
{fi..... A R, such that:
m+1 i m+1 a Σ
1. V F(L,T)
Σ
Σ
1'1 (1+r)= for some real coefficients { (f) "Jay L.
{
1 1= y=0
2. WENWENTV [4| 3f.g e ; Z(G (w); = f((,r) and Z(G (w), = g(1, r).
3. VENW ENVj E lal 3f E F B(Gr.)) = f(1,r)
Next, we define a target function and characterize the gap that necessarily exists between it and any function of the kind described in Lemma 4.5 (1).
Lemma 4.6. For l Noo, E Nyo, define h(G1,)) 1( 3+2mm 2.2222122) asjay P' r (14r)= for some coefficients {ai,jay) then
(+relr)
Let f(l,r)
Σ
3ro
lim (S(,r) - -(G.)) 1ox
Combining Lemma 4.5 and Lemma 4.6, we have that the target function is inexpressible by any MPGNN+VN, For / E Noo, r E N define l(G.,r) = 1( 3+eree 3+222122) Itre" I+re
Theorem 4.7. No MPGNN+ VN can approximate for all graphs {Gt,r). Formally, MPGNN+ VNs & h.
However, this is not the case for GPS. Lemma 4.8. There exists GPS that computes h exactly.
Combining Theorem 4.7 and Lemma 4.8, we arrive at our main conclusion. Corollary 4.9. MPGNN+ VNs (1.2) GPS.
EXPERIMENTS
We perform kinds of experiments'. First, we empirically verify the difference between GPS and MPGNN-VN architectures using synthetic datasets based on Theorems 4.3 and 4.7. Even when an architecture can theoretically express a target function uniformly, based optimization can learn expressing model from data. To investigate this, synthetic experiments test a uniformly expressive architecture actually yields models with improved o.o.d. generalization to larger graph sizes after training.
not guaranteed that SGD-
"https:///oo hhte://////tbb.tteeeeee htttt..coomotttooooooo/////t///e

---

Published as a conference paper at ICLR 2024
G25
04
0.4
MAg03
0.1
10
30
20 30
32
280
(a) Test performance of MP and GPS when computing the square function.
(b) Test performance of MPGNN+VN and GPS when com- puting the function (Gr,,) from Section 4.3. The training data restricted to I E [1, 10), E [1, where is the num-
We report the relative error. The graphs in
the training data were restricted to [V] =
ber of type- vertices and (-r the number of type-2 vertices.
Figure 2: Synthetic experiments confirming the theoretical differences between models in practice
Second, we perform experiments on real-world datasets and show that neither architecture strictly outperforms the other overall. On some datasets, a simple virtual node is enough to achieve state- of-the-at performance when compared to graph transformers. While these experiments loosely related to our theoretical results, they offer another view leading to the general message: Neither GPS nor MPGNN+VN performs strictly better than the other across all learning tasks and broad range of architectures should generally be considered.
more
5.1 SYNTHETIC EXPERIMENTS
MPGNN+VN & GPS From Corollary 4.4 we know that the simple function where the value V has to be predicted as a graph-level regression target can be uniformly expressed by an MPGNN with VN but not by Graph Transformer. In order to verify this empirically, we designed dataset consisting of 100k random graphs with size 10 S [V] I 50. For testing, we use larger graphs of interested in the generalization behavior of the trained models. We train
size up to 200 MPGNN+V VN and GPS architectures that are identical width (256 hidden dimensions) and depth standard GCN layer (Kipf & Welling, 2017) message
(3 layers). For both models passing module. To the GPS model, we additionally provide LapPE encodings. Figure 2a shows the results the test data. MPGNN+VN has learned to perfectly predict the target function even for graphs outside the training distribution. GPS does achieve a low relative eтror for graphs with size at most 50. However, for sizes unseen during training the performance deteriorates rapidly. Thus, GPS was unable to learn function that generalizes across graph sizes which is in line with Corollary 4.4.
GPS & MPGNN+ To empirically study the converse scenario, we generate another synthetic dataset consisting of 100k random graphs Gt.r as defined in the beginning of Section 4.3 with the target function being the graph-level regression target h(Gi,, r) from Section 4.3. During training, restrict the data distribution to E [1, 10) and [1,5] and increase the range to I, E 50) for testing. Again, we train 3-layer MPGNN+VN and GPS models based on GCN layers of identical width. Figure 2b provides the experiment's 's results. For both models the MAE increases roughly linearly in both and r. The error the MPGNN+VN model increases around twice as quickly as that of the GPS model which generalizes better values of and outside the training distribution which aligns with Corollary 4.9.
Through the synthetic experiments, showed that the theoretical findings from Section 4 extend to practice. Especially in the first case, we observe that a simple function on the number of nodes of graph was not learned robustly by GPS but learned by the uniformly expressive MPGNN+VN architecture.
5.2 EXPERIMENTS ON BENCHMARK DATASETS
Finally, we compare MPGNN+ to Graph Transformers to contrast the two paradigms of global information exchange. For this, we evaluate MPGNN+VNG on real-world benchmark datasets from both the recent IRGB collection (Dwivedi et al., 2022) and OGB (Hu et al., 2020a). Concretely,
8

---

Published as a conference paper at ICLR 2024
Table 1: Performance measurements of VN-equipped models. First, second, and third best values are colored. indicates methods lacking feature normalization on the computer vision datasets.
METHOD
PASCALVOC-SP
COCO-SP F1
PEPTIDES FUNC TEST AP
SEPTIDES-TTUUC TEst MAE 1
OGB-CODE2
OGB- MOLPOML TEST AP
TEST F
TEst FL
MPONN
GCN
0,2078 0.003]
0.1338 1 0.0007
0,6560 0.0050
0.2460 a 0.0007
0.1507 1 0.0018
0.2483 a 0.0037
GINE/ GIN
0.2718 0. 0.004
0.2125 a 0.0009
0.6621 0.0067
0.2473 a 0.0017
0.1495 : 0.002
0.2703 a 0.0023
GATERGIN
0,3880 + 0 0040
0.2922 + 0.0018
0.6765 0.0047
0.2477 + D. 0.0009
0.1606 + 0.0015
0.3066 0.0013
SAN
0.3230 0.0039*
0.2592 0.01588*
0,6439 0.0075
0,2545 0. 0.0012
0.2765 0.0042
GPS
0.0055
0.6534 0.0091
0.2509 0.00014
0.1894 0.0024
0.2907 0.0028
LGI-GT
0.1948 a 0.0024
0.3040 0.0029
EXPHORMER
0.3975 a 0,0037
0.3455 & 0.00 0.0009
0,6527 & 0.0043
0.2481 #: 0.00007
GCN-VN
0.2950 O. 0.0058
0.2072 & 0.0043
0.6732 a D. 0.00166
0.2505 a 0.0022
GATEIGEN-VN
0,4477 a 0.0137
013244 à 0.0025
0.6823 0,0016
0.2475 e 0,0018
0.1855 a 0.0018
0,3141 a 0.0019
use the two graph-level peptides datasets peptides-fung and peptides-struct and the two node-level superpixel datasets Pascal- VOC and COCO from LRGB and the two graph-level datasets code2 and MolPCBA from OGB. Details on the datasets are given in the appendix. We note that on LRGB Tönshoff et al. (2023) very recently showed that the original baseline results reported by Dwivedi et al. (2022) and Rampášek et al. (2022) suffered from suboptimal hyperparameters and lack of feature normalization. We thus use their updated baseline results on LRGB.
Results Our results are provided in Table 1. We can see that on the peptides datasets, and especially peptides-struct, all models are very close and neither Graph Transformers nor MPGNNs with virtual nodes hold a significant edge over simple MPGNNs. On the superpixel datasets PascalVOC-SP and COCO-SP the performance of MPGNNs significantly strengthened by adding a virtual node. On PascalVOC-SP the GatedGCN+VN VN model is on par with GPS, indicating that the virtual node yields similar performance benefits as the self-attention in GPS which also relies on GatedGCN as its message passing module on this dataset. On COCO-SP the improvement of adding a VN to MPGNNs is also sigmificant, although not enough to fully close the gap to GPS. The results on ogbg-code2 similar and adding virtual nodes MPGNNS significantly boosts the performance to almost the level of the GTss, Last, we provide new results for GatedGCN on oghg-molpcha (with and without virtual nodes) and achieved state-of-the-an performance. Here, virtual nodes were able to further boost the already very good performance of GatedGCN by about 1% AP which is a highly significant gain over all other methods and even reaches the level of Graphormer (not shown) which was pretrained on additional data.
Overall, the comparison yields mixed results with neither Graph Transformers nor MPGNNs+VN clearly outperforming the other. This adds to our main theoretical results which state that nei- ther architecture subsumes the other in terms of uniform expressivity. Furthermore, MPGNNs+VN do yield the best results on some datasets, showing that virtual nodes can generally compete with self-attention as a means of global information exchange on real-world learning tasks while being significantly more efficient.
6 CONCLUSION
In the non-uniform setting we formally proved that strong positional encodings imply universality not only for GTs but also for MPGNNs and even MLPs. We thus looked into uniform approximation where a single model has to work for all graph sizes. There we proved that GT's and MPGNNs with virtual nodes express different sets of functions. The core observations were that GT's are unable to perform unbounded aggregation (e.g. counting the nodes) and on the other hand self-attention can compute functions that can not be expressed uniformly by the simple computation of virtual node. Through synthetic experiments, we showed that this difference also extends to practice. On real-world datasets from LRGB and OGB we observe that simple and efficient virtual nodes generally competitive with graph transformers. To paraphrase this with a popular saying; in graph learning, attention is often not all you need.
9

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
This work was supported by the German Research Foundation (DFG) under grants GR 1492/16-1 and KI 2348/1-1 "Quantitative Reasoning About Database Queries". This work funded by the Deutsche Forschungsgemeinscafff (DFG) 2236/2 (UnRAVeL).
REFERENCES
Ralph Abboud, ismail īlkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. In Proceedings of the Thirtieth Inter- national Joint Conference on Artificial Intelligence, IJCAI 2021, 2021. 1.2
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv preprint arXiv:1607.06450 2016. 4
Pablo Barceló, Egor V Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Quan-Pablo Silva. The logical expressiveness of graph neural networks. In 8th International Conference on Learning Representations (ICLR 2020), 2020. 2, 4
Pablo Barceló, Floris Geerts, Juan Reutter, and Maksimilian Ryschkov. Graph neural networks with local graph parameters. Advances in Neural Information Processing Systems. 34:25280-25293,
2021. 2
Xavier Bresson and Thomas Laurent. arXiv:1711.07553, 2017. 3
Residual
gated
graph
convnets.
arXiv preprint
Chen Cai, Truong Son Hy, Rose Yu, and Yusu Wang. On the connection between mpnn and graph transformer. arXiv preprint arXiv:2301.11955 2023. 2
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. Neural Information Processing Systems, 2019. URL https: / /api....../ www.mmiiicccooll...m.m wotg/CorppsII::1111eee....
George Cybenko. Approximation by superpositions of a sigmoidal function. Math. Control. Signals Syst, 2(4):303-314, 1989. 14
George Dasoulas, Ludovic Dos Santos, Kevin Scaman, and Aladin Virmaux. Coloring graph neu- ral networks for node disambiguation. Proceedings of the Twenty-Ninth International Joint Conference Artificial Intelligence, IJCAI 2020, pp.
2020. 14
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszko- reit, and Neil Houlsby. An image worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2021. 1
Vijay Prakash Dwivedi and Xavier Bresson. generalization of transformer networks to graphs.
arXiv preprint arXiv:2012.09699, 2020. 1
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 Learning Representations, 2021. 20
Vijay Prakash Dwivedi, Ladislav Rampášek, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. Advances in Neural Information Processing Systems, 35:22326-22340. 2022. 8, 20
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neu- ral message passing for quantum chemistry. In Proceedings of the Thirty-Fourth International Conference on Machine Learning (ICML), pp. 1263-1272, 2017. 1,
C. Godsil and G. Royle. Algebraic Graph Theory. Springer, 2001. 13
Martin Grohe and Eran Rosenbluth. Are targeted messages more effective?? 2024. 2
10

---

Published as a conference paper at ICLR 2024
Kurt Hornik. Approximation capabilities of multilayer feedforward networks. Neural Networks, (2):251-257, 1991. 14
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovee. Open graph benchmark: Datasets for machine learning on graphs. In Ad- vances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, 2020a. 8, 20
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitmik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. International Conference on Learning Representations, 2020b. 3
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference machine learning, pp. 448-456. pmlr, 2015.
Jinwoo Kim, Dat Nguyen, Sconwoo Min, Sungjun Cho, Moontac Lee, Honglak Lee, and Seunghoon Hong. Pure transformers are powerful graph learners. Advances in Neural Information Processing Systems, 1448--1459955 2022. 2
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference Learning Representations (ICLR), 2017. 3,8
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourncau, and Prudencio Tossou. Re- thinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 14:21618-21622 2021. 1, 3, 5, 13, 14
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and Leman go neural: Higher-order graph neural networks. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence (AAAI), pp. 4602- 4609, 2019. 5
Christopher Morris, Gaurav Rattan, and Petra Mutzel. Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings. Advances Neural Information Processing Systems, 33:21824 21840, 2020.
Christopher Morris, Floris Geerts, Jan Tönshoff, and Martin Grohe WL meet VC. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scar- lett (eds.), Proceedings of the International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 25275-25302. PMLR, 2023.
Luis Müller, Mikhail Galkin, Christopher Morris, and Ladislav Rampášek. Attending to Graph Transformers. arXiv e-prints, art. 041111, February 2023. doi: 10.48550/arxiw.2302. 04181. 5.5
Nhat Khang Ngo, Truong Son Hy, and Risi Kondor. Multiresolution graph transformers and wavelet positional encoding for learning long-range and hierarchical structures. The Journal of Chemical Physics, 159(3), 2023.
Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy WOlf, and Do- minique Beaini. Recipe for general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 15:140011, 2022. 1, 3, 4, 5, 9, 20
Eran Rosenbluth, Jan Toenshoff, and Martin Grohe. Some might say all you need is sum. arXiv preprint arXiv:2302. 1603, 2023. 2
Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica J Sutherland, and Ali Kemal Sinop. Exphormer: Sparse transformers for graphs. In International Conference on Machine Learning, 2023. 3
Vighnesh Shiv and Chris Quirk. Novel positional encodings to enable rree-based transformers. Advances in neural information processing systems, 32, 2019. 4

---

Published as a conference paper at ICLR 2024
Jan Tönshoff, Martin Ritzert, Eran Rosenbluth, and Martin Grohe. Where did the gap go? reassess- ing the long-range graph benchmark. arXiv preprint arXiv:2309.00337, 2023. 9, 20
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.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In Proceedings of the Seventh International Conference on Learning Representations (ICLR), 2019. 1, 3,5
Shuo Yin and Guoqiang Zhong. Lgi-gt: Graph transformers with local and global operators in- terleaving. In Edith Elkind (ed.), Proceedings of the Thirty-Second International Joint Con- ference Artificial Intelligence, IJCAI-23, pp. 4504 4512. International Joint Conferences 2244663/jcai.20233333
Artificial Intelligence Organization, 8 2023. doi:
URL https:
//doi. orogioorgg10 10. (aarg//...4963//// 20t../29933iice. het.:iaiaa../000011. 2023/5012 Main Track. 3
Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. Are transformers universal approximators of sequence-to-seqeene functions? In International Con- ference on Learning Representations, 2020. URL
www.:eeettooooooo forum?
wddByxRMONt 2.5
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander Smola. Deep sets. Advances in neural information processing systems, 30, 2017. 5
12

---

Published as a conference paper at ICLR 2024
A ADDITIONAL DEFINITIONS
A.1 MULTI LAYER PERCEPTRON
A ReLU-activated Multi Layer Perceptron (MLP) of I/O dimensions p; consisting of m layers, is
tuple M (W()) E IRd xp, ((a) E IR,,, ..... .R...... ((m) E R ((mm E IR9) for some interme- diate dimensions d1,..., dm- It determines a function from an input vector X E Rº to a vector Y E IR9):
M(X) ((m) + W(m) ReLU(b(m-)) + W(m-1)... ReLU(b() x))
where Re)U(x) = max(0, 2)). We consider the size of M to be the total size of its underlying matrices and biases vectors.
In this paper, we assume all MLPs to be ReLU activated. ReLU activated MLPs subsume every finitely-mant seeely-man-ppieee -pecces piecewise-lines activated MLP, thus the results of this paper hold true for all such MIPss Every Reltivvct MI.P is Lipschitz-contimuus. That is, there exists a minimal aM E R20 such that for every input and output coordinates (i, for every specific input arguments 11, ..... Ln. and for every 5 > 0, it holds that
(M .n)s M M Fi- 11 o..... xn)sl/6 am
We call oM the Lipschite-consttan of M.
A.2 POSITIONAL ENCODINGS
In the following we describe the positional encoding LapPE as defined by Kreuzer et al. (2021) formally. We then describe at the example of LapPE why PEs are in general not equivariant. Note that this lack of equivariance might be detrimental in graph learning as a difference in the PE does typically not imply that the graphs
isomorphic.
Example A.1 (Kreuzer al. (2021)). A standard positional encoding uses basis of eigenvectors of the Laplacian matrix. Let G E) be a graph, and let LG E I. VV be its Laplacian matrix. Recall that LG has the vertex degrees as diagonal entries and off-diagonal position + entry -1 if v. w are adjacent and entry 0 otherwise. LG is positive semi semi-definite and has nonnegative eigenvalues X1 S >2... >m. Let u1..... un be an orthonormal basis of corresponding eigenvec- tors. These vectors are indexed by vertices of G. that is, E RRV, and we let usu be the v-entry of u, We define positional encoding π Laa by
Lop (G, v) = (A1, Ul X2, U2v: Ana Unw)
(since A1 and u1 = 1, we can also omit the first two entries). This positional encoding injective up to isomorphism, because the graph G can be reconstructed from the eigenvectors and eigenvalues >3. To make this positional encoding practical, but still keep it injective, we can round the reals to about n digits for graphs of order
Note that æ Lop not only depends on G, but also on the choice of the vectors ui which not canonical even if we normalize the vectors, because the signs cannot be normalized and eigenspaces may have dimension greater than Formally, this means that the mapping म is not equivariant.
Note that as described in the paper, the non non-equivariance of LapPE in the example shows that the converse of the implication Equation (3) is not required to hold.
2It necessary to put the cigenvalues as well as the entries of the vectors in the positional encoding. Neither the eigenvalues alone nor the eigenvectors alone sufficient to make the encoding injective. For the former, just note that there well-known examples of nonisomorphic co-spectral graphs (see, e.g.. Godsil Royle, 2001, Section 8.1). the latter. be the graph with two vertices and no edges with Laplacian
LG 9) and H the graph with two vertices one edge with Laplacian L
1 )
The eigenvalues of Le are A₁ = X = 0. and the eigenvalues of LH are \₁ = 0, A2 = 2. However. for both graphs in 11/2211/V2 u2 (1/v2, -1v/2 is orthonormal basis of eigenvectors.
13

---

Published as a conference paper at ICLR 2024
B EXPRESSIVITY RESULTS IN THE NON-UNIFORM SETTING
For the remainder of this section, fix some n E N and let π be some positional encoding that is injective up isomorphism and order n, e.g. LapPE by Kreuzer al. (2021), see Example A. A.1 in the appendix.
As stated in the main paper, the universality proofs of graph transformers and other architectures in the non-uniform setting relies the universality of MIPs. The following proposition extracts the core of the argument. For an n-vertex graph G with vertices vi....,, Un, we let (G, (N1...., Vn)) be the vector of length nd obtained by stacking the positional encodings of all vertices.
Proposition B.1. Let be a positional encoding that is injective up to isomorphism and order n. Let f be an arbitrary function that maps graphs to R9. Then for every n Z and > there is 2-layer MLP N of input dimension nd and output dimension q such that for all graphs G of order and all enumerations u = (Ui,..., "al....,Uu, Un) of the vertices of G we have
(T(T(G, - f(G)) Se.
Proof. Let X be the set of all TG, v), where G a graph of order n and v (U1,.... .......... Un) enumeration of its vertices. Note that X is a finite and hence compact subset of IRnd, Let g R Ry continuous function such that for all E X it holds that g g(x) = f(x).
an
By the Universal Approximation Theorem (Cybenko, 1989; Hornik, 1991) for MLPs, there is a 2- layer MLP that approximates on the compact set with an additive error bounded by e. Then for every graph G' of order and every enumeration (V1,..., (n) of its vertices, we have
||N(=( - f(G)) ( [|
g(<(G,,))) S E.
The following proposition is closely related to (Dasoulas al., 2020) (though slightly different, because we do not rely unique node identifiers, but just use multisets of node labels). Let NG T) denote the result of the computation of an MPGNN N on with initial vertex states x(G, v).
Proposition B.2 (1-layer MPGNNs are "universal"",. Let æ be a positional encoding that is injective up to isomorphism and order n. Let f be an arbitrary function mapping graphs to Ra. Then for every E >> 0 there a graph-level MPGNN N with a single message passing layer and sum readout such that for all graphs G of order at most n we have
N[( m)) f[G)] SE.
The argument is similar to the one given in the proof of Proposition B. albeit slightly more com- plicated. The key difference that the information that is stored the node encoding must survive the readout step where sum over all nodes is computed. We thus need to first use another 2-layer MLP that maps the encoding to something that can be safely aggregated through summation with- out losing information. We can then use the universality of MI.Ps again to approximate the desired function.
Proof. Let n 2 and f == [log + 1. Let X be the set of all TG, r),, where G is graph of order n and V vertex of G. Then X is finite subset of Rd Suppose that Rd + RR be a continuous function with h(r,) = 2- for j = k,...,k, and let = .श By the Universal Approximation Theorem, there is 2-layer MLP N₁, that approximates h on the compact have
{ar [..,.....2 x. Let
set X with an additive error bounded by 8. Then for every graph G with vertex set vI...., Up we
No (T)) - EM(x(G, I nd kt-2
Next, h injectively map multisets M C X of size J0, 1]: let M be such multiset, and for every j E [Kt], let my S n be the multiplicity of x, in M. We let
(MM Σ
m22
14

---

Published as a conference paper at ICLR 2024
The mapping is injective, because for m I 2 and j S k holds that 2 1 m2 m2-
2-0-1) 1 Furthermore, for distinct multisets M, M' it holds that [HT(M) H(M)) 2 2 2-ké kt Ob-
serve that for every graph of order n, Mr.G S is multiset of order at most n. If 01,-...: Un an enumeration of the vertex set of G, we have H (Mx
h(T(G, Thus
Σ (a(T(G, H(M,,)) 2
Let Y be the set of all (M²,G). where G is a graph of order n. Then Y S R is finite set, and for distinct y. o Y holds that ly - y/1 2 2-kt, kt, Let Z be the set of all 2 E such that la - yl S 2 kt-2 for some Y. Then Z is compact set, and for every 2 E Z there is a unique graph G2 of order n such that |= H.M ) 2-k(-2
Let g R + RS be a continuous function such that for all 2 E Z holds that g(z) - f(G.). J. By the Universal Approximation Theorem, there is 2-layer MLP Ng that approximates g on the compact set Z with an additive error bounded by E. Then for all graphs G with vertices U1...., Un we have
N Σ (T(((GG f(G) S..
To see this, let = Ei= N₁ (= uz). Then | H(M,,o)) S 2-2 Thus G² = G and hence [2) -(=) -
- [(G) s.
remains to implement the function (G, + No (Ei No (T(G, u;])) by a I-layer MPGNN. The message passing layer simply maps the state (xv) of node to N₂ (a(r)), ignoring the messages the node receives from its neighbors. Then global aggregation yields > ii= (=()))) The readout function is Ng. Thus, if the initial state æ(v) is π (G, v), then this MPGNN computes the desired function.
The following corollary formalizes that MPGNNs with injective PEs are able to distinguish all pairs of graphs discussed in the main paper.
Corollary B.3. Let be positional encoding that is injective up isomorphism and order n. There exists a graph-level MPGNN N with a single message passing layer and sum readout that
maps the encodings of two graphs G, Hl of order at most n to the same output if and only if G and H are isomorphic:
=(G,=)=N(H) GE
As also discussed in the paper, this does not contradict the fact that MPGNNs are bounded by 1-WL as the additional features also strengthen 1-WL to the point that 1-WL also distinguishes all pairs of graphs (and actually also isomorphic graphs for which the PE is not equivariant and the embeddings thus differ).
C UNIFORM EXPRESSIVITY, PROOFS
Note that throughout the section we consider a GPS model whose transformer modules incorporate neither BatchNorm nor LayerNorm (see preliminaries). BatchNorm does not increase GPS expres- sivity, and Layer-Norm would not help GPS in the tasks we define, hence, the lack of them does not affect our inexpressivity results.
Theorem 4.1. Let h be the characteristic function of NP-hard problem on graphs, for example: h(G) = 1 if G is 3-colorable and h(G) = O otherwise. Let Enc: G. + Z, a positional encoding function that is computable in polynomial time. Then, assuming PTIME + NPTIME we have that GPS & h and MPGNN+ VNs & even when the imput graph is featured with positional encodings computed by Enc.
Proof. Note that in the uniform setting having one network to handle graphs of all sizes the algorithm implied by any (GPS or MPGNN+VN) network has a runtime polynomial in the size of the input graph. Assume to the contrary that there exists (GPS or MPGNN+VN) network N that
15

---

Published as a conference paper at ICLR 2024
approximates hG)) every input graph G featured with Enc(G) positional encoding. Then, it is possible to approximate h(G) in polynomial time: Compute Enc(G) (G) in polynomial time and run N on G featured with Enc(G). This is in contradiction to h being NP-hard and the assumption that PTIME o NPTIME.
FF be p-dimensional GPS layer such that A (Wa: WK. Wv, Wo) is a (og::)--immessone attention module (for some q). M = (H, AGG) p-dimensional MPG with AGG {mean, sum, max), and F is a p. p-ddimnnnsional MI.. Then, if the features and the graph degree are bounded, then so are the values of the output feature map. Formally, for every b R,d N there exists b' E R. such that: For every imput [|G]].j E [p]) S b, it holds that
Lemma C.I. Let L
graph G of degree at most d and for which max))A()) [ E (pl) R.
Proof. 1) The linear transformation defined by W is Lipschitz-continuuus and so the bounded input features determine bounded range for the value vectors coordinates. By definition of the attention mechanism, the output of A is no higher than the maximum over the value vectors. Hence, there exists 9'Λ such that max))A(Z(C))))
[[G]]. [r]) S 6'A
2) An MLP is Lipschitz-continuuu hence for AGG E {mean, max} we have A to be Lipschitz- continuous, and for bounded degree input graph we have also for AGG sum that M is Lipschitz-continuuus
3) The addition and composition of musschitz-continnnn functions is Lipschitz-come continuuss and so for graph-domain that is both degree-bounded bounded and bouludd we have that A is bounded. 0
Theorem 4.3. Let f 91 + I a graph embedding such that for every n it holds that f(Gn) n². Then, no GPS can approximate f for all graphs {G.). Formally, GPS of f.
Proof. Let GPS B = (P, BI,..... Bm: R) of dimension p; d; where R (FR, AGGR). The degree of any Gn is bounded (to be zero), the features are bounded, and since P is Lipschitz- continuous also P(Z(G)) (denoting the application of in separate each vertex's initial feature) is bounded. Hence, by Lemma C.I we have that (G) is bounded. By induction, using Lemma C.I, have that the output of every layer B, is bounded, denote the bound on the output of B,, by bm- Finally, R is Lipschitz-continnonn {mean, max, sum} we have that B is bounded by n(p- bm d aR). Then, given 8 > 0, we set (8 p bm d annnn" + 1) and get
denote its Lipschitz-constant by an, then for AGGa E
If(G.) - (G..)) n(n p pb d-) 2 n(5 11) 8
Corollary 4.4. GPS L 1.I VNs.
Proof. By Theorem 4.3 no GPS+(bounded)PEs can approximate f. It is not difficult to verify that MPGNN+VV with one MPG+V with a sum-readout gadget, and a final sum-readout, can compute f exactly.
(P.(() Lemma C.2. Let a p; d-q-immensioaa MLP M = (W(I E Rdd xp b()) E Rd....., W(m) e
Raxdm-1, (fm) E R²). that is, for every input vector X = (II,..., E H² it holds that M(X) = ((m) + W(m) Re RU + W(m-1).. (b(U(b() + w()) Then, regardless of the imput, every output of M is one of finitely many affine functions. Formally, there exists a finite set F= = (fk of affine functions f; Rp + R, f(X)= = G; + 3=1
(a) such that:
E EF M(X); f(X)
Proof. By induction on the number of layers of M. For t = 1 we have that ei- ther (b w 0 ReIU w())) = u..) + ( x, hence the set F = (0, (1 + w x),.., .),...,(0 w x)) satisfies the requirement.
16

---

Published as a conference paper at ICLR 2024
Assuming correctness for t = 1, we prove for t Let F(n-1) be the function-set that
satisfies the lemma up to layer n - 1. Let Y E Rdn be the output of layer n 1, we have
that either (b( + y) = or ReLU (b(n) + w(r)y); bj + 5.. w Y, and by assumption 67th) + W (1)) Y ( + w/ (x) ................................ Id. (X)) for some 9i F(x-1), Hence, ReLU (b(m) + Wr()); E {0) U(b)))) + w. (9) (X), ..... 9a-1 (x)) 9: F(a-1)), J. and since linear combination of affine functions is an affine function the latter is a finite set of affine functions of X.
R, such that: Lemma 4.5. There exists a finite set of functions F (fi......JA ..).. :
1. VffE F f((,r) = m+1 m+1
(-,)=EE1 ΣΣΣD E "'
1'10 pat
(1tr)= for some real coefficients (
2. W N Vr ENj [d] 3f.g e F: Z(G (m) (u)) f(1,r) and Z(G(T)) (w), g(.,r).
3. WEN ENV E (a] 3ʃ E F: B(G,,)) f(L,)
Proof. Given & E im], i E [1 E [6r], we define shorthand notations for the values of any of the u, and w. after the th MPG+V:
(1) Z(C [1] Ur
= (wo() E [tr]
By induction on the layer of the MPGNN+VN:
a) For t 0, the preparation gadget is MLP, and so its output is one of finitely many affine functions of the initial vertex values wi,r (
(0)
b) Assume correctness for / = n - 1, we prove for L = n. Let an MPG+V B, = (Mn, Rn)) where
Mn (Un, AGG,, is an MPG and R2 = (Fn, RO,) is a readout gadget.
b. Since there are no edges, AGG,, (n-1)) = 0, and so Mn. (Gr,,,, = Un(ui (1
By the induction assumption Un (uir (m-1)) = (11 ...,, (9,r),,,,,,,,,,,))) where gi E for
some finite set F of functions of the form f(l,r) ΣΣΣΣ> anjeyt 1'd Ty (1+r)= By (g(1,)) is one of finitely many affine functions of (g) (f)...., .q) and so overall there is finite set
=
Lemma C.2, for every sequence (gi....,gh) 9n) E Fj E [g] Un(gi
F' of functions of the form f(Lr) Σ Σ Σ
aiaa P'' ([4t)) such that Vj
(f)
i 100000000
[q] (GI,, or () E F". Similarly, Mn ( 1) E F" for some finite F" of functions of the same form.
b.2 If ROn = sutn then (M = Fall(Ma (n-1)) (n-1))
.ir
+
frr wir (n-1)))). r M,(GGln
w (n-1)))) = By (b.l), Fa(l(Mn(G ((n-1) (1-1)) + where 9b E F for some fi- nite set F of functions of the form [(1rr) = a+1
by ui
MM, (G (((m-1)
z Σ Ciiing Prt -=
Σ
f= x= y=0
By Lemma C.2 then, using line of proof similar to (b. we have that Vj E (4) FnM (G( , (((--)) + rM, many possible functions of the aforementioned form.
r,, (G(n-1) ,0i, -.000a11 ( is one of finitely
(Ma.G .off "of (rM ()-) "u -o(o-"1))
b.3 If RO; = avg then Ra (M (G(p- = Fa
1(1+))
F, Ma(G w/. (--1)) Drr - ,, (n-1))
Using a line of proof similar to (b.2), we have
17

---

Published as a conference paper at ICLR 2024
that vj E [q] Fn( M. 1) w/ 1) 4r 10 1m/0 ))
; is one of finitely many possible
1+r
a+1
functions of the form f(1,r) Σ Σ
Σ
E oi.ja
Pr r
(14r)*.
j k
c) For the final readout R, whether R = sum or R = avg. by the induction assumption and using
a line of proof similar to (b.3), we have that bj E [r] R(G(m)) is one of finitely many possible
m i m+1 x
functions of the form
Σ Ois.z P' rd
(Itr)=
Lemma 4.6. For 1 N30,7 Noo. define h(Gr,r) 1( (222re
342re 12
"treel)
m+1 m+1
Let f()r) = Σ Σ Σ
aiy.yy l''s r (14rjz for some coefficients {aijawy) then
i=Ul
Bro Vr lim [f(,)) - h(G),))
Proof. 1. If there is i 1 such that dijay.
0 for some j. y, then clearly
lim (l, - h(G 0o for every r, and same if there exist no i > 0 and j, x, y for which
aigiayy O. This is because the function h(G1,)) is linear in I.
Otherwise, we can assume that
m++1
f(,r) = ΣΣΣΣ
(1+
1=0 1= x=0 y=
Define
f( =
00.0.a.M )r
(1 (1+r)at f2(1,))
r
anjay
1
r1+
10=0 y=
j=0 2=0 y=0
Then, we have that f(1,r) = =(fi(1,r) + r)) and
((0,))-(G,,)) h(G,,)) f((,.) + fe(l,r) 3 + 2re
(- +r
3 + 2re
re
1 re
Note that lim fi (t.r) = 0; fo is independent of and since f2, r + (3t2ee" + r 3+2re
Itre
14re
are distinct rational functions of they can only coincide at finitely many values of r. Hence, Bro Vr > ro limy [f(4, r), h(GG,)))) co.
Theorem 4.7. No MPGNN+ VN can approximate h for all graphs (Grr). Formally, MPGNN+VN VNs
h.
Proof. By Lemma 4.5 have that no matter the l,r, B(G,,) is neces- sarily one of finitely many functions (fi...., ft] such that, by Lemma 4.6, A E [b] Ar,
A d r > max(r: : [k]) lom ((rr)) - B(G,,)) = 00.
limp [fi(Gr))) h(Grr)
Hence,
Lemma 4.8. There exists a GPS that computes h exactly.
Proof. Define an attention head Il (WK, Wo, Wv) as follows:
We = ((1, 1))
Wx ((2)3))
Wv ((2, -1))
18

---

Published as a conference paper at ICLR 2024
We have that
Sot softmax
21 21
30...30)
40 40...40) (3.... 2...
28 28
3+2re T 1trel2
3+2re"
3+2re
3+2re Itrelt
14re
14re"
That is.
13e + 10
3c + 2re
3 2re
(uu)s
2e + tre
221 + re
1 + re re
13e + +r22440
38 + 20e
3 + 2re 12
Hww)r = 18 + Ire
28
+ 4e
1 re 12
It is not difficult to verify that there is GPS B comprising attention H and a final sum readout, 34
such that B(G (w),, +r)()) = 1(
3+2re
T-res
= "+re"r)= -((r))).
Corollary 499. MPGNN+VNS 20.2 GPS.
Proof. By Theorem 4.7 MPGNN+VN approximate h, and by Lemma 4.8 there exists GPS that computes h exactly.
19

---

Published as a conference paper at ICLR 2024
Table 2: Hyperparameters for GatedGCN+VN.
PascalVOC-SP
COCO-SP
Peptides-Fumi Fune
Peptides-Struct
oghg-code2
oghg-molpcha
0.001
0.001
0.001
0.001
0.001
0.001
dropout
0.1
0.1
0.1
0.3
0,4
Players
10
10
hidden dim.
70
256
1024
head depth
2
PE/SE
none
none
RWSE
LapPE
none
RWSE
VN pooling
mean
mean
mean
mean
mean
sum
batch size
50
200
200
32
512
#epochs
200
250
250
60
#Param.
478K
453K
486K
466K
1.20M
57M
time/epoch
668
206s
24s
28s
502s
487s
Table 3: Hyperparameters for GCN+VN.
PascalVOC-SP
COCO-SP
Peptides-
Peptides-Struce
Ir
0.001
0.001
0.001
0.001
dropout
0.2
0.1
#layers
8
10
10
hidden dim.
105
95
95
105
head depth
2
2
PE/SE
none
none
RWSE
LapPE:
VN pooling
mcan
mean
meun
batch size
50
50
200
200
#epochs
200
200
250
250
#Param.
460k
465k
487k
474k
time/epuch
35s
156s
18s
19s
D EXPERIMENT DETAILS
D.1 DATASETS
The LRGB dataset collection (Dwivedi et al., 2022) has recently been introduced as a set bench- marks that rely long-range interactions and are thus especially well-suited to benchmark chitectures that can handle long-range interactions such as graph transformers. Here, we use LRGB datasets: peptides-func and peptides-struc, which graph-level classification and regres- sion tasks, respectively, as well as the two vision datasets Pascal- VOC and COCO, which both model semantic segmentation on images as node classification tasks on superpixel graphs. Very recently, Tönshoff et al. (2023) showed that the original baseline results reported by Dwivedi et al. (2022) and Rampákek al. (2022) suffered from suboptimal hyperparameters and lack of feature normalization. We will use their updated baseline values in our experiments.
Additionally, we incorporate two graph-level datasets from the OGB project (Hu et al., 2020a): ogbg-code2 aims to predict the name of python methods presented abstract syntax trees. The molecular dataset ogbg-molpcha aims to regress the activity of molecules for 128 bioassays.
D.2 HYPERPARAMETERS
For our experiments on LRGB we adopted the hyperparameter ranges and tuning methodology from Tönshoff et al. (2023) and strictly adhere the the parameter budget of 500K. For the OGB datasets we train larger models as no official parameter budgets are given. Note that we view the usage of positional or structural encodings as a hyperparameter that is either chosen as LapPE (Rampášek et al., 2022), RWSE Dwivedi et al. (2021) or "none". On ggbg-molpcba in particular the usage of RWSE has a significant positive effect on performance. Table and Table 3 provide the chosen final hyperparameters and runtimes per epoch for GatedGCN and GCN, respectively. Note that in the final runs we average the results over 4 random seeds for LRGB datasets and over random seeds for OGB datasets.
20

---

Published as a conference paper at ICLR 2024
D.3 SYNTHETIC DATA GENERATION
For our synthetic experiments we use random Erdós-Rényi graphs with a mean degree samples uniformly from the interval [1, Note that we also use this graph distribution generate the graphs Gt,, from Section 4.3 even though the formal definition specifies an empty edge set. This does not affect the theoretical ability of GPS express the target function h(G,,r) but it does allow us to test if the model can learn to ignore the edges in a data driven manner. For both experiments, we train on I 100K randomly generated graphs and test on the parameter ranges specified in Section 5.
21


Reviews:
[{"review_id": "wZZM28EbuX", "reviewer": "Reviewer_Uru7", "summary": "This paper compares model expressivity between graph transformers (GT) and massage passing GNNs with virtual nodes (MPGNN+VN). The authors theoretically demonstrate that GT and MPGNN+VN are universal function approximators on the graph under uniform setups, where different neural networks can be utilized for every graph size. However, under the non-uniform case where one neural network is supposed to work for all the graphs, both are not universal approximators and express different sets of functions, indicating they do not subsume each other. The authors also conduct numerical experiments to validate the theoretical findings.", "questions": "The questions are mainly related to the “weakness”:\n(1)\tPlease add a list of math symbols and abbreviations in the appendix and clarify the above writing questions.\n(2)\tDoes the theory also satisfy different graph learning tasks?\n(3)\tHow can we utilize theory to understand the results of section 5.2?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "First of all, thank the authors for their submission to ICLR. This paper offers valuable insights into the expressive power of graph neural networks. Specifically, it exhibits the following notable strengths:\n(1)\tThe authors provide a novel and insightful comparison between Graph Transformer and MP-GNN (with VN) in both non-uniform and uniform setups. The latter setup, in particular, marks the first time it has been explored from this perspective, revealing that GT and MPGNN-VN do not subsume each other.\n(2)\tThe paper includes numerical experiments that complement the theoretical insights. The authors also attach the code, which will benefit the community. \n(3)\tLast but not least, the paper is well organized, and the writing is straightforward, so it is easy to follow even though the underlying proof is remarkable.", "weaknesses": "Despite the strengths listed above, there are still areas in the paper where improvements can be made to enhance clarity and overall significance.\n(1)\tRegarding the writing: \na.\tThe paper utilizes many acronyms, which may necessitate repeated explanations. For instance, in Figure 1, it would be helpful if the author could reiterate the meanings of \"MP,\" \"VN,\" “SA,” “PH,” and \"FF\" in the figure caption. Additionally, in Figure 2(b), clarifying the definitions of \"l\" and \"r\" would enhance writing clarity. It is also recommended that the authors create a table in the appendix with all the acronyms. \nb.\tThe utilization of some math symbols may confuse and misleading. For example, in subsection 4.3, the “lr” represents “l*r” instead of learning rate or number of layers. \nc.\tThere are some missing values in Table 1, which may be better to illustrate the reason in the table caption in addition to the other place. \nd.\tSome minor typos and grammars, such as “Based on the the positional encoding LapPE”.\n(2)\tRegarding the theory and numerical experiments:\na.\tThe assumptions and limitations of the proposed theory are somewhat unclear. For instance, it is not clearly defined whether the theory is applicable to various graph tasks or solely focused on graph classification tasks.\nb.\tThe message conveyed in Section 5.2 is also vague and disconnects with previous sections. Given that Table 1 indicates that the best performance appears somewhat random, it is not convincing how the theoretical insights can guide the practice. It may be valuable to conduct a more thorough investigation into the utilization of theoretical insights for model selection based on the characteristics of the dataset.", "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": "", "extra_scores": {}}, {"review_id": "cCyLBEc8fo", "reviewer": "Reviewer_BMpU", "summary": "This paper comprehensively compares the expressivity of Graph Transformers and Message-Passing GNNs. \n\nThis paper presents the following conclusions:\n\n1) Neither Graph Transformers nor Message-Passing GNNs are universal in the uniform setting. \n\n2) There are functions that Graph Transformers can express while Message-Passing GNNs with virtual nodes can not.\n\n3) Even with perfect positional encoding, the expressiveness of Graph Transformers and MPGNNs with virtual nodes differs substantially. \n\nThis paper conducts experiments on real data and synthetic data to verify the theoretical analysis proposed in the paper.\n\n---- After rebuttal---\nThanks for the authors' response. My main concern is strong assumption of the uniform setting and the experimental results.\n \nFor the strong assumption of the uniform setting, the author explained that\n﻿the uniform setting is a good representation of scenarios because the graph sizes at\ntraining time are smaller than the graph sizes during inference. I generally agree with the author's response.\n \nFor the novelty. The author reclaimed their novelty, which is not summarized (or even mentioned) in the introduction. Now, the author summarize this paper's novelty about the theoretical provements and the proposed synthetic data. I agree these two thing are new. However, the experimental results on real data still exists. The authors can carefully fix the minor mistakes or typos in their revised version.\n \nGiven the promise that the author will add the detailed proof and more analysis on the real dataset, I raise the score from reject to broadline accept.", "questions": "N/A", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1) This paper relates two common designs in graphs, i.e., graph transformer and message-passing GNN. \n\n2) This paper gives a theoretical analysis of the capabilities\tof two basic GNN designs and conducts comprehensive experiments to verify the theoretical analysis.\n\n3) The study provides insightful results that add depth to our understanding of the expressiveness of Graph Transformers and MPGNNs in scenarios with optimal positional encoding.\n\n4) The differentiation in the capabilities of Graph Transformers and MPGNNs is well highlighted, offering clarity on their respective strengths and limitations.", "weaknesses": "The important concern is the writing. Although this is primarily a theoretical paper, it does not express its flow of proof clearly. I recommend the author to improve their writing.\n\n1) The most important weakness of this paper is writing. The introduction is not easy to understand.\n\n2）**Lack of Justification**: The paper focuses on scenarios where positional encoding is injective. However, there is a noticeable lack of justification for why this particular scenario is important or realistic. To ensure that the results derived hold value in practical applications, it is essential to provide a clear context and relevance for the chosen scenario.\n\n3) The process of proof is not so clear. For example, in Section 4.2, the author attempts to prove GPS do not subsume MPGNN+VNs. However, I can not understand the main path of proof of Theorem 4.3 and Corollary 4.4.\n\n4) The strong assumption of uniform setting made in the paper may not align with the practical case.\n\n5) **Redundancy in Experimental Results**: Similar experimental outcomes have been presented in multiple prior works, notably:\n    - Tönshoff, Jan, et al. \"Where did the gap go? Reassessing the long-range graph benchmark.\" arXiv preprint arXiv:2309.00367 (2023).\n    - Cai, Chen, et al. \"On the connection between MPNN and graph transformer.\" arXiv preprint arXiv:2301.11956 (2023).\n   While building upon prior work is a hallmark of research progression, it's crucial to ensure that the presented findings either provide a novel perspective or build significantly upon the existing literature.\n\nGiven the value of the derived results, this paper can contribute substantially to the field with some revisions. I recommend a clear justification for the chosen scenario of positional encoding and a distinction between the presented findings and existing literature. This would fortify the paper's novelty and relevance, making it a more significant contribution to the domain.", "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": "", "extra_scores": {}}, {"review_id": "AQrtW4KCW8", "reviewer": "Reviewer_EnRw", "summary": "Summary: This work can be contextualized along a recent line of study in graph learning which is focused on comparing graph transformers (GTs) and message passing GNNs (MPGNNs) and finding out which is better and why. This paper in particular theoretically and empirically compares the expressive power of GTs and MPGNNs with virtual nodes (MPGNN+VNs) in the uniform setting where a single model must work for graphs of all sizes. It shows that neither model is uniformly universal, but they can express some unique functions, making their expressive power incomparable. \n\nthe paper's contributions:\n- Presents important insights that can be useful to understand the working capabilities of GTs and MPGNNs.\n- Proves that GTs and MPGNN+VNs cannot uniformly approximate every computable graph function, even with polynomial-time positional encodings.\n- Shows GTs cannot uniformly approximate unbounded summation like |V|2, while MPGNN+VNs can.\n- Shows MPGNN+VNs cannot uniformly approximate functions exploiting softmax attention's asymmetric neighbor weighting, while GTs can.", "questions": "in the Weaknesses section", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Strengths:\n- The paper makes an important theoretical contribution by formally proving distinguishing functions for GTs and MPGNN+VNs. This helps characterize their expressive power, and informs more about the strengths and weaknesses of these two model class in addition to what is known in recent literature (eg Cai et al., 2023). \n- The proofs identifying unique functions are non-trivial and provide insight into the core operations enabling GTs and MPGNN+VNs to express different functions.\n- The theoretical findings are verified through special designed experiments on synthetic data, showing the distinguishing functions are learnable in practice.\n- Experiments on real-world benchmarks demonstrate MPGNN+VNs can be competitive with GTs in some cases, due to global communication via virtual nodes. however, this is known in the literature, to the best of my understanding", "weaknesses": "Limitations and Questions:\n- The theoretical analysis focuses on comparing one variant of GTs (GPS) and MPGNN+VNs. Results could vary for different architectures within these families. How accurate would this generalization be?\n- On some realworld datasets, MPGNN+VNs do not fully close the performance gap compared to GTs. It is unclear if this limitation is fundamental or if deeper MPGNN+VNs could match GTs.", "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": "", "extra_scores": {}}, {"review_id": "UXcNVQI15q", "reviewer": "Reviewer_MBi3", "summary": "This paper studies the expressiveness of graph transformers and message-passing gnns. As its first step, the authors exploit the universality of MLP and the property of positional encoding, i.e., injective up to isomorphism, to prove the non-uniform universality of graph transformer and message-passing gnns. Then, the scope of discussion is extended to uniform expressivity, that is, whether these kinds of neural architectures can approximate arbitrary function no matter how large the input graph is. Basically, the authors show that both graph transformers and message-passing gnns are not universal approximator in this setting. Moreover, they offer important insight that these two kinds of neural architectures do not subsume each other. Specifically, graph transformers cannot perform unbounded aggregation, yet its attention mechanism allows asymmetric weighting of incoming messages. Accordingly, the authors design and conduct experiments on synthetic datasets to validate their theoretical results. On practical datasets, these models are also comparable, especially the virtual node trick, which helps a lot for message-passing gnns. In summary, this paper tells the community that attention is NOT all you need in graph learning.", "questions": "In the synthetic experiments, the authors said they were interested in the generalization behavior of the train models. However, the setting is not as usual. It is not an i.i.d. generalization but o.o.d. extrapolation (graph size <= 50 during training and > 50 in test). Generally and intuitively, a model that is more sophisticated with o.o.d. extrapolation is often due to its more reasonable inductive bias or limited hypothesis space, such that it captures the underlying actual mapping rather than fitting the training data by other consistent yet different mappings. Thus, I need clarification about the rationale behind experimental design. Could you explain this to me?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1.\tThis paper is well-written. I can effortlessly pick the main points up.\n2.\tThe theoretical results introduced in this paper seem to be crucial for developing machine learning models dedicated to graph data. Notably, these results explain some interesting phenomena emerging in recent years, including the superiority of graph transformers in some competitions, the surprising usefulness of virtual node trick, and the existence of some real-world datasets on which message-passing gnns are still state-of-the-art.\n3.\tThe experiments are convincing, where the difference between these two kinds of neural architectures is remarkable.", "weaknesses": "1.\tIt seems that the presented theoretical results in the non-uniform are relatively trivial, as they are straightforward results of the combination of MLP’s universality and PE’s discrimination capacity.\n2.\tThe difference and respective advantages deserve to be connected to practical tasks on molecular graphs, as there have been many public tasks, some of which graph transformers outperform traditional message-passing gnns, yet some are not. Such connections must be helpful for the community and make the theoretical results practical.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)