Rethinking Graph Lottery Tickets: Graph Sparsity Matters
Authors: Bo Hui
Da Yan
Xiaolong Ma
Wei-Shinn Ku
Venue: ICLR 2023 poster (2023)
Keywords: GLT

Abstract: Lottery Ticket Hypothesis (LTH) claims the existence of a winning ticket (i.e., a properly pruned sub-network together with original weight initialization) that can achieve competitive performance to the original dense network. A recent work, called UGS, extended LTH to prune graph neural networks (GNNs) for effectively accelerating GNN inference. UGS simultaneously prunes the graph adjacency matrix and the model weights using the same masking mechanism, but since the roles of the graph adjacency matrix and the weight matrices are very different, we find that their sparsifications lead to different performance characteristics. Specifically, we find that the performance of a sparsified GNN degrades significantly when the graph sparsity goes beyond a certain extent. Therefore, we propose two techniques to improve GNN performance when the graph sparsity is high. First, UGS prunes the adjacency matrix using a loss formulation which, however, does not properly involve all elements of the adjacency matrix; in contrast, we add a new auxiliary loss head to better guide the edge pruning by involving the entire adjacency matrix. Second, by regarding unfavorable graph sparsification as adversarial data perturbations, we formulate the pruning process as a min-max optimization problem to gain the robustness of lottery tickets when the graph sparsity is high. We further investigate the question: Can the ``retrainable'' winning ticket of a GNN be also effective for graph transferring learning? We call it the transferable graph lottery ticket (GLT) hypothesis. Extensive experiments were conducted which demonstrate the superiority of our proposed sparsification method over UGS, and which empirically verified our transferable GLT hypothesis.

