Improving the Effective Receptive Field of Message-Passing Neural Networks
Authors: Shahaf E. Finder
Ron Shapira Weber
Moshe Eliasof
Oren Freifeld
Eran Treister
Venue: ICML 2025 poster (2025)
Keywords: Effective Receptive Field
Multiscale Architectures
Message-Passing
Primary area: deep_learning->graph_neural_networks
TL;DR: We propose IM-MPNN, a multiscale message-passing framework that mitigates over-squashing, extends the effective receptive field, and improves long-range dependency capture in MPNNs.

Abstract: Message-Passing Neural Networks (MPNNs) have become a cornerstone for processing and analyzing graph-structured data. However, their effectiveness is often hindered by phenomena such as over-squashing, where long-range dependencies or interactions are inadequately captured and expressed in the MPNN output. This limitation mirrors the challenges of the Effective Receptive Field (ERF) in Convolutional Neural Networks (CNNs), where the theoretical receptive field is underutilized in practice. In this work, we show and theoretically explain the limited ERF problem in MPNNs. Furthermore, inspired by recent advances in ERF augmentation for CNNs, we propose an Interleaved Multiscale Message-Passing Neural Networks (IM-MPNN) architecture to address these problems in MPNNs. Our method incorporates a hierarchical coarsening of the graph, enabling message-passing across multiscale representations and facilitating long-range interactions without excessive depth or parameterization. Through extensive evaluations on benchmarks such as the Long-Range Graph Benchmark (LRGB), we demonstrate substantial improvements over baseline MPNNs in capturing long-range dependencies while maintaining computational efficiency.

