# Feature Interaction Strength in Catboost

I was wondering if anyone knew how the feature interaction strength is calculated in the catboost package. The documentation https://catboost.ai/docs/concepts/output-data_feature-analysis_feature-interaction-strength.html#output-data_feature-analysis_feature-interaction-strength__per-feature-interaction-strength does not explain exactly how it is calculated.

Feature interaction strength is stated here as: $$\text{feature_strength} = \sum_{leaf s} | \sum_{f_1=f_2} \text{Leaf_Value} - \sum_{f_1!=f_2} \text{Leaf_Value} |$$.
Decoding this: The value of the feature interaction strength for each pair of features $$f_1$$ and $$f_2$$ reflects the sum of absolute differences (after being summed across all trees) between the leaves of the tree containing the interaction $$f_1:f_2$$ and the leaves of the tree not containing the interaction of features $$f_1:f_2$$. Notice that this definition of feature interaction does not work if we have "stumps". At least one tree-learner of the ensemble is required to have at least two different features in its respective splits; if not, the term $$\sum_{f_1=f_2} \text{Leaf_Value}$$ will evaluate to NA.
The above mentioned methodology is a straightforward way of measuring interaction but unfortunately, none of the Catboost reference papers mentions anything formal on feature interactions (at the time of writing this answer). For a more authoritative/formal treatment of feature interactions in GBMs, I would strongly looking into the concept of $$H$$-statistic as proposed by Friedman and Popescu (2008) Predictive Learning via Rule Ensembles. This work takes the concept of partial dependency plots (from Friendman's earlier work (2001) Greedy function approximation: a gradient boosting machine) and generalises it. In short, it quantifies the change that the PDP of feature $$x_j$$ has when feature $$x_i$$ was included or not in the construction of $$x_j$$ PDP. Notice that the $$H$$-statistic becomes quickly quite expensive to evaluate as we really have to compute marginal distributions across numerous features-pairs. The Catboost approach should be extremely faster in comparison.