Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
strength_and_weaknesses: Strongness
1. The paper is well-written, and the motivation is intuitive and clear.
2. 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.
3. Extensive experiments demonstrate the effectiveness of the framework in terms of sparsity improvement, scalability, and performance

Weakness:
1. 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.
2. 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.
clarity,_quality,_novelty_and_reproducibility: This paper is well-written and easy to follow. For novelty, the authors propose a novel DGLT framework for GNN network pruning and graph sparsification. For reproducibility, the authors should provide source code to help better understand the proposed model.
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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
strength_and_weaknesses: **Strength**
- The dual lottery ticket hypothesis is firstly studied on graph lottery ticket.
- The graph pooling technique is introduced to replace the sampling-based graph sparsification.
- Extensive experiments are conducted for multiple applications.

**Weaknesses**
- Important details about the training loss are not provided, especially when the dimension of the sparsified graph is changed by pooling operations.
- Some claims made by the paper are not well justified, e.g. better explainability, pooling is better than sampling-based algorithms.
- The theoretical analysis of the proposed method is not clear enough.

clarity,_quality,_novelty_and_reproducibility: The clarity and quality of the paper presentation is generally satisfactory, and can be improved by providing more details/justifications about the questions I raised in the summary. The novelty and technical contribution is limited, as the dual lottery ticket hypothesis and pooling-based sparsification are not newly proposed in this work, but it is still good to find that such a combination provides empirical improvement. The codes have been included for reproducibility.
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. 

=== Method ===

1. 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. 
2. 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$?

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

4. The claim of better explainability is not demonstrated. It usually has a specific meaning of providing explanations to the model predictions.  

5. Is $G_{sub}$ the same as $G_{hgs}$?

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

=== Experiment ===

7. What is the definition of weight sparsity and graph sparsity in the experiment?

8. How sensitive is the method to the pooling-related hyperparameters, e.g. $n_{l}$?

=== Typos ===

There are also some typos. To name a few:
- In the paragraph after Eq. (2), “assignment matrix S^{(l)}... can projecting coarsened subgraph xxx” -> “Assignment … can project …”
- Duplicate “and” in the paragraph before Lemma 1.
- “a admirable” -> “an admirable” in the paragraph before Lemma 1.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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.
strength_and_weaknesses: **Strengths:**
* 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.

* Detailed empirical analysis, studying different aspects of the methodology.

**Weaknesses:**
* 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.

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

clarity,_quality,_novelty_and_reproducibility: Overall, the paper is well-written and most of the different concepts are clearly presented. At the same time, the paper keeps a good balance between theoretical contributions and empirical evaluation. Regarding the methodology, I believe the paper makes a novel contribution to the field.
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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
strength_and_weaknesses: Strength:
* 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.
* The design of hierarchical graph sparsification makes it possible to perform graph classification tasks.

Weakness:
* 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.
* 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. 
* 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.
* 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. 

[1] Dual Lottery Ticket Hypothesis, ICLR 2022


clarity,_quality,_novelty_and_reproducibility: The motivation and organization are clear but lack some technique detail. Adding more graph property related designs would be better to improve the novelty.
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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
strength_and_weaknesses: Strengths:
1.	As 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. 
2.	Empirical study is clean and shows promising results on some datasets.
3.	This paper is well-written with a nice presentation. Many sections are easy to follow.

Weaknesses:
1.	As 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.
2.	If my understanding above is true, the authors are also encouraged to compare their method with standard compression-based methods.
3.	As 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?

Minor concerns:
1.	All 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.
2.	Since 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.
3.	Missing references to some (potentially) very related paper: Inductive Lottery Ticket Learning for Graph Neural Networks, 2022.

clarity,_quality,_novelty_and_reproducibility: In general, this paper looks novel to me (with the first attempt to apply DLTH onto graphs and GNNs), with good clarity and a nice presentation. I found this paper interesting but not that exciting, mainly because of the way the graph lottery ticket is obtained (please refer to my first weaknesses). Some other concerns are over the experimental settings and results. 
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.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: 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. While initially concerns were raised regarding the vague theoretical analysis, unclear training details, and complexity, the authors provide a profound rebuttal that seems to address all reviewers to satisfaction. This paper hence receives a unanimously positive consensus from all reviewers, and AC joins them.

There is a known clarity issue that the authors must immediately fix:  please add a citation to accrediting Wang et al. (2020a) in the part A of the Appendix. The authors should also make more clear that their theory derivations in this part were also inherited from Wang et al. (2020a) - perhaps in order to make the paper more self-contained -  and isn't an independent contribution. This issue was raised and thoroughly investigated during the meta-review process. It is deemed that, since Wang et al. (2020a) was already cited and adequately accredited in the main text on borrowing the GIR regularizer, the credit of prior work was clearly conveyed to reviewers and no confusion was caused. However, Appendix part A should have more strictly followed the citation specification to explicitly indicate the source of the proof idea. The authors are strongly urged to address this concern in their final version.
justification_for_why_not_higher_score: Both dual LTH and graph LTH were studied before, so this work could be viewed as incremental 
justification_for_why_not_lower_score: The authors achieve a triple-win situation of graph lottery tickets with high sparsity, nice performance, and good explainability - which is new. Theory insights, thought not treated particularly as main novel contributions, are offered too
Decision: Accept: poster