Higher-Order Feature Attribution: Bridging Statistics, Explainable AI, and Topological Signal Processing

Technical Summary: Higher-Order Feature Attribution

Problem Statement
Feature attribution methods are essential for Explainable Artificial Intelligence (XAI), aiming to quantify how input features contribute to a model's output prediction. While standard attribution methods (e.g., Integrated Gradients) work well when features act independently, they face limitations when predictive models involve complex interactions, such as multiplicative relationships or joint contributions. In such cases, standard first-order attributions fail to detect or isolate the specific nature of feature interdependencies. Existing frameworks often treat interactions as secondary or lack a unified mathematical structure to represent higher-order dependencies (e.g., triplets of features) alongside first-order effects.

Methodology
The authors propose a general theory of higher-order feature attribution built upon the foundation of Integrated Gradients (IG). The core methodological innovation is the treatment of feature attribution as a linear operator acting on the space of predictive functions.

1. Operator-Theoretic Framework:

   • Standard first-order attribution $a_i$ is defined as the application of an attribution operator $A_i$ to a function $f$: $a_i(x) = A_i f(x)$.
   • Second-order attributions are defined by the composition of two operators: $a_{ij}(x) = A_i A_j f(x)$. This mirrors the concept of second-order derivatives (Hessians).
   • Higher-order attributions (e.g., third-order $a_{ijk}$) are similarly defined by the composition of $k$ operators.

2. Analytical Derivations:

   • Using the IG definition, the authors derive analytical expressions for these higher-order terms.
   • They demonstrate that second-order attributions coincide with the Integrated Hessians framework when $i \neq j$, and provide specific integral formulations for repeated attributions ($i=j$).
   • Key properties are established, including linearity (operators are linear), symmetry ($A_i A_j = A_j A_i$), marginalization (summing second-order attributions over an index recovers first-order attributions), and completeness (the sum of all $k$-th order attributions equals the total prediction change $f(x) - f(\tilde{x})$).

3. Topological Signal Processing Connection:

   • The paper bridges XAI with topological signal processing. It proposes representing attributions as signals over graphs or simplicial complexes.
   • First-order attributions ($a_i$) are viewed as node signals.
   • Second-order attributions ($a_{ij}$) are viewed as edge signals.
   • Higher-order attributions correspond to signals on higher-dimensional structures (e.g., triangles for third-order).
   • The completeness property implies that a node signal equals the sum of adjacent edge signals, creating a hierarchical geometric representation of feature interactions.

Key Results
The authors validate their theory through two primary experiments:

1. Synthetic Data Experiment:

   • A generative model was created with known ground-truth interactions, including a third-order term ($3x_1x_2x_3$) and various second-order terms.
   • A Gaussian Process Regression (GPR) model was trained on this data.
   • Findings: The second-order attributions successfully recovered the ground-truth interaction structure. Furthermore, the marginalization property held empirically: first-order attributions calculated directly via IG were consistent with those derived by summing second-order attributions. Third-order attributions also correctly identified the specific triplet interaction present in the ground truth.

2. Real Estate Valuation (Taipei Dataset):

   • A generalized linear model with quadratic inputs was trained on housing data (416 observations, 6 covariates).
   • Findings: While first-order attributions varied significantly across different house samples, the second-order attribution graphs revealed consistent patterns of joint feature behavior. Specifically, features such as "distance to metro," "number of stores," and "latitude" appeared to act jointly, whereas others contributed in isolation. This suggests the method can identify groups of features that interact during prediction, even when individual contributions vary.

Significance and Claims
The paper claims to provide a unified mathematical framework that extends existing XAI literature (specifically Integrated Gradients and Integrated Hessians) to arbitrary orders of interaction.

• Theoretical Unification: By defining attribution via linear operators, the work establishes a natural algebraic structure that allows for the composition of attributions, similar to derivative operators.
• Geometric Interpretation: The connection to topological signal processing offers a new way to visualize and manipulate feature attributions as graph signals, potentially simplifying the interpretation of complex model behaviors.
• Distinction from Prior Work: The authors distinguish their approach from Shapley interaction indices and Integrated Hessians by emphasizing the operator-theoretic perspective. This preserves algebraic and compositional structures that relate to combinatorial objects like graphs and simplicial complexes, rather than treating attributions merely as scalar scores on subsets of features.

The authors conclude that while this is a preliminary investigation, the framework demonstrates potential for uncovering novel insights into complex models by explicitly modeling and visualizing higher-order feature interactions.