Towards Dynamic Message Passing on Graphs
Authors: Junshu Sun
Chenxue Yang
Xiangyang Ji
Qingming Huang
Shuhui Wang
Venue: NeurIPS 2024 poster (2024)
Keywords: Graph Neural Networks
Graph Representation Learning
Node Classification
Graph Classification
Message Passing
Primary area: graph_neural_networks

Abstract: Message passing plays a vital role in graph neural networks (GNNs) for effective feature learning. However, the over-reliance on input topology diminishes the efficacy of message passing and restricts the ability of GNNs. Despite efforts to mitigate the reliance, existing study encounters message-passing bottlenecks or high computational expense problems, which invokes the demands for flexible message passing with low complexity. In this paper, we propose a novel dynamic message-passing mechanism for GNNs. It projects graph nodes and learnable pseudo nodes into a common space with measurable spatial relations between them. With nodes moving in the space, their evolving relations facilitate flexible pathway construction for a dynamic message-passing process. Associating pseudo nodes to input graphs with their measured relations, graph nodes can communicate with each other intermediately through pseudo nodes under linear complexity. We further develop a GNN model named $\mathtt{N^2}$ based on our dynamic message-passing mechanism. $\mathtt{N^2}$ employs a single recurrent layer to recursively generate the displacements of nodes and construct optimal dynamic pathways. Evaluation on eighteen benchmarks demonstrates the superior performance of $\mathtt{N^2}$ over popular GNNs. $\mathtt{N^2}$ successfully scales to large-scale benchmarks and requires significantly fewer parameters for graph classification with the shared recurrent layer.

