# Text-to-Image Models for Counterfactual Explanations: a Black-Box Approach

Guillaume Jeanneret, Loïc Simon, Frédéric Jurie
Normandy University, ENSICAEN, UNICAEN, CNRS, GREYC, France
<EMAIL_ADDRESS>
###### Abstract

This paper addresses the challenge of generating Counterfactual Explanations
(CEs), involving the identification and modification of the fewest necessary
features to alter a classifier’s prediction for a given image. Our proposed
method, Text-to-Image Models for Counterfactual Explanations (TIME), is a
black-box counterfactual technique based on distillation. Unlike previous
methods, this approach requires solely the image and its prediction, omitting
the need for the classifier’s structure, parameters, or gradients. Before
generating the counterfactuals, TIME introduces two distinct biases into
Stable Diffusion in the form of textual embeddings: the context bias,
associated with the image’s structure, and the class bias, linked to class-
specific features learned by the target classifier. After learning these
biases, we find the optimal latent code applying the classifier’s predicted
class token and regenerate the image using the target embedding as
conditioning, producing the counterfactual explanation. Extensive empirical
studies validate that TIME can generate explanations of comparable
effectiveness even when operating within a black-box setting.

##  1 Introduction

Recently, deep neural networks (DNN) have seen increased attention for their
impressive forecasting abilities. The use of deep learning in critical
applications, such as driving automation, made the scientific community
increasingly involved in what a model is learning and how it makes its
predictions. These concerns shed light on the field of Explainable Artificial
Intelligence (XAI) in an attempt to “open the black-box” and decipher its
induced biases.

Counterfactual explanations (CEs) are an attempt to find an answer to this
previous problem. They try answering the following question: _What do we need
to change in $X$ to change the prediction from $Y$ to $Z$_? Because CEs give
intuitive feedback about what to change to get the desired result, two
applications use these explanations: feedback recommendation systems and
debugging tools. Take an automated loan approval system as an example. From a
user’s point of view, if it gets a negative prediction, the user would be more
interested in knowing what plausible changes can be made to get a positive
result, rather than having an exhaustive list of explanations for why the
result is unfavorable. From the debugger’s point of view, it can look for
biases that were considered in the decision when they should not have been,
thus revealing the classifier’s weaknesses.

Method | Model | Training | Specificity | Optim.
---|---|---|---|---
DiVE [39] | VAE | Days | Only DNN | Yes
STEEX [23] | GAN | Days | Only DNN | Yes
DiME [24] | DDPM | Days | Only DNN | Yes
ACE [25] | DDPM | Days | Only DNN | Yes
TIME (Ours) | T2I | Hours | Black-Box | No
Table 1: Advantages of the proposed methodology. TIME uses a pre-trained T2I
model and trains only a few textual embeddings, requiring hours of training
instead of days. It does not require access to the target model (completely
black-box) and does not involve any optimization during counterfactual
generation.

While there are multiple ways to address this question for visual systems,
_e.g_. by adding adversarial noise [16], the modifications must be sparse and
comprehensive to provide insight into which variables the model is using. To
this end, most studies for CEs use generative models, such as GANs [15],
Denoising Diffusion Probabilistic Models (DDPMs) [19], or VAEs [30], as they
provide an intuitive interface to approximate the image manifold and constrain
the generation in an appropriate space. Although they have several advantages,
training these generative models is cumbersome and may not yield adequate
results, especially when the data is limited [27]. To this end, we expect that
the use of large generative models trained on colossal datasets, such as
LAION-5B [43], can provide a sufficient tool to generate CEs. On the one hand,
these generative models have shown remarkable qualitative performance, an
attractive feature to exploit. Second, since the generative model is already
optimized, it can be used to capture data set specific concepts - _e.g_.
textual inversion [12] captures the main aspects of a target object when
subject to only three to five images.

In this paper, we explore how to take advantage of Text-to-Image (T2I)
generative models for CEs - specifically, using Stable Diffusion [10]. To do
so, we take a distillation approach to transfer the learned information from
the model into new text embeddings to align the concept class in text space.
Second, we use inversion techniques [49] to find the optimal noise to recover
the original instance. Finally, with our distilled knowledge, we denoise this
optimal point to recover the final instance using the target label, thus
generating the CE. This is advantageous because we can tackle the challenging
scenario of explaining a black-box model, _i.e_. having access only to its
predictions.

Our proposed approach has three main advantages over previous literature, as
shown in Table 1. First, we only train some textual embeddings, making the
training efficient, while previous methods require training a generative model
from scratch. Second, we do not require an optimization loop when generating
the final counterfactual, which reduces the generation time. Finally, our
explainability tool works in a completely black-box environment. While most
modern approaches [39, 23, 24, 51, 25] are DNN-specific, because they rely on
gradients, our approach, which uses only the output and input as cues, can be
used to diagnose any model regardless of its internal functioning. This
setting is crucial for privacy-preserving applications, such as medical data
analysis, since eliminating access to the gradients could prevent data leakage
[54], as it helps protect personal or confidential information.

We summarize our contributions as follows:

  * •

We propose TIME: Text-to-Image Models for Counterfactual Explanations, using
Stable Diffusion [10] T2I generative model to generate CEs.

  * •

Our proposed approach is completely black-box.

  * •

Our counterfactual explanation method based on a distillation approach does
not require any optimization during inference, unlike most methods.

  * •

From a quantitative perspective, we achieve similar performance to the
previous state-of-the-art, while having access only to the input and the
prediction of the target classifier.

##  2 Related Work

###  2.1 Explainable Artificial Intelligence

The research branch of XAI broads multiple ways to provide insights into what
a model is learning. As a bird’s view analysis, there are two main
distinctions between methods: _Interpretable by-design_ architectures, and
_Post-Hoc_ explainability methods. The former searches to create algorithms
that directly expose why a decision was made [35, 8, 5, 3, 2, 22, 53]. Our
research study is based on the latter. Post-hoc explainability methods study
pretrained models and try to decipher the variables used for forecasting.
Along these lines, there are saliency maps [26, 37, 4, 44], concept
attribution [29, 11, 14], or distillation approaches into interpretable by-
design models [13]. In this paper, we study the on-growing branch of CEs [48].
In contrast to previous methods, these explanations are simpler and more
aligned with human understanding, making them appealing to comprehend machine
learning models.

###  2.2 Counterfactual Explanations

The seminal work of Watcher  _et al_. [48] defined what a counterfactual
explanation is and proposed to find them as a minimization problem between a
classification loss and a distance loss. In the image domain, optimizing the
image’s raw pixels produces adversarial noises [16]. So, many studies based
their work on Watcher  _et al_. [48]’s optimization procedure with a
generative model to regularize the CE production, such as variational
autoencoders [39], generative adversarial networks [23, 51, 28, 32, 45], and
diffusion models [24, 42, 25, 1]. In contrast to these works, our proposed
approach, TIME, is a distillation approach for counterfactuals. Our method
does not require any optimization loop when building the explanation, since we
transfer the learning into the T2I model. Furthermore, we do not require
access to the gradients of the target model but only the input and output,
making it black-box, unlike previous methods.

Co-occurent works analyze dataset biases using T2I models to create
distributional shifts in data [47, 38]. Although a valid approach to debug
datasets, we argue that these approaches do not search what a model learned
but instead a general strategy for the biases in datasets under distributional
shifts (_e.g_. it is normal to misclassify a dog with glasses since the model
was not trained to classify dog with glasses). Further, their proposed
approaches are computationally heavy, since they require fine-tuning Large
Language Models or optimizing each inversion step on top of Stable Diffusion.
Instead, ours requires training a word embedding, and the inference merely
requires Stable Diffusion without computing any gradients, which fits into a
single small GPU.

###  2.3 Customization with Text-to-Image Models

Due to the interest in creating unimaginable scenarios with personalized
objects, customizing T2I diffusion models has gained attention in recent
literature. Textual Inversion [12] and following works [41, 7, 17, 52, 34] are
popular approaches to learn to generate specific objects or styles by fine-
tuning all or some part of the T2I model. Thus, the new concept can be used in
a phrase such that the T2I model will synthesize it.

One of the most difficult problems is editing real-world images with T2I
models. The pioneer work of Song _et al_. [46] proposed a non-stochastic
variant of DDPMs, called Denoising Diffusion Implicit Models (DDIM). Hence, a
single noise seed yields the same image. So, to find an approximate noise,
DDIM Inversion noises the image using the diffusion model. Yet, some problems
arise with this approximation. So, novel works [33, 36] modify the inversion
process by including an inner gradient-based optimization at each noising
step, making it unfeasible when analyzing a bundle of images. Finally, Wallace
_et al_. [49] proposed to modify the DDIM algorithm into a two-stream
diffusion process, reaching a “perfect” inversion. We take advantage of these
works and distill the learned information from a classifier to generate
counterfactual explanations of real images, a step to interpret the target
classifier.

##  3 Methodology

This section explains the proposed methodology for generating counterfactuals
using Text To Image (T2I) generative models. In section 3.1, we briefly
introduce some useful preliminary concepts of diffusion models. Then we
describe our proposed method in a three-step procedure. First, we explain how
to transfer what the classifier has learned into the generative model as a set
of new text tokens (Section 3.2). Second, using recent advances in DDIM
Inversion, we revert the image to its noise representation using the original
prediction of the classifier. Finally, we denoise the noisy latent instance
using the target label (Section 3.3).

###  3.1 DDPM Preliminaries

Diffusion models [19] are generative architectures that create images by
iteratively _removing_ noise. DDPMs are based on two inverse Markov chains.
The forward chain _adds_ noise, while the reverse chain _removes_ it. Thus,
the generation process is reverse denoising, starting from a random Gaussian
variable and removing small amounts of noise until a plausible image is
returned.

Formally, given a diffusion model $\epsilon_{\theta}$ and a fixed set of steps
$T$, $\epsilon_{\theta}$ takes as input a noisy image $x_{t}$ and the current
step $t$ to compute a residual shift. For the generation, $\epsilon_{\theta}$
updates $x_{t}$ following:

$x_{t-1}=\frac{1}{\sqrt{\alpha_{t}}}\left(x_{t}-\frac{1-\alpha_{t}}{\sqrt{1-\bar{\alpha}_{t}}}\epsilon_{\theta}(x_{t},t)\right)+\sigma_{t}z,$
(1)

where $\sigma_{t}$, $\alpha_{t}$ and $\bar{\alpha}_{t}$ are some predefined
constants, and $z$ and $x_{T}$ are extracted from a Gaussian distribution.
This process is repeated until $t=0$. To train a DDPM, given an image $x$,
each optimization step minimizes the loss:

$L(x,\epsilon,t,\cdot)=\|\epsilon-\epsilon_{\theta}(x_{t}(x,t,\epsilon),\,t,\cdot)\|^{2},$
(2)

where $\cdot$ are additional inputs for $\epsilon_{\theta}$ if available, and

$x_{t}(x,t,\epsilon)=\sqrt{\bar{\alpha}_{t}}\,x+\sqrt{1-\bar{\alpha}_{t}}\,\epsilon.$
(3)

The pioneering work of Ho  _et al_. [19] focused on training and evaluating
these models in the pixel space, making them computationally heavy. Latent
Diffusion Models [40] proposed to reduce this burden by performing the
diffusion process in the latent space of a Quantized Autoencoder [10].
Further, they augment the generation by using textual conditioning $C$ at its
core to steer the diffusion process, as well as increasing the quality of the
generation using Classifier-Free Guidance [20] (CFG).

