💻 computer science

Triangle-Motif Proxy Entanglement in Markov Boundary-Based Fair Feature Selection: A Structural and Empirical Study

This paper demonstrates that in triangle-motif structures, the minimality and sufficiency guarantees of Markov Boundary-based feature selection can conflict with fairness goals by retaining high-utility proxies entangled with protected attributes, necessitating proxy-aware auditing before feature exclusion to avoid accuracy-fairness trade-offs.

Original authors: Roopa Maliakal, S. Asharaf

Published 2026-09-30

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Roopa Maliakal, S. Asharaf

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the high-stakes world of modern decision-making, from determining who gets a bank loan to deciding who is hired for a job, computer systems are increasingly tasked with making the call. These algorithms are designed to be accurate, but there is a growing demand that they also be fair, ensuring they do not discriminate against people based on protected characteristics like race or gender. To achieve this, data scientists often try to strip away sensitive information before the computer ever sees it. A popular method for finding the most useful information involves a concept called the Markov boundary. Think of this as a scientist's way of identifying the smallest, most essential group of clues needed to predict an outcome. If you have the right clues, you can predict the result perfectly without needing any extra, redundant data. The logic suggests that if you find this perfect, minimal set of clues and then simply remove the sensitive ones, you should be left with a model that is both accurate and fair.

However, a new study by researchers Roopa Maliakal and S. Asharaf from the Kerala University of Digital Sciences, Innovation and Technology challenges this straightforward approach. They investigated a specific, common situation where the clues needed to make a prediction are deeply tangled with the very information the system is supposed to ignore. The researchers found that in many real-world scenarios, the most useful predictors are not just loosely related to sensitive traits; they are structurally locked into the same pattern that makes them good at predicting the outcome. When researchers try to cut these "proxy" clues out of the system to ensure fairness, they often break the model's ability to predict accurately. The study suggests that simply removing a variable because it is linked to a protected group is not a neutral act; it is a trade-off that can cost the system its precision, and the cost is often higher than if a random, unrelated variable had been removed.

The researchers focused their attention on a specific shape of relationships between variables, which they call a "triangle motif." Imagine three points: a protected attribute, such as a person's gender; a target outcome, like their income; and a third variable, a proxy, such as their job title or hours worked. In this triangle, the job title is directly linked to the income, making it a vital clue for prediction. At the same time, the job title is also directly linked to gender, perhaps because of historical hiring patterns. Because the job title is so useful for predicting income and is not just a duplicate of the gender information, the computer's search for the "best" set of clues will naturally keep it. The researchers demonstrated that if you force the system to remove this job title to protect against gender bias, you are not just removing a sensitive link; you are removing a piece of the puzzle that the system genuinely needs to do its job.

To test this idea, the team did not rely on abstract theory alone. They built a controlled simulation where they knew exactly how the data was generated, creating these triangular relationships on purpose. In these simulations, they found that when they removed the proxy variable, the amount of useful information available to the computer dropped significantly. The system lost its ability to predict the outcome as well as it could before. This confirmed that the loss of accuracy was not a random glitch but a direct consequence of cutting a variable that was both predictive and entangled with the protected attribute. The study then moved to real-world data, using two large, well-known datasets about income: one from the UCI Adult dataset and another from the American Community Survey. They used two different, standard methods to find the "best" set of clues for predicting income, mimicking how a data scientist would normally work.

The results in the real world mirrored the simulations. The algorithms consistently kept certain variables, such as a person's relationship status, occupation, and hours worked, because these were the most reliable predictors of income. These variables were also highly correlated with protected attributes like sex and race. When the researchers then went back and manually removed these variables to try to make the model fair, the accuracy of the predictions fell. The drop in accuracy was not small or accidental; it was measurable and consistent across different types of computer models, including simple linear models and more complex, tree-based systems. In one dataset, removing the proxy variables caused a much larger drop in accuracy than if the researchers had simply removed a random set of unrelated variables. This proved that the cost was specific to the loss of the proxy information, not just a result of having fewer clues to work with.

