Mutual Information Maximization

The core principle is to find a subgraph G_S that maximizes I(Y; G_S), the mutual information between the subgraph's representation and the target prediction Y. This is mathematically equivalent to minimizing the conditional entropy H(Y|G_S), ensuring the selected subgraph reduces uncertainty about the output as much as the full graph does. The objective inherently balances expressiveness (capturing relevant structure) and sparsity (discarding noise).

The GIB principle formalizes the trade-off between compression and prediction:

• Compression: Minimize I(G; G_S) to force the explainer to select a maximally compressed subgraph.
• Prediction: Maximize I(Y; G_S) to ensure the compressed subgraph retains all label-relevant information.
• The Lagrangian formulation max I(Y; G_S) - β I(G; G_S) uses β as a hyperparameter controlling the sparsity of the explanation.

Direct computation of mutual information is intractable for high-dimensional graph data. Implementations rely on tractable variational bounds:

• Upper bound on I(G; G_S): Uses a KL-divergence term between the subgraph distribution and a prior (e.g., a Bernoulli distribution) to enforce sparsity.
• Lower bound on I(Y; G_S): Replaces the true conditional with a parameterized neural critic that estimates the mutual information, often via the InfoNCE or Jensen-Shannon divergence estimator.

Graph Stochastic Attention (GSAT) injects randomness into the edge selection process to prevent trivial solutions. The explainer learns a probability p_ij for each edge, sampling a discrete subgraph via the Gumbel-Softmax reparameterization trick. The training objective directly implements the GIB principle, where the KL-divergence regularizer penalizes edges with high probability, automatically pruning irrelevant connections without needing a fixed sparsity target.

To maximize I(Y; G_S), many frameworks use the InfoNCE (Noise-Contrastive Estimation) loss. This treats the positive pair (subgraph, label) against a batch of negative pairs (subgraph, other labels). The model learns to score the true pair higher than negatives, providing a stable, lower-bound estimate of mutual information. This approach is particularly effective when the label space is discrete and well-structured.

The quality of a mutual-information-maximized explanation is measured by:

• Fidelity+: The difference in accuracy when the model sees only the explanation subgraph versus the full graph. A small drop indicates high fidelity.
• Fidelity-: The drop in accuracy when the explanation subgraph is removed from the input. A large drop confirms the subgraph was critical.
• Sparsity: The fraction of edges retained, validating the compression constraint.

A principle for learning explainable GNNs by compressing the input graph into a minimal subgraph that retains maximal mutual information about the label. It explicitly trades off between compression (discarding irrelevant structural noise) and prediction accuracy, formalizing the objective that Mutual Information Maximization approximates. The bottleneck enforces a Lagrangian constraint to balance the mutual information between the input, the compressed representation, and the target.

A self-explainable GNN framework where a generator module extracts a concise, causal subgraph (the rationale) and a predictor module makes a decision based solely on that rationale. Unlike post-hoc methods, the rationale is discovered during training. The generator is optimized to maximize the mutual information between the extracted subgraph and the label while minimizing its size, directly implementing the Mutual Information Maximization objective in an end-to-end architecture.

A method that injects stochasticity into the attention mechanism to automatically select a minimal, label-relevant subgraph. GSAT treats edge selection as a Bernoulli sampling process and optimizes an information bottleneck objective. By adding controlled noise, it prevents the model from collapsing to trivial solutions and ensures the selected subgraph genuinely captures the mutual information with the prediction target, rather than exploiting spurious correlations.

A quantitative evaluation score that measures how accurately an explanation subgraph reflects the true reasoning process of the GNN. It is typically assessed by the drop in prediction performance when the explanation is removed or masked. A subgraph selected via Mutual Information Maximization should score highly on faithfulness, as removing it should maximally degrade the model's output, confirming that the identified structure genuinely drives the decision.

The process of inferring cause-and-effect relationships between variables in graph-structured data. While Mutual Information Maximization identifies predictive subgraphs, causal discovery goes further to distinguish correlation from causation. Integrating causal structure learning with mutual information objectives ensures that the selected subgraph represents a genuine causal mechanism rather than a spurious statistical association, critical for robust, intervention-ready explanations.

A fidelity assessment method that measures the change in a GNN's prediction after masking or altering the most important nodes or edges identified by an explainer. It directly validates the Mutual Information Maximization hypothesis: if the selected subgraph truly captures maximal mutual information with the output, then perturbing it should cause the largest prediction shift. Common perturbation strategies include:

• Node removal: Dropping high-importance nodes
• Edge deletion: Severing critical connections
• Feature noising: Corrupting node attributes