Searching Lottery Tickets in Graph Neural Networks: A Dual Perspective
Authors: Kun Wang
Yuxuan Liang
Pengkun Wang
Xu Wang
Pengfei Gu
Junfeng Fang
Yang Wang
Venue: ICLR 2023 poster (2023)
Keywords: Lottery Tickets Hypothesis
Dual Lottery Tickets Hypothesis
Graph pooling
Graph information bottleneck

Abstract: Graph Neural Networks (GNNs) have shown great promise in various graph learning tasks. However, the computational overheads of fitting GNNs to large-scale graphs grow rapidly, posing obstacles to GNNs from scaling up to real-world applications. To tackle this issue, Graph Lottery Ticket (GLT) hypothesis articulates that there always exists a sparse subnetwork/subgraph with admirable performance in GNNs with random initialization. Such a pair of core subgraph and sparse subnetwork (called graph lottery tickets) can be uncovered by iteratively applying a novel sparsification method. While GLT provides new insights for GNN compression, it requires a full pretraining process to obtain graph lottery tickets, which is not universal and friendly to real-world applications. Moreover, the graph sparsification in GLT utilizes sampling techniques, which may result in massive information loss and aggregation failure. In this paper, we explore the searching of graph lottery tickets from a complementary perspective -- transforming a random ticket into a graph lottery ticket, which allows us to more comprehensively explore the relationships between the original network/graph and their sparse counterpart. To achieve this, we propose regularization-based network pruning and hierarchical graph sparsification, leading to our Dual Graph Lottery Ticket (DGLT) framework for a joint sparsification of network and graph. Compared to GLT, our DGLT helps achieve a triple-win situation of graph lottery tickets with high sparsity, admirable performance, and good explainability. More importantly, we rigorously prove that our model can eliminate noise and maintain reliable information in substructures using the graph information bottleneck theory. Extensive experimental results on various graph-related tasks validate the effectiveness of our framework.

Published as a conference paper at ICLR 2023
SEARCHING LOTTERY TICKETS IN GRAPH NEURAL NETWORKS: A DUAL PERSPECTIVE
Kun Wang', Yuxuan Liang*, Pengkun Wang?, Xu Wang?, Pengfei Gu²,
Junfeng Fang', Yang Wang
1.23-
Key Laboratory of Precision and Intelligent Chemistry, University of Science and Technology of China (USTC), Hefei, China
2 School of Software Engineering, USTC. Schooo of Data Science, USTC.
*National University of Singapore, Singapore
(wk520529, pengkun, wx309, fjf, 9pf9061 Jm i ustc..tt... eew..eedu.coo angyangustc.co edu. cn" iux www.ootttooocooooooooooo.oo com"
ABSTRACT
Graph Neural Networks (GNNs) have shown great promise in various graph learn- ing tasks. However, the computational overheads of fitting GNNs large-scale graphs grow rapidly, posing obstacles to GNNs from scaling up to real-world ap- plications. To tackle this issue, Graph Lottery Ticket (GLT) hypothesis articu- lates that there always exists sparse subnetwork/subggaph with admirable per- formance in GNNs with random initialization. Such a pair of core subgraph and sparse subnetwork (called graph lottery tickets) can be uncovered by iteratively applying a novel sparsification method. While GLT provides new insights for GNN compression, it requires full pretraining process to obtain graph lottery tickets, which is not universal and friendly to real-world applications. Moreover, the graph sparsification in GLT utilizes sampling techniques, which may result in massive information loss and aggregation failure. In this paper, we explore the searching of graph lottery tickets from complementary perspective transform- ing a random ticket into a graph lottery ticket, which allows us to more compre- hensively explore the relationships between the original network/graph and their sparse counterpart. Compared to GLT, our proposal helps achieve a triple-win situation of graph lottery tickets with high sparsity, admirable performance, and good explainability. More importantly, we rigorously prove that our model can eliminate noise and maintain reliable information in substructures using the graph information bottleneck theory. Extensive experimental results on various graph- related tasks validate the effectiveness of our framework.
INTRODUCTION
Graph Neural Networks (GNNs) Kipf & Welling (0166; Hamilton et al. (2017) have recently emerged the dominant model for diversity of graph learning tasks, such as node classification
Velickovic et al. (2017). link prediction Zhang & Chen 2019). and graph classification Ying et al. (2018). The success of GNNs mainly derives from a recursive neighborhood aggregation scheme, I.c., message passing, in which each node updates its feature by aggregating and transforming the features of its neighbors. However, GNNs suffer notoriously high computational overheads when scaling up to large graphs or with dense connections, since conducting message passing over large or dense graphs proves costly for training and inference Xu et al. (2018); You et al. (2020).
To alleviate such inefficiency, existing approaches mostly fall into two research lines that is, they either simplify the graph structure or compress the GNN model. Within the first class, many studies Chen et al. (2018); Eden et al.) (2118: Calandriello et al. (2018) have investigated the of sam- pling to reduce the computational footprint of GNNs. These sampling-base based strategies are usually integrated with mini-batch training schedule for local feature aggregation and updating. Another representative is graph sparsification techniques Voudigari et al. (2016); Zheng et al. (2020); Li et al. (2020b) which improve training inference efficiency of GNNs by learning remove redun- dant edges from input graphs. In contrast to simplifying the graph structure, there are much fewer prior studies on pruning or compressing GNNs Tailor al. (2020), as GNNs are generally less parameterized than DNNs in other fields, e.g., computer vision Wen et al. (2016) : He et al. (2017).
Yang Wang and Yuxuan Liang the corresponding authors.

---

Published as a conference paper at ICLR 2023
Further, Graph Lottery Ticket hypothesis (GLT) Chen et al. (2021) has surprisingly killed two birds with one stone, i.c., for the first time it simultaneously simplifies the imput graph and prunes the GNNs without compromising model performance. The key insight is to generalize the theory of Lottery Ticket Hypothesis (L.HH) Frankle & Carbin (2018) to GNNs. Recall that LTH articulates there always exist sparse and tigh-performance subnetworks in dense network with random ini- tialization (like winning tickets in a lottery pool), GLT delineates Graph Lottery Ticket as a combination of core subgraph and sparse subnetwork with admirable performance. More specifi- cally, GLT first devises unified GNN sparsification (UGS) strategy for jointly pruning the graph adjacency matrix as well as the network weights, and then iteratively applies UGS to uncover the winning tickets in GNNs. Extensive experiments on GNN benchmarks have verified the effective- ness of GLT across various architectures, learning tasks, and initialization ways.
After revisiting the theory of GLT, we expose two crucial factors that may impede GLT in practice. Firstly, GLT takes a whole pretrain- ing process to obtain a sparse subnetwork, which limits its applicability to real- world us- ages and meanwhile complicates the investi- gation of the relationships between the origi- nal network (or graph) and their sparse coun- graph
GGT
Figure 1: Left: graph before sparsification. Right: a sparse graph obtained by GLT'Chen et al. (2021) The red star (*) denotes node that connects two important communities. After adopting GLT, it can be seen that the edge connecting the two commu- nities is discarded. Consequently, * can no longer aggregate information from both sub-structures. "unimportant" edges may be discarded by means of a pruning algorithm, but sometimes they connect two very important local communities (see Fig. [
terparts. Secondly, the sampling-basee simplification in GLT may lead to two devas- tating challenges: a) Information loss: prun- ing subgraph edges as GLT does may cause massive information loss, resulting in perfor- mance collapse Wu et al.] (2022a). b) Aggre- gation failure: as the sparsity increases, some
In this paper, we investigate a more universal yet challenging problem from a complementary per- spective of GLT: how to transform a randomly selected ticket (i.e., pair of graph and network) to a graph lottery ticket in GNNs? Compared to the magnitude-basee baseed network pruning and graph sparsification in GLT, such transformation process enables us to more comprehensively explore the relationships between the original network/graph and their sparse counterparts. Two-fold efforts made by us to answer the above question, including regularization- -based network pruning and hicrarchical graph sparsification.
Primarily, we present the first attempt to generalize the Dual Lottery Ticket Hypothesis (DLTH) Bai iet al. (2022) for GNN network pruning. Being initially designed for pruning deep neural networks, DLTH utilizes Gradually Increased Regularization (GIR) term Wang al. (2020a) transfer the model expressivity from the discarded part to the remaining part. When adapting to GNNs, we first randomly select target sparse subnetwork within the original dense network, and then attach GIR on the rest part to stimulate magnitude discrepancy among the parameters. In other words, as the regularization penalty factor increases, the information is continuously extruded from the rest part into our target subnetwork. Once the difference among parameters is discrepant enough, we remove the rest part to realize a final sparse network.
However, GIR is not applicable to graph sparsification when generalizing DLTH for finding graph lottery tickets. To this end, we propose Hierarchical Graph Sparsification (HGS) that is not only compatible with the -ased pruning strategy but also mitigates the information loss and aggrega- tion failure issue in GLT. HGS learns a differentiable soft assignment matrix for nodes at each GNN layer, projecting nodes to a set of clusters which is then utilized as the coarsened input for the next GNN layer. Hierarchical representations of graphs are produced accordingly. Finally, we element- wise product the adjacency matrix of the coarsened graph at each GNN layer with a trainable mask for graph sparsification. In this way, useful information is extruded into the anticipative structure, thereby avoiding massive information loss. Note there are no node or edge dropping operations in our method, HGS can naturally remedy the aggregation failure in GNNs as well.
We elaborately unify the above regularization- based pruning and hierarchical graph sparsification into single framework for transforming a random-selected ticket into a graph lottery ticket in GNNs, leading to dual perspective of GLTT. We therefore name our framework as Dual Graph
2

---

