TL;DR
This paper demonstrates that we can find highly accurate, completely untrained subnetworks within randomly initialized Graph Neural Networks (GNNs)—supporting the Strong Lottery Ticket Hypothesis (SLTH). By introducing Multicoated Supermasks (M-Sup) and network folding techniques, the authors achieve up to a 98.7% reduction in memory footprint while matching or exceeding the performance of traditionally trained, dense GNNs.
What Problem Does This Paper Address?
Graph Neural Networks (GNNs) are incredibly powerful for analyzing graph-structured data, but as graphs scale up, the computational and memory overhead of deep GNNs skyrockets.
To mitigate this, researchers often turn to the Lottery Ticket Hypothesis (LTH), which states that dense networks contain sparse subnetworks ("winning tickets") capable of matching the original network's performance. Most methods rely on the Weak LTH, which still requires computationally expensive weight re-training after pruning.
This paper focuses on the Strong Lottery Ticket Hypothesis (SLTH), where winning subnetworks are discovered within a randomly initialized network without any weight training at all. Prior attempts to apply SLTH to shallow GNNs left a noticeable accuracy gap compared to standard dense training. Furthermore, no one had successfully cracked how to apply SLTH to deep GNNs without suffering from extreme memory demands. This paper tackles both challenges.
Methods
The authors introduce a combination of novel masking and architectural optimization techniques:
- Multicoated Supermasks (M-Sup) with Adaptive Thresholds: Instead of using a single binary mask to prune weights (Single-coated Supermask / S-Sup), M-Sup overlays multiple scalar masks at varying sparsity levels to find better subnetworks. To make this work for GNNs, the authors designed an adaptive thresholding strategy that dynamically adjusts to the network's weight score distributions.
- Hidden-Fold Networks (HFN) for GNNs: To make deep GNNs memory-efficient, the authors "fold" deep feed-forward layers into a single, compact recurrent block that reuses the same weights across iterations.
- Multi-Stage Folding (MSF) & Unshared Masks: To expand the subnetwork search space, they introduce MSF (folding layers into multiple sequential stages rather than just one) and Unshared Masks (applying unique masks to each recurrent iteration instead of reusing the same mask).
Datasets
The authors evaluated their approaches across several standard graph benchmarks:
- Node-level tasks (Shallow GNNs): Cora, Citeseer, and PubMed.
- Large-scale node-level tasks (Deep GNNs): Open Graph Benchmark Arxiv (
OGBN-Arxiv). - Graph-level tasks: Open Graph Benchmark Molecular datasets (
OGBG-MolhivandOGBG-Molbace).
Key Insights and Ideas
- Untrained Recurrent Subnetworks Exist in Deep GNNs: The most surprising finding is that deep GNNs can be compressed into shallow, recurrent structures without ever training a single weight parameter. These random, pruned recurrent networks perform on par with their fully trained feed-forward counterparts.
- Multimodal Distributions Block Standard Pruning: The authors discovered that shallow GNNs exhibit complex, multi-peaked weight score distributions. Standard linear pruning schedules fail because they create ineffective mask layers. The proposed adaptive thresholding mechanism bypasses this by identifying and invalidating dead mask layers.
- Extreme Hardware Friendliness: Because the weights remain completely random and static, an inference accelerator doesn't actually need to store them in memory. Weights can be generated on-the-fly using a random number generator seed, meaning the hardware only needs to store the single-bit pruning masks.
Key Results
- Shallow GNNs: As shown in the accuracy curves below, M-Sup consistently outperforms the previous state-of-the-art SLTH method (UGT) across Cora, Citeseer, and PubMed, effectively closing the performance gap with dense-weight learning (DWL) baselines.
- Deep GNNs & Memory Efficiency: On the large-scale
OGBN-Arxivdataset, the folded ResGCN+ model achieved a 72% memory reduction while maintaining baseline accuracy. - Graph-Level Tasks: The folded DyResGEN model achieved an astonishing 98.7% memory reduction on the
OGBG-Molhivdataset while matching the baseline ROC-AUC.
Limitations and Future Work
While the paper demonstrates massive memory savings, the authors note a clear trade-off: using Unshared Masks and Multi-Stage Folding (MSF) significantly improves accuracy, but it increases the parameter and mask bit count compared to simpler single-stage folding with shared masks. Additionally, the choice between Uniform and Linear thresholding strategies still shows some dependency on the specific dataset and GNN architecture used.
For future work, the authors suggest expanding this weight-matrix pruning approach to simultaneously prune the graph's adjacency matrix, combining structural graph sparsity with weight sparsity under the SLTH framework.
Summary updated