Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors propose to use GFlowNet in a new application, explainability for GNNs. To me, this is a resemble application for GFlowNet, though, I'm not that much familiar with the explainability problem of GNNs. Intuitively, GFLowNet is able to generate subgraphs based on learning multiple trajectories which maximize a specific reward. In this paper, the authors use MI as the reward which seems to be consistent with the previous models in this domain. 

The paper is fairly well-structured and easy to follow. The most of methodological part of the paper is repeating the first GFLowNet paper. My main concern with this paper is that the authors use "flow matching condition" that has known issues. So, it raised some questions regarding some of the qualitative results. 


strength_and_weaknesses: **Pros:**

- Applying GFlowNet in a new domain, i.e. GNNs.

**Cons:**

- Based on the loss in eq. 18, the authors only use the naive "flow matching condition" which is underspecified and tends to have biased to smaller trajectories. Besides that, it is computationally very inefficient. These are already known and new methods have been proposed. 

- This also raises a question about the quantitative results. To me, it is not clear if the shown results in Figure 3 which show a smaller sub-graph for the proposed method are due to these biases or if it is really beneficial from GFlowNet. I would rather like to see the results for the "trajectory balance" based loss. 

- I'm also not sure how much gain they could get from the efficient parent state explorations. An ablation study around it would be gratefully appreciated. I think a naive solution still should not be that complicated.  

- Evaluation metrics are not enough. I would like to see comparisons in terms of Fidelity and Sparsity as well. 

- I also believe some of the baselines are missed. 


clarity,_quality,_novelty_and_reproducibility: The paper is well written. The paper is not novel from a theoretical perspective but is a use case of GFlowNet in a new domain, i.e. explainability for GNNs. 

As I'm not that familiar with the explainability of GNNs, it is hard for me to say that much regarding related works and experiments. But I felt  the paper missed a few recent works in this domain and evaluation metrics are not complete. 
summary_of_the_review: The paper seems to be a good application paper, however, it needs some modification in terms of the loss as well as experiments.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a novel strategy to obtain a connected subgraph as the interpretation of node classification and graph classification tasks. The proposed strategy starts from a state with only one node and learns a policy to achieve state transition via sampling new nodes and adding them to the current state. In general, the techniques used in this paper are novel under the topic of GNN interpretation, which reveals further insights on how to understand in what ways GNN predictions are made. However, there are also clear disadvantages in this paper. See the Summary of The Review for more details.
strength_and_weaknesses: Strength:

(1) This paper is solid in techniques: definitions are clearly presented, and proofs are also provided in the appendix.

(2) A novel approach is proposed borrowing the idea of generative flow networks to obtain subgraphs as interpretations for GNNs, which could reveal novel insights under this research topic.

(3) The empirical performance superiority on most datasets seems to be promising.

Weaknesses:

(1) The motivation of this paper is unclear: why do we need this model considering the existing GNN interpretation approaches? The presented motivations are not convincing – see Summary of The Review for more details.

(2) There are certain phenomena not clarified in the experiments – see Summary of The Review for more details.

(3) Only one real-world dataset is involved in the experiments performed in this paper.

(4) The writing of this paper needs to be further polished. I did notice some typos, such as “GFlowExplainer does not pre-training process”.

clarity,_quality,_novelty_and_reproducibility: Clarity: This paper does not provide a clear motivation for the proposed strategy; besides, how the proposed strategy avoids the disadvantages of previous works mentioned in the introduction should be further elaborated.

Quality: The adopted techniques are sound in this paper, but the organization of this paper can be further improved – see Summary of The Review for more details.

Novelty: This paper is novel in techniques under the topic of GNN interpretation.

Reproducibility: Most of the codes are provided. All datasets are open source.

summary_of_the_review: This paper proposes a strategy inheriting the idea of Generative Flow Networks to generate subgraphs as interpretations for GNN predictions, which is novel in techniques. Meanwhile, the theorems and lemmas are supported with detailed proofs. However, there are multiple unaddressed questions that prevent this paper from being well-prepared for publication. For example, the author mentioned that the primary motivation of this paper is: (1) searching subgraphs is a combinatorial problem, and it is hard to solve; and (2) previous works model the selection of subgraphs as a sequence generation problem, which is not beneficial. However, first, most GNN interpretation works based on learning do not require solving any combinatorial problem (e.g., [1]); second, we may also regard the proposed approach in this paper based on state transitioning as a strategy based on sequence generation. I thus believe the motivations above deserve a more rigorous justification. Moreover, there is no detailed discussion on how to choose an appropriate stopping criterion. Should all generated subgraphs reach the constraint of size K_M? Will there be cases where the size of the underlying interpretation subgraph is different from each other? If they exist, how could we design an appropriate stopping criterion that fits all scenarios? 

Finally, I would still have extra concerns as follows.

(1) There is a policy network in Fig. 1, while this notion is never mentioned elsewhere in this paper.

(2) The reported AUC seems to be much worse compared with the reported accuracy in the vanilla papers of baselines (e.g., [1]). Will it be more comprehensive to compare both AUC and accuracy?

(3) There is no evidence showing that the exhibited superiority is (partially) because the proposed strategy does not generate subgraphs in a sequential manner.