Published as a conference paper at ICLR 2023
Lottery Tickets (DGLT). Similar GLT, DGLT is model-agnostic and makes assumptions on the graph structure, and can be easily applied and scaled up to a variety of graph- susp-bbsed learning tasks. To enhance its explainability, we theoretically prove our information extrusion approach from the popular Graph Information Bottleneck (GIB) theory. Our contributions are summarized as follows:
We explore new and non-trivial problem of transferring random ticket to graph lottery ticket in GNNs. Compared to GLT which pretrains dense GNNs to recognize graph lottery tickets, transferring a random ticket into pair of nigh-performance sparse network and core subgraph is more appealing and valuable in practical usage, which allows us to investigate the relationships between the original network/graph and their sparse counterparts in principle way.
We present the Dual Graph Lottery Ticket (DGLT) framework to transform a random ticket into a triple-win graph lottery ticket, i.e., with high sparsity, high performance, and good explainability. DGLT prunes the GNN architecture by GIR-based information extrusion and sparsifies the input graph in a hierarchical manner to defeat information loss and aggregation failure GLT. More- over, the graph information bottleneck theory is utilized to guarantee the algorithm's 's preeminence.
Extensive experiments are conducted on GNN benchmarks to examine our DGLT. The results show that DGLT consistently outperforms GLT across various graph/network sparsity over these benchmarks, For node classification, DGLT achieves 40% ~ 85% graph sparsity and 65% ~ 92% weight sparsity (no performance degradation), with about 13% ~ 30% sparsity improvement on graph and 5% ~ 10% weights sparsity improvement. For large-scale dataset, i.e., Ogb-Collab, our model can obtain graph lottery tickets with nearly 43% sparsity gain on the graph. These findings demonstrate its potential in a wide range of real-world applications.
PRELIMINARY & RELATED WORK
Graph Neural Networks. Given an undirected graph G = (V.E) with a node set V and an edge set ε, GNNs aim to learn a representation vector of a node or entire graph based the adjacency matrix A E [V) and node features X R| Modern GNNs mostly follow message passing strategy, in which we iteratively update the representation of a node u, E V by aggregating and transforming the representations of its neighbors. For example, Kipf & Welling (2016) propose two-layer GNN with learnable parameters θ = ((1) for node classification as:
2 = S (Ao (Ax ea). and L (G, 0) - () E Velog (2)) is the loss function,
where 2 is the prediction results, o (-) denotes an activation function, Å -- (A I) D- is the normalized adjacency matrix with self-loops and Í is the degree matrix of A + To optimize such GNNs, we minimize the cross-entropy loss L (g. Q) over all labelled nodes V C V. where y: and 2; represents the label and prediction of node v, respectively, More message passing schemes have been investigated in Hamilton et al. (2017); Velickovic al. (017): Li et al. 2020a).
Despite the promising results obtained by GNNs, they encounter notorious inefficiency when scaling up to large or dense graphs. Many streams of work have been dedicated to solving this issue. Graph sampling or sparsification accelerates the representation learning process of GNNs by manually or
automatically extracting a sub-structure from the original graph Cheng al. (017); Chen et al.
(2018); Rong et al. (2019): Li et al. (2020b); |aber et al. (021)) Graph compression algorithms attempt to merge an original graph to form new small graph for fast representation learning Chakeri et al. (2016); Chiang et al. (011)). Tailor et al. (2020); Zhou et al. 1); Chen et al. (2022) prune GNNs for speeding up reasoning. Recently, G et al. (202 has presented the first attempt to jointly sparsify the input graph and the GNN model, which significantly trims down the computational cost without compromising predictive accuracy. More importantly, GLT has opened
up novel research line to the graph learning community on which our framework is built.
Lottery Ticket Hypothesis. LTH articulates that sparse and admirable subnetwork can be identi- fied from dense network by iterative pruning Frankle & Carbin (2018). LTH is initially observed in
dense networks and is broadly found in many fields Evci et al. (200)) Frankle et al. (2020); Malach
et al. (2020): Ding et al.] (2021); Chen et al. (2020a) 202 1); Sui et al. (2021). Derivative theories Chen et al. (2000b); You et al. ()021): Ma et al. (2021) are proposed to optimize the procedure of network sparsification and pruning. In addition to them, Dual Lottery Ticket Hypothesis (DLTH) considers a more general case to uncover the relationship between a dense network and its sparse counterparts Bai et al. (002).. It argues that when attaching GIR to pre-selected part of dense
3

---

