acceptodds
Under review as a conference paper at ICLR 2027

BottleneckMLP: Graph Explanation via Implicit Information Bottleneck

Abstract

The success of Graph Neural Networks (GNNs) in modeling unstructured data has heightened the demand for explainable AI (XAI) methods that provide transparent, interpretable rationales for their predictions. A prominent line of work leverages the Information Bottleneck (IB) principle, which frames explanation as optimizing for representations that maximize predictive information while minimizing input dependence . We show that explicit IB-based losses in GNN explainers provide little benefit beyond standard training. We show that the variational objectives used by existing explainers are invariant to the joint structure of the selected subgraph, and that the module's importance-scaled noise provably reduces input dependence while bounding predictive leakage. To address this, we propose BottleneckMLP, a model-agnostic module inserted between the GNN encoder and the explainer head consisting of an MLP compression block and a noise component. The compression block delivers an implicit information bottleneck, the first such two-phase IB dynamic observed in GNN representations, and replaces explicit variational IB losses without performance loss. By injecting Gaussian noise inversely scaled by node importance, BottleneckMLP yields embeddings where important nodes remain structured and clustered, while unimportant nodes drift toward Gaussianized, high-entropy distributions. This importance-scaled Gaussian noise component contributes a further 5-15% improvement in explanation fidelity (Fid+, Fid-), and accelerates convergence by 30-40% across datasets. Across 6+ ante-hoc and post-hoc explainers spanning graph and node classification, link prediction, subgraph recognition, and temporal graphs, BottleneckMLP recovers and exceeds existing baselines.

Primary area:
interpretability and explainable AI
Keywords:
Graph Neural Networks, Explainability, Information Bottleneck, Mutual Information, Representation Learning

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_KFVeOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper investigates the limitations of explicit Information Bottleneck (IB) objectives in GNN explainers and proposes BottleneckMLP, a lightweight module combining MLP-based compression with importance-aware Gaussian noise. The authors theoretically characterize the gap between variational IB surrogates and their intended information objectives, and empirically demonstrate improvements across multiple explainers and graph learning tasks.

Critical strengths
  1. The analysis of explicit IB objectives, particularly the decomposition involving total correlation and marginal mismatch, provides valuable insights into the limitations of existing regularization approaches.

  2. BottleneckMLP can be integrated into different GNN explanation frameworks with relatively limited architectural modifications.

  3. The experiments cover multiple explainers, datasets, and tasks, with additional analyses of representation dynamics, information compression, and component ablations.

Critical weaknesses
  1. The mutual information reduction guarantee assumes a fixed Gaussian noise channel, while the actual noise scale depends on input-dependent importance scores. The applicability of the theoretical result to the implemented mechanism is not fully established.

  2. The analysis primarily characterizes information compression in representations or selection masks, which does not directly guarantee faithful explanatory subgraphs.

  3. Although the overall improvements are encouraging, some configurations exhibit performance degradation, and the gains from MLP capacity versus importance-aware compression are not entirely disentangled.

Questions for authors
  1. Can the theoretical MI reduction guarantee be extended to input-dependent importance-scaled noise? How does the analysis of mask information relate to the information retained by the selected subgraph?

  2. Can the authors further clarify how representation compression translates into improved explanation faithfulness, beyond the observed empirical correlation?

  3. Are the pretrained prediction models kept frozen in all post-hoc experiments? Could the authors discuss the negative results on certain backbones and explainers?

4 comments
AuthorsOpenReview ↗

Response to Reviewer KFVe part 1 of 2

(Response to reviewer KFVe part 1/2)

We thank the reviewer for the careful reading and positive soundness assessment. We are glad the decomposition involving total correlation and marginal mismatch provided valuable insight, and that the module's ease of integration and the breadth of the analyses were recognized. We are particularly grateful for the identification of the input-dependent noise issue, which we agree is the most substantive technical concern raised on this submission and that we correct below. We have marked all updates in blue text within the manuscript.

W1/ Q1a. (Input-dependent importance-scaled noise)

The reviewer raises a good point that the theory assumes a fixed noise level, but ours depends on the input. The fix for this is minor. Theorem 1's proof treats the noise as independent of XX. One step uses h(Zi∣X)=d2log⁡(2πe ti)h(Z_i \mid X) = \tfrac{d}{2}\log(2\pi e\,t_i), which is valid only when tit_i is a constant. Ours is not because ti=σ/αit_i = \sigma/\alpha_i, and αi\alpha_i comes from the embeddings.

ZiZ_i now gives information about XX in two ways. It informs about the signal fi(X)f_i(X), which is intended, and it also informs of how noisy it is. A noisier ZiZ_i means the node had lower importance, and this is something which the theorem never accounted for. Conditioning separates the two. To make the necessary updates to the Theorem, we now fix α=a\alpha = a. Then every ti=σ/ait_i = \sigma/a_i is just a number, the noise is independent of XX again, and Theorem 1 applies unchanged. The chain rule splits the quantity to match:

I(X;Zunimp)=I(α;Zunimp)⏟leak via the noise level+I(X;Zunimp∣α)⏟Theorem 1 appliesI(X;Z_{\mathrm{unimp}}) = \underset{\text{leak via the noise level}}{\underbrace{I(\alpha;Z_{\mathrm{unimp}})}} + \underset{\text{Theorem 1 applies}}{\underbrace{I(X;Z_{\mathrm{unimp}}\mid\alpha)}}

The second term is the one Theorem 1 covers, derivative and strictness condition included. The first is the leak the reviewer identifies, and it is at most H(α)H(\alpha). Corollary 2 already has this shape, where H(M)H(M) is the cost of the mask revealing its own length. In this case H(α)H(\alpha) is the cost of the noise revealing its own scale. We have updated Theorem 1 accordingly, and have added the above discussion as the remark following the theorem. We have also updated the proof of Theorem 1 and added the conditioning to Lemma 1 and Proposition 2 (with no effect on their theoretical outcome or proof). There were no other downstream effects caused by this correction.

Q1b. (How mask information is related to information in the explanatory subgraph)