The CFG [20]’s core modifies the sampling strategy in Eq. 1 by replacing
$\epsilon_{\theta}$ with $\epsilon_{\theta}^{f}$, a shifted version defined as
follows:

$\begin{split}\epsilon_{\theta}^{f}(x_{t},t,\cdot):=(1+w)\,\epsilon_{\theta}(x_{t},t,\cdot)-w\,\epsilon_{\theta}(x_{t},t,\varnothing),\end{split}$
(4)

where $\varnothing$ is the empty conditioning, resulting in a qualitative
improvement.

###  3.2 Distilling Knowledge into Stable Diffusion

To use large generative models, and in particular Stable Diffusion [40] for
CEs, we chose to distill the learned biases of the target classifier into the
generative model to avoid computing gradients of these massive architectures.

However, a model is subject to several biases as it learns, of which we
distinguish two. The first is a _context bias_. This bias refers to the way
images are formed. For example, ImageNet images [6] tend to have the object
(_e.g_., animals, cars, bridges) in the center, while CelebA HQ images [31]
are human faces. The second bias is class-specific, and it relates to the
semantic cues extracted by the classifier to make its decision, _e.g_. white
and black stripes for a zebra.

So, we take a textual inversion approach to distill the context bias and the
knowledge of the target classifier into the textual embedding space of Stable
Diffusion. In a nutshell, Textual Inversion [12] links a new text embedding
$e^{*}$ and an object (or style) such that when this new token is used, it
will generate this new concept. To achieve this, Gal  _et al_. [12] proposed
to train the new text embedding $e^{*}$ and link it to a new text-code $c^{*}$
and then train $e^{*}$ by minimizing the loss

$\mathbb{E}_{x\sim D,t\sim
U[1,T],\epsilon\sim\mathcal{N}(0,I)}\left[L(x,t,\epsilon,C)\right].$ (5)

Here, $D$ is the set of images containing the concept to learn and $U$ is the
uniform distribution of natural numbers between $1$ and $T$, and $C$ is a text
prompt containing the new text code $c^{*}$.

Accordingly, to distill the context bias into Stable Diffusion, we follow [12]
practices and learn a new textual embedding $e^{*}_{context}$ minimizing Eq. 5
using as the conditioning the phrase A $c^{*}_{context}$ picture. Here,
$c^{*}_{context}$ is the textual token related to textual embedding
$e^{*}_{context}$. In our setup, we used the complete training set of images
with no labels where the model was trained.

So far, we have not been required to use the classifier. To transfer the
knowledge learned by the classifier to the T2I generation pipeline, we follow
a similar approach. In this case, we train a new textual embedding $e^{*}_{i}$
for each class $i$ and represent its text token with $c^{*}_{i}$. However,
instead of using the full training dataset $D$, we used only those images that
the classifier predicted to be the source class $i$. As for the conditioning
sentence, we take the previously learned context token and add the new class
token to the sentence. Thus, we optimize Eq. 5 with the new phrase A
$c^{*}_{context}$ image with a $c^{*}_{i}$ and the filtered dataset.

###  3.3 Counterfactual Explanations Generation

Now we want to use the learned embeddings to generate explanations. Current
research on diffusion models has attempted to recover input images by
retrieving the best noise, such that when the DDIM sampling strategy is used,
it generates the initial instance. This is advantageous for our goal, since we
can use current technological advances to generate this optimal latent noise
and then inpaint the changes necessary to flip the classifier.

Since we need to perform perfect recovery to avoid most changes in the input
image, we use EDICT [49]’s perfect inversion technique. In fact, they showed
that inverting an image with a caption $C$ (Eqs 8) and then denoising it (Eqs.
7) with a new caption $C^{\prime}$, modified from $C$, will produce semantic
changes in the image. In short, EDICT modifies the DDIM [46] sampling strategy
for diffusion models into a two-flow invertible sequence. By introducing a new
hyperparameter $0<p<1$, setting $x_{0}$ and $y_{0}$ as the target image, and
new variables:

$\begin{split}a_{t}&=\sqrt{\bar{\alpha}_{t-1}/\bar{\alpha}_{t}}\\\
b_{t}&=\sqrt{1-\bar{\alpha}_{t-1}}-\sqrt{\bar{\alpha}_{t-1}(1-\bar{\alpha}_{t})/\bar{\alpha}_{t}},\end{split}$
(6)

the denoising phase becomes:

$\begin{split}x_{t}^{inter}&=a_{t}\,x_{t}+b_{t}\,\epsilon_{\theta}^{f}(y_{t},t,C)\\\
y_{t}^{inter}&=a_{t}\,y_{t}+b_{t}\,\epsilon_{\theta}^{f}(x_{t}^{inter},t,C)\\\
x_{t-1}&=p\,x_{t}^{inter}+(1-p)\,y_{t}^{inter}\\\
y_{t-1}&=p\,y_{t}^{inter}+(1-p)\,x_{t-1}.\end{split}$ (7)

In a similar vein, the inversion phase is the inverse of Eqs. 7:

$\begin{split}y_{t+1}^{inter}&=(y_{t}-(1-p)\,x_{t})\;/\;p\\\
x_{t+1}^{inter}&=(x_{t}-(1-p)\,y_{t+1}^{inter})\;/\;p\\\
y_{t+1}&=\frac{1}{a_{t+1}}(y_{t+1}^{inter}-b_{t+1}\,\epsilon_{\theta}^{f}(x_{t+1}^{inter},t+1,C))\\\
x_{t+1}&=\frac{1}{a_{t+1}}(x_{t+1}^{inter}-b_{t+1}\,\epsilon_{\theta}^{f}(y_{t+1}^{inter},t+1,C)).\end{split}$
(8)

We can see a clear connection between Wallace  _et al_. [49]’s work and our
main objective. If we invert an image using the caption with our context and
source class tokens and then denoise it using the target class token (learned
in Section 3.2), we can hope to generate the necessary changes to flip the
classifier’s decision.

However, while adapting the EDICT method, we noticed a major problem with this
approach. Although the chosen algorithm recovers the input instance, many
images were difficult to modify. To circumvent this issue, we had to adjust
the scores of the CFG in Eq. 4. As diffusion models are seen as score-matching
models, the term

$w(\epsilon_{\theta}(x_{t},t,C)-\epsilon_{\theta}(x_{t},t,\varnothing))$ (9)

in Eq. 4 are gradients pointing to the target distribution conditioned on $C$.
Thus, by including a negative drift term,

$-w(\epsilon_{\theta}(x_{t},t,C^{\prime})-\epsilon_{\theta}(x_{t},t,\varnothing)),$
(10)

we can lead the generation process _away_ from the source distribution
conditioned in $C^{\prime}$. Therefore, we reformulate the CFG scores
$\epsilon_{\theta}^{f}$, and rename it to $\epsilon_{\theta}^{c}$, as follows:

$\epsilon_{\theta}^{c}(x_{t},t,C,C^{\prime})=(1+w)\,\epsilon_{\theta}(x_{t},t,C)-w\,\epsilon_{\theta}(x_{t},t,C^{\prime}).$
(11)

Figure 1: TIME Overview. Our proposed method consists of three steps: i) We
learn a context token for the whole dataset using textual inversion. ii) We
filter out the images that the classifier predicts as source class $i$ and
learn a new embedding. iii) Finally, to generate the counterfactual
explanation, we invert the input image using a prompt containing the source
embedding and then denoise it using the target embedding.

As a result, and given the previously introduced notions, we propose Text-to-
Image Models for counterfactual Explanations (TIME), illustrated in Figure 1.
To leverage these big generative models, we first distill the context bias
into the pipeline’s text embedding space. Then, we transfer the knowledge of
the model into another textual embedding. Finally, given an input image to
analyze, we find the optimal noise with Eqs. 8 using $\epsilon_{\theta}^{c}$
as the score network (Eq. 11) and setting as the target conditioning the
source class and as the source conditioning the target class. Then, we denoise
the noisy state using Eqs. 7 but switch the target and source conditioning
texts.

##### Practical considerations.

Note that to avoid large changes in the images, we do not go to $T$, but to an
intermediate step $\tau$. In addition, we have found that using more than a
single embedding for the context and class biases yield further
expressiveness. Also, if we fail to find a valid counterfactual, we choose a
new $\tau$ and $w$ to rerun the algorithm. We will give the implementation
details later in Section 4.

##  4 Experimental Validation

##### Datasets and Models.

We evaluate our counterfactual method in the popular dataset CelebAHQ [31].
The task at hand is classifying smile and age attributes from face instances,
computed with a DenseNet121 [21] with an image resolution of $256\times 256$
as in [23, 25]. The evaluation is performed on the test set. To make the
assessment fair with previous methods, we used the publicly available
classifiers for CelebA HQ dataset from previous studies [23].

##### Implementation Details.

We based our approach on Stable Diffusion V1.4 [10]. For all dataset, we
trained three textual embeddings for the context and class biases for 800
iterations with a learning rate of 0.01, a weight decay of 1e-4, and a batch
size of 64. For the inference, we used the default EDICT’s hyperparameter
$p=0.93$ and a total of 50 steps. For the smiling attribute, we begin the CE
generation with $(\tau,w)=(25,3)$. In case of failure, we increased the tuple
to $(30,4),(35,4)$ or $(35,6)$. For the age attribute, we used
$(\tau,w)\in\\{(30,4),(30,6),(35,4),(35,6)\\}$. We performed all training and
inference in a Nvidia GTX 1080.

Figure 2: Qualitative Results. We present qualitative examples and compare them to the previous state of the art. DiME generates some out-of-distribution noise, while ACE creates blurry image sections. In contrast, TIME produces more realistic changes by harnessing the generative power of the T2I model. Method | Smile | Age
---|---|---
FID | sFID | FVA | FS | MNAC | CD | COUT | FID | sFID | FVA | FS | MNAC | CD | COUT
DiVE [39] | 107.0 | - | 35.7 | - | 7.41 | - | - | 107.5 | - | 32.3 | - | 6.76 | - | -
STEEX [23] | 21.9 | - | 97.6 | - | 5.27 | - | - | 26.8 | - | 96.0 | - | 5.63 | - | -
DiME [24] | 18.1 | 27.7 | 96.7 | 0.6729 | 2.63 | 1.82 | 0.6495 | 18.7 | 27.8 | 95.0 | 0.6597 | 2.10 | 4.29 | 0.5615
ACE* $\ell_{1}$ [25] | 26.1 | 36.8 | 99.9 | 0.8020 | 2.33 | 2.49 | 0.4716 | 24.6 | 38.0 | 99.6 | 0.7680 | 1.95 | 4.61 | 0.4550
ACE $\ell_{1}$ [25] | 3.21 | 20.2 | 100.0 | 0.8941 | 1.56 | 2.61 | 0.5496 | 5.31 | 21.7 | 99.6 | 0.8085 | 1.53 | 5.4 | 0.3984
ACE* $\ell_{2}$ [25] | 26.0 | 35.2 | 99.9 | 0.8010 | 2.39 | 2.40 | 0.5048 | 24.2 | 34.9 | 99.4 | 0.7690 | 2.02 | 4.29 | 0.5332
ACE $\ell_{2}$ [25] | 6.93 | 22.0 | 100.0 | 0.8440 | 1.87 | 2.21 | 0.5946 | 16.4 | 28.2 | 99.6 | 0.7743 | 1.92 | 4.21 | 0.5303
TIME (Ours) | 10.98 | 23.8 | 96.6 | 0.7896 | 2.97 | 2.32 | 0.6303 | 20.9 | 32.9 | 79.3 | 0.6282 | 4.19 | 4.29 | 0.3124
Table 2: CelebAHQ Evaluation. While TIME does not outperform the state-of-the-
art metrics, our proposed method provides competitive performance while having
a black-box model, not requiring a fully trained model on the generative model
on the target dataset and no optimization during the CE generation, features
not presented before. ACE* is [25]’s method without their post-processing
method.

