Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies GNNs' explainability from the perspective of graph information bottleneck (GIB). The authors first provide justification on why most existing methods are essentially studying the tradeoff between attribution and selection by modeling them as GIB questions. Based on this observation, the authors discuss the relationship between regularizing the selection in sparsity, stochastic attention and out-of-distribution (OOD) issue, and propose the SRS and ORS scheme. Experimental results demonstrate that the proposed SRS and ORS improves the fidelity and accuracy of the proposed method.
strength_and_weaknesses: Strengths:
- I like the idea of unifying most existing methods with GIB.
- There are discussions for the relationships between GIBE and sparsity, stochastic attention mechanism and OOD. 
- Experimental results demonstrate the efficacy of the proposed techniques.

Concerns:
- In section 1, is it possible to better explain why the rank is better than L1 norm? A low-rank matrix is not necessarily sparse, but L1 norm can help control the size of the graph (#edges).
- Regarding GIB, how do Eq. (1) ensure the sparsity of subgraph? And how do we define the subgraph are sparse enough? Moreover, for some motif structure, it might not be sparse but is very important in determining specific properties of the graph (e.g., the hydroxide group -OH in some molecular graphs). In this case, should we consider such motifs if we want the explanatory subgraph to be sparse?
- Current definition 2 is not self-contained. It is better to explain what $G*$ is in the definition.
- A similar definition of GIBE is presented in Theorem 4.1 in (Miao et al. 2022). It would be great to discuss the similarity and difference with that formulation. 
- I think some contents in section 3 (or maybe previous sections) needs adjustment. This is actually a key section to show that most existing methods fall into this GIB-type formulation and to explain the regularization between attribution and selection. This key connection is somehow not clear in previous sections. I get the key idea of this paper until I finished reading section 3.
- It is better not to use gap1 and gap2 in the main body, as this is specific to Figure 1 and will confuse readers.
- I didn't fully understand the purpose of Q in Eq. (4). Analytically, why do the introduction of variational approximation Q make it constant while original marginal distribution P is not?
- Most contents in section 3, section 4.1 and section 4.2 are already studied in (Miao et al. 2022). It is better to spend more efforts in highlighting the contributions by the authors.
- In addition to quantitative analysis on the proposed method, I am more interested in qualitative analysis like case studies. This is related to one last long-standing question of myself: We say explainability helps understand the behavior of black-box models. But why can we trust the explanations generated by another black-box model(s)? How should we trust this black-box explanation generator?
clarity,_quality,_novelty_and_reproducibility: The writing is overall clear. The authors make use of the figures to help illustrate the key ideas. In terms of technical novelty, the authors could better highlight their own contributions. Some contents in the current version are overlapped with existing works. 
summary_of_the_review: The paper is interesting overall. It tries to explain the inherent regularization between attribution and selection for most existing works with the GIBE formulation. With the GIBE formulation, the authors discuss its relationships to sparsity, stochasticity and OOD. The technical contributions could be better highlighted in the literature. And some qualitative analysis would be helpful in understanding the superiority of the proposed method in real world scenarios.
review_title: null

final_score: rating: 1: strong reject
review_content: summary_of_the_paper: This paper aims to investigate the role of regularization used in existing GNN explainers. The paper analyzes the interpretable GNN model proposed by Miao et al. 2022 by rewriting the training objective function and mapping it into two parts, the feature attribution objective and the feature selection objective. And the authors claim to derive some findings about the "regularization" in this rewritten objective.
strength_and_weaknesses: Strength: The topic of this paper, theoretical understanding of GNN explainers, is an important research direction.


Weaknesses:

1) The writing of this paper needs to be largely improved. Many essential concepts are not well-defined in the main paper or the appendix. For example, what are the distribution assumptions on the graph data? In section 3.2, "Treating target GNN f' as the proxy function ...", what is f'? What is the formal definition of "regularization" in GIBE? The technical content is almost unreadable due to missing definitions.


2) The paper claims to provide an understanding of the role of regularization for existing GNN explainers. However, the analysis is specific to a particular type of GNN (proposed by Miao et al. 2022) that has a certain interpretable mechanism. It is unclear how the analysis can be transferred to the more commonly used post-hoc explanation methods that can be applied to different types of GNNs.

3) Many typos. For example, 

- right before section 3.2, "... of Equation 2 can be proved to equal to ...": to be equal to. 
- Many ":" should be replaced by ",", e.g., "... employing Data Processing Inequality (DPI) along the Markov chain**:** ...". 
- Proposition 2, "let K_i and K_j is the ...": let K_i and K_j be the ...


clarity,_quality,_novelty_and_reproducibility: As commented above, the clarity of this paper needs to be largely improved. It is difficult to assess the technical soundness due to the lack of clarity. As far as I can tell, the analysis seems to be limited to a specific GNN and cannot be applied to the common post-hoc GNN explainers, which limits the significance of the contribution. 
summary_of_the_review: Given the lack of clarity and the limited scope of analysis, I'm inclined to reject this paper as the problems are unlikely to be addressed during the author response period.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper investigates the role of regularization in the explainability of GNNs. They find that regularization pursues a balance between feature attribution and selection as well as that optimal regularization is related to the sparsity of the explanations.
strength_and_weaknesses: Strength
======

- The paper introduces GIBE, which is similar to GIB but for GNNs explainability.  To my understanding, this is novel.
- The authors do a good job at discussing the related literature and putting their work into perspective.

Weakness
========

- Figures 4 and 5 could definitely be improved by using different line formats and markers to facilitate the task of distinguishing the results.
- Overall, the proposed methodology in the paper is not easy to digest. In particular, I'm confused about the exact implementation/derivation of the proposed SRS method. Could you elaborate more on the rationale behind it? Is it just a grid search on $\eta$ and then scaling $\mathbf{K}$ by the best $\eta$?

Questions
========

- What is the role of $\alpha$ in Eq (2) given that its optimal solution is independent of it?
clarity,_quality,_novelty_and_reproducibility: The paper is novel to the extent that GIBE is an extension of GIB for explanability of GNNs. However, the manuscript could be significantly improved when it comes to clarity, as for example, the follow up to the proposed Propositions are not as clearly discussed by the authors (see e.g., my question on SRS).
summary_of_the_review: Overall it's a promising paper, but the clarity/justification of the proposed methodology could be improved.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper studies the role of regularization in explaining GNNs through the lens of information theory.  The reviewers agree that the paper addresses an important topic by integrating and shedding light on current explanation methods. However, one reviewer made some compelling arguments about the paper's lacking rigor in several places. For instance, the reviewer identified ambiguities in the definition of certain mathematical formalisms in the paper. The reviewer, after being encouraged to be more specific, provided in my opinion strong evidence that the paper is not ready for publication. Given that the other reviewers gave borderline scores, my recommendation is that this paper should be rejected. The authors should, however, feel encouraged to continue this line of work and improve the paper. 
justification_for_why_not_higher_score: One reviewer provided compelling reasons why the paper lacks clarity in the more formal parts.
Decision: Reject