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.

该研究基于强彩票模型假设（SLTH）证明了初始化模型中存在高效子网络，通过修剪卷积神经网络（CNN）而无需进行权重训练。论文通过采用多层拓扑和非共享蒙版方法在图神经网络（GNNs）中实现了 M-Sup 标量修剪蒙版，并通过自适应设置修剪阈值的策略，揭示了训练有素的前馈网络的非训练循环网络的性能相当。同时，通过在多个数据集上进行评估，包括 Open Graph Benchmark（OGB），该研究确立了 SLTH-GNN 的三重优势：高稀疏性、竞争性能和高内存效率，显示了其适用于高效图处理的能力。

多层覆盖与折叠图神经网络及强彩票

Multicoated and Folded Graph Neural Networks with Strong Lottery Tickets

The Strong Lottery Ticket Hypothesis (SLTH) states that randomly-initialised
neural networks likely contain subnetworks that perform well without any
training. Although unstructured pruning has been extensively studied in this
context, its structured counterpart, which can deliver significant
computational and memory efficiency gains, has been largely unexplored. One of
the main reasons for this gap is the limitations of the underlying mathematical
tools used in formal analyses of the SLTH. In this paper, we overcome these
limitations: we leverage recent advances in the multidimensional generalisation
of the Random Subset-Sum Problem and obtain a variant that admits the
stochastic dependencies that arise when addressing structured pruning in the
SLTH. We apply this result to prove, for a wide class of random Convolutional
Neural Networks, the existence of structured subnetworks that can approximate
any sufficiently smaller network.
This result provides the first sub-exponential bound around the SLTH for
structured pruning, opening up new avenues for further research on the
hypothesis and contributing to the understanding of the role of
over-parameterization in deep learning.

给定一个研究论文，识别并提取五个准确代表其主题和研究领域的关键词。然后，通过一句简洁的中文句子总结该论文。输出结果为 JSON，包含关键词和摘要字段，无需解释。

具有结构强胜算头奖券的 N 次多项式超参数化卷积神经网络

Polynomially Over-Parameterized Convolutional Neural Networks Contain  Structured Strong Winning Lottery Tickets

The Strong Lottery Ticket Hypothesis (SLTH) stipulates the existence of a
subnetwork within a sufficiently overparameterized (dense) neural network that
-- when initialized randomly and without any training -- achieves the accuracy
of a fully trained target network. Recent works by Da Cunha et. al 2022;
Burkholz 2022 demonstrate that the SLTH can be extended to translation
equivariant networks -- i.e. CNNs -- with the same level of overparametrization
as needed for the SLTs in dense networks. However, modern neural networks are
capable of incorporating more than just translation symmetry, and developing
general equivariant architectures such as rotation and permutation has been a
powerful design principle. In this paper, we generalize the SLTH to functions
that preserve the action of the group $G$ -- i.e. $G$-equivariant network --
and prove, with high probability, that one can approximate any $G$-equivariant
network of fixed width and depth by pruning a randomly initialized
overparametrized $G$-equivariant network to a $G$-equivariant subnetwork. We
further prove that our prescribed overparametrization scheme is optimal and
provides a lower bound on the number of effective parameters as a function of
the error tolerance. We develop our theory for a large range of groups,
including subgroups of the Euclidean $\text{E}(2)$ and Symmetric group $G \leq
\mathcal{S}_n$ -- allowing us to find SLTs for MLPs, CNNs,
$\text{E}(2)$-steerable CNNs, and permutation equivariant networks as specific
instantiations of our unified framework. Empirically, we verify our theory by
pruning overparametrized $\text{E}(2)$-steerable CNNs, $k$-order GNNs, and
message passing GNNs to match the performance of trained target networks.

本文将 Strong Lottery Ticket Hypothesis（SLTH）推广至可保持群作用的网络，即 G-equivariant network, 并证明可以通过对随机初始化的过参数化 G-equivariant network 进行修剪，获得 G-equivariant subnetwork 来逼近任意 G-equivariant network。实验证明该理论适用于多种网络，包括 MLPs, CNNs, E (2)-steerable CNNs 和 permutation equivariant networks。