Counterfactual Fairness with Graph Uncertainty

Davi Valério, Chrysoula Zerva, Mariana Pinto, Ricardo Santos, André Carreiro · 2026

Read Counterfactual Fairness with Graph Uncertainty by Davi Valério, Chrysoula Zerva, Mariana Pinto, Ricardo Santos, André Carreiro (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-03203.txt.

Introduction

Davi Valério and four co-authors make fairness audits of machine learning models honest about a hidden assumption: the causal graph they rely on. Counterfactual fairness judges bias through a causal model of how data were generated, but in practice that graph is rarely known for sure. Their procedure, CF-GU, folds the uncertainty about the graph into the audit itself.

The method bootstraps a causal discovery algorithm under domain knowledge constraints to produce a bag of plausible graphs. It measures the spread with normalized Shannon entropy, and reports confidence bounds on the fairness metrics. On synthetic data, different knowledge assumptions can support or refute an audit's conclusion. On the real COMPAS and Adult datasets, the method pinpoints well-known biases with high confidence, even from minimal domain knowledge.

Catalog record

CREATORDavi Valério, Chrysoula Zerva, Mariana Pinto, Ricardo Santos, André Carreiro
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE37 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-03203

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Counterfactual Fairness with Graph Uncertainty Davi Valério, Chrysoula Zerva, Mariana Pinto, Ricardo Santos, André Carreiro Abstract Evaluating machine learning (ML) model bias is key to building trustworthy and robust ML systems. Counterfactual Fairness (CF) audits allow the measurement of bias of ML models with a causal framework, yet their conclusions rely on a single causal graph that is rarely known with certainty in real-world scenarios. We propose CF with Graph Uncertainty (CF-GU), a bias evaluation procedure that incorporates the uncertainty of specifying a causal graph into CF. CF-GU (i) bootstraps a Causal Discovery algorithm under domain knowledge constraints to produce a bag of plausible Directed Acyclic Graphs (DAGs), (ii) quantifies graph uncertainty with the normalized Shannon entropy, and (iii) provides confidence bounds on CF metrics. Experiments on synthetic data show how contrasting domain knowledge assumptions support or refute audits of CF, while experiments on real-world data (COMPAS and Adult datasets) pinpoint well-known biases with high confidence, even when supplied with minimal domain knowledge constraints. † † footnotetext: Peer reviewed pre-print. Presented at the BIAS 2025 Workshop at ECML PKDD. 1 Introduction Evaluating the bias of machine learning (ML) models is a critical step in building trustworthy, fair, and robust ML systems [ 3 ] . The Counterfactual Fairness (CF) criterion is an individual-level metric designed to assess bias of ML models [ 11 ] . According to this criterion, an ML classifier is considered fair if its prediction is the same for an original data point and a counterfactual sample, where the protected attribute (e.g., race or gender) was changed (Section 2.2 ). CF provides a more detailed perspective on discrimination rather than group fairness metrics, such as Demographic Parity [ 18 ] , by explicitly integrating domain knowledge into Structural Causal Models (SCMs). This causal framework supports the understanding of underlying reasons for discriminatory outcomes and can identify biases that aggregate metrics may overlook [ 10 ] . To illustrate CF, consider a scenario inspired by the Dutch childcare benefits scandal [ 7 ] . Suppose a tax authority uses an ML model to predict the probability \hat{Y} that an individual has committed fraud based on their income I\in[0,1] , and assume we aim to evaluate whether the classifier discriminates based on nationality N\in\{\text{local}=1,\text{immigrant}=0\} . Under this scenario, we could hypothesize that nationality influences income and formalize this notion with the SCM: N\xrightarrow{}I\text{, with }I(N)\coloneq 0.5+0.2N+U_{I}\text{ and }N\coloneq U_{N} where U_{I} and U_{N} are drawn from a Gaussian and a Bernoulli distribution, respectively. In this framework, consider Bob, who is local ( N=1 ), has high income ( I=0.9 ), and receives a low predicted probability of fraud ( \hat{Y}=0.2 ). The classifier satisfies CF if Bob’s immigrant counterfactual ( N=0,I=0.7 ) also receives a similarly low \hat{Y} . Although this SCM has only two nodes, real-world applications may have hundreds of variables. In these cases, Causal Discovery (CD) methods can be used to find causal graphs from observational data [ 8 ] . Despite its advantages, the application of CF faces one major limitation. Its results depend on a single, fully specified causal graph. However, practitioners are rarely sure of the complete graph. Instead, there may be consensus about forbidden or required causality relationships between some of the features, while many other possible connections remain uncertain. We argue that this uncertainty should be quantified and incorporated into the CF audit. Our approach (i) leverages CD algorithms with domain knowledge restrictions, such as causal ordering, forbidden and required edges, to enumerate a bag of DAGS that respect the constraints defined by a practitioner. We then (ii) measure the entropy of the bag of DAGs to evaluate the uncertainty of the CD algorithm, and finally (iii) provide confidence bounds on the CF audit results to evaluate the uncertainty of the assessment’s conclusions. Therefore, instead of auditing CF with respect to a single graph, we audit if a model is fair with respect to a set of domain knowledge restrictions and provide reliability indicators for the audit. Concretely, in this work, we: 1. Propose CF with Graph Uncertainty (CF-GU), a procedure to measure and incorporate the uncertainty of graph specification with CD into CF assessments. Our approach enables the computation of dispersion metrics, informing practitioners about the reliability of a CF audit (Section 3 ). 2. Demonstrate that our method improves the reliability of CF assessments in empirical validation using the COMPAS [ 2 ] and Adult Census [ 4 ] datasets (Section 4 ). 2 Background 2.1 Structural Causal Models An SCM M formalizes our beliefs about the causal relationships between variables of a dataset [ 14 ] . It consists of two sets of variables \bm{U} and \bm{V} , and a set of functional assignments \bm{F} that assigns each variable in \bm{V} a value based on the other variables of the model. The variables in \bm{U} are called exogenous variables, and represent unmeasured noise, while the variables in \bm{V} are endogenous, measured features. If we know the value of every exogenous variable, we can determine the values of every endogenous variable using the functions in \bm{F} . SCMs can be represented by graphical causal models. We restrict ourselves to directed acyclic graphs (DAGs), which are graphs where all the edges between nodes are directed and do not contain any cycles. In a DAG, if a variable X is the child of another variable Y , then Y is a direct cause of X . To illustrate, recall the fraud example from Section 1 . The endogenous variables are \bm{V}=\{N,I\} , the exogenous are \bm{U}=\{U_{N},U_{I}\} , the functional assignments are I(N)=0.5+0.2N+U_{I} and N=U_{N} and the implied DAG is N\xrightarrow{}I . Interventions can be computed from an SCM, where we alter the SCM to measure causal effects [ 14 ] . We intervene on a variable by “cutting” its incoming edges and fixing its value. For example, in an SCM M with the DAG (A\xrightarrow{}B\xrightarrow{}C\xleftarrow{}D) , we can fix the variable B:=b , which yields the modified model M_{B:=b} with DAG (A\quad B\xrightarrow{}C\xleftarrow{}D) . In this section, we have presented interventions, which will be used when estimating counterfactuals. 2.2 Counterfactuals With an SCM, we can compute counterfactuals [ 14 ] . Counterfactuals are “what-if” statements, in which the “if” portion is a hypothetical condition. For example, “what would be the value of Y if X had been x_{1} instead of x_{2} ” is denoted by Y_{x_{1}}(u) , where u is the noise’s value when X=x_{2} . To calculate counterfactual quantities, we follow three steps: (i) abduction, (ii) action, and (iii) prediction. In the abduction step, we obtain an initial condition by updating the exogenous variables \bm{U} under evidence e . In the fraud example, our evidence was Bob’s nationality and income value (N=1,I=0.9) . With this evidence, we calculated the exogenous variables’ values that fully describe Bob (the initial state): U_{N}=N\text{ and }U_{I}=I-0.5-0.2N, yielding (U_{N}=0,U_{I}=0.2) . In the action step , we intervene on some variable of interest to apply the hypothetical condition in the model. In the example, we intervened on the nationality N:=1 . Finally, the prediction step calculates the value of the other variables in the model, given the initial condition and the intervention. In the example, we

Read the complete text