Graph Lottery Ticket Automated
Authors: Guibin Zhang
Kun Wang
Wei Huang
Yanwei Yue
Yang Wang
Roger Zimmermann
Aojun Zhou
Dawei Cheng
Jin Zeng
Yuxuan Liang
Venue: ICLR 2024 poster (2024)
Keywords: Lottery Ticket Hypothesis
Graph Neural Networks
Graph Neural Tangent Kernel
Primary area: learning on graphs and other geometries & topologies

Abstract: Graph Neural Networks (GNNs) have emerged as the leading deep learning models for graph-based representation learning. However, the training and inference of  GNNs on large graphs remain resource-intensive, impeding their utility in real-world scenarios and curtailing their applicability in deeper and more sophisticated GNN architectures. To address this issue, the Graph Lottery Ticket (GLT) hypothesis assumes that GNN with random initialization harbors a pair of core subgraph and sparse subnetwork, which can yield comparable performance and higher efficiency to that of the original dense network and complete graph. Despite that GLT offers a new paradigm for GNN training and inference, existing GLT algorithms heavily rely on trial-and-error pruning rate tuning and scheduling, and adhere to an irreversible pruning paradigm that lacks elasticity. Worse still, current methods suffer scalability issues when applied to deep GNNs, as they maintain the same topology structure across all layers. These challenges hinder the integration of GLT into deeper and larger-scale GNN contexts.  To bridge this critical gap, this paper introduces an $\textbf{A}$daptive, $\textbf{D}$ynamic, and $\textbf{A}$utomated framework for identifying $\textbf{G}$raph $\textbf{L}$ottery $\textbf{T}$ickets ($\textbf{AdaGLT}$). Our proposed method derives its key advantages and addresses the above limitations through the following three aspects: 1) tailoring layer-adaptive sparse structures for various datasets and GNNs, thus endowing it with the capability to facilitate deeper GNNs; 2) integrating the pruning and training processes, thereby achieving a dynamic workflow encompassing both pruning and restoration; 3) automatically capturing graph lottery tickets across diverse sparsity levels, obviating the necessity for extensive pruning parameter tuning. More importantly, we rigorously provide theoretical proofs to guarantee $\textbf{AdaGLT}$  to mitigate over-smoothing issues and obtain improved sparse structures in deep GNN scenarios. Extensive experiments demonstrate that $\textbf{AdaGLT}$ outperforms state-of-the-art competitors across multiple graph datasets of various scales and types, particularly in scenarios involving deep GNNs.

Published as a conference paper at ICLR 2024
GRAPH LOTTERY TICKET AUTOMATED
Guibin Zhang 1.2.1, Kun Wang Wei Huang', Yanwei Yue', Yang Wang", Roger Zimmermann', Aojun Zhou', Dawei Cheng', Jin Zeng' Yuxuan Liangl+ TTongii University "hhe Hong Kong University of Science and Technology (Guangzhou)
Uniieeriity of Science and Technology of China (USTC) 'RIKEN AIP
Nattional University of Singapore The Chinese University of Hong Kong
ABSTRACT
Graph Neural Networks (GNNs) demonstrate superior performance in various graph learning tasks, yet their wider real- world application is hindered by the com- putational overhead when applied to large-scale graphs. To address this issue, the Graph Lottery Ticket (GLT) hypothesis assumes that GNN with random initializa- tion harbors a pair of core subgraph and sparse subnetwork, which can yield com- parable performance and higher efficiency to that of the original dense network and complete graph. Despite that GLT offers a new paradigm for GNN training and inference, existing GL.T algorithms heavily rely on trial-and-error pruning rate tuning and scheduling, and adhere to an irreversible pruning paradigm that lacks elasticity. Worse still, current methods suffer scalability issues when applied to deep GNNs, as they maintain the same topology structure across all layers. These challenges hinder the integration of GLT into deeper and larger-scal scale GNN con- texts. To bridge this critical gap. this paper introduces an Adaptive, Dynamic, and Automated framework for identifying Graph Lottery Tickets (AdaGLT). Our proposed method derives its key advantages and addresses the above limitations through the following three aspects: 1) tailoring layer-adaptive sparse structures for various datasets and GNNs, thus enabling to facilitate deeper GNNs; 2) in- tegrating the pruning and training processes, thereby achieving dynamic work- flow encompassing both pruning and restoration: 3) automatically capturing graph lottery tickets across diverse sparsity levels, obviating the necessity for exten- sive pruning parameter tuning. More importantly, we rigorously provide theoret- ical proofs to guarantee AdaGLT to mitigate over-smoothing and obtain improved sparse structures in deep GNN scenarios. Extensive experiments demonstrate that AdaGLT outperforms ofate-of-the-ar competitors across multiple datasets of vari- ous scales and types, particularly in scenarios involving deep GNNs.
INTRODUCTION
Graph Neural Networks (GNNs) have emerged as the prevailing model for graph representation learning tasks (Kipf & Welling, 2017b; Veličković et al., 2018; Hamilton et al., 2017: Zhang & Chen, 2019; Liang et al., 2023; Gao et al., 2023; Cheng et al., 2021; Duan et al., 2024; Zhang et al., 2024). The success of GNNs is primarily attributed to their message passing scheme, where each node updates its features by aggregating information of its neighbors (Corso et al., 2020; Xie et al., 2020). Nevertheless, with the remarkable growth in graph sizes (from millions to billions of nodes) over the past few years, GNNs have experienced substantial computational overheads during both model training and inference (Xu et al., 2019; You et al., 2020).
To address this inefficiency, current research in this area mainly follows two distinct lines of investi- gation - one focuses simplifying the graph structure, while the other concentrates on compressing the GNN model. In the first line of study, previous literature has explored the utilization of sampling (Chen al., 2018: Eden al., 2018; Calandriello al., 2018) and sparsification (Voudigari et al., 2016; Zheng et al., 2020; Li et al., 2020b) to reduce the computational overhead of GNNs. Com- pared efforts in simplifying the graph structure, research on pruning or compressing GNNs (Tailor et al., 2020) has been relatively limited, mainly due to the inherent lower parameterization of GNNs compared to other fields such as computer vision (Wen et al., 2016; He et al., 2017).
"Yuxuan Liang and Jin Zeng are the corresponding authors, t denotes equal contributions.

---

Published as a conference paper at ICLR 2024
Interestingly, burgeoning subfield, inspired by the Lottery Ticket Hypothesis (Frankle & Carbin, 2018), is exploring the potential of jointly and iteratively pruning weights and ad- jacency matrices within GNNs. These pruned subnetworks and subgraphs, which can match the original baseline performance, are termed Graph Lottery Tickets (GLT) (Chen et al.,
Accuracy (%)
70
Accuracy (%)
70
60
60
2021b; Hui et al.. 2023). Specifically, UGS (Chen et al., 2021b) jointly prunes the weights and adjacency matrix and rewinds the weight at the regular iterations. TGLT (Hui et al., 2023) extends this concept and designs a new aux- iliary loss function to guide the edges prun- ing for identifying GLT, to name just a few. Despite their remarkable performance, training GLT models is extremely challenging. Issues arising in various aspects including predefined sparsity, network depth, and element pruning, potentially leading to the collapse of the entire model:
Baseline
Baseline
Sy 15%
Sg 15%
30%
30%
50
50
2
8
2
8
GNN Layers
GNN Layers
Figure The performance of (Left) UGS and (Right) TGLT on the Cora dataset for GCN pruning at 2-8 lay- ers, under graph sparsity levels of 0%, 15%, and 30%. See the definition of 8g in Eq. G.
Inferior scalability in the context of deep GNNs. Recent endeavors on GNN deepening (Li al., 2019; 2020a; 2021), have already attested to the potential of deep GNNs. However, the off- sheelf GLT algorithms demonstrate considerable sensitivity to model depth. As shown in Fig. UGS and TGLT exhibit a significant performance decline when applied to deeper GCNs. For example, there is performance degradation exceeding 10% from 6 + 8 GNN layers. This constrains the model's potential in the pursuit of ever-deeper GNNs.
Loss of elasticity in pruning process. The majority of GLT methods prune weights and edges in irreversible fashion, thereby rendering the pruned weights edges irretrievable. Nevertheless, recent investigations (He et al., 2018; Mocanu et al., 2018; Evei et al., 2020) suggest that the significance of both edges and weights might dynamically evolve during the training process. As a result, the pruning methodologies previously employed in GLT exhibit a lack of elasticity.
Inflexibility of fixed pruning rates. Prior GLT algorithms necessitate predetermined pruning ratios (e.g. 5% for graph and 20% for weight). Nonetheless, employing fixed pruning configura- tion across all GNN layers lacks flexibility and resilience. Worse still, the trial-and-error selection process for these pre-defined parameters could introduce additional computational overhead.
In this paper, aiming to jointly overcome these cru- cial, intractable, and inherent hurdles, we propose an Adaptive, Dynamic and Automatic framework for identifying Graph Lottery Tickets, termed AdaGLT. Fig. 2 left demonstrates the overall workflow of AdaGLT. In contrast to previous GLT methods (see Fig. 2 right) which prune a fixed rate of weights edges after certain epochs of pretraining, method seamlessly performs sparsification and train- ing within one epoch, thereby obtaining winning tickets at continuous sparsity levels. Our proposed algorithm is equipped with the following promising features, with strong experimental validation:
Kidd font contribttions
Bize denote
Network
Graph
AdaGLT
UGS/TGLT
Joint Sparstfcation
Pintrasi
opechs
Ohe-sbar
praning
roundl pruning
Autonaatcc proning
Freakfina!
Demarcic neronativ
prastin
Adaptive layer sparsification. Recent studies have suggested that shallower layers, owing to their lower node similarity, should be assigned more con- servative pruning rate. As the network depth in- creases, the pruning rate should be correspondingly adjusted upwards to effectively alleviate issues like over- smoothing (Wang et al., 2023a). Classic GLT algorithms lack effective adaptive mechanism, leading to suboptimal performance when applied to deep GNNs. AdaGLT is capable of learning layer-
epects
Adaytie Maerr goregiattoon
Gresstent noress layors
Rewind
Retrain
6
Graph
Figure 2: The overall workflow of our proposed AdaGLT compared with previous methods.
2

---

