Model Reconstruction Using Counterfactual Explanations: A Perspective From Polytope Theory
Authors: Pasan Dissanayake
Sanghamitra Dutta
Venue: NeurIPS 2024 poster (2024)
Keywords: model extraction
counterfactual explanations
decision boundary shift
query complexity
Primary area: interpretability_and_explainability
TL;DR: We propose novel performance guarantees and strategies for leveraging counterfactual explanations in model reconstruction.

Abstract: Counterfactual explanations provide ways of achieving a favorable model outcome with minimum input perturbation. However, counterfactual explanations can also be leveraged to reconstruct the model by strategically training a surrogate model to give similar predictions as the original (target) model. In this work, we analyze how model reconstruction using counterfactuals can be improved by
further leveraging the fact that the counterfactuals also lie quite close to the decision boundary. Our main contribution is to derive novel theoretical relationships between the error in model reconstruction and the number of counterfactual queries required using polytope theory. Our theoretical analysis leads us to propose a strategy for model reconstruction that we call Counterfactual Clamping Attack (CCA) which trains a surrogate model using a unique loss function that treats counterfactuals differently than ordinary instances. Our approach also alleviates the related problem of decision boundary shift that arises in existing model reconstruction approaches when counterfactuals are treated as ordinary instances. Experimental results demonstrate that our strategy improves fidelity between the target and surrogate model predictions on several datasets.

