Research map / Graph learning / GNN architectures

Pruning for GNNs: Lower Complexity with Comparable Expressiveness

ICML 2025 · Graph learning › GNN architectures · approach: Weisfeiler-Leman expressivity hierarchies

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes pruned versions of MP-GNN, K-Path GNN, and K-Hop GNN that remove redundant aggregation structures, proving comparable expressiveness with lower time/space complexity and reporting competitive benchmark results.

Problem

Expressive GNN variants (K-hop, K-path, higher-order) grow in aggregation complexity and depth, and standard MP-GNNs contain redundant computations that waste compute and hurt optimization.

Approach

Prune redundant multi-hop aggregation by aggregating l-path/l-hop neighbors at layer l (or a_k-walk neighbors with a_k=2^(k-1) in pruned MP-GNN), so that information is encoded without repetition; equivalence is argued via WL tests and matrix language (MATLANG).

Key results

• Pruned K-Path and pruned K-Hop GNNs match their original counterparts on EXP, SR25 and CSL expressiveness tests (e.g., 100% on EXP for K=3,4 for both).
• On ZINC, PR K-Hop reaches test MAE 0.077±0.009 with 476,615 parameters vs K-Hop 0.079±0.015 with 574,613 parameters.
• Time complexity of pruned K-Path/K-Hop is Θ(n·L/K) versus Θ(n·L) for the originals, per the paper's analysis.

Measured effects reported in the paper

Surprising findings

• Pruned MP-GNN with a_k=2^(k-1) walks reduces the parameter-configuration space of a toy task from 2^6 to 2^4 while keeping the same outputs.

Limitations

• Proof of pruned K-Hop equivalence to K-Hop is only established for regular and strongly regular graphs, not in general.
• Results are reported on small-scale benchmarks with overlapping error bars, so improvements are often within variance.

Experimental setup

Datasets: EXP SR25 CSL MUTAG DD PROTEINS PTC-MR IMDB-B QM9 ZINC

Benchmarks: EXP SR25 CSL TU datasets (MUTAG, DD, PROTEINS, PTC-MR, IMDB-B) QM9 ZINC

Metrics: accuracy MAE test MAE number of parameters runtime

Baselines: GIN GraphSAGE GraphSNN WL subtree kernel K-Hop K-Path

Builds on: GIN K-Hop GNN K-Path message passing (PathNN) 1-WL test MATLANG

Closest papers by meaning

• A Theoretical Comparison of Graph Neural Network Extensions (ICML 2022 · similarity 0.90)
• Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness (ICLR 2024 · similarity 0.90)
• Towards Bridging Generalization and Expressivity of Graph Neural Networks (ICLR 2025 · similarity 0.89)
• An Empirical Study of Realized GNN Expressiveness (ICML 2024 · similarity 0.89)
• On the Rademacher Complexity of Graph Neural Networks: Unifying Expressivity and Geometry (NeurIPS 2026 · similarity 0.88)
• Making Classic GNNs Strong Baselines Across Varying Homophily: A Smoothness–Generalization Perspective (NeurIPS 2025 · similarity 0.88)