Redundancy-Free Message Passing for Graph Neural Networks
Authors: Rongqin Chen
Shenghui Zhang
Leong Hou U
Ye Li
Venue: NeurIPS 2022 Accept (2022)
Keywords: redundancy-free
graph neural networks
graph similarity
over-squashing

Abstract: Graph Neural Networks (GNNs) resemble the Weisfeiler-Lehman (1-WL) test, which iteratively update the representation of each node by aggregating information from WL-tree. However, despite the computational superiority of the iterative aggregation scheme, it introduces redundant message flows to encode nodes. We found that the redundancy in message passing prevented conventional GNNs from propagating the information of long-length paths and learning graph similarities. In order to address this issue, we proposed Redundancy-Free Graph Neural Network (RFGNN), in which the information of each path (of limited length) in the original graph is propagated along a single message flow. Our rigorous theoretical analysis demonstrates the following advantages of RFGNN: (1) RFGNN is strictly more powerful than 1-WL; (2) RFGNN efficiently propagate structural information in original graphs, avoiding the over-squashing issue; and (3) RFGNN could capture subgraphs at multiple levels of granularity, and are more likely to encode graphs with closer graph edit distances into more similar representations. The experimental evaluation of graph-level prediction benchmarks confirmed our theoretical assertions, and the performance of the RFGNN can achieve the best results in most datasets.

Redundancy-Free Message Passing for Graph Neural Networks
Rongqin Chen 1,2 chen ronnggincccconeec........ um edu mo
Shenghui Zhang' zhang shenghui@connect edu mo
Leong Hou U
Ye Li 2 ye. li@siitt..... ac. cn
ryanlhu@um.. edu, mo
State Key Laboratory of Internet of Things for Smart City, University Macau, Macao SAR, China Shenzhen Institutes of Advanced Technology. Chinese Academy of Sciences, China
Abstract
Graph Neural Networks (GNNs) resemble the Weisfeiler-Lchman (1-WL) test; they iteratively update the representation of each node by aggregating information from WL subtrees. However, despite the computational superiority of the iterative aggregation scheme, introduces redundant message flows to encode nodes. We find that the redundancy in message passing prevented conventional GNNs from propagating information of long-length paths and learning graph similarities. In order to address this issue, proposed Redundancy-Frit Network (RFGNN), in which the information of each path (of limited length) in the original graph is propagated along message flow devoid of duplicate edges. Our rigorous thcoretical analysis demonstrates the following advantages of REGNN: (1) The height & REGNN is strictly more powerful than the k-layer WL-test based GNNs; (2) REGNN efficiently propagates structural information in original graphs, avoiding the over-squashing issue; and (3) REGNN encodes graphs of small graph edit distances into similar representations in practice. The experimental evaluation of graph property prediction tasks validates theoretical statements. And RFGNN achieves the best performance in most challenges.
Graph Neural
Introduction
Graph Neural Networks (GNNs) generally imitate the Weisteiler-Lehmann (1-WL) test [1] in the sense that they iteratively update the representation of each node of graph by aggregating information from its neighbors [2], which are referred to as WL-test based GNNs in this study. The iterative neighborhood aggregation scheme encodes trees (called WL subtrees [3]), where node's WL subtree children are its graph neighbors, so that a WL subtree is a height- beaaahtballaneed tree. Research on GNNs has made great strides and achieved remarkable success in recent years. Nevertheless, the vast majority of studies do not break the paradigm of repetitive neighborhood aggregation, which provides computational superiority but generates negative consequences due to message flow redundancy in tree-like encoding. Figure 1 illustrates example of message flow redundancy in computational graph. Message flow redundancy prevalent, especially when the number of message passing iterations (a.k.a. neural network layers) increases.
A recent study has been conducted the computation of redundancy in GNNs, e.g. [4]. We add note that the computational redundancy is orthogonal the message passing redundancy.
36th Conference on Neural Information Processing Systems (NeurIPS 2022).

---

(c) A message flow that transmits redundant information (i.e., the orange node)
(a) Input Graph
(b) 2-Layer GNN Computational Graph
Figure 1:
Redundancy exists in message flows, which are propagation chains in GNN computational graph that deliver the information from input nodes to output nodes.
The redundancy phenomenon is accompanied by the problem of over-squashing, which refers to the phenomenon in which the information originating from distant nodes can be distorted, thus limiting the efficiency of message passing for tasks that rely on long-distance interactions [S]. This issue attributable to the bottleneck of compressing rapidly growing number of neighboring nodes into a vector of finite length [6] and to the failure of certain input features to influence the output representation [5]. However, in previous studies, the understanding of over-squashing and the explanation for why it occurs are still deficient. In this study, we carefully analyze the influence of an input feature on an output representation along a trail (extracted from the original graph), and we observe that longer trails typically have smaller impact than shorter trails in the neighborhood aggregation process. One key reason behind this that short trails usually result in a great number of redundant message flows in the computational graph.
According to previous research [7. 8. 9, 10], fundamental problem of graph learning to quantify the similarities between graphs. In the real world, many graphs, such as molecules, have structures at both coarse levels (such as chains, rings, and trees) and fine levels (like chemical bonds and functional groups). Some scholars [11] believe that an ideal method of graph similarity measurement should be able to capture subgraphs at different levels of granularity. However, 1-WL [3] can only capture the graph similarity at coarse levels because WL subtrees are height-balanced trees. Besides, WL-test based GNNs tend to encode two graphs that yield similar message flows as similar representations. However, even if only one edge in the two original graphs is different, it can lead to two very different message flow sets due to message flow redundancy. Thus, WL-test based GNNs may have insufficient expressive power to measure graph similarity.
We propose Redundancy-Free Graph Neural Network (RFGNN) to address the aforementioned issues. We first eliminate message flow redundancy with a concept called path-search- trechheeeeeeee (a.k.a. breadth-firs. tree), which is constructed by running a breadth-firss search (BFS) from a node [12]. Since there are no repeated nodes in each path in the path-search-tree, by using the tree as the message passing graph, the resulting model would not suffer from message flow redundancy. However, this simple path- search-tree model cannot capture some graph structures, e.g., ring. To enhance the expressiveness of the model, we define a new concept called extended path (epath), which can represent a ring structure when its starting and finishing nodes are the same. Based on epath, we propose a concept called Truncated ePaths Tree (TPT), an epath-search-tree obtained by running a BFS, where all epaths of limited length starting from the node are accessed. Given TPT (of graph node), REGNN is a neural network to perform bottom-up message passing. Finally, we collect the representations of all TPTs of graph in order to update the representation of the entire graph.
In comparison prior research in the field of GNNs, the new findings of this work were summarized as follows: 1) To the best of our knowledge, this is the first study that investigates the theoretical and practical implications of message flow redundancy in GNNs; 2) We proved that the height à RFGNN is strictly more expressive than k-layer WL-test based GNNs; 3) De-redundancy balances the influence of epaths starting at the same node during message passing, propagates structural information in original graphs efficiently, and reduces over-squashing: 4) RFGNN always generates similar message flows for similar graphs compared to WL-test based GNNs; hence, RFGNN can learn better representations of similar graphs than WL-test based GNNs.