GsG_s is determined by (G,s^)(G, \hat{s}), so conditional on GG, these two carry the same information. s^\hat{s} is the quantity that the regularizer in GSAT bounds, and this is why we cover this in Proposition 1. We have added a paragraph to the beginning of Section 4 that explains each term and how we use it such that this is clear from the start. We have also added these three terms to Table 6 in Appendix A with our list of symbols and notations for clarity. This clearly distinguishes the selection mask, I(G;s^)I(G; \hat{s}), the embedding I(X;Z~)I(X; \tilde{Z}), and the explanatory subgraph I(G;Gs)I(G; G_s). We note that GsG_s is determined by (G,s^)(G, \hat{s}), so conditional on GG, the mask and the subgraph carry the same information, and s^\hat{s} is the quantity GSAT's regularizer actually bounds (as is stated in Proposition 1).

Theorem 1 claim 1 provides the exact derivative ∂I/∂ti=−mmse(1/ti∣Z−i)/2ti2\partial I/\partial t_i = -\mathrm{mmse}(1/t_i \mid Z_{-i})/2t_i^2, so I(X;Zunimp)I(X; Z_{unimp}) strictly decreases. This is not merely an upper bound. The part that is only a bound is the transfer to I(X;Gs)I(X; G_s) via the DPI. We have indirect empirical evidence that I(G;GS)I(G;G_S) does fall because the sparsity results (Appendix U) and the Fid$^+$ improvements both indicate more concentrated selections. We also see that the visualized explanatory subgraphs via BottleneckMLP are indeed the correctly identified ground truth motifs for BA-2Motifs and Mutag, and this is the exact mode where the bottleneck objectives are respectively optimized. We also have that Theorem 1 claim 3 propagates, since I(X;Z~unimp)→0I(X; \tilde Z_{\mathrm{unimp}}) \to 0 as min⁡iti→∞\min_i t_i \to \infty forces the unimportant nodes’ contribution to GSG_S to vanish, and this is a valid guarantee.

AuthorsOpenReview ↗

Response to Reviewer KFVe part 2 of 2

(Response to reviewer KFVe part 2/2)

W3 (Negative results and capacity versus importance-aware compression)

Concerning capacity, we would like to refer the reviewer to our parameter-matched controls in Appendix AA and AB. The noise component does not add any trainable parameters over the variant with the MLP-only, so the ablations hold the parameter capacity fixed while only varying the noise mechanism. The shuffled importance experiment shows that when the architecture, the parameter count, and the noise distribution are kept the same, and only the alignment between the noise and the importances was changed, we see the drop in accuracy and AUC-ROC performance.

Concerning the negative results, we have collected them in the table below. They do indeed give meaningful insights when taken together, and we appreciate the reviewer for encouraging this analysis. We have included the table and discussion in Appendix AE.

SettingMetric(s) affectedMagnitude
ProxyExplainerBA-2Motifs AUC; MUTAG AUC; Fluoride Carbonyl Fid-0.940-->0.779; 0.847-->0.822; 0.409 --> 0.633
GOAtBA-2Motifs Fid- (GCN and GIN); BA-2Motifs Fid+ (GCN)0.001 --> 0.056 / 0.070; 0.542 --> 0.509
V-InForMUTAG Mean Probability; BA3 Prob-N0.968-->0.712; -0.0003
DIRCausal accuracy; test MRRbelow original on all splits
PGExplainerTreeCycles AUC-0.3%
GNNExplainerall metricsinconclusive: all variants within 0.493--0.510
PNA backboneMUTAG explanation AUC0.993-->0.965

We have determined possible mechanisms that account for these negative results, and this relates to the discussion in Q1 of Reviewer NDFd connecting bottleneck width, noise scales, and convergence results.

  1. The ceiling effects where the baseline is already near-optimal. Proposition 2 caps the achievable separation at d2log⁡(αp/αq)\tfrac{d}{2}\log(\alpha_p/\alpha_q). Where the base explainer is already at or near that ceiling the noise does not offer benefit and may lead to some degradation. This covers GOAt on BA-2Motifs (baseline Fid$^-$ of 0.0010.001 is essentially perfect and cannot be improved), ProxyExplainer on BA-2Motifs (baseline AUC 0.9400.940), and PNA on MUTAG (baseline AUC 0.9930.993). We note the converse holds in the same table: GOAt-GIN on BA-2Motifs, where Fid$^+$ was not at ceiling, improves 0.573→0.9770.573 \to 0.977.

  2. Latent noise was already injected. ProxyExplainer generates proxy graphs with a Graph VAE and V-InFoR denoises through a variational latent, so both already inject noise before our module adds the noise component. The composite importance signal-to-noise ratio then falls to a level which is unproductive, as in (1.).

  3. Degenerate embedding geometry. Three of the failures above are on BA-2Motifs, which we find has only 327327 distinct embedding vectors across 25002500 test nodes because its node features are constant and embeddings are a deterministic function of local structure. A near-degenerate Cov(f(X))\mathrm{Cov}(f(X)) makes ρj=αλj/σ\rho_j = \alpha\lambda_j/\sigma ill-scaled at any fixed σ\sigma, and is also why the entropy-power lower bound of Proposition 2 is vacuous there.

  4. Objective mismatch, in the DIR case. DIR's invariance penalty is not a compression term, but rather, it enforces distributional invariance across environments, which our module does not provide. BottleneckMLP recovers what ablating that penalty loses, but it should not be expected to reproduce causal identification, and causal accuracy and test MRR are precisely the metrics that measure it. We interpret this more as a scope limit and not as a method negative result.

GNNExplainer is separate from all four because with every variant within 0.4930.493–0.5100.510 AUC, the setting does not discriminate between any methods and we draw no conclusion from it in either direction.

Q3 (Are the pretrained models frozen in the post-hoc experiments)

Thank you for pointing out that we did not mention this explicitly. We clarify that BottleneckMLP operates on the encoder’s embeddings, so in order for it to work in the post-hoc method pipeline, we need to retrain the base model. In these settings,(PGExplainer, GNNExplainer, ProxyExplainer, ReFine, V-InFoR), we retrain the classifier with the module in place and compare against the retrained baseline under identical settings. The comparison is matched, but it is not a post-hoc explanation of a fixed pretrained model in the strict sense. We would like to highlight that our method is mostly aimed at the ante-hoc setting, but we show that it operates well in the post-hoc setting as well for generalizability.

