Pruning for GNNs: Lower Complexity with Comparable Expressiveness

We sincerely thank all the reviewers for their feedback and constructive comments

Claims And Evidence:

(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)$.

Time 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).

However 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:

$for$ $i$ $in$ $[l]$ $do$: $h_i=A·h_{i-1}$

Our 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.

As 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):

On the other side, in our ablation experiment, the time consumed by aggregation is not significant.

As 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.

(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.

(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'$.

Methods And Evaluation Criteria:

(1)It has been mentioned above

(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).

(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

Experimental 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

We sincerely acknowledge reviewer V1ZW for the constructive criticism and insightful suggestions.

Questions For Authors:

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.

Q2: 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.

We have supplemented ablation experiments analyzing the impact of different pruning strategies on model efficiency and accuracy. We 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.

As 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.

Q3: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.

Q4: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.

Q5: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.

Weaknesses: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.

Our 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.

Compared 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

Thanks again, for the reviewer's detailed analysis and questions, which allowed me to further refine the model in the ogbn-arxiv experiments.

We thank reviewer hERx careful evaluation and meaningful suggestions.

Q1: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.

To 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.

Additionally, 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.

Q2: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.

After 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.

And all the experimental materials(code) and results in provided in https://anonymous.4open.science/r/PrunedGNN-AC61/README.md