Finding Non-Redundant Simpson's Paradox from Multidimensional Data

Yi Yang, Jian Pei, Jun Yang, Jichun XiearXiv 2025 · DOI · arXiv

Abstract

Simpson's paradox occurs when a statistical trend in an aggregate dataset reverses when the data is split into subgroups. This phenomenon can lead to misleading conclusions in fields ranging from epidemiology to machine learning. This paper reveals that automated methods for detecting these paradoxes in high-dimensional data often flag many "redundant" paradoxes that describe the exact same underlying phenomenon. The authors formalize this redundancy, group equivalent paradoxes into concise summaries, and introduce a fast algorithm to find only unique, non-redundant insights, significantly reducing noise and computation time.

Introduction: The Challenge of Redundancy

Simpson’s paradox is a classic statistical phenomenon with massive implications for decision-making. A famous example is a medical treatment that appears to perform better overall, but when patients are stratified by disease severity, the alternative treatment is actually better for both mild and severe cases.

In modern, high-dimensional datasets, analysts use automated algorithms to search for these paradoxes across all possible combinations of variables. However, a major blind spot exists in existing methods: redundancy. Because real-world data is often sparse, different combinations of attributes might select the exact same set of records.

An example dataset where different attribute combinations (e.g., A=a1 and C=c1) cover the same set of records, leading to redundant paradoxes.

For example, partitioning a dataset by "Department" might yield the exact same subgroups as partitioning by "Building." Existing algorithms treat these as distinct paradoxes, which inflates the number of reported findings, overwhelms the analyst with duplicate insights, and wastes computational resources.

Methodology: Formalizing and Exploiting Redundancy

To tackle this, the authors build a framework to identify and group redundant paradoxes based on three key pillars:

  1. Formalizing Redundancy: They define three specific ways paradoxes can be redundant: sibling child equivalence (different subgroup definitions cover the same records), separator equivalence (different attributes partition data identically), and statistic equivalence (perfectly correlated outcome labels).
  2. Concise Representation via Convexity: The authors prove that redundancy forms a mathematical equivalence relation. By mapping out all possible data subsets in a "population lattice," they show that populations with identical coverage form convex subsets. This means an entire group of redundant paradoxes can be represented simply by its "upper bound" and "lower bound" in the lattice, without needing to store or evaluate every single variation.
The population lattice structure where identical-coverage groups form convex subsets, enabling efficient summarization.
  1. Redundancy-Aware Algorithm: Instead of a brute-force search, they use a Depth-First Search (DFS) to materialize the data cube. The algorithm groups populations with identical coverage early on. During the paradox discovery phase, if a paradox falls into an already-discovered equivalence class, the algorithm skips evaluating its redundant variations entirely.

Evaluation and Results

The authors evaluated their framework on real-world datasets (Adult, Mushroom, Loan, CDC Diabetes) and synthetic datasets containing up to 30 million records.

Key Insights

  • Prevalence of Redundancy: Redundant paradoxes are widespread, making up 20.3% to 47.8% of all discovered paradoxes in real-world data.
  • Performance: The proposed algorithm achieved an average 6.72x speedup over brute-force baselines across the real-world datasets.
  • Pruning Impact: By introducing a tiny population pruning threshold (ignoring data subsets that cover less than 0.1% of the total records), the algorithm reduced run time by an additional 50%.
  • Scalability: The DFS-based materialization and redundancy-aware discovery allowed the algorithm to scale smoothly to synthetic datasets containing up to 30 million records.

Conclusion

Redundancy is a practical hurdle in automated data discovery. By leveraging the mathematical property of lattice convexity, the authors transformed a combinatorial explosion problem into a highly constrained search. Future work includes extending the framework to continuous variables and incorporating causal semantics to further refine the definitions of redundancy in practical domains like finance and healthcare.

Summary updated

BibTeX
@misc{yang2025finding,
  author = {Yi Yang and Jian Pei and Jun Yang and Jichun Xie},
  title = {{Finding Non-Redundant Simpson's Paradox from Multidimensional Data}},
  year = {2025},
  eprint = {2511.00748},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2511.00748},
}
Figure