Towards Dynamic Message Passing on Graphs
Junshu Sun 1.2 Chenxue Yang² Xiangyang Ji Qingming Huang
Shuhui Wang 1,5- IIstitutee of Computing Technology, CAS Uniiersstyy Chinese Academy of Sciences "Agricultrre Information Institute, CAAS "Tsinghua University *Peng Cheng Laboratory
(sunjunshu21s wangshuhuil@ict.com ac.
yangchenxue@caas.co en xyji@tsinghis edu. quhuang@ucas.com ac. cn
Abstract
Message passing plays a vital role in graph neural networks (GNNs) for effective feature learning. However, the over-reliance on input topology diminishes the efficacy message passing and restricts the ability of GNNs. Despite efforts mitigate the reliance, existing study encounters message-passen passing bottlenecks high computational expense problems, which invokes the demands for flexible message passing with low complexity. In this paper, we propose novel dynamic message-passing mechanism for GNNs. It projects graph nodes and learnable pseudo nodes into common space with measurable spatial relations between them. With nodes moving in the space, their evolving relations facilitate flexible pathway construction for dynamic pesssage-passing process. Associating pseudo nodes to input graphs with their measured relations, graph nodes can communicate with each other intermediately through pseudo nodes under linear complexity. We further develop a GNN model named N2 based on our dynamic peessage-passing mechanism. N employs single recurrent layer recursively generate the displacements of nodes and construct optimal dynamic pathways. Evaluation on eighteen benchmarks demonstrates the superior performance of N over popular GNNs. N successfully scales to large-scale benchmarks and requires significantly fewer parameters for graph classification with the shared recurrent layer.
Introduction
The inherent irregular structure of graphs poses nontriv- ial challenges in graph learning [77]. To enable effective learning graphs, graph neural networks (GNNs) 33 64
Uniform pathway
have been specifically designed for graph-structured data. Within GNN models, message passing serves crucial function in extracting informative graph features [22
63
Dynamic pathway
The vanilla message passing [33] (66) applies node-centric aggregation constrained between the adjacent nodes. During this aggregation process, central nodes access their neigh- bors in an isotropic manner [29] and aggregate multi-hop features iteratively. In consequence, the vanilla message passing relies heavily on the input graph structure, leading issues
Olewh-gaahhooo node: class1 gaph.ndde
A paoudo node
over-smoothing [46] or over-squashing
on GNNs.
Figure 1: Comparison between different connection patterns for pseudo nodes and graph nodes.
To further improve the effectiveness of GNNs for graph representation learning, one straightforward solution is to
"Corresponding author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

decouple message pathways from the input graph structure. Following this direction. methods [19 12 have been proposed to perform message passing beyond input structures for global information exchange. Some methods directly model the pairwise relation between nodes 72 35
but the dense relation causes high computational and space complexity. Other methods incorporate pseudo nodes connected with all the graph nodes to serve as message pathways [22 30 42 However, these models employ uniform pathways, i.e., each pseudo node is connected to all the graph nodes with equal weights, as illustrated at the top of Fig. 1 In consequence, an overwhelming number of node features are squashed equally into pseudo nodes, leading to information bottlenecks on pseudo nodes for message passing and less discriminative representations for downstream tasks [57].
The above limitations call for message passing with flexible pathways and low complexity. In this paper, we propose a novel dynamic m mechanism. To construct flexible pathways, our method measures the specific spatial relations between nodes across time and gives rise to dynamic pathways, as illustrated at the bottom of Fig. [ To reduce complexity, learnable pseudo nodes are introduced as message-passingg proxies between pairs of graph nodes.
Specifically, both graph nodes and pseudo nodes are embedded in a common space with measurable spatial relations between them. By moving nodes in the space, their measured relations evolve accordingly, facilitating a dynamic message-passing process with flexibility. Regarding the measured relation as pseudo edges, the message passing on the input graphs can be extended to pseudo nodes. As result, graph nodes can communicate with each other intermediately through pseudo nodes, free from dense relation modeling.
To achieve this dynamic process, we further develop a GNN model named N based on our graph Nodes and pseudo Nodes mechanism for message passing. N2 incorporates recurrent layer to parameterize the displacements of graph nodes and pseudo nodes in the common space. With both types of nodes moving in the common space, N2 measures the actively changing spatial relations and constructs evolving pathways for dynamic message passing.
Our contributions summarized as follows. First, we design flexible and low-complexity message- paassgg-passing mechanism from a new perspective, where dynamic message pathways are built upon evolving spatial relations between nodes. Second, we develop novel GNN model named N² to achieve dynamic message passing, which employs a recurrent layer to parameterize the evolutionary displacements of nodes. Third, we demonstrate the advantages of N eighteen real-world benchmarks, where N2 achieves superior performance. Codes are available at hhtpss //github htwp/hu..ooomeeeeeooomoeoeeeeeee somm/uunjss///2
2 Related Work
Flexible message passing on graphs. In pursuit of expressive operators for graph learning, methods
propose to approximate diverse filters with parameterized polynomials [3 [4]. However, due to the prohibitive computational complexity of higher-order polynomials, these methods [33] 71 are constrained with lower orders and only perform local aggregation graphs. This constrained process couples message passing with input topology and contains inherent limitations, including over-smoothing [39 46 and over-squashig 2 60] To overcome these limitations, some works try
to decouple message passing from input topology and introduce alternate pathways, including edge
shortcuts 12 pseudo nodes 42 571. and graph pooling operations 20 53 74.
By adding edge shortcuts, methods aim to improve the message- passing efficiency on graphs. These methods can relieve certain bottlenecks on the input graphs [2] 50 60) and aggregate multi-hop information during message passing [1 24). Notably, we categorize graph structure learning meth- into the edge shorteut paradigm, which constructs message pathways by modeling edge connectivity between nodes. While edge shortcuts refine local connections, pseudo nodes di- rectly enable global message passing. However, the pseudo nodes in prior works employ uniform pathways to connect with graph nodes, which become bottlenecks in message passing [57] and limit efficient global communication. Unlike these works, 2 models dynamic interactions between graph nodes and pseudo nodes, with edge weights varying flexibly across them.
ods [79 31 65 76
Another line of effort in decoupling message passing from input topology is hierarchical GNNs. These methods [53 74 learn multi-scale graph features through iterative graph pooling, i.e., node clustering or node drop. Node clustering [73, 3) learns soft assignment matrices to aggregate nodes into coarser

---

ranks and selects salient subsets to prune less critical nodes. Different from graph pooling methods, N performs both local and global message passing in each recursive step, avoiding information loss in coarser graphs [67]
levels. On the other hand, node drop 20 37
Reducing complexity for global message passing. Self-attention 12 that models pairwise relations between nodes can be seen as message passing on fully connected graphs. However, dense attention requires quadratic space and computational complexity, which intractable for large-scale graphs. In order to scale attention- global message passing to larger graphs, recent methods propose to approximate dense attention through expander graphs [57], kernel functions [69] and diffusion [68]. One similar work [7] to ours proves that message-passing passing layers with single pseudo node can approximate dense attention. In this paper, follow a contrary thread and develop N with single shared message passing layer and multiple pseudo nodes. Each pseudo node interacts dynamically with graph nodes, avoiding becoming message-passing bottlenecks as the uniform connected pattern
Recurrent layer for graph learning. Scarselli et al. [54] first employ recurrent layer update node features recursively. According to Banach's 's fixed point theorem [ implementing the recurrent layer a contraction mapping guarantees the existence of unique fixed point representation for any input graph, towards which the recursive updates converge. However, their contraction mapping formulation is apoloogydepenndee incurring over-smoothing as the number of recursive steps increases. In contrast, the recurrent layer in N2 decouples message passing from input topology. empowering flexible communication between graph nodes.
Common State Space
Proximity Measurement (O,
project
project
Fau
9u
F₁
Mesuae Stargh
4xx
input graph
I
Predmiy
class-0/1 griph node
pacudo node
message passing
projected node
leamable weight
Figure Dynamic pessage-ppsssngg pathway construction in common state space. Graph nodes and pseudo nodes interact actively in the common state space, constructing dynamic message pathways through proximity measurement. empirical model analysis, pseudo nodes tend to be attracted toward distinct graph node cluster.
3 Towards Dynamic Message Passing
Our dynamic message- pasgggggagingggggg mechanism parameterizes message pathways with measurable relations between nodes in a common space. The displacements of nodes in the space give rise to evolving relations. As result, the message-passing process also changes dynamically. This section defines the common space tailored for the dynamic saataage-passigg process, where pseudo nodes are employed to reduce the computational complexity. The next section demonstrates how N learns the displacements of nodes towards the dynamic process.
3.1 Preliminaries
Notations. Let G (V,E) be graph, where V {u1," ........,, vn) denotes the node set of size and (Con.e, by E (e,)) denotes the edge set of size m. N((-) denotes the one-hop neighbor set of a given node. Each node E corresponds to a feature vector x, E I where is the number of features. Let X (X xx..) n be the node feature matrix composed feature vectors. Let E E Rexxxde be the edge feature matrix with d, features. E.j,- en,." Idd
Parameterize pathways as shared functions. When introducing pseudo nodes message passing, uniform pathways 22 42 directly parameterize the edge weights between pairs of graph nodes and

---

pseudo nodes. Specifying different weights for each pair entails a parameter count scaling to the number of graph nodes. To ensure a tractable number of parameters for various scales of imput graphs, we gain inspiration from DyN 48 distinctive neural network model that directly models neurons, The connection weights in DyN are parameterized with path integral function given the spatial coordinates of neurons. By sharing the integral function across neurons, DyN circumvents the need for heavy parameters. Drawing an analogy between neurons and nodes, we can also parameterize relations between nodes as a shared function.
instead of learning connection weights as conventional approaches [6
3.2 Common State Space
In light of DyN, we propose to unify graph nodes and pseudo nodes in common state space S C R and define their spatial proximity with a shared measurement function. This function measures the relations between pairs of nodes, enabling the construction of dynamic message pathways. Here, we borrow the concept of state from prior works, such as DyN and LSTM [26], to denote the learned descriptive embedding of nodes. Examples of the information encoded in the states include node features and local topology. The states of node identify its spatial coordinate in the state space. For more discussion on "state space", please refer to Appendix A
Embedded node states. Given pseudo node set {wi, (nn.) of size [ = np. we embed pseudo nodes in the state space S as learnable parameters = (Fay:" .Tunp ) E R=,,0, These learnable elements are named "pseudo nodes" align with "graph nodes" from inputs. Pseudo nodes can be associated with input graphs through pseudo edges and participate in the message passing between graph nodes. We will elaborate on this association after introducing the spatial proximity measurement in the state space. Given the graph node set V with feature matrix X, we have graph node states Q = (qi, 9x.) f(X) E Raxy, where f RRd + S is a permutation equivariant function. Displacements of a node in the state space signify shifts in its states, i.e., the learned descriptive embeddings. The objective of a GNN is to model the true distribution of graph nodes in the state space, wherein nodes with similar features obtain proximal embeddings. In the following, we refer to both graph nodes and pseudo nodes collectively as embedded nodes.
Proximity measurement. To model complex relations, we assume that the embedded nodes have a non-linear relationship the state space S. However, modeling non-linearit, via operations such as path integral can be computationally complex. To address this problem, we approximate non-linear relations with piece-wise weighted inner products. Taking proximity measurement between graph nodes as an example, each node is divided into l pieces with their proximity formulated as
v (qu: 9o²) = Σ X:qoo Aiv' q. = (q,,
(1)
where A; is a learnable parameter, NL(-) denotes a non-linear function with linear mapping followed by LeakyReLU()). ( is termed as proximity instead of distance because it ranges in IR. The spatial proximity is weighted with different inner product similarity between k pairs of pieces to approximate complex relations. We conduct ablation studies on the number of pieces i in Appendix D.5
3.3 Associating Pseudo Nodes to Input Graphs
Pseudo edges. Based on the measurable proximity between the embedded nodes, we now introduce how to obtain pseudo edges and thus associate pseudo nodes input graphs. For each pseudo node u E l embedded at r, in the state space, it has pseudo edges with any pseudo node u' E ll and graph node E V, where pseudo edge weights eu,a' and Gu,u can be formulated as the proximity
eu,u' (a Tw), Gu,v = ( qu).
(2)
Messages for embedded nodes. Following the common practice in GNNs [63]. interaction between the embedded nodes as message passing. To achieve this, both graph node v and pseudo node learn their messages m., m, Bdd to be passed in the state space. As a result, graph node e and pseudo node w in the state space can be further described as
interpret the
(Fu, Mas {eu.w: Cw /w E (U (.UV) V)H), V A (qo, My, (Eo,ws e,, // E (N(v) U())).
(3)

---

The messages of graph nodes are initialized with node features, Each graph edge eu,er is characterized by its edge feature Cn,p!
3.4 Dynamic Message Passing in the State Space
Given the measured proximity as message pathways and the messages to be passed, the embedded nodes can interact with each other through message passing. Specifically, the interactions between graph nodes are performed in both local and global scope.
Global message passing. In the state space, graph nodes perform global message passing based on their states, where pseudo nodes serve as proxies. Given graph node states Q R pseudo- node states R E Rº,Xg x and graph node messages M (m...-. message-passing process can be formulated as (Diffuse)
m,m)) E Raxd the global
G = E
EV = Cu.,y = (R.... Q₁.))
(4)
(Refine)
G EPPG,
EPP Eu, 1h (B. Ry.);
AR = (G)) M = NL(LG() (G),
(Collect)
M
Ej Cr.,uy 10 (Q;... RR+ j.))
(6)
where E E 12 denotes the edge weight matrix from graph nodes to pseudo nodes, E and F follow the similar name rule. An example of E. computation is illustrated Fig. 2 Eq. formulates the process that graph nodes diffuse messages to pseudo nodes. Eq. 5 formulates the global feature refinement the pseudo-node level, where AR R denotes the learned displacements for
pseudo nodes, MP E Rd encodes the refined pseudo-node messages with global information. the message collection process from pseudo nodes to graph nodes.
For simplicity, we compile Eq. 4 6 as MBlob, AR = GlobMP (Q, M R).. Note that the space complexity of our global message passing is Okkn,, with k. "p n, significantly lower than Onn²) in dense global message passing.
Local message passing. Topology-couple message passing is employed to encode the local structure. The resulted local passsage-passingg process for graph node v can be formulated as
m
local
W
+1
m
Σ (VEN(()
NI(m://le..)
where || denotes the concatenate operation. Through local message passing, graph nodes aggregate messages from their adjacent nodes. Eq. can be compiled M LocalMP (M, E) for all the graph nodes.
Implementing Dynamic Message Passing with N
We further develop a GNN model named N to move the embedded nodes to their optimal positions. By feeding the states recursively into single recurrent layer, N2 learns the displacements of all the embedded nodes in the state space and updates their positions. The changes in position reshape the spatial relations between the embedded nodes and thus reshape the dynamic message pathways. These dynamically evolving pathways empower 2 to adapt to the specific positions of the embedded nodes at each recursive step. In this section, we first outline the key process the I-th recursive step. i.e., pseudo-node adaptation and dynamic message passing, then describe different output fashion for downstream tasks.
4.1 Pseudo-node Adaptation
Pseudo nodes are initialized randomly in the state space. To adapt to specific input graphs, N2 first diffuses graph node messages to pseudo nodes, adjusting pseudo-node states and corresponding messages accordingly. Given graph node messages M=(1-1) (M X), graph node states Q ((--i) and pseudo-node states (1-1) at the /-th recursive step, the adaptation process can be formulated as
Mgslb(() AR (1) GlobMP (Q (Q(12)) M=(l-1) (=((-)),R(-1)) R
(8)
R 0 R (1-1) + AR
5

---

Table 1: Graph classification results small-scale benchmarks (measured by accuracy: %).
PROTEIN
NCI1
IMDB-B
IMDB-M
COLLAB
GGRAPS
1,000
1,500
#NoDES
39,06
29.87
19.77
13.00
74,49
BERGUS
145.60
64.60
195.10
131.87
4,914.4
#NuDE PEATUMSS
37
0
0
PATCHY-SAN 45
72
73.24.007
11.79
10.33
10.41
vo.27
PG 29
76.30.3.m0
82.80-1.91
76. 80 22.00:2.0
53.20
80.90...0
COCN K53
26.56_0011
82.89
27.26
$6.32
86.15 15 so
GIN 71
13.84_0..
76. (2.62.11mm
72. 78
18.13
78.19 29.
19
GRAMISAGE
13.48_1..0
80
73 73.90.117
4PS2UID NO0I 42
73.95_1.00
74.31 22.90
DIFFPOOL
7X
75.62.1-17
76.62
73. 23.14gmm
$1.31 31.31
82.13
+PSRUDO Nont
75. 75.98g5.90 43
77.08
70.48.1.01
67.02.222
10.5
c1.71
77.58.0.. 10.45
SAGPoOL
71.56.1.4
61.4
50.23
78.03 .n.33
STRUL-PPOLL
75.16..044
78.64 11:0
72.06 Lo.s
50.23 sn.53
77.27 10.33
SEP (67
76.42
79.35
74.12
51.53
81.28 10.15
GMT
75.09.0.5
76.35
73.48
50.66.0.:2
80.74.0.54
N (OURS)
27.53-1.7
83.52
79.95
57.31
86.72.144
where Mtleb(() denotes pseudo-node messages that are collected by graph nodes, serving as query signals for different patterns on graphs. R() denotes the adjusted pseudo-node states.
4.2 Dynamic Message Passing
N2 performs both local and global message passing. At the local level, graph nodes exchange their own messages MD(t-1,, collected messages MBlob(!) and graph node states Q (1-1);
M local()) = LocalMP
Q Q (1-1) (M
Through local message passing, graph node messages Mlocal()) are generated in response to the query messages M1)lb((), N2 then sends the updated messages to global message passing:
(1lab(1), AR ( GlobMP (Q(,,Moca11)
M .((1))
Q = (() + (M MD()) MP(1-1) Mslob(l)
(10)
(0) R0 + A
4.3
Output Module
N2 updates the states of the embedded nodes recursively with single recurrent layer. Instead of employing different layers for each recursive step, the associated parameters are shared across steps. After L recursive steps, the embedded nodes now reach their final states (L) and R (4), N2 then takes graph node states and pseudo-node states as the learned representation for node-level and graph-level tasks, respectively. For graph classification, N2 further applies NL(.) to aggregate the pseudo-node states. To make class predictions, 2 employs learnable parameter C _ as the states of n. class nodes and outputs the proximity between the recursive output and the class nodes.
Experiment
In this section, we provide empirical evaluation results of 2 real-world benchmarks. N2 is implemented with PyTorcc [47] and PyTorch Geometric [18], and trained on a single Nvidia Geforce RTX 4090. The detailed experimental settings presented in Appendix C
5.1 Graph Classification
Experimental setups. We adopt six benchmarks including three biochemical datasets (OGB-
molpcba (27). PROTEINS 44,, NCII [4]) and three social network datasets 44) (COLLAB,

---

Table 2: Graph classification sults on large-scale benchmark OGB-molpebb.
Table 3: Node classification results on small-scale homophilic graphs (measured by accuracy: %).
COAUTHORCS
COAUTHORPHY
AMZPHOTO
AMZCOMPUTERS
#GRAPMS 437,929
&Noues
VEDGES 28.1
26
&NonES
18,333
34,493 247.962
7,487
13,381
METHODS
AVERAGE PRECISSON
4PARAMS (K)
GCN 33
92.92.0112
81,894
96. 16.18_.m
92. 22
119,043
89. 65.5
245,778
20. (56
GAT A4
93.6 93.61.011
96. 17
93 11
90 78.28
GCN
GPRGNN
95. 95.13_00m
96.85200
94.49_.0o7
26.54
34
1.923
50
94, 94.64_.
97.05 2o.0
94. 94.74.0.13
91. 11
MPNN
GRAPHGKMER
DOM
OOM
92. 92.74:0.14
GOM
SAN 33
94,51
0OM
94.86
89.
SAN 85
GRAPHTRANS
27.61 tm
GRAPHGPS
NAGPHORMER
93.93
75.75_mm
00M
34
26.66111
OOM
22
GRAPHGES
29.07
EXPRORMTR
57
95.77
97. ia
95. 35
91. 1..59
GRAPHORMER
31.39
119,529
N2 (OURS)
94.44_n
g7.56
95.75
92.51
Nº (OURS)
73
516
IMDB-BINARY and IMDB-MULTI), The benchmark statistics are summarized Tab. 1 and Tab. 2 We choose convolutional GNNs, GNNs with single pseudo node, hierarchical GNNs, and graph transformers as the baselines of graph classification. For more details, please refer to Appendix, C.T.2
Performance. N2 and baselines are evaluated on both small-scale and large-scale benchmarks. The evaluation results in Tab. and Tab. showcase the ability of N2 outperform various GNNs and graph transformers. Especially on the large-scale benchmark OGB- DGB-mollcba, N2 surpasses baseline models with only 500K parameters, while Graphormer reaches 31.39% average precision with 119.5M parameters. Compared to GNNs with single pseudo node, N gains significant improvements. This demonstrates the effectiveness of our common state space where pseudo nodes and graph nodes can interact dynamically with each other.
5.2 Node Classification
Experimental setups. For node classification, we conduct experiments on (1) six small- scale benchmarks: homophilic graphs (AmazonPhoto, Ama- zonComputers, CoauthorCS, and CoauthorPhysics) (55), heterophilic graphs (questions, amazon-ratings, tolokers, and minesweeper) [4); and (2)
Table 4: Node classification results on small-scale heterophilic graphs (measured by ROC-AUC except accuracy for amazon- ratings: %) ). i denotes our reproduced results.
QUESTIONS
AMAZON-RATINGS
TOLOKERS
MINESWEEPER
#NODES #EDGES
48,921
24,492
11,758
10,000
153,540
93,050
$19,000
39,400
SGC
66
75.91 go:05
50.66.9.4
80.70gao7
70.88
GCN 33
76.09-1:27
48, 48.70....z
83.642207
89.75
77.43_1-9
49.
83.70go.47
92.01
four large-scale benchmarks: homophilic graphs (OGB- arXiv, OGB-proteins) 27
GPRGNN [0]
HGGCN
78
63.59 :1.45
55.48-2.91
44,88 +0.54
36.47
72.94=n07
73.35
89.71 10.31
86.24 86.24:0.81
FAGCN
77.24:1.25
44.
77.75
88.17
GLOGNN
24.14.1..9
36.89; 10.14
g.117
11.00
GT 50
71.95
$1.17
83.23
91.85
heterophilic graphs (arXiv-year, genius) [1). The statisties of node classification benchmarks are summarized in Tab. 3 5 We
GRAPHORMER
0DM
0DM
00M
GRAPIGPS 52
GDM
0OM
84.70ga.6
32.29
EXPHORMER 37
73.86 73.86.000
49.36.0.0
84..00go
90.42.m.m0
(OurS)
78.07 20003
50.25 $o.53
86.25 (0:43
93.97 10.27
choose convolutional GNNs and graph transformers as the baselines. For detailed baseline setups, please refer to Appendix.
The evaluation results are presented in Tab. N2 reaches superior or comparable performance against strong GNN baselines on both small- scale and large- scale benchmarks. Com- pared to graph transformers based on dense attention, including Graphormer, SAN, and GraphGPS, N2 surpasses the baselines on small-scale benchmarks and successfully scales to large-scale bench- marks. Note that Exphormer based on sparse attention also suffers from the out-of-memory problem in our experimental environment, For other sparse graph transformers, N can achieve comparable results and perform consistently between heterophilic and homophilic benchmarks.
Performance.
7

---

Table 5: Node classification results on large-scale benchmarks (measured by ROC-AUC/aceuracy %). i denotes our repro- duced results.
ARXIS-YEAR ACCURAEY
OGR-ARXIV
OGR-FROTHIN ROC-AUC
ROC-AUC
ACEURACY
ANODES
121,961 984,979
169.343
169,343
132.534
AEDGES
1,166,243
1,166,243
39,561,252
62,
12
27
20
87 42
46.02_0m5
LIMEO
GAT 64
53. 80....7
46.05-n.5
67 67.63.2..2
74.63
APPNE 211
85 36
38.15
Figure 3: Complexity analy- sis. The results under differ- ent numbers of graph nodes are compared. Marker X denotes out- out-of-memory Dense denotes dense pairwise relation model- ing.
H&GCN
12
0OM
49.09
0OM
00M
LINKX
90.77
56.00_1.0
GRAPIORMPEE
SAN 85
DOM
GRAPEGPS
32
EXPHORMER
57
0OM
0OM
72.44
00M
28.62.a02
37.68
g7.45.1.18
83.91 a2.0 (7)
44.34.00r (t)
72.63 0o.33
po.35
Nº (OLKS)
89.32
58.69
70.01
79.55
5.3
Model Analysis
5.3.1
Complexity Analysis
Our proposed dynamic message passing enables graph nodes to access each other without dense pairwise modeling. As described in Sec. [3.4] the space complexity of our global message passing Okknp)) We further conduct empirical analysis of N on computational complexity. As presented in Fig. the computational time exhibits linear scalability for the number of graph nodes n, while being insensitive the number of pseudo nodes np. In comparison dense pairwise modeling. substitute the global message passing in N2 with dense attention scheme. The resulting growth rate of computational time for N is significantly lower than that of the dense method. Moreover, the dense method fails extend to large-scale graphs, whereas N only encounters out-of out-of-memory under the extreme situation of np 256 and 1M.
5.3.2 Effectiveness of 2
Tackling over-squashing. 2 employs pseudo nodes in the common state space to achieve global message passing with linear complexity. These pseudo nodes also benefit N2 in tack- ling over-squashing from two aspects, i.e., avoiding forming new bottlenecks pseudo nodes and detouring from the bot- tlenecks on input graphs. Specifically, our pscudo nodes avoid becoming new bottlenecks by employing dynamic connec- tions. Compared to the uniform connection, dynamic connec- tion learns the specific edge weights for each pseudo node to different graph nodes. During global message passing, these weights can eliminate messages from certain graph nodes while preserving the others. As result, the messages will not be squashed equally into the pseudo nodes, preventing the nodes from becoming new information bottlenecks. Regard- ing the bottlenecks on input graphs, the pseudo nodes produce two-hop message highways for message passing, detouring messages from these bottlenecks. To evaluate 2 in tackling over-squashing we conduct experiments on Trees Match [2] with training accuracy results presented in Fig. 4(a) 2 main- tains the fitting ability across different tree depths, demon- strating its ability to counteract over-squashing. Fig. 44a) also verifies the superiority of the dynamic connection in tackling over-squashing. where 2 with the uniform connection shows decline in accuracy the depth increases.
Tee bech
(a) Over-squashing
Amazoi
Mander Wnterllsea Recul 2006
(b) Over-smoothing
Figure 4: Effectiveness study.

---

Figure Ablation on the modules of N (measured by accuracy: %). PA., L., and G. denote pseudo-node adaptation, local message passing, and glohal message pass- ing. Att. and Prx. denote the attention and proximity measurement.
(a)
(b) E
Figure 6: Message passing analysis. The proximi- ties between sampled graph nodes and pseudo nodes depicted in the center of each sub-figure, where darker green indicates higher proximity and brighter green indicates lower proximity, The distribution on the top/right of each sub-figure denotes the sum of proximity for each graph/pseudo node. Graph/pseudo nodes are ranked based on the sum of proximity.
Anzz rratings
Amz
RPO
-TEINS
PA.
48 18.20..
40.77
75.76-2.m8
w/o.
L.
48.69
94.84
75.77 L9.17
50.16-0.54
94.58 40.40
75.54-1.05
Full with Ant.
49.18
95.02 1o.30
73.68 13.68
with Prx.
50.25 g0:53
35.75.0.24
77.53-1.75
Tackling over-smoothing. The other issue encountered when message passing relies heavily on input topology is over- over-smoothing [46]. In N2, pseudo nodes are adopted as message pathway alternates, decoupling the message-passing process from input topology. During global message passing, our dynamic connection empowers the connected graph nodes on the input graphs to receive different outputs and avoid becoming too similar to each other. For local message passing, learning node displacements in 2 allows the combination of local pesssage-passing outputs with layer inputs and global message- message-passing outputs. Although stacking multi-layer local message passing leads to over-smoothing, the layer inputs and global outputs can maintain the sighffreuency signals. To evaluate whether 2 can alleviate the over-smoothing issue, we explore the changes in the Dirichlet energy 3 as the number of recursive steps increases. Fig. comppres among N N2 with the uniform connection, and SGC [66] on AmazonPhoto and amazon-ratings. The reported values are normalized to [0, 1] by dividing the maximum energy values. Results show that N with uniform connections encounters over-smoothing as the number of recursive steps increases, while N with dynamic connections can maintain the Dirichlet energy and alleviate over-smoothing.
5.3.3 Distribution of Embedded Nodes
We visualize the distribution of all the em- bedded nodes during training. Results on AmazonPhoto at the first recursive step are depicted Fig. For results through re- cursion, please refer to Appendix[D2. We can see that as the graph nodes are clus- tered with different class nodes, pseudo nodes are also split into several groups. Each pseudo-node group is attracted to- ward distinct graph node cluster. This indicates that pseudo nodes will attend a particular graph node group, serving as the global message pathways to other groups. As a result, each pscudo node assumes a balanced fraction of the global message load, mitigating the risk of becoming bottlenecks for message passing.
(a) Epoch=20
(b) Epoch=500
Figure 5: Distribution of embedded nodes. The t- sne [61] results under different training epochs are com- pared. O, 1, 2, 3, 4, and 6 denote graph nodes with different labels. A denotes pseudo nodes. denotes class nodes.
To further analyze the message passing between graph nodes and pseudo nodes, we visualize the proximity matrix E and E for pseudo-nod adaptation (Eq. 8 on AmazonPhoto in Fig. 6 For more proximity visualizations, please refer to Appendix [D.3] 1000 graph nodes are sampled randomly and ranked based on their intro-/outre hitro-/outre-prximiity summation. The hutro//outreppoxximee
summation indicates the message load a graph node collects or diffuses during the message passing. As depicted in Fig- 6, both graph nodes and pseudo nodes assume balanced message load. Each pseudo node has various proximity values toward individual graph nodes, different from the uniform pathways. All these properties empower efficient global message passing on graphs.

---

5.3.4 Ablation Study
Pseudo node. We conduct ablation studies on the number of pseudo nodes np in Fig. To present the results compara- ble form within the same figure. the accuracy values have been normalized by subtracting the minimum value. As up increases, N² gets improvement in accuracy for all three datasets. How-
PC LS3 Anaaet
ever, the accuracy exhibits degradation on PROTEINS when Up reaches 256. This is because nyp exceeds the optimization capacity of N A similar degradation also happens amazon- ratings. In practice, the optimal value of Ap is around 16 to 32 for graph classification while reaching 128 to 300 for node classification. We also conduct ablation studies on the engage- ment of pseudo nodes in Appendix D.7 where N2 with pseudo nodes outperforms dense message passing.
of toda
Figure 8: Ablation on the number of pseudo nodes (npp)
Recurrent layer. By employing the same recurrent layer through recursive steps. N2 attains comparable performance to baseline models with substantially fewer parameters. To analyze the efficacy of parameter sharing, we conduct ablation studies the number of recurrent layers, comparing N with shared parameters against N with multiple recurrent layers in Fig. | For simplicity, we denote the number of recurrent layers as Lp. where N with multiple recurrent layers has Lp equals to the number of recursive steps L and N with shared parameters has Lp 1. Given the same L, N with Lp 1 achieves matching performance with Lp = L. This indicates that shared parameters are sufficient in modeling convergent dynamics the embedded nodes in the state space (Fig. (5) However, 2 achieves better performance with I,, L. when L surpasses 8 on amazon-ratings and AmazonPhoto. In further empirical analysis, we find that the embedded nodes in N2 with L, tend to maintain current dynamics through recursive steps and thus become less effective in precise position optimization. Please refer to Appendix D.4 for detailed
Figure 9; Comparison between single shared recurrent layer and multiple recurrent layers.
analysis. step-dependent parameter may further improve the performance of 2 with Lp 1. We will keep exploring it in future work.
Relation measurement. We compare proximity measurement with attention 62 in Tab. 7 Results show that N2 with proximity achieves better performance on all three benchmarks. We ascribe this to the flexible range of the proximity values. In contrast, normalized attention that ranges in [0, 1] can yield equally small weights and attenuate the messages, especially when the optimal assignment involves a large number of graph nodes the same pseudo node.
N2 modules. In Tab. N with all three modules achieves superior performance across all the benchmarks. In comparison among the ablated N removing global message passing leads to larger degradation in graph classification accuracy. Conversely, node classification exhibits greater sensitivity to the removal of local message passing. Moreover, pseudo- mode adaptation is required by N2 on all three benchmarks. This indicates that adapting the randomly initialized distribution of pseudo nodes enables better interactions with graph nodes.
Conclusion
In this paper, we presented dynamic message-passing method on graphs. Both graph nodes and pseudo nodes are embedded in common state space with measurable relations between them. The measured relations serve as dynamic pathways between the embedded nodes, empowering flexible message passing. Associating pseudo nodes to input graphs with measured relations, graph nodes can communicate with each other intermediately through pseudo nodes under linear complexity. Based on the proposed dynamic message passing, we further developed GNN model named N for graph and node classification tasks. Experimental results show that 2 achieves superior performance over competitive bascline models. For limitations discussion, please refer to Appendix F
10

---

Acknowledgments and Disclosure of Funding
This work was supported in part by the National Key R&D Program of China under Grant 2023YFC2508704, in part by the National Natural Science Foundation of China: 62236008, U21B2038, and 61931008, and in part by the Fundamental Research Funds for the Central Universi- ties. The authors would like to thank Wanxing Chang and the anonymous reviewers for their helpful comments and suggestions that improved this manuscript.
References
[1] Sami Ho--El-Haija. Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard. Kristina Lerman, Hrayr Harutyun- yan, Greg Ver Steeg, and Aram Galstyan. MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighhorhood Mixing. In International Conference on Machine Learning, pages 21-29, Long Beach, USA, 2019. PMLR.
[2] Uni Alon and Eran Yahav. On the Bottleneck of Graph Neural Networks and its Practical Implications. In International Conference on Learning Representations, Virtual Only, 2021.
[3] Jinheon Baek, Minki Kang, and Sung Ju Hwang. Accurate Learning of Graph Representations with Graph Multiset Pooling. In International Conference Learning Representations, virtual, 2022.
[4] Stefan Banach. Sur les opérations dans les ensembles abstraits et leur application équations intégrales. Fundamenta Mathematicae, 3(1):133- 181, 1922.
Deyu Bo, Xiao Wang. Chuan Shi, and Huawei Shen. Beyond Low-frequency Information in Graph Convolutional Networks. In AAAI Conference on Artificial Intelligence, volume 35, pages 3950-3957, virtual, 2021.
[6] Xavier Bresson and Thomas Laurent. Residual Gated Graph ConvNees, 2018
[7] Chen Cai, Truong Son Hy, Rose Yu, and Yusu Wang. On the Connection Between MPNN and Graph Transformer. Proceedings of the 40th International Conference on Machine Learning, pages 3408-3430. PMLR, 2023.
[8] Chen Cai and Yusu Wang. A Note on Over-Smoothing for Graph Neural Networks. arXiv:2006. 13318 Jcs, star], 2020.
[9] Jinsong Chen, Kaiyuan Gao, Gaichao Li, and Kun He. NAGphormer: A Tokenized Graph Transformer for Node Classification in Large Graphs. In International Conference for Learning Representations, 2023.
[10] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and Deep Graph Convolutional Networks, In International Conference on Machine Learning, pages 1725 1135, virtual, 2020. PMLR.
[11] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive Universal Generalized PageRank Graph Neural Network. In International Conference on Learning Representations, virtual, 2022.
[12] Andreea Deac, Mare Lackenby, and Petar Veličković. Expander Graph Propagation. In Learning on Graphs Conference, volume 198, page 38. PMLR, 2022.
[13] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering. arXiv:1606. 09300.09935//11 [cs, stat], 2017.
[14] Francesco Di Giovanni, Lorenzo Giusti, Federico Barbero, Giulia Luise, Pietro Lio', and Michael Bronstein. On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology. In International Conference on Machine Learning, 2023.
[15] Francesco Di Giovanni, T. Konstantin Rusch, Michael Bronstein, Andreea Deac, Mare Lackenby, Sid- dhartha Mishra, and Petar Veličković, How docs over-squashing affect the power of GNNs? Transactions on Machine Learning Research, 2023.
[16] Cameron Diao and Ricky Loynd. Relational Attention: Generalizing Transformers for Graph-Structured Tasks. In International Conference on Learning Representations, 2023.
[17] Vijay Prakash Dwivedi, Ladislav Rampášek, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long Range Graph Benchmark. In Advances in Neural Information Processing Systems. volume 35, pages 22326 22340, 2022.

---

[18] Matthias Fey and Jan Eric Lenssen. Fast Graph Representation Learning with PyTorch Geometrie. In International Conference on Learning Representations Workshop on Graphs and Manifolds, 2019.
[19] Luca Franceschi, Mathias Niepert, Massimiliano Pontil, and Xiao He. Learning Discrete Structures for Graph Neural Networks. In International Conference on Machine Learning, pages 1972-1982. PMLR, 2019.
[20] Hongyang Gao and Shuiwang Ji. Graph U-Nets. In International Conference on Machine Learning, pages 2083-2092, Long Beach, California, USA, 2019. PMLR.
[21] Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then Propagate: Graph
Neural Networks meet Personalized PageRank. International Conference on Learning Representations. Addis Ababa, Ethiopia, 2018.
[22] Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural Message Passing for Quantum Chemistry. In International Conference on Machine Learning, volume 70, pages 1263-1272, Sydney, Australia, 2017. PMLR.
[23] Albert Gu, Karan Goel, and Christopher Re. Efficiently Modeling Long Sequences with Structured State Spaces. In International Conference on Learning Representations, 2021.
[24] Benjamin Gutteridge, Xiaowen Dong, Michael M. Bronstein, and Francesco Di Giovanni. DRew: Dynam- ically Rewired Message Passing with Delay. In International Conference on Machine Learning, pages 12252-12266 PMLR, 2023.
[25] William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In International Conference on Neural Information Processing Systems, pages 1025-1035, Red Hook, USA, 2017. Curran Associates Inc.
[26] Sepp Hochreiter and Jürgen Schmidhuher. Long Short-Term Memory. Neural Computation, 9(8): 1780, 1997.
[27] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open Graph Benchmark: Datasets for Machine Learning on Graphs. In Advances in Neural Information Processing Systems, volume 33, pages 221 18-22133. Curran Associates, Inc., 2020.
[28] Weihua Hu*, Bowen Liu*, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for Pre-training Graph Neural Networks. In International Conference on Learning Representa- tions, 2019.
[29] Zhongyu Huang, Yingheng Wang, Chaozhuo Li, and Huiguang Hc. Going Deeper into Permutation- Sensitive Graph Neural Networks. In International Conference Machine Learning, pages 9377 9409, Baltimore, Maryland, USA, 2022. PMLR.
[30] EunJeong Hwang, Veronika Thost, Shib Sankar Dasgupta, and Tengfei Ma. Revisiting Virtual Nodes in Graph Neural Networks for Link Prediction. 2021.
[31] Anees Kazi, Luca Cosmo, Seyed-Ahmad Ahmadi, Nassir Navab, and Michael M. Bronstein. Differentiable Graph Module (DGM) for Graph Convolutional Networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(2):1606 1617, 2023.
[32] Diederik P. Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization. In International Conference for Learning Representtions,, San Diego, USA. 2015.
[33] Thomas Kipf and Max Welling, Suni-super Classification with Graph Convolutional Networks. In International Conference on Learning Representations, Toulon, France, 2017.
[34] Johannes Klicpera, Stefan Weiß enherger, and Stephan Günnemann. Diffusion Improves Graph Learning. In International Conference on Advances in Neural Information Processing Systems, volume 32, pages 13333-13345, Vancouver, Canada, 2019. Curran Associates, Inc.
[35] Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létournca,, and Prudencio Tossou. Rethinking Graph Transformers with Spectral Attention. In Advances in Neural Information Processing Systems, volume 34, pages 21618-21629. Curran Associates, Inc., 2021.
[36] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. ImageNet classification with deep convolutional neural networks. Communications of the ACM, 60(6):84 90, 2017.
12

---

[37] Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-Attention Graph Pooling, In International Conference Machine Learning, pages 3734-3743, Long Beach, California, USA, 2019. PMLR.
[38] Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http: wttp:ssttaoordddddddeeeeee 2014.
[39] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning. In AAAI Conference on Artificial Intelligence, New Orlcans, USA, 2018.
[40] Xiang Li, Renyu Zhu, Yao Cheng, Caihua Shan, Siqiang Luo, Dongsheng Li, and Weining Qian, Finding Global Homophily in Graph Neural Networks When Meeting Heterophily. In International Conference on Machine Learning, volume 162, pages 13242-13256, Baltimore, Maryland, USA, 2022. PMLR
[41] Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large Scale Learning on Non- Non-Hooophilous Graphs: New Benchmarks and Strong Simple Methods. In Advances in Neural Information Processing Systems, volume 34, pages 20887-20902. Curran Associates, Inc., 2021.
[42] Xin Liu, Jiayang Cheng, Yangqiu Song, and Xin Jiang. Boosting Graph Structure Learning with Dummy Nodes. In International Conference Machine Learning, pages 13704-13716. PMLR, 2022.
[43] Grégoire Mialon, Dexiong Chen, Margot Sclosse, and Julien Mairal. GraphiT: Encoding Graph Structure in Transformers. arXiv preprint.
[44] Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. TUDataset: A collection of benchmark datasets for learning with graphs. In International Conference on Machine Learning Workshop Graph Representation Learning and Beyond, Virtual Only, 2020. arXiv.
[45] Mathias Niepert, Mohamed Ahmed, and Konstantia Kutzkov. Learning convolutional neural networks for graphs. In International Conference on Machine Learning, volume 48, pages 2014-2023, New York, NY, USA, 2016. PMLR.
[46] Kenta Oono and Taiji Suzuki. Graph Neural Networks Exponentially Lose Expressive Power for Node Classification. In International Conference for Learning Representations, 2021.
[47] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan. Trevor Killeen, Zeming Lin. Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf. Edward Yang. Zach Veto,o, Martin Raison, Alykhan Tejami, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Py PoTorc: An imperative style, high-performance deep learning library. In International Conference on Neural Information Processing Systems, pages 0037, Red Hook, NY, USA, 2019. Curran Associates Inc.
[48] Zhengqi Pei and Shuhui Wang. Dynamics-inspired Neuromorphic Visual Representation Learning. In International Conference on Machine Learning, pages 27521-27541. PMLR, 2023.
[49] Oleg Platonov, Denis Kuznedeley, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. critical look at the evaluation GNNs under heterophily: Are we really making progress? In The Eleventh International Conference on Learning Representations, Kigali, Rwanda, 2023.
[50] Chendi Qian. Andrei Manolache, Kareem Ahmed, Zhe Zeng. Guy Van den Broeck, Mathias Niepert, and Christopher Morris. Probabilistically Rewired Message-Passing Neural Networks. In International Conference on Learning Representations, 2023.
[51] Saced Rahmani, Asiye Baghbani, Nizar Bouguila, and Zachary Patterson. Graph Neural Networks for Intelligent Transportation Systems: A Survey, IEEE Transactions on Intelligent Transportation Systems, 24(8):8846-888 8885, 2023.
[52] Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for General, Powerful, Scalahle Graph Transformer. In Advances in Neural Information Processing Systems, volume 35, pages 14501-14515, New Orleans, USA, 2022.
[53] Ekagra Ranjan, Soumya Sanyal, and Partha Talukdar. ASAP: Adaptive Structure Aware Pooling for Learning Hicrarchical Graph Representations. In AAAI Conference on Artificial Intelligence, volume 34, pages 5470-5477 5477, New York, NY, USA, 2020.
[54] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The Graph Neural Network Model. IEEE Transactions Neural Networks, 20(1):1 1-61-0000000..1111 2009.
13

---

[55] Oleksandr Shchur, Maximilian Mumme. Aleksandar Bojchevski. and Stephan Günnemann. Pitfalls of Graph Neural Network Evaluation. 1rXiv:1811.05868 [cs, stat], 2019.
[56] Yunsheng Shi, Zhengjie Huang. Shikun Feng, Hui Zhong, Wenjing Wang, and Yu Sun. Masked Label Prediction: Unified Message Passing Model for Semi- Bemi-Supervised Classification. In International Joint Conference on Artificial Intelligence, volume 2, pages 1558--554,, Virtual Event Montreal, Canada, 2021. ojeai.org.
[57] Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica J. Sutherland, and Ali Kemal Sinop. Exphormer: Sparse Transformers for Graphs. In International Conference on Machine Learning, volume 202, Honolulu, USA, 2023. PMLR.
[58] Junshu Sun, Shubui Wang, Xinzhe Han, Zhe Xue, and Qingming Huang. All in row: Compressed convolution networks for graphs. In International Conference on Machine Learning, volume 202, pages 33061-33076, Honolulu, USA, 2023. PMLR.
[59] Yifei Sun, Haoran Deng, Yang Yang. Chumping Wang, Jiarong Xu, Renhong Huang. Linfeng Cao. Yang Wang, and Lei Chen. Beyond Homophily: Structure-aware Path Aggregation Graph Neural Network. In International Joint Conference on Artificial Intelligence, volume 3. pages 2233-2240, 2022.
[60] Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. In International Conference for Learning Representations, 2021.
[61] Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 911), 2008.
[62] Ashish Vaswani. Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez. Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In International Conference on Neural Information Processing Systems, pages 1000-6010, Red Hook, NY, USA, 2017, Curran Associates Inc.
[63] Petar Veličković. Message passing all the way up. International Conference on Learning Representation Workshop on Geometrical and Topological Reprexentation Learning, 2022.
[64] Petar Veličković. Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. In International Conference on Learning Representations, Vancouver, Canada, 2018.
[65] Huizhao Wang, Yao Fu, Tao Yu, Linghui Hu, Weihao Jiang, and Shiliang Pu. PROSE: Graph Structure Learning via Progressive Strategy. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2337 2348, New York, NY, USA, 2023. Association for Computing Machinery.
[66] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinherger. Simplifying Graph Convolutional Networks. In International Conference Machine Learning, pages 6861-6871, Long Beach, USA, 2019. PMLR.
[67] Junran Wu, Xueyuan Chen, Shangzhe Li, and Ke Xu. Structural entropy guided graph hierarchical pooling. In International Conference on Machine Learning, volume 162, pages 24017-24030, Baltimore, Maryland, USA, 2022. PMLR.
[68] Qitian Wu, Chenxiao Yang, Wentao Zhao, Yixuan Hc, David Wipf, and Junchi Yan. DIFFormer: Scalable (Graph) Transformers Induced by Energy Constrained Diffusion. In The Eleventh International Conference on Learning Representations, 2023.
[69] Qitian Wu, Wentao Zhao, Zenan Li. David Wipf, and Junchi Yan. NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification. In Advances in Neural Information Processing Systems, 2022.
[70] Qitian Wu, Wentao Zhao, Chenxiao Yang, Hengrui Zhang, Fan Nie, Haitian Jiang, Yatao Bian, and Junchi Yan. SGFormer: Simplifying and Empowering Transformers for Large-Graph Representations. In Conference on Neural Information Processing Systems, 2023.
[71] Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanic Jegelka. How Powerful are Graph Neural Networks? In International Conference on Learning Representations, New Orlcans, LA, USA, 2019.
[72] Chengxuan Ying. Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie- Yan Liu. Do Transformers Really Perform Bad for Graph Representation? In Advances in Neural Information Processing Systems, volume 34, pages 28877-28885 Curran Associates, Inc., 2021.
14

---

[73] Zhitao Ying. Jiaxuan You, Christopher Morris. Xiang Ren, Will Hamilton, and Jure Leskovec. Hierarchical Graph Representation Learning with Differentiable Pooling. In Advances Neural Information Processing Systems, volume 31, pages 4805-481 Montréal, Canada, 2018. Curran Associales, Inc.
[74] Hao Yuan and Shuiwang Ji. StructPool: Structured Graph Pooling via Conditional Random Fields. In International Conference on Learning Representations. Addis Ababa, Ethiopia, 2020.
[75] Sheheryar Zaidi, Michael Schaarschmidt, James Martens, Hyunjik Kim, Yee Whye Teh, Alvaro Sanchez- Gouzalez, Peter Battaglia, Razvan Pascanu, and Jonathan Godwin. Pre-training Denoising Molecular Property Prediction. The Eleventh International Conference on Learning Representations, 2023.
[76] Wentao Zhao, Qitian Wu, Chenxiao Yang, Junchi Yan. GraphGLOW: Universal and Generalizable Structure Learning for Graph Neural Networks. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 3525-3536, New York, NY, USA, 2023, Association for Computing Machinery.
[77] Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang. Changeheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. Al Open, 1:57-81, 2020.
[78] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. In International Conference on Neural Information Processing Systems, pages 7793-7804, Red Hook, NY, USA, 2020. Curran Associates Inc.
[79] Yanqiao Zhu, Weizhi Xu, Jinghao Zhang, Qiang Liu, Shu Wu, and Liang Wang. Deep Graph Structure Learning for Robust Representations: A Survey. arXiv:2 03036 [cs], 2021.
15

---

A
State Space
N2 unifies graph nodes and pseudo nodes in common state space. The concept of state space has been widely adopted in various machine learning methods. In reinforcement learning, the state space is typically modeled as discrete space, encompassing all possible states of an agent. By taking discrete actions, agents make transitions between states. Through interactions with the environment, agents learn optimal policies that determine their actions at certain states, maximizing the cumulative reward over time.
In contrast to the discrete paradigm, recurrent models such as long short-term memory (LSTM) (26], and state space models (SSMs) [23] utilize continuous state representations model sequential data. In this setting, input sequences are tokenized and consumed by the model in a successive manner. As result, recurrent models learn update the state embeddings recursively.
Building upon the continuous paradigm, DyN [48] further applies measurements to the continuous state space, giving rise to measurable spatial relations between state embeddings. All the input tokens can now modeled simultaneously in the state space.
However, modeling dense pairwise relations among large number of graph nodes becomes in- tractable in the graph representation learning setting, due to the quadratic complexity. To reduce the complexity, we introduce pseudo nodes to serve as proxies for pairwise relations between graph nodes. Consequently, the relations between graph nodes are decomposed into two components, i.e., relations between source graph nodes and pseudo nodes, and relations between pseudo nodes and target graph nodes. Since the number of pseudo nodes substantially smaller than the number of graph nodes, this decomposition effectively reduces the overall complexity.
B Pseudo Nodes and Pooling Nodes
In hierarchical GNNs, graph nodes are compressed into higher-level nodes through iterative graph pooling. These higher-level nodes, referred as pooling nodes, are different from the pseudo nodes in N First, pseudo nodes and pooling nodes are learned for different objectives. Pseudo nodes optimize communication efficiency between graph nodes during global message passing. Pooling nodes capture the hierarchy in the graph structures, ensuring better structure compression. Second, pooling nodes and pseudo nodes have different relations with input graph nodes. Pooling nodes are higher-level abstractions of graph nodes and are not physically connected with them. In contrast, pscudo nodes can be regarded as learnable graph nodes. These nodes are physically connected to graph nodes part of the graphs and directly participate in the message passing between graph nodes. Third, pseudo nodes and pooling nodes employ different communication pathways. Pooling nodes employ the coarse adjacency matrix for message passing. Pseudo nodes are free from structure- presorringeeeeigggggg constraints and learn fully connected pathways to communicate with each other.
C Details on Experiments
We have performed grid search for the hyper-parameters in Tab. S6 and the reproduced models based on validation loss. All the learnable parameters in N2 are optimized during training, including the weights the linear transformations and the proximity measurement, the pseudo/class-not states. The cross-entropy loss is adopted for classification and the LI loss for regression. No position or structural encoding methods are employed for N
C.1 Graph Classification
C.1.1
Benchmark Descriptions
We adopt six benchmarks for graph classification, including three biochemical datasets (OGB- molpeba (27), PROTEINS 4., NCI1 44) and three social network datasets 44 (COLLAB, IMDB-BINARY, and MUDB-MULTT..
OGB-molpeha a large-scale molecular property prediction benchmark, Each graph is a discrete molecule, wherein nodes denote individual atoms and edges encode chemical bonds between atoms.
16

---

PROTEINS comprises 1,113 protein graphs with amino acids constituting the nodes. The associated binary classification task involves predicting protein category labels, specifically discriminating between enzymes versus non-enzymes.
NCI1 constitutes 4, 10 graphs of chemical compounds assembled by the National Cancer Institute (NCI). Graph labels categorize compounds as exhibiting either positive or negative efficacy against cell lung cancer.
IMDB-BINARY and IMDB-MULTI constitute collaboration network graphs of movie actors and actresses, with graph labels indicating movie genres.
COLLAB constitutes scientific collaboration networks wherein each graph an ego network for researcher, encompassing their co-authors. Graph labels indicate the specific scientific interest corresponding to each researcher.
C.1.2
Experimental Setups
We choose (1) Convolutional GNNs: GCN B3 PATCHY-SAN (45. GraphSAGE [25] GIN (7).
PG [29]. and CoCN [58] (2) GNNs with single pseudo node from 442
27 7 (3) Hierarchical
GNNs;
DiffPool 73, TopKPool (20). SAGPool (37], StructPool 741, SEP 67 and GMT 3]
(4) Graph transformers: Graphormer
772. SAN 35]. GraphGPS 52] and GraphTrans 7 as the
baselines of graph classification.
Except for OGB- OGB-molpe we perform 10-fold cross-validation with LIB-SVM following [7] and report average performance. Average precision reported for OGB-molpehe while aceuracy is for the others. Since COLLAB, BINAY,, and BMDB-MULTT have no graph node features, we use the one-hot encoding of node degrees as node features following 77
For experiments on all benchmarks, the learning rate is set to x 10-3, We adopt Adam [32 as optimizer and set weight decay as 1 x 10-6 Early stopping regularization is employed, where we stop the training if there is no further reduction in the validation loss during 300 epochs. The maximum epoch number set to 1.000. The batch size is set 1.024 on OGB-molpoba, 256 on PROTEINS, NCII, IMDB-BINALE BINARY, IMDB MMD-MMULTI, and COLLAB. The detailed settings on all benchmarks are reported in Tab, SS6
C.2
Node Classification
C.2.1
Benchmark Descriptions
For node classification, we conduct experiments on (1) six middle-scale benchmarks: homophilic (AmazonPhoto, AmazonComputers, CoauthorCS, and CoauthorPhysics) heterophilic graphs 44 (questions, amazon-ratings, tolokers, and minesweeper); (2) four large-scale benchmarks:
graphs [55
homophilic graphs (27 (OGB-arXiv, OGB DGB-proteins), heterophilic graphs [4 (arXiv-year, genius).
CoauthorCS and GoauthorPhysice originate from the Microsoft Academic Graph, comprising co-authorship graphs wherein nodes denote researchers and edges denote co-authorships between pairs. Node features encapsulate keyword frequencies extracted from an author's publications. Graph labels categorize the dominant research interest in computer science or physics for each author.
Compuenss and AmazonPhoto constitute Amazon co-purchase graphs. Nodes denote products that are available for purchase and edges denote co-purchase relation between pairs of items. Node features encoded customer review texts corresponding each product. Graph labels categorize the products.
Questions originates from the Yandex Q question-answering website, comprising user activity graphs over a one-year interval (September 2021 to August 2022). Nodes represent users with interest in "medicine". Edges denote one user answered another user's posted question. The associated binary graph classification task involves predicting which users remained active on the website without account deletion blocking. Node features are derived by averaging FastText word embedding vectors corresponding to user profile descriptions.
Amazon-ratings utilizes the Amazon product co-purchasing network metadata sourced from the SNAP Datasets [38] Nodes are products with edges encoding frequent co-purchase relations between item pairs. The associated task involves predicting the average reviewer rating for each product,
17

---

Table Hyper-parameter setups for N
#RECURSIVE
STATE SPACE
#PSEUDO NODES
HIDDEN DIM.
#UNITS
STEPS
DROPOUT
(k)
(L)
DIM.
(np)
GENIUS
128
64
8
256
0.1
ARXIV-YEAR
128
64
8
300
0.1
OGB-ARXIV
128
64
320
0.3
OGB-PROTEINS
128
64
8
256
0.3
QUESTIONS
128
64
8
256
0.1
AMAZON-RATINGS
64
64
8
256
0.3
TOLOKERS
6
128
64
8
256
0.1
MINESWEEPER
64
8
128
0.3
COAUTHORCS
128
64
8
256
0.4
COAUTHORPHYSICS
128
64
8
256
0.5
AMAZONPHOTO
128
64
8
256
0.1
AMAZONCOMPUTERS
128
64
8
256
0.3
PROTEINS
128
64
8
32
0.1
NCII
6
128
128
8
32
0.1
COLLAB
128
64
8
32
0.1
128
64
0.1
IMDB-MULTY
128
64
8
0.2
OGB-MOLPCRA
128
64
8
32
0.3
which is grouped into five ordinal rating classes. Node features are derived by averaging FastText embedding representations corresponding to each product's ' description text.
Tolokers encapsulates crowdsourcing participation data sourced from the Toloka platform. Nodes denote contributors, referred to as "tolokers". involved in at least one out of 13 selected projects. Edges link toloker pairs that have completed the same tasks. The associated binary classification is to predict which tolokers have been banned from projects. Node features are profile attributes and task performance statistics of each toloker.
Minesweeper is a synthetic 100x 100 grid network. Nodes denote grid cells. 20% of nodes are randomly designated as mines. The associated prediction task is to classify which nodes are mine or not. For all nodes, input features are initialized as one-hot vectors encoding counts neighboring mines. The initialized features of 50% of randomly selected nodes are then reset to unknown values. These nodes are indicated by an additional binary indicator.
OGB-arXiy is a citation network of Computer Science papers arXiv. Nodes represent individual articles whereas directed edges denote one paper citing another. Node features are derived by averag- ing 128-dimensional word embeddings corresponding to the title and abstract of each publication. The associated multi-class classification to predict the primary category for arXiv articles across 40 classes.
OGB-proteins is an undirected, weighted graph of proteins. Nodes denote proteins while edges denote biologically meaningful associations between proteins. Edge features represent confidence scores for each association type. Node features are one-hot vectors denoting the species of each protein. The associated multi-label classification is to predict the presence of 112 potential protein functions, formulated as a binary prediction task for each label.
Genius is an online social network. Each node represents a user. The associated binary classification task predict whether the accounts marked or
arXiv-year is citation network from arXiv. Each node represents a research publication. The associated classification task is to predict the publication time of each node.
18

---

Table S7: Effectiveness study on peptides-struct (measured by mean absolute error).
PEPTIDES SERESSSSSTTTTT +
GCNII
34.71
GCN
34.96
GINE
35.47
GATEDGCN
33.57
SAN
25.45
PATHNN
25.45
DREW-GCN
25.36
EXPHORMER
24.81
N (OurS)
25.12
C.2.2 Experimental Setups
For baseline models, we consider (1) Convolutional GNNs: GCN 33 GAT 664, APPNP (21].
SGC [66]. H2GCN (78), FAGCN [5] LINKX 4T. GPRGNN M and GloGNN 40); (2) Graph
transformers: GT
56] Graphormer 722. SAN [35 GraphGPS [22] Nodeformer 669 NAG-
phormer 9 SGFormer
70 and Exphormer [57] based on pseudo node.
ROC-AUC is reported for questions, tolokers, and minesweeper while accuracy is for the others. We apply 60%/20%/20% train/val/test random splits for Amazon and Coauthor benchmarks and follow the standard splits as the original papers for the rest of the benchmarks. We reproduce the results of Exphormer (57) (genius, arXiv-year, OGN-Proteins,, questions, amazon-ratings, tolokers, minesweeper), Nodeformer [69] and SGFormer [70 on (genius and arXiv-year) with their released codes for fair comparison.
For experiments on all benchmarks, the learning rate is set to x 10 We adopt Adam 32 as optimizer and set weight decay 1 x 10-6. Early stopping regularization is employed, where we stop the training there is no further reduction the validation loss during 300 epochs. The maximum epoch number is set to 1,000. The detailed hyper-parameter settings on all benchmarks reported in Tab. S6
D
Additional Experimental Results
D.1 Effeeciveness on Tackling Over-squashing
We further benchmark N2 on Peptides-struct [17. graph regression benchmark involving long-
range interactions. Baselines include traditional GNNs: GCN [33], GCNII [10]. GINE 7 28]. and GatedGCN 6]: methods aiming capture long-range features: SAN 35 PathNN (59 Drew- GCN 224, and Exphormer [57]. As presented in Tab. S7 we can see that 2 achieves competitive
performance with Exphormer and surpasses the rest of baselines. This indicates the effectiveness of 2 to encounter over-squashing.
D.2 Distribution of Embedded Nodes
The distribution the embedded nodes through training is visualized in Fig. S10 pseudo nodes and graph nodes adjust their relative position actively in the state space. For the same recursive step through training, pseudo nodes are split into several groups. Each group is attracted toward distinct graph node cluster. For the node clusters and the attracted pseudo nodes also evolve through recursive steps. This indicates that 2 optimizes the proximity between graph nodes and pseudo nodes recursively, constructing dynamic message-passing pathways.
We can see that
epoch, the relative positions between graph
D.3 Proximity for Message Passing
To further analyze the message passing berween graph nodes and pseudo nodes, we visualize their corresponding proximity on AmazonPhoto. In Fig. SIT 1, 000 graph nodes sampled randomly.
19

---

Epoche0
Epoch=20
Epoch=
(a)
(b) 1=1
(= (d) 1 1=
(e)
Figure $10: Full results on the distribution of embedded nodes. The t-sne 61 results under different recursive steps across training compared. Each row is from the same epoch. Fach column depicts results from the same recursive step (I-th step). Input graph nodes with different labels depicted as: 3, 4, 5, Pseudo nodes depicted as A. Class nodes depicted as
Both graph nodes and pseudo nodes are ranked based on their intro-/outre proximity summation. The intro-/outre-pp prroi/ittt-pooiitttyyy summation indicates the message load a graph node takes emits during the message passing. From Fig. [SIT we can see that the intro-/outre intro-/outte-proximitty is distributed evenly across different graph nodes and pseudo nodes. This indicates that both graph nodes and pseudo nodes assume balanced message load. For each proximity matrix, the proximity value varies between different pairs of graph nodes and pseudo nodes, thus constructing dynamic pathways instead of uniform pathways.
puropiottre-proximity
D.4 Displacements Comparison between Single Shared Recurrent Layer and Multiple Recurrent Layers
To understand the difference in multi-step performance, where N with multiple recurrent layers (L, = L) achieves better performance against N with shared parameters (Lp = 1), we further analyze the displacements of the embedded nodes on AmazonPhoto and amazon-ratings. Fig. S12 depicts the comparison results. Four displacement types are presented the figure, including displacements pseudo nodes in pscudo-node adaptation (
(1) (Eq. g) and global message passing (! (Eq. 10), displacements of graph nodes in local message passing NL NL (Mocall)) (Eq. and global message passing (L(Mooo)!)) (Eq. 10 We take the Frobenius norm of each displacement matrix and divide it by the larger results between N2 with Lp and 2 with L, L across recursive steps, e.g., max (AR!) 1,=1 AR! EE [))
From Fig. S12 ratings and AmazonPhoto. The displacement curves of N2 with Lp = 1 are smooth, whereas N2 with T,p = I. demonstrates fluctuation. We attribute this difference to the distinct inertia characteristics exhibited by the embedded nodes. For the embedded nodes N with 4, = they generally possess greater inertia, and thus tend to maintain current dynamics through recursive steps. In contrast, the embedded nodes N with L, = L have smaller inertia and vary their dynamics. Therefore, N with I,p = can adjust the displacements of the embedded nodes more flexibly according to different situations and gain better performance in situations requiring precise distribution optimization. A step-dependent parameter may further improve the performance of N2 with Lp = 1 on larger number of recursive steps. We leave this for future exploration.
the consistency in the shape of the displacement curve between amazon-
20

---

(a) PNode. Adapt. ETP
(b) PNode Adapt. E
(c) Dy. MP. E
(d) Dy. MP. E
Figure S11: Full results on the message passing analysis. The results under different recursive steps across training are compared. Each row is from the same recursive step (l-th step). PNode. Adpat. denotes the pscudo-node adaptation module in N Dy. MP. denotes the dynamic message passing in 2 The proximities between sampled graph nodes and pseudo nodes are depicted in the center of each sub-figure, where darker green indicates higher proximity and brighter green indicates lower proximity. Each column of the proximity matrix associates with graph node while each row associates pseudo node. The distribution on the top of each sub-figure denotes the sum of proximity each graph node while the distribution on right for each pseudo node. The sampled graph nodes and pseudo nodes are ranked based the sum of proximity.
D.5 Ablation on Proximity Measurement
To approximate non-linear relations with low complexity, we employ piece-wise weighted inner products on the proximity measurement in Eq. [ Each embedded node is divided into l pieces. Ablation studies are conducted on & with amazon-ratings, AmazonPhoto, and PROTEINS. As depicted Fig. S13 N2 with multiple pieces outperforms a single piece on three benchmarks and gains improvement with & increasing. The optimal number of pieces à is around 8.
D.6 Ablation on Messages
In 2 graph nodes and pseudo nodes perform message passing based on their current states in the common state space and pass on the leamned messages to each other. States and messages take different roles our proposed method. Specifically, states are the descriptive embeddings of graph nodes corresponding to specific tasks, and messages are employed for information exchange. For the message passing from graph nodes to pseudo nodes, the messages contain the features of an input graph. From pseudo nodes graph nodes, the messages may contain the query information towards input graphs. To evaluate the necessity of distinguishing states and messages, we conduct ablation studies on messages by directly passing graph node states in message passing. The results with or
21

---

si Staret: de
3.-
32-
20
10
12
Nomatton CAecbcomee
Mitove Co
3.
N. R.pMinKay
N.10 24
10 31
16
12
15
16
AccerSue ST0
(a) amazon-ratings
(b) AmazonPhoto
Figure S12: Displacement comparison between N with a shared recurrent layer and N2 with multiple recurrent layers.
95
AmazonPhoto
76
75
PROTEINS
50
amazon-rstings
2
6
16
Mumber of Pleces
Figure S13: Ablation studies the number of pieces k.
without specially distinguished messages are presented in Tab. S8 We can see that applying both states and messages achieves the best performance.
D.7 Ablation on Pseudo Nodes
In addition to investigating the number of pseudo nodes, conduct ablation studies examine the impact of including pseudo nodes within N2, For cases without pseudo nodes, dense message passing is employed. However, dense computation is not scalable, only small-scale benchmarks are utilized for this ablation study. The results are presented in Table S9 Surprisingly, we find that 2 with pseudo nodes outperforms dense computation on IMDB-B, IMDB-M, and PROTEINS. This can be attributed to pseudo nodes functioning as information filters in global message passing, facilitating the removal of redundant information while extracting discriminative features from inputs.
Intuitions for the 2 Implementation
We provide more intuitions for the implementation Section N embeds graph nodes and pseudo nodes into the common state space, employing recurrent layer to parameterize the displacements of embedded nodes. The recurrent layer includes pseudo-node adaptation and dynamic message passing. Pseudo-node adaptation employs GlobMP to generate query messages toward graph nodes. Dynamic message passing then extracts graph features through LocalMP and refines these extracted features at the pscudo-node level with GlobMP.
22

---

Table S8: Ablation studies on messages.
W. MESSAGES
w/o. MESSAGES
w/o.-W.
QUESTIONS
78.07
76.01
-2.06
AMAZON-RATINGS
50.25
47.79
-2.46
TOLOKERS
86.25
85.05
-1.20
MINESWEEPER
93.97
92.38
-1.59
COAUTHORCS
94.44
92.39
-2.05
COAUTHOR PHYSICS PHYSICS
97.56
96.27
-1.29
AMAZONPHOTO
95.75
93.80
-1.95
AMAZONCOMPUTERS
92.51
90.73
-1.78
Table 89: Comparison between dense and pseudo-node-basee message passing,
DENSE
N
IMDB-B
77.94
79.95
IMDB-M
56.41
57.31
PROTEINS
76.94
77.53
As described by the pseudo-node adaptation in Eq. 8 graph nodes first diffuse messages to pseudo nodes. Based on the information learned from these messages, pseudo nodes generate displacements to adjust their own representations, enabling better interactions with graph nodes. Subsequently, graph nodes collect responding messages from pseudo nodes, which serve the query signals toward specific information the input graphs.
During the dynamic message passing, Eq. 9 presents the local message passing on input graphs. Graph nodes collect query messages from pseudo nodes, and process them together with their own generated messages and states through the LocalMP function. As result, graph nodes learn the features of the input graphs and generate feedback messages to pseudo nodes accordingly. The generated messages containing the features of input graphs can also be leveraged to determine the displacements of graph nodes.
Eq. 10 presents how graph nodes perform global message passing intermediately through pseudo nodes. Pseudo nodes receive the feedback messages and again generate their displacements. As feedback messages are aggregated the pseudo-nodes level, more global information is incorporated, guiding the movements of graph nodes and their message update.
F
Limitations
22 employs shared parameters to update the distribution of pseudo nodes and graph nodes recursively, We only studied 2 with a simple update mechanism. As discussed the model analysis section,
N2 encounters performance degradation when the number of recursive steps increases. In addition, the learnable pseudo nodes can be regarded as parameters GNNs, classified in line with neurons of GNNs. Under this interpretation of pseudo nodes, only subset of neurons from GNNs embedded in the common state space within our framework. Comprehensively bridging all neurons and graph nodes remains an open research direction.
G Societal Impact
This paper proposed novel method for constructing dynamic passsage-passingg pathways by bridging graph nodes and pseudo nodes in common state space. Our goal is advance the field of graph representation learning. The proposed method remains independent of specific downstream applications. As graph data are ubiquitous in the real world, there are many potential applications of our work, including computational biology [75), intelligent transportation [51), and algorithmic reasoning [16). Regarding ethical considerations, we do not presently foresee evident issues or potential for adverse societal impacts.
23

---

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:
The main claims made in the abstract and introduction accurately reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made 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 be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as 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: This paper discusses the limitations of the work in Appendix
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 a separate "Limitations" section 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
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 images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency 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 used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]

---

Justification:
Code is provided at This paper does not provide theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix 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 of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Detailed experimental setups are provided Appendix C https://githi: tht. com/ fomm/snjjsss sunjss/Ny
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, 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 a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
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 instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to 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 to faithfully reproduce the main experimental results, as described in supplemental material?
25

---

Answer: [Yes]
Justification: Code with instructions for reproduction is provided at com/ sunjss/N2
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c ec/
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for 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 sonideSuumisssooPP.e
//nips. //nips.c//pil cc/public/gut
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
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:
Detailed experimental setups provided in Appendix C
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper 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, 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: Please refer to Tab.
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, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
26

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables 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: Please refer to the heginning of Sec. 5 and Fig.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http::
Answer: [Yes]
Justification: The research conducted in the paper conforms with the NeurIPS Code of Ethics in every respect.
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 circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Please refer to Appendix G
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact 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.
27

---

The conference expects that many papers will be foundational research and not tied 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 an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point 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 being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: 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?
Answer: [Yes]
Justification: Please refer Appendix
C
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.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. com com/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.
28

---

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: Please refer to the supplementary materials and our open source code at bttps://ggtthue
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/codeemoodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing or 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 expect authors to 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.
29


Reviews:
[{"review_id": "P1rQdKAppm", "reviewer": "Reviewer_Qj5n", "summary": "The paper considers the problem of flexible message passing with low complexity in GNNs. To tackle this concern, the paper proposes a novel dynamic message-passing mechanism for GNNs via projecting graph nodes and learnable pseudo nodes into a common space with measurable spatial relations. Based on this dynamic message passing mechanism, the paper constructs a GNN model Named N^2 to estimate the effectiveness and efficiency of the proposed message passing mechanism.", "questions": "1. The analysis of the dynamic message-passing mechanism. Can we learn an additional pseudo node to provide global guidance (like a cluster center)?\n2. Can authors provide the discussion between dynamic and adaptive message passing?\n3. Can authors show the possibility of incorporating the dynamic message passing mechanism into other networks?", "limitations": "Yes.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. A novel dynamic message passing mechanism for GNNs is proposed to provide flexible message passing with low complexity. The dynamic message passing is interesting. \n2. The constructed N^2 GNN model is simple and effective. The complexity requirement is guaranteed.  \n3. The proposed N^2 holds superior performance.", "weaknesses": "See questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your support and valuable suggestions that further broaden the potential application of our method to graph interpretations and other neural networks. We will keep studying these problems in the future.\n\n**Q1**: Can we learn an additional pseudo node to provide global guidance?\n\n**Response**: If we understand your question correctly, the additional pseudo node refers to the pseudo node of the current pseudo nodes. Please let us know if we make a mistake. \n\n- `Global guidance in` $N^2$. Given the number of pseudo nodes is relatively small, we directly apply **dense pairwise message passing between pseudo nodes** in the original $N^2$, which empowers the pseudo nodes to **capture global information**. The captured global information can be further fed back to graph nodes and serve as global guidance. The learning of global information can be supported by $N^2$ for graph classification where we employ pseudo-node states as the graph-level outputs. \n\n- `Additional pseudo nodes`. Following your suggestion, we further add an additional pseudo node that aggregates messages from the current pseudo nodes. The results are presented in Tab. R2. We can see that the additional pseudo node cannot further benefit $N^2$. However, regarding the pseudo nodes as cluster centers is interesting, and may help us to extend $N^2$ to graph interpretations. We will keep studying it in the future.\n\n| Table R2       | Addition Pseudo Node | Original |\n| :-- | :--: | :--: |\n| amazon-ratings | 49.41  | 50.25   |\n| AmazonPhoto    | 95.36  | 95.75   |\n| PROTEINS       | 76.48  | 77.53   |\n\n\n**Q2**: Discussion between dynamic and adaptive message passing.\n\n**Response**: We kindly refer you to the introduction and related works in our manuscript where we have discussed dynamic message passing with adaptive message passing. To summarize, dynamic message passing `achieves global message passing without forming new bottlenecks` and `requires linear computational complexity`. Dynamic message passing also empowers shared parameters thus `reducing the number of parameters required`.\n\n**Q3**: Broader application of the dynamic message passing.\n\n**Response**: Thank you for bringing up this interesting and inspiring question to us. First, in the context of graph representation learning, dynamic message passing currently only employs neighbor smoothing for local message passing to keep our method as simple as possible. However, `it can be further combined with other graph models to improve the effectiveness of our local message passing`.\n\nSecond, our dynamic pseudo-node strategy `can also be applied to networks such as Transformer to reduce their computational complexity`. This is a very interesting question and we will dig it up in the future.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VuVMxtbvF7", "reviewer": "Reviewer_ZLZY", "summary": "This paper proposes an adaptive message passing scheme for Graph Neural Networks that is based on learnable \"pseudonodes\" which, to a certain extent, decouple the paths along which node features are propagated from the topology of the underlying graph. Both pseudonodes and regular nodes in the underlying graph are embedded in a common space, which allows to utilize the common embeddings to generate proximity-dependent relations between nodes and pseudonodes that are used for a sparse \"global\" message passing layer. The proposed method is evaluated in a node and graph classification experiment for several benchmark data sets and the authors find superior performance on several data sets.", "questions": "I kindly ask the authors to address the following questions, which emerged during my review of the work: \n\n- Please provide more insights on the motivation behind the different ingredients of the dynamic message passing scheme, especially on (i) why the proposed local and global message scheme is supposed to address over-smoothing and over-squashing, and (ii) the motivation of the additional recurrent layer (see comments in [W1] and [W2]). For the first question, I see that there is an experimental analysis but I failed to see how this analysis supports the claims. For the latter question, it would be helpful to include an ablation study that removes the recurrent layer altogether. If I understood the ablation study correctly, currently only the influence of the number of recurrent layers is investigated. Or does the removal of the pseudo-code adaptation (Table 5) correspond to the removal of the recurrent layers?\n\n- Please clarify your contribution over other approaches using adaptive message passing architectures that combine local and non-local message exchanges (see comments in [W3], [W5] and [W6]).\n\n- Please provide details on the choice of hyperparameters and the use of hyperparameter tuning, both for the baseline methods and the proposed architecture (see detailed comments in [W3])\n\n- Please add details on the ablation study results shown in Table 5, especially the number of experimental runs and the standard deviation of results.\n\n- Please increase the font of the results in tables 1 - 4. The text is too small to be readable in a printed version. Please also increase the size of the figures, especially figure 5 and 6, which are way too small to be readable in a printed version.\n\nDuring my review, I found the following typo:\n\n- line 259: Complex_i_ty Analysis", "limitations": "In light of the open questions outlined above, I consider the discussion of limitations in appendix E overly short and not complete.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "[S1] The authors propose a new adaptive message passing scheme that introduces learnable pseudo-nodes and pseudo-edges, thus introducing dynamic pathways for message passing that are independent of the graph topology and that can be trained for a given learning task. The specific combination of pseudonde message passing and the use of recurrent layers is - to the best of my knowledge - new and original.\n\n[S2] The method is evaluated against several baseline methods for a node and graph classification task in 18 small and large-scale benchmark data sets. The experiments show superior performance for the proposed model in several of the data sets (all six data sets for graph classification, eight out of twelve data sets for node classification).\n\n[S3] Addressing limitations of GNNs that are due to over-squashing and over-smoothing, the authors address an important open issue in deep graph learning.", "weaknesses": "[W1] I did not find the motivation to add additional learnable parameters to Graph Neural Networks that decouple message passing pathways from the topology of the input graph convincing. The authors motivate their work based on over-smoothing and over-squashing in GNNs but in my view the paper lacks an intuitive explanation why the proposed dynamic messing passing scheme should mitigate those problems, especially since the architecture additionally includes regular (local) message passing. To this end, I think that the different, complex local and global components of the dynamic message passing - though formally defined - are not explained well in the paper and some of the design choices appear to be rather arbitrary.\n\n[W2] I similarly could not follow the motivation for the addition of the recurrent layer, which the authors argue is added \"to parameterize the displacements of embedded nodes\" and to \"revise the learned distribution [] of all embedded nodes and reshape the dynamic message passing pathways\". A better explanation would be helpful.\n\n[W3] The idea to add pseudonodes for neural message passing has been previously explored, e.g. in the form of a sparse attention mechanism with so-called \"global nodes\" in the Exphormer architecture (https://arxiv.org/pdf/2303.06147). A better explanation of the contribution of the authors would be helpful, especially since the experiments show that the performance is very close to this architecture in many of the experiments.\n\n[W4] There are important details missing in the description of the experimental setup, namely whether hyperparameter tuning has been performed (i) for the proposed mod4el and (ii) for the baseline models. Moreover, in section B.2.2 the authors claim that \"the detailed hyper-parameter settings on all benchmarks are reported in Tab. S6\", however this table only includes hyperparameters for the proposed N2 model and not for baseline methods. I also checked the provided code, which does not cover the baseline experiments.\n\nAs it is - despite the claims made in the answer to Q4 in the checklist - I do not consider the results showing superior performance compared to the baseline models reproducible based on the information provided in the paper and in the supplementary material.\n\n[W5] One could argue that the proposed approach to define pseudo-nodes and pseudo-edges that participate in the message passing could also be seen as a learnable graph pooling layer for GNNs, where pseudonodes take the role of supernodes. As such, I believe that the paper lacks a more detailed discussion of related works on (trainable) graph pooling operations (there is a single mention of graph pooling in the first paragraph of the related work section).\n\n[W6] Similarly, while the paper briefly mentions hierarchical Graph Neural Networks as related work that combines local and global message passing to learn multi-scale features, no explicit comparison to such approaches is included in the experimental evaluation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your valuable suggestions that help us improve our paper. We respectfully refer you to the PDF in the global response for the new figures/tables during the rebuttal due to the limited character number.\n\n**W1&Q1(a)**: Why $N^2$ mitigates over-smoothing/squashing.\n\n**Response**:\n\n1. `Over-smoothing`\n    - Unlike the uniform connection that shares edge weights for all the graph nodes, our dynamic connection measures specific relations for each graph node. Therefore, although two nodes are connected on the input graphs, they receive different outputs from global message passing (MP) and avoid becoming too similar to each other.\n    - Learning node displacements allows the addition of layer input, local and global output. Thus, even with local MP, the other two features maintain high-frequency signals.\n2. `Over-squashing`\n    - Pseudo nodes produce two-hop message highways, detouring messages from the graph bottlenecks.\n    - Dynamic connections avoid forming new pseudo-node bottlenecks that hinder global MP.\n3. `Why local MP`: previous studies show the importance of encoding graph structures[R1]. Therefore, we adopt local MP to implicitly encode graph structures.\n\n> To further evaluate our dynamic connection, we apply the uniform connection to $N^2$, which shows **performance degradation in tackling over-smoothing/squashing problems** in *Fig R1 in the PDF response*.\n\n**W2&Q1(b)**: Motivation and ablation on the recurrent layer.\n\n**Response**:\n\n- `Motivation for the layer`: We propose the recurrent layer, including BOTH pseudo-node adaptation and dynamic MP, to move nodes from current positions towards the optimal positions (L147-148).\n    - To move towards optimal position: Given the current node positions, a recurrent layer learns the displacements the nodes should take, changing their distribution in the space. \n    - To base on current positions: The recurrent layer employs pseudo-node adaptation and bases the edge weights for MP on the spatial relations between nodes, to adapt to nodes in various positions. The changes in position also reshape the spatial relations and thus reshape the message pathways.\n- `Motivation for the recurrence`: We adopt a single recurrent layer used recurrently to reduce the number of parameters, instead of modeling node displacement by different layers for each step.\n- `Ablation`. We have already evaluated layers without recurrence in Sec 5.3.4. Multiple recurrent layers do not share parameters and thus are not recurrent. We further remove the layer completely. With only input and output modules employed, *Tab R1(b) in the PDF response* shows performance degradation.\n\n**W3&Q2(a)**: Contribution compared to Exphormer.\n\n**Response**: \n\n1. Compared to Exphormer, we highlight our $N^2$ as follows\n    - `A new perspective` to model MP, where nodes are distributed in a common space; they communicate based on their spatial relations and learn to optimize their positions.\n    - `Fewer parameters` by a single shared recurrent layer.\n    - `Better scales up to large graphs` (Tab 4).\n\n2. Technically speaking, our $N^2$:\n    - `decouples global MP` into g(raph)-nodes to p(seudo)-nodes, p to p, and p to g. Instead, Exphormer performs MP between all nodes, which cannot differentiate between messages from pseudo or graph nodes.\n    - `multiplies proximity` with messages. Instead, Exphormer employs normalized attention, which can yield equally small weights and attenuate the messages, especially when the optimal assignment involves a large number of graph nodes to the same pseudo node.\n\n> We also evaluate the mixed messages or attention from Exphormer on $N^2$, where both show performance degradation in *Tab R1(c) in the PDF response*.\n\n**W4&Q3**: Hyperparameters.\n\n**Response**: We have performed grid search for the hyperparameters of $N^2$ (Tab S6) and the reproduced models based on validation loss. We emphasize that the superiority of our results is valid and the baseline results can be fully reproduced. Please refer to our AC for the `URL of detailed hyperparameter config files`.\n\n**W5&Q2(b)**: Design comparison with graph pooling.\n\n**Response**: First, we clarify that we have provided a discussion on graph pooling in L86-91, not just in L76. Second, the differences between pseudo nodes and graph pooling can be summarized as:\n\n- `Different objectives`. Pseudo nodes optimize communication efficiency while pooling nodes capture the hierarchy in the graph structures, ensuring better structure compression.\n- `Physical connection`. Pseudo nodes are physically connected to graph nodes as part of the graphs and participate in the MP. In contrast, pooling nodes are higher-level abstractions of graph nodes and are not physically connected with them. \n- `Intercommunication`. Pooling nodes use the coarse adjacency matrix for the MP. Pseudo nodes are free from structure-preserving constraints and learn fully connected pathways.\n\n**W6**: Comparison with hierarchical GNNs.\n\n**Response**: We have performed comparisons in Sec 5.1 with some representative hierarchical GNNs from L86-91. Please let us know if you are referring to other types of GNNs.\n\n**Q4**: Details for Tab 5.\n\n**Response**: Tab 5 follows the settings from Sec 5.1/5.2. and the hyperparameter setups in Tab S6. *Tab R1(a) in the PDF response* shows the standard deviation results for three runs.\n\n**Q5**: Font size, typo.\n\n**Response**: Thank you for your suggestions. We will fix them in our revision to ensure readability.\n\n**Q6 (Limitation)**: More limitation discussion based on the reviewer's open questions.\n\n**Response**: We will revise our paper based on your reviews. For Q1(i), we can only provide intuitive/empirical analysis, not rigorous proof due to limited rebuttal time. We will add this to our limitation part and keep working on it.\n\n[R1] Do Transformers Really Perform Bad for Graph Representation? NeurIPS21", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "t2POdpnVKT", "reviewer": "Reviewer_4Q2o", "summary": "The authors propose a dynamic message-passing scheme where graph nodes and learnable pseudo nodes are projected into a common space. This allows non adjacent nodes to communicate immediately whilst retaining linear complexity. The model performs well on a range of benchmarks and can reduce problems with over-squashing/over-smoothing compared to a baseline MPNN.", "questions": "- Do you use positional/structural encodings on these benchmarks? Does your baseline GIN/GCN + pseudo node also use these encodings? \n- It is not clear how the hyperparameter sweep is performed and what parameters are optimised over and on what metric. Could you provide some information on this?\n- Do you have any intuition why the method would outperform GTs on this benchmark? (not just have a lower computational complexity)", "limitations": "some limitations are outlined in the appendix.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The novel (to my knowledge) method is explained in depth and well outlined. It is clearly explained and evaluated in the context of other approaches (rewiring, virtual node, transformers). \n- The results/experiments are really strong and the method is shown to help alleviate over-squashing/over-smoothing and performs well on a wide range of benchmarks. \n- Visualising the distribution of embedded nodes helps with understanding what is happening in practice and I really like this empirical understanding. \n- It is clear how this method lowers the computational complexity over methods such as Graph Transformers and the results indicate it can still outperform these approaches.", "weaknesses": "- In line 45 the authors argue for their approach over using a single virtual node due to the fact that a VN can have a message-passing bottleneck. Firstly, I think this should be explained more rigorously rather than citing [1] as it is a key argument of the paper to not just have uniform global connections. Additionally, the extent to which your method alleviates this issue needs to be better explained. [Line 297], You use the balanced load argument to say that this helps alleviate the bottleneck. However, increasing connections between nodes within a community and not having global connections between communities would actually `increase' the bottleneck on those edges between the communities. The virtual node itself has less of a bottleneck BUT this does not mean bottlenecks in the graph are reduced. \n- On a similar note to above, we can reduce the bottleneck of the virtual node by subsampling edges (expander) or by adding more of them (this effectively increases their width) [1]. It is not clear in the paper how your dynamic and weighted approach improves over this (in terms of bottlenecks or some other property). \n- There are other dynamic message-passing schemes such as DRew [2]. The paper seems to argue for their approach over something like this due to pseudo nodes directly enabling global message-passing [line 82]. Given that these rewiring approaches seem relevant and closely-connected, I think this comparison and why your method can improve over this needs to be extended and evaluated in depth. For instance, in this case why would you need global message-passing in layer 1 when we always use > 1 layers?\n\n[1] Shirzad  et al. EXPHORMER: Sparse Transformers for Graphs. ICML 2023.\n\n[2] Gutteridge et al. DRew: Dynamically Rewired Message Passing with Delay. ICML 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the valuable suggestions for our paper. Under your guidance, we have discovered new advantages of $N^2$ compared to uniform connections and rewiring. We also kindly refer you to the PDF in the global response for the new figures/tables during the rebuttal due to the limited character number.\n\n**W1&W2**: More explanation of the pseudo-node bottleneck and why $N^2$ can reduce the bottlenecks in both pseudo nodes and input graphs.\n\n**Response**: \n\n1. `Uniform connection leads to pseudo-node bottlenecks` has been explained in L42-45 and Fig 1, before citing [1]. More rigorously, [1,R1] refer to **bottlenecks as nodes with large effective receptive fields**. The uniform connection forms pseudo-node bottlenecks by taking all the graph nodes into the receptive field equally. This results in large effective receptive fields on large-scale graphs and thus forms bottlenecks. We also evaluate $N^2$ with the uniform connection in *Fig R1 in the PDF response*, which shows inferior performance in tackling over-squashing.\n\n2. `Adding pseudo nodes` with uniform connection provides more pseudo-node bottlenecks, where each pseudo node still incorporates all graph nodes into its receptive field.\n\n3. `Subsampling edges` can remove some informative interaction between nodes, leading to sub-optimal message passing.\n\n4. $N^2$ `for pseudo-node bottlenecks`: we have provided both intuitive and empirical analysis in L48-49 and Sec 5.3.3 to show that $N^2$ DOES NOT form pseudo-node bottlenecks. $N^2$ learns the edge weights between graph and pseudo nodes through spatial relations. Therefore, **it can eliminate messages from certain nodes while preserving the others**, reducing the size of the effective receptive fields.\n    - Note that L297 refers to the pseudo-node bottlenecks specifically. We will fix this in the revision.\n\n5. $N^2$ `for input-graph bottlenecks`: we have provided empirical results in Sec 5.3.2 that $N^2$ can tackle over-squashing. This is because $N^2$ **optimizes the global two-hop message highways based on specific tasks and avoids forming new pseudo-node bottlenecks**. The global highways detour messages from the input-graph bottlenecks. Therefore, the original bottlenecks may still exist but are well circumvented.\n\n**W3**: Comparison with rewiring methods (DRew).\n\n**Response**: Thank you for bringing up this insightful question to us. The rewiring methods and pseudo-node methods actually represent the local-to-global and the global thread, respectively. Both threads are effective in improving message passing. We choose DRew[2] to represent rewiring methods, which has been referred to by many reviewers. The main reasons we need globality in one layer are:\n\n- `Less layers`: Pseudo-node methods require less layers than rewiring methods. For example, 6-layer $N^2$ surpasses 13-layer DRew in Tab S7 in the paper. We note that DRew with positional encodings will not be taken into comparison, because of the injected globality into node features.\n- `Less memory usage`: Rewiring methods either directly add edges to the input graphs or gather messages from multi-step neighbors in one layer. Both require more memory usage. We evaluate DRew on the same dataset in Sec 5.3.1. DRew is out-of-memory when the number of graph nodes surpasses 200,000 with 2 convolution layers and 8,000 with 3 layers.\n- `Better efficiency`: Rewiring edges is also time-consuming. We compare the computational complexity between $N^2$ and DRew with the same number of convolution layers/recursive steps. *Fig R2 in the PDF response* shows that DRew requires more time when scaling to large graphs.\n- `Simpler preprocess`: $N^2$ only requires the pre-construction of the adjacency matrix while DRew sample or select multi-step neighbors. We even encountered the timeout problem when trying a larger number of layers (5,6) on DRew on large graphs such as ogbn-arxiv.\n\nBesides DRew, we have also compared with other rewiring methods, such as GPRGNN and H$_2$GCN in Tab 3 and 4.\n\n**Q1**: Positional/structural encodings usage.\n\n**Response**: No positional or structural encodings are used for $N^2$. Except for being specifically noted, all the baseline results are from the original papers. Among X+pseudo node methods, only MPNN+pseudo node uses the positional encoding.\n\n**Q2**: Hyperparameter settings.\n\n**Response**: We perform grid search for the hyperparameters based on the loss of the validation split, including the recursive steps $\\in$[1,10], the hidden and the state space dimension $\\in${64,128}, the number of pseudo nodes $\\in${8,16,32,64,128,256,300,320}, and dropout $\\in$[0,0.8] with step equals 0.1. The rest of the hyperparameters are fixed as reported in the Appendix and have not been specially tuned on individual datasets. \n\nAll the learnable parameters in $N^2$ are optimized during training, including the weights in the linear transformation, $\\lambda$ in the proximity measurement, and the pseudo/class-node states. The cross-entropy loss is adopted for classification and the L1 loss for regression.\n\n**Q3**: Why $N^2$ outperforms graph transformers.\n\n**Response**: We attribute this to the flexible pseudo nodes:\n\n- `Simpler objective`. Instead of optimizing relations with all the other nodes, $N^2$ empowers the graph nodes to focus on relations with pseudo nodes, which are of a much smaller amount.\n- `Information filter`. The pseudo nodes can also be regarded as the information bottleneck [R2] in the graph space which filters out redundant information. This can be supported by the pseudo-node ablation in Fig. 7, where node amounts are upper-bounded to serve as an effective information filter. \n\n[R1] On the Bottleneck of Graph Neural Networks and its Practical Implications, ICLR21\n\n[R2] Deep Variational Information Bottleneck, ICLR17", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fvUlRnt681", "reviewer": "Reviewer_UBFx", "summary": "This work proposes a new dynamic message passing method $N^2$, which initializes a number of pseudo nodes, and apply message passing across graph nodes and pseudo nodes. The message passing scheme relies on the proximity of the node embeddings, and the node embeddings are updated through message passing. The method is quite dynamic and flexible. Besides, it is empirically shown to alleviate oversquashing and oversmoothing problems. Experimental results show the significance of the proposed method.", "questions": "- It is not intuitive to me why to use recurrent layers, except for the good property of weight sharing. Can you explain it?\n- Why use proximity measurement instead of some distance metrics?", "limitations": "As mentioned by the authors, the performance deteriorates when the number of recurrent layers grow too large.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- Overall, the writing is good and clear, the concepts are precisely described, and the introduction of background is easily understandable. \n- The methodology is quite interesting, and the message passing design makes sense. \n- The experimental results are strong on most datasets. And the method is widely applicable to both graph and node level prediction. The ablations are carefully designed and the visualizations are pretty good.\n- The proposed method exhibits good performance on oversquashing and oversmoothing problems.", "weaknesses": "- It would be good to have theoretical explanations why the method works well against oversquashing and oversmoothing problems, though not mandatory.\n- It would be good to compare with some graph structure learning or graph rewiring work. The baselines are basically GNNs and graph transformers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your kind suggestions and insightful questions about our work. We hope the following response can address your concerns. We also kindly refer you to the PDF in the global response for the new figures/tables during the rebuttal due to the limited number of characters.\n\n**W1**: Theoretical explanations on why $N^2$ works for over-squashing/smoothing.\n\n**Response**: We provide some intuitive and sketchy theoretical analysis. We will keep working on this in the future.\n\n- `Over-smoothing`: $N^2$ learns the displacements of nodes and gives rise to the linear combination of the layer input, the local message passing output, and the global message passing output. Specifically, the layer input represents the output of an `all-pass filter`, the local output is from a `low-pass filter`, and the global output is from a filter that aggregates messages from nodes of learnable similarity, and thus possesses `learnable frequency characteristics`. The messages from the all-pass filter and the learnable filter prevent the output from over-smoothing.\n    - We must note that global message passing with the uniform connection provides the SAME global output for all the graph nodes. This output can be regarded as a shared bias term and cannot alleviate over-smoothing. Please refer to *Fig R1b in the PDF response* for empirical results.\n\n- `Over-squashing`: $N^2$ tackles over-squashing by detouring from the original graph bottlenecks and avoiding forming new pseudo-node bottlenecks.\n    - First, pseudo nodes provide two-hop message highways for graph nodes. Therefore, graph nodes do not have to pass messages through the original bottlenecks.\n    - Second, the pseudo-node bottlenecks stem from the overwhelming number of graph nodes in the receptive field of each pseudo node. However, by multiplying edge weights with the messages from these nodes, certain messages can be eliminated and thus exclude the nodes from the receptive field. We can define the effective receptive field size based on the value of the edge weights, where nodes with smaller edge weights are eliminated from the effective field. This elimination reduces the size of the effective receptive field and avoids forming bottlenecks.\n        - Uniform connection shares the same edge weights for the messages from all nodes. Therefore, these messages are either completely eliminated or preserved, which cannot reduce the size of the effective receptive field. In *Fig R1a in the PDF response*, we show that $N^2$ with uniform connection is less effective in tackling over-squashing.\n        - Our dynamic connection measures the specific edge weights for each node, learning to eliminate messages from certain nodes, and thus reduce the size of the effective receptive field.\n\n\n**W2**: Comparison with graph structure learning or graph rewiring methods.\n\n**Response**: Thank you for your suggestion. There are some graph transformer or GNN methods in our manuscript that also employ graph structure learning or rewiring strategies, such as Exphormer with the expander graph and DRew, GPRGNN, and H$_2$GCN with edge shortcuts. Except for these methods, we also compared $N^2$ with DGM (L79-80), a graph structure learning method, and the results are presented in Tab. R3. $N^2$ shows better performance compared to DGM.\n\n| Table R3 | CORA  | CITESEER | PUBMED |\n| :------- | :--: | :--: | :--: |\n| DGM      | 84.6 | 74.8  | 88.6  |\n| $N^2$    | **85.4** | **77.6**  | **90.6**  |\n\n\n**Q1**: Why use the recurrent layer?\n\n**Response**: \n\n- `Why recurrent layer`: The recurrent layer is the core of $N^2$.  It is an implementation of the message passing in the common space from Sec 3. The recurrent layer, including pseudo-node adaptation and dynamic message passing, empowers dynamic interactions between nodes. $N^2$ employs the layer to move nodes recursively to their optimal positions.\n\n- `Why recurrence`: The main reason $N^2$ uses the parameters recurrently for the layer is to **largely reduce the number of parameters**. According to the ablation study in Fig. 8, nodes require multiple steps to move to their optimal position. Each step corresponds to a new layer with a set of parameters. To reduce the number of parameters, we conducted an ablation study and found that the layers can learn to move nodes based on their current positions. Therefore, a single set of parameters will be sufficient and thus give rise to the recurrent layer.\n\n**Q2**: Why propose proximity measurement instead of distance metrics?\n\n**Response**: Compared to distance metrics, such as Manhattan and Euclidean distance, proximity measurement has **lower spatial complexity**. We tested distance and proximity with `torch.cdist` and `torch.matmul` during model design. Results show that distance-based $N^2$ is on par with proximity-based $N^2$, but the distance version encounters out-of-memory problems under many hyperparameter settings. Therefore, we choose proximity (inner product) for $N^2$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We appreciate all the valuable suggestions and the time the reviewers take on our work. Your reviews help us a lot to improve the manuscript.

**Summary of strengths**. We sincerely appreciate that you find our method:

- novel and interesting (reviewers Qj5n, ZLZY, 4Q2o, and UBFx);
- clearly explained and evaluated (reviewers 4Q2o and UBFx);
- mitigates over-squashing/smoothing, an important open issue in deep graph learning (reviewers ZLZY, 4Q2o, and UBFx);
- shows guaranteed complexity requirement (reviewers Qj5n and 4Q2o);
- provides good visualization and analysis of the model (reviewers 4Q2o and UBFx);
- exhibits promising experimental performance (reviewers Qj5n, ZLZY, 4Q2o, and UBFx);
- widely applicable (reviewers 4Q2o and UBFx).

In the subsequent responses, we aim to address your concerns comprehensively, providing an item-by-item response to each of your comments.

We have provided new empirical results suggested by the reviewers. *Due to the limitation of character numbers, Tab R1, Fig R1, and Fig R2 are displayed in the global response PDF.*

Meta-review: The paper presents a new approach to address the limitations of traditional message-passing in Graph Neural Networks (GNNs). The proposed dynamic message-passing introduces learnable pseudo nodes projected into a common space with graph nodes and provides a flexible and low-complexity alternative to existing methods. The introduced GNN model, referred to as N2, demonstrates good performance across a wide range of tasks.

The reviewers recognized the originality of the proposed method and appreciated the thoroughness of the experimental evaluation, which spans multiple benchmarks. Additionally, the authors provided convincing explanations in their rebuttal regarding the motivation behind pseudo-bottlenecks and the relationship of their work to related methods like graph pooling, graph rewiring, and graph transformers. The presentation of these connections in the paper could be improved. Nonetheless, the paper’s contributions are substantial, and the dynamic message-passing mechanism offers a promising direction for future GNN research. The authors are encouraged to revise the paper based on the reviewer feedback to better explain its context and contributions.
Decision: Accept (poster)