###  4.1 Quantitative Assessment

Assessing counterfactuals presents inherent challenges. Despite this, several
metrics approximate the core objectives of counterfactual analysis. We will
now provide a concise overview of each objective and its frequent evaluation
protocol, reserving an in-depth exploration of these metrics for the
supplementary material.

##### Validity.

First, we need to quantify the ability of the counterfactual explanation
method to flip the classifier. This is measured by the Success Ratio (SR aka
Flip Rate).

##### Sparsity and Proximity.

A counterfactual must have sparse and proximal editions. Several metrics have
been proposed to evaluate this aspect, depending on the data type. For face
images[39, 25, 45, 24], there are the face verification accuracy (FVA), face
similarity (FS), mean number of attributes changed (MNAC), and Correlation
Difference (CD). For general-purpose images, like BDD100k [50], the
quantitative assessment is done via the SimSiam Similarity ($S^{3}$) [25] and
the COUT metric [28].

##### Realism.

The CE research adapts its evaluation metrics from the generation field.
Hence, the realism of CEs is commonly measured with the FID [18] and sFID [25]
metrics but only in the correctly classified images.

##### Efficiency.

An efficiency analysis is often omitted by many methods. A crucial criterion
for counterfactual generation techniques is to minimize computation time for
generating explanations in “real time”. This aims to empower users to examine
multiple counterfactuals without extended delays. We evaluate this by
contrasting efficiency using floating point operations (FLOPs) per explanation
- where lower values signify superior performance - and by measuring the
average time taken to generate an explanation, specifically within our cluster
environment.

####  4.1.1 Main Results.

Table 2 shows the results of TIME and compares them to the previous
literature. Although we do not outperform the state-of-the-art in any metric,
we found that our results are similar even when our proposed method is
restricted to be black-box. Further, it does not require training of a
completely new generative model and does not rely on any optimization for CE
generation. For the realism metric, we expected to get a low FID [18] and sFID
[25] due to the use of Stable Diffusion and beat ACE [25]. However, ACE uses
an inpainting strategy to post-process their counterfactuals. This reduces
this metric because they keep most of the original pixels in their output. If
we remove the post-processing, the FID increases dramatically. With these
results, we confirm that T2I generative models are a good tool to explain
classifiers counterfactually in a black-box environment.

####  4.1.2 Qualitative Results

We show some qualitative results in Figure 2 and added more instances in the
supplementary material. First, we see that DiME [24], ACE [25], and TIME
generate very realistic counterfactuals, and the differences are mostly in the
details. However, the most notable changes are between ACE and our method.
When we check the regions where ACE made the changes, they are blurred. This
is due to their over-respacing to create the counterfactual. For DiME, we
checked and found that some of their modifications seem out-of-distribution,
for many cases. However, TIME produces realistic changes most of the time.
Finally, in our opinion, TIME alterations can be spotted with more ease.

####  4.1.3 Efficiency Analysis

We continue our analysis and study the efficiency of TIME when creating the CE
with respect to previous state-of-the-art methods, DiME [24] and ACE [25]. We
estimated that TIME uses $98$ TFLOPs and $45$ seconds to create a single
counterfactual, using $\tau=35$ as the worst case scenario. In contrast, ACE
took $279$ TFLOPs and $62$ second per CE while DiME took $1004$ TFLOPs and
$163$ seconds.

###  4.2 Ablations

Steps | GS | SR | FID | FS | CD
---|---|---|---|---|---
25 | 3 | 30.1 | 35.26 | 0.8957 | 2.82
4 | 41.0 | 30.23 | 0.8570 | 2.61
5 | 50.1 | 27.39 | 0.8231 | 2.33
30 | 3 | 62.1 | 23.15 | 0.8147 | 2.34
4 | 74.0 | 22.51 | 0.7710 | 2.66
5 | 80.8 | 23.51 | 0.7300 | 2.85
35 | 3 | 87.1 | 21.69 | 0.7227 | 2.63
4 | 92.9 | 24.37 | 0.6731 | 3.03
5 | 95.0 | 27.53 | 0.6306 | 3.54
Table 3: Steps-Scale trade-off. We analyze the trade-off between our hyperparameters $\tau$ and $w$. Our results show that increasing $\tau$ gives a strong boost in SR while impacting the other metrics and increasing the generation time. In contrast, $w$ has a similar effect but is less potent without any effect on the generation time. Context | SR | FID | FS | CD
---|---|---|---|---
Without | 73.9 | 23.47 | 0.7480 | 2.41
With | 92.9 | 24.37 | 0.6731 | 3.03
Table 4: Context token ablation. Here, we check the effect of including the
context embeddings into our pipeline. The main advantage is increasing the
success ratio. This result suggests that we can reduce $\tau$ to reach similar
results while being more efficient - less number of EDICT iterations.

To show the effectiveness of each component, we realized thorough ablation
experiments. To this end, we first show the hyperparameter exploration between
the depth of the chain of noise $\tau$ and the guidance scale $w$.
Additionally, we will show the effect of including multiple textual tokens,
the context tokens, and, finally, the effect of adding our negative drift –
please refer to the practical consideration in section 3.3 for the variable
$\tau$. Unless explicitly told, we set $\tau=35$ and $w=4$ for all the
ablations. For the dataset, we did the ablation using 1000 instances of the
CelebA HQ validation dataset for the smiling attribute. As the quantitative
metrics, we used the SR, the FID, the FS, and the CD.

Regarding the FID metric, please note that this metric is very sensible to the
number of images. When using fewer images, the FID becomes less reliable to
compare two methods, and hardly becomes intelligible if the two approaches are
evaluated on different number of images. Since we use the FID to compare
counterfactual on only those instances that flipped the classifier, comparing
FIDs where the SR varies significantly does not give any cues.

##### Steps and scale trade-off.

To begin with, we investigate the effect of the number inversion steps and the
scale of the guidance. We jointly explore both variables to check the best
trade-off, as shown in Table 3. At first glance, we notice that adding a
higher guidance scale or more noise inversion steps produces more successful
counterfactuals, assessed with the SR. Yet, it comes with a trade-off in other
compartments: namely, the quality of the CE, and the amount of editions into
the image. Generally, increasing $\tau$ or $w$ reflects a decrease in the
quality of the image and the increasing numbers of editions.

##### Learning the Context Token.

Continuing with our study, we analyze the inclusion of our novel context token
into our counterfactual generation pipeline. To ablate this component, we test
whether using our learned context tokens has any advantage in contrast to
giving a generic description. The results are in Table 4. As we can see,
including our tokens provides the best performance gains in terms of SR.
Qualitatively, the images are similar, yet, the images without context present
some artifacts in some cases. Furthermore, we see that removing the context
provides a boost in the CD and FS metrics. Although it seems counterintuitive
to include this component, we can easily reach these values by decreasing
$\tau$ or $w$ (_e.g_. setting $\tau=30$ and $w=4$, check Table 3), and
reducing the inference time.

##### Effect of the guidance.

We further explore the inclusion of the negative drift term in Eq. 10 and show
the results in Table 5. From the quantitative assessment, we initially
observed that using the classifier-free guidance (CFG in the Table) decreases
the SR. When denoising the current stage $x_{t}$ at time $t$, the CFG in Eq. 4
estimates gradients of the log-likelihood conditioned on $C^{\prime}$,
$-\nabla_{x_{t}}\log(p(x_{t}|C^{\prime}))$, [20] thus, pushing the generation
toward the distribution of $C^{\prime}$. In contrast, incorporating the
negative guidance (NG) helps steer the generation away from the distribution
conditioned on $C$. Therefore, the combined effect results in moving the
instance from the boundary decision. From a qualitative perspective, we did
not see major differences, although some instances were better when removing
the CFG. Nonetheless, as noted in the context of ablation, this can be easily
mitigated by reducing $w$ and $\tau$.

Guidance | SR | FID | FS | CD
---|---|---|---|---
CFG | 75.9 | 21.58 | 0.7749 | 2.34
NG | 92.9 | 24.37 | 0.6731 | 3.03
Table 5: Negative Guidance. Here, we check the effect of performing the negative guidance (NG) instead of the classifier-free guidance (CFG). The main advantage is increasing the success ratio. This result suggests that we can reduce $\tau$ to reach similar results while being more efficient. Tokens | SR | FID | FS | CD
---|---|---|---|---
Single | 88.1 | 22.02 | 0.7177 | 3.02
Multiple | 92.9 | 24.37 | 0.6731 | 3.03
Table 6: Multiple-tokens Ablation. We test if using multiple tokens in our
pipeline provides any advantage. The results show an increase in SR.

##### Multi-token Inclusion.

Finally, we explore using multiple tokens instead of a single one for both the
context and class embeddings, shown in Table 6. Without any surprise, we
noticed that using a single token reduces the SR by a small factor. This
aligns with the observations given by [12], a token catches enough information
of an object or style - or in this case, inductive biases. Like in previous
analyses, including multiple tokens will increase the efficiency of the model,
since we can reach similar performances by tuning $\tau$ or $w$.
Qualitatively, the most notable change between the images is sharpness.

##### Recommendations.

Given the previous results, we propose several recommendations for the user
and the model debugger, as explained in the introduction. Recall that the
counterfactual explanations are used as well to recommend changes to the user
to get a positive outcome. So, for the user, we recommend using the lower
amount of iterations $\tau$ and guidance scale $w$. This results in a
similarity increase and fewer edited characteristics (as evidenced by the CD
and FS metrics). If the algorithm fails, it is preferable to adjust the
guidance scale rather than the number of steps. For the debugger, always use
the context, the negative guidance, and multiple tokens. When building the
counterfactuals, follow the same recommendations for the user.

Figure 3: BDD100k, a limit for TIME. TIME changes the entire scene when generating the counterfactuals. Nevertheless, it still gives some insight into what the models have learned, as illustrated by the features inside the red boxes. Method | FID | sFID |  S3 | COUT | FR
---|---|---|---|---|---
STEEX | 58.8 | - | - | - | 99.5
DiME | 7.94 | 11.40 | 0.9463 | 0.2435 | 90.5
ACE $\ell_{1}$ | 1.02 | 6.25 | 0.9970 | 0.7451 | 99.9
ACE $\ell_{2}$ | 1.56 | 6.53 | 0.9946 | 0.7875 | 99.9
TIME (Ours) | 51.5 | 76.18 | 0.7651 | 0.1490 | 81.8
Table 7: BDD Assessement. We evaluate the performance of TIME on the complex
BDD100k benchmark. On this dataset, there is still room for improvement for
black-box counterfactual methods.

###  4.3 Limitations.

To test TIME in more complex scenarios, we generate CEs in the BDD100k [50]
dataset using a DenseNet121 [21] trained in a _move-forward/stop_ binary
classification, as in [23]. We show the quantitative evaluation in Table 7.
When generating the explanations, we noticed that TIME modifies most parts of
the image, unfortunately, as shown by the $S^{3}$ metric. This is expected, as
this task is challenging since it requires multiple factors to decide if to
stop or to move forward. Nevertheless, we believe that these explanations
still give some useful insights as a debugging tool. For example, Figure 3
shows that removing the red lights and adding motion blur will change the
classification from _stop_ to _move_ , as evidenced in [25], or adding objects
in front will flip the prediction to _stop_.

