A Generic Framework for Conformal Fairness
Authors: Aditya T. Vadlamani
Anutam Srinivasan
Pranav Maneriker
Ali Payani
srinivasan parthasarathy
Venue: ICLR 2025 Poster (2025)
Keywords: Fairness
Conformal Prediction
Graph Neural Networks
Primary area: alignment, fairness, safety, privacy, and societal considerations

Abstract: Conformal Prediction (CP) is a popular method for uncertainty quantification with machine learning models. While conformal prediction provides probabilistic guarantees regarding the coverage of the true label, these guarantees are agnostic to the presence of sensitive attributes within the dataset. In this work, we formalize \textit{Conformal Fairness}, a notion of fairness using conformal predictors, and provide a theoretically well-founded algorithm and associated framework to control for the gaps in coverage between different sensitive groups. Our framework leverages the exchangeability assumption (implicit to CP) rather than the typical IID assumption, allowing us to apply the notion of Conformal Fairness to data types and tasks that are not IID, such as graph data. Experiments were conducted on graph and tabular datasets to demonstrate that the algorithm can control fairness-related gaps in addition to coverage aligned with theoretical expectations.

Published as a conference paper at ICLR 2025
A GENERIC FRAMEWORK FOR CONFORMAL FAIRNESS
Aditya T. Vadlamani 1,, Anutam Srinivasan 1,", Pranay Maneriker 2t, Ali Payani 3, Srinivasan Parthasarathy The Ohio State University ?Dolby Laboratories
Cisco Systems
ABSTRACT
Conformal Prediction (CP) is a popular method for uncertainty quantification with machine learning models. While conformal prediction provides probabilistic guarantees regarding the coverage of the true label, these guarantees are agnostic to the presence of sensitive attributes within the dataset. In this work, we formalize Conformal Fairness, notion of fairness using conformal predictors, and provide a theoretically well-founded algorithm and associated framework to control for the gaps in coverage between different sensitive groups. Our framework leverages the exchangeability assumption (implicit to CP) rather than the typical IID as- sumption, allowing us apply the notion of Conformal Fairesss data types and tasks that are not IID, such as graph data. Experiments were conducted on graph and tabular datasets demonstrate that the algorithm can control fairness-related gaps in addition to coverage aligned with theoretical expectations.
INTRODUCTION
Machine learning (MI.) models are increasingly used to make critical decisions in many fields of human endeavor, making it essential to quantify the uncertainty associated with their predictions. Conformal Prediction (CP) is a distribution-fii free framework (Vovk et al., (005) which produces
confidence sets with rigorous theoretical guarantees and has become popular in real-world applica-
tions (Cherian & Bronner 2020). Post-hoe CP allows for facile integration into ML pipelines and
applies to a wide variety of data types, including graph data (H. Zargarbashi et al. 2023 Huang
al. 2024). because of its weaker requirement of statistical exchangeability.
Relatedly, ensuring the fairness of machine learning models is vital for their high-stakes deployments in critical decision-making Biases affect ML models at different stages from data collection to al- gorithmic learning stages (Mehrabi et al.] 2021). During the data collection stage, measurement and representation biases can skew how each feature is interpreted, leading to inaccurate determinations by learning models. Algorithmic bias, caused by model design choices and prioritization of specific metrics while learning the model, can also lead to unfair outcomes. Many models inherit biases from historical outcomes (Kallus& & Zhou| Zhou||2088 2018 Dwork et al.) 2012) and inadvertently skew decisions to- wards members of certain advantaged groups (Mehrabi et al. (02T). These biases have led to several global actors proposing and requiring practitioners to adhere to certain fairness standards (Hirsch) et al. 2023). To facilitate ML pipeline and model adherence to socio-cultural or regulatory fairness standards, researchers have proposed methods to either construct fair-predictors (Alghamdi et al.) 2022 Creager et al. [019 Zhao et al. 2023) or audit fairness claims made by deployed machine
learning models (Ghosh et al. 2021| Maneriker et al., 2023 Yan Zhang 2022).
However, these efforts on fairness (predictors, auditing, and uncertainty quantification) primarily focus on binary classification, often implicitly relying on the independent and identically distributed (IID) assumption, and largely do not bridge fairness and uncertainty quantification. The need to both quantify uncertainty and ensure fairness considerations are met is critical. A few researchers have started to examine how to assess (and possibly improve) the prediction quality of unreliable models (Wang& & Wang 2024) while meeting socio-cultural or regulatory standards of fairness. However, these efforts are limited in that they either require knowledge of group membership at inference time (a somewhat impractical assumption) (Lu et al. 2022) or are model-specific (Wang & Wangl 2024).
Equal Contribution, "This work was done while the author was student The Ohio State University

---