Thank you for the detailed rebuttal. I appreciate the additional ablations, theoretical clarifications, and discussion of negative results, which address most of my original concerns.

Two points would benefit from more precise wording: (1) the conditional MI reduction does not necessarily guarantee unconditional compression, and (2) the post-hoc results involve retraining the predictive models rather than explaining fixed pretrained models.

I believe these remaining issues can be addressed through clearer theoretical statements and appropriate qualification of the claims, without additional experiments.

Overall, the rebuttal has strengthened the paper, and I maintain my weak-accept rating (3).

AuthorsOpenReview ↗

Response to Reviewer KFVe

We thank the reviewer for their continued discussion, and for acknowledging that the paper has become stronger throughout the rebuttal. We greatly appreciate the reviewer for their contribution to improving our work.

We would like to address the reviewer’s two remaining concerns. The reviewer is absolutely correct that the conditional MI prediction does not necessarily guarantee unconditional compression. To this end, we have made the following adjustments to the manuscript, which are now marked in orange for distinction from our previous edits.

  • We have updated the abstract from “We show that the variational objectives used by existing explainers are invariant to the joint structure of the selected subgraph, and that the module's importance-scaled noise provably reduces input dependence while bounding predictive leakage” to “We show that the variational objectives used by existing explainers are invariant to the joint structure of the selected subgraph, and that the module's importance-scaled noise provably reduces the conditional input dependence of unimportant-node representations, given the importance scores, while bounding conditional predictive leakage through those representations.”

  • We have updated contribution point 2 in the introduction from “We prove that the noise component monotonically reduces I(X;Zunimp)I(X; Z_{unimp}), that label-relevant leakage through unimportant nodes is bounded by that same term, and that retained information is graded by importance,” to “We prove that the noise component monotonically reduces I(X;Zunimp∣α)I(X;Z_{\mathrm{unimp}}\mid\alpha), that label-relevant leakage is bounded by the corresponding conditional compression term, and that retained information is graded by importance. We characterize the residual unconditional information carried by the input-dependent importance scores.”

  • In Section 4.2.1, we update “Theorem 1 shows it reduces I(X;Zunimp)I(X;Z_{\mathrm{unimp}}) monotonically, strictly under conditional non-redundancy,” to “Theorem 1 shows that, conditional on the importance scores α\alpha, increasing the noise applied to unimportant nodes monotonically reduces I(X;Zunimp∣α)I(X;Z_{\mathrm{unimp}}\mid\alpha), strictly under conditional non-redundancy. Because the importance scores are themselves input-dependent, this conditional reduction does not in general imply monotonic reduction of unconditional mutual information. We characterize this residual dependence explicitly in Remark 1”.

  • We also updated Proposition 2 to have made the conditioning explicit in the mutual-information, covariance, and entropy-power terms, consistent with the proof. No additional changes were necessary.

We also agree that our post-hoc experiments should not be interpreted as evaluations on unchanged, frozen pretrained predictors. Although the underlying methods (e.g., PGExplainer, GNNExplainer, V-InFoR, ReFine, and ProxyExplainer) are post-hoc explainers, our experiments incorporate BottleneckMLP into the corresponding trainable representation-learning pipelines, involving modification and retraining of the predictive models. We therefore establish compatibility with post-hoc explainer architectures and improvements within the resulting modified pipelines, rather than improvements in explanations of a fixed pretrained predictor.

We have added “We would like to be clear that the post-hoc designation refers to the underlying explainer methodology, not to a frozen-predictor evaluation protocol. In our BottleneckMLP variants, the module is incorporated into the relevant trainable representation pipeline. Thus, the reported comparisons evaluate modified and retrained pipelines rather than holding the original pretrained predictive model fixed” to Appendix O for clarification.

We appreciate the reviewer’s careful reading and positive assessment. These revisions sharpen the scope of our theoretical and empirical claims without changing the underlying method or experimental results. We are grateful that the reviewer recognizes the strengthened contribution of the paper.

Reviewer_NDFdOpenReview ↗
Rating
3
Confidence
1(−2)
Informativeness
2
Presentation
1(−1)
Soundness
2
Read review
Paper summary

This paper revisits the role of explicit IB regularization in GNN explanation and proposes BottleneckMLP, which combines an MLP bottleneck with importance-scaled noise to encourage compression implicitly. The authors support the approach with extensive theoretical analysis and experiments across several explainers, tasks, and GNN backbones.

Critical strengths

S1. The experimental evaluation is thorough. Beyond the main comparisons, the authors include many ablations and additional analyses, showing a substantial effort to understand how the method behaves under different settings.

S2. I find the discussion of the limitations of variational GIB objectives useful and well motivated and the theoretical analysis offers several interesting perspectives on information compression and retention.

Critical weaknesses

W1. I find the analysis of the variational IB gap useful. However, the connection between information compression and explanation faithfulness is less clear to me. I would appreciate a more concrete explanation of what the theoretical results tell us about when the method should produce better explanations.

W2. I appreciate the additional architectural comparisons, but I am still curious about the choice of this particular bottleneck. What makes a continuous MLP bottleneck suitable for explanation learning, and what would change if it were replaced with a variational or quantized bottleneck?

Questions for authors

The parameter analyses in Appendices L, W, and X are helpful. Could the authors clarify how these findings relate to the convergence improvements in Appendix T? In particular, does the analysis offer any guidance on choosing bottleneck width and noise scale to balance explanation quality and convergence speed?

2 comments
AuthorsOpenReview ↗

Response to Reviewer NDFd part 1 of 2

(Response to reviewer NDFd part 1/2)

We thank the reviewer for their constructive comments and for the positive assessment of the empirical work and the variational-gap analysis. We are glad the breadth of the experimental evaluation and the ablations were thorough, and that the discussion of the limitations of variational GIB objectives was seen as useful and well motivated. The two weaknesses raised (the link from compression to faithfulness, and the choice of a continuous MLP bottleneck) are both addressed directly below, and the question on parameter analyses has prompted an analysis that unifies several results currently presented separately. This has allowed us to improve the manuscript as well, and we thank the reviewer for encouraging this analysis (appearing in Section 4.2 after the two components of BottleneckMLP are introduced). We respond to each weakness and question below, and have marked all corresponding updates in blue text within the manuscript.

