Deeper with Riemannian Geometry: Overcoming Oversmoothing and Oversquashing for Graph Foundation Models
Authors: Li Sun
Zhenhao Huang
Ming Zhang
Philip S. Yu
Venue: NeurIPS 2025 poster ()
Keywords: MPNN
Oversmoothing
Oversquashing
Riemannian geometry
Graph Foundation Models
Primary area: deep_learning
TL;DR: We create a new  MPNN with Boundary Conditions of Riemannian Dynamics to combat oversquashing, while allowing for MPNN going deeper.

Abstract: Message Passing Neural Networks (MPNNs) are the building block of graph foundation models, but fundamentally suffer from oversmoothing and oversquashing. There has recently been a surge of interest in fixing both issues. Existing efforts primarily adopt global approaches, which may be beneficial in some regions but detrimental in others, ultimately leading to the suboptimal expressiveness. In this paper, we begin by revisiting oversquashing through a global measure -- spectral gap $\lambda$ -- and prove that the increase of $\lambda$ leads to gradient vanishing with respect to the input features, thereby undermining the effectiveness of message passing. Motivated by such theoretical insights, we propose a local approach that adaptively adjusts message passing based on local structures. To achieve this, we connect local Riemannian geometry with MPNNs, and establish a novel nonhomogeneous boundary condition to address both oversquashing and oversmoothing. Building on the Robin condition, we design a GBN network with local bottleneck adjustment, coupled with theoretical guarantees. Extensive experiments on homophilic and heterophilic graphs show the expressiveness of GBN. Furthermore, GBN does not exhibit performance degradation even when the network depth exceeds $256$ layers.

Deeper with Riemannian Geometry: Overcoming Oversmoothing and Oversquashing for Graph Foundation Models
Li Sun"
Zhenhao Huang
Beijing University of Posts and Telecommunication Beijing 100876, China
North China Electric Power University Beijing 102206, China
Isun@bupt.c edu. en
huangzhenha www.heeennnnnccc....ooooo edu. cn
Ming Zhang
Philip S. Yu
North China Electric Power University Beijing 102206, China
University of Illinois Chicago
IL 60607, USA
zhangming@ncepu.c edw.. edu. cn
psyušuic. edu
Abstract
Message Passing Neural Networks (MPNNs) the building block of graph foun- dation models, but fundamentally suffer from oversmoothing and oversquashing There has recently been surge of interest in fixing both issues. Existing efforts primarily adopt global approaches, which may be beneficial in some regions but detrimental in others, ultimately leading the suboptimal expressiveness. In this paper, we begin by revisiting oversquashing through a global measure spectral gap and prove that the increase of À leads gradient vanishing with respect to the input features, thereby undermining the effectiveness of message passing. Motivated by such theoretical insights, propose local approach that adaptively adjusts message passing based on local structures. To achieve this, we connect local Riemannian geometry with MPNNs, and establish a novel nonhomogeneous boundary condition to address both oversquashing and oversmoothing. Building on the Robin condition, we design a GBN network with local bottleneck adjustment, coupled with theoretical guarantees. Extensive experiments heterophilic graphs show the expressiveness of GBN. Furthermore, GBN does not exhibit performance degradation even when the network depth exceeds 256 layers.
homophilic and
Introduction
Recently, graph foundation models have attracted growing research interests 77] 61 offering the pre-trainable and general-purpose deep architectures based on Dassage-Passing Neural Network (MPNN). Against this backdrop, we revisit the fundamental issues of the core building block MPNN itself: Oversmoothing [35] 40), which prevents MPNN from going deeper as other typical neural architectures, and Oversquashing [4], which refers the difficulty in propagating information from distant nodes and capturing the Long-range dependencies.
In the literature, there has recently been surge of interest in jointly addressing oversquashing and oversmoothing. The former is caused by the topological "bottlenecks" in the graph structure [64], while the latter can also be related to the structure [1] Accordingly, primary solution is graph
rewriting, which conducts the structural refinement guided by Ricci curvature (3 38
20 or spectral
"Corresponding Author: Li Sun, Isun @ bupt.edu.cn
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

MPNN
BORF
Graph Rewritin
Boundary Condition
Figure Illustration of different solutions against oversquashing. (A) typical MPNNs, messages are "squashed" at the bottleneck of the graph structure. (B) In graph rewriting (e.g.. BORF (39)). oversquashing at the bottleneck mitigated by adding edges, but the removal of edges (in light of oversmoothing) hinders the message- passing in other regions. (C) In the proposed GBN, an adaptive adjustment based on the local Riemannian geometry is introduced to message passing in each region enhance expressiveness.
The underlying rationale lies in the global metric of spectral gap (i.c., the first non-zero eigenvalue of graph Laplacian A), which controls the size of the bottleneck [6] On the one hand, graph rewriting introduces significant computational overhead. On the other hand, it undergoes carefully designed edge Buding-deletinng procedure 2 altering the original graph structure. So far, existing efforts, including the recent advance [27]. adopt the global approach to fix MPNNs.
analysis [4].
In this paper, begin by rethinking a significant question: is it necessary increase the spectral gap À through a global approach? Intuitively, global approach may benefit some regions but be detrimental others. Theoretically, larger À accelerates the oversmoothing process, measured by Dirichlet energy [35] 40). Regarding oversquashing, we develop unified interpretation of typical MPNNs as neural solvers of the heat equation on Riemannian manifold, which reveals the negative impact of increasing À through the eigenvalue decomposition of Riemannian heat kernel. Specifically, increasing tends cause gradient vanishing (Theorem 4.2 thereby limiting the model expressiveness.
Motivated by the theoretical insights above, aim address both issues of MPNN through local approach. Instead of the structural refinement, we focus on refining the message passing paradigm, and the key innovation lies in the local bottleneck adjustment according the subgraph structure. To achieve this, we explore the functional space over subgraphs through its continuous counterpart - the local Riemannian geometry over submanifolds. Concretely, we establish novel nonhomogeneous boundary condition that is rigorously proven to mitigate both oversquashing and oversmoothing, thereby allowing for MPNNs to go deeper. Consequently, we design a simple yet effective Graph Boundary conditioned message passing Neural network (GBN) to implement the solver subject to the nonhomogeneous boundary condition. GBN unifies the updating rules for boundary and interior nodes with satisfactory scalability, accompanied with the favorable theoretical guarantees.
Contributions. In summary, our key contributions are three-fold: Insight. On oversquashing, we reveal a limitation of the global approach via the spectral gap, motivating a local approach where message passing is adaptively adjusted at each node. B. Theory. We introduce the concept of Riemannian boundary condition to address oversquashing - to the best of our knowledge, for the first time and establish nonhomogeneous boundary condition that also enables deeper MPNNs. C. Methodology. Grounded in the Robin condition, we propose a MPNN named GBN with theoretical guarantees. Extensive experiments on both homophilic and heterophilic graphs demonstrate the expressive power of GBN.
2 Related Work
Oversmoothing. Previous solutions mitigate oversmoothing can be roughly categorized into
four groups: ① Residual connections 772 36 74
particularly initial residual connections [13] 3 and
Graph rewriting methods typically add edges to enlarge bottlenecks, while removing some dense connections in light of oversmoothing.

---

② Normalization layers [25] 78 79 mitigate oversmoothing through the lens of gradient vanishing. Recently, 47 demystifies how they affect the expressive power of MPNNs, while B develops
principled explanation via gradient vanishing, and bridges MPNNs and recurrent networks. 3 Gating mechanism 8 75: 76 46 modulates gradient updates in the layers, and allows for different rates of
message passing. 4 Graph sparsification [ 44 combats this issue from the structural perspective,
given that some subgraphs, such as cliques, increase the risk of oversmoothing [39]. A theoretical
review is provided in [3I] ( (32] presents novel idea to transform the global spectral distribution in each layer of MPNN, while we focus on local adjustment of MPNN via boundary conditions. Different from designing additional modules or structural refinement, focus refining MPNN
mechanism, not susceptible to oversmoothing.
Oversquashing. ① It strongly depends on the graph structure, and thus a natural solution is graph rewriting, which typically adds edges to enlarge the topological bottlenecks, guided by Ricci curvature 164 18) or spectral analysis [30]. Also, graph transformers can be regarded as their generic form
with learnable attentional weights 770 21 44]. 77] understands graph rewriting from the lens of
effective resistance. Recently, it has been shown that incorporating virtual nodes is effective 45 50).
23 provides the theoretical aspects of oversquashing on depth, width, and topology of graphs.
Recent studies jointly address oversmoothing via global treatments. In the line of graph rewriting.
39
38 20 introduce edge -iiltiionneeeiionn algorithms in light of oversmoothing: (2 increases
the spectral gap via edge deletion; 44] conducts the feature rewriting with Delaunay triangulation. Recently, [27] considers the polynomial bases for the graph Fourier transform, while [4] designs an
auxiliary module to prevent heterophily mixing. To combat over-squashing. [16] presents novel
approach to select nodes with high centrality to expand in width to encapsulate the growing influx of signals from distant nodes. In contrast to the previous global treatments, introduce the local adjustment to peessage-passingg paradigm with nonhomogeneous boundary conditions.
Riemannian Geometry & MPNNs.
Riemannian geometry has been introduced to learning on
graphs, e.g., node clustering 55
57
55
node classification [53] 59 60 22 structural learning
[54], modeling dynamics 56
52
51
62
and generative models [14 69 63 and shown potential
to graph foundation models 161] In this context, efforts are made to extend Euclidean MPNNs to
geodesically complete manifolds, (e.g.. hyperbolic spaces (37 10 51), stereographic models (5),
product spaces [53] and pseudo Riemannian manifolds [34 7 71). D. seeking embeddings from graphs
to specific manifolds. Recently, the discrete versions of Ricei curvature, the concept describing
the structural connectivity [65), have been introduced to address oversmoothing and oversquashing
[3 38 20 64]. In contrast, we consider the functional spaces over Riemannian manifold.
3
Preliminaries
We review the heat flow on Riemannian manifold, the foundation of our analysis, and describe the oversquashing and oversmoothing in MPNNs. The notation table is provided at Appendix [A]
Riemannian Manifold & Heat Flow. In Riemannian geometry. a graph is regarded as the discrete analogy to certain Riemannian manifold (65). gM,g) denotes a n-dimennsinal manifold endowed with the Riemannian metric gf The volume form is written as vol. = /Idet gldx* A ... A dx". where E R" denotes local coordinates and x is the element of æ. A Hilbert (function) space (M) = {f E (MM) ʃm ff vol.} consists of smooth L integrable functions on M. Let A = div (grad f) be the Laplace-Beltrami Beltrami operator on M w.r.t. g. Ag on closed manifold has discrete eigenvalues and its eigenfunctions &p form basis of (2MM). A homogeneous heat flow on M is described as the following differential equation
0, x)) = (t)((, 1>0
with the initial condition u(O0, x) = o(x) at
0. The solution is induced by the heat kernel H(t, x. y) M M + R so that ult, x) = م f = SM H(t, x. f vV)
MPNN, Oversquashing & Oversmoothing. Let G (V, E) be an undirected and unweighted graph on the node set V and edge set & V x V. The nodes are associated with a feature matrix
Throughout this paper, the terminology of manifold M refers to a closed Riemannian manifold (compact and without boundary) unless otherwise specified.
3

---

X E I RNdd, where = N is the number of nodes, and d denotes the dimension of input features. The structural information is encoded in a binary adjacency matrix and. accordingly, the normalized Laplacian of G is written as L = I D-D AD 2 where D the diagonal degree matrix, Message Passing Neural Network (MPNN) recursively conducts neighborhood aggregation by K layers, and node representation of the k-th layer is updated with the following function,
x sp (k) (x Agg( (a=!-1) (u, v) E))).
(fa!
(2)
for k = f1,..... }). where Agg is a permutation invariant aggregation function, and (8) denotes the update function. MPNNs suffer from Oversquashing [ [4], the compression of messages from exponentially expanding receptive fields into fixed-size vectors. It is typically characterized by the Jacobian |åx.")) /0x; I]. and the exponential decay of derivative with respect to the hop distance implies the occurrence of oversquashing. Oversmoothing [35 [0] refers to the phenomenon that node representations become indistinguishable to each other exponentially as the number of layers increases. In this paper, aim to address both issues of MPNN through a novel local approach that leverages the local Riemannian geometry.
4 Theoretical Insights on Oversquashing
We first develop unified interpretation of MPNNs from the lens of Riemannian geometry. Then, regarding oversquashing, we demonstrate the negative impact of increasing the spectral gap X, which motivates us reconsider: is it necessary to increase X through global approach?
unified formalism. In order to provide a principled analysis, we construct a unified formalism in Riemannian geometry as its notions align with those in spectral graph theory [17 Chap. 10). To be specific, we first construct the following layer-wise heat equation analogous to Eq. ①.
{
8rup (1, x) Ag (1,
k k= k. K k 1= K
(3)
(12, x) = Φu (2r),
= with the initial condition Φ (x) = (xx) of input feature, where 0- = t < <t < tg < <tx+1=
and t tx- At for each layer k- = 1, .... K. Second, the solution is derived as follows,
(x(t,x) x) S H(t ts x, y) v)ox (z)v((y)). k= == K. K,
(4)
(x(x)) = Go, [ (14-1(4,, .)),
where Go, is learnable neural net with linear transformations. Third, with input representation du (w;),, the output of o at the k-th layer (k(,,, vi) = Ejev H(At, Us, (U,) is given by the heat kernel (t,, 04, m2y) = [He)y and H, = e-LL [7]. According to the matrix exponential LL I+ >k=1 ET (-(L-)) (L)* if we take a small time step A + O, the first-order approximation is given by e -AIL I AtL. Therefore, we have the updating rule in matrix form,
U HA (I AIL)
$ GO,((K))) (UK-1).
(5)
For example, GCN 33 is an instance of Eq. (5) with At = 1. That is, typical MPNNs in Eq. (2) can be interpreted as a neural solver to the heat equation over Riemannian manifold, offering the theoretical foundation of this paper. The following elaboration considers the scalar-valued function for clarity.
On oversquashing: revisiting the spectral gap Arranging the eigenvalues of the Laplacian of manifold heat kernel in ascending order, the first non-zero eigenvalue is referred to spectral gap X. From the topological perspective, we connect the value of À to the topological "bottleneck" from Riemannian geometry, and the connection established via Cheeger's constant. Concretely, for given manifold M, the Cheeger's constant hm = inf,s vull related to the area of the bottleneck's is cross-section dividing the M into disjoint submanifolds A and B.
Area({)
Theorem 4.1 (Cheeger and Buser's Inequality (9). If the Ricci curvature of manifold M is bounded by (n 1), and & 2 O, then 1 < \ < C(E hm + 12x), where is constant.
'More rigorously, let S be any compact (n 1) suummannifold embedded in manifold M, the Cheeger's constant hm is defined by the infinitum taking over all smooth S.

---

That is, the increase of À enlarges the topological bottleneck in which the messages are often squashed. However, we identify negative impact of increasing À from the perspective of gradient vanishing when we take closer look. Conducting the eigenvalue decomposition, we have the following hold.
Theorem 4.2 (Spectral Gap and Gradient Vanishing, B.I). Suppose t [tz, t with EL= K, the upper bound of the functional derivative Boly) and a model constant Cmodel- Let 1/s denote the eigenfunction. The sollowing inequality holds,
ducle) (t, x) is determined by the heat kernel H [t, x, y)
ōueløl (t, x) S "model (t, x, y) Cmodel 80(y))
Σn e Xik (i(()))))
(6)
The theorem above clarifies the relationship between the eigenvalue of the manifold heat kernel and model training, and states that the increase of tends to result in gradient vanishing, undermining the effectiveness of message passing.
On oversmoothing. Next, examine the impact of increasing À on oversmoothing via a prominent metric of Dirichlet energy 40, measuring the norm of the difference between node representations.
Theorem 4.3 (Spectral Gap and Dirichlet Energy, B.2 Suppose E [lx, le+1] with l S K, and the initial state uz (lz, x) = <br(ar) has an eigenvalue decomposition such that de = Ei=1 Ceets, the Dirichlet energy Dirlue(t, }}] = JM Igrad (e 1²² Volm decays exponentially w.r.t to t as
Dirlue(t,)) )) S Cmmodd (E 2ave-
E Li-1( 2y de -ee-- A )
The theorem states that MPNN is exposed to even more severe oversmoothing by increasing À since the upper bound of the Dirichlet energy is increased.
A more intuitive explanation. Taking graph rewriting as an example, the bottleneck is widened by adding edges to allow more messages to pass through, thereby mitigating oversquashing. Meanwhile, edge deletion is required to combat oversmoothing caused by denser connections, which in turn hinders the information flow in message passing.
Message of the Section: In the global approach, an increase in the spectral gap tends to accelerate gradient vanishing and oversmoothing, thereby deteriorating the efficacy of message passing.
Local Riemannian Geometry for the Best of Both Worlds
The theoretical insights above motivate us to seek for an alternative local solution. While preserving the original graph structure, we propose to adapt message passing according to the local structure or, in the language of Riemannian geometry, reshape the functional space over submanifolds. To achieve this, we establish a novel non- homogeneous boundary condition that is proven to simultancouusly mitigate both oversquashing and over- smoothing.
(a) A model of manifold bottl eneck
Mig
Neumann
5.1 Boundary Condition over Submanifold: Local Treatment against Oversquashing
Robin
Instead of treating the manifold as whole, we consider the heat flow over submanifold (subgraph), and intro- duce the notion of boundary condition to MPNN for the first time, to our best knowledge.
AAA
Dirichlet
Spectrum
(b) Boundary condition
Figure 2: A visual illustration.
Specifically, a heat flow over a submanifold with boundary is described as follows
0,u(t, x) = x)) E intM h(x)) = O,
(8)
x E a.M.
5