The study also looked at whether removing these variables actually made the system fairer. The answer was complicated. In some cases, the gap between how different groups were treated did shrink, but in other cases, it did not change much at all. The improvement in fairness depended heavily on which specific measure of fairness was being used and which computer model was running the show. This inconsistency highlights a difficult reality: there is no single switch to flip that makes a model both perfectly accurate and perfectly fair when the data is this tangled. The researchers introduced a new tool called the Proxy Entanglement Penalty, which acts as a warning signal. It helps data scientists identify which variables are so deeply connected to both the outcome and the protected attribute that removing them will likely hurt the model's performance.

The authors are careful to state that their findings do not mean fair machine learning is impossible. Instead, they argue that the common practice of finding the best clues first and then trying to cut out the bad ones is flawed in these specific situations. If the clues needed for accuracy are the same ones that carry bias, a simple cut will not work. The study suggests that data scientists need to be more careful. Before they delete a variable, they should check if it is a vital piece of the puzzle that is just unfortunately linked to a sensitive trait. If it is, simply deleting it is likely to hurt the model's accuracy without guaranteeing fairness. The researchers recommend a more thoughtful approach where the decision to remove a variable is treated as a documented governance choice, weighing the loss of accuracy against the potential gain in fairness, rather than assuming that removing a variable is a harmless technical step.

Ultimately, this research reveals a structural tension in how we build fair algorithms. It shows that in many real-world economic settings, the information that makes a prediction good is often the same information that makes it unfair. The study provides evidence that trying to solve this by simply pruning the data is a blunt instrument that often fails. It calls for a shift in how we approach these problems, moving away from the idea that we can just delete the bias and keep the accuracy, and toward methods that might need to change the way the model learns or represents the data in the first place. The work serves as a reminder that in the complex web of human data, the lines between what is useful and what is unfair are often drawn in the same place, and cutting one without understanding the other can leave the whole system broken.

Technical Summary: Triangle-Motif Proxy Entanglement in Markov Boundary-Based Fair Feature Selection

Problem Statement
Markov Boundary (MB) discovery is a standard technique in causal feature selection, valued for identifying a minimal set of predictors that renders the target variable conditionally independent of all others. In fairness-aware machine learning, a common pipeline strategy involves first discovering the MB to ensure predictive sufficiency and minimality, and then applying post-hoc pruning to remove protected attributes ( $S$ ) and their proxies ( $P$ ) to satisfy fairness constraints.

This paper investigates a structural conflict inherent in this "MB-first, prune-later" approach. Specifically, it analyzes the triangle motif, a causal topology where a protected attribute $S$ and a proxy variable $P$ are both direct parents of the target $Y$ and are statistically dependent on each other. The core problem is that under standard causal assumptions (Causal Markov, Faithfulness, and causal sufficiency), the MB discovery process will retain $P$ because it provides non-redundant predictive information. However, removing $P$ post-hoc to ensure fairness violates the minimality and sufficiency guarantees of the MB, potentially causing a significant loss in predictive utility.

Methodology
The study combines theoretical formalization with empirical auditing across synthetic and real-world datasets.

Theoretical Framework:
- The authors define an MB-retained causal proxy as a variable $P$ that is in the Markov Boundary of $Y$ , is statistically dependent on $S$ , and contributes unique predictive information (non-redundant) within the boundary.
- Proposition 1 characterizes the triangle motif (configurations $S \to Y, S \to P, P \to Y$ or $S \to Y, P \to S, P \to Y$ ), proving that in these structures, $P$ is structurally retained in the MB and remains dependent on $S$ .
- Proposition 2 formalizes the Minimality–Sufficiency Compromise: removing an MB-retained, non-redundant proxy reduces the mutual information $I(Y; M)$ relative to the full MB set $M$ .
Proxy Entanglement Penalty (PEP):
- To diagnose this issue empirically, the paper introduces the Proxy Entanglement Penalty (PEP), defined as the conditional mutual information $I(Y; P | S)$ .
- PEP serves as a diagnostic metric to identify proxies that carry target-relevant information not explained by the protected attribute. High PEP values indicate that removing such a proxy is likely to be predictively costly.
Empirical Evaluation:
- Datasets: The study utilizes the UCI Adult and ACSIncome (Folktables) datasets for socioeconomic prediction tasks.
- Discovery Algorithms: Two causal discovery paradigms were tested: a constraint-based method (PC-Stable) and a score-based method (Hill Climbing with BDeu score, HC-BDeu).
- Stability Analysis: A stability sweep was conducted across 50 bootstrap samples, varying significance levels ( $\alpha$ ) for PC-Stable and maximum in-degree ( $d$ ) for HC-BDeu to measure how frequently proxy-relevant variables are retained in the estimated MB.
- Fairness–Utility Audit: The downstream impact of post-hoc proxy removal was evaluated using Logistic Regression, Random Forest, and Gradient Boosting. Performance was measured via accuracy, while fairness was assessed using Demographic Parity Difference (DPD), Demographic Parity Ratio (DPR), Equalized Odds Difference (EOD), and Equalized Odds Ratio (EOR).
- Ablation: A random non-proxy removal baseline was used to distinguish the cost of removing specific proxies from the generic cost of reducing feature count.

