# A separability-based approach to quantifying generalization: which layer is
best?

Luciano Dyballa111Equal contribution. Corresponding Author. Email:
<EMAIL_ADDRESS>Evan Gerritz22footnotemark: 2 Corresponding Author.
Email<EMAIL_ADDRESS>Steven W. Zucker  Department of Computer
Science, Yale University, New Haven, CT, USA

###### Abstract

Generalization to unseen data remains poorly understood for deep learning
classification and foundation models. How can one assess the ability of
networks to adapt to new or extended versions of their input space in the
spirit of few-shot learning, out-of-distribution generalization, and domain
adaptation? Which layers of a network are likely to generalize best? We
provide a new method for evaluating the capacity of networks to represent a
sampled domain, regardless of whether the network has been trained on all
classes in the domain. Our approach is the following: after fine-tuning state-
of-the-art pre-trained models for visual classification on a particular
domain, we assess their performance on data from related but distinct
variations in that domain. Generalization power is quantified as a function of
the latent embeddings of unseen data from intermediate layers for both
unsupervised and supervised settings. Working throughout all stages of the
network, we find that (i) high classification accuracy does not imply high
generalizability; and (ii) deeper layers in a model do not always generalize
the best, which has implications for pruning. Since the trends observed across
datasets are largely consistent, we conclude that our approach reveals (a
function of) the intrinsic capacity of the different layers of a model to
generalize.

1600

##  1 Introduction

The extent to which a network represents a target domain is a key question for
successful generalization. We work from the observation that an equivalence
class structure underlies successful classification, and exploit this topology
to develop a measure of generalizability based on separability (Figure 1). Our
method examines the behavior of the intermediate layers on examples from
classes missing in both the training and test sets, a problem confounding
earlier attempts to quantify generalization to a different dataset with the
same classes [1]. Importantly, our measure can be applied to any intermediate
layer, allowing us to test the competing hypotheses that (i) early layers
should capture basic, general features that are more easily translatable to
other datasets, or that (ii) the deeper the representation is—and therefore
closer to the final encoding/output layer—, the more “useful” it should be.
Neither perspective, it turns out, is true.

To empirically study a model’s generalization capacity, we train it on a
subset of the classes from a dataset (the seen classes), and then investigate
the model’s behavior on the remaining classes (or unseen classes). The
motivation for this approach is that the features learned for the seen classes
should be used, only in different combinations, for representing the common
features of the domain. Thus, unseen classes could be organized/separable
within the same embedding space. To generalize well in this scenario, a
network must have a sufficient number of neurons to represent a rich set of
features that will also be found in the images from unseen classes; this idea
is depicted in Figure 2. Hence, models that tend to learn more details (even
those not necessarily useful for classification), in other words learning a
richer representation of the features in the seen classes will likely allow
the model to generalize better to the unseen classes.

We emphasize that this is different from the standard generalization notion
between training and test data. In that scenario, the network is evaluated on
how well it performs on held-out data points belonging to the same classes as
those present in the training data. This can be framed as “weak
generalization”, and may be interpreted geometrically as testing the network
on novel points sampled from the same manifold $\mathcal{M}\in\mathbb{R}^{d}$,
with $d\leq m$, where $m$ is the dimension of the input space. The basic
assumption is that, if the network is presented with sufficiently varied
inputs, it should be able to “interpolate” between those to perform well on
unseen inputs from the same distribution. The degree to which this will be
successful is a matter of how much the network can avoid overfitting, and
techniques such as weight regularization [25], dropout, and optimizing batch
size [18] are commonly used to help in that regard, although if has been shown
that some of these are not sufficient to explain why large networks generalize
in practice [42]. It has also been suggested that this type of generalization
could be related to the presence of flatness of local minima in the loss
function landscape [11].

###  1.1 Related Work

Problems related to our stronger notion of generalization have been previously
investigated in the deep learning literature. Domain adaptation [3, 32]
considers a change in distribution/domain of inputs (e.g., going from photos
to paintings), but maintaining the same classes (or subset thereof, in the
case of partial domain adaptation (PDA) [2, 7]). The key goal is to learn
domain-invariant features for each class that translate well across domains,
using labeled data from both the ‘source’ and ‘target’ domains. Unsupervised
domain adaptation (UDA) [4, 17, 5] is a variant of this problem where the
target domain is unlabeled; this is closer to our scenario, except we take it
a step further in that even the classes are not the same. Thus, we cannot use
the strategy of ’matching’ same-class data points from one domain into the
other.

Out-of-distribution (OOD) or out-of-sample detection [16]—of which anomaly
detection, outlier detection, novelty detection, and open-set recognition are
special cases [39]—is related to our setting because the novel input samples
come from classes unrelated to those seen during training. However, the task
is to use binary classification to distinguish between seen data (training +
test sets) and unseen data (OOD samples). Out-of-distribution generalization
[23] addresses the case where the test-set distribution may diverge from that
of the training set, so it can be also seen as domain adaption.

Figure 1: Motivation for our approach. (a) Example of a domain with an
equivalence class structure. Some classes are used in training and model
evaluation (seen, in green) and the rest are not (unseen, in red). (b) Typical
example of the disparity between seen-class embeddings and unseen-class
embeddings. Note the former are readily separable, but the latter are not,
despite high test-set classification accuracy. This illustrates poor
generalization. We formalize the representation’s generalization quality by
measures of separability for the unseen classes. Plots show embeddings of an
intermediate layer output from VGG16 [30], visualized using PCA. Figure 2:
Clustering in different models. (a) An impoverished model can classify stags
vs. polar bears based on the background: foliage vs. snow, but fails on unseen
examples. Note the lack of cluster separability (bears and reindeer are mixed
due to their similar backgrounds). $\Phi(x)$ denotes the feature vector
produced for the data point $x$. (b) A richer model also “knows” about
antlers, claws, hooves, etc. and uses those to separate reindeer from grizzly
bears, regardless of their background. Note the cluster separability.
Figure 3: Schematic of our method of assessing generalizability through out-
of-sample embeddings using intermediate layers. (a) During training, only a
subset of all classes in the dataset are utilized (seen classes, in green).
(b) At the inference stage, one may use the model to classify novel points
from the seen classes (green) or to extract intermediate feature vectors
$\Phi_{i}(X)$ from an intermediate layer $i$ to assess the degree of
separability of the unseen classes, as measured by our index $g^{i}$ (eq. 1).
(c) Embeddings from different hidden states of the Vision Transformer (ViT)
network produce widely varying results. Color labels indicate ground truth:
clustered unseen classes indicate better generalization ($g$).

The notion of taking advantage of latent feature representations of the data
is particularly important in the field of zero-shot learning [38, 28].
Traditionally, the goal is to infer the class of images from unseen classes
based on some form of annotation: semantic attributes [13, 26, 15], word
vector [14, 31], or a short text description/caption [29] that describes them.
Seen and unseen classes are related in a so-called ‘semantic space’, where the
knowledge from seen classes can be transferred to unseen classes by means of
the annotations. In one such approach, the model learns a joint embedding
space onto which both the semantic vectors and the visual feature vectors can
be projected [40, 22]. An alternative is to learn a mapping from one to the
other [31, 14]). Novel images can be classified by finding the class that is
nearest to it in the semantic space.

In one-shot and few-shot learning [6, 8, 10], a model is given a single, or
few, labeled examples of an unseen class along with an unlabeled example. The
model predicts the label based on how similar it is to the novel, labeled
examples. To achieve this, the model is expected to have a powerful feature-
level representation, but is still reliant on labeled classes.

Thus, our problem is more akin to a generalized zero-shot setting [15], in
which the goal is to correctly organize samples from both seen and unseen
labels, except that we do not employ semantic information beyond the visual
features already present in the input images. Instead, we use multiple
unlabeled points as context in order to infer class structure. In contrast, a
large language model (LLM) performs zero-shot inference by receiving
additional context about a new class(es) in the same prompt (‘zero-shot
prompting’) [35, 19]. For example: an autoregressive language model may
respond correctly to the prompt: “Classify the sentiment of following sentence
into positive or negative: ‘I enjoyed this paper.’ Sentiment: ” even if it had
not been trained to perform sentiment analysis. In our specific setting of
image classification, a context is given in the form of many additional inputs
coming from the unseen classes.

We work with a purely visual setting, as in [8, 10]. The idea is to utilize a
minimalist approach in order to avoid confounds from the method of embedding
semantic information and of relating visual to semantic features. This
paradigm is relevant for the common real-world scenario where many images are
available without annotation. Ultimately, we aim to test whether the learned
feature vectors are sufficient to support zero-shot learning (in the sense
that we do not have labels for the unseen classes) or few-shot learning (in
the sense that we need multiple examples to assess proximity between data
points).

Two unsupervised approaches are used to evaluate the success of such
predictions: $K$-means (which assumes that classes should form Gaussian-like
clusters) and $k$-nearest neighbors (which instead of clusters assumes that
samples should be closer to the $k$ closest samples from the same unseen class
than those from other classes). We also test a supervised approach (linear
probe classifier) to more directly measure how separable the unseen classes
are in the latent space—it addresses the practical case where one is aware of
the novelty of the classes being used for during inference (and therefore can
label the outputs), but fine-tuning the model is infeasible. Thus, the linear
probe emulates an $n$-way few-shot learning, where labeled unseen classes can
be seen as the support set. This supervised technique also resembles
transductive few-shot learning [27, 10, 21], in which all unseen examples are
classified at once.

##  2 Methodology

To test our approach, we fine-tuned six, pretrained, state-of-the-art visual-
classification networks: ViT-base (ViT) [12], Swin Transformer (Swin)[24],
Pyramid ViT (PViT) [33], CvT-21 (CvT) [37], PoolFormer-S12 (PF) [41], ConvNeXt
V2 (CNV2) [36]. We used two different datasets for fine tuning: the CIFAR-100
natural scenes dataset [20], which classifies images by their content, and a
Chinese calligraphy dataset [34], which classifies grayscale images of drawn
characters by the artist that drew them. For each dataset, we sampled 15
classes to be seen only during training (the seen classes) and 5 to be
withheld for assessing generalization (the unseen classes). 333Because all the
networks were pre-trained on ImageNet-1k, a dataset that shares considerable
overlap in classes with CIFAR-100, we needed to find classes in CIFAR-100 that
were not present in ImageNet-1k. Fortunately, we observed that ImageNet-1k
does not have classes for flower species but CIFAR-100 does, so we were able
to use ‘sunflower’, ‘tulip’, ‘orchid’, ‘poppy’, and ‘rose’ as the unseen
classes. There are no Chinese calligraphy images in ImageNet-1k, so this was
not a concern for the calligraphy dataset. Our approach to fine-tune the
models only on the seen classes is in contrast with other works investigating
few-shot learning where the model is fine-tuned on the support (unseen) set
[e.g., 10].

