Pruning for GNNs: Lower Complexity with Comparable Expressiveness

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. K-Path Message Passing Framework. The K-Path GNN extends the standard message passing to consider paths of length k (1 ≤ k ≤ K). Specifically, each k-path neighbor set N k path (v) is aggregated independently and then combined. Specifically, A node can appear multiple times as a k-path neighbor of v, allowing the algorithm to capture repeated walks of length k. We use (G, G ′ ) ∈ GI L K-P to denote that the K-Path WL test decides G and G ′ are isomorphic after L iterations. K-Hop Message Passing Framework. The K-Hop GNN differs by focusing on shortest-path neighbors. Each node