Model Reconstruction Using Counterfactual Explanations: A Perspective From Polytope Theory
Pasan Dissanayake University of Maryland College Park, MD pasand@und.cm edu
Sanghamitra Dutta University of Maryland College Park, MD Langhamd@umd. edu
Abstract
Counterfactual explanations provide ways of achieving a favorable model outcome with minimum input perturbation. However, counterfactual explanations also be leveraged to reconstruct the model by strategically training a surrogate model to give similar predictions the original (target) model. this work, we analyze how model reconstruction using counterfactuals can be improved by further leveraging the fact that the counterfactuals also lie quite close the decision boundary. Our main contribution is to derive novel theoretical relationships between the error in model reconstruction and the number of counterfactual queries required using polytope theory. Our theoretical analysis leads us to propose strategy for model reconstruction that we call Counterfactual Clamping Attack (CCA) which trains a surrogate model using unique loss function that treats counterfactuals differently than ordinary instances. Our approach also alleviates the related problem of deci- sion boundary shift that arises in existing model reconstruction approaches when counterfactuals are treated as ordinary instances. Experimental results demon- strate that our strategy improves fidelity between the target and surrogate model predictions on several datasets.
Introduction
Counterfactual explanations (also called counterfactuals) have emerged as a burgeoning area of research [Wachter et al. 2017 Guidotti 2022, Barocas al. 2020 Verma al. 2022 Karimi et al., 2022] for providing guidance on how to obtain a more favorable outcome from a machine learning model, e.g., increase your income by 10K to qualify for the loan. Interestingly, counterfactuals can also reveal information about the underlying model, posing a nuanced interplay between model privacy and explainability [Aīvodji et al. 2020 Wang al., 2022]. Our work provides the first theoretical analysis between the error in model reconstruction using counterfactuals and the number of counterfactuals queried for, through the lens of polytope theory.
Model reconstruction using counterfactuals can have serious implications in Machine Learning as Service (MLaaS) platforms that allow users query model for specified cost [Gong al. 2020 An adversary may be able to "steal" the model by querying for counterfactuals and training a surrogate model to provide similar predictions the target model, practice also referred extraction. On the other hand, model reconstruction could also be beneficial for preserving applicant privacy, e.g., if applicant wishes evaluate their chances of acceptance from crowdsourced information before formally sharing their own application information with an institution, often due resource constraints having limited number of attempts apply (e.g., applying for credit cards reduces the credit score [Capital One 2024 ). Our goal is to formalize how faithfully can one reconstruct underlying model given a set of counterfactual queries.
model
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

An existing approach for model reconstruction is to treat coun- terfactuals as ordinary labeled points and use them for training a surrogate model [Aivodji et al., 2020]. While this may work for a well-balanced counterfactual queries from the two classes lying roughly equidistant to the decision boundary, it is not the same for unbalanced datasets. The surrogate decision boundary might not always overlap with that of the target model (see Fig. D. a problem also referred to as a decision boundary shift. This due to the learning process where the boundary is kept far from the training examples (margin) for better generalization (Shokri et al. 2021
Target model's decision boundury
Surrogate model's decision boundary
Quurice
Cauntrfiiruals sided)
Favorable region
Unfavorblie region
Figure 1: Decision boundary shift when counterfactuals are treated as ordinary labeled points.
The decision boundary shift is aggravated when the system provides only one-sided counterfactuals, i.e., counterfactuals only for queries with unfavorable predictions. If one were allowed to query for two-sided counterfactuals, the decision boundary shift may be tackled by querying for the counterfactual of the counterfactual [Wang et al., 2022]. However, such strategies cannot be applied when only one-sided counterfactuals are available, which is more common and also a more challenging use case for model reconstruction, e.g., counterfactuals are only available for the rejected applicants to get accepted for a loan but not the other way.
In this work, we analyze how model reconstruction using counterfactuals can be improved by leveraging the fact that the counterfactuals are quite close the decision boundary. We provide novel theoretical analysis for model reconstruction using polytope theory, addressing an important knowledge gap in the existing literature. We demonstrate reconstruction strategies that alleviate the decision- Decision-boundary--e boundary-
issue for one-sided counterfactuals. In contrast to existing strategies Aivodji et al. [2020] and Wang et al. [2022] which require the system to provide counterfactuals for queries from both sides of the decision boundary, we are able to reconstruct using only one-sided counterfactuals, a problem that we also demonstrate to be theoretically more challenging than the two-sided case (see Corollary 3.8 In summary, our contributions can be listed as follows:
Fundamental guarantees on model reconstruction using counterfactuals: We derive novel theoret- ical relationships between the error in model reconstruction and the number of counterfactual queries (query complexity) under three settings: (i) Convex decision boundaries and closest counterfactuals (Theorem 3.2 : We rely on convex polytope approximations derive an exact relationship between expected model reconstruction error and query complexity; (ii) ReLU networks and closest coun- terfactuals (Theorem 3.6): Relaxing the convexity assumption, we provide probabilistic guarantees on the success of model reconstruction as a function of number of counterfactual queries; and (iii) Beyond closest counterfactuals: We provide approximate guarantees for broader class of models, including ReLU networks and
continuous models (Theorem 3.10).
We devise a reconstruction strategy that we call Counterfactual Clamping Attack (CCA) - that exploits only the fact that the counterfactuals lie reasonably close to the decision boundary, but need not be exactly the closest.
Model reconstruction strategy with unique loss function:
Empirical validation: We conduct experiments on both synthetic datasets, as well as, four real- world datasets, namely, Adult Income [Becker and Kohavi 1996). COMPAS [Angwin et al., 2016). DCCC YYeh, 2016), and HELOC [FICO] 2018). Our strategy outperforms the existing baseline Aivodji et al. al.[(020) over all these datasets (Section 4 using one-sided counterfactuals, i... counterfactuals only for queries from the unfavorable side of the decision boundary. We also include additional experiments to observe the effects of model architecture, Lipschitzness, and other types of counterfactual generation methods well ablation studies with other loss func- tions. A python- implementation is available at: https://githh: com/ ccom/paaanisssaaaaaa.... ssanayake/ model-reconstructi.. usingn wwwnterfactuullll.... wow.
Related Works: A plethora of counterfactual -eeteratiggggnnnggggggggn mechanisms has been suggested in existing
literature Guidotti 2022 Barocas al., [020 Verma et al. 2202 Karimi et al. 2022 2020 Mothal
et al.
2020 Dhurandhar et al. [2018] Deutch and Frost 2019 Mishra et al.) [021]. Related works that focus on leaking information about the dataset from counterfactual explanations include membership
inference attacks [Pawelczyk et al., 2023) and explanation-linee linkage attacks [Goethals et al.) 2023].
Shokri et al. [202]] examine membership inference from other types of explanations, e.g., feature- based. Model reconstruction (without counterfactuals) has been the topic of a wide array of studies (see surveys Gong et al. [2020] and Oliynyk et al. [2023]). Various mechanisms such as equation
solving Tramer et al. 2016 and active learning have been considered (Pal et al. 2020

---

Model inversion [Gong et al. 2021 Struppek et al. 2022 Zhao et al.) 2021] is another form of extracting information about black box model, under limited access the model aspects. In contrast to model extraction where the goal is to replicate the model itself, in model inversion an adversary tries to extract the representative attributes of a certain class with respect to the target model. In this regard, [Zhao et al. [202T] focuses on exploiting explanations for image classifiers such as saliency maps to improve model inversion attacks. SStruppek et al. [2022] proposes various methods based on Generative Adversarial Networks to make model inversion attacks robust (for
instance, to distributional shifts) in the domain of image classification.
Milli et al. 2019 looks into model reconstruction using other types of explanations, e.g., gradients. Yadav et al. 2023 explore algorithmic auditing using counterfactual explanations, focusing on linear classifiers and decision trees. Using counterfactual explanations for model reconstruction has received limited attention, with the notable exceptions of Alvodji et al. [2020] and Wang et al. [022]. Aivodji
et al. 2020] suggest using counterfactuals as ordinary labeled examples while training the surrogate model, leading to decision boundary shifts, particularly for unbalanced query datasets (one-sided counterfactuals) Wang et al. [2022] introduces strategy of mitigating this issue by further querying for the counterfactual of the counterfactual. However, both these methods require the system to provide counterfactuals for queries from both sides of the decision boundary. Nevertheless, user with a favorable decision may not usually require a counterfactual explanation, and hence a system providing one-sided counterfactuals might be more common, wherein lies our significance. While model reconstruction (without counterfactuals) has received interest from a theoretical perspective Tramer al. 2016 Papernot et al.] 2017, Milli et al. 2019], model reconstruction involving counterfactual explanations lack such a theoretical understanding. Our work theoretically analyzes model reconstruction using polytope theory and proposes novel strategies thereof, also addressing the decision-boundary shift issue.
2 Preliminaries
Notations:
We consider binary classification models m that take an input value x E IRd and output
probability between 0 and The final predicted class is denoted by [m(=)) (0, 13 which is obtained by thresholding the output probability at 0.5 as follows: [m[xx] = 1 [m(()) 2 0.5] where
1|-] denotes the indicator function. Throughout the paper, we denote the output probabiliity by m(x) and the corresponding thresholded output by [m( Consequently, the decision boundary of the model m is the (d- -ddimensional hypersurface (generalization of surface higher dimensions; see Definition 2.5p in the input space, given by ØM {x: m(x)) = 0.5]. We call the region where [m(x)]] = as the favorable region and the region where (m(x)) = 0 as the unfavorable region. We always state the convexity/concavity of the decision boundary with respect to the favorable region (i.e., the decision boundary is convex the set M = {x E Rd [m(x)] = 1} is convex). We assume that upon knowing the range of values for each feature, the dd-dimensional input space can be normalized so that the inputs lie within the set (0, 1] (the dd dimensional unit hypercube), as is common in literature [Liu et al.) 2020 Tramer al. 2016 Hamman et al.) 2023 Black et al. 2022 We let 9m denote the counterfactual generating mechanism corresponding to the model m.
Definition 2.1 (Counterfactual Generating Mechanism). Given a cost function e: [J, [0, 1j B for measuring the quality of a counterfactual, and model m, the corresponding coun- terfactual generating mechanism is the mapping Jm : [0, 1|d + [0, 1j specified as follows: * [m(w)].
Im (x) = arg mio c(x, w), such that [m(x)] ]
The cost c(æ, w) is selected based on specific desirable criteria. e.g., c(a, w) ||x w w|lp. with ||. 11p denoting the -nom.. Specifically, p = 2 leads to the following definition of the closest counterfactual (Wachter et al. 2017 Laugel et al. 2017 Mothilal et al. 2020).
Definition 2.2 (Closest Counterfactual), When c(æ, w) = || w| l2. the resulting counterfactual generated using 9m as per Definition 2.1 is called the closest counterfactual.
Given a model m and a counterfactual generating method 9m. we define the inverse counterfactual region G for a subset H C [0, 1 to be the region whose counterfactuals under gm fall in IH.
Definition 2.3 (Inverse Counterfactual Region). The inverse counterfactual region Gm.g.. of H C [0, 1]d is the the region defined as: Gm..g.. (IH) = {æ E [0, 1]d gm (w) E H].
3

---

Problem Setting: Our problem setting involves a target model m which is pre-trained and assumed be hosted on MM platform (see Fig. 2 Any user can query with a set of input instances S [0. 1] (also called counterfactual queries) and will be provided with the set
API Queries
Machine Learning
mix)
Prodictions D Coonterfactals (only if prediction unfaverable)
UserrAvversry
of predictions, i.e. { [=]] æ E [D) and a set one- sided counterfactuals for the instances whose predicted class 0, i.e., {gm (x) : E D, [m([))] = 0}. Note that, by the definition of a counterfactual, (gm (a:)) for all with (m(x)) 0. The goal of the user is to train a surrogate model to achieve a certain level of performance with as few gueries as possible. In this work, use fidelity our performance metric for model reconstruction")
Figure Problem setting
Definition 2.4 (Fidelity [Aivodji et al. (2000). With respect to given target model m and reference dataset Dier S [0, 1] the fidelity of a surrogate model m is given by
Fidm,, Dar (m)
Σ DeD
[[[m(=)] [m(())]]
Diefl
Background on Geometry of Decision Boundaries:
Our theoretical analysis employs arguments based on the geometry of the involved models' decision boundaries. We assume the decision boundaries are hypersurfaces. A hypersurface is generalization of surface into higher dimensions, e.g., line or a curve in a 2-dimensional space, surface in a 3-dimensional space, etc.
Definition 2.5 (Hypersurface, Lee 2209)) ). A hypersurface is a (d 1-))--dimma 1)-dimensional sub-manifold embedded in Rd, which can also be denoted by single implicit equation S(x) 0 where x E Rd.
We focus on the properties of hypersurfaces which are "touching" each other, as defined next. Definition 2.6 (Touching Hypersurfaces). Let S(x) 0 and T(æ) 0 denote differentiable hypersurfaces in Fd S(x) 0 and T(x) 0 are said to be touching each other the point if and only if S(w) = T(w) = 0, and there exists a non-empty neighborhood Bn, around w, such that Viz E B. with S(x) 0 and * w. only
of T(x:) > 0 or ((x) holds. (i.e., within Bw: ((x) = 0 and T(x)) = lie on the same side of each other).
Next, we show that touching hypersurfaces share a common tangent hyperplane at their point of contact. This result is instrumental in exploiting the closest counterfactuals in model reconstruction (proof in Appendix A.I).
Lemma 2.7. Let S(x) 0 and T(x) = 0 denote two differentiable hypersurfaces in Rd. touching each other at point w. Then, Six) = 0 and T(x) = have a common tangent hyperplane at w.
Main Results
We provide a set of theoretical guarantees on query size of model reconstruction that progressively build on top of each other, starting from stronger guarantees somewhat restricted setting towards more approximate guarantees in broadly applicable settings. We discuss important intuitions that can be inferred from the results. Finally, we propose model reconstruction strategy that is executable in practice, which is empirically evaluated in Section 4
3.1 Convex decision boundaries and closest counterfactuals
We start out with demonstrating how the closest counterfactuals provide a linear approximation of any decision boundary, around the corresponding counterfactual. Prior work (Yadav et al. 2023 shows that for linear models, the line joining query instance and the closest counterfactual w is perpendicular to the linear decision boundary. We generalize this observation to any differentiable decision boundary, not necessarily linear.
w(= 9m. (x))
Lemma 3.1. Let S denote the decision boundary of a classifier and æ E [0, be any point that not on S. Then, the line joining and its closest counterfactual w is perpendicular to S at w.
Performance can evaluated using accuracy or fidelity [Jagielkki
2020 Accuracy measure of
how well the surrogate model can predict the true labels over the data manifold of interest. While attacks based on both measures have been proposed in literature, fidelity-based attacks have been deemed more useful as first step in designing future attacks (Jagielski et al. 2020 Papernot al. 2017

---

The proof follows by showing that the di d-dimensional ball with radius || ||=--i w|12 touches (as 2.f S at w, and invoking Lemma 2.7 For details see Appendix A As direct consequence of Lemma 3.1 a user may query the system and calculate tangent hyperplanes of the deci- sion boundary drawn at the closest counterfactuals. This leads to a linear approximation of the decision boundary at the closest counterfactuals (see Fig. 3).
Target boundary m(x)=0.5
O Queries
Counterfactuals
(one-sided)
Polytope approximation
Figure 3: Polytope approximation of convex decision boundary using the clos- est counterfactuals.
If the decision boundary is convex, such an approximation will provide a of supporting hyperplanes. The intersec- tion of these supporting hyperplanes will provide a circumscribing convex polytope approximation of the decision boundary. We show that the average fidelity of such an approximation, evaluated over uniformly distributed input instances, tends to 1 when the number of queries is large.
Theorem 3.2. Let m be the target binary classifier whose decision boundary is convex (i.e., the } is convex) and has continuous second derivative. Denote by Mn the convex polytope approximation of m constructed with supporting hyperplanes obtained through i.i.d. counterfactual queries. Assume that the fidelity is evaluated with respect to Dey which is uniformly distributed over [0, 1]6. Then, when +
ser (xc [0, 1] [m(a=)] =}
Do the expected fideeityy of Ma with respect to
m is given by
E Fiddm. (Mn) =1-6
where E O (n A and the expectation is over both Mr and Drs.
Theorem 3.2 provides an exact relationship between the expected fidelity and number of queries.
The proof utilizes a result from random polytope theory [Böröczky Jr and Reitzner 2004] which provides complexity bound volume-approximmatig smooth convex sets by convex polytopes. The proof involves observing that the volume of the overlapping decision regions of m and Mn (for example, regions A and C in Fig. 3) translates to the expected fidelity when evaluated under a uniformly distributed Daar. Appendix A.2 provides the detailed steps.
Remark 3.3 (Relaxing the Convexity Assumption). This strategy of linear approximations can also be extended to concave decision boundary since the closest counterfactual will always lead to tan- gent hyperplane irrespective of convexity. Now the rejected region can be seen as the intersection of these half-spaces (Lemma 3.1 does not assume convexity). However, it is worth noting that approxi- mating concave decision boundary is. in general, more difficult than approximating a convex region. To obtain equally-spacee tangent hyperplanes on the decision boundary, concave region will require a much denser set of query points (see Fig. due to the inverse effect of length contraction discussed in Aleksandrov [9967] Chapter III Lemma 2]. Deriving similar theoretical guarantees for decision boundary which neither convex nor concave is much more challenging as the decision regions can no longer be approximated as intersections of half-spaces. The assumption of convex de- cision boundaries may only be satisfied under limited scenarios such as input-convex neural networks Amos et al. 2017). However, we observe that this limitation can be cireumvented in case of ReLU networks to arrive probabilistic guarantee discussed next.
Convex Region Length contraction
Concave Region
Denser
Queries
out
Figure 4: Approximating concave region needs denser queries w.r.t. a convex region.
3.2 ReL.U networks and closest counterfactuals
Rectified Linear Units (ReLU) are one of the most used activation functions in neural networks Zeiler et al.
2013 Maas et al. 2013 Ronneberger al. 2013 He al.) 2016). A deep neural network that uses ReI activations can be represented as a Continuous Piece- Wise Linear (CPWL) function
[Chen al.
2022 Hanin and Rolnick] 2019] A CPWL function comprises of union of linear
functions over a partition of the domain. Definition 3.4 below provides a precise characterization.
Definition 3.4 [Continuous Piece-Wiss Linear (CPWL) Function [Chen et al. 2022 ) function e: Rdd + R is said to be continuous piece-wise linear if and only if
5

---

1. There exists finite set of closed subsets of R2, denoted as {U;) such that Ug U, = R"
2. ((x) is affine over each U, i.e., over each U: ((x) - ((x) - a. x + by with a E IRd, by E R.
This definition can be readily applied to the models of our interest, of which the domain the unit hypercube [0, 1] A neural network with ReLU
|etiiiiattiooons activations can be used as classifier by appending Sigmoid activation [(2) = I+c to the final output. We denote such a classifier by (2x = (E(
where ((x) is CPWL It has been observed that the number of linear pieces of a trained |ee.U
network is generally way below the theoretically allowed maximum (Hanin and Rolnick] 2019].
We first show that the decision boundaries of such CPWL functions are collections of polytopes (not
necessarily convex). The proof of Lemma 3.5 is deferred to Appendix A.3
Lemma 3.5.
Let m(x) (l(x)) be a ReLU classifier: where ((z) is CPWL and a is the Sigmoid
function. Then, the decision boundary OM = (a: E [0, 1] m(x) 0.5) is a collection of (possibly non-convex) polytopes in [0, 1]s, when considered along with the boundaries of the unit hypercube.
Next we will analyze the probability of successful model reconstruction using counterfactuals. Consider a uniform grid Nr over the unit hypercube [0, 1js, where each cell is a smaller hypercube with side length (see Fig. 5). For this analysis, we make an assumption: If cell contains a part of the decision boundary, then that part is completely linear (affiee) within that small cell
Now, as the decision boundary becomes linear for each small cell that it passes through, having just one closest counterfactual in each such cell sufficient to get the decision boundary in that cell (recall Lemma 3.1 We formalize this intuition in Theorem (36 to obtain a probabilistic guarantee on the success of model reconstruction. A proof is presented in Appendix A.4
H
Theorem 3.6. Let m be a target binary classifier with ReLU acti- vations. Let k(e) be the number of cells through which the decision boundary passes. Define (IH,, (
be the collection of affine pieces of the decision boundary within each decision boundary cell where each H, is an open set. Let (e(e) V (G..g.m (H.)) where V.) is the d d-dimensional volume (i.e., the Lebesgue measure) and Gm..g.. (-) is the inverse counterfactual region w.rt. m and the clos- est counterfactual generator 9m- Then the probability of successful reconstruction with counterfactual queries distributed uniformly over [0, 11 is lower-bounded as
(mai) (H)
Figure 5: Nr grid and inverse counterfactual regions. Thick solid lines indicate the deci- sion boundary pieces (HH, 's). White color depicts the ac- cepted region. Pale-colored are the inverse counterfactual regions of the H2's with the matching color. In this case k(c) = and v (c) is the area of lower amber region.
[Reconstruction] 1 ((e)(1-
(2)
where " (c) = min;=11.... ve(e) and n is the number of queries. Remark 3.7. Here k:(c) and (c( depend only on the nature of the model being reconstructed and are independent of the number of queries n. The value of k(e) roughly grows with the surface area of the decision boundary (e.g., length when input is 2D), showing that models with more convoluted decision boundaries might need more queries for reconstruction. Generally, k(e) lies within the
interval A(OM) -2 < kcc) S 1 where A(-) denotes the surface area in d dimensional space. The
lower bound is due to the fact that the area of any slice of the unit hypercube being at-most v2 [Ball 1986). Upper bound is reached when the decision boundary traverses through all the cells in the grid which is less likely in practice. When the model complexity increases, we get a larger ki(e) as well as smaller v" (e), requiring a higher number of queries to achieve similar probabilities of success.
Corollary 3.8 (Linear Models). For linear models with one-sided counterfactuals, - (1 u)m where v is the volume of the unfavorable region. How- ever, with tio-sided counterfactuals, IP [Reconstruction]
[eeonntrructio]
with just one single query.
"Tii violated only for the cells containing parts the edges of the decision boundary. However, we may assume that e is small enough so that the total number of such cells is negligible compared to the total cells containing the decision boundary. Generally, e can be made sufficiently small such that for most of the cells, if a cell contains part of the decision boundary then that part affine within the cell.

---

This result mathematically demonstrates that allowing counterfactuals from both accepted and rejected regions (as in Aivodji et al. 2020 Wang et al. [022]) is easier for model reconstruction. when compared to the one-sided case. It effectively increases each v;(e) (volume of the inverse counterfactual region). As everything else remains unaffected, for a given n, IP Recoostrruction is higher when counterfactuals from both regions are available. For a linear model, this translates to guaranteed reconstruction with a single query since v =
However, we note that all of the aforementioned analysis relies on the closest counterfactual which can be challenging to generate, Practical counterfactual generating mechanisms usually provide counterfactuals that are reasonably close but may not be exactly the closest. This motivates us to now propose a more general strategy assuming local Lipschitz continuity of the models involved.
3.3
Beyond closest counterfactuals
Lipschitz continuity, a property that is often encountered in related works [Bartlett et al., 201 Gouk
et al.
2021 Pauli et al. 2021 Hamman al. 2023 2024 Liu et al. 2020 Marques-Sine Silva et al.
2021 demands the model output does not change too fast. Usually, a smaller Lipschitz constant is
indicative of a higher generalizability of model [Gouk et al. 2021 Pauli et al. [021].
Definition 3.9 (Local Lipschitz Continuity). A model m is said to be locally Lipschitz continuous
if for every 31 E [0, 1] there exists neighborhood Bx,, S [0, 1j around æ; such that for all 22 E B |m(x)) m m(x))) > æ 22
for some y I...
For analyzing model reconstruction under local- Lipschiis assumptions, we consider the difference of the model output probabilities (before thresholding) as measure of similarity between the target and surrogate models because would force the decision boundaries to overlap. The proposed strategy is motivated from the following observation: the difference of two models' output probabilities corresponding to a given input instance x can be bounded by having another point with matching outputs in the affinity of the instance æ. This observation is formally stated in Theorem 3.10 See Appendix A.5 for a proof.
Theorem 3.10. Let the target m and surrogate in be Rel.U classifiers such that m(un) m(ww) for every counterfactual w. For any point x that lies in a decision boundary cell, ((((x))) m(x)) )
vd((im + +/ma) holds with probability 2 1- 1 k(() --- (c))".
Note that within each decision boundary cell, models are affine and hence locally Lipschitz for some Ym Pin E RT- Local Lipschitz. property assures that the approximation is quite close (7m, Yha are small) except over a few small ill-behaved regions of the decision boundary. This result can be extended to any locally Lipschitz pair of models as stated in following corollary.
Corollary 3.11. Suppose the target m and surrogate in are locally Lipschitz (not necessarily ReLU such that m(w) = vi(w) ) for every counterfactual w. Assume the counterfactuals are well-spaced out and forms a 8-cover over the decision boundary. Then [m((x) - m(x) S (Y/ + 7/m )õ, over the target decision boundary.
Theorem 3.10 provides the motivation for novel model reconstruc- tion strategy. Let w be a counterfactual. Recall that ØM denotes the decision boundary of m. As implied by the theorem, for any x E OM,, the deviation of the surrogate model output from the tar- get model output can be bounded above by vd(mm + +m)) ) given that all the counterfactuals satisfy m(w)= = m m(w). Knowing that m(w) = 0.5, we may design a loss function which clamps m(w) to be 0.5. Consequently, with a sufficient number of well-spaced counterfactuals to cover iML we may achieve arbitrarily small [m(x) (=)) at the decision boundary of m (Fig. 6).
Target boundary mnix)-0.5
Surregate boundary
Manching
Points
Figure 6: Rationale for Coun- terfactual Clamping Strategy.
However, we note that simply forcing ri(ww) to be exactly equal to 0.5 is quite unstable since in practice the target model's output m(w) is known to be close 0.5, while being greater but may not be exactly equal. Thus, we propose a unique loss function for training the surrogate neural networks that does not penalize the counterfactuals that are already inside the favorable region of the surrogate model. For 0 << k 5 1, we define the Counterfactual Clamping loss function as
L (x:, )x)) = 1 [v 0.5, m(x) I k] {L (m)())) k) h(k)} + 1 [vx * 0.5] [ (x), (3)
7

---

Here, denotes the label assigned to the input instance æ by the target model, received from the API L(g. y) is the binary cross-entropy loss and h(-) denotes the binary entropy function. We assume that the counterfactuals are distinguishable from the ordinary instances, and assign them a label of ym = 0.5. The first term accounts for the counterfactuals, where they are assigned a non-zero loss if the surrogate model's prediction is below k. This term ensures mn(w) Z for the counterfactuals w while not penalizing the ones that lie farther inside the favorable region. The second term is the ordinary binary cross-entropy loss, which becomes non-zero only for ordinary query instances. Note that substituting = 1 La (m(()) yz) yields the ordinary binary cross entropy loss. Algorithm | summarizes the proposed strategy.
It is noteworthy that this approach is differ- ent from the broad area of soft-label learn-
Algorithm 1 Counterfactual Clamping
ing Nguyen et al. (2011a] b) in two major
Require: Attack dataset Danack A (k E (0, 1]. usually
aspects: (i) the labels our problem do not smoothly span the interval [0.1] in- stead they are either O, I or 0.5; (ii) la- bels of counterfactuals do not indicate a class probability; even though a label of 0.5 is assigned, there can be counterfactuals that are well within the surrogate decision boundary which should not be penalized. Nonetheless, we also perform ablation stud- ies where compare the performance of our proposed loss function with another potential loss which simply forces (w) to be exactly 0.5, inspired from soft-label learning (see Appendix [B.2. for results).
O.5),AAII for querying
Ensure: Trained surrogate model m
1: Initialize A 0
2: for x: E Datuek do
3: Query API x to get yo (ye E (0, 1}}
4:
A + A U (x, yee
5:
if ya = 0 then
6: Query API for counterfactual w of x
7:
A. <-
U ((w,0.5)) (Assign w a label of
0.5)
8: end if
9: end for
10: Train in on A with Lx(m(()), Me) as the loss
11: return m
Counterfactual Clamping overcomes two challenges beset in existing works; (i) the problem of decision boundary shift (particularly with one-sided counterfactuals) present in the method suggested by Aivodji et al. [2020] and (ii) the need for counterfactuals from both sides of the decision boundary in the methods of Aīvodji al. (0220) and Wang al. (2022).
Experiments
We carry out a number of experiments to study the performance our proposed strategy Counterfac- tual Clamping. We include some results here and provide further details in Appendix B
All the classifiers are neural networks unless specified otherwise and their decision boundaries are not necessarily convex. The performance of our strategy is compared with the existing attack presented in Aívodji et al. [2200] that we refer to as "Baseline", for the case of one-sided counterfactuals. As the initial counterfactual generating method, we use an implementation of the Minimum Cost Counterfactuals (MCCF) by Wachter et al. [2017].
Performance metrics: Fidelity is used for evaluating the agreement between the target and surrogate models. is evaluated over both uniformly generated instances (denoted by Dami) and test data instances from the data manifold (denoted by (Deas) as the reference dataset Der.
summary of the experiments is provided below with additional details in Appendix B
(i) Visualizing the attack using synthetic data: First, the effect of the proposed loss function in mitigating the decision boundary shift is observed over 2-D synthetic dataset. Fig. 7 presents the results. In the figure, it is clearly visible that the Baseline model is affected by a decision boundary shift. In contrast, the CCA model's decision boundary closely approximates the target decision boundary. See Appendix B for more details.
(ii) Comparing performance over four real-world dataset: We use four publicly available real- world datasets namely, Adult Income, COMPAS, DCCC, and HELOC (see Appendix B for our experiments. Table T provides some of the results over four real-world datasets. We refer to Appendix B.2.2 (specifically Fig. TT) for additional results. In all cases, we observe that CCA has either better or similar fidelity as compared to Baseline.
8

---

Target Model
Baseline Model
CCA Model
14
10
16
Training data
Counterfactuals
04
* Queries [m
44
0.4
64
Querles w/ [m(x)]-a
10
Figure 7: A 2-D demonstration of the proposed strategy. Orange and blue shades denote the favorable and unfavorable decision regions of each model. Circles denote the target model's 's training data.
Table 1: Average fidelity achieved with 400 queries on the real-world datasets over an ensemble of size 100. Target model has hidden layers with neurons (20100), Model O is similar to the target model in architecture. Model has hidden layers with neurons (20, 10, 5).
Architecture known (model 0)
Architecture unknown (model I)
Dataset
Dost
Duii
Dies
Dumi
Base.
CCA
Base.
CCA
Base.
CCA
Base.
CCA
Adult In.
9113.2
94:13.2
841:3.2
9113.22
9114.5
9413.2
8413.22
9013.2
COMPAS
9243.2
96+22.0
94+1.7
96+22.0
91+8.9
96+3322
94+2.0
94+8.9
DCCC
8918.9
99:00.9
95222.2
9.111.4
9017.7
97:44.5
9512.2
95111.
HELOC
9114.77
9612.22
92.12.8
94122.4
90117.4
95:5.55
9113.3
93:1..2
(iii) Studying effects of Lipschitz constants: We study the connection between the target model's Lipschitz constant and the CCA performance. Target model's Lipschitz constant is controlled by changing the L2 regularization coefficient, while keeping the surrogate models fixed. Results are presented in Fig. 15 Target models with smaller Lipschitz constant easier to extract. More details are provided in Appendix [B.2.4.
(iv) Studying different model architectures: We also consider different surrogate model architec- tures spanning models that are more complex than the target model to much simpler ones. Results show that when sufficiently close to the target model in complexity. the surrogate architecture plays a little role on the performance. See Appendix B.2.5 for details. Furthermore, two situations are considered where the target model is not neural network in Fig. and Appendix B.2.8 In both scenarios, CCA surpasses the baseline.
(v) Studying other counterfactual generating methods: Effects of counterfactuals being sparse, actionable, realistic, and robust are observed. Sparse counterfactuals are generated by using L1 norm as the cost function. Actionable counterfactuals are generated using DiCE [Mothilal et al.) 2020] by defining set of immutable features. Realistic counterfactuals (that on the data manifold) are generated by retrieving the I-Nearest-Neighhor from the accepted side for given query, as well as using the autoencoder-basel method C-CHVAE [Pawelczyk al., 2020). Additionally, we generate robust counterfactuals using ROAR (Upadhyay et al. 2021] J. We evaluate the attack performance on the HELOC dataset (Table 2}. Moreover we observe the distribution of the counterfactuals generated using each method w.r.t. the target model's decision boundary using histograms (Fig. 8). Additional
details are given in Appendix B.2.6
(vi) Comparison with DualCFX: DualCFX proposed by Wang et al. 2022 is strategy that utilizes the counterfactual of the counterfactuals mitigate the decision boundary shift. We compare CCA
with DualCFX in Table 6 Appendix B.2.7
(vii) Studying alternate loss functions: We explore using binary cross-entropy loss function directly with labels 0, and 0.5, in place of the proposed loss. However, experiments indicate that this scheme performs poorly when compared with the CCA loss (see Fig. [8 and Appendix BB2..0).
(viii) Validating Theorem 3.2; Empirical verification of the theorem is done through synthetic experiments, where the model has spherical decision boundary since they are known to be more difficult for polytope approximation [Arya et al.) 2012). Fig. presents a log-log plot comparing the theoretical and empirical query complexities for several dimensionality values d. The empirical approximation error decays faster than n (dd(11) predicted by the theorem (see Appendix B.3

---

Table 2:
Fidelity achieved with different counterfactual generating methods on HELOC dataset.
Target model has hidden layers with neurons (20, 30, 10). Surrogate model architecture is (10, 20).
Fidelity over Dis
Fidelity over Duni
CF method
n= n=100
n=200
n=100
n=
Base.
CCA
Base.
CCA
Base.
CCA
Base.
CCA
MCCF L2-norm MCCF L1-norm DiCE Actionable
96
95
93
96
92
91
95
93
94
95
95
90
91
93
94
1- Nearest-Neighthon
93
95
94
96
93
93
94
95
ROAR
Upadhyay al. 2021
87
85
C-CHVAL
Pawelczyk et al.
2020
5
JeJ
MCCF
1e3
MECF
1o3
DIFF Artinnalle
1e3
1-NN
163
ROAR
1.0s
4
4
4
3
3
3
Count
2-
2
2
2
1
0
0.4
0.2 Taigat pradiction
Target prediction
Target prediction
Target prediction
Targat prodiction
Figure 8: Histograms of the target model's predictions on different types of input instances. Coun- terfactual generating methods except MCCF with L2 norm often generate counterfactuals that are farther inside the favorable region, hence having a target model prediction much greater than 0.5. We count all the query results across all the target models in the ensembles used to compute the average fidelities corresponding to each counterfactual generating method.
Conclusion
Our work provides novel insights that bridge explainability and privacy through set of theoretical guarantees on model reconstruction using counterfactuals. We also propose a practical model reconstruction strategy based the analysis. Experiments demonstrate significant improvement in fidelity compared to the baseline method proposed in Aïvodji et al. (2020) for the case of one- sided counterfactuals. Results show that the attack performs well across different model types and counterfactual generating methods. Our findings also highlight an interesting connection between Lipschitz constant and vulnerability model reconstruction.
Even though Theorem 3.6 provides important insights about the role of query size in model reconstruction, it lacks exact characterization of k(() and (e(c). Moreover, local Lipschitz continuity might not be satisfied in some machine learning models such as decision trees. Any improvements along these lines can be avenues for future work. Utilizing techniques in active learning in conjunction with counterfactuals another problem of interest. Extending the results of this work for multi-class classification scenarios can also be explored. The relationship between Lipschitz constant and vulnerability to model reconstruction may have implications for future work generalization, robustness, etc. Another direction of future work is to design defenses for model reconstruction attacks, leveraging and building on strategies for robust counterfactuals [Dutta]
Limitations and Future Work:
al. 2022. Hamman al. 2024 Upadhyay al. 2021 Black et al. 2022 Jiang et al. 2023
Pawelczyk et al. 2020].
We demonstrate that sides counterfactuals can be used for perfecting model reconstruction. While this can be beneficial in some cases, also exposes a potential vulnerability in MLaaS platforms. Given the importance of counterfactuals in explaining model predictions, hope our work will inspire countermeasures and defense strategies, paving the way toward secure and trustworthy machine learning systems.
Broader Impact:
10

---

References
U. Aïvodji, A. Bolot, and S. Gambs. Model extraction from counterfactual explanations. arXiv preprint arXiv:2009.0188 01884, 2020.
A. D. Aleksandrov. A. D. Alexandrov: Selected Works Part II: Intrinsic Geometry of Convex Surfaces. American Mathematical Society, 1967.
B. Amos, L. Xu, and J. Z. Kolter. Input convex neural networks. In Proceedings of the 34th International Conference Machine Learning, pages 146-155. PMLR, July 2017.
J. Angwin,
Larson, S. Mattu, and L. Kirchner. ProPublica, 2016.
bias. URL https: //wp:///wwwwww/ propublica..... org arg/article/
Machine
machine- bias- Lhas-risk-oo asseasments in- criminal -eettencinnnnnnngge
Arya, G. D. Da Fonseca, and D. M. Mount. Polytope approximation and the Mahler volume. In Proceedings of the Twenty-Thire Annual ACM-SIAM Symposium on Discrete Algorithms, pages 29 42. Society for Industrial and Applied Mathematics, Jan. 2012.
K. Ball. Cube slicing in R Proceedings of the American Mathematical Society, 97(3):465-477 473, 1986.
S. Barocas, A. D. Selbst, and M. Raghavan. The hidden assumptions behind counterfactual explana- tions and principal reasons. In Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency, pages 80-89 2020.
P. L. Bartlett, D. J. Foster, and M. J. Telgarsky. Opectrally-normalizee margin bounds for neural networks. In Advances in Neural Information Processing Systems, volume 30, 2017.
B. Becker and R. Kohavi. Adult. http://..orgg1..24//////.///
UCI Machine Learning Repository, 1996. DOL:
E. Black, Z. Wang, and M. Fredrikson. Consistent counterfactuals for deep models. In International Conference on Learning Representations, 2022.
K. Böröczky Jr and M. Reitzner. Approximation of smooth convex bodies by random circumscribed polytopes. The Annals of Applied Probability, 14(1):239-273, 2004.
Capital One, Feb. 2024.
URL
money management/down does
denied- www.aa/gweeeoeo-oooooooaoraaaaan
K.-L. Chen, H. Garudadri, and B. D. Rao. Improved bounds on neural complexity for representing piecewise linear functions. Advances in Neural Information Processing Systems, 35:7 2022.
D. Deutch and N. Frost. Constraints banste explanations of classifications. In IEEE 35th International Conference on Data Engineering, pages 530-541, 2019.
A. Dhurandhar, P. Y. Chen, R. Luss, C. C. Tu, P. Ting, K. Shanmugam, and P. Das. Explanations based the missing: Towards contrastive explanations with pertinent negatives. In Advances in Neural Information Processing Systems, volume 31, 2018.
S. Dutta, J. Long, S. Mishra, C. Tilli, and D. Magazzeni. Robust counterfactual explanations for tree-based ensembles. In International Conference on Machine Learning, pages 5742-5756. PMLR, 2022.
FICO. Explainable machine learning challenge, 2018. Ut.lttpppp/cmmmmtt.fffcc. explainable- -eaeeeeeeeannnnnen chw.hggnchalleeee.e
S. Goethals, K. Sörensen, and Martens. The privacy issue of counterfactual explanations: Ex- planation linkage attacks. ACM Transactions on Intelligent Systems and Technology, 14(5):1-24, 2023.
X. Gong, Q. Wang, Y. Chen, W. Yang, and X. Jiang. Model extraction attacks and defenses on cloud-based machine learning models. IEEE Communications Magazine, 58(12):83-88 2020.

---

X. Gong, Y. Chen, W. Yang, G. Mei, and Q. Wang. Inversenet: Augmenting model extraction attacks with training data inversion. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, pages 2439-2444 2021.
H. Gouk, E. Frank, B. Pfahringer, and M. Cree. Regularisation of neural networks by enforeing lipschitz continuity. Machine Learning. 110:393-466, 2021.
R. Guidotti. Counterfactual explanations and how to find them: Literature review and benchmarking. Data Mining and Knowledge Discovery, pages 1-55, 2022.
F. Hamman, E. Noorani, S. Mishra, D. Magazzeni, and S. Dutta. Robust counterfactual explanations for neural networks with probabilistic guarantees. In 40th International Conference on Machine Learning, 2023.
Hamman, E. Noorani, S. Mishra, D. Magazzeni, and S. Dutta. Robust algorithmic recourse under model multiplicity with probabilistic guarantees. IEEE Journal on Selected Areas in Information Theory, 5:357-368, 2024. doi: 10. 10//4AATT:2024.4000
B. Hanin and D. Rolnick. Complexity of linear regions in deep networks. In International Conference on Machine Learning. pages 2596-2604. PMLR, 2019.
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
M. Jagielski, N. Carlini, D. Berthelot, A. Kurakin, and N. Papernot. High accuracy and high fidelity extraction of neural networks. In Proceedings of the 29th USENIX Conference Security Symposium, pages 1345-1362, 2020.
J. Jiang, F. Leofante, A. Rago, and F. Toni. Formalising the robustness of counterfactual explanations for neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages
2023.
A.-H. Karimi, G. Barthe, B. Balle, and Valera. Model-agnostic counterfactual explanations for consequential decisions. In International Conference on Artificial Intelligence and Statistics, pages 895-905, 2020.
A.-H. Karimi, G. Barthe, B. Schölkopf, and I. Valera. A survey of algorithmic recourse: Contrastive explanations and consequential recommendations. ACM Computing Surveys, 55(5):1-29, 2022.
T. Laugel, M.-. Lesot, C. Marsala, X. Renard, and M. Detyniecki. Inverse classification for comparison-basee interpretability in machine learning. arXiv preprint 17X1v:171..08443, 2017.
M. Lee. Manifolds and Differential Geometry. Graduate Studies in Mathematics. American Mathematical Society, 2009.
X. Liu, X. Han, N. Zhang, and Q. Liu, Certified monotonic neural networks. In Advances Neural Information Processing Systems, volume 33, pages 15427-15438, 2020.
A. L. Maas, A. Y. Hannun, A. Y. Ng. et al. Rectifier nonlinearities improve neural network acoustic models. In International Conference on Machine Learning, volume 30, page 3, 2013.
Marques- Malva Gerspacher, M. C. Cooper, A. Ignatiev, and N. Narodytska. Explanations for monotonic classifiers, In 38th International Conference on Machine Learning, 2021.
S. Milli, L. Schmidt, A. D. Dragan, and M. Hardt. Model reconstruction from model explanations. In Proceedings of the Conference on Fairness, Accountability, and Transparency, pages 1-9, 2019.
S. Mishra, S. Dutta, J. Long, and D. Magazzeni. A Survey the Robustness of Feature Importance and Counterfactual Explanations. arXiv e-prints, 1XXi:221110003:: 2021.
R. K. Mothilal, A. Sharma, and C. Tan. Explaining machine learning classifiers through diverse counterfactual explanations. Proceedings of the 2020 Conference on Fairness, Accountability and Transparency, 2020.
12

---

Q. Nguyen, H. Valizadegan, and M. Hauskrecht. Learning classification with auxiliary probabilistic information. IEEE International Conference on Data Mining. 2011:477-486, 201 la.
Q Nguyen, H. Valizadegan, A. Seybert, and M. Hauskrecht. Sample--fficien Iearning with auxiliary class-label information. AMIA Annual Symposium Proceedings, 2011:1004-101,, 2011b.
D. Oliynyk, R. Mayer, and A. Rauber. I know what you trained last summer: A survey on stealing machine learning models and defences. ACM Computing Surveys, 55(14s), 2023.
Pal, Y. Gupta, A. Shukla, A. Kanade, Shevade, and Ganapathy. Activethief: Model extraction using active learning and unannotated public data. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 865-872, 2020.
N. Papernot, P. McDaniel, I. Goodfellow, S. Jha, Z. B. Celik, and A. Swami. Practical black- box attacks against machine learning. In Proceedings of the 2017 ACM on Asia Conference on Computer and Communications Security, pages 506-519, 2017
P. Pauli, A. Koch, J. Berberich, P. Kohler, and F. Allgöwer. Training robust neural networks using Lipschitz bounds. IEEE Control Systems Letters, 6:121-126, 2021.
M. Pawelezyk, K. Broelemann, and G. Kasneci. Learning model-agnostic counterfactual explanations for tabular data. In Proceedings of the web conference 2020, pages 3126-3132, 2020.
M. Pawelezyk, H. Lakkaraju, and S. Neel. On the privacy risks of algorithmic recourse. In Proceedings of the 26th International Conference on Artificial Intelligence and Statistics, volume 206, pages 9680-9696, 2023.
O. Ronneberger, P. Fischer, and T. Brox. U-net: Convolutional networks for biomedical image segmentation. In Medical Image Computing and Computer-Assise Assistee Intervention MICCAI 2015, pages 231-241, Cham, 2015. Springer International Publishing. ISBN 978-3-319-24574-44
R. Shokri, M. Strobel, and Y. Zick. On the privacy risks of model explanations. In Proceedings of the 2021 AAAI/ACM Conference on Al, Ethics, and Sociery, pages 231-241, 2021.
L. Struppek, D. Hintersdorf, A. D. A. Correira, A. Adler, and K. Kersting. Plug & play attacks: Towards robust and flexible model inversion attacks. In International Conference on Machine Learning, pages 20522-20545. PMLR, 2022.
Tramèr, Zhang, A. Juels, M. K. Reiter, and T. Ristenpart. Stealing machine learning models via prediction APIs. In 25th USENIX Security Symposium, pages 601-618, 2016.
S. Upadhyay, S. Joshi, and H. Lakkaraju. Towards robust and reliable algorithmic recourse. Advances in Neural Information Processing Systems, 34:16926 16937, 2021.
S. Verma, V. Boonsanong, M. Hoang, K. E. Hines, J. P. Dickerson, and C. Shah. Counterfac- tual explanations and algorithmic recourses for machine learning: A review. arXiv preprint 1:X1v:2010.10596 2022.
S. Wachter, B. Mittelstadt, and C. Russell. Counterfactual explanations without opening the black box: Automated decisions and the GDPR. Harvard Journal of Law and Technology, 31:841, 2017.
Y. Wang, H. Qian, and C. Miao. DualCF: Efficient model extraction attack from counterfactual explanations. In 2022 ACM Conference on Fairness, Accountability and Transparency, pages 1318-1329, 2022.
C. Yadav, M. Moshkovitz, and K. Chaudhuri. Xaudit: A theoretical look at auditing with explanations. 047.04 2023.
I.C. Yeh. Default of Credit Card Clients. UCI Machine Learning Repository, 2016. DOL:
https://doi.or//10. http:///oo.og//0.244333//////// 2432/C55SH.
M. Zeiler, M. Ranzato, R. Monga, M. Mao, K. Yang, Q. Le, P. Nguyen, A. Senior, V. Vanhoucke, Dean, and G. Hinton. On rectified linear units for speech processing. In 2013 IEEE International Conference on Acoustics, Speech and Signal Processing, pages 3517-3521 2013.
X. Zhao, W. Zhang, X. Xiao, and B. Lim. Exploiting explanations for model inversion attacks. In Proceedings of the IEEE/CVF international conference computer vision, pages 682-692, 2021.
13

---

A Proof of Theoretical Results
A.1 Proof of Lemma 2.7 and Lemma 3.1
Lemma 2.7. Let S(x) = 0 and ( = 0 denote two differentiable hypersurfaces in R touching each other at point w. Then, S(x) 0 and T(x:) have a common langent hyperplane w.
Proof. From Definition 2.6 there exists a non-empty neighborhood _ around w, such that Vo E Bw with ((x) = and + w. only one of T(x) > or T(x) < 0 holds. Let x = (Ø1, 22,
I.d) ,2, and T/pl denote without Vp for S p S d. Then, within the neighborhood B we may re-parameterize S(x)
Tp p()))) Note that similar re-parameterization denoted by zp px can
be applied to T(x) = as well. Let An [ a E B.. {ur}}- From Definition 2.6 all B \ [w] satisfy only one of (x) 0 or (x) O, and hence without loss of generality the re-parameterization of TTx)) = 0 can be such that (() < T(z(s)) holds for all [(p] E Aw. Now, define p() = T( - S(())) Observe that F (21p)) has minimum at w and hence,
Vag, ((w))) = O. Consequently, V T(W()) = Va = (ww which implies that the tangent hyperplanes to both hypersurfaces have the same gradient un. Proof concludes by observing that
since both tangent hyperplanes go through w, the two hypersurfaces should share a common tangent
hyperplane
Lemma 3.1. Let denote the decision boundary of a classifier and æ E [0, 1]4 be any point that is not on S. Then, the line joining and its closest counterfactual is perpendicular to S at
Proof. The proof utilizes the following lemma.
Lemma A.1. Consider the d-dimensional ball C.e centered at æ, with lying on its boundary (hence Ce intersects S at W). Then, S lies completely outside Cz.
The proof of Lemma A.1 follows from the following contradiction. Assume part of S lies within C.. Then, points on the intersection of S and the interior of C, are closer to æ than w. Hence, up can no longer be the closest point æ, S.
From Lemma A. C. is touching the curve S at and hence, they share the same tangent hyperplane at w by Lemma 2.7 Now, observing that the line joining w and æ, being a radius of Cg. is the normal to the ball at concludes the proof (see Fig. 9
Target
Boundary
Tangent
O Query
Counterfactual
Figure 9:
Line joining the query and its closest counterfactual is perpendicular the decision boundary at the counterfactual. See Lemma 3.1 for details.
We present the following corollary as additional observation resulting from Lemma A.I Corollary A.2. Following Lemma A.7 can seen that all the points the d-dimensional ball with as the center and w on boundary lies on the same side of S x.
14

---

A.2 Proof of Theorem 3.2
Theorem 3.2. Let m be the target binary classifier whose decision boundary convex (i.e., the set {I E [0. [m(x)] = 1} is convex) and has continuous second derivative. Denote by Mn the convex polytope approximation of m. constructed with supporting hyperplanes obtained through i.i.d. counterfactual queries. Assume that the fidelity evaluated with respect to Dus which is uniformly distributed over [0, 1] Then, when nt - oo the expected fideitty of Ma with respect to is given by
E Fid (M,) = -
where O 20nn= (n- E.) and the expectation over both Mn and io
Proof. We first have a look at Böröczky Jr and Reitzner 2004 Theorem 1 (restated as Theorem below] from the polytope theory. Let MI be compact convex set with second-order differen- tiable boundary denoted by ÖM. Let d1,.... an be randomly chosen points on ÖM, distributed independently and identically according
given density dam- Denote by (a,)) the supporting
hyperplane of 0M at Assume C' to be a large enough hypercube which contains MI in its interior.
Now, define
M, n (a:)
which is the polytope created by the intersection of all the supporting hyperplanes. The theorem characterizes the expected difference of the volumes of M and M.,.
Theorem A.3 (Random Polytope Approximation, [Böröczky Jr and Reitzner 2004 For a convex
compact set M with second-order disferentiable OM. and non-zero continuous density dam.
E ((MM)-V((M)
(0M, d) n 2. + (n-
-
as T. DC, where (.) denotes the volume (i.e., the Lebesgue measure), and r (ÖM, d) is a constant that depends only on the boundary ÜM and the dimensionality of the space.
Let x;, = 1,..., n be n i.idd queries from the [m(x)] corresponding counterfactuals gm (X,) are also i..dd. Furthermore, they lie the decision boundary of m. Hence, we may arrive at the following result.
] 0 region of the target model. Then, their
Corollary A... Let M {x E [0, 11a [m(x)) 1} and MI, = fo E [0, [M,())
1}.
Then, by Theorem A.3
(V())) - V(MB] o (n
(6)
when n DC. Note that MI C Wl, and hence, the left-hand side is always non-negative.
From Definition 2.4
we may write
Fidm, Dnr (M
E
E [m(x)]] Mr, (x)
Mret
(7)
Drerl
DEDret
P [m(x)] = [ [x,
[x]
(t. query size is tixed)
(8)
[Berl
Lx
IP [m(x)] = [x(( x's are i.i.d))
(9)
I Mn
P [[m(x)] [MMx(x) [M mx)(x) IP (x)(() mm.(x)) dmn
(10)
where M, is the set of all possible m,
15

---

Now, by noting that
P [mm(x]] [ (x) [M mx(x)] 1 P [[m(x)] # [M)(s) [M, mx(xx)
(11)
may obtain
Fidm. Der (Mim)) =1 -
P [[m(x)]] [MTx(s) [xxx() mn (x))
E
Mr
Mn (x) mn mn(x)) dmn (12)
V (M [Mn(()) tm drnn
MM
Total volume
=1 for unit hypercube
(t x's are uniformly distributed) (13)
= 1 R ((M))
(14)
The above result, in conjunction with Corollary A.4
concludes the proof.
A.3 Proof of Lemma 3.5
(.) is the Sigmoid function. Then, the decision boundary OM = (a E [0, 1]a m(x) 0.5) is a collection of (possibly non-convex) polytopes in [0, 1]s, when considered along with the boundaries of the unit hypercube.
Lemma 3.5. Let (((()) be a ReLU classifier, where f(x) is CPWL and (.)
Proof. Consider the th piece (a)) of the classifier defined over U, A part of the decision boundary exists within U, only if lx U, such that m;(x) = 0.5. When is the case, at the decision boundary,
m(x) = 0.5
(15)
1
1 = 0.5
(16)
-((x) =1
(17)
(x) O
(18)
at x + b, =0
(19)
which represents hyperplane restricted U, Moreover, the continuity of the {(x: demands the decision boundary to be continuous across the boundaries of U,'s. This fact can be proved as follows:
Note that within each region U, exactly one of the following three conditions holds:
(a) Va E U2, (xx) >
U, does not contain a part of the decision boundary
(b) Va E U, (xx < 0 4 U, does not contain a part of the decision boundary
(c) 3x E U,, (xx)
U, contains part of the decision boundary
In case when (c) holds for some region U. the decision boundary within U; affine and it extends
from one point to another on the region boundary. Now let U, and Ug, 8, / E {1,....,u 7).4 * t be two adjacent regions sharing boundary. Assume that U, contains portion of the decision boundary, which intersects with a part of the shared boundary between U, and Ug (note that W,'s are closed and hence they include their boundaries). Let Do be point in the intersection of the decision boundary within U, and the shared region boundary. Now, continuity of f(x) at Do requires Hence, condition (c) holds for U₁. Moreover, this holds for all the points the said intersection. Therefore, if such a shared boundary exists between U, and U, then the decision boundary continues to U, Applying the argument to all U. U, pairs show that each segment of the decision boundary either closes upon itself or ends at boundary of the unit hypercube. Hence, when taken along with the boundaries of the unit hypercube, the decision boundary a collection of polytopes.
(xrp) = (xo)
16

---

A.4 Proof of Theorem 3.6
Theorem 3.6. Let m be a target binary classifier with ReLU activations. Let kc(e) be the number of cells through which the decision boundary passes. Define { fimm......6 to be the collection of affine pieces of the decision boundary within each decision boundary cell where each H4 an open set. Let nz(e)= = (.....m (H:)) where V(.) is the d- dimeennsional volume (i.e., the Lebesgue measure) and Gm.gm. (.) is the inverse counterfactual region w.r.t m. and the closest counterfactual generator 9u- Then the probability of successful reconstruction with counterfactuer queries distributed uniformly over [0, 1] is nower-bounder as
[Reconstruction) 2 21 2 (1=())())(())))))))))))))))))(() (c))"
where 2 (e)
ve(e) and the number of queries.
Proof. Note that
P|Reconstruction] = P(There is a counterfactual in every decision boundary cell
(20)
1 IP AAt least one decision boundary cell does not have counterfactual
(21)
k(e
-1 Σ plath decision boundary cell does not have counterfactual]
(22)
Let Mi denote the event decision boundary cell does not have a counterfactual". At the end of n queries.
P[M.]
UD th query falling outside of Gm..m (HH))
(23)
j=1
(e) for uniforn queries
= (1 -1---h (e))"
(24)
Therefore,
M(e)
P'Reconstruction]
=1 - Σ (1 (e))
(25)
i=1
2 1 - ((t)(1 (E)) (:v0(e) 2 ve(e) (::0(()2
ve(())= min mij))=)))))())
(26)
A.5 Proof of Theorem 3.10 and Corollary 3.11
Theorem 3.10. Let the larget m and surrogate vn be ReI.U classifters such that m(w) m(w) for
every counterfactual w. For any point x that lies in a decision boundary cell, |m(xx) m(x)) S
vd(cm + +/m)) c holds with probability 2 - k((c(1 v² (c))".
Corollary 3.11. Suppose the target m and surrogate mn are locally Lipschitz (not necessarily ReLU
such that m(w) = vi(w)
w) ()) for every counterfactual w. Assume the counterfactuals are well-spaced
out and forms a 8-cover over the decision boundary. Then [m(()) - m(()) S (Ymm + 7m)6 over the
target decision boundary.
Proof. Note that from Theorem 3.6 with probability p 2 1 1-11kee k(e) - 2 (E))" least one counter-
factual exists within each decision boundary cell. When this is the case, we have
[x((x:) m(=) = (m(()=) m(() (m(x) - m (w)
(27)
[m())) m(w) (m(x) m v(ww))
(28)
[m(x) (ww) + (m(x) m(w)
(29)
Sym Stmll1-will
Sym Stmlle-wl1
I (Ym + Nm. w|l2
(30)
< Vd(mm + Male
(31)
17

---

where the first inequality is a result of applying the triangle inequality and the second follows from the definition of local Lipschitz continuity (Definition 3.9). The final inequality is due the availability
of counterfactual within each decision boundary cell, which ensures ||æ: w|l2 S Vdc. Corollary
3.11 follows directly from the second inequality, since the d-cover of w ensure ||c- w wll2 S 5
B
Experimental Details and Additional Results
All the experiments were carried-out on two computers, one with a NVIDIA RTX A4500 GPU and the other with a NVIDIA RTX 3050 Mobile.
B.1 Details of World Datasets
We use four publicly available real-worke tabular datasets (namely, Adult Income, COMPAS, DCCC, and HELOC) to evaluate the performance of the attack proposed in Section 3.3 The details of these datasets follows:
The dataset is a 1994 census database with information such as educational level, marital status, age and annual income of individuals (Becker and Kohavi 1996]. The target is to predict "income", which indicates whether the annual income of given person exceeds $50000 not (i.e., y [income 2 0.5]). It contains 32561 instances in total (the training set), comprising of 24720 from = 0 and 7841 from 1. To make the dataset class-wise balanced randomly sample 7841 instances from class y = O, giving a total effective size of 15682 instances. Each instance has numerical features and 8 categorical features. During pre-process preppeeeessing categorical features are encoded integers. All the features are then normalized to the range [0, 1].
Adult Income:
Home Equity Line of Credit (HELOC): This dataset contains information about customers who have requested credit line
percentage of home equity FICO [2018]. It contains 10459 instances with 23 numerical features each. Prediction target is "is at risk" which indicates whether given customer would pay the loan in the future. Dataset is slightly unbalanced with class sizes of 5000 and 5459 for y 0 and = 1, respectively. Instead of using all 23 features, we the following subset of 10 for our experiments; "estimate of rissk",, inee_fraction___ _f oevoolvvin revolving_burdeer burden", "percent- age of leee_of_eegalttraae trades", smonths_sinee siinsinnnnttiineeeeee lasuuiu _ttr__no________ nocenet"""", "months since since_last_tee seatreentte_traddes.. with "aailea__ata_baaaaeee
"number_of_ sfaeeeroo__ttiiee sattssffccsfttttrrr_aaoaoaaaa___ ttrdy_t"ree"
"aver- All
potal_tradess. "nr wer_banks_wiing with__igh_aaatii the features are normalized to lie in the range [0, 1].
age_ ioge_ddratton___ of ofsreoouutioo"
Correctional Offender Management Profiling for Alternative Sanctions (COMPAS): This dataset has been used for investigating racial biases in commercial algorithm used for evaluating reoffending risks of criminal defendants (Angwin et al. 2016). includes 6172 instances and 20 numerical features. The target variable is is_rred Class-wise counts are 3182 and 2990 for y = 0 and = 1, respectively. All the features are normalized to the interval [0, 1] during pre processing..
Default of Credit Card Clients (DCCC): The dataset includes information about credit card clients in Taiwan Ych [0016). The target is to predict whether client will default on the credit or not, indicated by instances with 24 attributes each. Class-wise counts are 23364 from y and 6636 from y = 1. To alleviate the imbalance, we randomly select 6636 instances from = 0 class, instead of using all the instances. Dataset has 3 categorical attributes, which we encode into integer values. All the attributes are normalized to [0, 1] during prepprcesssig.
paw.llt...mmmt.nne...... mex..monnh". The dataset contains 30000
B.2 Experiments on the attack proposed in Section 3.3
In this section, provide details about experimental setup with additional results. For conve- nience, we present the neural network model architectures by specifying the number of neurons in each hidden layer tuple, where the leftmost element corresponds to the layer next to the input; e.g.: a model specified as (20,30,10) has the following architecture:
Input Dense(20, ReLU) > Dense(30, ReLU) Dense(10. ReLU) Output(Sigmoid)
18

---

Other specifications of the models, as detailed below, are similar across most of the experiments. Changes are specified specifically. The hidden layer activations are ReLU and the layer weights are T/2 regullalar The regularization coefficient is 0.001. Each model is trained for 200 epochs, with batch size of 32.
Fidelity is evaluated over a uniformly sampled set of input instances (uniform data) as well as held-out portion the original data (test data). The experiments were carried out as follows:
1. Initialize the target model. Train using Duain.
2. For t 1,2,.... ,..
(a) Sample N x t data points from the dataset to create attakk
(b) Curry-out the attack given in Algorithm with Datack- Use & 1 for "Baseline" models and k = 0.5 for "Proposed" models.
(c) Record the fidelity over Trer along with f.
3. Repeat steps and 2 for S number of times and calculate average fidelities for each t, across repetitions.
Based on the experiments of Aïvodji et al. [0200] and Wang et al. 2022 we select 7 20, 50, 100; N 20, 8, 4 and S 100, 50, in different experiments. We note that the exact numerical results are often variable due to the multiple random factors affecting the outcome such as the test-train eest-trai--attack split, target and surrogate model initialization, and the randomness incorporated in the counterfactual generating methods. Nevertheless, the advantage of CCA over the baseline attack is observed across different realizations.
B.2.1 Visualizing the attack using synthetic data
This experiment is conducted on synthetic dataset which consists of 1000 samples generated using the make_ make_moons _mons function from the sklearn package. Features are normalized to the range [0, 1] before feeding the classifier. The target model has 4 hidden layers with the architecture (10, 20, 20, 10). The surtogate model is 3-layered with the architecture (10, 20, 20). Each model is trained for 100 epochs. Since the intention of this experiment function given in (3). a large query of size 200 is used, instead of performing multiple small queries. Fig. shows how the original model reconstruction proposed by (Aivodji et (2020) suffers from
demonstrate the functionality of the modified loss
the boundary shift issue, while the model with the proposed loss function overcomes this problem.
Fig. 10 iiilusttratss the instances misclassified by the two surrogate models.
Baseline Model
CCA Model
Training data
E QUL
0.4
0.4
RED Intt
07
0.7
000
0.2
0.4
0.5
0.5
1.0
0.0
1.0
2.2
0.4
0.6
0.5
10
Figure 10: Misclassifications w.r.t. to the target model, over Buni and Dist as the reference datasets for the 2-dimensional demonstration in Fig. 7 "Baseline" model causes large number of misclassi- fications w.r.t. the "CCA" model.
B.2.2 Comparing performance over four real-world dataset
We use target model having 2 hidden layers with the architecture (20,10). Two surrogate model architectures, exactly similar to the target architecture (model 0 known architecture) and the other slightly different (model unknown architecture), are tested. Model has 3 hidden layers with the architecture 10.5).
Fig. TT illustrates the fidelities achieved by the two model architectures described above. Fig. 12 shows the corresponding variances of the fidelity values 100 realizations. It can be observed that
19

---

the variances diminish as the query size grows, indicating more stable model reconstructions. Fig. L3 demonstrates the effect of the proposed loss function in mitigating the decision boundary shift issue.
Adult Income
COMPAS
DCCC
HELOC
1.0
0.8
Fidelity over test data
0.6
Base. MO
CCA MO
0.4
1.0
0.8
0.6
Base. M1
CCA M1
0.4
1.0
0.8
Fidelity over uniform data
0.6
Base. MO
CCA MO
0.4
1.0
0.8
0.6
Base. M1
CCA M1
0.4
100
200
300
400
100
200
300
400
100
200
300
400
0
100
200
300
400
Query size
Query size
Query size
Query size
Figure 11: Fidelity for real-world datasets. Blue lines indicate "CCA" models. Black lines indicate "Baseline" models.
Adult
COMPAS
DCCC
HELOC
0.08
Base. MO
0.06
CCA MO
Variance over test data
0.04
0.08
Base, M1
0.06
CCA M1
0.04
0.02
0.0
0.08
Base.
0.06
Variance over uniform data
CCA MO
0.04
0.02
0.0
0.08
Base. M1
0.06
0.04
0.02
0.0
0
100
200
300
400
100
200
300
400
0
100
200
300
400
100
200
300
400
Query size
Query size
Query size
Query size
Figure 12: Variance of fidelity for real-world datasets. Blue lines indicate "CCA" models. Black
lines indicate "Baseline" models.
20

---

Baseline Model
CCA Model
400
[mx)]=
150
300
mm(x)==0
100
200
50
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4 m(x)
0.6
0.8
1.0
m(x)
Figure 13: Histograms of probabilities predicted by "Baseline" and "CCA" models under the "Unknown Architecture" scenario (model 1) for the HELOC dataset. Note how the "Baseline" model provides predictions higher than 0.5 for comparatively larger number of instances with [m(x)] = 0 due to the boundary shift issue. The clamping effect of the novel loss funetion evident the "CCA" model's 's histogram, where the decision boundary being held closer to the counterfactuals is causing the two prominent modes in the favorable region. The mode closer 0.5 due to counterfactuals and the mode closer to 1.0 is due to instances with [m(x))] 1.
B.2.3
Empirical and theoretical rates of convergence
Fig.
14 compares the rate of convergence of the empirical approximation eπror i...
E
Fidm, (Mn) for two of the above experiments with the rate predicted by Theorem 3.2 Notice
how the empirical error decays faster than 2/(d-1)
Adult Income Query Complexity
HELOC Query Complexity
(6-4)
Ingo)/
Model Test
Model D Test
Data
Dota
-0.
Data
Data
-10
Model Uni.
Micdel Uni.
Model Uni. Data
Micdel Uni. Dotaa
-15
-15
-2.0
-2.0
-2.5
-2.
In(n)
In(r)
Figure 14: A comparison of the query complexity derived in Theorem complexities obtained on the Adult Income and HELOC datasets. The graphs are a log-log scale. We observe that the analytical query complexity is an upper bound for the empirical query complexities. All the graphs recentered with additive constant for presentational convenience. However, this does not affect the slope of the graph, which corresponds to the complexity.
3.2 with the empirical query
B.2.4 Studying effects of Lipschitz constants
For this experiment, use target model having hidden layers with the architecture (20, 10. 5) and a surrogate model having hidden layers with the architecture (20, 10). The surrogate model layers are Ly-regularized with a fixed regularization coefficient of 0.001. We achieve different Lipschitz constants for the target models by controlling their Iezregullarizatinn coefficients during the target model training step. Following Gouk al. (2021), approximate the Lipschitz constant of target models by the product of the spectral norms of the weight matrices.
Fig. 15 illustrates the dependence of the attack performance on the Lipschitz constant of the target model. The results lead the conclusion that target models with larger Lipschitz constants are more difficult to extract. This follows the insight provided by Theorem 3.10
21

---

known
Archifeedure uninown
Architecture
37.947 (0.542) 140.348
(0.542) 149.348
124.002 (22.515)
124.902 515)
7122971 (70.524)
712.971
428
1.0
1.0
1.
Foaliy
08
0.7
07
077
07
06
0.5
06
0.
430
200
200 400
100
200
300
300
200
Query size
Query
Query
Query size
Figure 15: Dependence of fidelity on the target model's Lipschitz constant. The approximations of the Lipschitz constants are shown in the legend with standard deviations within brackets. Lipschitz constants are approximated as the product of the spectral norm of weight matrices in each model. With a higher Lipschitz constant, the fidelity achieved by given number of queries tend degrade.
B.2.5 Studying different model architectures
We observe the effect of the model architectures on the attack performance over Adult Income, COMPAS and HELOC datasets. Tables 3 and respectively, present the results.
Table 3: Fidelity over Des and Duni for Adult Income dataset
Target
(20,10)
100,10,5)
(20,20,10,5)
Dest
n=100
n=200
n=100
n=200
n=100
n=200
Surrogate
Base.
CCA
Base.
CCA
Base.
CCA
Base.
CCA
Base.
CCA
Base.
CCA
(20.10)
0.88
0.89
0.92
0.93
0.82
0.84
0.91
0.93
0.94
0.95
0.95
0.96
(20,10.5)
0.87
0.88
0.91
0.93
0.79
0.82
0.90
0.92
0.93
0,94
0.95
0.96
(20,20,10.5)
0.85
0.86
0.91
0.91
0.79
0.81
0.89
0.92
0.93
0.92
0.95
0.95
Target +
(20,10)
100,
120,00,10,5)
Duni
n=100
n=200
n=100
n=200
n=100
n=200
Surrogate
Base.
CCA
Base.
CCA
Base.
CCA
Base.
CCA
Base.
CCA
Base.
CCA
(20.10)
0.71
0.81
0.75
0.87
0.78
0.84
0.79
0.87
0.84
0.88
0.85
0.91
(20,10.5)
0.71
0.78
0.74
0.83
0.77
0.82
0.78
0.85
0.82
0.88
0.84
0.90
(20,20,10.5)
0.71
0.75
0.74
0.81
0.77
0.81
0.78
0.84
0.82
0.86
0.84
0.90
Table Fidelity over Dess and Dami for COMPAS dataset
Target
(20,10)
120,10.5)
(20,20,10,5)
Disst
n=100
n=200
n=100
n=200
n=100
n=200
Surrogate
Base.
CCA
Base. CCA
Base.
CCA
Base.
CCA
Base.
CCA
Base.
CCA
(20,10)
0.93
0.96
0.94
0.97
0.92
0.94
0.94
0.96
0.94
0.96
0.95
0.97
100,
0.92
0.95
0.94
0.97
0.92
0.93
0.95
0.95
0.94
0.96
0.95
0.97
(20,20,10,5)
0.92
0.95
0.92
0.97
0.84
0.91
0.89
0.94
0.92
0.94
0.94
0.96
Target-
(20,10)
10,,
(20,20,10.5)
Duni
n=100
n=200
n=100
n=200
n=100
n=200
Surrogate
Base.
CCA
Base.
CCA
Base.
CCA
Base.
CCA
Base.
CCA
Base.
CCA
(20.10)
0.94
0.95
0.94
0.96
0.95
0.95
0.95
0.96
0.96
0.95
0.96
0.96
(20,10.5)
0.93
0.95
0.94
0.95
0.94
0.92
0.95
0.92
0.95
0.96
0.96
0.96
(20,20,10,5)
0.93
0.94
0.94
0.95
0.94
0.85
0.94
0.90
0.95
0.92
0.95
0.94
22

---

Table 5: Fidelity over Diss and Duii for HELOC dataset
Target-
(20,10)
(20,10,5)
(20,20,10,5)
Dest
n=100
n=200
n=100
n=200
n=100
n=200
Surrogate
Base.
CCA
Base.
CCA
Base.
CCA
Base.
CCA
Base.
CCA
Base.
CCA
(20,10)
0.90
0.94
0.91
0.95
0.90
0.94
0.92
0.95
0.98
0.99
0.98
0.99
(20,10.5)
0.88
0.92
0.92
0.95
0.89
0.92
0.92
0.95
0.98
0,98
0.98
0.99
(20,
0.87
0.93
0.91
0.93
0.87
0.89
0.91
0.94
0.98
0.98
0.98
0.98
Target-
(20,10)
(20,10,5)
(20,20,10,5)
Duni
n=100
n=200
n=100
n=200
n=100
n=200
Surrogate
Base.
CCA
Base.
CCA
Base.
CCA
Base.
CCA
Base.
CCA
Base.
CCA
(20.10)
0.92 0.92
0.94
0.95
0.91
0.91
0.94
0.95
0.98
0.98
0.99
0.99
(20,10,5)
0.91
0.90
0.94
0.93
0.91
0.89
0.93
0.94
0.97
0.97
0.98
0.99
(20,
0.91
0.91
0.93
0.94
0.91
0.87
0.93
0.92
0.97
0.97
0.98
0.98
B.2.6 Studying alternate counterfactual generating method
Counterfactuals can be generated such that they satisfy additional desirable properties such as actionability, sparsity and closeness to the data manifold, other than the proximity to the original instance. In this experiment, performance. HELOC is used as the dataset. Target model has the architecture (20, 30, 10) and the architecture of the surrogate model is (10, 20).
observe how counterfactuals with above properties affect the attack
To generate actionable counterfactuals, we use Diverse Counterlactual Explanations (DiCE) by Mothilal et al. [2020) with the first four features, i.e., "estimate_of_____ _f__rss"", "months Secpaathssinnc______ since_last "ttdtrrdd"" cecaffactory_trades's trades" kept unchanged. The di- versity factor of DiCE generator is set to in order to obtain only a single counterfactual for each query. Sparse counterfactuals are obtained by the same MCCF generator used in other experiments, but now with L, norm the cost function c(ar, w). Counterfactuals from the data manifold (i.e., realistic counterfactuals, denoted by 1-NN) are generated using a 1 --Nearett-eiighher
"average duration of resolution", and "number of satisfactory
algorithm. We use ROAR (Upadhyay et al. 2021 and C-CHVAE (Pawelezyk et al. 2020) to generate robust counterfactuals. Table summarizes the performance of the attack. Fig. 8 shows the distribution of the counterfactuals generated using each method w.r.t. the decision boundary of the target model. We observe that the sparse, realistic, and robust counterfactuals have tendency to lie farther away from the decision boundary, within the favorable region, when compared the closest counterfactuals under Le norm.
B.2.7 Comparison with DualCFX Wang al. 2022
Wang et al. [2022] is one of the few pioneering works studying the effects of counterfactuals on model extraction, which proposes the interesting idea of using counterfactuals of counterfactuals to mitigate the decision boundary shift. This requires the AAP to provide counterfactuals for queries originating from both sides of the decision boundary. However, the primary focus of our work is on the one-sided scenario where an institution might be giving counterfactuals only to the rejected applicants to help them get accepted, but not to the accepted ones. Hence, a fair comparison cannot be achieved between CCA and the strategy proposed in Wang et al. [2022] the scenario where only one-sided counterfactuals are available.
Therefore, in the two-sided scenario, we compare the performance of CCA with the DualCFX strategy proposed in Wang et al. 2022] under two settings:
1. only one sided counterfactuals are available for CCA (named CCA1)
2. CCA has all the data that DualCFX has (named CCA2)
We also include another baseline (following Aivodji et al. 2020 for the two-sided scenario where the models are trained only on query instances and counterfactuals, but not the counterfactuals of the counterfactuals. Results are presented in Table 6 Note that even for the same number of initial
23

---

query instances, the total number of actual training instances change with the strategy being used (CCAI Baseline DualCFX CCA2 e.g. queries+CPs for the baseline but queries+CFs+CCCs for DualCFX).
Table 6: Comparison with DualCFX. Legend: Base.=Baseline model based on (Aīvodji et al. 2020 Dual=DualCFX, CCA1=CCA with one-sided counterfactuals, CCA2=CCA with counterfactuals from both sides.
Architecture known (model 0)
Dataset
Query size
Dest
Dai
Base.
Dual.
CCAI
CCA2
Base.
Dual.
CCAI
CCA2
1= 100
0.95
0.99
0.94
0.99
0.90
0.95
0.92
0.97
DCCC
n=200
0.96
0.99
0.98
0.99
0.90
0.96
0.95
0.98
n=100
0.94
0.97
0.90
0.98
0.91
0.98
0.84
0.98
HELOC
n=200
0.96
0.98
0.92
0.98
0.93
0.98
0.89
0,99
Architecture unknown (model 1)
Dataset
Query size
Dist
Dai
Base.
Dual.
CCA1
CCA2
Base.
Dual.
CCA1
CCA2
100
0.92
0.98
0.93
0.98
0.88
0.92
0.89
0.93
DCCC
n=200
0.96
0.99
0.96
0.99
0.89
0.94
0.94
0.96
n=100
0.92
0.91
0.90
0.96
0.88
0.92
0.84
0.96
HELOC
n=200
0.95
0.92
0.91
0.97
0.93
0.94
0.88
0.97
B.2.8 Studying other machine learning models
We explore the effectiveness of the proposed attack when the target model is no longer neural network classifier. The surrogate models still neural networks with the architectures (20, 10) for model and (20, 10, 5) for model 1. A random forest classifier with 100 estimators and a linear regression classifier, trained on Adult Income dataset are used the targets. Ensemble size S used is 20. Results are shown in Fig. 16 where the proposed attack performs better or similar to the baseline attack.
Random Forest
Linear Regression
0.85
0.75
Fideiity
0.65
Base. MO
CCA M1
CCA MD
Base.
Base.
0.55
0.95
0.85
Fidelity unfform
0.75
0.65
Base, MO
CCA M1
0.55
CCA
Base.
0.45
50
100
150
200
250
300
350
400
50
100
150
200
250
300
350
400
Query
Query
Figure 16: Performance of the attack when the target model is not neural network. Surrogates M0 and M1 are neural networks with the architectures (20,10) and (20,10,5) respectively. Baseline T is surrogate model from the same class as the target model.

---

B.2.9 Studying effect of unbalanced Dattack
In all the other experiments, the attack dataset Dattack used by the adversary is sampled from class-wise balanced dataset. In this experiment we explore the effect of querying using an unbalanced Danack. Model architectures used are (20, 10) for the target model and surrogate model 0, and (20, 10, 5) for surrogate model 1. While the training set of the teacher and the test set of both and the surrogates were kept constant, the proportion of the samples in the attack set Datack was changed. first case, examples from class the majority of the examples were from class y 0 (80%). The results shown in Fig. 17
teacher
were dominant (80%) and in the second case,
class 0: 0.2, class
class
1.0
Fidelity over test data
0.9
Base, MO CCA MO
Base. M1 CCA M1
0.85
1.0
Fidelity over uniform data
0.95
0.9
Base.
Base.
CCA
0.85
100
200
300
400
100
150
250
300
350
400
Query
Query
Figure 17: Results corresponding to the HELOC dataset with queries sampled from biased versions of the dataset (i.e., a biased Da The version on the left uses Dannck with 20% and 80% examples from classes 0 and 1, respectively. The version the right was obtained with a D comprising of 80% and 20% examples from classes = and = 1, respectively.
B.2.10 Studying alternate loss functions
We explore using binary cross-entropy loss function directly with labels 0, 1 and 0.5 in place of the proposed loss. Precisely, the surrogate loss is now defined as
L(m, y) (xxr) (z) log (m(()) (1 v())) log (1 (x))
(32)
which is symmetric around 0.5 for y(x) 0.5. Two surrogate models observed, with architectures (20, 10) for model and (20, 10, 5) for model 1. The target model's architecture is similar to that of model The ensemble size is 20.
The results (in Fig. indicate that the binary cross-entropy loss performs worse than the proposed loss. The reason might be the following: As the binary cross-entropy loss is symmetric around 0.5 for counterfactuals, it penalizes the counterfactuals that are farther inside the favorable region. This in turn pulls the surrogate decision boundary towards the favorable region more than necessary, causing a decision boundary shift.
25

---

Income
0.95
Fidelity over test data
0.85
BCE MO
BCE M1 CCA M1
CCA MO
0.65
0.55
0.45
0.95
Rielity over uniform data
0.85
0.75
0.65
0.55
MO
0.45
100
200
300
400
100
250
300
350
400
Query
Query
Figure 18: Performance of binary cross-entropy loss with labels 0, 0.5 and 1. Black lines correspond-
ing to binary cross entropy (BCE) loss and blue lines depict the performance of the CCA loss.
B.3 Experiments for verifying Theorem 3.2
This experiment includes approximating a spherical decision boundary in the first quadrant of d-dimensional space. The decision boundary is portion of sphere with radius and the origin at (1, 1, 1,..,, 1). The input space is assumed to be normalized, and hence, restricted to the unit hypercube. See Section 3.r a description of the attack strategy. Fig. preseents visualization of the experiment in the case where the dimensionality d = 2. Fig. presents a comparison of theoretical and empirical query complexities for higher dimensions. Experiments agree with the theoretical upper-bound.
1.00
0.75
0.50
0.25
0.00
0.0
0.5
1.0
x1
Figure 19: Synthetic attack for verifying Theorem 3.2 in the 2-dimensional case. Red dots represent queries and blue dots the corresponding closest counterfactuals. Dashed lines indicate the boundary of the polytope approximation.
26

---

In
d 15
6
4.0
455
5.0
5.5
6.0
6.5
In(n)
Figure 20: Verifying Theorem of convergence.
3.2 Dotted and solid lines indicate the theoretical and empirical rates
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: made.
Abstract and introduction correctly summarize and highlight the main claims
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Assumptions each theorem are specified on the spot. Paper also includes a discussion limitations and future work in the appendix.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
27

---

The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't It acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Assumptions corresponding to each thcoretical result are stated immediately before the theorems. Proofs for all the results are presented in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Details pertaining to all the experiments, including model architectures, datasets, querying strategy, of training epochs presented in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (c.g., in the case
28

---

of a large language model), releasing of a model checkpoint, or other means that are
appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g.. a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (c.g.. with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: While all the datasets used in the experiments are publicly available, we have made the code public as Github repository, which the link is given in the Introduction.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm cc/
public/guides httpe////oooeeueeeeiiooosooooooo
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurIPS code and data submission guidelines (https
//iips.cc/pull wwt.cc//pllccgccccceee wwwpc//ggieeeeeeee httaa///giiiees/odeSuubissss www.smmmmsssioPo.e ssionooiicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: Details pertaining to each experiment are given in the corresponding sections of the appendix.
Guidelines:
29

---

The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: In the main experiments supporting the claim, we report standard deviations or variance along with the results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative eтror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: While the GPU models on which the experiments were done are listed the appendix, compute times have not been reported.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics Bhtniggttppr///orrror..cc/aaaaap
Answer: [Yes]
30

---

Justification:
The research conforms with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Implications of the theoretical results on privacy of the models are discussed next to the theorems. Appendix contains a separate section on the broader impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This research does not release any data models.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
31

---

12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All publicly available datasets that were used in the experiments have been cited.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paterssi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Paper does not release any assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Paper does not include experiments involving crowdsourcing or human sub- jects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
32

---

According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based on the requirements of your country institution) were obtained?
Answer: [NA]
Justification: Paper does not include experiments involving crowdsourcing human sub- jects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
33


Reviews:
[{"review_id": "zacK32p1WO", "reviewer": "Reviewer_VLao", "summary": "This paper studies model reconstruction attacks by using the proximity of counterfactuals to the decision boundary. The authors aim to establish theoretical guarantees for such attacks. To this end, they characterize the number of queries required for the attacker to achieve a given error in model approximation using results from polytope theory (Theorem 2). The authors’ main result from relies on the decision boundary being convex. To relax the convexity assumption, the paper additionally studies the case of underlying relu networks to be attacked and provides probabilistic bound on the reconstruction rate. Finally, the authors propose a strategy for model extraction.\n\nThe paper offers strengths in terms of proposing new tools to analyze model extraction attacks. The main theoretical results are covered for two models classes that are commonly used in recourse literature (linear models, and NNs with relu activations) Overall, the paper provides a good starting point for future research in the area of model extraction attacks through counterfactual explanations but further improvements would be necessary to generealize the analysis to general commonly used models such a tree based classifiers.", "questions": "Could the authors provide insights into their attempts to estimate the Lipschitz constant in practical applications? Considering the inherent difficulty in obtaining low Lipschitz constants for neural networks of reasonable size, the practicality of the Lipschitz result may be questionable. Clarifying this aspect would help in understanding the real-world applicability of their theoretical findings.", "limitations": "The authors did not mention any limitations of their work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- *New theoretical approach to study extraction attacks*: The paper introduces a fresh approach to studying model extraction attacks using counterfactual explanation algorithms, employing methodologies from polytope theory that I have not seen explored in this context before.\n- *New method*: The authors propose a new model extraction method.\n- *Clearly structured*: The paper is overall well written and clearly structured.", "weaknesses": "*Missing variety of recourse methods*: The paper would greatly benefit from a more comprehensive set of experiments that examine the viability of model reconstruction under various recourse settings. Specifically, incorporating experiments that generate counterfactuals with data manifold constraints [3,4] or consider robustness [1,2] would be highly valuable. Such experiments would clarify the conditions under which the proposed attacks are likely to succeed or fail, and could indicate potential defenses. For instance, if the attacks fail under certain counterfactual attack methods, this would highlight key characteristics necessary to ensure the safe use of recourse or counterfactual explanations. I strongly encourage the authors to include additional experiments addressing these aspects. Demonstrating the impact of these conditions would significantly strengthen the paper, and I would be happy to increase my score if such experiments are provided.\n\n---------\n**References**\n\n[1] \"Probabilistically Robust Recourse: Navigating the Trade-offs between Costs and Robustness in Algorithmic Recourse\", ICLR, https://arxiv.org/abs/2203.06768\n\n[2] \"Towards robust and reliable algorithmic recourse.\", NeurIPS, https://arxiv.org/abs/2102.13620\n\n[3] \"Learning model-agnostic counterfactual explanations for tabular data\", WWW, https://arxiv.org/abs/1910.09398\n\n[4] \"Towards realistic individual recourse and actionable explanations in black-box decision making systems\", arxiv, https://arxiv.org/abs/1907.09615", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their review and greatly appreciate the positive opinion about our work.\n\n**_On the variety of recourse methods:_** As per the suggestions of the reviewer, we have now implemented **ROAR** [Upadhyay et al.] and **C-CHVAE** [Pawelczyk et al.]  methods and will include them in our paper. \n\nWe considered the following counterfactual generating methods in the manuscript, including MCCF with L1 and L2 norms, DiCE actionable counterfactuals, 1-Nearest-Neighbor counterfactuals (counterfactuals from the data manifold) and DiCE counterfactuals with varying levels of sparsity (Section D.2.6 Table 5 and Fig. 16, 17). Now, we also include ROAR and C-CHVAE and present the consolidated results in **Rebuttal PDF** Table 7. We have also included histograms of the target prediction probabilities for counterfactuals generated by different methods.\n\nWe would like to highlight the fact that our strategy does not take into account any specifics of the generating method. Instead, what affects the performance is the distribution of the counterfactuals around the decision boundary. Histograms in the Rebuttal PDF Fig. 23 provide some insights on how the counterfactuals generated using different methods are distributed. Firstly, observe that our strategy CCA does not require closest counterfactuals but is able to reconstruct models quite faithfully for many of the other counterfactual generating methods even if they are not the closest.\n\nAdditionally, we also observe that the robust counterfactuals generated using the ROAR method have relatively higher prediction probabilities from the target model. As we may observe from these histograms, when the counterfactual distribution is concentrated around higher prediction probabilities (e.g.: in case of ROAR in the Rebuttal PDF or sparse DiCE with posthoc_sparsity_param=0.2 in the manuscript in section D.2.6. Fig. 16, 17), the advantage of CCA over the baseline diminishes.\n\nWe will include a detailed discussion on these observations in the paper.\n\n**_On Lipschitz constants:_** In the experiments discussed in Section D.2.4 of the manuscript, we approximate the Lipschitz constant with the product of spectral norms of the weight matrices (following [Gouk et al., 2021]). A recent ICLR paper [Khromov and Singh] studies the tightness of this upper-bound as well as a lower-bound computed using the gradients around a subset of input instances. They point out that in practice, the actual Lipschitz constant lies more closer to the lower bound. They report the lower bound for a fully connected MLP with a layer width of 256 to be less than 40 [Khromov and Singh, Fig. 1]. \n\nIt is also noteworthy that Theorem 3.10 and Corollary 3.11 require the Lipschitz behavior only for a local region of any given input instance, provided that the counterfactuals are well-spread across the decision boundary. This local Lipschitz behavior is a much looser constraint than the global Lipschitzness.\n\nIn essence, Lipschitzness attempts to capture the well-behavedness of the target model, in that it does not change very erratically. There may be scenarios where a model is reasonably well-behaved except in few regions which is captured by another body of work called probabilistic Lipschitzness. Such a probabilistic Lipschitz approach [Khan et al.] in conjunction with our result might generalize to a broader class of machine learning models, which can be a path for future exploration.\n\n\n[Upadhyay et al.] Upadhyay, S., Joshi, S., & Lakkaraju, H. (2021). Towards robust and reliable algorithmic recourse. Advances in Neural Information Processing Systems, 34, 16926-16937.\n\n[Pawelczyk et al.] Pawelczyk, M., Broelemann, K., & Kasneci, G. (2020, April). Learning model-agnostic counterfactual explanations for tabular data. In Proceedings of the web conference 2020 (pp. 3126-3132).\n\n [Gouk et al., 2021] Gouk, H., Frank, E., Pfahringer, B., & Cree, M. J. (2021). Regularisation of neural networks by enforcing lipschitz continuity. Machine Learning, 110, 393-416.\n\n[Khromov and Singh] Khromov, G., & Singh, S. P. (2024). Some Fundamental Aspects about Lipschitz Continuity of Neural Networks. In The Twelfth International Conference on Learning Representations.\n\n[Khan et al.] Khan, Z. Q., Hill, D., Masoomi, A., Bone, J. T., & Dy, J. (2024, April). Analyzing Explainer Robustness via Probabilistic Lipschitzness of Prediction Functions. In International Conference on Artificial Intelligence and Statistics (pp. 1378-1386). PMLR.", "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": "bY3qAZYier", "reviewer": "Reviewer_Bnbn", "summary": "The paper presents an approach to mitigate the decision boundary shift problem of counterfactual-based model reconstruction algorithms. They leverage the fact that counterfactuals differ from ordinary instances since they exist relatively close to the decision boundary, to derive a novel loss function for model reconstruction that provides special treatment to counterfactuals. The theoretical foundations of this work are based on polytope theory, using which the authors derive a relationships between the error in model reconstruction and the number of required counterfactual samples. Experimental results show that the proposed approach surpasses the baseline on a number of model reconstruction benchmarks.", "questions": "Please refer to the Weaknesses section.", "limitations": "The limitations of this work have been adequately discussed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is very clearly written. The authors set a concise and understandable stage for the problem of model reconstruction using counterfactual explanations, and explaining the limitation of decision boundary shift that the existing models face due to treating counterfactuals same as ordinary samples. They zero-in on their approach motivated by a sound theoretical basis which establishes a relationship between the error in model reconstruction and number of required counterfactual examples using polytope theory.\n\n2. The theoretical results are intuitive. The authors derive rates at which the success of model reconstruction changes in terms of the decision boundary complexity and the number of samples for linear models. Further they provide a bound on the model reconstruction error based on the observation that deep ReLU networks can be represented as Continuous Piece-wise Linear functions, whose decision boundaries form collections of polytopes.\n\n3. The proposed approach provides state-of-the-art results on multiple benchmarks over the existing baseline for counterfactual-based model reconstruction.", "weaknesses": "1. Is there any dependency of the proposed method on the counterfactual generating method MCCF, or in other words, the quality/nature of the counterfactuals used?\n\n2. A comparison of the proposed method with regular approaches (that treat counterfactuals and ordinary samples the same) like [Wang et al., 2022] using two sided counterfactuals could help solidify the contributions. I can understand that it might sound like an unfair comparison, but one should not necessarily expect the proposed CCA to outperform models using two-sided counterfactuals. This is just to get an understanding of how close can one get (using a model like CCA) to such two-sided counter-factual based approaches, by just using one-sided counterfactuals.\n\n3. Comparing just with a single baseline seems a bit insufficient. Perhaps a discussion on how this work relates to model inversion attacks (such as [a,b]) would add to the completeness of the paper.\n\nReferences:\n\n[a] Zhao et al., \"Exploiting Explanations for Model Inversion Attacks\", ICCV 2021.\n\n[b] Struppek et al. \"Plug & Play Attacks: Towards Robust and Flexible Model Inversion Attacks\", ICML 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful for the detailed review and the important suggestions. \n\n**_Dependency on counterfactual generating method:_** The performance of the proposed method does not depend on the specific counterfactual generating method, except for the proximity of the generated counterfactuals to the decision boundary. CCA does not take any specifics of the generating method into account. However, the proximity to the decision boundary depends largely on the generating method. Therefore, we have considered several counterfactual generating methods in the experiments (Section D.2.6, Table 5 in manuscript). Furthermore, following the suggestions of Reviewer VLao, we have included two more counterfactual generating methods: **ROAR** [Upadhyay et al.] and **C-CHVAE** [Pawelczyk et al.] in the Rebuttal PDF (Table 7). In addition, we have included histograms of the predictions made by the target model on the generated counterfactuals and the query instances (see Rebuttal PDF Fig. 23).  They provide insights into the distribution of counterfactuals around the decision boundary. As evident from these, the CCA performance generalizes to a wide range of counterfactual generating methods as well as different counterfactual distributions w.r.t. the decision boundary. \n\nMoreover, we have discussed the effect of counterfactual sparsity on CCA performance in Section D.2.6 of the manuscript. It has been observed that the stricter the sparsity constraint gets, a significant amount of counterfactuals tend to lie further away from the decision boundary (Fig. 16). This in turn causes the gap between the baseline method and CCA to reduce (Fig. 17). We report some values in the table below for easy reference. An extreme effect of this nature can be observed in case of the ROAR generating method (Rebuttal PDF Table 7).\n\nQuery size=100, fidelity over **test** data (psp=posthoc_sparsity_param – sparsity increases with increasing psp)\n|Model|psp=0.1|psp=0.2|\n|:---|:---:|:---:|\n|Base. M0|0.97|0.97|\n|CCA M0|0.98|0.96|\n|Base. M1|0.97|0.98|\n| CCA M1 |0.98|0.98|\n\nQuery size=100, fidelity over **uniform** data\n|Model|psp=0.1|psp=0.2|\n|:---|:---:|:---:|\n|Base. M0|0.91|0.94| \n|CCA M0|0.92|0.90| \n|Base. M1|0.91|0.94| \n|CCA M1|0.94|0.95| \n\n**_Comparison with DualCFX_**: The related work [Wang et al.] is one of the few pioneering works studying the effects of counterfactuals on model extraction, which proposes the interesting idea of using counterfactuals of counterfactuals to mitigate the decision boundary shift. Based on the reviewer’s suggestion, we have now implemented DualCFX and included it in the Rebuttal PDF.\n\nThe primary focus of our work is on the one-sided scenario where an institution might be giving counterfactuals to rejected applicants to help them get accepted only but not to the accepted ones. As the reviewer has correctly pointed-out, a fair comparison cannot be achieved between CCA and the strategy proposed in [Wang et al.] in the scenario where only one-sided counterfactuals are available since DualCFX requires counterfactuals from both sides.\n\nTherefore, in the two-sided scenario, we compare the performance of CCA with the DualCFX strategy proposed in [Wang et al.] under two settings: \n1. only one sided counterfactuals are available for CCA (named CCA1);\n2.  CCA has all the data that DualCFX has (named CCA2). \n\nWe also include another baseline (following [Aïvodji et al.]) for the two-sided scenario where the models are trained only on query instances and counterfactuals, but not the counterfactuals of the counterfactuals. Results are presented in Table 6 of the Rebuttal PDF. Note that even for the same number of initial query instances, the total number of actual training instances change with the strategy being used (CCA1 < Baseline < DualCFX = CCA2 – e.g.: queries+CFs for the baseline but queries+CFs+CCFs for DualCFX).\n\n**_Related works in model inversion:_** We would like to thank the reviewer for suggesting two important related contributions. We will include a discussion on these works in a revised version of the manuscript.\n\nModel inversion is another form of extracting information about a black box model, under limited access to the model aspects. In contrast to model extraction where the goal is to replicate the model itself, in model inversion an adversary tries to extract the representative attributes of a certain class with respect to the target model. In this regard, [Zhao et al.] focusses on exploiting explanations for image classifiers such as saliency maps to improve model inversion attacks. [Struppek et al.] proposes various methods based on GANs to make model inversion attacks robust (for instance, to distributional shifts) in the domain of image classification. \n\n\n[Upadhyay et al.] Upadhyay, S., Joshi, S., & Lakkaraju, H. (2021). Towards robust and reliable algorithmic recourse. Advances in Neural Information Processing Systems, 34, 16926-16937.\n\n[Pawelczyk et al.] Pawelczyk, M., Broelemann, K., & Kasneci, G. (2020, April). Learning model-agnostic counterfactual explanations for tabular data. In Proceedings of the web conference 2020 (pp. 3126-3132).\n\n[Wang et al.] Wang, Y., Qian, H., & Miao, C. (2022, June). Dualcf: Efficient model extraction attack from counterfactual explanations. In Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency (pp. 1318-1329).\n\n[Aïvodji et al.] Aïvodji, U., Bolot, A., & Gambs, S. (2020). Model extraction from counterfactual explanations. arXiv preprint arXiv:2009.01884.\n\n [Zhao et al.] Zhao, X., Zhang, W., Xiao, X., & Lim, B. (2021). Exploiting explanations for model inversion attacks. In Proceedings of the IEEE/CVF international conference on computer vision (pp. 682-692).\n\n[Struppek et al.] Struppek, L., Hintersdorf, D., Correira, A. D. A., Adler, A., & Kersting, K. (2022, June). Plug & Play Attacks: Towards Robust and Flexible Model Inversion Attacks. In International Conference on Machine Learning (pp. 20522-20545). PMLR.", "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": "LjdM7uKIzx", "reviewer": "Reviewer_z1A7", "summary": "The paper proposed a model reconstruction methodology by using one-sided counterfactual explanations. After generating counterfactuals (assumed to be the closest counterfactual to the observation), the authors reconstruct the original model using a piece-wise linear approximation (with a bunch of hyperplanes). The key idea is that such hyperplanes can be identified by the pair of observation and its closest counterfactual, of which the the joining-line is straightforwardly perpendicular to the model's decision boundary. The paper discussed convex and non-convex decision regions, and demonstrated that the general non-convex case is challenging for being approximated with finite number of counterfactual explanations. Nevertheless, the authors showed that given sufficiently many counterfactual explanations (queries), a ReLU neural network can still be reconstructed. The experiment results demonstrated improvement over one literature (served as baseline), for both the known architecture and unknown architecture of the ReLU network.\n\nThe paper is well-written and organized. The idea, to my knowledge, is novel. The paper goes into good depth for analysis, showing interesting insights.", "questions": "How does the \"polytope theory\" help the model reconstruction algorithm design? Namely, the foundation (Lemma 3.1), the fidelity expectation for the convex case (Theorem 3.2), and the reconstruction probability lower bound (Theorem 3.6) are proposed, but how could we use them to better reconstruct the model than existing counterfactual explanations based reconstruction methodologies?\n\nThe results in Table 1 have large confidence intervals. For example, in the column Architecture unknown (model 1), D_{uni}, and row DCCC, the baseline is 95+-2.2 and the proposed CCA is 95+-11.8 etc. Does this imply that the proposed method is not very stable? \n\nWhat if we assume that sufficient many queries can be made and then increase the number of queries from 400 to 4000? Will the performance of CCA go close to the baseline?", "limitations": "Yes, the authors have stated clearly some limitations, and foresee potential non-positive impact.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The idea of using counterfactual explanations together with piece-wise linear approximation for model reconstruction, to my knowledge, is novel. The quality of writing and presentation is fairly clear.", "weaknesses": "The key limitation of this paper is that all the theories hold if the counterfactuals are the closest ones to the observations, which is difficult to be guaranteed utilizing counterfactual explanations algorithms. One way to deal with this is to consider in the derived theory some tolerance on the counterfactual's quality. Namely, if an algorithm is able to find counterfactuals within a given radius epsilon of the closest counterfactual, then how does this affect model construction.\n\nThe connection between the proposed theory and the effectiveness of the authors model construction methodology is not stated. Namely, algorithm 1 could stand alone without any of the derived theories.\n\nTheorem 3.6 relies on the assumption that each cell only contains completely linear part of the model's decision boundary, with one closest counterfactual in each cell. In order to make the first part (that only linear part is contained in a cell) holds for most of the cells, one has to make the edge of the cell (varepsilon) really small, which requires a massive amount of queries to be done. Hence, the assumption that is required to make this Theorem work, is too strong.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking out the time to review this paper, and appreciate their acknowledgement of the novelty of our work.\n\n**_On significance and limitations of theoretical results:_** Deriving theoretical bounds for model reconstruction using counterfactuals under general non-convex decision boundaries is a challenging problem. Our work proposes a novel non-trivial approach towards solving this problem through the lens of polytopes with assumptions for mathematical tractability. We will further elaborate on these assumptions in our limitations.\n\n1. **Closest counterfactuals:** We agree that assuming the availability of the closest counterfactuals in Theorems 3.2 and 3.6 limits their direct applicability into scenarios where the counterfactuals are reasonably close but not exactly the closest one. However, Theorems 3.2 and 3.6 still provide valuable insights into how counterfactuals might facilitate model reconstruction. E.g.: the empirical mean approximation error appears to be of $o(n^{-2/(d-1)})$ which is the theoretical rate of decay derived by assuming closest counterfactuals and convex decision boundaries (as discussed in Section D.2.3 of the manuscript).\n\n2. **Additional insights:** Moreover, Theorem 3.6 suggests that target models with simpler decision boundaries are easier to extract, and the Corollary 3.8 specifically shows why model reconstruction is mathematically easier when two-sided counterfactuals are available. Corollary 3.8 is quite relevant in the context of existing literature on model extraction which typically assume two-sided counterfactuals are available. For instance, an institution might give counterfactuals to rejected applicants but not necessarily to the accepted ones, leading to the one-sided counterfactual scenario.\n\n3. **Beyond closest counterfactuals:** In Section 3.3, we no longer assume the counterfactuals to be the closest, but they lie on the decision boundary, and provide guarantees under local Lipschitz assumptions (Theorem 3.10 and Corollary 3.11). We greatly appreciate the insightful suggestion to consider **a tolerance ball**, which can be included directly into Corollary 3.11. We will also include this suggestion in future works in conjunction with other relaxations such as probabilistically-Lipschitz assumptions [Khan et al.]. Algorithm 1 is motivated from the need to clamp the counterfactuals to the decision boundary as per our analysis in Theorem 3.10 and Corollary 3.11 (which will have further relaxations now using the tolerance ball).\n\n4. **Grid size:** Approximating a non-convex polytope becomes challenging due to facts such as it being impossible to be simply expressed as an intersection of half-planes leading us to explore ReLu networks whose decision boundaries are polytopes allowing for some mathematical traceability if the boundary is locally linear over some cells of a grid. We agree that the edge-cells (cells in which two or more high-dimensional facets are present) violate the assumption and hence, the grid size needs to be reduced (though such edge cells might be fewer in comparison to the entire set of boundary cells). \n\nNonetheless, we believe that our approach is a non-trivial approach towards solving this challenging problem. **The number of linear regions of a ReLU network in practice has been observed to be far less than the theoretically achievable maximum** [Hanin and Rolnick]. Moreover, [Jordan et al.] suggests that the decision regions can be represented as polyhedral complexes, which are a specific type of unions of convex polytopes. This may further reduce the number of high-dimensional edges that would occur in practice, as opposed to the worst-case scenario. Therefore, the required size of the grid might actually depend largely on the complexity of the classification problem.\n\n**_Variability of results in Table 1:_** The results in Table 1 have been averaged after training 100 different target models, generating queries and counterfactuals for them multiple times, and then surrogate models for each case. As pointed out by the reviewer, the standard deviation is a bit high for one setup, but for most others, it is fairly reasonable and comparable to the existing methods of model extraction using counterfactuals.\n\n**_Significantly higher number of queries:_** For a very high number of queries, the performance depends on how the positive and negative queries are actually distributed. Sometimes, we observe that good fidelity is achieved for both CCA and baseline possibly because the positive and negative queries dominate a lot more over the counterfactuals. Though, in a few cases, the fidelity of the baseline does not keep increasing with the number of queries and saturates because it treats the counterfactuals as points with label 1, and hence suffers from decision boundary shift issue (in this situation, ignoring the counterfactuals entirely or using CCA might be helpful than treating them as label 1 instances). \n\n\n[Khan et al.] Khan, Z. Q., Hill, D., Masoomi, A., Bone, J. T., & Dy, J. (2024, April). Analyzing Explainer Robustness via Probabilistic Lipschitzness of Prediction Functions. In International Conference on Artificial Intelligence and Statistics (pp. 1378-1386). PMLR.\n\n[Hanin and Rolnick] Hanin, B., & Rolnick, D. (2019, May). Complexity of linear regions in deep networks. In International Conference on Machine Learning (pp. 2596-2604). PMLR.\n\n[Jordan et al.] Jordan, M., Lewis, J., & Dimakis, A. G. (2019). Provable certificates for adversarial examples: Fitting a ball in the union of polytopes. Advances in neural information processing systems, 32.", "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": "JxcvpPhpLu", "reviewer": "Reviewer_J5Uq", "summary": "This paper presents a novel and valuable theoretical analysis leveraging polytope theory to provide novel insights into using counterfactual explanations for model reconstruction and significant contribution to the field of model reconstruction/interpretability of black box models.  The key contributions are:\nProviding a geometric interpretation of how counterfactuals relate to the decision boundary using polytope geometry.\nDeriving bounds on the expected approximation error of the reconstructed model as a function of the number of counterfactual queries .\nExtending the analysis to handle cases where only approximate closest counterfactuals are available using Lipschitz continuity.\nProposing the Counterfactual Clamping Attack (CCA) which treats counterfactuals differently in the loss function to prevent decision boundary shift during training of the surrogate model.\nDemonstrating CCA's improved performance over baselines on multiple real-world datasets, including with one-sided counterfactuals.", "questions": "1. Have you explored the application of CCA to other models like tree ensembles, XGBoost or others which might have non continuous / non differentiable decision boundaries? \n2. Have you explored into the computational complexity and memory requirements of CCA, especially when scaling to high-dimensional data or large datasets for example in comparison to other standard model reconstruction methods for practical applications of the approach?\n3. Any exploration of sensitivity of CCA's performance to the quality (e.g., sparsity, realistic) of the counterfactual instances used?", "limitations": "The theoretical analysis is limited to neural network architectures and assumes convex/concave decision boundaries. The authors should discuss the applicability to other model families like tree ensembles.\nWhile bounds on approximation error are derived, there is limited analysis of the computational complexity and scalability of the proposed Counterfactual Clamping Attack (CCA) to high-dimensional data or large datasets.\nThe paper does not explore the effect of counterfactual quality criteria like sparsity and similarity on CCA's model extraction performance, which is important for real-world applications.\nThe empirical evaluation is focused on classification tasks. More analysis on regression problems or tasks with complex decision boundaries is needed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Providing novel theoretical insights into the relationship between counterfactuals and the decision boundary geometry using polytope theory.\nDeriving mathematical bounds relating approximation error to the number of counterfactual queries.\nProposing CCA which mitigates decision boundary shift, a key issue with prior counterfactual-based model extraction approaches.\nExtensive empirical evaluation validating CCA's effectiveness across datasets.", "weaknesses": "Limited discussion on the applicability of CCA to model families beyond neural networks like tree based models XGBoost, Random Forest which are most commonly used for problems discussed like loan decisions. The loss function and counterfactual generation process may need adaptations.\nLack of analysis on the computational complexity and scalability of CCA, especially for high-dimensional data or large datasets. Generating closest counterfactuals can be computationally expensive.\nNo exploration of the effect of counterfactual quality aspects like sparsity, actionability or realness on CCA's performance. The paper does not analyze how enforcing quality constraints on counterfactuals impacts CCA's ability to accurately reconstruct the target model's decision boundary.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for reading the paper and appreciate their detailed review. \n\n**_CCA for other machine learning models:_** The proposed CCA algorithm, being implemented through a modified loss function, in its current form is limited to neural networks. However, the initial theoretical development, specifically, Theorem 3.2 and Corollary 3.11 are applicable to models with a convex decision region or models that are Lipschitz continuous, respectively. Extending Algorithm 1 to other models, as suggested by the reviewer, is an important path for exploration in the future. \n\n**_Computational complexity:_** In comparison to existing strategies of **model extraction specifically using counterfactuals** [Aïvodji et al., Wang et al.], our model training process in Algorithm 1 is the usual, except for the two factors: the loss function and the training dataset. Our loss function does not have any significant impact on the computational complexity or the memory requirement, since it involves typical mathematical operations such as addition and multiplication. \n\nOn the other hand, the training set includes counterfactual explanations and regular datapoints. We note that **computing counterfactual explanations can be computationally intensive,** particularly when the data is high-dimensional, and also varies based on the generation method chosen. We assume this increased computational burden is on the API’s side. Therefore, the reconstruction strategy is not directly affected by the computational complexity or memory requirements of computing the counterfactuals. \n\nThough, we acknowledge that it would indeed be **an interesting discussion** if considering the overall computational complexity of both parties including both model training and the API’s counterfactual generation complexity. [Aïvodji et al.] shows that model extraction using counterfactuals has better performance using fewer queries than traditional methods which do not use counterfactuals. DualCFX [Wang et al.] further improves performance at the expense of requiring the counterfactual of counterfactuals. Our work eliminates the requirement of the counterfactuals of counterfactuals by specifically leveraging the fact that counterfactuals are close to the decision boundary. **The benefit of model extraction specifically using counterfactuals does come at the additional computational cost of generating counterfactuals in the first place.** The exact cost depends on the strategy being used.\n\n**_Sensitivity to the quality of counterfactuals:_** We considered the following counterfactual generating methods in the manuscript, including MCCF with L1 and L2 norms, DiCE actionable counterfactuals, 1-Nearest-Neighbor counterfactuals (counterfactuals from the data manifold) and DiCE counterfactuals with varying levels of sparsity (Section D.2.6 Table 5 and Fig. 16, 17). Now, we also include ROAR [Upadhyay et al.] and C-CHVAE [Pawelczyk et al.]  and present the consolidated results in Rebuttal PDF Table 7. We have also included histograms of the prediction probabilities for counterfactuals generated by different methods.\n\nWe would like to highlight the fact that our strategy does not take into account any specifics of the generating method. Instead, what affects the performance is the distribution of the counterfactuals around the decision boundary. Histograms in the Rebuttal PDF Fig. 23 provide some insights on how the counterfactuals generated using different methods are distributed. Firstly, observe that our strategy CCA does not require closest counterfactuals but is able to reconstruct models quite faithfully for many of the other counterfactual generating methods even if they are not the closest.\n\nAdditionally, we also observe that the robust counterfactuals generated using the ROAR method have relatively higher prediction probabilities from the target model. As we may observe from these histograms, when the counterfactual distribution is concentrated around higher prediction probabilities (e.g.: in case of ROAR or sparse DiCE with posthoc_sparsity_param=0.2 – see manuscript section D.2.6. Fig. 16, 17), the advantage of CCA over the baseline diminishes.\n\nWe will include a detailed discussion on these observations in the paper.\n\n[Wang et al.] Wang, Y., Qian, H., & Miao, C. (2022, June). Dualcf: Efficient model extraction attack from counterfactual explanations. In Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency (pp. 1318-1329).\n\n[Aïvodji et al.] Aïvodji, U., Bolot, A., & Gambs, S. (2020). Model extraction from counterfactual explanations. arXiv preprint arXiv:2009.01884.\n\n[Upadhyay et al.] Upadhyay, S., Joshi, S., & Lakkaraju, H. (2021). Towards robust and reliable algorithmic recourse. Advances in Neural Information Processing Systems, 34, 16926-16937.\n\n[Pawelczyk et al.] Pawelczyk, M., Broelemann, K., & Kasneci, G. (2020, April). Learning model-agnostic counterfactual explanations for tabular data. In Proceedings of the web conference 2020 (pp. 3126-3132).", "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:
We thank all the reviewers for their insightful comments and suggestions. We are glad that our work has been recognized as an “in-depth analysis of a novel model reconstruction strategy” by Reviewer z1A7 and as a “good starting point for future works” by Reviewer VLao. 

Model reconstruction using counterfactuals has received limited attention when compared to the vast literature of model extraction strategies using other cues. Within the scope of model extraction using counterfacuals, the existing works focus on scenarios where the counterfactuals are available from both sides of the decision boundary. Moving beyond this requirement, our work proposes a novel extraction strategy that utilizes counterfactuals lying only in the accepted region. We arrive at this strategy by analyzing such attacks through the lens of polytope theory. Moreover, we provide a comprehensive set of experiments comparing existing strategies with ours.

In addition to the individual responses/clarifications, we have conducted the following additional experiments as per the reviewer suggestions: 
1. Two additional counterfactual generating methods (**ROAR** [Upadhyay et al.] and **C-CHVAE** [Pawelczyk et al.]) as suggested by Reviewer VLao
2. Comparing CCA with the **DualCFX** method proposed in [Wang et al.] as suggested by Reviewer Bnbn

Results of these experiments are included in the attached **Rebuttal PDF**.



[Upadhyay et al.] Upadhyay, S., Joshi, S., & Lakkaraju, H. (2021). Towards robust and reliable algorithmic recourse. Advances in Neural Information Processing Systems, 34, 16926-16937.

[Pawelczyk et al.] Pawelczyk, M., Broelemann, K., & Kasneci, G. (2020, April). Learning model-agnostic counterfactual explanations for tabular data. In Proceedings of the web conference 2020 (pp. 3126-3132).

[Wang et al.] Wang, Y., Qian, H., & Miao, C. (2022, June). Dualcf: Efficient model extraction attack from counterfactual explanations. In Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency (pp. 1318-1329).

Meta-review: This paper Counterfactual Clamping that approximates the boundary of a convex classification region by counterfactual queries. The paper contains the performance guarantees for the fidelity measured between the true boundary and the approximated boundary. All four reviewers appreciate the new perspective of polytope theory for the (counterfactual) explanation problem. I thus recommend to accept this paper.
Decision: Accept (poster)