(4) Will it be better to introduce the definitions in Section 3.3 before these notions are referred to?

(5) Is there any specific reason for the unique performance inferiority on BA-Community datasets compared with the baselines?

(6) Is it possible to include more than one real-world dataset for more comprehensive experiments?

[1] Rex Ying et al. Gnnexplainer: Generating explanations for graph neural networks. NeurIPS 2019.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposed a method to explain the GNN using a newly proposed tool graph flow network(GFlowNets). This framework enables the model to connect the trajectories of the same graph even with different node sequences. The paper also proposed an efficient cut vertex criteria to speed up the whole process. Compared with traditional Tarjan methods, the proposed algorithm is much more efficient. Also, the experiment part shows that the result outperforms some other baselines.
strength_and_weaknesses: The authors proposed a new framework based on GFlowNet. This network is more explainable since it's based on the conditional state flow network. The whole network is trained to minimize the discrepancy between the sum of the outgoing flow and the final reward and incoming flow. This framework is intuitive and novel. The authors also proposed an efficient algorithm to speed up the parent state exploration process. 

For the weaknesses, I have some concerns regarding the experiment part and the design of the loss function.

Just like the authors claimed, the reward doesn't contain the sparsity or consistency part, which can be important in the GNN explainer model.

Secondly, I'm a little confused since the performance shown in the paper is somehow different from the ones in the PGExplainer. Like the BA-community/Tree-cycles/BA-2motifs, there is a huge gap. Could the authors explain why? I found the performance from the arxiv version here. https://arxiv.org/pdf/2011.04573v1.pdf . Meanwhile, they are some other state-of-the-art baselines that are not compared in the paper, like IB-SUBGRAPH, GraphMask, DIR(Discovering invariant rationales for graph neural networks).  

I also have a question regarding the GFlowNet, since it is somehow related to reinforcement learning, I wonder if the model is robust. Or do we need to carefully tune the model to make it work?



clarity,_quality,_novelty_and_reproducibility: The paper is easy to follow, although the readers may need some background knowledge of GFlowNet to have a better understanding. The proposed algorithm provides an efficient method to find the parent state, which is easy to reimplement and can be easily extended to other scenarios. For the novelty, I'm a little concerned since the GFlowNet is borrowed from others' work. For the proposed algorithm, I'm also not sure whether it's novel enough.
summary_of_the_review: This paper provides a new perspective for graph explainers. The paper also proposed an easy but efficient algorithm to find the parent state. My main concern is the gap in performance. Another concern is the novelty.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors apply GFlowNets to the problem of scheduling operations in a computational graph on homogeneous parallel hardware. The evaluate conditional GFlowNets for the first time(?) with the computational graph being the conditioning input and the schedule being the output. They also innovate by conditioning on the reward temperature in order to find a good trade-off between diversity of the generated samples and their average reward. Diversity is important in this application because the generative policy is trained using an imperfect but cheap to compute proxy and only a few of the generated schedules are then evaluated on the ground truth hardware. GFlowNets are interesting in this context because their training objective makes them sample with probability proportional to the reward (rather than maximizing the reward as in other RL approaches). Experiments show improvements against previous methods, including standard RL methods.
strength_and_weaknesses: GFlowNets are a new RL variant (less than a year old) with only a few applications yet, so this paper introduces a new type of application, in the realm of scheduling, and an approach which may be applicable more broadly. The successfully show empirical success on two GFlowNet novelties: conditioning on a rich input (the computational graph) and on temperature (to control the diversity-reward trade-off).

In page 5, they claim that previous works on GFlowNets did not consider the conditional case, but this is not true and they themselves mention in section 4 that Bengio et al 2021b introduced the theoretical framework for conditional GFlowNets. What is true is that may be the first (or among the first, with concurrent work) to validate experimentally this framework and show its usefulness.
clarity,_quality,_novelty_and_reproducibility: The paper is clearly written, of good quality. Novelty is mostly in the form of experiments and a new application domain for a fairly new method (introduced at NeurIPS 2021). 
summary_of_the_review: This paper introduced a new form of application for GFlowNets, mapping a computational graph to a distribution over efficient schedules for it. To achieve this, the demonstrate the feasibility and success of the conditional GFlowNet formalism and also show how to use it to control the trade-off between diversity and average reward by conditioning on the reward temperature (exponent of the reward).
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This work proposes to use GFlowNets to propel GNN explainability. Both topics are very interesting and timely, and after a round of rebuttal discussions, all reviewers agree that the paper is worth accepting. I fully agree with them, and support this paper for acceptance.
justification_for_why_not_higher_score: While the paper ticks all the boxes for acceptance, I found that, as with any such emerging proposal, there are questions raised over whether the generative approach is really the best way towards achieving GNN explainability. This is reflected in the reviewers' initial comments and, while the authors certainly handled the rebuttal adequately to secure acceptance, I find that this line of research would need more iterations of fine-tuning before it would be spotlight-worthy. I hope the advice and ponderings provided by the reviewers, as well as the comments the work will receive at ICLR, can aid the authors on this quest going forward!
justification_for_why_not_lower_score: There is a clear consensus between the reviewers, and the work is interesting to a broad ICLR audience.
Decision: Accept: poster