We believe that counterfactual methods for tasks dependent on complex scenes,
where the decision is impacted by large objects or co-occurrences of several
stimuli, require specific architectures. In fact, we noticed that ACE [25]
mainly adds some small modifications (_e.g_. changing the red lights), which
is not inaccurate but is too constrained and cannot explore more insights
about the learned features. Indeed, the work of Zemni  _et al_. [51] focuses
only on the object aspect of counterfactuals, in this case using an object-
centric generator, BlobGAN [9]. This suggests that general-purpose
counterfactual methods are not adapted for these tasks.

##  5 Conclusion

In this work, we present TIME, a counterfactual generation method to analyze
classifiers disregarding their architecture and weights, only by looking at
their inputs and outputs. By leveraging T2I generative models and a
distillation approach, our method is capable of producing CEs for black-box
models, a complex scenario not tackled before. Further, we show the advantages
and limitations of TIME and shed light on possible future works. We believe
that our approach opens the door to research focus on counterfactual methods
in the challenging scenario of the black-box models.

Acknowledgements Research reported in this publication was supported by the
Agence Nationale pour la Recherche (ANR) under award number ANR-19-CHIA-0017.

## References

  * [1] Maximilian Augustin, Valentyn Boreiko, Francesco Croce, and Matthias Hein.  Diffusion visual counterfactual explanations.  In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
  * [2] Moritz Bohle, Mario Fritz, and Bernt Schiele.  Convolutional dynamic alignment networks for interpretable classifications.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 10029–10038, June 2021.
  * [3] Moritz Böhle, Mario Fritz, and Bernt Schiele.  B-cos networks: Alignment is all we need for interpretability.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 10329–10338, June 2022.
  * [4] Aditya Chattopadhay, Anirban Sarkar, Prantik Howlader, and Vineeth N Balasubramanian.  Grad-cam++: Generalized gradient-based visual explanations for deep convolutional networks.  In 2018 IEEE Winter Conference on Applications of Computer Vision (WACV), pages 839–847, 2018.
  * [5] Chaofan Chen, Oscar Li, Daniel Tao, Alina Barnett, Cynthia Rudin, and Jonathan K Su.  This looks like that: Deep learning for interpretable image recognition.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
  * [6] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In 2009 IEEE conference on computer vision and pattern recognition, pages 248–255. Ieee, 2009.
  * [7] Wenkai Dong, Song Xue, Xiaoyue Duan, and Shumin Han.  Prompt tuning inversion for text-driven image editing using diffusion models.  arXiv preprint arXiv:2305.04441, 2023.
  * [8] Jon Donnelly, Alina Jade Barnett, and Chaofan Chen.  Deformable ProtoPNet: An Interpretable Image Classifier Using Deformable Prototypes.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 10265–10275, 2022.
  * [9] Dave Epstein, Taesung Park, Richard Zhang, Eli Shechtman, and Alexei A. Efros.  Blobgan: Spatially disentangled scene representations.  European Conference on Computer Vision (ECCV), 2022.
  * [10] Patrick Esser, Robin Rombach, and Bjorn Ommer.  Taming transformers for high-resolution image synthesis.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 12873–12883, June 2021.
  * [11] Thomas Fel, Agustin Picard, Louis Bethune, Thibaut Boissin, David Vigouroux, Julien Colin, Rémi Cadène, and Thomas Serre.  Craft: Concept recursive activation factorization for explainability.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 2711–2721, 2023.
  * [12] Rinon Gal, Yuval Alaluf, Yuval Atzmon, Or Patashnik, Amit Haim Bermano, Gal Chechik, and Daniel Cohen-or.  An image is worth one word: Personalizing text-to-image generation using textual inversion.  In The Eleventh International Conference on Learning Representations, 2023.
  * [13] Yunhao Ge, Yao Xiao, Zhi Xu, Meng Zheng, Srikrishna Karanam, Terrence Chen, Laurent Itti, and Ziyan Wu.  A peek into the reasoning of neural networks: Interpreting with structural visual concepts.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 2195–2204, 2021.
  * [14] Amirata Ghorbani, James Wexler, James Y Zou, and Been Kim.  Towards automatic concept-based explanations.  Advances in Neural Information Processing Systems, 32, 2019.
  * [15] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial nets.  In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
  * [16] Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy.  Explaining and harnessing adversarial examples.  In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
  * [17] Jing Gu, Yilin Wang, Nanxuan Zhao, Tsu-Jui Fu, Wei Xiong, Qing Liu, Zhifei Zhang, He Zhang, Jianming Zhang, HyunJoon Jung, et al.  Photoswap: Personalized subject swapping in images.  arXiv preprint arXiv:2305.18286, 2023.
  * [18] Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter.  Gans trained by a two time-scale update rule converge to a local nash equilibrium.  Advances in neural information processing systems, 30, 2017.
  * [19] Jonathan Ho, Ajay Jain, and Pieter Abbeel.  Denoising diffusion probabilistic models.  Advances in Neural Information Processing Systems, 33:6840–6851, 2020.
  * [20] Jonathan Ho and Tim Salimans.  Classifier-free diffusion guidance.  In NeurIPS 2021 Workshop on Deep Generative Models and Downstream Applications, 2021.
  * [21] Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger.  Densely connected convolutional networks.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4700–4708, 2017.
  * [22] Zixuan Huang and Yin Li.  Interpretable and accurate fine-grained recognition via region grouping.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.
  * [23] Paul Jacob, Éloi Zablocki, Hédi Ben-Younes, Mickaël Chen, Patrick Pérez, and Matthieu Cord.  Steex: steering counterfactual explanations with semantics.  In Computer Vision–ECCV 2022: 17th European Conference, Tel Aviv, Israel, October 23–27, 2022, Proceedings, Part XII, pages 387–403. Springer, 2022.
  * [24] Guillaume Jeanneret, Loïc Simon, and Frédéric Jurie.  Diffusion models for counterfactual explanations.  In Proceedings of the Asian Conference on Computer Vision, pages 858–876, 2022.
  * [25] Guillaume Jeanneret, Loïc Simon, and Frédéric Jurie.  Adversarial counterfactual visual explanations.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 16425–16435, 2023.
  * [26] Hyungsik Jung and Youngrock Oh.  Towards better explanations of class activation mapping.  In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), pages 1336–1344, October 2021.
  * [27] Tero Karras, Miika Aittala, Janne Hellsten, Samuli Laine, Jaakko Lehtinen, and Timo Aila.  Training generative adversarial networks with limited data.  Advances in neural information processing systems, 33:12104–12114, 2020.
  * [28] Saeed Khorram and Li Fuxin.  Cycle-consistent counterfactuals by latent transformations.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10203–10212, 2022.
  * [29] Been Kim, Martin Wattenberg, Justin Gilmer, Carrie Cai, James Wexler, Fernanda Viegas, et al.  Interpretability beyond feature attribution: Quantitative testing with concept activation vectors (tcav).  In International conference on machine learning, pages 2668–2677. PMLR, 2018.
  * [30] Diederik P. Kingma and Max Welling.  Auto-Encoding Variational Bayes.  In 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014.
  * [31] Cheng-Han Lee, Ziwei Liu, Lingyun Wu, and Ping Luo.  Maskgan: Towards diverse and interactive facial image manipulation.  In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2020.
  * [32] Jinqi Luo, Zhaoning Wang, Chen Henry Wu, Dong Huang, and Fernando De la Torre.  Zero-shot model diagnosis.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 11631–11640, 2023.
  * [33] Ron Mokady, Amir Hertz, Kfir Aberman, Yael Pritch, and Daniel Cohen-Or.  Null-text inversion for editing real images using guided diffusion models.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 6038–6047, 2023.
  * [34] Chong Mou, Xintao Wang, Liangbin Xie, Jian Zhang, Zhongang Qi, Ying Shan, and Xiaohu Qie.  T2i-adapter: Learning adapters to dig out more controllable ability for text-to-image diffusion models.  arXiv preprint arXiv:2302.08453, 2023.
  * [35] Meike Nauta, Jörg Schlötterer, Maurice van Keulen, and Christin Seifert.  Pip-net: Patch-based intuitive prototypes for interpretable image classification.  2023\.
  * [36] Gaurav Parmar, Krishna Kumar Singh, Richard Zhang, Yijun Li, Jingwan Lu, and Jun-Yan Zhu.  Zero-shot image-to-image translation.  In ACM SIGGRAPH 2023 Conference Proceedings, pages 1–11, 2023.
  * [37] Vitali Petsiuk, Abir Das, and Kate Saenko.  Rise: Randomized input sampling for explanation of black-box models.  In Proceedings of the British Machine Vision Conference (BMVC), 2018.
  * [38] Viraj Prabhu, Sriram Yenamandra, Prithvijit Chattopadhyay, and Judy Hoffman.  Bridging the sim2real gap with care: Supervised detection adaptation with conditional alignment and reweighting.  2023\.
  * [39] Pau Rodriguez, Massimo Caccia, Alexandre Lacoste, Lee Zamparo, Issam Laradji, Laurent Charlin, and David Vazquez.  Beyond trivial counterfactual explanations with diverse valuable explanations.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 1056–1065, 2021.
  * [40] Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer.  High-resolution image synthesis with latent diffusion models.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 10684–10695, June 2022.
  * [41] Nataniel Ruiz, Yuanzhen Li, Varun Jampani, Yael Pritch, Michael Rubinstein, and Kfir Aberman.  Dreambooth: Fine tuning text-to-image diffusion models for subject-driven generation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 22500–22510, June 2023.
  * [42] Pedro Sanchez and Sotirios A. Tsaftaris.  Diffusion causal models for counterfactual estimation.  In CLEaR, 2022.
  * [43] Christoph Schuhmann, Romain Beaumont, Richard Vencu, Cade W Gordon, Ross Wightman, Mehdi Cherti, Theo Coombes, Aarush Katta, Clayton Mullis, Mitchell Wortsman, Patrick Schramowski, Srivatsa R Kundurthy, Katherine Crowson, Ludwig Schmidt, Robert Kaczmarczyk, and Jenia Jitsev.  LAION-5b: An open large-scale dataset for training next generation image-text models.  In Thirty-sixth Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2022.
  * [44] Ramprasaath R. Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra.  Grad-cam: Visual explanations from deep networks via gradient-based localization.  In 2017 IEEE International Conference on Computer Vision (ICCV), pages 618–626, 2017.
  * [45] Sumedha Singla, Brian Pollack, Junxiang Chen, and Kayhan Batmanghelich.  Explanation by progressive exaggeration.  In International Conference on Learning Representations, 2020.
  * [46] Jiaming Song, Chenlin Meng, and Stefano Ermon.  Denoising diffusion implicit models.  In International Conference on Learning Representations, 2021.
  * [47] Joshua Vendrow, Saachi Jain, Logan Engstrom, and Aleksander Madry.  Dataset interfaces: Diagnosing model failures using controllable counterfactual generation.  In ArXiv preprint arXiv:2302.07865, 2023.
  * [48] Sandra Wachter, Brent Mittelstadt, and Chris Russell.  Counterfactual Explanations Without Opening the Black Box: Automated Decisions and the GDPR.  arvard Journal of Law and Technology,, 31(2):841–887, 2018.
  * [49] Bram Wallace, Akash Gokul, and Nikhil Naik.  Edict: Exact diffusion inversion via coupled transformations.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 22532–22541, 2023.
  * [50] Fisher Yu, Haofeng Chen, Xin Wang, Wenqi Xian, Yingying Chen, Fangchen Liu, Vashisht Madhavan, and Trevor Darrell.  Bdd100k: A diverse driving dataset for heterogeneous multitask learning.  2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 2633–2642, 2020.
  * [51] Mehdi Zemni, Mickaël Chen, Éloi Zablocki, Hédi Ben-Younes, Patrick Pérez, and Matthieu Cord.  Octet: Object-aware counterfactual explanations.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 15062–15071, 2023.
  * [52] Lvmin Zhang and Maneesh Agrawala.  Adding conditional control to text-to-image diffusion models.  arXiv preprint arXiv:2302.05543, 2023.
  * [53] Quanshi Zhang, Ying Nian Wu, and Song-Chun Zhu.  Interpretable convolutional neural networks.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 8827–8836, 2018.
  * [54] Ligeng Zhu, Zhijian Liu, and Song Han.  Deep leakage from gradients.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.

