Graph Information Bottleneck

GIB frames explanation as a Lagrangian optimization problem balancing two competing objectives:

• Compression (Rate): Minimize the mutual information (I(G; G_S)) between the original graph (G) and the explanatory subgraph (G_S). This forces the explainer to discard as many nodes and edges as possible.
• Prediction (Distortion): Maximize the mutual information (I(G_S; Y)) between the subgraph and the target label (Y). This ensures the kept structure is causally relevant.

The hyperparameter (\beta) controls the trade-off, allowing practitioners to tune explanation sparsity.

Directly computing mutual information in high-dimensional graph space is intractable. GIB implementations rely on variational bounds to approximate these quantities:

• Upper bounds on (I(G; G_S)) are used for compression, often via a parameterized variational distribution or contrastive estimation.
• Lower bounds on (I(G_S; Y)) are maximized for prediction, typically using the cross-entropy loss of a classifier trained solely on the extracted subgraph. This variational approach makes the principle computationally feasible for real-world GNNs.

Unlike perturbation-based methods, GIB seeks an invariant rationale—a subgraph structure that consistently predicts the label across different environments or data splits. This is achieved by:

• Penalizing the explainer for including spurious correlations that only hold in the training distribution.
• Encouraging the selection of edges that form the causal core of the prediction. This property makes GIB-based explanations more robust to distribution shift than gradient-based saliency maps.

To enable gradient-based optimization over discrete graph structures, GIB explainers typically employ the Gumbel-Softmax reparameterization trick:

• An edge's importance is parameterized as a continuous logit.
• During training, discrete masks are sampled from a Concrete distribution, allowing gradients to flow through the stochastic node.
• The temperature parameter is annealed from high to low, gradually sharpening the mask toward a hard binary selection of the explanatory subgraph.

While both extract explanatory subgraphs, they differ fundamentally in objective:

• GNNExplainer maximizes mutual information between the subgraph and the prediction without an explicit compression term. It relies on a sparsity constraint on the mask size.
• GIB directly penalizes the information content of the subgraph, leading to a more principled information-theoretic stopping criterion. GIB explanations tend to be sparser and more stable across runs, as the compression term prevents the inclusion of marginally relevant edges.

GIB provides the theoretical foundation for the graph rationalization framework, where a generator-predictor architecture is trained end-to-end:

• The generator learns to sample a subgraph (G_S) that minimizes (I(G; G_S)).
• The predictor is trained to maximize (I(G_S; Y)) using only the extracted rationale. This cooperative training ensures the predictor relies exclusively on the causal subgraph, making the model inherently self-explainable without post-hoc analysis.

The foundational objective function of the Graph Information Bottleneck. It seeks to learn a compressed subgraph representation Z that maximizes I(Z; Y)—the mutual information with the label—while simultaneously minimizing I(Z; G)—the information retained from the original input graph. This forces the model to discard irrelevant structural noise and retain only the most predictive components. In practice, this is often optimized via a variational upper bound on the compression term and a tractable lower bound on the prediction term.

A self-explainable framework that directly instantiates the GIB principle. It decomposes a GNN into two collaborative modules: a generator that extracts a concise, causal subgraph (the rationale) from the input, and a predictor that makes a decision based solely on that rationale. The generator is trained to produce subgraphs that are both minimal and sufficient for accurate prediction, effectively learning to answer 'what part of the graph matters most?' without post-hoc analysis.

A method that injects stochasticity into the attention mechanism to automatically learn a minimal, label-relevant subgraph. GSAT treats edge selection as a Bernoulli sampling process, where the probability of retaining an edge is learned via an attention weight. The training objective directly penalizes the mutual information between the selected subgraph and the full graph, implementing the GIB compression constraint. A temperature parameter controls the discreteness of the mask, enabling gradient-based optimization.

A post-hoc explanation method that operationalizes the GIB concept by learning a sparse mask over the messages passed between nodes in each GNN layer. For a given prediction, GraphMask trains a classifier to predict whether each edge's message can be replaced with a learned baseline vector without changing the model's output. Edges that can be safely masked are deemed irrelevant. This identifies which connections in the computational graph are non-essential, effectively discarding structural noise layer by layer.

The primary metric for validating GIB-based explanations. Faithfulness measures how accurately an extracted subgraph reflects the model's true reasoning process. The standard protocol is the fidelity- curve: progressively remove the most important nodes or edges identified by the explainer and measure the drop in prediction accuracy. A steep drop indicates high faithfulness. The complementary metric, infidelity, measures the prediction change when keeping only the explanation and removing everything else.

An extension of the GIB principle that moves beyond statistical correlation to identify cause-and-effect relationships in graph data. While standard GIB selects subgraphs that are predictively sufficient, causal discovery seeks subgraphs that remain predictive under interventions and distribution shifts. This involves learning invariant representations that capture the true generative mechanisms rather than spurious correlations. Techniques often leverage structural causal models (SCMs) to define the data-generating process and identify the causal parents of the target variable.