Graph Lottery Ticket (GLT), a combination of core subgraph and sparse
subnetwork, has been proposed to mitigate the computational cost of deep Graph
Neural Networks (GNNs) on large input graphs while preserving original
performance. However, the winning GLTs in exisiting studies are obtained by
applying iterative magnitude-based pruning (IMP) without re-evaluating and
re-considering the pruned information, which disregards the dynamic changes in
the significance of edges/weights during graph/model structure pruning, and
thus limits the appeal of the winning tickets. In this paper, we formulate a
conjecture, i.e., existing overlooked valuable information in the pruned graph
connections and model parameters which can be re-grouped into GLT to enhance
the final performance. Specifically, we propose an adversarial complementary
erasing (ACE) framework to explore the valuable information from the pruned
components, thereby developing a more powerful GLT, referred to as the ACE-GLT.
The main idea is to mine valuable information from pruned edges/weights after
each round of IMP, and employ the ACE technique to refine the GLT processing.
Finally, experimental results demonstrate that our ACE-GLT outperforms existing
methods for searching GLT in diverse tasks. Our code will be made publicly
available.

我们提出了一种基于 Adversarial Complementary Erasing（ACE）框架的 Graph Lottery Ticket（GLT）方法，用于在研究中获取有价值的信息，并提升深度图神经网络（GNNs）在大型输入图上的性能。实验结果表明，ACE-GLT 在各种任务上优于现有的 GLT 搜索方法。

剪枝元素的对抗擦除：迈向更好的图形彩票

Adversarial Erasing with Pruned Elements: Towards Better Graph Lottery  Ticket

With graphs rapidly growing in size and deeper graph neural networks (GNNs)
emerging, the training and inference of GNNs become increasingly expensive.
Existing network weight pruning algorithms cannot address the main space and
computational bottleneck in GNNs, caused by the size and connectivity of the
graph. To this end, this paper first presents a unified GNN sparsification
(UGS) framework that simultaneously prunes the graph adjacency matrix and the
model weights, for effectively accelerating GNN inference on large-scale
graphs. Leveraging this new tool, we further generalize the recently popular
lottery ticket hypothesis to GNNs for the first time, by defining a graph
lottery ticket (GLT) as a pair of core sub-dataset and sparse sub-network,
which can be jointly identified from the original GNN and the full dense graph
by iteratively applying UGS. Like its counterpart in convolutional neural
networks, GLT can be trained in isolation to match the performance of training
with the full model and graph, and can be drawn from both randomly initialized
and self-supervised pre-trained GNNs. Our proposal has been experimentally
verified across various GNN architectures and diverse tasks, on both
small-scale graph datasets (Cora, Citeseer and PubMed), and large-scale
datasets from the challenging Open Graph Benchmark (OGB). Specifically, for
node classification, our found GLTs achieve the same accuracies with 20%~98%
MACs saving on small graphs and 25%~85% MACs saving on large ones. For link
prediction, GLTs lead to 48%~97% and 70% MACs saving on small and large graph
datasets, respectively, without compromising predictive performance. Codes
available at this https URL

提出了一种统一的 GNN 稀疏化 (UFG) 框架，同时剪枝图邻接矩阵和模型权重，以有效加速大规模图上的 GNN 推理，并将 lottery ticket 假设推广到 GNN，定义了图 lottery ticket (GLT) 作为核心子数据集和稀疏子网络对的一对，从原始的 GNN 和全密集图中通过迭代应用 UFS 联合鉴定。在各种 GNN 架构和不同任务的数据集上进行了实验验证，表明在不影响预测性能的前提下，GLT 能够实现小和大规模图数据集上的 MACS 节约。