Research map / Learning theory and algorithms / Sample complexity
Learning to Understand: Identifying Interactions via the Möbius Transform
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Sparse Möbius Transform (SMT), a non-adaptive group-testing-based algorithm that recovers sparse, low-degree Möbius transform coefficients of set functions with sublinear sample complexity, and shows it yields more faithful explanations than Shapley/Banzhaf values.
Problem
Computing the Möbius transform of a set function over n inputs normally requires 2^n evaluations; the paper targets efficient recovery of its interaction coefficients (importance of input subsets) when the function is sparse and low-degree.
Approach
Combine functional subsampling with aliasing (choosing H as rows of a group testing matrix), graph peeling message passing to resolve collisions, and group-testing-based singleton identification, yielding a non-adaptive algorithm with O(Kn) samples for uniform interactions and O(Kt log n) samples for t-degree interactions, including a noise-robust variant.
Key results
- On real models, SMT achieves higher R^2 than Shapley, Banzhaf and Faith-Banzhaf at the same number of terms for breast cancer and sentiment tasks, up to about twice as faithful.
- SMT recovers K-sparse Möbius transforms in O(Kn) non-adaptive samples under uniform interactions, and O(Kt log n) samples for t-degree interactions.
- In runtime comparisons at n>=100 with K=10 order-5 interactions, SMT is the only feasible method among SMT, SHAP-IQ and LASSO-based FSI.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SMT instead of Shapley or Banzhaf values for sparse representations | Real-world explanation tasks · Breast cancer diagnosis and sentiment analysis | R^2 faithfulness: up to twice as faithful | Helped |
| Use SMT instead of Faith-Banzhaf indices | Multiple-choice question answering · Sentence-level multiple-choice dataset | R^2 faithfulness | No clear effect |
| Use higher-order Möbius interactions in the representation | SMT explanations · Breast cancer diagnosis and sentiment analysis | R^2 faithfulness | Helped |
| Use group-testing SMT rather than the naive full-sampling approach | Synthetic sparse interaction recovery · Synthetic functions with K=100 | perfect reconstruction rate: 10^{-294} percent of total samples | Helped |
| Use SMT rather than SHAP-IQ or LASSO-based FSI | Synthetic functions with K=10 and interaction order 5 · Runtime comparison | runtime | Helped |
| Use sparse Möbius coefficients rather than Shapley or Banzhaf values | Explanations with a fixed number of terms · Breast cancer diagnosis and sentiment analysis | R^2 faithfulness: up to twice as faithful | Helped |
Surprising findings
- On the multiple-choice RACE model, the gap between SMT and Faith-Banzhaf is small because answers are usually within single sentences, so higher-order interactions add little.
Limitations
- Assumes non-zero interactions are uniformly random and independent, which may not hold in real models with correlated interactions.
- Computes the sparse transform rather than a sparse projection onto low-order terms, which may be what practitioners want.
- Theoretical results are asymptotic in n; finite-n experiments are limited to synthetic functions and models with n around 20.
Experimental setup
Datasets: Wisconsin Breast Cancer dataset IMDb Movie Reviews RACE
Benchmarks: Wisconsin Breast Cancer dataset IMDb sentiment analysis RACE multiple choice
Metrics: R^2 faithfulness sample complexity runtime
Baselines: Shapley values Banzhaf values Faith-Banzhaf SHAP-IQ LASSO-based FSI
Builds on: Sparse Boolean Fourier (Hadamard) transform Shapley value Banzhaf value Faith-Banzhaf interaction index SHAP-IQ
Closest papers by meaning
- Unlocking the Game: Estimating Games in Möbius Representation for Explanation and High-Order Interaction Detection (AAAI 2025 · similarity 0.86)
- SPEX: Scaling Feature Interaction Explanations for LLMs (ICML 2025 · similarity 0.83)
- shapiq: Shapley Interactions for Machine Learning (NeurIPS 2024 · similarity 0.82)
- Metric Transforms and Low Rank Representations of Kernels for Fast Attention (NeurIPS 2024 · similarity 0.82)
- Learning single index models via harmonic decomposition (NeurIPS 2025 · similarity 0.82)
- KernelSHAP-IQ: Weighted Least Square Optimization for Shapley Interactions (ICML 2024 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.