The networks were fine-tuned using PyTorch and the transformers package for
500 epochs on the seen classes using the following hyperparameters: learning
rate $2\mathrm{e}{-4}$, batch size 72; AdamW optimizer.

To assess generalization, we used the intuition that intermediate embeddings
of examples from learned classes should form separable clusters. Thus, we
created a _generalization index_ , $g$, that measures the degree of
separability of examples $\\{x\\}$ within latent space embeddings
$\\{\Phi_{i}(x)\\}$ where $i$ indexes the intermediate layer providing the
embedding.

For a given network, $g^{i}_{\text{unseen}}$ is measured via the normalized
mutual information [9] between a $K$-means cluster assignment (with $K$ equal
to the number of unseen classes) computed on the embedding of unseen examples
and the ground truth:

$g^{i}_{\text{unseen}}=\left\\{\mathrm{NMI}\left(\mathcal{C}^{\Phi_{i}}_{\mathrm{unseen}},\mathcal{C}^{\star}\right)\right\\}$
(1)

where $i$ indexes the intermediate layers,
$\mathcal{C}^{\Phi_{i}}_{\mathrm{unseen}}$ denotes the $K$-means cluster
assignments of the unseen examples embedded in $\Phi_{i}$, and
$\mathcal{C}^{\star}$ denotes the images’ true labels. We can then also define
the overall generalizability of a network by using the layer that generalizes
the best:

$g=\max_{i}g^{i}.$ (2)

To compare the separability of the unseen class embeddings
$g^{i}_{\text{unseen}}$ to those of the seen class embeddings, we also compute
$g^{i}_{\text{seen}}$ analogously by obtaining $K$-means cluster labels for
only the seen examples and comparing those to the ground truth.

To validate our choice of metric, we compared $g$ to another unsupervised
metric based on $k$-nearest neighbors ($g_{\text{kNN}}$), as well as a
supervised metric based on linear probes ($g_{\text{LPr}}$).

The $k$-nearest neighbors metric is used because $K$-means implicitly assumes
Gaussian-like clusters, thus penalizing latent embeddings in which the classes
may still be reasonably separable, but more uniformly distributed. The
$k$-nearest neighbors metric avoids this assumption via the relaxed, intuitive
notion that nearest neighbors should belong to the same class. For each data
point, we computed its $k$-nearest neighbors (kNN) in an embedding, where $k$
is the number of examples in each class. To compute $g^{i}_{\text{kNN}}$, we
used the mean, over all data points, of the fraction of a data point $x$’s $k$
nearest neighbors belonging to the same class as $x$.

For the linear probe, we trained a linear classification head using each
intermediate layer’s output after showing it a training set of 500 examples
from the unseen classes and then testing it on 360 more examples from the
unseen classes.

To control for randomness in the training, we fine-tuned and calculated
metrics for each model three times using different seeds and computed the
average of each result, along with standard deviations.

Figure 4: Generalizability to unseen classes varies across architectures, even
though accuracy increases roughly monotonically across training epochs. We
plot $g_{\text{unseen}}=\mathrm{max}_{i}(g^{i})$ and show generalizability to
seen classes ($g_{\text{seen}}$). $g_{\text{seen}}$ always dominates
$g_{\text{unseen}}$ (as expected). While one might assume that high
classification accuracy implies the model has learned a representation of its
complete domain, these plots suggest that it is fitting well (or overfitting)
only the sub-domain sampled by the training data. (Error bars denote std.
dev.)
Figure 5:  Generalizability varies differently across depth in different
networks. For ViT, maximum values of $g^{i}$ are achieved in early layers
(top); for Swin only at the final stage (bottom). $g^{i}$ is not monotonic
with depth and, for many models (ViT, PViT, and PoolFormer), the best
generalization resides at intermediate layers. This holds true across datasets
and metrics. (Note, especially, the agreement between the two unsupervised
methods, NMI and kNN). In most cases, all metrics identified the same layer as
the most generalizable to unseen classes. We conclude that, since the $g^{i}$
curves are qualitatively similar across datasets, the patterns observed follow
from the networks’ architecture, and are not specific to a dataset.

##  3 Results

After fine-tuning six networks on two datasets and measuring their
generalization performance via several metrics, we found that $g$, i.e. the
max $g^{i}_{\text{NMI}}$ across all layers, is always lower on the unseen
data, compared to the seen data (as expected). Furthermore, the difference is
often quite stark, especially on the CIFAR dataset, as can be seen in Figure
4. A low $g$ means that regardless of classification accuracy, an
intermediate-layer based embedding from the network would not be useful unless
that particular class had been encountered during training.

Additionally, while training a particular network, a higher classification
accuracy did not always lead to better generalization. While our
generalizability metrics on the seen classes tend to improve with
classification accuracy, generalizability on the unseen classes often plateaus
and, in most networks, decreases at least once during training.

Looking at generalizability across all layers—not just the best layer—, there
is no universal trend as to which layer will provide the best representation
for separating unseen examples; sometimes the last layer is best, but often an
earlier layer is better, as can be seen in Figure 5. It is usually the case,
however, that a network’s most generalizable layer identified for one dataset,
will be the same for a different dataset. Comparing across datasets, the layer
generalization curves are qualitatively similar, indicating that our metric
captures an intrinsic aspect of the architecture.

Furthermore, the different metrics tend to agree qualitatively. The
$g_{\text{kNN}}$ curves align well with $g_{\text{NMI}}$ for a given
architecture, demonstrating that the assumption that the classes should be
clustered is reasonable. The linear probe results are likewise similar with
regard to the relative performance of each layer. Its values are higher across
the board, which is unsurprising since the linear probe is a supervised
approach and trained on labeled examples, in contrast to the unsupervised
cluster-separation based approach. Overall, the findings of the three metrics
agree, reinforcing their conclusions.

The model accuracy and results for all three metrics on seen and unseen
classes are reported in Table 1 for the CIFAR-100 dataset, Table 2 for the
calligraphy dataset.

Table 1: Generalization $g$ of classification networks for unseen and seen classes after fine-tuning on CIFAR-100 dataset. Network | ViT | Swin | PViT | CvT | PF | CNV2
---|---|---|---|---|---|---
accuracy | 0.97 | 0.95 | 0.92 | 0.95 | 0.93 | 0.95
$g_{\text{\tiny NMI,seen}}$ | 0.84 | 0.71 | 0.76 | 0.78 | 0.75 | 0.79
$g_{\text{\tiny NMI,unseen}}$ | 0.26 | 0.04 | 0.21 | 0.15 | 0.22 | 0.15
$g_{\text{\tiny kNN,seen}}$ | 0.20 | 0.13 | 0.20 | 0.20 | 0.19 | 0.20
$g_{\text{\tiny kNN,unseen}}$ | 0.36 | 0.24 | 0.33 | 0.31 | 0.33 | 0.30
$g_{\text{\tiny LPr,seen}}$ | 0.96 | 0.92 | 0.92 | 0.95 | 0.92 | 0.94
$g_{\text{\tiny LPr,unseen}}$ | 0.90 | 0.67 | 0.82 | 0.80 | 0.83 | 0.80
Table 2: Generalization $g$ of classification networks for unseen and seen classes after fine-tuning on calligraphy dataset. Network | ViT | Swin | PViT | CvT | PF | CNV2
---|---|---|---|---|---|---
accuracy | 0.98 | 0.99 | 0.98 | 0.99 | 0.99 | 0.99
$g_{\text{\tiny NMI,seen}}$ | 0.97 | 0.8 | 0.95 | 0.94 | 0.94 | 0.93
$g_{\text{\tiny NMI,unseen}}$ | 0.68 | 0.59 | 0.76 | 0.63 | 0.78 | 0.5
$g_{\text{\tiny kNN,seen}}$ | 0.38 | 0.34 | 0.38 | 0.37 | 0.37 | 0.37
$g_{\text{\tiny kNN,unseen}}$ | 0.56 | 0.5 | 0.56 | 0.54 | 0.57 | 0.47
$g_{\text{\tiny LPr,seen}}$ | 0.99 | 0.95 | 0.98 | 0.99 | 0.98 | 0.99
$g_{\text{\tiny LPr,unseen}}$ | 0.97 | 0.93 | 0.95 | 0.96 | 0.96 | 0.96

##  4 Conclusion

As current models become larger and increasingly expensive to train, due to
the cost of manually labeling many images, hardware, and energy consumption,
there is a real necessity for developing models that can reliably organize
data from related domains in such a way that allows unseen classes to be
distinguished (e.g., for few-shot learning).

Intuitively, different architectures are likely to impose different inductive
biases, which may or may not help with generalization. First, we confirmed
that higher accuracy on a subset of the domain (seen classes) does not imply
higher generalizability: although all models reached high classification
accuracy after fine-tuning (at least 95%, see Fig. 6), they achieved widely
different generalization powers.

Figure 6: Six popular models were fine-tuned for 500 epochs on the Calligraphy
and CIFAR-100 datasets. Each model’s classification accuracy after every 100
epochs is shown above. Comparable performance and qualitatively similar
accuracy curves were observed for all models (although the CIFAR-100 dataset
was more challenging). This is in contrast with generalization power (see Fig.
4).

Second, our experiments demonstrated the central role architecture plays: some
architectures maximize generalization in shallow layers, while others only
generalize at the end. This has obvious implications for pruning and improving
model efficiency at inference time. In the case of ViT, for example, less than
a third of the full network is needed to achieve the highest levels of
generalizability. We believe that our proposed framework can be used to test
architectural modifications and their impact on inferring unseen classes, and
thereby guide future architectural design and improvements.

Future work in this area would look at specific ways to improve
generalizability through architecture design (e.g., number of layers, layer
size, etc.), training paradigms (e.g., contrastive learning), or
regularization techniques (e.g., dropout). Crucially, our method can be used
to quantify which of these are actually important.

Supported by NIH Grant 1R01EY031059, NSF Grant 1822598.