Supplementary Material
Text-to-Image Models for Counterfactual Explanations: a Black-Box Approach

##  Appendix A Evaluation Criteria

Before describing each metric and its formulation, we will thoroughly describe
the goals of counterfactual explanations. As we stated in the main manuscript,
counterfactual explanations seek to change an instance prediction by modifying
the input instance. However, these modifications must be small but
perceptually coherent. From the previous statement, we can extract many goals
of CEs:

  1. 1.

CEs must flip the decision of the classifier. In the literature, this feature
is called validity.

  2. 2.

The counterfactual changes should be plausible and realistic - simply referred
to as realism. Visual automated systems are generally brittle to adversarial
noise [16]. This noise is designed to fool the classifier, but with the
restriction that it is hidden from visual inspection. Since this noise cannot
be perceived, it cannot be analyzed to find spurious correlations. Therefore,
only realistic and plausible changes are allowed.

  3. 3.

The algorithm must generate proximal and sparse counterfactuals. One could
create a valid and realistic explanation by simply replacing the target
instance with a new one. This still obeys the realistic and valid goals.
However, it does not give any information about the variables. Thus, the
modifications must be sparse and close to the image to visually observe which
variables have changed.

  4. 4.

Finally, the algorithm must generate the explanation efficiently. This
property is required to avoid delays for the user.

Now we will proceed to describe each evaluation metric and link it to its
corresponding objective. As for notations, let $M(x,y)$ be the counterfactual
algorithm applied to an image $x\in D$ targeting the class $y$, where $D$ is a
dataset. Additionally, let $C$ be the classifier, $\mathbb{1}(condition)$ a
function that is one if the condition is true or zero otherwise. Finally, let
$a\in A$ be an attribute in a set $A$, then $O^{a}$ is an attribute oracle
classifier for $a$. This network predicts if its input has the attribute $a$.
Similarly, let $\mathcal{O}$ be an identity verification network This DNN is
trained to give a similarity measure between two images, often computed with
the cosine similarity $CS$.

##### Success Rate.

The success rate (or flip rate) measures the ratio at which counterfactuals
have successfully reversed the original classifier’s decision. This metric
correlates with the validity goal. To measure it, we simply compute the
proportion of valid counterfactuals to the size of the dataset, as in

$SR=\frac{1}{|D|}\sum_{x\in D}\mathbb{1}(C(M(x,y))=y).$ (12)

##### Realism.

To approximate the realism of the counterfactuals, the literature adopts the
FID [18] metric from generation research. Furthermore, [25] extended the
metric by computing the FID between the half of the dataset and the
counterfactuals of the complement set. This was motivated to reduce the
inherent bias in computing the FID, given that the difference between the
original images and their CE is a few pixels in the image.

##### Proximity and Sparsity.

To evaluate this goal, previous methods proposed several metrics to quantify
the degree of dissimilarity between an instance and its explanation.
Initially, most metrics were proposed for face images. Initially, [23]
suggested using the mean number of attributes changed (MNAC), computed as
follows:

$MNAC=\frac{1}{|D|}\sum_{x\in D}\sum_{a\in A}\mathbb{1}(O^{a}(M(x,y))\neq
O^{a}(x)).$ (13)

However, [24] noted that counterfactual methods will change some attributes if
they are correlated. Thus, based on the MNAC, the Correlation Difference (CD)
[24] measures the correlations produced by $M$. To further assess the
proximity and sparsity in face counterfactuals, [45] suggested using the Face
Verification Accuracy (FVA) to compute whether $M$ cannot modify the identity
of the person. This metric is calculated as

$FVA=\frac{1}{|D|}\sum_{x\in
D}\mathbb{1}(CS(\mathcal{O}(x),\mathcal{O}(M(x,y)))>0.5).$ (14)

[25] noted that this metric was already saturated. To measure a more fine-
grained metric, they proposed taking the continuous $CS$ and calling the
metric face similarity (FS):

