Greedy PIG: Adaptive Integrated Gradients

Kyriakos Axiotis, Sami Abu-El-Haija, Lin Chen, Matthew Fahrbach, Gang Fu

Abstract: Deep learning has become the standard approach for most machine learning tasks. While its impact is undeniable, interpreting the predictions of deep learning models from a human perspective remains a challenge. In contrast to model training, model interpretability is harder to quantify and pose as an explicit optimization problem. Inspired by the AUC softmax information curve (AUC SIC) metric for evaluating feature attribution methods, we propose a unified discrete optimization framework for feature attribution and feature selection based on subset selection. This leads to a natural adaptive generalization of the path integrated gradients (PIG) method for feature attribution, which we call Greedy PIG. We demonstrate the success of Greedy PIG on a wide variety of tasks, including image feature attribution, graph compression/explanation, and post-hoc feature selection on tabular data. Our results show that introducing adaptivity is a powerful and versatile method for making attribution methods more powerful.

Introduction

Deep learning models are often described as "black boxes"—we see what goes in and what comes out, but the internal logic remains largely opaque. To address this, researchers use feature attribution to assign importance scores to input features, such as pixels in an image or words in a sentence. However, most existing methods are "one-shot," calculating all scores simultaneously. This approach often fails when features are highly correlated, leading to noisy or misleading explanations.

In "Greedy PIG: Adaptive Integrated Gradients," researchers from Google Research propose a transformative approach: making feature attribution adaptive. By reframing attribution as an iterative subset selection problem, Greedy PIG significantly improves the clarity and accuracy of model explanations.

The Problem with One-Shot Attribution

The current gold standard for feature attribution is Path Integrated Gradients (PIG). It calculates the gradient of the model's output along a path from a "blank" baseline (e.g., a black image) to the actual input. While theoretically grounded, PIG assumes features act independently.

In real-world data, features are rarely independent. For example, adjacent pixels in an image are highly correlated. When faced with such redundancy, one-shot algorithms like PIG may split the "credit" between features or even assign negative scores to important ones. This results in "grainy" saliency maps that do not accurately reflect the model's decision process. Furthermore, feature attribution (explaining a single instance) and feature selection (choosing features for a whole dataset) have traditionally been treated as separate tasks. This paper seeks to unify them under a single mathematical framework: discrete subset selection.

Methodology: The Greedy PIG Framework

The authors introduce Greedy PIG, which applies the principles of greedy discrete optimization to the world of gradients. Instead of a single pass, the algorithm works in iterative rounds:

  1. Gradient Calculation: Calculate integrated gradients for the current state of the input.
  2. Selection: Identify the top-$z$ features based on these gradients.
  3. Adaptation: "Fix" these features by setting them to their final values in the baseline.
  4. Iteration: Repeat the process for the remaining features until the desired subset size is reached.

This "greedy" twist is the key to its success. By fixing features already chosen, the algorithm eliminates their correlation with the remaining features in subsequent rounds. If a feature is redundant, its gradient will naturally drop to zero once its "twin" has been selected. Additionally, the authors propose using the model's training loss (KL divergence) as the objective function, capturing the model's entire behavior across all classes rather than just the top prediction.

Key Insights

  • Addressing Correlation: The authors prove that standard PIG only accurately represents a feature's "marginal gain" when features are uncorrelated. Greedy PIG explicitly handles correlation by updating the model's state.
  • Conditional Importance: Greedy PIG essentially asks: "Which feature is most important given the ones I've already picked?" This conditional logic is much closer to human explanatory patterns.
  • Unified Approach: The same greedy algorithm proves effective for both local image attribution and global tabular feature selection, providing a general-purpose tool for interpretability.

Results and Analysis

The researchers evaluated Greedy PIG across computer vision (ImageNet), Graph Neural Networks (Cora, Pubmed), and tabular data (Criteo CTR). The quantitative improvements were substantial.

Performance curves showing Softmax of top class (left) and KL divergence (right) as a function of features kept. Greedy PIG (orange) shows superior efficiency.

As shown in the performance curves above, Greedy PIG (the orange line) maintains significantly higher model confidence with fewer features compared to baseline methods. On ImageNet, it achieved a Softmax AUC of 0.8486, compared to just 0.2639 for standard Integrated Gradients.

Quantitative comparison of attribution algorithms using Softmax AUC and KL divergence AUC.

The table above highlights the performance gap. In graph tasks, Greedy PIG identified edge subsets that allowed for the removal of over 50% of the graph with negligible accuracy loss. In tabular data, it consistently found more predictive feature subsets, leading to lower cross-entropy loss on the massive Criteo dataset.

Conclusion and Future Work

Greedy PIG demonstrates that adaptivity is a powerful tool for enhancing model interpretability. By treating attribution as an iterative optimization problem, it overcomes the limitations of one-shot methods and provides a unified framework for explanation and selection.

While Greedy PIG is computationally more intensive due to its iterative nature, its superior performance across diverse domains marks a significant advancement. Future work may involve applying this adaptive "Greedy" wrapper to other attribution methods, such as SmoothGrad or Blur PIG, to further push the boundaries of explainable AI.

Summary updated

Abstract

Deep learning has become the standard approach for most machine learning tasks. While its impact is undeniable, interpreting the predictions of deep learning models from a human perspective remains a challenge. In contrast to model training, model interpretability is harder to quantify and pose as an explicit optimization problem. Inspired by the AUC softmax information curve (AUC SIC) metric for evaluating feature attribution methods, we propose a unified discrete optimization framework for feature attribution and feature selection based on subset selection. This leads to a natural adaptive generalization of the path integrated gradients (PIG) method for feature attribution, which we call Greedy PIG. We demonstrate the success of Greedy PIG on a wide variety of tasks, including image feature attribution, graph compression/explanation, and post-hoc feature selection on tabular data. Our results show that introducing adaptivity is a powerful and versatile method for making attribution methods more powerful.
BibTeX
@misc{axiotis2023greedy,
  author = {Kyriakos Axiotis and Sami Abu-El-Haija and Lin Chen and Matthew Fahrbach and Gang Fu},
  title = {{Greedy PIG: Adaptive Integrated Gradients}},
  year = {2023},
  eprint = {2311.06192},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2311.06192},
}
Figure