## References

  * Alain and Bengio [2017] G. Alain and Y. Bengio.  Understanding intermediate layers using linear classifier probes.  In _5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Workshop Track Proceedings_. OpenReview.net, 2017.
  * Angeletti et al. [2018] G. Angeletti, B. Caputo, and T. Tommasi.  Adaptive deep learning through visual domain localization.  In _2018 IEEE International Conference on Robotics and Automation (ICRA)_ , pages 7135–7142. IEEE, 2018.
  * Ben-David et al. [2006] S. Ben-David, J. Blitzer, K. Crammer, and F. Pereira.  Analysis of representations for domain adaptation.  _Advances in Neural Information Processing Systems_ , 19, 2006.
  * Ben-David et al. [2010] S. Ben-David, J. Blitzer, K. Crammer, A. Kulesza, F. Pereira, and J. W. Vaughan.  A theory of learning from different domains.  _Machine learning_ , 79:151–175, 2010.
  * Bousmalis et al. [2017] K. Bousmalis, N. Silberman, D. Dohan, D. Erhan, and D. Krishnan.  Unsupervised pixel-level domain adaptation with generative adversarial networks.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 3722–3731, 2017.
  * Brown et al. [2020] T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, et al.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901, 2020.
  * Bucci et al. [2019] S. Bucci, A. D’Innocente, and T. Tommasi.  Tackling partial domain adaptation with self-supervision.  In _Image Analysis and Processing–ICIAP 2019: 20th International Conference, Trento, Italy, September 9–13, 2019, Proceedings, Part II 20_ , pages 70–81. Springer, 2019.
  * Chen et al. [2019] W.-Y. Chen, Y.-C. Liu, Z. Kira, Y.-C. F. Wang, and J.-B. Huang.  A closer look at few-shot classification.  _arXiv preprint arXiv:1904.04232_ , 2019.
  * Danon et al. [2005] L. Danon, A. Diaz-Guilera, J. Duch, and A. Arenas.  Comparing community structure identification.  _Journal of Statistical Mechanics: Theory and experiment_ , 2005(09):P09008, 2005.
  * Dhillon et al. [2019] G. S. Dhillon, P. Chaudhari, A. Ravichandran, and S. Soatto.  A baseline for few-shot image classification.  _arXiv preprint arXiv:1909.02729_ , 2019.
  * Dinh et al. [2017] L. Dinh, R. Pascanu, S. Bengio, and Y. Bengio.  Sharp minima can generalize for deep nets.  In _International Conference on Machine Learning_ , pages 1019–1028. PMLR, 2017.
  * Dosovitskiy et al. [2020] A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai, T. Unterthiner, M. Dehghani, M. Minderer, G. Heigold, S. Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  _arXiv preprint arXiv:2010.11929_ , 2020.
  * Farhadi et al. [2009] A. Farhadi, I. Endres, D. Hoiem, and D. Forsyth.  Describing objects by their attributes.  In _2009 IEEE conference on computer vision and pattern recognition_ , pages 1778–1785. IEEE, 2009.
  * Frome et al. [2013] A. Frome, G. S. Corrado, J. Shlens, S. Bengio, J. Dean, M. Ranzato, and T. Mikolov.  Devise: A deep visual-semantic embedding model.  _Advances in Neural Information Processing Systems_ , 26, 2013.
  * Han et al. [2021] Z. Han, Z. Fu, S. Chen, and J. Yang.  Contrastive embedding for generalized zero-shot learning.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 2371–2381, 2021.
  * Hendrycks and Gimpel [2016] D. Hendrycks and K. Gimpel.  A baseline for detecting misclassified and out-of-distribution examples in neural networks.  _arXiv preprint arXiv:1610.02136_ , 2016.
  * Kang et al. [2019] G. Kang, L. Jiang, Y. Yang, and A. G. Hauptmann.  Contrastive adaptation network for unsupervised domain adaptation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 4893–4902, 2019.
  * Keskar et al. [2017] N. S. Keskar, D. Mudigere, J. Nocedal, M. Smelyanskiy, and P. T. P. Tang.  On large-batch training for deep learning: Generalization gap and sharp minima.  In _International Conference on Learning Representations_ , 2017.  URL https://openreview.net/forum?id=H1oyRlYgg.
  * Kojima et al. [2022] T. Kojima, S. S. Gu, M. Reid, Y. Matsuo, and Y. Iwasawa.  Large language models are zero-shot reasoners.  _Advances in neural information processing systems_ , 35:22199–22213, 2022.
  * Krizhevsky [2009] A. Krizhevsky.  Learning multiple layers of features from tiny images.  Technical report, 2009.
  * Lazarou et al. [2021] M. Lazarou, T. Stathaki, and Y. Avrithis.  Iterative label cleaning for transductive and semi-supervised few-shot learning.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 8751–8760, 2021.
  * Lei Ba et al. [2015] J. Lei Ba, K. Swersky, S. Fidler, et al.  Predicting deep zero-shot convolutional neural networks using textual descriptions.  In _Proceedings of the IEEE international Conference on Computer Vision_ , pages 4247–4255, 2015.
  * Liu et al. [2021a] J. Liu, Z. Shen, Y. He, X. Zhang, R. Xu, H. Yu, and P. Cui.  Towards out-of-distribution generalization: A survey.  _arXiv preprint arXiv:2108.13624_ , 2021a.
  * Liu et al. [2021b] Z. Liu, Y. Lin, Y. Cao, H. Hu, Y. Wei, Z. Zhang, S. Lin, and B. Guo.  Swin transformer: Hierarchical vision transformer using shifted windows.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 10012–10022, 2021b.
  * Louizos et al. [2018] C. Louizos, M. Welling, and D. P. Kingma.  Learning sparse neural networks through $l_{0}$ regularization.  In _International Conference on Learning Representations_ , 2018.  URL https://openreview.net/forum?id=H1Y8hhg0b.
  * Maniyar et al. [2020] U. Maniyar, A. A. Deshmukh, U. Dogan, V. N. Balasubramanian, et al.  Zero shot domain generalization.  _arXiv preprint arXiv:2008.07443_ , 2020.
  * Nichol et al. [2018] A. Nichol, J. Achiam, and J. Schulman.  On first-order meta-learning algorithms.  _arXiv preprint arXiv:1803.02999_ , 2018.
  * Pourpanah et al. [2022] F. Pourpanah, M. Abdar, Y. Luo, X. Zhou, R. Wang, C. P. Lim, X.-Z. Wang, and Q. J. Wu.  A review of generalized zero-shot learning methods.  _IEEE transactions on pattern analysis and machine intelligence_ , 45(4):4051–4070, 2022.
  * Reed et al. [2016] S. Reed, Z. Akata, H. Lee, and B. Schiele.  Learning deep representations of fine-grained visual descriptions.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 49–58, 2016.
  * Simonyan and Zisserman [2014] K. Simonyan and A. Zisserman.  Very deep convolutional networks for large-scale image recognition.  _arXiv preprint arXiv:1409.1556_ , 2014.
  * Socher et al. [2013] R. Socher, M. Ganjoo, C. D. Manning, and A. Ng.  Zero-shot learning through cross-modal transfer.  _Advances in Neural Information Processing Systems_ , 26, 2013.
  * Wang and Deng [2018] M. Wang and W. Deng.  Deep visual domain adaptation: A survey.  _Neurocomputing_ , 312:135–153, 2018.
  * Wang et al. [2021] W. Wang, E. Xie, X. Li, D.-P. Fan, K. Song, D. Liang, T. Lu, P. Luo, and L. Shao.  Pyramid vision transformer: A versatile backbone for dense prediction without convolutions.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 568–578, 2021.
  * Wang [2020] Y. Wang.  Chinese calligraphy styles by calligraphers.  https://www.kaggle.com/datasets/yuanhaowang486/chinese-calligraphy-styles-by-calligraphers, 2020.
  * Wei et al. [2021] J. Wei, M. Bosma, V. Y. Zhao, K. Guu, A. W. Yu, B. Lester, N. Du, A. M. Dai, and Q. V. Le.  Finetuned language models are zero-shot learners.  _arXiv preprint arXiv:2109.01652_ , 2021.
  * Woo et al. [2023] S. Woo, S. Debnath, R. Hu, X. Chen, Z. Liu, I. S. Kweon, and S. Xie.  ConvNeXt V2: Co-designing and scaling convnets with masked autoencoders.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 16133–16142, 2023.
  * Wu et al. [2021] H. Wu, B. Xiao, N. Codella, M. Liu, X. Dai, L. Yuan, and L. Zhang.  Cvt: Introducing convolutions to vision transformers.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 22–31, 2021.
  * Xian et al. [2018] Y. Xian, C. H. Lampert, B. Schiele, and Z. Akata.  Zero-shot learning – a comprehensive evaluation of the good, the bad and the ugly.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 41(9):2251–2265, 2018.
  * Yang et al. [2021] J. Yang, K. Zhou, Y. Li, and Z. Liu.  Generalized out-of-distribution detection: A survey.  _arXiv preprint arXiv:2110.11334_ , 2021.
  * Yang and Hospedales [2014] Y. Yang and T. M. Hospedales.  A unified perspective on multi-domain and multi-task learning.  _arXiv preprint arXiv:1412.7489_ , 2014.
  * Yu et al. [2022] W. Yu, M. Luo, P. Zhou, C. Si, Y. Zhou, X. Wang, J. Feng, and S. Yan.  Metaformer is actually what you need for vision.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 10819–10829, 2022.
  * Zhang et al. [2021] C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals.  Understanding deep learning (still) requires rethinking generalization.  _Communications of the ACM_ , 64(3):107–115, 2021.


# Geometric Graphs with Unbounded Flip-Width††thanks: Research initiated at
the 10th Workshop on Geometry and Graphs, Feb. 3–10, 2023, Bellairs Research
Institute, Barbados. We thank the workshop participants (especially Jit Bose)
and Szymon Toruńczyk for helpful conversations on this work.

David Eppstein Department of Computer Science, University of California,
Irvine. Research supported in part by NSF grant CCF-2212129. Rose McCarty
Department of Mathematics, Princeton University. Research supported by the NSF
under grant DMS-2202961.

###### Abstract

We consider the flip-width of geometric graphs, a notion of graph width
recently introduced by Toruńczyk. We prove that many different types of
geometric graphs have unbounded flip-width. These include interval graphs,
permutation graphs, circle graphs, intersection graphs of axis-aligned line
segments or axis-aligned unit squares, unit distance graphs, unit disk graphs,
visibility graphs of simple polygons, $\beta$-skeletons, 4-polytopes,
rectangle of influence graphs, and 3d Delaunay triangulations.

##  1 Introduction

_Flip-width_ is a new and very general notion of width in graphs, defined by
Szymon Toruńczyk [28] using a cops-and-robbers game on graphs, and intended to
capture graph structure in a way that allows for efficient parameterized
algorithms. It is hoped that testing whether a given graph models a first-
order formula in the logic of graphs can be solved efficiently when
parameterized by flip-width and formula size, although currently this is known
only for more limited classes of graphs [10].