Improving the Effective Receptive Field of Message-Passing Neural Networks
Shahaf E. Finder' 12
Ron Shapira Weber Moshe Eliasof
Oren Freifeld 124 Eran Treister 1
Abstract
Message-Passe Passing Neural Networks (MPNNs) have become a comnestone for processing and an- alyzing graph-structured data. However, their ef- fectiveness is often hindered by phenomena such as over-squashing, where long-range dependen- cies or interactions are inadequately captured and expressed in the MPNN output. This limitation mirrors the challenges of the Effective Receptive Field (ERF) in Convolutional Neural Networks (CNNs), where the theoretical receptive field is underutilized in practice. In this work, we show and theoretically explain the limited ERF prob- lem in MPNNs. Furthermore, inspired by re- cent advances in ERF augmentation for CNNs, propose Interleaved Multiscale Message- Passing Neural Networks (IM-MPNN) architec- ture to address these problems in MPNNs. Our method incorporates hierarchical coarsening of the graph, enabling pesssage-passing across multiscale representations and facilitating long- range interactions without excessive depth or pa- rameterization. Through extensive evaluations benchmarks such the Long-Range Graph Benchmark (LRGB), we demonstrate substantial improvements over baseline MPNNs in captur- ing long-range dependencies while maintaining computational efficiency.
(a) t= 10
(b) L 20
(c) 30
(d) 6 10 (e) 10
( S0
Figure 1: Measuring the contribution each node the output of the central node in graph with maximal distance of 10 hops from the center. A brighter color marks larger contribution. We can see decay akin to Luo et al. (2016), (a)-(c) are MPNNs (GCN) with 10, 20, and 30 MP layers, while (d)-(f) are IM-MPNNs with a GCN backbone with 10 MP layers and 2, and 3 scales.
physics (Shlomi et al., 2020), and social network analysis (Fan al., 2019). Among the GNN frameworks, message- passing Neural Networks (MPNNs) lent. The core idea of MPNNs lies in local message-passing, where nodes aggregate features from their immediate neigh- bors, followed by an aggregation operation that updates node representations layer by layer. However, the effective- ness of MPNNs is often hindered by the phenomenon of over-squashing (Alon & Yahav, 2021), where information from distant nodes is ineffectively aggregated, leading limited expressiveness for long-range interactions.
particularly preva-
1. Introduction
Graph Neural Networks (GNNs) have emerged as power- ful tools for solving wide range of problems modeled as graphs. Applications span diverse domains, including combinatorial optimization (Cappart et al., 2023), particle
While over-squashing was initially attributed to bottleneck edges (Alon & Yahav, 2021), more recent analyses empha- size the role of inter-node distances (Di Giovanni et al., 2023). This perspective aligns closely with challenges ob- served Convolutional Neural Networks (CNNs), where the Effective Receptive Field (ERF) often smaller than the theoretical receptive field (Luo et al., 2016). In this work, we further analyze this phenomenon and show that the contribu- tion of node v to the output of node u decays exponentially by the travel distance between them (see Figure 1).
DDparrmment of Computer Science, Ben-Gurion University, Is- rael Data Science Research Center, Ben-Gurion University, Israel 'Department of Applied Mathematics and Theoretical Physics, University of Cambridge, United Kingdom "School of Brain Sci- ences and Cognition. Ben-Gurion University, Isracl. Correspon- dence to: Shahaf E. Finder <finders @ peanddere@pppsstbbgggg..... iil.
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
In CNNs, the ERF issue can be mitigated by increasing the

---

Improving the Effective Receptive Field of Message-Passingg Neural Networks
Input
Stage
MP
Scale-mix
Concat
Head
Output
T
Pool
MP
Scale-mix mix
Unpool
Pool
MP
Scale-mix
Unpool
3
Pool
MP
Scale-mix
Unpool
x
Figure 2: IM-MPNN architecture for scales=3. The input is first passed through an encoding stage (PE, SE, Graph features, etc.). Then, the graph is coarsened $ times. MP protocols (GCN, GINE, GatedGCN, etc.) are performed on the $ + scales of the graph separately. Scale-mix layers pass the information between consecutive scales, matching each graph node with its parent and child from the coarsening process. The process repeated times. The coarse graphs are unpooled, and the node features are concatenated to the parent node in the original graph. A GNN head is used according to the task.
kernel size (Ding et al., 2022). However, adapting such ap- proaches to GNNs is nontrivial due to the irregular structure and complexity of the graph's 's node connectivity. In recent work, Finder et al. (2024) proposed an alternative approach to increase the ERF of CNNs. That method involves small kernel convolutions over multiple scales of the image.
By integrating multiscale representations with message- passing, IM-MPNN offers a principled way to address fundamental limitations of traditional GNN architectures, paving the way for more expressive and scalable graph mod- els. Our code is available at https: / //gt/ttttnt githuu..... com/ BGU- CSLCCC--VIIII BCU-CSS-VILIIO-MMO IM-MPNN
We draw inspiration from such multiscale methodologies in CNNs and propose Interleaved Multiscale Message- Passing Neural Networks (IM-MPNN) architecture to ad- dress the limitations of limited effective receptive fields in GNNs. Our approach introduces hierarchical coarsening of the graph, each reduces the graph's resolution while pre- serving critical structural information. Message-passing operations are performed each scale, enabling the model to capture long-range dependencies through fewer layers. To further enhance information flow, we implement inter- scale mixing operations, where nodes receive aggregated features from both higher- and lower-resolution represen- tations. Finally, the features from all scales are combined and projected back to the original graph for downstream tasks. Our architecture is given in Figure 2, and is detailed in Section 4.
2. Related Work
In this section, we overview several topics related to our work. Specifically, we discuss the over-squashing phe- nomenon in MPNNs and its connection to their receptive field, as well as review hicrarchical MPNN models.
Over-squashing in MPNNs. Over-squashing in MPNNs, which hampers information transfer across distant nodes (Alon & Yahav, 2021), has prompted various mit- igation strategies. Graph rewiring methods like SDRF (Top- ping et al., 2022) densify graphs as a preprocessing step, while approaches such as GRAND (Chamberlain et al., 2021 BLEND (Chamberlain et al., 2021 DRew (Gut- teridge al., 2023), and aAsyn (Chen et al., 2024) dy- namically adjust connectivity based on node features. Transformer-based models (Dwivedi & Bresson, 2021; Rampášek et al., 2022) bypass wee--squshin with all-to-all message- paataggg...sing..... Another direction uses non-local dynam- ics to enable dense communication, as in FLODE (Maskey et al., 2023), which leverages fractional graph shifts, QDC (Markovich, 2024) with quantum diffusion kernels, and G2TN (Toth et al., 2022), which captures diffusion paths, or weight space constraints (Gravina et al., 2024). While effective in mitigating over-squashing. these methods often increase computational complexity due to dense prop- agation operators. Moreover, they are often limited by their reliance on the original graph resolution, i.c., its number of nodes and edges.
Our Main Contributions are as follows:
We formalize the concept of effective receptive fields for MPNNs, drawing parallels to similar challenges in CNNs.
We propose IM-MPNN- - an architecture that leverages hierarchical coarsening and scale mixing expand the receptive field of GNNs without increasing computational complexity significantly.
Through experiments on benchmarks such as the Long-
Range Graph Benchmark (LRGB), we demonstrate the superior performance of IM-MPNN in capturing long- range dependencies and mitigating over-squashing
2

---

Improving the Effective Receptive Field of Message-Passing Neural Networks
The Receptive Field of MPNNS. We argue that the re- lation the receptive field can be mitigated by looking at coarser version of the graph. E.g., when considering single hop on the 2nd coarsened scale of a graph, it is related to a receptive field of about four hops. However, all the nodes along the way were used only once for the aggregation function, and therefore, the "exponential" in- crease in information is mitigated along this path. An earlier study by Nicolicioiu & Duta (2019) focuses on analyzing the ERF in GCNs and Self-Attentin layers and showing it on synthetic examples. In contrast, our work addresses the limitations of the ERF in GCNs by introducing IM-MPNN, a hierarchical multiscale framework that explicitly mitigates over-squashing and enhances long-range dependency mod- eling. Furthermore, we extend the evaluation to diverse benchmarks like LRGB, demonstrating both theoretical and practical improvements.
V-3
V-2
R-1
vo
V2
03
Figure 3: An infinitely-long linear graph.
efficient and scalable message-passing, and Eliasof et al. (2023a) develop a wavelet based multiscale approach for the compression of node features in GNNs. Lastly, in the con- text of beyond MPNNs, Luo (2023) and Zhang et al. (2022) introduced a hierarchical encoding mechanism for graph transformers, effecctvvlyy capturing multi-scale graph struc- ture using hierarchical distances to improve the expressive power of transformers.
3. Message-Passing Effective Receptive Field
In this section we formulate the effective receptive field of MPNNs. In particular, we draw inspiration from the analysis provided by Luo et al. (2016), where a CNN with n convolutional layer with kernel size is x k is considered, and it shown that for k 2 2 the contribution of each pixel in the theoretical receptive field of a certain output decays as squared exponential with respect to its distance from the output unit. Here, we provide evidence of similar effect on graphs processed with MPNNs.
GeniePath (Liu et al., 2019) introduces an adaptive path layer comprising two complementary functions: one for breadth exploration, which learns the importance of neigh- borhoods of varying sizes, and another for depth exploration, which filters signals aggregated from neighbors at different hops. This design allows the model to adaptively select the most relevant receptive field for each node, enhancing its ability to capture complex dependencies. Similarly, Ma et al. (2021) propose a structural adaptive receptive field mecha- nism that enables the network to adjust its receptive field in response to the underlying graph topology. By learning the optimal receptive field for each node, the model effectively balances the trade-off between capturing local and global information, thereby improving performance on tasks re- quiring an understanding of both. Ma et al. (2023) extend this idea by learning discrete adaptive receptive fields for GCNs, further enhancing their ability to model heteroge- neous graphs with varying local structures.
Notations. Throughout this paper we consider a graph G = (V,E) where V is a set of n nodes, and & C V x V is a set of m edges. Additionally, the graph can be described using its adjacency matrix A E Ruxn, which is a binary matrix whose (i. entry is one if (i. E E, and zero otherwise. We denote the graph Laplacian as L D A, where D is the graph degree matrix. The i-th node is associated with a hidden feature vector x E g with c features, which provides a representation of the node at the 8-th hidden layer of the network. The term x(O) [x) ,..., x 2 I is an n x e matrix that represents the nodes features of the f-th hidden layer.
Hierarchical MPNNs. Hierarchical approaches to GNNs
aim to leverage multiscale representations of graph data to enhance the modeling of both local and global structures. Gao & Ji (2019) developed the Graph U-Net architecture, which employs hierarchical pooling and unpooling opera- tions to capture multiscale features while preserving struc- tural information, making it well-suited for tasks requiring both fine- tme-ggriied and high-level graph representations (e.g., Yang et al., 2024). Collectively, these hierarchical methods provide robust foundation for addressing the limitations of traditional GNNs in terms of scalability and expressiveness. Zhong et al. (2023) proposed framework for hierarchical GNNs that combines localized node feature aggregation with hierarchical graph pooling to better handle large-scale and complex graphs. Similarly, Vonessen et al. (2024) in- troduced the concept of bierarchical support graphs, which builds layered representation of the graph to facilitate
3.1. Linear Graph Analysis
We start by analyzing the case of a linear, sequence-like graph without self-loops, as illustrated in Figure 3. Without loss of generality, we theoretically analyze the contribution of distant nodes to the central node Up, center after applying stack of graph convolutions with uniform weights.
Formally, given an infinitely- linear graph with nodes V {..., v-3, V- 1- ro, U1 U2, ......), ), and examine the feature value x of node og after l convoluution applica- tions. At O, the feature of up is initialized as:
x Up-
(1)
3

---

Improving the Effective Receptive Field of Message-Passing Neural Networks
At E 1, the feature of vp is influenced by its neighbors:
f-1 + v1-
[= 1, 0.005
3
[= 3, 0.005
At - = 2 and é = 3. the feature of uo depends on contribu- tions propagated through its neighbors:
5, 0.005
2
4xmt
x = x + = v-2 + 200 + 22
(3)
x x²1 + xf = v-3 3 301 + 23.
(4)
0
0.0
0.2
0.4
0.6
0.8
1.0
1.2
2
As the process continues, the contribution of all nodes to the feature xo after convolutions follows Pascal's triangle:
0.02
4xmt x(p. 0
0.02
t= =
x
Di=0 021-6
(5)
where ()) are the binomial coefficients.
0.0
0.2
0.4
1.0
1.2
To analyze the relative contribution of nodes, we normalize the coefficients by 27, so that the feature x corresponds to a probabilistic distribution. In particular, this yields the binomial distribution:
Ip 1 Pol
Figure 4: The spread of a point source in time according to Equation (12), for d = 2. For k 0.005, at time = 1 the ERF is about 0.3, while for t 5, it grew to about 0.6 only. The ERF is more spread for a higher value of k.
X~ B 2)
(6)
where the probability mass function of X describes the distribution of contributions to any node from node up.
where L is the graph Laplacian x are node features that evolve through time (the equivalent of layers), Xo are the initial node features, and the integration time T typically corresponds the number of layers used in the network.
Using this binomial distribution, the cumulative contribution of the left-most & nodes from ti (i.e., U-t, f- is:
P(X S k) = = (9 20
=)
Specifically, the interpretation proposed in models that rely on Equation (9), assumes that the graph Laplacian L dis- cretizes the continuous negative Laplacian - A, under some geometry in dimension d, i.e., node coordinates p E Raxdd up constant denoted by K. The coordinates p can be induced from given graph Laplacian, e.g., by considering the Laplacian cigenvectors (Belkin & Niyogi, 2001).
Using Hoeffding's inequality, we get the upper bound:
P(X s k) exp -)))
e)
That is, the relative contribution of nodes to the feature of to the limit decreases exponentially with their distance from vo. This decay is quantified by the binomial distribution's 's tail bound, indicating that distant nodes have exponentially smaller influence.
Then, Equation (9) is a discretization of the continuous partial differential equation (PDE)
aa(()) x.m(t), s(t Xo. e [0, (10) Öt
3.2. Characterizing the ERF on Graphs
Building on the linear graph case presented above, we now provide a qualitative analysis of the ERF in diffusion pro- cesses on graphs, which are the core mechanism of many GNN architectures that mimic the behavior of the diffusion ordinary differential equation (ODE), as studied by Nt & Maehara (2019); Chamberlain et al. (2021b); Eliasof al. (2023b); Choi et al. (2023) and others, as thoroughly re- viewed by Han et al. (2024). Such methods rely on the fact that diffusion- based GNNs can be thought of as a discretiza- tion of the diffusion ODE in time
where sxt)) is continuous feature vector in time t with associated coordinates function (i.c., is discrete version of the continuous map x on the coordinates p)-
Similarly to the discussion Section 3.1, we focus on the distribution of node features in time and space when the initial condition is given by a point source located at around Po E Rd. while all other coordinates have an initial feature of zero. Explicitly, this initial condition is given by:
x = 0) = Xo = 5(po),
(11)
0x
Dt = Lxx, x(t = 0) Xo. tE [O
(9)
where 6(-) Dirac's function. In this case, the solution of

---

Improving the Effective Receptive Field of Message-Passing Neural Networks
Equation (10) in an infinite domain Rdd (Pattle, 1959) is
Laplacian is expressed by the kernel
1
exp (- ||p poll 4xt
0 -1 0
x(p,t)= (ANT))//2
(12)
i =
4
-1
(13)
0 -1
From Equation (12), we gain two key insights: (i) the co- efficient multiplying the exponential term in Equation (12) shows that the signal decays in time, i... the node features norm decays over time; and (ii) the spatial behavior around the source point po decays exponentially. That is, we see that regardless of the dimension d, the influence of the source point on other points in space decays exponentially as we move away from the source po- Furthermore, we note that, as grows in the denominator inside the exponential term, which is equivalent to a deeper network since layer number takes the role of time 4, features continue to spread, but slow rate. In other words, the typical ERF in standard MPNNs is limited and behaves according to Equation (12). In Figure 4, we illustrate this behavior.
with no dependency on h. The continuous Laplacian is typically discretized with a grid constant 1/h?, to yield discrete operator An. i.c., A ~ D, = L Using a coarser grid with a step size 2h, for example, yields A x A2h = 1 L. That means that if we coarsen the grid by a factor of two, the effective discrete Laplacian op- erator coefficients decrease by a factor of four. Hence, the value of in Equation (12) multiplies by four, resulting in spatial distribution of Equation (12) that spreads faster for the coarser representation as also illustrated in Figure 4.
4h2
Interleaving Scales. The discussion above showed how utilizing coarser scales helps in expanding the ERF. How- ever, in many tasks, ERF is not the only property that is needed for a GNN obtain favorable performance. By using coarser scales (via pooling), we also lose informa- tion in our feature maps-mostly information that is given in
4. Interleaved Multiscale Message-Passing
Following our analyses in Section 3 on the limited ERF of MPNNs, we introduce IM-MPNN an approach to improve ERF through the lens of interleaved multiscale MPNNs. We start by discussing our design principles, motivated by the understandings from Section 3, followed by description of our method, and a complexity analysis.
feature maps. Hence, to obtain the best performance we must combine both high and low-resolution maps and graph operation to capture and fuse high- and low- frequency information, and have high ERF. We obtain this by applying network layers that use multiple graph levels in each block and fuse the information between them.
4.1. Design Principles
4.2. Interleaved Multiscale Message-Passing Networks
In this section we outline the main design choices on which we build our IM-MPNN, which we present in Section 4. Specifically, we discuss: (i) the contribution of multiscale feature processing with MPNNs; and (ii) the interleaving of different scales.
We now describe our IM-MPNN, which involves three main parts: (i) an MPNN backbone; (ii) pooling and unpooling layers; and (iii) an interleaving mechanism.
MPNN Backbone. Our IM-MPNN offers a generalist ap- proach for enhancing the ERF of existing and future MPNNs by utilizing interleaved multiscale representations of input graphs. Therefore, we consider the following general update rule for node features (O)
Multiscale Processing. The analysis in Section 3.2 showed that MPNNs suffer from an exponentially-deeeet decayiin ERF. We propose to alleviate this problem by consider- ing coarser representations of the input graph, obtained via graph pooling such as Graclus (Dhillon et al., 2007, more information in Appendix A). Different types of pooling procedures can also be considered (e.g., Ying et al., 2018).
x(++1) (PNN( (x(1); A),
(14)
where (P denotes the MPNN backbone used at the f-th layer. In our experiments in Section 5, we demonstrate the effectiveness of our IM-MPNN on several backbones.
We note that when considering different graph Lapla- cians L,, .n...... Lnng of different scales with resolutions (number of nodes) n > 122 > ... > Tik, we obtain equiv- alent representations of the continuous Laplacian (up to discretization differences), each with a different constant k. To understand this equivalence, let us consider a 2D mesh grid, where each node is connected to its four neighbors, and whose grid step-size is h. which determines the grid resolution, i.e., the number of nodes. In this case, the graph
Pooling and Unpooling. The second component of IM- MPNN involves the pooling and unpooling operations, which are essential to obtain a multiscale representation of input graphs and their features. Given a graph g = (V, E). we define the pooling operation to be an aggregation of node pairs in a pairing set P. That is, the node pairing P represents node pairs (v,, v2), ). that are aggregated into a
5

---

Improving the Effective Receptive Field of Message-Passingg Neural Networks
pooling operation, we revert the graph to the previous size:
A * UNPOOI. A P*),
(18)
where X E R,,, A E R In practice, we dis- tribute the feature at a pooled node in x= to its two corre- sponding nodes in the finer representation in x
q
(1,5)
((p-))
(2.
We note that is possible to stack several pooling and unpooling layers, as we do in our IM-MPNN. illustrated in Figure 2. To be specific, we coarsen the graph S times. The repeated pooling yields set of graphs {G. ) where Go = G is the original input graph, and G is the coarsest graph. We denote v" as a node from G.. and A as the adjacency matrix of g.. Note that each node De E V.. > 0 is a coarsening of several nodes of ug- ...., "g uf-1
Figure 5: Coarsening of a graph according given pairing (edges marked in red).
Scale 8 1
Ve-1. creating a relationship between nodes consecutive scales, shown in Figure 5.
Scale
q
Multiscale Interleaving. As illustrated in Figure 2, the S scales of the input graph G are maintained throughout the network, each with its own message-passing layer and a separate set of weights. That is, Equation (14) for scale s reads the following update rule:
Scale s
(p-9)
Figure 6: Scale-mix. Each node receives information from its parents' and children's 's nodes of consecutive scales.
xx =
A*).
(19)
However, without further modifications, those graphs will be processed separately. Therefore, we define multiscale interleaving mechanism, where relevant nodes of consecu- tive scales share information. Specifically, let us consider a node v (im.i.) from the s-th scale, and its related node +++ ((p.9)
new node vn in the pooled graph. More formally, the pooled graph g' = =(V" (V",E") E¹) is given by
V- = (16 o/ = 1,,,,, E P), E' = (1 v//) Fu, E 16 E (1, E E},
(15)
from the + 1)-th scale, and oi , uz from the (s 1)-th scale, as illustrated in Figure 6. We define:
ie., the edges in the pooled graph represent edges that isted in the original graph between components of node pairs in the pooled graph. Note that the procedure described in Equation (15) denotes a single pooling step, between two consecutive scales. Overall, we denote the transition between the s-th and the + 1-th scales as follows:
(+.++1) (-()))
(+.t) (=f
+ (o.e) 1 ((((--10)) + +x/ x
t2h 2 7(x
(x.4)
(20)
12h h2! are learnable weights for the lower-to- higher and higher-to-lower information passing.
where W-ss.)) W=(e,))
x +1 A ++1 PXOL(x", (x;,
(16)
where x x+1 E R A++1 E 1**11 and n,+1 = |P8| < ng. That is, the POOl. function takes the node fea- tures and adjacency matrix at the s-th level, and decreases the number of nodes to n, according to and some ag- gregation function (e.g., mean), and returns a coarsened representation of the node features and the adjacency matrix. In practice, we use the Graclus algorithm (Dhillon et al., 2007) to find pairs of nodes to be averaged, as follows:
Lastly, before the final head (classifier), we cast all the infor- mation back to the original graph nodes, by concatenating the features of the coarse nodes into their source node, which can be done by recursive unpooling and concatenating
(L,9) (4,), UNPOOL(Z(Lot)) A p*)], (21)
for s = S 1,...,0, where we start from (L.))) = x (L.S)
7 (x + x²).
(17)
4.3. Complexity of IM-MPNN
As described, a single IM-MPNN layer is constructed out of two steps, the first being an MPNN operation on each scale, and then scale-mix operation. An MPNN operation
Analogously, the unpooling layer applies the opposite oper- ation. Using the same node pairing pa of the corresponding
6