---

The rest of this paper is structured as follows. Section 2 outlines the basic theories of GNNs. In Section 3, we demonstrate that message flow redundancy prevalent GNNs and analyze why it contributes to the issue of over-squashing in WL-test based GNNs. The framework of RFGNN presented Section 4, which not only eliminates the redundancy in computational graphs but also provides several additional advantages. Related work is then discussed in Section 5. Section 6 empirically validates RFGNN on a variety of graph property prediction challenges and demonstrates that RFGNN achieves statc-of-the-art performance on the vast majority of tasks. The conclusion is given in Section 7.
2 Preliminaries
We begin by reviewing the most commonly used message passing paradigm and its derivative GNNs, as well as introducing our notations. Let G (V, E) E be a graph, where V = V(G) = {1. 2....). V x V, and G is the graph set consisting of all possible graphs. The nodes and edges in G can have feature vectors associated with them, denoted by x. for u E V and eu, for (u, v) E E. In this work, we consider the graph property prediction problem follows: given a set of graphs (Gi,..., G C & and their labels (Vı.-... UNJ } S y, we aim to learn a representation vector he that helps to predict the label of entire graph by a predictor, yc p(hc).
E = {G)
Message passing and graph neural networks. GNNs iteratively update the representation of a node by aggregating its ncighbor information. The I-th layer GNN can be described as
h (0 (n! (n!-1), UUEN(()))
((-))) h -)
(I)
(u,n)
where 2)(0)) and ( denote differentiable functions such as MLPs (Multi Layer Perceptrons), U denotes differentiable and permutation invariant aggregator, (e.g., sum and mean), h (I) is the node representation, and (w.)) is the edge (u, v) representation transformed from ((,,)) by a differentiable function such as linear function. We initialize h x.. The readout function aggregates node
representations from the final layer to obtain the entire graph representation he:
ha = x ((n lueG))
The readout x be simple permutation invariant function such
Weisfeiler- Lehmmn (WL) test and WL-subtree. The graph isomorphism problem is to identify whether two graphs are topologically equivalent, i.e., isomorphic. The Weiseeiler-Lehman (1-WL) test [I] iteratively updates the label of a node by hashing the labels of its own and neighbors. If the node labels differ in any iteration, then 1-WL considers the graph to be non-isomorphic. Based on 1-WL, Shervashidze et al. [3] propose WL-subtree, which is a kernel method to measures the similarity of graphs based on the number distinct node labels, where node label indicates a WL subtree. In consequence, the graph similarity is then measured by the number of distinct WL subtrees.
Computational graph. Computational graphs represent neural networks as graphs on which gradients can be conveniently computed using chaining laws [13]. In message passing GNNs, the computational graph a node is the message passing graph that aggregates neighborhood information into the node. The computational graph is jointly decided by the adopted message passing paradigm and the structure of the input graph.
3 Message Flow Redundancy and Practical Implications
In this section, first explain the redundancy issue in computational graphs and then discuss the over-squashing issue. Without loss generality, we discuss the computational graph k-layer WL-test based GNN for (the representation of) node. All the proofs can be found in Appendix A.

---