Beyond potential algorithms, another purpose of flip-width is to unify
incompatible notions of graph width, including bounded expansion and of twin-
width. A graph family has bounded expansion if all shallow minors of its
graphs are sparse [25]. It has bounded twin-width if its graphs can be reduced
to one vertex by contracting pairs of vertices so that the subgraph of pairs
of contracted vertices with inconsistent adjacencies maintains bounded degree
throughout the contraction process [6]. The sparse graph families of bounded
flip-width are exactly the families of bounded expansion, and every graph
family of bounded twin-width has bounded flip-width [28]. It is easy to
construct graph families that have bounded flip-width but neither bounded
expansion nor bounded twin-width, such as the family of the graphs that are
either subcubic or cographs. The subcubic graphs have bounded expansion but
unbounded twin-width [3] while cographs reverse these inclusions. This union
is not very natural, though; subcubic graphs and cographs have little in
common. Can we find a natural family of graphs with bounded flip-width, but
neither bounded twin-width nor bounded expansion?

Natural candidates include geometric graphs, whose vertices come from points
or other simple objects in a geometric space, and whose edges are defined by
simple geometric relations between these objects. However, planar graphs, and
bounded-ply disk intersection graphs in bounded dimensions have bounded
expansion [24, 12], as do sparse intersection graphs of connected subsets of a
surface [21, 12]. To find the examples we seek, we need non-sparse graphs.
Geometric graph theory contains many examples of highly structured but non-
sparse graph families. Do any have bounded flip-width?

In this work we provide a negative answer for many standard geometric graphs.
We find a class of subgraphs common to these graphs, which we call
“interchanges” and which provide a winning strategy for a robber in the cops-
and-robbers game used to define flip-width. A graph family that includes
arbitrarily large interchanges has unbounded flip-width. Using this idea we
show that interval graphs, permutation graphs, circle graphs, intersection
graphs of simply-intersecting axis-aligned line segments, intersection graphs
of axis-aligned unit squares, unit distance graphs, unit disk graphs,
visibility graphs of simple polygons, $\beta$-skeletons, rectangle of
influence graphs, and the graphs of 4-polytopes all have unbounded flip-width.
We provide a different construction showing that the graphs of 3-dimensional
Delaunay triangulations have unbounded flip-width.

For many of these graphs we prove more strongly that the radius-1 flip-width
is unbounded and that these graphs are monadically independent, a related
concept in the logic of graphs. A similar approach was used by Hliněný,
Pokrývka, and Roy [17] to prove hardness of first-order model checking on
graph classes with a specific type of interchange, which they call the
“consecutive neighbourhood representation property”. Other hardness results,
as well as some efficient algorithms, have been obtained for various geometric
graphs in [2, 16, 14, 17]. The proofs of such hardness results typically imply
that the flip-width is unbounded, using the following key fact; a transduction
of a class of bounded flip-width also has bounded flip-width [28]. Beyond
extending these results to more graph classes, our approach has the advantages
of only using first concepts, and of providing a concrete robber strategy and
a specific bound on the radius.

##  2 Cops and robbers

Like treewidth [27] and bounded expansion [28], flip-width can be defined
using a certain cops-and-robbers game. The games for treewidth and expansion
involve “cops with helicopters”, chasing a robber on a graph. The cops can
occupy a limited number of graph vertices (initially, none); the robber can
choose any starting vertex. In each time step, the cops announce where they
will move next, the robber moves to escape them on a path through currently-
unoccupied vertices, and then the cops fly directly to their new locations.
The cops win by landing on the robber’s current vertex, and the robber wins by
evading the cops indefinitely. The treewidth of a graph is the maximum number
of cops that a robber can evade, moving arbitrarily far on each move [27]. A
family of graphs has bounded expansion if and only if, for some function $f$,
a robber who moves $\leq r$ steps per move can be caught by $f(r)$ cops [28].

The same game can be described differently. Instead of occupying a vertex, the
cops set up roadblocks on all edges incident to it. On each move, the cops
announce which vertices will be blockaded next. Then, the robber moves along
un-blockaded edges. Finally, the cops remove their current blockades and put
up new blockades at the announced locations. The cops win by leaving the
robber at an isolated vertex, unable to move. Flip-width is defined in the
same way, but with more powerful cops. Instead of blockading a single vertex,
they may “flip” any subset of vertices. This complements the subgraph induced
by that subset: pairs of adjacent vertices become non-adjacent, and vice
versa. Blockading a single vertex, for instance, takes two flips: one flip of
the vertex and its neighbors, and one of just the neighbors. The first flip
disconnects the given vertex, and the second restores its neighbors’
adjacencies. It doesn’t matter in which order these two flips (or any set of
flips) is performed.

In the flipping game used to define flip-width, at any move, the cops may
perform a limited number of flips, initially none. The robber chooses an
arbitrary starting vertex. In each move, the cops announce their next set of
flips. The robber moves on a path in the current flipped graph, to evade these
flips. Then, the cops undo their current flips and perform the flips that they
announced. The cops win by leaving the robber at an isolated vertex, unable to
move, and the robber wins by avoiding this fate indefinitely. A family of
graphs has bounded flip-width if, for some function $f$, $f(r)$ flips per move
suffice to catch a robber who moves $\leq r$ steps per move. Similarly, the
radius-$r$ flip-width of a graph is the least number of flips required to
catch a robber who moves $\leq r$ steps. Bounded flip-width implies bounded
radius-$r$ flip-width, but not vice versa; for instance, subdivisions of
complete graphs have bounded radius-1 flip-width but unbounded flip-width.
Conversely, unbounded radius-$r$ flip-width implies unbounded flip-width, but
not vice versa.

Because flipping can simulate blockading, graphs of bounded treewidth also
have bounded flip-width. However, graphs of unbounded treewidth may have
bounded flip-width. For instance, all planar graphs have bounded flip-width
but the planar graphs have unbounded treewidth.

##  3 Escaping through interchanges

In the treewidth game, escape strategies for the robber are modeled graph-
theoretically by havens, certain functions from subsets of vertices to
connected components of the subgraph formed by their removal [27]. In the same
spirit, and using terminology following a road network metaphor, we define
_interchanges_ , structures in a graph which can be used to define an escape
strategy for the robber in the flipping game.

Figure 1: An interchange of order five, with lanes in blue and ramps in red.
The yellow edges are optional.

######  Definition .

An interchange of order $n$ consists of:

  * •

A linear sequence of $n$ designated vertices, which we call _lanes_.

  * •

More designated vertices, called _ramps_. Each ramp is associated with two
lanes, and each two lanes that are $\leq n-3$ steps apart in the sequence have
a ramp. (We do not require ramps for farther-apart lanes because they would
not be of use to the robber.)

  * •

An edge between each ramp and its two lanes.

  * •

Optional edges between any two lanes or between any two ramps. These will be
unused by the robber. Making them optional, rather than specifying their
presence or absence, allows us to construct geometric realizations without
worrying about whether the construction includes these edges.

  * •

For a ramp that connects lanes $x$ and $y$, optional edges to other lanes
between $x$ and $y$ in the sequence. Edges to lanes outside that range are not
allowed.

Fig. 1 depicts an example.

######  Definition .

Let $\mathcal{F}$ be a collection of flips that could be made in the flipping
game (a family of sets of vertices of a given graph). We define two lanes of
an interchange to be equivalent under $\mathcal{F}$ if, for every flip $F$ in
$\mathcal{F}$, either both lanes belong to $F$ or both are omitted from $F$.

######  Lemma 3.1.

Let $a,b,c$ and $d,e,f$ be two disjoint triples of lanes such that, for a
collection of flips $\mathcal{F}$, all lanes in $\\{a,b,c\\}$ are equivalent
under $\mathcal{F}$, and all lanes in $\\{d,e,f\\}$ are equivalent under
$\mathcal{F}$. Then, after the flips in $\mathcal{F}$ are made, the flipped
interchange contains at least one two-edge lane–ramp–lane path between
$\\{a,b,c\\}$ and $\\{d,e,f\\}$.

######  Proof 3.2.

Assume (by swapping the triples if necessary) that the lane $b$ is before the
lane $e$. Then these six lanes contain the four-lane subsequence $a,b,e,f$. If
ramp $be$ is flipped with respect to the equivalent lanes $\\{a,b,c\\}$, it
becomes adjacent to $a$; otherwise it remains adjacent to $b$. If ramp $be$ is
flipped with respect to the equivalent lanes $\\{d,e,f\\}$ it becomes adjacent
to $f$; otherwise it remains adjacent to $e$. In all cases this ramp connects
at least one lane in $\\{a,b,c\\}$ to at least one lane in $\\{d,e,f\\}$.

######  Lemma 3.3.

Suppose that distinct lanes $a$, $b$, and $c$, in an interchange of order $n$,
are equivalent under a collection of flips $\mathcal{F}$. Then, in the flipped
interchange, at least one of $a$, $b$, or $c$ has paths of length two to at
least $\frac{1}{3}\bigl{(}n-2^{|\mathcal{F}|+1}-3\bigr{)}$-many other lanes.

######  Proof 3.4.

Under the flips in $\mathcal{F}$, there are $2^{|\mathcal{F}|}$ equivalence
classes of lanes. By Lemma 3.1, each equivalence class has at most two lanes
(other than $a$, $b$, and $c$) that are not connected by a two-edge path to at
least one of $a$, $b$, and $c$, because three disconnected but equivalent
lanes would contradict the lemma. The total number of these disconnected
vertices is at most $2^{|\mathcal{F}|+1}$; the remaining
$n-2^{|\mathcal{F}|+1}-3$ vertices have two-edge paths to at least one of $a$,
$b$, or $c$. Even if each were connected to exactly one of $a$, $b$, or $c$,
and even if these connections were evenly distributed between $a$, $b$, and
$c$, the statement of the lemma would hold. Multiple connections or uneven
distribution of connections only increases the largest of the three numbers of
connections among $a$, $b$, and $c$.

######  Theorem 3.5.

Suppose that cops and a robber play the radius-$2$ flipping game with $t$
flips per move on a graph that includes an interchange of order $n=2^{t+3}+3$.
Then the robber can win by moving at each step (including the initial step) to
a lane that maximizes the number of lanes that will be reachable after the
announced flips.

######  Proof 3.6.