Published as a conference paper at ICLR 2023
RETHINKING GRAPH LOTTERY TICKETS: GRAPH SPARSITY MATTERS
Bo Hui', Da Yan?, Xiaolong Ma¹, Wei-Shinn Ku' I Auburn University 2 The University of Alabama at Birmingham 3 Clemson University
ABSTRACT
Lottery Ticket Hypothesis (LTH) claims the existence of winning ticket (i.e., a properly pruned sub-network together with original weight initialization) that can achieve competitive performance to the original dense network. A recent work, called UGS, extended LTH to prune graph neural networks (GNNs) for effectively accelerating GNN inference. UGS simultaneously prunes the graph adjacency ma- trix and the model weights using the same masking mechanism, but since the roles of the graph adjacency matrix and the weight matrices are very different, we find that their sparsifications lead to different performance characteristics. Specifically, we find that the performance of sparsified GNN degrades significantly when the graph sparsity goes beyond certain extent. Therefore, we propose two techniques to improve GNN performance when the graph sparsity high. First, UGS prunes the adjacency matrix using loss formulation which, however, does not properly involve all elements the adjacency matrix; in contrast, we add new auxiliary loss head to better guide the edge pruning by involving the entire adja- cency matrix. Second, by regarding unfavorable graph sparsification as adversarial data perturbations, we formulate the pruning process as a min-max optimization problem to gain the robustness of lottery tickets when the graph sparsity is high. We further investigate the question: Can the "retrainable" winning ticket of GNN be also effective for graph transferring learning? We call it the transferable graph lottery ticket (GLT) hypothesis. Extensive experiments were conducted which demonstrate the superiority of our proposed sparsification method over UGS, and which empirically verified our transferable GLT hypothesis.
INTRODUCTION
Graph Neural Networks (GNNs) (Kipf & Welling 2017; Hamilton et al. 2017) have demonstrated state-of-the-arr performance on various graph-based based learning tasks. However, large graph size and over-parameterizeed network layers factors that limit the scalability of GNNs, causing high training cost, slow inference speed, and large memory consumption. Recently, Lottery Ticket Hypothesis (LTH) (Frankle & Carbin 2019) claims that there exists properly pruned sub-networks together with original weight initialization that can be retrained to achieve comparable performance to the original large deep neural networks. LTH has recently been extended to GNNs by Chen al. (2021b), which proposes unified GNN sparsification (UGS) framework that simultaneously prunes the graph adjacency matrix and the model weights accelerate GNN inference on large graphs. Specifically, two differentiable masks m and my are applied to the adjacency matrix A and the model weights O respectively, during end-to-end training by element-wi wise product. After training, elements in m, and my are set to zero w.r.t. pre-defined ratios Pa and pa, which basically eliminates low-scored edges and weights, respectively. The weight parameters are then rewound to their original initialization, and this pruning process is repeated until pre-defined sparsity levels are reached, i.c.,
maggitt
|| llo 2
[ llo
graph sparsity
8g
and weight sparsity
Z 80,
||Al|o
|
where |I-Ilo is the L norm counting the number of non-zero elements.
Intuitively, UGS simply extends the basic parameter-mashee algorithm Frankle Carbin (2019) for identifying winning tickets to also mask and remove graph edges. However, empirical study

---

Published as a conference paper at ICLR 2023
Nodes training set
90-
Neighbors within 2-hop
Graat sparsiyedh 260 ofr. sears kyee)
Nelghbors of 2-hop
Edgos related training loss
UGS
Edgos with grad
wdges
0.7
(a) Performance Study of UGS Variants
(b) Types of Edges and Nodes in GNN Training
Figure 1: UGS Analysis
finds that the performance of sparsified GNN degrades significantly when the graph sparsity goes beyond a certain level, while it is relatively insensitive to weight sparsification. Specifically, we compare UGS with its two variants: (1) "Only weight," which does not conduct graph sparsification, and (2) "80% edges," which stops pruning edges as soon as the graph sparsity is increased to 20% or above. Figure [(a) shows the performance comparison of UGS and the two variants on the Cora dataset (Chen et al., (021b), where we can see that the accuracy of UGS (the red line) collapses when the graph sparsity becomes larger than 25%, while the two variants do not suffer from such a significant performance degradation since neither of them sparsifies the edges beyond 20%. Clearly, the performance of GNNs is vulnerable to graph sparsification: removing certain edges tends to undermine the underlying structure of the graph, hampering message passing along edges.
In this paper, we propose two techniques to improve GNN performance when the graph sparsity is high. The first technique is based the observation that in UGS, only fraction of the adjacency matrix elements (i.e., graph edges) are involved in loss calculation. As an illustration, consider the semi-supervised node classification task shown in Figure [bb] where the nodes in yellow labeled, and we assume that a GNN with 2 graph convolution layers is used so only nodes within two hops from the yellow nodes are involved in the training process, which are highlighted in green. Note that the gray edges in Figure l(b) are not involved in loss calculation, i.c., no message passing happens along the dashed edges so their corresponding mask elements get zero gradients during backpropagation. On the Cora dataset, we find that around 50% edges are in such a situation, leaving the values of their corresponding mask elements unchanged throughout the entire training process. After checking the source code of UGS, we find that it initializes these mask elements by adding a random noise, so the ordering of the edge mask-scores totally determined by this initial mask randomization rather than the graph topology. As result, the removal of low-scored edges tends to be random in later iterations of UGS, causing performance collapse as some important "dashed" edges removed.
To address this problem, we add a new auxiliary loss head to better guide the edge pruning by involving the entire adjacency matrix. Specifically, this loss head uses novel loss function that measures the inter-class separateness of nodes with Wasserstein distance (WD). For each class, we calculate the WD between (1) the of nodes that predicted be in the class and (2) the set of other nodes. By minimizing WD for all classes, we maximize the difference between the extracted node features of different classes. Now that this loss function involves all nodes, all elements in the graph mask m, will now have gradient during backpropagation.
Our second technique is based on adversarial perturbation, which is widely used to improve the robustness of deep neural networks (Wong et al. 2020). To improve the robustness of the graph lottery tickets (i.e., the pruned GNN subnetworks) when graph sparsity is high, we regard unfavorable graph sparsification as an adversarial data perturbation and formulate the pruning process as a min-max optimization problem. Specifically, a minimizer seeks to update both the weight parameters and its mask me against maximizer that aims to perturb the graph mask m.. By performing projected gradient ascent on the graph mask, we are essentially using adversarial perturbations to significantly improve the robustness of our graph lottery tickets against the graph sparsity.
We further investigate the question: Can we use the obtained winning ticket of a GNN for graph transfer learning? Studying this problem is particularly interesting since the "retrainability" of a winning ticket (i.e., a pruned sub-network together with original weight initialization) on the same task is the most distinctive property of Lottery Ticket Hypothesis (LTHH): many works (Liu
2

---

Published as a conference paper at ICLR 2023
et al. 2019; Frankle & Carbin 2019) have verified the importance of winning ticket initialization and stated that the winning ticket initialization might land region of the loss landscape that is particularly amenable to optimization. Here, move one step further in the transfer learning setting, to investigate if the winning ticket identified on a source task also works on a target task. The answer affirmative through our empirical study, and call it the transferable graph LTH.
The contributions of this paper are summarized as follows:
We design a new auxiliary loss function to guide the edges pruning for identifying graph lottery tickets. Our new auxiliary loss is able to address the issue of random edge pruning UGS.
We formalize our sparsification algorithm as min-max optimization process to gain the robustness of lottery tickets to the graph sparsity.
We empirically investigated and verified the transferable graph lottery ticket hypotheses.
2
PRELIMINARY
This section defines our notations, reviews the concept of GNNs, defines graph lottery tickets, and reports our empirical study of UGS's random edge pruning issue.
Notations and GNN Formulation. We consider an undirected graph G = (V, E) where V and & are the sets of nodes and edges of G. respectively. Each node U; has feature vector x; R F. where F is the number of node features. We use X E IR x to denote the feature matrix of the whole graph G. where = | is the number of nodes, and stacks x; all nodes v; as its rows. Let A E NN be the adjacency matrix of G, i.e., Aijj 1 if there is an edge Ei.i & between nodes v, and V/ and As,j = otherwise. Graph Convolutional Networks (GCN) (Kipf & Welling 2017) is the most popular and widely adopted GNN model. Without loss of generality, consider GCN with two graph convolution layers, which is formulated as follows:
Z softmax C (AXW()) w() NRC.
Here, ( is an input-to-hidden weight matrix and (1)) is a hidden-to-output weight matrix. The softmax activation function is applied row-wise and (-) max(0; (0, is the ReLU activation function. The total number of classes C. The adjacency matrix with self-connections Á A + Iy is normalized by Å D & AD where D the degree matrix of Á. For the cumi-supe node classification tasks, the cross-entropy error over labeled nodes is given by:
Co = - -.-EX
ΣΣM Yi log (Zi)),
i=y
where J/2 is the set of node indices for those nodes with labels, Y, is the one-hot encoding (row) vector node Vj 's label.
Graph Lottery Tickets. If sub-networt of GNN with the original initialization trained sparsified graph has a comparable performance to the original GNN trained on the full graph in terms of test accuracy, then the GNN subnetwork along with the sparsified graph is defined as graph lottery ticket (GLT) (Chen et al. 20216). Different from the general LTH literature, GLT consists of three elements: (1) a sparsified graph obtained by pruning some edges in G, (2) GNN sub-network and (3) the initialization of its learnable parameters.
Without loss of generality, let consider 2-layer GCN denoted by J(X, Qn) where O 0
(w(0) w(O") is the initial weight parameters. Then, the task is to find two masks my and my such that the sub-network /(X, my On) along with the sparsified graph (m, @ A, X} be trained to comparable accuracy as f(X,
UGS Analysis. LTH algorithms including UGS (Chen et al. 2021b) sort the elements in a mask by magnitude and "zero out" the smallest ones for sparsification. To find and remove the insignificant connections and weights in the graph and the GNN model, UGS updates two masks my and ms by backpropagation. However, recall from Figure [(b) that UGS suffers from the issue that only fraction of edges G are related to the training loss as given by Eq 2 for semi-supervised node
3

---

Published as a conference paper at ICLR 2023
classification. Table I shows (I) the number of nodes in the training v.s. entire dataset and (2) the percentage of edges with gradients dur- ing backpropagation for three graph datasets: Cora, Citeseer and PubMed. We can see that significant percentage of edges (up to 91% % as in PubMed) are not related to the training loss. We carefully examined the source code of UGS and found that the pruning process for these edges tends to be random since each element in the graph mask is initialized by adding a random noise to magnitude. As we have seen in Figure [(a) the accuracy UGS collapses when the graph sparsity becomes high. It is crucial to properly guide the mask learning for those edges not related to the training loss in Eq to alleviate the performance degradation.
Table 1: Statistic of Edges with Gradients
# nodes (training/all)
Percentage edges related to loss
Dataset
Cora Citeseer
140 / 2,708
51% (2,702 5.429)
120 / 3,327
34% (1,593 / 4.732)
PubMed
60 / 44,338
9% (3,712 / 44,338)
3 METHODOLOGY
Auxiliary Loss Function. Since Co as given by Eg (2 does not involve all edges for backpropagation,
we hereby design another auxiliary loss function L1 to better guide the edge pruning together with La-
Given GNN output Z and class c, separate potential nodes of class and the other nodes by:
Z {z, rows(Z) (Z) az, c} and Z {z, E rows(Z) (Z) argmax(z,) + c).
(3)
for 21.2. C}. Since z, of those Y' properly guided by Lo, e to filter out the potential nodes that belong to class c. For each class c, we then calculate the Wasserstein distance (WD) between Ze and z
argmax((;)
WD(Z", z
inf (2 |||z; zjll]=
x~ 22)
where I[Z 2 denotes the set of all joint distributions ((2 23) whose marginals are, respectively, Z and Z:
[T 2 (P: Z
Wasserstein distance (WD) Villani 2009) is widely used to measure the distance between two distributions, especially under the vanishing overlap of two distributions. Intuitively, it is the cost of the optimal plan for transporting one distribution to match another distribution: in Eq (5). [[ 2 the set of valid transport plans, where P is a coupling matrix with each element P.j representing how much probability mass from point z, E Z is assigned to point zj E Z;; and is an all-one vector.
We consider Ze and 2 the distribution of class and other classes, respectively. Equation (4) can be approximated by smooth convex optimization problem with an entropic regularization term:
min min - Pos (Pg),,
where D is the pairwise Euclidean distance matrix between points of Z and Zá, and (..-) is the Frobenius inner product. Minimizing Eq (6) is solved using Sinkhomn iterations (Cuturi 2013), which form a sequence of linear operations straightforward for backpropagation.
Ideally, we want the node representations in one class to be very different from those in other classes so that the classes can be easily distinguished. By maximizing WD(Z 2 for all classes e, we maximize the difference between GNN outputs for different classes. Formally, the auxiliary loss function to minimize is given by:
L1 =- Σ W
GEC
To explore the relationship between unsupervised loss L1 with the supervised loss Lo (i.e., Eq (2). we train a 2-layer GCN on Cora with L, as the only loss function, and F the value of Co as well as the corresponding value of Enec WD(Z', Zo) (abbr. WD) during the training process. We can see that as training loss Lo decreases, the value of WD increases. The curves of both Lo and WD
4

---

Published as a conference paper at ICLR 2023
start to bounce back after 100 epochs. Therefore, max- imizing WD is consistent with improving classification accuracy. Note that Ecec WD(Z', Z is unsupervised and related to all nodes in the training set. It is natural to this new metric guide the pruning of edges that not directly related to Lo: if masking an edge decreases WD, this edge tends be important and its removal will decrease the test accuracy of node classification.
200
1.52
1.25
0.7
Our sparsification method uses semi- semi-super loss that combines Le and L1 (or, WD): L Lo + AC1.
0.25
50
Sparsification. To prune the edges and weights while retaining robustness, we formulate GNN sparsification as min-max problem given by: min
Supervised Loss Lo v.s. WD. Note that as training loss Co decreases. the value of WD increases. Both Co and WD start to bounce back after 100 epochs.
Figure 2:
max (Co + AC1). m
(8)
G.
where the outer minimization seeks to train the model weights and their masks minimize the classification error, and the inner maximization aims to adversarially perturb the graph mask.
Let L(O, mg, my) to denote (Co AL1), then the optimization problem in Eq be solved by alternating the following two steps as specified by (i) Eq (9) and (ii) Eqs (0)) & 111
Specifically, the inner maximization perturbs the graph mask at (t + 1) iteration follows:
m m
(++1) + PIo.IJNNN m + m V,, C(e m (e) m!?)
(9)
where Pc [c|m] arg min mm' m m|? differentiable projection operation that projects the mask values onto [0, I). and vn > is a proper learning rate. While the second step for outer minimization given by:
((+1)) T
d mg
(++1) t m m
m2 m (1) m m ((+1)) +
V ((e()) m
m
(((tt)))
dmg
(10)
(t+1)] T
(++1) - (()) (Ve
-nVCC( mm!" m) +
m
V m,
L(O m m 1
where the last term is an implicit gradient obtained by chain rule over m
((+1)
given by Eq 9
Algorithm Iterative pruning process
Input:Initial masks m, = A, my
Output: Sparsified masks my and mg
1: while 1 ||m,lle llo |
8y and | lo
50 do
|e|
2: mg my. m
mg.
θ (0)
(w
w
3: for iteration = 0, 1,
do
(t+1) with Eq
4: Compute mg
5: Compute m.
((+1) with Eq 10
6: Compute (t-1) with Eq
7: end for
my my (T-1) m. m
(T-1)
8:
9:
Set Py % of the lowest-scored values in my to 0 and set the others to 1
Set pa % of the lowest-scored values in mg to 0 and set the others to
11:
end while
We follow UGS's framework to repeatedly train, prune, and reset a GNN with initial weights after each round until the desired sparsity levels 8y and 89 reached. Algorithm iillustrates iterative
5

---

Published as a conference paper at ICLR 2023
pruning process. At each round once the model is trained and masks are computed, we set Pg fraction of the lowest-scored values in my to and set the others to 1. Likewise, (1 - Pe) fraction of the
weights in @ will survive to the next round. Finally, we retrain the obtained sub-network using only Lo to report the test accuracy.
TRANSFER LEARNING WITH GRAPH LOTTERY TICKETS
This section explores whether a graph lottery ticket (GLT) can be used for graph transfer learning. Specifically, we ask two questions: (1) Can we use the graph winning ticket of GNN for transfer learning? Here, the graph winning ticket is associated with the originally initialized weight parameters. (2) Can we use the post-trained winning ticket of a GNN for transfer learning? Here, "post-trained" means that the winning ticket directly uses the trained weight parameters on the source task to bootstrap the training on the target task.
To answer these two questions, we consider the node classification tasks on two citation networks arXiv and MAG (Hu et al. 2020). In both tasks, each node represents an author and is associated with 128-d feature vector ob- tained by averaging the word embeddings of papers that are published by the author. We train a 3-layer GCN model on arXiv and transfer the model to MAG by replacing the last dense layer. Since the graphs of arXiv and MAG are
5.50
Accurary om latget task
0.25
5.15
different, we only transfer my and O from arXiv, and use the original graph of MAG without sparsification. Fig- ure shows the training accuracy curves on MAG with winning tickets obtained from arviv. Here, "Post-trained GLT (red line) starts training with the pretrained winning ticket on arXiv, while "Re-initialized GLT" (green line) starts training with the winning ticket re-initialized using original initial weight parameters. We can see that the sub-netwe sub-network obtained from arXiv transfers well on MAG in both settings, so the answers to our two questions are affirmative. Also, the blue (resp. black) line starts training with the post-trained GNN from arXiv without any edge or weight pruning; while the yellow line starts training with the winning ticket but with randomly initialized weight parameters. We can observe that (1) the post-trained winning ticket (red) achieves the same performance as the post-trained GNN (blue), showing that the transferred performance is not sensitive to weight pruning; and that (2) the winning ticket identified on the source task (green) achieves even better performance on the target task than randomly initialized GNN (black). Note that gradient descent could get trapped in undesirable stationary points if it starts from arbitrary points, and our GLT identified from the source task allows the initialization land in region of the loss landscape that is particularly amenable to optimization (Ganea et al. 2018).
6.10
Fost trained GLT intiiaaa oLT
Randomly tht CKM
Poub brained GhN
5.00
Randomly Intiliedd OLT
203
660
600
ado
10c0
Epochs
Figure Training Curves on MAG. No- tice that the post-trained winning ticket achieves the similar performance as the post-trained GNN. Also, the winning ticket achieves even better performance than randomly initialized GNN.
5 EXPERIMENT
Experimental Setups. Following Chen et al. (2021b), evaluate our sparsification method with three popular GNN models: GCN (Kipf & Welling 2017), GAT (Velickovic et al. 2018) and GIN (Xu et al.] 2019), three widely used graph datasets from Chen et al. (202Tb) (Cora, Citeseer and PubMed) and two OGB datasets from Hu et al. (2020) (Arxiv and MAG) for semi- semi-supervised node classification. We compare our method with two baselines: UGS (Chen et al.] 2021b) and random pruning (Chen et al., (0211b. For fair comparison, we follow UGS to use the default setting: Py = 5 and po 20 unless otherwise stated. The value of X is configured as 0.1 by default. More details on the dataset statistics and model configurations can be found in the appendix.
Evaluation of Our Sparsification Method. Figures 4 5 and comppar our method with UGS and random pruning in terms of the test accuracy on three 2-layer GNN models: GCN, GIN and GAT, respectively. In each figure, the first (resp. second) row shows how the test accuracy changes with graph sparsity (resp. weight sparsity) during the iterative pruning process, on the three datasets: Cora, Citeseer and PubMed. We can observe that the accuracy of our method (green line) is much higher than UGS (yellow line) when the graph sparsity is high and when the weight sparsity is high.
6

---

Published as a conference paper at ICLR 2023
Table 2: Pair-wise comparison
Cora (17 iterations)
Model
GCN
GIN
GAT
Methods/Metrics
GS(%)
WS(
Accuricy(S) (8)
GS(S)
WS(
Accuracy (%)
GS(S)
WS(%)
Accuracy(S:)
UGS
56.28
97.52
72.5
57.62
97.25
69.0
57.42
97.33
78.7
Our
58.02
97.80
75.1
57.88
98.26
72.8
58.12
97.89
80.0
Citeseer (17 iterations)
Model
GCN
GIN
GAT
Methods/Metrics
GS(%)
WS(%)
Accurnc(())
GS(S)
WS(W))
Accuracy (%)
GS(S))
WS(
Accuracy(S)
UGS *
54.33
96.53
66.7
56,03
96.58
63.2
$4.99
97.21
70.
55.78
97.38
70.3
55.95
97.25
56.03
97.30
70.6
PubMed (17 iterations)
Model
GCN
GIN
GAT
Methods/Metrrcs
GS(%)
WS(%)
Accuracy($5
GS(
WS(%)
Accuracy( ())
GS(S)
WS(%)
Accuracy(*))
UGS *
58.21
97.70
77.7
58.23
99.19
76.3
57.64
97.32
78.8
Our
59,43
97.81
79.5
58.13
97.76
77.2
58.22
98.18
80.0
To clearly see this accuracy difference, we show the test accuracy, graph sparsity (GS) and weight sparsity (WS) after the 17th pruning iteration in Table for both UGS and our method. Note that each graph sparsity is paired with a weight sparsity. We use and * to represent UGS and our method, respectively. Given the same sparcification iteration number, the sub-networks found by our method have a higher accuracy than those found by UGS. For example, when GS 56.28% and WS = 97.52%, the accuracy of GCN on Cora is 72.5%, whereas our method improves the accuracy to 75.1% % with comparable setting: GS 57.95% and WS = 97.31%. Note that although same Py and pa for both our method and UGS, their sparsity values in the same pruning iteration are comparable but not exactly equal. This is because multiple mask entries can have the same value, and they span across the pruning threshold Py or we prune them all in an iteration such that slightly more than Py fraction of edges or pe fraction of weights may be removed. The higher accuracy of our method over UGS demonstrates that our approach finds lottery tickets that are more robust against the sparsity, and better prevents a performance collapse when the graph sparsity is high. In addition, we use and * to indicate the last GLT with an accuracy higher than the original model in the sparsification process of UGS and our method, respectively. We can observe that the GLTs identified by our method have higher sparsity than those located by UGS. It further verifies that our method can improve the robustness of GLT against the sparsity.
the
Note that in Figure $ the third subfigure, the accuracy of our method (green line) is very stable even when graph sparsity is high. This is because PubMed is a dense graph where some edges can result from noise during data collection, even improves model accuracy by alleviating the oversmoothing problem of GCN.
graph sparsification functions denoising, which retains or
3.55
ACuraa (Dherrear
Aecurery (PubWedd
Accuracy
USS
UGS
Bandom Ours
Random
Random
Ours
Ours
0.7
12
05
0:00
21 Grash soarsity
04
Graph sparsty
Graph sparsity
(Cheteee
0:10
Accract
2:10
USS Random
UGS
LCS
Random
2430
Random
Ours
Outs
0urs
Weigt sparsty
Weight sparstyy
Wiigt sparsky
Figure 4: Performance on GCN. Marker and * denote the spasified GCN (after 17 iterations) with UGS and our method, respectively. Marker and * indicate the last GLT that reaches higher accuracy than the original model the sparsification process of UGS and our method, respectively.
7

---

Published as a conference paper at ICLR 2023
0.1
0.7
Acourscy
1.2
0.35
E40
Random
Random
Durrs
OuT5
Ours
sparaky
Deaph
Arcuracy (PibMee))
0.77
0.5
LAC
Random
Random
0:3
OurS
OuTs
Ours
1.0
Weight spardiy
sparsty
Weight sparsity
Figure Performance on GIN
043
0.00
Aocuraay (NN0M00)
2.3
4m
0.70
UGS
Random
Random
Random
Ours
Ours
Ours
Graph sparety
Graph spersty
Graph speraty
3.02
Accracy Arcracy (PaMtee (ieee
024
0.0
072-
Random
Handom
Ours
Durs
Ours
1.5
6G
Wwightspenstt
sparsty
sparaty
Figure 6: Performance on GAT
Also note from Figure the performance of GAT is less sensitive to the sparsity as compared with GCN and GIN. This is because the attention mechanism in GAT leads to many more parameters than the other two models, allowing for pruning more parameters, moreover, GAT itself is able to identify the importance of edges through the attention mechanism, which better guides the edge pruning.
Ablation Study. To verify the effec- tiveness of each design component in our sparsification algorithm, we com- pare our method with several variants. First, we remove the Wasserstein- distance based auxiliary loss head by setting À = 0 during sparsification. shown in Figure / removing the auxiliary loss function leads to perfor- mance degradation. However, there exists tradeoff weight the importance of L. For example, if we increase À from 0.1 to 1, the performance backfires especially when the sparisty is high. We further investigate our adversarial perturbation strategy can improve the robustness of the pruned GNNs, by replacing optimization process with the algorithm in UGS. Specifically, the variant "UGS+WD" uses the sparsification algorithm in UGS to minimize L(O, mo, mg). Compared with this variant, our method
UGG+WW9
Graph sparsty
Weight sparsty
Figure 7: Ablation study
min-max
8

---

Published as a conference paper at ICLR 2023
can alleviate the performance degradation when graph sparsity is high, which verifies that adversarial perturbation improves robustness.
Pairwise Sparsity. In Figure 8 we investigate the accuracy of the pruned GNNs after 10 iterations with different combinations of Py and Po. Note that larger Py and po result in higher sparsity of the adjacent matrix and the weight matrices, respectively. We can see that the performance of the pruned GNN is more sensitive to the graph sparsity than the weight sparsity. It further verifies the necessity of finding robust GLTs when the graph sparsity is high. Since the pruned GNN is less sensitive to the weight sparsity, we can obtain GLTs with higher overall sparsity by setting po to be larger Pg. At the same time, a larger Pg can result in the pruning of more noisy and unimportant edges, which may help prevent GCN oversmoothing. Therefore, tradeoff' exists when choosing proper combination of Pa and pg. While users
08
79
25.
PL.
90
0.5
79.7
25.3
76.4
793
992
0.28
26.
724
781
702
0.8
061
724
963
025
0.1
028
1/6
Figure 8: Varying Pa and ps may try different combinations of Py and pa to find proper combination, our approach is superior to UGS in all combinations of Py and po, so should be better algorithm choice.
RELATED WORK
In the last few years, series of GNN models (Kipf & Welling, 2017; Velickovic et al., 2018 Xu
ct al. 2019 | Hamilton et al. 2017; Ying et al. (0is/Klicpera et al. 2019: Hui et al. 2020 Tong et al.
2020
Yun et al. (2019) have been designed to utilize the graph structure in spatial domain and spectral
domain for effective feature extraction. However, the computational cost of GNNs on large-scale
graphs can be very high especially when the graph is dense with many edges. Many models have been proposed to reduce this computational cost, such as FastGCN (Chen et al.) (018) and SGC (Wu) et al., (209)). However, their accuracy tends to be worse than GCN, while the speedup achieved is still limited. So, it is desirable to develop a pruning method to sparsify both the edges and the weight parameters for any given GNN model (including FastGCN and SGC) without accuracy compromise.
The lottery ticket hypothesis is first proposed in Frankle & Carbin (2019) to find an identically initialized sub-network that can be trained to achieve a similar performance as the original neural network. Many works (Frankle et al., 2019;; 20200 Diifenderter & Kailkhura| 2021; MMlach et al.
2020; Ma er af. 2021b; Savarese et al. 2020 //hang et al.] 2021 by /hou et 2019| Chen et al. 20 et al.) 20e0 et al. (022) have verified that the identified winning tickets are retrainable to reduce the high memory cost and long inference time of the original neural networks. LTH has
been extended to different kinds of neural networks such as GANs (Chen et al.
202leb a Kalibhat
ct al. 202 I), Transformers (Brix et al., 2020; Prasanna et al.] Chen et al. 2020 Behnke &
Heafield 2020) and even deep reinforcement learning models Vischer al. 202 Yu et al. 2020).
It has also been studied on GNNs by UGS (Chen et al. 20215).
Despite the competitive performance of winning tickets, the iterative train teii--puun--etrain process and even the subsequent fine-tuning (Liu et al., (021) are costly to compute. To address this issue, PrAC (Zhang et al., al.] (021c) proposes to find lottery tickets efficiently by using a selected subset of data rather than using the full training set. Other works (Wang el al.) 2020 Tanaka et al., (0200) attempt to find winning tickets at initialization without training. The new trend of dynamic sparse training shows that any random initialized sparse neural networks can achieves comparable accuracy to the dense neural networks (Ye et al.) 2020: Evei et al.] [020)] Hou al. [022] Ma et al. [02Ia] Yuan et al. 2021). Customized hardware architectures have also been used to accelcrate sparse training (Goli & Aamodt 2020: Raihan& & Aamodi 2020)). The Elastic Lottery Ticket Hypothesis [Chn et al. (222 d) studies the transferability of winning tickets between different network architectures within the same design family. For object recognition, MMhtaa (2019) shows that winning tickets from VGG19 do not transfer well to down-stream tasks. In the natural image domain, Morcos et al. (2019) finds that the winning ticket initializations generalize across a variety of vision benchmark datasets.
Commann,Morcos
7 CONCLUSION
In this paper, we empirically observe that the performance of GLTs collapses when the graph sparsity is high. We design new auxiliary loss to address this limitation. Moreover, we formulate the GNN sparsification process as a min-max optimization problem which adopts adversarial perturbation to improve the robustness of graph lottery tickets. Our experiments verified the superiority of our method over UGS. We further empirically studied transfer learning with GLTs and confirmed the transferability that gives rise to the transferable graph lottery ticket hypotheses.

---

Published as a conference paper at ICLR 2023
REFERENCES
Maximiliana Behnke and Kenneth Heafield. Losing heads in the lottery: Pruning transformer attention in neural machine translation. In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu (eds.), Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, Online, November 16-20, 2020, pp. 2664 2674. Association for Computational Linguistics, 2020. doi: 10. 1066:////2220..mmmmmmmaiii
URL
18653/v1/208B emp ma iiaiin.22 211
Christopher Brix, Parnia Bahar, and Hermann Ney. Successfully applying the stabilized lottery ticket hypothesis to the transformer architecture. In Dan Jurafsky, Joyce Chai, Natalie Schluter, and Joel R. Tetreault (eds.), Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, ACL 2020, Online, July 5-10, 2020, pp. 3909-3915, Association for Computational Linguistics, 2020. doi: 10. 10.18653/w1/0220..om main.3mi 360. URL https://dol
Oxc/10.18653/v1/222 aww.::200.ccmmaammm acl-aclllaaaa. 360
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: Fast learning with graph convolutional networks via importance sampling. In 6th International Conference Leurning Representutions, ICLR 2018, Vancouver, BC. Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL haattss:/openzeeiieeee net
Tianlong Chen, Jonathan Frankle, Shiyu Chang, Sijia Liu, Yang Zhang, Zhangyang Wang, and Michael Carbin. The lottery ticket hypothesis for pre-trained BERT networks. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan- Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Anmual Con- ference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020. URL httttttss/s/rccccediinoo// meurdiiinnnnn....osooeeeoo neurips cc pcc/paper/2020/hash 1aaa2299701222022277702aa.
html
Tianlong Chen, Yu Cheng, Zhe Gan, Jingjing Liu, and Zhangyang Wang. Data-efficient gan training beyond (just) augmentations: A lottery ticket perspective. In M. Ran- zato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 20941-20955, Curran Asso- ciates, Inc., 2021a. URL httt::t:/pprcceedingg meeeeeddiinnnnnniiii..eeeee.eeie cc/pppprr/22////1lee Papp:eaaaittiaaaaaaaa..e.. pdf
Tianlong Chen, Yongduo Sui, Xuxi Chen, Aston Zhang, and Zhangyang Wang. A unified lottery ticket hypothesis for graph neural networks. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 1695 1706. PMLR, 2021b. URL http:tt:pppooccceiinngi.
mlr. ppress/v3se Stteesssv13//chenllp.ott wwwnchh. html
Tianlong Chen, Zhenyu Zhang, Sijia Liu, Shiyu Chang, and Zhangyang Wang. Long live the lottery: The existence of winning tickets in lifelong learning. In 9th International Conference on Learning Representationss ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021c URL https://cpenzeevee net. forum? 2 LX=LXXXV
Tianlong Chen, Xuxi Chen, Xiaolong Ma, Yanzhi Wang, and Zhangyang Wang. Coarsening the granularity: Towards structurally sparse lottery tickets. In International Conference Machine Learning (ICML), 2022.
Xiaohan Chen, Yu Cheng, Shuohang Wang, Zhe Gan, Jingjing Liu, and Zhangyang Wang. The elastic lottery ticket hypothesis. In Mare' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6414, 2021, virtual, pp. 166099266622 http:///www.n..ppo/ooo.oeoooooo.
cc/
pa
Xuxi Chen, Zhenyu Zhang, Yongduo Sui, and Tianlong Chen. Gans can play lottery tickets too. In 9th International Conference Learning Representations, ICLR 2021. Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021e. URL hittps://openzeweee net/ forum?id
lAoMhe 9jRR
10

---

Published as a conference paper at ICLR 2023
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. In Christopher C. Burges, Léon Bottou, Zoubin Ghahramani, and Kilian Q. Weinberger (eds.), Advances in Neural Information Processing Systems 26: 27th Annual Conference Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States, pp. 22922-300, 2013. URL (tRl.httts::.. http:::///oooeeeeeeeee ngs www.eeripss...ppppereeeeeepepeee Abstsseaaaaddddaacaaaabaa html
James Diffenderfer and Bhavya Kailkhura. Multi- lottery ticket hypothesis: Finding accurate binary neural networks by pruning A randomly weighted network. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, net forum?id- mat Ob9iv
2021.
Utku Evci, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen. Rigging the lottery: Making all tickets winners. In Proceedings of the 37th International Conference Machine Learn- ing, ICMI. 2020, 13-18 July 2020, Virtual Event, volume 1 119 of Proceedings of Machine Learning Research, pp. 2952. PMLR, 2020. URL http::/pprcceeei//e//// evci20a.hr html
.mlr. www.r.preessviiss
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL htttttt:///ppeeeeeeeee
net/Forum?1d=r3]--
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M. Roy, and Michael Carbin. The lottery ticket hypothesis at scale. CoRR, abs/1903.01611, 2019. URL
org/ abs 1903
01611
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M. Roy, and Michael Carbin. Linear mode connectivity and the lottery ticket hypothesis. In Proceedings of the 37th International Conference on Machine Learming. ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 3259-325660 PMLR, 2020. URL http:::/prrccceeeggs mlr. www.prressvllll Fat.rannee2000 html
Octavian-Fuge Eugen Ganea, Gary Bécigneul, and Thomas Hofmann. Hyperbolic entailment cones for learning hierarchical embeddings. In Jennifer G. Dy and Andreas Krause (eds.), ICML, 2018.
Negar Goli and Tor M. Aamodt. Resprop: Reuse sparsified backpropagation. In 2020 IEEE/CVF Conference Computer Vision and Pattern Recognition, CVPR 2020, Seattle, WA, USA, June 13-19, 2020, pp. 1545-1555. Computer Vision Foundation / IEEE, 2020. doi: 10.1009/CVPR2222002000000 00162. httttpss///ppeacccsss CVPR_2020 2020/html/Goli ReSprop Bectspoo__euus_e____eee Reuse Sensss_SSarssfieeeaacccrrssssso Backpropagation. STPP_2020_paaeer html
William I.. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. N. Vishwanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Sys- tems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, neur /c/ .htll
Long Beach, CA, USA, pp. 1024 1034, 2017. URL paper/ 221//2117//
Zejiang Hou, Minghai Qin, Fei Sun, Xiaolong Ma, Kun Yuan, Yi Xu, Yen-Kuang Chen, Rong Jin, Yuan Xie, and Sun-Yuan Kung. Chex: Channel exploration for enn model compression. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp.
12287-12299 2022.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tiee Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020. URL httpaa/nnnn.///ttae////poeeeonnn oaood
neurips cc/ http:r/pp...caapppp/////////////

---

Published as a conference paper at ICLR 2023
Bo Hui, Da Yan, Wei-Shinn Ku, and Wenlu Wang. Predicting economic growth by region embedding: A multigraph convolutional network approach. In Mathieu d' Aquin, Stefan Dietze, Claudia Hauff, Edward Curry, and Philippe Cudré-Mauroux (eds.), CIKM '20: The 29th ACM International Conference on Information and Knowledge Management, Virtual Event, Ireland, October 19-23, 2020, pp. 555 555-564. ACM, 2020. doi: 10. 10.1145/3340531.. .34 1882. URL httph: :tdaps://doi.. .aaii..org.....
3411882
Neha Mukund Kalibhat, Yogesh Balaji, and Soheil Feizi Winning lottery tickets in deep generative models. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty- Thirty-Third Con- ference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021, AAAI Press, 2021. URL htttps://ooss...... aaai org/ index. pww.k..hpppAAAAA
pp.
aattice article/vieee 6980
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In Sth International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24- 26, 2017, Conference Track Proceedings. OpenReview.net, 2017. URL httpt::// /ttp:///peeeeeeeeeee
net/forum: /tt
Johannes Klicpera, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learning. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Flo- rence d' d'Alché-Buce Emily B. Fox, and Roman Garnett (eds.), Advances in Neural In- formation Processing Systems 32: Annual Conference
Neural Information Process- ing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 13335-13345, 2019. URL httpt:tt////t httpps:/ppooceed/iii 23c894276a2c55
neurips wwteeurrs.cccpppppeeeee wwtpppppppp/////ccc /20ppp/pp00111 9/hash/ 8d73 Abst .h.ml
Nishai Kooverjee, Steven James, and Terence L. van Zyl. Investigating transfer learning in graph neural networks. CoRR, abs/2202.007400, 2022. URL https: org abs 2aa.b//220 org/abs/2202 2202
00740
Ning Liu, Geng Yuan, Zhengping Che, Xuan Shen, Xiaolong Ma, Qing Jin, Jian Ren, Jian Tang, Sijia Liu, and Yanzhi Wang. Lottery ticket preserves weight correlation: Is it desirable or not? In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 7011-7020. PMLR, 2021. URL html
mlr www.pesssww19//1ine
Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell. Rethinking the value of network pruning. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL httttss://ppereeiiiee
Xiaolong Ma, Minghai Qin, Fei Sun, Zejiang Hou, Kun Yuan, Yi Xu, Yanzhi Wang, Yen-Kuang Chen, Rong Jin and Yuan Xie. Effective model sparsification by scheduled grow-and- methods. In International Conference on Learning Representations (ICLR), 2021a.
Xiaolong Ma, Geng Yuan, Xuan Shen, Tianlong Chen, Xuxi Chen, Xiaohan Chen, Ning Liu, Minghai Qin, Sijia Liu, Zhangyang Wang, and Yanzhi Wang. Sanity checks for lottery tickets: Does your winning ticket really win the jackpot? CoRR, abs/2107.00 00,666, 2021b. URL https
//arxiv. abs/ 2107.0000000 00166
Eran Malach, Gilad Yehudai, Shai Shalev-Shwards and Ohad Shamir. Proving the lottery ticket hypothesis: Pruning is all you need. In Proceedings the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 6682 6691. PMLR, 2020. URL http:://procdedngg html
mlr. wwwss/vwllli........ wttpp/////////aaaa//////2
Rahul Mehta. Sparse transfer learning via winning lottery tickets. CoRR, 0ttp://1005000775555
2019.
URL | http::t/tt//tiit
12

---

Published as a conference paper at ICLR 2023
Ari S. Morcos, Haonan Yu, Michela Paganini, and Yuandong Tian. One ticket to win them all: generalizing lottery ticket initializations across datasets and optimizers. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' A'ché-Buuc Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Inf Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 4933-4943, 2019. URL
neuriinnn..n...sssooeee..e... Abstract. html
Sai Prasanna, Anna Rogers, and Anna Rumshisky. When BERT plays the lottery. all tickets are winning. In Bonnie Webber, Trevor Cohn, Yulan Hc, and Yang Liu (eds.). Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, Online, November 16-20, 2020, pp. 3208 3229. Association for Computational Linguistics, 2020. doi: 10.18653/v1/2000 cannl-mmain... 259. URL https://doi. .rg. 10 Te..111..665//// 11653/v1/2020 emn: 1p ma in. 259
Md Aamir Raihan and Tor M. Aamodt. Sparse weight activation training. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Confer- ence on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL//ttpps///prceediii b441 8237 9bf 9 9 (e1.6 3cd8 Abstract.htte.
neurips wwtpaper///ccppppppccccccpe.. Seaper/2020//00 2020/hash/
Pedro Savarese, Hugo Silva, and Michael Maire. Winning the lottery with continuous sparsi- fication. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. /tt::ttpps////oceeediin htw.:occeedings..eur............ nwwrips...p...e CC wttp:/pppppppppppepppppeap wwtpppppppeo22..// /aahh/ 830041 001004990119337aa11555 ott.a/00000.001111110000011111e.
.tml
Jingtong Su, Yihang Chen, Tianle Cai, Tianhao Wu, Ruiqi Gao, Liwei Wang, and Ja- son D. Lee. Sanity-checking pruning methods: Random tickets can win the jackpot. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan- Tien Lin (eds.), Advunces in Neural Information Processing Systems 33: Annual Con- ference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL att.eeeeweeeeeeeeeasaaaaaaa....a http://cca2222000000eeeeeeee2ddd
neura cc ct/ wccppaper/222//aas/ Abst .tml
Hidenori Tanaka, Daniel Kunin, Daniel L. K. Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Confer- ence on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL RtRL:tttss://poceediiii
neurips cc wccppaper/222//aaaa. html
Zekun Tong, Yuxuan Liang, Changsheng Sun. Xinke Li, David S. Rosenblum, and Andrew Lim. Di- graph inception convolutional networks. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and disuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. BtRLhttss: / www.ips...... wwwppiippppcppppp.epppppp 2020/hash/cffbee2288... (7w030002228884444666666 httpa//eccccccceeeeeeeeeeeaeeeee Abst htm_
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liö, and Yoshua Bengio. Graph attention networks. In 6th International Conference Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL httthtts::// http:///eeeeeeveeee httptttps///eeeeeiiiee wwtp:orrmmeeeeeeoe pttp://rrmmmmid..xpppp.......
Cédric Villani. Optimal transport: old and new, volume 338. Springer, 2009.
Mare Aurel Vischer, Robert Tjarko Lange, and Henning Sprekeler. On lottery tickets and minimal task representations in deep reinforcement learning. CoRR, abs/2105.01648, 2021. URL hthhts
7/ rxivv wttp://wwwrr/a///...105////5 0164
13

---

Published as a conference paper at ICLR 2023
Chaoqi Wang, Guodong Zhang, and Roger B. Grosse. Picking winning tickets before training by preserving gradient flow. In 8th Interaational Conference on Learning Representations. ICLR 2020, Addis Ababa, Ethiopia, April 26-30. 2020. OpenReview.net, 2020. URL https:// openreview
nwt. wwwprrrvvwwwweeeeforrreeeee
Eric Wong, Leslie Rice, and J. Zico Kolter. Fast is better than free: Revisiting adversarial training. In
8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia. April 26-30, 2020. OpenReview.net, 2020. BtLLttps://// http//pppnreiie.eeeeeeeeeee / net http://wwwwweettuuutteee BJx040EFvH
forum?id
Felix Wu, Amauri H. Souza Jr., Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Q. Weinberger. Simplifying graph convolutional networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.). Proceedings of the 36th International Conference on Machine Learning. ICML 2019, 9- 15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 6861-6871. PMLR, 2019. URL wul 9e. html
ml press/v977
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful are graph neural networks? In 7th International Conference on Learning Representationss ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.ner, 2019. BKKLLtttss://peereeeee net/ forum?
id=ryGs 1m5Km
Mao Ye, Lemeng Wu, and Qiang Liu. Greedy optimization provably wins the lottery: Logarithmic number of winning tickets is enough. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (cds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, htt.tpp://pprceeedngg/ neur cttpspec//ppe/r///p//p Abstract.htt
December 6-12, 2020, virtual, 2020. 0114444777e272444442 /tta:///.....1111110044433/36222
Rex Ying, Ruining He. Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. Yike Guo and Faisal Farooq (eds.). Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2018, London, UK, August 19-23, 2018, pp. 974 983. ACM, 2018 URL https: / /oi. org 111.11115/32111111 9819, 3219899
doi: 10. 10.1145/3219819.5219999
Haonan Yu, Sergey Edunov, Yuandong Tian, and Ari S. Morcos. Playing the lottery with rewards and multiple languages: lottery tickets in RL and NLP. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL httphttts///ppeneeeett
net forum? id= 1 11XXXVVVW
Geng Yuan, Xiaolong Ma, Wei Niu, Zhengang Li, Zhenglun Kong, Ning Liu, Yifan Gong, Zheng Zhan, Chaoyang He, Qing Jin, al. Mest: Accurate and fast memory-economic sparse training framework on the edge. Advances in Neural Information Processing Systems, 08220888-28551 2021.
Seongjun Yun, Minbyul Jeong, Raehyun Kim, Jaewoo Kang, and Hyunwoo J. Kim. Graph transformer networks. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Flo- rence ''lché-Buu, Emily B. Fox, and Roman Garnett (eds.), Advances in Neural In- formation Processing Systems 32: Annual Conference
Neural Information Process- ing Systems 2019, NewriPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 11960-11970, 2019. URL httpt:ttt//.cm. 770 5404054455599
http:ttssp/ppoceeeiiiiiieeo http:////oceeeeneseeeee wwwrips......m httppp..cccpppee wwwpccppppp.c.accc 9/hash/
Abst. html
Shuai Zhang, Meng Wang, Sijia Liu, Pin- Yu Chen, and Jinjun Xiong. Why lottery ticket wins? a theoretical perspective of sample complexity on sparse neural networks. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Ad- vances in Neural Information Processing Systems, volume 34, pp. 2707-2720. Curran Asso- ciates, Inc., 2021a. URL httpttttttttceeeeeette 115992775aaB8633Caoeeeeeeeee2223
nwwriis..e....p... cc
file/
Zeru Zhang, Jiayin Jin, Zijie Zhang, Yang Zhou, Xin Zhao, Jiaxiang Ren, Ji Liu, Lingfei Wu, Ruoming Jin, and Dejing Dou. Validating the lottery ticket hypothesis with inertial manifold
14

---

Published as a conference paper at ICLR 2023
theory. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 30196-30210. Curran Asso- ciates, Inc., 2021b. URL http:ta:/ppooceeiiiiigg inw.:eeeeeddddno...n............ cC/ httpppappppppppeeeep 201l/fie// Fdc42b www.ffa2f2aaa.. 500e ofg
Zhenyu Zhang, Xuxi Chen, Tianlong Chen, and Zhangyang Wang. Efficient lottery ticket finding: Less data more. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning. ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. (2380-13390 PMLR, 2021c. URL http //proceedings... m pww.ss...eeseeeee..ee.eee https//v199/zaaaal htmll
Hattie Zhou, Janice Lan, Rosanne Liu, and Jason Yosinski. Deconstructing lottery tickets: Ze- ros, signs, and the supermask. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelz- imer, Florence d' d'Alché-Buc, Emily B. Fox, and Roman Garnett (eds.). Advances in Neu- ral Information Processing Systems 32: Anmual Conference on Neural Information Pro- cessing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 3592-3602, 2019. URL LLLSchaifffeaaab33330055466---
.ttm
A APPENDIX
A.1 DATASET AND CONFIGURATION
The statistics of benchmark datasets in the experiment are summarized in Table For three citation networks: Cora, CiteSeer and PubMed, the feature of each node corresponds to the bag-of-words representation of the document. For arXiv and MAG, each node is associated with 28-dimensional feature vector obtained by averaging the word embeddings of papers. Three models (GCN, GIN and GAT) are configured with the default parameters in their corresponding source code, including number of layers, dimension of hidden state and learning rate. In our sparsification process, the value of 7) 7/2 and a configured as le-2, le-2 and le-1 by default, respectively. In each pruning round, the number of epochs to update masks is configured as the default number of epochs in the training process of the original GNN model.
Table 3: Statistics of datasets
Dataset
#Nodes
#Edges
Average Deg.
Split ratio
Features
Classes
Cora
2,708
5,429
3.88
120/500/1000
1,433
7
Citeseer
3,327
4,732
2.84
140/500/1000
3,703
6
PubMed
19,717
44,338
4.50
60/500/1000
500
3
Xiv
169,343
1,166,243
13.7
54% 18%%
128
40
MAG
1,939,743
21,111,007
21.7
85%/9%%/6%
128
349
Table 4: GLT comparison
Model
GCN
GIN
GAT
Methods/MMtries
GS(%)
WS(S)
Accurncy( ()
GS(S)
WS(%)
Accuracy( %)
GS(S)
WSCK)
Accuracy( %)
UGS
Ours
18.52
59.12
82.2
4,86
20L07
79.6
63,82
98.93
80.7
Citeseer
Model
GCN
GIN
GAT
Methols/Memiss
(S())
WS(W)
Accurney 8)
GS(6) WS(R) (R)
Accuracy (6)
GS(6)
WS(W)
Accuracy W)
UGS
22.65
67.34
71.7
19.03
59.43
70.3
64.48
99.41
70.2
Ours
22.63
67.76
72.1
33,89
83,57
69.3
62.29
98.63
70.8
PubMed
Model
GCN
GIN
GAT
Methols/MMeriss
GS())
WS(S)
Accurnc((5)
GS(%)
WSCR)
Accuracy( (R)
GS(%)
WSCW)
Accuracy(*))
UGS
48.69
94.53
79.5
35.32
83.27
78.
57.64
97.32
78.8
65.35
98.91
48.84
94.52
78.5
64.26
99.07
80.4
15

---

Published as a conference paper at ICLR 2023
A.2 GLT COMPARISON
In T we show the test accuracy, graph sparsity (GS) and weight sparsity (WS) of the last GLT that reaches higher accuracy than the original model in the sparsification process of UGS and our method. Note that GLT of GIN cannot be found on Cora in the sparsification process. We can observe that the last GLT identified by our method either has higher sparsity or achieves higher accuracy with comparable sparsity.
In Table 5 we evaluate the test accuracy of sparsified GCN on two large-scale graph datasets: arXiv and MAG. We can observe that our method can result in higher accuracy than UGS with comparable graph sparsity and weight sparsity after 5, 15, and 20 iterations. It further verifies the effectiveness of the proposed method on large-scale datasets.
Table 5: Performance of GCN on large-scale graph datasets
ogbn-arxiv
Iterations
5
15
20
Methods/Metrics
GS(%)
WS(
Accuracy(58
WS(%)
Accuracy(18)
GS(%)
WS(%)
Accuracy(3))
UGS
22,68
67.23
71.92
53.69
96.49
71.15
64.27
98.86
69.87
Ours
23.51
67.24
71.94
52.81
96.52
71.89
63.82
98.93
70.79
ogbo-mag
Methods/Metrics
GS(%)
WS(%)
Accuracy($5 (%)
GS(%)
WS(%)
Accuracy( 9%
GS(%)
WS(%)
Accuracy(
UGS
23.66
67.31
33.43
55.99
96.50
30.71
67.42
98.77
30.12
Ours
22.65
67.31
34.11
54.81
96.49
32.23
63.59
98.85
31.76
A.3 PERFORMANCE STANDARD AND INFERENCE TIME
To combat randomness, we visualize the standard deviation of accuracy on Cora with shaded color. Following UGS, we also show the inference MACs (multiply-accumml) operations) of pruned models in the sparsification process. We can see that our method can significantly reduce the inference cost of GNNs with less performance drop.
6/2
UBS
Oure
UGS
(a) GCN
(b) GIN
(c) GAT
Figure 9: Performance over inference MACs of GCN, GIN, and GAT on Cora
A.4 TRANSFER LEARNING WITH GLTs
To verify the transferable graph lottery ticket hypothesis, we identify the GLT on arXiv and investigate the transfer ratio Kooverjee et al. (2022) of this GLT on MAG. Since the number classes on arXiv
WS 75%
130
WS- 85%
Eoocrs
Coecha
(a) Replacing Last Dense Layer (b) Add New Dense Layer
(c) Different GLTs
Figure 10:
Transfer Learning from Arxiv to MAG
16

---

Published as a conference paper at ICLR 2023
different from that MAG, need to either add dense layer for class mapping replace the last dense layer to match the output classes in MAG. Figure [[ shows the target-task test accuracy of 3-layer GLTs (or GNNs) where the last dense layer is replaced. We can that the post-trained GLT and post-trained GNN identified on the source task have a similar transfer ratio the target task. Both the nost-trained GLT and post-trained GNN have significant improvement over the randomly initialized GNNs. Also, we can observe improvement of re-initialized GLT over randomly initialized GLT. As shown in Figure To(b] similar results can be observed when adding new dense layer. Lastly, Figure [o(c) investigates the relation between sparsity and transfer ratio (recall that we only transfer WS rather than GS), where we can see that the performance the target task decreases as the sparsity of GLT increases.
17


Reviews:
[{"review_id": "w1EYChgpbg", "reviewer": "Reviewer_75Eg", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper extends UGS in order to improve its performance when the graph sparsity is high. The authors observe that the performance of UGS drops when the graph sparsity goes beyond a certain extent. The authors explain that this is due to the fact that only a small portion of the elements in the adjacency matrix are involved in the loss calculation. To address this problem, the authors introduce a new loss term to take into account all the elements of the adjacency matrix. They also improve the robustness of lottery tickets with sparse graphs by defining graph pruning as an adversarial graph perturbation and formulating it as a min-max optimization problem.", "summary_of_the_review": "I think that this paper could be a solid work if the experimental evaluation is improved by adding some experiments on more reliable datasets (see comments above).", "strength_and_weaknesses": "Strengths:\n- the paper is well written and easy to follow\n- the proposed method effectively solves one of the main weaknesses of UGS\n- the proposed method significantly improves the performance of UGS \nWeaknesses:\n- the experiments that assess the performance of the proposed sparsification method are conducted on three datasets: Cora, Citeseer and Pubmed. Even though these datasets are quite popular in this field, it is well known that they are not very reliable (see, e.g., the discussion in [*]). For this reason, it is better to evaluate the performance on other datasets such as OGB datasets or [*] in order to fairly assess the performance of the proposed method.\n- the analysis on the transferability of graph lottery tickets seems a bit disconnected from the rest of the paper. If I understood the paper correctly, the main goal of the paper is to propose a method for improving the performance of UGS on sparse graphs. The focus of this part is thus on the sparsity of the graph. Instead in Sec. 4 the authors analyze the transferability of the sparsified subnetwork to others graphs. Then, the focus in this case is on the sparsity of the network. For this reason, I cannot see the connection between this section and the rest of the paper. In addition, it doesn't seem to me that the proposed method can provide some advantages with respect to the transferability of the lottery ticket.\n\n[*] Dwivedi et al., Benchmarking Graph Neural Networks", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "XUPjMezYet", "reviewer": "Reviewer_FtWv", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper focuses on improving lottery tickets on GNN. Although existing work (UGS) prunes graph and weight simultaneously,  the performance degrades significantly when graph sparsity is high.\nThe paper found out the problem in UGS lies in the loss formulation for pruning adjacency matrix, as it does not involve all edges for back propagation.To solve this, they add a new auxiliary loss head that measures the inter-class separateness of nodes with Wasserstein distance to better guide the edge pruning.\nThe paper also proposed an adversarial perturbation technique, which formulates the pruning process as a min-max optimization problem.   This helps improve the robustness of their graph lottery tickets against the graph sparsity.\nAdditionally, the paper explored graph transfer learning by running node classification tasks on two citation networks.\nResults on three GNN models with multiple datasets show improvement over the existing LTH method.", "summary_of_the_review": "Generally speaking,  the paper has decent quality. \nMy concern lies in the significance of novelty and performance gain over existing works.", "strength_and_weaknesses": "Strengths:\n1. The paper is easy to follow. The paper describes the disadvantage lies in existing work and then introduced there methods for improving. \n2.  Experimental on multiple GNN models (GCN , GAT, and GIN) and datasets (Cora, Citeseer and PubMed, Arxiv and MAG) seems to be sufficient.\n3. I like the ablation on the  auxiliary loss weights and the prune ratio combination of weight and graph.\n\nWeekness:\n1. The paper target the work UGS ( by Chen et al. ) directly, by improving the performance at a high graph sparsity. However, looking at Figure 5-7. I’m not sure if the improvement is significant enough, especially since some seems quite similar.\n2. Less comparison with other existing work. \n\nQuestions:\n1. How to get equation 10,11 from equation 9?\n2. In Figure 4, the trend of Randomly initialized GLT and GNN is very similar.  What sparsity is the GLT? Does sparsity effect the converging speed?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "WfcYgMNyMo2", "reviewer": "Reviewer_DAbQ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper studies the pruning problem of graph neural networks (together with the adjacency matrix). It claims that the GNN performance drops sharply when the graph sparsity is beyond a certain extent in UGS. To address this issue, this work adopts two approaches: (1) adding a new auxiliary loss based on WD to better guide the edge pruning by involving the entire adjacency matrix. (2) regarding unfavorable graph sparsification as an adversarial data perturbation and formulating the pruning process as a min-max optimization problem. Further, this paper investigates the obtained winning tickets under a transfer learning setting. ", "summary_of_the_review": "This paper addresses a challenging and practical problem. Although this paper has some merits, I would like to recommend \"borderline rejection\" before the rebuttal phase given the weaknesses listed above.", "strength_and_weaknesses": "Strength:\n1. This paper studies a practical and challenging topic in GNNs. As the scale of graph data becomes larger, it will indeed arouse our attention to graph pruning. \n2. This work formulates the pruning process as a min-max optimization problem to gain the robustness of lottery tickets when the graph sparsity is high, which is novel to me.  \n3. This paper is easy to follow, with clear motivation and questions to address.\n\nWeaknesses:\n1. Firstly, I am extremely confused about the relationship between the problem caused by the excessive graph sparseness and the GNN transfer learning problem studied in this paper. The latter one (graph transfer learning) seems an independent part. Moreover, regarding transferring winning tickets, it seems that [1] has already done it. \n2. The loss function in UGS is $L_{UGS} = L({m_g⊙A,X},m_θ⊙Θ)+r_1 ||m_g ||_1+r_2 ||m_θ ||_1$. Note that there are regularization terms in the loss function to control model sparsity and graph sparsity, but this paper only has the cross-entropy loss. It seems inconsistent and unfair to compare your model with UGS.\n3. The paper uses too much vspace, resulting in an unfriendly layout for the audience. a) The formula of the “graph sparsity” and “weight sparsity” take up too much space. b) The layout of Figure 1 and 2 can also be adjusted accordingly (e.g., combining them). c) The whole algorithm process is a bit laborious for me to read, especially how to perform the network training process. An algorithm table may help. \n4. The paper separates the potential nodes of class c and the other nodes by Eq. (3), is the node number of $c$ identical to $\\bar{c}$? Can the Wasserstein distance measure the distance between two different node number distributions?\n5. The authors only evaluate the proposed method on 2-layer GNNs, which is not universal and convincing. For some deep GNNs, do we obtain similar observations to Figure 1? In my view, a very deep GNN can pass gradients to most of the edges.\n6. The improvement of the proposed method over UGS is not significant as shown in the experiments. I believe this work still has space to improve.\n\nI may have some misunderstanding above, please feel free to correct it in the rebuttal phase. Thank you.\n\n====after rebuttal====\nW1-W4 have been addressed by the authors. I still have concerns with W5 and W6.\n\n\n\n\n[1] Morcos A, Yu H, Paganini M, et al. One ticket to win them all: generalizing lottery ticket initializations across datasets and optimizers[J]. Advances in neural information processing systems, 2019, 32.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster