Understanding Variable Interactions via Möbius Transform in Machine Learning

Stop looking at feature importance as a list of individual weights. You are doing it wrong.

Most engineers treat Explainable AI (XAI) like a grocery list: “The model gave high weight to ‘apple’ and ‘banana’.” But what happens when the model sees “apple-banana” as a single, unified concept that behaves entirely differently from its parts? If you only track individual features, you are blind to the actual logic driving your production models. You aren’t seeing the architecture; you’re just guessing at the ingredients.

When you rely on first-order methods like Shapley values or Banzhaf values, you are essentially trying to conduct an orchestra by measuring how much each musician’s individual volume contributes to the room. It’s a flawed mental model. You might know the violin is loud, but you have no idea why the harmony suddenly shifts when the cello and flute play in unison.

The Failure of First-Order Attribution

Traditional game-theoretic notions of importance—Shapley and Banzhaf values—are great for seeing how much a single variable contributes to an output. They are fine for simple regressions. But they fail miserably when faced with the non-linear, high-order interactions inherent in modern neural networks.

In complex models, features don’t just add up; they multiply, flip, and collide. This is where we see non-monotonic interaction effects.

Consider a BERT model analyzing sentiment. Individually, words like “never” or “fails” carry heavy negative weight. If you use standard attribution, your dashboard tells you: “Warning: Negative sentiment detected due to ‘never’.” But what if the combination of those words actually triggers a different semantic state?

The Möbius transform changes the game. Its coefficients correspond to unique importance scores for sets of input variables, not just individual ones. It captures the “harmony”—the higher-order interactions that first-order methods collapse into singletons.

Why the Möbius Transform is Superior

The Möbius transform provides a mathematically grounded way to represent the model’s behavior by capturing multi-way dependencies. While Shapley values try to distribute “payout” among players, the Möbius transform actually maps out the interaction structure of the function itself.

The data shows that when you are constrained by a budget—meaning you can only afford to look at a limited number of terms or coefficients—the Möbius transform is significantly more effective. In fact, representations generated via the Sparse Möbius Transform have been observed to be up to twice as faithful to the original function compared to Shapley and Banzhaf values when using the same number of terms.

The Breakthrough: Sparse Möbius Transform (SMT)

If the Möbius transform is the “what,” the Sparse Möbius Transform (SMT) is the “how.”

Standard Möbius transforms are computationally expensive. If you have $n$ features, you’re looking at an exponential explosion of possible sets. You can’t run that in a production monitoring pipeline for a model with thousands of dimensions.

The SMT algorithm solves this by exploiting two critical properties observed in real-world neural networks:
1. Sparsity: Not every combination of features matters. Most higher-order interactions are noise.
2. Low-degree properties: Real-world models often exhibit most of their meaningful interaction at relatively low degrees (e.g., 2nd or 3rd order interactions).

The SMT algorithm is the first sub-linear query complexity, noise-tolerant algorithm for the Möbius transform. This means it doesn’t have to probe every possible combination of inputs to reconstruct the interaction landscape. It intelligently samples the space to recover the most important coefficients.

graph TD
    A[Input Features] --> B{SMT Algorithm}
    B --> C[Sparsity Exploitation]
    B --> D[Low-Degree Property Check]
    C --> E[Sub-linear Sampling]
    D --> E
    E --> F[Recovered Möbius Coefficients]
    F --> G[Higher-Order Interaction Map]
    G --> H[Model Interpretation/Debugging]

Practical Implications for Production Engineering

If you are an engineer building LLM-based systems or complex NLP pipelines, this isn’t just academic theory. It has direct applications in how we monitor and debug models.

1. Detecting “Interaction Triggers”

Instead of just monitoring for toxic words (individual features), you can use SMT to detect interaction triggers. These are specific combinations of tokens or structural patterns that cause a model to fail, hallucinate, or exhibit bias. If a model suddenly starts outputting biased content, SMT can tell you it wasn’t just “Word X,” but the interaction of “Word X + Context Y + Structure Z.”

2. Feature Pruning and Inference Optimization

You can use SMT to identify which higher-order interactions are actually driving your model’s output. If a specific set of features has zero or negligible Möbius coefficients, you can prune those inputs or simplify the feature engineering process, potentially reducing inference costs without sacrificing accuracy.

3. Granular Debugging

Stop saying “the model is biased.” Start saying “this specific phrase structure triggers the bias.” SMT allows for a level of granularity that makes debugging complex models actually actionable rather than a guessing game.

The Skeptic’s Corner: What to Watch Out For

I’m not going to tell you this is a magic bullet. There are real risks here that we need to be honest about:

• The “Low-Degree” Assumption: SMT relies on the assumption that models are “low-degree.” If you are working with a model that has extremely high-frequency, highly non-linear components, SMT might miss the most critical interactions because it’s looking for patterns in the wrong places.
• Complexity vs. Interpretability: While $R^2$ faithfulness is higher, as the number of interacting features grows, the complexity of interpreting those coefficients grows exponentially. It becomes “explainable” to a mathematician, but perhaps not to a human operator in a high-pressure production environment.
• Sub-linear Complexity Risks: The claim of sub-linear query complexity is heavy. We need to ensure that in extremely high-dimensional spaces (like long-context windows), the algorithm doesn’t trade off accuracy for speed by introducing catastrophic aliasing or incorrect coefficient estimation.

Discussion

1. How do you see the trade-off between “feature importance” and “interaction importance” playing out in your current XAI stack?
2. Given the assumption of low-degree properties, which types of modern architectures (e.g., Transformers vs. MLP-Mixers) do you think are most likely to break SMT’s assumptions?
3. Can we move from using SMT as a post-hoc interpretability tool to using it during training for automated feature engineering?

References

1. arxiv.org/abs/2402.02631
2. justinkang221.github.io/files/kang2024mobius.pdf
3. dl.acm.org/doi/abs/10.5555/3737916.3739383
4. neurips.cc/media/neurips-2024/Slides/94122.pdf
5. www.semanticscholar.org/paper/Learning-to-Understand:-Identifying-Interactions-Kang-Erginbas/d93ea1d8120d98f3ead7e658d5a30e82c6dc4ef3/figure/0
6. proceedings.neurips.cc/paper_files/paper/2024/file/520b379123d16e41f85472e766846486-Paper-Conference.pdf
7. deep-diver.github.io/neurips2024/posters/glgexu1zg4/
8. notesum.ai/share/arxiv_papers/public/conferences/neurips/2024/neurips.glGeXu1zG4
9. paperlist.ai/en/conferences/neurips/2024/topics/signal-processing
10. www.proceedings.com/079017-1467.html
11. openreview.net/pdf?id=KI8qan2EA7
12. www.semanticscholar.org/paper/Learning-to-Understand:-Identifying-Interactions-Kang-Erginbas/d93ea1d8120d98f3ead7e658d5a30e82c6dc4ef3/figure/2
13. arxiv.org/html/2402.02631v2
14. landonbutler.github.io/docs/Mobius.pdf
15. mlanthology.org/neurips/2024/kang2024neurips-learning/
16. proceedings.neurips.cc/paper_files/paper/2024/hash/520b379123d16e41f85472e766846486-Abstract-Conference.html
17. Partnering with industry leaders to accelerate AI transformation
18. Decoupled DiLoCo: A new frontier for resilient, distributed AI training

References Containing Code

1. 💻 https://openreview.net/forum?id=glGeXu1zG4