---

Improving the Effective Receptive Field of Message-Passing Neural Networks
Table 1:
Multiscale version of different GCNs for PascalVOC-SS and COCO-SP, increasing scales while re- ducing the width to stay within 500k params budget.
Table 2: Multiscale version of different GCNs for Peptides- func and Peptides-struct, increasing scales while reducing the width to stay within 500k params budget.
Method
scales
PaSCalVOC-SP Test F1 f
COCO-SP Test FI f
Method
scales
Peptides-fune Test AP f
Peptides-struct Test MAE +
GCN
0.0078
0.1338_0.0007
GCN
0.6860=20.00s
0.2460.20.0007
IM-GCN
0.2672
0.1655 20.051
IM-GCN
0.6822
0.2453 +0,0009
IM-GCN
2
0.284610.0008
0.1787=0.0016
IM-GCN
2
0.693640.o0m
0.2473
IM-GCN
3
0.2910 000005
0.1896 0009
IM-GCN
0.6942
20.22000000000 0083
0.2498 40.005
IM-GCN
4
0.2929 0.0058
0.1960=0.0023
IM-GCN
0.6907 00000
0.2473
GINE
0.271 0
0.2125=0.000p 00.0009
GINE
0.6621 000067
0.2473
IM-GINE
0.2757
0.2289 =0 0009
IM-GINE
0.6745 20.0022
0.2477
IM-GINE
2
0.2873 02277310.005 0.005
0.2387 =0.000 0.10
IM-GINE
0.6884=0.0027
0.2464-20.000s
IM-GINE
3
0.2909:: :: 0000074
0.2475
0.0017 0017
IM-GINE
0.6948 10.0034
0,2489
IM-GINE
4
0.2975 0.0088
0.2472
IM-GINE
4
0.6959 10.0021
0.2477:0.0015
GatedGCN
0.3880_00.0040
0.2922.20.0018
GatedGCN
0.6765
0.2477
MM-GatedGCN
0.4180 000002
0.3294=0.0021
IM-GateGGCN
0.67 00000
0.2456_000010
IM-GatedGCN
2
0_4299=+0.000
0,3453 =00507
IM-GatedGCN
0.67 17144++00 4000006
0.2469 +-000099
Il-GateeGGNN
3
0.4332:1..0m 0.0044
0,3501 =0.0033
IM-GatedGCN
0.6830 40.0037
0.2454 +000014
Gl-GGateGGNN
4
0.4317+0.0077
0.3414_0.006)
IM-GatedGCN
4
0.6773
0.2455
complexity is O([V|+ however, each of the operations is performed over a downscaled graph with a factor of 2. Hence, the time complexity of performing MPNN on all the scales (including the O-th scale) is
complexity of IM-MPNN) and measure the improvement
over them: (i) GCN (Kipf & Welling, 2016), (ii) Gat- edGCN (Bresson & Laurent, 2017), (iii) GINE (Hu et al., 2020), (iv) and GAT (Veličković et al., 2018).
8 Σo s=0
E 2
5.1. Long Range Graph Benchmark
O
(22)
2
Setup. We test our method on Long Range Graph Bench- mark (Dwivedi et al., 2022) following the improved evalua- tion (Tönshoff et al., 2023). The benchmark is constructed of several datasets with long-range dependencies and, there- fore, can be difficult for MPNNs. We take the same reported MPNN architecture, namely GCN (Kipf & Welling, 2016), GINE (Hu et al., 2020), and GatedGCN (Bresson & Lau- rent, 2017), and modify the architecture using our multiscale approach with different scales. Since an additional scale in- troduces more parameters, we reduce the channel dimension in order to stay within a budget of 500k parameters.
The scale-mix operation incorporates calculation that in- volves 4 nodes for every node on every scale, hence the time complexity is given by
s Σ
V 2
O
(2.V).
(23)
Hence, the time complexity of IM-MPNN is O ((V) + [E).
5. Experimental Results
We see a significant increase in scores, of up to 41% relative improvement on both Pascalvoc-SP and COCO-SP, see Table 1. While peptide-fune and peptide- struct (Table 2) are less affected by different configurations, we still see slight advantage in using our multiscale archi- tecture.
Results.
Objectives. We evaluate IM-MPNN and compare it with various methods. Specifically, we seek to address the follow- ing questions: (i) How effective is IM-MPNN at propagating information to distant nodes? And how well it predicts graph properties related to long-range interactions? (Section 5.2) (ii) How does IM-MPNN perform on real-world long-range benchmarks? (Sections 5.1, 5.3 and 5.4) (iii) How well does IM-MPNN perform with different message- message-passing proto- cols? (Sections 5.1 and 5.4). Additional experiments are available in Appendix E.
5.2. Graph Transfer
Setup. We consider a graph transfer task (Di Giovanni et al., 2023), where the goal is to transfer a label from a source to a target node with a distance of & hops, using a network of depth k. We note that this task can be effectively solved only by non-dissipative methods that preserve source information.
Baselines. We evaluate IM-MPNN with several message- passing protocols with linear complexity (similar to the
7

---

Improving the Effective Receptive Field of Message-Passing Neural Networks
Ring
Crossed-Ring
CliquePath
100
100
100
Accuracy (%)
50
50
50
0
0
0
10
20
30
40
60
10
20
30
50
60
10
20
30
40
50
60
Distance from source target
Distance from source to target
Distance from source to target
GCN IM-GCN S=1
IM-GCN S=2
IM-GCN S=3
--3 -anndom Guessing
Figure 7: Graph transfer results over three graph types (ring, crossed-ring, and cliquepath). The network depth (i.e. number of layers) is the same the distance between the source and the target node. We see that adding more scales to IM-GCN improves the ability of the network to transfer information across long distances.
We consider three graph distributions, i.e., ring, crossed-ring, and clique-path with distances & ... 65). Increasing increases the task complexity. When using IM-GCN, we decrease the number of channels according to the number of scales for fair comparison. Appendix C.1 provides additional details about the task and the datasets.
Table 3: Results of test accuracy (1) on City-Networks.
.2....65]
Method
scales
Paris
Shunghai
Los Angeles
London
GCN
47,3 47.310.
52.4
45.9
43.8_oa
IM-GCN
54.420.2
63.420
59.820.2
53.820a
IM-GCN
54.9102
65.8
61.620.2
57.1201
IM-GCN
55.3
66.740.3
62.220.2
58.4
IM-GCN
54.940.2
67.8
62.4
58.9_o.1
Results. Figure 7 reports the results on the graph trans- fer tasks. Overall, compared to GCN, IM-GCN show increase in the ability to transfer information over long dis- tances. E.g. for CliquePath, where GCN start failing at around & = 7 while IM-GCN with scales=3 still have 100% accuracy at around 37.
5.4. Heterophilic Node Classification
Setup. We evaluate IM-MPNN on five heterophilic node classification benchmarks introduced by Platonov et al. (2023): Roman-Empire, Tolokers, and Questions. The datasets span variety of domains, from natural language and e-commerce to crowd- sourcing and synthetic grids, each exhibiting weak ho- mophily and requiring models to reason beyond local neigh- borhoods. We follow the original experimental setup. train- ing models with the AdamW optimizer for up to 300 epochs on the official splits, without additional hyperparameter tun- ing. Additional details are provided in Appendix C.4.
BraazonnRaaings,, Minesweeper,
5.3. City-Networt
Setup. We evaluate IM-MPNN on the City-Networks benchmark (Liang et al., 2025), a recently introduced large- scale dataset based on real-world city road networks de- signed to test long-range dependencies in graph learning (see Appendix C.3 for details). Derived from real-world city road maps (Paris, Shanghai, Los Angeles, and London) using OpenStreetMap data, the graphs feature between 100k and 570k nodes with significantly larger diameters (over 100-400) compared to traditional datasets. Following the original setup, we train each model for 20k epochs using AdamW with learning rate of 10-3 and a weight decay of 10-5, and do not perform any additional hyperparameter tuning across runs to maintain consistency with the baseline protocol.
Results. We benchmark IM-MPNN with results from Platonov et al. (2023); Finkelshtein et (2024); Behrouz & Hashemi (2024); Müller et al. (2024) and find it achieves competitive performance, often surpassing state-of -httrrrrt methods. Our results reported in Table with additional comparisons in Table 6. Notably, the competitive perfor- mance on larger graphs and complex heterophilic scenarios while retaining the linear complexity of standard MPNNs, further highlights its effectiveness compared to Graph Trans- formers and seerroohily-designnat GNNs.
Results. The results are reported in Table 3. When using IM-GCN, we see a significant increase in accuracy com- pared to the GCN baseline of between +10% and +16.5%, when using the IM-MPNN version of the network.
8

---

Improving the Effective Receptive Field of Message-Passing Neural Networks
Table 4: Mean test set score and standard deviation are averaged over four random initializations on heterophilic datasets. First, second, and third best results per task are color-coded. Additional comparisons are provided Table
Roman-cmpire
Amazon-ratings
Minesweeper AUC
Tolokers AUC
Questions AUC
Model
Ascuracy 1
Accuracy 1
Graph Transformers
Exphormer
89.03_0.m. 0.33
53.51 46.46
90.74.0.55
83.77
13.94
GOAT
71.59 1.25
44.61 10.50
81.0911.00
83.1111.04
75.7611.66
GeSeec,Perfomer (RWSE)
84.72_0.65
48.08 +0.85
92.88
84.81
76.45
GPSaAT-Pafoome (RWSE)
87.04_0.58
49.92+t0.6
91.08
84.3840.01
17.14
GT-sep
87.32_0.39
$2.18
92.29
82.52
78,05
Eaterophily-Desiinatte GNNs
FSGNN
79.92_0.56
52.74
90.08
82.7620.61
78,8640.92
GBK-GNN
74.57
45,98 40.71
90.85
81.01 +0.07
40.47
JacobiConv
71.14 U.44
43.55 40.48
89.6644..4
68.66
43.88+1.16
MPNNs
GCN
73.69
48.70
89.75
83.64
76.09+1.27
Gated-GCN
74.46_0.54
43.00
87.54 1.22
41.14
76.61
GAT
80.87
49. 49.09 19.0990.60 60.63
92,01 #0.68
83.70+0.47
47.43
GAT-sep
88.75
52.70
93,9 1:0.35
83.7810.48
76.7940.71
CO-GNN(E, Σ)
91.57 0.32
51.28
95.09 1:11
83.36.1089
80.02
CO-GNN(J. p))
91.37
54.17 10.37
97.31 10.41
84.45
16.54
Interleaved Multiscale (Ours)
IM-GCN
83.53 0.57
52.37 #0066
91.80.10.54
40.17
78.17
IM- GatedGCN
90.82 0.59
54.01 10.27
97.32 20.83
85.10
79.27 4:0.91
IM-GAT
84.48 -0.32
51. 51.1620.55
92.68
85.21
77.98
IM-GAT-sep
89.93_0.34
53.97
96.15
85,44
77.92
IM-CO-GNN(E, Σ)
92.08 0.33
53.11
95.79
85.25
80.49 10.92
IM-CO-GNN(H,P) p))
-2.00-u.41 -0.41
54.43
40.39
85.77
78.92
6. Conclusion
National Science Foundation (NSF), by Israel Science Foun- dation Personal Grant #360/21, by the Lynn and William Frankel Center BGU CS, and by the Israeli Council for Higher Education (CHE) via the Data Science Research Center BGU. S.E.F's work was supported by the BGU's Hi-Tech Scholarship. S.E.F's and R.S.W.'s work was also supported by the Kreitman School of Advanced Graduate Studies. M.E. is funded by the Blavatnik- Caabbride fellow- ship. the Cambridge Accelerate Programme for Scientific Discovery, and the Maths4DL EPSRC Programme.
In this work, we have presented novel approach, In- terleaved Multiscale Message-Passing Neural Networks (LM-MPNN), that effectively addresses the limitations of MPNNs in capturing long-range dependencies and their lim- ited effective receptive field (ERF). By enhancing the ERF of MPNNs while maintaining their linear computational complexity in graph size, our method introduces hierarchi- cal coarsening and scale-mixing mechanisms to extend the receptive field of GNNs without sacrificing efficiency.
Through extensive theoretical and experimental evaluations, we demonstrated the advantages our method across di- verse datasets, including benchmarks with long-range de- pendencies, heterophilic settings, and large-scale graphs. Our results consistently highlight the superior performance of IM-MPNN in both predictive accuracy and computational efficiency, even when compared to state-of-th the- methods like Graph Transformers and sieerophil-ddesinaaie GNNs.
Impact Statement
This paper presents method for improving the limited ERF in GNNs. Generally, this improves the performance of existing standard GNNs and may contribute to any field in which unstructured data is processed using GNNs. We are not aware of possible negative societal impacts of our research.
Acknowledgments
References
This work was supported in part by Grant No 2023771 from the United States-Israel Binational Science Founda- tion (BSF), by Grant No 2411264 from the United States
Abu-El Abu-El-Haija. S., Perozzi, B., Kapoor, A., Alipourfard, N., Lerman, K., Harutyunyan, H., Ver Steeg, G., and Gal- styan, A. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In in-