Published as a conference paper at ICLR 2024
specific thresholds for GNN at different layers, enabling the model to acquire layer-adaptive sparse structures at each layer.
Dynamic restoration. In contrast to prior deterministic approaches (Chen et al., 2021b; Harn et al., 2022), AdaGLT can seamlessly integrate the pruning and training process, enabling a dynamic restoration of possibly mistakenly pruned edges or weights during subsequent training phases.
Automated pruning scheduling. AdaGLT eliminates the need for manually predefined pruning ratios. The sparsity of the graph and network grows progressively with the pruning threshold being automatically adjusted during the training process to discover the optimal sparse graph and network structure that best fits the downstream task. This ingredient is completely free of human labor of trial-an-erroo on pre-selected sparsity choices.
Empirical Evidence. AdaGLT has been empirically validated across diverse GNN architectures and tasks. The experimental results show that AdaGLT consistently surpasses UGS/TGLT across various graph/network sparsity configurations on all benchmark datasets (Cora, Citeseer, PubMed, and Open Graph Benchmark(OGB)) AdaGLT attains 23%-84% graph sparsity and 87%-99% weight sparsity, maintaining performance without compromise, exhibiting enhancements of 13%-30% in graph spar- sity and 50%10% in weight sparsity. In deep GNN scenarios, AdaGLT achieves remarkable increase of up to 40% in graph sparsity and 80% in weight sparsity. This substantial demonstration under- scores the immense potential of fully automated GLT in real-world applications.
2 PRELIMINARY & RELATED WORK
Notations. We consider an undirected graph G= (V,E) ( E} where V and are the sets of nodes and edges of respectively. We use X E RR to denote the features matrix of G, where N = D denotes the number of nodes on the graph. We use x; = X to represent the F-dimensional feature vector corresponding node Us E V. An adjacency matrix A N is employed to represent the connectivity between nodes, where [ii if (1;, v3) E & else A = 0.
Graph Neural Networks (GNNs). GNNs mainly fall into spectral and spatial two categories. The spectral GNN is derived from spectral graph theory (Chung & Graham, 1997; McSherry, 2001; Defferrard et al., 2016; Levie et al., 2018), 8), which leverages the eigenvalues and eigenvectors of the graph Laplacian matrix to encode and process graph information. Spatial GNN (Kipf & Welling, 2017a; Velickovic et al., 2017; Xu et al., 2019) excels its flexibility and efficiency by aggregating neighborhood information. Among those, Graph Convolutional Networks (GCN) (Kipf & Welling, 2017a) can be deemed as the most popular model. Without sacrificing generality, we consider a GCN with two convolutional layers for node classification, whose formulation and objective function can be defined as follows:
Z = Softmax (Ao(AXO()) L LG - -- Vilog (z:),
(1)
where Z denotes the model prediction, θ ( o (1) denotes the weights, a (-) denote the activation function, Å D D + I)D is the symmetric normalized adjacency matrix and D is the degree mtrix of A + I. We minimize the cross-entropy loss L (9, θ) over all labelled nodes Vi V. where y; and 2; represents the label and prediction of node U; respectively.
Graph Sparsification & Lottery Tickets (GLT). The Lottery Ticket Hypothesis (LTH) posits that a sparse and effective subnetwork can be extracted from dense network through an iterative pruning approach (Frankle & Carbin, 2018; Frankle et al., 2019; Zhang et al., 2021). Initially observed within dense networks. LTH has garnered significant attention across diverse domains, including generative models (Chen et al., 2021c;a), speech recognition (Ding et al., 2021), large language models (Chen et al., 2020; Prasanna et al., 2020). Chen al. (2021b) borrowed the concept from LTH and firstly unified simplifying the graph strcufure with compressing the GNN model in the GLT research line. Specifically, GLT is defined as a pair of core subgraphs and sparse sub-network, which can be jointly identified from the full graph and the original GNN model. Recent extensions of the GLT theory (You et al., 2022; Wang et al., 2023b) and new algorithms (Harn et al., 2022; Rahman & Azad, 2022; Liu et al., 2023; Wang et al., 2023c) have made GLT shine in the field of graph pruning research line. However, these algorithms lack sufficient flexibility in terms of sparsity, network depth, and element pruning, resulting in a lack of robustness in practical deployments.
3

---

Published as a conference paper at ICLR 2024
(a) Weight pruning
Dynamic: Weight recovery
Fierarchical traversal
Visunlization
Miric: The uriginal parmmeterr mapped derivaable form
0.9
0.6
13
1.2
No BP
New grdden Dhirihaiee
12
0.8
0.7
0.8
OW
07
11
0.9
1.
Weight
W
Thrshood
Eiiaary Mask
Vertor
Automatic
pruning
Edge SCDISS
Adaptive: Edge explainer
Marping
wwndkakinng
Node-ube
Straight- through gradients
0.704.
0.5
(13 0,80880 0:2
0.3
(c) Gradient estimator
Graph
D4
0.7
Forward propagation
Hierarchical
A
Threshold
Vedto
(b) Graph pruning
No BP
Back propegation
fraversal
Dynamic: Edge recovery
Contribations:
1.Dynamic Adagtive 3.Automatic
Figure 3: The framework AdaGLT, which we firstly allocate trainable threshold vectors to guide the weights and adjacency matrices pruning different layers. (a) illustrates the weight pruning through row-wise thresholds. (h) showcases layer-adaptive pruning of the adjacency matrix. (c) elucidates how the gradient estimator renders the training process differentiable and enables the dynamic restoration of weights and edges.
3 METHODOLOGY
In this section, proceed to provide an overarching depiction of the operational mechanies of AdaGLT, wherein adaptive, dynamic, and automated joint sparsification executed for searching GLT (Fig. 3). Taking macro look, undertake fine-grained weight sparsification, involving the creation of binary mask through row-wise thresholding (Fig. 3 (a)). For the adjacency ma- trix, the edge explainer guides pruning by learning a soft mask (Fig. 3 (b)). Given the inherent non-differentiabilit of the binary mask during backpropagation, we employ a gradient estimator to simulate its gradients (Fig. 3 (c)). the following parts, we will delve into the technical details of AdaGLT, focusing on its three core features and enhancement beyond mainstream GLT approaches.
3.1 AUTOMATED WEIGHT SPARSIFICATION
Existing GLT methods iteratively eliminate elements by choosing those with minimal magnitudes, and their lack of flexibility stems from the necessity of hyperparameter tuming. To rectify this draw- back, AdaGLT dispenses with manually defined pruning rates and autonomously schedule the prun- ing process through the employment of trainable threshold vectors' (Liu et al., 2020; 2022; Zhou al., 2021). Concretely, align with the weight set (0), (1), ... (L--1) across I.-layers GNN for sparsification. Within
allocate set of trainable threshold vectors {1(0) 4.
(1)
1g ((1-1)3 to
each layer, we calculate the binary mask my via the magnitude comparison for weight pruning:
1, if O5 2 ta
m& 55
00 otherwise
where Oij and ma.ij is the element the i-th row and j-th column of O and mg. respectively; tg.: is the i-th element of the threshold vector Lg.
Gradient Estimator. However, it is not feasible to optimize these learnable thresholds using tra- ditional gradient descent methods. The hard binary mask my is derived through comparison operation that prevents gradient backpropagation, rendering the thresholds untrainable. With this
objective in mind, we calculate a soft differentiable mask using the tempered sigmoid function (Liu et al., 2022). Subsequently. we convert it into a hard binary mask as follows:
me Sigmoid (r- ((Or,] ta.)), ma,j [mo,, 0.5],
(3)
where [ > 0.5] denotes an binary indicator that evaluates to when mo.3 > 0.5, and otherwise. In order approximate the hard mask, we leverage temperature parameter т, wherein
We discuss threshold scalar matrix and compare their performances in Sec. 4.5 and Appendix B.
4

---

Published as a conference paper at ICLR 2024
the Sigmoid function closely emulates the behavior of step function when the temperature is elevated adequately. With the gradient Straight Through Estimator (STE)² (Bengio et al., 2013; Tian et al., 2021; Yang et al., 2023),
compute the gradients of to as follows:
ac
ΣΣ ac 8 T exp (r(to.> Opp)
(4)
atg.
exp (r(to.p ppy)))
where C' denotes the gradient of the cost the context of paok-propngation and of evaluates to I when i = p, and 0 otherwise. Now that the calculation of pruning masks is differentiable, proceed to calculate the pruned weights as follows:
θ (
m @ @ @ ( - {0, 1.. 1},
(5)
where O denotes the element-wise multiplication and e denotes the pruned weight layer Upon obtaining the masked weights, they are employed in the subsequent convolutional opera- tions. During the backward propagation phase, gradients facilitated by STE concurrently update the weights of each layer and their corresponding threshold vectors. Our weight sparsification pro- cess not only guides the weight updates towards enhanced performance but also aids refining the threshold vectors to effectively unveil an optimal sparse structure within the network.
3.2 LAVER-ADAPTIVE ADIACENCY MATRIX PRUNING
Due to the discrete nature adjacency matrix, we relax edge elements from binary variables to continuous variables and subsequently apply the same pruning strategy as weight pruning.
Edge Explainer. Conventional GLT methods often employ a trainable mask with its shape identical to that of the adjacency matrix, which may result in quadratic increase in parameters with the size of the graph data (Sui et al., 2021). A promising and natural idea is to transform edge elements into a representation of importance scores, i.e., relaxing edge elements from binary variables continuous ones. With this in mind, we introduce the concept of edge explainer (Luo et al., 2020; Sui et al., 2022) into GNN pruning for the first time, ensuring interpretability during the pruning process while reducing unimportant edges. Specifically, we calculate the edge score according to the node features and node centrality as follows:
exp (xx,
81g = (1.))E E (N()) cxp (g (x,, x. \)/ go (x,, x,) = ((x,xx)((Wxx, (WQx,) (WKx,)
(6)
where sty is the edge score between t; and Uj. Iv is the edge explainer parameterized with L (Wo, Wk ). (1;) denotes the I-hop neighbors of v. and w represents a temperature coefficient to control the importance scores. Once the weighted graph topology has been obtained, proceed with the execution of layer-wise pruning. To achieve this objective, a trainable threshold vector is (L- -t(1-1) RN,,
allocated for each layer's adjacency matrix, denoted collectively as (t(() (t()) .th
mirroring the analogous allocation of threshold vectors for weights across each layer.
Layer-adaptive Pruning. Going beyond element pruning like weight sparsification, edge pruning seeks to obtain an optimal graph substructure with increasing sparsity across layers (especially in deep GNN cireumstances). Consequently, we compute the pruning mask for each layer's adjacency matrix in an iterative manner:
()) m A.5 = [
II
ml) A.0. 1= (0. 1, L-1),
(7)
where m E N denotes the graph mask at layer The product term I m A,4 ensures that edges pruned carlier layers are also retained as pruned in the I-th layer, thus compelling the searched graph substructure exhibit progressively escalating sparsity across layers. Similarly, utilize a gradient estimation approach akin to that delineated Eq. 3 and 4 to address the non- differentiability inherent in binary pruning masks. Ultimately, we attain distinct and layer-wise sparse graph topological structures, denoted as A (1) = m
( @ A and / = {0, 1, ... ,L- --11 13.
3.3 A UNIFIED AND DYNAMIC OPTIMIZATION
Sparse Regularization. pursuit of achieving the desired levels of sparsity for both weights and adjacency matrices, we seek to obtain threshold vectors with higher values. To this end, it becomes
We discuss alternative estimators and compare their performance in Appendix K.
5

---

Published as a conference paper at ICLR 2024
necessary to impose sparsity-indueing constraints on by and t to penalize smaller threshold values. Specifically, for any given threshold vector E IR,, its associated penalty term is given by R(t) = - exp (~ta) and 1i is the regularization coefficient. We unify the sparsity penalties for the R(t(2)).
threshold vectors of weights and adjacency matrices as -, Eio (R(t))) (R(t))
Objective function. The original fully-connected layers and the underlying graph topology have now been replaced with finely-graines masked weights and progressively sparse adjacency matrices. We can proceed to directly train a jointly sparsed GNN using the backpropagation algorithm. In our approach, the network weights θ edge explainer V as well as the weight threshold vector to and adjacency threshold vector L are concurrently trained in an end-to-end way:
LAAACLT ( V ta,tat ta) L (ImA @ X), me ①) + C..
(8)
A m 9 arg min LAdaaLr O V. to tx) eto.t
where (() denotes the cross-entropy loss, and g(-) represents inferring the optimal masks using parameters that minimize the loss. To facilitate reading, we show the algorithm in Algo. 1.
Dynamic Pruning and Restoration. From Sec. 3.1 to 3.3, we systematacially haved elaborated on how AdaGLT helps to find adaptive and automated wining tickets. The adaptiveness and automa- tion of the GLT algorithms, are at present obscured by one cloud (dynamic sparsification) In this part, we will explain how a pruned element can be restored through gradient updates. Specifically, considering a layer's adjacency matrix or weight (unified as Q E R RNXM), with its threshold vector denoted as t E I the resulting pruning mask is represented as m E RNNM XM At the n-th epoch, if the value Qi (i.e. edge score weight value) satisfies Qij < 4. then mij O. Although this element is pruned in this epoch, during the gradient backpropagation process, it can still be dynamically revived by the gradient, subject the following conditions:
[Q.I -, ( [8c 0t:
-aC)
aC)
ΣΣ
Oc 8Qm
T Tex (T(t, Qrq)) (8, + 1)8%
(10)
[QQ;
(1 exp exp (T(L, Qpa)))²²
where a denotes the learning rate. It can be observed that the restoration of an element depends on the joint update of Qiy and t,. During the collaborative optimization between element values and thresholds, the optimal sparse structure for both the graph and weights is dynamically obtained.
3.4 MODEL SUMMARY & THEORETICAL DICUSSIONS
After introducing the model details, we further offer theoretical guarantee for our layer-adaptive sparsification grounded in the well-established Graph Neural Tangent Kernel (GNTK) theory, which pertinent to deep GNNs (Huang al., 2021). The GNTK can be formally defined as:
X)( Σ
Vahl (o (X)V&N (X)" E RRN,
(11)
where (9) denotes the embedding representation at layer I. is widely recognized that the GNTK plays central role in optimizing infinitely-wide GNNs, as documented in various studies (Jacot et al., 2018; Huang et al., 2021). Specifically, a positive minimum eigenvalue is indicative of the successful training of the corresponding GNN through gradient descent. Conversely, the inability to achieve a minimal training еттоr suggests the presence of a zero or negative minimum eigenvalue. The propagation of GNTK with respect to graph convolution can be expressed as follows. With more compact expression when the tangent kernel is bacterized, we have k()) ((k((-1), where E N2 and G N xx is the operation matrix for GNTK propagation. By looking at (()) with 1 tends to infinity, we scrutinize the efficacy of layer-adaptive sparsification in mitigating the prevalent issue of over-smoothing.
Theorem 1. Denote smallest singluar value of (D) by oo Suppose that operation matrix (())
has the same singlular vectors, and d! satifies do (1) 1 a', where O < 1. Then, the smallest eigenvalue of GNTK is greater than zero as the depth of GNN tends to infinity, i.e., lim Ao ()( O.
Theorem states that as the depth tends to be infinity, the GNTK can still have a positive smallest eigenvalue, which implies that the corresponding GNN can be trained successfully. This result is op- posite to the case without graph sparsification (Huang et al., 2021), demonstrating the effectiveness of layer-wiss sparsification. We have provided detailed proofs in Appendix E.

---

Published as a conference paper at ICLR 2024
4 EXPERIMENTS
In this section, we conduct extensive experiments to answer the following research questions: RQI: How effective proposed AdaGLT algorithm in searching graph lottery tickets? RQ2: What is the scalability of AdaGLT on deeper GNNs? RQ3: Can AdaGLT scale up to large-scale datasets?
4.1 EXPERIMENTAL SETUPS
Datasets. To comprehensively evaluate AdaGLT across diverse datasets and tasks, we opt for Cora, Citeseer, and PubMed (Kipf& & Welling, 201 for node classification. For larger graphs. we choose Srbn-AArxii/Protein/PProouc (Hu al., 2020) for node classification and Ogbl-Collab for link prediction. Detailed dataset statistics can be found in Appendix F.
Backbones & Parameter Settings. We conduct comparative analyses between AdaGLT and ventional GLT (Chen et al., 2021b) and TGLT (Hui et al., 2023) in all available scenarios. For Cora, Citeseer, and PubMed, we employ GCN (Kipf & Welling, 2017b), GIN (Xu et al., 2019), and and Ogbl-Collab, we em-
GAT (Veličković et al., 2018) as backbones. For ploy DeeperGCN (Li et al., 2020a) as the backbone, while for Oghn-Produee we opt for Cluster- GCN (Chiang et al., 2019). More experimental details are specified in Appendix G.
4.2
CAN AdaGLT FIND GRAPH LOTTERY TICKETS? (RQI)
To answer RQI, conduct comparative analysis between AdaGLT and existing methodologies, including UGS, TGLT, and random pruning, on the node classification tasks. The results on Cite- seer and PubMed are presented in Fig. 4, and those Cora are displayed in Fig. 9. From the experimental results, we can make the following observations (Obs):
Obs 1. AdaGLT consistently outperforms TGLT, UGS, and random pruning. Across Cora, Cite- seer, and PubMed datasets, AdaGLT successfully identifies graph lottery tickets with graph sparsity
GCN
GIN
GAT
Aucuary (Citsstr)
70
70
60
Random
Random
Random
UGS
UGS
UGS
50
50
40
AdoGLT
40
AdaGLT
40
AdGGLT
1-17%
10
20
30
60
50
60
10
40
50
60
10
20
30
40
50
60
80
Graph Spansity (%)
Graph Sparsity (96)
Graph Spansity (96
Accrayy (Citesea)
20
Random UGS
Random
Random UGS
UGS
50
TGLT
TGLT
40
AdoGLT
50
AdoGLT
AdaGLT
10
20
30
40
50
60
S0
90
100
10
20
30 40
50
00
80
90
100
10
20
30 40
50
60
TO
30
90
100
Weight Spansity (96)
Weight Sponsity (%)
Weight Spansity (%)
Accuncy (PibhMed)
80
50
Random UGS
Romdom
Random
20
75
UGIS
75
UGGS
TGLT
TGLT
IGLT
60
AdaOLT
70
Graphi Spansity (%)
20
30
40
50
60
70
Graph Sparsity (3))
20
50
60
50 Craph Spanily (%)
30
40
60
Accuracy (PulaMeel)
3n
Random
75
Random
Rondon
70
TGLT
20
TGLT
TGLT
AdoGLT
AdaGLT
AdxüLT
60
A=1.%%
A=3%
70
A=09%
10
70
100
20
100
Weight Spusily (%)
Weight Sparsily (%)
Weight Spansily (%)
Figure 4: Results of node classification over Citeseer/PubMed with GCN/GIN/GAT backbones. Black dash lines represent the baseline performance. Marker m. and * indicates the last GLT that reaches higher accuracy than the original model in the sparsification process of UGS, TGLT, and AdaGLT, respectively. A quantifies the percentage by which our AdaGLT method outperforms the state-of-the-ar GLT methods.

---

Published as a conference paper at ICLR 2024
Table 1: The performance comparison between TGLT and AdaGLT in discovering GLTs GAT backbone across various graph sparsity settings (10% - 60%) and GNN layer configurations (4 + 16 layers). Cells highlighted in red and blue correspond to winning tickets found by TGLT and AdaGLT, respectively.
Graph Sparsity
Method
Cora
Citeseer
PubMed
12
16
16
12
Baseline
78.20
78.08
76.12
75.53
69.82
67.50
67.40
67.56
78. 80.10
76.82
76.30
76.81
TGLT
66.62
78.11
67.79
60.90
61.88
778.62
17.00
'6.779
61.22
10%
AdaGLT
79.82
78.77
77.21
74.28
69. 88
67.67
68 11
67 99
78. 13
78. 19
77. 76
75.29
20%
TGUT
73.70
78.80
40.79
36.77
69.80
56.88
58.10
53.33
78.30
69.88
68.49
50.27
AdaGLT
78.61
78.22
70. 88
75.00
70.03
03
68.30
67. 2-1
08 03
78. 14
78.23
76.80
73.03
30%
TGLT
70.84
76.22
44.83
42.88
66.21
55.45
53.42
47.99
75.07
65.98
59.42
58.60
AdaGLT
78.39
78.48
76.70
72.75
69.91
67.39
07.85
90
79
74.99
70.47
40%
72.60
722-11
11.
"79.77
60.82
17.80
30.88
19
21
68
80
69. 72
"65711
AdaGL7
77.33
74.91
74.30
69.98
69
67,50
67.58
65 33
78
74.39
71.26
TGLT10033
10.007"111:8
15:80
61.31
48.
77
51.62
15 90
66
23
68.
71
63.222
"60333
30%
Ada.L1
77.11
75.07
73 18
72. 60
69
97
64.10
65.31
64 68
77 42
76 90
75.30
74.95
60%
TCLT)
70.60
66:30
37
37.74
37:26
32.37
54.40
50.85
47 28
62.08
66.07
63.66
60.75
AdaGL7
70.97
75.00
72.29
71.88
68.13
64.98
64.34
60.97
75.82
73.23
69.47 69.01
from 23% to 84% and weight sparsity from 87% to 99%, all while sustaining performance. Notably, AdaGLT can find winning tickets on GCN for Citeseer, whose graph and weight sparsity separately reach 44% and 95%, significantly surpassing TGLT's 26% and 23%.
Obs 2. AdaGLT shows particular efficacy in uncovering sparse graphs. While weight pruning has been well developed, attaining GLTss with sufficient graph sparsity remains challenging (Wang et al., 2022). PubMed is often considered more robust against graph pruning, whereas the smaller-sized Cora and Citeseer are deemed more sensitive (Chen et al., 2021b; Wang et al., 2023b). It is worth noting that AdaGLT outperforms TGLT in terms of graph sparsity, achieving improvements of 26% and 18% on Citeseer and Cora, respectively. Particularly remarkable is our method's 's ability to prune 80% of edges when applied to GAT on Citeseer without any performance deterioration.
Obs 3. The GNN backbone intricately affects graph sparsity attainment. While AdaGLT consistently identifies GLTs with weight sparsity over 90%, its performance with graph sparsity relies more on the specific GNN structure. Concretely, in GAT, GLTs are found with graph sparsity over 65%, whereas those in GIN do not exceed 55%. We attribute this to GAT's attention-based aggregation, which adapts during the edge pruning process. However, as for GIN, its aggregation of outputs from all layers amplifies the information loss caused by edge pruning.
4.3 CAN AdaGLT HANDLE DEEPER GNNs? (RQ2)
Tab. and Tab. 6 to 10 present comparison between TGLT and AdaGLT GCNRRsGGCN/GTT backbones, with the number of GNN layers increasing from 4 to 16, graph sparsity from 10% to 60%, and weight sparsity from 10% to 90%. Our findings and insights are summarized below:
Obs 4. The increase in the number of GNN layers poses challenges for identifying GLTs, In Tab. 1, both TGLT and AdaGLT exhibit reduction in the number of lottery tickets as # of layers increases. Under 4-layer settings, the sparsity of the uncovered tickets is roughly similar to that on 2-layer GNNs. However, on 16-layer GNNs, both methods fail identify extremely sparse GLTs.
Obs 5. AdaGLT excels at discovering GLT's in deep GNNs. In Tab. 6 to 10, in comparison to the excellent performance observed in 2-layer GNNs, TGLT suffers setbacks in identifying GLTs. Even on the GCN backbone where it performs at its best, TGLT can barely identify tickets with graph sparsity of 20% and weight sparsity of 50%. In contrast, AdaGLT can identify GLTs with graph and weight sparsity exceeding 40% and 70% on Citeseer and PubMed across all settings.
4.4 CAN AdaGLT SCALE UP TO LARGE-SCALE DATASET? (RQ3)
Fig. 5 and Fig. 10 to 13 illustrate the performance of AdaGLT on DeeperGCN across depths ranging from 4 + 28 layers, evaluated on Ogbn- Arriv//Prrtoiins and Ogbl-Collab. We can list observations:
Obs 6. AdaGLT is capable of learning layer-wise sparse graph structures. As depicted in Fig. 6, the GLTs discovered by AdaGLT exhibit a progressively sparser graph topology across layers, with their graph sparsity increasing from 16% to high 70% across layers.
8

---

Published as a conference paper at ICLR 2024
85
80
45
Accuray
Hitse
65
Random
70
Randorn
30
35
Random
10
35
EGS
60
TGLT
65
TOET
20
TGLT
ADGILT
60
ADGGLL
AdKILT
10
20 30 40 50
10 20 30 40 Ogion Proteins
10
20 30 40 50 60 Oghi-Collai
Agin-Arxiv
Figure 5: The performance of AdaGLT compared with UGS, TGLT and random pruning on 12-layer DeeperGCN with gegbn-Ariv/Proteeen and Ogbl-Collab. Black dashed lines represent the bascline performance.
Figure The percentage re- maining edges at each layer of 12-layer DeeperGCN after ap- plying AdaGLT
Obs 7. AdaGLT can scale up to large graphs. As depicted in Fig. and Fig. 10 to 13, AdaGLT consistently outperforms TGLT and UGS. In line with the findings from Obs 6, with the increase in the number of GNN layers, TGLT and UGS struggle to find high graph sparsity graph lottery tickets. In contrast, AdaGLT exhibits greater robustness the number of layers, surpassing TGLT by 21 %, 7%, and 1 11% in graph sparsity with the 28-layer setting, respectively.
4.5 ABLATION STUDY
Effects of Threshold Level. In our comparison across different threshold levels on Cora, Citeseer, and PubMed, depicted in Fig. and we have made several noteworthy observations. First, on small graphs like Cora, the threshold matrix consistently outperforms the threshold scalar/vector (with GLTs of over 40% graph sparsity and 99% weight sparsity). This superiority can be attributed to its ability to adjust the threshold element-wisely; Second, when applied to larger graphs like Citeseer and PubMed, the threshold vector exhibits better performance, especially in sparsifying the graph. We believe this is because the threshold vector strikes a balance between precision and parameter efficiency. Unlike the threshold scalar, it does not uniformly apply a single threshold across the entire matrix. Additionally, it avoids introducing excessive parameters like the threshold matrix during training. In summary, we adopt the threshold vector for all experiments.
Settings
Graph Sparsity
Datasel Estimator
20%
30%
40%
50%
60%
Aoauary (Cor))
70
STE
80.6
79.8
80.0
78.7
74.5
600
Scalor
Random
Scalar
Random
+GCN
Cora
SR-STE
LTF
80.4
80.6
78.8
80.1
79.2
77.7
78.9
74.4
74.4
50
Matrix
STE
69.7
69.6
68.4
67.2
Citesoer
40
Vector
Vector
+GIN
SR-STE
LTE
69.8
69.5
69.4
69.4
68.0
68.5
68.2
67.8
67.0
66.7
0
40 Graph Sparsity
20
30
50
60
20
40
60
80
100
Weight Sparsity
Table 2: Ablation study different gra- dient estimators over different datasets and backbones. Cells highlighted in blue repre- sent the performance of found GLTs.
Figure 7: Ablation study different threshold levels (i.e. threshold scalar, vector, and matrix) with GCN on Cora dataset. Black dash lines represent the baseline performance.
Effects of Gradient Estimator. To assess the sensitivity of AdaGLT various gradient estimators, we compared STE with two other popular gradient estimators: Long-Tailes Estimator (LTE) (Xu & Cheung, 2019; Liu et al., 2020) and SR-STE (Zhou et al., 2021). As depicted in Tab. 2, the performance of different estimators is generally similar, demonstrating that AdaGLT is insensitive to the choice of estimators. More details can be found in Appendix K.
5 CONCLUSION
In this paper, we propose an adaptive, dynamic and automatic framework for identifying graph lottery tickets (AdaGLT) that unifies graph and weight sparsification in a dynamic and automated workflow and capable of winning layer-adaptive tickets. We provide theoretical substantiation for this layer-adaptive sparsification paradigm in the context of deep GNNs. To verify the effective- ness of AdaGLT, we conduct extensive experiments and ablations across different graph benchmarks, various backbones and depth settings of GNNs. Our experiments consistently demonstrate its periority over existing GLT methods. These findings shed light on automating the process of graph lottery ticket discovery and expanding the generality of such tickets.

---

Published as a conference paper at ICLR 2024
6 ACKNOWLEDGEMENT
This work was supported in part by the National Natural Science Foundation of China under Grant 62201389, the Shanghai Rising-Star Program under Grant 22YF1451200, the Guangzhou- HKUST(GZZ) Joint Funding Program (No. 2024A03J0620) and the Tongji University Undergraduate Innovation and Entrepreneurship Program (No. 2023 )
REFERENCES
Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating or propagating gradients through stochastic neurons for conditional computation. arXiv preprint arXiv: Iee::3388332 2013.
Daniele Calandriello, Alessandro Lazaric, Ioannis Koutis, and Michal Valko. Improved large-scale graph learning through ridge spectral sparsification. In International Conference on Machine Learning. pp. 688-698 697. PMLR, 2018.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: fast learning with graph convolutional networks via importance sampling. arXiv preprint / 2018.
Tianlong Chen, Jonathan Frankle, Shiyu Chang, Sijia Liu, Yang Zhang, Zhangyang Wang, and Michael Carbin. The lottery ticket hypothesis for pre-trained bert networks. Advances in neural information processing systems, 33:15834-15846, 2020.
Tianlong Chen, Yu Cheng, Zhe Gan, Jingjing Liu, and Zhangyang Wang. Data-efficient gan train- ing beyond (just) augmentations: A lottery ticket perspective. Advances in Neural Information Processing Systems, 34:20941-20055 2021a.
Tianlong Chen, Yongduo Sui, Xuxi Chen, Aston Zhang, and Zhangyang Wang. A unified lottery ticket hypothesis for graph neural networks. In International Conference on Machine Learning, pp. 1695-1706 PMLR, 2021b.
Xuxi Chen, Zhenyu Zhang, Yongduo Sui, and Tianlong Chen. Gans can play lottery tickets too. arXiv preprint arXiv:2106.00/33 2021c.
Dawei Cheng, Chen Chen, Xiaoyang Wang, and Sheng Xiang. Efficient top-k vulnerable nodes detection in uncertain graphs. IEEE Transactions on Knowledge and Data Engineering, 2021.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery amp; Data Mining, pp. 257-266, 2019,
doi: 10.1 00.144//2925000333099
FR Chung and FC Graham. Spectral graph theory, vol 92 american mathematical soc. 1997.
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. Advances in Neural Information Processing Systems, 13:13260-13271, 2020.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances neural information processing systems, 29, 2016.
Shaojin Ding, Tianlong Chen, and Zhangyang Wang. Audio lottery: Speech recognition made litra-higttweight, noise-robust, and transferable. In International Conference on Learning Repre- sentations, 2021.
Yifan Duan, Guibin Zhang, Shilong Wang, Xiaojiang Peng, Wang Ziqi, Junyuan Mao, Hao Wu, Xinke Jiang, and Kun Wang. Cat-gnn: Enhancing credit card fraud detection via causal temporal graph neural networks. arXiv preprint 24t::22002144000 2024.
Talya Eden, Shweta Jain, Ali Pinar, Dana Ron, and C Seshadhri. Provable and practical approxima- tions for the degree distribution using sublinear graph samples. In Proceedings of the 2018 World Wide Web Conference, pp. 449-458. 2018.
10

---

Published as a conference paper at ICLR 2024
Utku Evci, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen. Rigging the lottery: Making all tickets winners. In International Conference on Machine Learning, pp. 2943-2952. PMLR, 2020.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. arXiv preprini arXiv: 1803.03635, 2018.
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M Roy, and Michael Carbin. Stabilizing the lottery ticket hypothesis. arXiv preprint arXiv: DeXiiv:9903.00 119903001111 2019.
Yuan Gao, Xiang Wang, Xiangnan He, Huamin Feng, and Yongdong Zhang. Rumor detection with self-supervised learning on texts and social graph. Frontiers of Computer Science, 17(4): 174),, 2023.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pp. 1024-1034, 2017.
Fo-Wei Harn, Sai Deepthi Yeddula, Bo Hui, Jie Zhang, Libo Sun, Min-Te Sun, and Wei-Shinn Ku. Igrp: Iterative gradient rank pruning for finding graph lottery ticket. In 2022 IEEE International Conference on Big Data (Big Data), pp. 931-941 IEEE, 2022.
Yang He, Guoliang Kang, Xuanyi Dong, Yanwei Fu, and Yi Yang. Soft filter pruning for accelerating deep convolutional neural networks. arXiv preprint arXiv: /808. 06866, 2018.
Yihui He, Xiangyu Zhang, and Jian Sun. Channel pruning for accelerating very deep neural net- works. In Proceedings of the IEEE international conference on computer vision, pp. 1389-1397, 2017.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning graphs. arXiv preprint arXiv:2005.00689 2020.
Wei Huang, Yayong Li, Weitao Du, Jie Yin, Richard Yi Da Xu, Ling Chen, and Miao Zhang- Towards deepening graph neural networks: gntk-based optimization perspective. arXiv preprint 1oXiv:2103.03113. 2021.
Bo Hui, Da Yan, Xiaolong Ma, and Wei-Shinn Ku. Rethinking graph lottery tickets: Graph sparsity matters. In The Eleventh International Conference on Learning Representationss 2023.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- eralization in neural networks. Advances neural information processing systems, 31, 2018.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26. 2017, Conference Track Proceedings. OpenReview.net, 2017a. URL https:/ /ppprrevieeeeeeeeeeeeeeeeeeeeeee net/ forum?id==3304ay11
Thomas N. Kipf and Max Welling, Semi-Supervised Classification with Graph Convolutional Net- works. In Proceedings of the 5th International Conference on Learning Representations, 2017b.
Ron Levie, Federico Monti, Xavier Bresson, and Michael M Bronstein. Cayleynets: Graph con- volutional neural networks with complex rational spectral filters. IEEE Trunsactions on Signal Processing, 67(1)977-109 2018.
Guohao Li, Matthias Müllrr, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go as deep as cnns? In The IEEE International Conference on Computer Vision (0CCV)
Guohao Li, Chenxin Xiong, Ali Thabet, and Bernard Ghanem. Deepergen: All you need to train deeper gens. arXiv preprint arXiv:2006.07739, 2020a.
Guohao Li, Matthias Müller, Bernard Ghanem, and Vladlen Koltun. Training graph neural networks with 1000 layers. In International conference on machine learning, pp. 6437-6449. PMLR, 2021.

---

Published as a conference paper at ICLR 2024
Jiayu Li, Tianyun Zhang, Hao Tian, Shengmin Jin, Makan Fardad, and Reza Zafarani. Sgen: A graph sparsifier based on graph convolutional networks. In Pacific-Asia Conference on Knowledge Discovery and Data Mining, pp. 275-287. Springer, 2020b.
Yongquan Liang, Qiuyu Song, Zhongying Zhao, Hui Zhou, and Maoguo Gong. Ba-gnn: Behavior- aware graph neural network for session-based recommendation. Frontiers of Computer Science, 17(6):176613 2023.
Chuang Liu, Xueqi Ma, Yibing Zhan, Liang Ding, Dapeng Tao, Bo Du, Wenbin Hu, and Danilo P Mandic. Comprehensive graph gradual pruning for sparse training graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 2023.
Junjie Liu, Zhe Xu, Runbin Shi, Ray CC Cheung, and Hayden KH So. Dynamic sparse train- ing: Find efficient sparse network from scratch with trainable masked layers. arXiv preprint 066:02000.00670, 2020.
Xiangeheng Liu, Tianyi Wu, and Guodong Guo. Adaptive sparse vit: Towards learnable adaptive token pruning by fully exploiting self-attention. arXiv preprint arXiv:2209. 13802, 2022.
Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network. Advances in neural information pro- cessing systems, 33: 13:19620-19631 2020.
Frank McSherry. Spectral partitioning of random graphs. In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pp. 529-537. IEEE, 2001.
Decebal Constantin Mocanu, Elena Mocanu, Peter Stone, Phuong H Nguyen, Madeleine Gibescu, and Antonio Liotta. Scalable training of artificial neural networks with adaptive sparse connec- tivity inspired by network science. Nature communications, 91):2388, 2018.
Sai Prasanna, Anna Rogers, and Anna Rumshisky. When bert plays the lottery, all tickets are win- ning. arXiv preprint arXiv:2005.00561, 2020.
Md Khaledur Rahman and Ariful Azad. Triple sparsification of graph convolutional networks with- out sacrificing the accuracy. arXiv preprint arXiv:2208. 20t.022900.09999,, 03559, 2022.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. arXiv preprint 19Xi:: 2019.
2019.
Yongduo Sui, Xiang Wang, Tianlong Chen, Xiangnan He, and Tat-Seng Chua. Inductive lottery ticket learning for graph neural networks. 2021.
Yongduo Sui, Xiang Wang, Jiancan Wu, Min Lin, Xiangnan He, and Tat-Seng Chua. Causal tention for interpretable and generalizable graph classification. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 1696-1705, 2022.
Shyam A Tailor, Javier Fernandez-Marques, and Nicholas D Lane. Degree-quant: Quantization- aware training for graph neural networks. arXiv preprint arXiv:2008.0500) 2020.
Guanzhong Tian, Jun Chen, Xianfang Zeng, and Yong Liu. Pruning by training: novel deep neural network compression framework for image processing. IEEE Signal Processing Letters, 28:344-348, 2021.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. stat, 1050:20, 2017.
Petar Veličković, Guillem Cucurall, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Elli Voudigari, Nikos Salamanos, Theodore Papageorgiou, and Emmanuel J Yannakoudakis. Rank degree: An efficient algorithm for graph sampling. In 2016 JEEE/ACM International Conference Advances in Social Networks Analysis and Mining (ASONAM), pp. 120-129. IEFF, 2016.
12

---

Published as a conference paper at ICLR 2024
Kun Wang, Guohao Li, Shilong Wang, Guibin Zhang, Kai Wang. Yang You, Xiaojiang Peng, Yuxuan Liang, and Yang Wang. The snowflake hypothesis: Training deep gnn with one node one receptive field, 2023a.
Kun Wang. Yuxuan Liang, Pengkun Wang, Xu Wang, Pengfei Gu, Junfeng Fang, and Yang Wang. Searching lottery tickets in graph neural networks: A dual perspective. In The Eleventh Interna- tional Conference on Learning Representations, 2023b. URL https: https////eeeeeeeee.ee.mme nett/
Forum?id-Dvs-
Li Wang, Wei Huang, Miao Zhang, Shirui Pan, Xiaojun Chang, and Steven Weidong Su. Pruning graph neural networks by evaluating edge properties. Knowledge-Baud Based Systems, 256:109847, 2022.
Yuwen Wang. Shunyu Liu, Kaixuan Chen, Tongtian Zhu, Ji Qiao, Mengjie Shi, Yuanyu Wan, and Mingli Song, Adversarial erasing with pruned elements: Towards better graph lottery ticket. arXiv preprint arXiv:2308.029) 2023c.
Wei Wen, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Learning structured sparsity in deep neural networks. Advances in neural information processing systems, 29, 2016.
Yiqing Xie, Sha Li, Carl Yang, Raymond Chi- Chi-Wing Wong, and Jiawei Han. When do gnns work: Understanding and improving neighborhood aggregation. In IJCAI'20: Proceedings of the Twenty-Nint International Joint Conference Artificial Intelligence, (IJCA)) 2020, volume 2020, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
Zhe Xu and Ray CC Cheung. Accurate and compact convolutional neural networks with trained binarization. arXiv preprint arXiv: 1366, 2019.
Changdi Yang, Pu Zhao, Yanyu Li, Wei Niu, Jiexiong Guan, Hao Tang, Minghai Qin, Bin Ren, Xue Lin, and Yanzhi Wang. Pruning parameterization with bi-level optimization for efficient semantic segmentation on the edge. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pp. 15402-15412, 2023.
Haoran You, Zhihan Lu, Zijian Zhou, Yonggan Fu, and Yingyan Lin. Early-bird gens: Graph- network co-optimization towards more efficient gen training and inference via drawing early-bird lottery tickets. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp- 8910-8918, 2022.
Yuning You, Tianlong Chen, Zhangyang Wang, and Yang Shen. L2-gen: Layer-wise and learned efficient training of graph convolutional networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 2127-2135, 2020.
Guibin Zhang, Yanwei Yue, Kun Wang, Junfeng Fang, Yongduo Sui, Kai Wang, Yuxuan Liang, Dawei Cheng, Shirui Pan, and Tianlong Chen. Two heads are better than one: Boosting graph sparse training via semantic and topological awareness. arXiv preprint arXiv:2402.01242, 2024.
Muhan Zhang and Yixin Chen. Inductive matrix completion based on graph neural networks. arXiv preprint arXiv: I 1904. 12058, 2019.
Zhenyu Zhang, Xuxi Chen, Tianlong Chen, and Zhangyang Wang. Efficient lottery ticket finding: Less data is more. In International Conference on Machine Learning, pp. 12380- 12390. PMLR, 2021.
Cheng Zheng, Bo Zong, Wei Cheng, Dongjin Song, Jingchao Ni, Wenchao Yu, Haifeng Chen, and Wei Wang. Robust graph representation learning via neural sparsification. In International Conference on Machine Learning, pp. 11458 1468. PMLR, 2020.
Aojun Zhou, Yukun Ma. Junnan Zhu, Jianbo Liu, Zhijic Zhang, Kun Yuan, Wenxiu Sun, and Hong- sheng Li. Learning n: M fine- -reiggr structured sparse neural networks from scratch. In Interna- tional Conference on Learning Representations, 2021.
13

---

Published as a conference paper at ICLR 2024
A
NOTATIONS
Table 3: The notations that are commonly used in Methodology (Sec. 3).
Notation
Definition
(V, 33
Input graph
Input adjacency matrix
Input features
θ
θ
represent the weight matrices of GNN
Eg
(0)
represent threshold vectors for weight sparsification
A
A
(0)
(1-1)
represent threshold vectors for graph sparsification
mg
m
m
m
represent weight pruning masks
MA
m
(1)
m (0)
m A
A represent the graph pruning masks
Stj
Edge between u; and v;
V/ {Wx, Wy denotes parameters of edge explainer
O
Embedding representation after 1-th GNN embedding layer
(0)
Sparsified weight matrix [-th GNN layer
A
Sparsified adjacency marix at I-th GNN layer
B DETAILS ON THRESHOLD LEVEL
In addition to the threshold vector, we can also employ a threshold scalar or threshold matrix to learn adaptive thresholds for each weight matrix adjacency matrix (Liu al., 2020). Specifically, considering layer's adjacency matrix or weight (unified as Q E RRMM,,,, we define its threshold scalar and threshold matrix as and T E NxM respectively. The calculation of the binary pruning mask is as follows:
for threshold scalar 1 > Tal for threshold matrix
1 > f)
mij
(12)
where denotes the resulting binary pruning mask. We conduct comparative experiments on Cora, Citeseer, and Pubmed datasets assess the reliability and effectiveness of thresholds various levels.
70
80
80
Aocuracy (Citester)
Accuracy (Publedd)
65
75
60
75
60
70
Random
50
Random
Random
70
Random
55
Scalar
Scalar
65
Scalar
Scalar
Matrix
Matrix Vector
Matrix
Matrix
50
65
Vector
60
Vector
Vector
45 20 30 40 50 60 Graph Sparsity
0 20 40 60 80 100
0
30
50
70
20 40 60 80 100 Weight.Sparsigg Sparsity
Weight Sparsity
Graph Sparsity
Figure 8: Ablation study on different threshold levels (i.e. threshold scalar, vector, and matrix) with GCN on Citescer/PubMed datasct. Black dash lines represent the bascline performance.
14

---

Published as a conference paper at ICLR 2024
C ALGORITHM FRAMEWORK OF AdaGLT
In this section, we conclude the overall algorithm framework of AdaGLT in Algo. 1. During each epoch, first compute the edge scores with the edge explainer (Eq.3.2) and calculate the pruning masks for weight and adjacency matrix in a layer-wise manner (Eq. 2 & 7). After that, we forward the network with sparsed weights and graphs and updates parameter through gradient estimators. It is important to note that, unlike conventional network training, our objective is not to attain the optimal network parameters but rather achieve the optimal sparse structure (i.e. m mÿ). We draw the optimal sparse structure from pruning masks with sparsity levels within the desired range and with the best performance on the validation set.
Algorithm 1: Algorithm workflow of AdaGLT
Input : 9 = (A, X). GNN model f(g. @o), GNN's initialization Og threshold vectors to and t., step size 17, target graph sparsity $g and weight sparsity se, sparsity interval width Output: GLT f (ImA @ A, X). mo +)
for iteration + 1 to N do
Compute edge scores 8tj 1 (i,)EE En ENirE exp (99 (x)/x)))/ (Eq. 3.2)
(xp (x, /w/
for layer 1 t to L; do
Dynamic & Automated Pruning
mo. (1)
(1)
11 ta, (Eq.
m A.d 1 [sss A. I 1-1
m (8)
(Eq. 7)
Layer-adaptive
A.3
end
Forward f(;, my mm θ) with G = {ma o A, X) to compute the loss Laasour in Eq. 3.3. Backpropagate to update 0+11 +
1i+1 + v, v, LAGSCLT
Update to and ta with STE according 2q.
b Dynamic restoration
11 Compute current graph and weight sparsity og and co.
if Cg Sgl S and (ca sol S then
13
Update the optimal mask m mă + ma. my (if with higher validation score)
14 end
Rewind GNN's weights to O
16 Retrain the model with fixed m and mi.
D COMPLEXITY ANALYSIS
Following Chen et al. (2021b), we exhibit the complexity of AdaGLT. The inference time com- plexity of UGS is defined as O (L I|mA A D L x ||mollo x|V|xx=),, where L is
the number of layers, llma O All is the number of remaining edges in sparse graph, D is
the dimension of feature and |V is the number of nodes. The inference time complexity of
AdaGLT can be defined as O L Σ, m (1) @Al1 DD+Ex + L |lmmlll 1 x22
O A represents the remaining edges across all layers and E x denotes the complexity of calculating edge scores according Eq. 3.2. It is worth mentioning that we solely compute edge scores and their similarities for edges eij where (i.j) E E, thus avoiding the ((N2) complexity associated with all-pat alir similarity computations.
where Σ1 m (1)
E PROOF OF THEOREM 1
Proof of Theorem 1. We first study the propagation of GNTK with respect graph convolution. The expression of graph convolution is governed as follows:
( = [((1) +1
Σ (-))
(13)
vEA(u)uua
15

---

Published as a conference paper at ICLR 2024
where u, y denote the node index of the graph, and Uu is the union of node and its neighbors.
Equation (13) reveals the node feature aggregation operation among its neighborhood according to a GCN variant (Hamilton et al., 2017). Based on the definition of NTK (11), recursively formulate the propagation of GNTK in the infinite-width limit. As information propagation a GCN built aggregation (13), the corresponding formulas of GNTK expressed follows,
(u, w') [V(') +1 W(r)++1
Σ E
k
(E)( (""N'
In order to facilitate calculation, we rewrite the above equation in the format of matrix, k
((-1)
where k(0) x2nx1, the result of GNTK being vectorized. Thus, the matrix operation G R=²x=" xn=
Now we consider the impact of graph sparsification on the operation matrix G Different from what has been studied in (Huang et al., 2021) the operation matrix G is irreducible and aperiodic, with a stationary distribution vector. Here we consider the graph sparsification technique. In this case, the operation matrix is no longer a transition matrix that corresponds to a Markov process.
To study the limit behavior the smallest eigenvalue of the GNTK, we make an SVD decomposition of the operation matrix in each layer as follows:
G U V("
where U and V are both orthogonal matrix. Because the operation matrix G is symmetric matrix, know that U V Based on assumption that that operation matrix G(), for every layer, has the same singular vectors, which means that:
U U
U
Then we can obtain the expression for GNTK at the final layer:
(1)
V
( ... D.
Then we know that the smallest singular value of k9)) is determined by the product's smallest singu- lar value. According to our assumption on the smallest singular value with respect layer number, ie. of = a a', we obtain that:
II - - (1-5) 8))
II
We would like to calculate the limit value as the depth of GNN tends to be infinity:
lim
O = [Pochhammer[3]]
which is a Quantum Pochhammer Symbol, and marked as QPochhammer. According to the prop- erty of Quantum Pochhammer Symbol, when < 3 < 1, we have that QPochhammer[3]] > As result, we claim that the smallest eigenvalue of GNTK is greater than zero depth tends to be infinity:
lim (k((()) 400
which completes the proof.
F DATASET DESCRIPTION
We conclude the dataset statistics in Tab. 4
16

---

Published as a conference paper at ICLR 2024
Table 4: Graph datasets statistics.
Dataset
Task Type
Craphs
Nodes
Edges
Ave. Degree
Features
Classes
Metric
Cora
Node Classification
2,708
5,429
3.88
1,433
Accuracy
Citeseer
Node Classification
3,327
4,732
1.10
3,703
Accuracy
PubMed
Node Classification
19,717
44,338
8,00
500
Accuricy
Ogba-ArXO
Node Classification
169,343
1,166,233
13.77
128
40
Accuracy
Ogbn-Proteing
Node Classification
132,534
39,561,252
$97.00
8
ROC-AUC
Ogbn- Products
Classification
2,449,029
65,95114
100
Accuracy
Ogbl- Ogbl-Collab Collab
Link Prediction
235,868
1,285,465
10.90
128
Hots@50
G DETAILS ON EXPERIMENT CONFIGURATIONS
Metrics. Accuracy represents the ratio of correctly predicted outcomes to the total predictions made. The ROC-AUC (Receiver Operating Characteristic-Aren Under the Curve) value quantifies the probability that a randomly selected positive example will have a higher rank than a randomly selected negative example. @i denotes the proportion of correctly predicted edges among the top 50 candidate edges.
Sparsity Ratio. We define the graph sparsity ratio sg and weight sparsity ratio so in a single graph as follows:
(f) A
m (1)
m
$g
1
||Allo
0
S6
L
|000
(14)
where || |lo represents the Lo norm counting the number of non-zero elements. other words, 8y represents the percentage of pruned edges out of all edges in the entire I. layers, while so signifies the percentage of pruned elements out of all elements in the complete set of weights.
Train-val-test Splitting of Datasets. For node classification in small- and medium-scale datasets, following the semi-supervised settings (Chen et al., 2021b), we utilized 140 labeled data points (Cora). 120 (Citeseer), and 60 (PubMed) for training, with 500 nodes allocated for validation and 1000 nodes for testing. In the context of deep GNNs, we take the full-supervised settings (Rong et al., 2019), which set 1000 nodes for testing, 500 nodes for validation and the others for training. The data splits for Ogbn-ArXiv. Ogbn-Proteins, Produccs, and Ogbl-Collab were provided by the benchmark (Hu et al., 2020). Specifically, for Ogbn-ArXiv, we train on papers published until 2017, validate on papers from 2018 and test on those published since 2019. For Ogbn- -gbn-Proteins, protein nodes were segregated into training, validation, and test sets based their species of origin. For Producso, we sort the products according to their sales ranking and use the top 8% for training. next top 2% for validation, and the rest for testing. For Ogbl-Collab, we employed collab- orations until 2017 as training edges, those in 2018 as validation edges, and those in 2019 as test edges.
Backbone settings. For node classification and link prediction tasks on small- and medium graphs, we employ 2-layer GCN/GIN/GAT backbones within the framework of standard-depth GNNs. In the context of deeper GNNs, we utilize 4/8/12/16-layee GCN/ResGCN/GAT backbones. For large-scale graphs including Arxi///riv/rotteins and Ogbl-Collab, we adopt DeeperGCN (Li et al., 2020a) of 4/12/20/28 layers. We choose 4/8 4/8-layer Cluster- GCN for
For comparison with sfatc-of-the-art GLT methods, we choose UGS (Chen et al., 2021b) and TGLT (Hui et al., 2023), which the most efficient GLT methods to our best knowledge. For UGS, we directly adopt the source code provided by the authors and stick to their original parameter settings. For TGLT, carefully reproduced their model from the description in the paper.
Hyperparamters. We conclude the detailed hyperparameter settings in Tab. 5.
H ADDITIOANL EXPERIMENTS TO ANSWER RQ1
Fig. 9 showcases the results of AdaGLT on Cora dataset with the GCN/GIN/GAT backbone.
17

---

Published as a conference paper at ICLR 2024
Table Detailed hyper-parameter configurations. 7g and to denotes the coefficient attached R(ta) and
((to)) respectively.
Dataset
Model
Epochs (train/retain)
Optimizer
leurning rate
Weight Decay
GCN
400/300
Adam
0.01
8e-5
5e.5
0.001
Cora
GIN
400/300
Adam
0.002
8e-5
2e-6
0.002
3
GAT
400/300
Adam
0.001
8c-5
0.001
GCN
400/300
Adam
0.01
Se-4
9e-5
0.002
Citeseer
GIN
400/300
Adam
0.002
5e-4
2e-6
0.002
2
400/300
Adam
0.001
5e-4
0.001
GCN
500/400
Adam
0.01
5e-4
5e-5
0.001
PubMed
GIN
300/300
Adam
0.002
Se-4
0.002
GAT
500/400
Adam
0.001
Se-4
0.001
Ogbn-Arxiv
800/600
Adam
0.01
1c-12
Oghn- Min--Proteins
DeeperGCN
200/150
Adam
0.01
0
7e-8
3e-13
3
Oghi-Collab
800/500
Adam
0.01
0
1e-8
1e-12
Ogbn- Ogbn-Product Product
Cluster-GCn Cester-GCC
50/50
Adam
0.001
0
1e-8
Se-12
2
1-%
Accuracy (Coral
50
80
70
Randum
60
UGS
UGS
70
UGS
50
TGLT
50
KiLT
TGLT
AdbrLLT
60
40
50
60
10
20
30
Graphh Sparsity (%)
Granh Spersity (9)
Craph Spansity (%6
80
Hoxunyy/Co (Cora)
30-
20
Random
70
Random
Random
Acouncy
UGS
A-2%%
60
AdatLLT
AdaGiL
AdaGLT
30
50
50
60
80
10
50
60
70
901
100
20
50
100
Weight Spursity (%)
Weight Spinityy (%)
Wight Sporsity (%6)
Figure 9: Results of node classification over Cora with GCN/GIN/GAT backbones. Black dash lines represent the baseline performance. Marker M. and * indicates the last GLT that reaches higher accuracy than the original model in the sparsification process of UGS, TGLT and AdaGLT, respectively.
18

---

Published as a conference paper at ICLR 2024
1 ADDITIOANL EXPERIMENTS TO ANSWER RQ2
We provide detailed experimental results of the performance comparison between TGLT and AdaGLT on deep GAT/GCN/ReSGCN (4 + 16 layers) in Tab. 6 to 10.
Table 6: The performance comparison between TGLT and AdaGLT in discovering GLTs GAT backbone across various weight sparsity settings (10% + 90%) and GNN layer configurations (4 + 16 layers). Cells highlighted in red and blue correspond to winning tickets found by TGLT and AdaGLT, respectively.
Weight Sparsity
Method
Corn
Citeseer
PubMed
8
12
16
4
12
16
8
12
16
Baseline
78.20
78.08
76.12
75.53
69.82
67.50
67.40
67.56
78.10
76.82
76.30
76.81
10%
TGLT
78.79
79.39
73.52
71.49
70.
67.79
68.10
67.08
78.64
77.91
77.09
76.92
AdaGLT
79.
78.27
76.84
76.98
69. 90
08 67
68.
67 00
78 43
78. 19
77.76 76
77.09
30%
TGLT
78.25
78.80
73.28
70.66
69.94
63.52
63.90
76.93
76.49)
73.66
AdaGLT
79.07
78.65
77.68
76,90
69.73
08.00 06
68. 64
68 70
78 24
77,80
77.
77.11
50%
TGLT
78.21
76.42
70.19
72.00
69.86 86
67. 73
64.49
60.70
78. 13
74.36
72.97
70.28
AdaGLT
78.14
75.00
69.93
67 63
76.23
70%
TGLT
Y3.74
13.63
70.06
70.88
67. 26
63 40
60.7
62. 89
74.48
69.08
685.11"
AdaGLT
78.89
78.14
72.70
70.85
69.88 88
67 07
67 63
66.92
77
73.19
72.43
TGLT
70.10
67.71
62.28
03.36
64.22
63. 19
35.46
64.76
66.
67.72
69.71
60:02
90%
AdaGLT
75.83
76.41
69.90
63.18
61183
61.50
62.68
60.13
76.03
72.28
69.58
67.46
Table 7: The performance comparison between TGLT and AdaGLT in discovering GLTs on GCN backbone
across various graph sparsity settings (10% + 60%) and GNN layer configurations (4 + 16 layers).
Graph Sparsity
Method
Cora
Citeseer
PuhMed
8
12
16
4
12
16
8
12
16
0%
Baseline
83.95
83.65
84.80
83.60
75.10
74.20
73.80
74.00
88.
81.40
85 60
83.10
10%
TGLT
78.09
78.74
76.08
75.09
69.90
67 83
67.62
66.88
78. .2
76.92
85.79
78.22
AdaGLT
84.25
84.87
84.82
81.28
75.58
74.
76.21
741 19
89 55
85.00
85.92
81.01
20%
TGLT
84.02
79.05
78.9
77.15
67.06
68.04
66.30
66.93
83.30
85.07
81.44
71.27
AdaGLT
86.65
79.15
78.08
76.45
75 23
72.22
69.40
68. 23
88 14
84.
77
85
77.68
30%
"GLTT"
19.33
711.66
66.35
66.15
63.21
63
39:50
55..62 62
85.87 87
82
22
79.70
"13.18"
AdaGLT
81.76
77.75
75.30
69.15
75.45
70.70
70.21
60.
89
85 59
85.73
75.01
40%
TGLT
"40.88
67
6...5
61.80
13.71
78.11
12.
773
AdaGLT
82.25
75.82
66.13
11.60
84.57
TGLT
6Y.75
68.13"
68.65
38.84
"4.17""3077
37 49740
72. 16
70.18
"8.27"""6677""
50%
AdaGLT
77.65
71.97
67.82
60.27
73.46
70.20
70.71
52.23
81.17
83.64
75.15
73.29
TGLT
60.65
45.89
38
69
13:25
51.07
23.81
16.50
14.30
66.16 18
65.16
64.64"
54.88
60%
AdaGLT
75.17
71.45
64.49
53.25
73.55
70.40
65.44
57.87
78.92
75.43
70.48
67.44
Table 8: The performance comparison hetween TGLT and AdaGLT in discovering GLTss on GCN hackhone across various weight sparsity settings (10% 90%) and GNN layer configurations (4 16 layers).
Weight Sparsity
Method
Cora
Citeseer
PubMed
8
12
16
4
12
16
8
12
16
0%
Baseline
83.95
83.65
81.80
83.60
75.10
74.20
73.80
71.00
88.
81.10
85 60
83.10 $3.10
TOLT
80.35"
80.85"
"3..88"
""1.85"""1
"1.39
75.00
43
866
"8.777
80.32
10%
AdaGLT
85.55
85.27
85.30
82.75
76.55
75
20.20
76.31
74.39
88
65.07
85.
84.
"TGLT"
$1.35
81.67
83.
33.69
883668
70.16
16
72
00
71'23
'88
29
82.09
885.78
81.91
30%
AdaGLT
85.34
85.65
68.668
81.35
76.35
74.91
75.62
74 88
89 21
85, 22
85 88.
83.71
50%
"GLTT"
78.91
78.97
80.03
"81:85
68.95
72.20
71:22
73.39
86.07
811.5
82.22
79.50
AdaGLT
85.75
84.53
83.90
81.15
76.66
76.00
76.32
74.00
88,
85.67
86.48
83.
70%
TGLT
77.45
75.85
79.08
76.84
65.72
68.17
67.80
66.91
78.21
78. 92
76.40
76.23
AdaGLT
84.83
8..15
80.80
78.25
75.53
74.
75.68
73.10
88
04
86.39
84.15
90%
TGLT
75.35
70.95
70.51
67.26
64.55
62.00
02.08
53.20
58.61
76.40
76. 11
72.27
70.09
AdaGLT
85.43
83.55
81.70
78.55
76.23
74 50
70.58
64.50
89.35
84.67
85.34
82.86
19

---

Published as a conference paper at ICLR 2024
Table 9: The performance comparison between TGLT and AdaGLT in discovering GLTs on ResGCN backbone
across various graph sparsity settings (10% + 60%) and GNN layer configurations (4 + 16 layers).
Graph Sparsity
Method
Cora
Citeseer
PubMed
8
12
16
12
Baseline
84.40
84.15
84.25
82.00
75.20
40
74.15
T3.45 15
87.30
85.50
84.40
87.20
10%
TGLT
80.20
79.15
79.54
80.25
73.21
72.25
73.29
69.88
87.49
85.91
84.69
86.74
AdaGLT
86
84.47
81.45
82
75. 40
76.27
75.11
75. 3G
88 21
86 08
84 96
87.81
20%
TGLT
79.70
77.85
76.75
76.95
69.50
07.73
07
71.17
63
87
05
00
80.47
82.65
AdaGLT
85
85.15
79.55
81.994
74.60
74.25
72.70
72 23
87.
85. 81
84 66
86.98
30%
TGLTT"
13.10
72
12:22
69.28
09
61..1
61.78
61160
61 05
85
82
TT. 26
88
06
"9.882"
AdaGLT
22
82
74.31
72.11
87
85.37
87.14
40%
TGLT
12.60
71:33
68. 15
68.32
70.91 93
61.72
57:13
80.62
78. 39
78. .50
AdaGLT
80.83
78.35
78.45
77.88
74.13
71.65
73.10
74.
87.4
85, 45.02
85.01
86.88
TGLT
72.90
73.35
74.95
64.77
60.31
66.55
61.32
63.55
75.14
72.33
69.56
50%
AdaGLT
79.11
76.55
75.25
75.75
70.40
74.47
72.26
71.85
83.90
85. 86
84 68
86.25
60%
TGLT
62.90
70.15
65.45
69:26
39.80
66 35
66.35
63.26
68 03
70.64
66.29
68.06
AdaGLT
75.10
73.55
72.75
74.15
71.90
73.06
71.13
71.37
83.81
82.19
82.12
83.61
Table 10: The performance comparison between TGLT and AdaGLT in discovering GLTs on ResGCN back- bone across various weight sparsity settings (10% - 90%) and GNN layer configurations (4 - 16 layers). Cells highlighted in red and blue correspond to winning tickets found by TGLT and AdaGLT, respectively.
Weight Sparsity
Method
Cora
Citeseer
PuhMed
8
12
16
4
12
16
12
16
0%
Baseline
84.40
84.15
84.25
82.00
75.20
74.40
74.15
73.45
87.30
85.50
84.40
87,
TGLT
"8T.4""
"82.664""""
"80:T6"
75:70
12.88
"88.88"""""
"86:68
"8":8"""""""""""""""
866.3
10%
AdaGLT
87.71
86.47
81.61
82.61
75.58
76.25
71.31
71.25
88
01.001
86.45
85.67
87.11
30%
TGLT
79.40
80.85
83.05
80.57
69.76
72.35
73.40
71.03
86.08
85.69
84.72
86. 14
AdaGLT
86:00
86.16
83.55
81.22
74.43
75.20
74.14
74.03
87.56
85. $5.89
85.10 10
88.01
50%
TGLT
79.23
79.12
79.83
80.25
69.21
70.45
73.30
70.44
83.18
80.58
82.30
844.30
AdaGLT
86.98
85.08
84.15
82.03
75.31
73.35
73.50
73.04
88 23
85 09
84 98
87.00 68
70%
"GLT
17.00
77.85
76.75
76.99
70.52
688
F1.77
65.21
83
12
80.81
79.38
80.20
AdaGLT
85
20.20
84.14
83.77
80,82
73.53
73.75
73.00
72.25
87.
85.
74
84, 76
87.03
90%
TGLT
12.60
71.11
12:28
69.9
68.32' 92
68
776
6-1.38
59'33
78. 12
78 60
"f1.75
AdaGLT
81.73
83.85
79.98
73.08
74.41
87.78
85.34
86.94
J ADDITIOANL EXPERIMENTS TO ANSWER RQ3
Fig. 10 to 13 comprehensively illustrate the performance comparison of AdaGLT with TGLT, UGS, and random pruning on DeeperGCN at 4, 12, 20, and 28 layers, across AgbivArxiv. Ogbn- OgonnPrrs and Ogbl-Collab datasets. Fig. 14 illustrates the sparsity distribution of GLTs uncovered by AdaGLT under different settings and datasets.
Tab. 11 demonstrate the performance of AdaGLT on Ogbn-Producee with 4- and 8-layer Cluster- GCN. It can be observed that (1) AdaGLT can scale up to large graphs like effectively find GLTs, while UGS completely fails. (2) Discovering winning tickets within shallow GNNs is more feasible. Under 30% graph sparsity, AdaGLT successfully identifies winning tick- ets at 4-yayer GCN, while struggling to achieve baseline performance on an 8-layer GCN. This observation aligns with our findings in Sec. 4.3.
Products and
Table 11: The performance of AdaGLT on Ogbn- Products with 4- and 8-layer Cluster-GCN, We report the mean accuracy = stdev of runs.
Layer
4 (Baseline=79.23
8
(Baseline=78.822
Graph Sparsity
10%
30%
50%
10%
30%
50%
UGS
78. 78.4440.55
74.67+0.62
73.05
76.30
72.1341.25
71.32_1.14
AdaGLT
80.35
79.67 10.86
76.46_ 0.69
80.22 1o.78
78. 13
74.62_
20

---

Published as a conference paper at ICLR 2024
Ogba-ArXiv
Prot-Proteins
Ogbi-Collah
55.
A-15%
Random
Randors
Hitse:50
Randern
65
UGS
UGS
TGLT
TGLT
TGLT
60
AdsaLT
AdaiLT
20
AdaiLT
10
20
30
48
30
60
10
20
30
40
30
60
20
40
Graph Sparsity (%)
Graph Spursity (%)
Graph Spursity (%6
72
Rc
Accurazy
16
Hins
Randoca
Random
Random
UGS
UGS
TGLT
1-12%
TGLT
A-29%
TOLT
AdGGLT
AdacaLT
AdaGLT
30 50
20
50
40
Sparsity (%)
Weight Spansity (%)
Weight Sparsity (%)
Figure 10: The performance comparison on Ogbn- Sebn-ArxivOOgbn hww.ri//igggggo.oeiiiiggg.b.boo datasets with 4-layer
DeeperGCN. Black dash lines represent the baseline performance.
Ogba-ArXiv
Oghn-Proteins
Ogbi-Collab
75
A-18%
50
Accunicc
-70
Bandom
4.5
40
Bandes
UKIS
UGS
35
UGS
TGLT
TGLT
TGLT
AdaCi
AdaGLT
AdaGLT
Griph Sparsity (%)
Graph Sparsity (%)
Graph Sparsity
Accuniey
64
Hitsiie50 50
60
Randoca
22
Random
Random
56
UGS
UXIS
TGLT
TGLT
A-31%
TGLT
1-10%
18
AdaGUT
AdaGLT
64
10
20 30
40
50
60
70
80
90
10
20
30
40
50
50
N0
50
90
10
20
10
40
50
30
20
50
90
Weight Sparsity (%)
Weight Sparsity (%)
Weight Sparsity (%)
Figure 11: The performance comparison on OgbbrArriiilggnnPPoottiigoghogee datasets with 12-layer DeeperGCN. Black dash lines represent the baseline performance.
Ogbu-ArXiv
Oglan-Protcias
Ogbl-Collab
75
A-21%
Aoguraey
700
1-11%
Random
Random
3-7%
Randoma
65
TGLT
TGLTT A
TGLLT
60
AdaGUT
AdbiiET
1.5
40
60
20
30
40
50
40 Gruph Sparsity (%)
20
60
Graph Sparsity (%)
Graph Sparsity (%)
72)
Accuracy
HIly 5050
60
Randlen
Rundom
56
UGS
UGS
UGS
TGLT
A-24%
TGLT
AdaULT
AdaGLL
AdaGLT
50 Weight Sparsity (%)
50 Weight Sparsity
60
Weight Sparsity (%)
Figure 12: The performance comparison on AwriiiOOgnn-ProtciiSOO00-- datasets with 20-layer DecperGCN, Black dash lines represent the baseline performance.
21

---

Published as a conference paper at ICLR 2024
Ogbn-ArXiv
Ogba-Proteins
Oghi-Collah
75
3-15%
ROC-ALI 10
20
55
Aucuracy
20
Random
Randoca
A-8%
40
Randocs
UGS
UGS
UGS
TGLT
TGLLT
TGLLT
AdaKaT
AdaGET
AdaGLT
Gruph Sparsity (%)
Graph Spursity (%)
Graph Spursity
72
68
Accuracy
56
Randern
Random
HiNs
Random
TGLT
UGS
UGS
TGLT
x-31%
DGS
TGLT
A-1 3%
AdGGLT
AdaGETT
AdaGLT
10
30
50
60
70
80
90
20 30 40
30
70
50
90
10
20
40
60 70
50
90
Weight Sparsity (%)
Weight Sparsity (%)
Weight Sparsity (%)
Figure 13: The performance comparison on DeeperGCN, Black dash lines represent the baseline performance.
Prrpoggonnnooeennnggbboboooo- Collab datasets with 28 layer
12
19
20
1
2
3
18
11
74
67
17
72
5
35
25
16
33
9
90
52
ST
49
55
55
13
8
7
12
11
10
(a) A1xiv/12
(b) ArXiv/20
20
1
12
19
1
17 18
93
11
85
99
82
10
59
45
16
3224
80
47.
54
616
48
70
7
ST
37
HH 14
8
11
11 10
(c) Collab/12
(d) Collaby20
Figure 14: (a) denotes the percentage of remaining edges at each layer of a 12-layer DeeperGCN on Ogbn- Arxiv after applying AdaGLT. (b) denotes that under 20-layer settings with Ogbn- Arxiv. (c)(d) illustrates that under 12/20-layer settings with Ogbl-Collab.
22

---

Published as a conference paper at ICLR 2024
Update
Dense Weight
Thre- shold
Sparse Weight
No Backprop
BL de
BL
06
Dowwsiee
Thandederg
Throbokding
(b) Back-prop prop with ST R/L.ong tailed estimator
2H1+1
Thnsheating
Dense Adjaceacy
Thre-
Sparse Adjacency
Features
Features 11
80
shold
No Backprop
Thrshoidii
Forward
(a) Normal leed forward &
Hackward
backward process
(c) Back-prp with SR-STE
Figure 15: In this figure. @ denotes element wise multiplication and @ indicates matrix multiplication. (a) demonstrates the forward and backward processes of simultaneous sparsification without gradient estimators. backpropagation process blocked due to the binarization operation. (b) depicts weight and as- sociated threshold vector updates using straight-through/e tailettaildddee estimator, and g(-) denotes the long-tail transformation (Xu & Cheung, 2019). (c) clucidates the weight and its associated threshold vector updates using SR-STE.
K ABLATION STUDY ON GRADIENT ESTIMATORS
We have employed the straight-through estimator (STE) to enable differentiable binary pruning mask calculations. However, there exist alternative gradient estimators. To assess the sensitivity have also incorporated the LTE (Long-tailed estima-
of AdaGLT different gradient estimators, tor) (Xu & Cheung, 2019; Liu et al., 2020) and SR-STE (Zhou et al., 2021). ). Fig. 15 (a) illustrates the blocked backpropagation process when joint sparsification introduced into the graph convolution, while (b) details how STE and LTE update weights and threshold vectors. In the forward stage, θ is obtained by the row-wise thresholding with threshold vector tg. And in the backward stage, the gra- dient w.r.t. will be applied to @ directly. Fig. 15 (c) demonstrates how SR-STE updates weights and threshold vectors. Different from STE, O and to this case are updated not only through dc 8e but also guided by mg O, leading more stable sparsification process (Zhou et al., 2021).
We conducted comprehensive comparison of various gradient estimators applied to AdaGLT. Tab. 12 presents the extreme graph sparsity achieved by each gradient estimator, which corresponds to the most sparse graph lottery ticket found. Tab. 13 displays the extreme weight sparsity obtained by each gradient estimator. across various datasets and GNN models. However, it is noteworthy that SR-STE tends to exhibit suboptimal performance, particularly on GCN and GIN. On GIN, SR-STE achieved maximum graph sparsity decrease of merely 6.8% and weight sparsity decrease of 7.3%. This can be at- tributed to the fact that SR-STE was introduced to prevent the dynamic sparsifying procedure from ineffectively alternating the pruned network architecture (Zhou et al., 2021). Paradoxically, this hinders AdaGLT from exploring a wider range of sparse structures.
evident that STE and LTE demonstrate consistent performance
Table 12: The extreme graph sparsity at which AdaGLT is able to find GLTs with different gradient estimators different datasets and backbones.
Dataset + Model
Estimators
Cora +GCN
Cora +GIN
Cora +GAT
Citeseer +GCN
Citeseer +GIN
Citeseer +GAT
STE
27.6
22.7
74.1
45.7
42.0
84.2
LTE
28.9
21.2
71.8
47.2
44.0
85.9
SR-STE
22.7
15.9
72.8
43.8
37.9
83.3
23

---

Published as a conference paper at ICLR 2024
Table 13: The extreme weight sparsity which AdaGLT able find GLTs with different gradient estimators on different datasets and backbones.
Dataset + Model
Estimators
Cora +GCN
Cora +GIN
Cora +GAT
Citeseer +GCN
Citeseer +GIN
Citeseer
+GAT
STE
96.7
87.0
98.7
96.7
96.2
98.9
LTE
97.4
87.2
98.3
97.2
95.4
98.7
SR-STE
95.8
79.9
96.8
93.4
93.9
97.1
Table 14: Ablation study Citeseer with GCN backhone of 2 8 layers and 20% 60% graph sparsity,
evaluating the edge explainer (EE) and layer-adaptive pruning (LP). "w/o EE" signifies the replacement of the edge explainer with a trainable mask, and "w/o LP" indicates the maintenance of the same sparsity across all layers. The underlined number denotes the highest performance under certain graph sparsity across all AdaGLT variants.
Layer
2
4
8
Sparsity
20%
40%
60%
20%
40% %
60%
20%
40%
60%
20%
40%
60%
AdaGLT
71.32
70.66
66.
75.23
74.36
72.93
74.49
71.46
71.12
71.33
69.27
69.42
AdaGLT w/o EE
68.69
54.16
48.05
52.60
45.77
42.28
53.17
47.10
40.85
52.91
40.66
40.66
AdaGLT w/o LP
71.47
71.15
65.90
75.50
71.46
65.99
69.74
67.10
62.83
67.05
60.79
55.63
Table 15: Ablation study on Citeseer with GAT backbone of 2 + 8 layers and 40% ~ 80% graph sparsity,
evaluating the edge explainer (EB) and layer-adaptive pruning (LP).
Layer
2
8
Sparsity
40 %
60 %
80%
40 %
60 %
80%
40%
60%
80%
40%
60%
80%
AdaGLT
70.12
70.05
70.09
69.83
68. 13
66.47
68.46
66.12
06.43
67 07.50
64.98
63.
AdaGLT w/o EE
67.44
61.46
37.15
62.48
57.90
53.48
54.91
45.12
45.12
43.10
43.10
43.10
AdaGLT w/o LP
70.13
70.23
70.06
68.72
66.45
66.30
65.91
64.17
64.08
62.33
60.74
56.58
L ADDITIONAL ABLATION EXPERIMENTS
To validate the effectiveness of the individual components, we conduct additional ablation experi- ments in this section, focusing on two pivotal components of AdaGLT: the edge explainer and layer- adaptive pruning. Specifically, we aim to address the following two questions:
1. What is the impact on performance when our proposed edge explainer is substituted with a train- able mask employed in Chen et al. (2021b)?
2. How does performance vary when maintaining the same sparsity level for each layer compared to increasing sparsity as the number of layers grows?
We chose Citeseer+ GCN/GAT (for small graphs) and Ogbn-Arxiv + DeeperGCN (for large graphs) for ablation study. Our experimental results are shown in Tab. 14 to 16. We list two straightforward observations:
Obs. Substituting the edge explainer resulted in significant performance decline. Specifically, in deeper GNNs, such as 6- and 8-layer GCN/GAT, replacing the edge explainer with a trainable mask rendered the network unable to identify any winning tickets.
Layer-adaptive pruning significantly aids in discovering winning tickets in deeper GNNs. We observe that in 2- and 4-yayer GCNs, AdaGLT without layer-adaptive pruning occasionally out- performs original AdaGLT. However, deep scenarios, the elimination of layer-adaptive pruning results in sharp performance decline (8. (8.48%) under 40% sparsity and 13.79% under 60% sparsity in an 8-layer GCN).
Obs.2.
24

---

Published as a conference paper at ICLR 2024
Table 16: Ablation study on Ogbn-Arxe Arxiv with DeeperGCN backbone of + 28 layers and 60% graph sparsity. evaluating the edge explainer (EE) and layer-adaptive pruning (LP).
Layer
4
12
20
28
AdaGLT
70.13
70.08
71.34
69.79
AdaGLT w/o EE
60.34
52.60
47.44
42.40
AdaGLT w/o LP
68.74
63.89
60.33
58.05
25


Reviews:
[{"review_id": "WgWmJT1udK", "reviewer": "Reviewer_2ZB4", "summary": "The paper proposes Adaptive, Dynamic, and Automated framework for identifying Graph Lottery Tickets to overcome the integration of\nGLT into deeper and larger-scale GNN contexts. It attempts tailoring layer-adaptive sparse structures for various datasets and GNNs, thus endowing it with the capability to facilitate deeper GNNs; integrating the pruning and training processes, thereby achieving a dynamic workflow encompassing both pruning and restoration; and automatically capturing graph lottery tickets across diverse sparsity levels, obviating the necessity for extensive pruning parameter tuning.", "questions": "See above.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well written with motivation explicitly explained. The evolution of both edges and weights might dynamically during the training process as well as the flexibility of prune ratio are important missing links that are explored.\n2. The introduction of an edge explainer into GNN pruning that ensures interpretability during the pruning process while reducing unimportant edges, is a good way to mitigate the quadratic increase in parameters.\n3. Appendix is rich. I will recommend the authors move some large-scale experiments on OGBN-Arxiv and Products to be moved to main draft.", "weaknesses": "Although the introduced components like join sparsification, edge explainer etc make sense, one major concern I have is how these individual components affect the performance of AdaGLT. I appreciate the authors for their extensive experiments, but the role/importance of individual modules is not well explained. How does removing some components affect the performance. Another question, no significant performance benefit is observed for low sparsity ratios eg 30-50%. Any explanation of why it is effective only in high sparsity ratios will improve the manuscripts. I am open to increasing my score after the rebuttal discussion.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QcQUSNJZS9", "reviewer": "Reviewer_9csi", "summary": "The authors proposed the AdaGLT to obtain the graph lottery ticket to sparsify both the trainable weights and the graph structure together. The AdaGLT learns different masks for different layers of graph and weights, providing higher freedom of the sparsification. To save the memory for the training mask, the edge explainer was also introduced. Through extensive evaluation, the proposed framework achieves satisfactory results.", "questions": "1. What does the \"irreversible fashion\" refer to? The baseline UGS updates the mask only, and both the original A and weights are stored, so it should be considered as \"reversible\"?\n2. The authors stated that \"Existing GLT methods .... and their lack of flexibility stems from the necessity of hyperparameter tuning\". Can the author explain more in detail? The baseline UGS also has the trainable mask, which can be considered as the other version of the trainable threshold.\n3. Could the author describe how to get the equation 10?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The evaluation is sufficient to support the claims.\n2. The paper presentation is clear enough to get the main ideas.\n3. AdaGLT can work on deep GNNs and large-scale datasets.", "weaknesses": "1. Section 3.1 is the direct application of Liu et al. 2022, as stated in the paper. The edge explainer is also available. So, the main contribution seems incremental.\n2. The assumption of Theorem 1 may not be true for $G^{(l)}$ in most cases, since $G^{(l)}$ should be different due to the layer-adaptive pruning.\n3. The algorithm does not include the \"Dynamic Pruning and Restoration\" paragraph. And the statement of equation 10 is unclear to me. What does the restoration refer to?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EwqHf4Hi3X", "reviewer": "Reviewer_9nRP", "summary": "This paper argues that existing graph lottery ticket algorithms like UGS heavily rely on trial-and-error pruning rate tuning and scheduling, and suffer from stability issues when extended to deeper GCNs. Those limitations call for an adaptive framework to automatically identify the pruning hyper-parameters that improve the scalability of GCNs. To this end, the authors propose a framework called AdaGLT, adaptive graph lottery tickets, to overcome such limitations.\nExtensive experiments validate the effectiveness of the proposed AdaGLT as compared to previous ad-hoc UGS.", "questions": "See weaknesses. I wonder whether the contribution applied to an inductive setting or evolving graphs with increasing nodes or edges.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well-written and organized. As compared to previous UGS, the proposed AdaGLT jointly sparsifies both graphs and GNN weights and adopts an adaptive layer sparsification process. In addition, it offers the practitioner the chance to adopt automatic pruning and dynamic restoration for extracting the graph lottery tickets.\n\n2. The effective combination of automation, layer adaptivity, and dynamic pruning/restoration provides better properties as compared to previous methods.", "weaknesses": "Given the contribution of UGS and other series of graph lottery tickets work, this automated tool sounds like incremental work. However, the analysis of scalability issues when applied to deep GNNs is worth reading.\n\nMost experiments are conducted on small and transductive graph/tasks. The ogbn-arxiv is a small graph and ogbn-protein is a medium graph actually but are claimed as large graphs, more reasonablely large graphs should be considered. Also, how about inductive settings like GraphSAGE or other SOTA ones?\n\nOther than the above aspects, I think the other perspectives of this paper are clear.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)