---

where i. denotes the submanifold boundary while i is the interior. The boundary is constrained on some (homogeneous) boundary condition h(x) 0, and there exist 3 elementary types of boundary conditions, for or B 2 0, and ox B cannot be 0 simultaneously,
Dirichlet condition
f(x) = - 0f 8n (x) = 0
Neumann condition
Robin condition
af(x) + 13 (=)=
-=)= 00
where a denotes the outward normal derivative. ön
Models of manifold bottlenecks. To formalize the effect of boundary conditions, first introduce the models of manifold bottlenecks. Without loss of generality, we consider (1) simple case of cylinder, formally described as the product manifold S [o. L] (r) of closed interval length L and closed (n 1) b)-ball whose radius is a constant E(r) so over [0, L). and (2) a more generic form with a functional radius e(r) : [0, L] - (0, 1), and an instance sketched in Fig a). Now, we demonstrate how boundary conditions affect the gradient at the bottlenecks.
Theorem 5.1 (Oversquashing under Boundary Conditions, B.3.. Given the boundary of sub- manifold S written as as {0, L} x (s), we have the following claims hold:
For E(s) Eo, if the Dirichlet condition is applied, the decay of heat kernel is determined (ea
by eye-le (t)"t), while it is determined by e -t-- under Neumann condition.
For E(s) Eu cosh a(s 2 the decay of heat kernel under both the Dirichlet and Neu- mann conditions is related to e - a a
For both cases, the decay under Robin condition is upper bounded by the Dirichlet condition and lower bounded by the Neumann.
Corollary 5.2 (Adaptivity of Robin Condition, B.4). For e(s) [0, L] + (0,E) and I, > for the spectral gaps of Dirichlet, Neumann and no boundary, respectively.
small & 0, X2, XN
For e(s) = Eo, we have the order D 2 222 N hold.
For E(s) Eu cosh a(s ( 3) if L is fixed, then X2 2 AN 2 A: if Eo is fixed, then 2 A NN
Theorem 5.1 and Corollary 5.2 state that boundary conditions mitigate oversquashing by locally adjusting X. It is achieved by controlling the amount of messages that flow out of the bottlenecks, as in (bg Specifically, Dirichlet condition absorbs the message and only low-frequency messages be passed. Neumann condition clears the bottleneck by reflecting all the messages. Robin condition reaches balance between them. As - 0. it degenerates Dirichlet condition, while shifting to Neumann when 3 - 0, and offers the adaptivity to adjust at bottlenecks via a and B.
5.2 Nonhomogeneous Boundary Condition: Jointly Mitigating Oversmoothing
We discover that oversmoothing can be mitigated through the source term of external inputs.
Lemma 5.3 (Oversmoothing under Source Terms, B.5). For the nonhomogeneous heat equation
J,u(t, x) A,, x) [tt, x) with a source term [[l, x1, -; (.(()& and initial condition
u(0, x) ((x) al 0, regardless of the existence of boundary condition, there exist some parameters {a; > 2, 3 > 0} satisfying the convergence condition such that
dB. = (1
- (1
Ax (3: + +1) B.(0) = O.
(10)
dl
Then, the Dirichlet energy will decay polynomially w.r. time as
Dir[ue] = E 2- a (3, +t)=
-
X 2 -En
Σ (1+
)3! )
(11)
Lemma 5.3 states the source term mitigates the exponential decay of Dirichlet energy to polynomial.

---

Table 1: The boundary conditions on the graph
Dirichlet condition
Robin condition
Neumann condition
I'(u)
( B Eocs,maa((
f(v)
EncSseo(((u) M(w)
Our solution. We have shown the effect of boundary condition and external input on oversquashing and oversmoothing, respectively. A natural question raises that: does there exist a single operation for the best of both worlds? To this end, we establish the nonhomogeneous boundary condition of l(x)) = 7(1, a), a E 8.,, generalizing from the typical homogeneous ones of h(x)) = 0, æ E Q.. While enjoying the merit of boundary condition, can be equivalently convert into form of Lemma 5.3 to combat oversmoothing. We rigorously demonstrate the advantage of our construction below.
Theorem 5.4 (Equivalence, B.6). For the homogeneous heal equation 0.u(t, .)) g ær), E intM with a nonhomogeneous boundary condition of h(x))) = =1,,,)) x)) x. E 8M and initial condition (0, x) = o(x), t O, there exists a function wit, x) ; .M- + IR such that h w = 7 in i.M By w. Eq. 12 is equivalent to the nonhomogeneous heat equation satisfying Lemma 5.3
{
a,v(t, 2²) = gt, x)) + [(w), x aM, t > 0,
intM, 0
(12)
h(x)= = =0,
where (ww) = At x) - (t, 2:) with converted initial condition v(0, x²) <bxx) w((0 .:).
Consequently, we can simultancously mitigate oversquashing and oversmoothing, and our construc- tion applies the Dirichlet, Robin, or Neumann condition.
GBN: A Provable Neural Architecture
As discussed in Sec. 4 and 5, this calls for neural solver to the manifold heat equation with nonhomogeneous boundary condition. We address this challenge with a simple yet effective Graph Boundary conditioned message passing Neural network (GBN), grounded in the Robin condition. GBN unifies the updating rules for boundary and interior nodes, and we emphasize that it is a scalable model with favorable theoretical guarantees. We begin by introducing the concept of boundary nodes.
Definition 6.1 (Boundary Nodes). In a graph G. for subset S of the vertex set V. the induced subgraph on S has the edge set consisting of all edges of G with both endpoints in S. The vertex boundary is as {ulu u, E S}, where u ~ v denotes u is connected to v in G.
MPNN under Robin Condition Analogous to the continuous realm, the homogeneous boundary conditions are given in Table [
Now, we construct the nonhomogeneous Robin condition on graphs,
Or;0; + 3, E (z: æx) = 7c i E os,
(13)
where the coefficients are given by functions with respect to node current states, i.c., a; = a(x;), 3, = 3(x;), % ((x,) for each i E as. Subject to Eq. (13 on the boundary nodes, we consider the nonhomogeneous heat equation for the interior nodes, whose nontrivial steady state Fs exists.
Accordingly, we are to solve the following equation system in the matrix form,
Interior nodes:
Ls + Ls as Fs. diag(o;) ) Xas diag( 8.) Las, = Tas:
Ls.s Ls,o Las,s
L =
(14)
Boundary nodes:
Las,as
Lemma 6.2 (Solution to Heat Equation System, B.7). Ler D. U and V denote the diagonal. upper and lower matrix of L, respectively. Accordingly to the Jacobi method, the solution is derived as,
diag(a,) =a(x (x); 00),, diag(33) = 3(x (R); 000),, =
(x(()) (M)00)),
(15)
( D (V + ()) (k) +D-IT.
(16)
Let T :- T(i E 5) be an indicator, d, = d, - T,) + (2T - 1) Ejvi Ts and pi = B.
[D [D-UU)
Vā.
Ex-1
1 -xx (k)
V2,
[D vV)x (+)), p1-(1-p
Vd.
Enn
v
1 (k)
2
(17)
7

---

Table 2: Comparison of layer-wise complexity. V and & denotes node and edge set, respectively.
Models
DR
BORF
UniFilter
ProxyGap
Graph Transformer
GBN (Ours)
Complexity
O(jEld max
O(M + (E])
O[[E] * (V)
O(IV))
O + [EI)
The updating rule is given by adding nonlinearity a and a learnable MLP p(++1),
( =
()) (D + D-'TT
(18)
Note that GBN unifies the updating rule of boundary and interior nodes via an indicator, which is jointly optimized together with other parameters.
Computational Complexity A pseudocode description of training GBN is given in Appendix C, whose layer-wise complexity is yielded O(2) (l) We compare with some popular models in Table where dmaa is the maximum node degree.
Local Bottleneck Adjustment Building on nonhomogeneous Robin condition, we locally con- sider each bottleneck and perform adaptive message passing, Specifically, the amount of messages flowing out of the bottleneck regulated by the corresponding interior nodes, thereby mitigating oversquashing, while the cutoff frequency of message passing is learned in an end-to-end fashion.
Oversmoothing mitigated through the external inputs since the Dirichlet energy does not converge to zero owing to the existence of 7. On oversquashing, we examine whether or not the Jocabian ||0x; (K) /0xz II exhibits the exponential decay regarding the hop distance K.
Theoretical Guarantees
Theorem 6.3 (Distance Independence, B. Given two nodes v; and vj with the hop distance K, and the updating rule in Eq. (18). we have the Jocabian satisfy
(K)
dx
(E
U)]+
I CK
0x;
where CR is a constant related to the parameters. As K + co, | /0x; is independent of K.
The theorem states that, in the limit, the Jocabian converges constant independent on the distance, and thus implies that oversquashing does not occur.
Connection to Previous Models The recent virtual node methods 50 can be regarded as homogeneous Neumann condition with single additional boundary, and have guarantee against oversmoothing. Note that, the proposed GBN recovers the vanilla GCN when and y are eliminated.
7 Experiment
We compare 17 strong baselines 7 benchmark datasets answer the following research questions: 1) How does GBN perform on homophilic and heterophilic graphs? 2) How does each component contribute to GBN? 3) Does GBN allow for the network go deep? 4) Does GBN support capturing long-range dependencies? Codes are available https: // //titt////itub...... thub. com/ Zww.//uannhhgggggeeeee GBN
7.1 Experimental Setups
Datasets & Baselines. Experiments are conducted on variety of datasets, including homophilic
graphs of WikiCS, Computer and CS [48] [19] and 4 heterophilic graphs of Texas, Wisconsin,
RomanEmpire and Ratings (43] The baselines are categorized into three groups: (1) MPNNs:
GCN 33 GAT (66), GIN
773 hyperbolic HGCN (10) and message diffusion GREAD 15)
(2) Methods to improve MPNN: G2-GCN 46 and GraphNormv2 [47] against oversmoothing.
SWAN 24 and MPNN+VI VN
[50] on oversquashing, and BORF (9). DR 4, ProxyDelete (8 and
UniFilter 27 to tackle both issues; (3) Graph transformers: sp-exphormer [49), Graphrrperrerr
21, CoBFormer [70), and GraphMamba (67]. Datasets and baselines are detailed in Appendix D.

---

Table 3: Node Classification in terms of ACC (%) on both homophilic and heterophilic graphs. The best results are boldfaced, and the runner-ups are underlined.
Model
WikiCS
Computer
CS
Texas
Wisconsin
RomanEmpire
Ratings
GCN
77.43=0.83
88 1.
91. 91.49.0.42
55. 83.5.99
50.16
70.30
48. 12:40.44
GAT
75.81=1.03
88.36
92.17=0.46
22.007
50.78=6.41
80.89=0.70
48.78:0.60
GIN
82.37=2.45
90.6911.26
93
17.37112.12
69.23
02.20
48.68.20.7
HGCN
=4.32=0.67
1..98
90.79
18.177
55.05=1.84
80.42:00.55
47. :2.099
GREAD
79.25=1.16
88.21#1.86
91.20=0.75
84.37
85,23=3321
73.25=22.6
47.77
DR
77.62=0.16
89. 89.89+0.52
90.77
10.68
70.98=1.50
71.99=0.11 14
48. 25.233m0.22
UniFilter
84.00=0026
1.:2
95.25=0.ur
1.35
69.52=1.59
74.43=0022
19.44=0.20
ProxyGap
81.34=0.76
89.
93.75=0.48
74.21#122
67.75=1.64
77.45=0.66
49.75=0.46
MPNN VN
83.67=0.66
90.80
92.51
66.66716.77
80.63=2.84
81.07=00.26
46.46:00.1
GraphNormvv2
76.93=0.45
87 0.
93.80=0.15
72.07
83.01=1.18
71.79:
45.80=00006
BORF
85.89=0.28
91.76=0.08
93.48=0.01
74.88
=4.11
81.83=0.00
53.21=0001
GD-GCN
77.85=1.34
87.08
92.32=0.20
84.86++5.43
86.12=4.51
78.56=1.66
49.38=2.24
SWAN
1..20
88.57
90.57.0.81
76.9617:29
73.98=2.19
73.4820085
49.73=3.41
CoBTormer
83.95-0.22
80.9610.54
94.661:014
76.52.12.35
85.40.22.44
76.46::0.2
48.59.0025
VCR- Graphormer
84.32=0001
90.53:0.01
95.17=0.00
62.6322.50
73.33=0000
74.55=0.00
53.31=0.01
Spexphormer
84.53=2.11
89 23.
95.19
76, 76.96.33.05
80.93
87.54.0.14
48.61
Graph- Graph-Mamba
84.07
88.544...27
94.4610.16
73.33
77.42:1135
88.36=0.06
49.58=1.22
Ours
86.21
91.33+0.32
95.78+0.21
85.01=6.0
86.78+3.54
89.83
53.51
Table 4: Ablation Study
Evaluation Metrics. We evaluate the model performance with node classifica- tion and employ the popular metric of ACC. Each case undergoes 10 independent runs, and we report the mean with standard de- viations.
Model
CS
WikiCS
Texas
Ratings
GBN
95. 21
86 20..00
85.01=6.01
53 11.55199.0
70,
94, 94.14
85.3620.45
83.1744.32
03.05
0
92.26+0.68
80.01
76.27+5.84
48 1.020
&
93.7749.66
81.71a0.52
82.7845.36
50. 00.60920.s
91.71+0.34
78.29
62.16+44.50
48. 60
GCN
91.494n.42
77.43so.s
55.83
48. 12.0.4
Reproducibility & Model Configuration.
The hardware is NVIDIA GeForce RTX 4090 GPU 24GB memory, and Intel Xeon Platinum 8352V CPU with 120GB RAM. In GBN, the coefficients of o, 33, and y are implemented as 2-layer MLP, and the model is optimized by Adam. Further details on hyperparameter settings are in Appendix E
7.2 Results and Discussion
Dirichlet Energy flog scale)
10
Model Performance. We conduct node classification on all the 7 graphs, and the results of ACC are summa- rized in Table 3 The hyperparameter settings of the baselines is the same as the original papers. As in Table 3 mitigating oversmoothing oversquashing generally improves the performance of MPNNs. GBN consis-
10:
10-11
20 16
GAI
10 31
TrasyGup
tently achieves the best results except for one case on the Computer dataset.
10-26
10
100
1000
Layer
Figure 3: Dirichlet energy curve (lg-Ig).
Ablation Study. To examine the effectiveness of each module in GBN, we design several variant models and collect the model performance in Table 4 Coneretely, we replace the learnable boundary condition coefficients with fixed constants, termed as % Pg. The variant yss 0 disables the external inputs, while 3, 0 elim-
Test Accuracy
inates boundary interactions. Table 4 reports a perfor- mance decline in these variants compared to GBN, un- derscoring the critical role of each module. Also, under 7, 8 0, GBN degenerates as GCN in general.
0.7
0.6
0.5
32 Number of Layers
16
64
128
256
Deeper Network Oversmoothing. On oversmooth- ing, we evaluate the model performance and Dirichlet energy when MPNN goes deeper. Fig. shows the de- cay of Dirichlet energy the number of layers increases
Figure 4: Node classification accuracy with respect to the number of network lay- Cora dataset.

---

GCN
G²-GCN
MPNN +VN
ProxyGap
SWAN
GBN
Mean Squared Error
10
10-2
10
10-1
10
10
10-4
-5
35 10
50
35 10
50
35 10
50
Source-Target distance (#hops)
Source-Targel distance (#hops)
Source-Target distance (#hops)
(a) Line
(b) Ring
(c) Crossed-Ring
Figure 5: Results of graph transfer task in terms of Mean Squared Error (%).
from to 256 using the benchmark synthetic dataset 46 29], detailed in Appendix E, for fair comparison. parallel, we present node classification performance in Fig. 4 Traditional GCN and GAT exhibit exponential decay of Dirichlet energy and a corresponding performance decline, indicating severe oversmoothing. The graph rewriting method of BORF mitigates the decay, but ultimately, node representations become indistinguishable. Both G2 and our proposed GBN effectively combat oversmoothing in terms Dirichlet energy; however, G2-GCN struggles to capture long-range dependencies shown in the next paragraph. Notably, as shown in Fig. 4 the proposed GBN does not exhibit performance degradation even the network depth exceeds 256 layers.
Long-range Dependencies & Oversquashing To evaluate the ability against oversquashing we investigate the information transfer between distant nodes with the graph transfer experiment, following [24 23] Concretely, the experiment is conducted on 3 synthetic topologies: line, ring and cross-ring, where a source node labeled "1" and target node labeled "-1" are separated by hops of randomly valued nodes. Further details are in Appendix E. The task is to switch the labels between source and target nodes through message passing. We vary the hop distance in {3, 5, 10, 50} and present the results in Fig. [ where the number of network layers is equal to the hop distance. As the dis- tance increases, the messages from the expand- ing receptive field are squashed together. GCN, G2-GCN and GroxyGap fail to effectively propagate the labels, revealing limitation in capturing long-range dependencies. In contrast, the proposed GBN consistently achieves the best performance in Fig. 5
GCN
Original Graph
Node Feature Value
GBN
Figure Case study
Case Study & Visualization In the case study, we visualize result of graph transfer task in Fig. to further investigate the model performance. Specifically, the experiment is conducted on the graph where two complete graphs (i.e., the source on the left and the target on the right) are connected by line (i.e., topological bottleneck). The nodes are randomly assigned in [0. in the source, while [-1, 0) the target. The node value the connecting line is "0". The task the source and target components. As shown in Fig. o GCN results in the messages being severely "squashed" in the bottleneck. In contrast, the proposed GBN allows messages to pass through the bottleneck, thanks to local bottleneck adjustment.
swap the values in
8 Conclusion
Our work presents fresh local approach to jointly mitigate oversquashing and oversmoothing in MPNNs. Grounded Riemannian geometry, we establish the nonhomogeneous boundary condition that preserves the original graph structure while adaptively adjusting the message passing paradigm to achieve the best of both worlds. Building on the Robin condition, we design a simple yet effective GBN with local bottleneck adjustment, supported by favorable theoretical guarantees. Extensive experiments demonstrate the superior performance of GBN on benchmark graphs. We further demonstrate GBN can enable deeper MPNNs by exploiting the nonhomogeneous boundary condition.
10

---

Acknowledgement
This work is supported in part by NSFC under grants 62202164. Philip Yu is supported in part by NSF under grants III-2106758, and POSE-2346158.
References
[1] Alon, U. and Yahav, E. On the bottleneck of graph neural networks and its practical implications. In Proceedings of the 9th ICLR. OpenReview.net, 2021.
[2] ArmaizRRodriguez, A., Begga, A., Escolano, F., and Oliver, N. Diffwire: Inductive graph rewiring via the lovász bound. In Proceedings of the 1st Learning on Graphs Conference (LoG), pp. 15. PMLR, 2022.
[3] Arroyo, A., Gravina, A., Gutteridge, B., Barbero, F., Gallicchio, C., Dong, X., Bronstein, M. M., and Vandergheynst, P. On vanishing gradients, over-smoothing, and over-squashing in gnns: Bridging recurrent and graph learning. CoRR, abs/2502. 10818, 2025.
[4] Attali, H., Buscaldi, D., and Pernelle, N. Delaunay graph: Addressing over-squashing and over-smoothing using delaunay triangulation. Proceedings of the 41st ICML, pp. 1992 2008. PMLR, 2024.
[5] Bachmann, G., Béeigneul, G., and Ganea, O. Constant curvature graph convolutional networks. In Proceedings of the 37th ICML, volume 119, pp. 486-496. PMLR, 2020.
[6] Banerjee, P. K., Karhadkar, K., Wang, Y., Alon, U., and Montúfar, G. Oversquashing in gnns through the lens of information contraction and graph expansion. In Proceedings of the 58th Annual Allerton Conference on Communication, Control, and Computing, pp. 1-8. IEEE, 2022.
[7] Black, M., Wan, Z., Nayyeri, A., and Wang, Understanding oversquashing in gnns through the lens of effective resistance. In Proceedings of the 40th ICML, volume 202, pp. 2528-2547. PMLR, 2023.
[8] Bresson, X. and Laurent, T. Residual gated graph convnets. CoRR, abs/ 2017.
[9] Buser, P. A note on the isoperimetric constant. Annales Scientifiques de I École Normale Supérieure, 15(2), 1982.
[10] Chami, I., Ying, Z., Ré, C., and Leskovec, Hyperbolic graph convolutional neural networks. 2019.
In Advances in the 32nd NeurlPS, pp.
[11] Chen, D., Lin, Y., Li, W. Li, P., Zhou, J., and Sun, X. Measuring and relieving the over- smoothing problem for graph neural networks from the topological view. In Proceedings of the 34th AAAI, pp.
AAAI Press, 2020.
[12] Chen, H., Wang. X., Zhang, Z., Li, H., Feng, L., and Zhu, W. AutoGFM: Automated graph foun- dation model with adaptive architecture customization. Proceedings of the 42nd International Conference Machine Learning (ICML), 2025.
[13] Chen, M., Wei, Z., Huang, Z., Ding, B., and Li, Y. Simple and deep graph convolutional networks. In Proceedings of the 37th ICML, pp. 1725-1735. PMLR, 2020.
[14] Chen, T. Q. and Lipman, Y. Flow matching on general geometries. In Proceedings of the 12th ICLR, 2024.
[15] Choi, J., Hong, S., Park, N., and Cho, S.-B. GREAD: Graph neural reaction-diffusion networks. In Proceedings of the 40th ICML, volume 202, pp. 5722-5747. PMLR, 2023.
[16] Choi, J., Park, S., Wi, H., Cho, S.BB., and Park, N. PANDA: Expanded width-aware message passing beyond rewiring. In Forty-first International Conference on Machine Learning, 2024.
[17] Chung, F. R. K. Spectral Graph Theory. AMS, 2011.

---

[18] Deac, A., Lackenby, M., and Velickovic, P. Expander graph propagation. In Proceedings of the 1st Learning on Graphs Conference (LoG), pp. 38. PMLR, 2022.
[19] Dwivedi, V. P., Joshi, C. K., Luu, A. T., Laurent, T., Bengio, Y., and Bresson, X. Benchmarking graph neural networks. Journal of Machine Learning Research,
2023.
[20] Fesser, L. and Weber, M. Mitigating over-smoothing and over-squashing using augmentations of forman-ricei curvature. In Proceedings of Learning on Graphs Conference (LoG), volume 231, pp. 19. PMLR, 2023.
[21] Fu, D., Hua, Z., Xie, Y., Fang. J., Zhang, S., Sancak, K., Wu, H., Malevich, A., He, J., and Long, B. Ver-graphormer: A mini-batch graph transformer via virtual connections. In Proceedings of the 12th ICLR. OpenReview.net, 2024.
[22] Fu, X., Wang. J., Gao, Y., Sun, Q., Yuan, H., Li, J., and Li, X. Discrete curvature graph information bottleneck. In Proceedings of the 39th AAAI, pp. 16666-16673, AAAI Press, 2025.
[23] Giovanni, D., 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 ICML, volume 202, pp. 7865-7885. PMLR, 2023.
[24] Gravina, A., Eliasof, M., Gallicchio, C., Bacciu, D., and Schönlieb, C. On oversquashing in graph neural networks through the lens of dynamical systems. In Proceedings of the 39th AAAI, pp. 16906-16914, AAAI Press, 2025.
[25] Guo, X., Wang, Y., Du, T., and Wang, Y. Contranorm: A contrastive learning perspective on oversmoothing and beyond. In Proceedings of the 1ith ICLR. OpenReview.net, 2023.
[26] Gutteridge, B., Dong, X., Bronstein, M. M., and Giovanni, D. Drew: Dynamically rewired message passing with delay. In Proceedings of the 40th ICML, pp. 12252-12200 PMLR, 2023.
[27] Huang, K., Wang, Y. G., Li, M., and Lio, P. How universal polynomial bases enhance spectral graph neural networks: Heterophily, over-smoothing, and over-squashing. In Proceedings of the 41st ICML, pp. 20330. PMLR, 2024.
[28] Jamadandi, A., Rubio-Madrigal, C., and Burkholz, R. Spectral graph pruning against over- squashing and over-smoothing. In Advances in the 38th NeurIPS, 2024.
[29] Jiang, Y., Zou, D., Zhang, X., and Wang, Y. G. Limiting over-smoothing and over seusshuushnggggg of graph message passing by deep scattering transforms. CoRR, abs/2407.06988. 2024.
[30] Karhadkar, K., Banerjee, K., and Montúfar, G. Fosr: First-order spectral rewiring for addressing oversquashing in gnns. In Proceedings of the 11th ICLR. OpenReview.net, 2023.
[31] Keriven, N. Not too little, not too much: a theoretical analysis of graph (over)smoothing. In Advances in the 35th NeurIPS, 2022.
[32] Kiani, B., Fesser, L., and Weber, M. Unitary convolutions for learning on graphs and groups. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[33] Kipf, T. N. and Welling, M. Semi-supervised classification with graph convolutional networks. In Proceedings of the 5th ICLR. OpenReview.net, 2017.
[34] Law, M. Ultrahyperbolic neural networks. In Advances in the 34th NeurIPS, 2021.
[35] Li, Q., Han, 2., and Wu, X. Deeper insights into graph convolutional networks for semi- supervised learning. In Proceedings of the 32nd AAAI, pp.
AAAI Press, 2018.
[36] Liu, M., Gao, H., and Ji, S. Towards deeper graph neural networks. In Proceedings of the 26th SIGKDD, pp. 338-348. ACM, 2020.
[37] Liu, Q., Nickel, M., and Kiela, D. Hyperbolic graph neural networks. In Advances in the 32nd NewrIPS, 2019.
12

---

[38] Liu, Y., Zhou, C., Pan. S., Wu, J., Li, Z., Chen, H., and Zhang, P. Curvdrop: A ricci curvature based approach to prevent graph neural networks from over-smoothing and suua-squa In Proceedings of the ACM Web Conference (WWW), pp. 221-230. ACM, 2023.
[39] Nguyen, K., Hieu, N. M., Nguyen, D.D., Ho, N., Osher, S. J., and Nguyen, T. M. Revisiting over-smoothing and over squashing using ollivier-ricei curvature. In Proceedings of the 40th ICML, volume 202, pp. 25956-25979. PMLR, 2023.
[40] Oono, K. and Suzuki, T. Graph neural networks exponentially lose expressive power for node classification. In Proceedings of the 8th ICLR. OpenReview.nee net, 2020.
[41] Ortega, M. and Rheinboldt, W. C. Iterative Solution of Nonlinear Equations in Several Vari- ables. Society for Industrial and Applied Mathematics, 2000. doi: 10.1 (0.1137/1.9780898) 771111988888899888
[42] Pei, H., Li, Y., Deng. H., Hai, J., Wang. P., Ma, J., Tao, J., Xiong, Y., and Guan, X. Multi-track message passing: Tackling oversmoothing and oversquashing graph learning via preventing heterophily mixing. In Proceedings of the 4 ICMI., pp. 40078-40091, PMLR, 2024.
[43] Platonov, O., Kuznedelev, D., Diskin, M., Babenko, A., and Prokhorenkova, L. A critical look at the evaluation gnns under heterophily: Are we really making progress? In Proceedings of the 1 1ith ICLR. OpenReview.net, 2023.
[44] Rong, Y., Huang, W., Xu, T., and Huang, J. Dropedge: Towards deep graph convolutional networks on node classification. In Proceedings of the 8th ICLR. OpenReview.net, 2020.
[45] Rosenbluth, E., Tönshoff, J., Ritzert, M., Kisin, B., and Grohe, M. Distinguished in uniform: Self-attention vs. virtual nodes. In Proceedings of the 12th ICLR. OpenReview.net, 2024.
[46] Rusch, T. K., Chamberlain, B. P., Mahoney, M. W., Bronstein, M. M., and Mishra, S. Gradient gating for deep multi-rate learning on graphs. Proceedings of the 11th ICLR. OpenReview.net, 2023.
[47] Scholkemper, M., Wu, X., Jadbabaie, A., and Schaub, M. T. Residual connections and nor- malization can provably prevent oversmoothing in gnns. In Proceedings of the 13rd ICLR. OpenReview.net, 2025.
[48] Shchur, O., Mumme, M., Bojchevski, A., and Günnemann, S. Pitfalls of graph neural network evaluation. CoRR, abs/1811.00866 2018
[49] Shirzad, H., Lin, H., Venkatachalam, B., Velingker, A., Woodruff, D. P., and Sutherland, D. J. Even sparser graph transformers. In Advances in the 38th NeurlPS, 2024.
[50] Southern, J., Giovanni, F. D., Bronstein, M. M., and Lutzeyer. J. F. Understanding virtual nodes: Oversmoothing and node heterogeneity. In Pruceedings of the 13rd ICLR. OpenReview.net, 2025.
[51] Sun, L.,, Zhang, Z., Zhang, J., Wang, F., Peng, H., Su, S., and Yu, P. S. Hyperbolic variational graph neural network for modeling dynamic graphs. In Proceedings of the 35th AAAI, pp. 4375-4383, 2021.
[52] Sun, I.., Ye, J., Peng, H., and Yu, P. S. A self-supervised riemannian GNN with time varying curvature for temporal graph learning. In Proceedings of the 31st CIKM, pp. 1827-1836, 2022.
[53] Sun, L., Zhang, Z., Ye, J., Peng, H., Zhang, J., Su, S., and Yu, S. A self-supervised mixed-curvature graph neural network. In Proceedings of the 36th AAAI, pp. 4146-4155, 2022.
[54] Sun, L., Huang, Z., Wu, H., Ye, J., Peng, H., Yu, Z., and Yu, P. Deepricci: Self-supervised graph ceructureffeature co-refinement for alleviating over-squashing. In Proceedings of the 23rd ICDM, pp. 558-567, 2023.
[55] Sun, L., Wang, F., Ye, J., Peng, H., and Yu, S. Congregate: contrastive graph clustering in curvature spaces. In Proceedings of the 32nd IJCAI, pp. 2296-2305, 2023.
[56) Sun, I., Ye, J., Peng, H., Wang, F., and Yu, P. S. Self-supervised continual graph learning in adaptive riemannian spaces. In Proceedings of the 37th AAAI, pp. 4633-4642, 2023.
13

---

[57] Sun, L., Hu, J., Zhou, S., Huang, Z., Ye, J., Peng, H., Yu, Z., and Yu, P. S. Riccinet: Deep clustering via a riemannian generative model. In Proceedings of the ACM Web Conference (WWW), pp. 4071-4082, 2024.
[58] Sun, I.., Huang, Z.., Peng, H., Wang. Y., Liu, C., and Yu, P.S. Lsenet: Lorentz structural entropy neural network for deep graph clustering. In Proceedings of the 41st ICMI,, pp. 47078-47104, 2024.
[59] Sun, L... Huang, Z., Wan, Q., Peng, H., and Yu, P.S. Spiking graph neural network on riemannian manifolds. Advances in NeurIPS, 2024.
[60] Sun, L., Huang, Z., Wang. Z., Wang, F., Peng, H., and Yu, P. S. Motif-aware riemannian graph neural network with generative-contrastn learning. In Proceedings of the 38th AAAI, pp. 9044 9052, 2024.
[61] Sun, L., Huang, Z., Zhou, S., Wan, Q., Peng, H., and Yu, S. Riemanngfm: Learning graph foundation model from riemannian geometry. In Proceedings of the ACM Web Conference (WWW), pp. 1 1154-1165. ACM, 2025.
[62] Sun, L., Zhang, Z., Wang, Z., Wang, Y., Wan, Q. Li, H., Peng, H., and Yu, P. Pioneer: Physics-informed riemannian graph ode for 39th AAAI, pp. 12586-12588 2025.
dynamics. In Proceedings of the
[63] Sun, L., Zhou, S., Fang, B., Zhang, H., Ye, Ye, Y., and Yu, P. S. Trace: Structural riemannian bridge matching for transferable source localization in information propagation. In Proceedings of the 34th IJCAI, pp. -006,3336,2200 2025.
[64] Topping. J., Giovanni, F. D., Chamberlain, B. P., Dong, X., and Bronstein, M. M. Understanding over-squashing and bottlenecks on graphs via curvature. In Proceedings of the 10th ICLR. OpenReview.net, 2022.
[65] Tu, L. W. An Introduction to Manifolds. Springer New York, 2011.
[66] Velickovic, P., Cucurull, G., Casanova, A., Romero, A., Liò, P. and Bengio, Y. Graph attention networks. In Proceedings of the 6th ICLR. OpenReview.net, 2018.
[67] Wang, C., Tsepa, O., Ma, J., and Wang, B. Graph-mamba: Towards long-range graph sequence modeling with selective state spaces. CoRR, abs/2402.00789, 2024.
[68] Wang, S., Wang, B., Shen, Z., Deng, B., and Kang, Z. Multi-domail graph foundation models: Robust knowledge transfer via topology alignment. In Proceedings of the 42nd International Conference on Machine Learning (ICML), 2025.
[69] Wang, Y., Zhang, S., Ye, J., Peng, H., and Sun, L. A mixed-curvature graph diffusion model. In Proceedings of the 33rd CIKM, pp. 2482-2492. ACM, 2024.
[70] Xing, Y., Wang, X., Li, Y., Huang, H., and Shi, C. Less is more: the over-globalizing problem in graph transformers. In Proceedings of the 41st ICML, volume 235, pp. 54656-54672. PMLR, 2024.
[71] Xiong, B., Zhu, S., Potyka, N., Pan, S., Zhou, C., and Staab, S. Pseudo-riemannian graph convolutional networks. In Advances in the 35th NeurlPS, 2022.
[72] Xu, K., Li, C., Tian, Y., Sonobe, T., Kawarabayashi, K., and Jegelka, S. Representation learning on graphs with jumping knowledge networks. In Proceedings of the 35th ICML, pp. 5449-5458. PMLR, 2018.
[73] Xu, K., Hu, W., Leskovee, J., and Jegelka, How powerful are graph neural networks? In Proceedings of the 7th ICLR. OpenReview.ned 2019.
[74] Xue, Y., Dai, J., Lu, Z., Wu, Y., and Jia, Y. Residual hyperbolic graph convolution networks. In Proceedings of the 38th AAAI, pp. 16247-16254, AAAI Press, 2024.
14

---

[75] Yang, L., Kang, L., Zhang, Q. Li, M., Niu, B., He, D., Wang, Z., Wang, C., Cao, X.. and Guo, Y. OPEN: orthogonal propagation with ego-network modeling. In Advances in the 35th NeurIPS, 2022.
[76] Yang, L.,, Zhang, Q. Shi, R., Zhou, W., Niu, B., Wang, C., Cao, X., He, D., Wang, Z., and Guo, Graph neural networks without propagation. In Proceedings of the ACM Web Conference, pp. 469 (69-477.40 ACM, 2023.
[77] Yuan, H., Sun, Q. Shi, J., Fu, X., Hooi, B., Li, J., and Yu, P. How much can transfer? BRIDGE: Bounded multi-doman graph foundation model with generalization guarantees. In Proceedings of the 42nd International Conference on Machine Learning (ICML), 2025.
[78] Zhao, L. and Akoglu, L. Pairnorm: Tackling oversmoothing in gnns. In Proceedings of the 8th ICLR. OpenReview.nee 2020.
[79] Zhou, K., Dong, Y., Wang, K., Lee, W. S., Hooi, B., Xu, H., and Feng, J. Understanding and resolving performance degradation in deep graph convolutional networks. In Proceedings of the 30th CIKM, pp. 2728-2737. ACM, 2021.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Main claims made in the abstract and introduction reflect the contributions in Sections 4, 5, 6 and 7.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitations of the work is discussed in the paragraph entitled "Broader
Impact and Limitations".
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
15

---

The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't It acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proof's
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: The theoretical results including the assumptions are clearly stated in Theorems in this paper, while the complete and correct proof's are provided in Appendix B.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Key information is introduced in the subsection of "Model Configurations and Reproducibility", and further details are disclosed in Appendix entitled "Implementation Details".
Justification:
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibility also be provided via detailed
16

---

instructions for how to replicate the results, access to a hosted model (e.g., g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: Codes and data are available the anonymous GitHub link, where sufficient instructions are provided.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... ec/
cablic/guides httii///uuiios//oouuuuiiisssss "oodeSumiissionee
aesionPolicy oolicyyyy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Important settings are given in Appendix E entitled "Implementation Details", and the full details are included the code.
Guidelines:
17

---

The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: In the experiment, each case undergoes 10 independent runs, and we report the mean with the error bar standard derivations.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The hardware for the evaluation described in the subsection of "Experimental Setups", and further information is provided in Appendix E entitled "Implementation Details".
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics httppp////earrrp...c///bb//eeeee
18

---

Answer: [Yes]
Justification: We confirm that the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Both potential positive societal impacts and negative societal impacts are included in paragraph entitled "Broader Impact and Limitations".
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups). privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI...
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
The publicly available datasets are used for the evaluation.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided relcasing unsafe images.
19

---

We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: The original papers that produced the code package or dataset are properly cited in this submission.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, if possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. www.coo//aaaaaaa con/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
The documentation is provided alongside the Codes of the proposed model.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
20

---

According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based on the requirements of your country institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.MM policy hatt:p////eeaarrppc.c/////oorrrp for what should or should not be described.
21

---

Contents of Technical Appendix
Notations
Theorems, Proofs and Derivations
Algorithm
Datasets and Baselines
Implementation Notes (including detailed configurations and experimental setups).
A Notations
Table 5: Notations.
Notation
Description
M
A Riemannian manifold
The Riemannian metric
A point Riemannian manifold vector
volu
The volume form on M
SM volM(y)
The Riemannian integral w.r.t. variable y
Ag grad div Ae, the òz
The Laplace-Beltrane operator on M w.r.t.
The Riemannian gradient
The Riemannian divergence
The i-th eigenvalue and eigenfunction the Laplace-Beltramee operator
The parital derivative w.r.t. é
u(t, x))
The solution
heat equation The heat kernel
H V)
The spectral gap closed manifold The spectral gap of compact manifold with Dirichlet boundary
AD
AN
The spectral gap of compact manifold with Neumann boundary A graph with node set V and edge set
g (V,E)
X
The feature matrix
L
The normalized graph Laplacian
A
The graph adjacency matrix
MLP
The initial value function of the heat equation
u, v, Uz, By L,i,j.k, k.
A node in graph
The lower index
The identity matrix
The (n -imdeennsal submanifold of M
Area
The volume of M restrict to the (n 1 dimeessioaal submanifold
vol
The volume of M
h
The Cheeger's 's constant of M
A small value variable
öflel
The variational derivative of f w.r.t. Φ
de Dirl
The Dirichlet energy of function ʃ
The outward normal derivative The coefficients of the Robin condition
on
a.3
s(-)
The radius function
(r(r)
The closed ball with radius s(r) The interior node set of graph G The boundary node set of graph G The diagonal matrix for the Jacobi method The lower diagonal matrix for the Jacobi method The upper diagonal matrix for the Jacobi method The source term of nonhomogeneous Robin condition for boundary nodes The steady state of heat equation for interior nodes The concatenate for Fs and Fas
as D V U Tas
Fs
22

---

B Theorems, Proofs and Derivations
B.1 Proofs of Theorem
Theorem 4.2 (Spectral Gap and Gradient Vanishing). Suppose t Lte, leta] with 1 < <&<= K. &nelel (t, x:) is determined by the heat kernel (t, bo(y)
the upper bound of the functional derivative and the model constant Cmodel.
duelol (p(y)
(1, a) S Cmodel H1, 8. y) = Cmodel Σn Ael ((()))))))
Proof. The algebraic operations are omitted for clarity 5 and the key steps of the derivation are shown follows,
due [0)
(t,z) = I dueldel
Jōrløl 86(y)
(t,
vol
dΦ(y)
δos(zz)
Im Sueldee]
iGo, [ue-1]
due-1(o)
(t)
(te, 2e) volm(ze)
(0l(ze)
bte-ilte,22
50(y)
= -mc 0ue(Se)
8Go, [ue-1]
[t-1 Suz (441224))
8Go [us] b 2i)
(t,
dul (te: zt)
Sip((zs)
(01
(6)(0)
(t2, 22)
(22 (x)
801(21)
60(y)
= =/he H(t- - te,
H(t+41 - t, 211
H(t2 - t1, 22. 3)
8Ga, [ui-1]
II
vol (x
814-1 (tz, 21)
Ht,,x,,) /
II
1
8Go [14-1]
vol (x
Ju, (ti, 2x)
Cmodel H (t, x)
(19)
Since M is compact, by the eigen-decompositiinn w.r.t H1, xr 2), we have
8u [0) (t) I Canodel (t, v) Crusdel 80(y)
Xu (x)
(20)
B.2 Proof' of Theorem
Theorem 4.3 (Spectral Gap and Dirichlet Energy). Suppose E [te, te41] with 1 < E K, and the initial state (e(te, x) = (x)) has an eigenvalue decomposition such that Φe = Eie Ce, the Dirichlet energy Dir Di )] = J' Igrad uelt, )² Volm decays exponentially w.r.t. to as
Dirfue(t, -)
1 Wmodel
Σ 2ee 22
Σ
-, -M00-000 (te-1
where denotes eigenfunctions and the Cz the corresponding coefficients.
'Throughout the proof's in Part B, we demonstrate the derivation with the scalar a, and the same structure holds for the vector æ.
23

---

Proof. Suppose de(②) Ei=1 (1), where ce,s = (de, 1is). we have
I
2e(t,z)
H( - te. 2, ()) volu(y)
M
[
(1 volm())
M
i.j
(3) IN (i(U)150)) volm(s)
1
(21)
The Riemannian gradient of ue(t,-) is
8
grad ue(t, Σ
te
Ce grad, grad 1/.
(22)
Then, the Dirichlet energy of ur((,,) will be
Dir [ur [w] = / (ue(t, VolM
MM (Vue, Vuel, VOlm
-((tt)))--- I. (Vevi, Vatty) Volm
1
-(i++ ce I
M diroois Volm
2
Σ
Nect,iCt,ee (ArtAa / volu
i.j
2
Σ cr, 2 ()((-()
(23)
since de = ( x)1, the projection coefficient on tha is
Ice,1 = = 1/ Go, x)k/ volul
M
S
|Gau, ||l|ue- (14) (1))
Gep (1)
From Eq. 21
we have
1 C--1-CE-15c (a volm
(te))
Σ E2- - (22,((0-1))))
+
2 S
Go, 1| E
f-- 2--1--22y(l----
(24)
j
Substituting into Eq. 23
we have
Dir [ux(()) (t)
1
Σ
C,, dse (2,((=))))
2
(25)
2
==1
|o, 1
Σ
2
(26)
ig
24

---

By induction, we have
Dir [ur(())
-
1
II
Go 11?
Σ
bhe (4---)
(27)
2
A=1
1
Wmodel
Ea 24,t
Σ 20s(t-te)) -En Ase (1a- 1)
(28)
2
i.277
je7t
(29)
where Cf2 = (6, 3/22)
B.3 Proof' of Theorem 5.1
Theorem 5.1 (Oversquashing under Boundary Conditions). Given the boundary of submanifold S written as as {0, L} x (s),s,, we have the following claims hold:
For E(s) = Eo, if the Dirichlet condition is applied, the decay of heat kernel is determined e 2t), while it is determined by - under Neumann condition.
For E(s) = Eu cosh a(s 2). the decay of heat kernel under both the Dirichlet and Neu- mann conditions is related to e -5 cosh )
For both cases, the decay under Robin condition is upper bounded by the Dirichlet condition and lower bounded by the Neumann condition.
Proof. Consider S Use(o,.. {s} (s), where s(r) : L] (0,5) with (0, Denote the Laplace-Beltrami operator on [0, L] and (8) are DR and As..- Since As = AR @ IB... [o & AB... for eigenfunction zb of An and Bh.... for An...
As @ W Be)r) = A 8 We
B... + + @ V Br.
(um Me
Br,. Beg y
@ th
(30)
The first case Now, we consider that E(s) = Eu. where En E (0,8) 8) is constant. First, we solve the eigenvalue problem on R [0, L] with boundary condition:
On the Dirichlet boundary condition, the eigenvalue problem equation
de 2 =- = R
R
I E (0, L)
(31)
R R
(0))
E {0,
R 2 R (x)
pmm
sin
(32)
L
On the Neumann boundary condition, the eigenvalue problem equation is
d R
- R
RR
(0, L)
(33)
d de
1==0=
d
== O
T E {0, L}
de
pm
R
Mi
= COS
Mit
L Ø
(34)
For the eigenvalue problem in (s). the sectional surface is a closed ball with radius Sn- The Laplace-Belin Beltram operator As.s 2 A8.1, where Ag,1 is the Saplace-Beltran operator the
unit ball, under the polar coordinate (r, (,0),r= r [0, 1).0 0 e 1n
n- ②
AB p--1 Dr
p2 Agn-1
(35)
0r
25

---

Using separate variable method, let B = R(r)@(d), the eigenvalue problem equation is:
nn dR
R
dr A .0 = =1= ReO
0
(36)
pd-1 dr
Dividing θ and let ( = (0), where (0) is the spherical harmonics such that
g Y - k:k + 2)YL
(37)
Denote 2% = =k(k + 1 2), we have
2 dR² dr2
(n 1)r dR
+
+ -20
(38)
dr
Let R(r) =-==== w()), then
d dw dr
+
+ (,
? (k
n2 2
)² )w
(39)
dr
Set 2 = Vo we have the Bessel's different equation:
ddw dw
n 2
2x dz (2² (lc
(40)
2
Thus, R(r) - Ju V Ir, rr where v = k + n-2 is the order of the Bessel function Jv.
2
For the Dirichlet boundary condition, it satisfies
R(1) 0 0 μr pr E0.0
(41)
where juze the f-th zeros of Ju. The eigenfunction and eigenvalues of Beo is:
P1
Ben
Juue
Beo E.k
r =22 Ju
Jue
r
(0)
(42)
ED
For the Neumann boundary condition, satisfies
B.1 R1(1) = + H = u,e:
(43)
where Vh is the 8-th zeros of the derivative of jv- The eigenfunction and eigenvalues of Beo is:
Pg
Brg
Beo Vek
-r- 2 Jv Eo
)
(2)
(44)
E0
Above all, the eigenvalues of S = [0, I.] x Bro are
X D
m
mi
Jule
2
(45)
L
EO
Ju.t
2
N
mm
(46)
m,
L
Eo
Since for the Dirichlet boundary condition, the spectral gap X = -
)
[mm 50
2
the decay of
-2) [2.1 )² is determined by = for the Neumann boundary condition, the spectral
gap is N (7) 2 + %6.0
(E)² the decay of e AM is determined by e -
The second case Consider the radius function e(s) = EO (c 4)) 40
Eo cosh - 1
for a > 0, E j0, L). Since the radius of B depends on the variable in R, not overlay the solution on each component to get the eigenvalues. But the separate variable still working. Let I 2. the Doolacian--eetrann operator on S is
0²
1
As 013
Eo cosh al AB,1
(47)
26

---

Thus, let 2i (r) (r, the eigenvalue equation is:
d X
Y
XA
(48)
dl?
S (al)
Dividing XY, we have
1 d2x
AB, Y
+
-
(49)
X
dl2
og (al) Y
Set Y to be the eigenfunction of AB,1 as in the first case, we have
x
(rs
15,11
x=0
(50)
dl2
of cosh?(al)
Take z = tanh al,
d
d
a(1 22)
cosh?(al)
dz
dz
d
d²(1 - 222 dc
20²²(1 - -2²) dz
d12
dz2
22
dxx
2a²2(1 - 2²2 dx
11.1 - 22)
7 a²(1
22
+
S
X =
dz2
dz
=/
X
dX
1
1
(1
22
X = 0,
(51)
dz
dz
d²(1 22)
which is the associated Legendre differential equation:
dx
dXX
m² [((+1)
(1
=²)
2z
x
(52)
d=
22
with E({+ =
8. a
m² =
2 o.,
where m are the degree and order of the associated Legendre
polynomial, respectively.
We obtain the solution
X(x) = C. + C2OF X(1)= = P." (tanh(al)) + C2Q2" C2 (tanh(al))
(53)
Wh is the associated Legendre polynomials, Q is Legendre function of the second kind. Therefore, for the Dirichlet boundary condition,
L X(O) (Eo cosh a 2
L X(L)Y cosh a - 0) =
(54)
(- jun so cush
We find that the spectral gap X mainly relates to
since sa L, have
2
Ju,1 Eo cosh a
x
(55)
for the Neumann boundary condition,
X'( cosh
0) + X(O) cosh a
- 0) 0
2
L
I
(L) cosh a
0) + X(LYY (Eo cosh a
2 0) = O,
(56)
2
the spectral gap N mainly relates to
j.o
16 Ea cosh
meaning that
En ao
Jv.o En cosh o
N
(57)
27

---

B.4 Proofs of Corollary 5.2
Corollary 5.2 (Adaptivity of Robin Condition). For E(s) : |0. - (0,8) and L 8 for a small
5 > O, the spectral gaps X², x", X of the Dirichlet condition, Neumann condition, and no boundary
have the following order:
For E(s) = Eu, A 2 A
For e(s) 5o cosh a(s 4), if L is fixed, then X N A Z A: Eo is fixed, then
X2 A AN
Proof. From Cheeger and Buser's inequality (Theorem 4.1 if the manifold is closed, the spectral gap of its Laplace- Beltrami operator inf en-1 when taking as a submanifold embedded in closed manifold.
Laplace-Beltrami
For (s)) Eg. since Eo is small, Eo² will be large, and = will be small, thus we have the order
A
For {()) = én cosh a(s )) from the proofs of Theorem 5.1 since fu,1 > ju.o. we have A > A- If L is fixed, since Eg" - will be large, A > x >; is fixed, since L >>>>> EO. cosh -2 a will be much more smaller than o -0 then À 2 X P A
B.5 Proofs of Lemma 5.3
Lemma 5.3
(Oversmoothing under Source Terms). For the nonhomogeneous heat equation
0,u x Agu(t, a)) f(t, with source term att,x)==x =
(t)x((()) and initial condition 0. regardless of the existence of boundary condition, there exist some
x) <(x)
parameters {a; 3 > 0} satisfying the convergence condition such that
dB: (1 a, + Ar(3 + (3; + +t) B,(0)
dt
Then, the Dirichlet energy will decay polynomially w.r. time as
Dirlua]
Σ :=1
1
(8: + 2)2
Σ 1=1
(1+
A )81-a.
2 - ai
Proof. Consider the nonhomogeneous heat equation:
0,u(t,z) 2)) + f(t
x intM,t> I 0M,t> 0 x M,
h(x) =0 =(0,z)=00 o(x).
(58)
The solution is
u((,2) = 1/' J. - s,,,8, vol /
H(1, x, y))(() vol
(59)
Let [(1,x) -3 (.,,(00))()))) (.(1 = ti), oxx) = E( and e = de). Define
ul x1, = (-' / H(l -1,, (8. (x)
/t
(60)
(t, x) = [(x H(t, x, v) volu(1)
(61)
Then
u (t,x) = 1''
Σ
8
e A. () (1
Σ (((o))())) volu(y)ds
M
-x.(1=>) (3(5)
e-xit /' (Sds3())
Σ
(62)
0=0
28

---

Aet (xds(())) S.w (s(o)s(()) vol (
(1, =
1=0
=
Ge Act (1)))s
(63)
2=0
(64)
For Dirichlet energy, we have
Dir[ue] = 2 /// llgrad uel? vol. Dir[ut] Dir[uf] + /.d (grad ut, grad ugiy Volm
(65)
For each item, apply the divergence theorem or Green's first identity,
1 Dir[u!] - /// ut Au VOlm 2
B((() (,) Ast -e- S/¹ ci dB,
ds
ds
(66)
Dir[u = /
u Ant Volm = Σ
2
-
(67)
M
1=1
/ M
(grad ut, grad uz) dvolm =- 1 uf o volm
Ge det Bi(t) - 3:(00)- Act c Art 1-" cdio d3: ds
-
ds
(68)
If (() satisfies
(0)
(69)
dB (1 + A, + +)) + +t
for 0 < by <1,a3 2, i.e.
B,(t) \a(b; + 1)2-a.
+ (b: +1) (1 dxb,
0. b.-01
(70)
- a;
as
Then,
Act (- edra dB;
B[u
Σ X;
B,(1) ---
ds ds
i=1
(b; + +1)2 - -(1+
dxbs bl-aa
Σ
(71)
2 - 0
2 - aj
i=1
So the decay of the Dirichlet energy is mainly determined by
8 1 a3
(b: + 1)2-aa
which is polynomially decreasing.
B.6 Prool's of Theorem 5.4
Theorem 5.4 (Equivalence.. For the homogeneous heat equation d.u(t, x) = Agu(t, x),, x E intM with a nonhomogeneous boundary condition of h(x) xt,, E QM and initial condition u(O, x)) o(x), t O, there exists a function w(t, x) MM + E. such that h w = y in a.M By w. Eq. (12) is equivalent to the nonhomogeneous heat equation satisfying Lemma 5.3
{
(, a)) = A,,(1, x)) + [(w), h(()) 0, v(0, x) o(x) - 20,xx),
x E inIM, L 1> 0 E aM, >
x E M, t = 0 (The initial condition),
where I'(w) = A wtt x) (tw(txx)
29

---

Proof. Introducing an auxiliary function v such that h o = 0 in 0.M. Then.
{
: - A
dv 0,ú 0.
8,u(t, xx) = A (t, x) + A w(t a,w(t,a)) Given the linearity of all three types of boundary condition, we define
(72)
['w)
wtt, x) (t,
(73)
which satisfies the condition in Lemma 5.3 on intM.
The equation can be converted into the form in Lemma
5.3
{
0,v(L, x) = (4)(( + ((w), v0, = 6(x) w00,z), h(z) = 0,
I E intM, 1>0 0 IE M, =0 TE 0., t t>
(74)
B.7 Proofs of Lemma 6.2
(Solution to Heat Equation System). Let D. U and V denote the diagonal, upper and lower matrix of L, respectively. Accordingly to the Jacobi method, the matrix form for the k-th iteration is derived as follows,
Lemma 6.2
diag(a,) aaxX' ;0))),)) (3)) 3(x (K): -x))) (k)))))
(75)
X (k++1) D (V + ()) DT
(76)
Let 1= I(2 E S) be an indicator, d; d, 1,) + (21, - 1) Ejmi Ij. and pi = L
[D UIX(
Σ, Vá.
1
[D v) put(1-pill En- 1
(77)
vdd
Vdl
Proof. Merging the boundary condition and the steady solution, we have
Lg.s
Lg,s (iag(o,)aas,a)
X5
F r ass
Xas
=
=
(78)
Now, we use the Jacobi method to solve this nonlinear equation. The diagonal matrix is
Is.s Oas.s
Os.as
D =
(79)
diag(a;) (iag(a;)aas,as
The lower diagonal and upper diagonal matrices are
A low S.8
Os,a
U
S,8 Oas.s
up A
Ls,0s Oas,as
(80)
diag (3) Las.s
Oas,0s
For the k-th iteration,
diag(a a (xx 00w,, diag 3(X " wR), (X
x :
(81)
x D =D- + X DD'T
(82)
The (injr- of D Vis is
i J S ES . j~ 08,j E as ji E 08,j ES
DD D-
(83)
A. o: d
else
The (i, -e-etry of D U
j,i E S.j i j-jie 0S as i j.i j.j else
(D- (D-
(84)
30

---

B.8 Proofs of Theorem 6.3
Before proof, we first begin with the following lemma.
Lemma B.1 [41. For the matrix function [T(X))ı = Tiş (2x.). the spectral radius p < 1,
then
T(X)* (I-T(X))
(85)
A=
Theorem 6.3 (Distance Independence). of information transport
Given two nodes vs and vj with distance K, the measure
0x: dzy
(K)
(Ex K k=0 [D-1 (V (V+ UJ)**
S
CK
0x
where Ck is constant related to the GBN layer. As K + co, K.
is independent of the distance 8my
Proof. We give the proof under the scalar-valued case, the vector-valued case can be proved similarly. Denote Tú = D-11g (V + U) and b; -D (D-1r). then Eq. (18) can be represented element-wise
as
Σ Tijso(Et1)) (2)(1) + bi (z.
(k+1)
(86)
for k 2 0. Now prove the conclusion
dx (k)
s Cn
+ Tig + Σ Σ
TimmT Timim- ... Tizú)
(87)
0x,
m jmsenaa
by induction. For = 1, we have
x =0 Eijop(l (1zz) bi (xi)
(88)
jui
The Jacobian is
Oz:
(1)
0'
ÖTi dr:
(xz)) + TTijo(( (155) Or. Oz,
+
bb. dr:
Ora dz;
Oly v0 (1) (xz)088 + +1
ab. dis
+
Oes
Der:
Tig (xx) +
ab:
dij + 0' (0000(x))))) Te
dx.
Oz;
< (6 + TTy).
(89)
where Ci = max ssu 0' ेे. y (1) (m,))
ar,
ab. y2.
sup 0'' (x))))
+
Suppose Eq. 87 holds for k = K, i.c.,
(k)
K
< (r( + +Ty + Σ Σ
Titm Timm Temim- ............. T..s)
(90)
dr,
Then, for h: = K + 1, by the chain rule, we have
Or (K+1)
Oz (K+1)
Oz (K) 11
dx 0x (K+1)
Oz (K)
Σ (K)
jx11
(91)
0x;
Ox
Our (K)
Oz;
JK+1
31

---

dx. 0x(K+1))
0T 11
dx (K)
(k)
(x
(a Tixx 10 (k* ((2)))
ab.
dx (k))
0x (x(
da [K]
[K]
Ox Oxp
(K)
dx jx+1
(K)
jx++1
Tiiic 40 (KK+1)
+ ab 6AgK
(() (1 (K)
"j(t )oigets + Tix ( kKK+)) (2r
(K)
Ou! (K)
Ox,
(k)
UTijKt lolK +1) (1K) bb dx(k)
JKtt
+
8ijNti + oo' (1
(x]4)] Tijk+
0x(
S CK+I,K(OSNH Tigx-i)
(92)
where CK+1K max
sup o' STig op (k++)) (x Ba!a)
+
8b Bm,
sup a' (2((k+))) (10pcc.)))))) 1)
0xrkk (K) 0x,
I Cx((dRKLs + TRRNs E
Σ
Tx idm Timdn 1... Tizs)
(93)
m mm Jm
Substituting into Eq. 91))
Ox,
(K+1)
k
$ CCCCK+IKK
8egxes
8ixtss + Tiets +
Σ
Σ Jmmuuss
Tix+sim Imim- ... T.3s
Ox,
K
CRCKHIK
Tijx-
8iKI1 + +ixxni
Σ
Σ
Tigsiin Timan ... Tjzs
m=2 Sm
CO 2T
Σ
Σ
Teja T Timmm- ... Jai
m Jmsrnda
K+1
+
Σ Tijx Timns +
Σ
Σ
Tijm T Timi-- ... Tni)
SKIL
m= Imssenad
-CRCR+I,K00, + +TT +3 Σ
Tri
52
K
+
Tijm T Timmm-1
Tr2 +
Σ
Teim Timim-1 ... Tz2s)
1)=33 jm....j
jKL1.....2
K+1
= 9CCK 9CCCCHH1. (6. +T, + Σ Σ
Tijm
T Jimdnn ... Tzn.).
(94)
1==2 jmanngs
Let CK+1 = 9C 9C we finish the induction.
Since [a(x;)
a(a:)
< Jx: - xyy is contraction, and the Laplacian L is normalized, P(T) 1.
[[z;))
8(z,))
From Lemma B.I as K + oc.
(k)
lim +00
(I T
(95)
Ox,
where D (V U..
B.9
Derivation of GBN formalism
Set Robin condition coefficients a; = =a(x)), 3: -(xx), = -<(x)) then Robin condition becomes
0; + B, Σ
(a;; x.,)) %
(96)
jri.jSS
32

---

for each U/ E as.
Let the normalized graph Laplacian be reordered block matrix
Ls,
Lsas
L
(97)
Las,s
Las,s
Then the Robin condition can be converted into matrix form:
diag(a; Xas
diag Lossss Tas
(98)
Consider the steady solution of the nonhomogeneous heat equation. We have
S + Lasos Fs,
(99)
which is the form of Poisson's equation. Merging the above equations, we have
Lgs (
Lgas diag(o;)
Xs
Fs ras
=r
(100)
Xas
Now use the Jacobi method solve this nonlinear equation. The diagonal matrix is
Is.s Oas,s
0s,0s (lag(o;)Las.5)
D
(101)
The lower diagonal and upper diagonal matrices are
À A diag (B: Las,s
Os,as Oas,5
V
(102)
Agys
Ls,os
U
(103)
Oas.s
Ogs.5
for the k-th iteration,
diag(a,) = a (x), 0z)
(104)
diag(3.) 3(x (k), wx)
(105)
r (xx (1); m7)
(106)
x (k+1) D DV + (
(107)
The (i,j)-entry of D D- is
1 ji S,j E i jrjLie 0S.j e as jinjiie 0S.j E .els
de
(D DD-1V)
(108)
/ a
The (i, jenjryy of D D is
iN jii S.j S j.e 08,j Os
aa
D (D-UU)
(109)
i jii S,j 0s
Jayags
else
To give unified formula, we define the indicator 1, = T(i E S), then we define
d Σ I,, + (1 I1) 1,) d (1 1e) (2I: 1) Σ I jwi
(110)
33

---

Then.
18 1 (K)
(D (D= 1.
(111)
v dg j~i v vdz
[D VVx( = + (1 pi)li
Σ
1
zj
(112)
vd.
Vd.
jos
where p; dz.
&,
Since [D [D-1 Ti/as, can replace with the new variable T:/a: = %
Finally we get
(k+1) 4 (k)
Ps P
+1+
P.)L
Σ
47 1
(k)
+
(113)
de jost dj
Vd:
/d
C
Algorithm
Algorithm 1 Graph Boundary conditioned message passing Neural network (GBN)
Input:
Graph G(V.E,) A). Objective function J, Number of layers K, The activation function a.
MLPs with learnable parameters a(:; 0a), {-; 0g), 7(: 0y), <(-,)) (P(,,)))
Output: Node representations X ( Model parameters.
1: while not converge do
2: Input initial value ( (x)
3: Compute soft weights for being boundary node by I, <(x;; n));
4: for each layer k = K do
Compute coefficients a; - awx (k- (k-1), 0,), B = 3(x) (k-1), 0z), 7i = =7(x)) -7(=:--11:00)
5:
6:
Update node representations x (l) by Eq.
18
7:
end for
8: Compute the objective function J(
Y); (x)
9:
Train model parameters by Adam optimizer;
10: end while
Computational Complexity Computing boundary condition coefficients costs O(V)d), where d is the hidden layer dimension. The matrix multiplication is implemented as neighborhood aggregation of complexity O(EE). The overall complexity of K K-layer GBN is yielded as OK((V] (&))
D Datasets and Baselines
D.1 Datasets
We evaluate our method on range of benchmark datasets spanning diverse domains and structural characteristic. Summary statistics are shown in Table
WikiCS A citation graph of Wikipedia articles Computer Science. Nodes are articles with averaged word embeddings as features; edges represent hyperlinks. The goal is to classify articles into 10 subfields.
A product co- co-purchase graph focused on the "Computers" category from Amazon. Nodes represent products, edges indicate co- co-purchases, and features are bag-of-worde from reviews. The task is product category classification.
Amazon-Computer.
Coauthor-CS
co-authorship network from Microsoft Academic Graph. Nodes are authors, edges indicate collaborations, and features are derived from publication texts. The objective is to classify authors into research fields.
Texas A WebKB dataset based on webpages from the University of Texas. Nodes are webpages, edges are hyperlinks, and features come from bag-of-words. The task classify wehpages into categories like faculty, course, student.
34

---

Wisconsin Similar to Texas, but based on webpages from the University of Wisconsin. Nodes are webpages, edges are hyperlinks, and features use bag-of-words, is commonly used for evaluating models under small-scale settings.
Roman-Empire A word-level dependency graph from the "Roman Empire" Wikipedia article. Nodes are words; edges connect sequential or syntactically related words. The task is to predict the syntactic role of each word in context. The graph exhibits strong heterophily.
Amazon- RatzonnRaatins
bipartite graph of users and products from Amazon reviews. Edges represent ratings, with weights scores. Node features are extracted from review texts. The task is to predict product categories or user preferences.
Table 6: Dataset statistics. The reported number edges refers to directed edges; for undirected graphs, this count is twice the actual number of edges.
Average Degree
Node Features
Dataset
Nodes
Edges
Classes
Metric
WikiCS
11,701
431,726
36.90
300
10
Accuracy
Amazon- Conruters
13,381
491,722
35.76
767
10
Accuracy
Coauthor CS
18,333
163,788
8.93
6,805
15
Accuracy
Texas
183
650
3.55
1,703
5
Accuracy
Wisconsin
251
1030
4.10
1,703
5
Accuracy
Roman-Empire
22,662
65,854
2.91
300
18
Accuracy
Amazon-Ratings
24,492
186100
7.60
300
5
Accuracy
D.2 Baselines
GCN
employs neighborhood aggregation within the spectral domain.
incorporates the attention mechanism into graph- based learning to dynamically weigh neighbor nodes.
GAT 66
GIN 73 enhances graph learning by leveraging MLPs achieve maximum discriminative
power, mimicking the Weisfeiler-Lehman graph isomorphism test process.
DR 26 applies Delaunay triangulation to the node features to rewire the graph, creating a new topology that alters the structural properties mitigate over-squashing and over- smoothing in graph neural networks.
GIN+graphv2 [77 involves processing graph pairs using Graph Isomorphism Networks (GIN) without normalization, focusing on node and graph classification tasks. This approach applies GIN in batch setting to evaluate performance
various graph datasets.
UniFilter 27 combines low-pass and high-pass filters within each layer and adaptively integrates their embeddings. It also trains coefficient matrix measure node correlations for global aggregation.
GroxyGap 28 uses spectral graph pruning to eliminate edges causing over-squashing and over-smoothing, adjusting the graph structure for enhanced neural network performance.
Borf 39 applies Ollivier-Rieci curvature identify and mitigate over-smoothing and over-squashing in graph neural networks by analyzing and rewriting the graph edges based curvature values.
G²-GCN [46]introduces gradient gating to dynamically adjust the contribution of each node's 's gradient during training, allowing different parts of the graph to learn at varying speeds.
GREAD 15 models graph neural networks using -diffiinn process, where node features evolve through diffusion and reaction steps to capture complex graph structures and dynamics.
SWAN [24] examines oversquashing in graph neural networks through the lens of dynamical systems, analyzing how information flow and node interactions affect the network's ability to propagate information effectively.
35

---

CoBFormer [70] addresses the wer-globalizzin problem in graph transformers by selec- tively focusing on local structures and reducing the emphasis on global information, thereby improving the model's ability to capture fine-grained details.
VCR-Graphormer [1 introduces virtual connections to enable mini-batch processing in graph transformers, allowing for efficient training on large graphs by simulating connections that facilitate information exchange between nodes.
Spexphormer [49] proposes a technique to make graph transformers sparser by selec- tively retaining important connections and pruning less significant ones, aiming to improve computational efficiency without losing essential information.
HGCN 10
generalizes GAT in the Lorentz model of hyperbolic space in which the graph convolution is conducted in the tangent space.
focuses on long-range graph sequence modeling by employing selec- tive state spaces to capture distant dependencies and interactions within graph sequences, enhancing the model's ability to handle complex temporal dynamics.
Graph-mamba [67
MP investigates the impact of virtual nodes on oversquashing and node heterogeneity in graph neural networks, analyzing how virtual nodes can alter information flow and representation learning.
E
Implementation Notes
E.1
Graph transfer
We construct graph transfer datasets inspired by (Gravina et al. 2025), focusing on three types of graph structures: Line, Ring, and Crossed-Ring. Each graph within a task shares the same topology but differs in node features. Specifically, we initialize node features by sampling from a uniform distribution in the interval [0. 1). The source node is initialized with value of 1, while the target nodes are assigned a value of O. The objective is to transfer information from the source node to the target node, without considering the intermediate nodes. Each graph topology introduces distinct structural properties:
Line: A simple path graph of length n, where the source and target nodes are placed at opposite ends, resulting a shortest path of length n.
Ring: Cycles of size n, where the source and target nodes placed distance of [n/2] from each other.
Crossed- -ing: Cycles with additional "cross" edges between intermediate nodes, These edges do not reduce the shortest path between source and target, which remains [n/2]].
Figure 7 illustrates each graph structure with source target distance of n 5. In experiments, we consider distances E (3. 5, 10, 50). and use message passing neural networks (MPNNs) with depth equal to n. Unless stated otherwise, input dimension is set (regression tasks), hidden dimension to 64, and training is run for 2000 epochs. We apply node masking during training and testing to compute loss solely based on the source and the target node. We generate 1000 graphs for training, 100 for validation, and 100 for testing. Final performance is reported as the mean squared error over the test set. The architectural details and hyperparameters of our model are summarized in Table Z
Table 7: Hyperparameter settings for graph transfer task.
Dataset
hid dim
Activation
dropout
norm
Ir
w_decay
Line
64
Tanh
0
BatchNorm
1e-3
0
Ring
64
Tanh
0
BatchNorm
lc-3
Crossed-Ran Ring
64
Tanh
0
BatchNorm
le-3
0
36

---

(a) Line
(b) Ring
(c) Crossed-Ring -iined--inng
Figure 7: In all three graphs Line, Ring, and Crossed-Ring the source node "S" and target node "T" are placed five hops apart.
E.2 Further Details on Visualization
We visualize the graph transfer task in Fig. X investigate the model performance, comparing the vanilla GCN and the proposed GBN. To be specific, the experiment is conducted on the graph where two 10-node complete graphs (i.e., the source on the left numbered 14-23 and the target on the right 0-9) are connected by a line numbered 10-13 (i.e., topological bottleneck). The nodes are randomly assigned in [0, 1] in the source, while [-1, 0] the target. The node value the connecting line is "O". The task is to swap the values in the source and target components. As result, GCN results in the messages being severely "squashed" the bottleneck, as shown in the nodes numbered 9, 10, 13 and 14. In contrast, the proposed GBN allows messages to pass through the bottleneck, thanks to local bottleneck adjustment.
GCN
0.75
Original Graph
0.50
Node Feature Value
0.25
20
23
GBN
0.00
-0.25
-0.50
-0.75
Figure 8: Case Study on Graph Transfer
37

---

E.3 Hyperparameter settings
We conduct node classification experiments using 2-layer GBN network, all the datasets are available PyTorch Geometric datasets. All datasets are split into 50% training, 25% validation, and 25% testing. We report the final accuracy as the average over 10 random data splits. The same experimental setup is applied across baseline methods. For experiments on heterogeneous graphs, we utilize 5-layer model. 'he architectural details and hyperparameters are summarized in Table Learning rates are set to 3e-5, with dropout rate to 0.3, 0.2, 0.1 and hidden dimension size of 512. LayerNorm used to facilitate deeper models. All experiments are implemented using PyTorch Geometric library. The hardware is NVIDIA GeForce RTX 4090 GPU 24GB memory. and Intel Xeon Platinum 8352V CPU with 120GB RAM. Our code is publicly available at hhtps //anonymous 4open. sci eeceeen/eeNN/BeBE
Table 8: Hyperparameter settings for node classification task.
Dataset
n layers
hid dim
Activation
dropout
norm
W_ W_decay
Texas
512
GELU
0.3
LayerNorm
lc-4
Wisconsin
512
GELU
0.7
LayerNorm
le-3
0
Amazon-Rating
512
GELU
0.15
BatchNorm
3c-4
Roman- Emprre
512
GELU
0.15
LayerNorm
3c-4
Coauthor-CS
512
GELU
0.2
LayerNorm
3e-5
0
Ammpuonossuters
512
GELU
0.2
LayerNorm
3c-5
WikiCS
512
GELU
0.2
LayerNorm 3e-5
Broader Impact and Limitations
We pave the way to design deeper and better expressive MPNNs to learn graphs, offering new potentials of graph foundation models. A positive societal impact lies in the scalability of our design, allowing for the analysis on large scale real-world graphs. None of negative societal impacts we feel must be specifically highlighted. As for limitations, our work as well as typical MPNNs primarily considers the undirected graphs, while the message passing directed graphs has left to be the future work.
sophisticated
38


Reviews:
[{"review_id": "W2Hn7Puhmz", "reviewer": "Reviewer_nz6f", "summary": "The paper presents a novel local approach to tackle both oversmoothing and oversquashing in message passing neural networks (MPNNs). By integrating local Riemannian geometry, the authors design a Graph Boundary conditioned Neural network (GBN) that adaptively adjusts message passing based on local graph structures. The approach is supported by theoretical guarantees and experiments show that GBN achieves superior performance on various graph datasets.", "questions": "1. In the “Message of the Section” on line 162, it is stated that the method of increasing the spectral gap to reduce oversquashing impairs the effectiveness of message passing. However, in the “A more intuitive explanation” on line 158, it is mentioned that reducing oversquashing can be achieved by adding edges to allow more messages to flow. These two statements seem contradictory. I would like the authors to clarify whether the message passing becomes more unobstructed or more hindered when reducing oversquashing. A clear and consistent explanation would increase my evaluation of the paper's logical coherence.\n2. Are the graph rewriting operations (adding or deleting edges) and the operations for adjusting the spectral gap independent of each other? It is not clear from the paper how these two aspects interact. If the authors can elaborate on their relationship, such as whether one operation affects the other or if they can be applied simultaneously in a coordinated manner, it will enhance my understanding of the proposed approach and potentially increase the paper's score in terms of comprehensiveness.\n3. In the ablation study, when the learnable and adjustable $\\gamma$ and $\\beta$ are fixed to $\\gamma_0$ and $\\beta_0$, the accuracy does not drop significantly. I am curious about how these fixed values $\\gamma_0$ and $\\beta_0$ were selected. If there was a non-learning heuristic method used to choose them, please describe it. Additionally, if such a method was used, does it lead to a reduction in computational complexity? A detailed response on this would improve my assessment of the practicality and methodological soundness of the ablation study in the paper.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper demonstrates notable strengths in its theoretical rigor and experimental thoroughness, with theorems (e.g., 4.2, 4.3) formally guaranteeing the approach's efficacy against oversmoothing and oversquashing, and comprehensive ablation studies validating component contributions. The experimental setup is standard and reproducible, providing clear details for experts. \n\nHowever, its clarity suffers from dense theoretical notation (e.g., integral symbols and Riemannian geometry terms) that lack self-contained definitions, potentially alienating non-specialists. In significance, the work makes substantial contributions to MPNN research by addressing long-standing challenges, though its impact on broader fields remains limited. Regarding originality, while the integration of local Riemannian geometry is innovative, the paper could enhance distinctiveness by explicitly contrasting with related work (e.g., prior studies on Riemannian geometry and MPNNs cited in line 83), clarifying how the proposed GBN uniquely advances the paradigm. Strengthening these comparative analyses would solidify its claim to originality.", "was_revised": true, "final_justification": "1. The comparison to the related work in your rebuttal is good. Please consider adding it to the camera-ready version.\n2. \"both over-squashing and over-smoothing affect the effectiveness of message-passing (MPNNs).\" should be stated explicitly in your paper.\n3. Thanks for clarifying the relationship between graph rewriting and adjusting the spectral gap for me.\n4. Compared to determining $\\gamma$ and \\beta using grid search, learning $\\gamma$ and $\\beta$ through a learning approach indeed involves less computational effort, which is a good design.\nI will keep my score.", "rebuttal": "### **1. Add explicit comparison to the related work in Line 83**\n\nReferences 17, 34, 35 and 47 are curvature-guided graph rewriting methods, which mitigate over-squashing through adding and/or deleting edges guided by curvature. Different from this line of work altering the original graph structure, we maintain the original graph structure while mitigating over-squashing with theoretical guarantees.  \n\nReferences 5, 10, 30, 33 and 53 extends MPNNs to certain Riemannian manifolds, following the traditional message-passing mechanism. In contrast, we propose a new, adaptive message-passing with nonhomogeneous boundary condition to jointly mitigate over-squashing and over-smoothing.\n\n### **2. On the consistency of increasing spectral gap and adding edges w.r.t. over-squashing**\n\nNote that the topological bottleneck leads to over-squashing, but there exist other reasons resulting in over-squashing as well. (Indeed, a topological bottleneck is a sufficient but not necessary condition for causing over-squashing.)\nAlso, both over-squashing and over-smoothing affect the effectiveness of message-passing (MPNNs). \n- Adding edges, which enlarges the topological bottleneck, can be beneficial for mitigating over-squashing.\n- The increase of the spectral gap $\\lambda$ enlarges the topological bottleneck, as given in Theorem 4.1. However, the increase of spectral gap $\\lambda$ also tends to accelerate gradient vanishing (Theorem 4.2) and over-smoothing (Theorem 4.3). Accordingly, we state that the increase of spectral gap $\\lambda$ also has negative impacts on the expressiveness of MPNNs.\nThe two statements are indeed consistent, and the key point here is that the topological bottleneck is not the only reason for over-squashing.\n\nHence, over-squashing cannot be mitigated by merely increasing $\\lambda$ without considering other factors, e.g., gradient vanishing. It motivates our design of local adjustments taking into account both factors.\n\n### **3. Relationship between graph rewriting and adjusting the spectral gap**\n\nOn the one hand, graph rewriting directly alters the spectral gap $\\lambda$:\nAs in line 138 and Theorem 4.1, the spectral gap relates to the most bottlenecked region (characterized by Cheeger's constant) in a manifold or graph. The graph rewriting expands the bottlenecks to enlarge the spectral gap.\n\nOn the other hand, adjusting the spectral gap does not necessarily require graph rewriting:\nThe message bottleneck is related to the graph topology and the strategy of message passing over the topology. Also, the spectral gap can be regulated without modifying the graph topology, and we leverage such fact in our work.\n\nAs proved in Sec. 5, GBN achieves this by introducing boundary conditions, the adaptive Robin condition (Eq. 13).\n\n### **4. On $\\gamma$ and $\\beta$**\n\nIn the ablation study, the fixed values $\\gamma_0$ and $\\beta_0$ were determined through a grid search on the validation set, $\\gamma_0 \\in [0,1]$, $\\beta_0 \\in [0,2]$. This process required significant computational effort to identify the optimal values. \nIn addition, we observe that the optimal values vary across different graphs. Graphs are diverse, and the optimal boundary conditions are inherently related to the structural patterns. Therefore, we let \\gamma and \\beta be learnable in GBN."}, {"review_id": "sYeDvucCGt", "reviewer": "Reviewer_wr1V", "summary": "This paper addresses two fundamental, interconnected problems in MPNNs: oversmoothing and oversquashing.\nThe authors challenge the prevailing \"global\" approaches (e.g., graph rewriting) that aim to fix these issues by modifying the entire graph structure, often by increasing the spectral gap. Through a theoretical analysis grounded in Riemannian geometry. As an alternative, the paper proposes a \"local\" approach that refines the message-passing mechanism itself. By modeling MPNNs as solvers for a heat equation on a Riemannian manifold. This theoretical foundation leads to their proposed model, the Graph Boundary conditioned message passing Neural network (GBN).", "questions": "See weaknesses above.", "limitations": "No additional limitations are identified.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n1. The paper tackles oversmoothing and oversquashing, which are critical and well-recognized challenges that limit the depth and expressive power of modern GNNs.\n2. The authors provide theoretical analysis, connecting MPNNs to heat flow on Riemannian manifolds. \n3. GBN offers a promising direction for mitigating oversquashing without modifying the graph's topology. This is a significant advantage over conventional graph-rewiring methods, which can be computationally expensive and risk altering essential structural information.\n\n### Weaknesses\n1. The authors claim to \"put forward a local treatment and introduce the local Riemannian geometry for the first time.\" This claim is questionable, as several well-studied methods already leverage local geometric concepts. For instance, methods based on Ollivier-Ricci Curvature [1] and Forman-Ricci Curvature [2] are intrinsically local, as they operate on small neighborhoods. This undermines a central claim of the paper's novelty.\n\n2. The paper fails to compare against some highly relevant baselines. For example, PANDA [3] is another recent attempt to tackle oversquashing without altering the graph topology, making it a critical point of comparison that is missing from the evaluation.\n3. The paper's use of \"external inputs\" to combat oversmoothing appears conceptually similar to well-established techniques like initial residual connections. \n4. The paper argues that edge deletion, used by some methods to combat oversmoothing, \"hinders the information flow.\" This may be a mischaracterization of prior work [2, 4]. Methods like Spectral Graph Pruning or those using Ricci curvature typically only prune edges in overly dense regions, which is not necessarily a hindrance to overall information flow and may even be beneficial.\n5. The introduction of multiple MLPs for the boundary conditions adds a new set of hyperparameters. The paper does not explore the model's sensitivity to these choices.\n\n> References\n\n[1] Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvature\n\n[2] Mitigating Over-Smoothing and Over-Squashing using Augmentations of Forman-Ricci Curvature\n\n[3] PANDA: Expanded width-aware message passing beyond rewiring.\n\n[4] Spectral Graph Pruning Against Over-Squashing and Over-Smoothing.", "was_revised": true, "final_justification": "The authors have addressed some of my concerns, but the strength of their contribution remains limited by the fact that local Ricci curvature has already been proposed and applied in prior work (Mitigating Over-Smoothing and Over-Squashing using Augmentations of Forman-Ricci Curvature, LoG 2023). While it is novel to employ this metric within a non-rewiring framework, the core idea is not entirely new. I am maintaining a borderline rating for this paper, though my evaluation has become somewhat more positive.", "rebuttal": "### **1. On novelty and local Riemannian geometry**\nThe novelty of our work lies in that we introduce the local adjustment to message passing paradigm from the perspective of Riemannian geometry. The notion of “local” emphasizes that we locally adjust message passing via boundary condition, rather than any global criteria, e.g., spectral gap. Also, we clarify that: our theoretical contribution is not the introduction of geometric notion but the establishment of nonhomogeneous boundary condition. \n\nRicci curvature is defined on the edges and describes the connectivity over the graph. According to the definition (Eq. 4 in [1]), calculating Ricci curvature necessitates finding shortest paths between all node pairs (or sampled neighborhoods), inherently traversing the entire graph.\n\nWe recognize the effectiveness of (curvature-guided) graph rewriting methods, and consider that they are the natural solution as over-squashing is related to the topological bottlenecks in the graph structure. However, our work is inherently different from this research line:\n- Graph rewriting focuses on altering the original graph structure so that over-smoothing/over-squashing is mitigated under traditional message-passing.\n- We maintain the original graph structure but refine the message-passing paradigm to jointly mitigate over-smoothing and over-squashing.\n\nWe will paraphrase this sentence for clarity as follows:\n```\nWe introduce the local adjustment to the message passing paradigm with nonhomogeneous boundary conditions of Riemannian geometry.\n```\n\n### **2. On ICML’24 (PANDA)**\nNode Classification Performance in terms of ACC on 7 Datasets\n\n|Models|WikiCS| Computer| CS| Texas| Wisconsin|RomanEmpire|Ratings|\n|---|---|---|---|---|---|---|---|\n|PANDA|84.86±0.43|90.18±0.76|93.62±0.44|80.89±0.44|83.98±1.58|86.23±0.66|52.35±0.34|\n|GBN|86.21±0.39|91.33±0.32|95.78±0.21|85.01±6.51|86.78±3.84|89.83±0.46|53.51±0.88|\n\nThe proposed GBN consistently achieves better classification results than PANDA. \n\nPerformance on Long-range Dependence in terms of MSE\n\n|Models|Line 3|Line 5|Line 10|Line 50|\n|---|---|---|---|---|\n|PANDA|3.13e-7|5.76e-7|8.67e-7|3.71e-6|\n|GBN|2.04e-7|3.76e-7|7.51e-7|3.55e-6|\n\n|Models|ring 3|ring 5|ring 10|ring 50|\n|---|---|---|---|---|\n|PANDA|5.13e-7|6.76e-7|5.67e-6|1.21e-5|\n|GBN|2.6e-7|6.98e-7|2.13e-6|7.73e-6|\n\n|Models|CrossedRing 3|CrossedRing 5|CrossedRing 10|CrossedRing 50|\n|---|---|---|---|---|\n|PANDA|6.13e-7|1.76e-6|5.67e-6|1.21e-5|\n|GBN|4.82e-7|1.76e-6|2.74e-6|5.37e-6|\n\nThe proposed GBN presents superior information transfer ability on Line, Ring, and Cross-Ring datasets. It shows the ability to capture long-range dependence.\n\nWe will include the discussion of this insightful paper in Sec. of Related Work, and cite it as follows:\n```\nTo combat over-squashing, [PANDA] present a novel approach to select nodes with high centrality to expand in width to encapsulate the growing influx of signals from distant nodes.\n```\n\nIn addition, we would like to specify the difference between PANDA and the proposed GBN:\nPANDA changes the way of neighborhood aggregation without topological considerations, but GBN combines the (topological) boundary condition with functional behavior.\n\n### **3. Difference between external input and initial residual connection**\nOn the formulation:\nThe domain of definition is different. Concretely, the initial residual connection is uniformly applied to all nodes. In contrast, the proposed external input (the $\\gamma$-term) is exclusively defined for boundary nodes as in Definition 6.1 and Eq. 14. \nThe formulation of external input in Eq. 14 is derived from the nonhomogeneous Robin boundary condition, which is inherently different from that of previous MPNN residual connections.\n\nOn the theory and guarantees:\nResidual connections are primarily heuristic additions (e.g., identity mappings), whereas our $\\gamma$-term arises rigorously from Riemannian boundary condition in Theorem 5.4.\nThe proposed external input has theoretical guarantee. Concretely, the polynomial decay constraint for Dirichlet energy in Lemma 5.3 holds only at boundary nodes and vanishes in the interior (Remark B.6). Thus, applying external input at boundary nodes ensures the mitigation of over-smoothing.\n\n### **4. The sentence in Line 160**\nWe sincerely appreciate your comment, and will paraphrase this sentence for clarity as follows:\n“Edge deletion without careful consideration may hinder the information flow in message passing.”\n\nIndeed, we recognize the sophisticated graph rewriting techniques, and have cited [1], [2], and [4] in the Related Work as follows:\n```\nIn the line of graph rewriting, [1, 2, WWW’23] introduce edge addition-deletion algorithms in light of oversmoothing; [4] increases the spectral gap via edge deletion.\n```\n\nThough the advanced methods of carefully rewriting the graph structure are effective, it is still challenging to study the edge addition-deletion strategy. Thus, we explore an alternative direction – refine the message passing paradigm while maintaining the original structural topology and the computational complexity of traditional MPNNs.\n\n### **5. Parameter sensitivity on MLP**\nIn GBN, we utilize a 2-layer MLP with a hidden layer dimension of 256 by default. We conduct a sensitivity analysis on the hyperparameters of the layer and the hidden layer dimension, and GBN is generally robust to these hyperparameters.\n\n|Layers|hidden_dims|CS|Ratings|\n|---|---|---|---|\n|2|128|95.84±0.23|53.34±0.52|\n|2|256|95.84±0.33|53.14±0.34|\n|2|512|95.78±0.21|53.51±0.88|\n|3|128|95.59±0.32|51.22±0.33|\n|3|256|95.65±0.11|50.98±0.51|\n|3|512|95.58±0.32|50.70±0.56|\n|4|128|95.11±0.25|49.95±0.73|\n|4|256|94.97±0.24|49.22±0.78|\n|4|512|95.07±0.11|49.73±0.38|"}, {"review_id": "CtZ6mx0FAP", "reviewer": "Reviewer_QJWv", "summary": "The paper identifies that existing global remedies for oversquashing in MPNNs, specifically rewiring approaches that enlarge the graph's spectral gap, actually accelerate gradient vanishing and oversmoothing. For this, they draw on the continuous analogue of studying heat flow on Riemannian manifolds. To overcome these issues, they introduce *Graph Boundary-conditioned MPNNs* which adapt the message passing to include a learnable nonhomogenous Robin boundary condition, which can adaptively regulate information flow and mitigate both issues. They demonstrate the theoretical benefits of such a boundary condition for the continuous analogue, e.g., by analyzing Dirichlet energy decay. Empirically, the authors show that GBN outperforms a large set of baselines on standard small to medium-scale homophilic/heterophilic benchmarks, scales beyond 256 layers with no performance drop on Cora, and effectively mitigates oversquashing measured by performance on the standard graph transfer task.", "questions": "- Overall presentation and clarity of the paper should be improved, mainly self-containedness of § 6 (see sec. on Weaknesses), but also the general writing (just for example, the term \"GBN\" is introduced without explanation in the abstract, or the title of § 6 is \"GBN: A Provable Neural Architecture\").\n- Evaluation on the benchmarks from the Weaknesses section would make a stronger case for GBN.\n- The paper could dedicate more space to providing some intuition for GBN. After all, as far as I understand Eq (18) also implements some shift operator wrt. a weighted graph, whose filter response could be analyzed. Also, it would be valuable for intuition to, e.g., plot the boundary assignment $I_i = \\zeta(x_i, \\eta)$ for some specific graphs.\n- The related work section could mention some more recent approaches to achieve similar goals (such as, e.g., [2]).\n\n[2] *Unitary convolutions for learning on graphs and groups.* Bobak T. Kiani, Lukas Fesser, Melanie Weber. NeurIPS 2024.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n- To the best of my knowledge, the idea of considering such adaptive boundary conditions is novel and, in my view, a quite elegant way compared to the \"static\" graph rewiring approaches that have been proposed.\n- The method seems to introduce no significant computational overhead (i.e., scales similarly to GCNs).\n- Strong empirical performance for node classification, and the claims of mitigating oversmoothing and oversquashing are effectively verified as there is no performance degradation even with 256 layers and Dirichlet energy stays roughly constant.\n\n**Weaknesses:**\n- The main body leans heavily on Riemannian geometry (§ 5) to motivate GBN, but most of the benchmark graphs lack any clear manifold interpretation which makes the link seem somewhat loose. The resulting core GNN update in § 6 is barely discussed in the main body. Also, the fact that the boundary set is implemented dynamically via a learned, soft gate is only vaguely mentioned in the main body at lines 247-248 and only looking at the appendix/code helped clear things up for me. I understand that this might be a natural thing to do in PDE circles, but I would suspect that a GNN-focused audience might benefit from a more self-contained presentation.\n- For claiming scalability, the experiments are quite small-scale (and for the oversquashing experiment only on synthetic data). To validate (a) scalability, it could make sense to evaluate on `ogbn-{arxiv, products}`. For (b) long range dependencies, it might make sense to also evaluate on some tasks of the long range graph benchmark (such as `peptides-{func, struct}`) [1].\n\n[1] *Long Range Graph Benchmark.* Vijay Prakash Dwivedi, Ladislav Rampášek, Mikhail Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, Dominique Beaini. NeurIPS 2022.", "was_revised": true, "final_justification": "The authors resolved most of my concerns with the paper. I believe the method mitigating oversquashing without altering the graph's topology is conceptually nice and can be valuable to the community. I am confident that the inclusion of larger-scale and long range benchmarks, and an improved presentation of § 6, will improve the paper's impact. While I still believe that the lengthy motivation on manifolds is not very accessible to a graph learning audience (and maybe not necessary to understand the method), I will recommend acceptance.", "rebuttal": "### **1. Manifold interpretation of benchmark graphs**\nThe benchmark graphs are inherently connected to a Riemannian manifold. Theoretically, a graph is regarded as the discrete analogy to a certain Riemannian manifold [1]. It motivates us to study MPNN with Riemannian geometry. As an empirical observation, we take the Computer dataset for instance. Rather than Euclidean, it can be decomposed as a -1.15-curvature hyperbolic component of weight 0.61, a 0-curvature component of weight 0.18, and a +0.72-curvature hyperbolic component of weight 0.21.\n\nNote that we do not focus on the optimal embedding space or curvature distribution of the graphs, but explore the functional space over the manifold to combat over-smoothing and over-squashing.\n\n[1] Chung, F.R.K. Spectral Graph Theory. AMS, 1997.\n\n### **2. The term of GBN**\nWe will improve the presentation. The term comes from Graph Boundary Conditioned Message Passing Neural Network as in Line 228. We will explain GBN in Abstract in Line 13 as follows:\n“We design a Graph Boundary conditioned message passing Neural network (GBN) with local bottleneck adjustment”\n\n### **3. Scalability on large graphs and long-range graph benchmark**\nFor large graphs, we do the experiment on NVIDIA GeForce RTX 4090, and 16 vCPU Intel Xeon Gold 6430.\n\n|Datasets|Metric|GCN|ProxyGap| MPNN+VN| $\\text{G}^2\\text{-GCN}$|SWAN|PANDAS|GBN|\n|---|---|---|---|---|---|---|---|---|\n|ogbn-arixv|ACC| 71.53 ± 0.22| 72.02±0.76|OOM| 73.45±0.76|73.26±1.80 | 72.32±0.46|73.85±0.46|\n|ogbn-product|ACC| 80.33±0.19|OOM | OOM| 81.23±0.51| 80.98±0.31| OOM|82.40±0.32|\n|peptides-func|AP| 59.13±0.17| 65.64±0.58|66.18±0.67|62.73±0.43 |64.86±0.49 | 60.14±0.34|65.88±0.73 |\n\n\nOOM is short for Out-Of-Memory. We achieve the best node classification results on ogbn-arXiv and ogbn-product, and promising graph-level task performance on peptides-func.\n\n### **4. Updating rule in Sec. 6**\nWe do appreciate the careful review on Appendix/Code for the derivation and implementation of the GBN’s updating rule.\n\nIn addition, we would like to provide more explanation of the proposed updating rules:\n1. We first describe the behavior of the interior nodes and boundary nodes behavior in heat diffusion together. Without loss of generality, we first assume that the boundary nodes are recognized, then by reordering the nodes, we have the blocked Laplacian matrix and equation system as in Eq. (14). Then, the heat diffusion proceeds on the interior subgraphs, influenced by boundary condition, which form a linear equation in matrix form in Eq. (100), Appendix B.9.\n2. Then we use the numerical method (e.g., Jacobi method) to **iteratively solve the linear equation** in Eq. (100), the details are in Lemma 6.2. The results in Eq. (18) exactly meets **the form the traditional MPNNs** but **has different essential and more favorable properties that prevents over-smoothing and over-squashing.**\n3. To adopt learning ability, we fix the results in Lemma 6.2 with nonliear activation functions and learnable MLPs, so that we obtain the updating rules Eq. (18) which still have nice properties that prevents over-squashing by Theorem 6.3 and over-smoothing by nonhomogeneous boundary condition in Lemma 5.3 and Theorem 5.4.\n4. Now, under above framework, we need to determine which or how which a node being a boundary nodes. Since boundary condition affects a lot on its neighborhood, so we adopt a simple GCN layer (only include aggregation and MLP) and a sigmoid function to compute soft weights of indicators in Eq. (17) at the beginning phase of GBN architecture. This allows gradients to flow through the boundary detection mechanism, enabling end-to-end adaptation.\n5. To make the boundary condition more flexible and be able to learn complex graph structures, we assign different $(\\alpha, \\beta, \\gamma)$ to each boundary node. The values are computed by 2-layer MLPs.\n6. The model name GBN comes from the important tool, the boundary condition, we use to solve the over-smoothing and over-squashing problem in GNN. The complete name is Graph Neural Network with Boundary Condition.\n\n### **5. On Eq. 18**\nIt is interesting to view Eq. (18) as a graph filter. From the lens of graph signal processing, the matrix $\\mathbf{D}^{-1}(\\mathbf{V}+\\mathbf{U})$ can be treated as a local graph shift operator, which adaptively interpolates between a low-pass filter and a high-pass filter. \nThe filter's property is controlled by Robin boundary condition, i.e., each pair $(\\alpha_i, \\beta_i)$ or $p_i=\\frac{\\beta_i}{\\alpha_i}$:\n- It tends to act as a low-pass filter as $p_i$ increase, while shifting to high-pass filter if $p_i$ approaches 0. \n- For $p_i \\in (0,1)$, it is a band-pass filter that chooses intermediate frequencies to flow by.\n\n### **6. Visualization of Boundary Assignment**\nWe use the synthetic graph in the Case Study for elaboration. As shown in Fig. 1 in the supplementary material, the synthetic graph consists of two 10-node complete graphs (i.e., the source on the left of nodes 14-23 and the target on the right of nodes 0-9) with a line connecting them (nodes 10-13).\nOwing to the NeurIPS policy, we present the visualization of boundary assignment as in the table below.\n\n|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|17|18|19|20|21|22|23|24|\n|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|\n|99.99|99.99|99.99|99.99|99.99|99.99|99.99|99.99 | 100|99.98 |99.90 |98.88 |98.88 |97.87| 13.62| 19.84|19.03 |14.45 |12.95 |30.48 | 12.52|24.06 |25.67 |12.34 |\n\nNote that, the joint node 9 of the line and the right complete graph is labelled as the boundary of 100\\%, which lies in the topological bottleneck where the message passing should be locally adjusted. Note that, the nodes in the right complete graph are marked as 99.9\\%, since they are topologically equivalent and affected by node 9.\nAlso, the nodes 10-13 at the bottleneck need to adjust the information flow, and they are softly assigned as the boundary nodes.\n\n### **7. Related Work of NeurIPS’24 paper (Unitary convolutions for learning on graphs and groups).**\nWe will include the discussion of the NeurIPS’24 paper, which is an interesting work to mitigate over-smoothing with the solid theory of unitary group convolution.\n\nWe will cite it in Sec. of Related Work-Over-smoothing as follows:\n```\n[NeurIPS’24] present a novel idea to transform the global spectral distribution in each layer of MPNN, while we focus on local adjustment of MPNN via boundary conditions.\n```"}, {"review_id": "6I9ZnkcZ1G", "reviewer": "Reviewer_sXZ5", "summary": "In this submission, the authors propose to mitigate both oversmoothing and oversquashing issues of MPNNs. From the lens of Riemannian geometry, this paper begins with showing the increase of lambda leading to gradient vanishing, and thus present a message-passing paradigm of local adjustment, leveraging the proposed nonhomogeneous boundary condition. Consequently, a provable GBN is designed with the Robin condition, and is evaluated on both homophilic and heterophilic graphs.", "questions": "Q1. Link prediction performance comparison with GCN, GAT, GIN and SAGE on typical benchmark datasets such as Cora, Citeseer and CS.\n\nQ2. Does GBN need to explicitly identify the boundary nodes? Does there exist graphs having no boundary node, or to what extent? Under that case, GBN degenerates to GCN exactly? \n\nQ3. Please specify the computational overhead again the vanilla GCN.\n\nQ4. Implementation details, i.e., the initial values of boundary condition coefficients, and the neural network architecture for the indicator I.", "limitations": "yes", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths\n\nS1. The studied problem is significant given oversmoothing and oversquashing are longstanding issues in MPNNs. The authors theoretically discover the possible negative impact of globally increasing the spectral gap, and it is interesting to study the local adjustment MPNN alternatively.\n\nS2. The established theory is solid. The authors unify the MPNN formalism from Riemannian dynamics (manifold heat kernel) and, in order to jointly address the both issues, construct a nonhomogeneous boundary condition on the manifold with rigorous elaboration. No error is detected in the proof.\n\nS3. The proposed GBN is novel and its complexity is the same as vanilla GCN. The authors design a new message passing paradigm based on nonhomogeneous Robin condition with theoretical guarantees. \n\nS4. The experiments on homophilic and heterophilic graphs are convincing. The authors evaluate the ability of GBN against oversmoothing and oversquashing, and show model performance in very deep network. Codes are available.\n\nWeaknesses\n\nW1. The authors give the time complexity comparison with some baselines, while GraphNormv2, G2-GCN and SWAN are not listed.\n\nW2. Further details should be provided in the paper, e.g., is Lemma 5.3 only gives an existence about the solution of over-smoothing? See Q3. The theory in this paper is not friendly to the readers not familiar with Riemannian dynamics and PDEs.", "was_revised": true, "final_justification": "After reading the authors’ responses and other reviewers’ comments, I confirm that the proposed GBN mitigates both oversmoothing and oversquashing while maintaining the computational complexity of conventional GCN yet not altering the original topology. \n\nThus, this submission shows a new promising direction on MPNN. I vote for the acceptance and raise my scores accordingly.", "rebuttal": "### **1. Time complexity comparison**\n|Model|Complexity|\n|---|---|\n|GraphNormv2|$O(L\\cdot(\\lvert \\mathcal{V} \\rvert + \\lvert \\mathcal{E} \\rvert))$|\n|G2-GCN|$O(T\\cdot(\\lvert \\mathcal{V} \\rvert + \\lvert \\mathcal{E} \\rvert))$|\n|SWAN|$O(T\\cdot(\\lvert \\mathcal{V} \\rvert + \\lvert \\mathcal{E} \\rvert))$|\n|GBN|$O(L\\cdot(\\lvert \\mathcal{V} \\rvert + \\lvert \\mathcal{E} \\rvert))$|\n\n$T$ is the steps of ODE, $L$ is the number of layers. GBN has the same time complexity as GraphNormv2. \n\n### **2. On Lemma 5.3**\nLemma 5.3 claims that there exists some source term to combat over-smoothing, so that we can learn such source term with an MLP, supporting our design.\n\n### **3. Link prediction performance comparison to traditional MPNNs**\nWe show the link prediction results in terms of AUC (\\%).  \n\n|Model|Cora|Citeseer|CS|\n|---|---|---|---|\n|GCN|90.11(0.51)|90.16(0.49)|92.71(0.63)|\n|GAT|92.55(0.49)|90.32(0.36)|92.80(0.75)|\n|SAGE|90.02(0.55)|91.18(0.22)|92.44(0.76)|\n|GIN|91.02(0.37)|90.06(0.37)|91.58(0.46)|\n|GBN|97.93(0.44)|98.26(0.56)|98.21(0.34)|\n\nThe proposed GBN consistently achieves the best link prediction results on Cora, Citeseer and CS datasets, and receives at least 5\\% performance gain compared to traditional MPNNs.\n\n### **4. Boundary nodes and the connection to GCN**\nWe specify that the proposed GBN does not need to explicit identify the boundary nodes, but it is equipped with a neural boundary indicator adopting the soft assignment. That is, the boundary nodes are jointly learned with the model.\n\nThere exist special cases of graphs without boundary nodes, e.g., a complete graph where each node is connected to all the other nodes. The soft indicator approaches to $0$ for all the nodes. \n\nWe emphasize that GBN is applicable to any graphs, regardless of the existence of boundary nodes, since we locally adjust the message-passing at the boundary nodes with soft assignment.\nAlso, the proposed GBN recovers the vanilla GCN when $\\gamma$ and $\\beta$ are eliminated.\n\n### **5. Computational overhead against the vanilla GCN**\nThe computational complexity of the proposed GBN is $\\mathcal O(\\|\\mathcal V\\|+\\|\\mathcal E\\|)$, which is the same as the vanilla GCN, where $\\mathcal O(\\|\\mathcal V\\|)$ is for feature transformation and $\\mathcal O(\\|\\mathcal E\\|)$ for aggregation. $\\mathcal V$ and $\\mathcal E$ denote the node set and edge set, respectively.\n\nThat is, we jointly mitigate over-smoothing and over-squashing via a new message-passing paradigm grounded on Riemannian boundary condition with no computational overhead.\n\n### **6. Implementation details**\n1. For the initial values of boundary condition coefficients, $\\gamma$ and $\\beta$ are given as 2-layer MLPs. We do not need to explicitly construct $\\alpha$, since $\\alpha$ is nonzero, and can be divided by both $\\gamma$ and $\\beta$. Thus, $\\gamma$ and $\\beta$ are randomly initialized and jointly learned with the model.\n\n2. For the neural architecture of the indicator, the indicator is a learnable function to determine whether or not the node is on the boundary, and it needs the neighborhood information for the boundary judgment. Accordingly, we conduct feature mapping and aggregation. Then, a sigmoid function is utilized to get the soft assignment values to identify the boundary nodes. This indicator only computes once in the beginning."}]

Author rebuttal:

Meta-review: This paper introduces a method called GBN to overcome oversmoothing and oversquashing in graph neural networks, with theoretical underpinnings and strong empirical performance (I find the improved performance on Cora as depth increases a notable accomplishment). Reviewers are anonmyous in recommending acceptance, as do I. 

I request that the authors address the concerns voiced by the reviewers in the camera ready version, mostly related to more comprehensive discussion of related work and spacing issues.
Decision: Accept (poster)