Published as a conference paper at ICLR 2023
Details of DGLT
Overview of DGLT
Hierarchical graph sparsification (HGS)
Inputs
GNN ngs
Softmax
GNN lggs
S00
Pre selected sub of netwark and graph
Adjaconcy Anatrili
Pretrain
One-shot
pruning
(3) GNN
om
GNN
Increased regulrization
Fine-tune
Input feature X
Embedding
Gradually Increasing Regularization (GIR)
Sparsfiication
Joint
Pre-defined sturcture
High sparsity
Admirable accuracy
Good explanability
Triple-win!
5(L
Predictor
Subnetwork
GNN
MLP
Lightweight Subnetwork
subgrophh
Graph Lottory Ticket
Subgraph
subnetwork
Figure 2: (Left) The overview of DGLT. (Right) The details of DGLT algorithm.
network, the complementary part can be transformed into an excellent winning ticket in an isolated training way. In this paper, draw inspiration from DLTH and for the first time explore a dual problem of GLT, i.c., how to transform a random ticket into graph lottery ticket GNNs.
3 METHODOLOGY
Figure2 presents an overview of our DGLT for transforming a random ticket to a graph lottery ticket in GNNs. The first step is selecting target structure for subnetwork and subgraph. After that, the network is pretrained with Gradually Increased Regularization (GIR) for information extrusion. We meanwhile perform Hierarchical Graph Sparsification (HGS) to produce coarsened subgraph repre- sentations at each GNN layer. When GIR reaches a threshold, we stop adding penalty factors and train GNNs until the loss converges. Finally, we prune the network/graph for joint sparsification with one shot and fine-tune the pruned model to obtain graph lottery tickets for evaluation. In the following parts, we commence by introducing HGS in Sec. [3.] and then elaborate on how GIR benefits the sparse network training by extruding information from other weights to the target sparse structure (see Sec. 3.2). We further theoretically justify DGLT's power in transforming graph lottery tickets using the popular Graph Information Bottleneck (GIB) theory in Sec. 3.3 Frequently-use notations are listed in Appendix for clarity.
3.1 HIERARCHICAL GRAPH SPARSIFICATION
Inspired by recent advances in clustering-based graph pooling methods Wu al. (202aa); Ying ett al.) (2018); ; Roy et al. (202T), we propose Hierarchical Graph Sparsification (HGS) to generate hierarchical graph representations across different GNN layers for graph sparsification, where the number of nodes is reduced as the GNNs go deeper. Towards this goal, HGS learns differentiable soft assignment matrix for nodes at each GNN layer, mapping input nodes to multiple clusters which are then fed to the next GNN layer as coarsened inputs.
As seen in Fig. 2 HGS learns the embedding representation z( and assignment matrix 5(1) at layer I (1= 1,2 L) via two non-shared GNNs layers, respectively. To be specific, we first adopt GNN sparsification layer (denoted as GNN( after each GNN embedding layer (denoted as GNN()) em) for projecting nodes a set of feature clusters (!) and coarsened adjacency matrix (1)), which are then utilized as the coarsened input for the next GNN layer or final prediction. To facilitate subgraph
hgs))
generation, we impose a differentiable mask m A for (00) in the hierarchical sparsification process:
(1)
(
GNN()) em
(A x( (1)
(1)
4

---

Published as a conference paper at ICLR 2023
s()) = softmax (GNN)) hgs (A"-1) @ mma 1111)
1 ))
(2)
For Eq. 1 embedding GNN at I-th layer applies ( and A to produce node embed- ding representation 7 for clustering in next sparsification layer. For Eq. _ ① is the element- wise product operation, softmax function is applied in a row-wise fashion. assignment matrix s(t) E I 1x"; (m-1 > n)) can project coarsened subgraph into ny clusters. Notably that, in our implementation, we hope that n4-1 is slightly larger than ny to ensure that graph information in the hierarchical clustering process extrudes steadily into small sub-structure. Given the embedding z()) and assignment matrix g(t),, we apply the following equation obtain adjacency matrix A and embedding X in the next layer:
A 500 S()) X S 2
After L times of iterative embedding and sparsification of the input graph, we can obtain resilient subgraph representation Ghgz { x in the last layer L, where ( denotes the connec- tivity between each pair of subgraph clusters and (() represents new node representation.
3.2 GRADUALLY INCREASED REGULARIZATION FOR INFORMATION EXTRUSION
Hutter (2018), is one of the most popular regularization terms. L2 regularization draws the weights closer to the origin by adding constraint term Q (w) a | 2 the loss function, where a represents the penalty coefficient. BaT et al. 2022) presents the first attempt to leverage L2 regularization to extrude information from pre-selected part its complementary counterpart. It demonstrates that when progressively increasing the penalty coefficient by adding a mini-step value, the difference between the weights will be separated and the unimportant weights naturally pushed to a position close to zero LeCun it al. (1989); Wang et al. (2020a) (see proof in Appendix A))
L2 regularization, commonly known as weight
As depicted earlier, we get a sparse] representation Gsub- Then, we directly ceament-produce A (L) and trainable mask m (L) and send combination of m m @ A44) with (4) to GNN and MLP-
layer predictors for label forecasting (Bottom right in Fig. 2p. For DGLT framework, we pick a
sparse network structure from the whole network parameters O and trainable matrices, then attach GIR on the rest part to extrude information toward the target structure. DGLT can be achieved as optimization following objective function:
LDGLT = == [(mmA @ Auu, x), +
+ + 1110112
(4)
<(pt1)= = g(v) + Ea g(v)= < Eveil
plott)= = plr) + Pa p(v)) < Poeit
(5)
{()))
{(n) Eceil
xiP)) p(n) Peest
In Eq. 4 mA and Aatl denote the mask sets and adjacency matrices of all sparsification layers; in addition to the cross-entropy loss, the objective function contains two L2 regularization terms, where m² and O* are pre-selected parameters in mA and e which will be discarded after pretraining Finally, under the interplay of progressively mini-step addition of regularization penalty, the m and e* are pushed to a position close to zero, and the information is extruded to the target part. In Eq. [ {(p) and pfr) are the regularization terms at p-th updating. &a and Pa indicate increased mini-step values of penalty coefficient. Eoeil and Peeil indicate ceiling values of two regularization terms. We set range of regularization terms and control regularization value increases in linear fashion until reaches their ceiling. To facilitate reading, we show the algorithm in Algo. [
3.3 GIB VIEW OF GRADUALLY INCREASING REGULARIZATION
Graph Information Bottleneck (GIB): Information Bottleneck (IB), which originates from the in- formation theory, aims find a compression code of the input signals while retaining as much valid information as possible from the original encoding Tishby et al. (2000). In recent years, IB is natu- rally adapted to deep neural networks a variety of applications and shows excellent effects Peng et al. 2018); Luo et al. (2019): Wang et al. (2020b); Wu et al. (2020); Yu et al.) (2020) Miao et al.
(2022). 9. Our work builds upon graph field and often known as Graph Information Bottleneck (GIB),
|
DDifferent from pruning, we transform graphs into small size representations and note sparsity ratio. [1-Ilg and F-1 the number of non-zero elements and total number of elements, respectively.
[A] as
5

---

Published as a conference paper at ICLR 2023
as defined above, Y (21.Y2... .r..:...... .yy) denotes the label of all nodes and G is the imput graph. GIB-based methods try to find an optimal subgraph 93 in subgraph set aub (9) by optimizing:
maa.g..nGG.... (Geub: Y) - 31 (Gsub: 9) 9
(6)
9sub denotes a subgraph of the 9 and T (() represents Shannon mutual information. / is the hyper- parameter used to control the proportion of the two parts. In Eq. 6 The first term is used to maximize the mutual information of subgraphs and labels, and the second term wants the subgraph to be as small as possible. GIB theory tries to identify unserviceable or noisy nodes of the training graph- structured data describe spurious corelation-versu--causiiii means that after the introduction of nodes or graphs in the training set cannot increase or even reduce the mutual information between the training set and the tabel/Glymou et al. [016):[Aroovskk et al. (2019); KKueger al. (202T). Different from sampling models, we try to transform a full graph into G through a transformation function T (*) (i.e., gradually increasing regularization) and guarantee spurious correlation removal (satisfies Eq. 6). We will provide theoretical analysis of how DGLT can obtain an admirable subgraph from GIB perspective.
Intuitively, a spurious correlation
when the penalty is increased at the same pace, because of different local curvature structures, the weights respond differently weights with larger curvature will be less moved. As such, the magnitude discrepancy among weights will be magnified as regu- larization grows. Ultimately, the weights will naturally separate (unimportant weights tend to be very small and can be regarded as noise) Wang et al. (2000a).
Lemma 1:
Sampling--aase based algorithms
Information extrusion
Pure contribution nodes
Pure noise nodes
Postiiee contribution nodes
Negotive contribution nodes
GOLT algonithms
Pre- Pre-defined structure
T(-)
Based on Lemma 1, we list our two observations about spurious correlations distribution in graph: (1) Some nodes are pure noise; (2) Some node are composed of bootless correlations and useful associations. Un- der these two Observations. We can get such solution: Suppose each G contains subset Gub (9), there exist G E G gub (9) can remove spurious correlations, i.e., ( Z I (G. Y). Unserviceable or noisy infor- mation are distributed in graph node features. In our implementation, we can transform a to 9 and make sure that (G::Y 2 (9 Yg.
Spurious correlations remova)
Figure 3:
The white/blue node indicate that all features can /ncrease/decrease 7 (G, Y). while the green/yellow nodes indicate that there are useful associations and false as- sociations in the nodes, but in the end, the useful/spurious association dominates
Theoretical Analysis. Obs 1: There exist pure noise nodes (note nodes set as Gont) which make no contributions to 7 (G, Y)) at all. Considering that our target is to maximize T (9 Y):
(Grub, Y)=
9, - 99 = 1 9) - 1 9Y; Gent)
(7)
Where the first equality because Chain Rule for Mutual Information and the second equality is because Godd E Godd (9). T(: G) is given from the beginning, so 7 GY; is a constant. Our target is to maximize (Gsub, Y) (i.e., minimize the I (Y; GIGsus)). Since all nodes in Goub are noise, 1 (G.ndr Y) in 1 YG 1 (Grrmu Y) r)=
(goutr Y) reach the minimum. In GIB, G == G' For gradually increasing regularization, we can extrude information a pre-defined structure. Since Soub are unserviceable, the amount of information squeezed is 0 in transformed 9;- Based on the above inference, we can obtain (9;, Y) 1 (g=: Y) in Obs 1.
Theoretical Analysis. Obs 2: The spurious information is distributed in some nodes and these nodes are composed of valid information and spurious information.
Suppose nodes set with spurious information is G.ub ( Saub where nodes in G make
positive contributions to I (G.Y) and Gr... makes no (even negative) contributions to I [ Y). I (G, Y) reaches the maximum when 9;- = G G' In our implementation, we extrude information to Oz by training masks, and unimportant weights in masks tend to be exceedingly small and can be

---

Pretrain Published as a conference paper at ICLR 2023
regarded as noises. In this cireumstance, 93 contains at least more useful information than 9ن under the same sparseness as 9 We can obtain I (o: Y) > I (0;, Y) Yg) in Obs 2.
To summarize, DGLT can obtain a comparable (even better) subgraph compare to the sampling- based algorithm. The difference between DGLT and other sampling methods is shown in Tab. - Table 1: Comparison between our DGLT, LTH Frankle & Carbin (2018), DLTH Bai al. (2022) and GLT Chen et al. 202TT. Pruning, graph controllability, network controllability, transformation, and pretrain denote the type of pruning process, if sparse graph structure is controllable, sparse
network structure is controllable, if the selected subnetwork needs transformation before fine-tuning, and if pretraining dense network is needed, respectively.
Methods
Pruning
Graph controllability Network controllability
Transformation
LTH Iterative
Infeasible in GNNs Infeasible in GNNs
No
Yes
DLTH GL.T Iterative
One-shot
Yes
No
No
Yes
DGLTT (ours)
One-shot
Yes
No
4 EXPERIMENTS
In this section, we conduct extensive experiments to answer the following research questions: RQ1: How effective our proposed DGLT algorithm in transforming a random ticket to a pair of sparse subnetwork and subgraph? RQ2: Can DGLT scale up to large-scale datasets? RQ3: Under a certain sparse ratio of subgraph (or subnetwork), how does the other ratio affect the model performance? RQ4: How does the proposed hierarchical graph sparsification impact the results? RQ5: How should we set the mini-step values of the increased regularization force?
4.1 EXPERIMENTAL SETTINGS
Datasets. Six benchmarks for GNN evaluation are employed in this paper to verify the effectiveness of our DGLT. To be specific, we choose three popular graph-based datasets, including Core, Citeseer and PubMed Kipf & Welling (2016) for node classification and link prediction. To test the scalability
of DGLT, we further use a large-scale dataset called Ogbl-Collab Hu et al. (2020) for link prediction.
Finally, we examine our algorithm for graph classification on D&D Dobson & Doig (0033) and ENZYMES Borgwardt et al. (2005). The statistics of these datasets can be seen in Table
Backbones & Parameter Settings. For all selected backbones and datasets, we compare our DGLT algorithm with GLT Chen et al.) (202T) and the random pruning algorithm under the same network settings. For regular-scale datasets, we adopt GCN & Welling (2016), GIN et al. (2018) and GAT Velickoić et al. (2017) as backbones. For Cgbl-Collab which is a large-scale dataset, we take 28-layer deep ResGCNs et al. (2020a) as our backbone for link prediction. To evaluate our DGLT on the graph classification task, GraphSAGE| Hamilton et al. (2017) is leveraged as the backbone on HHamiton
D&D and ENZYMES. More details about experimental settings can be found in Appendix F
4.2 CAN DGLT FINDS GRAPH LOTTERY TICKETS? (RQ1)
To answer RQL, we compare our DGLT with GLT and random pruning on node classification. When investigating how accuracy changes with the growth of graph sparsity, we fix the weight sparsity to zero for stability, and vice versa. The results Citeseer and PubMed are depieted in Fig. 4 and
those on Cora is shown in Fig. g From Fig. and g we have the following observations:
(1) DGLT consistently outperforms GLT and random pruning under the same graph/weight sparsity over all datasets, verifying the superiority of transforming a random ticket to graph lottery ticket via information extrusion and hierarchical graph sparsification. For example, the graph lottery ticke 2 on PubMed+GIN identified by DGLT is with 85% graph sparsity or 87% weight sparsity. For Citeseer+GIN we can obtain it with 65.0% and 91.0% sparsity on graph/weights using DGLT. As for random pruning, the effectiveness of the model decreased significantly when the sparsity rate increased, which further demonstrate the superiority of our DGLT algorithm.
(2) DGLT for the first time enables us to search an altra-lightweight subnetwork in GNNs. For node classification on Cora and Citeseer, the model surprisingly shows no significant performance
In our experiments, we specify graph lottery ticket as pair of subgraph and subnetwork with comparable accuracy the baseline of full GNNs on full graphs.
7

---

Published as a conference paper at ICLR 2023
ChseeHOCK
GloverGNN
Accuracy
08
65
Soulica
50
Taacke
Indix IIITIOO
DOLD00ss
QET
GIT
Isaton Fraang
Varske Fanne
Graph sparsity
Graph sparsity (%)
Graph sparsity (%)
ChseriGat
Aucuracy (%)
8
DO
Fanken Prilig
30
9
Ø
70
10
20
20
66
12
52
30
5J
Weight sparsity (%)
Weight sparsity (%)
Weight sparsity (%)
Proidd GIN
Prinded GAT
Accunccy (%5
Bucli
DOLD
Proms
Fandes Tranis
Rander Frakk
Graph sparsity (%)
Graph spansity (15
Graph sparsity (%)
PANNed-GEN
PAMMel-GAT
Accuracy (%)
Rodiwr
Bud
Budix
Praiko
Weight sparsity (%)
Weight spansity (%)
Weight sparsity (36)
Figure 4: Results of node classification over Citeseer/PubMed with GCN/GIN/GAT backbones.
Blue dash lines represent the baseline performance of full GNNs on full graphs.
drop (even surpassing the baseline performance) until 90% weight sparsity. For larger dataset (i.e., PubMed), DGLT achieves 85.0% graph sparsity without performance degradation. We demonstrate that DGLT transforms graph lottery tickets by GIR, which can remedy the information loss and thus transfer a more informative pair of subgraph and subnetwork.
(3) Whether we can find an extremely sparse subgraph depends on the property of input graphs. Though DGLT can help find extreme sparse subgraphs in GNNs (c.g., on PubMed+GIN or PubMed+GAT), this phenomenon does not occur in smaller datasets (c.g., Cora). We argue that the graph property such as graph size may be an crucial factor to the possibility of transforming a very sparse subgraph. This question will be discussed further in Sec. 4.3 Besides node classification,
present additional empirical results on link prediction in Appendix
4.3
HOW DOES DGLT PERFORM ON LARGE- DATASET (RQ2)
To answer RQ2, we conduct exper- iments on the Ogbl-Collab dataset using ResGCNs We show the potential of DGLT in practice by evaluating the trade-off among the reasoning time overhead, accuracy, and memory savings. As shown in Fig. 3 DGLT performs better than GLT and random pruning across different graph sparsity and weight sparsity. By using DGLT, we can obtain a graph lottery ticket with nearly 70% graph sparsity and 85% weight sparsity which outperforms GLT by 6%~7%% Meanwhile, we find that DGLT is more stable on large-scale datasets. Similar to DGLT's performance on PubMed, as graph sparsity increases (until ~90% sparsity), we witness slow decline in performance, but there was a very obvious fluctuation in the small datasets (e.g. Cora), which shows that DGLT is more stable and conducive expanding to large-scale datasets.
55
the backbone.
41
Beatis:
Buelin:
(GL
DGLT)DDa))
GLT
GLT
Fracing
Pharing
32
10
20
50
50 90
30
40
30
Groph spansity
Weight qanstyy
Figure 5: Link prediction results on Ogbl--ollaa--ReSCCNN
8

---

Published as a conference paper at ICLR 2023
4.4 ABLATION STUDIES (RQ3 & RQ4)
To complement the experiments in Sec. 4.2 we investigate more complex case described in RQ3 by controlling the graph sparsity P, or weight sparsity Po at a fixed ratio (10%, 30%, 50%, and 70%) and examining the model performance under different sparsity of the other term. The experi- mental results are reported in Fig. [6] It can be seen easily that each line has a similar trend both sub-figures, where the accuracy slightly drops as the growth of the graph (or weight) sparsity. For example, given Pe = 70%. we can obtain an admirable subgraph (with only 2% lower accuracy) under 40% graph sparsity. The sparsified GNNs preserve excellent performance (only 8%~14% decrease on accuracy) even when the sparsity reaches 90%. This indicates the capability of DGLT in transforming graph lottery tickets with comparable performance to the original backbone. More- over, we find that the lines in the right figure are more easily distinguished. When Pg = 30%, an expressive subnetwork achieved with 70% weight sparsity of the original network.
To evaluate hierarchical graph sparsification (HGS), we compare DGLT with its variant without HGS which attaches a trainable mask to the adjacency matrix at the last GNN layer for graph sparsification like GLT. As depicted in Tab. 2 DGLT surpass its variant without HGS by large margin under the same graph sparsity. Such merits stem from its hierarchical information extrusion strategy, which allows the input graph to transfer information to the final small-size graph in gradually compressed form and thus avoids the instability of one-shot rough extrusion.
Settings
Graph Sparsity
Datuset HGGS?
10%
20%
40%
60%
80%
Acuurey (%)
Cora
85.7
85.2
84.5
83.1
82.5
Tead
+GCN
x
81.1
81.4
80.9
78.1
71.2
X5%
17%
Pie 1%%
30%
Citescer
75.2
75.7
74.9
70.5
58%
+GIN
74.1
7188
67.4
65.3
PubMed +GAT
87.5
90.4
86.6
88.1
87.4
Spariitysity (16)
16
Wright spunstyy (%)
90 61
85.0
83.1
77.5
74.3
72.6
Figure 6: Effects of different pruning ratios for transforming
Table Effects of HGS over dif- ferent datasets and backbones.
sparse graphs and networks Cora+GCN setting.
4.5 MINI-STEP VALUES OF REGULARIZATION (RQ5)
We control graph/weight sparsity 30%/70% and choose multiple mini-step values of regulariza- tion (Ea and Pa take the same mini-step values) for comparison. From Tab. 33] we argue that the mini-step values of regularization should be maintained in a small regime. When the progressive regularization force maintain in larger regime (>5e-4), the model effect decreases significantly. We demonstrate that the process of information extrusion should be slow and excessive steps of in- creased regularization may cause the model to fall into ill-condition.
Table 3: Different mini-step values of regularization over Cora/Citeser//uubMeed with different backbones. For clarity, the highest/sccond--ighhsst performances are emphasized with red/blue fonts.
Settings
Ministeps of Regularization
Datasets
Methods
le-6
5e-6
le-5
5e-5
1e-4
5e-4
GCN (baseline=86.7286
84.9340.11
86 7670200088
86 18
162202
84.5240.17
82,44:028
01.16:0027
Cora
GIN (basclinc=85.911 91%)
84.17:00.08
85.41=0.14
85.01=0.22
84.8420.17
84.07:0.115
82.68:0.155
80.13::0.14
(baseline=85.43%
83.62-10.22
85.41:10.33
85.82=0.17
85.03:0.19
83.224-0.22
81.7240.18
80.25:10.44
GCN (baeling=75.73%)
74.7310.13
75.67:1017
76.22 0.23
76.7810.45
75,3810.46
71.741047
71.8910.65
Citeseer
GIN 166ellnee=66.449)
74.54-10.3
76.27:10.22
76.07-0.38
73.44:0.25
74.47:10.28
72.17:10.34
71.09-10.65
GAT (baselinc=766559)
75.27=00.18
76.67=0.24
75.81=0:23
74.93+0.35
74.83+0.18
72.82+0:47
70.88::0.72
GCN (haseline=85.1 1195)
84.25-10.13
85.17:10.24
85.74=0.25
83.24.10.22
83.16:10.46
81.87-10.17
79.82-10.11
PubMod
(baseline=84 84%)
84.01+0.111
84.84-0.17
17
84.35-0.13
12:0.55
82.834:0.25
81.1240..34
80.44-0.47
GAT (baseline=85.755) 73%)
84.08+:0.14
85.67=0.117
85.07=0221
83.58=0.34
82.77+0.37
81,05+0.288
79.89::0.45
5 CONCLUSION
In this paper, we propose novel framework entitled Dual Graph Lottery Ticket (DGLT) that couples hierarchical graph sparsification and gradually increasing regularization to achieve triple-win graph lottery tickets (with high sparsity, admirable performance, and good explainability). Our work first points out that an admirable subgraph can be obtained by efficient hierarchical compression, which helps defeat the off-and-shelf sampling-bass of the dual lottery tickets hypothesis for GNNs across various GNN backbones, learning tasks, and benchmarks. These explorations provide us a new perspective to uncover the relationships between the full model/graph and its sparse counterpart.
GNNs methods. We further generalize the key idea
9

---

