  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.
