Interaction-Aware Influence Functions for Group Attribution

Technical Summary: Interaction-Aware Influence Functions for Group Attribution

Problem Statement
Influence functions are a foundational tool for approximating how removing a training example changes a target function, such as a held-out loss. The standard practice for estimating the influence of a group of examples is to sum the individual influences of its members. However, this additive approach assumes examples contribute independently, failing to capture joint effects. In reality, examples can be redundant (e.g., near-duplicates) or complementary (e.g., similar features with different labels). Summing individual influences double-counts redundant examples and misses the synergistic effects of complementary ones, leading to poor group attribution and suboptimal data selection (e.g., selecting highly redundant subsets). Prior attempts to address this, such as second-order corrections to parameter shifts, often miss how the target function itself responds to those shifts.

Methodology
The authors propose an interaction-aware influence function that characterizes how interactions between examples jointly affect a target function. The core innovation is expanding the target function $f$ to the second order around the trained parameters $\hat{\theta}$, rather than just linearizing the parameter shift.

1. Second-Order Expansion:
   The exact leave-group-out effect $I^-(S) = f(\hat{\theta}_{D\setminus S}) - f(\hat{\theta})$ is approximated by expanding $f$ to second order:
   $$\hat{I}^-(S) \approx \underbrace{\frac{1}{N} \nabla_\theta f(\hat{\theta})^\top u_S}_{\text{First-order influence}} + \underbrace{\frac{1}{2N^2} u_S^\top H_f u_S}_{\text{Interaction term}}$$
   Here, $u_S = \sum_{z_i \in S} u_i$ is the aggregate parameter shift, where $u_i = H^{-1}\nabla_\theta \ell(z_i, \hat{\theta})$, and $H_f = \nabla^2_\theta f(\hat{\theta})$ is the Hessian of the target function.

2. Pairwise Interaction Term:
   The second term (the interaction term) decomposes into a sum of pairwise contributions $\kappa(z_i, z_j) = u_i^\top H_f u_j$.

   • Interpretation: If $H_f$ is positive definite, $\kappa(z_i, z_j)$ acts as an inner product measuring the alignment of two examples' effects on the target.
   • Redundancy vs. Complementarity: The term is positive when examples push the model in similar directions (redundancy, diminishing returns) and negative when they push in opposite directions (complementarity, beneficial joint effect).
   • Closed-Form Factorization: For binary logistic regression, the authors prove that $\kappa(a, b) = (\sigma_a - y_a)(\sigma_b - y_b) \cdot \langle x_a, x_b \rangle_M$. This formally recovers the principle that similar examples with different labels are complementary, while similar examples with the same label are redundant.

3. Greedy Data Selection:
   To apply this to data selection (finding a subset $S$ that minimizes the target when added), the authors derive a marginal score $m(z_i | S)$ for adding a candidate $z_i$ to an already selected set $S$. This score includes a term $u_S^\top H_f u_i$ that penalizes candidates similar to those already selected, effectively balancing individual quality with group diversity without requiring an external diversity heuristic.

Key Contributions

• Theoretical Framework: A new influence function estimator that augments the standard first-order sum with a pairwise interaction term derived from a second-order expansion of the target function. This differs from prior work that expanded the parameter shift (e.g., Basu et al. [5]), offering a more stable and interpretable pairwise structure.
• Theoretical Guarantees: Proof that the interaction term encodes classical supervised learning principles (complementarity of cross-class similar pairs, redundancy of same-class similar pairs) in a closed-form factorization for logistic regression, extendable to deep multi-class classifiers.
• Algorithmic Efficiency: A greedy selection procedure (Algorithm 1) with complexity $O(KPd)$ that precomputes necessary quantities and updates an accumulator, making it scalable to large datasets and models.

Experimental Results
The method was evaluated in two primary settings:

1. Faithfulness to Retraining (Small-Scale Models):

   • Setup: Evaluated on six dataset-model pairs (Logistic Regression, MLPs, ResNet-9) across classification and regression tasks.
   • Metric: Spearman rank correlation between estimated influence and ground-truth leave-group-out retraining effects.
   • Result: The interaction-aware estimator (F+I) achieved the highest correlation in all settings, significantly outperforming standard first-order influence (F) and the second-order parameter-shift correction (F+B). Notably, F+B showed instability, confirming the theoretical ill-conditioning of expanding the parameter shift in non-convex settings.

2. Subset Selection (Small-Scale and LLMs):

   • Small-Scale (MLPs): On MNIST and FashionMNIST, standard influence-based selection (F) collapsed onto a few classes, performing worse than random selection. The interaction-aware method maintained class entropy comparable to random selection and achieved the lowest held-out test loss.
   • Large Language Models (Llama-3.1-8B): Applied to instruction-tuning data selection from a pool of ~270k examples.
   • Result: The proposed method outperformed random selection on all seven downstream tasks (GSM8K, AQuA, ARC-E, HellaSwag, PIQA, ECQA, SQuAD). It achieved the best overall performance on five of the seven tasks, surpassing both influence-based baselines (Additive IF, LESS) and representation-similarity baselines (RDS+, NV-Embed). Crucially, standard influence-based selection (Additive IF) underperformed random selection on most tasks, highlighting the failure of additive scoring in this regime.

Significance and Claims
The paper claims that group attribution is fundamentally about how training examples affect the target, not just the parameter shift. By characterizing interactions through their joint effect on the target, the proposed method addresses the "blind spot" of additive scoring, which leads to redundant data selection. The authors demonstrate that accounting for these interactions is critical for both accurately estimating group influence and selecting diverse, effective training subsets. The method provides a principled, second-order correction that emerges naturally from the target function's curvature, rather than relying on externally imposed diversity penalties.

Limitations
The authors note two main limitations:

1. The greedy selection procedure, while effective, lacks formal optimality guarantees.
2. The estimator inherits approximation errors from the underlying Hessian approximations (e.g., EK-FAC, low-rank projections). Future work could benefit from advances in scalable inverse-Hessian estimation.