Published as a conference paper at ICLR 2023
6 ACKNOWLEDGEMENT
This work is partially supported by the National Natural Science Foundation of China NNo.62074477, No. 12227011),) the Project of Stable Support for Youth Team in Basic Research Field, CAS (No. YSBR- Academic Leaders Cultivation Program, USTC.
REFERENCES
Martin Arjovsky, Léon Bottou, Ishaan Guirajani, and David Lopez-Paz. Invariant risk minimization. arXiv preprint arXiv: 1907v2997700299 2019.
Yue Bai, Huan Wang. Zhiqiang Tao, Kunpeng Li, and Yun Fu, Dual lottery ticket hypothesis. arXiv preprint arXiv:2203.04245 2022.
Karsten M Borgwardt, Cheng Soon Ong, Stefan Schönauer, SVN Vishwanathan, Alex Smola, and Hans-Peter Kriegel. Protein function prediction via graph kernels. Bioinformatics, 21(suppl 1): i47-i56, 2005.
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-697. PMLR, 2018.
Alireza Chakeri, Hamidreza Farhidzadeh, and Lawrence O Hall. Spectral sparsification in spectral clustering. In 2016 23rd international conference on pattern recognition (icpr), pp. 2301-2306. IEEE, 2016.
Shiyu Chang, Yang Zhang, Mo Yu, and Tommi Jaakkola. Invariant rationalization. In International Conference on Machine Learning, pp. 1448-1458. PMLR, 2020.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: fast learning with graph convolutional networks via 2018
importance sampling. arXiv preprint
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-15848 2020a.
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, 2021.
Tianlong Chen, Kaixiong Zhou, Keyu Duan, Wenqing Zheng, Peihao Wang, Xia Hu, and Zhangyang Wang. Bag of tricks for training deeper graph neural networks: A comprehensive benchmark study, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
Xiaohan Chen, Yu Cheng, Shuohang Wang, Zhe Gan, Zhangyang Wang, and Jingjing Liu. Earlybert: Efficient bert training via early-bird lottery tickets. arXiv preprint arXiv:2 101.0006,,, 2020b.
Yu Cheng, Duo Wang, Pan Zhou, and Tao Zhang. A survey of model compression and acceleration for deep neural networks. arXiv preprint 1wI.iv:1110.022000 2017.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsich. 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 & data mining, pp- 266-266, 2019.
Elliot Creager, Jömn-Henrik Jacobsen, and Richard Zemel. Environment inference for invariant learning. International Conference on Machine Learning, pp. 2189-2200. PMLR, 2021.
Shaojin Ding, Tianlong Chen, and Zhangyang Wang. Audio lottery: Speech recognition made ultra-lightteight, noise-robust, and transferable. In International Conference Learning Repre- sentations, 2021.
Paul D Dobson and Andrew Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of molecular biology, 330(4):771-783, 2003.
10

---

Published as a conference paper at ICLR 2023
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.
Utku Evei, 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.
Lukas Faber, Yifan Lu, and Roger Wattenhofer. Should graph neural networks use features, or both? arXiv preprint arXiv:2103.06857 2021.
edges,
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. arXiv preprini arXiv: /803:03333333 2018.
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel Roy, and Michael Carbin. Linear mode con- nectivity and the lottery ticket hypothesis. In International Conference Machine Learning, pp. 3259-3269. PMLR, 2020.
Madelyn Glymour, Judea Pearl, and Nicholas P Jewell. Causal inference in statistics: A primer. John Wiley & Sons, 2016.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Yihui He, Xiangyu Zhang, and Jian Sun. Channel pruning for accelerating very deep neural net- works. In Proceedings of the IEEE international conference 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 benehmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:221 2020.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works, arXiv preprint arXiv: 2016.
David Krueger, Ethan Caballero, Joemn-Henzi Henrik Jacobsen, Amy Zhang. Jonathan Binas, Dinghuai Zhang, Remi Le Priol, and Aaron Courville. Out-of-distribttion generalization via risk extrapo- lation (rex). In International Conference Machine Learning, pp. 5815-5826. PMLR, 2021.
Yann LeCun, John Denker, and Sara Solla. Optimal brain damage. Advances in neural information processing systems, 2, 1989.
Guohao Li, Chenxin Xiong, Ali Thabet, and Bernard Ghanem. Deepergen: All you need to train deeper gens. arXiv preprint arXiv:2006.0773, 2020a.
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.
Ilya Loshchilov and Frank Hutter. Fixing weight decay regularization in adam. 2018.
Yawei Luo, Ping Liu, Tao Guan, Junqing Yu, and Yi Yang. Significance-awart information bottle- neck for domain adaptive semantic segmentation. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 7778-67777,27 2019.
Xiaolong Ma, Geng Yuan, Xuan Shen, Tianlong Chen, Xuxi Chen, Xiaohan Chen, Ning Liu, Ming- hai Qin, Sijia Liu, Zhangyang Wang, et al. Sanity checks for lottery tickets: Does your winning ticket really win the jackpot? Advances in Neural Information Processing Systems, 34:12749- 12760, 2021.
Eran Malach, Gilad Yehudai, Shai Shalev-Schwartz, and Ohad Shamir. Proving the lottery ticket hypothesis: Pruning is all you need. International Conference on Machine Learning, pp. 6682- 6691. PMLR, 2020.
11

---

Published as a conference paper at ICLR 2023
Siqi Miao, Mia Liu, and Pan Li. Interpretable and generalizable graph learning via stochastic atten- tion mechanism. In International Conference on Machine Learning, pp. 15544.15543. PMLR, 2022.
Xue Bin Peng, Angjoo Kanazawa, Sam Toyer, Pieter Abbeel, and Sergey Levine. Variational dis- criminator bottleneck: Improving imitation learning, inverse rl, and gans by constraining infor- mation flow. arXiv preprint arXiv:1810.00821, 2018.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. arXiv preprint urXiv: 10903, 2019.
Kashob Kumar Roy, Amit Roy, AKM Mahbubur Rahman, M Ashraful Amin, and Amin Ahsan Ali. Structure- aware hierarchical graph pooling using information bottleneck. In 2021 International Joint Conference on Neural Networks (IJCNN), pp. 1-8. IEEE, 2021.
aware
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 at- tention for interpretable and generalizable graph classification. In Proceedings of the 28th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pp. 1696-1705, 2022.
Shyam Tailor, Javier Fernandez-Marques, and Nicholas D Lane. Degree-quant: Quantization-
aware training for graph neural networks. arXiv preprint S0ti::2008.00000 2020.
Naftali Tishby, Fernando Pereira, and William Bialek. The information bottleneck method. arXiv preprint physsic//0004057, 2000.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. stat, 1050:20, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 10903, 2017.
Elli Voudigari, Nikos Salamanos, Theodore Papageorgiou, and Emmanuel J Yannakoudakis. Rank degree: An efficient algorithm for graph sampling. In 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), pp. 120-129. IEEE, 2016.
Huan Wang, Can Qin, Yulun Zhang, and Yun Fu. Neural pruning via growing regularization. arXiv preprint arXiv:00/2.09243, 2020a.
Rundong Wang. Xu He, Runsheng Yu, Wei Qiu, Bo An, and Zinovi Rabinovich. Learning efficient multi-agent communication: An information bottleneck approach. In International Conference on Machine Learning. pp. 9908-999 PMLR, 2020b.
Wei Wen, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Learning structured sparsity in deep neural networks. Advances neural information processing systems, 29, 2016.
Junran Wu, Xueyuan Chen, Ke Xu, and Shangzhe Li. Structural entropy guided graph hicrarchical pooling. In International Conference on Machine Learning, pp. 24017-24030. PMLR, 2022a.
Tailin Wu, Hongyu Ren, Pan Li, and Jure Leskovec. Graph information bottleneck. Advances in
Neural Information Processing Systems, 33:20437-20448, 2020.
Ying-Xin Xin Wu, Xiang Wang, An Zhang. Xiangnan He, and Tat-Seng Chua. Discovering invariant rationales for graph neural networks. arXiv preprint arXiv:2201. 22872 2022b.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? arXiv preprint
2018
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hier- archical graph representation learning with differentiable pooling. Advances in neural information processing systems, 31, 2018.
12

---

Published as a conference paper at ICLR 2023
Haoran You, Zhihan Lu, Zijian Zhou, and Yingyan Lin. Gebt: Drawing early-bird tickets in graph convolutional network training. arXiv preprint arXiv:2103.00794 2021.
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 Paltern Recognition, pp. 2127-2135, 2020.
Junchi Yu, Tingyang Xu, Yu Rong, Yatao Bian, Junzhou Huang, and Ran He. Graph information bottleneck for subgraph recognition. arXiv preprint arXiv:2010.05563, 2020.
Muhan Zhang and Yixin Chen. Inductive matrix completion based on graph neural networks. arXiv preprint arXiv: 12058, 2019.
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-1 1468. PMLR, 2020.
Hongkuan Zhou, Ajitesh Srivastava, Hanqing Zeng, Raigopal Kannan, and Viktor Prasanna. Accelerating large scale real-time gnn inference using channel pruning. arXiv preprint arXiv:2105.04528, 2021.
A PROOF OF GRADUALLY INCREASING REGULARIZATION
Regularization is long deemed as a tool on limiting the capacity of deep learning networks, by adding penalty term Q (+) to the objective function J. We denote the regularized objective loss function by J=:
j
af? al((e)
Where a E [0, oo) is a hyperparameter that weights the relative contribution of the penalty term. Setting to 0 results in regularization. Larger values of a correspond to more regularization. For L2 regularization (commonly known as weight decay), 52 (+) 1 ||ll [ is added into objective function. To simplify the presentation, we assume no bias parameter, so θ is just equaled to w and we can list objective function as:
J(
& w
(9)
Where the gradient of objective function is:
V Vnn (w; X,y) aow + V (w; X,y) The whole network can be optimized by:
(10)
w + w E (aw + V V (w;X,y)
(11)
Written another way, the update is:
w + (1 - ca-ww) V X,y)
(12)
Further simplify the analysis by making quadratic approximation the objective function in the neighborhood of the weights that obtains minimal unregularized training cost, w" = argmin.. (w). In the neighborhood of w*, we can obtain:
1 J (0; x.y) = J (w*) )= + 7 w w²)²
T H (w - w²)
(13)
Where H is the Hessian matrix of J with respect evaluated w". There is first-order term in this quadratic approximation, because w" is defined to be a minimum, where the gradient vanishes. Meanwhile, due the w" is the minimum of J. we can conclude that H is positive-semidefnitte The minimum of J occurs where its gradient:
13

---

Published as a conference paper at ICLR 2023
Jww) H (w w3)
(14)
Gradually increasing regularization (GIR): We add weight decay gradient in 14 as regularized j reaches minimum (corresponding to wi), we can obtain:
ar + H (ύ
x (H (H+ Hw"
(15)
After increasing the penalty a by ga, the new converged weights vē have the same relation 13 with previous round convergence point
= (H + :all) H
(16)
where / represents identity matrix.
For ease of exposition and in order to make the paper more self-contained, we prudently inherit and place the proofs which analysis in Wang et al. (2020a), we list two simplified cases to move forward.
(1) H is diagonal. For d; with second derivative 1442- As adding da 0 regularized force, the new converged weights can be proved to be
has
W
W
Wi
(17)
ha
da
da hig +
Where E [0, 1) since h4 2 0 and da > 0. As seen, when hag 1, make weight relatively less moves towards the origin.
t. we can find that the
(2) We consider a general (2-d) instead of diagonal matrix of H.
hi
hi2 h22
)
A
h1 + gā h22
h12 h22 5o.
After adding mini-step value of regularization,
h2
d abz
(Jenhuz + hi1da
hij)) in + 8ach1212
{
(banlezz + huida -ī22) W1
(hurhez + hzzōa 1i2)) W2 8ahh1ai }
(lunlerz hzzda hfg)) d2
f1
(18)
th2
(hi122
h11da 122))
(h11222
h22da h122)
(19)
As seen, draw the same conclusion: hn h22 also results in m² my
According to Wang
al. (2020a), when the penalty is increased the same pace, due to the different local curvature structure, the weights response in a different way. Weights with larger curvature will be less moved. As regularization gradually increases, the magnitude discrepancy among weights will be magnified and the unimportant weights tend to zero and can be regarded as noise.
B NOTATIONS
For the convenience of reading and consulting, we put all the notations of this work in Table
C ALGORITHM OF DUAL GRAPH LOTTERY TICKET FRAMEWORK
In this part, summarize our DGLT algorithm process in Algo. | We first select part of parame- ters to discarded later. Then we initial our framework parameters. and perform backpropagation algorithm to update the network parameters. After that adopt GIR for information extrusion. until the useful information is sufficiently extruded into the target structure, we one-shot pruning pre-defined structure and fine-tune unpruned parameters for model evaluation.
14

