Adaptive Message Passing: A General Framework to Mitigate Oversmoothing, Oversquashing, and Underreaching
Authors: Federico Errica
Henrik Christiansen
Viktor Zaverkin
Takashi Maruyama
Mathias Niepert
Francesco Alesiani
Venue: ICML 2025 poster (2025)
Keywords: Graph Machine Learning
Variational Inference
Oversmoothing
Oversquashing
Underreaching
Depth Learning
Primary area: deep_learning->graph_neural_networks
TL;DR: We propose a message-passing framework for graph learning to adapt the number layers during training and filter outgoing messages, in order to control oversmoothing, oversquashing, and underreaching.

Abstract: Long-range interactions are essential for the correct description of complex systems in many scientific fields. The price to pay for including them in the calculations, however, is a dramatic increase in the overall computational costs. Recently, deep graph networks have been employed as efficient, data-driven models for predicting properties of complex systems represented as graphs. These models rely on a message passing strategy that should, in principle, capture long-range information without explicitly modeling the corresponding interactions. In practice, most deep graph networks cannot really model long-range dependencies due to the intrinsic limitations of (synchronous) message passing, namely oversmoothing, oversquashing, and underreaching. This work proposes a general framework that \textit{learns to mitigate} these limitations: within a variational inference framework, we endow message passing architectures with the ability to adapt their depth and filter messages along the way. With theoretical and empirical arguments, we show that this strategy better captures long-range interactions, by competing with the state of the art on five node and graph prediction datasets.

Adaptive Message Passing: A General Framework to Mitigate Oversmoothing, Oversquashing, and Underreaching
Federico Errica
Henrik Christiansen
Viktor Zaverkin |
Takashi Maruyama?
Mathias Niepert 12
Francesco Alesiani
Abstract
known that electrostatic and gravitational interactions decay slowly with distance (Campa et al., 2014); in computational chemistry and material sciences, the accurate modeling of non-local effects, such as non-bonded interactions in molec- ular systems, is necessary to estimate properties like the free energy (Shirts al., 2007; Piana al., 2012); in biology, disrupting long-range interactions in mRNA can inhibit slic- ing (Rüegsegger et al., 2001); in immunology, the distant interactions between a major histocompatibility complex and regions of the T-cell receptor molecule correlate with their binding process (Ferber et al., 2012).
Long-range interactions are essential for the cor- rect description of complex systems in many sci- entific fields. The price pay for including them in the calculations, however, is dramatic increase in the overall computational costs. Recently, deep graph networks have been employed as efficient, data-driven models for predicting properties of complex systems represented as graphs. These models rely on message passing strategy that should, in principle, capture long-range informa- tion without explicitly modeling the correspond- ing interactions. In practice, most deep graph networks cannot really model long-range depen- dencies due to the intrinsic limitations of (syn- chronous) message passing, namely oversmooth- ing, oversquashing, and underreaching. This work proposes a general framework that learns mit- igate these limitations: within variational in- ference framework, we endow message passing architectures with the ability to adapt their depth and filter messages along the way. With theoret- ical and empirical arguments, we show that this strategy better captures long-range interactions, by competing with the state of the art on five node and graph prediction datasets.
Complex systems can be represented as graphs of interact- ing entities. Modeling long-range interactions often implies that the graph has dense connectivity, meaning the number of interactions is quadratic in the number of entities. Ma- chine learning researchers tried to address these problems by relying on accurate surrogates for computationally demand- ing simulations (Sanchez- Gonzalez et al., 2020). Some of these methods rely on Deep Graph Networks (DGNs) (Bacciu et al., 2020b), deep learning models implement message passing paradigm of computation. In message pass- ing, nodes repeatedly exchange messages with each other to propagate information across the graph and compute their embeddings. More rounds of message passing increase the "receptive field" of each node.
Despite its long-standing history (Sperduti & Starita, 1997; Micheli, 2009; Scarselli et al., 2009; Bacciu et al., 2020b), research in graph representation learning has gained more traction in recent years, and there are still many open ques- tions. For instance, it is well-known that most message passing architectures are ineffective at capturing long-range dependencies, thus reducing their impact in the scientific fields mentioned before. Researchers relate this problem to at least three others, namely oversmoothing (Li et al., 2018), oversquashing (Alon & Yahav, 2021; Rusch et al., 2023), and underreuching (Alon & Yahav, 2021). Briefly, oversmoothing means that the node embeddings of a DGN tend to converge to the same value as the depth increases. In contrast, oversquashing relates to the bottleneck of com- pressing a (possibly) exponential amount of information from neighboring nodes into single node embedding. Fi-
1. Introduction
Complex systems, characterized by interacting entities and emergent behavior, are a cornerstone of research in many scientific disciplines. Mathematical models of such systems should consider the effects of both short and long-range interactions between entities, and the latter are often crucial describe the system's 's behavior with the highest degree of precision. For instance, in computational physics, is well-
'NEC Laboratories Europe University of Stuttgart. Correspon- dence to: Federico Errica silddrrico.rrriaee wwt.oio.crrciceeeccac...........
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Adaptive Message passing
nally, underreaching refers DGNs' inability to propagate node's information to more than K hops away.
tial equation-based message passing approaches, instead, provably preserve information regardless of the depth in the network (Gravina et al., 2023; Heilig et al., 2025). On the other hand, most graph rewiring methods alter the graph connectivity to increase the node sensitivity (Topping et al., 2022), which has been theoretically linked to a form of "topological oversquashing". Some of them preserve lo- cality and sparsity of the rewiring process (Barbero et al., 2024) or perform dynamic rewiring (Gutteridge al., 2023). Probabilistic approaches to rewiring are based on sampled nub-graphs (Qian et al., 2024a). Recently, a critical perspec- tive on the effectiveness of rewiring approaches has also been given (Tortorella & Micheli, 2022).
This work provides a general framework for improving the ability of any message passing architecture to capture long- range dependencies; we extend the general message passing formulation to propagate relevant information across the graph. At the heart of our proposal the idea to let DGNs learn how many layers of message passing to use and when to send specific messages. As matter of fact, one typically observes oversmoothing and oversquashing when too many messages are propagated, hence learning which messages to discard is important. At the same time, solving under- reaching requires a sufficient number of message passing rounds to be performed, and it crucial to learn this infor- mation from that task rather than guessing it via expensive grid searches. In light of these characteristics, we call our approach Adaptive Message Passing (AMP).
One practical mitigation to the over- smoothing problem is dropping edges, reducing the overall flow of messages and avoiding the convergence of all em- beddings to the same value (Rong et al., 2020). Another possibility to employ skip/residual connections (Kipf & Welling, 2017: Li et al., 2019). The concatenation of node representations across layers is yet another way to contain oversmoothing, which has been adopted in neural and proba- bilistic models to improve the downstream performances on several node and graph-related tasks (Bacciu et al., 2018; Xu et al., 2018). Instead, an orthogonal research direction con- siders implicit neural networks for graphs that correspond to infinite-depth models and seem to be able to capture long-range dependencies (Poli et al., 2021; Liu et al., 2021). These models simulate synchronous message passing with potentially infinite number of message- persage-propagation steps, and some of them appear to be empirically robust to the oversmoothing problem.
Oversmoothing.
Our contributions are multi-faceted. We extend a recent vari- ational framework for unbounded depth networks (Nazaret & Blei, 2022) to the processing of graphs, and we introduce new families of distributions with specific properties to over- come previous limitations. We also propose a soft message filtering scheme to prune irrelevant information for the task at hand and favor the propagation of messages to distant regions of the input graph. Theoretically, we show how to propagate a message unchanged between any two connected nodes in the graph and that filtering decreases the upper bound on sensitivity (Topping et al., 2022); thus, underreach- ing and oversquashing can be mitigated. Empirically, AMP significantly and consistently improves the performances of message passing architectures on five well-known node and graph prediction datasets where long-range information is important. Qualitative analyses provide further evidence that AMP mitigates oversmoothing and oversquashing as well as learning the number of message-passing layers. Fi- nally, we conduct an in-depth study of our approach via ablations and visualizations of the models' predictions.
Adaptive Architectures. This family of methods tries to learn the models' architecture during training. Our work is inspired by the unbounded depth networks (UDNs) of Nazaret & Blei (2022), who proposed a variational frame- work for learning the depth in multi-layer perceptrons and convolutional neural networks. In the graph domain, the first approach to learning the depth of a DGN was proposed by Micheli (2009), who applied the cascade correlation al- gorithm (Fahlman & Lebiere, 1989). Other works attempted to learn the "widdt"" of each message passing layer by ex- ploiting Bayesian non-parametric models (Castellana et al., 2022), which allows to save time and memory when build- ing deeper probabilistic DGNs. Finally, it is important to notice that these works, including this manuscript, are all orthogonal to the popular field of neural architecture search (Zhou et al., 2022): The former attempts at dynamically modifying the architecture during learning, whereas most neural architecture search approaches find smarter ways to carry out a grid search or assume a maximum number of layers. An advantage of adaptive approaches is that they can greatly reduce time and computational costs to perform
2. Related Work
Due to space reasons, we provide an extended literature review in Appendix A.
Oversquashing. There are many methods that attempt to address the oversquashing problem with the goal of better capturing long-range dependencies (Alon & Yahav, 2021). Some works learn how node should completely stop propa- gating a message in a fixed-depth architecture (Spinelli et al., 2020) or if it should only listen, isolate, or receive/broadcast its own message (Finkelshtein et al., 2024). Similarly, one can learn to sample edges at each message passing layer according to some learned parametrization (Hasanzadeh et al., 2020) or have a completely asynchronous message passing (Faber& & Wattenhofer, 2023). Ordinary differen-
2

---