In an interchange of this size, by Lemma 3.3, every three equivalent lanes
include one connected to $\geq 2^{t+1}$ other lanes by two-edge paths; it can
reach $\geq 2^{t+1}+1$ lanes including itself by paths of length $\leq 2$.
Among every $2^{t+1}+1$ lanes, at least three are equivalent. By induction, at
each step, the robber has a choice of $\geq 2^{t+1}+1$ lanes to move to, among
which three are equivalent, and therefore can move to a lane that will
continue to reach at least $2^{t+1}+1$ lanes after the announced flips.

Figure 2: Representing an interchange using the intervals of an interval graph
or interval containment graph.

######  Corollary 3.7.

A class of graphs that contains arbitrarily large interchanges does not have
bounded flip-width.

In Appendix A we show, more strongly, that graph classes with large
interchanges are not monadically dependent, a property that generalizes both
classes of bounded flip-width [28] and classes that are nowhere-dense [1].

##  4 Geometric graphs

The geometric graphs known to have bounded flip-width include the unit
interval graphs (which more strongly have bounded twin-width [4]) and the
intersection graphs of disks of bounded ply in any fixed dimension (which more
generally have bounded expansion [24, 12]). We prove that many other classes
of geometric graphs do not have bounded flip-width, by finding large
interchanges in them and applying Corollary 3.7.

######  Theorem 4.1.

The interval graphs, permutation graphs, circle graphs, and intersection
graphs of axis-aligned line segments (no two collinear) have unbounded flip-
width.

######  Proof 4.2.

We construct intervals representing an arbitrarily large interchange, with
short disjoint intervals for each lane and long intervals spanning multiple
lanes for each ramp (Fig. 2). The intersection graph of these intervals is an
interval graph forming the interchange, with all optional lane–ramp edges
included. The interval containment graph, having a vertex per interval and an
edge whenever one interval contains another, differs only in some optional
ramp–ramp edges. Interval containment graphs are the same as permutation
graphs, and are a subclass of circle graphs [7]. For axis-aligned line
segments, lift the ramp intervals to distinct $y$-coordinates, and replace the
lane intervals by tall vertical segments.

Figure 3: Representing an interchange using axis-aligned unit squares.

The graph classes in Theorem 4.1 are monadically independent [2], from which
unbounded flip-width follows, but without a bound on the robber’s escape
radius.

######  Theorem 4.3.

The intersection graphs of axis-aligned unit squares have unbounded flip-
width.

######  Proof 4.4.

Place the intervals of Theorem 4.1 on a diagonal line, scaled to have length
less than $\sqrt{2}$. Represent lanes by squares below this line, intersecting
the line in the given interval, and represent ramps by squares above this line
(Fig. 3). The resulting unit square intersection graph may have additional
lane–lane and ramp–ramp intersections, but these only create optional edges.

Figure 4: Representing an interchange as a unit distance graph or the center
points of a unit disk graph.

######  Theorem 4.5.

The unit distance graphs and unit disk graphs have unbounded flip-width.

######  Proof 4.6.

For unit distance graphs, place points representing the lanes equally spaced
along a line segment of length less than two in the plane, and place points
representing ramps at the intersections of pairs of unit circles centered at
the lane points (Fig. 4). The resulting graph may have ramp–ramp or lane–lane
edges, but it will have no optional lane–ramp edges. For unit disk graphs,
scale the same points by a factor of two so that unit disks centered at them
will be tangent when their points are adjacent in the unit-distance graph. The
resulting unit disk graph includes all possible optional lane–ramp edges,
forming an interchange of the same order.

######  Theorem 4.7.

The visibility graphs of simple polygons do not have bounded flip-width.

######  Proof 4.8.

Place points representing lanes on a horizontal line, and place points
representing the ramps between two consecutive lanes in the same order on a
parallel line above them. Place points representing the remaining ramps,
between non-consecutive lanes, on a third parallel line below the lanes. Draw
a triangle between each ramp vertex and the two lanes it should connect, and
take the union of the triangles. Fill any holes formed in taking the union,
keeping only the outer boundary, to form a simple polygon (Fig. 5). In the
resulting polygon, each ramp still has parts of two triangle sides adjoining
it, blocking its visibility from any lanes that it should not see. Within the
triangle for each ramp, it can see its two lanes and any other lane between
them.

Figure 5: Representing an interchange as the visibility graph of a simple
polygon.

Theorem 4.7 also follows from the fact that simple polygon visibility graphs
are monadically independent [2], which was shown using a similar construction.
Furthermore, simple polygon visibility graphs are _cop-win graphs_ ; a single
cop wins a different cop-and-robber game in which both players move along
graph edges or stand still [23]. But this has no implications for flip-width;
adding a universal vertex to any graph makes it cop-win but does not change
the boundedness of its flip-width.

The _$\beta$ -skeletons_ (for $\beta\leq 1$) are defined from a set of points
by constructing for each pair of points a lune, the intersection of two
congruent disks that cross at these points with angle $\pi-\sin^{-1}\beta$.
Two points are adjacent if this lune contains no other given points [20].

######  Theorem 4.9.

For any $\beta<1$, the $\beta$-skeletons have unbounded flip-width.

######  Proof 4.10.

Place vertices representing lanes and ramps on the lines $y=0$ and $y=1$
respectively, evenly spaced and very close to the line $x=0$, close enough to
ensure that each lane–ramp lune stays within the slab $0\leq y\leq 1$. For
each ramp $r$, place two blocking points on the line $y=1-\varepsilon$ for
suitably small $\varepsilon$, close enough to $r$ to avoid all lunes from
other ramps. These blocking points should be just outside the two lunes
connecting $r$ to its two lanes, one to the left and one to the right, so that
any lune connecting $r$ to a lane outside of its range of lanes contains one
of the blocking points and is non-empty. The resulting $\beta$-skeleton forms
an interchange with all optional lane–ramp edges.

######  Observation 4.11.

The graph of a $d$-dimensional hypercube contains an interchange of order $d$.

######  Proof 4.12.

This is the graph of subsets of a $d$-element set, adjacent when they differ
by one element. Let lanes be singletons and ramps be two-element sets.

_Rectangle of influence graphs_ connect pairs of points in the plane when
their bounding box contains no other points [18, 22]. Sources vary on how to
treat points on the boundary of this bounding box, but that can be avoided
using point sets with no equal coordinates.

Figure 6: A 5-dimensional hypercube graph as an induced subgraph of a
rectangle of influence graph.

######  Theorem 4.13.

Rectangle of influence graphs induce high-dimension hypercubes and have
unbounded flip-width.

######  Proof 4.14.

We recursively construct integer points with distinct coordinates whose
rectangle of influence graphs contain arbitrarily large induced hypercubes. As
a base case, the two points $(0,0)$ and $(1,1)$ give a one-dimensional
hypercube graph. If $X_{d-1}$ is defined in this way, with subset $Y_{d-1}$
inducing a $(d-1)$-dimensional hypercube, construct $X_{d}$ by placing side to
side the following three sets: (1) a copy of $X_{d-1}$ scaled vertically by a
factor of three; (2) a copy of $Y_{d-1}$ scaled by the same factor, offset
vertically by two units (and missing its topmost point), and (3) another
scaled copy of $X_{d-1}$, offset vertically by one unit. Choose $Y_{d}$ to be
the copies of $Y_{d-1}$ within the first and third of these three sets.
Scaling does not affect the hypercube graphs within these copies. The middle
copy of $Y_{d-1}$ blocks all empty rectangles stretching from the first copy
to the third copy, except those between corresponding pairs of points, so
$Y_{d}$ induces a $d$-dimensional hypercube graph.

Fig. 6 illustrates five levels of the recursive construction of Theorem 4.13,
with another (cosmetic) step that compacts the coordinates to use consecutive
integers.

######  Theorem 4.15.

The graphs of four-dimensional convex polytopes, and of three-dimensional
Euclidean Delaunay triangulations, have unbounded flip-width.

######  Proof 4.16.

For 4-polytopes, consider the barycentric subdivisions of neighborly
polytopes. The graph of a neighborly polytope is complete, and barycentric
subdivision preserves realizability as a convex polytope [13]. The barycentric
subdivision replaces the edges of the complete graph by disjoint two-edge
paths. The original vertices of the complete graph form the lanes, and the
subdivision points of these paths form the ramps, of an interchange, whose
order equals the number of vertices in the neighborly polytope.

For Delaunay triangulations, we do not use interchanges; instead we rely on a
result of Toruńczyk that weakly sparse graphs (that is, graphs with no
$K_{t,t}$ subgraph for some $t$) have bounded flip-width if and only if they
have bounded expansion [28]. To construct a Delaunay triangulation that does
not have bounded flip-width, we begin with the convex hull of certain points
in $\mathbb{R}^{4}$ (coordinatized by pairs of complex numbers), the union of
the following three sets of points on a unit sphere, for a given even integer
parameter $n$:

  * •

The $n$ points $(e^{2\pi i/n},0)$ for integer $i$, $0\leq i<n$.

  * •

The $n$ points $(0,e^{2\pi j/n})$ for integer $j$, $0\leq j<n$.

  * •

The $n^{2}$ points $(e^{2\pi i/n}/\sqrt{2},e^{2\pi j/n}/\sqrt{2})$ for $i$ and
$j$ in the same range.

The points with both coordinates nonzero form a square grid on the flat torus
$\\{(x,y)\mid|x|=|y|=1/\sqrt{2}\\}$, and the other two subsets of points form
$n$-gons (not faces of the convex hull) in the planes $x=0$ and $y=0$. Each
edge of an $n$-gon is parallel to the family of edges connecting a ring of
squares on the torus, and the facets of the convex hull are warped triangular
pyramids connecting an $n$-gon edge to one of these parallel squares. The
subgraph induced in the graph of this polytope by the vertices for which $i$
and $j$ are both even is the subdivision of a complete bipartite graph
$K_{n/2,n/2}$. This subdivision has no $K_{2,2}$ subgraph and does not have
bounded expansion, so it does not have bounded flip-width.

To transform this inscribed 4-polytope into a Delaunay triangulation, we apply
a stereographic projection whose pole is the center point of one of the
squares on the torus. On the unit sphere in $\mathbb{R}^{4}$, this pole
belongs to only two of the circumspheres of the facets, for the two facets
meeting at this square. Stereographic projection preserves spheres on the unit
sphere, so the empty spheres of all of the other facets project to empty
spheres for the corresponding set of six points in $\mathbb{R}^{3}$; that is,
these six points form a prism-shaped cell in the Delaunay complex of the
projected points. Each edge of the 4-polytope is part of one of these Delaunay
cells, so the Delaunay graph of the projected points is the same as that of
the complex. Perturbing the points to form a Delaunay triangulation, and
keeping only the points for which $i$ and $j$ are both even, again produces
the subdivision of a complete bipartite graph, as the subgraph of a three-
dimensional Delaunay triangulation.