---

Published as a conference paper at ICLR 2023
Table The notations that are commonly used in Methodology (Sec.
Notation
Definition
9 (V, E
Input graph
Input adjacency matrix
Input features
z
Embedding representation after 1-th GNN embedding layer
5()
Assignment matrix for 1-th GNN embedding layer output Adjacency matrix after 1-th GNN sparsification layer
A0
X
Nodes representation after 1-th GNN sparsification layer
! (I 1.2... I.)
Parameters of layer I-th embedding GNN
(1)
(1 1, 2... L)
Parameters layer I-th sparsification GNN
hgs
Trainable matrix for masking A
A
Aali
Aau {A, A()) A represent all adjacency matrix outputs
Ma mx m m.mm represent mask for Aaul
MA
D COMPLEXITY ANALYSIS OF GLT AND DGLT
present the complexity of DGLT algorithm. As for GLT, the inference time complexity of GLTs O (L x [| O O Allo x F + L x || x [ F2) la is the number remaining edges in sparse graph. F is the dimension of feature and [V] is the number of nodes. The inference time complexity of DGLT O allma O Aaullo F + ||m= Ilo x x) + O (K), where M = (m², m ... ...mm rep- resent mask set for all adjacency matrix outputs Aoul F is the dimension of feature and [V] is the number of nodes. llm=Ilo represents all remained parameters of two non non-shared GNNs. (K) represents inference time complexity of learning the node embeddings and the assignment ma- trix. They are obtained by multiplying multiple matrices and the inference time complexity of O (IC) o (T. 12) L X F).
Follow the Chen al. 20021,
where is the number of layers, m|g O Alll
E EXPERIMENTAL SETTINGS Metrics:
Accuracy is the proportion of correct prediction results all predictions. ROC-AUC (Re- ceiver Operating Characteristic-Arce Under the Curve) value is equivalent to the probability that a randomly chosen positive example is ranked higher than randomly chosen negative example.
Algorithm Dual Graph Lottery Tickets (DGLT) Algorithm (aligned with Fig,
Require:
Input graph g = (A, X GNN (G: m,, with initialization parameters O, and mm step size penalty hyper- parameters and of regularization terms.
1: Select part of parameters to be discarded later, i.e., m in ma and O* in O
for layer Φ = 2,2... .... L embedding GNN and sparsification GNN
3: Learn ø-layer embedding representation ( in Eq.
4: Learn ø-layer coarsened representation by S(t) in Eq
5: Hierarchical cluster to form new graph in Eq.
Obtain Goub (A(2), (()).
7: m4/44) (4) and send G.ub ( (2) A (2)
x(0) into predictor.
for iteration = 1, E
9: Forward f ([ma 0 A, θ) to compute loss LDGIT in Eq.
10: Update 0.+1 ー θ - Ve, LDGLT
11: Update MA441 <- m.s. V m, LDGLT
12: Increase regularization penalty 9, and m.s by mini-step in Eq.
13: One-shot pruning of M and e*.
14: Fine-tune the model with rest parameters.
15: return Dual graph lottery ticket.
15

---

Published as a conference paper at ICLR 2023
Table 5: Dataset details. The description of the metries is placed in Appendix
Dataset
Task
#Graphs
#Nodes
#Eidges
#becatures
#Classes
Evaluation Metric
Cora
Node classification/Laa Link prediction
2,708
5,429
1,443
7
Accuracy/RC- -OC-AACC
Citeseer
Node classification/ Link prodiction
3.327
4,732
3,703
Accuracy/RRCC- ABCCAACC
PuhMeed
Node classification/Ling Link prediction
19,717
88,338
500
Sccuray/RCC...
OgGl-Coolahh
LIn prediction
235,868
[255 J65
128
Hiss 2 5D
D&D
Graphh classiñeaation
1.178
334,922
16,8860922
89
Accuracy
ENZYMES
Graph classilication
600
19,580
745.654
Accuracy
Ho means that taking the candidate edge of the top 50, the proportion of the 50 edges is pre- dicted correctly.
|| Sparsity ratio: we transform graphs into small size representations and note 1
|A] as graph
sparsity ratio. I1-Ilo and Ho are the number of non-zero elements and total number of elements, respectively. Similarly, weight sparsity denotes that the ratio of the discarded parameters to the total parameters in the whole network.
Train-val-test Splitting of Datasets. To rigorously verify the effectiveness of our proposed DGLT algorithm, we control the network designs consistent under the same task. As for node classification task of regular-size datasets, we follow the same data split criteria among different backbones, i.e., 700 (Cora), 420 (Citeseer) and 460 (PubMed) labeled data for training, 500 nodes for validation and 500 nodes for testing. As for link prediction, we shuffle the datasets and sample 85% edges for training, 10% for validation, 5% for testing, respectively. For Ogbi-Collab, in order to simulate real collaborative recommendation application, we take the cooperation before 2017 as the training edge, the cooperation in 2018 the validation edge and the cooperation in 2019 the testing edge. For graph classification task, we choose D&D and ENZYMES datasets. D&D and ENZYMES includes graphs of protein structures, in which node represents amino acid. We perform 10-fold cross- cross-validation to observe model performance and reported the accuracy averaged over 10-fold.
Backbone settings. As for regular-scale datasets Cora, Citeseer and PubMed, adopt GCN/GIN/- GAT backbones for node classification and link prediction tasks. In our implementation, we adopt 3-layer GCN, 3-layer GIN and 3-layer GAT, respectively. For link prediction in Ogbl-Collab, we adopt 28-layer ResGCNs. For graph classification, we hope to obtain a small size graph represen- tation and we use GraphSAGE for forecasting. Concretely, we select three sparsification layers for graph size scaling. After the last sparsification layer. we add a GrpahS layer and MLP for prediction. Further, we place the training details and hyper-parameter configuration in Table
Weight sparsity settings. In our implementation, we control the sparsity of each individual layer to be equal to the total sparsity and random choice weights in each layer. In this setting, we keep the first layer dense, since sparsifying this layer has a disproportional effect on the performance and almost no effect on the total size.
Hierarchical graph sparsification ratio. For graph classification, we found that ny has little effect on the results, while the final пı can be limited to a small size (even 95% graph sparsity). As for node classification and link prediction tasks, we should control n4 to be slightly larger than n441 in hierarchical graph sparsification (HGS) process.
Table 6: Training details and pper-paaaaeetr configuration. (()) and (1)) indicate the starting value of the graph regularization and weight regularization, respectively. &a and pa indicate the size of the graph regularization and weight regularization increase value.
Computing Infrastractures: theee NIVIDIA Tesla 100 (16GB GPU) Softaree Framework: Pytorch
Tisk Dataset
Node classification
Link prediction
Graph classification
Cora
PubMed
Citeseer
PubMed
Ogbl-collab
ENZYMES
Epochs (pre-trinn/ine-tume))
500/200
500/200
700/200
500/200
500/200
700/200
500/200
500/500
500/300
((0)
5c-04
5c-14
So-04
5c-04
5c-04
3e-04
Sc-14
Sc-04
Sc-14
&
le-06
1e.06
1s:06
le-06
lc-06
1e-06
1e-06
le:06
1e-06
Sc-04
Sc-04
Sc-04
Sc-04
5c-04
5e-04
Sc-04
Sc:04
Se-04
Ic-06
Ic-06
Ic-06
Ic-06
Ic-06
Ic-06
Ic-06
Ic-06
Ic-06
Optimizer learning rate
Adam
Adam
Adam
Adam
Adam
Adam
Adam
0.008
0.01
0.01
0.008
0.01
0.01
0.01
0.0001
0.0001
16

---

Published as a conference paper at ICLR 2023
COOHGNN
OREAGIN
Con GA1
55
ROC-AUC (%6)
-55
30
Backe (CUU
76
70
DCLT(O
70
Frcckg
kander tgating
CLT
Ranken
80
86
16
46
50
60
500
Grmph sparsity (9%)
Graph sparsity (%)
Graph sparsity (%)
Cora GCN
COCHCEN
CauMSAT
ROC- ROC-AUCION
Rodix
DOLTIOWS
GLT
Brabor
Randes
20
Weight spursity (%)
Weight sparsity (%)
Weight spursity (%)
(
Cheeee--iN GIN
CleserGAT
ROC-AUC (%)
30
Rudi
IKE.iiitar))
GLT
70
Reabet Frising
Randon Frnie
30
30
52
16
25
46
80
20
30
60
70
50
Graph spursity (%)
Graph sparsity (%)
Graph spunsity (%)
Cleser-Gat GAT
ROC-AUCC ALCC (%)
Bld
Blsiing
Bea
G.l
G1T
CLT
Fanden Packin
50
Reader Pronin
itaken Praiigg
28
70
83
90
16
20
36
1)
56
X0
Weight sparsity (%)
Weight sparsity (%)
Weight sparsity (%)
PubMted GAT
85-
ROC-AUC AUC.AUCCI (%)
50
Toolre
lbcik
75
Bacia
GIT
65
frini
65
Radken
Griph spansity (%)
Graph sparsity
Gmaph spursity
PaXtld-GEN
PalMal: GAT
ROC-AUC (%)
75
70
Rucie:
Buadier
Bast at
T(Ows))
Rrraknn Truning
Franigg
10
59
70
30
70
Weight spursity (%)
Weight sparsity
Weight spansity (5)
Figure 7: The results for additional link prediction task. We adopt Cora/Citeseer/uuMMee as bench- marks and test our DGLT alogrithms on GCN/GIN/GAT three backbones for comparison. Blue dash lines represent the baseline performance of full GNNs on full graphs.
F ADDITIONAL EXPERIMENTS TO ANSWER RQ1
More experiments on link prediction task are shown in Fig. We make observations as follows:
(1) DGLT aggressively improves the reasoning efficiency without significant performance degrada- tion. For Cora dataset, we can get graph lottery tickets with nearly 50% graph sparsity and 80% weight sparsity. For Citeseer dataset, we can get graph lottery tickets with nearly 70% graph spar- sity and 85% weight sparsity. For PubMed dataset, we can get graph lottery tickets with nearly 60%
17

---

Published as a conference paper at ICLR 2023
CueNOCN
C251NN
Ger-GAl
Accumnt
(CLl)
OLT
Randen Pradiyy
Ladea herid
Ladee hrming
10
20
33
48
50
60
T0
30
3)
13
50
66
70
30
10
20
36
66
70
Graph sparsity (%)
Gruph spansty (%)
Gruph sparsity (%)
R5
1222 16
Accuracy (%)
75
Bov ke DO0
Tasline
05
Rodaar
GIT Rasket
ULT
Weight spursity (%)
Weight sparsity
Weight sparsity (%)
Figure 8: The results for node classification task on Cora benchmark. Blue dash lines represent the baseline performance of full GNNs on full graphs.
graph sparsity and 80% weight sparsity. (2) DGLT can transfer seamlessly to different graph-related tasks. In addition to the node classification task, DGLT model can also show better results on the link prediction task. (3) We can get similar conclusions as in the main experiments, DGLT can achieve better results than GLT and random pruning under the same sparsity ratio.
Further. we conduct 3-layer GraphS Hamilton et al. (2017) counterpart with DGLT algorithm on ENEYMES and D&D datasets under different weight sparsity ratio. Similar the original graph pooling method DIFFPOOL settings, we control the graph sparsity as 95% (total two pooling layers DIFFPOOL) and observe the performance under the different weight sparsity. As shown in Table 7 it is not difficult to find that the information extrusion algorithm well maintains the accuracy under high sparsity. On ENEYMES dataset, We can observe that the expressiveness of the model could be improved even pruning 80% weights. Meanwhile, when the weight sparsity of the model reached 90%, the performance of the model still did not decrease significantly: it only decreased by 2.24% on the ENEYMES dataset and by 0.62% on the D&D dataset. In a nutshell, these results demonstrate that our DGLT algorithm can also be easily generalized to graph classification tasks, which further illustrates that DGLT has resilient pluggability.
Table 7: Graph classification accuracies in percent over ENZYMES and D&D datasets under differ- ent weight sparsity.
DIFFPOLLAENZYESS Baseline accuracy:63.21% Graph 9parsity=95%
Weight sparsity (%)
10
20
30
40
50
60
70
80
90
DGLT (Ace) 65. 03.37 65.44:20.49 66.53 63.55 62. 6. 02.17:00,57 63,21 61.77:0044
60.97-:0.33
DDFFPOOL-&&D; Baseline 27..racy:77.336 77.33%
Graph 9parsity=95%
Weight sparsity (%)
10
20
30
40
50
60
70
80
90
DGLT (Acc)
00.17:10.34 0..47
76.39:10.55
77.670.78
78.50:10.11
77.51:0047
77.3610.47
10.59
76.71
G ADDITIONAL ABLATION RESULTS
In addition Cora+GCN setting on Sec. 4.4 summarize Citeseer+GAT experimental results on link prediction task and PubMed+GII experimental results on node classification task. As shown in Fig. [ we can further draw similar conclusions that our DGLT algorithm can obtain graph lottery tickets, which can both save memory footprints and speed up reasoning efficiency.
H CONNECTIONS TO GNN EXPLAINABILITY
GNN explainability research line mainly focuses on identifying a key subgraph of the full graph- that is, what knowledge drives the GNN model to make certain prediction? They cast
18

---

Published as a conference paper at ICLR 2023
Chocar GAT
CreeerKGTT
45
ROC-N CC-AUCC (%
90
Buseline
P6-10%
1g-10%
P9-30%
90
3g-30%
P9-50%
Pa-50N
P0-70%
7g-70%
85
sparsity (9)
Weight sparsity (%)
NiIMed-GIN
PAMatHGGN
83
(16
Baseline
Baseline
10%
84
PS-30%
Pg-30%
PS-50%
Pg-50%
PC-20%
Par 70%
80 1
10
15
30
Graph sparsity (%)
Weight sparsity (%)
Figure 9: Ablation studies of pruning ratios for transforming sparse graph Pg and network we select Git for link prediction task and PubMed+GIN for node classification task. Bule dash lines represent model performance over full graph counterpart with full networks.
the learning paradigm of GNN minimizing the empirical risk with the masked subgraphs, which are regarded as rationales to guide the model predictions Chang et al.) (2020); Miao et al.] (2022); Creager al. (202T): Wu al. (2022b): ((ui al. (2022). Our explanation focuses on why the trans- formed subgraph can make reliable predictions, which is similar to those described above. In our implementation, we want to give an explanation from a graph information bottleneck perspective about why the transformed subgraph has expressive ability. This "explanations" process (Section 3.3) similar Miao al.] (2022). the difference is that our subgraph is not fraction of the orig- inal full graph but is obtained by hierarchical graph sparsification (HGS) algorithm. However, to our best knowledge, this the first work to transform a graph lottery ticket from the information bottleneck perspective and will explore how the relationships between GNN explainability with gradually increased regularization in the future work.
DISCUSSION OF DGLT
In this work, we follow the perspective of the Dual Lottery Ticket Hypothesis (DLTH) and inves- tigate GNN subnetwork training and subgraph identifying from a complementary direction- is, given a specific substructure of GNN model or size adjacency matrix, we can always trans- form them winning graph lottery ticket (please note, we consider the common case based on uniformly random selection for GNN model or subgraph compression form, not including certain extreme situations such the disconnected subnetworks or subgraph). This conjecture, if it true, has rather promising practical implications- may suggests that the message passing function (i.e., information aggregation) of training GNN model is in fact unnecessary as one only needs to select target size of adjacency matrix or target substructure of GNN, and then use hierarchical graph sparsification (HGS) algorithm or gradually increased regularization for information extrusion.
Comparisons with DLTH. DLTH focuses on transforming randomly initialized dense network into an admirable subnetwork, which can achieve better at least comparable to LTH. Building upon DLTH, our DGLT firstly generalizes this idea to GNN, and investigates more universal yet chal- lenging problem that is, how to transform a randomly selected ticket (i.e., a pair of graph and network) to graph lottery ticket in GNNs? However, the key tool of DLTH gradually increased regularization not applicable to graphs due to the fixed structure. To this end, we adopt HGS to break this gap and adjustably pre-define the substructure of adjacency matrices. Compared with the
19

---

Published as a conference paper at ICLR 2023
infeasibility of DLTH in graph compression, method makes it possible sparse the graph and GNN targeting to the specified structure.
20


Reviews:
[{"review_id": "kYTPNBCWRt", "reviewer": "Reviewer_xzm4", "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 explores the dual lottery ticket hypothesis on graphs. Specifically, a pair of core subgraph and sparse subnetwork is jointly uncovered via regularization-based network pruning and hierarchical graph sparsification. The method is also analyzed from the perspective of graph information bottleneck. Experiments on node classification, graph classification and link prediction tasks show the effectiveness of the proposed method compared with GLT.", "summary_of_the_review": "The paper introduces dual lottery ticket hypothesis and graph pooling in graph lottery ticket. In general the paper is well written with clear motivation and extensive experiments are conducted. However, I have concerns about the limited technical contribution and unclear details. \n\n=== Method ===\n\n1. The example in Figure 1 is not convincing. Aggregation failure may also happen in the proposed sparsification, since mask matrices are also applied to the adjacency matrix (e.g. $m_A$) which removes edges among clusters/communities. \n2. The reason for imposing a mask $m^{(l)}_A$ in each layer is not well justified. If the graph is already pooled, why does it need to be further sparsified? What is the performance if removing the masks $m_A$?\n\n3. The calculation of the cross-entropy loss in Eq. (4) is crucial to understand how the method can serve for different tasks, but is not explained at all. If this is a node classification task, the label is per-node. However, after pooling and sparsification, the final subgraph $A^{(L)}$ and $X^{(L)}$ is no longer node-wise but cluster-wise (e.g. the dimension of $A^{(L)}$ is $n_{L}\\times n_{L}$). There is clearly a gap between node-wise labels and cluster-wise embeddings. What is the specific form of the cross-entropy loss for node classification, link prediction and graph classification task, respectively?\n\n4. The claim of better explainability is not demonstrated. It usually has a specific meaning of providing explanations to the model predictions.  \n\n5. Is $G_{sub}$ the same as $G_{hgs}$?\n\n6. The theoretical analysis is a bit vague, especially when it comes to the proposed method. For example, the logic of why the training mask will make $I(\\hat{\\mathcal{G}}^*_s, Y)>I(\\mathcal{G}^*_s, Y)$ is unclear. The analysis is more like intuition instead of rigorous theoretical proof. Meanwhile, Figure 3 is hard to understand. After reading the analysis, it is still unclear to me why DGLT can be comparable/better than sampling-based algorithms.\n\n=== Experiment ===\n\n7. What is the definition of weight sparsity and graph sparsity in the experiment?\n\n8. How sensitive is the method to the pooling-related hyperparameters, e.g. $n_{l}$?\n\n=== Typos ===\n\nThere are also some typos. To name a few:\n- In the paragraph after Eq. (2), “assignment matrix S^{(l)}... can projecting coarsened subgraph xxx” -> “Assignment … can project …”\n- Duplicate “and” in the paragraph before Lemma 1.\n- “a admirable” -> “an admirable” in the paragraph before Lemma 1.\n", "strength_and_weaknesses": "**Strength**\n- The dual lottery ticket hypothesis is firstly studied on graph lottery ticket.\n- The graph pooling technique is introduced to replace the sampling-based graph sparsification.\n- Extensive experiments are conducted for multiple applications.\n\n**Weaknesses**\n- Important details about the training loss are not provided, especially when the dimension of the sparsified graph is changed by pooling operations.\n- Some claims made by the paper are not well justified, e.g. better explainability, pooling is better than sampling-based algorithms.\n- The theoretical analysis of the proposed method is not clear enough.\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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "PES76ZOxgU", "reviewer": "Reviewer_cfDA", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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 generalizes the Dual Lottery Ticket Hypothesis in GNN network pruning and graph sparsification and proposes a Dual Graph Lottery Ticket framework. Their experimental results demonstrate the effectiveness of their framework.", "summary_of_the_review": "In general, it is a good paper with a novel framework, solid technical, and significant results. It is a modest-to-high impact paper in a subarea of graph machine learning, especially graph sparsification.", "strength_and_weaknesses": "Strongness\n1. The paper is well-written, and the motivation is intuitive and clear.\n2. It is interesting to introduce Lottery Ticket Hypothesis to simplify the input graph, and it is contributive to propose a Dual Graph Lottery Ticket for GNN pruning and graph sparsification.\n3. Extensive experiments demonstrate the effectiveness of the framework in terms of sparsity improvement, scalability, and performance\n\nWeakness:\n1. The model complexity in terms of training time and parameter volumes is not discussed and investigated in the paper. It is necessary to discuss the complexity of DGLT especially considering the non-shared GNNs to learn the node embeddings and the assignment matrix.\n2. The authors did not investigate the performance of random pruning on node classification. Whether the pruning would affect the performance of DGLT is not detailed.", "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": "KExpC49vymR", "reviewer": "Reviewer_yVH3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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 considered scaling up Graph Neural Networks (GNNs) via the input graph and model (GNNs) compression while maintaining model performance. The authors considered a dual problem of the original Graph Lottery Ticket hypothesis problem, i.e., transforming a random pair of input graphs and networks into a graph lottery ticket. The proposed framework called the Dual Graph Lottery Ticket (DGLT), utilizes the $L_2$ regularization to achieve sparsity and a hierarchical graph representation learning procedure to learn the sparse subgraph. In addition, a one-shot pre-train and finetune step are applied to prune the GNNs. The authors also provided some theoretical analyses to show that their proposed DGLT could achieve better subgraphs compared with sampling-based methods. Experiment results are provided on the proposed method’s effectiveness, scalability on large graphs and ablation study, etc.", "summary_of_the_review": "Overall, I found this paper interesting in exploring DLTH under the GNN setting. However, there are some concerns over the technical novelty as well as some empirical results. My final scores will be largely upon the discussion with other reviewers. I am open to hearing from the authors and willing to change my scores if I made any misunderstandings.", "strength_and_weaknesses": "Strengths:\n1.\tAs far as I know, this paper delivered the first attempt to generalize the Dual Lottery Ticket Hypothesis onto graph data and GNNs to obtain the graph lottery ticket. \n2.\tEmpirical study is clean and shows promising results on some datasets.\n3.\tThis paper is well-written with a nice presentation. Many sections are easy to follow.\n\nWeaknesses:\n1.\tAs far as I understand, the finally found dual graph lottery ticket is obtained after the training of the GNNs, i.e., the ticket contains fully trained parameters. This makes me feel the method proposed in this paper is more like a graph/model pruning method where we simultaneously train and prune a GNN until we finally find a sparse subgraph/subnetwork with non-dropped accuracy. If so, the dual perspective of the lottery ticket hypothesis does not that novel or interesting to me. I would like to see more explanations or justifications from the authors on this point.\n2.\tIf my understanding above is true, the authors are also encouraged to compare their method with standard compression-based methods.\n3.\tAs stated in the introduction, the Graph Lottery Ticket hypothesis can simultaneously simplify the input graph and prune the GNNs without compromising model performance. However, there exists an unignorable gap between the performance of the pruned GNNs with a pruning ratio above ~60% or 70% and the full-graph baselines on Citeseer and Ogbl-Collab. Is there any possible explanation for this phenomenon?\n\nMinor concerns:\n1.\tAll experiment results in the current manuscript do not have standard deviations. Authors are strongly encouraged to add them by multiple random runs since on several datasets the margin between some methods is very close. Also, single-run-based results could sometimes be tricky due to e.g., cherry-picking.\n2.\tSince this paper also tackles the compression of input graphs, I believe it is more meaningful to include “truly” large-scale graphs in the experiments. I believe nowadays large-scale graphs are typically at least in the scale of the millions in terms of the number of nodes, e.g., OGB-Products and ogbl-citation2.\n3.\tMissing references to some (potentially) very related paper: Inductive Lottery Ticket Learning for Graph Neural Networks, 2022.\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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "5zH-A7ZNIR3", "reviewer": "Reviewer_rozM", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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 studies a new formulation of the LTH problem on graphs. Instead of searching for a sparse subnetwork with good performance, it poses the question of how to transform a randomly selected ticket into a lottery one. Although this problem has been studied before in DNNs, the paper proposes a solution for GNNs. Specifically, the proposed methodology, called DGLT,  comprises a hierarchical graph sparsification module based on hierarchical graph pooling and a training module following a suitable adjusted L2 regularization component. In addition, the paper borrows ideas from the Information Bottleneck theory to provide performance guarantees. The model is empirically evaluated on the task of node classification.", "summary_of_the_review": "The paper makes an interesting contribution toward further understanding graph structure simplification and model compression in GNNs using lottery tickets. Nevertheless, I still have some concerns about the theoretical analysis derived in the paper.", "strength_and_weaknesses": "**Strengths:**\n* The paper presents a rigorous formulation of the GLT problem on graphs. Efforts have also been made to theoretically explain the performance of the model.\n\n* Detailed empirical analysis, studying different aspects of the methodology.\n\n**Weaknesses:**\n* A point that is not very clear in the paper has to do with the practical utility of the theoretical observations that are made in Sec. 3.3. I cannot really see how these observations have a direct impact on the performance of the model in practice. It would be helpful if the authors could further clarify this point.\n\n* Another point has to do with the ablation study. A core component of the methodology is based on the hierarchical graph sparsification module which is implemented as a trainable pooling operator. Oftentimes, especially on graphs with no clear modular structure, the benefit of hierarchical pooling is not always clear. The impact of this component on the performance of the model should be further analyzed.\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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "1jpPEw2KOHu", "reviewer": "Reviewer_PXxs", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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 proposes the Dual Graph Lottery Ticket framework to obtain the triple-win graph lottery ticket. Regularization-based network pruning and hierarchical graph sparsification are designed to jointly get the sparsified graph and subnetwork. What’s more, the graph information theory guarantees the explainability of this triple-win lottery ticket.", "summary_of_the_review": "It’s really interesting to transform a random ticket into a graph lottery one and the authors introduce gradually increased regularization terms and hierarchical graph sparsification to achieve this goal. Besides, the Graph Information Bottleneck theory is utilized to guarantee a more explainable ticket. However, the design of the random ticket and the technical detail to find DGLT need to be further illustrated and the explainability of DGLT needs more experiments to support it. ", "strength_and_weaknesses": "Strength:\n* It is interesting to extend the dual lottery tickets hypothesis into graph learning and jointly get well-performed sparse subgraphs and subnetworks from randomly selected ones.\n* The design of hierarchical graph sparsification makes it possible to perform graph classification tasks.\n\nWeakness:\n* The idea of the dual lottery ticket is to prove the universality of tickets in neural networks. However, the design of DGLT does not contain a ‘random graph’. The authors haven’t mentioned how to predefine the subgraph structure, instead, they only constrain the number of nodes in this graph.\n* The notion of hierarchical graph sparsification may be misleading. Graph sparsification means nodes with fewer connections rather than reducing the number of nodes in one graph with the hierarchical graph strategy. Besides, how to evaluate prediction for the hierarchical graph is vague because the label for nodes in the hierarchical graph is unknown. \n* The strategy of gradually increased regularization has already been proposed in [1]. It would be better if the authors could provide more differences for this strategy between DGLT and DLT.\n* Some technical detail needs further illustration. For example, how to uniformly sample subnetworks in DGLT should be described in more information. Meanwhile, good explainability is expected to have some empirical results to support it along with the GIB-based analysis. \n\n[1] Dual Lottery Ticket Hypothesis, ICLR 2022\n\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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster