Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: the paper has provided an explainable GNN framework using differentiable graph discovery algorithm. To me more specific, it utilize the solution over spanning trees greedy approximation and the explainer GNN is able to provide the influential node/edges. The experimental results has demonstrated the effectiveness of the proposed framework.

 The idea of the model is quite neat and artful designed and it is also intuitive formulate as ILP problem. However, I do have some concerns as follows:

1) In terms of the explainable GNN, I doubt the presenting systematic explanation of the graph model is explainable. It lacks of the details of perspective of explainability/interpretability definition over in either quantitative manner or qualitative way(e.g. user study/case study in downstream task). It could be still regarded as an open problem in AI transparency and I'm not criticizing this paper has not provided the corresponding merits. However, explaining the graph models leveraging as node/edge selections probably not uniform solution but a neat idea.

2) The paper also mentions the work provided by GNNExplainer, it would be more confident to believe your proposed method is optimal if considering the GNNExplainer as baseline. More importantly, it would be essential to reason why your proposed framework is better in terms of explainability.
review_title: neat idea, trustworthy results

final_score: rating: 4: Ok but not good enough - rejection
review_content: Summary:
This paper proposes a framework to discover graph-algorithms that are learned by neural networks to solve combinatorial optimization problems. To this end, the authors propose (a) augmenting the input of DNN-solver using features extracted by existing combinatorial algorithms and (b) explaining the DNN based on an additional "explainer" model trained based on maximizing the lower bound of mutual information between subgraph of the input and the labels predicted by the DNN solver. I think this paper pursues an important and promising direction to extract algorithms from DNN-based solvers. However, I think (a) additional baselines should be incorporated for evaluating the DNN-solver, (b) the proposed explainer does not generate practically useful outputs for discovering new algorithms, and (c) the proposed explainer seems a bit flawed.

Strength:
- The proposed augmentation scheme gives interesting insights and can be applied to other DNN-based solvers for combinatorial optimization.
- This paper tackles an interesting problem of discovering new algorithms from DNN-based solvers for combinatorial optimization.

Weakness:
- It is not clear why the authors only consider baselines with polynomial-time running time. To show that the proposed DNN-based solver is practically useful, the authors should compare with state-of-the-art solvers (both DNN-based and non-DNN-based) under limited running time. To compare the algorithms based on the tradeoff between complexity and approximation ratio, the authors should provide a theoretical analysis of the approximation ratio of the proposed algorithm.
- It is not clear how to use the proposed algorithm for discovering new graph algorithms. Especially, the algorithms produce results that are not very "explainable." For example, how did the authors use the explainer to "re-discover the node-degree greedy algorithm?" The proposed framework seems to assume that humans can easily analyze the provided explanations (i.e., graphs with colored nodes). However, it seems hard for me to analyze the pattern in node-degree of nodes just by glancing at several explanations provided by the proposed framework. Such a process becomes especially harder if we aim to discover algorithms based on novel concepts (instead of node-degree). Even more, researchers are usually interested in developing algorithms for large-scale graphs (where exact solutions are intractable), yet the explanation becomes notoriously hard to analyze in the eyes of humans for this case. The authors are encouraged to provide an actual process of extracting analysis on the explanations, e.g., did they (1) look at hundreds of explanations provided by the explainer, (2) intuitively group explanations with the common pattern in node-degree, and (3) infer a greedy pattern in node-degree of the selected nodes?
- The proposed explainer seems flawed for explaining the DNN-based solver. Namely, the proposed explainer only accesses the DNN-based solver based on its prediction probability. However, I do not think it makes sense to rely only on the prediction to explain the black-box algorithm. To demonstrate, both the brute force search and integer programming solver will give an identical prediction (i.e., optimal solution) for the combinatorial optimization. Applying the proposed explainer to two algorithms would give an identical explanation, but brute force search and integer programming operate in a very different way. 

---

I appreciate the thoughtful rebuttal provided by the authors. My main concerns are on Q2, i.e., the practical usefulness of the algorithm. I do think that the authors provide a convincing argument on "we can only understand what we can understand," hence we should set up a hypothesis and see if it aligns with the explanation. However, I think the usefulness is not well-supported in the current state of the paper. The authors can come up with (a) a stronger example of such a hypothesis and (b) a better measurement of how the hypothesis aligns with the explanation to strengthen the paper. 

Regarding Q3, I still think that it is not correct to provide the same explanation for different algorithms when they produce the same output. Hence, the proposed algorithm should be modified to consider this aspect. 

review_title: Novel approach to explain DNN-based graph algorithms, but experiments can be improved and the explainer model seems flawed.

final_score: rating: 7: Good paper, accept
review_content: In this paper, the authors proposed a framework for differentiable graph algorithm discovery (DAD). The framework is developed by improving two the discovery processes, i.e., designing a larger search space, and an effective explainer model. To enlarge the search space, the proposed DAD augments GNNs with cheap global graph features, which consist of solutions on the spanning trees of the original graph, and approximate solutions of greedy algorithms. All the features are concatenated together as input to GNNs. Experiments indicate that the proposed DAD is better than the approximate solutions. The explainer model is developed to explain the learned GNN, by employing the learning to explain (L2X) framework in (Chen et al., 2018). In general, the paper is well-written, and the method is interesting.

Some questions and comments:

1.  Although the authors have provided an ablation study to verify the contributions of tree solution versus greedy solution in Figure 11 in appendix, it is still not very clear about the impact of the global features on the model. The ablation study is short and lacks detailed discussions. In Figure 11, what is "raw" model? The global features are concatenated to the input, which actually increases the dimension of features. It would be necessary to see whether the global information or the extra degrees of freedom improve the performance.  

2. How to determine how many spanning tree solutions or greedy solutions is enough for performance improvement? The authors said that "We tuned the hyperparameters of GNN models for each graph category, such as the number of layers and the number of spanning trees, using grid search. " It sounds like the proposed model is hard to generalize to different datasets.

3. The novelty of the explainer model is not very clear. It seems that the authors just applied the learning to explain (L2X) framework in (Chen et al., 2018) to the GNN settings.

4. There many typos, e.g., 
(1) In page 4, "treat the l constraints seperately for efficient computations",    --->  separately 
(2) In page 5, above Eq.(11), "is irrelavent to nodes of distrance larger than T"   --> irrelevant, distance
(3) In page 5, "is defined to be the origianl GNN"   --> original
(4) In page 6, "add a global read-out functionto"   --> function


I have read the authors' response, and I would like to keep my current rating.




review_title: The paper is well presented with detailed motivations and analysis, but has weakness in experiments

Meta-review: This paper proposes a method for automatically discovering graph algorithms using GNNs. In general, the reviewers find the paper well-written, and the problem and the approach interesting.  However, there is a concern on the practical usefulness of proposed method as shown in the following comments:  “My main concerns are on Q2, i.e., the practical usefulness of the algorithm”[R1]; “It sounds like the proposed model is hard to generalize to different datasets” [R3]; “The proposed explainer does not generate practically useful outputs for discovering new algorithms”[R4]. 
Decision: Reject