##  5 Radius-1 flip-width

Our escape strategy for the robber through interchanges involves the robber
taking two steps per move. It is natural to ask whether this can be
strengthened to allow escapes of only one edge per move for the same classes
of geometric graphs. That is, do these geometric graphs have bounded or
unbounded radius-1 flip-width?

In the treewidth game, radius-1 corresponds to _degeneracy_ , where a graph
has degeneracy $\leq d$ if and only if its vertices can be ordered so that
each vertex has $\leq d$ earlier neighbors. The radius-1 treewidth game can be
won by $d+1$ cops, who always play on the current vertex of the robber and its
earlier neighbors, forcing the robber to move later in the ordering. On the
other hand, if the degeneracy is greater than $d$ then the graph has a
$(d+1)$-core, an induced subgraph with minimum degree $d+1$, within which the
robber is safe: no matter where the cops move next, there will be an
unoccupied vertex for the robber within one step [28].

For the radius-1 flip-width game, Toruńczyk identifies a corresponding concept
to a core, which we call a _$\Delta$ -diverse subgraph_. This is an induced
subgraph in which the open neighborhoods of each two vertices differ by at
least $\Delta$ vertices. As Toruńczyk proves, a family of graphs whose graphs
contain $\Delta$-diverse subgraphs, for arbitrarily large $\Delta$, has
unbounded radius-1 flip-width [28]. For cops that make $t$ flips per move, the
robber can escape by staying within a $2^{t+1}$-diverse subgraph and moving to
a vertex $v$ in this subgraph such that, after the announced flips, $v$ will
have at least $2^{t}$ neighbors. These neighbors, and $v$ itself, form a set
of $2^{t}+1$ vertices within which the robber can move, some two of which (say
$x$ and $y$) will be equivalent after the cops’ flips. Each vertex adjacent to
exactly one of $x$ and $y$ will remain adjacent to exactly one after the
flips, so one of $x$ and $y$ will have $\geq 2^{t}$ neighbors, enough to
continue the same strategy.

Slightly more generally, define a $(\Delta,\chi)$-diverse subgraph for a
subset of vertices in a given graph and an (improper) $\chi$-coloring of those
vertices, keeping all properly colored edges and removing all improperly
colored ones, with diversity measured between vertices of the same color. The
robber escapes by staying in a $(2^{t+1}(\chi-1)+2,\chi)$-diverse subgraph and
moving to a vertex with at least $2^{t}(\chi-1)+1$ differently-colored
neighbors. Some two neighbors will have the same color and be treated
equivalently by all flips, and one of these two will have enough neighbors in
the next move.

######  Lemma 5.1.

An order-$n$ interchange with all optional lane–ramp edges has an
$(\Omega(n^{1/3}),2)$-diverse subgraph.

######  Proof 5.2.

Number the lanes of the interchange from $0$ to $n-1$, and choose a parameter
$k\approx n^{1/3}$. Form a two-colored subgraph (colored by lanes and ramps)
with all lanes and a subset of ramps, the ramps for lanes $x$ and $y$ with
$x<y$ that meet the following two conditions: (1) $|y-x|\geq k$, and (2)
$x\equiv ky\bmod{k^{2}+1}$. The second condition leaves $\Theta(n^{1/3})$
ramps starting or ending at each lane, enough so every two lanes have diverse
neighborhoods.

Figure 7: The integer points $(x,y)$ with $x\equiv ky\bmod{k^{2}+1}$ (shown
for $k=4$) form a tilted grid in which all pairs of points have $L_{1}$
distance at least $k+1$.

Two ramps with disjoint ranges of lanes are distinguished by all their
neighbors, of which there are $\Omega(n^{1/3})$ by the first condition. Two
ramps with overlapping ranges of lanes $[x,y]$ and $[x^{\prime},y^{\prime}]$
are distinguished by the lanes between $x$ and $x^{\prime}$, and the lanes
between $y$ and $y^{\prime}$; there are $|x-x^{\prime}|+|y-y^{\prime}|$ such
lanes. The condition that $x\equiv ky\bmod{k^{2}+1}$ defines a subset of the
integer grid in the form of a tilted square grid in which all pairs of points
are at $L_{1}$ distance at least $k+1$ (Fig. 7), so the number of lanes that
are neighbors of only one of the two ramps is also at least
$k+1=\Omega(n^{1/3})$.

######  Corollary 5.3.

Interval graphs, permutation graphs, circle graphs, intersection graphs of
axis-aligned unit squares, unit disk graphs, visibility graphs of simple
polygons, and $\beta$-skeletons with $\beta<1$ have unbounded radius-1 flip-
width.

######  Observation 5.4.

The graph of a $d$-dimensional hypercube is $(2d-2)$-diverse.

######  Proof 5.5.

It is $d$-regular, and the neighborhoods of any two vertices can share at most
two neighbors.

######  Corollary 5.6.

Unit distance graphs, graphs of 4-polytopes, and rectangle of influence graphs
have unbounded radius-1 flip-width.

######  Proof 5.7.

The $d$-dimensional hypercube graphs can be drawn as unit distance graphs by
linear projections that map the basis vectors of $\mathbb{R}^{d}$ to generic
unit vectors in the plane [8]. They are the graphs of the 4-dimensional
_neighborly cubical polytopes_ [19]. For rectangle of influence graphs, the
result follows from Theorem 4.13

We do not know whether three-dimensional Delaunay triangulations have bounded
radius-1 flip-width; we leave this as open for future research.

## References

  * [1] Hans Adler and Isolde Adler.  Interpreting nowhere dense graph classes as a classical notion of model theory.  Eur. J. Comb., 36:322–330, 2014.  doi:10.1016/j.ejc.2013.06.048.
  * [2] Édouard Bonnet, Dibyayan Chakraborty, Eun Jung Kim, Noleen Köhler, Raul Lopes, and Stéphan Thomassé.  Twin-Width VIII: Delineation and win-wins.  In Holger Dell and Jesper Nederlof, editors, 17th International Symposium on Parameterized and Exact Computation, IPEC 2022, September 7–9, 2022, Potsdam, Germany, volume 249 of LIPIcs, pages 9:1–9:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022.  doi:10.4230/LIPIcs.IPEC.2022.9.
  * [3] Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant.  Twin-width II: small classes.  In Dániel Marx, editor, Proceedings of the 2021 ACM–SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10–13, 2021, pages 1977–1996. SIAM, 2021.  doi:10.1137/1.9781611976465.118.
  * [4] Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant.  Twin-width III: max independent set, min dominating set, and coloring.  In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12–16, 2021, Glasgow, Scotland (Virtual Conference), volume 198 of LIPIcs, pages 35:1–35:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021.  doi:10.4230/LIPIcs.ICALP.2021.35.
  * [5] Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé, and Szymon Toruńczyk.  Twin-width IV: ordered graphs and matrices.  In Stefano Leonardi and Anupam Gupta, editors, STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20–24, 2022, pages 924–937, New York, NY, USA, 2022. Association for Computing Machinery.  doi:10.1145/3519935.3520037.
  * [6] Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant.  Twin-width I: tractable FO model checking.  J. ACM, 69(1):A3:1–A3:46, 2022.  doi:10.1145/3486655.
  * [7] Andreas Brandstädt, Van Bang Le, and Jeremy P. Spinrad.  Graph Classes: A Survey.  SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics, 1999.  doi:10.1137/1.9780898719796.
  * [8] Peter Brass.  Erdős distance problems in normed spaces.  Comput. Geom. Theory & Appl., 6(4):195–214, 1996.  doi:10.1016/0925-7721(95)00019-4.
  * [9] Samuel Braunfeld and Michael C. Laskowski.  Characterizations of monadic NIP.  Trans. Amer. Math. Soc. Ser. B, 8:948–970, 2021.  doi:10.1090/btran/94.
  * [10] Jan Dreier, Nikolas Mählmann, and Sebastian Siebertz.  First-order model checking on structurally sparse graph classes.  Electronic preprint arxiv:2302.03527, 2023.
  * [11] Zdeněk Dvořák, Mirna Džamonja, Agelos Georgakopoulos, Jan Obdržálek, Patrice Ossona de Mendez, Sylvain Schmitz, Szymon Toruńczyk, and Jan Volec.  Open problems.  In Workshop on Algorithms, Logic and Structure. University of Warwick, December 12–14 2016.  Online web site, accessed March 19, 2023.  URL: https://warwick.ac.uk/fac/sci/maths/people/staff/daniel_kral/alglogstr/openproblems.pdf.
  * [12] Zdeněk Dvořák and Sergey Norin.  Strongly sublinear separators and polynomial expansion.  SIAM J. Discrete Math., 30(2):1095–1101, 2016.  doi:10.1137/15M1017569.
  * [13] G. Ewald and G. C. Shephard.  Stellar subdivisions of boundary complexes of convex polytopes.  Math. Ann., 210:7–16, 1974.  doi:10.1007/BF01344542.
  * [14] Jakub Gajarský, Petr Hliněný, Daniel Lokshtanov, Jan Obdrzálek, Sebastian Ordyniak, M. S. Ramanujan, and Saket Saurabh.  FO model checking on posets of bounded width.  In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17–20 October, 2015, pages 963–974. IEEE Computer Society, 2015.  doi:10.1109/FOCS.2015.63.
  * [15] Jakub Gajarský, Petr Hliněný, Jan Obdržálek, Daniel Lokshtanov, and M. S. Ramanujan.  A new perspective on FO model checking of dense graph classes.  ACM Trans. Comput. Log., 21(4):A28:1–A28:23, 2020.  doi:10.1145/3383206.
  * [16] Robert Ganian, Petr Hliněný, Daniel Král, Jan Obdržálek, Jarett Schwartz, and Jakub Teska.  FO model checking of interval graphs.  Log. Methods Comput. Sci., 11(4):1–20, 2015.  doi:10.2168/LMCS-11(4:11)2015.
  * [17] Petr Hliněný, Filip Pokrývka, and Bodhayan Roy.  FO model checking on geometric graphs.  Comput. Geom. Theory & Appl., 78:1–19, 2019.  doi:10.1016/j.comgeo.2018.10.001.
  * [18] Manabu Ichino and Jack Sklansky.  The relative neighborhood graph for mixed feature variables.  Pattern Recognition, 18(2):161–167, 1985.  doi:10.1016/0031-3203(85)90040-8.
  * [19] M. Joswig and Günter M. Ziegler.  Neighborly cubical polytopes.  Discrete Comput. Geom., 24(2-3):325–344, 2000.  doi:10.1007/s004540010039.
  * [20] David G. Kirkpatrick and John D. Radke.  A framework for computational morphology.  In Computational Geometry, volume 2 of Machine Intelligence and Pattern Recognition, pages 217–248. North-Holland, Amsterdam, 1985.
  * [21] James R. Lee.  Separators in region intersection graphs.  In Christos H. Papadimitriou, editor, 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9–11, 2017, Berkeley, CA, USA, volume 67 of LIPIcs, pages 1:1–1:8. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017.  doi:10.4230/LIPIcs.ITCS.2017.1.
  * [22] Giuseppe Liotta, Anna Lubiw, Henk Meijer, and Sue H. Whitesides.  The rectangle of influence drawability problem.  Comput. Geom. Theory & Appl., 10(1):1–22, 1998.  doi:10.1016/S0925-7721(97)00018-7.
  * [23] Anna Lubiw, Jack Snoeyink, and Hamideh Vosoughpour.  Visibility graphs, dismantlability, and the cops and robbers game.  Comput. Geom. Theory & Appl., 66:14–27, 2017.  doi:10.1016/j.comgeo.2017.07.001.
  * [24] Gary L. Miller, Shang-Hua Teng, William Thurston, and Stephen A. Vavasis.  Separators for sphere-packings and nearest neighbor graphs.  J. ACM, 44(1):1–29, January 1997.  doi:10.1145/256292.256294.
  * [25] Jaroslav Nešetřil and Patrice Ossona de Mendez.  5.5 Classes with bounded expansion.  In Sparsity: Graphs, Structures, and Algorithms, volume 28 of Algorithms and Combinatorics, pages 104–107. Springer, 2012.  doi:10.1007/978-3-642-27875-4.
  * [26] Jaroslav Nesetril, Patrice Ossona de Mendez, and Sebastian Siebertz.  Structural properties of the first-order transduction quasiorder.  In Florin Manea and Alex Simpson, editors, 30th EACSL Annual Conference on Computer Science Logic, CSL 2022, February 14–19, 2022, Göttingen, Germany (Virtual Conference), volume 216 of LIPIcs, pages 31:1–31:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022.  doi:10.4230/LIPIcs.CSL.2022.31.
  * [27] Paul D. Seymour and Robin Thomas.  Graph searching and a min-max theorem for tree-width.  J. Combinatorial Theory, Ser. B, 58(1):22–33, 1993.  doi:10.1006/jctb.1993.1027.
  * [28] Szymon Toruńczyk.  Flip-width: cops and robber on dense graphs.  Electronic preprint arxiv:2302.00352, 2023.

