BottleneckMLP: Graph Explanation via Implicit Information Bottleneck

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 $I(Z;Y)$ while minimizing input dependence $I(X;Z)$. 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.