Pruning for GNNs: Lower Complexity with Comparable Expressiveness
Authors: Dun Ma
Jianguo Chen
Wenguo Yang
Suixiang Gao
Shengminjie Chen
Venue: ICML 2025 poster (2025)
Keywords: Graph Neural Network
Pruning
Expressiveness
Complexity
Primary area: deep_learning->graph_neural_networks
TL;DR: We prune redundant structures in MP, K-path and K-hop GNNs, achieving lower complexity while preserving expressive power.

Abstract: In recent years, the pursuit of higher expressive power in graph neural networks (GNNs) has often led to more complex aggregation mechanisms and deeper architectures. To address these issues, we have identified redundant structures in GNNs, and by pruning them, we propose Pruned MP-GNNs, K-Path GNNs, and K-Hop GNNs based on their original architectures. We show that 1) Although some structures are pruned in Pruned MP-GNNs and Pruned K-Path GNNs, their expressive power has not been compromised. 2) K-Hop MP-GNNs and their pruned architecture exhibit equivalent expressiveness on regular and strongly regular graphs. 3) The complexity of pruned K-Path GNNs and pruned K-Hop GNNs is lower than that of MP-GNNs, yet their expressive power is higher. Experimental results validate our refinements, demonstrating competitive performance across benchmark datasets with improved efficiency.