W1 (Connection between compression and explanation faithfulness)

We clarify that we do not claim a direct/ proven connection between compression and faithfulness. Proposition 1 is exact and measured. It states that the explicit IB regularizer is invariant to the joint law of the mask, so it does not constrain I(G;s^)I(G; \hat{s}) beyond per-unit marginals. For example, at least 11.8 of NCI1's 22.8 nats provably is not information about GG (Table 1). Theorem 1 is also an exact derivative, not a bound, and it shows that importance-scaled noise strictly reduces I(X;Zunimp)I(X;Z_{unimp}) under conditional non-redundancy. Lemma 1 is a bound predicting that the leakage through unimportant nodes is dominated by that same term, so the reduction here does not come at the cost of prediction performance. Finally, the faithfulness is then shown as an empirical result. We see the ground truth motif recovery (the NO$_2$ group in MUTAG and the cycle/ house motifs in BA-2Motifs; Appendix H), the explanation AUC-ROC against ground truth masks, and the Fid$\pm$ results all empirically support that we effectively achieve explanation faithfulness as a result of our method. The method encourages compression of important nodes and drift in unimportant nodes, and this leads to increases in classifier and explanation performance. This would suggest that the compression mechanism is helping to identify the import nodes for prediction which is leading to the increased faithfulness as a natural explanation, but the reviewer is correct that this direct link is not a theoretical result and remains demonstrated by the empirical evidence.

W2 (Continuous MLP bottleneck versus variational or quantized bottleneck)

We appreciate this insightful question from the reviewer and have two reasons backing our decision for the continuous MLP bottleneck over the variational or quantized bottleneck alternatives. The first reason is theoretical. It is because our capacity argument requires this continuous channel setting. Proposition 4 (Appendix E) bounds I(X;Z)I(X;Z) by the top ww eigenvalues of Cov(f(X))Cov(f(X)) through the Gaussian channel. A quantized bottleneck would give only a log∣C∣log|C| bound with no dependence on the signal spectrum, and would lose the importance grading of Proposition 2, since α\alpha enters through a continuous noise variance. The practical reason is that the module must be a drop-in. One contribution of our method is that it is a self-contained architectural component that can easily be plugged into existing explainer architectures. A variational bottleneck reintroduces exactly the explicit KL term the paper argues can be realized using our implicit, architectural approach. A quantized bottleneck requires straight-through estimation that interacts with each base explainer's own sampling. Neither is model-agnostic as BottleneckMLP is.

AuthorsOpenReview ↗

(Response to Reviewer NDFd part 2 of 2)

(Response to reviewer NDFd part 2/2)

Q1 (How Appendices L, W, and X relate to the convergence results in Appendix T)

We thank the reviewer for this question. The existing data shows that bottleneck width (Appendix L) affects accuracy weakly. Across five GSAT widths, MUTAG spans 0.926–0.959 and NCI1 0.788–0.799, with narrow bottlenecks (h→h/4h \to h/4) at the top of that range. We see that the noise scale σ\sigma (Appendix X) matters more so and that too large σ\sigma values early in training degrades explanation AUC-ROC (classifier accuracy remains the same/ similar). And, we see that from the convergence studies in Appendix T, BottleneckMLP improves convergence by 30 – 40% and that this is attributable to both components of our method (both the layered compression (Eq. 12) and the noise-driven separation of representation dynamics).

The reviewer has motivated us to dive deeper into how these results are related. We now consider these together and find there is one driving parameter behind each of these observations.

Both the capacity bound (Proposition 4) and the retention bounds (Proposition 2) depend on the signal through the importance signal-to-noise ratio

\qquad \lambda_j \ \text{the eigenvalues of } \mathrm{Cov}(f(X)).$$ This leads to the distinction that the bottleneck width and noise scale act on $\{\rho_j\}$ in different ways. Proposition 4 bounds $I(X;\tilde Z)$ by $\tfrac12\sum_{j\le w}\log(1+\rho_j)$, so narrowing from $d$ to $w$ discards $\Delta I_{\mathrm{arch}} = \tfrac12\sum_{j>w}\log(1+\rho_j)$ exactly, independently of $\sigma$ and of everything downstream. By contrast $\sigma$ leaves every mode in place and slides all of them down the $\log(1+\rho)$ curve together. This predicts the weak width-dependence of accuracy observed in Appendix L where we see a decaying spectrum, where the discarded tail carries little, so accuracy spans only $0.926$–$0.959$ on MUTAG across five widths. Next, write $p$ for an important node and $q$ for an unimportant one. In the high signal-to-noise setting ($\rho_j >> 1$), both $I(X;Z_p)$ and $I(X; Z_q)$ are logarithmic in $1/\sigma$ and their ratio is close to $1$, so compression is weak and barely selective. In the low signal-to-noise setting $(\rho_j << 1)$, $log(1+\rho) \approx \rho$, so both scale as $1/\sigma$ and their ratio becomes constant at $dN_p\alpha_p/(tr(C)\alpha_q)$, so further noise buys no additional selectivity while continuing to destroy absolute signal. Selectivity therefore improves with $\sigma$ up to the transition $\bar{\rho} \approx 1$ and saturates beyond it, which is the interior optimum our grid search locates empirically (Appendix X). It also predicts where that optimum sits,

\sigma^\star \approx \mathrm{tr}(C)/d,

the mean eigenvalue of the signal covariance. We note this also follows independently from our backbone analysis (Q3), where PNA's degree-scalers inflate $tr(C)$ and leave a fixed $\sigma$ mis-scaled relative to GCN. As we noted, Appendix T attributes the 30 – 40% speed-up to layered compression via the diffusion-time argument (Eq. 12), where achieving compression $\Delta I$ by stochastic relaxation costs time $\exp(\Delta I/D)$. The link to width follows direction because the compression obtained architecturally costs no optimization time at all, so if $\Delta I_{\mathrm{tot}}$ is the total compression the task requires, then $$\text{epochs to converge} \sim \exp\Big(\frac{\Delta I_{\mathrm{tot}} - \Delta I_{\mathrm{arch}}}{D}\Big).$$ Therefore, narrowing the bottleneck increases $\Delta I_{\mathrm{arch}}$ and so reduces the residual compression that must be reached by diffusion, with an exponential effect on epochs. This explains why width has a lower effect on accuracy (it discards a low-energy tail) while materially affecting convergence (it removes work from the slow diffusive process). We thank the reviewer for this question which has helped us develop our analysis and understanding even further. We have added a paragraph connecting these together in a cohesive analysis in Section 4.2 after the explanation of the two components of BottleneckMLP (in blue).
Reviewer_m3DXOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes BottleneckMLP, an architectural module for improving Graph Neural Network (GNN) explainability without relying on explicit Information Bottleneck (IB) regularization losses. The authors argue that existing IB-based explainers, such as GSAT, PGIB, and TGIB, use variational regularizers that may poorly approximate the intended mutual information objective. To address this they introduce two components. (1) Importance scaled Gaussian Noise and (2) MLP based compression. They also provide comparison with other baseline explainers and report accuracy and fidelity improvements

Although the paper demonstrates promising empirical improvements, it does not conclusively establish that compressing intermediate node embeddings resolves the specific limitations identified in explicit IB regularizers or improves the original graph-level IB objective.

Critical strengths
  • Proposition 1 provides a decomposition of factorized variational IB regularizers into information and prior-mismatch components. Although some interpretations are questionable, this offers useful insight into the looseness of these regularizers.

  • The proposed architecture is simple, and the reported accuracy and fidelity improvements on several graph benchmarks may represent a useful engineering contribution.

Critical weaknesses
  • Paper claims IB based regularization in GSAT, GPIG and TGIB are invariant to the joint structure of the selected subgraph. However GSAT already addresses a similar concern (Miao et al. ICML 2022, Section 3.1). They say they deliberately avoids imposing a connectivity constraint. Furthermore independence of connectivity of regularizer does not imply GSAT objective completely ignores the graph structure. They use edge selection probabilities which are dependent on the GNN representation.

  • The experiments do not sufficiently isolate the contribution of the proposed mechanism. The reported improvements could potentially be attributed to increased model capacity from the additional MLP layers, the regularization effect of Gaussian noise, or the inductive bias introduced by importance-aware perturbations. Moreover, the results indicate that adding the MLP and noise components also improves the predictive accuracy of the underlying GNN-based model in several settings. Explainers often tend to perform poorly with a poorly performing GNN and vis-a-vis , it remains unclear whether the improvements in explanation fidelity arise from the proposed information-bottleneck mechanism or are merely a by-product of improved predictive performance.

Questions for authors

I have categorized my questions into Essential and Minor/Suggestions. Answers to Essential could affect my assessment, and Minor/Suggestions are just minor details or suggestions.

Essential

  1. Questionable interpretation of IB regularizers

    • Section 4.1 argues that factorized IB regularizers cannot distinguish between connected explanatory motifs and dispersed or redundant edge selections, using this observation to motivate the limitations of existing IB-based explainers.
    • However, graph connectivity is not an explicit requirement of the Graph Information Bottleneck objective, which seeks to preserve label-relevant information while limiting information retained from the input graph. In fact, the original GSAT paper (Miao et al., ICML 2022, Section 3.1) deliberately avoids imposing fixed-size or connectivity constraints, noting that valid explanatory patterns may have varying sizes or consist of disconnected components.
    • Furthermore, although GSAT's variational KL regularizer decomposes over individual edges, the edge-selection probabilities are obtained from graph-contextualized GNN representations, and the predictive loss is evaluated on the selected graph. Consequently, the separability of the regularizer does not imply that the complete GSAT objective ignores graph structure.
    • While the proposed decomposition identifies a legitimate source of looseness in the variational information bound, the paper does not clearly establish why this looseness necessarily harms explanation quality or why a preference for particular joint selection patterns would improve the intended information-bottleneck objective.
  2. Experiment does not clearly isolate the claimed mechanism.

    • The MLP introduces additional trainable layers. Gaussian noise introduces a regularization effect. The importance-aware scaling introduces another modeling assumption.
    • The real explanation for the performance gains could simply be the additional MLP capacity, noise regularization, or a useful inductive bias based on existing importance scores.
    • Moreover, the results indicate that adding the MLP and noise components also improves the predictive accuracy of the underlying GNN model in several settings. Explainers often tend to perform poorly with a poorly performing GNN and vis-a-vis , it remains unclear whether the improvements in explanation fidelity arise from the proposed information-bottleneck mechanism or are merely a by-product of improved predictive performance.
  3. Performance across different GNN backbones

    • Although the suggested method is applicable across different GNN backbones, however the improvement over GAT or PNA architectures is either low or simply insignificant. The major advantages only sems to be on GCN archetecture.
  4. Confusion between the three terms -

    • I(G;S^)⏟selection-mask informationI(X;Z~)⏟embedding informationI(G;GS)⏟explanatory-subgraph information.\underbrace{I(G;\hat S)}_{\text{selection-mask information}} \qquad \underbrace{I(X;\tilde Z)}_{\text{embedding information}} \qquad \underbrace{I(G;G_S)}_{\text{explanatory-subgraph information}}.
    • Section 4.1 characterizes the limitations of explicit IB regularizers through the gap between the variational objective and I(G;S^)I(G;\hat S) , while the intended graph IB objective involves I(G;GS)I(G;G_S) . Section 4.2 instead establishes information-reduction properties of the intermediate representations and uses the data-processing inequality I(X;GS)≤I(X;Z~)I(X;G_S)\leq I(X;\tilde Z) to connect these results to the explanation objective.
    • However, reducing an upper bound on subgraph mutual information does not necessarily imply a reduction in the actual mutual information relative to the original explainer. Could the authors clarify how the identified limitations of the explicit IB objective are addressed by the proposed representation-level compression mechanism? In particular, can they provide theoretical or empirical evidence that BottleneckMLP improves the intended minimal-sufficient-subgraph objective, rather than simply inducing stronger compression in intermediate GNN representations?

Minor/Suggestions

  • Minor:
    • Paper assumes the reader understands the IG based graph explainers and the notations they use.
      • Terms like $ e_{ i,j} $ in 4.1 are not defined properly. Line 150 for mutual information −→+- \rightarrow +.
    • Application of fixed-noise information theory to input-dependent noise
      • From my understanding the paper requires the noise to be independent
5 comments
AuthorsOpenReview ↗

Response to Reviewer m3DX part 1 of 3

(Response to reviewer m3DX part 1/3)

We thank the reviewer for their detailed review and constructive questions. We are glad Proposition 1 offered useful insight into the looseness of factorized variational IB regularizers, and that the architecture's simplicity and the accuracy and fidelity improvements were recognized as a useful contribution. We respond to each question below, and have marked all corresponding updates in blue text within the manuscript.

Q1 (Interpretation of IB regularizers)

We do not argue that connectivity should be imposed, and we agree with GSAT (Miao et al., 2022, Section 3.1) that valid explanatory patterns may have varying sizes or be disconnected. We also agree the full GSAT objective is not blind to graph structure. ϕij\phi_{ij} is produced by a graph-contextualized encoder and the predictive term is evaluated on the selected subgraph.

Our claim is not about connectivity and concerns only the compression term. Proposition 1 shows LIB\mathcal{L}{\mathrm{IB}} is a sum of per-unit terms, therefore is a function of the unit marginals only. Two selection distributions with identical marginals therefore have identical loss while differing in I(G;s^)I(G; \hat{s}) which is the quantity the term bounds. Our synthetic verification (Appendix F) makes this concrete using abstract units without any notion of connectivity. Here we see identical LIB=1.096798\mathcal{L}{\mathrm{IB}} = 1.096798, with I(U,s^)I(U, \hat{s}) differing by 30%. We now state the invariance in terms of the joint law only.

The looseness matters here because the gap can be reduced along two directions that leave I(G;s^)I(G; \hat{s}) unchanged (Equation 2). Then, gradient descent on LIB\mathcal{L}{\mathrm{IB}} can be in directions orthogonal to the target. This is shown in Figure 1 where the mutual information drops, yet the info loss does not match this behavior. We would like to clarify that we do not claim that the looseness necessarily harms the explanation quality, but we only claim that the term does not always work as well as it could, and that BottleneckMLP is a successful architectural alternative. In the end, graph explainability is a difficult problem and many approaches will likely be needed for the different possible settings. We offer one such approach into the ensemble of possible methods.

Q2 (Isolation of the claimed mechanism)

We would like to refer the reviewer to our parameter-matched controls in Appendix AA and AB. The noise component does not add any trainable parameters over the variant with the MLP-only, so the ablations hold the parameter capacity fixed while only varying the noise mechanism. The shuffled importance experiment offers this isolation. The architecture, the parameter count, and the noise distribution are all kept the same, and only the alignment between the noise and the importances is changed. On GSAT/MUTAG this gives 0.917±0.0240.917 \pm 0.024 accuracy against 0.949±0.0100.949 \pm 0.010 for BottleneckMLP. The pattern holds across datasets. On BA-2Motifs, every parameter-matched control falls to 0.8190.819–0.8670.867 accuracy against 1.0001.000 for BottleneckMLP, with standard deviations up to 0.1910.191 against effectively none, so the ablated variants are both weaker on average and far less stable.

Table 44 isolates the noise component on explanation quality at matched capacity. Removing the noise while keeping the identical MLP architecture costs Fid$^+$ on every dataset: 0.76→0.700.76 \to 0.70 on MUTAG, 0.98→0.940.98 \to 0.94 on BA-2Motifs, 0.77→0.670.77 \to 0.67 on NCI1 and 0.66→0.640.66 \to 0.64 on PROTEINS, with Fid$^-$ also worsening on MUTAG (0.38→0.410.38 \to 0.41) and BA-2Motifs (0.40→0.470.40 \to 0.47). Since the two variants have identical parameter counts, the difference is attributable to the importance-scaled noise rather than to capacity.

The same controls answer the reviewer's second point, that the fidelity gains could be a byproduct of improved predictive accuracy. Accuracy and fidelity move independently across them. On NCI1 the no-noise variant loses 4.04.0 accuracy points (0.762±0.0220.762 \pm 0.022 against 0.802±0.0190.802 \pm 0.019) while its Fid$^+$ falls from 0.770.77 to 0.670.67, a relative drop of 13%13\% that a 44-point accuracy difference would not predict. The reverse also occurs on Alkane Carbonyl where the no-noise variant matches BottleneckMLP on accuracy (0.996±0.0060.996 \pm 0.006 against 0.995±0.0060.995 \pm 0.006), so accuracy differences of this size clearly do not determine explanation quality in either direction. Additionally, Appendix Z rules out the possibility that the benefit is due to useful inductive bias from existing importance scores because it shows that with a frozen, randomly initialized subgraph extractor, the module retains increased performance over the baselines.

AuthorsOpenReview ↗

Response to Reviewer m3DX part 2 of 3

(Response to reviewer m3DX part 2/3)

Q3 (Performance across GNN backbones)

The reviewer is correct that the performance gains are the most significant on GCN backbones. With GAT backbones, the accuracy improves only modestly, and the explanation AUC-ROC remains the same. On PNA backbones, PROTEINS improves substantially, but remain flat for others. We do note that most explainers are built on a GCN backbone. We have revised Appendix W from claiming strict backbone independence and explained the difference in effectiveness depending on backbone. Explanation AUC-ROC measures how well the explainer ranks nodes, and the ceiling above depends on the ratio αp/αq\alpha_p/\alpha_q. These can diverge because an explainer can rank nearly perfectly while producing a compressed score range, leaving the module little to act on. We already observe compressed ranges in the GIN setting (GSAT/NCI1 has over half its nodes at α=1.000\alpha = 1.000, and MUTAG scores never fall below 0.4420.442), confirming this phenomenon does occur. The more compressed \alpha$ distribution on GAT and PNA as compared to on GCN accounts for the carrying effectiveness.