3.1 Message Flow Redundancy in Computational Graph
Definition 1 (Message flow). A message flow p computational graph depicts the propagation chain of an input feature from an input node to an output node, where p(i) denotes the i-th node of (zero based index).
WL-test based GNN iteratively updates the node representation by aggregating the neighbor information, where the message passing process (of the neighbor information) is analogous the traverse of the graph by walks, defined as follows.
Definition 2 (Walk). A walk is sequence of graph nodes and edges formed by graph traversal that permits backtracking and self-looping
Corollary 1. A message flow for output node u in the computational graph is walk of the same length that ends at u in the original graph.
Definition (Trail). A trail is succession of edges with no repetition, where (r) refers to the i-th node of tr (zero based index).
For instance, 41 + U2 U3 > u1 44 is valid trail, which has no repeating edges.
Lemma 1. The message flows that propagate the information of a trail are the walks of the trail from its beginning node to its ending node.
Message flow redundancy. trail can not be compressed since there is no repeated edge in the trail. As illustrated in Figure 2, we can transform trail into message flows via unordered sampling with replacement, sampling fashion in which repetition is allowed and ordering does not matter [14, Section 1.4.. Message flows derived from the same trail carry identical trail-related information. The backtracking and self-looping edges in message flows do not provide additional information and therefore redundant.
Trail
(c) Sampling Self-Loop Edges
(b) Sampling Backtracking Edges
(d) Derived Message Flow
The process of deriving a message flow from trail: Firstly, backtracking edges are sampled and placed in the trail. Then, self-loop edges sampled and inserted into the trail.
Figure 2:
Message flow redundancy is prevalent. Suppose there is trail of length and message flow of length derived from the trail. The backtracking edge of a self-loop edge is also a self-loop edge. Thus, begin by sampling backtracking edges from the backtracking edges. After the backtracking edges are placed, we sample k edges. Lemma demonstrates that message flow redundancy is widespread because trail shorter than the number of GNN layers would result in many message flows with backtracking and self-loop edges.
2s self-loop edges from the r + 1 + 2s self-loop
Lemma 2. Given a length-r trail, the number of length-k message flows derived from the trail is
(r + 1 + 25) r--
where <r k.
3.2
Redundancy Causes Message Over-squashing
Message flow redundancy in computational graphs comes with a phenomenon known as over- squashing, which occurs when GNNs are unable to propagate information effectively across graph

---

[6]. Recently Topping et al. [5] have proposed the Jacobian of a GNN-output to quantify the effect of over-squashing.
The influence of a change. Assume there is a graph with nodes u and e, as well as a k-layer WL-test based GNN update node representations. The Jacobian measures how change in the input feature X, affects the node output h() as
Th (k) /0x.-
(3)
Similar to [5], to avoid heavy notations, the node attributes and representations are assumed to be scalar; this assumption simplifies the analysis, whereas the vector case yields equivalent results.
Lemma 3. Assume there is graph with node set V, nodes u, v E V, and the computational graph of a k-layer WL-test based GNN for u. If all length-k k paths in the computational graph for are activated with the same probability, we can measure the relative inftuence of the input feature x, on (k) the node output ha)
on average,
Ti
A
Th 10x
E
(4)
Ever Thu 10x
Ever
Ili
A
u,
where À A + I the adjacency matrix of the graph with self-loop.
The influence of a change along a message flow. Assume there is a graph, the computational graph of a k-layer WL-test based GNN and its message flow p. The effect of change in the node
feature Xp(D) on the output node h (k) along the message flow p (a. a the influence of Xy(0) on p(k)
(k) along p) can be computed as pkk)
0h p(k) Op
0h P0)
(5)
1=k
1(1-1)
Lemma 4. Assume there is graph with node set V, the computational graph of a k-layer WL-test based GNN for node, and message flow p in the computational graph. We compute the relative
influence of x on h (K)
p(k) along p. on average, as
Oh (k) P(K)
00p
IIi Ap(D.p((-1) Ever
E
Σ Epephh
(k) /Op'
[Ti Ā x(k).o'
where Ā= = + is the adjacency matrix of the graph with self-loop and is the set of message flows that end trkk).
The influence of change along trail. Given a graph with trail tr and the computational graph of k-layer WL-test based GNN for tr's head node. Let Pa be the set of message flows derived from within the computational graph for the node (r))). How a change in Xtr(o) will be propagated
along and affect h (k)
(r(rr) (a.k.a the influence of Xtr(o) h (k)
(r()) along (r). denoted as @h /atr,
(8)
is computed as the summation of the influence of x (0) on (n(r) along all message flows belonging
to p* i.c.,
Oh
(r(r)) atr
Th
(k) (r(rr))
Σ
Op'
P'EP-
Corollary Assume there is a graph with trail tr and the computational graph of a k-layer WL-test based GNN for tr 's head node. We compute the relative influence along tr, on average, as
/Otr
@h(1) (6)
Epep. II Ap(r)
E
Σ Eyepoh
(K) /0/
Evev
[T.=k A
p(k),o'
5

---

where Ā= A + I is the adjacency matrix of the graph with self-loop and P is the set of message flows derived from ir.
The relative influence along trail is proportional (in terms of probability) to the number message flows derived from the trail, according Corollary 2. According to Lemma 2, trail typically produces fewer message flows than its child trail. Therefore, the effect along a lengthy path is always less than that of its sub-path. Thus, redundancy in the message passing paradigm is significant element the occurrence of over-squashing. Topping et al. [5] stated the phenomenon of over- squashing occurs when the absolute value of the Jacobian Thu (k) /0x, is small. Supplementally, we find the phenomenon over-squashing would occur even the absolute value of the Jacobian Th (k) /ox, is large; keeping the influence along tr constant, the relative influence along tr decreases (k) as the absolute value of the Jacobian ( (0xtr(() increases.
4 Redundancy-Free Graph Neural Network
the last section, we discussed message flow redundancy and its practical implications. To overcome this issuc, propose Rodundancy-Free GNN (RFGNN), kind of message passing GNN that is not only message flow redundancy-free but also improves the overall expressive power and message passing capability and thus generates better performance. All proofs for RFGNN can be found in Appendix B, and the space and time complexity analysis can be found in Appendix C.
4.1 The REGNN Framework
We first discuss the redundancy-free message passing paradigm based on a concept called extended path, epath, formally defined Definition 4 (Extended Path, epath). An epath is a path that has no repeated node along the path except that the starting node allowed to be the ending node when the length of the path is larger than 2.
For instance, u1 + W2 + Ug + u1 is a valid epath, where u1 is repeated at the ending node. Note that 1/2 W1 is not epath since the length not larger than 2.
component a graph is a connected subgraph that not part of any larger connected subgraph [15]. Breadth-first search (BFS) [12] allows us traverse all epaths of component from a node. On the basis of epath and BFS [12], we define the term Truncated ePath Tree (TPT) as follows.
node TPT
node not TPT
Input Graph
(b) Process of ePaths Search
Figure 3: The height-4 Truncated ePath Tree of G from u (hexagon).
Definition 5 (Truncated ePath Tree (TPT)). Given graph G = (V, E) and node E V, the height k TPT TPT (G..) is an epath search tree obtained by running a BFS from where all epaths of length up to are accessed. Additionally, ( refers to a node u at level and (v) denotes the child node set of the node on level k.

---

As shown in Figure 3, the original graph can form height-4 truncated epath tree (TPT) as tree structure of 8 nodes, where every tree path (from the root to the leaf) an epath of length smaller than or equal to 4.
Definition 6 (Truncated ePaths Forest (TPF)), Given a graph G = (V, E), the height k TPF of G is a multiset for all nodes u E V
TPF = {{ {(TPT(G..) Vu E v]]
Redundancy-Free Graph Neural Network (RFGNN). Assume there is graph G, TPT E TPFo and u E V(TP)) at level (1 1). We denote Xa (1-1) as a hidden feature transformed from the node features of u, h hidden feature of the subtree rooted at node C(I-1) (u), and ea,e hidden feature transformed from the edge features of (u, v). We can describe the RFGNN representation
(!)
update process of node u at level (I 1) as follows.
h (1-1) = (0 (x(-1), (e)))
a.e0 h!!)
where U denotes differentiable and permutation invariant function, e.g., sum and mean, and ø and & denote differentiable functions such as MLPs (Multi Layer Perceptrons).
To obtain the entire graph representation hg, we adopt readout function that aggregates the root node representations of the TPTs of G:
he = x ({ (oot(IPT)
TPT E TPFa)))
(8)
where the readout function X can be a simple permutation invariant function such as sum.
Symmetries. Given graph G with adjacency matrix A and feature matrix x, function f is (node) permutation equivalent if f(A, x) = f (MAM7, .x)., for any permutation matrix M. GNN layers respect this equation, which ensures they compute the same functions up to permutation (i.e., relabeling) of the nodes. Similarly, RFGNN is equivalent with respect to permutations of nodes, since the resulted TPTs and TPF is independent on any node permutation.
Corollary 3. Redundancy-Free GNNs are permutation equivalent.
Memory consumption. RFGNN's memory consumption may be higher than that of WL-test based GNNs since RFGNN requires constructing Truncated ePath Forest (TPF). In future work, we will carefully study potential techniques, c.g., common paths consolidation, to overcome this issue.
4.2 The Expressive Power of REGNN
1-WL recognized as an indicator for the expressive power of GNNs [16, 17, 18]. In line with these work, measure the expressive power of our model using hashing procedure of TPFs. We first define the hashing procedure of TPFs (TPFH), Then, we prove that TPFH has the most expressive power if there is height constraint the height of TPFs and that the height & TPFH is strictly more expressive than the 1-WL test of rounds.
TPF Hashing (TPFH). The height i TPFH is a hashing scheme for height k TPFs, which is generalization of 1-WL [1]. In short, the hashing scheme is to assign labels to nodes. Let ( be the label assigned to ( And let tu be the label assigned to the tree rooted at (0) We initialize the tree labels of nodes at level & by their labels in the original graph. The hashing procedure is conducted recursively from the level (k 1) to the root. Specifically, we collect the tree labels of the child nodes of u, denoted as {[t(+)) Yu E (()( (note would be a null multiset if node has child nodes). Then, compute the tree label of by injective mapping as (() HASH((()) (1((+)) Ve E C( (w)))), where HASH is perfect hash function. Finally, collect labels of all TPTs of a TPF multiset and injectively map it into label by perfect hash function. Two graphs are considered non-isomorphic if the labels of their TPFs are not equal. Otherwise, the test is inconclusive.
7

---

Lemma 3. Non-isomorphic graphs will generate non-isomorphic TPFs if the height of TPFs is not
constrained.
If there were no height limitations on TPFs, the epath search would end when the TPF height reached the length of the longest epath. Then, the TPF of a graph would be composed of all of its epaths. Hashing TPFs with an unbounded height can therefore assign different labels to non-isomorphic graphs. In other words, TPFH without height limitation offers the greatest expressive capability for distinguishing non non-isomorphic graphs.
Lemma 6. For two graphs G1 and Gg. and two nodes u E V(G and v E v(G2), the height WL subtree of u is non non-isomorphie to that of v, the height k TPTs of them are non non-isomorphic too.
Lemma 7. There exist two graphs G1 and G2 and two nodes, E ((G1 and v E (G2),, where the height k WL subtree of u is isomorphic to that of 2, but the height k. TPTs of them are non-isomorphic.
According to Lemma and Lemma 7, the expressive power of the height k TPFH is better than that of the 1-WL with k iterations. Similar to the proof in WL-test based GNNs [16], REGNN can be shown provide the same expressive power of TPFH when each layer of REGNN are equipped with a sufficient number of layers and the parametric local aggregators they use can learn to be injective.
4.3 Advantages of REGNN
We attempt to investigate what REGNN has learned by measuring how the output of a height k REGNN, as in Equation 7 is influenced by input values and hidden representations.
Lemma 8. Assume there is a height l RFGNN as in Equation 7, a graph G, and an epath ep in G of
(s) length! 1 S k. We can measure the influence of the node feature x xepis] on the tree representation (0) ep(0)- where 0 s sisk L, as
(0) Oh 0x
eplo|
I (apitOngto))
(ok (661 + O2 dx
Oxeply 160))
Similarly, we can measure the influence of the tree representation hopd on the tree representation where 0 s sisl. 1,
h (0)
ep[0]
Ōh (0) ep
II (020) (0o0)000001i)
) S3
co di rpl
Oh (1)
epli
Avoid over-quashing Lemma 8 points out that if all edges in the computational graph of a RFGNN is activated with the same probability, on average, epaths starting with the same node and having the same length would have the same influence their shared starting node. This is similar to the finding of [19, 5]. Thus, the problem of ver-squashing induced by message flow redundancy in the computational graph is avoided.
Capture subgraphs at multiple levels granularity. An ideal method of graph similarity mea- surement should be able to capture subgraphs at different levels of granularity [11]. GIN [16] achieve this by an architecture similar to Jumping Knowledge Networks [20], which concatenates node representations across all layers. In contrast, RFGNN can directly detect the presence of subtrees of arbitrary heights of TPTs by deactivating information about trees (rooted nodes in TPTs) that do not belong to subtrees.
Graph similarity comparison and graph overlap detection. Intuitively, GNNs should be able to encode graphs with near graph edit distance (GED) [21] into similar representations. However, a similar graph pair's message flow sets created by WL-test based GNNs may vary significantly. This is because the difference in the message flow sets is dependent not only on the difference between the two graphs but also on their own topologies. In contrast, RFGNN will always yield message flow sets for graphs with near GED because of RFGNN's redundancy free message passing, even if there are rings in the graphs, as stated by Lemma 9, Therefore, RFGNN is likely more capable than WL-test based GNNs at comparing graph similarity. A detailed discussion can be found in Appendix B 6.
8

---

Lemma 9. Assume there is graph G = (V, E), node V, and an edge E E within the k-hop neighborhood of u. be the number of rings the k-hop neighborhood of u. We have that the number of repeations of within the height k TPT of u is no more than 1 nb.
Related Work
Higher order GNNs. Recently, higher expressive GNNs have been developed, which based on enhanced WL algorithms. such as PPGN (based on k-FWL) [17], 1-2-3-GNN (based on k- L-WL) [22], CWNs (based on Cellular WL) [23], and Nested GNNs (based on Nested 1-WL) [24]. Nonetheless, none of them breaks the iterative aggregation-update scheme.
Over-squashing issue. The Jacobian GNN-output is limited by term given as the power of the graph normalised adjacency matrix [5]. And, [6, 5] both argued that small absolute values of the Jacobian are indicative poor information propagation or over-squashing Furthermore, [5] investigated graphs from Ricci curvature perspective and demonstrated how negative curved edges contribute to the problem of over-squashing.
Graph kernels. Graph kernels are frequently employed measure the similarities between graphs by dccomposing graphs into substructures and comparing these substructures [25]] The measurement
of graph similarity could utilized for subsequent tasks such as classifications [25]. In comparison to earlier graph kernels, Tree++ [7], which allows comparing graphs at multiple levels of granularity, has the highest classification accuracy on numerous benchmark datasets.
Experiments
We examine the performance of REGNN and compare it with that of baseline approaches. REGNN implemented based the Deep Graph Library (DGL) [26]. And the code is available at Neurbhalewall-twwork
https://g/ thgtbbb...ttt..../m thub. com/ SategiiinChee/Rdduuddaaaa Ferettunnnnnnnnn---eeeeeeeeeeeee
First, we evaluate RFGNN by conducting series of supervised graph classification tasks on 5 bioinformatics datasets (NCI1 [27], PTC [28], MUTAG [29], PROTEINS [30], ENZYMES [30]) and 3 small molecules datasets (BZR [31], COX2 [31], DHFR [31]). We adopted two different sorts of baselines: graph kernels (such as WL-subtree [3] and Tree++ (7J) and GNNs (such as GIN [16],
PPGN [18], 1-2-3-GNN [22], and CWN [23]). We applied REGNN with height of 3. Φ and vi functions Equation are an identify mapping (because because all these datasets have no edge attributes) and 2-layer MLP, respectively. The experiment configurations follows that of GIN [16]. such as the number of hidden units (32), batch size (128), 10-fold cross validation, the number of epochs (350), and learning rate (initialized as 0.01 decayed by 0.5 every 50 epochs). Configurations of baselines are follow their original papers. Due to the lack of executable codes, some Tree++ results missing. In addition, 1-2-3-GNT 3-GNN result is missing because of out-of-memory error.
The data set statistics and the test set classification accuracy REGNN and baselines are shown in Ta- ble 1. We see that RFGNN outperforms GIN and even high order GNNs on most datasets, supporting our argument that REGNN is theoretically sound method for improving GNN performance.
Table 1: Statistics of the datasets and performance comparison.
Datascts
MUTAG
PROTEINS
PTC
NCII
ENZYMES
BZR
COX2
DHFR
#graphs
188
1113
344
4110
600
405
467
756
#classes
2
2
2
2
2
Avg. #nodes
17.93
39.06
25.56
29.87
32.63
35.75
41.22
42,43
Avg. Wedges
19.79
72.82
25.96
32,30
62, 14
38.36
43.44
44.54
TPF Avg. nodes
232.84
2165.3
336.56
376.48
1908.11
503.12
564.87
563.00
TPF Avg. edges
216.77
2160.0
311.41
349.05
1904.98
469,98
525.87
$22.69
WL-subiree
3.7
76.0
59.9
06.0111
62.6 1 1.2
87.3
81.2
82.4
Tree++
85.8 - 0.1
87.9 1.0
84.3
0.9
83.7
+.6
GIN [16]
8..0
76.2 1: 2.8
6.6
82.7 62.7111 1.7
72.5 - 6.1
89.9 3.8
87.6
1: 4.0
82.9
3.9
1-2-3-GNN [22]
9.42
17.3442
61.0 6.5
3.3
78.7
1.3
63.4
PPGN [17]
90.6
77.2 -
66.2 6.5
83.2
63.3 + 11.8
$9.1
86.7 4.1
79.6
CWN [23]
9.17+
77.0
63.6 5.6
62.6
8.1
78.8 1.0
78.4
68.
REGNN
93.3
3.4
71.5332
83.6
90.9 7.0
87.4 4.6
4.6

---

To further evaluate the ability to model long-range interactions and the capacity to quantify graph similarity of RFGNN, we computed and compared the performance of RFGNNs with heights ranging from 6 to 8 and baseline approaches QM9 [32, 331, graph dataset with 12 regression tasks. QM9 [32. 33] contains 130K small molecules. The task here is to separately perform regressions on 12 targets representing energetic, electronic, geometric, and thermodynamic properties, based on the graph structure and node/edge features. All evaluation metrics are mean absolute error (MAE). We use sum aggregator to obtain graph representations. (0 and wi()) in Equation 7 both are 2-layer MLPs. All other settings follow [24].
We report the average test MAE across 10 folds and show the QM9 results in Table 2. The results of baseline methods are extracted from [24]. We highlight the results of RFGNNs if they are better than those of baselines. Several positive conclusions can be drawn from the experimental results: (I) RFGNNs achieved the best results on 7 out of 12 prediction targets, which means RFGNNS have better performance on measuring graph similarity. (2) The performance of REGNN increases with increasing height on several targets, which underlines the need for modeling long-range interactions in these targets. (3) Ne. 1-GNN has the potential to model longer-range interactions better than RFGNN-8 due to its deeper layers; however, Ne.I-GNN does not perform better than RFGNN-8. We believe that redundancy-free message passing allows RFGNN to model long-range interactions more competently than Ne. I-NNN,,N, as Ne.1-GNN's message passing is redundant.
Table 2: MAE results on QM9
(smaller the better)
Target
a Fμомо FLUMU
As
(R2)
ZPVE
Ug
U
H
G
C.
DTNN [34]
0.244 0.95
0.00388 0.00512 0.0112
17.0
0.00172
2.43
2.43
2.43
2.43
0.27
MPNN [2]
0.358 0.89 0.00541 0.00623
0.0066
28.5
0.00216
2.05
2.00
2.02
2.02
0.42
Deep LRP [35]
0.364 0.298 0.00254 0.00277 0,00353
19.3
0.00055
0.413
0.413
0.413
0.413
0.129
1-GNN [22]
0.493 0.78 0.00321 0.00355
0.0049
34.1
0.00124
2.32
2.08
2.23
1.94
0.27
2 GNN [22]
0.493 0.27 0 0.03331 0.00350
0.0047
21.5
0.00018
0.0357
0.107
0.070
0.140
0.0989
1-3-GNN [22]
0.473 0.46 0.00328 0.00354 0.0046
25.8
0.00064
0.6855
0.686
0.794
0.587
0.158
1-2-3-GNN [22]
0.476 0.27 0.00337 0.00351
0.0048
22.9
0.00019
0.0427
0.111
0.0419
0.0469
0.0944
Ne.1-GNN [24]
0.428 0.29 0.00265 0.00299
0.0038
20.5
0.00020
0,295
0.361
0.305
0.489
0.174
Ne. 1-2-GNN [24]
0.437 0.278 0.00275 0.00271
0.0039
20.4
0.00017
0.252
0.265
0.241
0.272
0.0891
Ne.1-3-GNN [24]
0.436 0.261 0.00265 0.00269
0.0039
20.2
0.00017
0.291
0.278
0.267
0.287
0.0879
Ne. 1-2-3-GNN [24]
0.433 0.265 O 00279 0.00276
0 0039
20.1
0.00015
0.205
0.200
0.249
0.253
0.0811
RFGNN-6
0.323 0.216 0.00204 0.00206
0.00311
14.277
0.000156
0.0997
0.1257
0.1153
0.1103
0.07720
RFGNN-7
0.318 0.209 0.00200 0.00205
0.00310
14.316
0.000162
1082
0.1
0.1
0.1099
0.07420
RFGNN-8
0.322 0.208 0.00200 0.00205
0.00314
14.057
0,000159
0.0775
0.0741
0.0744
0,1015 0.07485
7 Conclusions
In this work, we carefully investigated the message flow redundancy issue in recent GNNs and its implications. In particular, we have proved that message flow redundancy one key factor in the over-squashing phenomenon. To address the message flow redundancy issue, we have proposed Redundancy-Free Graph Neural Networks (RFGNN), which conducts redundancy- passing. Theoretically, we demonstrate the benefits of our method, and experimentally, we show that our REGNN outperforms existing WL-test based GNNs on a large number of graph property prediction challenges.
message
8 Acknowledgement
The authors appreciate the constructive comments and valuable suggestions from the review- ers. This work was supported by the National Key Research and Development Plan of China NN..001YFB22021000 the Strategic Priority Research Program of Chinese Academy of Sci- ences (Grant No. XDB38040200), the National Key Research and Development Plan of China 104), the Science and Technology Development Fund Macau (SKL-IOTSC-202)- 2023, 0015/201//KKP, /031/2022/A), University of Macau (MYRG2019-00119--S)) MYRG2022- 00252-FST), Wuyi University Hong Kong and Macau joint Research Fund (202IWGALHI4,
10

---

References
[1] Boris J Weisfeiler and Andrei A Lehman. A reduction of a graph to a canonical form and an algebra arising during this reduction. nauchno-techmicheskaya informatsiya, 2 (9): 12-16, 1968.
[2] Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. ArXiv, abs/1704.01212, 2017.
[3] Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mchlhorn, and Karsten M. Borgwardt. Weisfeiler-Lehaan Graph Kernels. Journal of Machine Learning Research, 12(77))259--251, 2011.
[4] Zhihao Jia, Sina Lin, Rex Ying, Jiaxuan You, Jure Leskovec, and Alexander Aiken. Redundancy- free computation for graph neural networks. Proceedings of the 26th ACM SIGKDD Interna- tional Conference on Knowledge Discovery & Data Mining, 2020.
[5] 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 on Learning Representations, 2022.
[6] Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In 9th International Conference on Learning Representations, ICLR 2021, 2021.
[7] Wei Ye, Zhen Wang, Rachel Redberg, and Ambuj K. Singh. Tree++: Truncated based graph kernels. IEEE Transactions on Knowledge and Data Engineering, 33:1778-1789, 2021.
[8] Yu Su, Fangqiu Han, Richard Harang, and Xifeng Yan. A fast kernel for attributed graphs In Proceedings of the 2016 SIAM international conference on data mining, pages 486-494, SIAM, 2016.
[9] Giannis Nikolentzos, Polykarpos Meladianos, and Michalis Vazirgiannis. Matching node embeddings for graph similarity. In Thirty-first AAAI conference on artificial intelligence, 2017.
[10] Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mchlhorn, and Karsten M Borgwardt. Weeisfiierrlehmma graph kernels. Journal of Machine Learning Research, 12(9). 2011.
[11] Anton Tsitsulin, Davide Mottin, Panagiotis Karras, Alexander M. Bronstein, and Emmanuel Müller. Netlsd: Hearing the shape of a graph. Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & DDta Mining, 2018
[12] Wikipedia contributors.
Breadth-first search Wikipedia, the free encyclo- pedia. https: //en. wikipedia. hwtpppda...gg//iiiie.eeee wtg/w/index..oo///////oo/oo Beatiitiee #1aid=1011190311, 2022.
[13] Michael Collins. Computational graphs, and backpropagation. Lecture Notes, Columbia University, pages 11-23, 2018.
[14] Hossein Pishro-Nik. Introduction to probability, statistics, and random processes. Amazon, 2016.
[15] Wikipedia contributors. Component (graph theory) Wikipedia, the free encyclopedia, 2022. [Online; accessed 9-October-2022).
[16] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019.
[17] Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. ArXiv, abs/18 0tss/8812.0902.. 2019.
[18] Haggai Maron, Heli Ben-Hamil Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 2153-2164, 2019.
11

---

[19] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In ICML, pages 5449-5458, 2018
[20] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe. Ken ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In ICML, 2018
[21] Xinbo Gao, Bing Xiao, Dacheng Tao, and Xuelong Li. A survey of graph edit distance. Pattern Analysis and applications, 13(1):113-129, 2010.
[22] Christopher Morris. Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. ArXiv, 0tbs//810.02244/ 2019.
[23] Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yu Guang Wang, Pietro Lio', Guido Montúfar, and Michael M. Bronstein. Weisfeiler and lehman go cellular: Cw networks. In NewrIPS, 2021.
[24] Muhan Zhang and Pan Li. Nested graph neural networks. Advances in Neural Information Processing Systems, 34, 2021.
[25] Nils M. Kriege, Fredrik D. Johansson, and Christopher Morris. A survey on graph kernels. Applied Network Science, 5:1-42, 2020.
[26] Minjic Wang. Da Zheng, Zihao Ye, Quan Gan, Mufci Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yujie Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, and Zheng Zhang. package for graph neural networks.
Deep graph library: A graph-centric, arXiv: Learning, 2019.
[27] John Boaz Lee, Ryan Rossi, and Xiangnan Kong. Graph classification using structural attention. In Proceedings of the 24th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pages 1666 1674, 2018.
[28) Hannu Toivonen, Ashwin Srinivasan, Ross D King, Stefan Kramer, and Christoph Helma. Statis- tical evaluation of the predictive toxicology challenge 2000-2001. Bioinformatics, 19(10):1183- 1 1193, 2003.
[29] Asim Kumar Debnath, Rosa L Lopez de Compadre, Gargi Debnath, Alan J Shusterman, and Corwin Hansch. cructure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, 34(2):76--797, 1991.
[30] Karsten M Borgwardt, Cheng Soon Ong, Stefan Schönauer, SVN Vishwanathan, Alex Smola, and Hans-Peter Kriegel. Protein function prediction via graph kernels. Bioinformatics, ([(suppl_)::47-iiss 2005.
[31] Jeffrey J. Sutherland, Lee A. O'Brien, and Donald F. Weaver. Spline-fitting with a genetic algorithm: A method for developing classification structure-activity relationships. Journal of chemical information and computer sciences, 43 6:1906-15, 2003.
[32] Raghunathan Ramakrishnan, Pavlo O. Dral, Matthias Rupp, and O. Anatolc von Lilienfeld. Quantum chemistry structures and properties of 134 kilo molecules. Scientific Data, 1, 2014.
[33] Zhenqin Wu, Bharath Ramsundar, Evan N. Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh Pappu, Karl Leswing, and Vijay S. Pande. Moleculenet: A benchmark for molecular machine learning. arXiv: Learming, 2017.
[34] Kristof T. Schütt, Farhad Arbabzadah, Stefan Chmicla, Tlaus-Robert Müller, and Alexandre Tkatchenko. Quantum-chemical insights from deep tensor neural networks. Nature Communi- cations, 8, 2017.
[35] Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? ArXiv, abs/2002.04005,. 2020.
12


Reviews:
[{"review_id": "s0jy-3nd6mH", "reviewer": "Reviewer_Da5u", "summary": "This work aims to eliminate the message flow redundancy in traditional message passing schemes so as to reduce the over-squashing issue. The authors first explain the redundancy in the computational graph of message passing and then theoretically quantify that the redundancy would cause the over-squashing issue. Based on these findings, the authors propose a message-passing GNN that is message flow redundancy-free and theoretically has better expressive power than 1-WL.\n\nTo empirically evaluate the performance of the proposed GNN (RFGNN), semisupervised graph classification tasks are done to compare RFGNN to several baselines. The results show that RFGNN in general exhibits better performance than the baselines.", "questions": "I saw the height of the Truncated ePaths Forest (TPF) in RFGNN is 3 in experiments, how would the height affect the performance? Besides,  I'm not sure why the length of each epath should be larger than 2. Will the choice of 2 affect any analysis and the performance?", "limitations": "Since the proposed GNN is redundancy-free for the message flows, it would be interesting to investigate the computational complexity of the proposed model. If the model can reduce redundant computations and save memory/time, that can be also an advantage to be discussed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The investigation of the message flow redundancy in message passing together with the over-squashing problem is novel. There are existing works related to the redundancy in message passing. However, they usually focus on reducing the computational complexity caused by redundant operations.\n2. The authors conduct theoretical analysis when quantifying the effect of over-squashing and analyzing the expressive power of the proposed GNN. These analyses make the proposed method more solid.\n3. The paper is generally easy to follow and well-written. The concepts and the proposed models are clearly explained.\n\nWeaknesses:\n1. The experiments are relatively weak compared to the theoretical part. The experiments need to be better designed to better demonstrate the performance of the proposed method. For example, the performance difference between the proposed RFGNN and the other baselines can be smaller than the stds as shown in Table 1, it would be necessary to confirm the statistical significance when comparing them. Besides, the results of GIN. k-order GNN, and CIN are not computed for Enzymes, BZR, Cox2 and DHFR in Table 1, thus the comparison is not comprehensive enough. \n2. There are existing works investigating the redundant computations in GNNs (e.g. Redundancy-Free Computation for Graph Neural Networks, KDD 2020). The authors should address these works in the Related Works section.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "VJgU3PMJyjj", "reviewer": "Reviewer_7sMW", "summary": "One challenge of conventional GNNs is the propagation of information between long-distance node / long-length paths. This paper argues the redundant aggregation of the same node/edge information attenuates the effect of features coming from long distance paths (Message Over-squashing). \nAs a solution, Redundancy-Free Graph Neural Networks (RFGNN) are proposed. They are a variation of GNNs which is  redundancy-free.\nThis contribution also proposes a theoretical framework allowing to compare RFGNN with traditional WL-GNNs. In particular, it is shown that:\n- The expressive powers of RFGNN can surpass the conventional GNNs (TPF Hashing is more powerful than WL-1).\n- Over-squashing is reduced by de-redundancy.\nEventually, RFGNN is evaluated on graph classification tasks against several baselines (including GIN, k-GNN, and CIN) and on several bioinformatics datasets (NCI1, PTC, MUTAG, PROTEINS, ENZYMES) as well as 3 small molecules datasets (BZR, COX2, DHFR).", "questions": "- The TPF Hashing (TPFH) is compared to WL-1 test. Why not compare a TPFH with trees of height k with a WL-k test? Would they be the same?\n\n- Shouldn’t k-Tree RFGNN be as powerful as a k-order GNN when learning is done appropriately?\n\n- What is the blue color in the result Table? It is a bit misleading because RFGNN is the 3rd score and not the 2nd one.\n", "limitations": "Limitations are not discussed. No potential negative societal impact.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n - I believe this work is very novel. It introduces a new type of Graph Neural Network as well as theoretical framework to analyze them.\n - The contribution is well written and of high quality. Given the space constraint, the contribution is relatively clear.\n - It seems that RFGNN achieves superior performance in graph discrimination than traditional GNNs and even k-order GNNs.\n\n ## Weaknesses\n  - I believe that NeurIPS is not a good format for this contribution. 9 pages are just not enough to fit all the relevant information and the presentation of this paper suffers a bit from this. Therefore, if the paper is accepted, I would suggest to the authors to publish a longer version on arxiv that includes some of the appendices in the main text as well as spend a bit more time explaining the core idea of this contribution. This being said, I agree that such a contribution should be presented at NeurIPS.\n  - The experimental evaluation feels a bit weak. It misses some scores (a lot of \"-\"). A longer discussion of the results would be welcome. According to me, not all baselines are equivalent and the main one should be the k-order GNN.\n  - According to me, implementing the RFGNN is not trivial. Some explanation on how it is done would be welcome. Code is provided, though.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "DnLzv52_nzy", "reviewer": "Reviewer_6V6A", "summary": "This paper analyzes the redundancy problem in message passing in graph neural networks, and proposes a method to address this issue. Theoretical analysis and empirical verification are presented to justify the effectiveness of the proposed method.\nThe contributions can be summarized as follows:\n1) Formulate and analyze the redundancy problem in message flows and suggest its impact on hindering the performance of GNNs.\n2) Propose a redundancy-free GNN (RFGNN), and justify the superior expressive power of RFGNN in terms of addressing the over-squashing issue.\n3) Show another advantage of RFGNN, i.e., capable of measuring the similarity between graphs in different granularity and detecting overlapping subgraphs.\n4) Empirically verify the effectiveness of RFGNN through graph classification tasks on eight benchmark datasets by comparing with graph kernels and powerful GNNs.", "questions": "Questions:\n1. As the paper described in section 6 (page 9: line 314),  the experiment is semi-supervised graph classification. But the experiment follows the configuration of <How powerful are Graph Neural Networks>, which conducts experiments with supervised graph classification tasks. Can you explain this inconsistency? And give more details of the semi-supervised learning in this experiment?\n\n2. Why are most baseline results missing in Table 1?", "limitations": "1. No appendix with proofs.\n\n2. It is preferable to give instances during the theoretical analysis, so the readers can follow the idea easier.\n\n3. The results in Table 1 are incomplete.\n\n4. More experiments are needed to demonstrate the details of the learning of RFGNN.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. This paper studies an important problem, i.e., the redundancy within the message passing flow, which is highly related to the performance of graph-level tasks where higher-order neighbors are important.\n\n2. This paper is well organized, and the theoretical analysis is clearly presented. The redundancy problem is introduced and formulated strictly in the research context. \n\n3. This paper also analyzes the negative impact of message flow redundancies and connects it with the over-squashing phenomenon. The significance of this work is highlighted by showing its ability to address the over-squashing problem.\n\n4. The expressive power of RFGNN is studied by 1) theoretical analysis and comparison with 1-WL, 2) empirical verification through experiments by comparing with graph kernels and power GNNs such as GIN, k-GNN, and CIN.\n\n5. The proposed method shows other advantages in measuring graph similarity and detecting overlapping subgraphs.\n\n\nWeakness:\n1. It is said at the beginning of section 3 that “all proofs can be found in Appendix“, but there is no appendix attached.\n\n2. The lack of illustrations/visualization during the analysis in Section 3 makes it difficult to catch the idea. For instance, on page 4, lines 133-139, this part can be illustrated with an example.\n\n3. The results for baselines in Table 1 are reported from the original papers. However, the different configurations may result in different performance results of the baselines. In this paper, the experiment follows the configuration in the paper <How powerful are Graph Neural Networks>. The configurations between RFGNN and other baselines (e.g., Tree++) are not consistent.\n\n4. The experiments are kind of simple. Only one graph classification experiment is presented. There are only five baseline methods, and around half of the baseline results are not available. And there are no explanations for the missing results.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Ba73zsiovfH", "reviewer": "Reviewer_hcxm", "summary": "The authors aim to theoretically analyze the redundancy in GNNs and its practical implications, which is an interesting and important problem in the GNN community. To overcome the redundancy problem, the authors propose an expressive RFGNN based on the so-called Truncated ePath Tree. Experiments demonstrate that RFGNN outperforms existing models.", "questions": "1. Whether RFGNN is applicable to larger graphs such as ogbg-ppa and ogbg-code2?\n2. Since one of the motivations to alleviate over-squashing is to better model long-distance interactions, I suggest the authors to conduct experiments to evaluate the effect of the number of GNN layers. The current number of GNN layers is always 3, which may not reflect“long-distance interactions”.\n3. In Line 182, the authors claim that “the influence along a long path is always less than that of its sub-paths”. Is there any possibility that distant nodes should contribute less than closer nodes?", "limitations": "The authors have addressed the limitations of their work, but did not discuss the potential negative societal impact.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- Originality\n  - The authors are the first to theoretically analyze the redundancy GNNs and its practical implications. Thus, the submission is certainly an original work.\n  - The idea that using extended path to develop a redundancy-free message passing paradigm seems novel to me.\n- Quality\n  - This paper is well motivated. The authors did a good job in illustrating the redundancy problem in message passing and propose a reasonable solution to it.\n  - This paper is technically solid. The authors rigorously analyze why redundancy causes message over-squashing. Besides, the authors provide theoretical analysis for the proposed method and show their method outperforms 1-WL test.\n  - My major concern is the scalability of the proposed RFGNN. As shown in Table 1, in TPF, the average number of nodes/edges becomes at least ten times larger than that in the original graph. I am wondering if RFGNN is applicable to larger graphs such as ogbg-ppa and ogbg-code2.\n- Clarity\n  - The writing of this paper is overall clear. My only complaint is about Figure 1. It looks confusing to me and the authors may want to give a more clear illustration in either the main text or caption.\n- Significance\n  - Both the theoretical and empirical results are significant. ", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept