Integrated Gradients on Graphs

Integrated Gradients is built on two critical axioms that guarantee explanation validity. Sensitivity demands that if a single input feature (an edge or node) changes and causes a different prediction, it must receive a non-zero attribution. Implementation Invariance ensures that functionally equivalent networks—regardless of internal architecture—produce identical attributions. This mathematical rigor distinguishes it from heuristic gradient methods that can saturate and miss critical features.

The method computes attributions by accumulating gradients along a straight-line path from a baseline graph to the actual input graph. The baseline typically represents a neutral, information-free state—such as a graph with all zeros for node features or an empty adjacency matrix. By integrating gradients at every interpolated step, the method captures the cumulative effect of adding structural information, avoiding the local saturation problems that plague simple gradient saliency maps.

Adapting Integrated Gradients to discrete graph structures requires a continuous relaxation. Instead of binary edge removal, a continuous edge mask is applied where edge weights are interpolated from 0 (baseline) to 1 (original). The adjacency matrix becomes a weighted, fully differentiable object during the integration process. This allows gradients to flow through the structural connections themselves, attributing importance directly to specific edges in the computational graph.

Beyond structural edges, the method simultaneously computes attributions for node-level features. The interpolation path blends a baseline feature vector (often a zero vector or global average) with the original node attributes. The integrated gradient for each feature dimension quantifies its contribution to the final prediction. This dual attribution—structural and feature-based—provides a complete picture of why a Graph Neural Network made a specific decision.

The Completeness axiom guarantees that the sum of all attributions across every edge and node feature exactly equals the difference between the model's output for the input and the baseline. This conservation property ensures no importance is lost or artificially created during the explanation process. For a graph classification task, this means the total attributed importance perfectly accounts for the shift from a neutral prediction to the final class probability.

The continuous integral is approximated in practice using the Riemann sum with a finite number of interpolation steps (typically 20 to 300). At each step, the gradient of the model output with respect to the interpolated adjacency and feature matrices is computed. The final attribution is the average of these gradients multiplied by the difference between the input and baseline. Increasing the number of steps improves approximation accuracy at the cost of linear computational overhead.

A model-agnostic framework that identifies the most influential compact subgraph and a small subset of node features for a GNN's prediction. Unlike gradient-based methods, it learns a soft mask over edges and features by maximizing mutual information between the masked input and the original prediction. It provides a direct structural explanation without requiring access to model internals.

A foundational visualization technique that assigns an importance score to each node or edge based on the gradient of the target prediction with respect to the input adjacency or feature matrix. It computes a simple first-order approximation, whereas Integrated Gradients satisfies the completeness axiom by accumulating gradients along a path. Saliency maps are computationally cheaper but can suffer from gradient saturation in deep networks.

A game-theoretic approach that assigns a fair importance score to each node or edge by computing its marginal contribution across all possible coalitions of graph components. Methods like GraphSVX decompose predictions using Shapley values on coalitions of nodes and features. While Shapley values satisfy strong axiomatic guarantees, they are computationally exponential; Integrated Gradients offers a more tractable path-integral alternative.

Layer-wise Relevance Propagation adapted for Graph Neural Networks decomposes the output prediction backwards through the network layers to assign relevance scores to input nodes and edges. It uses a conservation principle to redistribute relevance, ensuring no relevance is lost or created. This contrasts with Integrated Gradients, which operates in the input space by interpolating from a baseline graph.

The minimal structural perturbations—such as removing specific edges or nodes—that would alter a GNN's prediction to a different outcome. Tools like CF-GNNExplainer identify actionable edge deletions. While Integrated Gradients answers 'which parts were important?', counterfactual methods answer 'what would need to change for a different outcome?', providing recourse rather than attribution.

A quantitative evaluation score that measures how accurately an explanation reflects the GNN's true reasoning process. It is typically assessed by the drop in prediction performance when the top-k most important edges or nodes identified by Integrated Gradients are removed from the input graph. A steep drop indicates high faithfulness; a shallow drop suggests the explanation missed critical structures.