Probabilistic Graph Rewiring via Virtual Nodes
Authors: Chendi Qian
Andrei Manolache
Christopher Morris
Mathias Niepert
Venue: NeurIPS 2024 poster (2024)
Keywords: probabilistic
graph
rewiring
virtual
nodes
long-range
Primary area: graph_neural_networks
TL;DR: Our approach enhances message-passing in graphs with probabilistic rewiring and virtual nodes, addressing under-reaching and over-squashing, and outperforming traditional MPNNs and graph transformers in both expressiveness and efficiency.

Abstract: Message-passing graph neural networks (MPNNs) have emerged as a powerful paradigm for graph-based machine learning. Despite their effectiveness, MPNNs face challenges such as under-reaching and over-squashing, where limited receptive fields and structural bottlenecks hinder information flow in the graph. While graph transformers hold promise in addressing these issues, their scalability is limited due to quadratic complexity regarding the number of nodes, rendering them impractical for larger graphs. Here, we propose implicitly rewired message-passing neural networks (IPR-MPNNs), a novel approach that integrates implicit probabilistic graph rewiring into MPNNs. By introducing a small number of virtual nodes, i.e., adding additional nodes to a given graph and connecting them to existing nodes, in a differentiable, end-to-end manner, IPR-MPNNs enable long-distance message propagation, circumventing quadratic complexity. Theoretically, we demonstrate that IPR-MPNNs surpass the expressiveness of traditional MPNNs.  Empirically, we validate our approach by showcasing its ability to mitigate under-reaching and over-squashing effects, achieving state-of-the-art performance across multiple graph datasets. Notably, IPR-MPNNs outperform graph transformers while maintaining significantly faster computational efficiency.

