Inductive Lottery Ticket Learning for Graph Neural Networks
Authors: Yongduo Sui
Xiang Wang
Tianlong Chen
Xiangnan He
Tat-Seng Chua
Venue: ICLR 2022 Submitted (2022)
Keywords: Lottery Ticket Hypothesis
Graph Neural Networks
Neural Network Pruning

Abstract: Deep graph neural networks (GNNs) have gained increasing popularity, while usually suffer from unaffordable computations for real-world large-scale applications. Hence, pruning GNNs is of great need but largely unexplored. A recent work, UGS, studies lottery ticket learning for GNNs, aiming to find a subset of model parameters and graph structure that can best maintain the GNN performance. However, it is tailed for the transductive setting, failing to generalize to unseen graphs, which are common in inductive tasks like graph classification. In this work, we propose a simple and effective learning paradigm, Inductive Co-Pruning of GNNs (ICPG), to endow graph lottery tickets with inductive pruning capacity. To prune the input graphs, we design a generative probabilistic model to generate importance scores for each edge based on the input; to prune the model parameters, it views the weight's magnitude as their importance scores. Then we design an iterative co-pruning strategy to trim the graph edges and GNN weights based on their importance scores. Although it might be strikingly simple, ICPG surpasses the existing pruning method and can be universally applicable in both inductive and transductive learning settings. On ten graph-classification and two node-classification benchmarks, ICPG achieves the same performance level with $14.26\%\sim43.12\%$ sparsity for graphs and $48.80\%\sim91.41\%$ sparsity for the model.

Under review as a conference paper at ICLR 2022
INDUCTIVE LOTTERY TICKET LEARNING FOR GRAPH NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Deep graph neural networks (GNNs) have gained increasing popularity, while usually suffer from unaffordable computations for real-world large-scale appli- cations. Hence, pruning GNNs is of great need but largely unexplored. A re- cent work (Chen et al., 2021) studies lottery ticket learning for GNNs, aiming find subset of model parameters and graph structure that can best maintain the GNN performance. However, it is tailed for the transductive setting, failing to generalize to unseen graphs, which are common in inductive tasks like graph classification. In this work, we propose simple and effective learning paradigm, Inductive Co-Pruning of GNNs (ICPG), to endow graph lottery tickets with in- ductive pruning capacity. To prune the input graphs, we design predictive model to predict importance scores for each edge based on the input; to prune the model parameters, it views the weight's 's magnitude as their importance scores. Then we design an iterative co-pruning strategy to trim the graph edges and GNN weights based on their importance scores. Although it might be strikingly simple, ICPG surpasses the existing pruning method and can be universally applicable in both inductive and transductive learning settings. On ten graph graph-classffication and two node-classification benchmarks, ICPG achieves the same performance level with 14.26% sparsity for graphs and 48. 90%.0% 91.41% % sparsity for the model.
INTRODUCTION
Graph neural networks (GNNs) (Kipf & Welling, 2016; Veličković et al., 2017; Zhou et al., 2018) have become a prevalent solution for machine learning tasks on graph-structured data. Such success is usually ascribed to the powerful representation learning of GNN, which incorporates the graph structure into the representations, such as aggregating neural messages from the neighboring nodes to update the ego node's representation (Veličković et al., 2017; Kipf & Welling, 2016).
As the field grows, there is an increasing need of building deeper GNN architectures (Li et al., 2020a; 2021) on larger-scale graphs (Hu et al., 2020). While deepening GNNs shows potentials on large-scale graphs, it also brings expensive computations due to the increased scale of graph data and model parameters, limiting their deployment in essorcce-constrinee applications. Taking fraud detection in a transaction network as an example, the scale of user nodes casily reaches millions or even larger, making a GNN-detector model prohibitive to stack deep layers and predict the malicious behaviors in real time. Hence, pruning over- vver-prameeterieed GNNs is of great need, which aims to answer the question: Can we co-sparsify the input graphs and model parameters, while preserving or even improving the performance?
Recently, the pruning approach for GNNs, UGS, (Chen al., 2021), is proposed find graph lottery tickets (GI.Ts) - smaller subsets of model parameters and input graphs. At its core is Lottery Ticket Hypothesis (LTH) (Frankle Carbin, 2018) speculating that any dense, randomly-initializzz neural network contains sparse subnetwork, which can be trained independently to achieve matching performance as the dense network. Specifically, UGS employs trainable masks on each edge in the input graph and each weight in the model parameters, specify their importance. When training the model with the masks, the strategy of iterative magnitude- based pruning (IMP) (Frankle & Carbin, 2018) is used to discard the edges and weights with the lowest mask values at each iteration.
Despite effectiveness, there exist the following limitations: (1) UGS focuses solely on providing the transductive graph masks by generating painstakingly customized mask for single edge

---