---

Improving the Effective Receptive Field of Message-Passingg Neural Networks
ternational conference on machine learning, 2019.
Di Giovanni, F., Giusti, L., Barbero, F., Luise, G., Lio, P., and Bronstein, M. M. On over-squashing in message passing neural networks: The impact of width, depth, and topology. In International Conference on Machine Learning, pp. 7865-7885. PMLR, 2023.
Achanta, R., Shaji, A., Smith, K., Lucchi, A., Fua, P., and Süsstrunk, S. Slic superpixels, 2010.
Alon, U. and Yahav, E. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2021.
Ding, X., Zhang, X., Han, J., and Ding, G. Scaling up your kernels to 31x31: Revisiting large kernel design in cnns. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 11963- 11975, 2022.
Behrouz, A. and Hashemi, F. Graph Mamba: Towards Learning on Graphs with State Space Models. arXiv preprint MiXiv:2402.08777 2024.
Belkin, M. and Niyogi, P. Laplacian eigenmaps and spectral techniques for embedding and clustering. Advances in neural information processing systems, 14, 2001.
Du, L., Shi, X., Fu, Q., Ma, X., Liu, H.,, Han, S., and Zhang, D. Gbk-gnn: Gated bi-kernel graph neural networks for modeling both homophily and heterophily. In Proceed- ings of the ACM Web Conference 2022, pp. 1550-1558, 2022.
Bo, D., Wang, X., Shi, C., and Shen, H. Beyond low- frequency information in graph convolutional networks. Proceedings of the AAAI Conference on Artificial Intelli gence, 35, 2021. doi: 10. 10.1609/aaai.v33 v35.5.166144
Dwivedi, V. P. and Bresson, X. A generalization of trans- former networks to graphs. AAAI Workshop on Deep Learning on Graphs: Methods and Applications, 2021.
Bresson, X. and Laurent, T. Residual gated graph convnets. arXiv preprint arXiv:1711.07553. 2017.
Dwivedi, V. P., Rampášek, L.,, Galkin, M., Parviz, A., Wolf, G., Luu, A. T.,, and Beaini, D. Long range graph bench- mark. Advances in Neural Information Processing Sys- lems, 2-:22226-22340, 2022.
Cappart, Q., Chételat, D., Khalil, E. B., Lodi, A., Morris, C., and Veličković, P. Combinatorial optimization and rea- soning with graph neural networks. Journal of Machine Learning Research, 24(130):1-61, 20233.
Eliasof, M., Bodner, B. J., and Treister, E. Haar wavelet feature compression for quantized graph convolutional networks. IEEE Transactions on Neural Networks and Learning Systems, 2023a.
Chamberlain, B., Rowbottom, J., Eynard, D., Di Giovanni, F., Dong, X., and Bronstein, M. Beltrami flow and neural diffusion on graphs. Advances in Neural Information Processing Systems, 34:1594-1609, 2021a.
Eliasof, M., Ruthotto, L.,, and Treister, E. Improving graph neural networks with learnable propagation operators. In International Conference on Machine Learning, pp. 9224-9245. PMLR, 2023b.
Chamberlain, B. P., Rowbottom, J., Gorinova, M., Webb, S., Rossi, E., and Bronstein, M. M. GRAND: Graph neural diffusion. In International Conference on Machine Learning, 2021b.
Everingham, M., Van Gool, L., Williams, C. K., Winn, J., and Zisserman, A. The paseal visual object classes (voc) challenge. International journal of computer vision, 88: 303-338, 2010.
Chen, J., Liao, T., Chen, C., and Zheng, Z. Improving message- message-passing passing gnns by asynchronous aggregation. In Proceedings of the 33rd ACM International Conference on Information and Knowledge Management, pp. 228- 238, 2024.
Fan, W., Ma, Y., Li, Q., He, Y., Zhao, E., Tang, J., and Yin, D. Graph neural networks for social recommendation. In The world wide web conference, pp. 417-426, 2019.
Chien, E., Peng, J.. Li, P., and Milenkovic, O. Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations, 2021.
Finder, S. E.,, Amoyal, R., Treister, E., and Freifeld, O. Wavelet convolutions for large receptive fields. In Eu- ropean Conference on Computer Vision, pp. 363-380. Springer, 2024.
Choi, J., Hong. S., Park, N., and Cho, S.-B. Gread: Graph neural reaction-diffusin networks. In International Con- ference on Machine Learning, pp. 5722-5747. PMLR, 2023.
Finkelshtein, B., Huang, X., Bronstein, M. M., and Cey- lan, I. Cooperative graph neural networks. In Inter- national Conference on Machine Learning, pp. 13633- 13659. PMLR, 2024.
Dhillon, I. S., Guan, Y., and Kulis, B. Weighted graph cuts without eigenvectors a multilevel approach. IEEE transactions on pattern analysis and machine intelligence, 1951,) 2007.
Gao, H. and Ji, S. Graph u-nets. international conference on machine learning, pp.
PMLR, 2019.
10

---

Improving the Effective Receptive Field of Message-Passingg Neural Networks
Gasteiger, J., Weißenberger, S., and Günnemann, S. Diffu- sion improves graph learning. Advances in neural infor- mation processing systems, 32, 2019.
Lin, T.-Y., Maire, M., Belongie, S., Hays, J., Perona, P., Ra- manan, D., Dollár, P., and Zitnick, C. L.. Microsoft coco: Common objects in context. In Computer Vision-ECCV 2014: 13th European Conference, Zurich, Switzerland, September 6-12, 2014, Proceedings, Part V 13, pp. 740- 755. Springer, 2014.
Gravina, A., Eliasof, M., Galliechio, C., Bacciu, D., and Schönlieb, C.-B. Tackling graph oversquashing by global and local non-dissipativity arXiv preprint arXiv:2405.01009 2024.
Liu, Z., Chen, C., Li, L., Zhou, J., Li, X., Song, L., and Qi, Y. Geniepath: Graph neural networks with adaptive receptive paths. In Proceedings of the AAAI Conference Artificial Intelligence, 2019.
Gutteridge, B., Dong, X., Bronstein, M. M., and Di Gio- vanni, F. Drew: Dynamically rewired message pass- ing with delay. In Interaational Conference on Machine Learning, 2023.
Luo, W., Li, Y., Urtasun, R., and Zemel, R. Understanding the effective receptive field in deep convolutional neural networks. Advances in neural information processing systems, 29, 2016.
Hamilton, W., Ying, Z., and Leskovec, J. Inductive repre- sentation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Luo, Y. Transformers for capturing multi-level graph struc- using hierarchical distances. CoRR, 2023.
Han, A., Shi, D., Lin, L., and Gao, J. From continuous dynamics to graph neural networks: Neural diffusion and beyond. Transactions Machine Learning Research, 2024. ISSN 2835-8856.
Ma, X., Wang, J., Chen, H., and Song, G. Improving graph neural networks with structural adaptive receptive fields. In Proceedings of the Web Conference 2021, pp. 2438- 2447, 2021.
Hu, W., Liu, B., Gomes, J., Zitnik, M., Liang, P., Pande, V., and Leskovec, J. Strategies for pre-training graph neu- ral networks. In International Conference Learning Representations, 2020.
Ma, X., Li, Z., Song. G., and Shi, C. Learning discrete adap- tive receptive fields for graph convolutional networks. Sci- ence China Information Sciences, 66(12):22210, 2023.
Kipf, T. N. and Welling, M. Semi-supervised classifica- tion with graph convolutional networks. arXiv preprint arXiv: 1609,02907, 2016.
Markovich, T. QDC: Quantum diffusion convolution kemels graphs. Transactions Machine Learning Research, 2024.
Kong, K., Chen, J., Kirchenbauer, J., Ni, R., Bruss, C. B., and Goldstein, T. GOAT: A global transformer on large- scale graphs. In Proceedings of the 40th International Conference on Machine Learning, 2023.
Maskey, S., Paolino, R., Bacho, A., and Kutyniok, G. A fractional graph laplacian approach to oversmoothing. Advances in Neural Information Processing Systems, 36: 13022-13063, 2023.
Kreuzer, D.,. Beaini, D., Hamilton, W., Létourneau, V., and Tossou, Rethinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 02221188-21299 2021.
Maurya, S. K., Liu, X., and Murata, T. Simplifying approach to node classification in graph neural networks. Journal of Computational Science, 62: 10:101, 2022.
Müller, L.., Galkin, M., Morris, C., and Rampášek, L. At- tending to graph transformers. Transactions on Machine Learning Research, 2024. ISSN 2835-8856.
Li, X., Zhu. R., Cheng, Y., Shan, C., Luo, S., Li, D., and Qian, W. Finding global homophily in graph neural networks when meeting heterophily. In Proceedings of the 39th International Conference Machine Learning, 2022.
Nicolicioiu, A. and Duta, Effective receptive field of graph neural networks, 2019.
Liang, H., Borde, H. S. d. O., Sripathmanathan, B., Bron- stein, M., and Dong, X. Towards quantifying long- range interactions in graph machine learning: large graph dataset and a measurement. arXiv preprint arXiv:2503.09008,, 2025.
Nt, H. and Machara, T. Revisiting graph neural net- works: All have is low-pass filters. arXiv preprint arXiv: 1905//055000. 995.09550, 2019.
Pattle, R. E. Diffusson from an instantancous point source with siicentration-depeneenn coefficient. The Quar- terly Journal of Mechanics and Applied Mathematics, 12 (4):407-400 1959.
Likhobaba, D., Pavlichenko, N., and Ustalov, D. Toloker graph: Interaction of crowd annotators, 2023.

---