Probabilistic Graph Rewiring via Virtual Nodes
Chendi Qian 1
Andrei Manolache Christopher Morris
Mathias Niepert 23r
'Computer Science Department, RWTH Aachen University, Germany
Computer Science Department, University of Stuttaart, Germany
*IMPRS-IS *Bitdefender, Romania
chendi an wwth- de andrei wwwaanlacheeii....mm www.:uuutttittttttt..mmmm stuttgart.de
Abstract
Message-passingg graph neural networks (MPNNs) have emerged as a powerful paradigm for graph-based machine learning. Despite their effectiveness, MPNNS face challenges such as under-reaching and over-squashing. where limited receptive fields and structural bottlenecks hinder information flow the graph. While graph transformers hold promise in addressing these issues, their scalability is limited due quadratic complexity regarding the number of nodes, rendering them impractical for larger graphs. Here, we propose implicitly rewired weessage-passigg neural networks (IPR-MPNNs), novel approach that integrates implicit probabilistic graph rewiring into MPNNs. By introducing a small number of virtual nodes, i.c., adding additional nodes to a given graph and connecting them existing nodes, a differentiable, end-to-end manner, IPR PRMM enable long-distance message propagation, circumventing quadratic complexity. Theoretically, we demonstrate that IPR-MPNNN surpass the expressiveness of traditional MPNNs. Empirically, we validate our approach by showcasing ability to mitigate under-reaching and over- squashing effects, achieving sate-of-thhe-ar art performance across multiple graph datasets. Notably, IPR-MPNNs outperform graph transformers while maintaining significantly faster computational efficiency.
1 Introduction
Message-passing graph neural networks (MPNNs) [Gilmer et al. 2017 Scarselli et al. 2008 recently emerged as the most prominent machine-learning architecture for graph-structured, applicable to large set of domains where data is naturally represented as graphs, such as bioinformatics (Jumper)
al., 2021
Wong et al.) 2023 social network analysis [Easley et al. 2012], and combinatorial
optimization [Cappart et al. 2023 Qian et al. 2024).
MPNNs have been studied extensively in theory and practice [Böker al.
2023 Gilmer et al. 2017
Kipf and Welling 2017, Maron et al. 2019b] Morris et al., 2019 2021
2023 Veličković et al.
shown that MPNNs suffer from over-squashing AAlon and Yahay [2021]. where bottlenecks arise from stacking multiple layers leading to large receptive fields, and uncering [Barceló et al.) 2020). where distant nodes fail to communicate effectively because MPNNs' receptive fields are too narrow. These phenomena become prevalent when dealing with graphs with large diameter, potentially hindering the performance of MPNNs on essential applications that depend on long-range interactions, such as protein folding [Gromiha and Selvaraj. 1999]. However, modeling long-range interactions in atomistic systems such as proteins remains
2018 Xu et al. 2019). Recent works
'These authors contributed equally. CCo-senoor authorship.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Forward pass
== (G)A
H ~ Piaa) (H)
< (AG)) X. (H H
Upstream MPNN
Virmu Cruphh
Exactly-A Sampling
Downstream MPNN
Downstream Loss
AG))
X 0
Bi 5.6
8 =-17
Backward pass
Figure 1: Overview of how IPR-MPNNS implicitly rewire a graph through adding virtual nodes. IPR-MPNNs upstream MPNN to learn priors 0 for connecting original nodes with virtual nodes via edges, parameterizing a probability mass function conditioned on exactly-k constraints. Subsequently, sample exactly l edges from this distribution for each original node, connecting to & virtual nodes. We input the resulting graph to a downstream model, typically an MPNN, for the final predictions task, propagating information from (1) original nodes to virtual nodes, (2) among virtual nodes, and (3) among original nodes. On the backward pass, the gradients of the loss l regarding the parameters 0 are approximated through the derivative of the exactly-k marginals.
challenging problem often solved in an ad-hoc fashion using coarse waase-graining methods (Saunders and Voth 2013 Husic al., 2020), effectively grouping the input nodes into cluster nodes.
Recently, graph rewiring BBhee et al. 2022 Deac et al. 2022 Gutteridge et al. 2023 Karhadkar et al. 2022 Shirzad et al.) 2023 Topping et al.] 2021
techniques emerged, adapting the graph structure to enhance connectivity and reduce node distance through methods ranging from edge additions to leveraging spectral properties and expander graphs. However, these approaches typically employ heuristic methods for selecting node pairs to rewire. Furthermore, graph transformers (GTs)
[Chen al. 2022a. Dwivedi al., [022b] He al.) 2023] Müller al., [023]] Müller and Morris
2024 Rampášek et al., [022] and adaptive techniques like those by Errica et al. [2023] improve
handling long-range relationships but face challenges of quadratic complexity and extensive
parameter sets, limiting their scalability.
Most similar IPR-MPNNS is the work of Qian et al. 2023), which, like IPR-MPNNs, leverage recent techniques in differentiable ke-ubsse sampling [Ahmed et al. 2023 to learn to add or remove
edges of given graph. However, like GTs, their approach suffers from quadratic complexity due to their need to compute a score for each node pair.
Present Work Our proposed IPR-MPNN architecture advances end-to-end probabilistic adaptive graph rewiring. Unlike the PR-MPNN framework of Qiia et al. [2023], which suffers from quadratic complexity since the edge distribution modeled explicitly, IPR-MPNNs implicitly transmits infor- mation across different parts of a graph by learning to connect the existing graph with newly-added virtual nodes, effectively circumventing quadratic complexity; Figure T for high-level overview of IPN-MSNNs. Our contributions are as follows.
1. We introduce IPR-MPNNs, adding virtual nodes to graphs, and learn to rewire them to the existing nodes end-to-end. IPR-MPNNs successfully overcome the quadratic complexity of graph transformers and previous graph rewiring techniques.
2. Theoretically, we demonstrate that IPR-MPNNs exceed the expressive capacity standard MPNNs, typically limited by the 1-dimensional Weisfeiler--Lmaat algorithm.
3. Empirically, we show that IPR-MPNNs outperform standard MPNN and GT architectures large of established benchmark datasets, all while maintaining significantly faster computational efficiency.
4. We show that IPR-MPNNS are reducing the total effective resistance Black et al., 2023 of multiple molecular datasets while also significantly improving the layer-wiss wise sensitivity

---

Di Giovanni et al. 2023 Xu et al. 2018 between distant nodes when compared to the base model.
In summary, IPR-MPNNs represent a significunt advancement towards scalable and aduptable MPNNs. They enhance expressiveness and adaptability to various data distributions while scaling to large graphs effectively.
1.1 Related Work
In the following, we discuss relevant related work.
Recently, MPNNs [Gilmer et al. 2017 Scarselli et al. 2008 emerged as the most prominent graph machine learning architecture. Notable instances of this architecture include, e.g., Duvenaud et al. 2015), Hamilton et al. [2017]. and Veličković al. [2018). which can be subsumed under the message-
MPNNs
framework introduced in Gilmer et al. [2017]. In parallel, approaches based on spectral information were introduced in, e.g., Bruna al. [2014]. Defferrard
ct al. 2016). Gama et al. (2019), Kipf and Welling [2017). Levie et al. [2019], and Monti et al.
2017 all of which descend from early work in Baskin et al. [1997] Goller and Küchler [199]].
Kireev 1995]. Merkwirth and Lengauer [2005]. Micheli and Sesttto| 2005 Micheli 2009 Scarselli
al.
2008 and (Sperduti and Starita 1997].
Limitations of MPNNs MPNNs are inherently biased towards encoding local structures, limiting their expressive power [Morris al., 2019 2021 Xu et al. 2019]. Specifically, they are at most as powerful as distinguishing non-isomorphic graphs or nodes with different structural roles as the 1-dimensional Weisfeiler-Lemeee algorithm (Weisfeiler and Leman
1968). well-studied heuristic for the graph isomorphism problem; see Section C Additionally, they cannot capture global or long-range information, often linked to phenomena such as under-reaching (Barceló et al. 2020 or over-squashing AAlon and Yahav 2021]. with the latter being heavily investigated in recent works.
Graph Transformers Different from the above, graph transformers Chen al. 2022a Dwivedi
et al. 2022b He et al. [223] Hussain et al., [2022 Kim et al.] [2022] Ma et al. [02.3] Mialon et al.
2021 Müller et al.) 2023 Müller and Morris 2024 Rampášek al. 2022 Shirzad et al.) 2023) and
similar global attention mechanisms [Liu et al.) 202 Wu et al. [022]] marked shift from local to global message passing, aggregating over all nodes. While not understood in a principled way, empirical studies indicate that graph transformers possibly alleviate over-squashing: see Müller et al.) [2023]. However, all transformers suffer from their quadratic space and memory requirements due to computing attention matrix.
Several recent works aim to circumvent over-squashing via graph rewiring. The most straightforward way of graph rewiring is incorporating multi-hop neighbors. For example, Brtucl-Gabrielsson et al. [2022] rewires the graphs with k-hop neighbors and virtual nodes and augments them with positional encodings. MixHop (Abu-El-Haija et al. 2019). SIGN
Rewiring Approaches for MPNNS
[Fraca et al. 2020). DIGL (Gasteiger et al., 2019], and SP-MPNN (Abboud et al. 2022] can also be considered graph rewiring as they reach further-away neighbors in single layer. Particularly, [Gutteridge
Particulaty,,Gutterddge et al. (2023) rewires the graph similarly to ub/bbouu et al.] [2022] but with a
novel delay mechanism, showcasing promising empirical results. Several rewiring methods depend on particular metrics, e.g., Ricci or Forman curvature [Bober et al., 2022 and balanced Forman
curvature [Topping al. 2021 In addition, Deac et al. [2022], Shirzad al. (2023 utilize expander graphs to enhance message passing and connectivity, techniques, and Banerjee et al. [2022] propose greedy random edge flip approach to overcome over- squashing. DiffWire (Arnaiz-Rodriuee et al./ 2022) conducts fully differentiable and parameter-fie free graph rewiring by leveraging the Lovász bound and spectral gap. Refining Topping et al. (202T), Di Giovanni et al. (2023) analyzed how the architectures' width and graph structure contribute to the over-squashing problem, showing that over- squashing happens among nodes with high commute time, stressing the importance of rewiring techniques. Contrary to our proposed method, these strategies to mitigate over-squashing rely on heuristic rewiring methods or purely randomized approaches that may not adapt well to given prediction task. LASER [Barbero et al. 2023 performs graph rewiring while respecting the original graph structure. The recent work S2GCN [Geisler et al., 2024] combines spectral and spatial graph filters and implicitly introduces graph rewiring for message passing. Most
Karhadkar et al.
2022 resort to spectral
3

---

similar to IPR-MPNNs is the work of Qian et al. [2023), which, like IPR-MPNNS, leverage recent techniques in differentiable k-subset sampling [Ahmed al. 2023) to learn to add or remove edges of given graph. However, like GT's, their approach suffers from quadratic complexity due to their need to compute a score for each node pair. addition to the differentiable s-sbeeet sampling [Ahmed et al. 2023] method we use in this work, there are other gradient estimation approaches such as GUMBEL SOFTSUB-ST [ii and Ermon 2019] and I-MLE [Niepert et al. 2021 Minervini et al. 2023
There is also large set of works from graph structure learning proposing heuristical graph rewiring approaches and hierarchical MPNNs; see Section A for details.
2
Background
In the following, we introduce notation and formally define MPNNs.
Notations Let N = (1. }. For n 2 1, let [n] == [I.....n], C N. We use f... B to denote multisets, i.c., the generalization of sets allowing for multiple instances for each of its elements. A graph G is a pair (V(G), E(G)) with finite sets of nodes or vertices VGG and edges & v). If not otherwise stated, of order n. We also call the graph G an n-order graph. For ease of notation, we denote the edge {u, in E(G) by (u,)) or (v, u). Throughout the paper, we standard notations, e.g., denote the neighborhood of vertex e by (() and E(v) denotes its discrete vertex label, and so on;
E(G) (fu, r) C V(G)
set
IV(G)), and the graph
Section
B for details.
Message Graph Neural Networks Intuitively, MPNNS Iearn a vectorial representation. i.e,& d-dimensional real-valued vector, representing each vertex in graph by aggregating information from neighboring vertices. Let G (G, be an n-order attributed graph with node feature matrix
X E Randd for d > 0, following, Gilmer et al. 2017] and Scarselli et al. [2008], each layer, > we compute vertex features
(PD (h! (h((-)), AGG (G u (()))) E R
where (!D()) and (G may parameterized functions, e.g., neural networks, and h = X,,. In the case of graph-level tasks, e.g., graph classification, one uses
hg = READOUT ((NTT) I (()))) E RR
to compute a single vectorial representation based on learned vertex features after iteration T.. Again, READOUT may be a parameterized function, e.g., neural network. To adapt the parameters of the above three functions, they are optimized end-to-end, usually through a variant of stochastic gradient descent, e.g.. KKngmaa and Ba 2015)] together with the parameters of a neural network used for classification or regression.
Implicit Probabilistically Rewired MPNNs
Implicit probabilistically rewired message-passingg neural networks (IPR-MPNNs) learn probability distribution over edges connecting the original nodes a graph to additional virtual nodes, providing an implicit way of enhancing the graph connectivity. To learn to rewire original nodes with these added virtual nodes, IPR-MPNN use an upstream model, usually an MPNN, to generate scores or (unnormalized) priors 0 ha (A(G), X) E Raxm, where G is an n-order graph with adjacency matrix A(G)) {0, 1] 1 node feature matrix X guxd for d >> 0, and number of virtual nodes m with m & TL.
IPR-MPNNs use the priors 0 from the upstream model to sample new edges between the original nodes and the m virtual nodes from the posterior constrained exactly it edges, thus obtaining an assignment matrix H E {0. 1 i.e., an adjacency matrix between the input and virtual nodes. The assignment matrix H then used in a downstream model fux utilized for solving our downstream task, e.g., graph-level classification or regression. Leveraging recent advancements in gradient estimation for k-subset sampling [Ahed et al. 2023), the upstream and downstream models jointly optimized, enabling the model to be trained end-to-end; see below.

---

Hence, unlike PR-MPNNS [Qian et al. 2023], which in the worst case explicitly model an edge distribution for all n² possible edge candidates for rewiring, IPR-MPNNS leverage virtual nodes for implicit rewiring and passing long-range information. Therefore, IPR-MPNNs benefit from better computation complexity while being more expressive than the 1-WL; see Section 4 Moreover, intuitively, it is also easier to model a distribution of edges connected to few virtual nodes than to learn the explicit distribution of all possible edges in a graph. More specifically, while in PR-MPNNs, the priors 0 can have a size of up to n² for n-order graph, IPR-MPNNs use parameters, therefore significantly enhancing both computational efficiency and model simplicity.
In the following, we describe the IPR-MPNN architecture in detail.
Sampling Edges Let 2, represent the adjacency matrices of n-order graphs. Consider (G, X) graph of order with adjacency matrix A(G) M, and node feature matrix X E R for > O. IPR-MPNNs maintain parameterized upstream model h 2l, Raxd + O, usually implemented through an MPNN and parameterized by u. The upstream model transforms an adjacency matrix along with its node attributes into set of unnormalized node priors 0 E O C R=xm with m denoting the predefined number of virtual nodes. Formally,
) as
0 l,,(AG),, X) R
The matrix of priors serves as the parameter matrix for the conditional probability mass function from which the assignment matrix H {0, 1) joxm is sampled. Crucially and contrary to prior work (Qian et al. 2023), these edges connect the input and small number m of virtual nodes. Hence, each row of matrix 0g E TR represents the unnormalized probability of assigning node to each virtual node. Formally, we have,
M II pe.. (Hy), for E [n]. j=1
pe (H))
where po., (H,, sigmoid and po., H.; 0) (0gy) Without loss of generality, allow each node to be assigned to k virtual nodes, with & [m². That is, each row of the sampled assignment matrix has exactly ls non-zero entries, i.e.,
P(o,))(H) = po Po(H//2 if Hf = for all i [n]. with == 0
Σ
Po (B).
otherwise,
| 1B
We can potentially sample independently q times ()) P(o, (H) and consequently obtain multiple assignment matrices H == (H(1,, ( H B. which, together with corresponding number of copies of A(G) and X, will be utilized by the downstream model for the tasks.
Message-passe passing Architecture of IPR-MPNNs Here, we outline the message-passinng passing scheme after adding virtual nodes and edges. Consider an n-order graph G and a virtual node C(G) of cardinality m, where each original node V(G) == [m] is assigned to k [m] virtual nodes. We assign original nodes v subset of the virtual node using the function a: V(G) [C(G)] k where v + {c C(G) H.c = }} and [C(G)] is the set of k-element subsets of the virtual nodes. Conversely, each virtual node e C(G) links to several original nodes. Hence, we define an inverse assignment the set of all original nodes assigned to virtual node i.e., (c) = {u E V(G) e E a(v)). Across the graph, the union of these inverse assignments equals the set of original nodes, i... U. (c) VG).
We represent the embedding of an original node v E V(G) at any given layer / 2 0 as h and similarly, the embedding for a virtual node E C(G) as g. To compute these embeddings, IPR- MPNNs compute initial embeddings for each virtual node. Subsequently, the architecture updates the virtual nodes via the adjacent original nodes" embeddings. Afterward, the virtual nodes exchange messages, and finally, the virtual nodes update adjacent original nodes' embeddings. Below, we outline the steps in order of execution involved in passsag algorithm in detail.
5

---

Intializing Virtual Node Embeddings Before executing inter- hierarhhrall message passing, we need to initialize the embeddings of virtual nodes. To that, given the node assignments a(t), , for E V(G). we can effectively divide the original graph into several subgraphs, where nodes sharing the same assignment label are grouped together to form an induced subgraph. Formally, for any virtual node e E C(G), we have the induced subgraph Ge with node subset V.(G,) = {w V(G) n na (c)} and edge set (G.) = {u, t} {u, v} E E(G), u E a a-+ and a (c)). The initial attributes of the virtual node are defined by the node features of its corresponding subgraph G., calculated using an MPNN, i.e.,
MPNN (Go), for e E C(G).
Alternatiely,, we can generate random features for each virtual node as initial node features or assign unique identifiers to them.
Updating Virtual Nodes In each step > O, we collect the embeddings from original nodes to virtual nodes according to their assignments and obtain intermediate virtual node embeddings
g
(GGn (gh!-)) ( (c))), for E C(G),
where AGGn (c) denotes some permutation-cquivariaie aggregation function designed for multisets.
Updating Among Virtual Nodes We assume the virtual nodes form a complete, undirected, weighted graph, and we perform message passing among the virtual nodes to update their embeddings. That is, at step i, we set
AGG ( (g.t"),
(Ko AGGG
lj C(G.)
where UPDc and AGGc are the update and neighborhood aggregation functions for virtual nodes.
Updating Original Nodes Finally, we redistribute the embeddings from the virtual nodes back to the base nodes. This update process considers both the neighbors in the original graph and the virtual nodes to which the original nodes are assigned. The updating mechanism detailed in the following equation,
h ( (?) (n(-1), (GG")) (gh!-") I (())) () (4g! Ice (cE)())))
where UPD is the update function, AGG is the aggregation function, and DS is the distributing function that incorporates embeddings from virtual nodes back to the original nodes.
Gradient Estimation In the context of our downstream MPNN model described above, we define the set of its learnable parameters as and group these with the upstream model parameters u into combined tuple
(u, v). We express the downstream model as fu, resulting in the loss function
L (A(G), X, H: w) = EH [e (fo ( (A(G), X, ( (H ..... H 3).))
While the gradients for the downstream model fo can be straightforwardly calculated via back- propagation, obtaining gradients for the upstream model parameters is more challenging, as the assignment matrices H are sampled from the priors 0, a process which is not differentiable.
utilize SIMPLE [Ahmed et al., 2023 J, which efficiently estimates gradients under k-subset constraints. This method involves exact sampling in the forward phase and uses the marginal of the priors (() R during the backward phase to approximate gradients Vol. x V
Similar to prior work [Qian et al. 2023],
The following analysis shows that our proposed method circumvents the problem of being quadratic the number input nodes.
Complexity Assuming constant number of hidden dimensions and layers of the MPNNs, recall that the runtime complexity of a plain MPNN is O(F.,), where [E] is the number of edges of given graph. In the IPR-MPNN framework, we still have MPNN backbone, augmented with

---

-25
Log of Layer Sensitivity
-5.0
-5.0
MPNN (-29)
MPNN (1-0)
-10.0
IPR-MPNN (1-25)
Bast (1-20)
Base (1-30)
IPA-MPNN
10.00
IPR-MPNN (2 nodes)
IPR-MPNN (15% undes)
-12.5
Bast (1:25)
Buse (1-40)
-12.5
IPR- WW-MPPN nodes)
Baseline (0v, modes)
IPR MPNN (10 aodes)
-15.0
-15.0
-17.5
-20.0
10
15
20 Layer
25
30
35
40
5
10
15
25
30 35
40
Layer K
Figure 2: Comparing model sensitivity across different layers for the two most distant nodes from graphs from the ZinC dataset. On the left, we compare the sensitivity for models with a varying number of layers. We can observe that IPR-MPNNs maintain a high sensitivity even for the last layer, while the base models have the sensitivity decaying to On the right, we compare models with different number of virtual nodes, observing that the results are similar for all of the variants.
intee--messeee message passing involving virtual nodes. Hence, obtaining priors for the original nodes via an MPNN or candidate virtual nodes to be selected. Sampling the node assignment with with Ahmed et al. [223]] is in On log m log k). The message aggregation and distribution between base nodes and virtual nodes have complexity (n k)), where & E [m]] is the number of nodes node is assigned to. Finally, the
simple MLP has complexity of O(EE) + n m)). where is the number of
they are fully connected. In summary, IPR-MPNNs have a running time complexity in O(EE) + n m + m²). Since m < n is a small constant, IPR-MPNNS show great potential due their low complexity compared the quadratic worst-case complexities of graph transformers [Müller et al. 2023) and other rewiring methods,
node message passing is in O O(m²).
e.g., Gutteridge al. 2023
Qian al. 2023
4 Expressive Power
In this section, we analyze the extent to which IPR-MPNNs can separate non-isomorphic graphs on which the 1-WL isomorphism test fails Xu et et. 2019 Morris et al. 2019) and whether IPR-MPNNs can maintain isomorphisms between pairs of graphs. We adopt the notion of probabilistic separation from Qian al. 2023
Our arguments rely on the ability of our upstream MPNN to assign arbitrary and distinct exactly-k distributions for each color class. By modifying the graph structure, graphs -i--isitinuuishabll, enabling our downstream MPNN to separate them. However, since the expressiveness of the upstream model is also equivalent to 1-WL, there is possibility of still separating isomorphic graphs.
make the rewired
The following result demonstrates that we can preserve almost all partial subgraph isomorphisms.
Theorem 4.1. Let k > O, E (0, 1), and G, H be two graphs with identical 1-WL stable colorings. Let M be the set of ordered virtual nodes, Va and VH be the subset of nodes in G and H that have color class of cardinality 1, with IVal = [V d, and WG. WH the subset of nodes that have a color class of cardinality greater than 1, with Wa = [W = n. Then, for all choices of 1- WL-eeuivvlennt functtoon f.
(1) there exists conditional probability mass function P(e,k) that does not separate G[Vo] and [VH]] with probability at least 1 E.
(2) There exists a conditional probability mass function P(e.)) that separates G[Wa] and H[ #] with probability strictly greater than 0.
We argue that preserving these partial subgraph isomorphisms is sufficient for most examples in practice. Indeed, our empirical findings show that datasets, whereas a 1-WL model obtains random performance; see Table A11 AableAA1
successfully solve both the ExP and CSL
The next corollary follows the above and recovers Theorem 4.1 from Qian et al. 2023 The corollary
tells us that, even if there are isomorphic graphs that we risk making separable, we will maintain the isomorphism between almost all isomorphic pairs.
7

---

Table 1: We compare IPR-MPNN on QM9 with the base downstream GIN model Xu et 2019 two graph rewiring techniques [uutterdgee et al. 2023] Qian et al., 2023], multi-hop MPNN [Abboud] al. 2022], and the relational GIN [Schlichtkrull colored in green, the second-best in blue, and third in orange. IPR-MPNN obtains the best result on
al. 2018 The best-performing method is
all targets, except for MU, where it obtains the second- best result.
PROPERTY
2019
R-GIN+FA [2018]
SPN [2022
2023
PR-MPNN
IPR-MPNN
MU
2.64.000
m
2. 2.32,00.0
1.93
1.9920.0
2.01 2001
ALPHA
7.67s0.15
2.28=000
1.77=6.00
1.63e0.00
2.2840.00
1.36 #001
HOMO
1.70=n0:
1.26=amu
1.26e0.0
1.16s0.01
1.14
20033
LUMO
3.0520m1
1.34
1.19:00.0
1.13
1.12+0.01
1.03 =0007
GAP
3.37
1.96:000
1.89
1.74
1.70
1.61 20.0
R2
23.35.1:00
12.61:007
10 10.6622049
9.392a-11
10.41:10.00
8.17
ZPVE
66.87.11445
5.03_.0.3
2.7716.17
2.73
4.73.00.06
10.07
UO
21:48:0.17
2.21 12
1.12
1.01
2.23+0.11
0.74 20.11
U
20.59
1.
1,03ec.0
0,99
2.31+0.00
0.79
21.96=1.24
2.26=6.19
1.05=0.0
1.06e0.m
2.66
G
19.53
2.04
0.97
1.06
2.24
0.62 20.13
CV
7.34_00s
1.86,000
1.361.000
1.24
1.4410.01
1.03 1001
OMEGA
0.60s00s
0.80=0.4
0.57=0.0:
0.55
0,4840.00
20.33
Table 2: Results on the PEPTIDES and PCQM-CONTACT datasets from the long-range graph benchmark (Dwivedi al. 2022b) For PCQM-CONTACT, use both the initially proposed evaluation methodology (PCQM and the filtering methodologies proposed in Tönshoff al. [2023) (PCQM()) for filtering and (CQM(3) for extended filtering). Green is the best model, blue is the second, and red the third. IPR-MPNNS obtain the best predictive performance on all datasets.
PEPTIDES- 1
STRUCT
PCQM"N
PCQM
PCQM 1
GINE
2019
2025
3.6621 2000
0.2473ga.oo 2017
D. 2..00
D.372520006 0.363120006
7200000005 0.4526100066
GCN
COLER
0.68601o.nee
0.246010.000
D. 3.24224.5 000007
DREW
0.7150
0.2536.88 0.253610.0015
0.3444
0.6825eo.0te
0.2477a0.c0m
AMP
2023
0.7163 Louaace
0.24.31 100.0001
NBA -023
0.7207 0.7207ae.ttar sq.0nos
0.2472 20.2000
GATENGCK-PE+NVE
2024
0.6 0.6822
0.2458
S2GCN
0.7275=s0.0om
0.2467
S2GCN-PEL 2024
0.73 I ao.000s
0.2447ao.com
GPS 2022
0.6535 s0.0041
0.2509
D. 0.3498
0.3722
0,4703
EXPHOEMER 2023
0.6527
0.248
0.3637
696988
0.2460 Lo0.00000000
GRAPH MLL MIXER
2023
0.6970
0.2475 0.2475ao.001 80.0015
GRAPH VIT
2023
0.6942s0.com
0.2449e0.001s
IPR-MPNN (OURS)
0.7210sa.ccom
0.242280.007
0.3670
0.3846620044
0,4756s00us
Corollary 4.1.1. For sufficiently large n, for every & E (), a set m of ordered virtual nodes, and k O, have that almost all pairs, in the sense of Babai al. [1980), of isomorphic n-order graphs G and H and all germutation-invaiinae there exists a probability mass function k)) that separates the graph G and H with probability at most e regarding f.
I-WL-equivalent functions f: 2,, + R2d d > O,
The previous theorems show that we are preserving isomorphisms better than purely randomized approaches while being more powerful than 1-WL since we can separate non isomorphic graphs with a probability strictly greater than O. We provide the proofs and examples in Section E
5 Experimental Setup and Results
To empirically validate the effectiveness of our IPR-MPNN framework, conducted series of experiments on both synthetic and real-world molecular datasets, answering the following research questions. An open repository of our code can be accessed at httpt:t////// http:::://gituub... cww www.chendigiaan IPR-MPNN
Q1 Do IPR-MPNNs alleviate over-squashing and under-reaching?
Q2 Do IPR-MPNNs demonstrate enhanced expressivity compared to MPNNs?
Q3 How do IPR-MPNNs compare in predictive performance on molecular datasets against other rewiring methods and graph transformers?
Q4 Does the lower theoretical complexity of IPR-M MPMNNN translate to faster runtimes in practice?
8

---

Table IPR-MPNN training, inference (seconds per epoch), and memory consumption statistics in comparison to the base GINE model [Xu et al., 2019], the GPS graph transformer [Rampášek et al. 2022 and the Drew model [Gutteridge et al. 2023] on the PEPTIDES-STRUCE dataset [Dwivedi et al., 2022b]. Our model has almost the same computation and memory efficiency as the base GINE model while being twice as fast and significantly more memory efficient when compared to GPS.
GINE
IPR-MPNN
GPS
DREW
PAR.
503k
536k
558k
522k
TRN S/EP.
2.68=0.01
2.98=0.02
7.81
3.20=0.03
VAL S/EP.
0.21:10.00
0.2710000
0.58.10.44
0.36
MEM.
1.7GB
1.9GB
22.2GB
1.8GB
Datasets, Experimental Results, and Discussion To address Q1, we investigate whether our method alleviates over-squashing and under-reaching by experimenting NEIGHBBUUSMMATCH [Alon and Yahav 2021] and TREES-LEAFCOUNT [Qian et al. 2023 On LEEES-LEAFCOunT with a tree depth of four, we obtain perfect performance on the test dataset with a one-layer downstream network, indicating we can alleviate under-reaching. Furthermore, on NEIHHSEENGBBOURSSNA
TREES-
our method obtains perfect performance to a depth up to six, effectively alleviating over-squashing, as shown in Figure A4 To quantitatively assess whether over-squashing is mitigated in real-world scenarios, we computed the average layer-wise sensitivity [uu et al., 2018 8 Di Giovanni et al., [203 Errica et al., [023) between the most distant nodes in graphs from the ZINC dataset and compared these results with those from the baseline GINE model. Specifically, we compute the logarithm of the symmetric sensitivity between the most distant nodes u, U as log (jon(/on", + pnt,/on, I), where k to 1 represent the intermediate layers. We show that IPR-MPNNs maintain high layer-wise sensitivity compared to the base model, as seen in Figure 2 implying that they can successfully account for long-range relationships, even with multiple stacked layers. Lastly, measured the average total effective resistance [Black al. [023] of five molecular datasets before and after rewiring, showing in Figure 3 that IPR-MPNNs are successfully improving connectivity by reducing the average total effective resistance of all evaluated datasets.
For Q2, we conduct experiments on the EXP [Abboud et al.. 2020 and CSL MMurphy et al. 2019 datasets to evaluate the expressiveness of IPR- IPR-MPNNs. The results, as detailed in Table A10 and Table/ATT] demonstrate that our IPR-MPNN framework handles these datasets effectively and exhibits improved expressiveness over the base I-WL-equivalent GIN model.
For answering Q3. we utilize several real-world molecular datasets QM9 (Hamilton et al. 2017). ZINK 12k (Jin et al. 2017). OGB-MOLHIV [Hu et al., 20220]. TUDATASET MMrris et al.) [220aa] and datasets from the LONG-RANGE GRAPH BENCHMARK [Dwivedi et al. 2202b], namely PEPTIDES and PCQM-CONTACT. Our results demonstrate that İPR-MPNNs effectively account for long- range relationships, achieving state-of-the-an performance on the PEPTiDES and PCQM-CONTAS datasets, as detailed in Table Notably, on the FCQM-CONTAR link prediction tasks, IPR IPR-MPNNs outperform all other candidates across three measurement metrics outlined in Tönshoff et al. [002). For QM9, we show in Table [ that IPR-MPNNs greatly outperform similar methods, obtaining the best results on of target properties. On ZINC and OGB MOLHIVV we outperform similar MPNNs and graph transformers, namely GPS Rampášek et al. 2022) and SAT [Chen et al.) 2022a]. obtaining state-of-the-ar results; see Table 4 For the TUDATASET collection, we achieve the best results on four of the five molecular datasets; see A9
Finally, to address Q4, we evaluate the computation time and memory usage of IPR-MPNNS in comparison with the GPS graph transformer [Rampášek et al. 2022) on SEPTIDES-STRUCE and extend our analysis to include PR-MPNNs [Qian al. 2023). SAT Chen et al. 2022a). and GPS on the ZINC dataset. The results in Tables demostttt that IPR-MPNNY adhere to their theoretical linear runtime complexity in practice. We observed a notable speedup in training and validation times per epoch while reducing the memory footprint by a large margin compared to the two mentioned transformers. This efficiency underscores the practical advantages of IPR-MPNNs in computational speed and resource utilization.
demonstrate

---

Log the weg. dotaect Rot
Comparison of Original and Rewired Darasets
Table Results on the ZINC [Jin et al. 2017] and OGBG-MOLHI (Hu al. 2020 datasets. Green is the best model, blue the second, and red the third. The IPR-MPNN outperforms both SAT and GPS on ZINC, while obtaining the same performance GPS on OGB-MOLHIV.
'6
811552
26635
5319
841
3993
887
2330
471
912
320
8.0
Peyndds
Motaar
PCuoe-Uarad Datasets
ZINc
QMP
MODEL
ZINC (12K)
OGB COB-MOLIIV
Figure 3: We compute the log of total effective resistance [Black al. 2023 of five molecular datasets before and after rewiring the graphs using virtual nodes. Our rewiring technique consistently lowers the total effective resistance, indicating better information flow all of the datasets.
GINE 2019 2022
0.101 001
0.764=0.010
PX-MPAX 2043
0. 0.0844x..042
0.795.2..0m
GPS
2023
0.077.15
0.758.10.00
0.11
0.08516 oos
0.779110015
IPR-MPNN (OURS)
0.067.50000
0. 0.788,0..06
Conclusion
Here, we introduced implicit probabilistically rewired sassage-passing neural networks (IPR- MPNNs), graph-rewiring approach leveraging recent progress in end-to-end differentiable sampling. IPR-MPNNs show drastically improved running times and memory usage efficiency over graph transformers and competing rewiring-base baste architectures due to IPR-MPNNS' ability to circumvent comparing every pair nodes and significantly outperforming them on real-world datasets while effectively addressing over-squashing and overreaching. Hence, IPR-MPNDI represent significant step towards designing scalable, adaptable MPNNs, making them more reliable and expressive.
Acknowledgments
CQ and CM partially funded by DFG (German Research Foundation) Emmy Noether grant (468502433) and RWTH Junior Principal Investigator Fellowship under Germany's 's Excellence Strategy. AM and MN acknowledge DFG funding under Germany's Excellence Strategy-EX 2075 390740016, the support of the Stuttgart Center for Simulation Science (SimTech), and the International Max Planck Research School for Intelligent Systems (IMPRS-IS).
10

---

References
R. Abboud, I. I. Ceylan, M. Grohe, and T. Lukasiewicz. The surprising power of graph neural networks with random node initialization. arXiv preprint, 2020.
9 20
R. Abboud, R. Dimitrov, and I. Ceylan. Shortest path networks for graph property prediction. In Learning on Graphs Conference, 2022. 3
S. Abu-El-Haija, B. Perozzi, A. Kapoor, N. Alipourfard, K. Lerman, H. Harutyunyan, G. Ver Steeg,
and A. Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighbor- hood mixing. In International Conference Machine Learning. 2019.
K. Ahmed, Z. Zeng, M. Niepert, and G. Van den Broeck. Simple: A gradient estimator for k-subset sampling. In International Conference on Learning Representations, 2023.
18
U. Alon and E. Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2021,
21
A. Armaiz-Rodríguez, A. Begga, F. Escolano, and N. Oliver. Diffwire: Inductive graph rewiring via the lovasz bound. arXiv preprint, 2022. 3 26
V. Arvind, J. Köbler, G. Rattan, and O. Verbitsky. On the power of color refinement. In International Symposium on Fundamentals of Computation Theory, 2015. I9
Babai and L.. Kucera. Canonical labelling graphs in linear average time. Annual Symposium on Foundations of Computer Science (sfcs 1979), 1979.
19
L. Babai, P. Erdos, and S. M. Selkow. Random graph isomorphism. SIAM Journal on computing,
(3):628-635, 1980. g 19 23
P. K. Banerjee, K. Karhadkar, Y. G. Wang, U. Alon, and G. Montúfar. Oversquashing in gnns through the lens of information contraction and graph expansion. In Anmual Allerton Conference Communicationn Control, and Computing (Allerton), 2022.
Barbero, A. Velingker, A. Saberi, M. Bronstein, and Di Giovanni. Locality-aware graph-rewiring in gnns. arXiv preprint, 2023. 3
P. Barceló, E. V. Kostylev, M. Monet, J. Pérez, J. Reutter, and J. P. Silva. The logical expressiveness of graph neural networks. In International Conference on Learning Representations, 2020. L
I. I. Baskin, V. A. Palyulin, and N. S. Zefirov, A neural device for searching direct correlations between structures and properties of chemical compounds. Journal of Chemical Information and Computer Sciences, (7):7715577 1997.
P. W. Battaglia, J. B. Hamrick, V. Bapst, A. Sanchez-Gonzalez V. Zambaldi, M. Malinowski, A. Tacchetti, D. Raposo, A. Santoro, R. Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint, 2018. [8
M. Black, Z. Wan, A. Nayyeri, and Wang. Understanding oversquashing in gnns through the lens of effective resistance. In International Conference on Machine Learning, 2023.
20
J. Bober, A. Monod, E. Saucan, and K. N. Webster. Rewiring networks for graph neural network training using discrete geometry. arXiv preprint, 2022.
C. Bodnar, F. Frasca, Y. Wang, N. Otter, G. F. Montufar, P. Lio, and M. Bronstein. Weisfeiler and Lehman go topological: Message passing simplicial networks. In International Conference on Machine Learning. 2021. 26
G. Bouritsas, F. Frasca, S. 7afeiriou, and M. M. Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45()):657-668 2022. 26
R. Gabrei-na,,,,,sson,, M. Yurochkin, and J. Solomon. Rewiring with positional encodings for graph neural networks. arXiv preprint, 2022.

---

J. Bruna, W. Zaremba, A. Szlam, and Y. LeCun. Spectral networks and deep locally connected networks on graphs. In International Conference on Learning Representation, 2014.
J. Böker, R. Levie, N. Huang, S. Villar, and C. Morris. Fine-grained expressivity of graph neural networks. In NeurIPS, 2023.
C. Cai, T. S. Hy, R. Yu, and Y. Wang. On the connection between MPNN and graph transformer. arXiv preprimi, 2023. 18
J.-Y. Cai, M. Fürer, and N. Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389-411) 1992. T9
Q. Cappart, D. Chételat, B. Khalil, A. Lodi, C. Morris, and Veličković. Combinatorial optimization and reasoning with graph neural networks. Journal of Machine Learning Research, 24(100):1-6 1-0 2023. [
D. Chen, L. O' O'Bray, and K. Borgwardt, Structure-aware transformer for graph representation learning. In International Conference on Machine Learning, 2022a. 2
J. Chen, K. Gao, G. Li, and K. He. Nagphormer: A tokenized graph transformer for node classification in large graphs. arXiv preprint, 2022b.
Y. Chen, L. Wu, and M. Zaki. Iterative deep graph learning for graph neural networks: Better and robust node embeddings. Advances Neural Information Processing Systems, 2020. 18
M. Craven, D. DiPasquo, D. Freitag, A. McCallum, T. Mitchell, K. Nigam, and S. Slattery. Learning to extract symbolic knowledge from the world wide web. AAAI/IAAI, 3(.66)2, 1998. 20
de Haan, T. S. Cohen, and M. Welling. Natural graph networks. Advances in Neural Information Processing Systems, 2020. 26
A. Deac, M. Lackenby, and P. Veličković. Expander graph propagation. In Learning on Graphs Conference, 2022.
M. Defferrard, X. Bresson, and P. Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems, 2016.
Di Giovanni, L.. Giusti, Barbero, G. Luise, P. Lio, and M. M. Bronstein. over-squashing in message passing neural networks: The impact of width, depth, and topology. In International Conference on Machine Learning, 2023. 3
D. Duvenaud, D. Maclaurin, J. Guzik, and P. Adams. Convolutional networks on graphs for learning molecular fingerprints. In Advances in Neural Information Processing Systems, 2015.
R. Gómez-Boobarelle T. Hirzel, A. Aspuru-
V. P. Dwivedi and X. Bresson. A generalization of transformer networks graphs. ArXiv preprint, 2020. 26
V. Dwivedi, A. T. Luu, Т. Laurent, Bengio, and Bresson. Graph neural networks with learnable structural and positional representations. In International Conference on Learning Representations, 2022a. 20
V. P. Dwivedi, L.. Rampášek, M. Galkin, A. Parviz, G. Wolf, A. T. Luu, and D. Beaini. Long range graph benchmark. Advances in Neural Information Processing Systems, 2022b. 2 3
24
D. Fasley, J. Kleinberg, et al. Networks, crowds, and markets. Cambridge Books, 2012.
F. Errica, H. Christiansen, V. Zaverkin, T. Maruyama. M. Niepert, and F. Alesiani. Adaptive message passing: A general framework to mitigate oversmoothing, oversquashing and underreaching.
arXiv preprint, 2023. g 20
B. Fatemi, El Asri, and S. M. Kazemi. Slaps: Self-supervision improves structure learning for graph neural networks. Advances in Neural Information Processing Systems, 2021. [8
12

---

B. Fatemi, S. Abu-El-Haija, A. Tsitsulin, M. Kazemi, D. Zelle, N. Bulut, J. Halcrow, and B. Perozzi. Ugsl: A unified framework for benchmarking graph structure learning. arXiv preprint. 2023, 18
M. Fey, J.-G. Yuen, and Weichert. Hierarchical inter-message passing for learning on molecular graphs. arXiv preprint, 2020. 18
L. Franceschi, M. Niepert, M. Pontil, and X. He. Learning discrete structures for graph neural networks. In International Conference on Machine Learning. 2019. [8
Frasca, Rossi, D. Eynard, B. Chamberlain, M. Bronstein, and F. Monti, Sign: Scalable inception graph neural networks. arXiv preprint, 2020.
F. Gama, A. G. Marques, G. Leus, and A. Ribeiro. Convolutional neural network architectures for signals supported on graphs. IEEE Transactions on Signal Processing, 67(4):1034 1049, 2019.
H. Gao and S. Ji. Graph U-Nets. In International Conference on Machine Learning. 2019. 18
Gasteiger, S. Weißenberger, and Günnemann. Diffusion improves graph learning. Advances in Neural Information Processing Systems, 32, 2019. 3 26
S. Geisler, A. Kosmala, D. Herbst, and S. Günnemann. Spatio-spectral graph neural networks. arXiv preprint, 2024.
8
Gilmer, S. S. Schoenholz, P. Riley, O. Vinyals, and G. E. Dahl. Neural message passing for quantum chemistry. International Conference on Machine Learning, 2017. T
18
L. Giusti, C. Battiloro, L. Testa, P. Di Lorenzo, S. Sardellitti, and S. Barbarossa. Cell attention networks. In International Joint Conference on Neural Networks, 2023a. 26
L. Giusti, T. Reu, F. Ceccarelli, C. Bodnar, and P. Lid. Cin++: Enhancing topological message passing. arXiv preprint, 2023b. 26
C. Goller and A. Küchler. Learning task-dependent distributed representations by backpropagation through structure. In International Conference on Neural Networks, 1996. 3
M. Grohe. Descriptive complexity, canonisation, and definable graph structure theory. Cambridge University Press, 2017. 20
M. Grohe. The logic of graph neural networks. In Symposium on Logic in Computer Science, 2021. 19
M. M. Gromiha and S. Selvaraj. Importance of long-range interactions in protein folding. Biophysical Chemistry, 77(1):49--6 1999.
B. Gutteridge, X. Dong, M. M. Bronstein, and F. Di Giovanni. Drew: dynamically rewired message passing with delay. In International Conference Machine Learning, 2023.
9
W. L. Hamilton, Z. Ying, and J. Leskovec. Inductive representation learning large graphs. In Advances in Neural Information Processing Systems, 2017. 3
X. He, B. Hooi, Laurent, A. Perold, Y. LeCun, and X. Bresson. generalization of vit/mlp-mixer to graphs. In International Conference on Machine Learning, 2023, 2
10
F. Hu, Y. Zhu, S. Wu, L. Wang, and T. Tan. Hierarchical graph convolutional networks for semi- supervised node classification. arXiv preprint, 2019. 18
W. Hu, M. Fey, M. Zitnik, Dong. H. Ren, B. Liu, M. Catasta, and Leskovee. Open graph benchmark: Datasets for machine learning on graphs. Advances in Neural Information Processing
Systems, 2020. 10
Huang, Z. Li, N. Li, Liu, and G. Li. Attool:: towards hierarchical feature representation in graph convolutional networks via attention mechanism. In IEEE/CVF International Conference Computer Vision, 2019, [8]
Huang, S. Zhang, C. Xi, T. Liu, and M. Zhou. Scaling up graph neural networks via graph coarsening. In SIGKDD Conference Knowledge Discovery & Data Mining, 2021. I8
13

---

B. E. Husic, N. E. Charron, D. Lemm, J. Wang. A. Pérez. M. Majewski. A. Krämer, Y. Chen, S. Olsson, G. de Fabritiis, et al. Coarse graining molecular dynamics with graph neural networks. The Journal of Chemical Physics, 153(19), 2020. 2
M. S. Hussain, M. Zaki, and D. Subramanian. Global self-attention as a replacement for graph convolution. In SIGKDD Conference on Knowledge Discovery and Data Mining, 2022. 3
K. Ishiguro, S.-i. Maeda, and M. Koyama. Graph warp module: an auxiliary module for boosting the power of graph neural networks in molecular graph analysis. arXiv preprint, 2019. 18
W. Jin, C. Coley, R. Barzilay, and T. Jaakkola. Predicting organic reaction outcomes with Weisfeiler- Lehman network. Advances in Neural Information Processing Systems, 2017. 10
W. Jin, Y. Ma, X. Liu, X. Tang, S. Wang, and J. Tang. Graph structure learning for robust graph
neural networks. arXiv preprint, 2020. 18
J. Jumper, R. Evans, A. Pritzel, T. Green, M. Figurnov, O. Ronneberger, K. Tunyasuvunakool,
R. Bates, A. Zídek. A. Potapenko, et al. Highly accurate protein structure prediction with alphafold. Nature, 596(7873):583-555) 2021.
K. Karhadkar, P. K. Banerjee, and G. Montúfar. FoSR: First-order spectral rewiring for addressing oversquashing in gnns. arXiv preprimt, 2022.
26
A. Kazi, L. Cosmo, S.-A. Ahmadi, N. Navab, and M. M. Bronstein. Differentiable graph module (dgm) for graph convolutional networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(2):100--161,, 2022. 18
S. Kiefer and B. D. McKay. The iteration number of Colour Refinement. In International Colloquium on Automata, Languages, and Programming, pages 73:1-73:19, 2020. 20
J. Kim, T. D. Nguyen, S. Min, S. Cho, M. Lee, H. Lee, and S. Hong. Pure transformers are powerful graph learners. arXiv preprint, 2022. 3
D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In International Conference
on Learning Representations, 2015. 20
T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
D. B. Kireev. Chemnet: A novel neural network based method for graph/property mapping. Journal of Chemical Information and Computer Sciences, 35(2):175-180, 1995. 3
R. Levie, F. Monti, X. Bresson, and M. M. Bronstein. CayleyNets: Graph convolutional neural networks with complex rational spectral filters. IEEE Transactions on Signal Processing, 67(1): 97-109, 2019. B
J. Li, D. Cai, and X. He. Learning graph-level representation for drug discovery. arXiv preprint, 2017. 18
M. S. S. Chen, Y. Zhang, and I. Tsang. Graph cross networks with vertex infomax pooling. Advances in Neural Information Processing Systems, 2020. [8
X. Li. Z. Zhou, J. Yao, Y. Rong, L. Zhang, and B. Han. Long-range neural atom learning for molecular graphs. arXiv preprint, 2023. 18
J. Liang, S. Gurukar, and S. Parthasarathy. Mile: A multi-level framework for scalable graph embedding. In AAAI Conference Web and Social Media, 2021.
18
M. Liu, Z. Wang, and S. Ji. Non-local graph neural networks. IEEE Transactions on Pattern Analysis
and Machine Intelligence, (2112):0227010222 2021. 3
N. Liu, X. Wang, I. Wu, Y. Chen, X. Guo, and C. Shi. Compact graph structure learning via mutual
information compression. In ACM Web Conference 2022, 2022a. 18
14

---

Y. Liu, Y. Zheng, D. Zhang, H. Chen, H. Peng. and S. Pan. Towards unsupervised deep graph structure learning. ACM Web Conference 2022, 2022b. [8]
L. Ma, C. Lin, D. Lim, A. Romero-Soriano, P. K. Dokania, M. Coates, Torr, and S.-N. Lim. Graph inductive biases in transformers without message passing. In International Conference on Machine Learning, 2023. 3
H. Maron, H. Ben-Hamu, H. Serviansky, and Y. Lipman. Provably powerful graph networks. In Advances in Neural Information Processing Systems, 2019a.
26
H. Maron, H. Ben-Hamu, N. Shamir, and Y. Lipman. Invariant and equivariant graph networks. In International Conference Learning Representations, 2019b. 26
C. Merkwirth and T. Lengauer. Automatic generation of complementary descriptors with molecular graph networks. Journal of Chemical Information and Modeling, 45(5):1159-1166 2005,
G. Mialon, D. Chen, M. Sclosse, and J. Mairal. Graphit: Encoding graph structure in transformers. arXiv preprint, 2021.
26
A. Micheli. Neural network for graphs: A contextual constructive approach. IEEE Transactions Neural Nenworks, 20(3):498-5111 2009. 3
A. Micheli and A. S. Sestito. A new neural network model for contextual processing of graphs. In Italian Workshop Neural Nets Neural Nets and International Workshop on Natural and Artificial Immune Systems, 2005.
P. Minervini, L. Franceschi, and M. Niepert. Adaptive perturbation-busel gradient estimation for discrete latent variable models. In AAAI, 2023. 4
F. Monti, D. Boscaini, J. Masci, E. Rodolå, J. Svoboda, and M. M. Bronstein. Geometric deep learning on graphs and manifolds using mixture model CNNs. In IEEE Conference on Computer Vision and Putlern Recognition, 2017.
C. Morris, M. Ritzert, M. Fey, L. Hamilton, J. E. Lenssen, G. Rattan, and M. Grohe Weisfeiler and Leman go neural: Higher-order graph neural networks. In AAAI Conference on Artificial Intelligence, 2019.
22
C. Morris, M. Kriege, Bause, K. Kersting, Mutzel, and M. Neumann. TUDataset: A collection of benchmark datasets for learning with graphs. arXiv preprint, 2020a. 9
C. Morris, G. Rattan, and Mutzel. Weisfeiler and Leman go sparse: Towards higher-order graph embeddings. In Advances in Neural Information Processing Systems, 2020b. 21
C. Morris, Y. Lipman, H. Maron, B. Rieck, N. M. Kriege, M. Grohe, M. Fey, and K. Borgwardt. Weisfeiler and Leman go machine learning: The story so far. arXiv preprint, 2021. 33
C. Morris, F. Geerts, J. Tönshoff, and M. Grohe. WL meet VC. In ICML, 2023. I
L. Müller, M. Galkin, C. Morris, and L. Rampášek. Attending to graph transformers. arXiv preprint, 2023. 7
R. Murphy, B. Srinivasan, V. Rao, and B. Ribeiro. Relational pooling for graph representations. In International Conference on Machine Learning, pages 4663-4673, 2019. 20
L. Müller and C. Morris. Towards principled graph transformers. In NeurlPS, 2024.
R. Namazi, E. Ghalebi, S. Williamson, and H. Mahyar. Smgrl: Scalable multi-resolution graph representation learning. arXiv preprint, 2022. 18
M. Neumann, R. Garnett, C. Bauckhage, and K. Kersting. Propagation kernels: efficient graph kernels from propagated information. Machine learning, 102:209- 245, 2016. 26
M. Niepert, Minervini, and L.. Franceschi. Implicit MLE: Backpropagating through discrete exponential family distributions. Advances in Neural Information Processing Systems, 2021. 4
15

---

P. A. Papp, K. Martinkus, L. Faber, and R. Wattenhofer. DropGNN: Random dropouts increase the expressiveness of graph neural networks. Advances in Neural Information Processing Systems, 2021. 26
S. Park, N. Ryu, G. Kim, D. Woo, S.-Y. Yun, and S. Ahn. Non-backtracking graph neural networks. arXiv preprint, 2023. 8
H. Pei, B. Wei, K. C.-C. Chang, Y. Lei, and B. Yang. Geom-gen: Geometric graph convolutional networks. In International Conference on Learning Representations, 2020. 26
T. Pham, T. Tran, H. Dam, and S. Venkatesh. Graph classification via deep learning with virtual nodes. arXiv preprint, 2017. 18
O. Platonov, D. Kuznedelev, M. Diskin, A. Babenko, and L. Prokhorenkova. A critical look the evaluation of gnns under heterophily: Are we really making progress? arXiv preprint, 2023. 20
C. Qian, A. Manolache, K. Ahmed, Z. Zeng, G. V. den Broeck, M. Niepert, and C. Morris. Proba- bilistically rewired message-passing neural networks, 2023. 5
T0
20
26
C. Qian, D. Chételat, and C. Morris. Exploring the power of graph neural networks in solving linear optimization problems. In AISTATS, 2024.
L. Rampášek and G. Wolf. Hierarchical graph neural nets can capture -angeragee interactions. In IEEE International Workshop on Machine Learning for Signal Processing, 2021. T8
L. Rampášek, M. Galkin, V. Dwivedi, A. T. Luu, G. Wolf, and D. Beaini. Recipe for general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 2022.
26
E. Ranjan, S. Sanyal, and P. Talukdar. Asap: graph representations. AAAI Conference on Artificial Intelligence, 2020. 18
Adaptive structure aware pooling for learning hierarchical
E. Rosenbluth, J. Tönshoff, M. Ritzert, B. Kisin, and M. Grohe Distinguished uniform: Self-
attention virtual nodes. In International Conference Learning Representations, 2024.
18
A. Saha, O. Mendez, C. Russell, and R. Bowden. Learning adaptive neighborhoods for graph neural networks. arXiv preprint, 2023. [8
M. G. Saunders and G. A. Voth. Coarse-graining methods for computational biology. Annual Review of Biophysics, 42:73-93, 2013. 2
F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1): 2008
M. Schlichtkrull, N. Kipf, P. Bloem, R. van den Berg. I. Titov, and M. Welling. Modeling relational data with graph convolutional networks. In The Semantic Web, pages 593-607, 2018.
N. Shervashidze, S. Vishwanathan, T. Petri, K. Mchlhorn, and K. Borgwardt. Efficient graphlet kernels for large graph comparison. In AISTATS, 2009. 26
N. Shervashidze, P. Schweitzer, E. J. Van Leeuwen, K. Mehlhorn, and K. M. Borgwardt. Weisfeiler- lehman graph kernels. Journal of Machine Learning Research, 12(9), 2011. 26
H. Shirzad, A. Velingker, B. Venkatachalam, D. J. Sutherland, and A. K. Sinop. Exphormer: Sparse transformers for graphs. arXiv preprint, 2023. 2
J. Southern, F. Di Giovanni, M. Bronstein, and F. Lutzeyer. Understanding virtual nodes: Over-
smoothing, oversquashing, and node heterogencity. arXiv preprint, 2024. & 18
A. Sperduti and A. Starita. Supervised neural networks for the classification of structures. IFEE Transactions Neural Networks, 8(3):714-35, 1997.
16

---

J. Topping, F. Di Giovanni, B. P. Chamberlain, X. Dong, and M. M. Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. arXiv preprint. 2021.
Tönshoff, M. Ritzert, E. Rosenbluth, and M. Grohe. Where did the gap go? reassessing the
long-range graph benchmark. arXiv preprint, 2023. 8 TO
P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio. Graph attention networks. In International Conference on Learning Representations, 2018. [
B. Weisfeiler and A. Leman. The reduction of a graph to canonical form and the algebra which
appears therein. nti, Series, 2(9):12-16, 1968. 3 19
Wong. E. J. Zheng. A. Valeri, N. M. Donghia, M. N. Anahtar, S. Omori, Li, A. Cubillos-Ruit Ruizz, A. Krishnan, W. Jin, A. L. Manson, J. Friedrichs, R. Helbig, B. Hajian, D. K. Fiejtek, F. F. Wagner,
H. H. Soutter, A. M. Earl, J. M. Stokes, I.. D. Renner, and J. J. Collins. Discovery of structural
class of antibiotics with explainable deep learning. Nature, 2023. [
Z. Wu, P. Jain, M. Wright, A. Mirhoseini, J. E. Gonzalez, and I. Stoica. Representing long-range context for graph neural networks with global attention. Advances in Neural Information Processing Systems, 2021.
S. M. Xie and S. Ermon. Reparameterizable subset sampling via continuous relaxations. International Joint Conference on Artificial Intelligence, 2019.
K. Xu, C. Li, Y. Tian, T. Sonobe, K.-i. Kawarabayashi, and S. Jegelka. Representation learning on graphs with jumping knowledge networks. In International Conference on Machine Learning. 2018.
K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
9 10 26
C. Ying, T. Cai, S. Luo, S. Zheng, G. Ke, D. He, Y. Shen, and T.-Y. Do transformers really perform badly for graph representation? Advances in neural information processing systems, 34: 28877-28888, 2021. 26
Z. Ying. J. You, C. Morris, X. Ren, W. Hamilton, and J. Leskovec. Hierarchical graph representation learning with differentiable pooling, Advances in Neural Information Processing Systems, 2018.
18
T. Younesian, T. Thanapalasingam, E. van Krieken, D. Daza, and P. Bloem. GRAPES: Learning to sample graphs for scalable graph neural networks. arXiv preprint, 2023. 18
D. Yu, R. Zhang, Z. Jiang. Y. Wu, and Y. Yang. Graph-revised convolutional network. European Conference Machine Learning and Knowledge Discovery in Databases, 2021. 18
M. Zhang, Z. Cui, M. Neumann, and Y. Chen. An end-to-end deep learning architecture for graph
classification, In AAAI Conference on Artificial Intelligence, 2018. 26
T. Zhao, Y. Liu, L. Neves, O. Woodford, M. Jiang, and N. Shah. Data augmentation for graph neural networks. In AAAI Conference on Artificial Intelligence, 2021.
18
Z. Zhong, C.-T. Li, and J. Pang. Hierarchical message- message-passing graph neural networks. Data Mining and Knowledge Discovery, 37(1):381-400) 2023. 18
Z. Zhou, S. Zhou, B. Mao, X. Zhou, J. Chen, Q. Tan, D. Zha, Y. Feng, C. Chen, and C. Wang. OpenGSL: A comprehensive benchmark for graph structure learning, 2023a. 18
Z. Zhou, S. Zhou, B. Mao, X. Zhou, J. Chen, Q. Tan, D. Zha, C. Wang, Y. Feng, and C. Chen. OpenGSL: A comprehensive benchmark for graph structure learning. arXiv preprint, 2023b. T8
D. Zou, H. Peng, X. Huang, R. Yang, J. Li, Wu, C. Liu, and P. S. Yu. SE-GSL: A general and effective graph structure learning framework through structural entropy optimization. arXiv preprint, 2023. [8
17

---

A Additional Related Work
In the following, we discuss related work.
Graph Structure Learning Graph structure learning (GSL) is closely related to graph rewiring, where the primary motivation is refining and optimizing the graph structure while jointly learning graph representations (Zhou et al. 2023a]. Several methods have been proposed in this field. Jin et al.. [220]] develop a technique to optimize graph structures from scratch using specific loss function bias, while the general approach is using edge scoring functions for refinment (Chen al.. 2020 Yu et al. 2021| Zhao et al.] 2021). but discrete sampling methods have also been applied. More specifically, DGM [Kazi et al. [222]] predicting the latent graph structure by leveraging Gumbel discrete sampling, while Franceschi et al. [2019] is learning Bernoulli distribution via Hypergradient Descent. [Shaa et al. [023] learns adaptive neighborhoods for trajectory prediction and point cloud classification by sampling through the smoothed- -eaviiide function, while Younesian et al. [2023] samples nodes that are used for downstream tasks using GFlowNets. Some GSL techniques also employ unsupervised learning [Zou ct al. 2023 Fatemi et al. 2021 Liu ct al. 2022a b). We encourage
the reader to refer to Fatemi et al. 2023 Zhou et [023b for detailed surveys regarding GSL..
Our proposed IPR-MPNN is different from other GSL framework in two main ways: (1) instead of sparsifying the graph using randomized k-NN approaches independent Bernoulli random variables, we learn probability mass function with exactly-k constraints (Ahmed et al. 2023). Moreover, don't aim to discover the graph structure by considering a fully-connected latent graph from which we sample new edges [Qian et al. 2023). instead we introduce sparse connections from base nodes to virtual nodes, with complexity N k (2) GSL methods do not investigate exact sampling of the exactly-k distribution; however, one of our aims is to demonstrate that these techniques can significantly alleviate information propagation issues caused by inadequate graph connectivity, such as over- squashing and under-reaching.
Moreover, IPR-MPNN also differs from previous graph rewiring method, specifically PR-MPNN [Qian et al.; 2023). First, we rewire the graph implicitly by connecting nodes to virtual nodes, respecting the original graph structure. Besides, we show significant run-time advantage in that our worst-case complexity is sub-quadratic, while PR-MPNN optimally needs to consider n node pairs for n--order graph.
Hierarchical MPNNs Our method draws connections to hierarchical MPNNs. The hierarchi- cal model initially emerged in graph-level representation learning, as seen in approaches like AttPool [Huang et al. 2019). DiftPool (Ying et al. 2018), and ASAP (Ranjan et al. [0220. Further developments, such as Graph U-Net [Gao and Jil 2019]. H-GCN (Hu et 2019), and GXN (Li et al. 2020). introduced top-down and bottom-up methods within their architectures. However, they did not incorporate virtual node message passing. Other works create hierarchical MPNNs while incorpo- rating hirarhhiraac message passing. For example, Fey et al. [2020) introduced
on molecular learning, using a junction tree to create a higher hierarchy of the original graph and do inter-message passing between the hierarchies. Raappšsk and Wolf [20TT] proposed HGNet for long-range dependencies, generating hierarchies with edge pooling and training with relational GCN. Zhong et al. 2023) designed HC-GNN, more efficient than HGNet, for better node and higher level resolution community representations. These hierarchical MPNNs require well-chosen heuristics for hierarchy generation. Using an auxiliary supernode is particularly prominent in molecular tasks GGimmrr et al. 2017 Pham et al. 2017 Li et al.) 2017). which involves adding a global node to encapsulate graph-level representations. Further advancements in this area, as suggested in [Battaglia et al. (2019). have enhanced supernode MPNNS with a gating mechanism. Theoretically, Cai et al. [2023] proves MPNN with virtual node can simulate self-attention, which is further investigated in Rosenbluth et al. 2024 In addition, [Southern] al. 2024) studied the effect of MPNNs using virtual node on over smoothing and oversquashing
let al. 2018). and developments like
Simu Itnuulann,usly, the recent study by Li et al. (2023) has introduced the concept of a collection of supernodes, termed "neural atoms," " which incorporate supernode message passing with an attention mechanism. Moreover, the idea of coarsened hierarchical graph has become widely employed in scalable MPNN training and graph representation learning, as evidenced by works like Huang et al. [2021] Liang et al. [] Namazi et al. (2022). Unlike existing hierurchical MPNNs, our IPR- MPNN uniquely leverages differential k-subset sampling techniques for dynamic, probabilistic graph rewiring and incorporates hierarchical message passing in an end-to- -nd trainable framework. This
18

---

approach enhances graph connectivity and expressiveness without relying on predefined heuristics or fixed structures.
B Extended Notation
A graph G a pair E(G)) with finite sets of vertices or nodes V(G) and edges B(G) S
If not otherwise stated, we set n == [V(G)], and the graph is of onder n. We also call the graph G an n-order graph. For ease of notation, we denote the edge (u.v) in E(G)
{ Hu, of C [VG) u 4
by (u, v) or (v. u). A (vertex-Jlabeled graph G is triple E(G)) {) with a (vertex-)lad laael function l: V(G) + N. Then ((v) a label of v, for in V(G). An attributed graph G is a triple (V(G), o) with graph (V(G), E(G) and (vertex-)attribee some d > 0. That is, contrary to labeled graphs, we allow for vertex annotations from an uncountable set. Then (v) is an attribute or feature of c, for o in V(G). Equivalently, we define an n-order attributed graph G = (V(G), E(G), o) as a pair G = (G, L), where G = (V(G), E(G) and L in Raxd is a node feature matrix. Here, we identify V(G) with [n]. For a matrix L in Rx xd and e in [n]. we denote by L, in Rixd the uth row of L such that Ly. == a(v). Furthermore, we can encode an n-order graph G via an adjacency matrix A(G) E [0, where Aig = 1 if, and only, if (i,5) E E(G). We also write Rd for Rixd
function V(G) T Ixdd for
The neighborhood of in V(G) is denoted by N(v) = (v))===EV(G)) (v, u) B(G)) and the degree of a vertex v is IN [.)).. Two graphs G and H are isomorphic and we write G ~ H if there exists a bijection y:: VGG) + V(H) preserving the adjacency relation, i.e.. (u, v) is in E(G) if and only if (p(u), (Q)) is in E(H). Then y is an isomorphism between G and H. In the case of labeled graphs, we additionally require that l(v) = I(p(()) for e in VGG), and similarly for attributed graphs.
A node coloring is function e: V(G) + Rd, d > O, and we say that c(v) is the color of E V(G). node coloring induces an edge coloring Eg: E(G) + N, where (u, v) + {c(w), c(t)} for (u, v) E E(G). A node coloring (edge coloring) e refines node coloring (edge coloring) d, written E d if c(t) = c(w) implies d(v) = d(ww) for every v, w,w- E V(G) (U, w E E(G)). Two colorings are equivalent if
and d _ c, in which case we write = d. A color class Q S V(G) of node coloring c is a maximal set of nodes with c(v) = c(w) for every v, w E Q. A node coloring is called discrete if all color classes have cardinality 1.
C The 1-dimensional Weisfeiler-Leman algorithm
The 1-WL or color refinement is fundamental, well-studied heuristic for the graph isomorphism problem, originally proposed by WWisfeiler and Leman| [1968) | The algorithm is an iterative method starting from labeling updating the color of a node with its color as well as its neighbors' colors. During the iterations, two vertices with the same label get different labels if the number of identically labeled neighbors is unequal. Each iteration ends up with a vertex color partition, and the algorithm terminates when the partition is not refined by the algorithm, i.e., when stable coloring or stable partition is obtained. We can finally conclude that the two graphs are not isomorphic if the color partitions are different, or the number of nodes of specific color is different. Although in Cai al. (192 the limitation is shown that 1 1-WL algorithm cannot distinguish all non-isomorphic graphs, it is a powerful heuristic that can succeed 1980].
coloring vertices in both graphs with degrees other information, and
broad class of graphs (Arvind al.. 2015 Babai and Kucera 1979 Babai et al.
Formally, let G = (V E) be labeled graph. In each iteration, t > 0, the 1-WL computes a vertex coloring C.: VVG) + N, depending on the coloring of the ego node and of the neighbors. That is, in iteration & > 0, we set
C. (v) = RELABEL ((GLI(W) (CL)(()) / N()B))
'Strictly speaking. the 1-WL and color refinement are two different algorithms. That is the 1-WL considers neighbors and non- non-neighbors to update the coloring, resulting in a slightly higher expressive power when distinguishing vertices in a given graph: see Grohe [2021] for details. Following customs in the machine learning literature, we consider both algorithms to be equivalent.
19

---

for all vertices v E V(G), where RELABEL injectively maps the above pair to unique natural number, which has not been used in previous iterations. In iteration 0, the coloring Cj == & is used. To test whether two graphs G and H are non-isomorphic, we run the above algorithm in "parallel" on both graphs. If the two graphs have a different number of vertices colored E N at some iteration, the 1 1-WL distinguishes the graphs as non-isomorphic. Moreover, if the number of colors between two iterations, t and (t + 1), does not change, i..., the cardinalities of the images of C7 and Ci are equal, or, equivalently,
[v) = (c) = C++(()) - C++((w),
for all vertices v and w in V(GUH), then the algorithm terminates. For such t, we define the stable coloring C (v) (v), for E V(GÚH). The stable coloring is reached after at most max([V [VH)I iterations [Grohe 2017
Kiefer and McKay, 2020]. A function f: V(G) -
R. for d > is 1- I-WL-equivalent
C2
D Additional Empirical Results and Experimental Details
Here, we provide additional empirical results and experimental details.
virtual nodes with hidden dimension twice as large as the base nodes. We randomly initialize the features of the virtual nodes. For the upstream and downstream models, we do hyperparameter search; see Table A5 We use RWSE and LapPE positional encodings (Dwivedi et al., 2022a] for all of our experiments as additional node features, except for the synthetic TREES datasets [Alon and Yahav 2021 Qian al., 2023). EXP [bbooud et al. 2020) and CSL [Murphy et al.] 2019]. as well as node classification tasks on heterophilic datasets. For LEAFCOT,,,, we use a single one-layer downstream GINE network, and for PREES-NEIGHBOURSSN tree. For both TREES datasets, we have hidden dimension of 32 for the original nodes. For most graph-level tasks, we apply a read-out function over the final pooled node embeddings, virtual node embeddings, or combination of both. Distinctly, for PEPTIDES-FUNC we apply read-out functions and use a supervised loss on all the intermediate embeddings, similarly to cofErrica et al. [2023]. We compute the logarithm of the symmetric sensitivity between the most distant two nodes u, 2 in Fig. P
Details In all of our real-world experiments,
we use n + 1 layers, where n is the depth of the
similar to Errica et al. [2023). i.e. 1, and the total Effective Resistance of the datasets in Fig. as in Black et al. [2023]. We optimize the network using Adam Kingma and Ba 2015) with cosine annealing learning rate scheduler. We use the official dataset splits when available. Notably, for
the TUDATASET. WEBKB datasets [Craven et al. 1998) and heterophilic datasets proposed in
Platonov et al. 22233. we perform 10-Fold Cross- Validation and report the average validation performance, similarly to the other methods that we compare with. For some experiments, we search for hyperparameters using grid-search, for more details please see Table A5 All experiments were performed on a mixture of A10, A A100, A5000, and RTX 4090 NVIDIA GPUs. For each run, we used most eight CPUs and 64 GB of RAM.
Heterophilic datasets We exhibit experimental results on the WEBKB datasets in Table A6 and on the heterophilic datasets in Table A7 Our method exhibits significant improvement WEBKB datasets as well as ROMAN-EMPIRE datasets compared with other MPNN baselines.
Ablations We conduct ablation experiments on the number of virtual nodes and repetition of samples, see Table A8
E
Expressivity
We first discuss three scenarios where we (1) separate isomorphic graphs with the same non-discrete stable 1-WL colorings (Figure A5). (2) separate nom-isomorphic graphs with the same non-discrete 1-WL colorings (Figure A6), and (3) preserve isomorphisms between isomorphic graphs with the same discrete 1-WL colorings (Figure A7p. For each of the three examples, we assume two unique virtual nodes with l- 1, i.e., we sample single edge between base node and virtual node.
For example (1), consider Figure [A5] and assume that, for each color class, the upstream MPNN randomly selects virtual node, i.c., we have uniform prior. Since both base nodes have the same
20

---

1.0
0.8
Accuracy
0.6
Trans former
0.4
IPR-MPNN
GCN
GGNN
Problem radius
Figure A4: IPR-MPNN obtains perfect accuracy on TREEES-NEIGHROSSMATCH 2021 for a depth up 6.
Alon and Yahav
a
(b)
(c)
(d)
Figure A5: Possible new configurations.
color class, each base node connects to one of the virtual nodes uniformly at random. The scenario where two graphs remain isomorphic is when they connect to exactly the same virtual nodes or either connect as in case (a) or (b). Therefore, we have a high probability of separating these isomorphic graphs.
For example (2), we again produce uniform priors for each color class of the graphs Figure A6 Once again, there is high probability of separation. One possible configuration that separate between the two graphs is shown in Figure [6 where in the first graph (a), the nodes colored with 1 get assigned virtual node 4, while the nodes colored with are assigned to virtual node In the second graph (b), all nodes get assigned to the same virtual node 3.
consider producing priors that assign, with high probability, the same virtual node to all of the nodes that are in color classes of cardinality This approach ensures that the discretely-colooe
For example (3) in Figure A7
graphs remain isomorphic with high probability.
The intuition is that if we want to distinguish between graphs that have the same 1-WL stable color partitioning, the upstream model needs to produce "uninformative" prior weights for some color classes. However, preserving isomorphisms is most likely when the nodes in the same color class in the two graphs get assigned to the same virtual nodes. Since our upstream model is as powerful as 1-WL, we can control the prior distribution for the color classes but not for individual nodes, therefore we can only guarantee high assignment probabilities for nodes in color classes of cardinality 1.
Next, we formally argue that we can preserve. with arbitrarily high probability, isomorphisms between graphs that have the same discrete stable 1-WL color partitions, as well as isomorphisms between subgraphs with the same discrete stable 1-WL color partitions.
Lemma E.1. Let G and H be a puir of graphs with the same 1-WL graph coloring, i.e,, they are WL non distiiiiingui...be.. Let le N, let G¹ be color-induced subgraph where V = {o e V(G) (v) = k) C V(G), and V(H') similarly. Then the subgraphs induced by V(G', and V(H)) are still not 1 WL-distinguishabe.
Proof. To prove the lemma, we use concept of an unrolling tree for a node; see, e.g., Morris et al.) 2020bb. That is, for node, we recursively unroll its neighbors, resulting in tree. It is easy to see that two nodes get the same colors under 1-WL and only if such trees are isomorphic; see Morris
al. (2020b] for details.
21

---

4
aa)
(b)
Figure A6: Separating graphs with the same stable 1-WL color.
2
8
3
Figure A7: An example where we preserve the isomorphism when all the nodes from the initial graph are discretely colored. For each base node, we assign high probability of connecting to the same virtual node (node 8).
Consider nodes v, V(G (V that share the same stable 1-WL coloring k. Based on the above, and u must have isomorphic unrolling trees. Now remove subgraphs the two trees not rooted at the vertex with color k. Since both and have isomorphic unrolling trees, the resulting trees are isomorphic. Hence, running 1-WL on top of G¹ and Hy will still not distinguish them.
UVG))
Lemma E.2. Let G and H pair of graphs with the same stable coloring under 1-WL If we add finite number of virtual nodes on both graphs C(G), C(H), and connect these virtual nodes based on WL colors of the original graphs, ie.. two equally colored vertices get assigned the same virtual nodes. Then, the augmented graphs G and H have the same stable partition.
Proof. The proof is by straightforward induction on the number of iterations using the fact that two nodes with the same color will be assigned to the same virtual node. That is, the neighborhood of two such nodes is extended by the same nodes.
Besides, we leverage the following result by Qian et al. [2033 Morris et al. 2019
Lemma E.3 (Qian et al.
2023 Morris et al. 2019 Lei G be n-order graph and let V(G) Rdd d > O, be 1- WL -eeequivalent node coloring. Then, for all = > O, there exists a (permutation- equivariant) MPNN f: V(G) Rd, such that
max HEV(G)
(1(()) <E.
Theorem E.4. Let k > O, E E (0, and G, H be two graphs with identical 1- 1-WL stable colorings. Let M be the set of ordered virtual nodes, Va and VH the subset of nodes G and H that have color class of cardinality 1, with [Vl= [Vn| = d, and WG. WH the subset of nodes that have a color class of cardinality greater than 1, with Wal = |Wn n. Then, for all choices of 1- WL-equivalent functions f.
22

---

(1) there exists conditional probability mass function P(o.k) that does not separate G[Vcl and
[[ with probability at least 1 -.
(2) There exists a conditional probability mass function P(o.)) that separates G[Wa] and H[ H with probability strictly greater than 0.
Proof. Let M = {UI,,... J be the set of m ordered virtual nodes and d = VVll = |V To prove this theorem, we leverage Lemma B.3 to assign distinct and arbitrary priors for every color class.
For (1), we know that since G and H have identical 1-WL stable colorings and Vg. Vи have a color class of cardinality 1, then G[Va] and [[VH] must be discrete and isomorphic. Using Lemma E.3 we can obtain an upstream MPNN that assigns a sufficiently high prior 8, such that, when we sample from the exactly-k distribution, can assign the corresponding virtual nodes to base node with probability at least -1-
To demonstrate the existence of such set of priors 0, let ô E (0, 1) and S C M be subset of virtual nodes. Let w/ > W2 be two prior weights such that 0, wi U/ S, and 0; = W2 E M \ S. We have that
m -
(S) 2 8
82,
1:
==
with the upper bound [Qian et al. 2023
(m)-1) w
(m²
2 wt +
Thus, @ exists and can be obtained using this inequality.
Next, we 8 VI Consequently, the probability that the sampled virtual nodes are identical
for both graphs is at least WI-E" 2d 1 e. Finally, using Lemma E.2 we know that the two graphs also retain their color partitions and remain isomorphic with probability at least 1-
For (2), it is easy to see that, for any prior weights f that we assign to the color classes of cardinality greater than 1, there is at least one configuration separating the two graphs. For instance, since k < m, we can separate G[Wa] [[Wr] v by assigning the first k virtual nodes {1,..., k} to every node in G[Wa]. but have least one node in H[ be assigned
the next k nodes {2, (2.... k 1}. More Om.
and 0,, be an uniform prior, i.e. 0 02 Again, Lemma F.3 and obtain distribution pe arbitrarily close to the uniform distribution. Then, the probability of making the two graphs distinguishable by obtaining the mentioned example greater than which is strietly greater than 0. For a visual example, see Figure A6
concretely, let e E (0, 1), E G[Wa]
The next Corollary follows directly from Theorem and recovers Theorem 4.1 from Qian et al. (2033..
Corollary E.4.1. For sufficiently large n. for every 6 E (0. a set M of ordered virtual nodes, and l: >> 0, we have that almost all pairs, in the sense of Babai al. (1980), of isomorphic n-order graphs G and H and all there exists probability mass function P)) that separates the graph G and H with probability at mosts s with respect to
1 -LL-euvvallent functions f: 2, - / d > O,
Proof. We know from Babai et al. 1980 that an 1-WL-equivalent algorithm will produce a discrete color partition for almost all pairs of isomorphic graphs G. H of sufficient size. We use Theorem E.4 and set WG Wi = ( and conclude that we maintain isomorphisms between almost all isomorphic graphs.
23

---

Limitations
limitation of our approach is the assumption that the number virtual nodes m is significantly smaller than the total number of nodes n. As the number of virtual nodes increases, the runtime also expected rise (see Table for detailed example). In the worst-case scenario, where m n, our method exhibits quadratic complexity. However, in all real-world datasets we have tested, the required number of virtual nodes for achieving optimal performance low. For more information, refer to Table A5 Another question is whether IPR-MPNNs can perform well on node-level tasks. We have designed our rewiring method specifically to solve long-range graph-level tasks (such as the tasks on the molccular datasets from the LONG-RANGE GRAPH BENCHMARE (Dwivedi et al.) (022b]). Nevertheless, PPRMMPNNs and adaptations might also work on node-level tasks, but we leave this question open for further work.
24

---

SAMPLES TRAINTESST
2
2
2
2
2
15
VIRTUAL NODES
2
2
2
2
2
2
2
8
2
2
3
3
K
LAYERS SOSNSOONNSSSSS CONSSTAAAA
(3.5,8) 8,
(3,5.8)
(3.5.8)
(3,5,87
(3.5.87
(3,5,81
(N+1)
10
6
Table AS: Overview used syperparameters.
HIDDEN VIRUUAA
[64, (28,256)
(64,128 124.128]
(64, 164,128] 128
(64, 128
(64, 128
(64, 128
256
256
256
256
64
64
128
284
284
284
256
384
256
128
HIDDEN DOW
[64, 12,128,22 (9,1228,566 256)
[64,128)
(64, (64,128] 128]
(64, 128
[64, 128
(64, 128]
128
128
128
128
32
32
64
64
256
256
128
256
256
256
256
LAYERS UISTREAM
(0.2.5)
[0.2,5]
[0.2.5]
[0,2.5)
(0.2.5)
[0.2.5]
HIDDEN HIDDENOPSTREAN OPSTREAM
(64,128]
[64,128]
(64,128)
(64, 128
(64, 128
(64. 128
128
128
128
128
32
32
64
64
128
128
64
64
128
64
128
TREES-LAN LEAFMATCH--
PEPTIDES-STIE S STRUCT
TREES- LEAFCOUNT
AMAZON- RATINGS
OGBG-MOLIHN MOLHIV Q.99
PEPTIDES FUNC
ROMAN-FE EMPIRE
MINESWEEPER
WISCONSIN
TOL TOLOKERS
DATASET
MUTAG
PTC_NT MR
NCT109
PROTEINS
CORNELL
TEXAS
ZINC
NCI1
CSL
ExP
25

---

Table A6: Performance comparison of different models on the Comell, Texas, and Wisconsin heterophilic datasets.
MODEL
CORNELL
TEXAS f
WISCONSIN t
GINE 2019
0,448 #0.073
0.650
0.517=0.054
SDRF 2021
0.546 #0,004
0.644 #0.004
0.555 #0,003
DIGL 2019
0.582 #0.005
0,620 #0.003
0.495 #0.003
GEOM-GCH 2020
0.608 =N/A
0.676 #NIA
0.641 #N/A
DIFFW IRE 2022
0,690 20.044
N/A
0.791 20.021
GRAPHORMER 2021
0.683 =0
0.767 =0.017
0.770 20.019
GPS 2022
0.718 00.024
0,773 20.013
0.798 20.090
(OURS)
0.764 +: 056
0.808 =0.052
0.804 #0.052
Table A7: Performance comparison between the base GINE and IPR-MPNN on recently-proposed heterophilic datasets.
MODEL
ROMAN-EMPIRE
TOLOKERS
MINESWEEPER
AMAZON-RATINGE
GINE (BASE)
0. 0.47622 n06
0.807
0. 0.709
0.488 006
IPR- MPNN (OURS)
0.839 10:9 006
0.000
0.88710.006
0. 0.480=20.007
Table A8: Performance between virtual node connected the entire original graph (IVN-FC) and IPR-MPNNs with two virtual nodes with one sample (2VN1S) and two samples, respectively (2VN2S).
MODEL
ZINC
OGB-MOLHIV
PEPTIDES-FUNC
PEPTIDES-STRUCT
IVN FC
0.074 10.002
0.753
10.011
0.7039
20,0046
0.2435 2.0.0077
2VNIS
0.072 +0.004
0.762 10.014
0.7146 20.0055
0.2472 1:0.0144
2VN2S
0.067 +0.001
0.788 #0.006
0.7210 #0,0039
0.2422 +000007
2VN4S
0.7145 #0.0020
Table A9: IPR-MPNN compared to other approaches as reported in Giusti et al. [2023b] Karhadkar
al. 2022 Papp et al. [001T] the best model, blue the second second-best, and red the third. Our rewiring technique obtains the best
Rodríguez et al. [2022], ,iin al. [023 Green indicates
performance on every dataset, except for MUTAG, where PR-MPNN obtains a slightly better average mean score and standard deviation.
MODEL
MUTAG
PTC_MR
PROTEINS
NCII
NC1109
GK (c: = 3)
2009
81.4g1.7
55.7+0.5
71.420.
62.5
62.420.5
PK 22016
76.0=2.7
59.5+2.
73.7
82.5
N/A
WL KERNEL 2011
90.4
59.944.3
75.0a3.1
86,021.
N/A
DGCNN 2018
85.821
58.6125
75.5200
74.4105
N/A
IGN 2019B
83.9=13.0
58.5+6..
76.6=5.5
74.3+27
72.8
GIN 9
89. $9.425.6
64.617.0
76.2=a.8
82.7+1.
N/A
PPGNS
A
90.62x.7
66.216.
77.2
83.2
82.2a1.4
NATURAL
GN 2020
89. 4=1.6
66. 8+1.7
71.7=11.
82,4+1.
83 13.0
2022
92.227.5
68.247.3
76.625.0
83.5
83.5
CIN 2021
92.7-6.1
68.245.8
77.0:4.5
83.6114
84.0=16
CAN
2023A
94.1
72.8+8.a
78.2=2.0
84,5+1.
83.6a12
CIN
202,50
94.4sa.
73.2
80.5
85,3
84.5
GT 2020
83.99 83.926.5
58.418.2
70.1 2332
80.0a1a
N/A
GRAPHIT
2021
90.5=7.0
62.0+9.4
76.2
81.4
N/A
FOSR
2202
86.2a1.5
58.511.7
75.1
72.940.
71. 1206
DROPGINN 2021
90.4=7.0
66.3
76.3
81,6118
80.8=24
GAP(R) 2022
86. $6.9=4.0
N/A
75.0=s.0
N/A
N/A
GAP(N)
86.924.
N/A
75.3
N/A
N/A
PR-MPNS
2023
98.422.
74,313.
80.7
85.6108
84.6212
IPR-MPP MPNN (OURS)
98.0=3.4
75.8
85.424.
86.2
86.5
26

---

Table A11: Comparison between the base GIN model w/wo positional encoding and IPR- MPNN on CSL dataset. For IPR-MPNN* we pre-calculate the graph partitioning for each data instance, and label each node with its partition
Table A10: Comparison between the base GIN
model, its variants, and IPR-MPNN on the EXP dataset.
MODEL
ACCURACY t
ID.
GIN
0.511#0.021
MODEL
ACCURACY
GIN ID-GNN
1.000+10.000
GIN
0.100:+0.000
PR-MPNN
1.000+0.000
GIN POSENC
1.000-10.000
IPR-MPNN (OURS)
1.000:10.000
PR-MPNN
0.998+
IPR-MPNI (OURS)
0.987+000013
IPR-MPNN' (OURS)
1.000+0.0000
Table A12: More memory consumption details together with train and validation times per epoch seconds. We compare to the base GINE model, various variants of the SAT Graph Transformer, GraphGPS, and the PR-MPNN rewiring technique. IPR-MPNIS maintain low memory usage while also being significantly faster when compared to the Graph Transformers and PR-MPNN. The experiments were performed on the OGBG-MB MOLHIV dataset, with the same batch size and the same machine that contains an Nvidia RTX A5000 GPU and an Intel i9-1 1900K CPU.
MODEL
#PARAMS
V. NODES
SAMPLES
TRAIN S/EP
VAL S/EP
MEM. USAGE
GINE
502k
3.1920.03
0.20+0.01
0.5GIB
K-ST SATaINE
506k
16.54-0.13
4.78+0.01
11.0GIB
K-SG SATGINE
481k
97. 90.34
5.5710.01
8.5GIB
K-ST SATPNA
534A
90.34 00.29
4.8510.01
10.1GIB
K-SG SATPNA
5091:
118.75 110.5
5.84
9.1GIB
GRAPHGPS
558k
17.02=0.70
0.6540.06
6.6GIB
PR-MPNNGHE
582k
20
15.20
1.00
0.8GIB
PR-MPNNMEL
582k
15.01
1.08
0.9GIB
PR-MPNN
582k
20
15.98
1.07
2.1GIB
IPR-MPNN STM
548k
7.31
0.34
0.8GıB
PR-MPNNs5h SIM
548k
7.37=0.08
0.35+0.01
0.8GıB
IPR IPR-MPNNGG SIM
548k
10
7.68
0.35
0.9G1B
IPR-MPNN SIM
5491:
10
8.64+4.06
0.35
1.1GIB
IPR-MPNN- STM
5449k
9.41
0,43
1.2GIB
27

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We describe the IPR-MPNN in detail in Section and explain its sub-quadratic running time in the same section. Moreover, in Section 4, prove that the architecture overcomes expressivity limitations of standard MPNNs. Finally, in Section 5, we show empirically that IPR-MPNNs mitigate underreaching and over-squashing effects.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We describe limitations of IPR-MPNNs in Section F
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
28

---

Answer: [Yes]
Justification: In the appendix, we formally prove all theorems stated Section 4. All theorems contain all used assumptions.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We will make the code publicly available, including the evaluation protocols. In Table A4, we list all hyperparameters.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (c.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
cases, in which
5. Open access to data and code
29

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We will make the code publicly available, including references to the used public-available datasets. All datasets are available through the interface PyTorch Geo- metric.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https::/nnis..c cc/ gublic/guides hwtps///oooeeubiassiooooooooeeee
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed run reproduce the results. See the NeurIPS code and data submission guidelines (https
//iips.cc/ppppp wttpccccppppcppeeececceccccccc http://guuuieee/eeuuubbiiibeeee CodeSuomi ssioooiiccc for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: In Table A4, we list all hyperparameters. Experimental details and protocols are described in Section 5, and more details are given in Appendix E.
Justification: We provide information about the data splits, how they were selected, and the optimizer in Section D Further, for every dataset and benchmark, we detail the hyper- parameters in Table A5
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes].
Justification:
We provide standard deviations for all experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
30

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: See Appendix E for details on the used hardware, In Table 1, we provide details on computation time and memory consumption.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics htttp://neurips. httpr/ppss.ppppbbiic/cccccucuuue
Answer: [Yes]
Justification:
We reviewed the NeurIPS Code of Ethics, and our work respects it.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
31

---

10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper conducts foundational research in the area of graph learning. While certainly our work could be used both for positive and negative societal impact, we do not foresee any immediate positive or negative societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: We release neither data nor large-scale models as part of this work. Further, our experiments are conducted on comparatively small, curated, task -ask-specffic datasets used for benchmarking graph learning models. Hence, our work does not pose immediate risks for misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
32

---

Answer: [Yes]
Justification: We cite all used datasets and provide the original publications. This is the default in the field of graph learning.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwwppsppppeaaaaeeeee thcode com datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
Justification:
The paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
33

---

Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This work does not involve crowdsourcing research with humans.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
34


Reviews:
[{"review_id": "RCK5yAQid1", "reviewer": "Reviewer_UsNW", "summary": "This paper introduces Implicitly Rewired Message-Passing Neural Networks (IPR-MPNNs) to address the limitations of traditional MPNNs, such as under-reaching and over-squashing. By integrating implicit probabilistic graph rewiring and adding a small number of virtual nodes, IPR-MPNNs enable long-distance message propagation without quadratic complexity. This approach enhances expressiveness and computational efficiency.", "questions": "1. Does the method exacerbate over-smoothing?\n2. Why is it necessary to sample $q$ times? Does this serve a similar function as multi-head attention?\n3. How do you ensure that the union of the inverse assignments covers the entire set of original nodes?\n4. What is the initial set of $G_c$ ?\n5. What is the runtime when $q$ is large?\n6. How does the method perform on node-level tasks that require long-range interactions?\n7. Can more ablation studies be conducted to provide additional insights?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well-written.\n2. The experimental performance is good, demonstrating promising improvements on molecule datasets.\n3. The method effectively overcomes the quadratic complexity of graph transformers while capturing long-range information.", "weaknesses": "1. **Risk of Over-Smoothing**:\n   - While IPR-MPNNs alleviate squashing and under-reaching, the approach of connecting all nodes via virtual nodes increases the risk of over-smoothing. A discussion on over-smoothing analysis would strengthen the paper.\n\n2. **Applicability to Node-Level Tasks**:\n   - The method should be directly applicable to node-level tasks, where long-range interactions are particularly beneficial. Conducting experiments on node-level datasets requiring long-range interactions and comparing with existing works would enhance the paper.\n\n3. **Unclear Method Description**:\n   - The benefit of sampling \\( H \\) \\( q \\) times, its implications, and the associated costs and disadvantages need further clarification.\n   - It is unclear how to ensure that the union of the inverse assignments covers the entire set of original nodes.\n   - The initial set of \\( G_c \\) is not clearly defined.\n\n4. **Runtime Measurement**:\n   - Better reporting of runtime measurements with respect to the number of \\( q \\) would provide valuable insights.\n\n5. **Notation Confusion**:\n   - There is some notation confusion, such as between \\( h^{(t)} \\) and \\( H^{(q)} \\), which needs to be clarified.\n\n6. **Optimal Parameters and Ablation Studies**:\n   - Reporting the optimal \\( m \\) and \\( q \\) for each experiment and conducting ablation studies on these parameters would provide insights on how to choose them effectively.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their assessment and feedback. In the following, we respond to the reviewer’s questions. Please note that the tables containing new experiments are in the next official comment and the pdf file attached to the “Global Response”.\n\n- **Q1, Q2:** Do IPR-MPNNs increase the risk of over-smoothing? Experiments on node-level tasks would strengthen the paper.\n\n- **R1, R2:** The reviewer raises a valid concern. Over-smoothing happens when nodes close to each other collapse to similar representations after several message-passing steps. \n\nWe provide intuitive arguments and empirical results showing our method does not increase the risk of over-smoothing:\n\n* Over-smoothing is more likely if the virtual complete graph connects to the entire original graph since all nodes would get the same embedding from the virtual nodes during the final update. We sparsely connect original nodes to virtual nodes, which can be seen as a clustering step. This allows distant nodes of the same class to directly pass messages via the same virtual node, potentially reducing over-smoothing when compared to using virtual nodes connected to the entire graph. Therefore, it should be easier to find IPR-MPNN configurations that better handle heterophilic, long-range tasks.\n\n* To empirically address the reviewers' concern and to verify whether IPR-MPNNs can deal with node classification, we perform experiments on the WebKB datasets and some newly-proposed heterophilic datasets [PV23], which contain node classification tasks in heterophilic scenarios. We generally outperform the methods we compare with. We leave the results in the next official comment.\n\nThank you for your question. We will update the manuscript to include a discussion on over-smoothing and the new experiments, showing improvements over baselines on heterophilic, node-level tasks.\n\n---\n\n- **Q3:** The benefits and drawbacks of sampling are unclear.\n\n- **R3:** We thank the reviewer for raising the concern about clarity. In the following, we will try to highlight the benefits and drawbacks of sampling:\n\n* **Benefits**: the main advantage of sampling is obtaining multiple virtual node assignments for the base nodes. They can then be used to obtain different final embeddings for the same graph. From an optimization perspective, sampling multiple configurations makes it easier for the upstream model to explore the combinatorial solution space. From a representation perspective, it effectively augments the data with multiple virtual node configurations. As the reviewer pointed out, this could function similarly to multi-head attention with shared parameters.\n\n* **Costs**: we add all of the sampled configurations to the same batch, feeding the batch to the downstream model. The sample embeddings are computed in parallel, and the downstream parameters are shared. The overhead for this is typically low. The computation times for multiple samples and multiple virtual nodes are available in Table A9 in our Supplementary material. We leave the tables in the next official comment for convenience.\n\nIn scenarios with 2-4 virtual nodes and 1-2 samples, our method greatly improves computation time over GraphGPS, with memory usage similar to GINE. Even with 30 virtual nodes and 20 samples, we remain faster and more memory-efficient than GraphGPS.\n\n---\n\n- **Q3.2:** It is unclear how to ensure that the union of the inverse assignments covers the entire set of original nodes. \n\n- **R3.2:** We thank the reviewer for pointing out that this is unclear. When sampling virtual nodes, we sample exactly $k$ virtual nodes for each of the original nodes; therefore, each original node will have connections to exactly $k$ nodes in the virtual graph. We will clarify the text on lines 183-191 in the camera ready: “(...) where each original node $v\\in V(G) := [n]$ is assigned to $k \\in [m]$ virtual nodes, _therefore, all of the nodes in original graph will have exactly $k$ edges connecting to the virtual graph._”\n\n---\n\n- **Q3.3:** The C(G) set of virtual nodes is not well defined.\n\n- **R3.3:** Thank you for pointing to this unclarity. The virtual node set C(G) is a set of new nodes that form a complete virtual graph - we will expand the text on lines 183-191 for the next revision: “and a _fixed, new_ virtual node set $C(G):=[m]$ of cardinality $m$”\n\n---\n\n- **Q4:** Runtimes with respect to the number of samples.\n\n- **R4:** We report runtimes based on the number of samples and virtual nodes in Table A9 of our Supplementary materials. We will move some results from the Appendix to the main paper for the final revision.\n\n---\n\n- **Q5:** $H^{(q)}$ and $h^{(t)}$ are a confusing notation. \n\n- **R5:** Thank you for highlighting the unclear notation. $H^{(q)}$ represents the matrix of new connections between original and virtual nodes, while $h^{(t)}$ represents the hidden embeddings of the original nodes after $t$ message-passing layers. We will clarify this in the final version.\n\n---\n\n- **Q6:** Optimal hyperparameters and ablation studies.\n\n- **R6:** The hyperparameters used in our experiments are in Table A5 of the Supplementary materials. We also conducted new experiments with a virtual node connected to the entire virtual graph and with two virtual nodes, sampling one, two, or four configurations. Please see the next official comments for the results. \n\nIn most practical scenarios that we have tested on, having more than 2 samples doesn’t positively affect the performance but can lower the standard deviation between runs. We see that using 4 samples decreases overall performance, but the standard deviation for the 5 runs is much lower. \n\n---\n\nOnce again, we thank the reviewer for their suggestions, and we kindly ask the reviewer to increase their score if they are satisfied with our response. We are happy to answer any remaining questions!", "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": "rD4ahJ67gw", "reviewer": "Reviewer_bePC", "summary": "The paper introduces a method (IPR-MPNN) which connects nodes to a small number of virtual nodes in a learnable way. The proposed approach is more expressive than MPNN whilst circumventing quadratic complexity. It can reduce oversquashing and performs well on various benchmarks.", "questions": "- Do you have some explanation for why your approach improves over GTs? Can GTs not replicate this method?\n- It would be useful to the community to mention the fraction of nodes which are connected to the VNs on some of these datasets. Connecting to a single node seems similar to node-marking and to all nodes would be equivalent to standard VN. It is interesting to see how this approach falls in this region for certain tasks.", "limitations": "some limitations have been addressed in the appendix. For example: \"We have designed our rewiring method specifically to solve long-range graph-level tasks\" - I assume the model is flexible here though in that it could also only use local interactions by connecting to. single node or node neighbours.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The benefits of the approach in the context of MPNNs (Expressivity) and Graph Transformers (Complexity) are well argued and I particularly like the probabilistic argument to ensure that isomorphic graphs are not separated with high probability. \n- The results are extremely good and the approach while quite simple, achieves SOTA on various benchmarks.\n- To the best of my knowledge the approach is novel due to the learnable rewiring, whilst there are interesting connections to other methods (Hierarchical MPNNs, node marking etc) which will interest the community.", "weaknesses": "- Whilst the method is shown well in the context of MPNNs and GTs, the probabilistic rewiring is less well motivated in the context of standard virtual nodes. Adding a baseline of MPNN + VN (with your number of VNs) would help and your results seem like they would be much better. Additionally, explaining why only connecting a fraction of nodes to the VN (instead of all) helps in terms of expressivity could also be mentioned/explored - this seems like it would be the case intuitively. You could also compare the effective resistance of your IPR-GNN graph to one where we just have a single global VN. As MPNN + VN is quite popular in the community, this would help us understand why we should favour your approach for certain tasks. \n- In line 68, you suggest that your approach helps with \"scaling to large graphs effectively\". To me, it is not clear if this is the case. Firstly, the results seem to be mainly on small molecular datasets. Additionally, whilst you only use a small number of VNs on these datasets (eg. 2), This can still be 10% of the number of nodes in the graph. It is not clear if for large graphs you also need to have 10% VNs compared to total number of nodes. If this is the case, would your approach still be practical?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive assessment of our work. In the following, we will respond to the raised issues:\n\n- **W1:** Empirical and theoretical comparison with MPNN + VN.\n\n- **RW1:** We thank the reviewer for the suggestion.  The paper currently contains one such comparison in Table 2 - R-GIN-FA is a Relational GIN model with a fully-connected virtual node. Nevertheless, we also conducted the following experiments with the base model and a fully-connected virtual node, which we will include in the final version of our paper:\n\nOur approach treats the virtual nodes and original nodes as heterogeneous nodes, therefore, for fair comparison, we use the same heterogeneous MPNN on MPNN+VN experiments, without reducing the number of parameters. \n\n| Model           \t| ZINC &darr;            \t| ogb-molhiv &uarr;      \t| peptides-func &uarr;  \t| peptides-struct &darr;\t|\n|---------------------|----------------------|----------------------|---------------------|---------------------|\n| 1VN - FC        \t| 0.074 ± 0.002    \t| 0.753 ± 0.011    \t| 0.7039 ± 0.0046 \t| 0.2435 ± 0.0007 \t|\n| IPR-MPNN 2VN1S  \t| 0.072 ± 0.004    \t| 0.762 ± 0.014    \t| 0.7146 ± 0.0055 \t| 0.2472 ± 0.0014 \t|\n| IPR-MPNN 2VN2S  \t| **0.067 ± 0.001**    \t| **0.788 ± 0.006**    \t| **0.7210 ± 0.0039** \t| **0.2422 ± 0.0007** \t|\n\n \nThe advantages of having sparse, learnable connections over fully-connected virtual nodes are as follows:\n\n* **Bottlenecks** - The network is less likely to suffer from information bottlenecks in the virtual graph since not all original nodes are connected to the virtual nodes.\n\n* **Expressiveness** - adding virtual nodes connected to the entire base graph would not make the MPNN more powerful than 1-WL. Consider the following proof sketch:\n\nAssume that we have a graph $G$ with some stable $1$-WL coloring. Now, for each node $v$ we recursively unroll the neighborhoods into a rooted tree of sufficient depth. The isomorphism type of this tree is $1$-to-$1$ to the stable color of node $v$. Now, if we consider all vertices, we have a forest of unrolling trees. We create a new vertex (the virtual node) and connect the roots of the trees in the forest to this new vertex. Then, the isomorphism type (of this forest) is $1$-to-$1$ to the isomorphism type of the original graph modulo $1$-WL; therefore, if some other graph with a virtual node has the same $1$-WL coloring, the two graphs remain indistinguishable. \n\nOn the other hand, we can attach the virtual node to the original graph and unrolling from the virtual node. However, this tree will be isomorphic to the above constructed tree (forest + root vertex). Therefore, the graphs remain indistinguishable.\n\nWe will add a more nuanced discussion regarding the comparison with other virtual node approaches in the final version of our paper.\n\n---\n\n- **W2:** Would the approach be practical for large graphs? \n\n- **RW2:** We thank the reviewer for pointing out the inconsistency. We have performed new experiments on heterophilic datasets, which have a significantly greater number of nodes per graph. We report here the results:\n\n| Methods      | Cornell &uarr;   | Texas &uarr; | Wisconsin &uarr; |\n|-------------------------------|-------------------------|-------------| --- |\n| GINE                          \t| 0.448±0.073             | 0.650±0.068 \t| 0.517±0.054 | \n| DIGL [GR19] \t\t\t| 0.582±0.005             | 0.620±0.003 \t| 0.495±0.003|\n| Geom-GCN [PI20]  \t\t| 0.608±N/A                | 0.676±N/A    \t| 0.641±N/A |\n| SDRF [TG21]  \t\t\t| 0.546±0.004             | 0.644±0.004 \t| 0.555±0.003 |\n| DiffWire [ARZ22]  \t\t\t| 0.690±0.044\t\t| N/A\t\t| 0.791±0.021 |\n| GPS [RK22] \t\t\t| 0.718±0.024 \t\t| 0.773±0.013  | 0.798±0.090 |\n| Graphormer [YG21] \t\t| 0.683±0.017\t\t| 0.767±0.017\t| 0.770±0.019|\n| IPR-MPNN \t\t\t| __0.764±0.056__ \t| __0.808±0.052__ | __0.804±0.052__ |\n\nMoreover, we also report results on the newly-introduced heterophilic datasets from [PV23]. These datasets contain more challenging scenarios and have a significantly higher number of nodes per graph (22K for roman-empire, 11k for tolokers, 24k for amazon-ratings, 10k for minesweeper). We can run all IPR-MPNN experiments with a memory consumption of at most 10GB.\n\n| Model        \t| Roman-empire &uarr;           \t| Tolokers &uarr;               \t| Minesweeper &uarr;            \t| Amazon-ratings &uarr;         \t|\n|------------------|-----------------------------|-----------------------------|-----------------------------|-----------------------------|\n| GINE (base)  \t| 0.476±0.006             \t| 0.807±0.006             \t| 0.799±0.002             \t| **0.488±0.006**         \t|\n| IPR-MPNN (ours)  | **0.839±0.006**         \t| **0.820±0.008**         \t| **0.887±0.006**         \t| 0.480±0.007             \t|\n\n---\n\n- **Q1:** Why do we see improvements over GTs?\n\n- **RQ1:** This is a great question. We posit that the improvements come from having a stronger graph inductive bias than most GTs, where the graph is assumed to be complete. By performing all of our computations using message-passing, we keep a strong inductive bias, while the virtual nodes with learnable connections act similarly to a hard, sparse attention mechanism, thereby allowing for long-range messages to be passed while still maintaining a strong locality bias. Graph Transformers might be able to replicate this method, assuming a sparsification of the attention matrix, with a bias towards the GT “latent graph” being more similar to the original graph, thereby maintaining a better graph bias.\n\n---\n\n- **Q2:** How many virtual nodes are used?\n\n- **RQ2:** In Table A5 from the Supplementary Materials, we report the number of virtual nodes used for most experiments. A low number (2-8 virtual nodes) is effective for most tasks.\n\n---\n\nWe want to thank the reviewer for their suggestions and kindly ask the reviewer to increase their score if they are satisfied with our response. We are happy to answer any remaining questions!", "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": "OZbCjWPuR0", "reviewer": "Reviewer_YQwu", "summary": "The paper proposes implicitly rewired message-passing neural networks (IPR-MPNNs), which integrate implicit probabilistic graph rewiring into MPNNs. This method involves introducing a small number of virtual nodes into the graph, allowing for long-distance message propagation without the quadratic complexity associated with graph transformers.", "questions": "1. Can you provide an algorithm table that details the training process of IPR-MPNN？", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The introduction of implicit probabilistic graph rewiring via virtual nodes is a novel contribution that addresses the limitations of traditional MPNNs, such as under-reaching and over-squashing, without incurring the high computational cost of graph transformers.\n2. The authors provide a theoretical analysis demonstrating that IPR-MPNNs exceed the expressive capacity of standard MPNNs, typically limited by the 1-dimensional Weisfeiler-Leman algorithm.", "weaknesses": "1. It remains unclear to me how the unnormalized node priors $\\theta$ are derived. On Line 170, the authors mentioned that $\\theta \\in \\Theta$, but what is $\\Theta$? According to Line 169, is it the output of the upstream GNN? Why can we trust that it accurately reflects the original node-virtual node connectivity? Is there any related optimization objective?\n\n2. Gradient estimators for graph sampling are not a new topic. The authors may refer to [1, 2]. Providing related ablations might be more convincing.\n\n3. I do not fully understand Figure 2. As stated by the authors, the values in the figure are about \"the two most distant nodes,\" but why is this referred to as model sensitivity? How is this sensitivity defined?\n\n4. Although the authors provided a complexity analysis, I believe it is necessary to provide numerical comparisons, such as the per epoch time and wall-clock time before and after using IPR-MPNN.\n\n\n[1] Robust Graph Representation Learning via Neural Sparsification, NeurIPS22\n\n[2] Differentiable Graph Module (DGM) for Graph Convolutional Networks, TPAMI", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback on our work. In the following, we will try to address the concerns raised by the reviewer:\n\n- **W1:** How are the unnormalized priors $\\theta$ obtained? Is there any related optimization objective?\n\n- **RW1:** The unnormalized priors are the output of the upstream MPNN. Specifically, after some message-passing steps, we use a shared linear readout layer for each node to obtain $\\theta$. If we have $N$ virtual nodes, we obtain a $1\\times N$ unnormalized prior $\\theta$ for each of the original nodes. These priors are then sent to the sampling layer, ensuring exactly $k$ virtual nodes are selected for each original node. There is no related optimization objective for the priors; we estimate the gradients for the sampling layer using an exactly-$k$ gradient estimator (SIMPLE).\n---\n- **W2:** Gradient estimation for graph sampling is not a new topic.\n\n- **RW2:** We agree that gradient estimation for graph sampling is not novel by itself. We discuss similar approaches in the “Graph Structure Learning” section of Related Work in the Supplementary Materials (lines 636-648). However, our work's novelty lies in leveraging differential $k$-subset sampling for probabilistic rewiring and incorporating hierarchical message passing in an end-to-end trainable framework. We show how this probabilistic framework increases model expressiveness and benefits modeling long-range interactions. Additionally, our work differs from previous approaches by using state-of-the-art $k$-subset sampling algorithms (SIMPLE), while most previous works use $1$-subset sampling and estimate gradients with the Gumbel-Softmax trick.\n\nRegarding possible ablations - we show how the model sensitivity changes when different numbers of virtual nodes are used in Figure 2. \n\nWe also provide a new ablation for the number of virtual nodes and samples. Our approach treats the virtual nodes and original nodes as heterogeneous nodes, therefore, for fair comparison, we use the same heterogeneous MPNN on MPNN+VN experiments, without reducing the number of parameters. \n\n| Model           \t| ZINC  &darr;           \t| ogb-molhiv  &uarr;     \t| peptides-func &uarr;  \t| peptides-struct &darr;\t|\n|---------------------|----------------------|----------------------|---------------------|---------------------|\n| 1VN - FC        \t| 0.074 ± 0.002    \t| 0.753 ± 0.011    \t| 0.7039 ± 0.0046 \t| 0.2435 ± 0.0007 \t|\n| IPR-MPNN 2VN1S  \t| 0.072 ± 0.004    \t| 0.762 ± 0.014    \t| 0.7146 ± 0.0055 \t| 0.2472 ± 0.0014 \t|\n| IPR-MPNN 2VN2S  \t| **0.067 ± 0.001**    \t| **0.788 ± 0.006**    \t| **0.7210 ± 0.0039** \t| **0.2422 ± 0.0007** \t|\n\n| Model\t| peptides-func &uarr;  \t|\n|----------|---------------------|\n| 1VN - FC | 0.7039 ± 0.0046 \t|\n| 2VN1S\t| 0.7146 ± 0.0055 \t|\n| 2VN2S\t| **0.7210 ± 0.0039** \t|\n| 2VN4S\t| 0.7145 ± 0.0020 \t|\n\nIn most practical scenarios that we have tested on, having more than 2 samples doesn’t positively affect the performance but can lower the standard deviation between runs. We see that using 4 samples decreases overall performance, but the standard deviation for the 5 runs is much lower. \n\n---\n\n- **W3:** Sensitivity analysis is unclear.\n\n- **RW3:** We detail this on lines 756-758 of our Supplementary Materials. We compute the logarithm of the symmetric sensitivity between the most distant nodes $u$, $v$, i.e., $ln\\left(\\left| \\frac{\\partial \\mathbf{h}^{l}_v}{\\partial \\mathbf{h}^{k}_u} \\right| + \\left| \\frac{\\partial \\mathbf{h}^{l}_u}{\\partial \\mathbf{h}^{k}_v} \\right|\\right)$, where $k$ to $l$ represent the intermediate layers. We thank the reviewer for pointing out that this is unclear; we will move these details to the main text of our work for the final version of our paper.\n\n---\n\n- **W4:** Runtime comparisons for IPR-MPNN.\n\n- **RW4:** The paper includes two comparisons. The first, in Table 1, is between the base GINE model, IPR-MPNNs, and the GPS Graph Transformer. We show that our method has similar inference times and memory consumption to the base model, while being significantly more efficient than GPS. The second comparison is in Table A9 in the Supplementary Materials, where we compare various configurations of IPR-MPNN with the base GINE model, variants of the SAT Graph Transformer, GPS, and variants of the PR-MPNN rewiring method. In most cases, we perform better than the other models while maintaining similar performance and memory consumption to the base GINE model.\n\n---\n\n- **Q1:** Algorithm table for training IPR-MPNN.\n\n- **RQ1:** We thank the reviewer for their suggestion; we will include an algorithm table/pseudocode for IPR-MPNN in the final version of our paper.\n\n---\n\nWe want to thank the reviewer for their suggestions and kindly ask the reviewer to increase their score if they are satisfied with our response. We are happy to answer any remaining questions!", "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": "XcM1vYdomR", "reviewer": "Reviewer_5s4E", "summary": "This work introduces an approach called implicitly rewired message-passing neural networks (IPR-MPNNs) to address limitations in message-passing graph neural networks (MPNNs): expressiveness and mainly over-squashing. Their method works by adding virtual nodes and learning to connect them to existing nodes in a differentiable, end-to-end manner. Authors claim that previous techniques are not scalable, and state that their approach is more scalable. They empirically show the performance of their proposed model.", "questions": "Questions are listed along with each specific identified weaknesses in the previous section.", "limitations": "I summarize the limitations of the work, however, I refer to weaknesses section for a more detailed feedback.\n\n* Relate work is not complete and not clearly explained and structured.\n* The authors do not closely connect how virtual nodes solve oversquahing.\n* Authors do not discuss limitations of the virtual nodes wrt over-squashing.\n* All the important contributions are empirical, and the theoretical ones are not very novel.\n* The core of the idea is not very novel, just a combination of previous work on virtual nodes an probabilistic message passing, but not a big contribution by itself. Also, they mention as contributions that their methods alliviates the limitations of GNNs, but there is no explanation why, just empirical results.", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* Their method slighlty improves the computational complexity when using m<<n virtual nodes (otherwise is quadratic as well).\n* Empirically, their proposed method improves the accuracy in some of the datasets wrt some of the baselines.\n* Theoretically, IPR-MPNNs exceed the expressiveness of MPNNs, overcoming 1WL test. \n* The method allows for end-to-end differentiable learning, integrating the rewiring process seamlessly into the training of MPNNs. This is done by few previous approaches (see next section)\n\n\n**[POST-REBUTTAL COMMENT]** \n\nAfter carefully reading the answer from the authors, I acknowledge the improvement of the manuscript after the rebuttal (related work, additional discussion, clarification of misunderstandings, additional experiments...), I increase my score and I support the acceptance of the manuscript.", "weaknesses": "### Related work\n\n* The state of the art is in general not properly structured and not enough detailed. Although they cite some of the important work, thay do not delve into the detail of the different papers about limitations on oversquashing (Di Giovanni 2023, Black 2023, they cite both of them, but authors dot seem to cite them when talking about limitations or even they dont mention the rewiring methods they propose SDRF and GTR), which is one of the main points in this work. For instance, when talking about graph rewiring they cite several works, no detailing what are the contributions of each and also mixing works of different solutions in the same sentence: MixHop is based on a adaptative message passing and DIGL is rewiring basd on difussion, but authors just say that both works are \"considered as graph rewiring as they can reach further-away neighbors in a single layer\". I mean, authors mix adaptative MP with spatial rewiring with spectral rewiring, expanders with no explanation about it. I do not think that the level of structure and detail is enough for a paper in this conference. See Di giovanni 2023, Banerjee 2022a(FOSR), 2022b(RLEF), Choi 2024(Pandas), for an example of better structured and detailed explanation of the different rewiring methods.\n\n* In addition, they miss very relevant works in the literature about graph rewiring and the analysis of graph limitations that are related with this paper. Specifically, authors evaluate their contribution using commute time or effective resistance. They miss 2 very important rewiring works in this line DiffWire (Arnaiz-Rodriguez, 2022) and FOSR (Banerjee, 2022), where they introduce the oversquashing connectino with the Cheger constant and methods to reduce the effective resistance between nodes to overcome oversquashing. To be even more clear regarding Banerjee 2022: in the references appears RLEF and FOSR, but in the text there is only one reference to RLEF. They also do not mention GTR from the already cited paper Black 2023, which is also based on effective resistance, metric that authors then use to evaluate IPR-MPNN. I suggest the authors to look more carefully also Di Giovanni 2023 on all the impact of not only these but also more works in the graph rewiring literature, and to completely cite all the important first works in this area.\n\n* On top of DiffWire and FOSR, authors also miss more important papers in grph rewiring such as Drew (Gutteridge 2023), LASER (Barbero 2024) or Affinity-Aware GNNs (Velingker). \n\n* In addition, they miss relevant papers in the literature about virtual nodes, which is one of the main points in this paper. For instance, the two first important works about virtual nodes (Battaglia 2017 and Brüel-Gabrielsson 2022) are just cited in the appendix and/or not even mentioning that they proposed the virtual nodes. Additionally, authors are not aware of works focused on the limitations of virtual nodes and how they are related with oversquashing: Southern 2024 and Geisler 2024. These papers completelly address how *theoretically* virtual nodes affect oversquashing and how they can be used to mitigate it (see methodology weaknesses). I suggest the authors to look more carefully at the literature about virtual nodes and oversquashing, and to completely and properly cite all the important first works in this area correctly stating the main contributions of the prior work.\n\n\n### Methodology\n\n* The contribution of this work is limited since it comes from the combination of virtual nodes and probabilistic message passing. Both ideas were already previously proposed. It would be helpful if authors are more transparent on what are the exact novelty of this method. Virtual nodes ar not novelty as proposed before (Battaglia 2017) and probabilitistic message passing as well. The changes to make this approach novel are not sufficient in my opinion.\n  \n* Regarding the contributions, only the expressiveness contribution is shown theoretically, and it is the less related with the problem they claim to solve (OVSQ). The rest of the contributions are just shown empirically, which does not advance on the knowledge of the limitations of the GNN field.\n* Authors do not justify thoretically how their approach improves oversquashing, which should be the main approach of the paper. They just empirically show that the effective resitance and sensitivity are smalles, which is a trivial result of the Rayleigh’s monotonicity principle when densifying a graph. The paper would increase a lot the quality if authors really tryy to understand why their method improve oversauashing and if it really does. Souther 2024 and Geisler 2024 might be helpful for this. To reach the level of Neurips authors should have a more theoretical approach to the problem they are trying to solve. However, it is monstly empirical as they also aknowledge in the section 5 (they answer all the questions just empirically). This is very dangerous, since the empirical results might not be generalizable to other datasets or tasks. Also, in the GNN community is widely known the lack of understanding of how GNNs work if we only look at the results of datasets.\n\n  \n* One key contribution is that they do rewiring it in less than quadratic complexity (which is only ok for transphormers but is not ok for rewiring methods). However this is only empirically, since authors also mention l865 \"In the worst-case scenario, where m = n, our method exhibits quadratic complexity. However, in all real-world datasets we have tested, the required number of virtual nodes for achieving optimal performance is low\". \n\n* Also, mention do not delve into the limitation of the virtual and oversquashing (See Southern 2024 and Geisler 2024). For instance, altough the effective resistance is reduced using virtual nodes, the oversquashing is not fully solved since all the messages are squeezed in the virtual nodes, even worsening the problem of exponential aggregation of information in some bottleneck \"nodes\". As shown in Topping 2022 and Arnaiz-Rodriguez 2022, the blottleneckness of the nodes (measured either by curvature, spectral metrics or centralities), causes oversquashing.\n\n* As their main experiments are in graph classification tasks,  and the main contribution is based on pairwise scores, they also should compare aagaints CT-Layer in Diffwire (Arnáiz-Rodrigues 2023), which is a rewiring based also in similarity scores that was shown to improve graph classification tasks. Also, authors claim that previous \"strategies to mitigate over-squashing rely on heuristic rewiring methods or purely randomized approaches that may not adapt well to a given prediction task\". Also, diffwire is in-processing rewiring and takes into account the task. Finally, also Geisler 2024 is task-oriented.\n\n  \n* They compare the running time against transformer but not against rewiring, which does not make sense. They propose an architecture to do graph rewiring and alliviate oversquashing, so they should compare with graph rewiring methods.\n\n\n### Refs\n\nP. W. Battaglia,  et al. Relational inductive biases, deep learning, and graph networks. 2017.\n\nA. Arnaiz-Rodriguez et al. DiffWire: Inductive Graph Rewiring via the Lovász Bound. LoG, 2022.\n\nP. K. Banerjee et al. Oversquashing in gnns through the lens of information contraction and graph expansion. AACCC, 2022.\n\nR. Brüel-Gabrielsson, M. Yurochkin, and J. Solomon. Rewiring with positional encodings for graph neural networks. 2022\n\nF. Di Giovanni et al. On over-squashing in message passing neural networks: The impact of width, depth, and topology. ICML 2023.\n\nM. Black et al. Understanding Oversquashing in GNNs through the Lens of Effective Resistance. ICML 2023.\n\nD. Gutteridge et al. Drew: Dynamically rewired message passing with delay. ICML 2023.\n\nA. Velingker. Affinity-Aware Graph Networks. NeurIPS 2023.\n\nF. Barbero. Locality-Aware Graph Rewiring in GNNs. ICML 2024.\n\nJ. Choi. PANDA: Expanded Width-Aware Message Passing Beyond Rewiring. ICML 2024\n\nJ. Southern. Understanding Virtual Nodes: Oversmoothing, Oversquashing, and Node Heterogeneity. 2024.\n\nS. Geisler. Spatio-Spectral Graph Neural Networks. 2024.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback and detailed review. \n\nDue to the space restrictions for the rebuttal, we address related work and novelty comments here, with the remaining concerns, additional results, and the bibliography in other official comments at the same level.\n\n- **Q: Related work.**\n\n- **R:** We thank the reviewer for the feedback on our related work sections. We agree that giving a comprehensive overview of current literature is essential. Based on the reviewer's comments, we will improve the related work sections for the final paper.\n\nIn the following, we discuss the related work that the reviewer has proposed in detail:\n\n**Missing concurrent related work:**\n\n* **[SN24, GR24]: We would like to point out to the reviewer and the program committee that these are concurrent works that became publicly available on arXiv on 22 May and 29 May, respectively. The NeurIPS Main Conference Paper Submission deadline was 22 May, AoE, so it would have been impossible to include the papers in the related work section at submission time.**\n\n---\n\n**Related work proposals that have been discussed:**\n\n* **[GE23]:** This is a key work we compare with, citing and discussing it on lines 35, 101-102, and 253. We compare with Drew on the QM9 dataset (Table 2), where we outperform it on 12 out of 13 properties, and on Peptides-func and Peptides-struct (Table 3), where we outperform it on both datasets.\n\n* **[BGN22]:** When discussing related rewiring approaches, the first work we mention is [BGN22] (lines 97-98).\n\n* **[BA17]:**  We include related work regarding Hierarchical MPNNs in our Supplementary Materials. We provide an extensive discussion on both hierarchical methods and virtual node-based methods, including Battaglia 2017 (lines 677-678).\n\n* **[BE23]:** We cite this method on line 106.\n\n* **[KR22]:** We cite this work on line 35 and briefly discuss it on line 105. We also compare with their FoSR method on the TUDataset collection in Table A6, where we achieve significantly better results on all datasets.\n\n---\n\n**Missing related work:**\n\n* **[ARZ22, VR23, BO24]:** We thank the reviewer for pointing out that this related work is missing.\n\nWe will update our manuscript to include the concurrent works of [SN24, GR24] and comparisons with them on the peptides datasets. We will add the missing related work of [ARZ22, VR23, BO24] and expand the discussions on [BE23, KR22].\n\n---\n\n* **Q: Methodology.**\n\n* **R:** We thank the reviewer for their suggestions; in the following, we try to respond to their concerns:\n\n1. **Novelty:** While probabilistic rewiring [QN24] and the concept of virtual nodes [BA17] have been explored in the past, combining the two concepts is not trivial. As highlighted in our paper, the key difference between the present work and [QN24] is that, unlike [QN24], where the adjacency matrix is modified directly, we keep the original adjacency matrix fixed and \"rewire\" by learning a $k$-subset distribution from the original graph nodes to the virtual nodes. Moreover, the virtual nodes can have different dimensions, connecting our message-passing scheme to heterogeneous message-passing and hierarchical MPNNs. Unlike existing hierarchical MPNNs that employ virtual/super nodes, e.g., [BA17, PM17, LI17, CI23], our IPR-MPNNs uniquely leverage differential $k$-subset sampling and incorporate hierarchical message-passing in an end-to-end framework. We discuss our connection to hierarchical message-passing and virtual nodes-based methods in the Supplementary materials, lines 663-689.\n\n2. **Theoretical guarantees:** Our primary goal is to improve the long-range capabilities of MPNNs while keeping complexity, memory usage, and runtimes low. Long-range dependency modeling is affected by over-squashing and under-reaching, but they are not our core theoretical concern. In our work, the theoretical guarantees of expressiveness, along with the over-squashing and under-reaching analyses, indicate where the performance gains might come from.\n\n\n3. **Empirical results might not be generalizable:** Our experimental section offers a comprehensive comparison on both real-world molecular datasets (ZINC, OGBG-Molhiv, QM9, Peptides-struct, Peptides-func, PCQM-Contact, TUDataset) and synthetic datasets (Trees-LeafCount, Trees-LeafMatch, CSL, EXP), where we generally achieve state-of-the-art results. Our empirical evidence shows that our method is effective in addressing over-squashing through model sensitivity (Fig. 2), effective resistance (Fig. 3), and the Trees-NeighborsMatch dataset (Fig A4). We also outperform other rewiring methods (Drew, PR-MPNN, AMP) and graph transformers (GPS, Exphormer, GRIT, etc.) on long-range tasks (Table 3) and various molecular datasets (QM9 in Table 2, ZINC and OGB-Molhiv in Table 4, TUDataset in Table A6).  Thus, we argue that IPR-MPNNs are an efficient, state-of-the-art class of MPNNs for both common molecular datasets and those requiring long-range interactions, with strong empirical evidence that indicates an alleviation of over-squashing.\n\n4. **The paper is not theoretical enough for NeurIPS:** NeurIPS Reviewer Guidelines [NS24-1] state that \"_claims can be supported by **either theoretical analysis or experimental results**_\". NeurIPS has historically included many empirical works and remains a generalist conference, suitable for applications and general machine learning topics, as per the NeurIPS 2024 Call for Papers [NS24-2].\n\nWe continue addressing the raised methodology issues in the next official comment.", "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:
We thank the reviewers for their thoughtful comments and suggestions. We believe that our paper is much stronger after considering reviewer feedback. 

All of the new comparisons and experiments are included in the one-page pdf attached to the global response.

---

In the following, we summarize the modifications that will be included in our final paper:

**UsNW, bePC, 5s4E:** New experiments on heterophilic datasets (WebKB, [PV23]) - Tables 10, 11 in the pdf. We show that we are able to run our model on large graphs and that, in most cases, we obtain better results on heterophilic datasets when compared to baselines, indicating that IPR-MPNNs might alleviate over-smoothing.

**UsNW, bePC, YQwu:** New experiments where we compare with a simple MPNN + VN and we change the number of samples that we use in Tables 13,15. We observe that, generally, having only two samples achieves very good performance with low computation overhead. We will also add a discussion regarding how we are different from MPNN+VN and about the benefits and costs of sampling to the final version of the paper.

**UsNW:** We will fix the clarity issues on lines 183-191 and the confusing notation.

**YQwu:** We will clarify how we compute the sensitivity in the final version of our paper.

**YQwu:** We will add an algorithm table/pseudocode for IPR-MPNN in the final version of our paper.

**5s4E:** We will add the three missing related works [ARZ22, VR23, BO24] and expand the discussions on [BE23, KR22]. We will also have a discussion regarding our connection to [GR24, SN24] - two concurrent works that were not available at submission time.

**5s4E:** We will add a more nuanced discussion about possible bottlenecks in the virtual graph.

**5s4E:** We added new comparisons with [ARZ22] in Tables 10 and 12, and with the concurrent works of [GR24, SN24] in Table 16. We show that we outperform [ARZ22, SN24] and are generally competitive with [GR24].

**5s4E:** We added a runtime and memory comparison with Drew [GE23] in Table 14. We are slightly faster than Drew but with slightly higher memory consumption.

---

We would like to once again thank the reviewers for their feedback and for helping us significantly strengthen our paper. We are happy to respond to any additional questions during the discussion period.

We kindly ask the reviewers to increase their scores if they are satisfied with our response.

---
References:

[PV23]: Platonov, O., et al. "A critical look at the evaluation of GNNs under heterophily: Are we really making progress?", ICLR 2023

[ARZ22]: Arnaiz-Rodríguez, A., et al. "Diffwire: Inductive graph rewiring via the Lovász bound." LoG 2022.

[VR23]: Velingker, A. et al., “Affinity-Aware Graph Networks”, NeurIPS 2023

[BO24]: Barbero, F. et al., “Locality-Aware Graph Rewiring in GNNs”, ICML 2024

[BE23]: Banerjee, P.K. et al., “Oversquashing in GNNs through the lens of information contraction and graph expansion”, ALLERTON 2022

[KR22]: Karhadkar, K. et al., “FoSR: First-order spectral rewiring for addressing over-squashing in GNNs”, ICLR 2023

[GE23]: Gutteridge, B. et al., “DRew: Dynamically Rewired Message Passing with Delay”, ICML 2023

[GR24]: Geisler, S. et al., “Spatio-Spectral Graph Neural Networks”, arXiv 2024

[SN24]: Southern, J. et al. “Understanding Virtual Nodes: Oversmoothing, Oversquashing, and Node Heterogeneity”, arXiv 2024

Meta-review: This paper proposed implicitly rewired message-passing neural networks (IPR-MPNNs), which integrate implicit probabilistic graph rewiring into MPNNs to alleviate the under-reaching and over-squashing issues. Most of the reviewers agreed that the proposed approach is novel and this paper is technically solid. All the reviews tend to accept the paper during the reviewer-author discussion phase. Therefore, I recommend this paper to the NeurIPS 2024 conference.
Decision: Accept (poster)