$FS=\frac{1}{|D|}\sum_{x\in D}CS(\mathcal{O}(x),\mathcal{O}(M(x,y)).$ (15)

Finally, the same authors extended this metric for general-purpose images by
computing Eq. 15 using a self-supervised trained model as $\mathcal{O}$. They
called this metric $S^{3}$. Finally, [28] proposed to compute COUT. This
metric computes the probability of the class $y$ using multiple linear
interpolations between $x$ and $M(x,y)$.

##### Efficiency.

The literature generally ignores computing an efficiency metric. To compute
the efficiency of counterfactual models, the widely accepted metric is
floating point operations (FLOPs). In addition, it is also recommended to
compute the average time per counterfactual. However, this metric is only
comparable if all measurements are computed on the under the same
circumstances. twocolumn

##  Appendix B Qualitative Results

In this section, we provide additional qualitative results. For the CelebA HQ
[31] dataset, we provide our and ACE [25] counterfactuals to show the
differences.

Figure 4: Counterfactual Explanations targeting the Non-Smile attribute.
Figure 5: Counterfactual Explanations targeting the Smile attribute. Figure 6:
Counterfactual Explanations targeting the Young attribute. Figure 7:
Counterfactual Explanations targeting the Old attribute. Figure 8:
Counterfactual Explanations targeting the Stop action. Figure 9:
Counterfactual Explanations targeting the Forward action.


# Deterministic Online Call Control in Cellular Networks and Triangle-Free
Cellular Networks

Joseph Wun-Tat Chan College of International Education, Hong Kong Baptist
University, Hong Kong<EMAIL_ADDRESS>Francis Y.L. Chin Department of
Computer Science, The University of Hong Kong, Hong Kong<EMAIL_ADDRESS>Research supported by HK RGC grant HKU-7117/09E and the William M.W. Mong
Engineering Research Fund Xin Han School of Software, Dalian University of
Technology, China<EMAIL_ADDRESS>Partially supported by Start-up
Funding (1600-893335) provided by DUT, China Ka-Cheong Lam College of Computer
Science, Zhejiang University, China<EMAIL_ADDRESS>Hing-Fung Ting
Department of Computer Science, The University of Hong Kong, Hong Kong,
<EMAIL_ADDRESS>Research supported by HK RGC grant HKU-7171/08E Yong Zhang
Department of Computer Science, The University of Hong Kong, Hong Kong,
<EMAIL_ADDRESS>
###### Abstract

Wireless Communication Networks based on Frequency Division Multiplexing (FDM
in short) plays an important role in the field of communications, in which
each request can be satisfied by assigning a frequency. To avoid interference,
each assigned frequency must be different to the neighboring assigned
frequencies. Since frequency is a scarce resource, the main problem in
wireless networks is how to fully utilize the given bandwidth of frequencies.
In this paper, we consider the online call control problem. Given a fixed
bandwidth of frequencies and a sequence of communication requests arrive over
time, each request must be either satisfied immediately after its arrival by
assigning an available frequency, or rejected. The objective of call control
problem is to maximize the number of accepted requests. We study the
asymptotic performance of this problem, i.e., the number of requests in the
sequence and the bandwidth of frequencies are very large. In this paper, we
give a 7/3-competitive algorithm for call control problem in cellular network,
improving the previous 2.5-competitive result. Moreover, we investigate the
triangle-free cellular network, propose a 9/4-competitive algorithm and prove
that the lower bound of competitive ratio is at least 5/3.

Keywords: Online algorithms, Call control problem, Cellular networks,
Triangle-free cellular network

##  1 Introduction

Frequency Division Multiplexing (FDM in short) is commonly used in wireless
communications. To implement FDM, the wireless network is partitioned into
small regions (cell) and each cell is equipped with a base station. When a
call request arrives at a cell, the base station in this cell will assign a
frequency to this request, and the call is established via this frequency.
Since frequency is a scarce resource, to satisfy the requests from many users,
a straightforward idea is reusing the same frequency for different call
requests. But if two calls which are close to each other are using the same
frequency, interference will happen to violate the quality of communications.
Thus, to avoid interference, the same frequency cannot be assigned to two
different calls with distance close to each other. In general, the same
frequency cannot be assigned to two calls in the same cell or neighboring
cells.

There are two research directions on the fully utilization of the frequencies.
One is frequency assignment problem, and the other is call control problem. In
frequency assignment problem, each call request must be accepted, and the
objective is to minimize the number of frequencies to satisfy all requests. In
call control problem, the bandwidth of frequency is fixed, thus, when the
number of call requests in a cell or in some neighboring cells is larger than
the total bandwidth, the request sequence cannot be totally accepted, i.e.,
some requests would be rejected. The objective of call control problem is to
accept the requests as many as possible.

Problem Statement:

In this paper, we consider the online version of call control problem. There
are $\omega$ frequencies available in the wireless networks. A sequence
$\sigma$ of call requests arrives over time, where
$\sigma=\\{r_{1},r_{2},...,r_{t},...\\}$, $r_{t}$ denotes the $t$-th call
request and also represent the cell where the $t$-th request arrives. When a
request arrives at a cell, the system must either choose a frequency to
satisfy this request without interference with other assigned frequencies in
this cell and its neighboring cells, or reject this request. When handling a
request, the system does not know any information about future call requests.
We assume that when a frequency is assigned to a call, this call will never
terminate and the frequency cannot be changed. The objective of this problem
is to maximize the number of accepted requests.

We focus on the call control problem in cellular networks and triangle-free
cellular networks. In the cellular networks, each cell is a hexagonal region
and has six neighbors, as shown in Figure 1(a). The cellular network is widely
used in wireless communication networks. A network is triangle-free if there
are no 3-cliques in the network, i.e., there are no three mutually-adjacent
cells. An example of a triangle-free cellular network is shown in Fig. 1(b).

(a) cellular network

(b) triangle-free cellular network

Figure 1: An example of the cellular network and triangle-free cellular
network

Performance Measure:

To measure the performance of online algorithms, we use the competitive ratio
to compare the performance between the online algorithm and the optimal
offline algorithm, which knows the whole request sequence in advance. In call
control problem, the output is the number of accepted requests. For a request
sequence $\sigma$, let $A(\sigma)$ and $O(\sigma)$ denote the number of
accepted request of an online algorithm $A$ and the optimal offline algorithm
$O$, respectively. We focus on the asymptotic performance for the call control
problem, i.e., the number of requests and the number of frequencies are very
large positive integers. The asymptotic competitive ratio for an online
algorithm $A$ is

$R_{A}^{\infty}=\limsup_{n\rightarrow\infty}\max_{\sigma}\\{\frac{O(\sigma)}{A(\sigma)}|O(\sigma)=n\\}.$

Related Works:

How to fully utilize the frequencies to satisfy the communication requests is
a very fundamental problem in theoretical computer science and wireless
communications. Both the frequency assignment problem and the call control
problem are well studied during these years. From the description of these two
problems, we know that the call control problem is the dual problem of the
frequency assignment problem.

The offline version of the frequency assignment problem in cellular networks
was proved to be NP-hard by McDiarmid and Reed [6], and two 4/3-approximation
algorithms were given in [6, 7]. In the online frequency assignment problem,
when a call request arrives, the network must immediately assign a frequency
to this call without any interference. There are mainly three strategies:
Fixed Allocation [5], Greedy Assignment [1], and Hybrid Assignment [3]. If the
duration of each call is infinity and the assigned frequency cannot be
changed, the hybrid algorithm gave the best result for online frequency
assignment, i.e., a 2-competitive algorithm for the absolute performance and a
1.9126-competitive algorithm for the asymptotic performance. When the
background network is triangle-free, a 2-local 5/4-competitive algorithm was
given in [9], an inductive proof for the 7/6 ratio was reported in [4], where
$k$-local means when assigning a frequency, the base station only knows the
information of its neighboring cells within distance $k$. In [11], a 1-local
4/3-competitive algorithm was given.

For the call control problem, the offline version is NP-hard too [6]. To
handle such problem, greedy strategy is always the first try, when a call
request arrives, the network choose the minimal available frequency to serve
this request, if any frequency is interfere with some neighboring assigned
frequency, the request will be rejected. Pantziou et al. [8] analyzed the
performance of the greedy strategy, proved that the asymptotic competitive
ratio of the greedy strategy is equal to the maximal degree of the network.
Caragiannis et al. [1] gave a randomized algorithm for the call control
problem in cellular networks, the asymptotic competitive ratio of their
algorithm is 2.651. Later, the performance of the randomized algorithms was
improved to 16/7 by the same authors [2], they also proved the lower bound of
the asymptotic competitive ratio for the randomized algorithm is at least 2.
Very recently, a deterministic algorithm with asymptotic competitive ratio 2.5
was given in [10], and the lower bound of the asymptotic competitive ratio for
the deterministic algorithm was proved to be 2.

Our Contributions:

In this paper, we consider the deterministic algorithms for the online call
control problem in cellular networks and triangle-free cellular networks. In
cellular network, we give a 7/3-competitive algorithm, improving the previous
2.5-competitive result. In triangle-free network, we propose a 9/4-competitive
algorithm, moreover, we show that the lower bound of the competitive ratio in
triangle-free network is at least 5/3.

##  2 Call Control in Cellular Networks

The idea of our algorithm for call control problem in cellular networks is
similar to the algorithm in [10]. By using a totally different analysis, the
performance of our algorithm is better. Moreover, our algorithm is best
possible among algorithms using this kind of idea.

Cellular networks are 3 colorable, each cell can be associated with a color
from $\\{R,G,B\\}$ and any two neighboring cells are with different colors.
Partition the frequencies into four sets, $F_{R}$, $F_{B}$, $F_{G}$, and
$F_{S}$, where $F_{X}$ ($X\in\\{R,G,B\\}$) can be only used in cells with
color $X$ and $F_{S}$ can be used in any cell. Since we consider the
asymptotic performance of the call control problem, we may regard the number
$\omega$ of frequencies in the system is a multiple of 7. Divide the the
frequencies into four disjoint sets as follows:

$\begin{array}[]{ll}F_{R}=&\\{1,...,2\omega/7\\},\\\
F_{G}=&\\{2\omega/7+1,...,4\omega/7\\},\\\
F_{B}=&\\{4\omega/7+1,...,6\omega/7\\},and\\\
F_{S}=&\\{6\omega/7+1,...,\omega\\}\end{array}$

Obviously, the ratio between the number of frequencies in $F_{R}$, $F_{G}$,
$F_{B}$, and $F_{S}$ is $2:2:2:1$.

Now we describe our algorithm CACO as follows:

Algorithm 1 CACO: When a request arrives at a cell $C$ with color
$c\in\\{R,G,B\\}$

1:if $F_{c}$ is not totally used up then

2: assign the minimal available frequency from $F_{c}$ to satisfy this
request.

3:else if $F_{S}$ is not totally used up in cell $C$ and its neighboring cells
then

4: assign the minimal available frequency from $F_{S}$ to satisfy this
request.

5:else

6: reject this request.

7:end if

The high level idea to show the performance of our algorithm CACO is to prove
that the ratio between the total number of accepted requests by CACO and the
total number of satisfied requests by the optimal offline algorithm is at
least 3/7. To prove this, we analyze the number of satisfied requests in each
cell and its neighboring cells, then compare the number with the optimum
value.

Let $R_{i}$ be the number of the requests arrived in cell $C_{i}$. Let $O_{i}$
be the number of requests accepted by the optimal offline algorithm in cell
$C_{i}$. $\sum_{i}O_{i}$ is the total number of accepted request by the
optimal offline algorithm. Let $A_{i}$ be the number of requests accepted by
our online algorithm CACO in cell $C_{i}$. $\sum_{i}A_{i}$ is the total number
of accepted request by CACO. Let $A_{x}(C_{i})$ be the the number of requests
accepted by CACO in cell $C_{i}$ by assigning frequencies from frequency set
$F_{x}$. It can be seen that
$A_{i}=A_{R}(C_{i})+A_{G}(C_{i})+A_{B}(C_{i})+A_{S}(C_{i})$. If $C_{i}$ is
colored with $x\in\\{R,G,B\\}$, then $A_{i}=A_{x}(C_{i})+A_{S}(C_{i})$.

######  Fact 1.

For each cell $C_{i}$, $O_{i}\leq R_{i}$, $A_{i}\leq R_{i}$, and $A_{i}\geq
2\omega/7$ when $R_{i}\geq 2\omega/7$.

According to the number of satisfied requests by the optimal offline
algorithm, we classify the cells into two types: cell $C_{i}$ is $safe$ if
$O_{i}\leq 2\omega/3$, and $dangerous$ otherwise.

######  Lemma 2.

Suppose cell $C_{i}$ is with color $x$, if $C_{i}$ is safe, then $A_{i}\geq
3O_{i}/7$

###### Proof.

Consider the following two cases.

  * •

$R_{i}\leq 2\omega/7$

According to CACO, all requests in this cell must be satisfied when $R_{i}\leq
2\omega/7$, thus, $A_{i}=R_{i}$. Since $R_{i}\geq O_{i}$, we have $A_{i}\geq
3O_{i}/7$.

  * •

$R_{i}>2\omega/7$

In this case, CACO will accept at least $2\omega/7$ requests by assigning
frequencies from $F_{x}$, thus, $A_{i}\geq 2\omega/7$. Since $C_{i}$ is safe,
$O_{i}\leq 2\omega/3$, therefore, we have $A_{i}\geq 3O_{i}/7$.

Combining the above two cases, this lemma is true. ∎

######  Fact 3.

A safe cell has at most 3 dangerous neighboring cells. All neighboring cells
around a dangerous cell are safe.

###### Proof.

This fact can be proved by contradiction. If a safe cell $C$ has more than 3
dangerous neighboring cells, since $C$ has 6 neighboring cells, there must
exist two dangerous cells which are neighbors. From the definition of
dangerous cell, the total number of accepted request in these two dangerous
neighboring cells is strictly more than $\omega$, contradiction!

Similarly, if a dangerous cell $C^{\prime}$ is a neighboring cell of another
dangerous cell $C$, the total number of accepted request in $C$ and
$C^{\prime}$ is strictly more than $\omega$. Contradiction! ∎

According to the algorithm CACO, when a request cannot be satisfied in a cell
$C$ with color $c$, all frequencies in $F_{c}$ must be used in $C$, and all
frequencies in $F_{S}$ must be used in $C$ and its six neighbors. Thus, we
have the following fact:

######  Fact 4.

If cell $C$ cannot satisfy a request according to the algorithm CACO, then
$A_{S}(C)+\sum_{k}A_{S}(C_{k})\geq\omega/7$, where $C_{k}$ represents the
neighboring cell of $C$.

To compare the number of satisfied requests by CACO in each cell with the
optimal offline solution, we define $B_{i}$ as follows, where $C_{k}$
represents the neighboring cell of $C_{i}$.

$B_{i}=\left\\{\begin{array}[]{ll}3O_{i}/7&\textrm{if $C_{i}$ is safe}\\\
A_{i}+\sum_{k}(A_{k}-3O_{k}/7)/3&\textrm{if $C_{i}$ is dangerous.}\\\
\end{array}\right.$

######  Lemma 5.

$\sum_{i}B_{i}\leq\sum_{i}A_{i}$.

###### Proof.

Suppose $C_{k}$ is a safe cell. According to Lemma 2, we have $A_{k}\geq
3O_{k}/7$. From Fact 3, we know that there are at most three dangerous
neighbors around $C_{k}$, thus, after counting $B_{k}=3O_{k}/7$ frequencies in
$C_{k}$, the remaining $A_{k}-3O_{k}/7$ frequencies can compensate the
frequencies in its dangerous neighbors, and each dangerous cell receives
$(A_{k}-3O_{k}/7)/3$ frequencies. From the definition of $B_{i}$, we can see
that $\sum_{i}B_{i}\leq\sum_{i}A_{i}$. ∎

######  Theorem 6.

The asymptotic competitive ratio of algorithm CACO is at most 7/3.

###### Proof.

From the definition of $O_{i}$ and $B_{i}$, we can say that $O_{i}/B_{i}\leq
7/3$ for any cell $C_{i}$ leads to the correctness of this theorem. That is
because

$\frac{\sum_{i}O_{i}}{\sum_{i}A_{i}}\leq\frac{\sum_{i}O_{i}}{\sum_{i}B_{i}}\leq\max_{i}\frac{O_{i}}{B_{i}}.$

If the cell $C_{i}$ is safe, i.e., $O_{i}\leq 2\omega/3$, we have
$O_{i}/B_{i}=7/3$.

If the cell $C_{i}$ is dangerous, i.e., $O_{i}>2\omega/3$, since $R_{i}\geq
O_{i}>2\omega/3>3\omega/7$, that means the number of requests $R_{i}$ in this
cell is larger than $A_{i}$. Thus, some requests are rejected, and this cell
cannot accept any further requests.

  * •

If the number of accepted requests in any neighbor of $C_{i}$ is no more than
$2\omega/7$, that means all frequencies in $F_{S}$ are assigned to requests in
cell $C_{i}$. Thus, $A_{i}=3\omega/7$. In this case, we have

$O_{i}/B_{i}=O_{i}/(A_{i}+(\sum_{k}(A_{k}-3O_{k}/7))/3)\leq
O_{i}/A_{i}\leq\omega/A_{i}=7/3.$

  * •

Otherwise, suppose there are $m$ neighbors of $C_{i}$ in which the number of
accepted requests are more than $2\omega/7$. Let $\hat{O_{i}}$ denote the
average number of the optimum value of accepted requests in these $m$
neighboring cells around $C_{i}$.

$\displaystyle B_{i}=A_{i}+(\sum_{k}(A_{k}-3O_{k}/7))/3$ $\displaystyle=$
$\displaystyle 2\omega/7+A_{S}(C_{i})+(\sum_{k}(A_{k}-3O_{k}/7))/3$
$\displaystyle\geq$ $\displaystyle 2\omega/7+A_{S}(C_{i})+(m\times
2\omega/7+\sum_{\begin{subarray}{c}\textrm{for the neighbors}\\\ \textrm{with
$A_{k}>2\omega/7$}\end{subarray}}A_{S}(C_{k})-m\times 3\hat{O_{i}}/7)/3$
$\displaystyle\geq$ $\displaystyle 2\omega/7+(m\times
2\omega/7+\sum_{\begin{subarray}{c}\textrm{for the neighbors}\\\ \textrm{with
$A_{k}>2\omega/7$}\end{subarray}}A_{S}(C_{k})+A_{S}(C_{i})-m\times
3\hat{O_{i}}/7)/3$ $\displaystyle\geq$ $\displaystyle 2\omega/7+(m\times
2\omega/7+\omega/7-m\times 3\hat{O_{i}}/7)/3$ $\displaystyle\geq$
$\displaystyle 2\omega/7+(2\omega/7+\omega/7-3\hat{O_{i}}/7)/3$
$\displaystyle(\textrm{that is because for any neighbor with }A_{k}>2w/7,$
$\displaystyle O_{k}\leq(\omega-
O_{i})\leq\omega/3,\textrm{thus},\hat{O_{i}}\leq\omega/3\textrm{ and
}2\omega/7-3\hat{O_{i}}/7\geq 0.)$ $\displaystyle\geq$ $\displaystyle
2\omega/7+(3\omega/7-3(\omega-O_{i})/7)/3$ $\displaystyle(\textrm{since
}O_{k}\leq\omega-O_{i}\textrm{, we have }\hat{O_{i}}\leq\omega-O_{i})$
$\displaystyle=$ $\displaystyle 2\omega/7+O_{i}/7$

Thus, $O_{i}/B_{i}\leq O_{i}/(2w/7+O_{i}/7)\leq 7/3$.

From the above analysis, we can say that the asymptotic competitive ratio of
the algorithm CACO is at most 7/3. ∎

In this kind of algorithms, the frequencies are partitioned into $F_{R}$,
$F_{G}$, $F_{B}$ and $F_{S}$, when a request arrives at a cell with color $c$,
first choose the frequency from the set $F_{c}$, then from $F_{S}$ if no
interference appear. The performances are different w.r.t. the ratio between
$|F_{R}|$ ($|F_{G}|$, $|F_{B}|$) and $|F_{S}|$. Note that from symmetry, the
size of $F_{R}$, $F_{G}$ and $F_{B}$ should be same. Now we show that CACO is
best possible among such kind of algorithms. Suppose the ratio between
$|F_{R}|$ and $|F_{S}|$ is $x:y$. Consider the configuration shown in Figure
2. In the first step, $\omega$ requests arrive at the center cell $C$ with
color $c$, the algorithm will use up all frequencies in $F_{c}$ and $F_{S}$,
in this case, the ratio of accepted requests by the optimal offline algorithm
and the online algorithm is $(3x+y)/(x+y)$ since the optimal algorithm will
accept all these requests. In the second step, $\omega$ requests arrive at
$C_{1}$, $C_{2}$ and $C_{3}$ with the same color $c^{\prime}$. The online
algorithm can only accept $x\omega/(3x+y)$ requests in each $C_{i}$ ($1\leq
i\leq 3$) since the frequencies in $F_{S}$ are all used in $C$. In this case,
the ratio between the optimal offline algorithm and the online algorithm is
$3(3x+y)/(4x+y)$ since the optimal algorithm will accept all $\omega$ requests
in $C_{i}$ ($1\leq i\leq 3$) and reject all requests in $C$. Balancing these
two ratios, we have $x:y=2:1$. From the description of the above two steps,
the lower bound of competitive ratio for this kind of algorithm is $7/3$.

Figure 2: Algorithm CACO is best possible among this kind of algorithms

##  3 Call Control in Triangle-Free Cellular Networks

The call control problem in cellular network is hard. But for some various
graph classes, this problem may have a better performance. For example, in
linear network, an optimal online algorithm with competitive ratio 3/2 can be
achieved [10]. An interesting induced network, triangle-free cellular network,
has been studied for many problems including frequency assignment problem[4,
9, 11].

For a cell $C_{i}$ in triangle-free cellular networks, there are only two
possible configurations for its neighboring cells, which are shown in Fig. 3.
If $C_{i}$ has 3 neighbors, the neighboring vertices are of the same color. On
the other hand, if the neighbors are of different colors, $C_{i}$ has 2
neighbors. There exists a simple structure in triangle-free cellular network,
i.e., a cell has only one neighbor, this structure can be regarded as the case
in Fig. 3(b).

(a) Structure A: neighbors with the same base color

(b) Structure B: neighbors with different base colors

Figure 3: Structure of neighboring cells

For the three base colors $R$, $G$ and $B$, we define a cyclic order among
them as $R\rightarrow G$, $G\rightarrow B$ and $B\rightarrow R$. Partition the
frequency set $\\{1,...,\omega\\}$ into three disjoint sets:

$F_{R}=\\{1,...,\omega/3\\},\emph{
}F_{G}=\\{\omega/3+1,...,2\omega/3\\},\emph{
}F_{B}=\\{2\omega/3+1,...,\omega\\}$

To be precisely, assigning frequencies from a set must in order of bottom-to-
top (assigning frequencies from the lower number to the higher number) or top-
to-bottom (assigning frequencies from the higher number to the lower number).
Now we describe our algorithm for call control problem in triangle-free
cellular networks.

Algorithm CACO2: Handling arrival requests in a cell $C$ with color
$X\in\\{R,G,B\\}$

  1. 1.

If cell $C$ has no neighbors, just assign frequencies from 1 to $\omega$.

  2. 2.

If cell $C$ has neighboring structure $A$ (Fig. 3(a)), let $Y$ be the base
color of $C$’s neighbors and $Z$ be the other third color. Assign frequency in
cell $C$ as follows if no interference appear:

    1. (a)

Assign frequencies from $F_{X}$ in bottom-to-top order.

    2. (b)

If all frequencies in $F_{X}$ are used up, assign frequencies from $F_{Z}$ in
bottom-to-top order if $X\rightarrow Y$; and in top-to-bottom order otherwise.

Such assignment guarantees that if $C$ uses the frequency from $F_{Z}$ after
using up all frequencies from $F_{X}$, and its neighboring cell $C^{\prime}$
also uses the frequency from $F_{Z}$ after using up the frequencies from
$F_{Y}$, $C$ and $C^{\prime}$ must assign frequency from $F_{Z}$ in different
order no matter what the neighbor configuration of $C^{\prime}$ is. (This can
be verified by checking this case (case 2) and the next case (case 3) of
CACO2.)

  3. 3.

If cell $C$ has neighboring configuration $B$ (Fig. 3(b)), let $Y$ and $Z$ be
the base colors of its two neighbors, respectively. Without loss of
generality, assume that $X\rightarrow Y$. Assign frequency in cell $C$ as
follows if no interference appear:

    1. (a)

Assign frequencies from $F_{X}$ in bottom-to-top order.

    2. (b)

If all frequencies in $F_{X}$ are used up, assign frequencies from $F_{Y}$ in
top-to-bottom order.

######  Theorem 7.

The competitive ratio of CACO2 is at most 9/4.

###### Proof.

For a given request sequence, let $O_{i}$ and $A_{i}$ be the numbers of
accepted requests in cell $C_{i}$ by the optimal offline algorithm and online
algorithm CACO2, respectively. This theorem holds if
$\sum_{i}O_{i}/\sum_{i}A_{i}\leq 9/4$. Similar to the analysis for CACO,
define $B_{i}$ as the amortized number of accepted requests in cell $C_{i}$.
Again, our target is to prove that $\sum_{i}B_{i}\leq\sum_{i}A_{i}$ and
$O_{i}/B_{i}\leq 9/4$ in any cell $C_{i}$. W.l.o.g., let $X$, $Y$ and $Z$
denote the three colors in the network.

Intuitively, we may set $B_{i}=4O_{i}/9$ if $A_{i}\geq 4O_{i}/9$, and the
remaining uncounted frequencies can be used to compensate the number of
accepted frequencies in its neighboring cells. Next, we describe how to
partition the remaining uncounted frequencies according to cell $C_{i}$’s
neighboring configuration. Let $H_{ij}$ be the number of frequencies used in
$C_{i}$ and compensates the number of frequencies in $C_{j}$.

  1. 1.

The neighboring configuration of $C_{i}$ is $A$ (Fig. 3(a)), the uncounted
number of frequencies is $A_{i}-4O_{i}/9$, evenly distribute this number to
its three neighboring cells, i.e., each neighbors $C_{j}$ of $C_{i}$ receives
$H_{ij}=(A_{i}-4O_{i}/9)/3$.

  2. 2.

The neighboring configuration of $C_{i}$ is $B$ (Fig. 3(b)). Assume that the
color of $C_{i}$ is $X$, the colors of its neighboring cells are $Y$ (cell
$C_{j}$) and $Z$ (cell $C_{k}$) respectively. W.l.o.g., assume that
$X\rightarrow Y$, $Y\rightarrow Z$ and $Z\rightarrow X$.

     * •

If $A_{i}>\omega/3$,

In this case, the requests in cell $C_{i}$ will use some frequencies from the
top part of $F_{Y}$.

       * –

If $A_{j}<4O_{j}/9$,

there exist rejected request in $C_{j}$, thus, $A_{i}+A_{j}=2\omega/3$. The
remaining uncounted number of frequencies in $C_{i}$ is partitioned into
$(4O_{j}/9-A_{j})$ and $\omega/9$. The former part $(4O_{j}/9-A_{j})$
compensates the number in $C_{j}$ (i.e., $H_{ij}=4O_{j}/9-A_{j}$), and the
latter part $\omega/9$ compensates the number in $C_{k}$ (i.e.,
$H_{ik}=\omega/9$) if $A_{k}<4O_{k}/9$. This compensation is justified since
$4O_{i}/9+(4O_{j}/9-A_{j})+\omega/9=4(O_{i}+O_{j})/9-A_{j}+\omega/9\leq
5\omega/9-A_{j}<A_{i}$.

       * –

If $A_{j}\geq 4O_{j}/9$,

in this case, no compensation is needed in $C_{j}$. Let
$H_{ik}=A_{i}-4O_{i}/9$ if $A_{k}<4O_{k}/9$.

     * •

If $A_{i}\leq\omega/3$,

In this case, all frequencies used in $C_{i}$ are from $F_{X}$, and some
frequencies used in $C_{k}$ may from $F_{X}$ too. If $A_{k}<4O_{k}/9$, all
remaining uncounted number $A_{i}-4O_{i}/9$ compensates the number in $C_{k}$,
i.e., $H_{ik}=A_{i}-4O_{i}/9$. No extra number of frequencies compensates the
number of frequencies in $C_{j}$, i.e., $H_{ij}=0$.

We define $B_{i}$ as follows, where $H_{ji}$ is the compensation from its
neighbor $C_{j}$.

$B_{i}=\left\\{\begin{array}[]{ll}4O_{i}/9&\textrm{if $A_{i}\geq 4O_{i}/9$}\\\
A_{i}+\sum_{j}H_{ji}&\textrm{if $A_{i}<4O_{i}/9$},\\\ \end{array}\right.$

From previous description, we have $4O_{i}/9+\sum_{j}H_{ij}\leq A_{i}$ if
$A_{i}\geq 4O_{i}/9$, thus,

$\displaystyle\sum_{i}B_{i}\emph{ }\hbox
to0.0pt{$\displaystyle=\sum_{A_{i}\geq
4O_{i}/9}4O_{i}/9+\sum_{A_{i}<4O_{i}/9}(A_{i}+\sum_{\textrm{$C_{i}$ and
$C_{j}$ are neighbors}}H_{ji})$\hss}$ $\displaystyle=$
$\displaystyle\sum_{A_{i}\geq 4O_{i}/9}(4O_{i}/9+\sum_{\textrm{$C_{i}$ and
$C_{j}$ are neighbors}}H_{ij})+\sum_{A_{i}<4O_{i}/9}A_{i}$ $\displaystyle\leq$
$\displaystyle\sum_{A_{i}\geq 4O_{i}/9}A_{i}+\sum_{A_{i}<4O_{i}/9}A_{i}$
$\displaystyle=$ $\displaystyle\sum_{i}A_{i}$

Now we analyze the relationship between $B_{i}$ and $O_{i}$ for any cell
$C_{i}$. Assuming that the color of $C_{i}$ is $X$.

  1. 1.

If $A_{i}\geq 4O_{i}/9$, $B_{i}=4O_{i}/9$.

  2. 2.

If $A_{i}<4O_{i}/9$,

    1. (a)

If $A_{i}<\omega/3$

Since $A_{i}<4O_{i}/9$, there must exist some rejected requests in $C_{i}$.
Some frequencies in $F_{X}$ are used in one of $C_{i}$’s neighbor $C_{j}$.
According to the algorithm, the neighboring structure of $C_{j}$ is $B$ (Fig.
3(b)), and $A_{i}+A_{j}=2\omega/3$. We say that $A_{j}\geq 4O_{j}/9$.
Otherwise, $A_{i}+A_{j}<4O_{i}/9+4O_{j}/9=4(O_{i}+O_{j})/9\leq 4\omega/9$,
contradiction!

In this case, $H_{ji}=4O_{i}/9-A_{i}$, thus,

$B_{i}=A_{i}+\sum_{\textrm{$C_{k}$ and $C_{i}$ are neighbors}}H_{ki}\geq
A_{i}+H_{ji}=4O_{i}/9.$

    2. (b)

If $A_{i}\geq\omega/3$ and $C_{i}$ has two neighbors $C_{j}$ with color $Y$
and $C_{k}$ with color $Z$ as shown in Fig. 3(b).

W.l.o.g., assume that $X\rightarrow Y$, $Y\rightarrow Z$ and $Z\rightarrow X$.
According to the algorithm, after using up the frequencies in $F_{X}$, $C_{i}$
will use some frequencies from $F_{Y}$ until interference appear, thus,
$A_{i}+A_{j}\geq 2\omega/3$. We claim that $A_{j}>4O_{j}/9$. That is because
$O_{j}\leq\omega-O_{i}<\omega-9A_{i}/4\leq\omega-9\omega/12=\omega/4$,
$A_{i}<4O_{i}/9\leq 4\omega/9$, and $A_{i}+A_{j}\geq 2\omega/3$. Thus, we have
$A_{j}\geq 2\omega/9>4O_{j}/9$.

      1. i.

If the neighboring configuration around $C_{j}$ is $A$ (Fig. 3(a)),
$H_{ji}=(A_{j}-4O_{j}/9)/3$, and

$\displaystyle B_{i}$ $\displaystyle\geq$ $\displaystyle A_{i}+H_{ji}$
$\displaystyle=$ $\displaystyle A_{i}+(A_{j}-4O_{j}/9)/3$ $\displaystyle=$
$\displaystyle 2A_{i}/3+(A_{i}+A_{j})/3-4O_{j}/27$ $\displaystyle\geq$
$\displaystyle 4\omega/9-4O_{j}/27$ $\displaystyle\geq$ $\displaystyle
4O_{i}/9$

      2. ii.

If the neighboring configuration around $C_{j}$ is $B$ (Fig. 3(b)),

         * •

If $A_{j}\leq\omega/3$, we have $H_{ji}=A_{j}-4O_{j}/9$. Thus,

$B_{i}\geq A_{i}+H_{ji}=A_{i}+A_{j}-4O_{j}/9\geq 2\omega/3-4O_{j}/9\geq
4O_{i}/9.$

         * •

If $A_{j}>\omega/3$, according to the description of the compensation,
$H_{ji}=\omega/9$ or $H_{ji}=A_{j}-4O_{j}/9$. In the former case,

$B_{i}\geq A_{i}+H_{ji}=A_{i}+\omega/9\geq\omega/3+\omega/9=4\omega/9\geq
4O_{i}/9.$

In the latter case,

$B_{i}\geq A_{i}+H_{ji}=A_{i}+A_{j}-4O_{j}/9\geq 2\omega/3-4O_{j}/9\geq
4O_{i}/9.$

    3. (c)

If $A_{i}\geq\omega/3$ and the neighbors of $C_{i}$ are of the same color
(Fig. 3(a)),

Assume that the color of its neighboring cell is $Y$. According to the
algorithm, after using up the frequencies from $F_{X}$, $C_{i}$ will use some
frequencies from $F_{Z}$ to satisfy some requests. Since $C_{i}$ rejects some
requests, we have either $A_{i}=2\omega/3$, or $A_{i}+A_{j}=\omega$ for some
neighboring cell $C_{j}$ of $C_{i}$, which is because $C_{i}$ and $C_{j}$
assign frequencies from $F_{Z}$ in different order, and $C_{j}$ will use the
frequency from $F_{Z}$ after using up the frequency from $F_{Y}$. Since
$A_{i}<4O_{i}/9\leq 4\omega/9$, the first case does not happen.

We claim that $A_{j}\geq 4O_{j}/9$, which is because $A_{j}=\omega-
A_{i}>\omega-4O_{i}/9\geq 5\omega/9>4O_{j}/9$.

       * •

If the neighboring configuration of $C_{j}$ is $A$ (Fig. 3(a)),
$H_{ji}=(A_{j}-4O_{j}/9)/3$. Thus,

$\displaystyle B_{i}$ $\displaystyle\geq$ $\displaystyle A_{i}+H_{ji}$
$\displaystyle=$ $\displaystyle A_{i}+(A_{j}-4O_{j}/9)/3$ $\displaystyle=$
$\displaystyle 2A_{i}/3+(A_{i}+A_{j})/3-4O_{j}/27$ $\displaystyle\geq$
$\displaystyle 5\omega/9-4O_{j}/27$ $\displaystyle>$ $\displaystyle 4O_{i}/9$

       * •

If the neighboring configuration of $C_{j}$ is $B$ (Fig. 3(b)),
$H_{ji}=\omega/9$ or $A_{j}-4O_{j}/9$. In the former case,

$B_{i}\geq A_{i}+H_{ji}=A_{i}+\omega/9\geq 4\omega/9\geq 4O_{i}/9.$

In the latter case,

$B_{i}\geq A_{i}+H_{ji}=A_{i}+A_{j}-4O_{j}/9=\omega-4O_{j}/9\geq 4O_{i}/9.$

Combine all above cases, we have $O_{i}/B_{i}\leq 9/4$ in each cell $C_{i}$.
Since $\sum_{i}B_{i}\leq\sum_{i}A_{i}$, we have
$\sum_{i}O_{i}/\sum_{i}A_{i}\leq 9/4$. ∎

Next, we prove that the lower bound of the competitive ratio for call control
problem in triangle-free cellular networks is at least 5/3.

######  Theorem 8.

The competitive ratio for call control problem in triangle-free cellular
network is at least 5/3.

###### Proof.

We prove the lower bound by using an adversary who sends requests according to
the assignment of the online algorithm.

Figure 4: lower bound of competitive ratio is at least 5/3

Consider the configuration shown in Figure 4.

In the first step, the adversary sends $\omega$ requests in the center cell
$C$. Suppose the online algorithm accepts $x$ requests. If $x\leq 3\omega/5$,
the adversary stop sending request. In this case, the optimal offline
algorithm can accept all these $\omega$ requests, thus, the ratio is at least
$5/3$.

If $x>3\omega/5$, the adversary then sends $\omega$ requests in each cell of
$C_{1}$, $C_{2}$ and $C_{3}$. To avoid interference, the online algorithm
accepts at most $\omega-x$ requests in each cell, and the total number of
accepted requests is $x+3(\omega-x)=3\omega-2x$. In this case, the optimal
offline algorithm will accept $3\omega$ requests, i.e., reject all requests in
the center cell $C$. Thus, the ratio in this case is $3\omega/(3\omega-2x)$.
Since $x>3\omega/5$, this value is at least $5/3$.

Combine the above two cases, the competitive ratio for call control problem in
triangle-free cellular network is at least 5/3. ∎

##  4 Concluding Remarks

We have studied online call control problem in wireless communication networks
and presented online algorithms in cellular networks and triangle-free
cellular networks. In cellular networks, we derived an upper bound of 7/3,
while in triangle-free cellular networks, the upper bound and lower bound we
achieved in this paper are 9/4 and 5/3, respectively. These bounds surpass the
previous best known results. The gap between the upper and lower bound is
quite big in both cases, and closing the gaps are very interesting problems
for future research.

## References

  * [1] Ioannis Caragiannis, Christos Kaklamanis, and Evi Papaioannou.  Efficient on-line frequency allocation and call control in cellular networks.  Theory Comput. Syst., 35(5):521-543, 2002. A preliminary version of the paper is in SPAA 2000.
  * [2] Ioannis Caragiannis, Christos Kaklamanis, and Evi Papaioannou.  Competitive Algorithms and Lower Bounds for On-Line Randomized Call Control in Cellular Networks.  Networks 52(4): 235-251, 2008. Preliminary versions are in WAOA 03 and EUROPAR 05.
  * [3] Wun-Tat Chan, Francis Y.L. Chin, Deshi Ye and Yong Zhang.  Online Frequency Allocation in Cellular Networks.  In Proc. of the 19th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2007), pp. 241-249.
  * [4] Fr$\acute{\textmd{e}}$d$\acute{\textmd{e}}$ric Havet.  Channel assignment and multicoloring of the induced subgraphs of the triangular lattice.  Discrete Math. 233, 219-231 (2001).
  * [5] V. H. MacDonald.  Advanced mobile phone service: The cellular concept.  Bell Systems Technical Journal, 58(1):15-41, 1979.
  * [6] Colin McDiarmid and Bruce Reed.  Channel assignment and weighted coloring.  Networks, 36(2):114-117, 2000.
  * [7] Lata Narayanan, and Sunil Shende.  Static frequency assignment in cellular networks.  Algorithmica, 29(3):396-409, 2001.
  * [8] Grammati E. Pantziou, George P. Pentaris, and Paul G. Spirakis  Competitive Call Control in Mobile Networks.  Theory of Computing Systems, 35(6): 625-639, 2002.
  * [9] Petra $\check{\textmd{S}}$parl, and Janez $\check{\textmd{Z}}$erovnik.  2-local 5/4-competitive algorithm for multicoloring triangle-free hexagonal graphs.  Inf. Process. Lett. 90, 239-246 (2004)
  * [10] Deshi Ye, Xin Han, and Guochuan Zhang.  Deterministic On-line Call Control in Cellular Networks.  Theor. Comput. Sci. 411(31-33): 2871-2877 (2010)
  * [11] Yong Zhang, Francis Y.L. Chin, and Hong Zhu.  A 1-Local Asymptotic 13/9-Competitive Algorithm for Multicoloring Hexagonal Graphs.  Algorithmica (2009) 54:557-567.