Multicoated and Folded Graph Neural Networks with Strong Lottery Tickets

Jiale Yan, Hiroaki Ito, Ángel López García-Arias, Yasuyuki Okoshi, Hikari Otsuka, Kazushi Kawamura, Thiem Van Chu, Masato Motomura

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:

  1. 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.
  2. 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.
  3. 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).
Figure 1: A GNN with the M-Sup method: (a) shows how to apply M-Sup to a GNN. Weights are randomly initialized to ±δ, where δ is the standard deviation of the Kaiming normal distribution. (b) illustrates weight score distributions of GNN models. 256-2-GCN has 256 hidden neurons and two layers used on Cora, and 386-4-GCN has 386 hidden neurons and four layers used on OGBN-Arxiv. st1, st2, st3 are the thresholds with the Linear method.
Figure 2: Folded GNN: a ResGNN can be folded into a recursive structure like a 1-stage or an n-stage MSF. Shared masks have a set for each stage and are reused as often as the number of iterations for one stage. Unshared masks are used only once, with individual masks for each iteration.

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-Molhiv and OGBG-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.
Figure 4: The accuracy of GCN, GAT, and GIN with various sparsity values on four datasets: experiments use 2-layer GNNs of width 256 for the Cora, Citeseer, and Pubmed datasets. For the OGBN-Arxiv datasets, a 4-layer GNN with a width of 386 is used, and affine BN is applied. The head of GAT is 1 for the following experiments.
  • Deep GNNs & Memory Efficiency: On the large-scale OGBN-Arxiv dataset, 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-Molhiv dataset 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

Abstract

The Strong Lottery Ticket Hypothesis (SLTH) demonstrates the existence of high-performing subnetworks within a randomly initialized model, discoverable through pruning a convolutional neural network (CNN) without any weight training. A recent study, called Untrained GNNs Tickets (UGT), expanded SLTH from CNNs to shallow graph neural networks (GNNs). However, discrepancies persist when comparing baseline models with learned dense weights. Additionally, there remains an unexplored area in applying SLTH to deeper GNNs, which, despite delivering improved accuracy with additional layers, suffer from excessive memory requirements. To address these challenges, this work utilizes Multicoated Supermasks (M-Sup), a scalar pruning mask method, and implements it in GNNs by proposing a strategy for setting its pruning thresholds adaptively. In the context of deep GNNs, this research uncovers the existence of untrained recurrent networks, which exhibit performance on par with their trained feed-forward counterparts. This paper also introduces the Multi-Stage Folding and Unshared Masks methods to expand the search space in terms of both architecture and parameters. Through the evaluation of various datasets, including the Open Graph Benchmark (OGB), this work establishes a triple-win scenario for SLTH-based GNNs: by achieving high sparsity, competitive performance, and high memory efficiency with up to 98.7\% reduction, it demonstrates suitability for energy-efficient graph processing.
BibTeX
@inproceedings{yan2023multicoated,
  author = {Jiale Yan and Hiroaki Ito and Ángel López García-Arias and Yasuyuki Okoshi and Hikari Otsuka and Kazushi Kawamura and Thiem Van Chu and Masato Motomura},
  title = {{Multicoated and Folded Graph Neural Networks with Strong Lottery Tickets}},
  booktitle = {LoG},
  year = {2023},
}
Figure