Under review as a conference paper at ICLR 2022
individually and independently. That is, the edge masks are limited the given graph, making UGS infeasible to be applied in the inductive setting, since the edge masks hardly generalize to unseen edges entirely new graphs. (2) Applying a mask for each edge alone only provides local understanding of the edge, rather than the global view of the entire graph (e.g., in node classification) or multiple graphs (e.g., in graph classification). Moreover, the way of creating trainable edge masks will double the parameters of GNNs, which violates the purpose of pruning somehow. As a result, these edge masks could be suboptimal to guide the pruning. (3) The unsatisfactory graph pruning will negatively influence the pruning of model weights. Worse still, low- low-quality weight pruning will amplify the misleading signal of edge masks in turn. They influence each other and form vicious circle. We ascribe all these limitations of UGS to its transductive nature. Hence, conducting the combinatorial pruning in the inductive setting is crucial to high-quality winning tickets.
In this work, we emphasize the inductive nature within the combinatorial pruning of input graphs and GNN parameters and present our framework, Inductive Co-Pruning of GNNs (ICPG). It is an ex- tremely simple but effective pruning framework that is applicable to any GNN in both inductive and transductive settings. Specifically, for the input graphs, we design a generative probabilistic model (termed AutoMasker), which learns to generate edge masks from the observed graphs. It is param- eterized with an additional GNN-based encoder, whose parameters are shared across the population of observed graphs. As consequence, AutoMasker is naturally capable to specify the significance for each edge and extract core-subgraphs from a global view of the entire observations. For the model parameters, we simply exploit the magnitude of model weight to assess whether it should be pruned, rather than training an additional mask (Chen et al., 2021). Having established the edge masks and weight magnitudes, we can obtain high-quality GLTs by pruning the lowest-mask edges and lowest-manniude weights. Experiments on ten graph-classification and two node- snde-classification benchmarks consistently validate our framework ICPG by identifying high-qualit, GLTs. The visu- alizations show that ICPG always retains decisive subgraphs, such edges located on digital pixels in MNIST graphs, which further illustrates the effectiveness and rationality. Moreover, we inspect the graph- and GNN-level transferability of GLTs, which promises for deploying our ICPG in the pre-training and fine-tuning paradigm. Our main contributions can be summarized as follows:
We proposed simple but effective pruning framework, ICPG, to prune the GNN model and input graphs simultancously. It can identify high-quality GLTs in diverse tasks of graph representation learning, under both inductive and transductive settings.
For graph classification tasks, ICPG can locate GLTs from small-scale (TUDataset), medium- scale (Superpixel graphs) to challenging large-scale datasets (OGB) with graph sparsity from 22.62%~<33.1 and GNN sparsity from 17.23%~99.4149 with no degradation on performance.
For node classification tasks, ICPG can effectively develop on both transductive learning (Cora dataset) and inductive learning (PPI dataset), which identifies the GLTs with graph sparsity from 22.62%~226.4999 and GNN sparsity from 67.23%~~3..77 79% without sacrificing performance.
The proposed AutoMasker promises for both GNN-level and graph-level transferability, which can achieve comparable or even better performance as compared with the original full graphs. In-depth analyses with visual inspections further demonstrate the effectiveness and rationality.
2 RELATED WORK
Graph Neural Networks (GNNs) (Kipf& & Welling, 2016; Veličković et al., 2017: Xu et al., 2019; Ying et al., 2018) have emerged as powerful tool for learning the representation of graph-structured data. The great success mainly comes from the structure-aware aware learning, which follows the iterative message-passing scheme (Veličković al., 2017). Specifically, we denote an undirected graph by
= XA with the node set V and edge set E. A E {0, 1)1III1 is the adjacency matrix, where Jii denotes the edge between node v, and node vy. otherwise A = O. X E R xd is the matrix of node features, where x; = Xli. :] is the d'-dimensional feature of the node v E V. Given a K K-layer GNN, its k-th layer generates the representation of node v, as:
AAGGEEATTIONNT ((n55=1) E A()))) h = COMBINE ( (k-1)
(K)
(1)
where (R) and at nodes set Nii,, respectively; the AGGREGATION and COMBINE operators are the message
(1) are the representation of node e; and the message aggregated from its neighbor
2

---

Under review as a conference paper at ICLR 2022
passing and update functions, respectively. After propagating through K layers, get the final representations of nodes, which facilitate downstream node-level tasks, such as node classification and link prediction. As for graph-level tasks like graph classification and graph matching, we further hire the READOUT function to generate the representation of the whole graph G:
Z = RERRDUUTTR by E V, E (1, K]])-
Various GNNs, such as GIN (Xu et al., 2019) and GAT (Veličković al., 2017), implement different AGGREGATION, COMBINE and READOUT functions, as to refine the desired information from graph structures.
Graph Sparsification or Sampling (Voudigari et al., 2016; Leskovec & Faloutsos, 2006) aims to find small core-subgraphs from the original graph, which can remain effective for graph learning tasks. Numerous strategies (Zeng et al., 2019; Franceschi et al., 2019; Ying al., 2019; Hamil- ton et al., 2017; Chen et al., 2018) are proposed to achieve efficient graph learning. For example, GraphSAGE (Hamilton et al., 2017) samples and aggregates feature from node's ' local neighbor- hood. FastGCN (Chen et al., 2018) adopts the global importance sampling, which more efficient for training. DropEdge (Rong al., 2019) randomly drops edges from the input graph, which can be seen as a data augmenter. Another research line selects the core-subgraph in an optimization way. SGCN (Li et al., 2020b) adopts the ADMM optimization algorithm sparsify the adjacency matrix. UGS (Chen et al., 2021) utilizes trainable mask for each edge to remove the potential task-irrelevant edges. Distinct from them, our AutoMasker predicts the importance score of each edge from a global view, thus having better generalization ability in the inductive settings.
Lottery Ticket Hypothesis (LTH) (Frankle & Carbin, 2018) states that sparse subnetwork exists in a dense mandomly-iitializze network that can be trained to achieve comparable performance to the full models. LTT is explored in many fields such as computer vision and natural language processing (Chen et al., 2020; Ma et al., 2021; Yin et al., 2020; Liu et al., 2019; Wang et al., 2020; Savarese et al., 2020). Recently, Chen et al. (2021) extends the LTH to the GNNs and proposes the Graph Lottery Ticket (GLT), which includes subgraph and subnetwork pairs that can be trained independently to reach comparable performance to the dense pairs. However, due to the transductive nature of graph-specific masks, UGS (Chen et al., 2021) can not develop inductive learning settings, such as graph classification tasks. To tackle the dilemma, we propose AutoMasker to globally learn the significance of each edge from training graphs and predict importance scores for new coming graphs, which is graph-independent and inductive.
3 METHODOLOGY
Here we first formulate the task of learning graph lottery tickets, and then present our inductive strategy of co-pruning the input graphs and model weights.
3.1 INDUCTIVE GRAPH LOTTERY TICKET
Without loss of generality, we consider the inductive task of graph classification as an example. Given a GNN classifier [( ,, ). it starts from the randomly-initialzzed parameters O before training and arrives at the well-optimized parameters θ, after training. Once trained, takes any graph G = (A,X) X) as the input and yields probability distribution over C classes ý = f(g. Og)) Wherein, G is associated with the adjacency matrix and the pre-existing node features X.
The goal of learning graph lottery tickets is to make the input graph G and the model weights O g. sparse to reduce the computational costs, while preserving the classification performance. Formally, it aims generate two masks mg and me, which are applied on G and Ogo correspondingly, so as to establish the sparser input graph g' = (mg O A, and initialized weights @¹ .m @ θ 20 Hereafter, through retraining the subnetwork f(,, O' on the sparse versions (g') of training graphs, we can get the new converged parameters O', If the well-optimized subnetwork can achieve comparable performance with full graphs and network, we term the pair of g' and f(, e go as graph lottery tickets (GLTs).
Although a very recent study, UGS (Chen et al., 2021), has proposed an approach to leam the GLTs, it focuses solely on the transductive setting but leaves the inductive setting untouched. Specifically,
3

---

Under review as a conference paper at ICLR 2022
it
assigns trainable mask to each edge of the imput graph and trains such graph-specific masks individually and independently. As a consequence, these adge-dependens masks are limited to the given graph, hardly generalizing to unseen edges entirely new graphs. Distinct from UGS, aim to uncover GLTs in inductive learning settings.
3.2 AUTOMASKER
Instead of assigning mask single edge, our idea is extremely simple: we take a collection of graph instances and design a trainable model to learn to mask edges collectively. The key ingredient to- wards this model is an additional GNN-based model, termed AutoMasker, whose parameters are shared across the population of observed graphs. Here we represent AutoMasker as the combina- tion of a graph encoder and a subsequent scoring function. Formally, given a graph G = (A, AutoMasker applies a GNN-based graph encoder g(-) to create representations of all nodes as:
= X),
where E R xxd stores d-dimension representations of all nodes, whose i-th row h; represents the representation of node o; 9()) is GNN following the pressage-psssing paradigm in Equation 1. To assess the importance score of edge (i..j) between node e and node Uj. AutoMasker builds a multi- layer perceptron (MLP) upon the concatenation of node representations h; and hj. which yields the score asj- In what follows, the sigmoid function a--) projects Qzj into the range of (0, 1), which represents the probability of edge (i,j) being the winning ticket. The scoring function is represented as follows:
Stj (a:y), Ozj MLP((,,, hy]).
By employing the scoring function over all possible edges, we are able to collect the matrix of edge masks sg, where sgli.]] = S- if edge (i.j) holds, otherwise sg ji 0. In a nutshell, we summarize the AutoMasker function as follows:
sg AutoMasker(G. Oa),
(5)
where θ is the trainable parameters of AutoMasker, covering the parameters of the GNN encoder and the MLP.
Although the key ingredient of AutoMasker is simple, it has several conceptual advantages over UGS: (1) Global view: Although edge masks derived from UGS might preserve the fidelity to local importance, they do not help to delineate the general picture of the whole graph population. Distinet from UGS, our AutoMasker takes a global view of the graph population, which enables us identify the edge coalitions. Specifically, as edges usually collaborate with each other to make predictions, rather than working individually, they form a coalition like the functional groups of a molecule graph, the community of social network. Considering such coalition effects, AutoMasker is able to measure the importance of edges more accurately. (2) Lightweight edge masks: When using UGS to prune graph data with millions of edges nodes, the cost of assigning local edge masks one- by-one will be prohibitive with such large-scale dataset in real-world scenarios. Moreover, UGS introduces additional parameters, whose scale remains the same the edge numbers Σg |ε| and is much larger than the original parameters being pruned. Hence, it somehow violates the purpose of pruning. In our AutoMasker, the additional parameters are i.e.. O, in Equation only and remain invariant across the change of data scale. (3) Generalization: AutoMasker can generalize the mechanism of mask generation to new graphs without retraining, making more efficient to prune unseen and large-scale graphs.
3.3 INDUCTIVE CO-PRUNING STRATEGY
Here we present the framework of Inductive Co-Pruning of GNNs (ICPG) to localize GLTs induc- tively. Figure demonstrates its overview, which consists of the following steps:
Step 1: Co-training AutoMasker and the GNN model of interest. Given input graph G (A,X), AutoMasker first generates the edge mask Sg via Equation 5. Then we apply Sg to the adjacency matrix A to create the masked graph G. (sg @ A, X). which fully reflects AutoMasker's decision for the importance of each edge, such that less important edges are prone have lower mask values. Finally, we feed the masked graphs into the GNN model to co-train the
4