Improving the Effective Receptive Field of Message-Passingg Neural Networks
Platonov, O., Kuznedelev, D., Diskin, M., Babenko, A., and Prokhorenkova, I.. A critical look the evaluation of GNNs under heterophily: Are we really making progress? In The Eleventh International Conference on Learning Representations, 2023.
Yang, Y., Wu, Q. He, B., Peng, H., Yang, R., Hao, Z., and Liao, Y. Sehot: Structural entropy guided multi- view contrastive learning for social bot detection. In Proceedings of the 30th ACM SICKDD Conference on Knowledge Discovery and Data Mining, pp. 3841-3852, 2024.
Rampášek, L., Galkin, M., Dwivedi, V. P., A. T. Wolf, G., and Beaini, D. Recipe for a general, powerful, scal- able graph transformer. Advances in Neural Information Processing Systems, 35:14501-14514 2022.
Ying, Z., You, J., Morris, C., Ren, X.,, Hamilton, W., and Leskovec. J. Hierarchical graph representation learning with differentiable pooling. Advances in neural informa- tion processing systems, 31, 2018.
Shi, Y., Huang, Z., Feng. S., Zhong. H., Wang. W., and Sun, Y. Masked label prediction: Unified message passing model for semi-supervised classification. In Proceedings of the Thirtieth International Joint Conference on Artifi- International Joint Con-
Zhang, Z., Liu, Q. Hu, Q. and Lee, C.-K. Hierarchi- cal graph transformer with adaptive node sampling. Ad- vances in Neural Information Processing Systems, 35: 21171-21183, 2022.
cial Intelligence, pp. ferences on Artificial Intelligence Organization, 2021.
Zhong. Z., Li, C.-T., and Pang, J. Hierarchical message- passing graph neural networks. Data Mining and Knowl- edge Discovery, (7(1):38-4408 2023.
Shirzad, H., Velingker, A., Venkatachalam, B., Sutherland, D. J., and Sinop, A. K. Exphormer: Sparse transform- ers for graphs. In International Conference on Machine Learning, pp. 31613-31632. PMLR, 2023.
Zhu, J., Yan, Y., Zhao, L., Heimann, M., Akoglu, L., and Koutra, D. Beyond homophily in graph neural networks: Current limitations and effective designs. In Advances in Neural Information Processing Systems, 2020.
Shlomi, J., Battaglia, P., and Vlimant, J.-R. Graph neural networks in particle physics Machine Learning: Science and Technology. 2(2):021001, 2020.
Zhu, J.. Rossi, R. A., Rao, A., Mai, T., Lipka, N., Ahmed, N. K., and Koutra, D. Graph neural networks with het- erophily. Proceedings of the AAAI Conference on Artifi- cial Intelligence, 2021. doi: 10. 16.1/a/aaai, wwi.i...111133333....
Tönshoff, J., Ritzert, M., Rosenbluth, E., and Grohe, M. Where did the gap go? reassessing the long-range graph benchmark. arXiv preprint arXiv:2309.0033 00367, 2023.
Topping, J., Di Giovanni, F., Chamberlain, B. P., Dong, X., and Bronstein, M. M. Understanding over-squashing and bottlenecks on graphs via curvature. In International Conference Learning Representations, 2022.
Toth, C., Lee, D., Hacker, C., and Oberhauser, H. Capturing graphs with hypo-elliptic diffusions. Advances in Neural Information Processing Systems, 35:38803-38817, 2022.
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., and Bengio, Y. Graph attention networks. In International Conference on Learning Representations, 2018.
Vonessen, C., Grötschla, F., and Wattenhofer, R. Next level message-passing with hierarchical support graphs. arXiv preprint ar Arv:224066. 15852, 2024.
Wang, X. and Zhang, M. How powerful are spectral graph neural networks. In International conference on machine learning, pp. 23341-23362, PMLR, 2022.
Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
12

---

Improving the Effective Receptive Field of Message-Passinng Neural Networks
A. On Graclus
The Graclus algorithm is an efficient, non-parametric graph clustering method commonly utilized for hierarchical pooling in graph neural networks (GNNs). Originally, Graclus employs a multilevel clustering strategy-consisting consisting of graph coarsening by iteratively merging node pairs based on edge weights, performing initial clustering on the reduced graph, and refining the partitions during successive uncoarsening steps. This process efficiently approximates graph partitioning objectives like normalized cut without computationally intensive eigenvector computations.
In practice, particularly within frameworks such as PyTorch Geometric (PyG), simplified version of Graclus is used. PyG's implementation performs a single-pass greedy clustering, pairing each node with its highest-weighh neighbor to approximately halve the graph size at each pooling step. This variant omits the refinement phase and the broader multilevel approach of the original algorithm, prioritizing computational efficiency and GPU compatibility. IM-MPNN specifically, we further simplify by using this PyG implementation in an unweighted manner, clustering node pairs without considering edge weights.
It is important to note that IM-MPNN does not rely on the coarsening algorithm and can be easily modified to work with any alternative for the simplified Graclus clustering.
B. Choosing the Number of Scales
The number of scales used in IM-MPNN is hyperparameter that requires empirical tuning, analogous other architectural parameters such as depth and width. However, intuitive guidance can be drawn from structural and attribute properties of the input graph. Graphs with larger diameters naturally benefit from additional coarsening levels, as these allow the model to capture interactions occurring across longer distances by aggregating information into nodes at progressively coarser scales. Conversely, once nodes at the coarsest scale represent substantial portions of the graph, further increases in the number of scales typically yield diminishing returns. Another relevant factor is the attribute homophily of the graph: graphs with high homophily, where nodes predominantly connect similar nodes, might require fewer scales because local neighborhoods already provide substantial predictive information. In contrast, heterophilic graphs-wa where informative node interactions more dispersed-coul benefit from additional scales, enabling effective aggregation of meaningful signals from more distant regions.
C. Datasets and Experimental Settings
C.1. Graph Transfer
Dataset. The graph transfer task follows the settings Giovanni et al. (2023). each graph, a one-hot label assigned to a target node at distance l from the source, and a constant unitary feature vector assigned to all other nodes. Graphs were sampled from three different distributions: ring, crossed-ring, and clique-path (see Figure 8 for visual exemplification). In ring graphs, the nodes form cycle of size n, with the source and target placed [n/2] apart. Similarly, crossed-ring graphs consisting of cycles of size but introduced additional edges crossing intermediate nodes, while still maintaining source-targe distance of [n/2]. Lastly, the slique-path graph contains clique of size [n/2] followed by path of length [n/2]. The source node is placed in the clique and the target is at the other end of the path. Our experiments focus on a regression task aimed at assigning the target label of the target to the source node. all graphs, we refer to the distance between the source node and the target node as l regardless of the number of nodes in the graph.
(a) Ring
(b) Crossed-Ring
(c) Clique-Path
Figure 8: Line, ring, and crossed-ring graphs where the distance between source and target nodes is equal to 5, Nodes marked with "S" are source nodes, while the nodes with a "T" are target nodes.
13

---

Improving the Effective Receptive Field of Message-Passingg Neural Networks
Experimental Setting. We design each model as a combination of three main components. The first is the encoder which maps the node input features into latent hidden space; the second is the graph convolution (i.e., IM-MPNN or the other baselines); and the third is readout that maps the output of the convolution into the output space. The encoder and the readout share the same architecture among all models in the experiments.
We use the same hyperparameters given by Di Giovanni et al. (2023), with the only difference being reducing the number of channels when increasing the number of scales for a fair comparison (i.e., increased width might help against the other causes of over-squashing. For each model configuration, we perform 3 training runs with different weight initialization and report the average and standard deviation of the results.
C.2. Long Range Graph Benehmark
Dataset. To assess the performance on real-world long-range graph benchmarks, we considered the Pascalvoc-SP, COCO-
SP, Peptides-fune, and Peptides-struct datasets from the Long Range Graph Benchmark (Dwivedi et al., 2022).
The PS and COCO-SP datasets are based Pascal VOC 2011 image dataset (Everingham et al., 2010) and MS COCO image dataset (Lin et al., 2014), where each image is divided into coherent regions called superpixels based on the SLIC algorithm (Achanta et al., 2010). Each image is then graph whose nodes are its superpixels which are connected with an edge if they share a boundary. The task of both datasets is node classification which predicts the label of the semantic segmentation of the original datasets. Pascalvoc-SP contains I 11,355 graphs, with a total of 5.4 million nodes. COCO-SP contains 123,286 graphs, with a total of 58.8 million nodes.
The peptides-related graphs represent ID amino acid chains, with nodes corresponding to the heavy (non-hydrogen) atoms of the peptides, and edges representing the bonds between them. reptides-func is multi-label graph classification dataset containing 10 classes based on peptide functions, such as antibacterial, antiviral, and cell-cell communication. Peptides-struct is a multi-label graph regression dataset, focused on predicting 3D structural properties of peptides. The regression tasks involve predicting the inertia of molecules based on atomic mass and valence, the maximum atom-pair distance, sphericity, and the average distance of all heavy atoms from the plane of best fit. Both datasets, Peptides-fung and Peptides- struct, consist of 15,535 graphs, encompassing total of 2.3 million nodes.
For all datasets, we used the official splits as by Dwivedi et al. (2022), and reported the average and standard-deviatinn performance across 3 seeds.
Experimental Setting. We employ the same datasets and experimental setting presented by Tönshoff et al. (2023), an improved hyperparameter tuning for the LRGB dataset. We used the reported hyperparameters, changing the number of scales while using our IM-MPNN variant, and only modifying the number of channels to accommodate for the change in the number of parameters order to stay within the 500K parameter budget. For each model configuration, we perform training runs with different weight initialization and report the average of the results.
C.3. City-Networks Benchmark
Dataset. City-Networks (Liang et al., 2025) is a recently introduced benchmark specifically designed to evaluate the ability of graph neural networks (GNNs) to capture long-ram long-range dependencies. Traditional graph learning benchmarks often involve graphs with small diameters and relatively limited structural complexity, where most tasks can be solved using information aggregated from immediate or short-range neighbors. In contrast, -ity-Net provides more challenging setting that demands explicit modeling of long-range interactions across large graphs.
The dataset is constructed from real-world road networks of four major cities-Paris Shanghai, Los Angeles, and Lon- Kon-using data extracted from OpenStreetMap. Each graph contains between 100,000 and 570,000 nodes, making them several orders of magnitude larger than common benchmark graphs. Furthermore, these graphs exhibit very large diameters, typically ranging from 100 to over 400, ensuring that many node pairs are separated by long paths. This structural property makes City- fity-Networks particularly suitable for assessing how well GNN can propagate information across extended distances.
Each node in the dataset is associated with a set of geographic and road-related features, such as spatial coordinates, road type, and additional local attributes derived from the map data. The labels are not based on external metadata but are generated using an approximation of node eccentricity the maximum distance from a node to any other node in the graph. This task setup emphasizes the need for models to gather and process information from distant nodes, rather than relying
14

---

Improving the Effective Receptive Field of Message-Passingg Neural Networks
solely local neighborhood structures.
Another notable aspect of City-Networks is its transductive nature: models are trained and evaluated on the same graph, as opposed to inductive settings where generalization to unseen graphs is required. This design choice aligns with the benchmark's ' primary goal of probing long-range information flow within a fixed large structure, rather than testing generalization across different domains.
Experimental Setting. We follow Liang et al. (2025) training procedure of 20k epochs, batch size of 20k, learning rate of 10-3 and weight decay of 10-5 The model evaluated for accuracy every 100 epochs, and the model with the best validation is saved for final testing. All the scenarios are repeated 5 times, and report their means and standard deviations.
C.4. Heterophilic Node Classification
Dataset. We evaluate IM-MPNN on the Roman Empire, Amazon Amazon-Ratings, Minesweeper, Tolokers, and Questions tasks from (Platonov et al., 2023). Roman-Empire is derived from Wikipedia, where nodes represent words and edges connect syntactically related or sequential words. The task involves classifying words into 18 syntactic roles. The graph is chain-like with sparse connectivity and long-range dependencies. Amazon-Rativg models an Amazon product co- co-purchasing network. Nodes represent products, edges connect frequently co-purchased items, and the goal is to predict average product ratings (five classes). Node features are fastText embeddings of product descriptions. Minesweeper is a synthetic dataset based on a 100x 100 grid. Nodes represent cells, edges connect neighbors, and 20% of nodes are designated as mines. The task to predict mine locations using one-hot-encoded neighboring mine counts as features. Tolokers based on the Toloka crowdsoureing platform (Likhobaba al., 2023). Nodes represent workers (tolokers), edges indicate collaboration, and the task is to predict whether worker has been banned, using profile and performance features. Questions originates from the Yandex Q guestion-answering platform. Nodes represent users, edges connect those who have interacted by answering each other's questions, and the goal is to predict user retention. Node features are derived from user descriptions. A summary of the dataset statistics is provided in Table 5.
Experimental Setting. We follow the training and evaluation protocols from Platonov et al. (2023), and partieular follow the same splits. For hyperparameters, we consider learning rates and weight decays in the range of 1e 5 to 1e 3 using the A optimizer, and we consider 2, 3, 4, 8 scales within our IM-MPNN framework.
Additional Comparisons. In addition to the benchmarking provided in Section 5, and in particular in Table 4, we provided additional comparisons with more baselines in Table 6, showing that also in this case, our IM-MPNN offers similar or better performance, while maintaining linear complexity with respect to the graph number of nodes and edges. We consider a range of models, including classical JPPNN-bsed methods such as GCN (Kipf & Welling, 2016), GraphSAGE (Hamilton et al., 2017), GAT (Veličković et al., 2018). GatedGCN (Bresson & Laurent, 2017), GIN (Xu et al., 2019), GINE (Hu et al., 2020), and CoGNN (Finkelshtein et al., 2024); heterophily-speccin 2021), FAGCN (Bo al., 2021), GPR-GNN (Chien et al., 2021), FSGNN (Maurya et al., 2022), GloGNN (Li et al., 2022), GBK-GNN (Du et al., 2022), and JacobiCony (Wang& & Zhang. 2022); Graph Transformers such as Transformer (Dwivedi & Bresson, 2021), GT (Shi et al., 2021), SAN (Kreuzer et al., 2021), GPS (Rampášek et al., 2022), GOAT (Kong et al., 2023), and Exphormer (Shirzad et al., 2023); Higher-Ordee Order DGNs like DIGL (Gasteiger et al., 2019), MixHop (Abu-El-Haija et al., 2019), and DRew (Gutteridge et al., 2023).
models like H2GCN (Zhu al., 2020), CPGNN (Zhu et al..
Table 5: Statistics of the heterophilic node classification datasets.
Roman-empire
Amazon-ratings
Minesweeper
Tolokers
Questions
N. nodes
22,662
24,492
10,000
11,758
48,921
N. adges
32,927
93,050
39.402
519,000
153,540
Avg degree
2.91
7.60
7.88
88,28
6.28
Diameter
6,824
Node features
300
300
10
301
Classes
18
2
Edge homophily
0.05
0.38
0.68
0.59
0.84
15

---

Improving the Effective Receptive Field of Message-Passing Neural Networks
Table 6: Mean test set score and standard deviation are averaged over four random weight initializations on heterophilic datasets (higher better).
Roman-empire
Amazon-ratings
Minesweeper AU
Tolokers AUCT
Questions AUC
Model
Accurscy 1
Accuracy 1
MPNNs
GAT
80.87
49.09
92.01 92.0120.66 20.68
83.70
77.43+1.20
GAT-sep
88.75_0.41
52.70
93,9 10.35
83.7840.43
76.79+0.71
GAT (LapPE)
84.80
40.90
93.50
84.9940.54
76.55+00.4
GAT (RWSE)
86.62_u.5a
48.58 40.41
92.53 00.63
85.02++..07
77.83+1.22
GAT (DEG)
85,51
51.65 60.60
23,044t..oo
84.22++0.a
17.10+1.25
Gated-GCN
74.46_0.54
43.00
87 1
77.31
1..61
GCN
73.69
48.70
89.75
83.64
76.09
GCN (LapPI)
83.37
44.35
94,26
84.95
77.79+1.34
GCN (RWSE)
84.84_0.55
46.40+0.65
23.84
85.11
11.40
GCN (DEG)
50.01 +0.69
94. 20.10
82.51
76.96+1.21
CO-GNN(2, ))
91.57=0.32
51,28
95.09
83.3640.88
80.02
CO-GNN(ja. (4)
91.37 0.35
54.17 40.37
97.31 #0.41
84.45
16.54
SAGE
85.74 0.67
53.63 +0.39
93.51 +0.37
82.43
76.44
Graph Transformers
Exphormer
0.307
$3.51 +0.46
90.74
83.77+0.78
73.94+1.000
NAGphormer
74.34 u..7
51.26
84.19 $4.19 #0.66
78.32
68.
68.1741.03
GOAT
71.59
44.61 40.50
81,09 +1
83.11+1.04
75.7641.66
GPS
82.00
53.10
90.63
83.7110.48
71.73+1.47
GPSGCN-Perromer
83.96_0.55
48. 48.20
93.85 10.41
84.72.10.77
17.85
GPSacc+Peflmmer
(RWSE)
84.72_0.65
48.08 10.85
92.88 02.88.10.88 188.0..500
84.81
16.45
GPSecN
(DEG)
83.38_0.68
48. 40.43
93.60
80.49+0.07
74.24+1.18
GPS
(LapPE)
85.93_0.52
48. 48.86
92.62
84.62+0.54
76.71
GPS Paat-ooeeee
(RWSE)
87,04_0.58
49.92
91.08
84.3840.01
77.14
GPSGxT-Perommer
85.54 0.58
51.03 6.0.0
91.52.10.4
82.45
GT
86.51 0.73
51.17 1..68
91.85 0..76
83.23
77.95
GT-scp
87.32
52.18 10.80
92.29
82.52
78.05
Heterophily-Designadt GNNs
CPGNN
63.96
39.79
52,03
73.3641.01
65.9641.95
FAGCN
65.22 u.56
44.12
88.17 a0.7a
77.75
47.24
ESGNN
79.92_0.56
52.74-1068
90.08
82.76.00611
78.
08.8640.92
GBK-GNN
74.57 -0.4
45.98
90.85
81.01
10.87
GloGNN
59.63
36.89
51.08 1.23
73.39+1.11
65.74
GPR-GNN
64.85
44.88
86.24
72.94
55.48
H2GCN
60. 00.52
36.47 20.23
89.71 +0.31
73.3541.01
63.5941.46
JacobiConv
71.14 0.442
+0.45
89.66
68.66+4..0
13.88
Interleaved Multiscale (Ours)
IM-GCN
83.53_0.57
52.37 20.66
91.80=00.58
84.17
18.1740.89
IM-GatedGCN
90.82_n.58
54.01 20.27
97.32
85.10
79.27
IM-GAT
84.48
51.16
92.68
85.21
77.98
IM-FAGCY
86.26_0.44
52.81 40.35
95.17
84.49
78.17
IM-GAT-sep
89.93
53.97 +0.58
96.15 4
85.4444.40
77.92+
IM IM-CO-GNN(E, Σ)
92.08-0.33
23.11
95.79 96.96
85.25+1.03
80.4940.92
IM-CO-GNN(JA. p)
92.00
54.43
97.39
85.77+1.05
78.9240.87
16

---

Improving the Effective Receptive Field of Message-Passingg Neural Networks
D. Runtimes
measure the runtimes of our IM-MPNN and compare it with baseline GNN backbone under different scales settings and three different datasets. The results are reported in Table 7, and show the effectiveness IM-MPNN- it allows achieve improved performance while maintaining competitive computational demand in terms of runtimes, with similar number of parameters.
Table Training and inference runtime per epoch using an Nvidia RTX A6000 GPU.
Method
scales
Pascal VOC-
COCO-SP
Peptides-
params
time/epoch
params
time/epoch
params
sec/epoch
GCN
490K
8.00s
500K
78.95s
486K
2.00s
IM-GCN
1
489K
10.98s
487K
104.22s
488K
2.60s
IM-GCN
2
482K
14.22s
495K
132.64s
495K
3.41s
IM-GCN
3
497K
17.93s
495K
155.41s
489K
4.31s
IM-GCN
4
472K
21.86s
489K
183.94s
478K
5.16s
GINE
450K
8.03s
409K
76.18s
491K
1.90s
IM-GINE
1
497K
10.74s
484K
105.51s
499K
2.88s
IM-GINE
2
496K
14.04s
484K
130.33s
479K
3.85s
IM-GINE
3
476K
17.23s
484K
155.76s
481K
4.93s
IM-GINE
4
491K
20.83s
499K
182.76s
481K
6.02s
GatedGCN
473K
12.47s
450K
128.10s
493K
2.97s
IM-GatedGCN
1
477K
15.86s
486K
180.38s
507K
4.82s
IM-GatedGCN
2
491K
20.60s
494K
219.218
492K
6.98s
IM- GGGeeeGGNNN
3
475K
26.18s
499K
276.63s
480K
9.03s
IM- MM-GatedGCN
4
495K
31.72s
488K
332.258
453K
11.20s
Table 8: Runtimes on the Questions dataset using 8-layer network with 256 channels on Nvidia RTX A6000 GPU.
Method
milliseconds per epoch
GCN
68.67
CO-GNN
211.43
FAGCN
104.85
GatedGCN
127, 127.90
GAT
113.26
GPS(Perfommr-GGCN)
412.07
GPS (TeNsssoooomm)))GC
Out of memory 151.74
IM-GCN (Ours)
17

---

Improving the Effective Receptive Field of Message-Passingg Neural Networks
E. Additional Experiments
We've compared IM-MPNN results on PascalVOC-SP against two methods. The first U-Net, which popular hierarchical method for node classification. The other is DRew, which is graph rewiring method that aims to avoid over-squashing. Table shows the results.
We also provide additional results OGBN Arxiv. The results are reported in Table 10.
Table 10: ORGB Arxiv results.
Table 9: Comparison with other methods.
Method
ORGB Arxiv
Method
VOCcalVOC-SP Test F1 f
Accuracy f
GCN GAT
71.74:1.29
Graph U-Net (GatedGCCN)
0.1801 0.1801 +0.0055
71.95
0.3909 10.0051
IM-GCN IM-GAT
73.89 10.21
IM-GatedGCN
0.4332+t.00045 0.00
73.87
18


Reviews:
[{"review_id": "lppilXYR1j", "reviewer": "Reviewer_U4Ms", "summary": "This paper proposes a new messages passing strategy to expand the receptive field of GNNs by transmitting information between graphs at multiple scales, and theoretical analysizes the influence decay of message passing  along the path between nodes. The experiments are conducted on long-range graph benchmarks to validate the effectiveness of multiscale message interaction.\n\n## update after rebuttal:\n\nMy concerns in the first review phase have been addressed by the authors with empirical justification, so I raised my score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer U4Ms for their thoughtful and constructive feedback. We appreciate you finding our paper *well-written and easy to follow*, and that the proposed method is  *meaningful* with *impressive results*, and we are pleased to address your comments in detail below.\n\n\n1. **Regarding SeBot (Yang et al. 2024)**: Thank you for the reference. The hierarchical information processing in SeBot appears to be based on a Graph U-Net structure, focusing on how to perform coarsening between scales. In contrast, our IM-MPNN uses existing coarsening operations, and its contribution is in the unique multiscale interleaving approach to enhance the ERF of MPNNs, as reflected by the results in the Table below, where our method significantly outperforms Graph U-Net. It might be possible (and interesting to try) to use SeBot with IM-MPNN in future works. We added this discussion and a citation to SeBot in our revised paper.\n\n| Method | PascalVOC-SP |\n|---|---|\n| Graph U-Net | 0.1801$_{\\pm 0.0055}$ |\n| IM-GatedGCN | 0.4332$_{\\pm 0.0045}$ |\n\n2. **Regarding other methods on heterophilic graphs:** Thank you for the suggestion. As noted by Reviewer EHuP, our IM-MPNN offers a different approach compared with existing methods, that rely mostly on rewiring or designated architectures, while our IM-MPNN  offers a hierarchical approach to allow the propagation of information from distant nodes. Moreover, IM-MPNN can be combined with these methods, to further improve performance, as shown in our results provided in the response to Reviewer EHuP. We added the discussion and results to the revised paper. \n\n3. **Regarding messages between any pair of coarsened graphs:** We appreciate the interesting question. We have tried similar ideas of passing information between different scales of the graph, which also adds to the computational complexity of the architecture. However, we did not see an improvement over the proposed interleaving approach.\n\n4. **Regarding the coarsening of heterophilic graphs:** Thank you for the insightful question.  We would like to kindly note that an IM-MPNN layer processes the original resolution features (as well as other scales) on their own, followed by their aggregation. Thus, in our IM-MPNN, we only add information to the original resolution node features, which are aggregated from distant nodes, using the Graclus pooling algorithm. We agree with the Reviewer that the specific choice of pooling and aggregation may be improved for heterophilic graphs, and it will be interesting to explore such approaches in future works. Finally, we note that our experiments consistently indicate that our IM-MPNN improves downstream performance, also in heterophilic graphs, including when combined heterophily-designated MPNNs, as shown in our added experiments in our response to Reviewer EHuP. We added this fruitful discussion to our revised paper. Thank you.\n\n\n5. **Regarding Eq. (20):** Thank you for pointing out our typo, we have now corrected the equation according to your guidance, and it reads (apologies for the line separation. There were issues with Openreview's rendering of the equation):\n\n$$x_{q=(i,j)}^{(s,\\ell+1)} = \\tilde{x}_{q=(i,j)}^{(s,\\ell)}$$\n\n$$+ W_{l2h}^{(s,\\ell)}\\frac{1}{2}(\\tilde{x}_i^{(s-1,\\ell)}+\\tilde{x}_j^{(s-1,\\ell)})$$\n\n$$+ W_{h2l}^{(s,\\ell)}\\tilde{x}_{(q,p)}^{(s+1,\\ell)}.$$\n\n----------\nWe hope that you find our responses satisfactory, and that you will consider revising your score.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "checked.", "experimental_designs_or_analyses": "Yes. The experimental designs are sound, which follow the widely used protocals.", "relation_to_broader_scientific_literature": "The key contribution of this work is to build message passing among multi-layered graphs, namely, original graph and its coarsened graphs at different scale, which shares idea with (Yang et al. \"SeBot: Structural Entropy Guided Multi-View Contrastive\nLearning for Social Bot Detection\", in KDD'24), where the hierarchy of the graph in question is constructed with some coarsening method like structure entropy, but the messages are only allowed to transfer from higher level to low level (directionally).", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strengths:\n1. The paper is well-written and easy to follow.\n2. It is a good idea to establish short-cut message passing channels between long-range nodes via coarsened graphs. \n3. The message passing interleaved among different scaled graphs  is meaningful, leading to  impressive results.\n\nWeaknesses: Why the proposed method is superior to other methods that are also able to capture the long-range dependence on heterophilic graphs is not discussed.", "other_comments_or_suggestions": "1. Messages are constrained to pass through the coarsen graphs in the adjacent layers, why not passing messages between any pair of coarsened graphs (including the original one)? what is the benefit of the current choice?\n2. It is somehow counterintuitive to adopt  pairwise coarsening according to the topology of the heterophilic graphs, as there is a good chance for connected nodes in that setting that have different features/labels, but grouping them into one node as well as feature aggregation according to eq.(17) may lead to invalid node features. How can we explain the outperformance of IM-GNN in heterophilic graphs?", "questions_for_authors": "In Eq.(20), what are X_1 and X_2? Can it be formulated in the product of coarsening matrix and feature matrix, which I guess will be more neat.", "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": "gUgCxE5265", "reviewer": "Reviewer_EHuP", "summary": "The paper addresses the challenges faced in capturing long-range interactions in GNNs due to limited effective receptive field of the message passing mechanism and proposes a novel architecture based on a hierarchical coarsening of graph to improve communication between distant nodes.\n\n## update after rebuttal:\nFollowing the clarifications and additional results provided by the authors during the rebuttal, I believe the complementary nature of the proposed approach could be valuable to the GNN community. Therefore, I have raised my score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer EHuP for the thoughtful and constructive feedback and for finding our paper *interesting*, *well-written*, valuable to the current GNN literature, and offering a *different perspective on enabling long-range interactions*. We are pleased to address your comments in detail below.\n\nAll the results and discussions were added to our revised paper, and we think they improved our paper, thank you.\n\n1. **Regarding organizing Table 5:** Our goal was to compare with multiple relevant methods, hence Appendix Table 5 includes 33 methods. Following your suggestion, CO-GNN is now included in Table 3 (main paper), as well as our IM-COGNN -- please see details below.\n2. **Re runtimes:**  We agree with that IM-MPNN increases runtime, as discussed in Section 4.3 and Appendix B (Table 6). However, IM-MPNN retains the asymptotic complexity of its backbone MPNN, typically linear in the number of nodes and edges, and Tables 1, 2, and 6 show that IM-MPNN significantly improves performance over its backbone. We also kindly note that methods like DRew (Gutteridge et al., 2023) requires higher runtimes. For example, on PascalVOC-SP, DRew-GatedGCN takes 119.84s vs. 31.72s for IM-GatedGCN (4 levels). Following your advice, we now report runtimes on the Questions dataset using 8-layer networks with 256 channels on an Nvidia A6000. The results demonstrate that our method achieves strong performance while keeping runtime comparable to methods like CO-GNN.\n\n|Method|milliseconds per epoch|\n|---|---|\n|GCN|68.67|\n|CO-GNN|211.43|\n|FAGCN|104.85|\n|GatedGCN|127.90|\n|GAT|113.26|\n|GPS(Performer+GCN)|412.07|\n|GPS(Transformer+GCN)|Out of memory|\n|IM-GCN (Ours)|151.74|\n\n3. **Regarding comparison with CO-GNN:** We incorporated IM-MPNN into CO-GNN and found it further improves CO-GNN’s strong baseline, as shown in the table below.\n\n|Method|Roman.|Amazon.|Mine.|Tolo.|Ques.|\n|---|---|---|---|---|---|\n|CO-GNN($\\Sigma$,$\\Sigma$)|91.57+-0.32|51.28+-0.56|95.09+-1.18|83.36+-0.89|80.02+-0.86|\n|CO-GNN($\\mu$,$\\mu$)|91.37+-0.35|54.17+-0.37|97.31+-0.41|84.45+-1.17|76.54+-0.95|\n|IM-CO-GNN($\\Sigma$,$\\Sigma$) (Ours)|92.08+-0.33|53.11+-0.59|95.79+-0.96|85.25+-1.03|80.49+-0.92|\n|IM-CO-GNN($\\mu$,$\\mu$) (Ours)|92.00+-0.41|54.43+-0.41|97.39+-0.35|85.77+-1.05|78.92+-0.87|\n\n4. **Regarding OGB dataset:** During the rebuttal, we ran experiments with a couple of IM-MPNN options on OGBN ARXIV. The results are reported in the table below, and they suggest that our approach is beneficial also for larger graphs.\n\n|Method|OGBN Arxiv (Acc)|\n|---|---|\n|GCN|71.74+-0.29|\n|GAT|71.95+-0.36|\n|IM-GCN (Ours)|73.89+-0.21|\n|IM-GAT (Ours)|73.87+-0.16|\n\n5. **Regarding the Graclus algorithm:** Our focus was not on the coarsening method, as IM-MPNN can benefit from other approaches in the literature. However, we agree that an explanation is helpful and have added it to the revised paper. Thank you.\n\n6. **Regarding number of scales:** The Reviewer is correct that the number of scales is a hyperparameter. Like width and depth in neural networks, performance eventually plateaus or drops, which can be due to several factors. First, to stay within a parameter budget, we reduce network width when increasing scales, which may limit performance. Second, adding more scales may offer no benefit once the interaction range is sufficient for the data. For example, on a graph with a diameter of 16 and 3 coarsening levels, a node at the coarsest scale may already span most of the graph, making further scaling unnecessary. Thus, the optimal number of scales depends on the graph’s diameter.\n\n7. **Regarding the number of layers:** We use IM-MPNN to enhance MPNN backbones and therefore follow the hyperparameters from prior work. For example, in IM-GatedGCN on PascalVOC-SP, we use the GatedGCN settings from Toenshoff et al. (2023), including 10 layers.\n\n8. **Regarding IM-MPNN with heterophily designated GNNs:** To address your insightful question, we provide results of IM-GATsep and IM-FAGCN on heterophilic datasets below. These show that IM-MPNN can enhance various MPNN backbones and improve their performance.\n\n|Method|Roman.|Amazon.|Mine.|Tolo.|Ques.|\n|---|---|---|---|---|---|\n|GAT-sep|88.75+-0.41|52.70+-0.62|93.91+-0.35|83.78+-0.43|76.79+-0.71|\n|FAGCN|65.22+-0.56|44.12+-0.30|88.17+-0.73|77.75+-1.05|77.24+-1.26|\n|IM-GAT-sep (Ours)|89.93+-0.34|53.97+-0.58|96.15+-0.37|85.44+-0.40|77.92+-0.92|\n|IM-FAGCN (Ours)|86.26+-0.44|52.81+-0.35|95.17+-0.84|84.49+-0.97|78.17+-1.06|\n\n9. **Regarding IM-MPNNs and CO-GNNs:** CO-GNN is a strong method that explores learning MPNN actions. We see IM-MPNN as a complementary contribution, offering interleaved hierarchical processing that can be combined with CO-GNN. To demonstrate this, we now include IM-COGNN in the table above, showing that IM-MPNN can further enhance CO-GNN’s strong baseline.\n\n---------\nWe hope that you find our responses satisfactory, and that you will consider revising your score.", "claims_and_evidence": "- The main claim that the contribution of one node to another node's output decaying exponentially by the distance between them is shown and analyzed on different synthetic graph types.\n\n- While the results in Table 3 show  IM-MPNN to achieve the best performance, some more baselines reported in Table 5 seem to be more competitive, particularly CO-GNN. Although I understand all results can not be reported in the main paper due to space limitation, I believe comparison with most recent competitors such as CO-GNNs should be included in the main results table.", "methods_and_evaluation_criteria": "- The proposed technique is analyzed on different graph types and evaluated on relevant real-world benchmark datasets.\n\n-  IM-MPNN, while interesting, is more time consuming in practice although its time complexity  is a linear factor of a regular MPNN. Since the predictive performance is competitve or only a small improvement over a baseline such as CO-GNNs , it would also be nice to see how IM-MPNN compares empirically to CO-GNNs (and/or other such competing methods in addition to basic MPNNs such as GCN already shown in Table 6) in terms of runtime.", "theoretical_claims": "The theoretical claims seem correct but the mathematical details were not checked in detail.", "experimental_designs_or_analyses": "The experiments and analyses are reasonably well designed and conducted.", "relation_to_broader_scientific_literature": "The paper offers a relatively new perspective on effectively enabling long range interactions whereas most existing solutions are based on re-wiring strategies or specifically designed architectures and thus adds value to the current GNN literature.", "essential_references_not_discussed": "None that I can recall.", "other_strengths_and_weaknesses": "**Strengths**: The paper provides an interesting perspective to an imporant problem in the GNN landscape,  is well-written with illustrations aiding comprehension.\n\n**Weaknesses**: Runtime for even 4 scale levels in hierarchical coarsening is realtively quite high. An empirical comparison of runtime between IM-MPNN and competitive baselines with similar performance such  as CO-GNNs and evaluation on large-scale OGB datasets could be a valuable addition.", "other_comments_or_suggestions": "A brief basic explanation of the method used to select nodes pairs for graph coarsening could be helpful for readers not familiar with Graclus algorithm.", "questions_for_authors": "1. Would the number of scales (and the number of nodes in each scale level) be a hyperparameter to be tuned? Is there any guideline for its selection depending on some properties of the input graph? Does performance tend to level out or decrease if the number of scales are further increased? \n\n2. How many layers did the IM-MPGNNs generally constitute of? \n\n3. Can IM-MPNN use heterophily designated GNNs or others as the underlying MPNN? For example, IM-GATsep or IM-FAGCN? If so, how would they be expected to perform? Is IM-MPNN complimentary with any GNN backbone or is there a case where a certain type of GNN could be deterimental to IM-MPNN?\n\n4. Since the performance of IM-MPNNs and CO-GNNs is similar, do  IM-MPNNs hold any other advantages over CO-GNNs, such as efficiency?", "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": "1gONLTpZ29", "reviewer": "Reviewer_1PKF", "summary": "This work proposes a hierarchical coarsening method during GNN message passing in order to increase the effective receptive field while reducing over-squashing. The method is compared against datasets within the Long Range Graph Benchmark.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer 1PKF for their thoughtful and constructive feedback. We are happy to read that you found our *claims well demonstrated* and that the *paper tackles a problem important for the field*, and we are pleased to address your comments in detail below.\n\n1. **Regarding related hierarchical MPNNs (DiffPool and ANS-GT):** Thank you for pointing out these related works. DiffPool is a coarsening (pooling) method for graphs. In contrast, our proposed IM-MPNN utilizes coarsening operations as a building block, and its main contribution is in the way in which the hierarchical representations of graph features are processed. Thus, it is possible to use DiffPool within IM-MPNN as its coarsening operation instead of Graclus. We chose to work with Graclus thanks to its popularity. We have clarified this important distinction in our paper.  \nANS-GT is a variation of graph transformers that uses a preprocessed graph coarsening within its attention mechanism. It differs from IM-MPNN in two ways: First, our IM-MPNN uses coarsening as part of a message-passing network. Second, it interleaves multiple coarsening levels instead of a single one. In our revised paper, we now added this discussion and citations to DiffPool and ANS-GT. Thank you.\n\n2. **Regarding the difference from other hierarchical MPNNs:** To the best of our knowledge, this is the first MPNN-based method to use multiple graph scales during the entire processing stage of the neural network, which is different from U-Net based approaches that only consider pairs of scales at a time. We demonstrate that it outperforms the baselines on datasets that require long-range interactions, and inspired by your comment, we also include an empirical comparison to highlight the effectiveness of IM-MPNN compared with Graph U-Net, in the table below. We have included this discussion in our revised paper. \n\n| Method | PascalVOC-SP|\n|---|---|\n| Graph U-Net | 0.1801+-0.0055 |\n| IM-GatedGCN | 0.4332+-0.0045 |\n\n3. **Regarding the pairing set P:** The pairing is done using the Graclus clustering, as discussed in our response to point 1. However, it is not limited to this specific method and can be obtained with other clustering methods as well. Following your question and a request from reviewer EHuP, we added more information about Graclus to the appendix.\n\n4. **Reasoning on IM-GatedGCN vs. IM-GAT results:**\nWe agree with the reviewer that this is an interesting topic. However, we would like to point out that this is a phenomenon that can happen empirically. For example, in Table 5, we see that GPS+Performer+GCN outperforms GPS+Performer+GAT on three of the five datasets. Therefore, while this is interesting to explore, investigating it is out of the scope of this paper.\n\n5. **Regarding asynchronous aggregation during message passing:** We thank the reviewer for bringing the work to our attention. The method, aAsyn, suggests a multi-hop aggregation in an asynchronous approach. We did not find the code for this method in order to compare results with it. Hence, we compared with DRew (Gutteridge et al., 2023), which is another multi-hop approach, as discussed in response to Reviewer UcQT, to show the benefits of IM-MPNN over it.  We agree that aAsyn is relevant to our work, and we now cite and discuss it in our revised paper. \n\n| Method | PascalVOC-SP |\n|---|---|\n| DRew(GatedGCN) | 0.3909+-0.0051 |\n| IM-GatedGCN | 0.4332+-0.0045 |\n\n----\nWe hope that you find our responses satisfactory, and that you will consider revising your score.", "claims_and_evidence": "The experimental results well demonstrate the claims. Particularly with Figure 7, the IM-GCN shows strong performance on the given long-range dependence prediction task as the scale increases.", "methods_and_evaluation_criteria": "The methods and evaluation make sense for the problem.", "theoretical_claims": "The paper doesn’t put a large emphasis on theoretical findings.", "experimental_designs_or_analyses": "The experimental designs are standard for graph learning problems. Hierarchical MPNNs should be included in the experimental results, as these works are very closely related to the idea of graph coarsening.", "relation_to_broader_scientific_literature": "This work positions itself within the important discussion about the limitations of MPNNs, specifically about over-smoothing and over-squashing. The depth of graph models is limited by these factors. Therefore, works investigating ways to remedy these problems are important for the field.", "essential_references_not_discussed": "Most relevant references are discussed. One major work for hierarchical representations is DiffPool [1]. For hierarchical graph transformers, which utilize graph coarsening, another work to consider is ANS-GT [2].\n\n[1] Ying, Zhitao, et al. \"Hierarchical graph representation learning with differentiable pooling.\" Advances in neural information processing systems 31 (2018).\n\n[2] Zhang, Zaixi, et al. \"Hierarchical graph transformer with adaptive node sampling.\" Advances in Neural Information Processing Systems 35 (2022): 21171-21183.", "other_strengths_and_weaknesses": "The interleaved multiscale message passing is straightforward. Some extra discussion and comparison to hierarchical MPNNs would be important to highlight the differences to IM-MPNNs. As the paper is currently written, the novelty of this work is not entirely clear.", "other_comments_or_suggestions": "See questions. I would increase my score with strong answers to my questions.", "questions_for_authors": "(1) How is the pairing set P constructed?\n\n(2) As mentioned previously, this work seems to resemble hierarchical MPNNs. What makes this work novel and sufficiently different from existing hierarchical MPNNs?\n\n(3) What could the reason that IM-GatedGCN outperformed IM-GAT, despite the vanilla GAT outperforming the vanilla Gated-GCN? Why would interleaved multiscaling be more suited on a GatedGCN than a GAT?\n\n(4) An interesting idea from a recent work is to perform what they call asynchronous aggregation during message passing [3]. This method is able to increase the effective receptive field as well by selectively aggregating messages from a node’s k-hop neighborhood and adding delays on when to aggregate each message. What do you see as the benefits of hierarchical coarsening over an approach like this?\n\n[3] Jialong Chen, Tianchi Liao, Chuan Chen, and Zibin Zheng. 2024. Improving Message-Passing GNNs by Asynchronous Aggregation. In Proceedings of the 33rd ACM International Conference on Information and Knowledge Management (CIKM '24). Association for Computing Machinery, New York, NY, USA, 228–238. https://doi.org/10.1145/3627673.3679778", "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": "5HH6UfcSej", "reviewer": "Reviewer_UcQT", "summary": "This paper introduces an architecture called Interleaved Multiscale Message-Passing Neural Networks (IM-MPNN) to address limitations in traditional Message-Passing Neural Networks (MPNNs), particularly the problem of over-squashing and the limited Effective Receptive Field (ERF). The key issue identified is that MPNNs struggle to capture long-range dependencies in graph-structured data due to an exponentially decaying influence of distant nodes, similar to the ERF limitations in Convolutional Neural Networks (CNNs).\n\n## update after rebuttal\nI keep my score, given the introduced addtional computation load, which may offset the performance gain. Also, it is not quite clear on how to choose the right scales for graphs.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer UcQT for their thoughtful and constructive feedback, and for acknowledging our work being  *well-motivated*, *well-presented*, *distinct from existing solutions*, and *addressing a fundamental GNN limitation*. We are pleased to address your comments in detail below.\n\n1. **Regarding comparison with rewiring:** During the rebuttal phase, we have experimented with a couple of methods that address oversquashing. The first is Graph U-Net, a hierarchical architecture that uses stages of pooling and unpooling to operate on different scales of the graph, with the main difference from IM-MPNN being that the U-Net approach only considers pairs of scales at a time. The second is DRew, a multi-hop method that utilizes rewiring, and we have chosen it because its implementation is compatible with the LRGB codebase, and because of its strong baseline performance. DRew was originally trained with the LRGB official hyperparameters, and not with the better-tuned ones presented in Toenshoff et al. (2023). Hence, for a fair comparison, we've rerun the experiments with those, changing only the width of the network to stay within the 500k parameter budget. The results for Graph U-Net, DRew, and our IM-GatedGCN are reported in the table below, further highlighting its effectiveness. \n\n| Method | PascalVOC-SP |\n|---|---|\n| Graph U-Net | 0.1801+-0.0055 |\n| DRew(GatedGCN) | 0.3909+-0.0051 |\n| IM-GatedGCN | 0.4332+-0.0045 |\n\n\n2. **Regarding runtime:** Thank you for the comment.  We agree with the Reviewer that our IM-MPNN framework increases running times, as discussed in Section 4.3 reported in Appendix B (Table 6). However, Table 6 compares it to vanilla MPNNs, which are very fast and simple. It is expected that more complex architectures will require longer running times. For instance, on PascalVOC-SP, we measured a training runtime of 119.84 seconds using DRew-GatedGCN, while our IM-GatedGCN (with 4 levels) requires 31.72 seconds. That said, we agree that a leaner and faster method inspired by the interleaving multiscale principle is a promising direction for future work.\n\n3. **Regarding the extension of the ERF analysis to more graph topologies:**\nThe ERF analysis that we present in Section 3.2 relies on the connection between the combinatorial Laplacian being a discretization of the continuous Laplacian for some geometry. This connection is rather general and can hold for geometric problems characterized by graphs resembling an unstructured mesh discretizing a continuous domain. Figure 1, for example, presents such a mesh, discretizing a circular domain using triangulation. One can locate the nodes in space such that the combinatorial Laplacian (which is defined by the connectivity alone) will be equivalent to a finite element (FEM) discretization of a (minus) analytical Laplacian operator. Finite elements methods can discretize arbitrary domains in various dimensions, using quite a few types of elements and their mixes (triangular, rectangular, tetrahedral, etc.). Hence, since our analysis fits any FEM discretization (because it approximates a continuous equation in (10)), it is rather general, at least for geometric problems, and not limited only to a structured regular grid. Furthermore, the discussion in Section 4.1 regarding the scales will hold for any Finite Element discretization, as the discretization operators are scaled by the size of the elements (equivalent to $h^2$ in the paper). On the other hand, graphs are indeed more general than unstructured meshes, but we believe that our analysis gives intuition and motivation to use our method in such cases as well.  \n\n4. **Regarding lines 323-329 and addressing the three questions in the experiments:** While not explicitly answering these questions, we believe our experiments are constructed in a way that answers them. That is, Section 5.2 answers (i), and Sections 5.1 and 5.3 answer (ii) and (iii). We revised the text of the results section to reflect it more explicitly.\n\n5. **Regarding typos and editorial suggestions:** Thank you for pointing those out. We have fixed our paper according to your guidance.\n\n----\nWe hope that you find our responses satisfactory, and that you will consider revising your score.", "claims_and_evidence": "The linear graph analysis (Section 3.1) assumes a simple topology, and the diffusion model (Section 3.2) relies on Laplacian-based assumptions. These may not fully generalize to complex, real-world graph structures. Table 6 shows increased runtimes with more scales. The claim of \"maintaining computational efficiency\" is supported by complexity analysis (O(|V| + |E|)), but practical runtime impacts are underexplored, especially for large-scale graphs.", "methods_and_evaluation_criteria": "The IM-MPNN design is well-motivated, addressing over-squashing by expanding ERF through multiscale processing—a direct analogy to CNN solutions. The benchmarks (LRGB, heterophilic datasets, graph transfer) are appropriate.", "theoretical_claims": "There is no proof in this paper.", "experimental_designs_or_analyses": "The experimental designs are appropriate, including relevant datasets for evaluations. But more compasions with baselines on different benchmarks are needed.", "relation_to_broader_scientific_literature": "This paper mainly builds on the idea of increasing the ERF of CNN, and adapts it to graphs. Based on that, this work extends several key ideas in GNN research, i.e., oversquashing, Hierarchical GNNs, and Long-Range Dependencies.", "essential_references_not_discussed": "Most relevant references are cited.", "other_strengths_and_weaknesses": "Strengths:\n1. The multiscale interleaving approach is a novel synthesis of CNN-inspired ERF enhancement, distinct from existing over-squashing solutions.\n2. Improving ERF addresses a fundamental GNN limitation.\n3. The proposed multiscale interleaved MP approach is well-presented and easy to follow.\n\nWeaknesses:\n1. It lacks comparisons with other approaches addressing the oversquashing problem, e.g., re-wiring. \n2. Runtime increases with scales (Table 6), which suggest a trade-off not fully addressed, potentially limiting scalability for massive graphs.\n3. The ERF analysis could explore more graph topologies or non-diffusion-based MPNNs to strengthen generality.", "other_comments_or_suggestions": "1. Explain what different colors mean in Figure 1.\n2. Figure 2, Line 67, \"The the\" -> \"Then the\"\n3. Line 138, \"nodes features the ℓ-th hidden layer\" -> nodes features of the ℓ-th hidden layer", "questions_for_authors": "1. Line 323-329, it is said to address the three questions in the experiments, and it is better to refer the question when discuss the corresponding results.\n2. Table 1 and 2, it seems that the performance is not necessarily increasing with scales, can the authors further elaborate on this? How to choose the right scales for different graphs?\n3. Can the authors compare the multiscale interleaved message passing with other approaches of addressing oversquashing, such as rewiring?", "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:

Meta-review: This work introduces a formal definition of "effective receptive field" in GNNs, inspired by the literature on Convolutional Neural Networks. The authors present a novel architecture based on hierarchical coarsening and scale mixing to extend the receptive field of GNNs. The proposed method is evaluated empirically on challenging benchmarks such as the Long-Range Graph Benchmark, showing that it outperforms existing approaches in modeling long-range dependencies and alleviating the over-squashing problem.

The paper was reviewed by four reviewers. All four initially raised concerns, mainly about novelty, certain design choices, applicability to heterophilic graphs, and computational overhead. These concerns were addressed satisfactorily in detailed rebuttals. Specifically, the authors clarified differences from prior work and provided additional experiments, including runtime benchmarks and performance results on Open Graph Benchmark datasets and heterophilic graph settings, showing comparable or better performance without sacrificing efficiency.

I share their view that this is a well-written and clearly structured paper presenting an interesting method supported by solid evidence. I believe this is a significant contribution to the area of graph learning and therefore recommend acceptance.

For the revised version, I suggest that the authors include the additional results and discussion provided during the rebuttal phase, especially the details of the strategy for selecting the number of scales.
Decision: Accept (poster)