Q4 (Clarifying the three information terms)

This is a fair criticism of our presentation and we have fixed it. The reviewer's understanding and separation of the three terms is correct. We have added a paragraph to the beginning of Section 4 that explains each term and how we use it such that this is clear from the start. We have also added these three terms to Table 6 in Appendix A with our list of symbols and notations for clarity. This clearly distinguishes the selection mask, I(G;s^)I(G; \hat{s}), the embedding I(X;Z~)I(X; \tilde{Z}), and the explanatory subgraph I(G;Gs)I(G; G_s). We note that GsG_s is determined by (G,s^)(G, \hat{s}), so conditional on GG, the mask and the subgraph carry up to same information, with s^\hat{s} as the quantity bounded by GSAT’s regularizer (as is stated in Proposition 1). We have also added Lemma 1 to explicitly determine the relation between I(G;s^)I(G; \hat{s}) and I(G;Gs)I(G; G_s). Since GsG_s is determined by (G,s^)(G, \hat{s}), the chain rule gives I(G;GS)≤I(G;s^)+I(G;GS∣s^)I(G; G_S) \le I(G; \hat{s}) + I(G; G_S \mid \hat{s}), so the two targets differ by the information the subgraph carries about GG once the mask is known. The second term is exact and H(Gs∣s^)≤E[∣s^∣]log⁡∣A∣H(G_s| \hat{s}) \leq \mathbb{E}[|\hat{s}|]\log|\mathcal{A}|, where ∣s^∣|\hat s| is the number of selected units. If s^\hat{s} is indexed by a fixed ambient unit set, so that GSG_S is a function of s^\hat{s} alone, then H(GS∣s^)=0H(G_S | \hat{s}) = 0, and I(G;GS)≤I(G;s^)I(G; G_S) \leq I(G; \hat{s}).

Concerning the reviewer’s comment that “reducing an upper bound does not necessarily imply a reduction in the actual mutual information,” we would like to be clear about what we do and do not show. Theorem 1 claim 1 gives the exact derivative ∂I/∂ti=−mmse(1/ti∣Z−i)/2ti2\partial I/\partial t_i = -\mathrm{mmse}(1/t_i \mid Z_{-i})/2t_i^2, so I(X;Zunimp)I(X; Z_{unimp}) strictly decreases. This is not merely an upper bound. The part that is only a bound is the transfer to I(X;Gs)I(X; G_s) via the DPI. The reviewer is correct here that in principle, I(X;Gs)I(X; G_s) could remain unchanged while I(X;Z~)I(X; \tilde{Z}) decreases. We have two points to support that this does not occur. First, we have indirect empirical evidence that I(G;GS)I(G;G_S) does fall because the sparsity results (Appxendix U) and the Fid$^+$ improvements both indicate more concentrated selections. We also see that the visualized explanatory subgraphs via BottleneckMLP are indeed the correctly identified ground truth motifs for BA-2Motifs and Mutag, and this is the exact mode where the bottleneck objectives are respectively optimized. Second, we do have that Theorem 1 claim 3 propagates, since I(X;Z~unimp)→0I(X; \tilde Z_{\mathrm{unimp}}) \to 0 as min⁡iti→∞\min_i t_i \to \infty forces the unimportant nodes’ contribution to GSG_S to vanish, and this remains a valid guarantee.

AuthorsOpenReview ↗

Response to Reviewer m3DX part 3 of 3

(Response to reviewer m3DX part 3/3)

Minor Points

Thank you for these points of improvement. We have updated the manuscript to ensure we fully define all notation, and ensure our list of symbols in Appendix A is complete for all notation used both in our paper, and in the papers for each baseline method.

Fixed-noise theory with input-dependent noise.

The reviewer raises a good point that the theory assumes a fixed noise level, but ours depends on the input. The fix for this is minor. Theorem 1's proof treats the noise as independent of XX. One step uses h(Zi∣X)=d2log⁡(2πe ti)h(Z_i \mid X) = \tfrac{d}{2}\log(2\pi e\,t_i), which is valid only when tit_i is a constant. Ours is not because ti=σ/αit_i = \sigma/\alpha_i, and αi\alpha_i comes from the embeddings.

ZiZ_i now gives information about XX in two ways. It informs about the signal fi(X)f_i(X), which is intended, and it also informs of how noisy it is. A noisier ZiZ_i means the node had lower importance, and this is something which the theorem never accounted for. Conditioning separates the two. To make the necessary updates to the Theorem, we now fix α=a\alpha = a. Then every ti=σ/ait_i = \sigma/a_i is just a number, the noise is independent of XX again, and Theorem 1 applies unchanged. The chain rule splits the quantity to match:

I(X;Zunimp)=I(α;Zunimp)⏟leak via the noise level+I(X;Zunimp∣α)⏟Theorem 1 appliesI(X;Z_{\mathrm{unimp}}) = \underset{\text{leak via the noise level}}{\underbrace{I(\alpha;Z_{\mathrm{unimp}})}} + \underset{\text{Theorem 1 applies}}{\underbrace{I(X;Z_{\mathrm{unimp}}\mid\alpha)}}

The second term is the one Theorem 1 covers, derivative and strictness condition included. The first is the leak the reviewer identifies, and it is at most H(α)H(\alpha). Corollary 2 already has this shape, where H(M)H(M) is the cost of the mask revealing its own length. In this case H(α)H(\alpha) is the cost of the noise revealing its own scale. We have updated Theorem 1 accordingly, and have added the above discussion as the remark following the theorem. We have also updated the proof of Theorem 1 and added the conditioning to Lemma 1 and Proposition 2 (with no effect on their theoretical outcome or proof). There were no other downstream effects caused by this correction.

Ethics Flag

We see that the reviewer has marked the paper with an ethics flag, however, no concern is stated in the review. We are happy to discuss this and relieve any concerns that the reviewer should have.

Comments on the paper

2 comments
AuthorsOpenReview ↗

General comment to all reviewers and the AC (Part 1/2)

General comment to all reviewers and the AC (Part 1/2)