##  Appendix A Monadic dependence

In this appendix we show that graph classes that include arbitrarily large
interchanges are monadically independent. This in particular implies that they
do not have bounded flip-width, but unlike Theorem 3.5 it does not directly
bound the radius $r$ at which the robber can win.

Here, _monadic dependence_ is a general notion for logical relations of
arbitrary arity based on the concept of a _transduction_ , a method of
representing one logical structure by a system of first-order formulas over a
finite system of monadic predicates, or equivalently over a finite coloring,
of a second structure [9]. When applied to the first-order theory of graphs, a
transduction is a mapping from vertex-colored graphs to graphs, defined by
logical predicates that describe which pairs of vertices are adjacent in the
image graph, and which vertices of the starting graph correspond to vertices
in the image graph [26]. A family of graphs $\mathcal{F}$ is monadically
dependent (also written as “monadically NIP”) if every transduction on the
graphs in $\mathcal{F}$ is incomplete: there is some target graph that it does
not produce, regardless of which graph in $\mathcal{F}$ and which coloring of
that graph it is applied to. On the other hand, $\mathcal{F}$ is monadically
independent (“not monadically NIP”) if it is possible to find a “universal”
transduction, one that maps colorings of graphs in $\mathcal{F}$ to all
possible graphs.

It is conjectured that, among hereditary graph families, the monadically
dependent families are exactly the ones for which first-order model checking
is fixed-parameter tractable [11, 15]. For hereditary classes of ordered
graphs, and logical properties that can make use of this ordering, being
monadically dependent is equivalent to having bounded twin-width [5]. Without
the assumption of an ordering, bounded flip-width implies monadically
dependence, and a weakening of bounded flip-width, _almost bounded flip-width_
, is conjectured to be equivalent to monadic dependence [28].

In this section we use a slightly stronger definition of interchanges that
includes ramps between all pairs of lanes, instead of omitting the outermost
lanes. An interchange under this stronger definition satisfies the weaker
definition (where fewer ramps are required). In the other direction, an
interchange for the weaker definition can be converted to one for the stronger
definition, with two fewer lanes, by omitting the two outermost lanes.

We first observe that every huge interchange contains, as an induced subgraph,
a large interchange in which either all optional ramp-lane edges are present,
or a large interchange in which no optional ramp-lane edges are present. Call
those two types of interchanges _dense interchanges_ and _sparse interchanges_
, respectively.

######  Lemma A.1.

If a class of graphs contains arbitrarily large interchanges, it contains
either arbitrarily large dense interchanges or arbitrarily large sparse
interchanges.

######  Proof A.2.

This follows from applying standard methods of Ramsey theory to a 2-colored
3-uniform hypergraph on triples of lanes, with each triple given color $1$ if
an optional edge connects the middle of the three lanes to the ramp between
the two outer lanes, and color $0$ if the optional edge is not present. By
Ramsey’s theorem, we can extract a large subset of the lanes that induces a
monochromatic sub-hypergraph. The selected lanes, together with the ramps
associated with pairs of selected lanes, then form a large regular
interchange: if they all have color $1$, the result is a dense interchange,
and if they all have color $0$, the result is a sparse interchange.

The following result is from Szymon Toruńczyk (personal communication):

######  Theorem A.3.

A graph class that contains arbitrarily large interchanges as induced
subgraphs is monadically independent.

######  Proof A.4.

By Lemma A.1, we can assume either that there are arbitrarily large sparse
interchanges, or that there are arbitrarily large dense interchanges. We show
that in each of these cases, the class is monadically independent.

We first argue that any class containing arbitrarily large sparse interchanges
is monadically independent. We can represent an arbitrary $n$-vertex graph $G$
in a colored sparse interchange with at least $n$ lanes, by identifying the
vertices of $G$ with a subset of the lanes, and for each ramp associated with
a pair $uv$ of vertices of $G$, marking this ramp with a special color if and
only if $u$ and $v$ are adjacent in $G$. Formally, describe this marking by a
monadic predicate $A(z)$ that is true of these marked ramps and false for all
other vertices. Then adjacency in the original graph $G$ can be recovered from
the obtained colored interchange, by a first-order formula

$\phi(x,y)\equiv\exists z\bigl{(}x\sim z\wedge y\sim z\wedge A(z)\bigr{)}$

(where adjacency in $G$ is represented by the binary predicate $\sim$),
expressing that there is a vertex $z$ that is adjacent to $x$ and $y$ and has
the special marking. The formula $\phi$ does not depend on the selected graph
$G$. It follows that the formula $\phi$ can be used to define a transduction
that may produce an arbitrary graph $G$ from any sufficiently large sparse
interchange, by first coloring its vertices using a single special color, then
applying the formula $\phi(x,y)$ to define a new edge relation, and finally,
taking an induced subgraph to restrict only to the lanes of the interchange
that correspond to the vertices of $G$. Thus, every class transduces the class
of all graphs, and is therefore monadically independent.

We now argue that every class containing arbitrarily large dense interchanges
is monadically independent, by showing that such a class transduces a class of
arbitrarily large sparse interchanges. Since transductions can be composed,
this implies that the former class is monadically independent.

Given a dense interchange, color all the ramps using a special color, denoted
by the monadic predicate $R(v)$, and color the first lane (in the order on
lanes) with another color, denoted by the monadic predicate $F(v)$. We can
recover the order on two lanes $x$ and $y$ using a first-order formula

$\begin{split}\psi(x,y)&\equiv\\\ &\bigl{(}F(x)\wedge x\neq y\bigr{)}\vee{}\\\
&\exists w\exists z\bigl{(}F(w)\wedge R(z)\wedge w\sim z\wedge x\sim
z\wedge\lnot(y\sim z)\bigr{)}.\\\ \end{split}$

Namely, a lane $x$ is smaller than a lane $y$ if and only if either $x$ is the
first lane, or there a ramp $z$ which is adjacent to the first lane and to $x$
but not to $y$. Since ramps and the first lane are marked with a special
color, this can be expressed using a fixed first-order formula (not depending
on the interchange), that can use the colors.

Now, we can identify the two lanes $x,y$ to which a ramp $z$ is associated
with, using a first-order formula. Namely, in a sparse interchange, a ramp $z$
should be associated with exactly the smallest lane, and the largest lane
among its neighboring lanes. Therefore, $z$ is associated with a lane $x$ if
and only if $z$ is adjacent to $x$ and there do not exist lanes $u$ and $v$,
smaller and larger than $x$, respectively, that are also adjacent to $z$. This
can be expressed by a first-order formula

$\begin{split}\gamma(x,z)\equiv{}&\lnot R(x)\wedge R(z)\wedge x\sim
z\wedge{}\\\ &\lnot\exists u\exists v\left(\begin{split}&\lnot R(u)\wedge\lnot
R(v)\wedge{}\\\ &u\sim z\wedge v\sim z\wedge{}\\\ &\psi(u,x)\wedge\psi(x,v)\\\
\end{split}\right).\end{split}$

that uses the colors, and does not depend on the considered interchange. Thus,
the formula $\gamma(x,z)$ defines the edges of a sparse interchange, of the
same size as the original dense interchange.

Hence, every class that contains arbitrarily large dense interchanges as
induced subgraphs transduces a class that contains arbitrarily large sparse
interchanges, and is therefore monadically independent.

This applies, in particular, to all the classes of geometric graphs for which
we have constructed large interchanges. Our proof that three-dimensional
Delaunay triangulations have unbounded flip-width is an exception, as it does
not use interchanges. However, in this case we have constructed weakly sparse
Delaunay triangulations that are not nowhere-dense, so it follows from known
results that they are monadically independent.


# Error-correction and extraction in request dialogs