Key Contributions

Triangle-Motif Proxy Retention: The paper formally identifies that in triangle motifs, the structural adjacency of a proxy to the target ensures its retention in the MB, even when it is statistically entangled with a protected attribute.
Minimality–Sufficiency Compromise: The work establishes that in these topologies, the goals of MB minimality (predictive sufficiency) and fairness-driven proxy suppression are structurally in tension. Removing an entangled proxy from an MB-based set inevitably reduces predictive information relative to the MB reference.
Proxy Entanglement Penalty (PEP): The introduction of PEP as an information-theoretic diagnostic tool for prioritizing proxies that are both stable in the MB and costly to remove.
Empirical Validation: The study demonstrates that high-utility proxy variables (e.g., relationship, occupation, education) are repeatedly and stably retained by MB discovery algorithms. Post-hoc pruning of these variables consistently results in measurable accuracy reductions, while fairness improvements are inconsistent and metric-dependent.

Results

Stability: In the UCI Adult dataset, the variable relationship showed high selection stability (0.913 under PC-Stable, 1.000 under HC-BDeu). In ACSIncome, variables like OCCP, SCHL, WKHP, and RELP exhibited near-perfect stability, even when the protected attribute SEX was not selected into the MB.
Predictive Cost: Removing these stable proxies resulted in significant accuracy drops. For ACSIncome, proxy removal caused accuracy reductions ranging from approximately 12.99% to 13.41% compared to the MB reference. Notably, the gap between the accuracy reduction caused by proxy removal versus random non-proxy removal was approximately 11.05 to 13.26 percentage points, indicating that the predictive cost is specifically associated with removing target-relevant proxy information rather than merely reducing feature count.
Fairness Trade-offs: While proxy filtering often reduced disparity metrics like DPD and EOD (indicating improved fairness in terms of difference), the improvements were not uniform across all classifiers or metrics. The study found that fairness gains came at the cost of predictive utility, and the magnitude of these gains varied by model family and metric.
Synthetic Validation: Controlled experiments confirmed that in triangle motifs, excluding the proxy $P$ leads to a reduction in aggregate mutual information, validating the theoretical cost of the minimality–sufficiency compromise.

Significance and Claims
The paper claims that its findings are specific to the triangle topology and rely on standard causal assumptions; it does not assert that fair feature selection is impossible, nor does it claim that all MB-based pipelines fail. Instead, the significance lies in exposing a theoretical limitation of the "MB-first, prune-later" pipeline template.

The authors argue that in structurally entangled settings, MB discovery should not be treated as a fairness-neutral starting point. Because the MB retains proxies that are essential for predictive sufficiency, simply pruning them post-hoc creates a trade-off between accuracy and fairness. Consequently, the paper advocates for proxy-aware auditing before feature exclusion. Practitioners are advised to use diagnostics like PEP and stability analysis to identify high-cost proxies. If such proxies are identified, the paper suggests that fairness interventions should move beyond simple feature exclusion toward methods that directly modify dependency structures, such as constrained modeling or representation learning, rather than relying on post-hoc pruning of MB-derived feature sets.

Technical Summary: Triangle-Motif Proxy Entanglement in Markov Boundary-Based Fair Feature Selection

More like this