[Paper] Counterfactual Fairness with Graph Uncertainty

Source: arXiv - 2601.03203v1

Overview

The paper introduces Counterfactual Fairness with Graph Uncertainty (CF‑GU), a new way to audit machine‑learning models for bias when the underlying causal structure is not known exactly. By explicitly accounting for uncertainty in the causal graph, the method delivers more reliable fairness assessments that can be trusted in real‑world deployments.

Key Contributions

• Graph‑aware fairness auditing – Extends counterfactual fairness (CF) to handle a distribution of plausible causal graphs rather than a single assumed graph.
• Bootstrapped causal discovery – Uses a causal discovery algorithm constrained by domain knowledge to generate a “bag” of candidate DAGs, capturing structural uncertainty.
• Quantitative uncertainty metric – Introduces normalized Shannon entropy to measure how much disagreement exists among the candidate graphs.
• Confidence‑bounded CF metrics – Provides statistical confidence intervals for standard CF scores (e.g., counterfactual disparity) that reflect graph uncertainty.
• Empirical validation – Demonstrates on synthetic data how different knowledge assumptions affect audit outcomes, and on real‑world datasets (COMPAS, Adult) shows the method can pinpoint known biases with high confidence even with minimal prior knowledge.

Methodology

1. Domain‑knowledge constraints – Practitioners supply a few high‑level causal assumptions (e.g., “age cannot be caused by gender”).
2. Causal discovery with bootstrapping – A standard causal discovery algorithm (such as PC or GES) is run repeatedly on resampled data, each time respecting the supplied constraints. This yields a collection of plausible DAGs.
3. Graph uncertainty quantification – For each edge, the frequency of its appearance across the DAG bag is computed; the normalized Shannon entropy of these frequencies serves as a single scalar summarizing overall uncertainty.
4. Counterfactual fairness evaluation – For every candidate DAG, the usual CF metric (difference in model prediction under a counterfactual change to the protected attribute) is calculated.
5. Confidence bounds – The distribution of CF scores across the DAG bag is used to construct confidence intervals, giving a range within which the true fairness measure likely lies given the graph uncertainty.

The pipeline is deliberately modular: any causal discovery tool and any CF metric can be swapped in, making the approach adaptable to different domains and fairness definitions.

Results & Findings

• Synthetic experiments – When the true causal graph is known, CF‑GU’s confidence intervals tightly enclose the ground‑truth CF score. When the imposed domain knowledge is too weak or contradictory, the entropy rises and the intervals widen, correctly signaling low confidence in the audit.
• COMPAS dataset – Even with only a handful of constraints (e.g., “prior convictions precede recidivism”), CF‑GU identifies a statistically significant unfair impact of race on risk scores, matching prior forensic analyses.
• Adult income dataset – The method flags gender‑related disparity in predicted income with narrow confidence bounds, despite the causal graph being largely ambiguous.
• Across both real datasets, the normalized entropy stays modest (≈0.2–0.35), indicating that a small amount of domain knowledge is sufficient to narrow down plausible graphs and produce actionable fairness insights.

Practical Implications

• Robust fairness audits – Teams can now run CF checks without having to “guess” the exact causal graph, reducing the risk of false fairness claims.
• Iterative model improvement – The entropy measure tells engineers whether they need to gather more domain knowledge or data before trusting the audit, guiding data‑collection priorities.
• Regulatory compliance – Confidence‑bounded fairness metrics align well with emerging audit standards that require quantifiable uncertainty reporting.
• Tool integration – Because CF‑GU is built on off‑the‑shelf causal discovery libraries, it can be wrapped into existing ML pipelines (e.g., as a post‑training validation step in MLflow or Kubeflow).
• Cross‑domain applicability – From credit scoring to hiring algorithms, any setting where protected attributes interact with a complex causal web can benefit from this uncertainty‑aware approach.

Limitations & Future Work

• Scalability – Bootstrapping causal discovery on large, high‑dimensional datasets can be computationally intensive; the authors note the need for more efficient sampling or parallelization strategies.
• Reliance on domain constraints – While minimal constraints are sufficient in the experiments, poorly chosen or contradictory constraints could mislead the DAG bag generation.
• Single‑type fairness metric – The study focuses on counterfactual disparity; extending the framework to other fairness notions (e.g., demographic parity, equalized odds) remains an open avenue.
• Real‑world causal validation – Future work could integrate expert‑elicited causal priors or interventional data to further tighten the graph bag and reduce entropy.

Authors

• Davi Valério
• Chrysoula Zerva
• Mariana Pinto
• Ricardo Santos
• André Carreiro

Paper Information

• arXiv ID: 2601.03203v1
• Categories: cs.LG, cs.AI, cs.CY
• Published: January 6, 2026
• PDF: Download PDF