# Learning to Understand: Identifying Interactions via the M"obius Transform

arXiv: https://arxiv.org/abs/2402.02631 · HTML: https://mlsanity.com/paper/2402.02631/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 63 references that are in the map.
- First posted on arXiv 4 Feb 2024.

## Builds on (most cited first, 27 of 27)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [Variational Diffusion Models](https://mlsanity.com/paper/2107.00630/) (2021)
- [RACE: Large-scale ReAding Comprehension Dataset From Examinations](https://mlsanity.com/paper/1704.04683/) (2017)
- [Data Shapley: Equitable Valuation of Data for Machine Learning](https://mlsanity.com/paper/1904.02868/) (2019)
- [BERTweet: A pre-trained language model for English Tweets](https://mlsanity.com/paper/2005.10200/) (2020)
- [Towards Efficient Data Valuation Based on the Shapley Value](https://mlsanity.com/paper/1902.10275/) (2019)
- [Explaining individual predictions when features are dependent: More accurate approximations to Shapley values](https://mlsanity.com/paper/1903.10464/) (2019)
- [Feature relevance quantification in explainable AI: A causal problem](https://mlsanity.com/paper/1910.13413/) (2019)
- [The Shapley Taylor Interaction Index](https://mlsanity.com/paper/1902.05622/) (2019)
- [Data Banzhaf: A Robust Data Valuation Framework for Machine Learning](https://mlsanity.com/paper/2205.15466/) (2022)
- [True to the Model or True to the Data?](https://mlsanity.com/paper/2006.16234/) (2020)
- [A Distributional Framework for Data Valuation](https://mlsanity.com/paper/2002.12334/) (2020)
- [Faith-Shap: The Faithful Shapley Interaction Index](https://mlsanity.com/paper/2203.00870/) (2022)
- [SHAP-IQ: Unified Approximation of any-order Shapley Interactions](https://mlsanity.com/paper/2303.01179/) (2023)
- [Using Captum to Explain Generative Language Models](https://mlsanity.com/paper/2312.05491/) (2023)
- [groupShapley: Efficient prediction explanation with Shapley values for feature groups](https://mlsanity.com/paper/2106.12228/) (2021)
- [TextGenSHAP: Scalable Post-hoc Explanations in Text Generation with Long Documents](https://mlsanity.com/paper/2312.01279/) (2023)
- [Joint Shapley values: a measure of joint feature importance](https://mlsanity.com/paper/2107.11357/) (2021)
- [Fourier Analysis-based Iterative Combinatorial Auctions](https://mlsanity.com/paper/2009.10749/) (2020)
- [Learning Set Functions that are Sparse in Non-Orthogonal Fourier Bases](https://mlsanity.com/paper/2010.00439/) (2020)
- [Efficiently Computing Sparse Fourier Transforms of q-ary Functions](https://mlsanity.com/paper/2301.06200/) (2023)
- [The Fair Value of Data Under Heterogeneous Privacy Constraints in Federated Learning](https://mlsanity.com/paper/2301.13336/) (2023)
- [Computing a k-sparse n-length Discrete Fourier Transform using at most 4k samples and O(k log k) complexity](https://mlsanity.com/paper/1305.0870/) (2013)

## Built on by (most cited first, 13 of 13)

- [ProxySPEX: Inference-Efficient Interpretability via Sparse Feature Interactions in LLMs](https://mlsanity.com/paper/2505.17495/) (2025)
- [Exact Computation of Any-Order Shapley Interactions for Graph Neural Networks](https://mlsanity.com/paper/2501.16944/) (2025)
- [SPEX: Scaling Feature Interaction Explanations for LLMs](https://mlsanity.com/paper/2502.13870/) (2025)
- [PolySHAP: Extending KernelSHAP with Interaction-Informed Polynomial Regression](https://mlsanity.com/paper/2601.18608/) (2026)
- [Explaining Similarity in Vision-Language Encoders with Weighted Banzhaf Interactions](https://mlsanity.com/paper/2508.05430/) (2025)
- [SHAP zero Explains Biological Sequence Models with Near-zero Marginal Cost for Future Queries](https://mlsanity.com/paper/2410.19236/) (2024)
- [H-Sets: Hessian-Guided Discovery of Set-Level Feature Interactions in Image Classifiers](https://mlsanity.com/paper/2604.22045/) (2026)
- [Cross-LLM Consistency in Inference: Evidence from Shared Interactions](https://mlsanity.com/paper/2606.08129/) (2026)
- [CUBE: Contrastive Understanding by Balanced Experiments](https://mlsanity.com/paper/2509.10825/) (2025)
- [Adaptive Sparse M"obius Transforms for Learning Polynomials](https://mlsanity.com/paper/2602.06246/) (2026)
- [Reconciling Contradictory Views on the Effectiveness of SFT in LLMs: An Interaction Perspective](https://mlsanity.com/paper/2605.17967/) (2026)
- [Representation Redundancy and Structural Complexity in Finite-Field Inversion](https://mlsanity.com/paper/2609.04583/) (2026)
- [Do ResNets Route? Sparse Interaction Experts in Residual Networks](https://mlsanity.com/paper/2610.02907/) (2026)

## Abstract (arXiv)

One of the key challenges in machine learning is to find interpretable representations of learned functions. The M"obius transform is essential for this purpose, as its coefficients correspond to unique importance scores for sets of input variables. This transform is closely related to widely used game-theoretic notions of importance like the Shapley and Bhanzaf value, but it also captures crucial higher-order interactions. Although computing the obius Transform of a function with n inputs involves 2n coefficients, it becomes tractable when the function is sparse and of low-degree as we show is the case for many real-world functions. Under these conditions, the complexity of the transform computation is significantly reduced. When there are K non-zero coefficients, our algorithm recovers the M"obius transform in O(Kn) samples and O(Kn2) time asymptotically under certain assumptions, the first non-adaptive algorithm to do so. We also uncover a surprising connection between group testing and the M"obius transform. For functions where all interactions involve at most t inputs, we use group testing results to compute the M"obius transform with O(Ktlog n) sample complexity and O(Kpoly(n)) time. A robust version of this algorithm withstands noise and maintains this complexity. This marks the first n sub-linear query complexity, noise-tolerant algorithm for the M"obius transform. In several examples, we observe that representations generated via sparse M"obius transform are up to twice as faithful to the original function, as compared to Shaply and Banzhaf values, while using the same number of terms.