TL;DR
Path Integrated Gradients (PIG) is one of the most widely used methods for explaining neural network predictions, but its "one-shot" nature makes it brittle when features are correlated or redundant. By formulating feature attribution and feature selection as a discrete subset selection problem, this paper introduces Greedy PIG—an adaptive, multi-round extension of PIG that iteratively selects features and conditions on them to cancel out feature correlations.
What Problem Does This Paper Address?
Deep neural networks are notoriously opaque, making interpretability critical for high-stakes applications like healthcare and law. While Path Integrated Gradients (PIG) provides an axiomatic way to attribute network decisions to input features, it operates in a single pass ("one-shot").
The authors demonstrate that one-shot PIG struggles severely with feature correlations and redundancy:
- It can assign identical, diluted importance to multiple identical/redundant features, ignoring other crucial signals.
- Strong off-diagonal interactions in the model's Hessian can cause attribution scores to deviate significantly from actual marginal gains, sometimes even yielding negative scores.
- Feature attribution (explaining a single prediction) and feature selection (choosing a global feature subset across a dataset) have traditionally been treated as disconnected problems.
Methods
The authors unify attribution and selection under a discrete subset selection objective: $\max_{S \subseteq [n], |S| \le k} G(S)$, relaxed onto the continuous hypercube $[0, 1]^n$.
- Flexible Objectives: Beyond standard top-class softmax attribution, they introduce a Loss/KL attribution objective ($G_{\text{ATTRIBUTIONKL}}(S) = f(x) \log f(x_S)$), which measures how well a subset of features preserves the network's entire output distribution rather than just the top prediction.
- Greedy PIG (Algorithm 1): Instead of calculating path integrals once across all features, Greedy PIG proceeds in $R$ adaptive rounds. In each round, it computes the integrated gradient along the path only for the remaining unselected features, fixes the top-$z$ features into the baseline (setting their indicator to 1), and repeats.
- Sequential Gradient (SG): A lightweight variant that approximates the integral in each round with a single gradient evaluation ($\nabla g$), dramatically reducing computational overhead.
Datasets
The authors evaluate their method across three distinct modalities without introducing new datasets:
- Image Recognition: ImageNet (using pretrained MobileNetV2 and ResNet50) for Softmax Information Curves (SIC), Loss Information Curves (LIC), and the pointing game.
- Graph Representation Learning: Cora, Pubmed, and ogbn-arxiv evaluated on a 3-layer Graph Convolutional Network (GCN) for edge attribution and graph compression.
- Tabular CTR Prediction: A random subset of the Criteo Click-Through Rate (CTR) dataset for post-hoc global feature selection.
Key Insights and Ideas
- PIG approximates marginal gain up to Hessian cross-terms: The authors prove (Lemma 4.3) that the difference between an integrated gradient attribution and an element's true marginal gain is bounded by the sum of off-diagonal Hessian terms $\sum_{j \neq i} H_{ij}$. When variables are uncorrelated, PIG exactly equals the marginal gain.
- Adaptivity eliminates redundancy: In one-shot attribution, replicating a top feature causes the duplicates to greedily consume all top attribution slots (Lemma 4.4). Adaptivity fixes this: once a feature is selected, it is frozen in the baseline, forcing subsequent attribution scores for its duplicates to drop to zero.
- Unified post-hoc feature selection: By aggregating gradient-based attribution across dataset batches without modifying or retraining the underlying network parameters, post-hoc feature selection can be framed directly within the same subset selection framework.
Key Results
- Image Attribution (ImageNet / MobileNetV2):
- Greedy PIG dramatically improves the Softmax Information Curve area-under-the-curve (Softmax AUC: 0.8486 vs. 0.2639 for standard PIG, 0.4433 for Smooth PIG, and 0.2623 for Guided PIG).
- On Loss Information Curves, Greedy PIG achieves a substantially better KL divergence AUC of 0.6655 (lower is better) compared to standard PIG (2.0812).
- In the 2×2 grid pointing game, Greedy PIG improves pointing accuracy from 0.66 to 0.83.
- Graph Compression: Pruning edges according to Greedy PIG allows dropping >50% of graph edges on Cora, Pubmed, and ogbn-arxiv with negligible loss in GCN node classification accuracy, outperforming random, degree-based, and standard PIG pruning.
- Tabular Feature Selection (Criteo): When pruning down to top-$k$ features ($k \in \{5, 10, 20, 30\}$), Greedy PIG consistently achieves lower validation cross-entropy loss than one-shot PIG (e.g., at $k=5$, loss drops from 0.4827 to 0.4723).
Limitations and Future Work
- Theoretical Set Properties: Formal approximation bounds in submodular optimization rely on specific properties (such as weak submodularity), but proving which properties hold for realistic deep neural network losses remains an open problem.
- Computational Cost: Multi-round integration requires multiple gradient passes; while the Sequential Gradient approximation helps, it remains more expensive than one-shot baselines.
- Scope of Adaptivity: The paper focuses on adapting PIG; evaluating whether similar greedy multi-round extensions benefit other attribution techniques (such as SmoothGrad) is left to future work.
Summary updated