Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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. 


 
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?

2) 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. 

3) 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. 

4) 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.

summary_of_the_review: I have concerns about novelty, scalability, and practical use case of the proposed method.  

------ after reading the rebuttal

Thanks 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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
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.

ICPG 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.

A small comment on presentation - the x-axis in Figure 2 is not very readable.

In 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.

Figure 7 is a good visualization of the kind of pruning the method is performing.

UPDATE: I acknowledge that I have read the author's response and maintain my score.

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.

Since there is no equivalent technique to compare against, the authors compare against random pruning which is probably a very weak baseline.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
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.

I 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.

Here are some of my other questions and concerns.
- 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.
- 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).
- 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.
- 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.
- The term extreme sparsity is not defined. This makes it difficult to follow the experiments section.
- Please compare to stronger baselines than random pruning. For instance, how do transductive pruning algorithms perform?

Some minor comments:
- The notation G' = (mG \hadamard A, X) is used in Sec 3.1. Wouldn't the features X be affected as well by mG?
- The last sentence in Obs.1 does not make sense.
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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this work, the authors propose an iterative co-pruning framework using a lottery ticket learning for GNNs. 

Graph lottery ticket learning implies that a sparse subnetwork exists in a dense and randomly initialized network for both GNNs and graph data.

UGS was proposed by Chen et al. to apply the lottery ticket learning to GNNs.

The basic concept is quite similar but it is distinguished from Chen et al. in that it can be applied for the inductive setting.

In Inductive Co-Pruning of GNNs (ICPG), edges of input graphs and model parameters are pruned according to the importance scores for each.

The authors exploit generative probabilistic models named AutoMasker to specify the importance of each edge and then configure core subgraphs.

Compared to the previous Graph Lottery Ticket (GLT) model, ICPG has a nice generalization ability for both node classification and graph classification.
main_review: It is very important to extend the concept of methodologies for the transductive setting to that of the inductive setting in GNNs.

This 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.

Explicitly, 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).

AutoMasker has a simple architecture (GNN-MLP) and provides the importance scores of edges like EdgePool [1].

Even 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?).

[1] Edge contraction pooling for graph neural networks, F Diehl
summary_of_the_review: I couldn't find an issue to reject this paper but it is difficult to evaluate novelty enough.
To be honest, it is quite simple so there is not much to comment on but at the same time, the contribution is clear.
I want to make a decision after discussing it with other reviewers or reading other points that I might miss.
review_title: null

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