Stefan Constantin
<EMAIL_ADDRESS>
Karlsruhe Institute of Technology  Alex Waibel
<EMAIL_ADDRESS>
Karlsruhe Institute of Technology

###### Abstract

We propose a component that gets a request and a correction and outputs a
corrected request. To get this corrected request, the entities in the
correction phrase replace their corresponding entities in the request. In
addition, the proposed component outputs these pairs of corresponding
reparandum and repair entity. These entity pairs can be used, for example, for
learning in a life-long learning component of a dialog system to reduce the
need for correction in future dialogs.

For the approach described in this work, we fine-tune BERT for sequence
labeling. We created a dataset to evaluate our component; for which we got an
accuracy of 93.28 %. An accuracy of 88.58 % has been achieved for out-of-
domain data. This accuracy shows that the proposed component is learning the
concept of corrections and can be developed to be used as an upstream
component to avoid the need for collecting data for request corrections for
every new domain.

##  1 Introduction

Errors and ambiguities are difficult to avoid in a dialog. Corrections allow
to recover from errors and to disambiguate ambiguities. For example, a
household robot gets the request Put the cleaned knives into the cutlery
drawer, but the robot does not know which one of the drawers is the cutlery
drawer. It can choose one of the drawers and puts the knives there. If its
choice is wrong, the user must correct the robot, e. g. No, into the drawer
right of the sink. Alternatively, the robot can ask which one of the drawers
is the cutlery drawer. The clarification response of the human, e. g. It’s the
drawer right of the sink, is also a correction because the response
disambiguates the ambiguity. Another type of correction occurs when the user
changes their mind, e. g. I changed my mind, the forks.

All these correction types can be processed in the same manner and therefore
we propose a component that gets a request and a correction and outputs a
corrected request. To get this corrected request, the entities in the
correction phrase replace their corresponding entities in the request. The
request Put the cleaned knives into the cutlery drawer with its correction No,
into the drawer right of the sink is converted to Put the cleaned knives into
the drawer right of the sink. Such a component has two advantages compared to
handling the corrections in the actual dialog component. First, it reduces the
amount of required training data for the actual dialog component because
corrections will not need to be learned if there is an open-domain correction
component. Second, this kind of correction component can be extended so that
it outputs the pairs of reparandum and repair entity. In our example there is
one pair: cutlery drawer and drawer right of the sink. These entity pairs can
be used, for example, for learning in a life-long learning component of a
dialog system to reduce the need for correction in future dialogs, e. g. the
robot can learn which one of the drawers is the cutlery drawer.

##  2 Related Work

The task of request correction is related to the task of disfluency removal.
In disfluency removal, there are the reparandum (which entity should be
replaced), the interruption point (where the correction begins), the
interregnum (which phrase is the signal phrase for the correction), and the
repair phrase (the correct entity) [5].

In Figure 1, a disfluent utterance annotated with this terminology is
depicted.

knives in the $\underbrace{\text{drawer}}_{\text{reparandum}}$
$\underbrace{\text{}}_{\text{interruption point}}$
$\underbrace{\text{uh}}_{\text{interregnum}}$
$\underbrace{\text{sink}}_{\text{repair}}$

Figure 1: disfluent utterance annotated with repair terminology

A lot of work has been conducted for disfluency removal [1, 3, 6, 4]. In all
these works, it is assumed that it is enough to delete tokens of the disfluent
utterance to get a fluent utterance. A disfluent utterance with the copy and
delete labels is depicted in Figure 2.

knives | in | the | drawer | uh | sink
---|---|---|---|---|---
C | C | C | D | D | C
Figure 2: disfluent utterance labeled with copy and delete labels

However, in the task of corrections, long-distance replacements can occur.
Such a long-distance replacement is depicted in Figure 3.

$\underbrace{\text{knives}}_{\text{reparandum}}\text{in the
drawer}\underbrace{\text{}}_{\text{interruption
point}}\underbrace{\text{no}}_{\text{interregnum}}\underbrace{\text{forks}}_{\text{repair}}$
Figure 3: request and correction phrase annotated with repair terminology

##  3 Dataset

We created a dataset with requests and corresponding corrections. Outputs of
the system like error actions and clarification questions are not part of the
dataset. The training dataset is in the domain of a kitchen robot. For the
first version of the dataset, we focused on the task of bringing a specified
object to a specified location and cooking a specified recipe.

We collected 20 utterances and correspondingly 20 correction responses from
each of the seven participants for the task of bringing a specified object to
a specified location. For the task of cooking a specified recipe, we collected
10 utterances and correspondingly 10 correction responses from each of the
seven participants. Examples of the collected data are the request Put the
cleaned knives into the cutlery drawer, the correction of the robot’s wrong
action No, into the drawer right of the sink, the clarification It’s the
drawer right of the sink, or the user’s change of mind I changed my mind, the
forks. Correction responses were collected to correct or clarify the object,
the location, the object and the location, or the recipe.

The collected data was used as inspiration to build templates that try to
cover the natural language variety. To increase this variety, we added
synonyms, new objects, new locations, and new recipes to the collected data.
Example templates are depicted in Figure 4. We created 15 templates for the
requests and 45 templates for the correction responses and got 74 309 request
and correction pairs.

example request templates:
can you put the object into the location
the location is the place where you put the object

example correction templates:
no the other object than in the request template into the other location than
in the request template
i meant the other location than in the request template

Figure 4: example templates

The dataset has two targets. The first target is the corrected request, while
the second target is the pairs of reparandum and repair entity.

In our validation and testing dataset, the following four abilities: handling
of unknown entities, unknown templates, unknown entities and templates, out-
of-domain templates and entities are tested. For testing the handling of
unknown entities, we used the templates of the training dataset and replaced
all entities with entities not occurring in the training dataset. In order to
test the generalization in regard to the variety of natural language, we
replaced all templates of the training dataset with unknown templates with the
same semantic. To combine both described tests, we used only unknown entities
and templates. To test whether the trained model can be used for other domains
or tasks without retraining, we used the new tasks of buying a product and
attaching a specific object to a specific location. There are 400 request and
correction pairs for validation and 1727 pairs for testing. In Table 1, the
numbers of pairs for the individual tests are depicted.

| validation | test
---|---|---
unknown entities | 100 | 205
unknown templates | 100 | 606
unknown entities and templates | 100 | 584
out-of-domain entities and templates | 100 | 332
sum | 400 | 1727
Table 1: validation and test dataset sizes

##  4 Model

For the correction and extraction, we used a sequence labeling approach. We
labeled every word token either with the token C (copy), D (delete), R1
(entity 1 potentially to be replaced), R2 (entity 2 potentially to be
replaced), S1 (entity to replace entity 1), or S2 (entity to replace entity
2). For the correction target, we used the S1 and S2 labeled entities to
replace the R1 and R2 labeled entities, respectively. For the extraction
target, the output is the pairs R1 and S1 as well as R2 and S2. In Figure 5,
an example request and correction pair is labeled and both targets are given.

request || correction | cook | rice | for | me | no | curry | rice
---|---|---|---|---|---|---|---
labels | C | R1 | C | C | D | S1 | S1
corrected request | cook curry rice for me
pairs of reparandum and repair entity | rice → curry rice
Figure 5: sequence labeling approach

For the sequence labeling, we fine-tuned the cased BERT base model (12
Transformer blocks, hidden size of 768, 12 self-attention heads, and 110M
parameters) [2] with a Named Entity Recognition
tool111https://github.com/kyzhouhzau/BERT-NER. We fine-tuned three epochs with
a starting fine-tuning learning rate of $2e^{-5}$.

##  5 Evaluation

We evaluated our architecture with the metric accuracy. A request and
correction pair was correctly converted if both targets, the corrected request
and the pairs of reparandum and repair entity were equal to their references.

The results for the datasets are depicted in Table 2.

| validation | test
---|---|---
unknown entities | 100 % | 98.54 %
unknown templates | 97 % | 97.03 %
unknown entities and templates | 91 % | 90.24 %
out-of-domain entities and templates | 82 % | 88.55 %
all together | 92.50 % | 93.28 %
Table 2: evaluation results (metric accuracy both targets correct)

The replacement of trained entities with unknown entities or trained templates
with unknown templates does not cause problems for the trained model. We still
got an accuracy of 98.54 % or 97.03 %, respectively. The combination of both,
reduced the performance to 90.24 %. We got an accuracy of 88.35 % for out-of-
domain entities and templates.

##  6 Conclusions and Further Work

The proposed component that can convert a request and a correction into a
correct request, and can extract the pairs of reparandum and repair entity,
shows high potential. An accuracy of 88.58 % has been achieved for out-of-
domain data. This accuracy shows that the proposed component is learning the
concept of corrections and can be developed to be used as an upstream
component to avoid the need for collecting data for request corrections for
every new domain. In addition, the extraction of the pairs of reperandum and
repair entity can be used for learning in a life-long learning component of a
dialog system to reduce the need for correction in future dialogs.

In future work, the training dataset can be extended by new tasks which will
enable the model to learn the concept of corrections even better and to get a
better out-of-domain performance. Another research topic could be the
classification of correction types to give this information the life-long
learning component.

##  7 Acknowledgement

The project on which this report is based was funded by the Federal Ministry
of Education and Research (BMBF) of Germany under the number 01IS18040A. The
authors are responsible for the content of this publication.

We thank Leonard Bärmann, Thanh-Le Ha, Teresa Herrmann, Tuan-Nam Nguyen, Ngoc-
Quan Pham, Felix Schneider, and Franziska Vogel for participating in the data
collection.

## References

  * [1] Eunah Cho, Jan Niehues, and Alex Waibel.  Machine translation of multi-party meetings: Segmentation and disfluency removal strategies.  In Proceedings of the 11th International Workshop on Spoken Language Translation, 2014.
  * [2] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics (NACL), 2019.
  * [3] Qianqian Dong, Feng Wanga, Zhen Yang, Wei Chenand Shuang Xu, and Bo Xu.  Adapting translation models for transcript disfluency detection.  In Proceedings of the Thirty-Third Conference on Artificial Intelligence (AAAI), 2019.
  * [4] Paria Jamshid Lou, Peter Anderson, and Mark Johnson.  Disfluency detection using auto-correlational neural networks.  In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing (EMNLP), 2018.
  * [5] Elizabeth Ellen Shriberg.  Preliminaries to a Theory of Speech Disfluencies.  PhD thesis, University of California, 1994.
  * [6] Shaolei Wang, Wanxiang Che, and Ting Liu.  A neural attention model for disfluency detection.  In Proceedings of the 26th International Conference on Computational Linguistic (COLING), 2016.