We thank all three reviewers for their detailed and constructive reviews. Reviewer m3DX found that Proposition 1 offers useful insight into the looseness of factorized variational IB regularizers, and that the architecture is simple with accuracy and fidelity improvements that may represent a useful contribution. Reviewer NDFd found the experimental evaluation thorough, with substantial effort devoted to understanding how the method behaves under different settings, and found the discussion of the limitations of variational GIB objectives useful and well motivated. Reviewer KFVe found that the decomposition involving total correlation and marginal mismatch provides valuable insight into the limitations of existing regularization approaches, that the module integrates into different frameworks with limited architectural modification, and had no substantive concerns about the paper's soundness.

For the rebuttal, we corrected every technical issue the reviewers identified and added the analyses they asked for. In the revised PDF, new results and changed claims are shown in blue.

We made one substantive correction to the theory, identified independently by Reviewers KFVe and m3DX. Theorem 1 as stated assumes a fixed Gaussian channel, whereas ti=σ/αit_i = \sigma/\alpha_i with α(i)=αi(x)\alpha(i) = \alpha_i(x). Since α\alpha is a deterministic function of XX, the chain rule gives I(X;Zunimp)=I(α;Zunimp)+I(X;Zunimp∣α),I(X; Z_{\mathrm{unimp}}) = I(\alpha; Z_{\mathrm{unimp}}) + I(X; Z_{\mathrm{unimp}} \mid \alpha), and conditional on α\alpha every tit_i is a constant, so the channel is additive Gaussian with fixed noise and Theorem 1 holds verbatim for the second term, I-MMSE derivative and strictness condition included. The first term is the information the noise level itself reveals, bounded by H)α)H)\alpha). This has the same structure as the H(M)H(M) correction already present in Corollary 2, where the mask reveals its own length. Theorem 1, its proof, and the conditioning in Lemma 1 and Proposition 2 are updated; there were no other downstream effects.

Reviewer NDFd's question on how Appendices L, W and X relate to the convergence results in Appendix T prompted an analysis that unifies results previously presented separately, now added to Section 4.2. Both the capacity bound and the retention bounds depend on the signal only through the per-mode signal-to-noise ratio ρi=αλj/σ\rho_i = \alpha\lambda_j/\sigma, and the two components act on it differently: the bottleneck encourages discarding ΔIarch=12∑j>wlog⁡(1+ρj)\Delta I_{\mathrm{arch}} = \tfrac{1}{2}\sum_{j>w}\log(1+\rho_j), while σ\sigma attenuates every mode together. Since architectural compression costs no optimization time whereas compression by stochastic relaxation costs exp⁡(ΔI/D)\exp(\Delta I/D), epochs to converge∼exp⁡(ΔItot−ΔIarchD).\text{epochs to converge} \sim \exp\Big(\frac{\Delta I_{\mathrm{tot}} - \Delta I_{\mathrm{arch}}}{D}\Big). This explains why width has a lesser effect on accuracy, discarding only a low-energy spectral tail, while materially affecting convergence. The same framework predicts an interior optimum for σ\sigma near σ∗≈tr(C)/d\sigma * \approx tr(C)/d, which is where our grid search locates it empirically.

That framework also accounts for the backbone differences Reviewer m3DX raised and for the negative results Reviewer KFVe asked us to collect. We agree gains are clearest on GCN, and we have revised Appendix W to state the per-backbone results rather than claim backbone independence. Explanation AUC measures ranking while the separation ceiling of Proposition 2 depends on the ratio αp/αq\alpha_p / \alpha_q so an explainer can rank well while producing a compressed score range; we already observe such compression in the GIN setting. We have collected every setting where the module does not strictly improve into a single table and identify four mechanisms: ceiling effects where the baseline is already near-optimal, stacked stochasticity where the base explainer already injects noise, degenerate embedding geometry, and objective mismatch in the case of DIR's invariance penalty.

Three presentational issues are addressed. Following Reviewer m3DX's Q4 and Reviewer KFVe's Q1b, Section 4 now opens with a paragraph distinguishing I(G;s^)I(G; \hat{s}), I(X;Z~)I(X; \tilde{Z}), and I(G;GS)I(G; G_S), and all three are added to the symbol table in Appendix A, which is now complete for notation from our paper and from each baseline method. Following Reviewer m3DX's Q1, the invariance claim in Section 4.1 is restated in terms of the joint law only; we agree that connectivity is not a requirement of the GIB objective and that the full GSAT objective is not blind to graph structure, and our claim concerns the compression term alone.

AuthorsOpenReview ↗

General comment to all reviewers and the AC (Part 2/2)

General comment to all reviewers and the AC (Part 2/2)

We also state more carefully what the theory does and does not establish, following Reviewers NDFd and KFVe. Proposition 1 is exact and measured: at least 11.8 of NCI1's 22.8 nats provably is not information about GG. We have also added Lemma 1 to explicitly determine the relation between I(G;s^)I(G; \hat{s}) and I(G;Gs)I(G; G_s). Since GsG_s is determined by (G,s^)(G, \hat{s}), the chain rule gives I(G;GS)≤I(G;s^)+I(G;GS∣s^)I(G; G_S) \le I(G; \hat{s}) + I(G; G_S \mid \hat{s}), so the two targets differ by the information the subgraph carries about GG once the mask is known. The second term is exact and H(Gs∣s^)≤E[∣s^∣]log⁡∣A∣H(G_s| \hat{s}) \leq \mathbb{E}[|\hat{s}|]\log|\mathcal{A}|, where ∣s^∣|\hat s| is the number of selected units. If s^\hat{s} is indexed by a fixed ambient unit set, so that GSG_S is a function of s^\hat{s} alone, then H(GS∣s^)=0H(G_S | \hat{s}) = 0, and I(G;GS)≤I(G;s^)I(G; G_S) \leq I(G; \hat{s}). Theorem 1 gives an exact derivative rather than a bound, and Lemma 1 bounds predictive leakage by the same term the module reduces. Faithfulness is established empirically, through ground-truth motif recovery, explanation AUC-ROC against ground-truth masks, and Fid±Fid\pm; the direct link from compression to faithfulness is not a theoretical result, and we say so.

We hope this review answers all of the reviewer's concerns, and we are happy to address any remaining questions during the discussion period.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.