Pruning for GNNs: Lower Complexity with Comparable Expressiveness
Dun Ma
Jianguo Chen
Wenguo Yang?
Suixiang Gao
Shengminjie Chen
Abstract
Morris al., 2019). Specifically, GNNs cannot distinguish between non-isomorphic graph structures that the 1-WL test cannot differentiate. To address this, many works ex- tend message passing to K K-Hop Aabu-El-Haipe et al., 2019; Nikolentzos et al., 2020; Wang et al., 2021; Chien et al., 2021; Brossard et al., 2020) or K-Path (Zhang et al., 2023; Michel et al., 2023; Ma et al., 2020) message passing, which enhances the framework's expressive power. In K-Hop and K-Path GNNs, node representations are updated by aggre- gating information not only from neighbors but also from all nodes within K-hop and K K-path distances. Despite the great success of GNNs in handling graph data, they still have some deficiencies: Ex)pxsree power restricted by the number of layers. (2) Excessive depth hinders GNN's performance due nonlinearity. (3) Redundant structure of GNNs. (4) Growing complexity with the increase in ex- pressive power. Those deficiencies might impact their per- formance.
In recent years, the pursuit of higher expressive power in graph neural networks (GNNs) has of- ten led to more complex aggregation mechanisms and deeper architectures. To address these issues, we have identified redundant structures in GNNs, and by pruning them, we propose Pruned MP- GNNs, K-Path GNNs, and K-Hop GNNs based on their original architectures. We show that 1) AI- though some structures are pruned in Pruned MP- GNNs and Pruned K-Path GNNs, their expres- sive power has not been compromised. K-Hop MP-GNNs and their pruned architecture exhibit equivalent expressiveness on regular and strongly regular graphs. 3) The complexity of pruned K- Path GNNs and pruned K-Hop GNNs is lower than that of MP-GNNs, yet their expressive power is higher. Experimental results validate our refine- ments, demonstrating competitive performance across benchmark datasets with improved effi- ciency.
To address these deficiencies, we theoretically character- ize the expressive power of MP-GNN, K K-Hop, and K- Path message passing GNNs by utilizing matrix language tool (Brijder al., 2019; Geerts, 2021). Surprisingly, we discovered the redundant structures in all three types of GNN frameworks. We "cut off" the redundant structures in MP-GNN, K-Hop, and K-Path message passing GNNs, and therefore propose the pruned MP-GNN, pruned K- Hop, and pruned K K-Path frameworks. We prove the equiva- lence of expressive power between MP-GNN, K K-Hop, and K K-Path message- paassagg GNNs and the matrix language C (-, d,dig)) therefore are able demonstrate that the pruned frameworks are powerful as the origi- nal frameworks for MP-GNN and K-Path message passing GNNs, and show the equivalence between pruned K-Hop frameworks and K- K-Hop frameworks for distinguishing reg- ular and strongly regular graphs by utilizing the matrix language tool. Additionally, we show that the complexity of pruned K-Path GNNs and pruned K K-Hop GNNs is lower than the complexity of MP-GNNs, yet they can distinguish more non-isomorphic graphs that MP-GNN cannot.
1. Introduction
Currently, most GNNs (Kipf& & Welling, 2017; Duvenaud et al., 2015; Hamilton et al., 2017; Veličković et al., 2018: Li et al., 2015; Zhang et al., 2018; Xu et al., 2019a) fol- low a framework that iteratively aggregate information from neighboring nodes and updates node representations. Since the message passing procedure is similar the 1- (1-WL) test (Weisfeiler & Lehman, 1968), the expressive power of message-passig GNNs is also limited by the 1-WL test (Xu et al., 2019a;
dimensional Weisfeiler-
Schooo of Advanced Interdisciplinary Sciences, University of Chinese Academy of Sciences Acaddmyy of Mathematics and Systems Science, Chinese Academy of Seiences 'School of Mathematical Sciences, University of Chinese Academy of Sciences 'Zhongguancun Jaboratory.Beijing. China Sttte Key Lab of Processors, Institute of Computing Technology. Chi- nese Academy Sciences. Correspondence to: Wenguo Yang <yangwg @ ucas.ac.co. ac.c>>
The proposed pruned frameworks have several additional advantages. (1) Unlike MP-GNNs, the range of neighbor information aggregation in the pruned MP-GNNs grows exponentially with the number of layers. Therefore, the pruned MP-GNN does not require many layers to obtain
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

PRUNING For GNNS: HIGHER EXPRESSIVENESS LOWER COMPLEXITY
vast amount of neighbor information. (2) Pruned MP-GNNS do not need pile up many layers MP-GNNs, hence the nonlinearity which hinders GNN's performance of node rep- resentations is restricted. (3) In our pruned framework, the redundant structure of GNNs has been "cut off", therefore the framework is easier to train and optimize. (4) In large graphs, our pruned K- K-aath and K K-Hop GNNs, compared to MP-GNNs, can distinguish more non-isomorphic graphs that MP-GNNs cannot while maintaining the lower com- plexity. We conduct both synthetic and real experiments, which demonstrate the superior performance of our pro- posed pruned framework and validate our theoretical find- ings.
2.2. Matrix Language
Recently, Brijder (Brijder et al., 2019) and Geerts (Geerts, 2021) proposed new matrix language called MATLANG. Matrix languages can be formalised through composition of linear algebra operations. Intuitively, a linear algebra opera- tion takes a number of matrices as input and returns another matrix(or vector or scalar). We employ MATLANG as a theoretical tool for our proofs, with its detailed formulation provided in Appendix D.
2.3. Graph Neural Networks
The WL algorithm is a heuristic method for graph isomor- phism testing that iteratively refines vertex labels based on their neighbors' labels, which is specifically introduced in Appendix B. MP-GNNs match the expressive power of WL when their feature aggregation and combination functions are injective. Most GNNs use a message passing framework, where the features of a node's neighbors are first aggregated and then combined with the node's own features. In this subsection, denote Hi as the output representation of node layer
2. Preliminaries
In this section, we present some basic notations and concepts of the matrix language and the message passing framework.
2.1. Notations
Denote graph as G = E), where V {1, 2, ..... n) is
the node set and the edge set is denoted as E C V x V.
The adjacency matrix is denoted by A E {0. 1) The notation [m,, nı] represents the integers from m to n, and [r]] represents [1, n].
Message Passing Framework. In the standard message passing framework, the update rules are typically written as:
We define the k-length walk (u, ",. .us) as k-walk neighbor of v, its representation is the same as that of node u/s.. Similarly, we can define k-path neighbor of v. if (v. "i,..., ( is path. The set of k-walkk .aah neighbors is denoted as Nh (N) path peat (v). Note that the element A (i, () equals the number walk from U2 1j with length k. Hence, we denote A graph G's k-walk adjacency matrix. Denote PR E Nnxn as k-path neighbor matrix. The element (t.)..) represents the number of k-length paths from v; to ut.. Node u is called node v's k-hop neighbor: u E Nhop (v), if the length of shortest path from v to u equal to k. Denote On as the k-hop matrix, it's worth noticed that O2 (0, 1) mmx
M = AGG' (H
N(b)B)
(1)
H = COB M!)
(2)
where M represents the message received by node e at layer I, AGG' and COB' are the aggregation and combi- nation functions, respectively. After L layers of message passing. H is the final representation of node v. According to Theorem 3 in (Xu et al., 2019a), nodes receive the same feature representations if and only if they receive the same labels in the corresponding WL test.
K-Path Message Passing Framework. The K-Path GNN extends the standard message passing to consider paths of length (1 S < K). Specifically, each k-path neighbor set N parn (v) is aggregated independently and then combined. Specifically,
A is a graph isomorphism algorithm. (G,G") is pair of graphs and T. E N+, we denote (G, G') E GT4, if algo- rithm A decides (G, G²) is isomorphic at th iteration. In this paper, we assume that the aggregation and combination functions of all the mentioned GNNs are injective, making their expressive power equivalent to the corresponding WL Test. In this paper, we only consider necessary graph iso- morphism algorithms, which means that the isomorphism to algorithm is only a necessary but not sufficient condition for graph isomorphism. Therefore, given two graph isomor- phism algorithm, A and B, if GT C GTg. then algorithm A is regarded to be more powerful than B.
Mr* = AGG (AH | u E N (H)),
(3)
M (MD) M12 ,..... M.
(4)
H = COB' (H!
(5)
A node can appear multiple times k-path neighbor of v, allowing the algorithm to capture repeated walks of length k. We use (G, G') E GI to denote that the K-Path WL test decides G and G' are isomorphic after J. iterations.
K K-Hop Message Passing Framework. The K K-Hop GNN differs by focusing on shortest-pan -ath neighbors. Each node
2

---

PRUNING For GNNS: HIGHER EXPRESSIVENESS LOWER COMPLEXITY
belongs to N hop (v) if the shortest path from to u has length k. Importantly, a node can be k-hop neighbor of at most once. The update process is similar to the K-Path Message Passing framework, but the aggregation process equation 3 is replaced by the following steps:
3.1. Pruned (ag-walk) Message Passing Framework
Input graph
WL
Pruned WL
M AGG (H u queEE (V)B)
(6)
Likewise, we denote by (G, G*) GTk-H the event that the KoH WL test deems G and G' isomorphic after L iterations.
Figure 1. Comparison of MP-GNN and pruned MP-GNN: Blue and Green represents structure information node v has aggregated at 1st and 2nd iterations respectively. The overlap in the MP-GNN indicates computational redundancy.
By introducing K-path or K-hop neighbors, these frame- works can potentially enhance the expressive power of GNNs relative to the standard 1 H-Hop message passing, albeit with higher computational cost.
Given a sequence of positive integers dg, we propose a new framework called the ag-walk message passing framework like as Fig. 1. The key difference from the standard MP framework is that, at the 1th layer, node aggregates fea- tures from its ag ag-walk neighbors, rather than just its direct neighbors. Specifically, H is computed as follows:
2.4. Deficiencies of Graph Neural Networks
Despite the great success of GNNs in handling graph data, they still have some deficiencies that might impact their performance as follows.
Expressive power restricted by the number of layers: An MP-GNN with L layers can aggregate information from at most L-walk neighbors. Therefore, the expressive power of GNNs is particularly limited by the number of layers, especially on large graphs.
M = AAGG ( 'Iu E N
Wark (b)
(7)
F = COB* C (H M+)
(8)
Excessive depth hinders GNN's performance. Suzuki (2020) points out piling up many layers does not improve GNN's performance (or sometimes worsens it). The core reason is that each layer's iteration increases the nonlinearity of node representations, causing the differences between node representations to diminish over layers.
We point out the aggregation of k-walk neighbors' features can be computed as
( M = AGG (HH,lu Noate( (v)
AGG(... BEG(...AGG(UUAA AGG( N(v)
(9)
4g times
The redundant structure of GNNs will lead reduced computational efficiency, an increased search space during optimization, and, in some cases, decline in the model's generalization ability. In the section 4, we will demonstrate the redundant structure in GNNs.
Redundant structure of GNN:
Hence the computation complexity of AGG HH E N (v) B)) will not exceed ag times of the computational complexity of AGG ( H. /u E N ((v))) We provide a long- refinement graph example for comparison in Appendix C.4.
We refer to the a ag-walk message passing framework when OK 2 the pruned message passing framework. Additionally, we denote (G, G") E GI if the pair of graphs (G, G') gets the same representation in pruned MP- GNN frameworks. We also provide Pruned Message Passing Framework's 's corresponding WL Test in C.1.
Growing Complexity with the increase in expressive power: Since Xuel al. (20196) pointed out that MP-GNNs might suffer from insufficient expressive power, many GNN variants with higher expresive power have been proposed. However, as their expressive power increases, both time and space complexity usually also grows.
3.2. Pruned K KPPath Message Passing Framework
In Figure 2, the K-path message passing framework exhibits redundant computations as certain structural information is repeatedly encoded into nodes' features across iterations. To address this, we propose the pruned K K-path message pass- ing framework. Unlike the standard K K-path framework, the pruned version aggregates features from the (-path neigh- bors N Noath to the K K-path neighbors Npoth at the t layer (1 S K), rather than from the 1-path neighbors N path to the
3. Pruned Message Passing Framework
In order to address the shortcomings of GNNs mentioned in previous section, we propose pruned frameworks for MP- GNN and its variants, including K K-path and K-hop message passing frameworks. These pruned frameworks have stream- lined structures, resulting in lower computational complex- ity compared to the original frameworks.
3

---

PRUNING For GNNS: HIGHER EXPRESSIVENESS, LOWER COMPLEXITY
has been repetitively encoded into nodes' features which will cause redundant computations. Therefore, we propose the pruned K -hoop message passing framework. Different from K -hhop message passing framework, when 1 S K, the K-hop pruned message passing framework is similar to the K K-path pruned message passing framework, but the aggre- gation process equation 10 is replaced by the following:
Input graph
2-Path WL
Pruned 2-Path
Mr = AGG ( //u E (hop(1))))
(14)
else when > K, the K-hop pruned message passing frame- work can be defined as follows:
Figure 2. Comparison of 2-path and pruned 2-path frameworks, where colors denote aggregated structure information for node v: Blue (1*h iteration, 1-path neighbors), Green (1* iteration, 2-path neighhors), Red (2nd iteration, 1-path neighbors), and Yellow (2nd iteration. 2- path neighbors). The range of Red covered by Blue, Green, and Yellow.
MaK AGG (U hhop (b)
(15)
H = COB' (H. (H. .M.K).
Denote (G, G') E GI K- if the pruned K-Hop frame- work's ' corresponding WL test decides and G' are iso- morphic after iterations. We also provide k-path GNN's corresponding WL Test in Appendia C.3.
K K-path neighbors N path Let H.g denote the feature of node v at the 1 layer. When / S K, the pruned K K-path message passing framework is defined as follows:
M =
u E Naan (v)B)( SIS
4. Pruned Framework's Equivalent Expressiveness Solving GNNs' Deficiencies
(10)
M = (M! _Mi+1..... M.. M
(11)
In this section, we theoretically analyze the expressive power of the message passing framework, K K-Path and K- Hop frameworks and their pruned frameworks. We also demonstrate how our pruned frameworks
H COB' (H,-
(12)
else when 1 > K. the K- K-path pruned Message passing framework can be defined as follows:
# = AGG (H( 'lu E N (U)))
We assume there are no edge features and all nodes in the graph have the same feature, which means that GNNs can only distinguish two nodes based on local structure of nodes. Let aggregation and combination functions be injective. We will show that the pruned message passing framework is as powerful as 1-WL test and pruned K K-Path is as powerful as K-Path framework. As for pruned K -Hop framework, it is as powerful as K-Hop framework when distinguishing regular or strong regular graphs.
(13)
H COB' (H (H.K)
Denote GG) E GIPRK-P- if the pruned K-Path frame- work's corresponding WI. test decides G and G' are isomor-
phic after L iterations.
3.3. Pruned K- K-Hop Message Passing Framework
H-Hop WL
Pruned 2-Hop WL
4.1. Expressive power of Pruned Message Passing Framework
In this subsection, we delve into a theoretical analysis of the expressive power of a, walk (pruned) message passing framework. Xu et al. (2019a) have proven that the expressive power of 1-hop message passing is bounded by the 1-WL test.
Given a positive integers sequence dg. S = >(E(N) 4g We say that sequence Og is viewable if Ak: N r [Sp]. there exists subset T S [k]. such that Σier at r. We will prove that if a is viewable, then 4g- 4g-walk message passing framework is at least as powerful as 1-WL test. The theorem is as follows:
Figure 3. Comparison of 2-hop and pruned h-hop frameworks. Col- ors indicate aggregated structure information for node v: Blue (1st iteration, 1-hop neighbors). Green (1sr iteration, 2-hop neighbors), Red (2nd iteration. 1-hop neighbors), and Yellow (2nd iteration, 2-hop neighbors). The range of Red is covered by Blue, Green, and Yellow.
In figure 3, at the iteration of K K-hop message passing frame- work, there's ' also specific node structure information which
Theorem 4.1. Given a positive integer sequence Os and a pair of graphs (G, G'), Se = Eeej at if og is viewable,
4

---

PRUNING For GNNS: HIGHER EXPRESSIVENESS, LOWER COMPLEXITY
then VI N+ GI Glay-watk C GI
We indicate the core of the proof of Theorem 4.4 is trans- forming the expressiveness problem of K-Path GNN into algebraic problem through MATLANG, Specifically, we identify a matrix language that is expressively equivalent to the K-Path framework and proved that the pruned K- Path framework has the same expressiveness as this matrix language.
The following lemma and theorem are meant to explain why we chose 2--1-walk as the pruned framework:
Lemma 4.2. Given a positive integer sequence age, Sk=- E(E(H) 0t, if Sy > 2 -1, 1, then ag is not viewable.
Theorem 4.3. Given a positive integer sequence og if ag is not viewable, then there's 'ss a pair of non-isomorphic graphs (G, (G) that GG) GI -wak WL but (G, G') & GT WE
As for the pruned K K-Hop framework, unfortunately, we have to point out the difficulty in proving the equivalent expressive power between the pruned K-Hop framework and K K-Hop framework. We emphasize the main reason can be traced back to the proof of Theorem E.10 in the Appendix: during the process of generating K-hop matrices from K K-path matrices, the matrix language has removed two critical structural pieces of information (1): the number of shortest paths between two nodes. (2)the number of paths which are longer than shortest paths between two nodes.
The proof of Lemma 4.2, Theorem 4.1 and Theorem 4.3 is provided in Appendia E. Lemmaa 4.2 indicates that when a2 = 2*-1, the pruned MP-GNN framework can collect information from the most distant nodes while main- taining an expressive power comparable to that of MP GNNs. Theorem 4.3 provides an example to demonstrate that if ag is not viewable, then the expressive power of wa-walk framework will be diminished.
On the other hand, the K K-Hop GNN was proposed largely to compensate for the inability of MP-GNN to distinguish regular graphs. Let RG denote the set of pairs of regular graphs, and SRG denote the set of pairs of strong regular graphs. We show that pruned K-Hop GNN has comparable expressiveness as K Hop GNN in distinguishing strong regular graphs, as well as for for regular graphs when K = 2. In other words:
Despite the expressive power of -wakk message passing framework is bounded by I-WL test, we are able to "cut off" the number of GNN's layers and parameters to reduce computational complexity.
We now show why wwlk- message passing framework is more effective than message passing framework. As the proof of I em 4.1 shows, for an unlabeled graph, the determining factor of label that node v gets in 1-WL test the cardinality of v's I-walk neighbor IN La (v)). As Figure suggests, there's 's an overlapping part between the blue rectangle and green rectangles, which implies cardinal- ity information has been repetitively encoded into node However, the pruned WI. test, as the figure shows, makes sure that every (-walk neighbor's cardinality information will be encoded into node e without repetition. This makes the pruned framework more effective than message passing framework.
Theorem 4.5. VL, K E N (RGnGIpR2-Hl S (RGn Gl n) and (SRG n G kn) S n G
4.3. Pruned Frameworks Address Deficiencies of GNNs
In this subsection, we demonstrate how pruned frameworks address deficiencies of GNNs. Regarding the limited ex- pressive power restricted by the number of layers, unlike MP-GNNs the range of neighbor information aggregation in the pruned MP-GNNs grows exponentially with the number of layers. Therefore, the pruned MP-GNN does not require many layers to obtain a vast amount of neighbor informa- tion. Meanwhile, the pruned MP-GNNs do not need to pile up many layers as MP-GNNs, thus the nonlinearity of node representations is restricted.
4.2. Expressive Power of Pruned K-Path and K-Hop Message Passing Framework
In this subsection, we conduct a detailed analysis of the expressive power of K KPPtth and K K-Hop GNNs and their pruned frameworks. We will show that, although the pruned K-Path GNNs message passing framework does not aggre- gate as much graph structure information as K-Path frame- work, this does not diminish the expressive power of pruned K-Path framework. The theorem is as follows:
We now show the redundant structure of MP-GNNs along with a comparison to pruned MP-GNNs through a example. Given a connected graph with least 3 nodes, while some nodes are specially marked, we consider a simple node-level task for GNNs. We want node e's 1 1-dimensional representa- tion H₂, outputs 1 if and only if is marked or there's 's node u marked while the distance between and u is less than or equal to 3, and outputs 0 otherwise. We consider a 3-layer MP-GNN M, the initial representation H = 1 if and only if is marked and H = O otherwise, its representation
Theorem 4.4. Given a pair of graphs (") and K E N+, the expressiveness of pruned K -Pahhh framework is as powerful as K-Path framework. In other words, VL e N+ GIlnK-P- =Gk-p
The proof of Theorem 4.4 is provided in the Appendix.
5

---

PRUNING For GNNS: HIGHER EXPRESSIVENESS LOWER COMPLEXITY
Table 1. Simulation dataset result. The best is highlighted.
Node Properties
Graph Properties
Counting Substructures (MAE)
Method
SSSP
Ecc.
Lap.
Connect.
Diameter
Radius
Tri.
Tailed Tri.
Star
4-Cycle
GIN
-2.1476
-1.0388
-1.6000
-1.9239
-3.3079
-4.7584
0.3306
0.1534
-0.8716
0.1176
PR GIN
-1.9202
-1.6817
-1.7772
-1.7342
-3.2023
-4.9635
0.2893
0.3737
-0.9309
0.1260
K-Path
-2.7063
-2,4900
-4,9596
-4.3159
-3,8475
-5.2038
-1.3566
-1,2709
-0,9342
-0,4936
PR K-Path
-2.7833
-2,5977
-52884
-4.4239
-3,9324
-5.2983
-1.4588
-1.3839
-1.0391
-0.6070
K-Hop
-2.8152
-2.5963
-4.6254
-2.1877
-3,9683
-5.2923
0.1919
0.0637
-1.0043
0.0960
PR K-Hop
-2.7785
-2.6672
-4.9970
-2.1472
-3.7005
-5.0619
0.0499
0.0091
-1.3141
0.0665
Table TU dataset (Yanardag & Vishwanathan, 2015) evaluation result. The top three are highlighted with bold text and marked in red. blue, and black, respectively.
Method
MUTAG
D&D
PTC-MR
PROTEINS
IMDB-B
WL
90.4115.7
79.4
59.9
75.0
73.813.9
GraphSAGE
91.716.55
78.1
66.514.0
76.514.6
76.412.7
GraphSNN
91.2+
82.4+2.7
66.94
76.5+2.5
76.9
GIN
88.41:522
76.3 +1.2
63.6 +:500
74.9 41.9
74.1
PR GIN
89.7+3.0
77.2 #0.3
64.7 #1.3
75.8 =2.0
75.2+3.4
K-Hop
92.1+2.0
81.9+3.4
64.2+2..
75.0+1.2
74.5+ 1.0
PR K-Hop
91.8+44.3
84.1 +0099
65.5 +4.1
77.0++3.4
76.2+00.6
K-Path
91.711.7
82.113.4
65.915.1
78.6.11.8
76.813.2
PR K-Path
92.6 +3.3
83.3 #0.4
67.5 +3.5
79.1 +2.1
74.9+2.9
updated as follows:
As for the high expressive power accompanied with higher complexity, we refer our pruned framework: pruned K- K-Path and K-Hop GNN. When layer 1 > K, the complexity of pruned K-Path and K-Hop GNN is the same as MP-GNN, but the breadth of neighbor information obtained in each iteration of pruned K --Path and K-Hop GNN is equivalent to that of MP-GNN after K iterations. Hence in a large graph, K K-Path and K K-Hop GNN can reduce complexity by decreasing the number of layers while still distinguishing graphs that MP-GNN cannot.
H oH!
Σ HW)",,)), uEN(2)
(16)
where (xx) = min(max(O, 2), 1) parameter matrix W E {(0), (i) E [2),1 [3)) There are parameter config- urations for M, one of them is setting
W = while the remaining three are to set one of these parameter con- figurations W 0 for 1 [3]. We prove that among all the parameter settings of M, only these four are capable of handling this task in the Appendix. In other words, we can randomly choose one of the parameters W equal to O, the structure of MP-GNN will represent the same outcome. We can observe the redundant structure of GNNs from the randomness in the selection of W!.
To demonstrate the efficiency of the pruned framework, provide the iteration process of the WL Test (MP-GNN), the pruned WL Test (PR MP-GNN), and the pruned 2-Hop WL Test (PR 2-Hop GNN) on the long-refinement graph in Appendiæ: C.4. We can see both pruned WI. Test and pruned 2-Hop WL Test terminate 4th iteration while WL Test at the 11 iteration.
However, for the pruned MP-GNN, consider 2-layer M as
- - .
Σ
H W.).
(17)
5. Time and Space Complexity
WE (v)
In this section, we discuss the time and space complexity of MP, K --path, K Khoop, and their pruned frameworks. We assume graph has n nodes, every framework designed gather nodes information
Except for setting all parameters equal to 1, there is only one parameter configuration for M', as setting W?2 = 0, which means that we have pruned this redundant structure, reducing the cardinality of the parameter space from 28 in MP-GNN to 2 in pruned MP-GNN.
distance of L, and we assume K). The time and space complexities are listed
(n >>>> L >
6

---

PRUNING For GNNS: HIGHER EXPRESSIVENESS, LOWER COMPLEXITY
Table QM9 results. The hest is highlighted.
Target
GraphSAGE
GIN
PR GIN
K-Hopp
PR K K-Hopp
K-Pathh
PR K-Patth
0.369
0,355
0.422
0.301
0.303
0.311
0.268
Q
0.308
0.258
0.277
0.384
0.282
0.274
0.291
HOMO
0.00382
0.00427
0.00335
0.00266
0.00276
0.00221
0.00197
LUMO
0.00492
0.00644
0.00264
0.00294
0.00275
0.00281
0.00279
Ae
0.01187
0.00419
0.00430
0.00379
0.00396
0.00357
0.00316
(R?)
16.38
20.97
20.69
16.13
20.44
17.66
15.70
ZPVE
0.001747
0.001262
0.001537
0.000220
0.000141
0.000174
0.000159
Uo
2.05
2.05
2.31
0.0690
0,0629
0.0571
0,0502
2.05
2.02
2.00
0.0650
0.0593
0.0637
0.0527
H 2.05
2.02
2.00
0.0589
0.0604
0.0533
0.0552
2.05
2.02
2.00
0.0663
0.0574
0.0543
0.0559
C
0.2716
0.2170
0.2262
0.0841
0.0847
0.0878
0.0847
Table Verification the equivalence of the expressive power.
Table 5. Time and Space Complexity
Method
Time
Space
EXP (ACC)
SR (ACC)
CSL (ACC)
Method
K
SPD
GD
SPD
GD
SPD
GD
MP
((n-
( L)
PR MP
O(n- log
On log L))
GIN
50
50
6.67
6.67
12
12
PR GIN
50
50
6.67
6.67
12
12
K-Hop
O L.)
O(n L)
PR K-Hop
O(n k)
O(n k)
K=2
50
50
73.33
73.33
52.7
52.7
K-Path
K=3
100
100
73.33
73.33
90
K-Path
O L)
O(n L)
K=4
100
100
73.33
73.33
100
100
PR K-Path
O k
O(n k
K=2
100
100
73.33
73.33
52.7
52.7
PR K-Path
3=3
100
100
73.33
73.33
90
90
K=4
100
100
73.33
73.33
100
100
2021), and (3) CSL, comparing them with their original
K=2
50
50
6.67
6.67
32
22.7
frameworks (Murphy et al., 2019). We use node properties (such as single-source shortest path, eccentricity, and Lapla- cian feature) and graph property regression (connectivity, diameter, radius), well as graph substructure counting (triangle, tailed triangle, star, and 4-cycle) to demonstrate
K-Hop
3=3
100
66.9
6.67
6.67
62
42
K=4
100
100
6.67
6.67
92.7
62.7
K=2
50
50
13.33
13.33
32
22.7
PR K-Hop
K=3
100
66.9
13.33
13.33
62
62.7
K=4
100
100
13.33
13.33
62
62.7
expressive power.
we also perform the original and pruned WI. test on each graph to test whether pruned WL test produces the same number of node classes as the original WL we conclude that the pruned WL test consistent with the original WL. test that graph. The WL Test algorithm applies the hashed and power iterated color refinement algorithm proposed by Kersting K(Kersting et al., 2014), and others are derived from it. The algorithm provided in appendix G:
in Table
Further discussion is provided in Appendia: F.
6. Experiment
In this section, we conduct extensive experiments to evaluate the performance of the pruned frameworks. Specifically, we focus on answering the following three questions:
verify whether pruning improves the frameworks' per- formance, we evaluate the pruned frameworks' perfor- mance on 8 real-world datasets: MUTAG (Debnath al., 1991), DD (Dobson & Doig, 2003), PROTEINS (Dob- son & Doig, 2003), PTC-MR (Toivonen et al., 2003), and IMDB-B (Yanardag & Vishwanathan. 2015) from TU database, as well as QM9 (Ramakrishnan et al., 2014; Wu et al., 2018) and ZINC (Dwivedi et al., 2020) for molecular property prediction. The results are shown
Q1: Do the pruned frameworks have the same expres- sive power as the original frameworks?
Q2: Does the pruning improve the frameworks' perfor- mance?
To verify the expressive power of the pruned frameworks, we empirically evaluate them on three simulation datasets: (1) EXP (Abboud al., 2021), (2) SR25 (Balcilar et al.,

---

PRUNING For GNNS: HIGHER EXPRESSIVENESS, LOWER COMPLEXITY
in Tables to and 6. And all the experimental ma- terials in provided in https: / ///oymoonommmuuuuommom 4open. Patlence///rrueeeee
hop pruned frameworks achieve the best performance, and the pruned frameworks perform well the originals but with fewer parameters. Overall, on all real-world datasets, pruned frameworks outperform their original counterparts.
AC6]/README md
To assess the improvement in the effectiveness of the pruned frameworks, we compare the running time and the number of parameters of the pruned frameworks with the original ones. Detailed dataset statistics and results are provided in the Appendix G.
7. Conclusion
In this work, we proposed pruned versions of MP-GNN, K-Hop, and K-Path frameworks by removing redundant structures, thereby improving efficiency. Our theoretical analysis confirmed that these pruned MP-GNN and K-Hop frameworks retain the expressive power of their original counterparts, with the added benefit of reduced computa- tional complexity, and K-hop MP-GNNs and their pruned architecture exhibit equivalent expressiveness on regular and strongly regular graph. Specifically, the pruned frameworks use fewer parameters. making them more computationally efficient and easier to optimize and train. Through exten- sive experiments, we demonstrated that the pruned frame- works outperform the original ones in terms of runtime and memory usage, while maintaining competitive performance on various benchmark datasets. These results validate the practical advantages of using pruned frameworks without sacrificing expressive power.
Verification of Equivalence of Expressive Power: To ver- ify the equivalence of expressive power, we evaluate both pruned and original frameworks, implementing GIN as the base encoder for each. The results in Table 4 lead to the following conclusions: (1) For both K-Path and K-hop frameworks, expressive power improves K increases. (2) The expressive power of pruned frameworks is comparable to that of the original frameworks, as evidenced by their equally excellent performance. (3) While ensuring equiva- lent expressive power, the pruning framework significantly improves efficiency compared to the original.
Effectiveness on Node/Graph Properties and Substruc- ture Prediction: We compare the pruned frameworks with their original counterparts to evaluate their effectiveness and expressive power node/graph properties and substructure prediction. GIN is used as the base encoder for all frame- works. Pruned K K-hop and K-path frameworks achieve the best performance on most tasks. Morcover, the performance between pruned and original frameworks is highly consis- tent, indicating their equivalent expressive power.
Table 6. ZINC result.
Method
# param.
test MAE
GraphSAGE
480805
0.143++0.0
GIN
356406
0.134+0.007
PR GIN
256406
0.136:+0.012
K-Hop
574613
0.079110.015
PR K-Hop
476615
0.077+00009
K-Path
581659
0.082+0.011
PR KPPath
456414
0.079+0.004
Evaluation on TU and QM9 Datasets: For the TU datasets, we select the graph kernel-bact method (WL subtree ker- nel) and advanced GNN methods (GraphSNN (Wijesinghe & Wang. 2022) and GraphSAGE (Hamilton al., 2017)) as baseline models. For both the pruned and original frame- works, we use GIN (Xu et al., 2019a) as the base encoder. The results, shown in Table 3, indicate that the pruned frame- works achieve the best performance on almost all tasks. For the QM9 dataset, except for C,,. both K path and K K-hop pruned frameworks outperform the others across all tasks. The ZINC dataset results, shown in Table 5, reveal that K-
8

---

PRUNING For GNNS: HIGHER EXPRESSIVENESS, LOWER COMPLEXITY
Impact Statement
Bodnar, C., Frasca, F., Wang, Y., Otter, N., Montufar, G. F., Lio, P., and Bronstein, M. Weisfeiler and lehman go topological: Message passing simplicial networks. In International Conference on Machine Learning, pp. 1026- 1037. PMLR, 2021b.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Bouritsas, G., Frasca, F., Zafeiriou, S. P., and Bronstein, M. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
Acknowledgements
This work is supported by the National Key R&D Program of China under grant 2022YFA 1003900 and National Natu- ral Science Foundation of China under Grant T2341006.
Brijder, R., Geerts, F., Bussche, J. V. D., and Weerwag, T. On the expressive power of query languages for matrices. ACM Transactions on Database Systems (TODS), 44(4):
References
1-31, 2019.
Abboud, R., Ceylan, t., Grohe, M., and Lukasiewicz, T. The surprising power of graph neural networks with random node initialization. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, pp. 2112-2118, 8 2021. doi: 10. 10.249663/iccai22221/99, URL https:/ /oo. 222444436/....22222
Brossard, R., Frigo, O., and Dehaene, D. Graph convolu- tions that can finally model local structure. arXiv preprint arXiv:2011.15065 2020.
Chen, Z., Villar, S., Chen, L., and Bruna, J. On the equiv- alence between graph isomorphism testing and function approximation with gnns. In Advances in Neural Infor- mation Processing Systems, pp. 15894-15902, 2019.
Abu-El-Haija, S., Perozzi, B., Kapoor, A., Alipourfard, N., Lerman, K., Harutyunyan, H., Ver Steeg, G., and Gal- styan, A. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In in- ternational conference machine learning, pp. 21-29. PMLR. 2019.
Chen, Z., Chen, L., Villar, S., and Bruna, J. Can graph neural networks count substructures? Advances in neural information processing systems, 2020.
Chien, E., Peng, J., Li, P., and Milenkovic, O. Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations, 2021. URL https://p///.. /wwnreveeeeeeeeeeeeeeeeeerrr.eem net/ forum?
Azizian, W. and Lelarge, M. Expressive power of invariant and equivariant graph neural networks. In International Conference on Learning Representations, 2021.
id-n6]17fLxi?
Cotta, L., Morris, C., and Ribeiro, B. Reconstruction for powerful graph representations. In Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, W. (eds.), Advances in Neural Information Processing Systems, 2021. URL https: attps://openreee /wpp/reveeeeeeeeeeeeeeeeee net forum? id=2KbZ 4meb191.
Balcilar, M., Héroux, P., Gaüzère, B., Vasseur, P., Adam, S., and Honeine, P. Breaking the limits of message pass- ing graph neural networks. In Proceedings of the 38th International Conference on Machine Learning (ICML), 2021.
Barceló, P., Geerts, F., Reutter, J., and Ryschkov, M. Graph neural networks with local graph parameters. In Advances in Neural Information Processing Systems, volume 34, pp. 35280-25293, 2021.
Debnath, A. K., Lopez, d. C. R., Debnath, G., Shusterman, A. J., and Hansch, C. Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydropho- bicity. Journal of medicinal chemistry, 34(2):786-797, 1991.
Bevilacqua, B., Frasca, F., Lim, D., Srinivasan, B., Cai, C., Balamurugan, G., Bronstein, M. M., and Maron, H. Equivariant subgraph aggregation networks. In International Conference on Learning Representations, 2022. URL https://///........ http://pppeeeeeeeeeeeeeee/ net/ forum? id cd=dFbXQaRk15w.
Dobson, P. D. and Doig, A. J. Distinguishing enzyme struc- tures from non-enzymes without alignments. Journal of molecular biology, 330(4)7771-83, 2003.
Duvenaud, D. K., Maclaurin, D., Iparraguirre, J., Bombarell, R., Hirzel, T., Aspuru-Guzik, A., and Adams, R. P. Con- volutional networks on graphs for learning molecular fin- gerprints. In Advances in neural information processing systems, pp. 2232,, 2015
Bodnar, C.,, Frasca, F., Otter, N., Wang, Y. G., Liò, P., Mont- ufar, G., and Bronstein, M. M. Weisfeiler and lehman go cellular: CW networks. In Advances in Neural Informa- tion Processing Systems, volume 34, 2021a

---

PRUNING For GNNS: HIGHER EXPRESSIVENESS, LOWER COMPLEXITY
Dwivedi, V. P., Joshi, C. K., Luu, A. T., Laurent, T., Bengio, Y., and Bresson, X. Benchmarking graph neural networks. arXiv preprint arXiv:2003. 009882 2020.
Maron, H., Fetaya, E., Segol, N., and Lipman, Y. On the universality of invariant networks. In International con- ference machine learning, pp. 4363-4371. PMLR, 2019c.
Frasca, F., Bevilacqua, B., Bronstein, M., and Maron, H. Understanding and extending subgraph gnns by rethink- ing their symmetries. arXiv preprint Wiiv:2206.111444 2022.
Michel, G., Nikolentzos, G., Lutzeyer, J. F., and Vazirgian- nis, M. Path neural networks: Expressive and accurate graph neural networks. In International Conference on Machine Learning, pp. 14737-244555 PMLR, 2023.
Geerts, F. On the expressive power of linear algebra on graphs. Theory of Computing Systems, 65:179-239, 2021.
Morris, C., Ritzert, M., Fey, M., Hamilton, W. L., Lenssen, J. E., Rattan, G., and Grohe, M. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceed- ings of the AAAI Conference on Artificial Intelligence. volume 33, pp. 4602-4609, 2019.
Geerts, and Reutter, L. Expressiveness and approxima- tion properties of graph neural networks. In International Conference Learning Representations, 2022.
Hamilton, W., Ying, Z. and Leskovec, J. Inductive repre- sentation learning on large graphs. In Advances in Neural Information Processing Systems, pp. 1025-1035, 2017.
Morris, C., Rattan, G., and Mutzel, P. Weisfeiler and le- man go sparse: Towards scalable higher-order graph beddings. Advances in Neural Information Processing Systems, 33:21824-21888 2020.
Horn, M., De Brouwer, E.,, Moor, M., Moreau, Y., Rieck, B., and Borgwardt, K. Topological graph neural networks. In International Conference on Learning Representations, 2022.
Morris, C., Rattan, G., Kiefer, S., and Ravanbakhsh, S. Spe- qnets: Sparsity-aware permutation- permutation-equivaraani graph net- works. In International Conference on Machine Learning, pp. 16017-16042. PMLR, 2022.
Jokić, I. and Van Mieghem, P. Number of paths in a graph. arXiv preprint (:X.v:2209.088844 2022.
Murphy, R., Srinivasan, B., Rao, V., and Ribeiro, B. Re- lational pooling for graph representations. In Interna- tional Conference on Machine Learning, pp. 4663-4673 4673. PMLR, 2019.
Keriven, N. and Peyré, G. Universal invariant and cquivariant graph neural networks. arXiv preprint 1rXiv:1905.04443, 2019.
Kersting, K., Mladenov, M., Garnett, R., and Grohe, M.
Nikolentzos, G., Dasoulas, G., and Vazirgiannis, M. k-hop graph neural networks. Neural Networks, 130: 130:195-205, 2020.
Power iterated color refinement. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 28, 2014.
Papp, A. and Wattenhofer, A theoretical compari- son of graph neural network extensions. arXiv preprint arXiv: 12884, 2022.
Kipf, T. N. and Welling, M. Semi-supervised classifica- tion with graph convolutional networks. In International Conference Learning Representations, 2017.
Qian, C., Rattan, G., Geerts, F., Morris, C., and Niepert, M. Ordered subgraph aggregation networks. arXiv preprint arXiv:2206. 1 1666 2022.
Li, Y.. Tarlow, D., Brockschmidt, M.. and Zemel, R. Gated graph sequence neural networks. arXiv preprint arXiv:1511.0549. 2015.
Ramakrishnan, R., Dral, P. O., Rupp. M., and Von Lilienfeld, O, A. Quantum chemistry structures and properties of 134 kilo molecules. Scientific duta, 1(1):177, 2014.
Ma, Z., Xuan, J., Wang, Y. G., Li, M., and Liò, P. Path integral based convolution and pooling for graph neural networks. Advances in Neural Information Processing Systems, 33:16421 2020.
Suzuki, T. Graph neural networks exponentially lose expressive power for node classification. ICLR2020, 8, 2020. URL https: //cir wweeeriniiiiie. .ii. mii.ac.jj/crid 101029061 731366621119199977
Maron, H., Ben-Hamu, H., Serviansky, H., and Lipman, Y. Provably powerful graph networks. Advances in Neural Information Processing Systems, pp. 2156-2167, 2019a.
Thiede, E., Zhou, W., and Kondor, R. Autobahn: Automorphism based graph neural nets. In Advances in Neural Information Processing Systems, volume 34, pp. 29922-29934, 2021.
Maron, H., Ben-Hamu, H., Shamir, N., and Lipman, Y. In- variant and equivariant graph networks. In International Conference on Learning Representations, 2019b.
10

---

PRUNING For GNNS: HIGHER EXPRESSIVENESS, LOWER COMPLEXITY
Toenshoff, J., Ritzert, M., Wolf, H., and Grohe, M. Graph learning with 1 convolutions random walks, arXiv preprint arXiv:2102.08788 2021.
Zhang, M. and Li, P. Nested graph neural networks. In Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems, 2021. URL https: /ttppp/eee/eeeeeieenn.ee forum? d=2_eEEvF
opw.revieneveeeeeeeeeeeeee .eteeeeeewweeeeeeeeeeeee..... nnt/
Toivonen, H., Srinivasan, A., King, R. D., Kramer, S., and Helma, C. Statistical evaluation of the predictive tox- icology challenge 2000-2001. Bioinformatics, 19(10) 1183-1193, 2003.
Zhang, M., Cui, Z.,, Neumann, M., and Chen, Y. An end-to- end deep learning architecture for graph classification. In AAAI, pp. 4438 4445, 2018.
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P.. and Bengio, Y. Graph attention networks. In International Conference on Learning Representations, 2018. URL wttpt:tp///// bestps://ppenreviee..eeee id=rJXMpikC2.
Zhang, S., Zhang, J., Song, X., Adeshina, S., Zheng, D., Faloutsos, C., and Sun, Y. Page-link: Path-based graph neural network explanation for heterogeneous link predic- tion. In Proceedings of the ACM Web Conference 2023, pp. 3784-3793, 2023.
Vignac, C., Loukas, A., and Frossard, Building powerful and equivariant graph neural networks with structural Bessaage-passing arXiv e-prints, pp. arXiv-2006, 2020.
Zhao, L., Jin, w., Akoglu, L., and Shah, N. From stars sub- graphs: Uplifting any gnn with local structure awareness. In International Conference on Learning Representations, 2022.
Wang, G., Ying, R., Huang, J., and Leskovec, J. Multi-hop attention graph neural networks. In International Joint Conference on Artificial Intelligence, 2021.
Weisfeiler, B. and Lehman, A. A reduction of graph to a canonical form and an algebra arising during this reduction. Nauchno-Teehhniheekkaya Informatsia, 2(9): 12-16, 1968.
Wijesinghe, A. and Wang, Q- A new perspective on "how graph neural networks go beyond weisfeiler-lehman?. In International Conference on Learning Representations, 2022. URL /ettps://operrettt net. forum? id id-uxgg9o7bI__3
Wu, Z., Ramsundar, B., Feinberg. E. N., Gomes, J., Ge- niesse, C., Pappu, A. S., Leswing, K., and Pande, V. Moleculenet: a benchmark for molecular machine learn- ing. Chemical science, 9(2):513-530, 2018.
Xu, K., Hu, W., Leskovec, J., and Jegelka, How powerful are graph neural networks? In International Conference Learning Representations, 2019a. URL https:// openreview net wewteeeorrridooooeeeeee 61A5Km.
Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? In International Conference on Learning Representations, 2019b.
Yanardag, P. and Vishwanathan, S. Deep graph kernels. In Proceedings the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1365-1374. ACM, 2015.
You, J.,
J. M., Ying, R., and Leskovec, J. Identity- aware graph neural networks. Proceedings of the AAAI Conference on Artificial Intelligence, 35(12): 10737-10745, May 2021.

---

PRUNING For GNNS: HIGHER EXPRESSIVENESS, LOWER COMPLEXITY
Appendix
A. Related Work
Following the pioneering studies of Xu et al. (2019b); Morris et al. (2019), a substantial body of research has focused on designing novel GNN architectures that surpass the expressiveness of the 1-WL. test. Broadly, these approaches can be categorized as follows.
Higher-order GNNs. Unlike traditional GNNs, higher-order GNNs compute representations for multi- multi-tuples of nodes and employ tensor operations to aggregate features across these tuples (Morris et al., 2019; Maron et al., 2019b;c;a; Keriven & Peyré, 2019; Azizian & Lelarge, 2021; Geerts & Reutter, 2022). However, the computational complexity of higher-order GNNs increases exponentially with the number of tuples, making them unsuitable for large-scale graphs. This challenge has motivated research into localized variants of higher-order GNNs, which leverage the sparse and local nature of graphs to reduce complexity at the cost of some expressiveness. Notable models include the 1-2-3 GNN (Morris et al., 2019), PPGN (Maron et al., 2019a), and Ring-GNN (Chen et al., 2019), which aim to approximate higher-order WL tests while maintaining computational efficiency. For example, Morris et al. (2020; 2022) introduced methods that localize k-WL. aggregation to exploit graph sparsity (see Appendix B.2), while Vignac et al. (2020) proposed localized 2-order GNN whose expressive power aligns with 3-IGN (Maron et al., 2019c). These developments illustrate how localized higher-order GNNs strike a balance between expressiveness and scalability, enabling their practical use in real-world applications.
Substructure-basee GNNs, Chen et al. (2020) showed that standard message passing GNNs fail to detect or count common substructures such as cycles, cliques, and paths. Building on this insight, another approach to enhancing GNN expressiveness involves leveraging substructure information within graphs. For example. Bouritsas al. (2022) proposed the Graph Substructure Network (GSN), which integrates substructure counting into node features via a preprocessing. This idea was further extended by Barceló et al. (2021) through homomorphism counting. Additional progress has been made by Bodnar et al. (2021b;a); Thiede et al. (2021); Horn et al. (2022). who introduced novel WL aggregation strategies that incorporate specific substructures like cycles and cliques. Moreover, Toenshoff et al. (2021) employed random walk techniques to generate small substructures for GNNs.
Subgraph GNNs. Recent approaches have explored breaking graph symmetry to better distinguish highly symmetric structures. These methods generate subgraphs according to predefined policies and then aggregate features across all subgraphs. Various subgraph generation strategies have been investigated. For instance, (Cotta et al., 2021) proposed node deletion strategy, while (Bevilacqua et al., 2022) studied an edge deletion method. Additionally, node marking techniques have been explored by (Papp& & Wattenhofer, 2022). and ego-network-basse approaches have been examined in (Zhao et al., 2022: Zhang & Li, 2021; You et al., 2021). ID-GNN (You et al., 2021) extracts ego-networks and labels the root node to break symmetry, while NGNN (Zhang& & Li, 2021) uses subgraph pooling to encode rooted subgraphs, improving expressiveness for distinguishing regular graphs. For the aggregation mechanisms of subgraphs, some methods have been explored to improve expressiveness by leveraging structural information. For instance, ESAN (Bevilacqua al., 2022), performs layer-wise aggregation across subgraphs, enhancing expressive power. Building on this, Frasca al. (2022) proposed relaxed symmetry analysis, demonstrating that the expressiveness of such approaches is bounded by 3-WL. Furthermore, Qian et al. (2022) established connections between subgraph GNNs and k-FWL, introducing a learnable subgraph generation policy for improved flexibility.
Multi-aggreeation GNNs Several existing works have been developed to instantiate the K hohop or K K-path message passing framework. For instance, MixHop (Abu-Ea Haijaa et al., 2019) applies message passing on each hop using graph diffusion kernel, then concatenates the representations across all hops form the final output. K-hop sequentially executes message passing from hop K to hop 1 to compute the central node's representation, though its computational procedure limits parallelizability in (Nikolentzos et al., 2020). MAGNA (Wang et al., 2021) incorporates an attention mechanism into K-hop message passing. Similarly, GPR-GNI (Chien et al., 2021) employs a graph diffusion kernel to perform graph convolution on K-hop neighborhoods and aggregates the results using learnable parameters. However, these approaches do not provide a formal definition of K-hop message passing or analyze its theoretical representational capabilities and limitations. Additionally, PathNNs (Michel et al., 2023) introduces a model that updates node representations by aggregating paths originating from the nodes. Path Integral- -aasd Convolution and Pooling for GNNs (Ma et al., 2020) proposes a
12

---

PRUNING For GNNS: HIGHER EXPRESSIVENESS LOWER COMPLEXITY
framework called PAN, which leverages path integrals enhance GNN expressiveness and pooling mechanisms.
B. The Weisfeiler-Lehman (WL) Algorithm and Its Variants
In this section, we describe the existing WL algorithm and its some variants.
B.1. Weisfeiler-Lehman Algorithm
The I-dimensional Ceisfeiler-Lehmadd algorithm (1-WL), also known as the color refinement algorithm, iteratively computes a color mapping XG for graph G = (V; E), where each vertex u E V is assigned a color Xc(v) E C, with C denoting the set of colors. The pseudo-code for 1-WL. is presented in Algorithm 1. Initially, all vertices are assigned the same color. At each iteration I, the algorithm updates the color of each vertex v by combining its current color with the multiset of colors of its neighbors by hash function, denoted m (v). Then the hash function is then applied produce the new color X (v).. This procedure is repeated for predefined number of iterations I. or until convergence.
Algorithm 1 The 1-WL Algorithm
(V, E) and the number of iterations L. 2: Initialize: Choose fixed (arbitrary) element co C, and set (v) == co for all V.
Input: Graph
3: for | 1--1 1 to L do
4: for each u E V do
5: m' (v) H Hash(1ix (f N(O)))
6: x²())= == Hash (x (u).
7: end for
8:
end for
9: Output: Color mapping X V:V- C.
At each iteration, the color mapping induces a partition of the vertex set V. A key property of the 1-WL algorithm that each iteration refines this partition, resulting in a progressively finer partition. Since the vertex set V is finite, the algorithm guaranteed reach a stabilization point where the partition no longer changes.
The 1-WL algorithm can be used to determine whether two graphs G and H are isomorphic by comparing their representa- tions. It is fast and effective method for many practical applications, particularly when dealing with large graphs or when quick approximation is sufficient. If the two representations differ, the graphs are not isomorphic, making 1-WL a necessary condition for graph isomorphism. However, the 1-WL test may fail to distinguish between two con-isomorppic graphs G and H. This limitation has motivated the development of more expressive higher-order WL tests, as discussed in the next subsection.
B.2. The k-dimensional Weisfeller-Lehman Algorithm (k-WL)
The k-dimensional Weisfeiler-Lehhaal algorithm (k-WL) extends the 1-WL, algorithm by enhancing its expressive power through the coloring of k-tuples of vertices from V(G)* instead of individual vertices.
To begin, we introduce the concept of neighborhood in the context of k-WL. For a k-tuple (SI..... sn) E V(G)*, the j-th neighborhood N (s) is defined as:
Ny(s) = 85-1,, $j+1..... .t) 1 ((G)),
(18)
where (s) formed by replacing the j-th component of s with every vertex r VGG.. This definition enables the algorithm to explore the structural context of the k-tuple by systematically iterating over all possible substitutions for its j-th component.
This algorithm computes a coloring function x V(G) + C at each iteration t. At iteration / = 0, each k-tuple E V(G) is assigned an initial label based on its atomic type. Specifically, two k-tuples and s' receive the same color if the map s; + s/ induces an isomorphism between the subgraphs induced by the nodes in s and s', respectively. For > 0, the algorithm updates the label of each k-tuple s by aggregating information from its j-th neighborhoods (s). The pruned
13

---

PRUNING For GNNS: HIGHER EXPRESSIVENESS, LOWER COMPLEXITY
labels are computed follows:
= HasHHahh Hash((x' Ny(+))).
(19)
where C² (s) captures the aggregated information from the j-th neighborhood of s. The final label of s at iteration is then computed as:
(()) (C(),,,
(20)
This refinement ensures that two tuples and s' with identical labels at iteration t - 1 will receive different labels at iteration t if there exists a j E [1: : k] such that the distribution of j-neighbors with specific colors differs between 8 and s'. In summary, the pseudo-code for SC-WL is provided Algorithm 2.
Algorithm 2 The k-WL Algorithm
1: Input: Graph = (V, E) and the number of iterations L.
2: Initialize: Define tuples V(G)*, choose a fixed element co E C, and set (v) == co for & V(G)*.
3: for |
L do
4: for each V(G)** do
5:
(+) Hash Hash (1(x- & (n))))
6:
(s) Hash((((s), (C(),,) (s.
7: end for
8: end for
9: Output: Color mapping X V(G)* + C.
By operating on k-tuples of vertices rather than individual nodes, the k- WL algorithm substantially enhances its capability to distinguish between non-isomorphic graphs. However, this improvement in expressive power comes the expense of increased computational complexity, which grows rapidly as k increases. Consequently, practical implementations typically involve trade-off between the value of k and the associated computational cost.
B.3. The K K-Path Weisfelle-LLeman Algorithm (K- WL)
The K-Path WL algorithm extends the classical WL method by incorporating paths of length K, rather than focusing solely on the immediate neighborhood of vertices. To begin, we recall the definition of the k-path neighborhood. Let N walk (e) denote the set of all distinct paths of length starting from vertex v. A path (u, W1 u2, 44) is defined as a sequence of vertices and edges in which no edge or vertex repeated. We say that a vertex ug is a k-path neighbor if there exists a path (v. ,,,..... ux) E & Waal(()) (v), with ug being the terminal vertex the path.
At the beginning, each vertex u V is assigned initial label x (v), typically derived from vertex-specifie features such as its degree other attributes. In each iteration 1, the algorithm updates the label (z) of each vertex by aggregating information from the t-path neighborhood for / E [1, K]. Specifically, for each / [1, K].
(x) = Hash (x), (x'=((x) | Qu E Npaen (v)})
(21)
Then, the algorithm updates the original label (v()) by aggregating the labels from the t-path neighborhoods x((v) for all t [1, K]. Specifically,
x Hash
Hash (xx(0) Ite [I.)
(22)
This process of refinement continues until the labels stabilize, meaning no further updates occur during an iteration. The pseudocode for the K-IWI. algorithm provided in Algorithm 3.
14

---

PRUNING For GNNS: HIGHER EXPRESSIVENESS, LOWER COMPLEXITY
Algorithm 3 The K-Path WL Algorithm
1: Input: Graph G = (V,E), E), number of iterations L.
2: Initialization: Vu E V. xx))
3: while S do
4: 1=1+1.
5: for V do
6: fort E [1, K] do
7:
xi(u)= = Hosh( u No. paun (v))
8:
end for
9:
X (v) = (x), (z)...... xxx())).
(v), (v), (u)). ((( Hash(x 1-1 (v),
end for 11: end while
12:
Output: Final labels (v) for all u eeW V.
While this method is heuristic and may yield false positives or negatives, it provides a practical tool for many applications. This extension improves the algorithm's capacity to differentiate between large and intricate graphs, making it especially valuable for applications in graph databases and pattern recognition.
B.4. The KoHop Weisfeiler-Lehman Algorithm (K-Hop WL)
The Kop WL algorithm extends the classical WL method by considering the K-hopp neighborhoods of vertices, rather than focusing solely on their immediate neighbors (Nikolentzos et al., 2020). To begin, we recall the definition of the t-hop neighborhood. Let Nop (v) denote the set of vertices that are exactly a distance of hops from vertex v, where the distance measured by the shortest path between u and each vertex in Mopp (v). It is important to note that the t-hop neighborhoods different hop levels are disjoint, meaning that each vertex belongs to exactly one (-hop neighborhood for given l.
At the start, each vertex degree other attributes. In each iteration the algorithm updates the label x1( of each vertex by aggregating information from its t-hop neighborhood for t [1, K]. Specifically, for each [1, K].
is assigned an initial label x (v). typically derived from vertex-specific features such as its
(v) Hash (w), fx (u)
(r))()))
(23)
Then, the algorithm updates the original label x x'(v) by aggregating the labels from the t-hop neighborhoods x((e) for all E KJ. Specifically,
(v) = Hash ((x1()) | | []]).
(24)
This refinement process continues until the labels stabilize, meaning no further changes occur in an iteration. The pscudocode for the K KChop WL algorithm provided in Algorithm 4.
Algorithm 4 The K K-Hop WL Algorithm
1: Input: Graph G = (V, E), number of iterations L.
2: Initialization: Vu E V. V (u).1=
3: while < do
4: 1= 1.
5: for V do
6: fort E [1, K] do
7:
xd(x) = Hash( (w) :::::):))) u Nhop (v))))
8:
end for
9:
(v) (x) (v) xx(()).
x'(x) = Hash(x (v), x'))).
end for end while
Output: Final labels x(v) for all v V.
15

---

PRUNING For GNNS: HIGHER EXPRESSIVENESS, LOWER COMPLEXITY
C. The Pruned Weisfeiler-Lehman Algorithm and Its Variants
In this section, we present our pruned versions of the WL algorithms and provide an intuitive comparison between the standard WL and the pruned WL. highlightnng their performance differences.
C.I. The Pruned Weisfeiler-Lchmen Algorithm (PR WL)
The Pruned Weisfeiler-Lchann (PWL) algorithm builds upon the standard WL method by introducing additional steps that refine the label update process using hierarchical hashing. Unlike the original WL algorithm, PWL employs hierarchical approach for label refinement. Initially, each vertex assigned initial label x x²(x). During the 1-th iteration, each vertex aggregates the labels of its - neighbors, specifically:
my (ig=i(v) Hash (fxx-t(u)= : N (wak()))))
(25)
Subsequently, each vertex updates its label by applying a hash function to both its previous label and the aggregated neighborhood information, as follows:
x((x) = Hush (x² miy
(26)
The pseudocode for the Pruned WL. algorithm provided in Algorithm
Algorithm 5 The PR WL Algorithm
Input: Graph G (V,E), E). number of iterations L.
2: Initialization: Vu E V, (v),
3: while / < L do
4: 1= 1 1,t=1 1,
5: mi (v) = Hash (oxsh(((1(111)) ((xx= :
6: for Vu E do
7: while < 2/-1 do
8:
t= t=t+1
9:
m)(v)= Hash (f/m/ (u) N(M).. N()M)
10:
end while
11:
x((r)=
(v)).
12: end for
13:
end while
14:
Output: Final labels (v) for all v E V.
C.2. The Pruned K K-Path Weisteiler-Lehman Algorithm(PR K-Path WL)
To address the computational overhead the K-path WI. algorithm, pruned version is proposed, which selectively reduces the complexity by focusing on relevant paths at each iteration.
Unlike the standard K K-path WL, the pruned version aggregates features from the I-path neighbors Ne path the K K-path
neighbors N path at the th layer (I < K), rather than from the 1-path neighbors N to the K K-path neighbors path Let X denote the feature of node v at the 1th layer. When 7 K, the pruned K K-pWI. is defined as follows:
X Hash( ffx (w)lu E No path (
(27)
X Hash(Hlsh (* = (l.. KJ)
(28)
else when 2 K, the K --path pruned Message passing framework can be defined as follows:
H Hash(x (v), Hxx--(u)lu E N path (v)
(29)
The pruned algorithm is outlined in Algorithm 6.
16

---

PRUNING For GNNS: HIGHER EXPRESSIVENESS, LOWER COMPLEXITY
Algorithm 6 The Pruned K-Path WL Algorithm
1: Input: Graph G = EV, E, X), number of iterations L.
2: Initialization: Vv E V. (v,
3: while S K do
4: 1=1+1.
5: for E V do
6: fort E K] do
7:
xi(u)= = Hosh( E Naat paan(()) (+))
8:
end for
9:
X' (') (xi(e), (1)
(v). xxx())).
('(r) Hash(x'-1(0 (v)).
10: end for
11: end while
while < do
1=1+1.
14: for V do
15:
x'(x) Hash (xx-=((x)) E paen pm (v)}
16:
end for
17:
end while
18:
Output: Final labels (v) for all v V.
Compared to the standard K-Path WL algorithm, the pruned version achieves greater computational efficiency by dynami- cally adjusting the paths considered at each iteration. This reduction in complexity makes more suitable for large-scale graphs while preserving much the discriminative power the original algorithm.
C.3. The Pruned K-Hop Weisfeiler-Lehman Algorithm (PR K-Hop WI.
To further enhance computational efficiency, a pruned version of the K-hopp WL algorithm is introduced. Unlike the standard K- K-hop WL, the pruned version aggregates features from the I-hop neighbors Nhpp to the K-hop neighbors N at the tt layer (1 < K), rather than from the 1-hop neighbors Nhop to the K K-hop neighbors N hop Let x!. denote the feature of node the ( layer. When / S K, the pruned K-hWL defined as follows:
hop
X = Hash(x' ltx (u)lue (1)
(30)
X Hash(((x"*(v)) .....))))
(31)
else when 2 K, the K K-Hop WL can be defined as follows:
H = Hxss(x"-1(0)) (xxxxx(() NK
EN) (o)
(32)
The pruned algorithm outlined in Algorithm
17

---

PRUNING For GNNS: HIGHER EXPRESSIVENESS, LOWER COMPLEXITY
Algorithm 7 The Pruned K-Hop WL Algorithm
1: Input: Graph G = E), number of iterations L.
2: Initialization: Vv E V. (x),
3: while S K do
4: 1=1+1.
5: for E V do
6: fort E K] do
7:
xi(u)= = Hosh((tx- u (+))))
8:
end for
x' (') = (xi(e), X14))) (v). ,xx(o)).
9:
('()) Hash(x"-1(0
10: end for
11: end while
while < do
13:
1=1+1.
14: for V do
15:
x'(x)= Hash (x) :u) (v))))
16:
end for
17:
end while
18: Output: Final labels (v) for all v e V.
Compared the standard K K-Hop WL algorithm, the pruned version significantly reduces computational overhead by dynam- ically adjusting the neighborhoods considered during early iterations. This approach maintains much of the expressiveness of the original algorithm while being more scalable for large graphs.
C.4. Process of WL Test, Pruned WL Test and Pruned 2-hop WL Test on Long-refinement Graph
Long-refinement graphs a class of graphs for which the WL test does not terminate until it has iterated [V| 1 times. As shown in Table 7, the adjacency lists of the long-refinement graph G are provided. The Figures 4 and 5 illustrate the process of the WL test and the pruned WL test applied to graph G. During these processes, the WI. test requires 11 iterations to terminate, whereas the pruned WL test and 2-Hop WL test only needs 4 iterations to achieve the same result as the WL test. Therefore, the pruned WL test and 2-Hop WL test is more efficient than the standard WL test.
N(v)
N(e)
6
3,7,8,9,11
0,2,3.4.5
7
2,6,8,9,10
2
1,3,5,7,10
5,6,7,10,11
3
1,2,4,6,10
9
4.6,7.10,11
1,3,5,9,11
10
2.3,7,8.9
1,2,4,8111
11
4,5,6,8,9
Table 7. Adjacency lists of long-refinement graph G
The Figure 6 illustrates the process the pruned WL test applied to graph G. The results illustrate the process of the WL test and the pruned 2-hop WL test applied to graph G. During these processes, the WL test requires 11 iterations aggregation and combination terminate, whereas the pruned 2-hop WL test only needs iterations of aggregation and 4 iterations of combination achieve the same result as the WL test. Therefore, the pruned 2-hop WL test is more efficient than the standard WL test.
D. Detail of Matrix Language
Recently, Brijder (Brijder et al., 2019) and Geerts (Geerts, 2021) proposed a new matrix language called MATLANG. Matrix languages can formalized as compositions linear algebra operations. Intuitively, linear algebra operation takes
18

---

PRUNING For GNNS: HIGHER EXPRESSIVENESS, LOWER COMPLEXITY
Seresion
Figure 4. Process WL test on Long-refinement Graph
Srewion
Figure Process of pruned WT. test on Long-refinement Graph
19

---

PRUNING For GNNS: HIGHER EXPRESSIVENESS, LOWER COMPLEXITY
Figure 6. Process of pruned 2-hop WL test on Long-refinement Graph
number of matrices as input and returns another matrix (vector scalar). More specifically, for linear algebra operations .p...... op the corresponding matrix query language is denoted by ML(op),--. ). This language includes various operations on matrices and establishes explicit connections between specific sets of operations and the WL tests, including the 1- and 3- WL tests. The expressive power of MATLANG varies depending on the operations included each set.
Definition D.1. MLCC) is a matrix language with an allowed set of operations L = {opt,...,op.. where op, E +. diag, tr, 1, x, f.. The possible operations are introduced the Appendix.
Definition D.2. A scalar sentence e(X) E R ML consists of any possible consecutive operations in being applicd to given matrix X, resulting
scalar value. Similarly, a vector sentence e(X) E R" in ML (C) results in a vector, and a matrix sentence e(X) E R=x* in M (C) results matrix.
For example, if A is the adjacency matrix of graph G, then e(A) 1 A1 scalar sentence in ML) with f- 1}. computing the number of edges in G. Additionally, e(A) A1 is vector sentence in (L), computing the number of neighbors for each node in G. Geerts (Geerts, 2021) demonstrated that the languages L C2, and L3 can characterize the WL test. The results are summarized as follows:
Remark D.3. Two adjacency matrices are indistinguishable by the 1-WL test if and only if e(Ac) e(Ac') for all (C,, where L {.. 1, diag). Hence, all possible scalar sentences in (L) are identical for 1-WL equivalent adjacency matrices. Thus, G =1-WL G" Ag (L)(C.) Ag'. (See Theorem 7.1 in (Geerts, 2021).)
Remark D.4. Denote the operation On as pointwise vector multiplication on vector sentences. The expressive power of (L, is equivalent that of (Ls) where Cs- {., 1, 1.). Thus, for any two adjacency matrices Ag and Agr, they are indistinguishable by all possible sealar sentences in (L, if and only if they are indistinguishable by all possible scalar sentences in ML Ag (Cs) Ac ++ AG (MI:(CC) Ag'. (see Proposition 8.1 in (Geerts, 2021)) Remark D.5. Two adjacency matrices are indistinguishable by the 3-WL test if and only if they are indistinguishable by any scalar sentence in ML (Ls)) where L3- = {-, 1, diag, tr, }}. Thus, G = WL G' ++ Ag ML (Cx) (see Theorem 9.2 in (Geerts, 2021)) Remark D.6. Enriching the operation set to L+ = LUt+, f), where L E (L1, Lz). does not improve the expressive power of the language. Thus, AG (C) Ag + AG (MT"(Ct) Ag. (see Proposition 7.5 in (Geerts, 2021))
For any two vectors H1, H2 RR, we denote Hi ~a H2 if there exists permutation such that Vi E [1, Hi) Hz)a( For any two matrices A₁ and Ag. we denote A ~a A₂ if there exists a permutation a such that Vi,j E [1, (i = (()())))())) We denote AG =MIA(2) Ag if there exists a permutation a such that for all e E (L), e(Ac) ~ e(Arr). ). Similarly, we denote AG =M()(E) Acr if there exists a permutation a such that for all E ML)( e(Aa) ~a e. In this research, we propose the language MT((a) with La = 1, diag, o} and prove the equivalence between M ((C)) and M L(Ca) as follows:
Lemma D.7. For all i E (0, 1,2, AG (MI((Cs) Ag + AG EMI((C)) Age Lemma D.8. For all L E (C1, L2, Ls, L.), AG MMTA(C) Ag - Ag EMI((C) Ag + AG MMI((C) Age.
Proofs are provided in the Appendix E.
The list of operations in Table 8 differs slightly from the list presented in Brijder Brijder et al., 2019: Instead of denoting
20

---

PRUNING For GNNS: HIGHER EXPRESSIVENESS, LOWER COMPLEXITY
conjugate transposition (op(e) = =)) e(v(X)) = A E C
e(v(X))* = A E C
(A*); = Ags
one-vector = =
c(v(X)) A C
1(e(v(X)) E Cmxi
1, 1,=1
diagonalization of vector (op(e) = diag(e))
diag(A); Ai
c(v(X)) A Cmxl
diag(e(v(X)) diag(A) E Cm
diag( (A)ss 0, i +
matrix multiplication (op(e1, c1 (x(((X) A Cmxn
C C
Cj Σ Art Bkj
ex(r(X)) B E C
matrix addition (op(e1, E2) = (x)) = E Cm
(v(())) + +e((((x)) C
Cij = Aij + Bii
(x()(X)) = B mm
scalar multiplication (eX exc(v(X)) = B E M
e(v(X)) = A C
Bij = cx Asj
trace (cp = tr(e))
e(v(X)) = A Cm
tr(e(u(X)) =CE
C Σm Ai
pointwise vector multiplication (op(e1, 62) 61 O 62)
(x)( A Cm
ci(v(X)) On e2(u(X)) C E Cmx1
C A x B
(x)) B E Cm
pointwise matrix multiplication (Schur-Hadamarde (0p(c1, = Ce) (x))) A E C
( C Cm
Cjj = Aij Big
e2(v(X)) B E Cm
pointwise function application (op(ei,.... htp..//....p.p...l...o.......... ()(((X) = A E mm
(1.... -CE
ppphfflee(l(x)).......ll = B Cmn Bi f(A! ..... A!)
ex(v(X)) A() E CM
Table Linear algehra operations supported in MATLANG and their semantics. In the last column, -, + and x denote complex conjugation, addition and multiplication C, respectively, Brijder al., 2019
ML ) every matrix language which returns vector, we denote (op.o.. . (op. as every matrix language which returns another matrix (vector or scalar).
E. Materials Of Proofs
E.1. Proof of lemma D.7
Lemma E.1. For all i (0,1,2). AG MMi(((ss) AG Ao MMD((A) Ac.
Proof. Note that equation
e(A) -TT (A ding (1). tr()).
(33)
Hence we have e E (L.( that e(A) = (r(),, which implies E (L, ML)(C.).
E.2. Proof Lemma D.8
Lemma E.2. For all (L1, Lz, La, L1), Ag =MP Ag - Ao (M) Ag AG EMLº(C) Age
Proof. Since every vector or scalar value is generated by operation {,, +, diag, tr, 1, x, f). Hence if Yop e {,,+. T ,diag, tr, 1, O, ff) op is permutation o preserved, then we can prove the lemma.
Multiplication operation
21

---

PRUNING For GNNS: HIGHER EXPRESSIVENESS LOWER COMPLEXITY
For all vectors H1, 22, T, E R", RR, Hf ~o H2 and Ti ~o T2. then
HT. (10)- E (a((o())-TT(((())) = E H2(1) = -22
(34)
For all vectors H1, H2 E IR" and matrices A1, A2 E Ruxn if Hı ~a H2 and A ~a A2, then
-1) Σ Ai(i,) Σ As(a(0). -2((())) A2 H2(o(1)).
(35)
For all matrices A1, A2, B1, B2 E Ruxn A1 ~a A2 and B1 ~a B2, then
A1 A1..)( Σ A = Σ (z(o(1), (
(2( = A2 B2(o(1).
(36)
k
Hence multiplication operation is preserved.
Operation trace tr: For all matrices A1, A2 E RRax,, if A ~a A2, then
tr tr( = -1(,))) (((o),))()) = tr((2)
(37)
by lemma D.7, there's the corresponding indicator vector of Ir, e(A) (A @ (1)ag(1)) 1, that e(A1) ~a e(A2)
tr(Ai) = (A2), hence the trace operation tr is o-preserved.
Pointwise matrix (vector) multiplication (Schur- Haddmarr @: For all matrices A,, A2, B1, B2 Rn if A ~ A2 and B1 ~n B2, then
A c Bi(i.)) Ai(i.)) Bi A2(o o()) @ B2(a()).(() As o o2(o()).
(38)
For all vectors H1, H2, T. E R", if H1 ~, H2 and Ti T2. then
Hi o (1) = H1 (1) , (1)) = (2) o B(((1)) = H2 @ T2(o(i).
(39)
hence the pointwise matrix (vector) multiplication operation is o-preserved.
Operation of the one-vector For all vectors H1, H2 E IR", H1 ~e Hg, then:
1(1) = 1 = 1()(i)
(40)
Hence the operation of the one-vector is o-preserved.
It's obvious that operation {+, +t,,, is a-preserved, hence Ag MM Ag - Ag EML((C) Ag + Ag =M
Age
E.3. Proof Lemma 4.2
Lemma E.3, Given a positive integer sequence dk. S₁ Evere Cr Sx > 2* then 0g is not viewable.
Proof. We first will prove S, 2" 1: when = 1, if an 1, then S, 1 < 2 1. If a, # 1, then S, 0 2 - Hence the lemma is true when 1.
Assume that the lemma is not true, hence there is a positive integer sequence af and a positive integer n4, where a' 's length of view St 2 2". Define a vector X E 13 (Xn, + )0) We can establish a mapping f : {0, 13 N:
[(x"))
Σ
(41)
IsiSm (1==
22

---

PRUNING For GNNS: HIGHER EXPRESSIVENESS, LOWER COMPLEXITY
By the definition of the viewed integer sequence, AI SIS Snx there exists X E [0, 111")*(X,,, + {0)")) such that f(X*)) L. Since S > 2 the cardinality of the image of f: [Tm(f)) 2 2". However, the other hand, the cardinality of f's domain: HO, 1 [O]", 2 which induces paradox because the cardinality of the image of the mapping is less than or equal to the cardinality of its domain. Hence, An E N+, Sn - 1
We now prove the equation holds iff Cn = 2 v1 - 2 1, has a corresponding vector X" E (0,1)"(X, * (0)"), such that f(X) = I, hence the 2 s length view is 2 1. If there is another positive integer sequence bns its length view S is 2 1, nog is the smallest positive integer such that One + bag if Ing I 2n - 1, then
Σ
by S 2 2.
(42)
iE(I,"
Hence the length of the view of b,s Shg 2
2. If bno
2 -n001 + 1,, since
Σ
b; 2"20
(43)
(E(1... mma
Sh = 2 1, the cardinality of the image f: [m( = 2 - 11+ Eie(1 mo) by 2 2n0, but the cardinality of f's domain: H0, 11 (00) {0) n - L, which induces a paradox because the cardinality the image f exceeds the cardinality its domain. Hence the equation holds iff an 2n-1
E.4. Proof Theorem 4.1
Theorem E.4. Given a positive integer sequence og and pair of graphs(G, (G, Sz = =Eejj ap if is viewable, then
VI MENN N+ GI Glag- -wakk S G1
Proof. Since the sentences in (C,) produce a scalar value which can be reached in the graph readout layer as a sum thanks to 1 // (Hend), we need to show that if ag is viewable, the eq.8 can produce all possible vectors (C,) on the last node representation layer. Since every vector ML (L) can be formed as:
* Ac,, diag(e))) E (C:)).
(44)
We can define the degree of those vectors:
deg(A (A k, ( e,) k k deg(e,), (eg((ia)()))))) degge) ML' N). (45)
Then we have the following conclusion:
Lemma E.5. Given two adjacent matrices A and A, k N+, if there's permulation a, V1 sL k, A'1 ~a A",, then
Ve (ele E (I) & k), then e(A) ~o e(A').
Proof. The lemma holds if A²,, since every vectors in ML (C1) can be formed as:
A Ae,, diag(es)e, e, E (L.)
(46)
Notice diag(e;)e; is equivalent to e, O ej. therefore every vectors e E M (C,) can be reformed as:
II (A
(47)
Where k; E N By the definition of degree, degree
I 1)441) max(kili E [], Let h = max(k:li e [1, m]}.
Then Vl S 1 S k A'1 ~a 1 then V1 < S
A (()) = II A 1((())) II i=1
(48)
i=1
Therefore,Ye E fele (C.) deg(e) S k), e(A) ~o e(A'). Thus, we have proved the lemma.
23

---

PRUNING For GNNS: HIGHER EXPRESSIVENESS LOWER COMPLEXITY
Lemma E.6. Given a pair of unlabeled graphs G"), A and A' are their corresponding adjacency matrices, then if there's permutation o, Ve (f)) that deg(e) S k, e(A) ~a e(A"), then the k feature H. ~a H
Proof. Since the pair of unlabeled graphs are unlabeled, their nodes' feature can be represented as 1, hence when k=1, the feature is updated as following:
H' = AMM(11A-11)
(49)
Hence if there's permutation Ve E (c1) that deg(e) $1, e(A) ~o e(A'), then Hgg ~o Har Assume it holds when k = ko, the feature is updated as following:
H M A.H
(50)
Since by assumption if Ve E (Li) that deg(e) S ko, e(A) ~o e(A'), then we have Ha ~a H Notice Ve ML (C1) that deg(e) S kn, (Ae) I Ko +1, hence if Ve E ML' (C₂) that deg(e) I ko 1. e(A) ~a e(A'), then A ~o A Since MLP(WL test) can be regarded apply [f], by remark D.6, Ho ~o H The lemma holds
when k- = ku 1.
Now we can prove theorem 4.1: by lemma E.5 and lemma E.6, to prove GI a wolk WL S GI we only need to prove that (0 < i S S,), there's ' 0g- walk GNN with t layers is able to generate:
When t = L, if a1 # 1 then S = 0, in this case, ag- - walk GNN is able to generate vector 1. if a1 # 1 then S₁ = -1 in this case, 0g. walk GNN is able to generate vector 1 and A1. Hence it theorem 4.1 holds when t1.
Assume 4.1 holds when = lg- Then there's ag- - walk GNN with lg layers is able to generate vector A A'1 Sis Sto) By lemma 4.2, Vj. Sto +1 S j S Sto+1, there's 's subset of N L S {1,... ,t, to + 1}, where to E L, that Elez ai = j. ato+1 S Sto. by assumption, there's ag walk GNN with to layers which is able to generate vector
Since 0- < A R
- 1 1. By eq.7
H MIP(HH + A (roo.
(51)
Hence there's ' ag- walk GNN with to + 1 layers which is able to generate vector A A A A'1. Hence (0 S i S S,), there's ag walk GNN with layers is able to generate, therefore GTt. ag watk WL. S GI have proved theorem 4.1.
WL- Now we
E.5. Proof of Theorem 4.3
Theorem E.7. Given positive integer sequence az, if on is not viewable, then there's 's pair of non-isomorphic graphs (G, G') that G') E GI! walk WL. but (G, G') & GI W.
G
G
Ay -
25,22
65,-
45.
45,
25
46 4
25
Figure 7. (G, G') Gl while (G, G') & GI GI2 walk WL
Given a positive integer sequence an, S, is the length view of az If there's 's positive integer S > Sn, that can be formed as
Exer 0g where is subset of integer set {1, 2, ... nn., observe that the counterexample graphs G and G' in figure 7, both G and G' have 4S, nodes, the edge set of is E(G) = {(i, ( 1)li E [1,45, - 1]] U {4S', - 2, 2)1 U {4S), 2S, - 2)} and the edge set of G' is F(G)- = ((i, + 1))i E 4S,, - 1]} u (455, - 1)) U ((45,,, 25, - 1))}
24

---

PRUNING For GNNS: HIGHER EXPRESSIVENESS LOWER COMPLEXITY
Lemma E.8. GG, E Gl while (G, & Gl
on walk W.'
Proof. We first will prove (G, G') E G Let label (i) denotes the label node i gets at nthh iteration, We define the following permutation a mapping nodes from G to G' such as:
if i e [1,5% (3S, 1.45,
(1)
i+1 S, +1 if i= 3S" -
if i [S, +1,35 -3]
(52)
In this way, we will prove that unravelling tree of node i in G and node (i) in G' at depth S, - 1 are isomorphic:
Let (i, u) be the distance between node u and u, the k-length distance induced graph of graph G, denoted as Gli, k..
whose node set is Via,s) {u V Vidis( u) - k} and edge set is ((,)) {fu, w) E Eldis( (v, u) < k. dis(r, w) - k). Let d; = min (di 45% 1), (i, 4S,)) - 1, then as for node i E [1, 4SS, - 21/( 35, - 1, 355 2, 2,35% - 3) in graph G. i's (S, - Hennghh distance induced graph Gli, S, - 1] is isomorphic to graph H in figure which is -legtt path with an additional node adjacent to one of the nodes in path which is d,-length distant from node i.
As for node (i))s(i E [1,44, 21 35, - 1S 2, 3, - -3) (S, 1)-length distance induced graph in G', G'(o(i), Sa - 1] is isomorphic to Gli,, - -1], therefore their unravelling tree: Unr 5 (i) and Unr St (a(i)) are isomorphic, node and (i) get same label at S th iteration in WL test.
For node i E {S,, 35, - 1,35% - 2, 35 - 3) in graph G, their (S, - 1)-length distance induced graphs: Gli, S - 11, are a 25, -lengh paths, while their corresponding node (il's s (S, 1)-length distance induced graphs are also -5 -lnggh paths, therefore their unravelling tree: Unr (t) and Unr S 1thh iteration in WL test.
S - (a)) are isomorphic, node i and (i) get same label at
For node i e {4S;, - 1, } in graph G. their (S% - 1e--nngth distance induced graphs: Gli, S, - 1], are a 2S, 2- length paths with additional node adjacent to the middle node in path. Also, their corresponding node (i)'s (S, 1)- length distance induced graphs are also are isomorphic to G(i, Sy - 1]. therefore their unravelling tree: Unr 8 (n (i))) are isomorphic, node and (i) get same label at S% - th iteration in WL test.
(i) and
In conclusion, every node: i E (1,4),), i and (i) get same label at Sy th iteration in WL test, therefore (G, Gr since S, < S% - 1, by the definition of WL test we have (G, G') E GI -1
Next we will prove that (G, & G1 woak w in WI test only node S, 35,,, - 1,5,, - 2,, - in graph G and node S,, S, +,, - L, 2 in graph G" gets the same label iteration Sy 1. By theorem 4.1, GI wwalk WL S GI
hence if there's permutation a (from G to G"), then will map 5%, to 5%, Sy 1,,3,, - 3S% 2. On the other hand, node Sh's S' -aalkak neighbor Nwai((s)) (S%) can be decomposed into two parts:N patt (5%) and N (5%)NN path (S%).. while the second part determined by N Wotk (I $ S% 1).. Since S in graph G has the same label as node S,, S +1,+1,33 3S, -...1,.3,,
in graph G², their cardinality of second part IN wark (8,)/N path (S))) are equal, however cardinality of node S 's first part equal to 4: Aypan "paan((")) (S,))- = 4 in graph G, while S S, + 1,
n - 1,35, - 2 equal to 2 in graph G", hence there's 's no node in graph G' get the same label at n'h h iteration in wnlk WL test, hence (') & GI walk WT.
E.6. Proof of Theorem 4.4
Theorem E.9. Given pair of graphs GG) and K E N+, then the expressiveness of pruned K-Path framework is as powerful as K-Path framework. In other word, L E No GIPRK-P= Gik-p
To prove theorem 4.4, we establish a connection with (CI), we now extend the definition of matrix language E (L): let PiK] be the set of k-path matrices as PKK] = (Palk E [0, KT), and vector sentence e( ((P(K) are formed by multiple operation on (K) as follow:
= (X XpH (p.....,,pp))
ep.) (p Epx)
(53)
where {Xi...., Xx} denotes a set of matrix variables from an infinite set, serving as inputs to expressions, and p. denotes the number of inputs required by operation op, Therefore e( (PI)) denotes the comprehensive operation on Pg. For example:
25

---

PRUNING For GNNS: HIGHER EXPRESSIVENESS, LOWER COMPLEXITY
let (P(1)) Po1 + P11 11 then vector sentence el (P(2)) denotes each node's the number of 2-1ength walks. We denote the equivalence between two path matrices set PKK] and Pix) as P(K] (MD)(C)) Pik] iff there's permutation o, Ve E (L)) el (x)) ~ el (x)))
The proof is quite lengthy so we first describe its structure.
(I) First, we prove that PIK] (c) Pik] is equivalent to G = G'.
(2) Second, we find the equivalent matrix language ML (K.1)) for pruned K-Path framework, where M MLFF (L(((K))) equal ML (C1).
(K,K) is
(3) Finally, we prove the equivalent expressive power for matrix language ML & ().1)) and M MT (T.((K.))) therefore K-Path and its pruned frameworks have the same expressive power.
Regarding the connection between matrix language ML' ML'(C,) (C1) and the expressive power of the K-Path framework, we have the following result:
Theorem E.10. PiK] (C)( Pik] + G=E-P G'
Proof. To prove theorem E.10, we will prove any label,, in K-path WL test will has corresponding index vector sentence ((K))) (C3) that (P()) iff node gets label, at 1th iteration.
Let LABEL'- = {label}] be the set of label nodes get at 1th layer in K-path message passing framework's corresponding K- K-tatt WI. test and [LABEL Kt, hence if (ub label; (v;) then node o; and vy will gets the same feature for any I-layers -patth message passing framework. If Vlabel; there's 's corresponding sentence e mC)) that ())
and only if node v gets label! at 1th iteration, then we can prove the theorem
First of all, since every node is not labeled, we denote the expression e (X) :- (X) as nodes' corresponding sentence. Next, when 1 = L. suppose by induction that we can have all label!'s s corresponding sentence e!' (Pix)) we will show that ML (L)(Cs) is able to generate label corresponding index vector sentence e, e (P(r). To this aim, we consider expressions:
(())((())))) Pk ef (PR)) (1 (I m (s.k)
L+1
(54)
L+1 The process of eq.54 is similar to the first equation in eq.6, Vr, E [1, we have m L+1 (r))(r)=(mp)))))) = (i.)) (k) iff (ik))
M.++I. = o M Let D be the set of values occurring in the column vector ((.))) (P()). for i = 1,2, KLL We can compute, by means of an ML (C+) expression, an indicator vector which identifies the rows for M!++1. that hold a specific value e E D.L+1, This expression is similar to the one used in the proof of theorem cite. More precisely, we consider expressions:
f--1
m (1+ (P()) (iceoofii-ezceec))) x
II
d T+1 (Px) -d 1(P(N))) ((pp)) (55) (1.e
CED + #/
for the current iteration L 1 and value oi D. D. Given these expressions, one can now easily obtain an indicator vector identifying all labels in M.++,,, Since m == vector of HL+1A, define the equation as follow:
(141,1)) (P(x) and (PP)) are all 0- - 1 vectors, to have an indicator
(I++1,i,)) m =ott á (PI)) = diag(m (I+11i))) =ot
(PIK)) (ct E D.tL
.J E (1,)
(56)
(Px))() iff in K -ath WL test node e, get label h+t1 R.j (L+1,5,)
Then m =
+ layer for k-path feature. Hence to
have an indicator vector of l we define the equation as follow:
26

---

PRUNING For GNNS: HIGHER EXPRESSIVENESS, LOWER COMPLEXITY
m (1+1)))
soleee (P(K)) =
II
diag(m (Lt1a (Px))) I(Pxi) (ct E Df . E [1.61]).
(57)
=ot
Hence if (1+1,1)
-.. o. (Pk))(r) m (L+1.)
of (P)n)(()) 1 iff node v, and vo get the same label at iteration L + 1.
Hence let WL+1 = (m (1++1,0)
=ol (P(x) E D. D . [1, (1, and KL+1 = |WL+1 then we have already construct
the + 1 layer's the set of vector indicator (1 < i S kL+1). Since every indicator of E (T). if there's
permutation σ, Ve E (L1) e(P(k)) ~o e(P(k)) then vI E N+ and i E Kt. {label( E VJ = (label e V),, therefore G hop G'. Now we have proved the PKK] MM)())) P(k] G = K-pth G'.
To prove P(K] (M))(A)) P(k) +- G KK-pald G',, we can derive the proposition from the proof of theorem 4.1 as following:
Proposition E.11. Ve E M e(P(K) has equivalent form as
e(P(k)) =
II ((LK"
diag ( III kE(L.K]
P p())1)) 1
(58)
Therefore since the pair of unlabeled graphs are unlabeled, their nodes' feature can be represented as 1, hence when I=1, the feature is updated as following:
H MLP(1, Px
(59)
hence if there's permutation a, Ve E (C,) that deg(e) S 1, e(P(K) ~o e(Pix)) then Hy ~a Hy Assume holds when L, the feature is updated as following:
H - H
(60)
since by assumption if Ve E MT (f1) that deg(e) S I,, ((P())) ~a e( e(P'r)), then we have H& ~a Hy. Notice
We (T) that deg(e) S ko, then deg( (x e) S T.+ 1, hence if Ve E MT.) that degle) L 1, el ((A) ~a e(A'),
then Pa H1 No P/- Hy. Since MLP(WL can regarded as apply[f]. by remark D.6, Ha L.lk ~a H HL-L. therefore
H!+ ~o H The proposition holds when
1. now we have proved PiKj (M))(A)) Pix]) + K-poot G'
To understand why this holds, consider the relationship between node configurant configurations and the first layer of message passing. In the first layer of K- K-Hop message passing, each node aggregates information from its 1-path neighbors its K K-path neighbors. Since assume edge features and identical node features across the graph, the GNNs will only consider the local structural information of nodes, which corresponds to P.1(1 encoded into node features and aggregated through different types of neighbors. Hence PKK: =MIA(C)) PiK] implies that all the structural information extracted by the K-Path message passing framework is equivalent, leading G KK-path G'.
K). After the first iteration, all this information is
We now present the equivalence in expressive power between the pruned K-Path framework and the original K-Path framework. By Theorem E. 10, to prove this equivalence, we need to show that G = K K-path G' P(K] =M)"(C.) P(K
Ivan (Jokić & Van Mieghem, 2022) has proved that k-path matrix Ps can generated by La = {,, diag, @), the conclusion can be stated as follow:
Theorem E. (Jokić & Van Mieghem, 2022)). Vk E N+, A is the adjacent matrix in graph G.there's ex E ML)(CA). that e (A) Рy-
By theorem E.10, to prove theorem 4.4, we only need to prove that G =PRK-P G - PIg EMI(())) P(Kj hence we have following conclusion:
27

---

PRUNING For GNNS: HIGHER EXPRESSIVENESS LOWER COMPLEXITY
Lemma E.13. Let Puj and Pkk] be two set of k k-path matrices(1 k S K), if there's 's a set of vector sentences 111,iiag diag) and vector sentence e₁ E (L,) = {.- 1. diag), if there's permutation We' E E (P(() ~o e'(((n) will imply e1((k) Na (x(P(K)) then Vez E (L)) if there's 's permutation
Ei C (c)) = {., ,1,
de E Ei (((P)))_(PP(x)))
(cz(P(x).e( (((((())))) will imply (e2 (P)(())))(((( (ca(Pix)-ex1PP))
Proof. By the condition, there's function f. c1 f(e,,.. ((C), s.c E Ei), hence Vez (L)) 62 e2' f(e,, ,,'),, therefore VPK, PKk. if there's permutation o, Ve' E Ei, (es((())))))) (cx(P(k)) . (P(x)) then (e((Pii))e1(P())) (c
Lemma E.13 for example. since P7-1 P2- + P1-1, hence if there's permutation o, Ps (2-1) ~a (PH-1) and
)
(RI-1)~, 1) hold will imply that (PP-1) (PP.1). hence if there's permutation o, p . 1) (ptt1 1)
and (14 P1- (Pg Pf-1) can deduce that (P4-PP2 1 (Pz (P3
Same as theorem 4.1, We can define the degree of those vectors sentence:
deg(1) = deg( (P. e) = 1 deg(e), deg(diag(es)e))
E Li, E [1, K])
(61)
degSt Pix implies Since by theorem E.10, P and Pkk are the set of k p-path matrices of graph G and G', P(K =2 G hop G", hence to prove the equivalent expressive power of K-hop framework and K-hop refined framework, we only need prove that K-hop refined framework is able to generate any vector sentence e e(P(k)) E ML)
{-, 1, diog) (deg)) S 1).
For K K-hop framework and K-hopp refined framework, we define the multiplicative structure of k-path denoted as F I. (I,,)) with L layers and f-corner crased I t $ K):
k-path-matrices matrices set P(K).
P
P2
Ps
P
Pk
Po
1st layer
P2
P3
P
PK
Po
2nd layer
P3
P
Pк
Po
3th layer
:
:
(62)
P
PK
Po
t layer
: P
: PK
Po
th layer
As 62 shows, when I t, at 1t layer, there are path- path-matrices from 1-path to K K-path with extra 0-path matrix(equal to identity matrix 7). when / 2 at 1thh layer, there are path-matrices from (-path to K K-path with extra 0-path matrix(equal to identity matrix Z).
We define vector sentence e( e(P(x) follow: pick up one arbitrary path matrix at every layer, calculate the product of them, then multiply the result with 1. We denote the set of those vector sentences and the pointwise multiplication of those vector sentences II C (Pir)) in / k.. as ML(F (K.,)). Therefore, given two graph G and G², denote G == =MLFF (x.a)) G", they are equivalent for any sentence in M L (K. (K.,) there's permutation a, c(P(x)) ~a ((P(k))) we can conclude the following proposition from lemma E.13.
Proposition E.14. Ift, K1, E N+, t K1 S K2, then if theorem: for any pair of graph (G, G") G =ML tx G'
holds, then theorem: for any pair of graph (G, G'), G ML(F (xg.)) G' holds.
28

---

: PRUNING For GNNS: HIGHER EXPRESSIVENESS LOWER COMPLEXITY
Since if 1 S 12, then ML k k ML(F R,ty). Hence, suggested below, Proposition E.14 demonstrates that if the equivalence between ML(F (K.))) and ML(F (k,))) (KK,o)) holds for (f1 Σ t2), then the equivalence between ML(F (K+1))))
and LL Lx (K<41.2)) holds:
P1 P2... Ps
Ptz
Pk
Po
Pi Pa
P3
Pt
Pk
Po
1st layer
P2... Pty
Pta ..
Pk Po
P2 P2...
Ps. ....
Psa
PK
Po
2nd layer
:
:
Pta"
Pk
Po
P..
Ptz"
Pk
Po
th layer
: :
:
Pta ... Pk Po
Pra ...
Px
Po
th layer
: :
:
Ps .ta.. Pk Po
P
PK
Po
9 layer
then we can derive from as:
P1 Pr... Pt. ... Pto Pk+1 Po
P1 P2 ... Pr Ps ...
PK+1
Po
1st layer
P2...
Pr. ... P1a ... PK+1 Po
P2
P.
Pt.
PK41
Po
2nd layer
:
:
Pr. ... Pe. ... Pк+1 Po
P ... ... PK+1 Po
&thh layer
:
:
Ph TM Ptz Pк41 Po
Pta ..
PK41 Po
th layer
Pr.
Prz
PK+1 Po
P
PK+1
Po th layer
Now are proving the equivalence between ML(F 1 (K,1)) and ML (F.: ()) We first prove it when K 2, for example.
When L < K - ML( (22)) -M (2.1)). the equivalence holds.
When L + K, the structures of ML L (Kx1)) and ML ( (k.K)) are follow:
P
P2
Po
P
P₂ Po
1 layer
P2
Po
P2
Po
2nd layer
P1
P2
Po
Pa
Po
1h layer
Since Pf- P2 + Pt, hence Vi E N+, P(1,
descend order of Pi by replacing Pł with Pa + Pt, hence Pf is
determined by P/ .P 1 and P/1 (0 < 1 1],0 j2 [)] Therefore Vi,, in E N P 1o is is determined
by p'a+11 P and p (0 i - 1|.0 1 j2 - 1). On the other hand, è f1 +1 & ig + ④ - -1]+1 i +12,
i2 + < 12 + 1 < i + iz, Which means VL E N E M (2.))), there's subset E, S ML( L (2.2))
that vector
sentence e is determined by Eg, now we have proved the equivalence between ML(FL (2)) and ML(FL. (F(2))))
29

---

PRUNING For GNNS: HIGHER EXPRESSIVENESS LOWER COMPLEXITY
Now assume the equivalence between M ML(F(R.A (R.K-1)) and ( L (k, holds when A: s K. Therefore, by proposition E.14, the equivalence between ML(F (ML(F(KHI,K (K+1,--)) and ML(F (M(((K+1,K)) (K+1,K)) holds. Hence we only need to prove the equivalence between M L( L (k+1,K)) and ML (K+1,K+1)). Let e be a sentence, and ((e(P())) denotes the corresponding walk to e(P1)),, for example, if e((1a)) = P2. then ((((P))))) denotes all the 2-1ength path in graph. We first consider w w(Pk)/ w(PK+I- -aai-Px-il PK-1): (PP)) (R)//(((Px// (PK is the subset of 2K -lenth walks in graph but the K + 1 node is recurring in the walk sequence, hence the number of these walks from every node is determined by Pk P.(( S i i K 1), in the same way w(Pk+1 Px-1)//((PPP
is the subset of 2K Kleeength walks in graph but the K + 2th node is recurring in the walk sequence, hence the number of these walks from every node is determined by PK+1 P3 S S K 2). Therefore Pk is determined by Px P; and Pk+1 P31 < i K - 1), which means that there's subset E(rg 1) C ML ( (K+L,K+)) that vector sentence P is determined by ()
Now we are able to prove the equivalence between ML (F(((K4).)) (K)),K)) and ML(F (F (K+1,K4))
P1 P2...
PK
PK+1 Po
P P2... Pk Pk+1 Po
1st layer
P2...
PK
PK+1 Po
PB... PK
Pk+1
Po
2nd layer
: :
:
Pk PK+1 Po
Pk Pk+1
Po
T layer
Pk
PK+1 Po
PK+1
Po
K + 1 layer
: :
:
Pk
Pk+1 Po
Px+1
Po
th layer
e
I (Ky but & F I (K+11,4+1-- then
P is not in e: let i equal the order of PK+1 in and epxi1 be with pig-1 erased. Then ep E (K,K-1)' by L-ix
L-ix-1
assumption, eP is determined by (K.K)
L-iK since Pk is not in e, K+1 epx-1 is determined by (K+1,++1)'
piga1
Pk is in let P ee' = since P 1 is determined by PxP. and PR+ P.1 < <iski K --1), 1), we are able to descend the order of Pk, until P is not in, therefore e are determined by the subset of F (K+1,K) where PR is not in every vector sentence, from the conclusion above those vector sentences are determined by / L proved the equivalence between ML(F (K)1,K) and ML
(K-1,K+1)* therefore we have
(T((F (K+41K4+))-
Therefore, we can prove the equivalence between ML L. (K<+1.)) and ML(F L (K+1,44)): since Vk N+, ML (R.R-I) and MLF ()) are equivalent, hence by proposition E.14 ML I. (R))-1) and ML(F (K,)) (1 k K) equivalent, hence the expressive power of M L(F (k..)) and LL L (1 S k < K) are equivalent.
Now that we can prove theorem 4.4: by theorem E.10, PIKT FML(FR k)) PiKj ++ G=K-P G' while PIK EMLLF (x..) PKK + G =PRK-P G.. We already obtain the conclusion that the expressive power of ML(I (x.1)) and ML(F (T((FK.)) (( < k < K) are equivalent, hence we have G =K-P G + G =PRK-P G', indicating T. E N+ GIP -p we have proved the expressiveness of pruned K-Path framework as powerful K-Path frame- work.
E.7. Proof of Theorem 4.5
Theorem E.15. VL, K E N (RG (RGnGIkR2-n)) n)) S (RG GI n) and (SRG GIk =-)) S (SRG GIk n).
To prove theorem 4.5, we connect its equivalence with matrix language. We establish a connection with (C1),,, let us denote the of k-hop matrices as O[K] = {O&lk E [0, K]]. We then arrive at the following conclusion:
30

---

PRUNING For GNNS: HIGHER EXPRESSIVENESS, LOWER COMPLEXITY
Theorem E.16. [KK] (M)) OiK ++ G GK--Hop G'
To proof if theorem E.16 is same as theorem E.10, just replace PIK] with Ojx). Given a pair of regular graphs (G, OJK] and O [K) are their K' hop matrices set, by theorem E.16, if 2-hop WL test decides that they are isomorphic, then O12 (C) O12)- Since (G) are regular graphs, each node's number of neighbors is equal, hence Vi N+
0f1 = IT- IT- (O,1,,), so 0 is decided by 11 Hence if c(Opp) & (F (2.2)): then p())) is formed the pointwise multiplication of vector O O 1(1 + S L), which is determined by 0,1 and 0 since O,1, O E ML(I (2.2)) hence if G¹) is a pair of regular graphs, then O/2 =ML (a.))) 0/2 + 0 MMrr (a.)) %/8
Before prove the the equivalence of OΙK] between L [K (k+) and ( ( (x+1,K+1)) on strong regular graph, we first start with a lemma:
Lemma E.17. Let G be an (n, r, a, c) strongly regular graph, if = O, then G is isomorphic to mK,+1 for some m + 2(Kr Complete graph with nodes).
Proof. If O, then any two neighbours of a vertex v must be adjacent, and so a = r 1, hence the component containing any vertex must be a complete graph Kr+1 1 and hence G is disjoint union of complete graphs.
Since SRG c RG, can derive the equivalence of O1g) between ML [ (K+1.a) and ML (TL(Ft+L.K44)) (K+1.44)) from the conclusion above, now we prove the equivalence of Op3) between (L L (K+1.1)) and (L (E(FF)xnn (K+1,K+1)): for each node r's s 2-hop neighbor Nhop if u E Nhop then u and v have c common neighbors, henee for every v's 2-hop neighbor node u, there are e paths from o to u. Hence c021 = P21 = Pf1 P11 = r(r 11)1 (P,l- @ 1,
Next we consider the walks in w (PP), if e and u have a walk in wP3)) then e and u cannot be adjacent, hence P31 = P21 @ P21, therefore P21 is determined by P.1, hence if e(O & (F (3.3)), then e(0(2) is formed as the pointwise multiplication of vector 0f O 1(1 + 12 + is S D), which is determined by O,1, O21 1 and O since 0,1, 021, 0 E ML (IL(((a.). (3.3)), hence if (G, G') is pair of regular graphs, then 0l =MLO (3.a)) %2) OpT = ML(F (a.))) Oe8
Now we prove the equivalence of Ojx] between ML L (K (K+1,1) and ML L. (K (K+) when K * 4: if 031 + 0, then there is nodes e and u, e and u do not have common neighbor, hence c = 0, therefore by E. graph G is isomorphic to mK,+1, since K- K-hop pruned WL test able to output n and r, hence K K-hop pruned WL test will decide (G, G') are
isomorphic iff they are isomorphic to mK (m+ + 2).
On the other hand, if O31 0, then vk E N+, K + 3, 0₂1 0, hence the output of K-hop WL test and K-hop pruned WL test for (G, G') are the same, now we have proved the theorem.
E.8. Detail of GNNs Redundant Structure Task
For MP-GNN M, the 4 parameter configurations of M which is competent for the task is listed as follow:
configurations
configurations 2
configurations 3
configurations 4
H = o H + Σ H
H! = a H + h
H. = o H + H
H = > HD) H = a H HD
2 a H + > H
H² = a ( H H
H o > H
H = o (H + Σ H
Ha = = H
H H H
Hº = a -
For pruned MP-GNN M', the 2 parameter configurations of M' which is competent for the task is listed as follow:
configurations
configurations 2
H. = a (H) +Σ H.) H = H + +Σ
H a ( + H = =
We now prove that those 6 models are competent for the task: It is obvious for both models the configurations I is competent for the task. We will categorize the conditions to discuss the rest configurations can also accomplish the task.
31

---

PRUNING For GNNS: HIGHER EXPRESSIVENESS, LOWER COMPLEXITY
(I) u is marked: for MP-GNN, since graph is connected with at least 3 nodes, node has at least one 2-hop neighbor u. its H., will be equal to in two iterations such that W A O, therefore H3 1. As for pruned MP-GNN, since H. 1,
H = (A²)). = 1.
(2) u's 1-hop neighbor u is marked: its Hu will be equal to I in two iterations that W| * 0, therefore H = 1. As for pruned MP-GNN, we have H = 1, hence H = 1.
(3) o's 2-hop neighbor u is marked: its H., will be equal to in two iterations that W1- = and W 1, therefore H& 1.
As for pruned MP-GNN, we have H 1, hence H² 1.
(3) v's s 3-hop neighbor is marked: it's obvious since for both model will gather 3-hop- distance node information.
Now that if task outputs 1, iff at least one situation happens, therefore the rest configurations can also accomplish the task.
F. Time and Space Complexity
In this section, we discuss more about the time and space complexity of MP, K-Path, K-Hop and their pruned frameworks, We suppose graph has n nodes, every framework is designed to gather node's information at distance of L, (n >> L > K).
Message Passing Framework:
For WL DestMPP-GNN) to gather node's information at a distance of L, we need set the number of layers equal to L, hence the space complexity is O(nL) and time complexity is O(n- L). As for pruned WL test(pruned MP-GNN), to gather node's s information at distance of L, we only need set the number of layers at most [log(L)] + 1, hence the space complexity is O(n- lo)(L)) and time complexity O(n- lo)(
K-Path Framework: For K- K-path WL test (K-Path GNN) to gather node's information at distance of L,, we need set the number of layers equal to k. at every layer, K-path WL aggregate from 1-Path neighbor to K K-Path neighbor, therefore the space complexity and time complexity for per layer are O(n- K) O(n-K) the space complexity and time complexity for whole model are (n L) and O(n- L). As for pruned K-Path WL test (pruned K-Path GNN), the number of layers is set K too. Since (n >>>>>>> I. >>>> K), at most layers, the architecture of pruned K-Path WL test is same as WL. test, the space complexity and time complexity for whole model are O(n- k) and ( k)
equal to &
K-Hop Framework:
Same as K-Path Framework, at every layer, K-Hop WL aggregate from 1-Path neighbor to K-Path neighbor, the space complexity and time complexity for whole model are On--)) and Onn L). For pruned K K-Hop WL test (pruned K K-Hop GNN), the space complexity and time complexity for whole model are (n k) and O(n k)
G. Consistency of Expressiveness for Pruned WL Test
To verify the expressive power equivalence between the pruned k-path WL. the WL test and their original algorithms, while for K-Hop WL. WHETHER loses information about non shoresst paths is critical. We conducted experiments on both real-world and synthetic datasets. For graph tasks, we perform the original WI. test on each graph to assign a classification label to every node. Subsequently, we execute the pruned WL test on the same graph. If the pruned WL test produces the same number of node classes as the original WL test(HCC = [[CrrwLH
m), and there exists mapping f: [m]] + [m]] between the classes that Hvlx(v) E CWD. = Holx(v) E OPRWLHl, then we conclude that the pruned WL test is consistent with the original WL test on that graph. we execute both the original and pruned WL tests on each individual graph for node-level tasks. The WI. Test algorithm applies the hashed and power iterated color refinement algorithm proposed by Kersting (Kersting et al., 2014), and others are derived from it. T(-) denotes the prime number function(T((i the 7th prime), in multiple aggregations WL test we assign different primes into different aggregation (a (T(( - I) ()(((--)) k 1)).
This avoids hash collision since if k is different (T((K- - I) ((t()) + k- 1)) will be different. The algorithm is as follow:
G.1. Real-World
As shown in Table 9, we conducted comparative experiments between WL and pruned WL on real-world datasets, Acc denotes the proportion that the pruned variant output coincides with original WL test. Time(s) denotes the time of cost, and Aver denotes the average number of classes that algorithms assign to node in graph.
32

---

PRUNING For GNNS: HIGHER EXPRESSIVENESS, LOWER COMPLEXITY
Algorithm 8 HCGCR: Hashed CGCR(WL Test Algorithm)
Input: Adjucency matrix A, number of iteration
2: Output: Nodes corresponding class C(L), number of class m (L)
3: Initialization: C(O) 1, m0
4: for -= 1 to L do
5: C < unique (aiique(C(l1)) + Alog(T(C((-1))
6: m + ))
7: end for
Algorithm Pseudocode for the Pruned WI. Test Algorithm
1: Input: Adjacency matrix A, number of aggregations of each iteration T, number of aggregation for each iteration
2: Output: Nodes corresponding class C(4), number of class mL()
3: Initialization: (1(D) 1, (") 1
4: Io 1 to L do
5: Co c(1-1) log(T(((U-)))
6: for = T do
c(-1)) - c(!-!))
7:
8:
end for
C + unique CrT")
9:
10: m max(C())
11: end for
Algorithm 10 Pseudocode for the K-HoopPPth) WI. Test Algorithm
1: Input: k-HoppPath) Adjacency matrix A&(k E [K], number iteration
2: Output: Nodes corresponding class C(1), number of class (L)
3: Initialization: C(() < 1, (0) +
4: for := to L do
5: for k (1-1)) + Ak- log(T((( - 1) 1)(((1))) + k-1))
to K do
6:
k
7: end for
8: C + UCU EnE[K] ((-11))
9: m ma)(
10: end for
Algorithm 11 Pseudocode for the Pruned K K-Hop(Path) WL Test Algorithm
1: Input:K,, k-Hop(Path) Adjacency matrix A& E []), number iteration
2: Output: Nodes corresponding class C(L), number of class (L)
Initialization: (()) < 1, (0)
4: for - 1 to T. do
5: i K then
6:
7:
for k= to K do
c(l-1) + A log(a((K - 1). C(I-)) + +k)1)) (()) unique (0l- EkE(UKK] cll-1))
8:
9:
10:
end for
11: else
(!--)) + Ax (Cg(T(((-1)))
12:
13: (t)) CCique + c(l-1))
end if
15: () max(((1)
16:
end for
33

---

PRUNING For GNNS: HIGHER EXPRESSIVENESS, LOWER COMPLEXITY
Table 9. Pruned WT. Test real-world dataset.
MUTAG
PTC
NCII
PROTEINS
Model
Acc
Time
Aver
Acc
Time
Aver
Acc
Time
Aver
Acc
Time
Aver
WI
1,522
11.196
4,265
11.069
139.715
19.227
98.185
31.622
PRWLEI
100%
0.557
11.196
100%
1.328
11.069
100%
31,207
19.227
100%
11.340
31.622
WIG.
14.644
14.739
31.912
15.075
631.695
40.376
363.649
37.286
PRWIG1
98.9%
3,454
14.771
100%
8.624
15.075
99.5%
145.192
40.319
100%
127.640
37.286
WIG.
25.536
14.803
77.879
15.392
916.559
48,259
779.075
41,966
PRWI.C1
98.9%
7.134
14.795
100%
20.049
15.392
99.5%
191.903
48.452
100%
178.697
41 11.986
K- H.p
2.175
16,161
6.093
13.394
199.593
44,995
166.914
41 41,015
PR2 Hop
100%
1.903
16.161
100%
5.331
13.394
100%
174.644
44.995
100%
147.712
41,015
2 --
10.976
17.077
30.845
16.150
295.2.3
$1.155
290,919
43.174
PR2 Hogfs1
100%
10.192
17.077
100%
28.642
16.150
100%
274.148
51.155
100%
276.373
43.174
G.th
2.240
16.324
6.275
13.529
205.581
45.449
171.922
41,429
100%
100%
100%
100%
PR2 Poth..
1.960
16.324
5.491
13.529
179.883
45,449
152.143
41.429
2- Path
11.306
17.249
31.770
16.314
304.093
51.672
299.646
43.610
100%
100%
100%
100%
PR2 G.1
10.498
17.249
29.501
16.314
282.372
51.672
284.664
43.610
The parameter settings for the number of layers are configured as follows()WLLLMPGGNNY: layers,7 layers and 10 lay- ers.
livers, (12, 1..2.3.4llayerrs (oop KK225 layers.(4)Prune) K K-Hop: K=2,3 K=2, (5)ers.(5)K-Pattt K=2,3 layers, (6) K-Path: K=2,3 layers,K=2, layers.
G.2. Synthetic
As shown in Table 10, we conducted comparative experiments between WL and pruned WL on Synthetic datasets for node-level, Equi denotes the whether the pruned variant output coincides with original WL test. Time denotes the time of cost, and class denotes the number of classes that algorithms assign to node in graph. Every graph has 200 nodes, and RANDOM is a random graph with edge generated probability 0.01, based on the principle of preferential attachment gich-get-richer effect) with edge generated probability 0.01, and 3-Random Regular is a regular graph where each node has 3 degrees.
The experimental results lead us to the following conclusions: The pruned algorithm almost perfectly matches the original algorithm, the few mismatches occur because CUDA operations on high-precision data introduce computational errors, leading the algorithm to (with low probability) classify WL-equivalent nodes into different categories. (2)The complexity of pruned algorithm is stricly reduced, especially for pruned WL algorithm. layers, the K-Path method yields more class number than K-Hop. This aligns with the fact that K-Hop pruning loses information about non-shortest paths. (4)Under the condition of aggregating identical distances greater than K, the pruned K-Hop/Path WL demonstrates stronger expressive power than WL. (classifying nodes into more categories) while requiring less computation time than W5yhe pruned 2-Hop achieves complete expressive equivalence with the original algorithm, demonstrating that pruned K- K-Hop can be considered approximately equal to standard K-Hop in terms of expressive power.
the same K value and number of
G.3. Ablation on Complexity
Table 11 presents a comparison between the pruned and original models in terms of training time, where Acc denotes model accuracy and Time represents the duration required for one training iteration. Table 12 demonstrate the comparison between total training time and aggregation time, where the aggregation time accounts for a relatively small proportion of the total time. The pruned models achieve comparable accuracy to the original model, while most pruned variants demonstrate better training efficiency than the baseline.
34

---

PRUNING For GNNS: HIGHER EXPRESSIVENESS, LOWER COMPLEXITY
Table 10. Synthetic Data
RANDOM
Barabási-Albert
3-Random Regular
Model
Equi
Time (s)
class
Equi
Time (s)
class
Equi
Time (s)
class
WL
0.468
121
0.515
130
0.015
V
PRWLG.
0.026
121
0.028
130
0.014
1
WLG.
3.585
145
3.934
155
0.034
/
PRWLG.
0.721
145
0.794
155
0.030
1
WLG.
7.327
153
8.009
163
0.051
/
PRWIGA
1.878
153
2.064
163
0.046
K- -Hopp
0.585
141
0.644
151
0.380
12
V
PR2 - Hop G.1
0.568
141
0.625
151
0.369
12
2- G-Hop
2.868
153
3.149
163
0.837
23
v
V
PR 2-Hop 5
2.940
153
3.228
163
0.812
23
P.t
0.591
141
0.651
151
0.384
15
V
PR2 Path G.I
0.574
141
0.631
151
0.373
15
2 - P.P
2.894
153
3.178
163
0.846
26
V
PR2 P.1
10.498
153
3.257
163
0.820
26
Table 11. Comparison training efficiency
COLLAB
NCII
IMDB-B
IMDB-M
MUTAG
PROTEINS
Model
Time
Ace (%)
Time
Acc (%)
Time
Acc (%)
Time
Acc (%)
Time
Acc (%)
Time
Acc (%)
GIN(3)
1.104
0.480
71.9 + 0.5
0.251
71.9 0.3
0.304
49.9
0.889
89.4 0.4
0.268
73.7
PR GIN(1)
1.060
0.461
72.9 +
0.209
69.9
2.0
0.284
0.886
88.5
0.233
72.2
GIN(7)
1.638
77.4 +: 1.6
0.748
71.5 +: 1.4
0.578
72.6
0.3
0.534
51.1 + 0.3
0.904
89.4 = 1.0
0.527
76.3 1 0.2
PR GIN(124)
1.284
76.4 - 0.7
0.6961
75.4 + 0.2
0.481
71.7 + 1.4
0.464
52.0 + 0.5
0,916
92.0 = 0.4
0,425
74.1 1:1:::1 1.0
GIN(10)
2,142
74.7 + 0.6
1.122
75.9 +: 1.3
0.948
72.1 + 2.8
0.898
49.7 + 1.5
0.874
87.7 = 0.2
0.867
72.3 1 0.0
PR GIN(1234)
1.689
75.6 + 0.3
0,981
74.7 + 0.2
0.710
71.5 0.5
0.780
51.2 + 0.9
0.929
90.7 = 2.1
0.667
72.5 2.2
2-Hop(3)
1.357
76.8
0.608
0.9 76.5
0.410
71.0
0.415
50.1
0.910
0.394
69.5 1.3
PR H-H))(3)
1.180
75.1
0.528
0.357
71.5 0.5
0.361
52.5
0.929
91.3
0.342
73.3 0.3
2-Hop(S)
1.927
74.2 + 0.5
0.880
70.6 + 1.7
0.680
68.8
0.8
0.628
49.5 + 0.6
0.894
88.3 = 1.0
0.621
71.0 -1.08....
PR 2-Hop((5)
1.606
74.5 + 0.4
0.734
71.1 +: 1.5
0.566
69.7 1: 0.2
0.523
48.0 +: 2.2
0.871
88.7 = 1.5
0.517
72.0 -1 0.3
2-Path(3)
1,385
75.6
+ 0.0
0,620
73.0 0.8
0.418
71.4 0.1
0.423
49.5 + 1.8
0.9045
88.7 = 1.7
0.402
72.7 2.0
PR 2-Path(3)
1,385
76.1 0.3
0.632
75.5 4 0.4
0.488
74.2
0.451
51.6 - 0.4
0.915
91.6 = 0.0
0.446
76.9 : 0.7
2-Path(S)
2.111
76.0
0.964
0.3
0.745
70.0 0.6
0.688
51.3 0.1
0.890
89.4 0.4
0.680
69.3 1.0
PR 2-Path(5)
1.730
72.1
0.790
70.5 + 2.3
0.610
71.8 1.5
0.564
50.2 +
0.898
88.9 0.8
0.557
71.9 2.4
35

---

PRUNING For GNNS: HIGHER EXPRESSIVENESS, LOWER COMPLEXITY
Table 12. Comparison on aggregation time
COLLAB
NCII
IMDB-B
IMDB-M
MUTAG
PROTEINS
Model
Time
Agg. Time
Time
Agg. Time
Time
Agg. Time
Time
Agg. Time
Time
Agg. Time
Time
Agg. Time
GIN(3)
1.104
0.091
0.480
0.033
0.251
0.017
0.304
0.021
0.889
0.063
0.268
0.018
PR GIN(12)
1,060
0.087
0,461
0.032
0.209
0.014
0.284
0.020
0.886
0.062
0,233
0.016
GlN(7)
1.638
0.143
0.748
0.052
0.578
0,040
0.534
0.037
0.904
0.064
0.527
0.037
PR GIN(124)
1.284
0.133
0.6961
0.049
0.481
0.033
0.464
0.032
0.916
0.065
0.425
0.029
GIN(10)
2.142
0.215
1.122
0.079
0.948
0.067
0.898
0.063
0.874
0.062
0.867
0.061
PR GIN(1234)
1.689
0.188
0,981
0.069
0.710
0.050
0.780
0.055
0,929
0.065
0.667
0.047
2-Hop(3)
1.357
0.116
0.608
0.042
0.410
0.028
0.415
0.029
0.910
0.064
0.394
0.027
PR H-H))33)
1,180
0.1
0.528
0.037
0.357
0.025
0.361
0.025
0.929
0.065
0.342
0.024
2-Hop(5)
1.927
0.168
0.880
0.062
0.680
0.048
0.628
0.044
0.894
0.063
0.621
0.043
PR 2-Hop(5)
1.606
0.14
0.734
0.051
0.566
0.040
0.523
0.036
0.871
0.061
0.517
0.036
2-Path(3)
1,385
0.118
0.620
0.043
0.418
0.029
0.423
0.029
0.9045
0.064
0.402
0.028
PR 2-Path(3)
1,385
0.12
0.632
0.044
0.488
0.034
0.451
0.031
0,915
0.064
0.446
0.031
2-Path(5)
2.111
0.185
0.964
0.068
0.745
0.052
0.688
0.048
0.890
0.063
0.680
0.048
PR 2-Path(5)
1.730
0.151
0.790
0.055
0.610
0.043
0.564
0.039
0.898
0.063
0.557
0.039
36


Reviews:
[{"review_id": "UnPrMBIWGy", "reviewer": "Reviewer_hERx", "summary": "This paper proposes pruned versions of Message Passing GNNs, K-Hop GNNs, and K-Path GNNs by eliminating redundant structures. The authors claim that these pruned frameworks maintain or even improve expressive power while reducing computational complexity. Theoretical analysis based on matrix language is used to demonstrate equivalence in expressiveness between the pruned and original frameworks. Additionally, experimental results on benchmark datasets show that pruned GNNs achieve comparable or better performance with improved efficiency.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer hERx careful evaluation and meaningful suggestions.\n\nQ1:The methodology is theoretically sound in using matrix language tools to analyze expressiveness. However, the evaluation mainly focuses on standard benchmark datasets without strong ablation studies or comparisons with more sophisticated recent baselines.\n\nTo verify the expressive power equivalence between the pruned WL test and their original algorithms, We have added experiments to verify the consistency of the expressive power between the pruned architecture and the original algorithm on both real and synthetic datasets. The experimental results show that the expressive power of the pruned architecture is almost identical to that of the original algorithm.\n\nAdditionally, we have evaluated the efficiency improvements of the pruned architecture compared to the original architecture in the WL algorithm and as a GNN model. The results show that under the WL algorithm, the pruned architecture maintains the same expressive power as the original algorithm while significantly reducing computation time. As for GNN, We compared the pruned model in terms of accuracy and training time, and the results show that the pruned models achieve comparable accuracy to the original model, while most pruned variants demonstrate better training efficiency than the baseline. Some of the results are shown below.\n\n| Model         | COLLAB Time   |COLLAB Acc (%) | NCI1 Time   | NCI1 Acc (%) | IMDB-B Time   | IMDB-B Acc (%) | IMDB-M Time   | IMDB-M Acc (%) | MUTAG Time   | MUTAG Acc (%) |  PROTEINS Time   | PROTEINS Acc (%) |\n|---------------|--------|---------|--------|---------|--------|---------|--------|---------|--------|---------|--------|---------|\n| GIN(3)        | 1.104  | 74.8 ± 1.3 | 0.480  | 71.9 ± 0.5 | 0.251  | 71.9 ± 0.3 | 0.304  | 49.9 ± 0.0 | 0.889  | 89.4 ± 0.4 | 0.268  | 73.7 ± 0.7 |\n| PR GIN(1)    | 1.060  | 73.9 ± 0.0 | 0.461  | 72.9 ± 1.4 | 0.209  | 69.9 ± 2.0 | 0.284  | 50.6 ± 0.3 | 0.886  | 88.5 ± 0.0 | 0.233  | 72.2 ± 1.9 |\n| GIN(7)        | 1.638  | 77.4 ± 1.6 | 0.748  | 71.5 ± 1.4 | 0.578  | 72.6 ± 0.3 | 0.534  | 51.1 ± 0.3 | 0.904  | 89.4 ± 1.0 | 0.527  | 76.3 ± 0.2 |\n| PR GIN(124)  | 1.284  | 76.4 ± 0.7 | 0.6961 | 75.4 ± 0.2 | 0.481  | 71.7 ± 1.4 | 0.464  | 52.0 ± 0.5 | 0.916  | 92.0 ± 0.4 | 0.425  | 74.1 ± 1.0 |\n| GIN(10)       | 2.142  | 74.7 ± 0.6 | 1.122  | 75.9 ± 1.3 | 0.948  | 72.1 ± 2.8 | 0.898  | 49.7 ± 1.5 | 0.874  | 87.7 ± 0.2 | 0.867  | 72.3 ± 0.0 |\n| PR GIN(1234) | 1.689  | 75.6 ± 0.3 | 0.981  | 74.7 ± 0.2 | 0.710  | 71.5 ± 0.5 | 0.780  | 51.2 ± 0.9 | 0.929  | 90.7 ± 2.1 | 0.667  | 72.5 ± 2.2 |\n| 2-Hop(3)    | 1.357  | 76.8 ± 0.8 | 0.608  | 73.6 ± 0.9 | 0.410  | 71.0 ± 0.7 | 0.415  | 50.1 ± 1.5 | 0.910  | 91.0 ± 0.0 | 0.394  | 69.5 ± 1.3 |\n| PR 2-Hop(3) | 1.180  | 75.1 ± 1.1 | 0.528  | 76.5 ± 1.6 | 0.357  | 71.5 ± 0.5 | 0.361  | 52.5 ± 0.7 | 0.929  | 91.3 ± 1.5 | 0.342  | 73.3 ± 0.3 |\n| 2-Hop(5)    | 1.927  | 74.2 ± 0.5 | 0.880  | 70.6 ± 1.7 | 0.680  | 68.8 ± 0.8 | 0.628  | 49.5 ± 0.6 | 0.894  | 88.3 ± 1.0 | 0.621  | 71.0 ± 0.8 |\n| PR 2-Hop(5) | 1.606  | 74.5 ± 0.4 | 0.734  | 71.1 ± 1.5 | 0.566  | 69.7 ± 0.2 | 0.523  | 48.0 ± 2.2 | 0.871  | 88.7 ± 1.5 | 0.517  | 72.0 ± 0.3 |\n| 2-Path(3)    | 1.385  | 75.6 ± 0.0 | 0.620  | 73.0 ± 0.8 | 0.418  | 71.4 ± 0.1 | 0.423  | 49.5 ± 1.8 | 0.9045 | 88.7 ± 1.7 | 0.402  | 72.7 ± 2.0 |\n| PR 2-Path(3) | 1.385  | 76.1 ± 0.3 | 0.632  | 75.5 ± 0.4 | 0.488  | 74.2 ± 1.9 | 0.451  | 51.6 ± 0.4 | 0.915  | 91.6 ± 0.0 | 0.446  | 76.9 ± 0.7 |\n\nQ2:The experimental setup evaluates pruned GNNs on several benchmark datasets. However, the improvements in efficiency are marginal, and the comparisons do not convincingly demonstrate practical benefits over existing optimized GNN models. I do not think the TUdatasets are enough to evaluate the method. The authors should consider OGB datasets for evaluations.\n\nAfter we made appropriate improvements to the models to make them suitable for large-scale graphs, we conducted large-scale graph experiments on dataset ogb-arvix for GIN, Pruned GIN, and Pruned multiple aggregation GIN, the results show that  while maintaining comparable accuracy to the original model, the pruned version achieves significant reductions in both parameter count and training duration, showing noticeable efficiency improvements. Some of the results are shown below.\n\n|Model|Test Accuracy|Val Accuracy|Parameter |Total time|\n|----------|----------|----------|----------|----------|\n|GIN|0.7012 $\\pm$ 0.0114|0.7132$\\pm$0.0023|2.29M |2.23h|\n|Pruned GIN |0.6905 $\\pm$ 0.0241|0.7231$\\pm$0.0041|0.98M |1.52h||\n|Pruned 2-Mul GIN|0.7121 $\\pm$ 0.0092|0.7341$\\pm$0.0066|1.14M |1.73h|\n\nAnd all the experimental materials(code) and results in provided in https://anonymous.4open.science/r/PrunedGNN-AC61/README.md", "claims_and_evidence": "The paper claims that pruning redundant structures in MP-GNNs, K-Hop GNNs, and K-Path GNNs maintains expressiveness while reducing complexity. While some theoretical arguments support this claim, the practical significance is not well justified.", "methods_and_evaluation_criteria": "The methodology is theoretically sound in using matrix language tools to analyze expressiveness. However, the evaluation mainly focuses on standard benchmark datasets without strong ablation studies or comparisons with more sophisticated recent baselines.", "theoretical_claims": "The theoretical analysis claims that pruned GNNs maintain the expressive power of the original architectures.", "experimental_designs_or_analyses": "The experimental setup evaluates pruned GNNs on several benchmark datasets. However, the improvements in efficiency are marginal, and the comparisons do not convincingly demonstrate practical benefits over existing optimized GNN models. I do not think the TUdatasets are enough to evaluate the method. The authors should consider OGB datasets for evaluations.", "relation_to_broader_scientific_literature": "It improves the expressiveness of GNNs (broader literature) while reducing complexity.", "essential_references_not_discussed": "No significant gaps found.", "other_strengths_and_weaknesses": "The theoretical analysis provides an interesting perspective on expressiveness equivalence. But the empirical evaluations are limited.", "other_comments_or_suggestions": "Consider adding experiments on larger, real-world datasets to better illustrate the efficiency gains.", "questions_for_authors": "Have you tested the approach on large-scale graphs where efficiency improvements might be more noticeable?", "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": "PYBMgbazPr", "reviewer": "Reviewer_V1ZW", "summary": "The paper proposes a pruning framework for GNNs aimed at improving computational efficiency while maintaining or even enhancing expressive power. The authors introduce pruned versions of Message Passing GNNs (MP-GNNs), K-Path GNNs, and K-Hop GNNs by identifying and removing redundant structures. Theoretical analysis using MATLANG demonstrates that pruned versions retain the expressive power of their unpruned counterparts, and experiments on multiple datasets validate the efficiency gains. The main contributions include:\n\n- A theoretical justification for pruning in GNNs without sacrificing expressive power.\n- A pruned message passing framework that maintains equivalent expressiveness while reducing complexity.\n- Empirical validation showing that pruned frameworks outperform or match unpruned models across benchmark datasets with lower computational cost.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely acknowledge reviewer V1ZW for the constructive criticism and insightful suggestions.\n\nQuestions For Authors:\n\n Q1: Unfortulately, we have to admit that find a pair of graphs that pruned K-Hop fails to distinguish graphs and the original K-Hop framework can differentiate involves a tremendous amount of algebraic analytic work. Since the proof of the theorem of the existance of a pair of graphs distinguishable by the (k+1)-dimensional Weisfeiler-Lehman ((k+1)-WL) test but not by the k-dimensional Weisfeiler-Lehman (k-WL) test spans 58 pages. However, even if it exists, we can draw the conclusion that the probability for inconsistent expressiveness between K-Hop and  pruned K-Hop goes to 0 as the size of graphs n goes to infinity. As shown in the respond to Q2, we also conducted experiments on this issue real-world and synthetic datasets, all of the results show that they have same expressiveness. \n\nQ2: We have added experiments to verify the consistency of the expressive power between the pruned architecture and the original algorithm on both real and synthetic datasets. The experimental results show that the expressive power of the pruned architecture is identical to that of the original algorithm. We also conducted ablation experiments for GNNs, result shows the pruned version achieves significant reductions in both parameter count and training duration, showing noticeable efficiency improvements.\n\nWe have supplemented ablation experiments analyzing the impact of different pruning strategies on model efficiency and accuracy.\nWe summarize the core conclusion:(1)Regarding to the expressiveness(Graph Isomorphism WL test), all identified redundant structures should be removed since it will enhance efficiency.(2)When it comes to the performances(accuracy), sometimes retaining certain redundant structures can slightly improve the model's accuracy. The reason is that if all identified redundant structures are removed, the subsequent layers will need to aggregate a large amount of representations. Since MLP are not strict hash functions, this can degrade the model's performance.\n\nAs for pruning strategies for MP-GNNs, we point out that the sequence $a_l$ can be flexibly adjusted, as long as $a_l$ is viewable(The subset's sum of {$a_l$} is dense in $[S_l]$), such as geometric sequence($a_l=l$) or fibonacci sequence($a_l=a_{l-1}+a_{l-2}$), then it have same expressiveness as MP-GNN. \n\nQ3:We have tested how pruning affects GNNs trained on very large graphs on dataset obg-arvix. The result shows that  while maintaining comparable accuracy to the original model, the pruned version achieves significant reductions in both parameter count and training duration, showing noticeable efficiency improvements.\n\nQ4:As shown in Q2, we have conducted WL Test on both real and synthetic datasets. For the pruned WL algorithm, it is considered accurate only when its graph output results are entirely consistent with the original algorithm. This requires high expressiveness. Meanwhile, experimental results demonstrate a significant improvement in the efficiency of the pruned algorithm.\n\nQ5:During the experiments, the performance for 4 layers [1,2,3,4] Pruned GIN often performs worse than  3 layers [1,2,3] Pruned GIN, We find out the reason is， when the layer gets deeper，a substantial number of neighbor representations will be repeatedly  aggregated. This significantly impedes the model's ability to extract useful information. Consequently, we refined the model to eliminate redundant representation aggregation, thereby enhancing Pruned GIN's performance.\n\nWeaknesses:In particular, K-Hop pruning loses information about non-shortest paths. While the authors argue that this is not critical, further empirical evidence would help support this claim.\n\nOur original intention was to point out that, compared to the K-Path framework, K-Hop loses information about non-shortest paths. As a result, we cannot prove that the pruned K-Hop is equivalent in expressive power to the original model. However, this does not have a significant impact. Firstly, we demonstrate the equivalence between the pruned K-Hop and the original model for regular graphs and strongly regular graphs—while the K-Hop model was specifically designed to address the inability of MP-GNNs to distinguish regular graphs. Secondly, in our ablation experiments, the pruned K-Hop exhibits equivalent expressive power to the original model for both real-world and Synthetic experiments. \n\nCompared to K-Path,  K-Hop indeed is less powerful than K-Path, since K-Path asigned more number of classes during the WL expressiveness experiment. All the experimental materials (code), results and responses to References in provided in https://anonymous.4open.science/r/PrunedGNN-AC61/README.md\n\nThanks again, for the reviewer's detailed analysis and questions, which allowed me to further refine the model in the ogbn-arxiv experiments.", "claims_and_evidence": "The authors claim that:\n- Pruning redundant structures does not reduce expressive power - This is well-supported by theoretical analysis using MATLANG and empirical validation on graph isomorphism tasks.\n- Pruned models have lower computational complexity - The paper provides clear evidence through algorithmic complexity analysis and runtime measurements.\n- Pruned K-Hop and K-Path GNNs distinguish more non-isomorphic graphs than MP-GNNs - While theoretically sound, this claim could benefit from more empirical results on diverse graph structures.\n- Pruning improves training efficiency and scalability - The results support this claim, but more large-scale graph evaluations (e.g., OGB datasets) would strengthen it.\n\nOverall, the claims are mostly well-supported, but additional empirical validation, particularly on large-scale datasets, would reinforce the conclusions.", "methods_and_evaluation_criteria": "The methodology is well-structured, with clear mathematical definitions and derivations. The pruning strategies are rigorously developed, and the expressiveness analysis is grounded in matrix algebra. The evaluation criteria include:\n\n- Expressiveness tests: Distinguishing non-isomorphic graphs.\n- Graph property prediction: Evaluating node and graph features.\n- Real-world benchmarks: TU datasets, QM9, and ZINC. The chosen benchmarks and evaluation metrics are appropriate, though additional experiments on larger-scale datasets would provide further validation.", "theoretical_claims": "The paper provides several key theoretical results:\n\n- Proof that pruned MP-GNNs retain 1-WL equivalence - The proof is logically structured and appears correct.\n- Equivalence of pruned K-Path GNNs to standard K-Path GNNs - This is rigorously shown via MATLANG.\n- Pruned K-Hop GNNs retain equivalence for distinguishing regular graphs - The proof is incomplete due to lost structural information.\n- Computational complexity analysis - The theoretical derivations appear sound.", "experimental_designs_or_analyses": "The experiments are well-designed but could be improved in a few areas:\n\n- Expressiveness experiments: The graph isomorphism tests effectively demonstrate the theoretical claims.\n- Graph property prediction: Results on the TU datasets and QM9 confirm that pruning does not degrade performance.\n- Computational efficiency: The paper successfully demonstrates reduced parameter count and runtime improvements.\n\nHowever, experiments on larger graphs (e.g., OGB datasets) and ablation studies on different pruning strategies would strengthen the empirical claims.", "relation_to_broader_scientific_literature": "The paper is well-grounded in the existing literature on GNN expressiveness and efficiency:\n\n- Expressiveness limits of MP-GNNs (Xu et al., 2019; Morris et al., 2019) - The pruning approach aligns with previous findings that message-passing GNNs are constrained by 1-WL limitations.\n- Higher-order GNNs (Maron et al., 2019; Azizian & Lelarge, 2021) - The authors position their work as a computationally efficient alternative to higher-order approaches.\n- Subgraph-based methods (Bevilacqua et al., 2022; Zhao et al., 2022) - The paper could better contrast pruning with subgraph-based improvements in expressiveness.", "essential_references_not_discussed": "The following studies could be cited, as they present different pruning techniques that can be compared against the proposed approach in the paper:\n\n[1] Dupty et al., PF-GNN: Differentiable particle filtering based approximation of universal graph representations, ICLR 2022.\n\n[2] Fey et al., GNNAutoScale: Scalable and Expressive Graph Neural Networks via Historical Embeddings, ICML 2021.\n\n[3] Müller et al., GraphChef: Decision-Tree Recipes to Explain Graph Neural Networks, ICLR 2024.", "other_strengths_and_weaknesses": "**Strengths**\n- The paper introduces a novel pruning strategy for GNNs, which reduces computational complexity while preserving expressive power. Unlike existing methods that enhance expressiveness by increasing depth or complexity, this approach optimizes efficiency without sacrificing performance.\n- The paper is well-structured, with clear theoretical justifications, proofs, and empirical results supporting the claims.\n- The extensive experimentation across synthetic and real-world datasets strengthens the findings, particularly for efficiency improvements.\n- If widely adopted, the proposed pruning strategies could make expressive GNNs more computationally feasible for large-scale applications, such as molecular modeling.\n\n**Weaknesses**\n- While the theoretical analysis supports the expressiveness claims, the experimental validation relies mostly on synthetic datasets and indirect comparisons (e.g., isomorphism tests). Direct comparisons on real-world tasks requiring high expressiveness (e.g., molecular property prediction) would strengthen the argument. A more comprehensive ablation study showing how different pruning levels affect expressiveness would be useful.\n- The efficiency claims are theoretically sound, but the experimental validation on large-scale graphs is somewhat lacking. How well do the pruned frameworks generalize to datasets with millions of nodes and edges?\n- In particular, K-Hop pruning loses information about non-shortest paths. While the authors argue that this is not critical, further empirical evidence would help support this claim.", "other_comments_or_suggestions": "Please refer to the weaknesses mentioned above.", "questions_for_authors": "1. Are there any known cases where pruned K-Hop fails to distinguish graphs that the original K-Hop framework can differentiate? Providing examples would help clarify the limitations.\n2. The claim that pruning redundant structures enhances efficiency without compromising expressiveness is central to the paper. Could the authors conduct an ablation study comparing different pruning strategies to determine whether all identified redundant structures should be removed?\n3. Have the authors tested how pruning affects GNNs trained on very large graphs (e.g., OGB datasets)? If so, do the training and inference times scale as expected?\n4. The experimental results validate the effectiveness of pruned frameworks but do not directly measure expressiveness beyond isomorphism-based tasks. Could the authors evaluate the frameworks on tasks that require high expressiveness, such as molecular property prediction with long-range dependencies?\n5. Could there be datasets where pruning negatively impacts expressiveness? If so, an analysis of when pruning is beneficial versus detrimental would strengthen the conclusions.", "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": "621gHG8uWb", "reviewer": "Reviewer_h6cq", "summary": "In this paper, the author proposed pruned MPNNs, K-path GNNs, and K-hop GNNs to reduce the computation redundancy in the original method. The author proved the expressive equivalence between the original version and the pruned version. The proposed method is evaluated on various benchmarking datasets and shows comparable results to the original version.\n\n## Update after rebuttal\n\nI would like to thank the authors for the detailed response to my questions and concerns. The author provides both a textual explanation for the complexity analysis of their method and the experimental comparison result. This helps to solve my biggest concern about the proposed method. I would like to increase my original score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank all the reviewers for their feedback and constructive comments\n\nClaims And Evidence:\n\n(2)Space Complexity:During backpropagation in training, the node representations of intermediate layers (e.g., activation values) are required to compute gradients and update weights. If intermediate node representations are discarded, backpropagation cannot proceed. Therefore node representations from each layer need to be cached, which results in $O(n·L)$.\n\nTime Complexity:We speculate the reviewer might draw conclusion:$\\sum^i_{log(L)}O(nd^{2^{i-1}})$ due to the divergence in computational paradigms. Suppose aggreation method as sum. In the reviewer’s view, the aggregation of $l$ times is computed as follow:(1)Compute the $l$-th power of the adjacency matrix $A^l$.(2)Calculate the product of $A^l$ and node representations $h$ as $A^l·h$. This computation method involves calculating the product between matrices L times, resulting in extremely high complexity (even if A is a sparse matrix). \n\nHowever in our approch (mentioned in Equation (15) on page 5), the aggregation is decomposed into $l$ times of 1-neighborhood aggregation. In other word, $A^l·h$ is computed as:\n\n  $for$ $i$ $in$ $[l]$ $do$:  $h_i=A·h_{i-1}$\n\nOur approch will only compute  the product between matrice and node representations vector. Thus, it achieves lower computational complexity compared to the approach above. Therefore the complexity of aggregation is $\\sum^i_{log(L)}O(2^{i-1}nd)=O(ndL)$. We provided pruned architectures better visualized in the link.\n\nAs for reviewer's concern for complexity, we decompose the computational time complexity into two components: (1) feature aggregation($O_{agg}(1)$ refers to one basic aggreation for a node) and (2) the MLP operations($O_{MLP}(1)$ refer one layer's MLP) and space complexity ($O_{spa}(1)$ refers to one node's represetations). Table 5 can be modified into the following table(we assume K<<L):\n\n|Training Complexity | MP-GNN | PR MP-GNN |K-HOP|PR K-HOP|K-PATH|PR K-PATH|\n|----------|----------|----------|----------|----------|----------|----------|\n| Time  | $O_{agg}(nL)+O_{MLP}(L)$ | $O_{agg}(nL)+O_{MLP}(log(L))$|$O_{agg}(nL)+O_{MLP}(L/K)$ | $O_{agg}(nL/K)+O_{MLP}(L/K)$ | $O_{agg}(nL)+O_{MLP}(L/K)$ | $O_{agg}(nL/K)+O_{MLP}(L/K)$ | \n| Space   | $O_{spa}(nL) $  | $O_{spa}(nlog(L)) $ | $O_{spa}(nL/K) $  | $O_{spa}(nL/K) $  | $O_{spa}(nL/K) $  | $O_{spa}(nL/K) $  |\n \n On the other side, in our ablation experiment, the time consumed by aggregation is not significant.\n\nAs for adjusting the number of layers, $a_l$ doesn's have to be $2^{l-1}$, we point out $2^{l-1}$ because it will reach its maximum expressiveness. Theorem4.1has shown as long as it is viewable, it will be as powerful as WL. Hence we can flexibly adjust $a_l$  as geometric sequence($a_l=l$) or other viewable sequence.\n\n(1):The Initial intention of the title derives from the comparasion of MP-GNN and PR K-PATH GNN instead of MP-GNN and PR MP-GNN: from(2), if K<<L, the complexity of PR K-PATH GNN is less than MP-GNN, while PR K-PATH is as powerful as K-PATH and K-PATH is stirctly more powerful than MP-GNN. We sincerely appreciate the reviewer's insightful comment regarding the potential ambiguity in the paper's title. In response to the reviewer's suggestion, we would like to modify the title to \"PRUNING For GNNs: LOWER COMPLEXITY WITH COMPARABLE EXPRESSIVENESS\" to better reflect the study's focus.\n\n(3)The pruned methods can also be used in Node-level tasks,  since the graph representation is a aggreation of node representations. In other word, given a Pruned MP-GNN $M'$ as powerful as arbitrary MP-GNN $M$, if for any two nodes they get same representation $M$ it will also get same representation in $M'$. \n\nMethods And Evaluation Criteria:\n\n(1)It has been mentioned above\n\n(2) The pruning strategy seems different because MP-GNN is one-aggreation while K-HOP\\PATH is Multi-aggregation. Our pruned method  for MP-GNN is suitable for any one-aggreation GNN, but pruned method for Multi-aggregation is associations between different aggregated neighbor nodes (can not guarantee the expressive equivalence).\n\n(3)The reason why GNNs typically aggregate node information within a distance L≤10 is that larger L values lead to issues such as excessive parameter size (prone to overfitting on small datasets) and high computational/memory costs. However, our pruning method reduces the parameters to a logarithmic scale (log(L)),thereby potentially enabling GNNs to aggregate information from more distant nodes\n\n\nExperimental Designs Or Analyses:We have supplemented the ablation experiments on pruning efficiency and conducted experiments on the large-scale graph OGB-arXiv. The experimental conclusion can be found in our response to other reviewers. All the experimental materials(code), results, the better visualized pruned architectures and responses to other questions are provided in https://anonymous.4open.science/r/PrunedGNN-AC61/README.md", "claims_and_evidence": "1. In the title, the authors claim that the pruned GNNs have higher expressiveness. However, I think it’s kind of misleading, as the expressive power of pruned GNNs is bounded by the original version based on the proofs provided in the paper. It is only safe to say that given the limited number of layers/iteration, the pruned version is better than the original one. \n2. In Table 5, the authors claim that the pruned version has better complexity than the original version. However, I am not convinced. First, I do not understand why the space complexity is associated with the distance $L$. Since for both MPNN, K-path GNNs, and K-hop GNNs or their pruned version, we only need to save embedding for each node in the graph, which results in $O(n)$. For time complexity, it’s also not correct, as we need to consider the density of the graph. Let’s use the average degree $d$ to characterize. For MPNNs, it should be $O(ndL)$. For PR MPNNs, it seems to me that when we need to aggregate higher order neighbors, the complexity of the aggregation will go up, which means that the complexity is different for different layers. The first layer is just $nd$. For the second layer, we will aggregate neighbors from the second hop, which results in $nd^2$. Overall, it should be $O(\\sum_{log(L)}^{i}nd^{2^{i-1}})$\n. Similarly, the analysis for K-path and K-hop GNNs is also not correct to me. Given my understanding of the complexity part, I don’t think the proposed pruned framework will result in huge computation improvement over the original version. Even worse, the pruned version requires aggregation of different neighbors for different layers, which introduces additional pre-processing time and is not flexible for adjusting the number of layers.\n3. The author mentioned that fewer layers can reduce the nonlinearity of GNNs and reduce over-smoothing. However, it is a problem primarily for node tasks. But the proposed methods are mainly used in Graph-level tasks.", "methods_and_evaluation_criteria": "1. As mentioned above, although the proposed method requires fewer layers to achieve certain expressive power, the complexity is varied and much higher than the pruned version for each layer. Therefore, it is hard to see that the proposed method is more efficient.\n2. The pruning strategy seems totally different for different GNNs. Are there any common criteria for pruning so that we can apply a similar strategy to other GNNs?\n3. Even if the proposed method does introduce efficiency due to the fewer number of layers. The application is limited. Specifically, the advantage is $log(L)$ over $L$. However, real-world graph tasks are usually molecules, whose $L$ are usually less than 10. Therefore, it seems not a big improvement to me.", "theoretical_claims": "The complexity analysis seems wrong to me. See above. Given the limited time, I cannot check the proofs of all theorems. All other conclusions seem correct to me.", "experimental_designs_or_analyses": "1. I believe a more comprehensive ablation study on the complexity is **necessary** for showing the potential of the proposed methods. Specifically, I would like to see the comparison of the original version and the pruned version on both pre-process, train, and inference time under different numbers of layers and datasets (different graph distribution). Meanwhile, the cost of space should also be evaluated to support Table 5. \n2. I would suggest another ablation study between the number of layers and the performance using both the original version and the pruned version using both the simulation data and real-world data to see if the pruned version really has better performance, especially under a imited number of layers.", "relation_to_broader_scientific_literature": "If the method really has a computation advantage over the existing method, it can be used in the field of molecular or biomedical research.", "essential_references_not_discussed": "The topic is related, and the experiment protocol is almost identical to the existing paper [1], but it is not cited, discussed, and compared.\n\n[1] Jiarui Feng, et al., How powerful are K-hop message passing graph neural networks, NeurIPS22.", "other_strengths_and_weaknesses": "See above.", "other_comments_or_suggestions": "See above.", "questions_for_authors": "See above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper proposes pruning techniques for various graph neural network architectures, including Message Passing (MP), K-Path, and K-Hop GNNs. The core contribution is a theoretically grounded framework for pruning redundant structures within these models, which reduces complexity while preserving the expressive power relative to traditional architectures. The authors provide rigorous theoretical justifications using matrix language (MATLANG) and substantiate their claims through experimental validations. The authors should include all the rebuttal efforts into the revision, especially more experiments on large-scale datasets to demonstrate the practical effectiveness and efficiency of the pruned versions. Other than that, it is known that theoretical expressiveness does not always turn into practical distinguishability of non-isomorphic graphs. Thus, I strongly encourage the authors to test their pruned GNNs on the BREC dataset (https://arxiv.org/pdf/2304.07702) to test whether the pruning compromises practical expressiveness.
Decision: Accept (poster)