---

Under review as a conference paper at ICLR 2022
Step1: Co-training the Matora and GNN model.
Raling Scores
AutoMasker
Training Graph(s)
Masked Graphís)
GNN
Magmibude Pruning
Step2: Co-sparsifying the input graphs and GNN model.
Rating
Mask Pruning
Scores
AutoMasker
Training/Testing Graph(s)
Masked Graph(s)
Sparse Graph(s)
Sparse GNN
Figure 1: The Inductive Co- Co-Pruning of GNNs (ICPG) framework to find the GLTs.
AutoMasker and the model. The GNN model adopts the masked graph to learn the representation and make predictions, which can be viewed the supervision signals to guide the AutoMasker to achieve a more accurate decision. The detailed co-training process shown in Algorithm 1 of Appendix A1.1. When the training is done, conduct Step 2 to perform the pruning.
Step 2: Co-sparsifying the input graphs and GNN model. Having obtained the well-trained AutoMasker and GÑN model, we can apply the knowledge learned from numerous graphs to co- sparsify the graphs and the model. For graphs, all the edges for each graph. Then the edges of a certain graph are sorted based on the mask values, and the edges with 5% the lowest values are pruned to obtain the binary graph mask mg. For GNN, we sort the parameters based on the weight magnitude and prune 20% the lowest- magnitude parameters to obtain the binary model mask me. Under the current sparsity level, we now successfully obtain the sparsified graph g' = (mg C A, X) and the sparsified mask me for the model. Finally, we need to check whether the sparsity meets our condition. the sparsity is satisfied, the algorithm is completed; if not, we need to reuse the found GLT to update the original graphs and GNN model, and iteratively use Step and Step 2 (dotted arrow in Figure 1) until the condition is met. In Appendix A1.1, Algorithm 2 offers the detailed algorithm of ICPG.
adopt AutoMasker predict the importance
EXPERIMENTS
In this section, we conduct extensive experiments on diverse benchmarks to validate the effective- ness of the ICPG. We first introduce the experimental settings in Section 4.1, and explore the exis- tence of GLTs in graph classification and node classification in Sections 4.2 and 4.3, respectively. We also validate the transferability of the AutoMasker Section 4.4. More ablation studies and visualizations are provided in Sections 4.5 and 4.6, respectively.
4.1 EXPERIMENTAL SETTINGS
Datasets. For graph classification, we use two biological graphs (NCII, MUTAG), four social graphs (COLLAB, RED-B, RED-M5K, RED-MI2K) (Morris et al., 2020), two superpixel graphs (MNIST, CIFAR-10) (Knyazev al., 2019), and two large-scale Open Graph Benchmark (ogbg- ppa and ogbg-code2) (Hu al., 2020). For node classification, choose the transductive learning dataset: Cora, and the inductive learning dataset: PPI. More details are provided Appendix Al.
Models and Training Details. We adopt the same architecture for the GNN model and GNN encoder for AutoMasker. For all graph classification datasets and Cora dataset, we adopt the GCN (Kipf & Welling, 2016) model with different layers and hiddens. For the PPI dataset, GAT (Veličković et al., 2017) network to achieve a better baseline performance as work (Veličković al., 2017). More details about models and training are provided in Appendix A A1.4 and A A..5.
choose the
5

---

Under review as a conference paper at ICLR 2022
NC11
MUTAG
COLLAB
RED-B
100
80
80
Paqurascy (8)
80
70
RP
RP
RP
RP
(Curs)
IGPG
70
ICPG [Curs]
60
Baseine
70
Baseline
Baseline
60
Basalio
RP-GLLT ( (0%)
RP-GLT (18.65))
RP-CL (6 (0%)
RP-GLT (9.75%)
50
(2649%)
ICPG-GLT 17%)
ICPB GLT (33.00%)
ICPG (22
Graph Sparsily (%)
Graph Sparsily 186)
Graph Sporsity (%)
Graph Spareity (8)
RED-M5K
RED-M12K
MNIST
CIFAR-10
50
80
20 35
Accuraai
40
40
40
ICPG (Durs)
ICPG (Durs)
ICPG (Ouns)
ICPG (Ours)
Baseine
30
Baseline
40
Basefne
30
Basslino
30
CLT (1926%)
GL (9.76%
(0.00%)
20
RP (0.00%)
20
ICPG-OLT (40.18%)
ICPO-CLT
ICPG-CLT 125)
ICPO-OLT (14 26%)
Graph Sparshty (%)
Graph Sparsity
Graph Sparsiyy
Grapn Sparsty (N)
Figure 2: Graph classification performance on achieved graph sparsity.
4.2 GRAPH LOTTERY TICKETS IN GRAPH CLASSIFICATION
We first conduct experiments to find the GLT's in graph classification tasks. The results are displayed in Figure 2 and Figure 3. We also plot the random pruning (RP) for better comparison. Stars denote the extreme sparsity, which is the maximal sparsity-level without performance degradation. More results about GNNs sparsity are provided in Appendix 12.1. We make the following Observations:
Obs.1. GLTs extensively exist in graph classification tasks. Utilizing the ICPG, fully locate the GLTss with different sparsity-leveks from different types of graphs. For NCI1 and MUTAG, we precisely identify GLTs with the extreme graph sparsity at 26.49% and 30.17% GNN sparsity at 73.79% and 79.03%, respectively. On four social network datasets, we find the GLTs with graph sparsity of 22.62%%~51.223% and GNN sparsity-level in 37.23%~95..60%. For MNIST and CIFAR-10, the GLTs are achieved with graphs sparsity of 43.13% and 14.26%, GNN sparsity of 91.41% and 48.80% These results show that ICPG can locate the high-quality GLTs in graph classification tasks with different graph types, and demonstrate the potential of efficient training or inference with sparser graphs and lightweight GNNs without sacrificing performance.
success-
Obs.2. AutoMasker has good generalization ability. The mainstream graph sparsification tech- niques (Chen et al., 2021; Zheng et al., 2020; Li et al., 2020b) cannot inductively prune unseen graphs. However, the AutoMasker can flexibly overcome this challenge. Compared with random pruning (RP), our proposed ICPG can find more sparse subgraphs and subnetworks and keep large gap with RP. For instance, the RED-M5K and RED-MI2K graphs pruned by ICPG can achieve 40. and 51. 11.23% extreme graph sparsity, improving 25.87% and 41.48% compared with RP, which keeps extremely large superiority. The excellent results indicate that AutoMasker can pre- cisely capture more significant core- core-patterns from the training graphs and have a good generalization ability to predict the high-quality masks for unseen graphs.
Obs.3. The extreme sparsity of GLTs depends on the property of graphs. Although ICPG achieves higher spar- sity than RP on most graphs, the im-
ogbg-ppa
ogbg-code2
60
14
Accuracy (%)
provements are not obvious on a small part of the graphs, such as biochemical molecule graphs: NCII or MUTAG. We make the following conjectures: Firstly, most of the edges in these graphs are important, such as a certain edge may correspond to crucial chemical bond, which may drastically affect the chemi- cal properties of the molecule if pruned. Secondly, the graph size is relatively small, which just includes a few dozen nodes and edges, so is more sensitive to pruning. On the contrary, the larger social network datasets, such as RED-M5K
12
RP
RP
ICPG (Ours)
10
ICPG (Ours)
Baseline
F1
Baseline
RP-GLT T (5.00%)
RP-GLT (0.00%
ICPG-GLT (14.26%)
ICPG-OLT (18. (18.58%)
Graph Sparsity (%)
Graph Sparsity (%)
Figure Graph classification performance over achieved graph sparsity on large-scale scale datasets.
6

---

Under review as a conference paper at ICLR 2022
or RED-MI2K, contain hundreds thousands of edges for each graph, there may be plenty of redundant edges that demonstrate the insensitivity to pruning.
Obs.4. AutoMasker can well tackle larger-size and larger-quantity graphs. Figure 3 demon- strates the results on the challenging OGB datasets, which are consist of larger-size graphs (2266.1 edges and 243.4 nodes on average per graph for ogbg-ppa) and larger-quantity graphs (452,741 graphs for ogbg-code2). We surprisingly find the OGB datasets are so intractable that RP can only locate 5% graph sparsity of GLT on the ogbg-ppa, and it is even impossible find any sparser GLTs on the ogbg-code2, Despite this, the proposed ICPG can locate the GLTs with 14.26% and 18.55% graph sparsity, 48, 80% and 59.40% GNN sparsity on ogbg-ppa and cobg- respectively. The superior performance further verifies the strong scalability and generalization of the AutoMasker.
4.3 GRAPH LOTTERY TICKETS IN NODE CLASSIFICATION
Since ICPG can achieve excellent performance diverse types and scales of graphs, also want to explore that it can also tackle node-Ievel tasks. To answer this question. we conduct experiments on Core and PPI datasets, which are commonly used in transductive and inductive node classification tasks. We also reproduce the recent work UGS (Chen et al., 2021) for Cora (cannot apply for inductive setting) for better comparison. We can get the following Observations:
Obs.5. ICPG can achieve excellent performance on node classification tasks. Firstly, for Cora, both ICPG and UGS can find GLTs that are sparser than RP. which demonstrates that both are applicable to transductive node classifi- cation. Secondly, ICPG can find sparser GLTs than UGS (17.94%) while the performance drop faster than UGS in the later stage, we give the following con- jectures: (1) UGS just adopts simple trainable masks for edges without con- sidering the global topological structure of the entire graph, while AutoMasker is constructed based on a GNN-encoder, which can provide a global understanding of the whole graph. Hence, the AutoMasker can predict more high-quality masks than UGS. (2) ICPG is worse than UGS in the later stage. The reason is that AutoMasker has found the most significant edges in advance, which consists of an extremely compact core- our-ruugg at certain critical point, so further pruning over that point will seriously degrade the performance. Thirdly, as for the PPI dataset, the performance of ICPG still keeps large gap with RP and can achieve 22.62% graph sparsity and 67.23% GNN sparsity without sacrificing performance, which further demonstrates the effectiveness of the ICPG on inductive learning.
Cora
PPI
100
80
Maaurasyy (%)
60
UGS
80
ICPG (Ours)
Baseline
ICPG (Ours)
40
RP. (9.75%
Baseline
VLS-GLL
RP-GLT (0.00%)
60
ICPG (26 49%
ICPG CPGG-GLT (22.82%)
Graph Sparsity (%)
Graph Sparsty (%)
Figure 4: Transductive and inductive node classification
performance on achieved graph sparsity.
4.4 THE TRANSFERABILITY OF THE AUTOMASKER
We consider two orthogonal perspectives to verify the transferability of the AutoMasker: GNN-level transferability and graph-level transferability. From GNNs view, we transfer the sparse graphs found by AutoMasker to the other two popular GNN models: GIN (Xu et al., 2019) and GAT (Veličković et al., 2017). From graphs view, we first pre-train the AutoMasker on larger-scale RED-MI2K graphs and then transfer the well-trained AutoMasker to other two smaller-scale graphs: RED-B and RED-M5K. Please notes that we keep the GNN models unpruned on transferred tasks. The experimental results are provided in Figure 5 and Table 1. We make the following Observations:
Obs.6. AutoMasker has both GNN-level and graph-level transferability. For GNN-level, we can observe from Figure 5 that GIN and GAT can achieve ranging 9.75%~45.965% and 18.55%~~22.62%% extreme sparsity on NCII and RED-MI2K without sacrificing performance. And AutoMasker also outperforms RP and keeps large gap. These results demonstrate that AutoMasker can effectively extract the GNN-independent subgraphs. These sparse subgraphs represent significant semantic in- formation and can be universally transferred to any GNN architecture without performance degrada- tion. For graph-level. the performance of random pruning decreases as the graph sparsity increases. For RED-B and RED-M5K, when the pruning sparsity increases from 0 to 55.99% the performance
7

---

Under review as a conference paper at ICLR 2022
NCI1 (GIN)
NC11 (GAT)
RED-M12K (GIN)
RED-M12K (GAT)
85
50
Rocurasy (8)
80
80
75
75
46
RP
46
70
AutsMaskor
Busalin
22 o PA 895535
Graph Sparsity (%)
Graph Sparsity (%)
Graph Sparsity
Graph Sparsity (%)
Figure 5: Performance of diverse GNNs on the sparse graphs found by AutoMasker.
Table 1: Graph-level transferability performance. From RED-MI2K to RED-B and RED-M5K
Settings
Graph Sparsity
Dataset
Method
0% (No pruning)
9.75
18.55 %
33.66 %
45.96
55.99 %
Random Pruning
1..
1.22
89.75+1.75
86.75:12.41
85.1593.92
85.34:11.67
RED-B
AutoMasker
12,15++1.59
92.16
+-214
90.15 1.89
90.06
89.64
Random Pruning
56.63+t:0.33
$6.33:+1..59
55.85++1100
54.81+22,17
14.19-22.27
$4.95:t:1.79
RED-M5K
AutoMasker
56.63440.93
56.89:12.16
56.69:12.59
57.0113..90
56.97:12.86
56.09:1-.444
decreases by 7.39% and 2.97%, respectively. While AutoMasker can achieve consistent improve- ment within all sparsity levels. Furthermore, the GNN model trained with more sparse graphs even outperforms the GNN trained with the original dense graphs, such as RED-B at 9.75% and RED- M5K at 75%.6%% It demonstrates that the pre-trained AutoMasker can transfer the learned knowledge to small-scale downstream tasks, with lower computational cost and better performance. In summary, AutoMasker can learn model-independent, general and significant sparse subgraph structures from the graphs, so that it has outstanding GNN-level and graph-level transferability.
4.5 ABLATION STUDY
In this section, we investigate the diverse encoder networks in Au-
RED-MSK
PPI
100
toMasker and explore the two inde- pendent components in ICPG. We
Acourayy (%)
50
90
can make the following findings:
70
RPGM
ICAG
GCN GIN
MLP
RPG--P
PG
Encoder networks. AutoMasker is designed on a GNN-based encoder, which leads to a global understanding of each edge from the entire graphs. So we extensively investigate the im- pact of the diverse encoders, such as GNN-based or MLP-based encoders. We can observe the results from Fig- ure 6 (Left) that, for all the GNN-based encoders, AutoMasker can achieve good performance: 45. 45.96% extreme sparsity for GCN and 51.23% for GIN and GAT, while MLP-based encoder only achieves 33.66% extreme sparsity. It indicates that the message passing scheme of the GNN encoder naturally considers the graph structure from global view, while the MLP-based encoder does not.
RP
60
RPG
PM
Basaline
Baseltie
20
Graph Sparsity (36)
Graph Sporsity (N)
Figure 6: (Left): graph sparsity with AutoMasker based on diverse encoders. (Right): The comparison of different components in ICPG.
The performance of ICPG over achieved
Co-sparsification. To further study the effectiveness of each component in ICPG: mask-based prun- ing for graphs (PG) and magnitude-basee their roles when applying on the graphs and the model independently. We also plot the performance of random pruning only for graphs (RPG), only for models (RPM), both of all (RPGM), random pruning for graphs with magnitude-based pruning for model (RPG-PM) for comparison. The results are summarized in Figure 6 (Right). We can find that: PG can also find the matching subgraphs (9.75% sparsity), which indicates that apply AutoMasker separately can also extract the significant edges from each graph. PM can also locate the matching subnetworks at 14.26% sparsity, which is consistent with the LTH (Frankle & Carbin, 2018) in the computer vision field. ICPG significantly outperforms RPGM and RPG-PM, and the gap gradually widens as the sparsity increases. We also observe that ICPG is even better than PG (11..77% we made the following conjectures: (1) As for
pruming for model (PM), we separate them and explore
8

---

Under review as a conference paper at ICLR 2022
Original Image
Original Graph
RP Graph
ICPG Graph
Original Image
Original Graph
RP Graph
ICPG Graph
4
8
(a) MNIST
(b) CIFAR-10
Figure 7: Visualization of the subgraphs extracted by AutoMasker from MNIST (a) and CIFAR- 10 (b) superpixel graphs. Original images and graphs are displayed on the first and second columns in (a) and (b), respectively. The sparsity of RP and ICPG in (a) and (b) is 1.%%.
PG, with the sparsity gradually increasing, the graphs also become more simple. If we still train the over-parameterrized GNN model with simple graphs, it may cause over-fitting. (2) Slightly pruning the werr-parameterized GNN through PM can be regarded improve the performance, and is consistent with LTH (Frankle & Carbin, 2018). Further, the regularized GNN can additionally provide AutoMasker with more precise supervision signals from the gradient in backpropagation to make more wise decisions. To summary, we should co-train the AutoMasker and GNN and co-sparsify the input graphs and model to achieve better performance.
kind of regularization, which will
4.6 VISUALIZATION AND ANALYSIS
To better illustrate the significant subgraphs extracted by the AutoMasker, we visualize the matching subgraphs in GLT's found by the ICPG. We select graphs with 64. 15% sparsity level from the MNIST and CIFAR-10 superpixel datasets. For better comparison, we also plot the original images, original graphs, random pruning graphs, which are depicted in Figure 7. More wonderful visualizations are provided in Figure All and Figure A12. We can make the following findings:
For MNIST and CIFAR-10, the edges between nodes that locate on the digitals and objects pix- els (the dark blue nodes) should be denser, which are conducive the graph classification tasks. RP evenly prunes the significant edges or structures without considering any important reference, which makes the core-subgraphs destroyed and seriously deteriorates the performance. ICPG uti- lizes Masker to learn the significance of each edge from global view and can precisely prune redundant edges. As the ICPG graph in Figure (a) shows, the pruned edges are mainly located on non-digital pixels, such as the upper-left, lower-right corners and the center part of the number O: the lower-left corner of the number 8, while the remaining edges or nodes are mainly located on digital pixels, which demonstrate that AutoMasker can indeed extract significant patterns.
5 CONCLUSION
In this work, we endow the graph lottery tickets with inductive pruning capacity. We propose a simple and effective pruming framework ICPG, co-sparsify the input graphs and GNN model. For graphs, we propose a generative probabilistic model to generate the importance score for each edge. provides a global understanding of edge importance from the entire graph topological structure to guarantee high-quality graph masks and has strong generalization ability and transferability in inductive learning settings. For the model, we adopt the GNN weight's magnitude to estimate their importance scores. Then co-sparsify the input graphs and GNN model based on their impor- tant scores to find the graph lottery tickets. Extensive experiments on diverse types (biochemical molecules, social networks, superpixel graphs, citation networks) and scales (small, medium, large) of graphs, diverse learning settings (inductive, transductive) and diverse tasks (graph classification, node classification) consistently validate the effectiveness of the ICPG.

---

Under review as a conference paper at ICLR 2022
6 ETHICS STATEMENT
In recent years, graph neural networks (GNNs) have been widely applied in learning and process- ing graph-structured data, such as recommendation systems and drug discovery. With the rapidly growing size of graphs, deep graph neural networks will inevitably confront expensive computa- tional costs and slow response times in the training and inference stage. Hence, it is challenging to implement deep GNNs in real-world large-scale graphs. However, the current GNNs pruning methods cannot solve the inductive learning settings, which are common in real-world scenes, such as dynamicc social networks learning. Fortunately, the proposed co-pruning framework provides an effective and practical solution to reduce computational costs, which can be universally applicd to both transductive and inductive graph learning. Furthermore, the proposed AutoMasker also gives novel pre- training perspective to save the computational cost in downstream tasks.
7 REPRODUCIBILITY STATEMENT
We promise that all results in this paper are reproducible. The models, datasets, and training and inference settings in this paper have been given in the main text and Appendix A1. To help readers easily reproduce our results, we provide more detailed explanation. Codes available at https: / /aanoyynous 4open. science/ Inductive httprr/oooooooooooeooooetteeeere Srcckterr_Tikke_..cee hitprerr__ricceeeeeerinnnnn-aaa Learning-1419
(I) Models. For simplicity, we keep the same GNN architecture for the proposed AutoMasker and the following GNN model. Please note that Autoeasker usually requires fewer hidden units. The GNN encoder network of Auto.asker can also be changed needed and we have already given an example of replacing GCN based encoder with GIN or GAT in the ablation study. All the results in this paper are based on the GCN model, except for the PPI dataset. According to the suggestion of (Veličković et al., 2017), GAT (Veličković et al., 2017) network can achieve a better baseline performance on PPI dataset. More detailed model settings such as the number of layers or hidden units have been summarized in Appendix A1.4 and Table A3.
(2) Datasets. We conduct all the experiments on common graph learning benchmarks (Dwivedi et al., 2020; Xu et al., 2019; Veličković et al., 2017; Kipf & Welling, 2016; You et al., 2020; Hu al., 2020). We have summarized the detailed information of the datasets in Appendix A1.2, the statistics of the datasets in Table A2, the method of the datasets splitting in Appendix A1.3.
(3) Baselines. We adopt the following two baselines for comparison: random pruning (RP) and UGS (Chen et al., 2021). For random pruning, we simply adopt a completely random selection strategy to prune the edges of the graph or the parameters of the GNN model. For UGS, we reproduce the results of the original paper (Chen al., 2021) based on the released code.
(4) Training and inference settings. We extensively refer to the training settings for numerous literature in the field of graph learning (Chen et al., 2019; Xu et al., 2019; Dwivedi et al., 2020; Chen et al., 2021; Veličković et al., 2017), and configure the training hyperparameters according to their suggestions. The detailed training settings have been given in the Appendix A1.5, As for inference settings, we adopt the method consistent with (Chen et al., 2021; Xu et al., 2019; Hu et al., 2020). For the TUDataset, we adopt the 10-fold cross validation and report the mean and standard deviation. For the OGB datasets, we follow the official method (Hu et al., 2020) to report the results. For other datasets, we report the test accuracy the epoch with the best validation accuracy.
REFERENCES
Radhakrishna Achanta, Appu Shaji, Kevin Smith, Aurelien Lucchi, Pascal Fua, and Sabine Süsstrunk. Slic superpixels compared to state-of-the-an superpixel methods. IEEE transactions on pattern analysis and machine intelligence, 34(11)2224-2288. 2012.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: Fast learning with graph convolutional networks via importance sampling. In International Conference on Learning Representations, 2018.
Tianlong Chen, Jonathan Frankle, Shiyu Chang, Sijia Liu, Yang Zhang, Michael Carbin, and Zhangyang Wang. The lottery tickets hypothesis for supervised and self-supervised pre-training in computer vision models. arXiv preprint arXiv:20/2.06908 2020.
10

---

Under review as a conference paper at ICLR 2022
Tianlong Chen, Yongduo Sui, Xuxi Chen, Aston Zhang, and Zhangyang Wang. A unified lottery
ticket hypothesis for graph neural networks. arXiv preprint arXiv:2102.06990, 2021.
Ting Chen, Song Bian, and Yizhou Sun. Are powerful graph neural nets necessary? a dissection on graph classification. arXiv preprint wwXiv:/905.04577 2019.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.00953 2020.
Luca Franceschi, Mathias Niepert, Massimiliano Pontil, and Xiao He. Learning discrete structures for graph neural networks. In International conference on machine learning, pp. 1972-1982.
PMLR, 2019.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference on Learning Representations, 2018.
Will Hamilton, Zhitao Ying. and Jure Leskovec. Inductive representation learning on large graphs. In Advances in neural information processing systems, pp. 1024-1034, 2017.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovee. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.0068) 2020.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: /11.666099000... 2016.
Boris Knyazev, Graham Taylor, and Mohamed R Amer. Understanding attention and generaliza- tion in graph neural networks. arXiv preprint arXiv: 1et5:02550005 2019.
Jure Leskovec and Christos Faloutsos. Sampling from large graphs. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 631-636, 2006.
Guohao Li, Chenxin Xiong, Ali Thabet, and Bernard Ghanem. Deepergen: All you need to train deeper gens, arXiv preprint arX1v:2006.07739, 2020a.
Guohao Li, Matthias Müller, Guocheng Qian, Itzel Carolina Delgadillo Perez, Abdulellah Abual- shour, Ali Kassem Thabet, and Bernard Ghanem. Deepgens: Making gens go as deep as cnns. TPAMI, 2021.
Jayy 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.
Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell. Rethinking the value of network pruning. In 7th International Conference on Learning Representations, 2019.
Haoyu Ma, Tianlong Chen, Ting-Kuei Hu, Chenyu You, Xiaohui Xie, and Zhangyang Wang. Good students play big lottery better. arXiv, abs/2101 01.0255, 2021.
Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. arXiv preprint arXiv:2007.08663, 2020.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. arXiv preprini 1rXiv:1977.10900 2019.
Pedro Savarese, Hugo Silva, and Michael Maire. Winning the lottery with continuous sparsification. In Advances in Neural Information Processing Systems 33 pre-proceedings. 2020.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua 2017.
Bengio. Graph attention networks. arXiv preprint
Elli Voudigari, Nikos Salamanos, Theodore Papageorgiou, and Emmanuel J Yannakoudakis. Rank
degree: An efficient algorithm for graph sampling. In 2016 JEEE/ACM International Conference Advances in Social Networks Analysis and Mining (ASONAM), pp. 120-129. IEFF, 2016.
11

---

Under review as a conference paper at ICLR 2022
Chaoqi Wang. Guodong Zhang, and Roger Grosse. Picking winning tickets before training by preserving gradient flow. In 8th International Conference on Learning Representations, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural
networks? In International Conference Learning Representations, 2019. URL https: //openzeview, htt///ooommmmmrreeeeeeeeeee
Shihui Yin, Kyu-Hyoun Kim, Jinwook Oh, Naigang Wang, Mauricio Serrano, Jae-Sun Seo, and Jungwook Choi. The sooner the better: Investigating structure of early winning lottery tickets, 2020.
Rex Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gan explainer: A tool for post-hoe explanation of graph neural networks. arXiv preprint arXiv: 003.999990.. 2019.
Zhitao Ying. Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hi- erarchical graph representation learning with differentiable pooling. In Advances in Neural Infor- mation Processing Systems, pp. 4800-4810, 2018.
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. Advances Neural Information Processing Systems, 33, 2020.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. arXiv preprint arXiv: 1907.0491,, 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 1458811468, PMLR, 2020.
Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review methods and applications. arXiv preprint arXiv:1812.08434, 2018.
A12

---

Under review as a conference paper at ICLR 2022
A1
MORE IMPLEMENTATION DETAILS
A1.1 ALGORITHMS
We summarize the detailed implementation of the proposed ICPG in Algorithm The Algorithm represents the co-training and co-sparsifying for a single iteration in ICPG.
Algorithm 1: Mask & Magnitude Pruning
Algorithm 2: Finding GLTs by ICPG
Input: D, f(: + g AutoMasker(;; mo)
Input: Graphs D = {9 (A,, ))
M, me, Epoch T. Output: Sparsified masks (m/, J.N. m'.
f(, O no AutoMasker( Oao) sparsity levels Sd. 80.
for f = 0 -'
Output: GLT {g] (me, O A, x,)
for G. D and mg, E E do
f(: f(:ma
go
9; + (mg, @ X;)
Initialize masks set M + {mg. + A
Sg: AutoMasker(G; On.)
2 Initialize GNN mask ma f- 1 R
Ga < (Sc. ④ A; ; X,)
3 while the sparsity of .M < Sd, ma < S8 do Sparsify the GNN ((; with me and dataset D =9 (A,, X
Forward f(g,, me )x)
Backward to update O Putss ge41
end
with the mask set M and get the new masks as presented in Algorithm I. Update M + (mg. + m y
end
for
G E do
11
Sg. <- AutoMasker(G, @ar)
Update m <- m'e
12
Set 5% of the lowest mask values in sg,
7 Rewind AutoMasker's weight Oap- Rewind GNN's weight to + g0-
to 0 and others to 1, creating m'g.-
13 end
end
14 Prune 20% of the lowest magnitude parameters in C gr, creating m'g.
A1.2 DATASETS DETAILS
As for graph classification, we conduct the experiments with three scale levels: small-scale, medium- scale and large-scale. We provide the following details:
Small-scale: We adpot the TUDataset (Morris et al., 2020), which is a collection of benchmark datasets for graph classification and regression. We choose two biological graphs: NCII, MU- TAG and four social graphs: COLLAB, Reddit-Binary (RED-B), Reddit-MultiSSK (RED-M5K), Reddit-Multi-121 (RED-M12K) as numerous works (Xu et al., 2019; You et al., 2020; Dwivedi et al., 2020) does.
Medium-scale: We use MNIST and CIFAR-10 superpixel graphs. The original MNIST and CIFAR-10 images are converted to graphs using superpixels, which represent small regions of homogeneous intensity in images and can be extracted with the SLIC (Achanta et al., 2012) tech- nique. These datasets are commonly used in numerous graph representation learning researches (Dwivedi et al., 2020; You et al., 2020; Knyazev et al., 2019).
Large-scale, we adopt the Open Graph Benchmark (OGB) (Hu et al., 2020), which is a collec- tion of realistic, large-scale, and diverse benchmark datasets for machine learning on graphs. We choose two commonly used large-scale graph property prediction dataset: ogbg-ppa and ogbg- code2. The ogbg-ppa dataset set of undirected protein association neighborhoods extracted from the protein-prove
association networks of 1,581 different species that cover 37 broad taxo- nomic groups and span the tree of life. The ogbg-code2 dataset a collection of Abstract Syntax Trees (ASTs) obtained from approximately 450 thousands Python method definitions.
As for node classification, we use the commonly used citation network Cora dataset for semi- supervised learning and the popular inductive learning dataset PPI. The task for PPT is classifying protein functions across various biological protein-prone protein interaction (PPI) graphs. These datasets commonly used in transductive learning (Kipf & Welling, 2016; Veličković et al., 2017) and in- ductive learning (Hamilton et al., 2017; Zheng et al., 2020) researches. All the detail statistics about theaforementioned datasets summerized in Table A2.
A13

---

Under review as a conference paper at ICLR 2022
Table A2: Datasets statistics.
Datasets
Category
Graphs
Avg. Nodes
Avg. Edges
Avg. Degree Classes
NCI1
Biochemical Molecules
4,110
29.87
32.30
1.08
MUTAG
Biochemical Molecules
188
17.93
19.79
1.10
2
COLLAB
Social Networks
5,000
74.49
2457.78
32.99
RED-B
Social Networks
2,000
429.63
494.07
1.15
2
RED-M5K
Social Networks
4,999
508.52
594.87
1.17
RED-MI2K
Social Networks
11,929
391.41
456.89
1.16
11
MNIST
Superpixel Graphs
70,000
70.57
564.56
8.00
10
CIFAR-10
Superpixel Graphs
60,000
117.63
941.04
8.00
10
ogbg-ppa
OGB Dataset
158,100
243.4
2,266.1
9.31
37
ogbg-code2
OGB Dataset
452,741
125.2
124.2
0.99
Cora
Citation Network
2708
5429
2.00
PPI
Biological Protein
24
2372.67
34113.16
14.38
121
A1.3 DATASETS SPLITTING
TUDataset: We perform the commonly used 10-fold validation. Consistent with the work (Chen et al., 2019; Xu et al., 2019), we select the epoch with the best cross-validation accuracy averaged over the 10 folds and report the average and standard deviation of accuracies the selected epoch over 10 folds.
Consistent with (Dwivedi al., 2020), we split them 55000 train/5000 vali- dation/ 10000 test for MNIST, and 45000 train/5000 validation/ 10000 test for CIFARIO respectively. We report the test accuracy the epoch with the best validation accuracy.
Superpixel dataset:
OGB dataset: We adopt the official dataset splitting method for ogbg-ppu ppa and ogbg-code2 in the following links: sttps://oggt stanford. wew/ddocsssseeeee http://ooss//ppppheeeeeee graphprop. #ogbg-ppa and https: ogb.
wwtp///o///eeeeeeeeeeeeeeeeeee// wetp///occs//rppppppoo//// #ogbg-code2.
Following the work (Chen al., 2021), we use labeled data for training, 500 nodes for validation and 1000 nodes for testing and report the test accuracy at the epoch with the best validation accuracy.
Cora:
We adopt the same splitting as works (Hamilton et al., 2017; Veličković et al., 2017). The dataset contains graphs for training, 2 validation and for testing. Critically, testing graphs remain completely unobserved during training.
PPI:
A1.4 MODEL CONFIGURATIONS
TUDataset: adopt the ResGCN (Chen al., 2019) with 3 layers and 128 hidden dimensions. Superpixel dataset: we use GCN with 4 layers and 146 hidden dimensions as work (Dwivedi et al., 2020). OGB dataset: we five-layer GCN model with 300 hidden dimensions for all experiments. Cora dataset: we adopt two-layer GCN network with 512 hidden dimensions as work (Chen et al., 2021). PPI dataset: we adopt two-layer GAT network with 256 hidden and 4 attention heads as work (Veličković et al., 2017). For GCN encoder in AutoMasker, we use the same structure with different hidden dimensions as the GNN model. More details are summarized in Table A3.
A1.5 TRAINING DETAILS
All training parammersssserss such as epochs, learning rate for GNN model and AutoMasker, opti- mizer, batch size, weight decay summarized in Table A3.
A14

---

Under review as a conference paper at ICLR 2022
Table A3: Implementation details of graph classification and node classification.
Task
Graph Classification
Node Classification
Dataset
TUDataset
Superpixel
ogbg-ppa
ogbg-code2
Cora
PPI
Epoch
100
100
100
25
200
100
Optimizer
Admm
Admm
Admm
Admm
Admm
Admm
Batch Size
128
128
32
128
1
Weight Decay
0
Se-4
Model Layer-hidden
3-128
4-146
5-300
5-300
2-512
2-256
AutoMasker Layer-hidden
3-64
4-146
5-300
5-300
2-128
2-128
Model LR
le-3
le-3
le-3
1e-3
le-2
Se-3
AutoMasker LR
le-4
5e-3
le-3
1e-3
le-2
le-3
A2
MORE EXPERIMENTAL RESULTS
A2.1
GRAPH LOTTERY TICKETS GRAPH CLASSIFICATION
The graph classification performance with different GNN sparsity levels is shown in Figure A8. The performance on large-scale datasets is provided in Figure A9.
NC11
MUTAG
COLLAB
RED BB
100
80
Accuraay (%5
80
70
RP
ICPG (Curs)
IDPG (Cuss)
ICPG (Oun)
ICPG (Ours)
80
RP.GLT (20.0%)
(09.04))))04
RP GLT (20 00%
80
RP/GLT (36.0)))
ICPG-OLT (73.78%)
ICPG-CLT
ICPC-OLT (83.22%)
ICPO-OLT (57.288)
50
50
o Pa
& l PAAPAA
GNN Sparsity (%)
GNN Sparsity (%6
GNN Sparsity (9)
GNN Sparsity (%)
RED-M5K
RED-M12K
MNIST
CIFAR-10
60
50
Pecuratyy (%6
50
RP
RP
80
RP
40
RP
40
ICPG
ICPG (Curs)
Baseiie
Baseling
Baseling
30
Baselife
30
RR.LT (48.80%)
RP-CLT (38 00%)
RP-CLT (0.00%)
AP-OLT 00%)
(0.0%))
(9141%)
61%)
20
ICPGALT (1141%)
ICPG-GLI (48,80%)
20
GNN Sparsity (%)
GNN Sparsity (%)
GNN Sparsity (%)
GNN Sparsity (%)
Figure A8: Graph classification performance over achieved GNN sparsity.
ogbg-ppa
ogbg-code2
60
14
Accuracy (%)
F1 score (%)
12
40
RP
RP
ICPG (Ours)
10
ICPG (Ours)
Baseline
Baseline
20
RP-GLT (20.00%)
8
RP-GLT (0.0%%)
ICPG-GLT (48 80%)
ICPG-GLT (59 04%)
0.00
20.90
30.00
80
0.00
20.00
30.00
48.00
59.00
GNN Sparsity (%)
GNN Sparsity (%)
Figure A9: Graph classification performance over achieved GNN sparsity on large-scale datasets.
A15

---

Under review as a conference paper at ICLR 2022
A2.2 GRAPH LOTTERY TICKETS IN NODE CLASSIFICATION
More results about the transductive and inductive node classification on achieved GNN sparsity are shown in Figure A10. We can observe that ICPG can achieve 73.79% GNN sparsity for transductive node classification and 67. 2.% GNN sparsity for inductive node classification.
Cora
PPI
100
80
70
RP
90
Accuracy (%)
UGS
ICPG (Ours)
RP
50
Baseline
70
ICPG (Ours)
RP-GLT (3.00%%
Baseline
40
UGS-GLT (59.04%)
RP-GLT (0.00%)
60
ICPG-GLT (73.79%)
ICPG-GLT (3%)
30
0.00
20.00
00
48,00
50.0
0.00
20,00
48.90
GNN Sparsity (%)
Graph Sparsity (%)
Figure A10: Transductive and inductive node classification performance achieved GNN sparsity.
A3 MORE VISUALIZATION RESULTS
More visualization results about the MNIST and CIFAR-10 superpixel graphs are shown in Figure All and Figure A12. For MNIST, the important subgraphs are mainly located on the digital pixel area. We can observe that RP evenly prunes the connections between any two nodes without consid- ering any important information. While the proposed AutoMasker mainly prunes the insignificant edges that locate on non-digital pixel background. For CIFAR-10, objects for classification, so the edges between the nodes that locate on the objects (the dark blue nodes) should be denser. We can observe that RP prunes on both the objects and the background, which also makes all the vital edges become sparse. As a comparison, the subgraphs extracted by AutoMasker remain most of the edges located on objects while the sparsify edges are located on the backgrounds. In summary, the AutoMasker effectively extracts the sigmificant core patterns while filter out the re- dundant edges from dense graphs, which necessarily leads to less degradation on performance even the graphs are heavily pruned.
critical information
A16

---

Under review as a conference paper at ICLR 2022
Original Image
Original Graph
Graph
ICPG Graph
{
2
SES9
8
9
Figure Al1: Visualization of the subgraphs at 64.15% sparsity from MNIST superpixel graphs.
A17

---

Under review as a conference paper at ICLR 2022
Original Image
Original Graph
Graph
ICPG Graph
Figure A12: Visualization of the subgraphs at 64.15% sparsity from CIFAR-10 superpixel graphs.
A18


Reviews:
[{"review_id": "p-MYyI4LZlk", "reviewer": "Reviewer_FXPK", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "1) What is the practical purpose/use cases of the proposed method?  can the proposed method reduce the training time over GCN? Speeding up the inference? if so how much inference/training time can be saved? Or can the proposed method improve the prediction accuracy?\n\n2) The paper seems getting confused about graph sampling over graph sparsity. See the section of \"Graph Sparsification\" in page 3. In fact, graphsage and fastGCN are both graph sampling method (definitely not for graph sparsity) aiming for speed up the training of GCN, and used in inductive setting, and is NOT transductive only. \n\n3) what is the time complexity/running time for the proposed method? It seems to me that the proposed method is quite expensive---many rounds of GCN training and heavy computation over scoring the edge, # of edges of pair of data points. And how about  the scalability of the proposed method. I saw the experiment are all done on the small/median scale datasets. \n\n4) What is the novelty of the proposed method of weight pruning? To my understanding, weight pruning using magnitude of weights score is quite well known--because there will be some redundancy in the weights during training.\n", "summary_of_the_paper": "This paper is on generalizing UGS, (Chen et al., 2021) from transductive setting to inductive setting. The main idea is to learn the importance of each edge using the MLP over the learnt embedding from GNN, and pruning them through sorting the importance score. And weight pruning is done just by sorting the magnitude of weights in GCN. \n\n\n ", "summary_of_the_review": "I have concerns about novelty, scalability, and practical use case of the proposed method.  \n\n------ after reading the rebuttal\n\nThanks for the replies from the authors. I have read the reviews carefully. Some of my concerns are indeed solved, but I am still not convinced by the novelty, scalability and usefulness of the proposed method. For example, the use of this method is improving the inference time. The inference speed ups as shown in the comments are not significant, while lots of state-of-the-art inference speed up methods can do at least 10x speedup. Also according to the comments, the scalability is indeed a problem due to the lottery tickets problem, which is the main idea of the paper. So I think this paper's use scope is limited. ", "strength_and_weaknesses": "", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "Jd80A8IL7ul", "reviewer": "Reviewer_6qg1", "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": "In Section 4, the authors evaluate ICPG on an extensive collection of datasets covering a several domains. Since the authors don't have a comparable baseline from previous works, they compare their method against Random Pruning which I think is acceptable.\n\nICPG consistently produces sparser graphs with higher accuracy than RP. The ability of ICPG to generalize on larger graphs compared to RP on the OGB dataset is a good result, many GNN based algorithms fail to generalize on large graphs.\n\nA small comment on presentation - the x-axis in Figure 2 is not very readable.\n\nIn Section 4.4, the authors show that ICPG can indeed generalized to unseen graphs. This is a novel contribution. In Section 4.3, while the performance of ICPG drops faster than UGS, this is expected since UGS is not designed to generalize to unseen graphs. It is impressive that ICPG beats UGS while being able to generalize to unseen graphs.\n\nFigure 7 is a good visualization of the kind of pruning the method is performing.\n\nUPDATE: I acknowledge that I have read the author's response and maintain my score.\n", "summary_of_the_paper": "The authors introduce ICPG, a novel method for pruning in graph and node classification tasks. The technique achieves good accuracy and is able to generate sparse graphs. Further, unlike previous work, the method is able to generalize to unseen graphs.", "summary_of_the_review": "The authors introduce a novel way to prune graphs graph and node classification tasks which can generalize to unseen graphs. They evaluate the method on an extensive number of tasks. The method shows good performance.\n\nSince there is no equivalent technique to compare against, the authors compare against random pruning which is probably a very weak baseline.", "strength_and_weaknesses": "", "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": "IrkBgzsJia", "reviewer": "Reviewer_4F4b", "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": "It is very important to extend the concept of methodologies for the transductive setting to that of the inductive setting in GNNs.\n\nThis work, ICPG, has significant meaning on this point but it is also true that it seems like the simple extended (or improved) version of UGS.\n\nExplicitly, the most novel component of this framework is the AutoMasker (and also co-training strategy is a key idea as well, but there are a lot of co-training frameworks for GNNs).\n\nAutoMasker has a simple architecture (GNN-MLP) and provides the importance scores of edges like EdgePool [1].\n\nEven though the authors described several conceptual advantages over UGS, I wonder if there is a better design than this (do you have several candidates for it?).\n\n[1] Edge contraction pooling for graph neural networks, F Diehl", "summary_of_the_paper": "In this work, the authors propose an iterative co-pruning framework using a lottery ticket learning for GNNs. \n\nGraph lottery ticket learning implies that a sparse subnetwork exists in a dense and randomly initialized network for both GNNs and graph data.\n\nUGS was proposed by Chen et al. to apply the lottery ticket learning to GNNs.\n\nThe basic concept is quite similar but it is distinguished from Chen et al. in that it can be applied for the inductive setting.\n\nIn Inductive Co-Pruning of GNNs (ICPG), edges of input graphs and model parameters are pruned according to the importance scores for each.\n\nThe authors exploit generative probabilistic models named AutoMasker to specify the importance of each edge and then configure core subgraphs.\n\nCompared to the previous Graph Lottery Ticket (GLT) model, ICPG has a nice generalization ability for both node classification and graph classification.", "summary_of_the_review": "I couldn't find an issue to reject this paper but it is difficult to evaluate novelty enough.\nTo be honest, it is quite simple so there is not much to comment on but at the same time, the contribution is clear.\nI want to make a decision after discussing it with other reviewers or reading other points that I might miss.", "strength_and_weaknesses": "", "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": "1UpIsj4DH-b", "reviewer": "Reviewer_HhcH", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The paper aims to solve an important real-life problem - that of pruning inductive graphs. The idea in the algorithm is pretty simple - 1) learn a mask for edges using the features of the nodes connected by the nodes, and 2) apply a gnn to the graph modified using the mask in step 1.\n\nI did not find any insights that generalize from the paper. The proposed method is one way to perform pruning a graph and generating a GLT, but there could be several ways. The experiments also compare the method to random pruning alone, which is a weak baseline. For instance, it would be really interesting to see how the inductive properties of the graph help, which can be done by comparing the performance to the transductive pruning algorithm.\n\nHere are some of my other questions and concerns.\n- The authors use the term 'generative probabilitistic model' in the abstract to generate importance scores. Is this referring to the sigmoid and MLP in equation (4)? This is a discriminative model, and I do not see what is generative about it.\n- The authors criticize UGS for independently pruning edges (in the experiments), and also for simultaneously pruning the graph and weights (in point 3 in the introduction). This seems contradictory. Pruning edges independently has the benefit of being robust to unsatisfactory edge masks (which is listed as the shortcoming of simultaneous pruning).\n- One of the claimed advantages of the mask is that it takes the global graph into account and is not independent for every edge. Eqn 4 however only takes the incident node features into account. While this is global because the MLP is trained for all the edges, it does ignore the neighborhood of an edge in deciding whether to mask it or not. For example, if a graph has random / useless node features but useful neighborhood structure, the mask should utilize this information.\n- What does it mean when s_G[i,j] is high for an edge that did not originally exist? It seems incorrect to ignore the high value s_G[i,j] for such edges - for example this may be telling us about a missing edge.\n- The term extreme sparsity is not defined. This makes it difficult to follow the experiments section.\n- Please compare to stronger baselines than random pruning. For instance, how do transductive pruning algorithms perform?\n\nSome minor comments:\n- The notation G' = (mG \\hadamard A, X) is used in Sec 3.1. Wouldn't the features X be affected as well by mG?\n- The last sentence in Obs.1 does not make sense.", "summary_of_the_paper": "This paper proposes a method to perform pruning of graph neural networks. The novelty of the paper is that the method works for inductive graphs, and thus can generalize to unseen graphs. By virtue of the masks being inductive, they also have the potential to take the global graph into consideration and not apply locally on each edge.", "summary_of_the_review": "Overall, I feel that the paper identifies an important problem, but the solution proposed and experiments are not thorough. The algorithm can be refined by incorporating neighborhood information in the mask generation process. The empirical performance can be vetted by comparing with existing pruning baselines.", "strength_and_weaknesses": "", "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": {}}]

Author rebuttal:

Meta-review: This paper studies the pruning problem of graph neural networks, i.e. finding lottery tickets for GNN. In particular, it generalizes UGS by Chen et al. (2021) from transductive setting to inductive setting where prediction on unseen graphs is possible. The main idea is: 1) learn a mask network to assign importance scores for edges using the embedding features of the nodes connected, that avoids the double parameter memory costs in UGS; 2) prune the edges according to the importance score and weights of GCN according to their magnitudes. Main concerns from reviewers are about the novelty, evaluation, and scalability. Despite that generalization to unseen graphs using the mask functions on embedding features is a new aspect, the evaluation is compared with relatively weak baselines and inference time scalability of is still an issue.
Decision: Reject