Published as a conference paper at ICLR 2025
Key Contributions: We propose novel and comprehensive Conformal Fairesss (CF) Framework to redress these concerns.
First, we develop the theoretical insights that facilitate how framework leverages CP's distribution-free approach to build and construct fair uncertainty sets according to user-speeified notions of fairness. Our framework is not only comprehensive but also highly flexible, as it can be adapted to bespoke user-specified fairness criteria. This adaptability ensures that the framework can be customized to meet the specific needs of different users, enhancing its practicality and usability.
Second, the weaker (exchangeability) assumptions required by CP allow us to extend the utility of framework to fairnsss problems in graph models. Graph models, in particular, suffer from the homophily effect, which exacerbates inherent segregation due to node linkages and causes further biases in predictions (Current al. 2022; Dong al. 2023 He et al.) (023).
Third, we discuss how our approach serves as a fairness auditing tool for conformal predictors. This function is important as it allows one to verify model fairness, ensuring that fairness is not just theoretical concept but practical reality in predictive modeling.
Finally, we demonstrate the effectiveness of our CF Framework by evaluating fairness using multiple popular fairness metrics for multiple different conformal predictors on both real-world graph and tabular fairness datasets.
BACKGROUND
2.1 CONFORMAL PREDICTION
Conformal Prediction (Vovk et al. 2005) is a framework for quantifying the uncertainty of a model
by constructing prediction sets that satisfy a coverage guarantee. For expository simplicity, we will focus on split (or inductive) conformal prediction (CP) in the classification setting. Given calibration dataset, D calib = { (w),,)) }>) and a test point (In+1, 1n+1), where æ; E X = R and
Ya E y {o..... K- 1}. CP is used construct prediction set C(xx+1) such that:
S Pr(yn+1 E C((n++)) S - a n 1+1
where a E 10 is the coverage bound. Concretely, given a non-conformity score function n (y E y s(# v) {(()) is prediction set that satisfies Equation 1
X x RR let ((a) Quantile [(++))1-a)]; {s( y:) be the conformal quantile. Then
Evaluating CP: Coverage quantifies the true test time probability Pr Pr|yn+1 efficiency is the average test prediction set size, (G(a)((x+1)) Intuitively, there an inverse re- lationship between coverage and efficiency, as higher desired coverage is harder to achieve, the method may produce larger prediction sets to satisfy the guarantee. In CP, the only assumption made about the data is that Dealib U {( 1n+1) is exchangeable weaker notion than iid, enabling its use on non-iid data, including graph data.
while
Graph CP: In this work, focus the node classification task. Given attributed graph (V, VYE,X), X), where V is the set of nodes, & is the set of edges, and X is the set of node attributes. Let A be the adjacency matrix for the graph. Further, let y {0,.... K 1} denote the set of classes associated with the nodes. For E V, 2, E Rd denotes its features and ye E y denotes its true class. The task of node classification is learn model that predicts the label for each node given all the node features and the adjacency matrix, i.e., (X, v) + Yu- In the transductive setting, the entire graph, including test points, is accessible during the base model training. In this scenario, for any trained permutation-equivariaa function (e.g., GNN) trained on a set of training/validation nodes, the scores produced on the calibration set and test set are exchangeable, thus enabling CP to be applied (H. Zargarbashi et al. 2023 Huang et al. 2024h.
2.2 FAIRNESS METRICS
Group (or statistical) fairness requires individuals from different sensitive groups to be treated equally. Sensitive groups are subpopulations characterized by sensitive attributes, including gen-
2

---

Published as a conference paper at ICLR 2025
der, race, and/or ethnicity. Group fairness metries aim observe bias in the predictions of model between the different groups dataset. This work considers several popular faireess metrics, in- cluding equal opportunity, equalized odds, demographic parity, predictive equality, and predictive parity. For generality, we define the metrics for the multiclass setting with an n-ary sensitive at- tribute. Let y+ denote the set of advantaged lahels (e.g., "is_approved" in loan approval task), Y be the true label, and Y be the predicted label from a classifier. Let & be the set of all groups for the sensitive attribute(s). Table Al discusses the formal definitions of different faimess metrics considered in this work.
Achieving exact fairness (i.c., the equality in Table Al can be challenging or, in some cases, im- possible (Barocas et al. 2023). Often, regulatory requirements focus on the difference (or ratio) in probabilities between groups for any given positive label. This is achieved by ensuring the dif- ference (or ratio) meets a prespecified closeness criterion. For example, many regulatory bodies consider the Four-Fifths Rule (EEOC, 1979. Feldman et al., 2015), which asserts that the ratio of the selection probabilities between groups least 0.8.
3 CONFORMAL FAIRNESS (CF) FRAMEWORK
In this section, we propose a theoretically well-founded framework using conformal predictors to control for fairness disparity between different sensitive groups. The framework is motivated by adapting the standard CP algorithm to determine conditional coverage given a score threshold, X, for the prediction sets (i.e. 11) = {y E s(xn+1, 8) I ^}). Depending on the fairness cover- ages between groups and advantaged labels. The conditional coverages are leveraged to evaluate fairness is achieved for some closeness criterion for different fairness metrics. This is achieved by searching threshold space for an optimal threshold Aopt that achieves the closeness criteria. The framework also handles user-defined metrics as discussed in Section 3.4 thus controlling for quantities, potentially orthogonal to conditional coverage.
metric, fairness disparity refers to gaps in group-conde coup-conditional or group-and- mund-clas-cooddiiin
3.1 EXEMPLAR CONFORMAL FAIRNESS (CF) METRICS
For conformal fairness, we adapt popular fairness metrics defined for multiclass classification (shown in Table AT.. For standard point-wise predictions, faimess measures are concerned with the probability& a prediction is specific label (i.e., Y), given condition, i.e., X E ga. Y for Equal Opportunity, for a particular covariate (X, Y). We replace equivalence to the predicted value with set membership (ú E (X)) adapt these notions for prediction sets. The adapted conformal fairness metrics are Table
Table 1: Conformal Faimnsss Metries.
Demographic Stutistccaly Parity
(x(x) x |r((ECC((O) x= | Y x
Ps e (x(x) E Vea E G, vy c
Equal Opportunity
Pr Prrpee (x(x)
Y= = ex
<a Vea a E 9, vi y+
Predictive Equility
Pr(s E CAIX) Y Y F sa]
<e Vsa.
y+
Equalized Odds
Equil Opp Pied. Equality
Predictive Parity
p.(y a 8E0
Pr a (X Ysa. 96 E G. v9 ey
3.2 CONFORMAL FAIRNESS (CF) THEORY
Before presenting our framework, we first lay out the necessary theoretical groundwork. Detailed proofs in Appendix B
Group fairness metrics are evaluated on a subset of the population, defined by a condition the data (i..,, membership in group, true label value). For example, Demographic Parity is evaluated per group (X e 9a in definition), while Equal Opportunity is evaluated per group and true label (Y y, X 9a in definition). To formalize this notion, let M denote
Filtering D
3

---

Published as a conference paper at ICLR 2025
fairness metric (e.g. Equal Opportunity) and define Fas X x y x G y - {0.1) be filter function which maps a calibration point along with a group and positive label, (æ,, 9/s 9. y). to 0 or depending whether the condition for the faimess metric, M, is satisfied. For Equal Opportunity, Fas would instantiate to (EO Di, 5) = at; E 9 n = ø]- We can filter Dealib to be (galib(g.5)
(( yı) DDalib Fas (2ig, yb: 9- 9) 1). By doing so, provide guarantees regarding the conditional coverages as stated in Lemma 3.1
Lemma 3.1. For any (g: !) 9 Vt, calibrating on @ = (( W:) ( Vc, D. D) guarantees the following about the conditional cov- erage:
1
as Priya+1 Cx(xn+1) FMr U.t1.9..) 1| a+ [ (ealib(g.9)) +
The interval width is (Pealib
Vovk et al. 2005 Lei al. 2016) focused on the upper bound; however, the lower bound also necessary for our framework.
Prior work (Ding et al. 2024
Inverse Quantile:
Given an (1 cooveaae level, have that the (1-a)) (1-ax)-quantlee of the calibra- tion non-conformity scores is the appropriate threshold to achieve Equation [ For our framework, given a threshold, recover the coverage level. This can be done using the inverse X-quantile. {s(#,, M1) (æ,, 91) E Dealib,, the inverse
Formally, if (#n+1.3n+1) is a test point and Scalib
X-quantile given by
(A, Scalb) = Pr[s(#n+1, Mn+1) S ^| Pr(yn+1 E Cx(xx)1)].
Moreover, Q-1(A, Seath) ) is the coverage level for the label Vn+1- Lemma 3.2 asserts that the cover- age level is within bounded interval of length |eatis/+I*
Lemma 3.2. For A E [0, 1] and n [Dealibl.
E
[[s 91) S X]
E 1[s(, 91) S Al +1
< Pr[yn+1 Cx(xn11) $
(3)
n ++1
+
CF for Fixed Label: In standard CP, coverage is only evaluated for the true label, y/. However, for fairness evaluation, it is essential to balance disparity between groups for all positive labels (see Table AT So for conformal fairness evaluation, coverage needs to be balanced between groups for any given E y+, as seen in Table Lemma 3.3 asserts that we can perform CP using fixed label and get the same coverage guarantees.
Lemma 3.3. Equation holds if we replace {(x;, (()) with {(x;, 3)} for fixed ğ E y
Connecting Theory to the Framework: For a particular fairness metric, we filter the calibration set based on the conditional from T and achieve bounds the conditional coverage with Lemma 3.1 By Lemma 3.3] the bounds continue to hold when considering the conditional coverage for fixed positive labei. We use Lemma 3.2 perform inverse quantile compute the coverage under various À thresholds. With the coverages for fixed positive label and each sensitive group, we compute the worst pairwise coverage gap across the groups using the bounds given by Lemma 3.3 to evaluate and control fairness at the desired closeness criterion.
3.3 CORE CONFORMAL FAIRNESS (CF) ALGORITHM
Input: The input to the core CF algorithm (Algorithm T.. include the calibration set, Dealiby the set of labels ()?) and positive labels ()*+), the set of sensitive groups, G. closeness criterion, the threshold search space, A, fairness metric, M, and a corresponding filter function, FM-
Specifying c: In practice, the choice of closeness criterion, c, may not be in the hands of the prac- titioner but instead defined by a (external) regulatory framework. For example, for Demographic Parity and want that Vga, 96 G.
Priyn+1 (x(xx+1) In+1 go] Pr(y e Cx(#n+1) |xn-1 E gull <.
Choosing A: The algorithm accepts a user-provided search space, A, which avoids degen- erate thresholds and guarantee desirable conditions. For experiments, set A
4

---

Published as a conference paper at ICLR 2025
lÿ(a), max(S } ensuring that the optimal threshold, Aopt. is at least ((a)). Since Aopt 2 ((a),, the coverage increases for larger thresholds and still satisfies the 1 a coverage requirement. That is,
- S Pr Pr[u++ E (ala)) x Pr[ya+1 E CA (2n+1)]
Procedure: For each À A, we want to check if it balances the coverage between groups for all positive labels. So, for each (g. ū) E x y+, we use FM to filter Dealib (Line
Algorithm d and then compute the non-conformity scores, Scalibr (Line T2) With the inverse quantile,
the coverage level is computed at the À threshold on the scores (Line 14). We then compare the coverages for a fixed y y+ between groups and check if the worst-case disparity satisfies the desired closeness criterion (Lines 16 21), forming the set AM (Line[). We choose Aopt minx A (Line 3 to minimize the final prediction set size (i.e., get the best efficiency). When evaluating multiple fairness metrics simultaneously, for example with Equalized Odds, the framework can be used to construct the set of satisfying lambdas for Equal Opportunity and Predictive Equality, Ago and Arg respectively. Then, Aopt min {Ago I7 MAP.).
Algorithm Conformal Fairness Framework
1: procedure CANFORMAL..AARRNESSSE V. yt, t G. A, FM)
2: AM {A E A SATISFY LAMBBAALL V.y* G,,,
Optimize for faimess D Optimize for efficiency
3: Auge miny Aas
4: return Aopt
5:
end procedure
6:
7: procedure SATISEY LAMBDA V.y+& I, c.A, Far)
8: label coverages (
9:
widths (G.
for (g.W) W) E 9 x y* do Dralib(g.0) = [( yi) E Deatth (xi, 9.
11:
Stalhh {s(.., 34) (mx, Ve) E Dealib(g.5))
interval widths|[ 77] D Penlibi
Uses Lemma
14:
label label_coveragees((. 0)] Q (A, S
b Uses Lemmal 3.2
end for
for ÿ E y
Uses Lemma
17:
Ommin min [labee__oovergges((:
widthss 7)1)
18:
max (label mmaxlabellccoveragee cooeraggee((- vI))
19:
if Oraax
O'min then return False
20:
end if end for
21:
22:
return True
23:
end procedure
Using multiple A thresholds: We also consider classwise approach where choose Do Nopts....
Nopt ,
Xopt E [0, 1]x for each of the K classes. Nopt is only required to satisfy the closeness criterion for the 7th class. One can achieve this by setting y {ÿ} and repeating Lines 2 and Blin in Algorithm [ for each y This allows for smaller X to be chosen for most classes as they are no longer impacted by minority classes, which require larger threshold to meet the closeness criterion.
distinguishing feature of the CF framework is that it does not require group information in- ference time. Though one can choose different À for each (g. y) E G ) pair, in streaming (or online) settings, the sensitive attribute may unavailable. For example, loan applications may be race or gender-blind to enforce fairer judgment. In these settings, the CF Framework is not limited and provides group conditional coverage when group information is absent at inference time.
3.4 FRAMEWORK EXTENSIBILITY
Algorithm I directly applies to Demographic Parity, Equal Opportunity, Predictive Equality, and Equalized Odds. The following modifications are necessary to accommodate Disparate Impact, Predictive Parity, and some user-defined metrics.
5

---

Published as a conference paper at ICLR 2025
Disparate Impact: The standard criterion for Disparate Impact is the Four-Fifthe Rule applied to Demographic Parity. To control the conditional coverages for the Four-Fifths Rule, we only change Line 19 in Algorithm to check if (1 0maax / Qmin) < for 0.8.
Predictive Parity: Predictive Parity seeks to balance the Positive Predictive Value (PPV) between groups (Verma& & Rubin 2018). It differs from the other fairness metries in Table T as it is condi- rioned on membership in the prediction set. Given the objective of balancing conditional coverage, the conformal definition of Predictive Parity, and Bayes' Theorem, we get
Pr(ū E (xA( - V, X g.) E X E 9:
Pr|Y = -ellgggeeeeeeeee (x)), X
Pr(Y = D X E
(4)
Conditional Label Probability
Equal Opportunity over Demographic Parity
for JE E y and gs E G. A threshold, is guaranteed to exist for any y+ S y if e greater than the maximum pairwise total variation distance of the group-conditioned label distribution. This is formalized Theorem 3.4
WW gi) the label distribution conditioned on group membership. Then there exists such that for max(Drv((V (W,, Wj) i,j E (9..)..,111),, where Drv is the total variation distance the difference in Predictive Parity between groups is within c.
Theorem 3.4. Let W be a random variable for label distribution over V. Let Wi
In Equation the Equal Opportunity, Demographic Parity, and Conditional Label Probability terms lie within finite intervals. This allows us to compute an interval where conformal Predictive Parity holds and use the CF framework to identify values of that meet the coverage closeness criterion. Further theoretical details and the proof of Theorem 3.4 are provided in Appendix
To control for arbitrarily small values of e, we use the Predictive Parity Proxy-an example user-defined metric- defined in Equation 5
For all 9i E "GNJE>" E3T
Pr(Y = ū 5 (xC, - Pr(Y (
(5)
In cases where is possible to assume the label distribution is independent of group membership, Equation 4 can be directly controlled for an arbitrarily small closeness criterion, Proofs and technical details on these modifications can be found Appendix
3.5 LEVERAGING THE CF FRAMEWORK FOR FAIRNESS AUDITING
Using the Conformal Faimess Framework, between multiple groups violates a user-specified faimess criterion. Specifically, we have thus far focused on fairness criteria concerning bounding the disparity between groups using the fairness metrics described in Table T by some closeness criterion, c. It is straightforward to support user- defined fairness metrics concerning label coverage. While Algorithm [ as presented, gives method of finding an optimal À threshold which satisfies the fairness guarantees using Lemmas 3.1 3.2 and 3.3, the same SATISFY_LAMBDA procedure can leveraged to check if a given À used by conformal predictor satisfies the same fairness guarantees. Notably, the CF framework can also be leveraged even the conformal predictor is treated as a black- bbx model. In this case, we construct an Daudit set exchangeable with the calibration data used for the conformal predictor. Using Daudits we can determine if the conformal predictor satisfies the corresponding fairness guarantee given the fairness metric and the À threshold used.
audit if the disparity of conformal predictor
3.6 NON-CONFORMITY SCORES
There are several choices for the non-conformity score for performing fair conformal prediction with classification tasks. We currently implement TPS (Sadinle al. 2019). APS (Romano al.,
2020 RAPS (Angelopouios et al.] 2022). DAPS (H. Zargarbashi et al. 2023). and CFGNN (Huang al. 2024) in the CF framework, though any non-conformity score can be used. More details on the specifics of each non-conformity score can be found in Appendix D.2
A modified total variation distance, Dit (W, W5) suPkey+ [P[[W k] Pr(W, k]], can be used in place of Dry Theorem 3.4 for weaker assumption about e, which still gives a satisfying

---

Published as a conference paper at ICLR 2025
4 EXPERIMENTS
4.1 SETUP
Datasets: To evaluate the CF Framework, we used five multi-class datasets: Pokec-n TTakac & Zabovsky 2012). Pokec-z (Takac & Zabovsky (012), Credit (Agarwal et al. (02T), ACSIncome
(Ding et | 2021 and ACSEducation (Ding et al. 2021) (see Table for details). For each dataset,
use 30%/20% 20% 22%5%%%% 25% /25% stratified split of the labeled points for Durain/
Ptrain//Daaii /Dvatid/ Caand/Peatii /aatii Paaiii/Duue /Dusst.
Table 2: Dataset Statistics. T refers to Tabular, and G refers to Graph.
Name
Type
Size
# Labeled
Groups
# Classes
ACSIncome
T
1, 6666,, 500
ALL
race
4
ACSEducation
1, 664, 500
ALL
race
6
Name
Type
(IV), [E])
# Labeled
# Groups
# Classes
Credit
T/G
(30, 000, 1, 436, 858)
ALL 8, 797
age(2)
4
Pokee-n
(66, 569, 729, 129)
region (2), gender(2)
4
Pokec-z
(66, 569, 729, 129)
8, 797
region(2) 2), gender(2)
4
Models: For the graph datasets, we evaluated with GCN Kipf & Welling 2017), Graph- SAGE (Hamilton et al. 2017). or GAT (Veličković et al. 2018) as the base model (results reported for the highest performing base model). For Credit, & Guestrin 2016) (i.e., ignoring the graph structure) as we empirically observed this approach to outperform the graph neural network baselines in terms of efficiency for this dataset. The choice of ignoring edge information while training Credit on XGBoost does not prohibit us from using CFGNN or DAPS, which utilize the edge information. The conformal predictor requires the soft- max logits from the base model (i.e., XGBoostt but is otherwise model agnostic. For ACSIncome and ACSEducation, we used an XGBoost model. Each model's hyperparameters were tuned as discussed in Appendix D.3
additionally evaluated XGBoost (Chen
Baseline: For each dataset and CP non-conformity score, we built a conformal predictor to achieve a coverage level of = 0.9. Then, we assess fairness according to the specific fairness metric using the SATISFY_LAMBDA from Algorithm [ for = ((a))
We report the worst fairness disparity and efficiency. For Disparate Impact, the worst fairness disparity is the minimum (1 0max)/((1 - amin) across the positive labels. For the remaining metrics, we record the maximum O'max Qmiu across the positive labels.
Evaluation Metrics:
4.2 RESULTS
For each figure, parity across different thresholds, the bar plot for the worst fairness disparity using the CF Frame- work, and dot denote the desired fairness disparity. We report the average base performance for simplicity and readability of the figures. In every experiment, except for Figure the CF framework was better than the average base conformal predictor. We provide more granular version of Figure 2 with Figure where it is clear that the framework performs better for every closeness threshold.
a line indicate the base conformal predictor's average worst faimesss dis-
Controlling for Fairness Disparity: For different closeness thresholds, our CF Framework effec- tively controls the fairness disparity for several metrics compared the base conformal predictor. In Figure [inure[[and2] we can observe that in terms of fairness disparity, our CF Framework precisely (note step-wise change with e on violations) improves upon the baseline conformal predictor. As with al- gorithmic fairness, a trade-off is involved in that there is slightly worse efficiency. From Figure we continue to observe this for both standard and graph-based conformal predictors. Furthermore, if the base conformal predictor is already "fair" according to our fairness disparity criterion, then the CF Framework will report the results accordingly. This phenomenon is observed with the CFGNN results in Figure 2 where the CF Framework matches the bascline regarding both evaluation met- rics. This behavior of the CF Framework makes it suitable to leverage for black box fairness auditing (as noted previously). We present additional results, for example, the disparity results for the CF
7

---

Published as a conference paper at ICLR 2025
Framework without classwise lambdas in Appendix E Notably, the prediction set sizes more prominent due to selecting a larger À than the classwise approach (see Figure E3 vs Figure I.
Controlling for Disparate Impact: For Disparate Impact, we present results for the standard Four-Fifths Rule. In 3 we see that using the CF Framework can significantly improve the base conformal predictor for the Four-Fifths Rule. The disparate impact value far below the desired 0.8 for the base conformal predictor, sometimes even less than 0.4, as with Credit with TPS and ACSIncome dataset. Our framework, however, is close to the 0.8 value and in some cases surpasses it, like in Credit with CFGNN, with minor effects the efficiency for both datasets.
Table Four-Fifth Rule for Credit and ACSIncome. Our framework surpasses the base conformal predictor and achieves close to or exceeds the disparate impact value of 0.80. The means N/A.
APS
RAPS
TPS
CEGNN
DAPS Base
Base
CF
Base
CF
Base
CF
Base
CF
CF
Disp. Impact 0.646
0,821 0,586
0.768
0.252
0,922 0.922 0.539 0.809 2.558 2.202
0.793
Credit
Efficiency
2.326
2.513 2.326 2,509 2.268
2.202 2.254 2.526
Disp. Impact 0.397 0.797
0.387
0.790
0.356
0.798
ACSIncome
Efficiency 2.212
2.674 2.169 2.752 2.109 2.679
As discussed earlier, the CF Framework can support a va- riety of non-conformity scores, emphasizing the agnostic nature of our framework. We achieved effective results for conformal predictors with different underlying non-conformity score functions for all the experiments. Further results can be found in Appendix
Agnostic to Non-Conformity Score:
Contenans Cribtion
0.1
0.5
2.0
Clscrroaa Ciiaaion
A75
TPS
505
14,006
14.040
Figure I: ACSIncome. The left two plots are efficiency results, while the right two are the fairness disparities for (a) APS, (b) RAPS, and (c) TPS. In all cases, our framework gives results at or hetter than the desired threshold and better than the baseline.
Intersectional Fairness: When characterizing data points into groups, we are not limited to single sensitive attribute. In many applications, there can be multiple sensitive attributes (e.g., race and gender) that need to be considered. Our CF Framework is not limited to analyzing a single sensitive attribute. To demonstrate this, we experiment with the Pokec-n dataset. Pokec-n has two sensitive attributes, namely region and gender. We treat each combination of region and gender as a separate sensitive group and apply the CF framework to control for faimess disparities. Figure 3 shows that the CF framework improves upon the base conformal predictor regarding faireess disparity. This improvement is starker with the graph-based conformal predictors, CFGNN, and DAPS, seen in Figure 3 plots (b) and (c).
8

---

Published as a conference paper at ICLR 2025
ChONS
DAYS
BAPS
OOarE DAPS
COONS
BAPS
TPS
Figure 2: Credit. The top four plots efficiency results, while the bottom four the fairness disparities for (a) APS, (h) CFGNN, (e) DAPS, (d) RAPS, and TPS. In all cases, our framework achieves the desired coverage gap better than the baseline, with minor impact on efficiency.
A key challenge with intersectional faireess is the multiplicative increase in the number of groups (i.e., combinations of sensitive attributes and classes) that must be calibrated and evaluated. This increases the data requirements needed to satisfy the coverage guarantees discussed in Section 3.2
as these guarantees become harder to achieve when the size of D(g.y) decreases. This problem is exacerbated (in empirical results) for datasets with only few labeled points, such Pokec-n. For Pokec-n, using a standard data splít, the calibration set has around 2200 data points. The calibration set is then further split get the conditional positive label coverage for each positive label and group pair. This results in the calibration being done with sets of fewer than a few hundred points, which much lower than the suggested 1000 points in the literature (Angelopoulos Figure [3] the effect of this challenge is seen with the fairnsss disparity given by the CF Framework being slightly above the desired closeness threshold for c 0.1. Nevertheless, the guarantees still hold, even under intersectional fairness constraints.
Bates, 202T). In
01000
PALES
OLOW
Den,ar GLOW
0.55
8
PMUA
Pokec-n using both sensitive attributes. The top four plots are the efficiency results, while the bottom four are the fairness disparitics for (a) APS, (b) CFGNN, (c) DAPS, (d) RAPS, and (c) TPS. CFGNN (b) and DAPS (c) achieve the desired faimess coverage thresholds better than standard CP methods.
Figure 3:
As discussed, the CF framework is extensible to user-defined fairness notions. We consider the Predictive Parity Proxy in Equation 5] an example of a user's 's ability to provide reasonable fairness measure (Disparate Impact, above, is another example). An experiment on ACSEducation in Table g demonstrates we can control for arbitrarily small values of c, unlike the standard notion of Predictive Parity. Additionally, it empirically illustrates that we can control
Predictive Parity Proxy:

---

Published as a conference paper at ICLR 2025
for disparities of probabilities conditioned the prediction set. This metric can also be applied in the graph setting, as seen in Appendix
Table 4: ACSEducation. The worst-case fairness disparity, based on the Predictive Parity Proxy, with our method is below the desired threshold, while the average baseline disparity much higher (> 0.30) than all of the thresholds we consider.
Closeness Threshold (c)
0.05
0.10
0.15
0.20
Base (Average)
Max Fairness Disparity Efficiency
0.044
0.093
0,152
0.166
0.411
APS
3.662
3,236
3.049
3.008
2.982
RAPS Max Fairness Disparity
0.043
0.094
0.153
0.172
0.268
Efficiency
3.948 3.339
3.102
3.063
3.030
Max Fairness Disparity Efficiency
0.038
0.091
0.167
0.199
0.319
TPS
3.662
3.061
2.880 2.845
2.828
4.3 DISCUSSION AND RELATED WORK
Few prior efforts study fairness and conformal prediction (Wang et al. 2024 Lu al. 2022 Liu
iet al. (022). One line of work has focused on applying fairness notions toward CP problems for regression tasks, explicitly focusing on Demographic Parity (Liu al. 2022 and Equal Opportunity (Wang et al., 2024). Another line of work focuses applying the notion of Overall Accuracy Equality for CP (Lu et al., 2022). This effort considers a specific medical application of detecting
malignant skin conditions and applies group-balanced CP
(ook 2012).
orthogonal direction is on (group) conditional CP, Foygel Barber et al. (202T) provides a theoret- ical grounding for conditional CP, while Gibbs et al. (2023) considers the impact of covariate shift for conditional coverage under the L.D. assumption. Others Bastani et al. (2022); Jung et al. (2023) look at multivalid CP. which requires (1) group-conditional and (2) threshold-calibrant
coverage
guarantees - a distinct notion from Conformal Fairness. Deng et al. (2023) also introduces a gen- eralization for multi-calibration and how it relates to algorithmic fairness for conformal prediction, focusing on equalized coverage for regression.
Our work differs in its breadth and flexibility (i.e., support for several faimess metrics and non- conformity scores) and focus on classification. Some existing works represent specific instantia- tions in our framework (e.g.. Wann et al. (0224)). Others provide baselines for comparison (e.g., BatchGCP (Jung et al. 2023)), without our framework's 's theoretical guarantees for fairness. Ap- pendix E.6 contains more details on BatchGCP and results. The CF framework generalizes group- balanced CP to consider the notion of coverage for specific labels, thus allowing us to evaluate disparity based on classical fairness metrics in manner that does not require a priori knowledge of group membership at inference time, unlike many approaches listed above.
Lastly, CF can be used in fairness-critical domains where conditional conformal prediction is infea- sible, such as finance, which can have strict fairness requirements (Agarwal et al. 2021). and health care (Wang et al. 2024), where privileged information may be unavailable at inference time.
5 CONCLUSION
In this work, we formalize the notion of Conformal Fairness (CF) for conformal predictors and pro- pose a novel and comprehensive CF Framework. We provide theoretically grounded algorithm that can be used to control for the gaps in conditional coverage, defined based on different fairness metries, across sensitive groups. We conduct experiments on tabular and graph datasets, leveraging the exchangeability assumption of conformal prediction. We present results for CF based on vari- ous classical and user-defined fairness metrics on conformal predictors with various non-conformity score functions, including results on the framework's effectiveness in evaluating intersectional fair- ness with conformal predictors. We further describe how the CF framework can be practically leveraged for applications, including faimess auditing of conformal predictors. Future work could extend the framework to regression tasks and strengthen the theory by relaxing assumptions and exploring non-exchangeable settings.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
The authors acknowledge support from National Science Foundation (NSF) grant #2112471 (AI- EDGE) and a grant from Cisco Research (US202581249), Any opinions and findings are those of the author(s) and do not necessarily reflect the views of the granting agencies. The authors also thank the anonymous reviewers for their constructive feedback on this work.
REPRODUCIBILITY STATEMENT
In the spirit of reproducibility, the proofs for the theoretical aspects of our work can be found in Details of the experiments, including datasets, non-conformity scores, and hyperparameters, are provided in Appendix The source code available at com
Appendices B and C
ffairness
REFERENCES
Chirag Agarwal, Himabindu Lakkaraju, and Marinka Zitnik. Towards a unified framework for fair and stable graph representation learning. In Uncertainty Artificial Intelligence, pp. 2114-2124. PMLR, 2021.
Wael Alghamdi, Hsiang Hsu, Haewon Jeong, Hao Wang, Peter Michalak, Shahab Asoodeh, and Flavio Calmon. Beyond adult and compas: Fair multi-class prediction via information projection. Advances in Neural Information Processing Systems, 35:38747-388 008777777770, 2022.
Anastasios Angelopoulos, Stephen Bates, Jitendra Malik, and Michael I. Jordan. Uncertainty sets for image classifiers using conformal prediction, 2022. URL https://arxiy> httpa/iiiv..gggaaaa./a org/abs/
2009.14192
Anastasios N. Angelopoulos and Stephen Bates. A gentle introduction to conformal prediction
and distribution-free uncertainty quantification. CoRR, abs/2107.07511, 2021. URL https:
//axxivv.rg//ab///000..co
Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness and Machine Learning: Limitations
and Opportunities. MIT Press, 2023.
Osbert Bastani, Varun Gupta, Christopher Jung, Georgy Noarov, Ramya Ramalingam, and Aaron Roth. Practical adversarial multivalid conformal prediction. Advances Neural Information Processing Systems, 35:29362-29373, 2022.
Tianqi Chen and Carlos Guestrin. Xghoost: A scalable tree boosting system. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Min- ing. KDD '1,, pp. 785-794, New York, NY. USA. 2016. Association for Computing Machin- ery. ISBN 9781450342 doi: 10.114579336772.2939788 URL /ttt:ttt////::ttrrr
1145/2939 2939785
John Cherian and Lenny Bronner. How the washington post estimates outstanding votes for the 2020 presidential election. Retrieved September, 13:2023, 2020.
Elliot Creager, David Madras, Jömn-Hentte Jacobsen, Marissa Weis, Kevin Swersky, Toniann Pitassi, and Richard Zemel. Flexibly fair representation learning by disentanglement. In International conference on machine learning, pp.
PMLR, 2019.
Sean Current, Yuntian He, Saket Gurukar, and Srinivasan Parthasarathy. Fairegm: Fair link pre- diction and recommendation via emulated graph modification. In Proceedings of the 2nd ACM Conference on Equity and Access in Algorithms, Mechanisms, and Optimization, EAAMO '22, New York. NY, USA, 2022. Association for Computing Machinery. ISBN 978 178344779 doi: 3555287
10.1145/3551624335522222
URL htthttps: http://oo.........../...... 1111110..1111550 /rA.S//..................//../..
Zhun Deng, Cynthia Dwork, and Linjun Zhang. Happymap: A generalized multicalibration method.
In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), 2023.
Frances Ding, Moritz Hardt, John Miller, and Ludwig Schmidt. Retiring adult: New datasets for fair machine learning. Advances in neural information processing systems, 34:6478 14:6478-6490, 2021.
11

---

Published as a conference paper at ICLR 2025
Tiffany Ding, Anastasios N. Angelopoulos, Stephen Bates, Michael I. Jordan, and Ryan J. Tib- shirami. clansicoodiiional conformai prediction with many classes. In Proceedings of the 37th International Conference Neural Information Processing Systems, NIPS '23, Red Hook, NY, USA, 2024. Curran Associates Inc.
Yushun Dong, Jing Ma. Song Wang. Chen Chen, and Jundong Li. Fairness graph mining: A survey. IEEE Transactions Knowledge and Data Engineering, 35(10):10583-1066 2023.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd innovations theoretical computer science confer- ence, pp. 214-226, 2012.
The U.S. EEOC. Uniform guidelines employee selection procedures. March 1979.
Michael Feldman, Sorelle A. Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasub- ramanian. Certifying and removing disparate impact. In Proceedings of the 21th ACM SICKDD International Conference on Knowledge Discovery and Data Mining. KDD '15, pp. 259-2668, New York, NY, USA, 2015. Association for Computing Machinery. ISBN 9781450336642, doi: 00.11455278335582883311 URL http::://////// otg/10.0r0100.0 1145 72828882828822 22583288311.2211
Rina Foygel Barber, Emmanuel Candes, Aaditya Ramdas, and Ryan J Tibshirani. The limits of distribution-Fi free conditional predictive inference. Information and Inference: Journal of the
IMA, 10(2):455-483 2021.
Bishwamittra Ghosh, Debabrota Basu, and Kuldeep S. Meel. Justicia: A stochastic sat approach to formally verify fairness. Proceedings of the AAAI Conference on Artificial Intelligence, 35 (9):7554-756) May 2021. doi: 10. (0.16099aaii.v3519 w3t....199999 URL httpps://ojs..e. org/ index. wwtp://pp/AAAA/attt...
Isaac Gibbs, John Cherian, and Emmanuel Candès. Conformal prediction with conditional guar- antees. arXiv preprint arXiv:2305./200 2023.
Soroush H. Zargarbashi, Simone Antonelli, and Aleksandar Bojchevski. Conformal prediction sets for graph neural networks. In Andreas Krause, Emma Brunskill, Kyunghyun Cho. Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 12292-12318. PMLR, 23-29 Jul 2023. URL htttps://procest ngs m press/ html
22.02hh-aararbaan
William L. Hamilton, Rex Ying, and Jure Leskovee. Inductive representation learning on large graphs. CoRR, abs/1706.02216, 2017. URL htttt::///ax....o////bbbs 070110221666666616
02216
Yuntian He, Saket Gurukar, and Srinivasan Parthasarathy. Fairmile: Towards an efficient framework for fair graph representation learning. In Proceedings of the 3rd ACM Conference on Equity and Access in Algoritiums, Mechanisms, and Optimization, pp. 1-10, 2023.
Dennis Hirsch, Timothy Bartley, Aravind Chandrasekaran, Davon Norris, Srinivasan Parthasarathy, and Piers Norris Turner. Business Data Ethics: Emerging Models for Governing Al and Advanced Analytics. Springer Nature, 2023.
Kexin Huang, Ying Jin, Emmanuel Candès, and Jure Leskovec. Uncertainty quantification over graph with conformalized graph neural networks. In Proceedings of the 37th International Con- ference on Neural Information Processing Systems, NIPS '23, Red Hook, NY, USA, 2024. Curran Associates Inc.
Christopher Jung, Georgy Noarov, Ramya Ramalingam, and Aaron Roth. Batch multivalid confor- mal prediction. 11th International Conference on Learning Representations (ICLR), 2023.
Nathan Kallus and Angela Zhou. Residual unfairness in fair machine learning from prejudiced data. In International Conference on Machine Learning, pp. 2439-2448. PMLR, 2018.
12

---

Published as a conference paper at ICLR 2025
Thomas N. Kipf and Max Welling. Semi- Semi-supervised classification with graph convolutional net- works. In 5th International Conference on Learning Representations, ICLR 2017. Toulon, France, April 24-26. 2017, Conference Track Proceedings. OpenReview.net, 2017 2017. //openreview. net. formm? S
htRp:tts:
Jing Lei, Max Grazier G' GeSlll, Alessandro Rinaldo, Ryan Tibshirani, and Larry A. Wasserman. Distribution-Fri predictive inference for regression. Journal of the American Statistical Associ- ation, 113:1094- 2016. URL ott.o//ooootttt....../oaaaoooooo
www.smmitscchhoooooeeoeee arr. http:/oog//o/oaooecc/ooo
13741419
Richard Liaw, Bric Liang, Robert Nishihara, Philipp Moritz, Joseph E Gonzalez, and Ion Sto- ica. Tune: A research platform for distributed model selection and training. arXiv preprint 187.vv1807.05118 2018.
Meichen Liu, Lei Ding, Dengdeng Yu, Wulong Liu, Linglong Kong, and Bei Jiang. Conformalized fairness via quantile regression. Advances in Neural Information Processing Systems, 35:1 1561- 11572, 2022.
Tianci Liu, Haoyu Wang, Yaqing Wang, Xiaoqian Wang, Lu Su, and Jing Gao. Simfair: A unified framework for fairness-awand multi-label classification. Proceedings of the AAAI Conference on Artificial Intelligence, 37(12):14338 -41444338814666,,---1 Jun. 2023. doi: htt.////aaaa...31.22e.e...o AAAT http///AAA/rrriceeeeeeeee///////
URL
https::/ojss.o aaai wrweeidex.iiiiooooeooooeeooe.ee.
Charles Lu, Andréamne Lemay, Ken Chang, Katharina Höbel, and Jayashree Salpathy-Cramed Fair conformal predictors for applications in medical imaging. Proceedings of the AAAI Conference
on Artificial Intelligence, 36(1 12006-1201,, Jun. 2022. doi: 10. v361: 1.6111..2 .,41999, URL
https://ojs www.:osssaaaa...... aaai. org/ ht////ndxxxx http////ttaattiilel/////////////
Pranav Maneriker, Codi Burley, and Srinivasan Parthasarathy. Online fairness auditing through iterative refinement. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Dis- covery and Data Mining, KDD '23, pp. 1665-1676, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9798400701030.
doi: 10. 00.1145535803055559955.. URL
htttps://doi..o 1tt.://////..1113588000000
3599454
Ninarch Mchrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. A survey on bias and fairness in machine learning. ACM computing surveys (CSUR), 54(6):1-35, 2021.
Yaniv Romano, Evan Patterson, and Emmanuel Candes. Conformalized quantile regression. Ad- vances in neural information processing systems, 32, 2019.
Yaniv Romano, Matteo Sesia, and Emmanuel Candes. Classification with valid and adaptive cover- age. Advances in neural information processing systems, 33:3581-3591, 2020.
Julien Rouzot, Julien Ferry, and Marie-José Huguet. Learning optimal fair scoring systems for multi-class classification. In 2022 IEEE 34th International Conference on Tools with Artificial Intelligence (ICTAI), pp. 197-204, 2022. doi: (O09/CCAA15018.002222
Mauricio Sadinle, Jing Lei, and Larry Wasserman. Least ambiguous set-valued classifiers with bounded error levels. Journal of the American Statistical Association, 114(525):223 234, 2019.
Lubos Takac and Michal Zabovsky. Data analysis public social networks. In International scien- rific conference and international workshop present day trends of innovations, volume 2012.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks, 2018. URL htll:htt////aatt/ wwtp//ooogggaabbeoa /1100111011000 10903
Sahil Verma and Julia Rubin. Fairness definitions explained. In Proceedings of the international workshop
fairness, pp. 1-7, 2018.
Vladimir Vovk. Conditional validity of inductive conformal predictors. In Steven C. H. Hoi and Wray Buntine (eds.), Proceedings of the Asian Conference on Machine Learning, volume 25 of Proceedings of Machine Learning Research, pp. 475-490, Singapore Management University, Singapore, 04-06 Nov 2012. PMLR. URL https: httppss//prrceeeiinge mir press/v25/ vovk 12. 12.
13

---

Published as a conference paper at ICLR 2025
Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic learning in a random world, volume 29. Springer, 2005.
Fangxin Wang, Lu Cheng, Ruocheng Guo, Kay Liu, and Philip S. Yu. Equal opportunity of coverage in fair regression. In Proceedings of the 37th International Conference Neural Information Processing Systems, NIPS '23, Red Hook, NY, USA, 2024, Curran Associates Inc.
Ziyan Wang and Hao Wang. Variational imbalanced regression: Fair uncertainty quantification via probabilistic smoothing. Advances Neural Information Processing Systems, 36, 2024.
Tom Yan and Chicheng Zhang. Active fairness auditing. In International Conference on Machine Learning, pp. 24929 299222249622.. PMLR, 2022.
I-Cheng Yeh and Che-hui Lien. The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clients. Expert systems with applications, 36(2): 2473-2480, 2009.
Chen Zhao, Le Wu, Pengyang Shao, Kun Zhang, Richang Hong, and Meng Wang. Fair repre- sentation learning for recommendation: A mutual information perspective. Proceedings of the AAA/ Conference on Artificial Intelligence, 37((4)49111-99) --99, Jun. 2023. doi: 10. 10.11699/aai.v3774 25617. URL https://oj....aa..ro///////// wwwrggiiiex...e wttp:::ppppppppapaaaaaaa
14

---

Published as a conference paper at ICLR 2025
A FAIRNESS METRICS
As discussed in Section 2.2 exact fairness difficult to achieve. So, for many metrics, we want say something about the difference between groups. Formally, for Demographic Parity, may require that for some (small) c E (0, 1].
Pr Y
y X ga PPrp
x E go]
Vga Ib E $ <c
max BEyT
Similar requirements exist for the other fairness metrics.
Table Al: Fairness metrics formulations for multiclass classification (Rouzot al. 2022)
Metric
Definition
Demographic Stutistiall) Purty
Pr 8
Pr
X Vea Vy e
Equal Opportunity
Pr Y = Y X
=Pr Y x
Voa. E Vy y
Predictive Equality
Pr
n. E 8
=Pr[F x. mo]
Vec.
Equilized
Equal Opp. Equality
Predictive Parity
Pr(y= =y = X
Pr
E Vea 6, Vy y
B PROOFS
B. PROOF OF LEMMA 3.1
Lemma 3.1. For any (g. 9) 9 y+, calibrating on
(g.0) = ((x,, vi) (M, Vr. D) = =1 guarantees the following about the conditional cov- erage:
1
1- Prlya41 Cx(#a41) Far = (Daalib(aaa)
+
The interval width is (Pelit I11
Proof. The proof for the upper bound follows Ding al. (2024). where the test score s(2,+1 Mx++1) follows the distribution of scores in Dealib n R. thus holding the conditional coverage. The upper- bound guarantee directly follows/Roman suitably random way to tie-break equal scores.
al. (2019). assuming distinct non-conformity scores or
B.2 PROOF OF LEMMA 3.2
To prove Lemma 3.2 we use the following Lemma that stated in the proof of Theorem D.1 from Angelopoulos & Bates (2021):
Lemma B.1. Suppose you have n + exchangeable random variables Zı, Zz....,, Zny Zn+1. Then, Pr|Zat1 S [(k) = n+ for all S n, where Zn+1 is the test point.
Proof Sketch. Using Zi Zi...., Zn. you can form + intervals, (L, (1)), (Z(1), 4ml (Z())) Zi (Z(n): UT. where L and U are the lower and upper bounds the random vari- ables. Exchangeability gives that Zn+1 falls in any of the 1 intervals with equal prob- ability. Thus, Pr[Za41 & (uo) is the probability that it falls in the first k intervals giving us Pr|Zn+1 < Z(k)
&
m+T
Now using Lemma B.I we will prove Lemmal 3.2
Lemma 3.2. For E [0, and n = =Peeatbl
D 1[s v1) < Al n +1
Pr Cx(x EL 1|s(0,, v.) < A]+1 +1
(3)
n n+1
15

---

Published as a conference paper at ICLR 2025
Proof. Let s(z,, Va) for brevity. By Lemma B.1 have that Pr(Sn+1 S (())) Λ+ for all k n. Let k be s.t. 8(k) S I 8(4+1)- We then have that Pr(8n+1 8(4)) Pr(sn+1 A) s Pr(sn-1 S 8(++))). So,
n+1 Pr(sn+1 5) k ++1
k
+
Since $1,... $ Sn are known empirically, we have that h = Ei=1 1[s, S X]. Hence,
E 1/s S X] n n+1
Σ 1== 1 S +
Pr(sn+1 5A)
n
Since Pr[sn+t S = Pr|p++1 E Cx (2 we get Equation
B.3
PROOF LEMMA 3.3
Lemma 3.3. Equation holds if we replace {(x:; vi)) with {(x; ū)) for fixed ğ E Y
Proof. By computing q(a) Quantile [[a+1)]-=)]] {s( 17) (=) where ÿ is the fixed label.
Using the assumption of exchangeability have that s(x1, W), s (Z2, ū) ......... s(xn+1, D) is changeable sequence. Thus
Pr(s(ann1, 5, [(a)) <
(6)
n n
Equivalently,
1 Pr (Zn))) $ - n
C FURTHER DISCUSSION ON PREDICTIVE PARITY
Theorem 3.4. Let W be a random variable for a label distribution over y. Let W; W e g:) the label distribution conditioned on group membership. Then there exists X such that for c 2 max(DDv (w.(W,, W,) i E 19.......)], where DTv the total variation distance the difference in Predictive Parity between groups is within
Proof. Let A be the maximum value it can take on the threshold of the prediction set. Let y e y and Jm In G. Then,
Pr (x)
y y-y.
Pr Y =
(EC,(X), E 9m
Pr Y = E gm
Pr (X)x(X)
X
Pr Y = y
X E gm
since the numerator and the denominator are 1 due to the selection of X. Using the same argument for In and the definition of Dry the difference in Predictive Parities is:
Pr-y = X gm Pr Y
X E 9m S Dry (W... m: W.)
Since, Drv (Wm, m. Wn) < max LaxxDrv(1 (W,, WG) i E (1....,191) [9])] c, the choosen value causes the Predictive Parity difference to be less than c. Thus a solution exists for max(Drv( W,) i.j E fl..... (9).)..(9I))..
A modified total variation distance, Di (W, W,) supkey+ Pr[W, k] used in place of Dry Theorem 3.4 for weaker assumption about e, which still gives a satisfying X.
Pr(rr, K||, can be
16

---

Published as a conference paper at ICLR 2025
C.I ACHIEVING ARBITRARY CLOSENESS
We will further discuss the two methods for controlling for arbitrarily small values of c, depending on whether the label distribution is independent of group membership.
C.1.1 LABEL DISTRIBUTION INDEPENDENT GROUP MEMBERSHIP
Assuming independence, we have the following corollary of Theorem 3.4
Corollary C.1. Given a random variable, W, from a label distribution over y that is independent of group membership. then the Conformal Fairness Framework can find a X such that the disparity of Predictive Parity is within any c O.
Proof. Let W; ( 9:) be the label distribution condition on group membership. Using the independence assumption we get W Wi, Vi E (1...., G thus Drv (W; W2) 0, Vi, e
{I..... }. Hence, using Theorem 3.4 max W3) i.j j (.. 0. Thus a A can be found for any >> 0.
C.1.2 WITHOUT INDEPENDENCE ASSUMPTION
When independence cannot be assumed, then we propose a proxy for Predictive Parity that the Conformal Fairness Framework can use. We propose Predictive Parity Proxy as the balancing the quantity Pr(Y = E (x)), E go) - Pr(Y labels. Thus, for the framework, given a user-specified value for c, we want Vga, Ib 9, by E y+:
X E 9a) across all groups and positive
(Pr|Y y y E X E gal Pr[Y = y X E gal)
(Pr[[Y = E (x)x, e ml Pr(y = X 9b)l <c (8)
Observe that using À = sup A will make Equation g equal to zero, thus c can be arbitrarily small. Intuitively, this proxy balances the information provided about outcome if the label is in the prediction set, similar to Predictive Parity. Formally, if the label distribution is independent of group membership, then balancing the proxy would be the same as balancing Predictive Parity.
D ADDITIONAL EXPERIMENT DETAILS
D.1 DATASETS
Credit (G): The Credit dataset is from the UCI repository, and traditionally the binary target is to predict the existence of default payments (Yeh & Lien 2009). We used graph version of Credit as considered by Agarwal et al. (202T). To convert the dataset to a multi-class dataset, we used the education level (4 labels) the target and used gender as the sensitive attribute, as done by Liu et al. 2023).
Pokec- [n,z] (G): The Pokec dataset TTakac & Zabovsky 2012) a social-network graph dataset collected from Pokec, popular social network in Slovakia. Since several rows in the dataset are missing features, two commonly used subgraphs are the Pokec-z and Pokec-n datasets. The graphs have 4 labels, corresponding groups) and region (2 groups). Our experiments consider each attribute individually and intersec- tional fairness by creating attribute with 4 (2x2) groups
the fieldwork. They also have two sensitive attributes, gender (2
ACSIncome (T): In the faimess space, the American Community Services (ACS) datasets from the Polkkables library are widely used (Ding et al. 2021). For ACSIncome, we used the standard ACSIncome dataset in Foltables however, we divided the targets into 4 classes by evenly dividing the income into 4 brackets. Race the sensitive attribute and has 9 groups
ACSEducation (T): Similar to ACSIncome, we used the ACS data and selected the Education Level as our target. We broke the education level into 6 groups (did not complete high school,
17

---

Published as a conference paper at ICLR 2025
has high school diploma, has GED, started undergrad program, completed undergrad pro- gram, and completed graduate or professional school]. ACSEducation also uses race as a sensitive attribute.
D.2 NON-CONFORMITY SCORES
Let be a trained classification model with softmaxed output.
Threshold Prediction Sets (TPS) In TPS (Sadinle al. 2019), the score function is s(x; y) 1 - (())g. where (a) is the class probability for the correct class. This is the simplest method, which is also shown be optimal with respect efficiency (Sadinle et al. 2019).
Adaptive Prediction Sets (APS) The most popular baseline when comparing CP method is APS (Romano et al. 2019). The scoring function works by sorting the softmax logits in de- scending order and accumulating the class probabilities until the correct class is included. For tighter prediction sets, randomization is introduced through a uniform random variable. Formally, if 7 (1) 2 (2) 2 ... [())((-1)) a (O, 1), and Ty is the rank the correct label, then
s(x, v)
Σ (
un u
Regularized Adaptive Prediction Sets (RAPS) One drawback APS is that it can produce large prediction sets. |Angelopoulos et al. (2022) introduces a regularization approach for APS. Given the same setup and notation as APS, define a(., y) {e ((r) 2 (())))) Then,
5xx y)
Σ # (2)
u + v max((o(x, y) kreg), 0},
where y and kreg 2 0 are regularization hyperparameters.
Diffusion Adaptive Prediction Sets (DAPS) Graphs are rich with neighborhood information, with nodes tending be homophilous. Intuitively, this suggests that the non-conformity scores of connected nodes are also related. To utilize this observation. DAPS H. Zargarbashi et al. (2023) performs one-step diffusion update on the non-conformity scores. Formally, s(x y) a point- wise score function (e.g., APS), then the diffusion step gives new score function
s(æ, v) = (1 - 8)s(2,8) v) +
Σ WEN.
s(u, y),
W
where 8 e [0, 1] is diffusion hyperparamter and N₂, is the 1-hop neighborhood of æ.
Conformalized GNN (CFGNN) CFGNN Huang et al. 2024 is a GNN approach to graph CP. correlated between nodes with similar neigh-
The underlying observation is that the inefficiencies borhood topologies. Bearing this in mind, using the calibration set, second GNN trained to correct the scores from the base model optimize for efficiency through inefficiency loss func- tion Huang et al.] (2024) propose. The inefficiency loss function definition includes a pisnt-wise score function and can different for training and validation. For our experiments, we the score function to be APS and kept it consistent between training and validation.
D.3 HYPERPARAMETER TUNING
Hyperparameter tuning was done using Ray Tune (Liaw et al. 20188. For the Pokec.n and Pokec.2 datasets, hyperparameters for the base GNN models were tuned via random search using Table DI for each model type (i.e., GCN, GAT, and GraphSAGE) and for each choice of the sensitive attribute(s). For the Credit, ACS Income, and ACS Education datasets, the base XGBoost models tuned via random search using Table D2 for each choice of sensitive attribute(s).
18

---

Published as a conference paper at ICLR 2025
For Credit, Pokec_n, and Pokec_z, tune the hyperparameters for the CFGNN model via random search using Table D3 for each model type (c.g.. GCN, GAT, and GraphSAGE), for each dataset, and choice of sensitive attribute(s). We set Dealib Drest = Drrain v
All experiments were run on a single PI0O GPU.
In the interest of reproducibility, the source code for the CF Framework is provided in the supple- mentary material.
Table DI: Hyperparameter search space for the base GNN model for Pokec n and Pokec z. The last two rows are layer-type specific for GAT and GraphSAGE, respectively.
Hyperparameter Search Space
batch_size
64
Ir
loguniform( (10-1, 10-1)
{16, 32, 64, 128) {1,2, 4]
layers
dropout
uniform uniform(0.1,03. 0.81
heads
4, (mean, gen, pool, 1stm}
aggr_fn
Table D2: Hyperparameter search space for the base XGBoost model for Credit, ACS Education, and ACS Income.
Hyperparameter
Search Space
Ir
loguniform 10-1)
n. eesstimatooss
, ,500
max_depth
[2, . ,03
gamma
uniform 1)
colsample bytree
uniform (0.20r 1.0)
colsample bylevel
uniform ().25, 1.0)
colsample.bynoo
uniform 0).25, 1.0)
subsample
uniform (0.5, 1.0)
Table D3: Hyperparameter search space for the CFGNN model for Credit, Pokec.n n, and Pokec The last two rows are layer-type specific for GAT and GraphSAGE, respectively.
Hyperparameter Search Space
batch_size
64
Ir
loguniform( 10:0:ommmm011. (10-4, 10-1)
hidden channels
{16, 32, 64, 128) (1,2, 4}
layers
dropout r
uniform 0. mauniform(11-21 10a)
heads
[2 2]
aggr_fn
meean, gen, pool, Istm}
E ADDITIONAL RESULTS
Here we provide additional results and discourse for each dataset and experiment we discuss in the main paper.
19

---

Published as a conference paper at ICLR 2025
E.1 ACSEDUCATION
Below we include results for the ACSEducation dataset, which unique as has a greater number of classes and is custom dataset generated from the ACS datasets.
Closeness Criterion:
Emeclenc
Critarion:
RAPS
Efficlency
Dem Party
ErpOpp
Erdodds
Pred_Pq
Dem_Parity
ErLOpp
ErgOods
Dem_Parity Ba_Opp
Comparison of efficiencies when using the CF Framework without (top) and with (bottom) classwise lambdas. We observe that the efficiencies are better in the right plot. This is because Xetaswise (k is the number of classes), which causes fewer labels be included the prediction set, thus improving efficiency with the classwise approach. For some experiments, the faimess disparity is 0 (c.g. APS and RAPS in the no-classwise setting), because the framework is producing the full prediction set-the trivial which means the coverage of ÿ y is 1.00, thus causing the disparity to be 0.
Figure E1: ACSEducation.
Vi..... Auce classise
20

---

Published as a conference paper at ICLR 2025
Closeness Criterion:
0.05
0.1
0.15
0.2
APS
RAPS
TPS
Actual Faimess Disparity
0.4
0.2
0.1
Jam_Parity Eq Opp
EddOdds Pred Eq
Dem, Parity
Eq_Opp
Fo_ Fdddd
Pred_Fq Fq
Dam_ Parity
Ea, Opp
Eq Odds
Pred Eq
Closeness Criterion:
0.05
0.1
0.15
0.2
0.5
Faimess Disparity
0.3
Actual ActualFairess
0.1
Jem_Parity
Eq_Opp
Eq_Odds
Pred Fi
Dem, Paritay
Eo_Opp
Fa_Odds
Pred_Fq
Dam_Pank
Ea_Opp
Pred Eq_Odds
Comparison of fairness disparities when using the CF Framework without (top) and with (bottom) classwise lambdas. We observe that the fairness disparities are better in the left plot. This because using single λ. only the hardest-to-satisfy label will be around the coverage gap, unlike classwise which ensures all labels will or around the coverage gap. Since fewer labels have coverages around the coverage gap. for non-classwise in (left) the likelihood of being above the threshold is limited as opposed to the classwise approach (right).
Figure F2: ACSEducation.
21

---

Published as a conference paper at ICLR 2025
E.2
IMPACT OF CLASSWISE LAMBDAS
E.2.1
ACSINCOME
Closeness Criterion:
0.05
0.1
0.15
0.2
APS
RAPS
TPS
3.5
2.5
2.0
1.0
Dem Pariyy E4, 0pp
Ea, Oods
Pred Ee
Dem, Partty
Eq, Opp
Eq Odds
Pred Eq
Dem Parky
Ea, Opp
E4, Odds
Prod E4
Closeness Criterion:
0.05
0.1
Actual Fairerss Disparty
0.0
Dem_ Party
Eq_0pp
E2_06ds
Pr
DemuParty
Eq_0pp
Eq_Oods
Pred Ea
Dem_Parity
Eq.Opp
Eq_
Prod_Eq
Figure E3: ACSIncome. The efficiency (top) and fairness disparity (bottom) plots when using classwise lambdas. We observe the efficiency worse, the disparity control much better than using classwise
lambdas (see Figure
E.2.2
CREDIT
Aabllaames
Dem, Party FrpOpp
Fr.ddds FredFEs
Dem Party
EopOpe
Pred
Dem, Jarty FnLOrp
Ei.Odds
PredEE
0.5
RAPS
TP5
0.3
Dcm. Partiy
Ea, Oods
Frod Ba
Dan Partyy
Ddds
Pred.
Figure E4: Credit. A granular version of Figure which has bar over each value of rather than considering an average. This plot clarifies that the CF framework matches or exceeds the baseline conformal predictor's performance in fairness disparity.
22

---

Published as a conference paper at ICLR 2025
Clssenass Citter
Clsseees
2.0
0.4
CTGNN
CTIGNN
35
Dam. Partt
t0.90m 360
Te. 0dds
Tred Ea
Dam Parfy
Te,
Eq 0dd
Prid Fo
DAPS
BAPS
0.5
25
20
0.2
Purty
0.3
0.
Dam.
2e.0
Dem
10
TP5
0.5
TPS
2.2
022
2
Dam. Party
3po
5o 1d.0ss
Dam Party
Figure E5: Credit. The efficiency (left) and fairness disparity (right) plots when not using classwise lambdas. We observe that the efficiency worse, but the disparity control is much better than using classwise lambdas (see Figure 2
23

---

Published as a conference paper at ICLR 2025
E.3 IMPACT OF DIFFERENT POKEC SENSITIVE ATTRIBUTES
E.3.1 POKEC-N
Coseness Oiteronn
4.0
225
0.
00
Patt
Prd.Do
40
CHONN
CPONN
3.0
122
2.0
65
Dan./wity
62.9p ELO0Me
Ded.Dt
Dem AwrTV
Frnd.F
3.5
200
10
Den Juty
C4.55
bLO
Prdd Di
CemtTarcy
Co.Osp
Prod_E
255
10
0.0
400
225
Day. Party
EoLOals
Pre..00
Den Part
E3_O
Piot.E
Figure E6: Pokec-n. The elficiency (top) and fairness violation (bottom) plots when considering only gender sensitive attribute. Observe that baseline disparity here is smaller than the baseline intersectional faimess (see Figure 3. Thus, when controlling for 0.05 coverage, there is a minimal change in efficiency across all the non con--ooooomittyycm scores.
24

---

Published as a conference paper at ICLR 2025
Clssenass Citter
Clsseress
2.0
25
CTONN
CTIGNN
15
20
35
Dam. Party
$0.90 960
Te. 05ds
Tred D4
Dam Party
Te. 0p0
Dq 0dd0
Prid to
DAPS
DAPS
0,3
25
20
Dem, Paryy
0.
Dam.
2e.0
Dem
Phed
10
TP5
0.3
TPS
2.
Dom. Party
3po
5o Odd0ss
Dam Party
Se.
Eqg Odte
Figure E7: Pokee-n. The efficiency (top) and fairness violation (bottom) plots when considering only region the sensitive attribute. Compared to using gender in Figure HG when controlling 0.05, thus illustrating that exact performance will vary based on the sensitive attribute and group distribution.
the prediction sizes are larger for region
25

---

Published as a conference paper at ICLR 2025
E.3.2 POKEC-Z
Closness Citeeior
Cosseress Citteton
015
0.05
0..3
2.5
0.2
20
CFONN
0.0
Dem
Dem
Phed
10
DAPS
DAPS
255
Dam Party
Dent Party
Eo.0po
10
0.2
0.6
TPS
TPS
2.25
2.0
25
Dom. PafYy
$6.00 3p0
Te. O.dc
Fred Er
Dam Party
Te. Cpo
Eq. Od.
Prid, Fo
Figure ES: Pokec-z. The efficiency (top) and faimesss violation (bottom) plots when considering only gender the sensitive attribute. Unlike Pokec-n using gender (see Figure E6 find that the baseline unfair for several values exemplifying the auditing capabilities of CF framework. This result also demonstrates how fairness can vary at different localities since Pokec-n and Pakec-z are disjoint subgraphs of the same graph
26

---

Published as a conference paper at ICLR 2025
Clssenass Citter
Closeress
2.0
2.5
CTGNN
CIIGNN
15
20
35
Dam. Party
$0.90 360
Te. Odds
Tred D4
Dam Party
Te. 0p0
Dq 0dd0
Prid Fo
DAPS
BAPS
0.3
25
20
Dem,Put Party
0.
Dam.
2e.0
Dem
Phen
TP5
0.3
TPS
2.2
Dom. Party
3po
$o. O5ds
Dam Party De.
Figure E9: Pokce-z. The efficiency (top) and fairness violation (bottom) plots when considering only region the sensitive attribute. In these plots for 2 0.1, the baselines fair for all score functions except for TPS. The baseline TPS being 'unfair" c 0.1 suggests TPS sacrifices fairness for efficiency.
E.4 PREDICTIVE PARITY PROXY RESULTS
CPOWN
D25
Crlurin::
1210000
03
635
W60 PM
WMH. AuRky
PMTT
PiNt Paity
Figure E11: Pokec-z. Results using the Predictive Parity Proxy on a graph dataset. We can see that the CF Framework controls for this metric as well as or better than the base conformal predictor all values of and non-conformity scores.
27

---

Published as a conference paper at ICLR 2025
Diourrien Criaaion:
0.15
2.1
0.13
012
APS
Acuoa Fummzze Aigooii
3.0
2.5
4.0
0.1
6.5
8.0
Dem_Pettt
Cop OLU
CEGNN
3.5
3.0
52 sumoze Ouaae
0.2
2.5
1.0
6.5
Dum Parky
E1. Opo
Eq. O453
Prod
Dum, Terty
OAA
Prid,
4.0
DAPS
Aduaa Pimise Disoorfs
2.5
2.0
0.1
6.0
Dom Party
Cop
D4 Odds
3.5
Famis Duse/t
3.0
2.5
0.2
1.0
0.5
Dem, Parke
E1,999
Wat.5t
Dem Tartyy
Odds
Prad.
TPP
TPS
4.0
0.5
3.5
2.5
0.1
Partyy
E1 Opo
Eq Oszs
Prad
Dem Party
De. Cop
Eqg Odds
Figure E10: Pokec-z. Another example of intersectional fairness using both sensitive attributes of the Pokec- dataset. Like Pokec-n, find that the worst-case faimesss disparity is better than the bascline for the CF Framework. We reiterate that the challenge intersection fairness the multiplicative increase the number groups that must be balanced. Thus, intersection fairness would benefit from more calibration points.
28

---

Published as a conference paper at ICLR 2025
E.5 DISPARATE IMPACT RESULTS
Table El: ACSEducation. The CF framework significanlyy enhances fairness (increases the ratio close the desired 80% disparate impact rule), with cost efficiency. The classwise approach improves efficiency further while retaining a ratio near 80%.
ACSEducation
APS
RAPS
TPS
Classwise
Base
CF
Base
CF
Base
CF
Disp. Impact
0.011
0.799
0.014
0.791
0.019
0.804 5.705
False
Efficiency
2.982
5.662
3.031
5.658
2.828
Disp. Impact
0.011
0.781
0.014
0.761
0.019
0.797
True
Efficiency
2.982
4.727 3.031
4.724
2.828 4.744
Table E2: ACSIncome. The CF framework significantly enhances fairness (increases the ratio close the desired 80% disparate impact rule), with a cost efficiency. The classwise approach improves efficiency further while retaining ratio near 80%.
ACSIncome
APS
RAPS
TPS
Classwise
Base
CF
Base
CF
Base
CF
Disp. Impact 0.397
0,815 0.387
0.847 0.356
0.804 3.416
False
Efficiency
2.212
3.557 2.169
3.610
2.109
Disp. Impact
0.397 0.797
0.387
0.790
0.356
0.797
True
Efficiency
2.212 2.674
2.169 2.752
2.1 2.679
Table E3: Credit. For the Credit dataset, notice that the CF Framework improves the baseline for APS, RAPS, TPS, and DAPS. We find that the baseline for TPS performs the worst of the 4 methods regarding disparate impact. Interestingly, the CFGNN baseline, on the other hand, maximizes the disparate impact while having the best efficiency. CFGNN demonstrates a case where CF does not perform worse than the baseline since the baseline was already 'fair', also provides an example of where an audit via CF would find that the CFGNN conformal predictor is a priori fair.
Credit
APS
RAPS
TPS
CFGNN
DAPS
Classwise
Basc
CF
Base
CF
Base
CF
Basc
CF
Basc
CF
Disp. Impact 0.646
0.821
0.586
0.768 0,252
0.793 0.922
0.539
0.809
False
Efficiency
2.325
2,561
2.326
2.559
2.268
2.620
2,202
2.202
2.254
2.573
Disp. Impact
0.646
0.821
0.586
0.768
0.252
0.793
0.922
0.922
0.539
0.809
True
Efficiency
2.325 2.513
2.326
2.509
2.268
2.558
2,202
2.202
2.254
2.526
29

---

Published as a conference paper at ICLR 2025
Table E4: Pokec-n. For Pokec-n, the CF Framework improves the disparate impact of the base- line conformal predictor. Similar to the other fairness metrics, the disparate impact worsens when considering intersectional fairness and near or exceeds 80% when only one sensitive attribute considered (i.e., region or gender).
Pokec-n
APS
RAPS
TPS
CFGNN
DAPS
Classwise
Group
Basc
CF
Basc
CF
Basc
CF
Base
CF
Base
CF
Disp. Impact 0.798
0.802
0.793
0.811
0.777
0.796
0.784
0.797
0.800
0.806
False
Gender
Efficiency
2.465
2.565
2.434
2.648
2.343
2.494
2.636
2.838
2.474
2.639
Disp. Impact 0.798 Efficiency
0.802
0.793
0.810
0.777
0.796
0.784
0.797
0.800
0.806
True
Gender
2.465
2.473
2.434
2.457
2.343
2.358
2.636
2.666
2.474
2.494
Disp. Impact 0.814 Efficiency
0.823
0.820
0.829
0.803
0.814
0.916
0.918
0.822
0.831
False
Region
2.401
2.498
2.373
2.552
2.300
2.426
3.168
3.185
2.413
2.584
Disp. Impact 0.814 Efficiency
0.814
0.820
0.822
0.803
0.806
0.916
0.917
0.822
0.824
True
Region
2.401
2.430
2.374
2.404
2.300
2.332
3.168
3.180 2.413 2.437
Region Gender
Disp. Impact 0.718 Efficiency
0.792
0.723
0.774
0.716
0.785
0.602
0.812
0.720
0.787
False
2.485
3.037
2.435
3.012
2.341
2.970
2.537 3.563 2.509
2.991
Region Disp. Impact 0.718
0.767
0.723
0.760
0.716
0.754
0.602
0.779
0.720 0.764
True
Gender Efficiency
2,485
2.739
2.435
2.656
2.341
2.566
2.537
2.964
2.509 2.709
Table E5: Pokec-z. For Pokec-z, the CF Framework improves the disparate impact of the base- line conformal predictor. Similar to the other faimess metries, the disparate impact worsens when considering intersectional fairness and is near or exceeds 80% when only one sensitive attribute is considered (i.e., region or gender).
Pokec-z
APS
RAPS
TPS
CEGNN
DAPS
Classwise
Group
Base
CF
Base
Base
Base
CF
Base
CF
Disp. Impact 0.798
0.802
0.737
0.800
0.737
0.800
0.784
0.797 0.800
0.806
False
Gender
Efficiency
2.523
2.995
2.489
3.088
2.327
3.134
2.512
3.388
2.522
2.996
Disp. Impact 0.798
0.802
0.737
0.800
0.661
0.742
0.784
0.797
0.800
0.806
True
Gender
Efficiency
2.523
2.572
2.489
2.571
2.327
2.415
2.512
2.642
2.522
2.579
Disp. Impact 0.807
0.823
0.796
0.826
0.812
0.816
0.781
0.796
0.811
0.829
False
Region
Efficiency
2.429
2.569
2.369
2.592
2.337
2.497
2.546
2.644
2.416
2.586
Disp. Impact 0.807
0.815
0.796
0.800
0.812
0.816
0.781
0.796
0.811
0.813
True
Region
Efficiency
2.429
2.475
2.369
2.403
2.337
2.391
2.546
2.603
2.416
2.453
Region
Disp. Impact 0.658
0.787
0.661
0.770
0.640
0.785
0.590
0.806
0.658
0.768
False
Gender
Efficiency
2.408
3.173
2.359
3.214
2.265
3.175
2.512
3,471
2.409
3.133
Region Disp. Impact 0.658 0.773
0.661
0.742
0.640
0.745
0.590
0.800
0.658
0.749
True
Gender Efficiency
2.408 2.799
2.359
2,741
2.265
2.627
2.512
2.788
2.409
2.743
30

---

Published as a conference paper at ICLR 2025
E.6 COMPARISON WITH BATCHGCP
To produce conformal prediction sets with group-wise coverage, BatchGCP (Jung et al. 2023) learns group-dependent threshold function provide
coverage for the correct label i.e. Pr [/++1 E (( 1:A) (Zn+11) 1) [n++1 E 5 =1 Vy' E G. To achieve this, a group-dependent
threshold function, farn+1; A), in Equation is used to construct prediction sets by adding cor- rection to the base threshold function f():). For the scoring functions considered (i.e., APS), we
define f()) = ς((a) as the - quantile of the calibration scores. À E I is vector with Ag corresponding to the entry for the g' group. The groups, g', may intersect, allowing for xn+1 to be part of multiple groups.
f(x) + Eg e g'EG
(9)
To determine the value of X. Jung et al. 2023) solve the convex optimization problem 10, where Lg is the pinball loss (Equation 11 function used to determine how close threshold, f(z; A), is to specific quantile, 1 a, for given score, Using the pinball loss, X the optimal À is computed and used to construct prediction sets.
X argmin E Ly ((xx))
(10)
(T_ =
s)al <]
(11)
To compare against BatchGCP, we adapted the codebase provided modate APS as a non-conformity score and use the classification variant of the Folktables datasets since sinceJung et al. (2023) conducts experiments with those datasets. With the BatchGCP implemen- tation, we get the threshold function, f. and use it when constructing prediction sets. The fairness disparity is evaluated using Demographic Parity and Disparate Impact. Since BatchGCP aims to optimize group-conditional coverage, we only compare against those two fairness metrics, for fair comparison.
provvided by Jung et al. 2023) to accom-
While BatchGCP provides PAC guarantees group-wise coverage, it does not necessarily provide the fairness guarantees our framework does, as empirically seen with the ACSIncome and ACSE- ducation datasets in Table E6 and Figures E12 and E13 We can dissect the poor performance these datasets by looking at the per- ger-group conditional coverages in Fig where several groups undercovered. We note that BatchGCP requires group information at inference time, which stricts it from settings where group information may unavailable at inference time this is not a limitation of the CF Framework.
Table E6: Comparing Base APS, BatchGCP, and CF framework under Disparate Impact. For the CF frame- work, we set с 0.8 and use classwise lambdas. We observe that the CF Framework can achieve disparate impact value much closer to = 0.8 with little effect efficiency.
Base APS BatchGCP
CF
Disp. Impact Efficiency
0.011
0.576
0.781
ACSEducation
2.982
2.893
4.727
Disp. Impact
0.397
0.349
0.797
ACSIncome
Efficiency
2.212
2.200
2.674
htths/hs//h..tii..ooooo//r///rrr i formal
31

---

Published as a conference paper at ICLR 2025
Closeness Criterion:
Closeness Criterion:
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
APS
AP5
4.0
3.5
Actual Fairnsss Disparity
0.5
3.0
Efficiency
2.5
2.0
0.3
1.5
1.0
0.1
0.5
0.0
Dem_Parity
Dem_ Dem_Parity
Figure E12: ACSIncome. Comparing Base APS, BatchGCP, and CF framework under Demographic Parity. For the CF framework, we vary E {0.05, 0.1, 0.15, 0.2). We observe that the CF Framework achieves the smallest disparity
every value e (seen on the right figure) with small cost to efficiency (as seen on the left figure). In the figure, Base APS = Black lines, BatchGCP = Red lines, and the CF framework is the bar charts. The black dots are the desired disparity level for the CF framework, which the CF framework achieves, while neither Base APS nor BatchGCP meets these thresholds.
Closeness Criterion:
Closeness Criterion:
0.05
0.1
0.15
0.2
0.05
0.1
0.15
0.2
APS
APS
Actual Faimess Disparity
0.4
4
Efficiency
0.3
0.2
2
0.1
0
0.0
Dem_ Perr_tr
Dem Parity
Figure E13: ACSEducation. Comparing Base APS, BatchGCP, and CF framework under Demographic Parity. For the CF framework, vary [0.05, 0.1, 0.15. 0.2). We observe that the CF Framework achieves the smallest disparity for every value of (seen the right figure) with small on the left figure). the figure, Base APS Black lines. BatchGCP the bar charts. The black dots are the desired disparity level for the CF framework, which the CF framework achieves. while neither Base APS nor BatchGCP meets these thresholds.
the efficiency (as seen lines, and the CF framework
32

---

Published as a conference paper at ICLR 2025
Nefimmance Optimal Deferraal hrdicioo en lest Duto
Pefiomence Oatim Cerforma Preicioo es let Date
Mender
(a) ACSIncome.
(b) ACSEducation.
Figure E14:
To dissect the poor performance of BatchGCP seen in Figures P12 and E13 present the per-
group conditional coverages for both datasets and that certain groups significantly undercovered (i.c., groups 4. 5, and in both figures).
33


Reviews:
[{"review_id": "YfB7jY1SXT", "reviewer": "Reviewer_ST3N", "summary": "The manuscript introduces and studies a general-purpose conformal fairness framework. It consists of an algorithm that can enforce various notions of fairness (such as demographic parity, equalized odds, predictive parity, and several others contained in the ML fairness literature) on the coverage of prediction sets, in the sense of satisfying appropriate conformal guarantees on expected coverage conditional on sensitive labels/attributes. To demonstrate practical performance of the framework given the various fairness notions, experimental evaluation is provided on a variety of supervised learning tasks; besides the standard setting, graph conformal prediction with fairness constraints is also demonstrated in experiments.", "questions": "The main desideratum is a substantial overhaul of the paper's writing, especially as it pertains to the methodology Section 3. \n\nThere are other minor concerns, such as the exact conformal methods that the current proposed method is tested against. For instance, APS has been superseded in the literature by RAPS, so that should be included in the comparison. Also, importantly, at least a couple of the many recently appearing class-conditional and local conformal methods should also be included in the comparison for the sake of fairness; indeed, these methods are designed to be able to empirically attain partial versions of conditional coverage without receiving explicit constraints (such as fairness ones) as input, so they should provide a stronger baseline than methods like APS.\n\n----------------------------------------------------------------------------------\n\nUPDATE: The rebuttal, and the post-rebuttal manuscript update, address the immediate concern of improving the presentation of key terms/concepts in Section 3 and beyond. Other improvements such as updates to the experimental section were also made. Given these, I have raised my overall score to 6.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper's main asset is a reasonably broad evaluation of the proposed methods on a variety of datasets where fairness concerns may necessitate using one of the tabulated conformal fairness metrics. Compared to prior works the experimental section appears more extensive, both in terms of metrics and datasets. Moreover, conformal fairness guarantees were displayed on graph data in addition to the standard supervised tasks. The results indicate that explicitly enforcing fairness according to any of the tabulated fairness criteria is in fact often necessary, as evidenced by vanilla methods not satisfying non-enforced fairness coverage constraints. Furthermore, no drastic deterioration in efficiency guarantees is observed, indicating that the price to pay for fairness conditional coverage may often be acceptable.", "weaknesses": "--- The main weakness and bottleneck at this point is the writing of the manuscript. In particular, the writing of Section 3, which introduces the objectives, the general algorithm, and the analysis, is currently not acceptable. Indeed, lots of key notions and terms, both on the fairness side and on the conformal side, are not properly and unambiguously introduced and/or are discussed in arbitrary order. \n(Fairness: groups/group collections are never formally defined, nor are requirements on them specified (e.g. non-intersectionality etc); \"filters\" and \"filter functions\" are simply thrown into the presentation. No background on the fairness measures, no elaboration on how they are transformed into conformal analogues compared to original notions, except for an incoherent sentence starting with \"Essentially achieved...\" in line 130. Conformal prediction: auxiliary notions like \"interval widths\", \"label miscoverages\" appear right away in the pseudocode, which also uses clunky notation and for which the textual explanation is as confusing as the pseudocode notation.) This is not to say that one cannot fill in many of the details with enough imagination and enough expertise, but at the moment the writing is hardly structured and accessible enough.\n\n--- The theoretical/methodological side does not offer strong novel contributions; for the most part it simply wraps class-conditional and group-conditional conformal methodology into fairness-specific terminology --- and is currently doing it in a somewhat confusing way, given the currently unsatisfactory presentation as stated above.\n\n--- In addition, the literature background review, where it's claimed that there are \"very few prior efforts\" on fairness and conformal prediction, misses an established line of work on group-conditional fairness guarantees; these works study the enforcement of coverage guarantees (usually of both upper and lower bounds) on rich classes of subpopulations given by possibly arbitrarily overlapping groups.\n\nR. Barber et al: The limits of distribution-free conditional predictive inference [Journal of IMA 2020]\nC. Jung et al: Batch Multivalid Conformal Prediction [ICLR 2023]\nZ. Deng et al: Happymap: A generalized multi-calibration method [ITCS 2023]\nO. Bastani et al: Practical adversarial multivalid conformal prediction [NeurIPS 2022]\nI. Gibbs et al: Conformal Prediction with Conditional Guarantees [2023]", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "k7lXpnX51V", "reviewer": "Reviewer_zT1T", "summary": "The paper introduces \"Conformal Fairness,\" a framework that extends Conformal Prediction (CP) to ensure fairness across sensitive groups. The authors develop a theoretically grounded algorithm to control gaps in coverage between these groups, leveraging the exchangeability assumption instead of the typical IID assumption. This allows the framework to be applied to non-IID data types, including graph data. Experiments on both graph and tabular datasets show that the framework can effectively control fairness gaps while maintaining coverage guarantees.", "questions": "- How does the framework handle scalability with multiple sensitive attributes, especially computationally?\n\n- Why were existing fairness-aware methods not used as baselines for comparison?\n\n- How practical is the exchangeability assumption for real-world graph data? Any empirical evidence?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- Originality: Introduces \"Conformal Fairness,\" extending Conformal Prediction (CP) to address fairness in uncertainty quantification, especially for non-IID data.\n- Quality: Provides strong theoretical backing with rigorous proofs and effective validation through experiments on graph and tabular datasets.\n- Clarity: Clearly defined theoretical concepts and a stepwise algorithm description make the methodology accessible to those with relevant background knowledge. Providing additional background information on key concepts would help readers who are less familiar with the topics to follow more easily\n- Significance: Tackles an important gap by combining fairness with uncertainty quantification. Adaptable to multiple fairness metrics and data types, making it broadly applicable in ethical AI contexts.", "weaknesses": "- The paper lacks a detailed discussion of the fairness-efficiency trade-off. Quantifying acceptable efficiency losses when fairness is improved would make the results more actionable for practitioners balancing both aspects.\n\n- The extension of the exchangeability assumption to real-world data may not always hold. Adding empirical evidence or discussion on when this assumption is valid in practice would make the claims more robust.\n\n-Lack of comparison with all existing fairness-aware methods limits benchmarking. Adding baselines would clarify the framework's effectiveness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rwt1lZcl6U", "reviewer": "Reviewer_VVws", "summary": "This paper proposes a framework to check and find the suitable threshold for conformal learning. Further, the framework can be easily extended to some constraints, like fairness constraints. The authors specifically studied achieving fairness properties for graph models. Further, the authors studied how to use their framework to check the fairness property of a model. The authors' algorithm first find the right use inverse quantile to check whether a threshold is good.", "questions": "I think it would be very helpful for the authors to explain more about their design choices. For example, why choose inverse quantile for miscoverage level? Explain a bit more about the intuitions behind lemma 3.1 and 3.2 would really help the readers.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Conformal prediction is a very interesting area and there are many interesting works in this area. It is a natural question to ask how to achieve fairness for models in this setting. The authors provide a very general framework that can achieve many different definitions of algorithmic fairness. The paper also did many interesting experiments in graph datasets.", "weaknesses": "I personally think the author does not elaborate enough on why they chose this algorithm design. The writing of this paper could be improved.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "f4EQIxp9Nc", "reviewer": "Reviewer_3NSU", "summary": "This paper proposes a notion of fairness, named $\\textit{conformal fairness}$. In contrast with standard fairness notions (e.g. demographic parity), this notion significantly applies conformal mapping, which the authors clearly defined. The authors developed an algorithm to achieve this type of fairness on graph datas and confirmed with experiments.", "questions": "Please see the weaknesses section.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This paper is well-written with a clear structure.\n\n2. The notion of conformal prediction is common, while its application on fairness is not widely studied to the best of my knowledge. The novelty of this notion is well justified.\n\n3. The conformal fairness metrics in Table 1 are intuitive and well-founded.", "weaknesses": "1. Although the conformal fairness metrics are well-defined in Table 1, they were not carefully discussed in later results (Theorem 3.4). Specifically, Theorem 3.4 states that \"the coverage difference for Predictive Parity is satisfied\". In Table 1, the definition of Predictive Parity relies on a conformal prediction $\\mathcal{C}$, but the specific mapping/quantification is not discussed in the theorem statement.\n\n2. This is a continuation of the previous point. Suppose there is a conformal prediction in Theorem 3.4, how good is it, i.e. what shall the value of $\\alpha$ be, as in Equation 1?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)