Unlocking the Game: Estimating Games in Möbius Representation for Explanation and High-Order Interaction Detection

Majid Mohammadi, Ilaria Tiddi, Annette ten TeijeAAAI 2025 · DOI

Introduction

Explainable AI (XAI) has long grappled with a fundamental trade-off between computational efficiency and model fidelity. Popular tools like Kernel SHAP often rely on the "inessential game" assumption—the idea that features contribute to a model's prediction independently. While this simplifies the math, it ignores the complex, synergistic interactions that define real-world data. Researchers from Vrije Universiteit Amsterdam have introduced GEM-FIX (Game Estimation in Möbius representation for Feature Interaction detection and eXplanation), a framework that moves beyond simple feature attribution to capture high-order interactions without the usual exponential computational explosion.

The Challenge of Feature Interactions

In cooperative game theory, calculating the exact contribution of every possible combination of features is computationally prohibitive, scaling at $2^d$ for $d$ features. Existing approximations struggle when features have strong synergistic effects and fail to explicitly identify how features interact (e.g., "Feature A is only significant in the presence of Feature B").

The GEM-FIX Framework

GEM-FIX addresses these limitations by shifting estimation to the Möbius representation. In this mathematical space, the value of a coalition is decomposed into unique contributions from every possible subset, naturally highlighting interactions.

Key technical innovations include:

  • Polynomial-Time Computation: The authors prove that the inner product of high-dimensional Möbius vectors can be calculated in $O(d)$ time. This allows the problem to be framed as a regression with $O(n)$ parameters, where $n$ is the sample size, rather than $2^d$.
  • Efficient Shapley Values: A new formula derives Shapley values directly from the regression solution in linear time, bypassing the need to enumerate all subsets.
  • Sparsity and Regularization: By employing L2 and Lasso regularization, GEM-FIX identifies only the most significant interactions, ensuring that explanations remain interpretable rather than becoming a "wall of noise."

Experimental Validation

The framework was validated across game simulations, synthetic data, and real-world tabular and textual benchmarks.

Superior Accuracy in Game Simulations

In controlled simulations where ground-truth Shapley values are known, GEM-FIX consistently outperformed Kernel SHAP. As the complexity of the game (number of players) increased, GEM-FIX maintained a significantly lower absolute deviation from the truth, even with limited samples. This demonstrates that relaxing the independence assumption leads to more reliable explanations.

Error rates of GEM-FIX versus SHAP variants as the number of players and samples vary.

Robustness on Tabular Benchmarks

On classic benchmarks such as California Housing and Diabetes, GEM-FIX demonstrated superior stability. By accounting for interactions, it achieves lower absolute error compared to methods that treat the model as a simple sum of individual parts.

Absolute error comparison on tabular benchmarks, showing GEM-FIX's consistent performance across datasets.

Interaction Detection and Text Analysis

GEM-FIX successfully recovered high-order interactions (up to 3rd order) with high true positive rates. In sentiment analysis tasks using BERT, GEM-FIX proved more reliable at identifying redundant words. When the "least important" words identified by GEM-FIX were masked, the model's prediction remained stable, whereas other methods like LIME or MAPLE caused the prediction to fluctuate significantly.

Conclusion

GEM-FIX represents a significant step forward for XAI by making "essential" game estimation computationally feasible. By relaxing the independence assumption, it provides more accurate explanations and uncovers the hidden interactions that drive complex model decisions. Future work may focus on integrating Bayesian methods to quantify the uncertainty of these high-order interaction estimates, providing users with a clearer sense of how much to trust specific feature attributions.

Summary updated

BibTeX
@inproceedings{mohammadi2025unlocking,
  author = {Majid Mohammadi and Ilaria Tiddi and Annette ten Teije},
  title = {{Unlocking the Game: Estimating Games in Möbius Representation for Explanation and High-Order Interaction Detection}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i18.34148},
}
Figure