Adaptive Message passing
hyper--arameete search.
Contrary to all these approaches, AMP uses variational framework to jointly learn both the depth of the DGN and filter messages passed between nodes in each of these layers.
{= f=....c
T:
3. Adaptive Message Passing
i= 1=....
This section introduces the probabilisticc framework of AMP, which train with simple backpropagation to optimize variational lower bound. This bound is composed of a predictive term and two (optional) regularizers over the parameters and the DGN's depth.
Figure I. The graphical model of AMP, where white and blue cir- cles denote, respectively, latent and ohservable random variables. O₂ is the over the parameters of layer F, defines distribu- tion over the message filters, L implements a distribution over the layers of the architecture, while G. and Tr are distributions over the (observable) input graph and the target label, respectively.
Definitions. We consider directed attributed graphs g AV) each consisting of a set of nodes V = (l....,ngg] that are connected together via set of oriented edges & = {(u, lu, u E V). When a graph is undirected, each edge is converted into two oriented ones, that is, (u, v) and (u, u). The set X' = fx, E I E V} defines the d-dimensional attribute vector of each node in the graph, and similarly for the d'-dimensional edge attributes belong- ing to the set A - {an. E Rd (u, v) E 8.. Finally, we define the neighborhood of a node v as the set of incoming edges N₁ [u| (u, v) E E). As outlined in previous works (Hammer et al., 2005; Bongini al., 2018), each attributed realization of some random variable
where Pl. P2 denote learnable functions and & is global pooling function that aggregates all node representations computed at a given layer f. The Iearnable functions &f, w , are typically implemented as 1-hidden layer MLPs parametrized by O₂.
Variational Inference Given dataset DD of [D] i.d. graphs we seek to maximize the log- likeeliod
Inp(Y = II p(Y 19:) = Σ In pY 19.).
(3)
graph can be seen (rv:) G with support in the graph domain. Similarly to clas- sical machine learning, we do not have access to the data distribution p(G), rather we are interested in modeling the conditional distribution p(T Yg 9 = g). where Yg stands for the target value(s) to be predicted.
One usually assumes the existence of set of latent variables Z such that p f PY,, ZlG)dZ. By designing a proper graphical model, which encodes conditional indepen- dence assumptions, we define how to compute p(Y, Z))); however, the integral to maximize often remains intractable. Therefore, one approach is to turn variational inference (Jordan et al., 1999; Blei et al., 2017), which maximizes the Expected Lower Bound (ELBO) instead. In particular, by arbitrarily defining distribution (Z(G), one has
Multi-output Family of Architectures. AMP produces deep graph networks of potentially infinite depth, where each layer é comprises a message passing operation MP and a readout mapping R (Bacciu et al., 2020b) from node embeddings to the desired output.
Inp(Y 2 B In PY, g(Z]G)
(4)
Without loss of generality, a message passing layer MP2 can compute node embeddings h,, Ve V as follows:
Below, we show how we define the joint distribution p(Y, ZIG) as well as the variational distribution q( ((Z
h = 66 (h--, (( ( E N.H)),
(1)
in the specific context of AMP.
where o and g/ are learnable functions and V is a permu- tation invariant function that aggregates the embeddings of
AMP Formulation. Figure represents the graphical model associated with AMP, where white and blue circles represent latent and observed r.v.s, respectively. We extend the formulation of Nazaret Blei (2022) the domain of graphs by modeling the message filtering strategy: The vari- able θ₂ follows distribution over the parameters of layer el of an infinite-depth network, and L follows a distribution over layers L E N and is used to truncate the network to a finite depth L. For the i-th graph g., F, follows a distribu- tion over soft message filters F, E [0, 1] Exx, In partic- ular, given a node v and a layer E, the d-dimensional vector
e's neighbors computed at the previous layer. When e = 1, h is obtained by applying a learnable transformation of the node v's features h. = Te, and no neighbor aggregation is performed. Instead, the readout mapping RS depends on the task: If one needs node-wist predictions, then the readout implements learnable map " of (h()) from h,, to node output of: On the other hand, in the case of whole-graph predictions, a global aggregation has to be performed first:
"ن p (+ (loi(h))le v))).
3

---

Adaptive Message passing
(1; {) specifies how much of hng has to be propagated through the outgoing edges in the next message passing layer. The generative model is
(8)
mode:
mode
mode
7
mode
modo
mode
Do0e
0~ (~p(0)=
I ((t))
(5)
7
I. ~ p(f)
(6)
(c)
(d)
0) 19. L.O 1,00~ p(T; (g F. 0))
Filgt. L,
(7)
(8)
with St,, being the infinite DGN truncated at depth L whose output parametrizes the target distribution. This means that the joint distribution decomposes as
Standard MP (161.2)
Adapise
Adapeie (fet)
FG, LG) =
Figure 2. Given an input graph (a) and a discrete message filtering scheme (b), we observe how a T==2-layer standard message passing (c) differs from AMP (d) terms the number messages sent. Please refer the text for more details.
[D]
- (((0)(() II
p(y 0,, (.
Note that the independence of the priors is key for an effi- cient approximation of the posterior distribution (Nazaret & Blei, 2022).
([L)) as the sum Eeesuppor((g) (())((() for any function f. In Appendix B, we extend the original treat- ment of Poisson distributions to Gaussians and mixtures of distributions. Second, we define q()) (:)) such that we cannot make any statement about the layers greater than L. (Kurihara et al., 2007):
In Figure 2, we visually represent the effect that message filtering has on the propagation of messages across DGN layers. A graph of seven nodes (a) is provided and the mes- sage filtering scheme (b) has been discretized in the interest of simplicity. For instance, node 1 will send its message only at message passing layer 1, nodes & 3 will never send a message, and node 4 will send a message only at layer 2. Compared to the standard message passing (c), where all nodes send their messages at each layer, AMP implements learnable filtering (d), where subset of all possible messages is propagated at each layer in way that depends on the task to be solved. In Section D, we discuss the implications of this adaptive message filtering scheme in mitigating the well-known issues of oversquashing, un- derreaching. and oversmoothing. Notably, message filtering does not introduce significant computational burden since it has linear complexity in the number of nodes.
q(0 L; = ((O...P II
p(O,)
(10)
(=L+1
and p(Or) can be, for instance, a Gaussian prior. We also fix q ((1.L:: I2 I NoO0; Me, I).
Finally, we define ((Filg L, 0) Dirac delta function 6F. whose parameters F; E [0, 1] are computed by a function fg.). Choosing the delta function makes the computation of its expectation straightforward, but other choices can, principle, be made. We propose two ver- sions of the function f(g)), whose choice is left as a hyper- parameter: the first computes (u, E) = fe( and the second computes Fi(U, E) fe fe where fe is a Multi- Layer Perceptron (MLP) with sigmoidal activations. In other words, a node's outgoing messages will be filtered according to either the input features of that node or its em- bedding at layer l. Given F, ~ q(Felge L, 0), we extend Equation to apply such filtering:
Choice of the Variational Distributions. We now need to define the learnable variational distribution q(0, L, F., 19,, ). We assume it factorizes as ((O)T:))q(L, (Flg,,, O), where v, A are learnable parameters. We also assume that the variational posterior does not depend on Y,: (so we can drop the term) to allow for predictions on unseen graphs. Below, we describe how to compute each factor that the computation of the ELBO is tractable.
h = @ ((FFi(u,E-1) 1) o' (h aav))uu E NoH)). (11)
with @ being the element-wiss product. Such message filtering is similar in spirit to many works (Franceschi et al., 2019; Spinelli et al., 2020; Finkelshtein et al., 2024), but our approach does not require gradient approximations caused by discrete operations and fully differentiable.
The distribution ((; has to belong to an unbounded with bounded and connected members' family (see Definition B. in Section B). In short, since the support of each distribution q in the family is bounded, we can compute its expectation

---

Adaptive Message passing
Computation of the ELBO. Our choice of the variational distributions allows compute the ELBO efficiently and maximize it using backpropagation (Rumelhart et al., 1986). In particular, we write (the full derivation is in Appendix C)
Note that kp S 1; if we consider for simplicity a constant filtering function, namely er 0 and we filter enough, meaning kp < 1, then filtering will decrease the sensitiv- ity's ityss upper bound. At the same time, this helps to reduce the amount of messages that get squashed into a fixed size vec- tor Alon & Yahav (2021), contradicting the widely accepted notion that "improving sensitivity mitigates oversquashing". Please consult Appendix D for a more detailed discussion this matter.
E
In p(e) x(ex)) + In p(v)
(Y|(
>
Σ u(e: A)
[
((((e:))
[D]
In q( Fi ggi, k, + In le, F, 9i) |
F(F.)
(12)
Practical Considerations. The depth of AMP varies dy- namically; in particular, the support of the distribution q(;; A) is obtained by truncating it the quantile func- tion evaluated at 0.99 (in our experiments). Whenever the quantile threshold shifts, we either grow or shrink the DGN by instantiating a new message- message-passing layer and increasing the output dimension of the function fg:: that produces F, When shrinking the DGN, we can retain the excess layers to account for future expansions or delete them; here we opt for the retention strategy. Importantly, the depth is not hyper-paramede
where i. = support(g(I))), PT..) is prior over layers, such as Poisson distribution, and P(F,) is a prior over all possible message filtering schemes (uninformative in this work, so the term cancels). The second equivalence relies on the specific properties of the variational distributions and on the approximation of expectation (ej0),,)) (0(..))) for function f, at the first order' with f( 1.)) (01...) (P1.L) as in Nazaret & Blei (2022).
Akin to Nazaret& & Blei (2022), AMP makes predictions about a new graph 9j as:
to be tuned anymore. While AMP re- quires choosing a family of truncated distributions (L)) and a proper initialization, it is generally believed that this has a smaller effect on the final result (Goel & Degroot, 1981; Bernardo & Smith, 2009). Also, setting uninformative pri- ors works well in our experiments but they are convenient way to penalize the computational costs of deeper networks.
p(Y,, (g;) R EgG.LL [D(Y,;; An 0)
(13)
Σ ale: (ee:))(( Pelos, U)).
(14)
In other words. using the fact that qf;; A) has bounded support up to i, we obtain the prediction as the weighted sum of the L output layers of the DGN, and the variational distribution q(:: >) over layers provides said weights.
We conclude with a theorem on AMP's ability to propagate a message unchanged from two connected nodes in a graph, which would not be possible on classical (synchronous) message-passing neural networks. However, achieving such behavior in practice might be difficult.
We now show that there is direct relation between the ability to filter out messages of Equation 11 and the upper bound on the Jacobian sensitivity discussed in Di Giovanni et al. (2023).
Theorem 3.2 (Short Version). For each graph g, a source node v and destination node u, there exists a parametriza- tion of AMP and depth K such that h = hhg = Rv-
Theorem 3.1. For AMP with m layers and u, V E V,
(m) (m))
Proof. The proof is provided in Appendix D, and Figure 8 sketches the process formalized in the theorem.
< d ((Cup (CraT + Cmp (crka + kF) A))m) ) yu
2h
(0)
1.
Here, MPNN is in the the following form
3.1. Computational Considerations
The cost of filtering messages is O(V)). Therefore, the message passing operation is not altered significantly, since it has a cost of O +)+|&)), However, the additional burden introduced by AMP, compared to classical message-passing architectures. the layer-wise readout that we implemented as an MLP. Classical MPNNs employ a single readout with cost O(V)) or (1) depending the task nature, whereas we use one per layer, so we have O(VIZ) and T())) respectively. In terms of training costs, we employ standard backpropagation with at most two leihht additional regularizers, which is not so different from classical ap- proaches.
h = up (is(hh + mp( Σ A o k(-1)
where up, 1S, and mp are sipschitzz as in Di Gio- vanni et al. (2023) with constants Cup- Cra, Cmp, Cp is the OF upper bound of the entry-wise L matrix norm of de for the filtering function F, kú, is the maximal absolute value among entries of h and similarly kF for the output of F.
Proof. The proof is provided in Appendix D.
FFirtt-rderr second-moment method (FOSM) of probability.
5

---

Adaptive Message passing
4. Experimental Details
very competitive performances when properly tuned. In addition, we follow previous works (Rampásek et al., 2022; Tönshoff et al., 2023a) and add random-walk structural encodings for peptides-fune and Laplacian positional encod- ings for peptides-struct. For completeness, we include re- sults from Dwivedi et al. (2022), its re-evaluation (Tönshoff' et al., 2023a), and other results such as CRaWL (Tönshoff et al., 2023b), DRew (Gutteridge et al., 2023). Exphormer (Shirzad et al., 2023), GRIT (Ma et al., 2023), Graph ViT and G-MLPMixer (He et al., 2023), LASER (Barbero et al., 2024), CO-GNN (Finkelshtein et al., 2024), NBA (Park et al., 2024), PH-DGN (Heilig et al., 2025), GRED (Ding et al., 2024), PR-MPNN (Qian et al., 2024a) and IPR-MPNN (Qian et al., 2024b).
We evaluate AMP on two sets of tasks, both requiring the ability to capture long-range interactions. Additional node classifcation results can be found in Appendix F.
Synthetic Datasets We consider the tasks of predicting the diameter, the single-source shortest paths (SSSP), and the node eccentricity on synthetic graphs (Corso et al., 2020). In particular, we closely follow the setup of Gravina et al. (2023) with graph sizes ranging from 25 to 35 nodes, topolo- gies sampled from different graph generators, and each node has one random (sampled from a Normal distribution) fea- ture attached, For SSSP, a binary feature is added to each node to indicate whether is the source node in the graph or not. Each dataset amounts to 7040 graphs split into 5120 for training, 640 for validation, and 1280 for testing. The metric to be optimized is the logio of the mean squared error (MSE). We apply early stopping on the validation MSE. We have observed that the performance reported in Gravina et al. (2023) can be improved by a significant margin we average results over 20 rather than four final (that is, after model selection) training runs and increase the patience of the early stopper from 100 to 300, giving models more time to converge to good solution. Therefore, to ensure a more robust set of results, we re-evaluated all baselines considering these changes, and in many cases, we improved the scores. We combine AMP with three message pass- ing architectures, namely the Graph Convolutional Network (GCN) (Kipf & Welling, 2017), the Graph Isomorphism Network (GIN) (Xu et al., 2019). and the Symmeeyittiic DGN (ADGN) (Gravina et al., 2023), and in addition we compare against GAT (Velickovic et al., 2018), GraphSAGE (Hamilton et al., 2017), GCNII (Chen et al., 2020a), DGC (Wang et al., 2021), and GRAND (Chamberlain et al., 2021). Hyper-parameter details can be found in Appendix E.
We evaluate AMP on GCN, GINE (Hu et al., 2020), and GatedGCN (Bresson & Laurent, 2017); our grid search follows the best hyper-parameter reported by Tönshoff et al. (2023a) (except the depth). As above, details on AMP's hyper-parameters can be found in Appendix E. Because the optimal depth ultimately depends on the task and the specific configuration of the model, we cannot impose arbitrary restrictions on the number of total parameters as done in Dwivedi et al. (2022); instead, are interested in letting the model freely adapt and choose the best parametrization that maximizes the performance.
5. Results
5.1. Quantitative Results
Table reports the test scores for the Diameter, SSSP, and Eccentricity datasets for all baselines and AMP versions. On all datasets, AMP always grants a reduction of the test error, with an average improvement of 63 % Diameter, 72 % on SSSP, and 32 % on Eccentricity. These results show that learning the proper depth of a network and a pol- icy for filtering messages exchanged between nodes is more effective than relying on a manually crafted grid search and fully synchronous message passing behavior. Eccentricity is the most difficult task to solve, whereas one could claim that SSSP is almost solved for the graphs considered. We achieved the greatest reduction in error with respect to the GIN model, probably because the authors in Gravina et al. (2023) found that a 1-layer GIN was the best configuration across all tasks after tuning the depth. This stresses the positive impact of letting the model learn how and when to propagate messages. On the chemical datasets (Table 2), observe similar trend. Regardless of the base message passing architecture, AMP consistently improves its perfor- mance on classification and regression tasks. On peptides- func, we achieve an improvement of 2 to 3.4 % compared to the base models and a reduction of MAE on peptides-struct that positions all AMP versions at state-of-the-ar levels (considering overlap of standard deviations). Our analyses
Chemical Datasets We also test AMP on real-world chemical graph prediction benchmarks, taken from the Long Range Graph Benchmark, called peptides-fune and peptides- struct (Dwivedi al., 2022). The first is an inbalanced multi-label graph classification dataset with ten total peptide functions, and we measure performances using the average precision (AP). The second is a multi- graph regres- sion task where we want to predict the peptides' properties based on their 3D information, and one evaluates the mean absolute error (MAE). Both datasets contain 15535 peptides with approximately 150 nodes each, and the data is split into 70 % for training, 15 % for validation, and 15 % for testing. We apply early stopping on the validation MAE. We rely on the fair re-evaluation of Tönshoff et al. (2023a) that shows how simple baselines like a GCN can achieve
"htps://gituh..cmm// wtt../cc//eeeeccccc///// wetprcccecccacc//apiieeeeeeeee Saatiiii-Messsgggee desssag--aassing We received support from the authors of paper.
6

---

Adaptive Message passing
Diameter
Rel Imp
SSSP
Rel Imp
Eccentricity
Rel Imp
GCN
0.6146 +: 0.0375
0.9132 0.0051
0.7398 0.0705
GAT
1.4367 + 0.3558
0.6070 + 0.0376
1,0714 + 0.0616
GRAPESAGE
0.6146 1 0.0744
-1,0139 1: 0.0120
1.0859 0.0001
GIN
0.2408 + 0.0154
-0.2648 0.4437
0.9229 0.0002
GCNII
0.5037 + 0.0309
-0.9172 + 0.1396
0.7112 + 0.0255
DGC
0.5601 0,0220
-0,0254 0.0077
0.8051
GRAND
0.9477 1 0.2160
0.1909 1 0.3103
0.7450 1 0.1369
ADGN
-0.4530 + 0.0883
-3.5448 0.2749
0.0547.0.00722
AMP
-0.1072| 0.0791
-81%
0.5440
0.0108
-57%
0.6054 +: 0.0919
-26%
AMPaIN
0.4874 0.1111
81%
-3.0628
0.3159
.99%
0.4093'
1: 0.0546
AMPADGS
0.58911 0.0720
-27%
-3.9599
0.0769
-61%
0.05151
+ 0.1811
-1%
Avg Rel lmsp
-635%
-72%
-2%
Table 1. Mean (MSI) and standard deviation averaged over 20 final runs Diameter, SSSP, and Fecentricity. A indicates that AMP yields an improvement in the mean score compared to the base model.
Method
peptides-fune Test AP
peptides-struct 'Tss MAE
5.2. AMP mitigates oversmoothing and oversquashing
GCN
0.5930 + 0. 0023
0.3/19 0. 0.0013
16
RE-EVAL LKGB
GINE
0.5498 + 0.0079
0.3547 0.0045
In Layer-wise Dirichler Energy
TRANSFORMER
GATEDGCN
0.6069 1 0.0035
0.6326 + 0.0126
0.3357
0.2529 0.0016
0.0006
In Layer-wise Sensitivity
14.
SAN
0.6439 1 0.0075
0.2545 1 0.0012
0.6535 + 0.0041
0.2500 0.0005
12
GCN
0.6860 1: 0.0050
0.2460
0.0007
GINE
0.6621 + 0.0067
0.2473 0.0017
10
GATEDGCN
0.6765 + 0. 0047
0.2477 0.0009
GPS
0.6531 0.0091
0,2509 0.0014
CRAWL
0.7074 + 000002
0.2506
0.0022
DREWoON
0.7150 = O. 0.0011
0.2536 0.0015
DREWGSNSGON
0.6977 1: 0. 0.0026
0.2539 0.0007
EXPHORMER
0.6527 0.0043
0,2181 0.0007
GRIT
0.6988 + U. 00.8
0,2460 + 0.0012
OTHERS
GRAPH VIT
0.6942 1 0.0075
0.2449
10
20
30
0
10
20
30
G-MLPMIXER
0.6021 + 0.0054
0.2475 0.00
Layers
Layers
LASER
0. 0.61:00 = 8.0000
0.3043 0.0019
CO-GNN
0,6990 + U. 0.9933
Eccentricity (GCN)
SSSP (AMPGCN
NBAGCN
0.7207 1 0.0028
0.2472
0.0008
Facentrictt (AMPGCN)
peprides- (GCN)
NBAGATDGEN
0,6982 0.0014
0,2466
Diamoler (GCN)
pepiide--ums (AMP (AMP GCN)
PII DIN
0.7012 1 0.0045
0.2465 1 0.0020
Diameter (AMP GCN)
pepides struct (GCN)
GRED
0.7041 1 0.0049
0.2584 0.0015
SSSP (GCN)
pepiides-trect (AMP
PR-MPNN
0.6825 = 0.0086
0,2477 0.0005
IPR-MPNN
0.7210 + 0. 0039
0,2122 0.0007
AMPacs
0.7161 + 0.0047
0.2446 + 0.0026
AMP
0.7065 1 0.0105
0.2468*
1 0.0026
Figure 3. We show the Dirichlet energy (left) and the sensitivity (right) across layers for the GCN model and its AMP version.
AMPaaroOOC
0.69113 + 0.0046
0.2480 = 0.0012
Table 2. Mean test scores and standard deviation averaged over 4 final runs on the chemical datasets. The indicates that AMP yields an improvement compared to the base architecture.
We now comment on AMP's ability to mitigate oversmooth- ing and oversquashing. and we refer to Figure 3 for a quali- tative analysis of the former (left) and of the latter (right). First, we computed the logarithm of the Dirichlet energy over embeddings of a trained GCN for different layers and datasets. This analysis reveals that the Dirichlet energy for AMP's variants is typically higher than the corresponding baselines and it can exhibit a stable, decreasing, or increas- ing behavior as the depth grows, in contrast to existing theoretical research on the GCN model where the Dirichlet energy constantly decreases and embeddings converge to the same value (Li et al., 2018; Rusch et al., 2023); note that we apply skip connections to the base GCN, so the energy does not immediately decreases. Therefore, it appears that our approach is indeed capable of controlling oversmooth- ing: we attribute this to the combination of message filtering and a layer-wise loss, which favors the propagation of gra-
also found that the number of hidden units is an important to perform well on these tasks, and larger value seems to correlate well with good performances. Com- bined with the above results, we argue that the parameter budget imposed by previous works (Dwivedi et al., 2022) might limit the future progress on these tasks, as deeper networks are probably needed (we provide analysis of the depth found by AMP below). The average diameter of these peptides is 57, meaning that using ten layers as done in other works might not be enough to capture long-range dependencies (Tönshoff et al., 2023a). We provide a visual analysis of predictions Appendix G.
7

---

Adaptive Message passing
Eccentr: (E). Diameter (D), SSSP (S)
peptides fune (F) struct (S)
0.15
Probubility
Probability
0.10
0.2
0.05
0.D
0.00
15
20
25
30
35
10
20
30
40
Layers
Layers
E(AMP
D (AMPGCN)
(AMPOCN)
F(AMPOCN)
(AMP
C(A
D (AMPGIN)
CAMP)IN
F(AMPGINE)
GAMP
A(AMPADGX)
HIAMPADGN
(AMP)DGG)
FUAMPGATEDGEN
GATEDGEN)
Figure 4. We show the distribution learned by the best configurations of each base model the synthetic and chemical datasets.
dient to intermediate layers. We also report the layer-wise logarithm of node embeddings' sensitivity* the gradient of the embeddings of the last layer L with respect to the Sensi- tivity provides insights into how pruning messages affects oversquashing: fact, filtering messages might reduce said sensitivity with respect to the input. We report quite het- erogeneous picture in Figure 3 (right): the sensitivity of AMP can peak at the first or last layers, increase abruptly, or remain relatively stable. In all these cases, we have seen how AMPGON substantially improves performances on tasks where it seems important to address oversquash- ing. This evidence also warns us against using sensitivity as the sole metric measure oversquashing performance bottleneck.
mostly Poisson ones, and AMP learns deeper networks than the corresponding baselines to reach better scores. These distributions peak at around ten layers for peptides-struct, which is more or less in line with what was reported in previous works (Tönshoff et al., 2023a). In any case, AMP enables training of very deep architectures thanks to its layer-wise output. However, this has a non-negligible cost in terms of number of readout parameters.
a
ones of intermediate layers 1: E(mn)ey ahe
5.4. On the Effects of Message Filtering
Figure visualizes the amount of information pruned at each layer by AMP on all datasets, together with an ablation study about the benefits of message filtering. The amount of information pruned is computed by summing the message filters' activations and normalizing the result by the total number of messages exchanged at each layer. We can see how AMPGCN gradually increases the amount of information to be used for Eccentricity, whereas in peptides- func, this quantity is almost always below 50%. One can appreciate how, depending on the task, the behavior of the message filtering changes significantly.
5.3. Analysis of the AMP's Learned Depth
To understand how AMP mitigates underreaching, we in- spect the learned distributions for synthetic datasets in Fig- ure 4 (left). AMP uses more layers than the baselines (de- tails in Appendix H) to achieve the best score on Eccentric- ity. Instead, it is found that about 20 layers are necessary to solve the task for the Diameter dataset, with all runs attain- ing a mean value between 17 and 22 layers. Finally, SSSP seems be the task that requires fewer layers on average, with AMP selecting less than ten layers reach a very competitive score. Overall, it appears that folded normal and mixtures of folded normal distributions were selected more frequently as the best hyper-parameter for the syn- thetic tasks; in particular, the distributions for Eccentricity look sharply peaked, as if the models would need to use only the information computed at the very end of the deep architecture. It is worth remarking that this behavior is com- pletely adaptive and guided by the task. Finally, we observe that the distributions learned on the chemical datasets are
The ablation study, on the other hand, provides evidence that message filtering is, in most cases, a good strategy for performance improvements. We see that, for each model and dataset, input-based and embedding- based filtering provide a positive improvement in scores compared no-filtering. Points lying in the grey area correspond no improvement. We conclude that the choice of which filtering strategy to use remains matter of empirical investigations.
6. Conclusions
We have introduced Adaptive Message Passing, a probabilis- tic framework that endows message passing architectures with the ability to learn how many messages to exchange between nodes and which messages to filter out. Our ap-
Averaggdd over 250 validation nodes due to prohibitive costs.
8

---

Adaptive Message passing
% of informatio preserved
100
Embed Bused Filter (A io (SME)
ADGNN
0.0
(MluettxAMMGGGC
80
Diameter GAMF
Fccenricity (AMP ADGN AAGN)
0.5
60
Eccentricty GCMP
GCN
Eecentricity (IMP
-1.0
40
Fccentriety
SSSP (AMP ADGN
SESP (AMP GCN)
SSSP
-155
SSSP LAMP GIN
20
pegeides-fune
pepcides-sinux
-2.0
20
Laycrs
Input Based Filter (Alog
Embed. Based Filter (AAP)
0.030
pepeidesffune (AMP GCN
Emnhed. Based Filter (AMAR)
0.002
0.026
peptides-une (AMP (AMPGINE)
0.001
peptides-fune func (AMP (AMP CXTEDCGN)
0.020
0.015
-0.001
-0.002
0.010
peptides struct (AMP'GxX'
0.005
-0.004
poptides struct (AMP'INE))
0.000
pepiiee-sttudd (AMP GAHICGON)
-0.005
0.000
0.005
0.010
0.015
0.020
0.025
0.030
0.000 0.001 0.002
Input Based Filter (AAP)
Input Based Filter (AMAE)
Figure 5. (Top right) visualize the amount of information preserved in each layer by AMP (Others) Ablation study of message filtering scheme: If a point lies in the area represented by the gray color, then filtering is not beneficial.
proach actively targets the long-range issue by relying on the observation that filtering messages mitigates oversmooth- ing and oversquashing, whereas learning depth can ideally solve underreaching. AMP achieves competitive results long-range datasets without imposing strong inductive biases. Through qualitative analyses, findings reveal how AMP learns very deep architectures if necessary for the task, and the amount of information propagated can greatly be reduced compared to classical message passing. Overall, our approach suggests that it might not be necessary to alter initial graph structure, e.g., through rewiring, to improve the performances on long-range tasks. We hope Adaptive message passing will foster exciting research opportuni- ties in the graph machine learning field and find successful applications in physics, chemistry, and material sciences.
References
Abboud, R., Dimitrov, R., and Ceylan, I. Shortest path net- works for graph property prediction. The 1st Learning on Graphs Conference (LoG). 2022.
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 Pro- ceedings of the 36th International Conference on Ma- chine Learning (ICML), 2019.
Alon, U. and Yahav, E. On the bottleneck of graph neural networks and its practical implications. In 9th Interna- tional Conference on Learning Representations (ICLR), 2021.
Impact Statement
This paper presents work whose goal advance the field of Machine Learning. There are many potential societal consequences of our work, none of which feel must be specifically highlighted here.
Bacciu, D., Errica, F., and Micheli, A. Contextual Graph Markov Model: A deep and generative approach graph processing. In Proceedings of the 35th International Conference on Machine Learning (ICML), volume 80, pp. 294-303, 2018.
Bacciu, D., Errica, F., and Micheli, A. Probabilistic learn- ing on graphs via contextual architectures. Journal of Machine Learning Research, 21(134):1-33 2020a.

---

Adaptive Message passing
Bacciu, D., Errica, F., Micheli, A., and Podda, M. A gentle introduction to deep learning for graphs. Neural Net- works, 129:203-221, 9 2020b.
Chen, D., O'Bray, L.., and Borgwardt, K. Structure-aware transformer for graph representation learning. In Proceed- ings of the 39th International Conference Machine Learning (ICML). PMLR, 2022.
Banerjee, P. K. Karhadkar, K., Wang, Y. G., Alon, U., and Montúfar, G. Oversquashing in gnns through the lens of information contraction and graph expansion. In Proceed- ings ot the 58th Annual Allerton Conference on Commu- nication, Control, and Computing (Allerton), 2022.
Chen, M., Wei, Z.,, Huang. Z., Ding, B., and Li. Y. Simple and deep graph convolutional networks. In Proceedings of the 37th International Conference on Machine Learning (ICML), 2020a.
Barbero, F., Velingker, A., Saberi, A., Bronstein, M. M., and Giovanni, F. D. Locality graph rewiring in GNNs. In Proceedings of the 12th International Conference on Learning Representations (ICLR), 2024.
Chen, Y., Wu, L.,, and Zaki, M. Iterative deep graph learning for graph neural networks: Better and robust node embed- dings. Proceedings of the 34th Conference on Neural Information Processing Systems (NeurIPS), 2020b.
Bernardo, J. M. and Smith, A. F. Bayesian theory, volume 405. John Wiley & Sons, 2009.
Corso, G., Cavalleri, L., Beaini, D., Liò, P., and Veličković, P. Principal neighbourhood aggregation for graph nets. In Proceedings of the 34th Conference on Neural Infor- mation Processing Systems (NeurlPS), 2020.
Blei, D. M., Kucukelbir, A., and McAuliffe, D. Varia- tional inference: A review for statisticians. Journal of the American statistical Association, (2(518):859-877) 2017.
Deac, A., Lackenby, M., and Veličkovie, P. Expander graph propagation. In The 1st Learning on Graphs Conference (LoG), 2022.
Bober, J., Monod, A., Saucan, E., and Webster, K. N. Rewiring networks for graph neural network training us- ing discrete geometry. In International Conference On Complex Networks And Their Applications, 2023.
del Castillo, J. and Pérez-Casany, M. Overdispersed and underdispersed poisson generalizations. Journal of Sta- tistical Planning and Inference, 134:486-500, 2005.
Bongini, M., Rigutini, L., and Trentin, E. Recursive neural networks for density estimation over generalized random graphs. IEEE Transactions Neural Networks and 5458, 2018.
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 Proceedings of the 40th International Conference on Machine Learning (ICML), 2023.
Learning Systems,
Bresson, X. and Laurent, T. Residual gated graph convnets. arXiv preprint arXiv: 2017.
Ding, Y., Orvicto, A., He, B., and Hofmann, Recur- rent distance filtering for graph representation learning. In Proceedings of the 41st International Conference on Machine Learning (ICMI., 2024.
Brockschmidt, M. Gnn-film:
Graph neural networks with feature-wise linear modulation. In Proceedings of the 37th International Conference on Machine Learning (ICML), 2020.
Dwivedi, V. P., Rampášek, L.,, Galkin, M., Parviz, A., Wolf, G., Luu, A. T.,, and Beaini, D. Long range graph bench- mark. In Proceedings of the 36th Conference on Neural Information Processing Systems (NeurIPS), 2022.
Campa, A., Dauxois, T., Fanelli, D., and Ruffo, S. Physics of long-range interacting systems. OUP Oxford, 2014.
Castellana, D. and Errica, F. Investigating the interplay between features and structures in graph learning. In MLG Workshop at ECMI. PKDD, 2023.
Errica, F. On class distributions induced by nearest neighbor graphs for node classification of tabular data. In Pro- ceedings of the 37th Conference on Neural Information Processing Systems (NeurIPS), 2023.
Castellana, D., Errica, F., Bacciu, D., and Micheli, A. The infinite contextual graph Markov model. In Proceedings of the 39th International Conference Machine Learn- ing (ICML), pp. 2721-2737, 2022.
Faber, L. and Wattenhofer, R. GwAC: GNNs with asyn- chronous communication. In The 2nd Learning on Graphs Conference (LoG), 2023.
Chamberlain, B., Rowbottom. J., Gorinova, M. I., Bronstein, M., Webb, S., and Rossi, E. Grand: Graph neural diffu- sion. In Proceedings of the 38th International Conference on Machine Learning (ICMI.,, 2021.
Fahlman, S. and Lebiere, C. The correlatioel learn- ing architecture. In Proceedings of the 3rd Conference on Neural Information Processing Systems (NIPS), 1989.
10

---

Adaptive Message passing
Fatemi, B., Abu-EI-Haija, S., Tsitsulin, A., Kazemi, M., Zelle, D., Bulut, N., Halerow, J., and Perozzi, B. Ugst: A unified framework for benchmarking graph structure learning. In Topology, Algebra, and Geometry in Machine Learning Workshop, ICMI., 2023.
Hammer, B., Micheli, A., and Sperduti, A. Universal approx-
imation capability of cascade correlation for structures. Neural Computation, 17(5):1109-11 2005.
Harris, T., Yang. Z., and Hardin, J. W. Modeling underdis- persed count data with generalized poisson regression. The Stata Journal, 12:736 747, 2012.
Ferber, M., Zoete, V., and Michielin, O. T-cell receptors binding orientation over peptide/mhe class i is driven by long-range interactions. PloS one, 7(12):e51943, 2012.
Hasanzadeh, A., Hajiramezanali, E., Boluki, S., Zhou, M., Duffield. N., Narayanan, K., and Qian, X. Bayesian graph neural networks with adaptive connection sampling, Proceedings of the 37th International Conference on Machine Learning (ICML), 2020.
Finkelshtein, B., Huang, X., Bronstein, M. M., and Ceylan, I. Cooperative graph neural networks. In Pro Proceedings of the 41st International Conference Machine Learning (ICML), 2024.
He, X., Hooi, B., Laurent, T., Perold, A., LeCun, Y., and Bresson, X. A generalization of vit/mlp-mixer to graphs. In Proceedings of the 40th International Conference on Machine Learning (ICMI.), 2023.
Franceschi, L.,, Niepert, M., Pontil, M., and He, X. Learning discrete structures for graph neural networks. In Proceed- ings of the 36th International Conference on Machine Learning (ICML), 2019.
Frasca, F., Rossi, E., Eynard, D., Chamberlain, B., Bron- stein, M., and Monti, F. Sign: Scalable inception graph neural networks. In Graph Representation Learning and Beyond (GRL+) Workshop, ICML,, 2020.
Heilig, S., Gravina, A., Trenta, A., Gallicchio, C., and Bac- ciu, D. Port-hamiltonian architectural bias for long-range propagation in deep graph networks. In Proceedings of the 13th International Conference on Learning Represen- tations (ICLR), 2025.
Gabrielsson, R. B., Yurochkin, M., and Solomon, Rewiring with positional encodings for graph neural net- works. Transactions on Machine Learning Research, 2023. ISSN 2835-8856.
Hu, W., Liu, B., Gomes, J., Zitnik, M., Liang, P., Pande, V., and Leskovec, J. Strategies for pre-training graph neural networks. In Sth International Conference on Learning Representations (ICLR), 2020.
Gasteiger, J., WeiBenberger, S., and Günnemann, S. Diffu- sion improves graph learning. In Proceedings of the 33rd Conference on Neural Information Processing Systems (NeurIPS), 2019.
Jordan, M. I., Ghahramani, 7.,, Jaakkola, T. S., and Saul, L. K. An introduction to variational methods for graphical models. Muchine Learning, 37:183-233, 1999.
Goel, P. K. and Degroot, M. H. Information about hy- perparamters in hierarchical models. Journal of the American Statistical Association, 76(373):140-147 1981.
Karhadkar, K., Banerjee, P. K., and Montufar, G. FoSR: First-order spectral rewiring for addressing oversquash- ing in GNNs. In The Ith International Conference on Learning Representations (ICLR), 2023.
ISSN 01621459.
Gravina, A., Bacciu, D., and Gallicchio, C. Anti-symmetric DGN: a stable architecture for deep graph networks. In 1Th International Conference on Learning Representa- tions (ICLR), 2023.
Kazi, A., Cosmo, L., Ahmadi, S.-A., Navab, N., and Bron- stein, M. M. Differentiable graph module (dgm) for graph convolutional networks. IEEE Transactions Pattern Analysis and Machine Intelligence, 45: 15:1606-22 1601616611,,, 2022.
Gruber, L., Schäfl, B., Brandstetter, J., and Hochreiter, S. Processing large-scale graphs with g- g-signatures. ICML. 2024 Al for Science Workshop. 2024.
Kipf, T. N. and Welling, M. Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations (ICLR), 2017.
Gutteridge, B., Dong, X., Bronstein, M. M., and Di Gio- vanni, F. Drew: Dynamically rewired message passing with delay. In Proceedings of the 40th International Con- ference on Machine Learning (ICML), 2023.
Kurihara, K., Welling, M., and Teh, Y. W. Collapsed varia- tional dirichlet process mixture models. In Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI), 2007.
Hamilton, W., Ying, Z., and Leskovec, J. Inductive rep- resentation learning on large graphs. In Proceedings of the 31st Conference on Neural Information Processing Systems (NIPS), pp. (024-1034 2017.
Leone, F. C., Nelson, L. S., and Nottingham, R. B. The folded normal distribution. Technometrics, 3:543-550, 1961.

---

Adaptive Message passing
Li, G., Muller, M., Thabet, A., and Ghanem, B. DeepGCNs: Can GCNs go deep as CNNs? In Proceedings of the IEEE/CVF International Conference Computer Vision (ICCV), 2019.
Poli, M., Massaroli, S., Rabideau, C. M., Park, J., Yamashita, A., Asama, H., and Park, J. Continuous-depth neural models for dynamic graph prediction. arXiv preprint arXiv:2106.158// 2021.
Li, Q. Han, Z., and Wu, X.-M. Deeper insights into graph convolutional networks for semi-supervised learning. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI), 2018.
Qian, C., Manolache, A., Ahmed, K., Zeng. Z., Broeck, G. V. d., Niepert, M., and Morris, C. Probabilistically rewired message-passinng neural networks. In Proceed- ings of the 12th International Conference on Learning Representations (ICLR), 2024a.
Li, Y. Wang, Y. Huang, L.,, Yang, H., Wei, X., Zhang, J., Wang, T., Wang, Z., Shao, B., and Liu, T.-Y. Long-short- physics-informeet framework to capture non-local interaction for scalable molecular dynamics simulation. In Proceedings of the 12th Interna- lional Conference Learning Representations (ICLR), 2024.
Qian, C.,, Manolache, A., Morris, C., and Niepert, M. Prob- abilistic graph rewiring via virtual nodes. In The 38th Annual Conference on Neural Information Processing Systems (NeurIPS), 2024b.
range message-passingg
Rampášek, L., Galkin, M., Dwivedi, V. P., Luu, A. T., Wolf, G., and Beaini, D. Recipe for general, powerful, scalable graph transformer. In Proceedings of the 36th Conference on Neural Information Processing Systems (NeurIPS), 2022.
Liu, J., Kawaguchi, K., Hooi, B., Wang, Y., and Xiao, X. Eignn: Efficient infinite-depth graph neural networks. In Proceedings of the 35th Conference on Neural Informa- tion Processing Systems (NeurIPS), 2021.
Rong, Y., Huang, W., Xu, T., and Huang. J. Dropedge: Towards deep graph convolutional networks on node clas- sification. In 8th International Conference on Learning Representations (ICLR), 2020.
Ma, L., Lin, C., Lim, D., Romero-Soriang A., Dokania, P. K., Coates, M., Torr, P., and Lim, S.-N. Graph in- ductive biases in transformers without message passing. In Proceedings of the 40th International Conference Machine Learning (ICML), 2023.
Roy, D. The discrete normal distribution. Communications in Statistics Theory and Methods, 32:1871-1888 2003. doi: 10.1081/sta- 120itaa-22022556.
Micheli, A. Neural network for graphs: A contextual con- structive approach. IEEE Transactions on Neural Net- works, 20(3):498-511 2009.
Rüegsegger, U., Leber, H., and Walter, P. Block of hacl translation by long-range base pairing is released by cytoplasmic splicing upon induction of the unfolded protein response. Cell, 107(1):103-114, 2001.
Müller, L., Galkin, M., Morris, C., and Rampášek, L. At- tending to graph transformers. Transactions on Machine Learning Research, 2024.
Rumelhart, D. E., Hinton, G. E., and Williams, R. J. Leam- ing representations by back-propagating errors. Nature, 323:533-536 1986.
Nazaret, A. and Blei, D. Variational inference for infinitely deep neural networks. In Proceedings of the 39th In- ternational Conference on Machine Learning (ICML), 2022.
Rusch, T. K., Chamberlain, B., Rowbottom, J., Mishra, S., and Bronstein, M. Graph-coupled oscillator networks. In Proceedings of the 39th International Conference on Machine Learning (ICMI., 2022.
Oono, K. and Suzuki, T. Graph neural networks exponen- tially lose expressive power for node classification. In 8th International Conference Learning Representations (ICLR), 2020.
Rusch, K., Bronstein, M. M., and Mishra, S. A survey on oversmoothing in graph neural networks. arXiv preprint arXiv:2303.10993, 2023.
Park, S., Ryu, N., Kim, G., Woo, D., Yun, S.-Y., and Ahn, S. Non Non-backtracking graph neural networks. Transactions on Machine Learning Research, 2024.
Sanchez-Gonzalezz A., Godwin, J., Pfaff, T., Ying, R., Leskovee, J., and Battaglia, P. Learning to simulate com- plex physics with graph networks. In Proceedings of the 37th International Conference on Machine Learning (ICML), 2020.
Piana, S., Lindorff-Larsen, K., Dirks, R. M., Salmon, J. K., Dror, R. O., and Shaw, D. E. Evaluating the effects of cutoffs and treatment of long-range electrostatics in protein folding simulations. PLoS One, 7(6):139918, 2012.
Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M., and Monfardini, G. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80, 2009.
12

---

Adaptive Message passing
Shirts, M. R., Mobley, D. L.,, Chodera, J. D., and Pande, V. Accurate and efficient corrections for missing dispersion interactions in molecular simulations. Journal of Physical Chemistry B, 111:11052-130000 2007.
Xu, K., Li, C., Tian, Y., Sonobe, T., Kawarabayashi, K.-I., and Jegelka, S. Representation learning on graphs with jumping knowledge networks. Proceedings of the 35th International Conference on Machine Learning (ICML), pp. 5453-5462, 2018.
Shirzad, H., Velingker, A., Venkatachalam, B., Sutherland, D. J., and Sinop, A. K. Exphormer: Sparse transformers for graphs. In Proceedings of the 40th International Conference on Machine Learning (ICML), 2023.
Xu, K., Hu, w., Leskovec, J., and Jegelka, S. How pow- erful are graph neural networks? In 7th International Conference on Learning Representations (ICLR), 2019.
Sperduti, A. and Starita, A. Supervised neural networks for the classification of structures. IEEE Transactions Neural Networks, 8(3):144-335, 1997.
Young, L. C. An inequality of the hölder type, connected with stieltjes integration. Acta Mathematica, 67:251-282. 1936. URL https: / /api..pp...//// semantccscholar org/ Ctrr/orrrss/./ 122 61 8935.
Spinelli, I., Scardapane, S., and Uncini, A. Adaptive propa- gation graph convolutional network. IEEE Transactions on Neural Networks and Learning Systems, 32(10):4755- 4760, 2020.
Yu, D., Zhang, R., Jiang, Z., Wu. Y., and Yang. Y. Graph- revised convolutional network. In Proceedings of the Ma- chine Learning and Knowledge Discovery in Databases: European Conference (ECMI. PKDD), 2020.
Tönshoff, J., Ritzert, M., Rosenbluth, E., and Grohe, M. Where did the gap go? reassessing the long-range graph benchmark. In The 2nd Learning on Graphs Conference (LoG), 2023a.
Zhao, T., Liu, Y., Neves, L., Woodford, O., Jiang, M., and Shah, N. Data augmentation for graph neural networks. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), 2021.
Tönshoff, J., Ritzert, M., Wolf, H., and Grohe, M. Walk- ing out of the weisfeiler leman hierarchy: Graph learn- ing beyond message passing. Transactions on Machine Learning Research, 2023b.
Zhou, K., Huang, X., Song, Q.. Chen, R., and Hu, X. Auto- gnn: Neural architecture search of graph neural networks. Frontiers in Big Data, 5:1029307, 2022.
Zhou, Z., Zhou, S., Mao, B., Zhou, X., Chen, J., Tan, Q..
Topping, J., Giovanni, F. D., Chamberlain, B. P., Dong, X., and Bronstein, M. M. Understanding over-squashing and bottlenecks on graphs via curvature. In 10th International Conference on Learning Representations (ICLR), 2022.
Zha, D., Feng, Y., Chen, C., and Wang, C. Opengsl: A comprehensive benchmark for graph structure learn- ing. In Proceedings of the 37th Conference on Neural Information Processing Systems (NeurIPS), 2023.
Tortorella, D. and Micheli, A. Leave graphs alone: Address- ing over-squashing without rewiring. In The 1st Learning on Graphs Conference (LoG), 2022.
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 Proceedings of the 34th Conference on Neural Information Processing Systems (NeurIPS), 2020.
Toth, C., Lee, D., Hacker, C., and Oberhauser, H. Capturing graphs with hypo-elliptic diffusions. The 36th Annual Conference on Neural Information Processing Systems (NeurlPS), 2022.
Velickovic, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., and Bengio, Y. Graph attention networks. In 6th International Conference on Learning Representations (ICLR), 2018
Wang, C., Tsepa, O., Ma, J., and Wang, B. Graph-mamba: Towards long-range graph sequence modeling with se- lective state spaces. arXiv preprint arXiv:2402.00789, 2024.
Wang, Y., Wang. Y., Yang, J., and Lin, Z. Dissecting the diffusion process in linear graph convolutional networks. In The 35th Annual Conference on Neural Information Processing Systems (NeurIPS), 2021.
13

---

Adaptive Message passing
A. Extended Related Work Section
Below we provide a more detailed related work section that does not fit in the main paper.
Oversquashing. There are many methods that attempt to address the oversquashing problem with the goal of better capturing long-range dependencies (Alon & Yahav, 2021; Li et al., 2024). There is agreement that modifying the message passing scheme leads to improved performances; in this sense, the graph structure does not match exactly the computational graph used to compute the node embeddings. Some works learn how a node should completely stop propagating a message in a fixed-depth architecture (Spinelli et al., 2020) or if it should only listen, isolate, or receive/broadcast its own message (Finkelshtein et al., 2024). Similarly, one can learn to sample edges at each message passing layer according to some learned parametrization (Hasanzadeh et al., 2020) or have completely asynchronous message passing (Faber & Wattenhofer, 2023). Our work differs from these works as we apply learned (soft) filtering to all existing messages.
Another idea is to modify message passing to avoid backtracking of messages back to the source node, to achieve less redundancy of information (Park et al., 2024). While this choice proves effective at several tasks, it is still an open question whether it is always the best choice for the task at hand. In attention baseodd----dddd--- approaches (Velickovic et al., 2018), an edge filter is computed using some non-linear relationship between the embeddings of the source and destination nodes. This can introduce a severe computational burden as the function needs to be applied to all edges. Similarly, GNN-FiLM (Brockschmidt, 2020) learns a feature-wise linear modulator that depends on the destination node and modulates the magnitude of all incoming messages.
On the other hand, rewiring approaches try to alter the graph connectivity rather than the message passing operation. This action is meant to increase the sensitivity (Topping et al., 2022) of node with respect to another, and it has been theoretically linked to the oversquashing problem. Some recent works try to preserve locality and sparsity of the rewiring process (Barbero et al., 2024) or dynamically rewire the graph based on the layers (Gutteridge et al., 2023). In contrast, others take a probabilistic approach to rewiring based on sampled sub-graphs (Qian et al., 2024a). Recently, a critical perspective on the effectiveness of rewiring approaches has also been given (Tortorella & Micheli, 2022).
Finally, we mention ordinary differential equation-based message passing approaches, which are provably preserving information regardless of the depth in the network (Gravina et al., 2023) and have shown great results on datasets aimed at capturing long-range dependencies.
Oversmoothing. Oversmoothing is perhaps one of the first problems that emerged empirically and was then analyzed theoretically (Li et al., 2018; Oono & Suzuki, 2020; Rusch et al., 2023). Not surprisingly, one practical solution to oversmoothing is dropping edges to reduce the overall flow of messages and, thus, avoid the convergence of all embeddings to the same value (Rong et al., 2020). Another well-known solution to alleviate oversmoothing is to employ skip/residual connections (Kipf & Welling, 2017; Li et al., 2019). which consists of summing the representations learned at deeper layers with those of previous ones. Similarly to what is done in this work, the concatenation of node representations across layers is also way to circumvent oversmoothing, which has been adopted in neural and probabilistic models to improve the downstream performances on several node and graph-related tasks (Bacciu et al., 2018: Xu et al., 2018; Bacciu et al., 2020a). Instead, an orthogonal research direction considers implicit neural networks for graphs that correspond to infinite-depth models and seem to be able to capture long-range dependencies (Poli et al., 2021; Liu et al., 2021). These models simulate synchronous message passing with potentially infinite number of pesssae-prropggaioon steps, and some of them appear to be empirically robust to the oversmoothing problem.
Adaptive Architectures. The last part of this section is dedicated to works that try to learn the architecture of the model during training. Our work is inspired by the unbounded depth networks (UDNs) of Nazaret & Blei (2022), who proposed a variational framework for learning the depth in deep neural networks. In the graph domain, the first approach to learning the depth of DGN was proposed by Micheli (2009), who applied the cascade correlation algorithm (Fahlman & Lebiere, 1989) to learn a proper depth for the task. In the field of graph representation learning, other works attempted to learn the width of the representation of each message passing layer by exploiting Bayesian non-parametric models (Castellana et al., 2022), which allows to save time and memory when building deeper probabilistic DGNs. Finally, it is important to notice that these works, including this manuscript, are all orthogonal to the popular field of neural architecture search (Zhou et al., 2022): The former attempts at dynamically modifying the architecture during learning, whereas neural architecture search approaches find smarter ways to carry out a grid search. An advantage of adaptive approaches is that they can greatly reduce time and computational costs to perform a
search.
14

---

Adaptive Message passing
Graph Rewiring, Structure Learning, and Transformer Models for Graphs. There has been a growing interest in adapting the input graph structure and, therefore, the pesssage-pssiing operations of DGNs. These approaches can be roughly divided into graph structure learning and rewiring methods on one hand and transformerrbased models on the other. There are several strategies of graph rewiring such as incorporating multi-hop neighbors (Gabrielsson et al., 2023) and nodes reachable through shortest paths (Abboud et al., 2022). Gutteridge et al. (2023) is most related to the filtering approach we layer. The methods MixHop
introduce as it rewires the graph for every message- (Frasca et al., 2020), and DIGL (Gasteiger et al., 2019) can also be considered as graph rewiring as these leverage different heuristics reach further-away neighbors in a single pesssage-passing layer. Deac al. (2022); Shirzad et al. (2023) use the notion of expander graphs alter the messages, while Karhadkar al. (2023) resort to spectral techniques, and Banerjee et al. (2022) propose random edge flip approach. There also exist rewiring heuristics based on particular metrics such as Ricci and Forman curvature (Bober et al., 2023). Finally, recent work has proposed an approach to rewire the input graph probabilistically and in a data-driven way (Qian et al., 2024a).
et al., 2019), SIGN
Graph structure learning (GSL) approaches are another line of work rewiring the input graphs. Here the focus is on node classification problems on a single graph. Typically, these methods maintain learnable function that assigns prior scores to the edges, and based on these scores a subset of edges is selected from the original graph (Chen et al., 2020b; Yu et al., 2020; Zhao et al., 2021). To introduce discreteness and sparsity, Franceschi et al. (2019); Kazi et al. (2022); Zhao et al. (2021) discrete categorical (sampled from using the Gumbel softmax trick) and Bernoulli distributions, respectively. Most existing GSL. approaches typically use k-NN algorithm, simple randomized version of k-NN, or represent edges with independent Bernoulli random variables. For a comprehensive survey of GSL, see Fatemi et al. (2023); Zhou et al. (2023). In the context of node classification, there has been recent progress in a more principled understanding of the possible advantages of GSL in the fully supervised setting (Castellana & Errica, 2023; Errica, 2023).
Graph transformers (Dwivedi et al., 2022; He et al., 2023; Müller al., 2024; Rampášek et al., 2022: Chen et al., 2022) adaptively change the message-passinng operations for each layer by applying an attention mechanism among all nodes of the input graphs. Experimental results have shown that graph transformers have the ability to mitigate over-squashing (Müller et al., 2024). Due to their attention mechanism, however, transformer-bis based models have typically a quadratic space and memory requirement.
State space models have also been applied to graphs (Wang et al., 2024). Similarly, theoretically grounded sequence- processing frameworks (Toth et al., 2022; Gruber et al., 2024), leveraging randomized signatures, demonstrated promising potential in alleviating oversquashing effects in large graphs. The main differences with AMP, Wang al. (2024) relies a separate sequence model to develop node selection mechanism whereas we work on the message passing itself; Toth et al. (2022) develops a new graph Laplacian that is better suited for long-range propagation; Gruber et al. (2024) converts graph into a latent representation that can be passed to downstream classifiers.
Contrary to all these approaches, AMP, the adaptive message passing approach presented here, uses a variational framework to jointly learn both the depth of the DGN and a filtering of the messages passed between nodes in each of these layers.
B. Generalization to New Families of Truncated Distributions
The family of "truncated"' Poisson distributions, proposed by Nazaret & Blei (2022) to learn unbounded depth networks, satisfies specific requirements that allow us to efficiently perform (variational) inference. In particular, by truncating the Poisson distribution at its quantile function evaluated at c, one can bound its support and compute expectations in finite time. However, the Poisson distribution suffers from equidispersion, meaning that the variance is equal to the mean; this is a particularly limiting scenario when learning distributions over the importance of layers. fact, one might also want to model variances that are smaller or greater than the mean, which is referred as under and over-dispersion, respectively, to learn broader class of distributions (del Castillo & Pérez- 2005; Harris et al., 2012). To address this problem, in the following we introduce two families of distributions and prove that they also satisfy the requirements defined in Nazaret & Blei (2022); we formally recall such requirements below.
Definition B.1. A variational family Q = q(w) over N+ is unbounded with connected and bounded members if
1. Vy E Q, (y) is bounded
2. VL E N+ 3q E Q such that L E argmax(g)
3. Each parameter in the set w a continuous variable.
15

---

Adaptive Message passing
0.14
0.8
0.10
p.m.F.
0.08
c.m.f.
0.6
0.06
0.4
0.2
0.02
quantile lower hound at 0.99
quantile upper bound at 0.99
0.00
10
30
35
Figure 6. (Left) Probability mass function of a DFN distribution with and a = 5. (Right) The cumulative mass function of the distribution with example lower and upper bounds (vertical dashed lines) for the quantile function evaluated 0.99 of the corresponding FN distribution (horizontal dashed line).
Condition is necessary compute the expectation over ((;; A) in finite time, condition 2 ensures that we can give enough probability mass to each point in the support of and condition 3 is required for learning the distributions' parameters in a differentiable manner.
The Discrete Folded Normal Distribution. folded normal (FN) distributions (Leone al., 1961) can model under-, equi-, and over-dispersion. They are parametrized by a mean parameter μ and a standard deviation o. Its density is defined
1
PeN(E: = V2T02
14,0 E R
(15)
V2TO2
To use FN distribution in AMP, the idea is to first define a discrete version of the folded normal (DFN) with the strategy highlighted in Roy (2003):
PDEN (1; a) = SI,(1;
(16)
PDEN (z; p. o)) = SEN(1 + 1; - SFN(2: o), Vx E N
(17)
where SFN(2; uu, o) is the cumulative distribution function (c.d.f.) of the folded normal distribution evaluated at v. It is also useful to notice the equivalence between the c.d.f of the DFN SpEN(I; or) and that of a folded normal SpN(2;
SpAN p1 O)
Σ (D)N(E; (, SIN(# 1; E,
(18)
which implies that SDFN(I; nt, a) > SFN(2; (,) o). Figure 6 shows the probability mass function (p.m.f.) of a DFN distribution with = and = 5 and its cumulative mass function (c.m.f.).
Clearly, condition of Definition B.1 is satisfied. is also trivial to satisfy condition 2 by choosing a peaked distribution with small value of a. In what follows, we focus on lower and upper bounds the quantile function evaluated at c the DFN distribution so that we know we can truncate the distribution the finite quantile threshold, meaning condition also satisfied.
Theorem B.2. There exists lower and upper bounds to the quantile evaluated at 0 < c < 1. for any DFN distribution with a > 0.
Proof. We first need to compute a lower bound to the quantile function of the FN distribution since there is no closed formula for it. To start, we note that the c.d.f. of the Gaussian distribution is greater or equal to that folded normal distribution:
erf
x x-
+ 1 1
erf
x 11 o
erf
erf
(x
Sin(1;,,
(19)
ov2
S
Wee note that support defined over and not on t this not an issue from a practical point of view.
16

---

Adaptive Message passing
where "erf" is the error function. This implies that the quantile threshold of the Gaussian ae. which know how to
compute, is reached earlier than that of the FN 3rx, that is, 3G 2Fx, and in particular [ S [arN] are also lower
bounds. It then follows from Equation 18 that [ 1 is lower bound for the DFN distribution.
To find an upper bound, we apply Chernoff's Bound
(t exx
p(X 2 x)
Vt > 0
(20)
where X is a F.v. that follows a folded normal distribution with mean μ and standard deviation o, and Mx = E the well-known moment generating function of the X. To find an upper bound the quantile threshold, we need that
(1 c) (t for some choice of t. Defining & the normal c.d.f. ((x))
2 1 erf x 0, we choose t
and obtain
Mx(t) exx
(e 22 ( (M + 1) + c
222 - u
(-m +1)
t
(21)
= etE
1 (=+1)) + 2 (- +1
1
(22)
E21/0
ke
(23)
h = e
@ (1++)) + +
( +1)
1
0.
(24)
221//0
Therefore, the upper bound of the quantile threshold is given by
ke - = (11-c)
(25)
In k + p- =In(1 - c)
(26)
o lnkk + μ - x = o In(1 (n
(27)
x x= μ + a In - In(1 c)- c)-
(28)
Therefore, if the upper bound to the quantile of the FN is x, it follows from Equation 18 that 1 is also an upper bound of the DFN.
Consequently, we can efficiently find the true quantile threshold by running a binary search between the lower and the upper bounds. Figure 6 (right) shows an example of lower and upper bounds (vertical dashed lines) as well as the true quantile threshold of the FN distribution.
A Mixture of Simpler Distributions. is possible to learn more complex distributions q(;; w) that satisfy the conditions of Definition B.1 by mixing simpler distributions like the DFN defined above. A mixture of C families of unbounded distributions (C; ".......cc. (e; w) with bounded and connected members is defined as:
(M((:w) = Σ ()
(29)
where 0 < w; < is mixture's i weight and Di- wi = 1. Conditions 2 and are again trivially satisfied (a mixture can always collapse to one of its distributions that satisfy said conditions), and below, we show that lower and upper bounds still exist.
Theorem B.3. There exist lower and upper bounds to the quantile evaluated at 0 < < for mixture of C distributions that satisfy the conditions of Definition B.I, provided that lower and upper bounds exist for each distribution in the mixture.
Proof. The c.m.f. of mixture of discrete distributions can be written as a weighted sum of c.m.f.s:
Sm(I;w) Σ (KSWW)
(30)
17

---

Adaptive Message passing
Let x² be the greatest upper bound of the quantile threshold across all C' components of the mixture, and let i" be the associated component. It follows that, Vj, Sx("" 2 c, and
:m( Σ w. S,('
w
(31)
Therefore, x" also an upper bound for the mixture distributions. It possible to prove that a lower bound of the mixture the smallest lower bound of the quantile threshold across all C' components using a similar approach.
To summarize, we have shown how one can use more complex families of distributions in the context of AMP, allowing us to model under and over-dispersion. In this work, we will treat the choice of the family of distributions q(E; w) as Syper-parameter to be tuned.
C. ELBO Derivation
We now report the full derivation of our ELBO for a single sample:
In p(gr, y,,)
1,(0,,,FF.lo:. [l L, F,F,, F,,
(32)
= BggL In {[= Bg(0lLan) In p(0)
p(L)
(33)
q(0)L: v)
p( (F))
+ (a(001:a))(Flooo..)))
In g(Filgg, L, 0)
+ Inp(( (. [L, F, 0lgi)
(34)
i
In p(()
p(v) In p(F.) q(v(e:v)
Σ
((; 2)
In
In (Y, F,, vg))
(35)
((:)))
q (F.lg. Lvv)
The extension to the full dataset is identical except for the decomposition of the rightmost term into a product of conditional probabilities, one for each i.i.d. sample.
D. On Oversmoothing, Oversquashing, and Underreaching
In this section, we discuss AMP's implications on oversmoothing, oversquashing, and underreaching, all of which hamper the ability of DGNs to capture long-range interactions between nodes in the graph and are related in subtle ways.
Oversmoothing. Oversmoothing has been formally defined by Rusch et al. (2023) as the convergence of a node embed- dings' similarity as the number of message passing layers increases. other words, it formalizes the widely accepted notion that node embeddings tend become identical after many layers of message passing. Different oversmoothing metrics have been proposed, and in this work, we consider the Dirichlet energy (Rusch et al., 2022; 2023) at layer E defined as
E(H*)
1 ΣΣ VI NEV
| 1
(36)
where we indicate with H the set of node embeddings computed at layer
There are at least two reasons why AMP alleviates oversmoothing. The first is that, in principle, the adaptive message filtering scheme reduces the synchronous exchange of all messages at given layer, and message exchange will be different depending on the specific layer. The second is that the readout mapping of each layer directly propagates the gradient of the loss into the corresponding message passing operation, which encourages diversity of node representations of each layer ! as long as ql; >) is large enough (that is, layer l's output is important for the final prediction). In our experiments, we will show that AMP can generate architectures in which the Dirichlet energy does not decay exponentially and thus suffers less from oversmoothing than the baselines.
18

---

Adaptive Message passing
3
3
1
5
3
3
8
3
Standard MP
Adaptive MP
Figure 7. Comparison of the 2-hop computational tree necessary to compute h3 in the graph of Figure 2 for standard message passing (left) and AMP (right), where we discretized message filtering to simplify the concept. AMP can effectively prune/filter information in sub-trees to propagate only the relevant information for the task.
Oversquashing. The term oversquashing refers to the compression of an apponentially-growiiie amount of information (Micheli, 2009) into fixed-size node embeddings (Alon & Yahav, 2021; Di Giovanni et al., 2023), causing possibly severe bottleneck that hampers DGNs ability to effectively propagate task-specific information. An intuitive visualization is provided in Figure 7 (left), where node 3 of the graph defined in Figure 2 needs to compress information of its 2-hop neighborhood into a single node embedding. The literature on the topic is already vast despite its very recent introduction; some works address topological bottlenecks through rewiring of the original graph structure (Topping et al., 2022), while others preserve information by viewing the message passing operations through the lens of ordinary differential equations (Gravina al., 2023; Heilig et al., 2025). By properly modifying the curvature of graph (Topping al., 2022), some graph rewiring approaches aim at increasing the sensitivity of node's embedding h with respect the input σ of another node v, that is capture long-rarn range dependencies. Indeed, by rewiring two distant nodes with a new edge, the sensitivity of these two nodes will almost certainly increase.
Topping et al. (2022) argue that increasing the sensitivity can alleviate oversquashing and better
da t
While we do agree that long-range dependencies can be better captured, we argue that rewiring might make the computational bottleneck problem worse by adding extra information be compressed into node's embedding (assuming other edges not removed). In contrast, the adaptive filtering scheme of AMP shown in Figure 7 (right) might decrease the overall sensitivity defined above, but at the same time it will reduce the number of messages that need to be compressed into node 3, hence alleviating oversquashing. Similarly, the synthetic datasets defined in Alon & Yahav (2021), which are meant to measure how well a model addresses oversquashing, require that all information is preserved to solve a task. This would certainly be a good test-bed for ODE-based models (Gravina et al., 2023), but other tasks might require propagating only a subset of the total information contained in the graph. The ability to isolate such information from the rest can be seen as solution the oversquashing problem, which is exactly the opposite goal of the synthetic tasks previously mentioned. In summary, the problem of "oversquashing" is clearly multi-faceted and requires great care regarding its evaluation. As such, it might be good idea for the future to decompose over-squahhing into simpler sub aub-rroblems, such as the ability to isolate the relevant information (which AMP can do), the ability to propagate all information, and the ability to increase the sensitivity between far-away nodes.
We complement this discussion with a Theorem, inspired by Di Giovanni et al. (2023), that shows how AMP can control the upper bound on the sensitivity by filtering messages.
Theorem 3.1 For AMP with layers, embedding dimension d, and u, v E V,
the
S d ((cup (Cral + Cmp (crkn + kF) A))²) v4
@Mo
Here, MPNN is in the following form
(Rd (e h up (s((h + mp An k1-)
where up, rs, and mp are Lipschitz functions as in Di Giovanni et al. (2023) with constants Cups Cray Cmps OF is the upper bound of the entr L' matrix norm of åf for the filtering function F, kn is the maximal absolute value among the Or entries of h, and similarly ky for the output of F.
19

---

The right-hand side of (37) is further expanded to Adaptive Message passing
Proof. Case: = 1
The gradient of the a-th element of hidden vector after the first layer with respect the 3-th element of an input is written as
ah a
d
Oupt.a
d
Örs--P Ol
@mpl-p
(F h4)
Σ
Σ
Auz
pzp
dr, Ohu
drg
Hereinafter, a, 3 E [d] and for scalar-valued function dz. represents the derivative of with respect s-th element x, of its vector imput. We define part of the second term in the right-ham side of the above equation
Øf
a (Fo(h) O 12)
M() =
Oh 0.8
and then
(N))
0h..
M(2)
1.. (h))
oha 0.3
Otu 0,3
d ( 0h
2h ah
h + F (h%)
Oh
Oh
Therefore,
oh 0
Öupl.a
d Örst.p 0h..r
@mplip
Σ Auz M())
=
dzp
dz, ahu
dzg
@upl.a Ōrst.p
Suplia Oxp
@mplip
80a
Σ Az)
(37)
dxp
Org
dzg
8=
Ōupl.a d
@mpt-
d FF oh
Auz
0.4
(38)
0zp
Bzg
dz, Dh
p=
q=1
aupz.a
Smplip
ah..4 0.4
Σ Au F9 (h)
(39)
Ozg
ah 0.3
9-1
Since this is the very first layer of MPNN, both terms can be reduced to simpler forms. Indeed, (38) can be reduced to Using (generalized) Hölder's inequality, inequality (3.1) in Young (1936), we get
Ōup
d
Omp'.p
OF
(38)=
A Ors
0.4
Ox.
0r.
Oup 1. Oxp
0mp' 1. dxy
OF
[(38) < Avu
[64-9
Ox
d
aup I
d
0mp 1.
d OF
< A Knn
Dzp
p=1
< Avu
Cup
Cmp
CF
kn.
(40)
Similarly, the norm of (39) is also bounded from above
[(39] I AvaCupCmppr.
20

---

Adaptive Message passing
The left-hand term of (37) is also bounded by Cup va (see also the proof of Theorem B.1. in Di Giovanni al. (2023).) and get
ah
S Cup (Crsl Cmp (crks + kF) A)
0h 0.3
Case: arbitrary L.
The gradient of the hidden vector at the layer of arbitrary is written as
Oup
Örs oh
@mp
① (F(h)) o n2) o
Σ
Auz
0 0,5
Orp
dr, 0.B
dsg
Ohu 0.5
Define and expand the right-hand term of the above equation as follows:
Ömp
①
((())) O N))*
(#)
Σ
Ave
Drp
dzg
Oh 0.8
OupetI,a ela
0mp e.1
0F4 oh Er
ah59
Σ Auz
Σ
M + (h))
Stp
deg
dr. 0.
0ho.3
Then, its norm is
Qup-+1.0s +1,
Ömp 1.
d OF
Oh
(#)1
Σ Aus
Orp
dzg
0s,
Oh 0,5
P
r=1
Oup
@mpe+I.p
0h.99
Σ
Σ Auz
Oxp
dzg
0,8
aup + tla
Ömp +
OF
Aua
|65-9
Oup
Oer
@up
Ōmpe+I.p eII.p
Omp
Σ Ausa |r (p(())
Otp
asg
Cup ((Crs I + Cmpp (crkin + kr) Dom-
(41)
The first term of (41), except the constant term, is bounded from above:
Ōup
8mp
0F4
Σ Ave
Σ
|15-9
Σ
Dap
azyg
acr,,
d
dup 1,a
@mp ( +1pp
0.a9
Σ Avz
Σ
kin
Σ
Dr.
Seg
O.r
p=l
rva
Cup
Cmp
kn,
CF
E Avz-
(42)
Note that the first inequality is derived by using Hölder inequality again. Similarly, the second term of (41) is
aup
1mp
aup
8mp 1,p
Σ Aus
F(159)
Σ Auz
kr
Oxp
0z.
Ox,
Or..
q=1
S Cup
Cmp
kF
Σ Avg.
(43)
21

---

Adaptive Message passing
Finally, define
UB({)== == 1p = cup (cat cmp (ophin + kip) A)
a a
and then the norm of
is
Ohetia O
d Cup
Örs dz,
Ohe Oh )
+ ((42) + (43)) UB(()au
Oxp
p=1
S Crs Cis UB( + Cup
Av UB({) + Cup Cuppk Σ Avs (B))ss
s+1
Crs - UB ra + Σ Cmp Ckppk + kF)
Avs U L.B.N.
E+1 (col + CmplknnF + kF))) Cup
UB(E + 1)
which completes the proof.
Underreaching. Finally, underreaching is defined as the inability of standard message passing with K layers to capture interactions of range greater than K. Alon & Yahav (2021) addresses this problem by adding a message passing layer on fully connected graph at the last layer of the architecture, which empirically improves the performances but does not fundamentally solve the problem. A solution to this problem is letting the model decide the right depth of the architecture for the task, which is exactly what AMP does.
Below, we provide the extended formulation and proof of our theorem about the propagation of message unchanged through the graph.
Theorem 3.2 Let consider graph g (V,E,), X). where V {1....,,, nyg is the set of nodes connected via oriented edges = = ((u, u)lu, v E V}, and X' (x, E |R V} is the set of d node aftributes. The neighborhood of a node is defined as N₁, = (ul(u, }. Further, let us define the following message aggregation scheme, which produces vectors h, E Rd for node u at iteration f, up to a maximum iteration K:
h Fy
(44)
h Σ F(u,O)n (121), uEN.
where F(u, E) E (0.1)", Vu VUEVE [1, K] and O is the element-wis product. Let us also assume that g contains two (not necessarily distinct) nodes u and u, and walk ((v, v2).... (uK, u)) of length K 2 exists between them. Then, Ve. there exists a parametrization of F such that h belongs the closed ball B(x,, de, I11) of radius de centered at x under norm |||.
Proof. We prove the statement by induction over K.
Base (K 1): In this case, the source node is neighbor of the destination node It holds that
h
Σ F(u',)
h
W.N.
= F(u,, ①
Σ
F(u', 1) о a.
weN.N(u)
22

---

Adaptive Message passing
We choose F(v, 1) 1 Ev and F(u,; 1) Eu', for some uur Eo' with all components 0, therefore
h = (1 - Ev)
+
Σ
Eu O ww
(EN
Σ
(-1)0(u'
.0) Ew ① Lw'
Lv +
W.N.
At this point, we can always choose Ewr, Vu' E Nu such that, Vi E [I,.... d] it holds
Σ
(-1)6(u'm)) ()) Ear Mi [ S
-E
w'EN.
noting that the inequality is due to the fact that values of Ea can be negative. Therefore, for every i we have that
z - < - k S m.1i + = |A
x.lill S
(45)
which implies h E B(x,, de, || I11).
Inductive case (K > I): Let us consider random walk of length K, and assume our proposition holds for values up to K- 1. With the same arguments as before, we can write
ht = (1 -E- Eux
② hox
K-1
Σ
En @ h
Σ W'
(-1)6(u',en) Enr h-1
By the inductive hypothesis we know that there exists a parametrization of F (up to iteration K - 1) such that h K-1
E
B(x,, dg, - IIt). As before, we pick Ew', Vu' E No such that, E .l,....de d] it holds
Σ
(-1)6tw ax) e [i] [
N.EN
and therefore, noting that [,
1/2 S h
[i] S xe + by the inductive hypothesis,
r.1i 2
< M K
x.. 2 _ |
x. [i)s S
(46)
2
meaning h E B(æ,, de, 111)
It is worth noting that the use of differentiable sigmoidal activation makes it impossible to propagate the exact same value, but this holds in the limit of c -> O. In light of the above discussion, this theorem hints at AMP indeed mitigating oversmoothing, oversquashing, and underreaching by being able to propagate a single message unchanged, which is reminiscent of asynchronous message passing (Faber & Wattenhofer, 2023).
E.
Details
The set of hyper- saper-parameters tried for the baselines and for AMP (except for the number of layers) is the same of Gravina et al. (2023) and Tönshoff et al. (2023a).
In particular, for the baselines and AMP on the synthetic tasks, we used an Adam optimizer with learning rate 0.003, weight decay le - 6, embedding dimension in [10, 20, 30). tanh activation function and a number of layers (except for AMP) in [1, 5, 10, 20).
Instead, results on the peptides-fumt ffnnc dataset rely on the following layers for GCN, GINE and GatedGCN respectively, and similarly embedding dimensions 235, 160 and 95. We use readout with depth of layers, and RWSE positional encodings, a batch size of 200 and 250 maximum training epochs.
learning rate 0.001, dropout 0.1, 10
Finally, results on the peptides-struct rely on similar set of hyper-parameters with the following exceptions: number of layers 6, 10, 8 for GCN, GINE, and GatedGCN respectively, Laplacian positional encodings, and embedding dimensions 235, 145, 100.
Below, we report the additional hyper- peramepprameteer values that we introduced when evaluating AMP.
23

---

Adaptive Message passing
node
node
node
4
3
L
2
3
L
2
3
L
1
1
3
2
2
4
2
4
Adaptive MP (f=1)
Adaptive MP (f=2)
Adaptive MP (4=3)
Figure 8. We sketch the idea of the proof of Theorem 3.2 for graph of 4 nodes. When messages are filtered appropriately, a message can flow between node and node 4 almost unchanged.
Synthetic Datasets To perform the grid search AMP, in addition to the hyper-paramene parameters range used for the base methods (with the exception of the depth), we tested four different distributions g(E; X): a Poisson with initial rate X = 10, an FN with initial parameters μ 10 and a {5, 10}. and a mixture of two folded normal distributions with initial parameters 141 = 5, = 3, //2 = 15, d2 = 3. We fix the prior p(0)) = _e(e;; O, 10 * I), and we choose between three priors p)): an uninformative prior, a Poisson with rate 5, and folded normal with parameters μ = 5 and a = 10. Finally, the message filtering function was chosen between one that does not filter at all, a function f(x)) acting on node features, and function f(hf acting on node embeddings.
Chemical Datasets We tested three different distributions ((;; A): a Poisson with the initial rate À = 5, a folded normal with initial parameters μ = 5 and o = 1, and a mixture of two folded normal distributions with initial parameters 1i = 1, o1 12 = 5, 02 = 1. The tested message filtering functions and the number of layers are the same as the synthetic tasks, whereas p(0)) (0 0, 10x + I) for peptides-func and p(0t) Ao(0;; 0, s I) for peptides-struct. Also, following Tönshoff et al. (2023a), we use dropout in the output layers, after each activation function, and set its value to 0.1.
F. Node Classification Results
To demonstrate AMP''s applicability on a broader range of tasks, we report node classification performances on different datasets with varying degrees of homophily, following the data split strategy of Zhu et al. (2020). We train a GCN by testing the following papre-parameter: embedding size in [8, 32, 64] and number of layers in [2, 4, 6). Adam optimizer with learning rate 0.01, maximum of 2000 training epochs and early stopping with patience 250 the validation performance. The syper-parameter were the same for AMP with the exception for the number of layers, which is replaced by the distributions tried for the chemical datasets.
Table 3 clearly shows that wrapping our framework around a GCN always grants a performance improvement. Only for reference, we report other results taken by (Zhu et al., 2020). However, please note that there an homophillichettrophilli graph does not imply that the task is long-range, nor the converse necessarily true.
G. Analysis of AMP's Predictions
We further delve into the predictions of AMPAMP on few representative cases. In Figure 9 (left), we report the mean predictions of the best performing GCN and AMP runs on the Diameter dataset, where the shaded bands denote the minimal and maximal errors that both models make. Similarly, Figure (right) shows the same plot but for ADGN and AMP ADGN on Eccentricity. We can see how AMP generates an almost ideal average prediction on Diameter and is able to deal with higher eccentricity than the base model (despite an almost identical error being achieved in the latter case).
24

---

Adaptive Message passing
Texas
Wisconsin
Actor
Squirrel
Chameleon
Citeseer 0.74
Pubmed
Cora
Hom. ratio
0.11
0.21
0.22
0.22
0.23
0.8
0.81
#Nodes
183
251
7,600
5,201
2.277
3,327
19,717
2,708
#Edges
295
466
26,752
198,493 5
31,421
4,676
44,327
5,278
#Classes
HGGCN-1
84.8626.77
86.6714.60
35.86= 1.03
36.4211.8
1..1
77.07
89.40=0.34
86.921133
H₂GCN-2
82.1615.28
85.8814.22
35.62=1.90
37.90+2.02
59.39=1.08
76.8821.77
89.59=0.33
81.35
GrE
82.4326.14
81.18
34.23=0.90
+0.74
58.73=1.68
76.0411.30
88.45=0.50
86.90+1.04
GCN-Cheby
77.30++4.07
79.41+-4.46
34.11#1.09
43.86++1.4
55.24=2.76
75.82+1.na
88.72-0.03
86.76+0.95
MixHop
77.8447.78
45.88+4.90
32.22
43.80++.4s
60.50=2.68
76.26+1.a3
85.31=0.61
87.61++086
GraphSAGE+IJ
83.7842.22
81.9611..6
1..28=1001
40.85+1.22 .99
58.
18.11
76.05+1 .37
88.3440.62
85.96=00 63
Ch
78.3846.37
82.55
15.14
1..03+1.73
63.79-2.27
74.98
89.07=0.30
85.49
GCN+JK
66.49+6.64
76.3116648
34.18=0.85
40.45+161
63.42+2.00 1..5
88.41+0.45
85.79=0.92
GAT
58.3844.45
25.29
26.28=1.73
30.62+2.11
5.1.69
75.46+1.72
84.68=0.44
82.68+1.80
GEOM-GCN*
67.57
61.12
31.63
38.14
60.90 77.99
90.05
85.27
MLP
818894475
85.29
35.76=0.8
29.68
46.36=2.52
72.41+2.18
86.65=0.35
7..751
GCN
52. 45.998
44.90
28.02 0.559
27.7310.95
41.89#1.58
72.71+1.54
87.62
$7.62=0.55 0.559
84.2441.44
AMPGGN GGN
81.46+3.06
80.45+4.47
04 35.28+0..0
48.56=1.70
75.07+1.29
89.67
1..68+1.52
Table Node classification results on heterophilic and homophilic graphs. Results are taken from al. (2020).
25
AMPOCN
Predicted diameter
GCN
Predicted eccentricity
20
20
16
10
10
Meal
AMP ADGN
15
25
Target diameter
Target eccentricity
Figure report the average predicted vs target graph diameter and node eccentricities the GCN ADGN message passing architectures, respectively. Shaded hands denote minimal and maximal errors for each prediction.
H. Tuned Depth of Base Models
We report, for the base architectures we have tested within AMP, the number of layers selected by the hyper-paramest search in the original papers. For the synthetic datasets, we obtained this information directly from the authors (Gravina et al., 2023), whereas for the chemical datasets this information already available in Tönshoff et al. (2023a).
I. Impact of Positional and Structural Encodings
For completeness, we investigate the impact of the positional and structural encodings on performances. Our findings show that, on peptides-fune, the performance gain compared to AMP is marginal on GCN and GINE, but it becomes substantial on GatedGCN. In all cases, even without the additional encodings, AMP has better or comparable performance than the base models. We observe similar trend peptides-struct, with AMPGcN suffering the most from the absence of extra information: here, the result is significantly worse than the base model.
J. Ablation Study on the Depth
Performing an ablation study about the depth of AMP implies that we perform model selection across wide range of (fixed) depths and we learn the importance of each layer. This is an a-posteriori analysis, meaning that we the range of layers
25

---

Adaptive Message passing
Diameter SSSP
Eccentricity peptides-func peptides-struc
GCN
5
10
6
GIN
1
ADGN
10
20
20
GINE
8
10
GATEDGCN
10
8
Table Best number of layers selected during hyper- ppeerpparametr tuning for models considered within AMP. These values are taken from the original papers provided by their authors.
Method
peptides- -func Test AP
peptides struct Test MAE, +
W/O PE/SE
0,6860 0.0050
0.2460
0.0007
GINE
0.6621 1 0.0067
0.2473 0.0017
GATEDGCN
0.6765
0.0047
0.2477 = 0.0009
AMPacN
0.7161
0.00417
0.2146
O. 0026
AMParn
0.7065
0.0105
0.2468 = 0.0026
AMPGamGGEN
0.0943
0.0046
0.2480 0.0012
AMPeCe
0.7102 0.0074
0.2524 = 0.0035
AMPOINE
0.6994 0. 0.0098
0.2477 0.0017
0.6725 0.0113 0.2166 0.0008
Table Mean test scores and standard deviation averaged over final runs on the chemical datasets.
to try is suggested by our previous results; the whole point of our contribution that it may be difficult to find the exact range of message-passing layers that the task needs. The goal of this section to understand it is worth fixing the depth after a sensible range of layers has been found by AMP.
We the information from Figure 4 to set up reasonable range of fixed number of message passing layers try, and then the experiments again the real-world chemical datasets. We also fix the other tlyper-parameter to the best configuration found, for each model and dataset, by our model selection procedure.
Method
peptides-fune Tost AP
peptides-struet Teat MAE
AMPSCN 0.7161 0.0047
0.2446 0.0026
AMP
0.7065 + 0.0105
0.2468 = 0.0026
AMPGerarir
0.6943 0.0046
0.2480 + 0.0012
FIXED
AMPocN 0.7076 + 0.0059
0.2497 + 0.0009
AMP
0.0014
AMPexneGCN
0.6750 + 0.0029
0.2493 = 0.0013
Table 6. Mean test scores and standard deviation averaged over 4 final runs on the chemical datasets.
appears that fixing the depth does not allow to obtain better performances than the fully adaptive AMP.
26


Reviews:
[{"review_id": "4iQzYAFIsV", "reviewer": "Reviewer_XraS", "summary": "The authors propose a general framework to tackle certain long-range interaction problems in GNNs, namely (1) oversmoothing, (2) oversquashing, and (3) underreaching. Their Adaptive Message Passing (AMP) framework extends the work of Nazaret and Blei on unbounded depth networks to the GNN setting. The idea is to use a variational theory to learn the GNN structure, both in terms of GNN depth as well as message passing (message filtering). This allows for a finer control on the flow of messages across the graph.", "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 the reviewer for recognizing the merits of our contribution and for providing constructive criticism. Below we comment on some of the points raised by the reviewer.\n\n**Methods And Evaluation Criteria:** Following Reviewer ZB4Z’s suggestion, we will include node classification tasks related to homophily and heterophily and increase the number of real-world datasets considered. Please see our response to Reviewer ZB4Z for a first batch of results.\n\n**Theoretical Claims:** AMP focuses on long-range interactions problems, where far-away nodes may need to communicate effectively (for instance, without oversquashing arising).  Theorem 3.1 shows that, for a proper parametrization, it is possible to realize such long-range communication between two specific nodes without oversquashing behavior, which would not be possible on classical (synchronous) message-passing neural networks. This is meant to support the design choices made for AMP, although we do not want to claim that AMP is always able to implement such behavior in practice (we do not observe it empirically). At the same time, such a behavior is reminiscent of the asynchronous updates of [FW]. We will revise the paper to reflect these considerations, and we hope that this clarifies the reviewer’s doubts.\n\n**Other Strengths And Weaknesses:** Thank you for the kind words about our work. We provide an answer for each potential improvement below.\n\n- It is true that we did not mention additional costs in detail, thank you for pointing this out. The cost of filtering messages is $O(N)$, with $N$ nodes (lines 184-185). Therefore, the message passing operation is not altered significantly, since it has a cost of $O(N+E)$, with $E$ edges. However, the additional burden introduced by AMP, compared to classical MPNNs, is the layer-wise readout (lines 344-345) that we implemented as an MLP. Classical MPNNs employ a single readout with cost $O(N)$ or $O(1)$ depending on the task nature, whereas we use one per layer, so we have $O(NL)$ and $O(L)$ respectively. Note that other popular MPNN architectures, such as JK-Net (Xu et al., 2018), employ a similar scheme by means of concatenating the node embeddings across all layers. In terms of training costs, standard backpropagation with at most two light-weight additional regularizers is employed. We will make this clear in the revised version of the paper.\n- Please refer to our additional experiments in Reviewer ZB4Z’s response, as mentioned before. \n\n--------\n**Conclusion:** Thank you once more for the constructive feedback! We hope our clarifications and additional experiments may constitute ground for a score improvement. We remain available for further discussions.", "claims_and_evidence": "Yes, the claims are supported by clear and convincing evidence. For oversmoothing/oversquashing, the authors use standard tools such as Dirichlet energy to examine the quality of the embeddings. They also provide ablation studies to examine the effects of message filtering.", "methods_and_evaluation_criteria": "Yes, the proposed methods and criteria are overall justified. The number of real-world datasets considered could be larger, since the paper targets a very broad array of GNN limitations.", "theoretical_claims": "I did not check for all theoretical details: Some of the background needed is out of my knowledge scope. \n\nI am also not sure how Theorem 3.1 supports the overal theory: What does it even mean to propagate a message unchanged from two connected nodes in a graph? Why is that important? And does this really show that a GNN can learn \"asynchronously\", as alluded by the citation [FW]? Is this case observed experimentally?", "experimental_designs_or_analyses": "Yes, the experimental protocols are fairly thorough, in line with recent hyperparameters consideration for long range benchmarks [Tonshoff et al.]", "relation_to_broader_scientific_literature": "The paper forms an important contribution in the current research to mitigate oversmoothing/oversquashing/underreaching. The paper brings in novel tools from learning unbounded depth NNs to address these problems simultaneously.", "essential_references_not_discussed": "No, as far as I know,.", "other_strengths_and_weaknesses": "Strengths\n1) The paper employs a very well-motivated theory-driven approach to tackle the target problems. The proposed solution is novel and effective, with potential for further research. \n\nWeakness\n1) One key advantage of blanket Message-Passing is scalability. The authors have not commented clearly on the exact computational costs of the setting up AMP on top of a GNN. \n2) The number of real-world datasets considered is fairly small, as compared to usual GNN literature.", "other_comments_or_suggestions": "-", "questions_for_authors": "-", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2u54y4B3pi", "reviewer": "Reviewer_wzem", "summary": "Graph Neural Networks (GNNs) often struggle to capture long-range dependencies in graphs due to challenges such as oversmoothing, oversquashing, and underreaching. In this work, the authors introduce a variational inference framework that allows GNNs to dynamically adapt their depth and selectively filter message passing. The proposed approach is supported by theoretical insights and empirically validated on multiple graph benchmarks.", "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 the reviewer for the comments. Below, we clarify some of the points raised.\n\n**Claims And Evidence:** We apologize for the incorrect statement in the abstract about “surpassing” the state of the art. That statement was true in the past, before we revised Table 2. Indeed, we had fixed our claims elsewhere in the paper (lines 80-83, 242-244, 377-379) by talking about “competitive” performances.\n\n\nHowever, the goal of the analysis is not to show absolute improvements compared to recent works. Rather, it is to show, as the reviewer correctly identified, that wrapping the AMP framework around basic MPNNs grants a performance improvement in capturing long-range dependencies, due to the particular characteristics of AMP that endow MPNNs to mitigate oversmoothing and oversquashing as measured in Figure 3, in addition to the adaptive learning of the depth to mitigate underreaching.\nIt is our belief that our work should be judged in terms of these contributions, and not solely in terms of absolute numbers, since we, for the ease of prototyping, chose to wrap AMP around classical MPNNs, rather than more recent and convoluted ones.\n\nIn terms of mitigating under-reaching, it is possible that the network finds a degenerate solution during training that corresponds to an unsatisfactory depth, but this is similar to how MLPs can end up in poor local minima when trying to learn functions. The design of AMP enables learning the depth and we see that it works empirically. \n\nFinally, in our results, it seems the method learns more layers than those tried in previous works using grid search.\n\n**Experimental Designs Or Analyses:** Thanks for pointing this out, we partly referred to the hyper-parameter ranges and data splits of Gravina et al. and Tonshoff et al. without explicitly mentioning them in the paper. To improve self-containment and reproducibility, we will add this information to Appendix E. The search methodology was a standard grid search with early stopping on validation performance.\n\n\n**Relation To Broader Scientific Literature:** We would like to clarify that our approach does not pertain to probabilistic graph rewiring approaches; it is probabilistic, but it does not perform a topological rewiring of the graph. The graph topology remains the same, and messages are partially filtered to mitigate the oversmoothing and oversquashing issues. Concretely, we never add new edges to the input graph: please also refer to our answer to question 1 below.\n\n**Essential References Not Discussed:** Thank you for providing these additional references, we agree with the reviewer’s analysis and we will include and discuss them in the revised manuscript. Briefly, in terms of main differences with AMP, [3] relies on a separate sequence model to develop a node selection mechanism whereas we work on the message passing itself; [4] develops a new graph Laplacian that is better suited for long-range propagation; [5] converts a graph into a latent representation that can be passed to downstream classifiers.\n\n**Questions For Authors:** \n1. As we also clarified earlier, our approach differs significantly from rewiring approaches, including probabilistic ones. In AMP, the probabilistic formulation is used to dynamically learn the depth (following Nazaret and Blei), something which rewiring approaches cannot do, whereas the “filtering of messages” is not to be intended as a variation to the original graph topology, rather as a “node-based” filtering of outgoing messages. The major difference is that AMP alters the computational graph but not the graph topology, whereas typical graph rewiring methods alter the graph topology. In Appendix D, we have discussed this through the lens of  oversquashing.\n2. Modeling a one-dimensional distribution leads to no particular overhead during training. We point the reviewer to our answer to Reviewer XraS for a discussion on computational complexity. In short, the main complexity is caused by the addition of one readout per layer, something which was also done in previous works such as JK-Net (Xu et al, 2018). In terms of training, optimizing the ELBO reduces to performing backpropagation w.r.t. a standard prediction loss, plus one (optional) weight regularization term and another (optional) depth regularization term. The overall asymptotic complexity is therefore not different from other GNNs that appeared in the literature in previous years.\n\n---------\n**Conclusion:** We hope to have clarified the goal of our contribution and to have addressed the other questions. We would appreciate it if the reviewer could consider increasing the score in light of these considerations and revisions. We remain available should further information be needed.", "claims_and_evidence": "The claims made in the paper are partially supported by experimental evidence. The results presented in Tables 1 and 2, as well as the synthetic tasks, demonstrate performance improvements when the authors’ approach is integrated with popular GNN variants. On the other hand, the method does not surpass the state-of-the-art (as claimed) in Table 2. It's also not clear how underreaching can be mitigated when messages are filtered which could rather introduce underreaching as the propagation of information is thereby prevented.", "methods_and_evaluation_criteria": "The proposed probabilistic message passing framework is well-motivated for the graph-processing methodology, with a clear intuitive rationale for its potential to enhance performance. The selection of benchmark datasets and evaluation metrics is appropriate and aligns with standard practices in assessing graph-based methods.", "theoretical_claims": "The proof of Theorem 3.1 is intuitive and straight-forward.", "experimental_designs_or_analyses": "The experimental setup appears to be well-structured for evaluating the stated claims. I could not find a detailed description of the hyperparameter selection process, including dataset splits, search methodology, and search grid specification for all tasks and methods, however.", "relation_to_broader_scientific_literature": "The primary contributions of this paper pertain to probabilistic approaches to graph rewiring [1,2] and established GNN methods, which are utilized as baselines for comparison.\n[1] Qian et al. Probabilistically rewired message-passing neural networks, 2024\n[2] Qian et al. Probabilistic graph rewiring via virtual nodes, 2024", "essential_references_not_discussed": "To enhance the comprehensiveness of the study, it would be beneficial to discuss related approaches or incorporate them as baseline methods for comparison. For instance, [3] introduced Graph-Mamba, an adapted state-space model designed to facilitate long-range information propagation in graph data. Similarly, theoretically grounded sequence-processing frameworks [4,5], leveraging randomized signatures from rough path theory, demonstrated promising potential in alleviating oversquashing effects in large graphs.\n\n[3] Wang et al. Graph-Mamba: Towards Long-Range Graph Sequence Modeling with Selective State Spaces, 2024\n\n[4] Toth et al. Capturing Graphs with Hypo-Elliptic Diffusions, 2022\n\n[5] Gruber et al. Processing large-scale graphs with G-Signatures, 2024", "other_strengths_and_weaknesses": "None", "other_comments_or_suggestions": "None", "questions_for_authors": "1. At first glance, [1,2] seem to be conceptually very similar to the approach in this paper. Could the authors emphasize the major differences/novelties compared to these approaches?\n2. How expensive is the whole probabilistic modeling process? The modeled distribution has to account for layers, parameters and graphs at the same time, how does the computational complexity compare to GNN variants that do not have to model these components?\n3. Since a distribution has to be modeled, is there a trade-off in case of scarce high-dimensional data where distribution-modeling is hard?", "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": "rCneglEWlU", "reviewer": "Reviewer_ZB4Z", "summary": "This paper introduces Adaptive Message Passing (AMP) a novel approach to enrich GNNs with learnable depth and message filtering distributions. A variational inference framework is adopted to jointly train netwoks representing these distributions with both mechanisms being aplied to a range of existing GNN baselines as wrapper style enhancments. The paper also \"introduce new families of distributions with specific properties to overcome previous limitations\" in order to facilitate the variational framework which are outlined in the appendix. The main aim of the work is to dynamically learn these distributions such that models overcome oversquashing, under-reaching, oversmoothing (OUO). To demonstrate the effectiveness of this approach AMP is tested on 2 datasets that represent tasks with long-range dependancies. An analysis of the depth and filtering distributions shows the distributions dynamically adapt for the task and various baseline GNNs.", "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 sincerely thank the reviewer for the detailed review and the valuable suggestions. We will do our best to clarify doubts and address the points of the reviewer.\n\n**Claims And Evidence:**\n\n*On Figure 3:* We will improve the coloring scheme as suggested, thank you. Also, the reason why we do not show GCN results for more layers is because we report the best configuration on the validation set, but we can mention in the paper that it has been already proven how GCNs oversmooth in the long run. Finally, the Dirichlet Energy (DE) becomes negative simply because the y-axis is in log scale to aid readability, as DE values and sensitivities vary a lot.\n\n*Theoretical Analysis:* We cannot thank the reviewer enough for the suggestion! We indeed extended Theorem 3.2 of Di Giovanni ‘23 to our message filtering scheme, and (in short) we arrived at the conclusion that, if $c_F$ is the Lipschitz constant of our filtering function, $k_F \\le 1$ is the maximal element-wise value attained by the Filtering function $F$, and $k_h$ is the maximal element-wise value of a node embedding, we arrive at a similar result for (using the notation of Theorem 3.2)\n\n$\\boldsymbol{S}_{r,a} := c_r\\boldsymbol{I} + c_a(c_F*k_h + k_F)\\boldsymbol{A}$\n\nWhere $\\boldsymbol{S}_{r,a}$ controls the upper bound on sensitivity due to the topology of the graph.\nWe are very happy with the Reviewer’s suggestion because this result formally supports what we argued in Appendix D: if we consider for simplicity a constant filtering function, namely $c_F=0$ and we filter enough, meaning $k_F < 1$, then filtering will decrease the sensitivity’s upper bound. However, this is actually helping to reduce the “informational oversquashing” defined in Alon et al., contradicting the widely used statements that “improving sensitivity mitigates oversquashing”. As a result, we argue that the community should probably distinguish the “informational oversquashing” of Alon et al. from the “topological oversquashing” of Topping et al..\nWe will add these results to our paper. Thank you so much for the invaluable suggestion! This will help our community reason more clearly about these issues.\n\n**Methods And Evaluation Criteria:** Following the reviewer’s suggestion, we perform additional experiments with GCN and AMP_GCN on homophilic and heterophilic datasets. Risk assessment is performed using 10-fold Cross Validation, with an internal hold-out hyper-parameter tuning for both models. For each of the 10 folds, the best configuration on that fold is re-trained 10 times and the test values averaged. The final test score is the average of the test scores across the 10 folds. This procedure is inspired from [*] and results are shown below.\n\n|     \t| Cora   \t| Citeseer   | Pubmed  \t| Texas  \t| Wisconsin  | Chameleon  | Squirrel   | Actor  \t|\n|---------|------------|------------|-------------|------------|------------|------------|------------|------------|\n| GCN \t| 85.1 (2.0) | 72.3 (1.9) | 87.9 (0.9)  | 51.9 (8.1) | 45.9 (4.1) | 43.4 (1.5) | 27.6 (1.1) | 28.5 (0.7) |\n| AMP_GCN | 86.5 (1.7) | 75.3 (2.2) | 89.8 (0.5)  | 78.6 (7.0) | 81.3 (7.1) | 49.8 (2.2) | 35.2 (1.8) | 34.8 (1.2) |\n\nIt appears that AMP allows GCN to improve results especially on heterophilic datasets. Therefore results seem to align with the reviewer’s intuition. We will add other common datasets and baselines in the revised version of the paper. Thank you for suggesting these extra experiments.\n\n[*] Errica F., Podda M., Bacciu D., Micheli M., A fair comparison of graph neural networks on graph classification. ICLR 2020\n\n**Essential References Not Discussed:** Thanks for pointing out that some references in the Table are not cited, we will amend that.\n\n**Remaining Sections:** We hope to have addressed the weaknesses highlighted by the reviewer, namely the theoretical analysis and the extra experiments on node classification tasks on homo/heterophilic datasets. We will provide a complete proof of the extended version of Theorem 3.2 for AMP in the revised paper.\n\n**Questions For Authors:** As a matter of fact, the entire architecture is trained using conventional backprop on a prediction loss + some regularization terms. There is no MLP involved in the distribution of the layers’ importance because we simply need to learn its parameters, but note that the variational formulation merely serves to show that AMP arises from a well defined graphical model, grounding our design choices in a principled formulation. The practical implementation is very simple, thanks to the brilliant work of Nazaret and Blei. Please let us know if we can further clarify this point.\n\n----------\n**Conclusion:** Thank you again for the constructive comments, especially those related to the theoretical analysis. We hope the Reviewer appreciates our efforts and that this will lead to a score increase.", "claims_and_evidence": "The paper claims to \"provide(s) a general framework for improving the ability of any message passing architecture to capture longrange dependencies\" which is emperically shown on the selected datasets.\n\nIt also claims the framework \"mitigates\" OUO which is somewhat supported with the analysis in Figure 3, however I would say this coud be improved with a more consistent colouring scheme for GCN vs AMP_GCN for each task. It might also be more informative to standard GCN DE decay for a larger number layers. It also also unclear why the Dirichlet becomes negative.\n\nThere is an extensive discussion on OUO in Section App.D with some conjecture but I think the paper is missing a theoretical analysis in the style of the cited papers (more \"suggested\" below).\n\nOne step in this direction Theorem 3.1 but in my opinion the property shown in theorem 3.1 \"AMP’s ability to propagate a message unchanged from two connected nodes\" is potentially trivial and not useful in the learning setting. It just shows the existence by construction of a message passing scheme for one graph sample between 2 nodes essentially choosing the nessary weights to maintain the feature vector within the ball.", "methods_and_evaluation_criteria": "As the paper claims to introduce a framework to overcome OUO on tasks requiring long distance information propagation I would say the chosen datasets fit the task. However this might indicate bias selecting datasets for which the framework has been designed to perform well in. I would like to see experiments performed on classical homophilic and heterophilic node classification tasks (ie Cora/Texas) to show the scheme is universal.", "theoretical_claims": "As above the proof of Theorem 3.1 seems correct but the property seems unuseable in practice and relies on construction.\nTo demonstrate mitigation of OUO it would be better to focus on a gradient based analysis as I suggest below.", "experimental_designs_or_analyses": "Experiments and abalations are suitable and exectued well but see my comments above.", "relation_to_broader_scientific_literature": "Due to the extensive literature review the paper does a good job in positioning itself within the current literature wrt adjustable depth, rewiring and adaptive architectures pointing out here the architeture can be adaptively learned during trainined due to the variational formulation.", "essential_references_not_discussed": "I am satisfied a comprehensive literature review of related works has been performed. I would note some benchmarks in Table 1 are not cited.", "other_strengths_and_weaknesses": "I am borderline accept given the novel approach to overcoming the common problems of OUO and promising results and informative emperical analysis. However there are two weaknesses I believe if addressed could significantly strengthen the paper. A proper theoretical analysis of the message passing scheme (as suggested below) and performing exerpiments on classical homophilic and heterophilic node classification tasks (ie Cora/Texas) to show the scheme is universal. It migh be impressive to show where the framework learns whether long or short range information is relevant or useful. One might assume short/long distance for homo/heterophily respectively", "other_comments_or_suggestions": "I think the paper is missing a proper analysis that the framework overcomes oversmoothing. One suggestion might be to look at the proof of Theorem B.1 in \"On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology\" (Di Giovanni '23) and split the message passing matrix, isolating the \"relevant\" signal, as done in proof 3.1 being able to show the sigmoid gating sharpens the signal on relevent pathways wrt to the node sensitivity might be a way to proceed. In addition It might also be benefical to remove the standard symetric degree normalisation of GCN with \"sum of sigmoid\" based normalisation which would further sharpen the signal.", "questions_for_authors": "It's unclear to me why the MLPs to output the weights over the layer depths and sigmoid MLP for message filtering can't just be trained using conventional methods?", "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": "TIuk4DAIvN", "reviewer": "Reviewer_8uEx", "summary": "This work addresses the challenge of modeling long-range interactions in deep graph networks, which are often hindered by oversmoothing, oversquashing, and underreaching in message passing. The authors propose a variational inference framework that adaptively adjusts message depth and filters information to mitigate these limitations. The approach is theoretically and empirically validated, demonstrating superior performance on five node and graph prediction datasets. This method enhances the ability of deep graph networks to capture long-range dependencies without explicitly modeling interactions.", "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 the reviewer for recognizing that the paper is well written and the findings are convincing. We will comment below on the questions raised.\n\n**Other Strengths And Weaknesses:** \n\n1. While oversmoothing, oversquashing, and underreaching are topics of great interest in the community, which are far from being fully understood or solved, our paper’s unique motivation is that, by combining the ability to learn the depth with the adaptive filtering of messages, we want to determine *i)* the number of required layers and *ii)* which messages should be propagated. In other words, our contribution is unique in that it determines, *during training*, *how much and when* to send information. We hope to have clarified this point.\n2. In Appendix D, we provide a critical view on how the oversquashing term is defined and understood by our community. In particular, we argue that if oversquashing refers to “informational bottlenecks”, then additive rewiring may hurt performances if the same amount of layers is kept; in contrast, oversquashing defined as sensitivity is always improved by additive rewiring. For this reason, we believe that AMP and rewiring-based approaches are different but equally valid approaches to achieve long-range propagation. We will clarify these aspects in the paper, and we hope the reviewer appreciates our considerations. Thanks to the suggestion of Reviewer ZB4Z, we now have a new Theorem inspired by Di Giovanni et al, 2023 that exposes this inconsistency in the literature!\n3. In terms of impact of the depth as regards efficiency, we refer to the computational complexity analysis written in Reviewer XraS’s response. We will add these considerations to the paper. Overall, the complexity of using a deeper network increases due to i) the higher parametrization, as usual; ii) the need for a layer-wise readout in AMP, as also done in previous works [JK-Net, Xu et al., 2018]. \n\nIn addition, we prepared an ablation study where we try different (fixed) depths for AMP, maintaining the other architectural changes intact. In particular, we allow AMP to learn a normalized importance over the fixed number of layers. Here, we want to see the impact of dynamically learning the depth on effectiveness. The depths we tried depend on the range shown in Figure 4 (so, up to 45 different depths for a single model and dataset), while the other hyper-parameters were fixed to the best one we found for the task. The table is shown below for the peptides datasets:\n\n| | Func | Struct |\n|-------------|-----------|--------|\n| AMP_GCN  \t| 0.7076  (0.0059) | 0.2497 (0.0009) |  \n| AMP_GINE \t| 0.6999  (0.0041) | 0.2481 (0.0014) |\n| AMP_GATEDGCN | 0.6750 (0.0029) | 0.2493  (0.0013) | \n\nIt appears that learning the importance of fixed-depth network layers does not allow to obtain better performances than the fully adaptive AMP, and it potentially requires many more configurations to be tried, which is the main disadvantage of considering the depth as a hyper-parameter rather than a learnable parameter (as we do).\n\n**Questions For Authors:**\nThe specific tasks are chosen because there is reason to believe long-range information plays an important role. In other words, all our tasks require the ability to “reason” globally about the graph and have specifically tested for these reasons. In addition, we used the molecular tasks of the LRGB paper because i) it is possible to perform a fair evaluation on these tasks, thanks to the robust re-evaluation of Tönshoff et al.. IPR-MPNN evaluation on additional benchmarks is necessary to empirically validate their increased expressive power compared to 1-WL MPNNs, whereas we believe to already have sufficient empirical evidence that AMP can be beneficial to improve the performance of MPNNs on long-range tasks; AMP always improves the results compared to any of its base versions on all datasets.\n\n**An important clarification about AMP’s competitiveness:** our goal is *not* to demonstrate that AMP surpasses the state of the art, as AMP **is not a model but a framework** that can be wrapped around most MPNNs. In our paper, we used simple MPNNs for their ease of use, showing the performance gains that AMP grants without changing a single line of code of these convolutional layers. In our view, the correct metric to assess AMP’s effectiveness is the gap in performance compared to the base versions AMP is wrapped around, showing that it helps to better capture long-range dependencies.\n\n\nFinally, thank you for the reference, we will include it in the revised manuscript. We were unable to find such models for the considered datasets, but we should definitely mention architectures specific to molecular tasks in our work, as it is relevant due to the electrostatics interactions necessary to model energy and forces.\n\n--------\n**Conclusion:** We will report these clarifications and additional statements in the paper. We hope the reviewer appreciates our response and hopefully will increase the score.", "claims_and_evidence": "The content has already been provided in the subsequent subsections.", "methods_and_evaluation_criteria": "The content has already been provided in the subsequent subsections.", "theoretical_claims": "The content has already been provided in the subsequent subsections.", "experimental_designs_or_analyses": "The content has already been provided in the subsequent subsections.", "relation_to_broader_scientific_literature": "The content has already been provided in the subsequent subsections.", "essential_references_not_discussed": "The content has already been provided in the subsequent subsections.", "other_strengths_and_weaknesses": "Advantages:\n1. The paper is well-written, clear, and easy to read.  \n2. The experiments are thorough and directly correspond to the target problems introduced, making the findings highly convincing.  \n3. The paper extends variational methods from neural architecture search to GNNs and provides detailed theoretical proofs.  \n4. The authors have released the source code, data, and configuration files, ensuring high credibility and reproducibility.  \n\nWeaknesses:\n1. The introduction focuses heavily on the limitations of standard GNNs, but issues like oversmoothing, oversquashing, and underreaching have already been extensively studied. Given the comparative experiments provided, what is the paper’s unique motivation in this context?  \n2. Based on Table 2, AMP's performance is comparable to IPR-MPNN, with the key difference being whether rewiring is used. Has the paper clearly explained the advantage of ‘not requiring rewiring’?  \n3. Has the impact of AMP’s dynamic depth on efficiency been sufficiently evaluated in the results section? Similarly, how does its efficiency and complexity compare with other methods? For instance, if AMP tends to choose deeper networks for certain tasks, does this lead to a significant drop in overall efficiency?", "other_comments_or_suggestions": "The content has already been provided in the subsequent subsections.", "questions_for_authors": "1. Could the authors clarify the rationale behind selecting these specific tasks as benchmark objectives? Given that they differ from the benchmarks used for comparison with baselines like IPR-MPNN, I have concerns about the representativeness and competitiveness of these tasks in evaluating the proposed method.  \n\n2. Have the authors considered including domain-specific models designed to handle long-range interactions as additional baselines? While I am not certain whether such methods exist for all tasks in this paper (e.g., peptide property prediction), there has been extensive research in machine learning force fields addressing similar challenges. One relevant example is:  \n\n[1] Li Y, Wang Y, Huang L, et al. *Long-short-range message-passing: A physics-informed framework to capture non-local interaction for scalable molecular dynamics simulation*. arXiv preprint arXiv:2304.13542, 2023.", "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: The reviewers unanimously recommend acceptance of the paper with varying degrees of strength. I agree with their assessment and am happy to recommend acceptance of this paper for publication at the ICML conference. 

The reviews and the rebuttal have given rise to several interesting points and results that I encourage the authors to include in their revised manuscript. This includes the additional empirical results on further datasets, in my point of view, results on even more datasets would significantly help strengthen your paper. I furthermore encourage the inclusion of the analysis of the computational cost of your method, a more detailed reporting of hyperparameter ranges and datasplits, as well as the additional theoretical results that you derived with Reviewer ZB4Z.
Decision: Accept (poster)