#  : A Benchmark for Lexical Substitution
with Improved Data Coverage and Quality

Mina Lee* &Chris Donahue* &Robin Jia
Stanford University
{minalee, cdonahue, robinjia, aiyabor<EMAIL_ADDRESS>
&Alexander Iyabor &Percy Liang

###### Abstract

We release a new benchmark for lexical substitution, the task of finding
appropriate substitutes for a target word in a context. To assist humans with
writing, lexical substitution systems can suggest words that humans cannot
easily think of. However, existing benchmarks depend on human recall as the
only source of data, and therefore lack coverage of the substitutes that would
be most helpful to humans. Furthermore, annotators often provide substitutes
of low quality, which are not actually appropriate in the given context. We
collect higher-coverage and higher-quality data by framing lexical
substitution as a classification problem, guided by the intuition that it is
easier for humans to judge the appropriateness of candidate substitutes than
conjure them from memory. To this end, we use a context-free thesaurus to
produce candidates and rely on human judgement to determine contextual
appropriateness. Compared to the previous largest benchmark, our benchmark has
4.1x more substitutes per target word for the same level of quality, and its
substitutes are 1.5x more appropriate (based on human judgement) for the same
number of substitutes.

00footnotetext: *Equal contribution.

##  1 Introduction

Imagine you are writing the message “I read an amazing paper today” to a
colleague, but you want to choose a more descriptive adjective to replace
“amazing.” At first you might think of substitutes like “awesome” and “great,”
but feel that these are also unsatisfactory. You turn to a thesaurus for
inspiration, but among reasonable alternatives like “incredible” and
“fascinating” are words like “prodigious” which do not quite fit in your
context. Ultimately, you choose to go with “fascinating,” but reaching this
decision required a non-trivial amount of time and effort.

Research on _lexical substitution_ (McCarthy, 2002; McCarthy and Navigli,
2007; Erk and Padó, 2008; Szarvas et al., 2013; Kremer et al., 2014; Melamud
et al., 2015; Hintz and Biemann, 2016; Zhou et al., 2019; Arefyev et al.,
2020) considers the task of replacing a target word in context with
appropriate substitutes. There are two widely-used English benchmarks for this
task: SemEval (McCarthy and Navigli, 2007) and CoInCo (Kremer et al., 2014).
For both benchmarks, data was collected by asking human annotators to think of
substitutes from memory. Because lexical substitution was originally proposed
as a means for evaluating word sense disambiguation systems (McCarthy, 2002),
this data collection strategy was designed to avoid a bias towards any
particular word sense inventory.

In this work, we consider a different use case for lexical substitution:
writing assistance. For this use case, we are interested in evaluating a
system’s ability to produce appropriate substitutes that are likely to be
difficult for humans to think of. We show that the data collection strategy
used in past benchmarks yields low _coverage_ of such uncommon substitutes—for
our previous example, they might contain words like “awesome” and “great,” but
miss words like “incredible” and “fascinating.” Furthermore, we observe that
these benchmarks have low _quality_ , containing words like “fun,” which are
easy to think of, but not quite appropriate in context.

Context |  My favorite thing about her is her straightforward honesty.
---|---
CoInCo |  candid (3), artless (1), blunt (1), complete (1), direct (1), forthright (1), frank (1), outspoken (1), plainspoken (1), truthful (1), unreserved (1)
Thesaurus |  aboveboard, apparent, barefaced, candid, clear, clear-cut, direct, distinct, easy, elementary, evident, forthright, frank, genuine, guileless, honest, honorable, just, laid on the line, level, like it is, manifest, … 32 more
|  sincere (80%), genuine (80%), frank (70%), candid (70%), direct (70%),
forthright (70%), uncomplicated (60%), up front (60%), clear-cut (60%), clear
(60%), plainspoken (60%), complete (50%), straight-arrow (50%), honest (50%),
open (50%), blunt (50%), outspoken (50%), truthful (50%), plain-dealing (40%),
undisguised (40%), unvarnished (40%), unreserved (40%), barefaced (40%),
unequivocal (30%), upright (30%), simple (30%), veracious (30%), unconcealed
(30%), like it is (30%), square-shooting (20%), upstanding (20%), undissembled
(20%), manifest (20%), unambiguous (20%), pretenseless (20%), level (10%),
laid on the line (10%), honorable (10%), guileless (10%), … 20 more with 0%
Table 1:  We consider lexical substitution, the task of finding appropriate
substitutes for a target word in context. In CoInCo (the previous largest
benchmark), humans are asked to think of substitutes from memory and result in
low coverage (the number of annotators who produced each substitute is shown
in parentheses; out of six annotators). On the other hand, looking up the
target word in a thesaurus has higher coverage, but low quality, because it
does not consider the context. In , we combine the best of both worlds and
provide a list of substitutes that has high coverage and high quality, along
with fine-grained scores for each substitute (shown in parentheses).
Substitutes with scores greater than 50% from are bolded.

We present —the Stanford Word Substitution Benchmark—an English lexical
substitution benchmark that raises the bar for both coverage and quality
(Table 1). We collect by asking human annotators to _judge_ whether a given
candidate word is an appropriate substitute for a target word in context,
following the intuition that judging a given substitute is easier than
producing that same substitute from memory. To bootstrap a set of candidates
for humans to annotate, we look up target words in an existing context-free
thesaurus (Kipfer, 2013).111Note that our use of a thesaurus makes less
appropriate for the original use case for lexical substitution: evaluating
word sense disambiguation systems. Because a thesaurus might miss substitutes
that would not typically be synonymous with the target word outside of the
provided context (e.g. “thought-provoking” for “amazing”), we also include
human-proposed candidates from the previous CoInCo benchmark.

Determining whether a substitute is appropriate is intrinsically subjective.
To address this, we collect binary labels from up to ten annotators for each
substitute, inducing a score for each substitute. In CoInCo, analogous scores
are derived from the number of independent annotators who thought of a
substitute—hence, as we will show in Section 4, these scores tend to
correspond more to ease-of-recollection than appropriateness. In contrast,
scores from correspond to appropriateness, and also allow us to explicitly
trade off coverage and quality, permitting more nuanced evaluation. Our
analysis shows that compared to CoInCo, has 4.1x more substitutes per target
word for the same level of quality, and its substitutes are 1.5x more
appropriate based on scores for the same number of substitutes.

We demonstrate that is a challenging benchmark by evaluating state-of-the-art
lexical substitution systems and large-scale, pre-trained language models
including systems based on BERT (Devlin et al., 2019; Zhou et al., 2019) and
GPT-3 (Brown et al., 2020). In our evaluation, we find that humans
substantially outperform all existing systems, suggesting that lexical
substitution can be used as a downstream language understanding task for pre-
trained models. We release publicly as a benchmark for lexical substitution,
coupled with a Python library that includes previous benchmarks in a common
format, standardized evaluation scripts for prescribed metrics, and
reproducible re-implementations of several baselines.222 :
github.com/p-lambda/swords
All experiments reproducible on the CodaLab platform:
worksheets.codalab.org/worksheets/0xc924392d555f4b4fbee47be92e3daa0b

##  2 Background

Benchmark | Contexts | Targets | Substitutes | Labels | Substitutes per target (on average)
---|---|---|---|---|---
|  |  |  |  | Total | Inconceivable | Conceivable | Acceptable
|  |  |  |  |  | (score $=0$%) | (score $>0$%) | (score $>50$%)
SemEval | $2010$ | $201$ | $8025$ | $12300$ | $4.0$ | - | - | -
CoInCo | $2474$ | $15629$ | $112742$ | $167446$ | $7.2$ |  $2.5$* |  $5.2$* |  $2.3$*
| $1132$ | $1132$ | $68683$ | $375855$ | $60.7$ | $39.3$ | $21.4$ | $4.1$
CoInCo (dev) | $1577$ | $10179$ | $67814$ | $98950$ | $6.7$ |  $2.2$* |  $5.2$* |  $2.5$*
(dev) | $370$ | $370$ | $22978$ | $121938$ | $62.1$ | $41.6$ | $20.5$ | $4.2$
CoInCo (test) | $897$ | $5450$ | $44928$ | $68496$ | $8.2$ |  $2.9$* |  $5.7$* |  $2.4$*
(test) | $762$ | $762$ | $45705$ | $253917$ | $60.0$ | $38.1$ | $21.9$ | $4.0$
Table 2: Benchmark statistics for SemEval, CoInCo, and . Our benchmark
contains 4.1x more conceivable substitutes (21.4) and 1.8x more acceptable
substitutes (4.1) on average, compared to the previous largest benchmark
CoInCo. Unlike prior benchmarks, has inconceivable substitutes that received a
score of 0 from appropriateness judgement, which are useful as challenging
distractors for model evaluation. The numbers of inconceivable, conceivable,
and acceptable substitutes for CoInCo (numbers with *) are estimated based on
the subset of CoInCo used to build and therefore received scores.

We describe lexical substitution and briefly introduce two widely-used
benchmarks: SemEval (McCarthy and Navigli, 2007), the first benchmark, and
CoInCo (Kremer et al., 2014), the largest existing benchmark. For a survey of
other benchmarks, we refer readers to Kremer et al. (2014), Hintz and Biemann
(2016), and Miller (2016).

#### Lexical substitution.

Lexical substitution is the task of generating a list of substitutes
$w^{\prime}$ that can replace a given target word $w$ in a given context $c$
(McCarthy, 2002):

$(\text{context}~{}c,\text{target}~{}w)\rightarrow[\text{substitute}~{}w^{\prime}].$

The context $c$ is one or more sentences where the target word $w$ is
situated. The target word $w$ is one word in the context, which is either
manually chosen by humans (McCarthy and Navigli, 2007) or automatically
selected based on the part-of-speech of the target word (Kremer et al., 2014).
The substitute $w^{\prime}$ can be a word or phrase. Note that the task of
lexical substitution does not consider inflection and does not involve grammar
correction; all benchmarks contain lemmas as substitutes (e.g. “run” instead
of “ran”).

####  SemEval.

The first lexical substitution benchmark, SemEval-2007 Task 10 (McCarthy and
Navigli, 2007), contains $201$ manually chosen target words. For each target
word, $10$ sentences were chosen as contexts (mostly at random, but in part by
hand) from the English Internet Corpus (Sharoff, 2006) and presented to five
human annotators. The five annotators were instructed to produce up to three
substitutes from memory as a replacement for the target word in context that
“preserves the meaning of the original word.” This resulted in $12300$ labels
in total with four substitutes per target word on average.

####  CoInCo.

The previous largest lexical substitution benchmark, CoInCo (Kremer et al.,
2014), was constructed by first choosing $2474$ contexts from the Manually
Annotated Sub-Corpus (Ide et al., 2008, 2010). Then, all content words (nouns,
verbs, adjective, and adverbs) in the sentences were selected to be target
words. Each target word was presented to six human annotators, who were asked
to provide up to five substitutions or mark it as unsubstitutable. All the
annotators were instructed to provide (preferably single-word) substitutes for
the target that “would not change the meaning.” This resulted in $167446$
labels in total and $7.2$ substitutions per target word on average.333The
reported number in Kremer et al. (2014) is $167336$ and $10.71$, respectively.
The latter differs as they counted the same substitute multiple times when
suggested by multiple annotators, whereas we report the number of unique
substitutes. We also find that scores under CoInCo (i.e. the number of
annotators who provided a substitute) could be inflated, as at least $375$
substitutes have scores greater than six (up to $21$). For the rest of the
paper, we focus on CoInCo (but not SemEval) as our benchmark is built on
CoInCo and it is the largest existing benchmark.

##  3 Our benchmark

is composed of context, target word, and substitute triples
($c,w,w^{\prime}$), each of which has a score that indicates the
appropriateness of the substitute. We consider a substitute to be acceptable
if its score is greater than 50% (e.g. bolded words in Table 1) and
unacceptable if the score is less than or equal to 50%. Similarly, a
substitute with a score greater than 0% is considered conceivable, and
otherwise inconceivable. Note that these terms are operational definitions for
convenience, and different thresholds can be chosen for desired applications.

###  3.1 Addressing limitations of past work

#### Improving quality.

In prior work, annotators were prompted to consider whether a substitute
“preserves the meaning” (McCarthy and Navigli, 2007) or “would not change the
meaning” (Kremer et al., 2014) of the target word. Instead, we ask annotators
whether they “would actually consider using this substitute as the author of
the original sentence.” We believe this wording encourages a higher standard.
In Section 4.1, we provide evidence that substitutes from have higher quality
than those from CoInCo on average.

#### Improving coverage.

For prior benchmarks, annotators were asked to generate a list of substitutes
from memory. Psycholinguistic studies have shown that when humans are asked to
predict the next word of a sentence, they deviate systematically from the true
corpus probabilities (Smith and Levy, 2011; Eisape et al., 2020). Thus, we may
reasonably expect that asking humans to generate substitutes would similarly
lead to systematic omissions of some appropriate substitutes.

We observe that prior benchmarks exclude many appropriate substitutes that are
difficult for humans to think of (Section 4.2). To address this limitation, we
first obtain a set of candidate substitutes and then ask annotators to judge
whether they would consider using a given candidate to replace the target word
in the context. That is, given a context $c$, target word $w$, and candidate
substitute $w^{\prime}$, we ask humans to judge whether $w^{\prime}$ is a good
replacement for the target word:

$(\text{context}~{}c,\text{target}~{}w,\text{substitute}~{}w\textquoteright)\rightarrow\\{0,1\\},$

where a positive label $1$ corresponds to “I would actually consider using
this substitute as the author of the original sentence,” and a negative label
$0$ as the opposite. As described in Section 3.2, we annotate a large pool of
candidate substitutes to ensure high coverage of all possible substitutes. We
confirm that this increases coverage compared to CoInCo in Section 4.2.

#### Redefining scores to reflect appropriateness.

In past work, each substitute $w^{\prime}$ has an associated score defined as
the number of annotators who produced $w^{\prime}$ given the associated
context $c$ and target word $w$. Instead, we define the score as the fraction
of annotators who judged the $w^{\prime}$ to be an appropriate replacement of
$w$. We argue that the previous definition of score reflects ease-of-
recollection, but not necessarily appropriateness. In Section 4.3, we show
that our definition of score better represents the appropriateness of each
substitute.

###  3.2 Data collection

We collect substitutes and scores for a context and target word pair $(c,w)$
via the following three steps.

#### Step 1: Select contexts, targets, and substitutes.

We use the subset of contexts and target words from CoInCo. Concretely, we
start with the $(c,w)$ pairs in CoInCo and randomly select one $w$ per $c$ to
annotate. Here, the context $c$ consists of three sentences, where the middle
sentence has the target word $w$ (see Section A.1 to see how we handled
duplicate contexts from CoInCo).

Next, we choose a set of candidate substitutes $w^{\prime}$ to annotate for
each $(c,w)$ pair, as framing annotation as binary classification requires
determining the set of candidate substitutes a priori. We use human-generated
substitutes from CoInCo, then add substitutes from an existing context-free
thesaurus, Roget’s Thesaurus (Kipfer (2013); see Section A.2 for details). In
principle, candidate substitutes can be retrieved from any lexical resource or
even sampled from a generative model, which we leave as future work. By
combining candidates from CoInCo and the thesaurus, we increase the coverage
of acceptable substitutes.

#### Step 2: Reduce the pool of substitutes.

Given a list of candidate substitutes from the previous step, we collect three
binary labels on each $(c,w,w^{\prime})$ triple (see Section 3.3 for details).
Then, we pass any substitute with at least one positive label to Step 3 and
further collect fine-grained scores. We show that the probability that an
acceptable substitute gets incorrectly filtered out as an inconceivable
substitute is very low in Section 4.4.

#### Step 3: Collect fine-grained scores.

In the final step, we collect seven more binary labels on the substitutes
which received at least one positive label from Step 2. This yields a total of
$10$ binary labels for the substitutes.

###  3.3 Crowdsourcing

We used Amazon Mechanical Turk (AMT) to crowdsource labels on substitutes.
Each Human Intelligence Task (HIT) contained a target word highlighted in the
context and at most $10$ candidate substitutes for the target word. Each
candidate substitute had three radio buttons for positive, negative, and
abstain. Annotators were asked to choose positive if they would actually
consider using the substitute to replace the target word as the author of the
context, negative if they would not consider using the substitute, and abstain
if they do not know the meaning of the substitute. We treated all abstain
labels ($1.2$% of total labels) as negative labels, thereby making it binary.
The benchmark includes abstain labels to maintain the option for them to be
handled separately (e.g. excluded) in the future. The interface, instructions,
qualification conditions, and filtering criteria used for crowdsourcing can be
found in Appendix B.

Context with target word | Substitute |  CoInCo’s score |  ’s score
---|---|---|---
Listen, man, he’s not there! | kid | 4 | 0%
We might have a lot of work ahead of us. | bit | 2 | 0%
She was heading for a drink and slipped out of the crowd. | look | 2 | 10%
The e-commerce free zone is situated in north Dubai. | district | 1 | 90%
She will have reunions in the next few weeks. | forthcoming | 1 | 60%
It’s very reassuring. | extraordinarily | 0 | 80%
Table 3: Controversial examples of contexts, target words, and substitutes
(lemmas) which have high scores under either CoInCo or , but not the other. We
consider a score to be high if it is greater than 1 for CoInCo (25.3% of
substitutes) and 50% for (24.5% of substitutes). The contexts are simplified
for readability.

##  4 Data analysis

Table 2 shows overall statistics of our benchmark. comprises a total of $1132$
context and target word pairs (418 nouns, 442 verbs, 176 adjectives, 96
adverbs) and $68683$ total substitutes that have been labeled (including both
acceptable and unacceptable substitutes). For brevity, we defer an analysis of
annotator agreement to Section C.1.

###  4.1 High quality

With our notion of acceptability, we first observe that $75.7$% of the
substitutes from CoInCo 444For this analysis, we consider CoInCo’s substitutes
that are used and labeled under . are considered unacceptable, and $28.1$% of
the substitutes are even inconceivable (receiving scores less than $50$% and
$0$% from our human annotators). Table 3 shows examples of substitutes that
received relatively high scores under CoInCo, yet were considered unacceptable
under . With the same size as CoInCo (by taking the subset of our benchmark
with the highest scoring substitutes per target), the average score of the
substitutes is $50.7$% for and $34.4$% for CoInCo, resulting in 1.5x higher
quality. Furthermore, minimizes the potential noise by having fine-grained
scores to account for appropriateness (Section 4.3) as well as explicit
inconceivable substitutes, which is useful for evaluation (Section 5.2).

###  4.2 High coverage

We show that achieves high coverage. Among the conceivable substitutes in ,
13.1% are only in CoInCo (CoInCo-only), 14.4% are common to both CoInCo and
the thesaurus (CoInCo $\cap$ Thesaurus), and 72.5% are only from thesaurus
(Thesaurus-only). Among the acceptable substitutes in , 21.5% are from CoInCo-
only, 36% are from CoInCo $\cap$ Thesaurus, and 42.5% are from Thesaurus-only.
This suggests that a substantial number of substitutes are not present in
CoInCo. Overall, contains 21.4 conceivable and 4.1 acceptable substitutes per
target word on average, increasing those numbers by 4.1x and 1.8x over CoInCo,
respectively.

In addition, we find that substitutes from CoInCo-only are more likely to be
common words whereas substitutes from Thesaurus-only are more likely to be
rare words. We compute the Zipf frequency (Speer et al., 2018) of each
substitute based on the Google $n$-gram corpus (Brants and Franz, 2006) and
threshold conceivable substitutes into three groups: uncommon ($\leq 3.5$),
neutral, common ($>4.5$). We observe that substitutes from CoInCo-only are
more likely to be common words (53.1%) than those from Thesaurus-only (38.6%).
On the other hand, the substitutes from Thesaurus-only tend to be more
uncommon words (28.2%) than those from CoInCo-only (17.6%).

###  4.3 Reflection of appropriateness in scores

We show that scores in better reflect the appropriateness of each substitute
compared to CoInCo both quantitatively and qualitatively. We consider a
CoInCo’s score to be high if it is greater than 1 (25.3% of substitutes) and a
’s score to be high if it is greater than 50% (24.5% of substitutes). We find
that if a substitute has a high score under CoInCo, it is likely to be
acceptable under almost half of the time (47.2%). However, the converse does
not hold: the acceptable substitutes under have high scores under CoInCo only
29.3% of the time. Intuitively, this is because CoInCo’s scores reflect the
ease of producing the substitute from memory, whereas ’s scores reflect the
appropriateness of the substitute. Table 3 shows examples of context, target
word, and substitute triples which received high scores under either CoInCo or
, but did not under the other benchmark.

Figure 1: Score distribution of ’s substitutes with the source of substitutes.
We find that neither CoInCo nor the thesaurus completely dominates
substitutions across scores, indicating the necessity of both human-generated
substitutes as well as substitutes from the thesaurus. Substitutes with score
0% are not shown to make the bars visually distinguishable.6661691 substitutes
from CoInCo-only, 917 from CoInCo $\cap$ Thesaurus, and 41817 from Thesaurus-
only received a score of 0%.

###  4.4 Validation with additional data

We show that the probability of an acceptable substitute falsely filtered out
in Step 2 is very low. To this end, we collected $10$ additional labels on 89
context-target word pairs randomly selected from the test set, without
reducing the pool of substitutes as in Step 2. By comparing the first three
labels to the entire $10$ labels, we find that $33.7$% of substitutes without
any positive labels in Step 2 could have received one or more positive labels
if they were kept in Step 3. However, we find that $99.2$% of these
substitutes were eventually considered unacceptable (judged by $10$ labels),
indicating that the probability of an acceptable substitute incorrectly
filtered out in Step 2 is very low ($0.8$%).

###  4.5 Score distribution

Figure 6 shows the score distribution of substitutes in along with the source
of substitutes: CoInCo-only, CoInCo $\cap$ Thesaurus, or Thesaurus-only.
Across scores, neither CoInCo nor thesaurus completely dominates substitutes,
and the overlap between CoInCo and thesaurus is quite small, thus indicating
the necessity of both human-recalled substitutes as well as substitutes from a
thesaurus. We also find that adds more substitutes for all the scores,
although substitutes from the thesaurus tend to have a lower range of scores
compared to those from CoInCo. Lastly, we observe that substitutes from CoInCo
roughly form a normal distribution, which suggests that even the substitutes
provided by human annotators are controvertible, and that it is important to
account for the intrinsically continuous nature of appropriateness with fine-
grained scores.

##  5 Model evaluation

In this section, we evaluate several methods on . The goals of this evaluation
are three-fold: (1) to prescribe our recommended evaluation practice for , (2)
to measure performance of existing large-scale pre-trained models and state-
of-the-art lexical substitution systems, and (3) to measure human performance
for the purpose of comparing current and future systems.

###  5.1 Evaluation settings

There are two primary evaluation settings in lexical substitution research:
the _generative_ setting (McCarthy and Navigli, 2007) and the _ranking_
setting (Thater et al., 2010). In the generative setting, systems output a
ranked list of substitute candidates. There are no restrictions on the number
of candidates that a system may output. In the ranking setting, systems are
given all substitute candidates from the benchmark (including those marked as
inconceivable) and tasked with ranking them by appropriateness. Here, we
primarily focus on the generative setting and defer our experiments on the
ranking setting to Appendix D.

###  5.2 Evaluation metrics

In a writing assistance context, we envision that lexical substitution systems
would be used to suggest a limited number of substitutes to users (e.g. $10$
substitutes as opposed to $100$). Hence, we consider evaluation metrics that
examine the quality and coverage of the top-ranked substitutes from a system
with respect to the substitutes that humans judged as _acceptable_ (score
$>50$%). Specifically, we compute precision ($P^{k}$) and recall ($R^{k}$) at
$k$777Note that our definition of recall at $k$ is non-standard; the $\min$
compensates for the fact that there are often fewer than $k$ acceptable
substitutes.:

$\displaystyle P^{k}$ $\displaystyle=\frac{\text{\\# acceptable substitutes in
system top-}k}{\text{\\# substitutes in system top-}k}$ $\displaystyle R^{k}$
$\displaystyle=\frac{\text{\\# acceptable substitutes in system
top-}k}{\min(k,\text{\\# acceptable substitutes})}$

Because we care about both quality (precision) and coverage (recall) when
comparing systems, we report $F^{k}$, the harmonic mean of $P^{k}$ and
$R^{k}$. Likewise, we evaluate against the list of substitutes which humans
judged as _conceivable_ (score $>0$%). $P_{c}^{k}$ and $R_{c}^{k}$ constitute
precision and recall of systems against this larger candidate list, and
$F_{c}^{k}$ their harmonic mean. Motivated by past work (McCarthy and Navigli,
2007), we primarily examine performance for $k=10$ and lemmatize system-
generated substitutes before comparison.888Note that some methods use lemmas
of target words (e.g. Thesaurus) and others use original word forms of target
words (e.g. Gpt-3). We provide both forms in the benchmark.

We note that these metrics represent a departure from standard lexical
substitution methodology, established by McCarthy and Navigli (2007). Like
$P^{k}$ and $R^{k}$, the previously-used best and oot metrics are also
measures of precision and recall, but are not designed to take advantage of
inconceivable substitutes as no such explicit negative substitutes existed in
the earlier benchmarks. Nevertheless, we report performance of all systems on
these metrics in Appendix E as reference.

###  5.3 Baselines

We evaluate both state-of-the-art lexical substitution systems and large-scale
pre-trained models as baselines on . We reimplement the BERT-based lexical
substitution system (Bert-LS) from Zhou et al. (2019), which achieves state-
of-the-art results on past benchmarks. As another lexical substitution system,
we examine Wordtune (AI21, 2020), a commercial system which offers lexical
substitution capabilities.999Wordtune is not optimized for lexical
substitution.

We also examine two large-scale pre-trained models adapted to the task of
lexical substitution: Bert (Devlin et al., 2019) and Gpt-3 (Brown et al.,
2020). To generate and rank substitute candidates with Bert, we feed in a
context with a target word either masked (Bert-M) or kept intact (Bert-K), and
output the top $50$ most likely words according to the masked language
modeling head. Because the target word is removed, Bert-M is expected to
perform poorly—its main purpose is to assess the relative importance of the
presence of the target word compared to the context. Note that both of these
strategies for using Bert to generate candidates differ from that of Bert-LS,
which applies dropout to the target word embedding to partially obscure it. To
generate candidates with GPT-3, we formulate lexical substitution as natural
language generation (see Section D.5 for details).

| Lenient | Strict
---|---|---
Model | $F^{10}$ | $F_{c}^{10}$ | $F^{10}$ | $F_{c}^{10}$
Humans* | $48.8$ | $77.9$ | $-$ | $-$
CoInCo | $34.1$ | $63.6$ | $-$ | $-$
Thesaurus† | $25.6$ | $61.6$ | $-$ | $-$
Thesaurus | $12.0$ | $44.9$ | $-$ | $-$
Gpt-3 | 34.6 | $49.0$ | $22.7$ | 36.3
Wordtune† | $34.6$ | $45.4$ | 23.5 | $34.7$
Gpt-3† | $34.4$ | $49.0$ | $22.3$ | $34.7$
Wordtune | $34.3$ | $45.2$ | $22.8$ | $33.6$
Bert-K† | $32.4$ | 55.4 | $19.2$ | $30.3$
Bert-LS | $32.1$ | $54.9$ | $17.2$ | $27.0$
Bert-K | $31.7$ | $54.8$ | $15.7$ | $24.5$
Bert-M | $30.9$ | $48.1$ | $10.7$ | $16.5$
Bert-M† | $30.9$ | $48.3$ | $16.2$ | $25.4$
Table 4:  Evaluation of systems on in the generative setting. Here, systems must both generate and rank a set of substitutes. We observe that the performance of all baselines on all metrics falls short of human performance. For the “lenient” setting, we filter out system generated substitutes which are not in . *Computed on a subset of the test data. †Reranked by our best ranking model (Bert).  Context |  The e-commerce free zone is situated in north Dubai, near the industrial free zone in Hebel Ali
---|---
Substitutes in  |  sector (90%), district (90%), area (90%), region (70%), section (70%), range (60%), strip (60%), ground (50%), segment (50%), territory (50%), sphere (40%), realm (40%), place (30%), tract (30%), city (30%), belt (20%), circuit (20%), band (0%)
Reference for $F^{k}$ ($7$) |  sector, district, area, region, section, range, strip
Reference for $F_{c}^{k}$ ($17$) |  sector, district, area, region, section, range, strip, ground, segment, territory
CoInCo ($9$) |  area, region, district, section, city, place, range, strip, territory
Thesaurus† ($14$) |  district, area, belt, territory, region, realm, sector, section, circuit, segment
Wordtune† ($11$) |  district, area, city, region, site, league, center, system, place, zona
Gpt-3† ($13$) |  district, area, territory, region, realm, sector, locality, section, quarter, precinct
Bert-LS ($50$) |  belt, district, port, area, zones, city, park, center, strip, sector
Bert-K† ($50$) |  zones, district, area, city, belt, region, park, ville, site, sector
Bert-M† ($50$) |  zones, district, area, city, belt, territory, region, haven, park, site
Table 5:  Qualitative comparison of top 10 candidates generated by best
systems. From top to bottom, table sections show (1) a context, target word,
substitutes, and scores from (dev), (2) reference lists used to compute
$F^{k}$ and $F_{c}^{k}$ (applying thresholds of $>50\%$ and $>0\%$ to scores),
(3) substitute candidates from oracle systems (sources of substitutes in ),
and (4) substitute candidates from best systems. For each system, we include
the total number of substitute candidates produced by the system in
parentheses (after removing duplicates). Substitutes with scores greater than
50% from are bolded.

###  5.4 Human and oracle systems

Here we consider human and oracle “systems” to help contextualize the
performance of automatic lexical substitution systems evaluated on . We
evaluate the performance of Humans using labels from a separate pool of
annotators as described in Section 4.4. Because this task is inherently
subjective, this system represents the agreement of two independent sets of
humans on this task, which can be viewed as a realistic upper bound for all
metrics. We consider the substitutes that have score $>0\%$ from the separate
pool of annotators as Humans’s substitutes in the generative setting.

We also consider both of the candidate sources, CoInCo and Thesaurus, as
oracle systems. Each source contains a list of substitutes for every target
word, and therefore can be viewed as a lexical substitution system and
evaluated on . CoInCo provides substitutes for a target word that were
provided by six human annotators. This can be thought of as a proxy for how
humans perform on lexical substitution when recalling words off the top of
their heads (as opposed to making binary judgements as in Humans). Thesaurus
provides context-free substitutes for a target word (regardless of their word
senses) with the default ranking retrieved from the thesaurus. This represents
the context-insensitive ordering that a user of the same thesaurus would
encounter.

Because these oracle systems only produce candidates which are guaranteed to
be in , they have an inherent advantage on the evaluation metrics over other
systems. Hence, to be more equitable to other systems, we additionally compute
$F^{10}$ and $F_{c}^{10}$ in a “lenient” fashion—filtering out model generated
substitutes which are not scored under (we refer to the setup without
filtering as “strict”). It is our intention that future systems should _not_
use CoInCo or Thesaurus in any way, as they leak information about the
benchmark.

###  5.5 Evaluation results

Table 4 shows that the performance of all methods falls short of that of
humans on all metrics. We interpret this as evidence that is a challenging
benchmark, since strong (albeit unsupervised) baselines like Bert and Gpt-3 do
not reach parity with humans. We also observe that two models (Wordtune and
Gpt-3) achieve higher $F^{10}$ than CoInCo. In other words, while all models
perform worse than humans who are judging the appropriateness of substitutes
(Humans), some models appear to slightly outperform humans who are thinking of
substitutes off the top of their head (CoInCo). This implies that some lexical
substitution models may already be helpful to humans for writing assistance,
with room for improvement.

Overall, we find that there is no single system which emerges as the best on
all metrics. We note that, despite Bert-LS representing the state-of-the-art
for past lexical substitution benchmarks, its performance falls short of that
of commercial systems like Gpt-3 and Wordtune on most criteria. Also, the
Bert-based methods output around $5$x as many candidates as the other models
on average, thus having an inherent advantage in recall with the lenient
criteria (see Table 7 in Appendix E).

In Table 4, we additionally report the performance of generative models by re-
ranking their lists of substitutes using the best ranker from our candidate
ranking evaluation, Bert (see Appendix D for details). This procedure
unilaterally improves performance for all systems on all metrics except for
Gpt-3. Hence, we speculate that improved performance on the ranking setting
will be mostly complementary to improved performance on the generative
setting.

From a qualitative perspective, many of the systems we evaluate already
produce helpful substitutes (Table 5). In examining errors, we find that Bert-
based models and Wordtune tend to produce words that differ semantically from
the target (e.g. “league” for zone). Substitutes generated by Gpt-3 are often
repetitive (e.g. for zone, Gpt-3 produced $64$ substitutes, out of which only
$13$ were unique)—we filter out duplicates for evaluation. Finally, we observe
that some systems produce appropriate substitutes which are not present in
(e.g. Gpt-3 produces “precinct” for zone), indicating that has limitations in
coverage. However, the higher coverage and quality in compared to past
benchmarks still improves the reliability of our proposed evaluation.

##  6 Related work

As we discussed previous benchmarks for lexical substitution in Section 2 and
relevant models in Section 5, we use this section to draw connections to other
related literature.

#### Word sense disambiguation.

The task of word sense disambiguation consists of selecting the intended
meaning (i.e. sense) from the pre-defined set of senses for that word in a
sense inventory. The task of lexical substitution is closely related to word
sense disambiguation, as many words are _sense synonyms_ —some of their senses
are synonymous, but others are not (Murphy, 2010). In fact, McCarthy (2002)
proposed lexical substitution as an application-oriented word sense
disambiguation task that avoids some of the drawbacks of standard word sense
disambiguation, such as biases created by the choice of sense inventory
(Kilgarriff, 1997).

#### Near-synonym lexical choice.

Words are often _near-synonyms_ —they can substitute for each other in some
contexts, but not every context (DiMarco et al., 1993; Murphy, 2010). can be
viewed as a collection of human judgments on when certain near-synonyms are
substitutable in a given context. The task of near-synonym lexical choice
consists of selecting the original target word from a set of candidate words
given a context where the target word is masked out (Edmonds and Hirst, 2002).
The candidate words are composed of the target word and its near-synonyms
which are often retrieved from a lexical resource such as Hayakawa (1994). In
this task, systems are tested whether they can reason about near-synonyms and
choose the best substitute that fits in the context, without knowing any
direct semantic information about the target word and without having to
explicitly judge the appropriateness of other candidates.

#### Lexical and phrasal resources.

Lexical resources such as thesauri are often used to identify possible word
substitutes. WordNet (Fellbaum, 1998) is a widely used lexical resource for
English that includes synonymy, antonymy, hypernymy, and other relations
between words. PPDB (Pavlick et al., 2015) includes both word-level and
phrase-level paraphrase rules ranked by paraphrase quality. These resources
relate words and phrases in the absence of context, whereas lexical
substitution requires suggesting appropriate words in context.

#### Paraphrase generation.

Work on sentence-level paraphrase generation considers a wide range of
meaning-preserving sentence transformations, including phrase-level
substitutions and large syntactic changes (Madnani and Dorr, 2010; Wieting and
Gimpel, 2018; Iyyer et al., 2018; Hu et al., 2019). Our work could be extended
to phrases given appropriate methods for identifying target phrases and
proposing candidate substitute phrases. One benefit of focusing on word
substitutions is that we can cover a large fraction of all appropriate
substitutes, and thus estimate recall of generative systems. Some word-level
substitutions, such as function word variation and substitutions that rely on
external knowledge, are also outside the scope of our work but occur in
standard paraphrase datasets (Bhagat and Hovy, 2013).

#### Self-supervised pre-trained models.

The task of suggesting words given surrounding context bears strong
resemblance to masked language modeling, which is commonly used for
pretraining (Devlin et al., 2019). However, for lexical substitution,
appropriate substitutes must not only fit in context but also preserve the
meaning of the target word; thus, additional work is required to make BERT
perform lexical substitution (Zhou et al., 2019; Arefyev et al., 2020).

#### Modeling human disagreement.

In , we find considerable subjectivity between annotators on the
appropriateness of substitutes. For the task of natural language inference,
recent work argues that inherent disagreement between human annotators
captures important uncertainty in human language processing that current NLP
systems model poorly (Pavlick and Kwiatkowski, 2019; Nie et al., 2020). We
hope that the fine-grained scores in encourage the development of systems that
more accurately capture the graded nature of lexical substitution.

## Acknowledgments

We sincerely thank Frieda Rong, Nelson Liu, Stephen Mussmann, Kyle Mahowald,
Daniel Jiang, and all reviewers for their help and feedback throughout this
project. We also thank OpenAI and Wordtune for allowing us to evaluate their
systems. This work was funded by DARPA CwC under ARO prime contract no.
W911NF-15-1-0462.

## References

  * AI21 (2020) AI21. 2020.  Wordtune (accessed 2020 Oct 30).  https://www.wordtune.com/.
  * Arefyev et al. (2020) Nikolay Arefyev, Boris Sheludko, Alexander Podolskiy, and Alexander Panchenko. 2020\.  A comparative study of lexical substitution approaches based on neural language models.
  * Bhagat and Hovy (2013) Rahul Bhagat and Eduard Hovy. 2013.  Squibs: What is a paraphrase? _Computational Linguistics_ , 39(3):463–472.
  * Brants and Franz (2006) Thorsten Brants and Alex Franz. 2006.  Web 1T 5-gram version 1.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020.  Language models are few-shot learners.  In _Advances in Neural Information Processing Systems_ , volume 33, pages 1877–1901. Curran Associates, Inc.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  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: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * DiMarco et al. (1993) Chrysanne DiMarco, Graeme Hirst, and Manfred Stede. 1993.  The semantic and stylistic differentiation of synonyms and near-synonyms.  In _AAAI Spring Symposium on Building Lexicons for Machine Translation_.
  * Edmonds and Hirst (2002) Philip Edmonds and Graeme Hirst. 2002.  Near-synonymy and lexical choice.  _Computational Linguistics_ , 28(2):105–144.
  * Eisape et al. (2020) Tiwalayo Eisape, Noga Zaslavsky, and Roger Levy. 2020.  Cloze distillation: Improving neural language models with human next-word prediction.  In _Proceedings of the 24th Conference on Computational Natural Language Learning_ , pages 609–619, Online. Association for Computational Linguistics.
  * Erk and Padó (2008) Katrin Erk and Sebastian Padó. 2008.  A structured vector space model for word meaning in context.  In _Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing_ , pages 897–906, Honolulu, Hawaii. Association for Computational Linguistics.
  * Fellbaum (1998) Christiane Fellbaum. 1998.  _WordNet: An Electronic Lexical Database_.  MIT Press.
  * Hayakawa (1994) Samuel Ichiye Hayakawa. 1994.  _Choose the Right Word: A Contemporary Guide to Selecting the Precise Word for Every Situation_.  Collins Reference.
  * Hintz and Biemann (2016) Gerold Hintz and Chris Biemann. 2016.  Language transfer learning for supervised lexical substitution.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 118–129, Berlin, Germany. Association for Computational Linguistics.
  * Hu et al. (2019) J. Edward Hu, Rachel Rudinger, Matt Post, and Benjamin Van Durme. 2019.  ParaBank: Monolingual bitext generation and sentential paraphrasing via lexically-constrained neural machine translation.  In _Association for the Advancement of Artificial Intelligence_.
  * Ide et al. (2008) Nancy Ide, Collin Baker, Christiane Fellbaum, Charles Fillmore, and Rebecca Passonneau. 2008.  MASC: the manually annotated sub-corpus of American English.  In _Proceedings of the Sixth International Conference on Language Resources and Evaluation (LREC’08)_ , Marrakech, Morocco. European Language Resources Association (ELRA).
  * Ide et al. (2010) Nancy Ide, Collin Baker, Christiane Fellbaum, and Rebecca Passonneau. 2010.  The manually annotated sub-corpus: A community resource for and by the people.  In _Proceedings of the ACL 2010 Conference Short Papers_ , pages 68–73, Uppsala, Sweden. Association for Computational Linguistics.
  * Iyyer et al. (2018) Mohit Iyyer, John Wieting, Kevin Gimpel, and Luke Zettlemoyer. 2018.  Adversarial example generation with syntactically controlled paraphrase networks.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_ , pages 1875–1885, New Orleans, Louisiana. Association for Computational Linguistics.
  * Kilgarriff (1997) A. Kilgarriff. 1997.  I don’t believe in word senses.  _Computers and the Humanities_.
  * Kipfer (2013) Barbara Ann Kipfer. 2013.  _Roget’s 21st Century Thesaurus, Third Edition_.  Random House Publishing Group.
  * Kishida (2005) Kazuaki Kishida. 2005.  _Property of average precision and its generalization: An examination of evaluation indicator for information retrieval experiments_.  National Institute of Informatics Tokyo, Japan.
  * Kremer et al. (2014) Gerhard Kremer, Katrin Erk, Sebastian Padó, and Stefan Thater. 2014.  What substitutes tell us \- analysis of an “all-words” lexical substitution corpus.  In _Proceedings of the 14th Conference of the European Chapter of the Association for Computational Linguistics_ , pages 540–549, Gothenburg, Sweden. Association for Computational Linguistics.
  * Madnani and Dorr (2010) Nitin Madnani and Bonnie J. Dorr. 2010.  Generating phrasal and sentential paraphrases: A survey of data-driven methods.  _Computational Linguistics_ , 36(3):341–387.
  * McCarthy (2002) Diana McCarthy. 2002.  Lexical substitution as a task for WSD evaluation.  In _Proceedings of the ACL-02 Workshop on Word Sense Disambiguation: Recent Successes and Future Directions_ , pages 089–115. Association for Computational Linguistics.
  * McCarthy and Navigli (2007) Diana McCarthy and Roberto Navigli. 2007.  SemEval-2007 task 10: English lexical substitution task.  In _Proceedings of the Fourth International Workshop on Semantic Evaluations (SemEval-2007)_ , pages 48–53, Prague, Czech Republic. Association for Computational Linguistics.
  * Melamud et al. (2015) Oren Melamud, Ido Dagan, and Jacob Goldberger. 2015.  Modeling word meaning in context with substitute vectors.  In _Proceedings of the 2015 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 472–482, Denver, Colorado. Association for Computational Linguistics.
  * Miller (2016) Tristan Miller. 2016.  _Adjusting Sense Representations for Word Sense Disambiguation and Automatic Pun Interpretation_.  Ph.D. thesis, Technische Universität Darmstadt.
  * Murphy (2010) M. Lynne Murphy. 2010.  _Lexical Meaning_.  Cambridge University Press.
  * Nie et al. (2020) Yixin Nie, Xiang Zhou, and Mohit Bansal. 2020.  What can we learn from collective human opinions on natural language inference data? In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 9131–9143, Online. Association for Computational Linguistics.
  * Pavlick and Kwiatkowski (2019) Ellie Pavlick and Tom Kwiatkowski. 2019.  Inherent disagreements in human textual inferences.  _Transactions of the Association for Computational Linguistics_ , 7:677–694.
  * Pavlick et al. (2015) Ellie Pavlick, Pushpendre Rastogi, Juri Ganitkevitch, Benjamin Van Durme, and Chris Callison-Burch. 2015.  PPDB 2.0: Better paraphrase ranking, fine-grained entailment relations, word embeddings, and style classification.  In _Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 2: Short Papers)_ , pages 425–430, Beijing, China. Association for Computational Linguistics.
  * Pennington et al. (2014) Jeffrey Pennington, Richard Socher, and Christopher Manning. 2014.  GloVe: Global vectors for word representation.  In _Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 1532–1543, Doha, Qatar. Association for Computational Linguistics.
  * Sharoff (2006) S. Sharoff. 2006.  Open-source corpora: Using the net to fish for linguistic data.  _International Journal of Corpus Linguistics_ , 11:435–462.
  * Smith and Levy (2011) Nathaniel Smith and Roger Levy. 2011.  Cloze but no cigar: The complex relationship between cloze, corpus, and subjective probabilities in language processing.  In _Proceedings of the Annual Meeting of the Cognitive Science Society_.
  * Speer et al. (2018) Robyn Speer, Joshua Chin, Andrew Lin, Sara Jewett, and Lance Nathan. 2018.  LuminosoInsight/wordfreq: v2.2.
  * Szarvas et al. (2013) György Szarvas, Róbert Busa-Fekete, and Eyke Hüllermeier. 2013.  Learning to rank lexical substitutions.  In _Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing_ , pages 1926–1932, Seattle, Washington, USA. Association for Computational Linguistics.
  * Thater et al. (2010) Stefan Thater, Hagen Fürstenau, and Manfred Pinkal. 2010.  Contextualizing semantic representations using syntactically enriched vector models.  In _Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics_ , pages 948–957, Uppsala, Sweden. Association for Computational Linguistics.
  * Webber et al. (2010) William Webber, Alistair Moffat, and Justin Zobel. 2010.  A similarity measure for indefinite rankings.  _ACM Transactions on Information Systems_ , 28(4):1–38.
  * Wieting and Gimpel (2018) John Wieting and Kevin Gimpel. 2018.  ParaNMT-50M: Pushing the limits of paraphrastic sentence embeddings with millions of machine translations.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 451–462, Melbourne, Australia. Association for Computational Linguistics.
  * Zhou et al. (2019) Wangchunshu Zhou, Tao Ge, Ke Xu, Furu Wei, and Ming Zhou. 2019.  BERT-based lexical substitution.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 3368–3373, Florence, Italy. Association for Computational Linguistics.

##  Appendix A Data collection

###  A.1 Deduplicating context

uses the same contexts as CoInCo, but with slight modifications to avoid
duplication issues and incomplete contexts found in CoInCo. CoInCo uses a
subset of contexts from the Manually Annotated Sub-Corpus (MASC) (Ide et al.,
2008, 2010), in which some sentences are erroneously repeated multiple times
due to multiple IDs assigned to a single sentence. Consequently, CoInCo
contains duplicate sentences in some contexts, as shown below:

> " –was kindly received," "But an artist who would stay first among his
> fellows can tell when he begins to fail."  "But an artist who would stay
> first among his fellows can tell when he begins to fail."

Furthermore, we found that some parts of the document context are missing in
CoInCo because an ID was not assigned to the parts in MASC (e.g. “he said.” is
missing from the above passage after the word “received”).

To address this issue, we re-extracted full contexts from MASC. Given a
sentence containing a target word in CoInCo, we located the sentence in MASC
and used three non-overlapping adjacent MASC regions as our context. As a
result, our context contains additional text that was erroneously omitted in
CoInCo (including newlines), thereby reducing annotator confusion. The context
of the above example in our benchmark is as follows:

> " –was kindly received,"  he said. "But an artist who would stay first among
> his fellows can tell when he begins to fail."  "Oh?"

###  A.2 Retrieving substitutes from a thesaurus

We use Roget’s Thesaurus (Kipfer, 2013), upon which thesaurus.com is built, as
a primary source of context-free substitutes for target words in . To select
substitutes for a particular target word, we gather substitutes from all word
senses that have the same part of speech as the original target, in order to
disentangle lexical substitution from the task of word sense disambiguation as
well as to include challenging distractors for evaluating models.101010In
CoInCo, contexts, target words, and their part-of-speech tags all come from
the Manually Annotated Sub-Corpus (Ide et al., 2008, 2010) We use the default
ranking retrieved from the thesaurus. When a target word has multiple word
senses, we rank substitutes by simply concatenating the lists of substitutes
for each sense in the order that the senses appear in the thesaurus.

##  Appendix B Crowdsourcing

###  B.1 Instructions and interface

Figure 2: Our instructions ask annotators to accept a substitute if they would
actually consider using the substitute as the author of the context, reject if
not, or abstain if they do not know the definition of the substitutes.
Examples are provided for reference, when annotators click the “click to show
examples” buttons. Figure 3: Our Human Intelligence Task (HIT) contains a
highlighted target word in the context, which consisted of three sentences to
provide sufficient context. For each HIT, we show at most 10 candidate
substitutes for the target word and two control substitutes for filtering.

Figures 2 and 3 show the instructions and interface we used for Amazon
Mechanical Turk (AMT) to crowdsource labels on substitutes. Following the
practice of CoInCo, we showed a highlighted target word in the context, which
consisted of three sentences to provide sufficient context. We instructed
annotators to provide a negative label if the target word is a proper noun or
part of a fixed expression or phrase.

Since our Human Intelligence Task (HIT) concerns acceptability judgement as
opposed to substitute generation, we made the following modifications to the
CoInCo’s setup. First, we asked annotators whether they “would actually
consider using this substitute” rather than whether the substitute “would not
change the meaning” of the target word (Section 3.1). Second, we allowed
annotators to abstain if they do not know the definition of the substitute,
while asking them to return the HIT if they do not know the definition of the
target word or more than three substitutes. Third, we asked annotators to
accept a substitute which is “good but not quite grammatically correct.”
Lastly, we asked annotators to accept the substitute identical to the target
word, in attempt to filtering out spammed HITs (Section B.3).

###  B.2 Setting on Amazon Mechanical Turk

Each HIT contained at most 10 candidate substitutes for a context-target word
pair. When there were more than 10 candidate substitutes, we generated
multiple HITs by partitioning the candidate substitutes into multiple subsets
with potentially different length, using $\mathtt{numpy.array\\_split}$. We
randomized the ordering of substitutes so that each HIT is likely to contain
substitutes from both CoInCo and the thesaurus. The following qualification
conditions were used to allow experienced annotators to participate in our
task:

  * •

HIT Approval Rate (%) for all Requesters’ HITs is greater than 98.

  * •

Location is the United States.

  * •

Number of HITs Approved is greater than 10,000.

Our target hourly wage for annotators was $15. Based on our in-person pilot
study with five native English speakers, we approximated the time per
assignment (labeling at most twelve substitutes) to be 25 seconds. Then, we
assumed that it may take 1-2x longer for crowd workers to complete the
assignments and decided on the compensation of $0.10 to fall into the range of
$7.25 (US federal minimum wage) and $15 per hour, which corresponds to 50
seconds and 24 seconds per assignment, respectively.

It may be surprising that our assignments only take 25 seconds on average,
though there are several reasons why this is the case: (1) In general, making
binary judgements about substitute words takes very little time for native
speakers. (2) Annotators only have to read the target sentence once to provide
judgements for all substitutes in an assignment. (3) Annotators usually do not
need to read the two additional context sentences to make judgements. (4)
Annotators can almost instantly judge two control substitutes (Section B.3),
and are therefore only realistically evaluating at most ten candidates per
assignment.

###  B.3 Filtering spam

In order to filter out work done by spammers, we included two additional
control candidate substitutes in every HIT: the original target word and a
randomly chosen dictionary word. Annotators were instructed to accept the
substitute identical to the target word and were expected to either reject or
abstain on the random word. We used these control substitutes to filter out
spammed HITs. Concretely, we filtered out all the HITs with any wrong label
assigned to the control substitutes as well as HITs completed by annotators
whose overall accuracy on control substitutes across HITs was less than $90$%.
Then, we re-collected labels on these filtered HITs for Step 2 and Step 3.

##  Appendix C Data analysis

###  C.1 Annotator agreement

Figure 4: Annotator agreement between and $k$ additional annotators measured
by rank-biased overlap (RBO) (Webber et al., 2010). The standard deviations
from $100$ simulations are shown as error bars. We observe quite low RBO for
$k<3$ and diminishing returns as $k$ grows. This indicates that there is wide
variation in opinions, and it is necessary to use sufficiently large $k$ to
capture the distribution.

McCarthy and Navigli (2007) introduced two inter-annotator agreement measures,
which assumes that a fixed number of annotators generate a set of substitutes
for every context-target word pair.111111McCarthy and Navigli (2007) had five
annotators from the UK, where each of them annotated the entire dataset.
However, these measures are not designed for the case when there is only one
collective set of substitutes for each context-target word pair, and every
context-target word pair is labeled by various combinations of annotators.

Instead, we compute correlation between the two ranked lists using rank-biased
overlap (RBO) (Webber et al., 2010), which handles non-conjoint lists and
weights high ranks more heavily than low unlike other common rank similarity
measures such as Kendall’s $\tau$ and Spearman’s $\rho$. With additionally
collected 10 labels (Section 4.4), we computed RBO by comparing the ranked
list of substitutes derived from the data to that of and simulate the effect
of having $k$ annotators by sampling $k$ labels per substitute without
replacement a total of $100$ times.

Figure 4 shows the correlation between and $k$ additional human annotators. We
observe quite low RBO for $k<3$ and diminishing returns as $k$ grows. Based on
this observation, we argue that there is wide variation in opinions and it is
necessary to use sufficiently large $k$ to capture the distribution.

##  Appendix D Model evaluation

###  D.1 Ranking setting

Model | GAP
---|---
Humans* | $66.2$
Bert | 56.9
Bert-LS | $53.4$
Bert-LS w/o $s_{p}$ | $52.9$
Bert-LS w/o $s_{v}$ | $51.7$
GloVe | $49.7$
Random | $32.7$
Table 6: Evaluation of models on in the ranking setting. Here, systems provide
a score for every candidate in the benchmark. *Computed on a subset of the
test data.

As opposed to the generative setting where systems must generate and rank
substitute candidates, in the (easier) ranking setting, systems are given all
substitute candidates from the benchmark (including those marked as
inconceivable) and tasked with ranking them by their appropriateness.

###  D.2 Evaluation metrics

To evaluate ranking models, we adopt standard practice and report generalized
average precision (GAP) (Kishida, 2005). GAP is similar to mean average
precision, but assigns more credit for systems which produce substitutes that
have higher scores in the reference list. Considering that our data collection
procedure results in reference scores which correspond more to substitute
appropriateness than ease-of-recollection, GAP is aligned with our high-level
goals.

###  D.3 Baselines

We evaluate contextual embeddings from Bert and word embeddings from GloVe
(Pennington et al., 2014), using cosine similarity of the target and
substitute embeddings as the score. To compute the contextual embedding of a
target or substitute with Bert, we mean pool contextual embeddings of its
constituent word pieces. Because GloVe discards contextual information, we
expect it to perform worse than Bert, and is mainly used to assist
interpretation of GAP scores. In the ranking setting, we are unable to
evaluate Gpt-3 and Wordtune, as we interface with these systems via an API
which provides limited access to the underlying models. We report GAP scores
in Table 6.

###  D.4 Results

We posit that contextual word embedding models should be invariant to
contextual synonymy—they should embed acceptable substitutes nearby to one
another. Hence, the ranking setting may offer a useful perspective for
evaluating this aspect of such models. In the ranking setting, our best
contextual embedding model (Bert) achieves a GAP score of $56.9$. While Bert
outperforms a simple context-free baseline (GloVe), it falls short of the
$66.2$ GAP score achieved by Humans. We interpret this as evidence that
contextual embedding models have room to improve before attaining the
aforementioned invariance.

###  D.5 Lexical substitution as natural language generation

GPT-3 is a language model which generates text in a left-to-right order, and
is not designed specifically for the task of lexical substitution. To use
GPT-3 to perform lexical substitution, we formulate the task in terms of
natural language generation, and use in-context learning as described in
(Brown et al., 2020). Specifically, we draw examples at random from the
development set to construct triplets of text consisting of (context with
target word indicated using asterisks, natural language query, comma-separated
list of all substitutes with score $>0$% in descending score order) as
follows:

> Phone calls were monitored. An undercover force of Manhattan Project
> security agents **infiltrated** the base and bars in the little town of
> Wendover (population 103) to spy on airmen. Karnes knew the 509th was
> preparing for a special bombing mission, but he had no idea what kind of
> bombs were involved.
>
> Q: What are appropriate substitutes for **infiltrated** in the above text?
>
> A: penetrate, swarm, break into, infest, overtake, encompass, raid, breach

We construct as many of these priming triplets as as can fit in GPT-3’s
$2048$-token context (roughly $12$ examples on average), leaving enough room
for a test example formatted the same way except without the list of answers.
Then, we query the 175B-parameter $\mathtt{davinci}$ configuration of GPT-3 to
generate a text continuation with up to $128$ tokens. Finally, we parse the
generated text from GPT-3, using its natural language ordering as the ordering
for evaluation.

In an initial pilot study on a random split of our development set, we
selected the sampling hyperparameters for GPT-3 as $\mathtt{temperature}$ $0$,
$\mathtt{presence\\_penalty}$ $0.5$, and $\mathtt{frequency\\_penalty}$ $0$,
among possible candidates of $\\{0,1\\}$ and $\\{0,0.5,1.0\\}$, and
$\\{0,0.5,1.0\\}$, respectively. We used a grid search ($18$ runs) to select
values based on highest $F_{c}^{10}$.

##  Appendix E Additional evaluation results

We include additional results from our evaluation. In Table 7, we break down
$F^{10}$ from Table 4 into $P^{10}$ and $R^{10}$. In Table 8, we report
performance of all generative baselines on traditional metrics for lexical
substitution.

| Lenient | Strict
---|---|---
Model | $F^{10}$ | $P^{10}$ | $R^{10}$ | $F_{c}^{10}$ | $P_{c}^{10}$ | $R_{c}^{10}$ | $F^{10}$ | $P^{10}$ | $R^{10}$ | $F_{c}^{10}$ | $P_{c}^{10}$ | $R_{c}^{10}$
Humans* | $48.8$ | $43.9$ | $54.8$ | $77.9$ | $76.7$ | $79.1$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$
CoInCo | $34.1$ | $24.3$ | $57.0$ | $63.6$ | $71.5$ | $57.3$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$
Thesaurus† | $25.6$ | $17.0$ | $51.8$ | $61.6$ | $60.4$ | $62.8$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$
Thesaurus | $12.0$ | $8.0$ | $24.2$ | $44.9$ | $44.1$ | $45.8$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$
Gpt-3 | 34.6 | $29.8$ | $41.4$ | $49.0$ | $76.0$ | $36.1$ | $22.7$ | $15.9$ | 40.0 | 36.3 | $39.2$ | 33.8
Wordtune† | $34.6$ | 31.3 | $38.7$ | $45.4$ | 76.5 | $32.3$ | 23.5 | 17.2 | $37.0$ | $34.7$ | 41.0 | $30.1$
Gpt-3† | $34.4$ | $29.6$ | $41.2$ | $49.0$ | $76.1$ | $36.2$ | $22.3$ | $15.6$ | $39.2$ | $34.7$ | $37.4$ | $32.3$
Wordtune | $34.3$ | $31.0$ | $38.4$ | $45.2$ | $76.2$ | $32.2$ | $22.8$ | $16.7$ | $35.9$ | $33.6$ | $39.7$ | $29.1$
Bert-K† | $32.4$ | $24.4$ | 48.2 | 55.4 | $68.7$ | 46.4 | $19.2$ | $12.7$ | $38.9$ | $30.3$ | $29.6$ | $30.9$
Bert-LS | $32.1$ | $24.2$ | $47.7$ | $54.9$ | $68.2$ | $45.9$ | $17.2$ | $11.4$ | $34.9$ | $27.0$ | $26.4$ | $27.6$
Bert-K | $31.7$ | $23.8$ | $47.2$ | $54.8$ | $67.9$ | $45.9$ | $15.7$ | $10.4$ | $31.8$ | $24.5$ | $24.0$ | $25.0$
Bert-M | $30.9$ | $25.6$ | $39.0$ | $48.1$ | $70.3$ | $36.6$ | $10.7$ | $7.1$ | $21.8$ | $16.5$ | $16.2$ | $16.9$
Bert-M† | $30.9$ | $25.6$ | $39.0$ | $48.3$ | $70.6$ | $36.7$ | $16.2$ | $10.7$ | $32.8$ | $25.4$ | $24.8$ | $25.9$
Table 7:  Expansion on the results from Table 4, breaking down F-measures by precision and recall. *Computed on a subset of the test data. †Reranked by our best ranking model (Bert).  Model | Best | Best-M | Oot | Oot-M | $P^{1}$
---|---|---|---|---|---
Oracle | $6.7$ | $96.9$ | $71.5$ | $99.4$ | $100.0$
Humans* | $3.4$ | $29.4$ | $54.0$ | $92.2$ | $87.6$
CoInCo | $5.5$ | $26.3$ | $39.2$ | $67.9$ | $88.2$
Thesaurus† | $2.1$ | $18.8$ | $37.7$ | $52.8$ | $80.4$
Thesaurus | $2.1$ | $7.9$ | $24.1$ | $24.6$ | $63.0$
Gpt-3 | $2.5$ | 22.4 | 22.8 | $45.5$ | $70.9$
Wordtune† | 2.7 | $20.8$ | $20.2$ | $41.4$ | 73.5
Gpt-3† | $2.5$ | $18.7$ | $21.9$ | $44.3$ | $61.4$
Wordtune | $2.7$ | $15.7$ | $19.6$ | $40.6$ | $61.4$
Bert-K† | $0.7$ | $16.8$ | $22.4$ | 46.4 | $60.0$
Bert-LS | $0.7$ | $17.8$ | $20.0$ | $42.2$ | $54.3$
Bert-K | $0.7$ | $15.7$ | $18.3$ | $40.0$ | $48.3$
Bert-M | $0.5$ | $7.9$ | $12.7$ | $25.9$ | $29.3$
Bert-M† | $0.5$ | $18.0$ | $18.6$ | $37.7$ | $58.0$
Table 8: Evaluation of models on SWORD in the generative setting using
traditional evaluation metrics. We also include numbers for an Oracle, as
(unlike for $F^{10}$ and GAP), the oracle does not achieve a score of $100$.
*Computed on a subset of the test data. †Reranked by our best ranking model
(Bert).


# On the clique behavior of graphs of low degree

Rafael Villarroel-Flores
Universidad Autónoma del Estado de Hidalgo
Carretera Pachuca-Tulancingo km. 4.5
Pachuca 42184 Hgo. México
email<EMAIL_ADDRESS>
MSC: 05C76
keywords: iterated clique graphs, convergent graphs
Partially supported by CONACYT, grant A1-S-45528

###### Abstract

To any simple graph $G$, the clique graph operator $K$ associates the graph
$K(G)$ which is the intersection graph of the maximal complete subgraphs of
$G$. The iterated clique graphs are defined by $K^{0}(G)=G$ and
$K^{n}(G)=K(K^{n-1}(G))$ for $n\geq 1$. If there are $m<n$ such that
$K^{m}(G)$ is isomorphic to $K^{n}(G)$ we say that $G$ is convergent,
otherwise, $G$ is divergent. The first example of a divergent graph was shown
by Neumann-Lara in the 1970s, and is the graph of the octahedron. In this
paper, we prove that among the connected graphs with maximum degree 4, the
octahedron is the only one that is divergent.

##  1 Introduction

All graphs in this paper are finite and simple. Following [5], a _clique_ in a
graph $G$ is a maximal and complete subgraph of $G$. The _clique graph_ of
$G$, denoted by $K(G)$, is the intersection graph of its cliques. We define
the sequence of _iterated clique graphs_ by $K^{0}(G)=G$ and
$K^{n}(G)=K(K^{n-1}(G))$ for $n\geq 1$. We say that the graph $G$ is
_convergent_ if the sequence of iterated clique graphs has, up to isomorphism,
a finite number of graphs. This is equivalent to the existence of $m<n$ such
that $K^{m}(G)$ is isomorphic to $K^{n}(G)$ and to the fact that the set of
orders of the iterated clique graphs is bounded. If $G$ is not convergent we
say that $G$ is _divergent_. The graph of the octahedron was the first known
example of a divergent graph, given by Neumann-Lara in [15].

The problem of determining the _behavior_ of $G$ under iterated applications
of the clique operator is one of the main topics in this theory, as the clique
graph operator is considered one of the most complex graph operators ([17]).
There are many families of graphs for which criterions have been proved, and
in some cases the behavior can even be determined in polynomial time (see for
example [7], [8], [11], [9], [10], [13], [14], [6], [4], [1]), however the
problem has been found to be undecidable for automatic graphs ([2]).

We denote the maximum degree in $G$ as $\Delta(G)$. The purpose of this paper
is to show the following:

######  Main Theorem.

If $G$ is a connected graph with $\Delta(G)\leq 4$ and $G$ is not the graph of
the octahedron, then $G$ is convergent.

We use standard notation for graph theory, such as $x\sim y$ whenever the
vertices $x,y$ are adjacent, $N(x)$ for the set of neighbors of the vertex
$x$, $N[x]=N(x)\cup\\{x\\}$, and $|A|$ for the cardinality of the set $A$.
Throughout the paper, we usually identify a subset of the vertex set of a
graph with the subgraph that it induces. When we say that two sets _meet_ , we
mean that they have non-empty intersection. A complete subgraph will be called
just a _complete_. The difference of the sets $A,B$ is denoted as $A-B$.

##  2 Preliminaries

We say that a collection of sets is _intersecting_ if any two members of the
collection has nonempty intersection. The collection has the _Helly property_
if any intersecting subcollection has nonempty intersection. A graph $G$ is
_Helly_ if the collection of the cliques of $G$ has the Helly property.

The following theorem gives a criterion for convergence.

######  Theorem 2.1.

([3]) If a graph $G$ is Helly, then $G$ is convergent.

Not every connected graph with $\Delta(G)\leq 4$ different from the octahedron
is Helly. However, we will prove that for any such graph, one has that
$K^{2}(G)$ is Helly. In order to do that, we will have to study the vertices
of $K^{2}(G)$, that is, the cliques of cliques of $G$. We will pick some
terminology from [10], but for the convenience of the reader, we include all
the relevant definitions here.

Given $x\in G$, we define the _star_ of $x$, denoted by $x^{*}$, as the set of
cliques of $G$ that contain $x$, that is, $x^{*}=\\{q\in K(G)\mid x\in q\\}$.
This is a complete subgraph of $K(G)$. If $x^{*}\in K^{2}(G)$, we say that $x$
is a _normal vertex_. If $Q\in K^{2}(G)$ is such that $\cap Q=\emptyset$, we
say that $Q$ is a _necktie_ of $G$. Thus, vertices of $K^{2}(G)$ are
partitioned in stars and neckties of $G$, and $G$ is Helly precisely when $G$
has no neckties.

A _triangle_ in a graph $G$ is a complete with three vertices. A triangle $T$
in $G$ will be called here an _inner triangle_ if $T$ is a clique of $G$ and
for any of the edges of $T$ there is a triangle $T^{\prime}\neq T$ such that
$T\cap T^{\prime}$ is precisely that edge. Given an inner triangle $T$ in $G$,
we define $Q_{T}=\\{q\in K(G)\mid|q\cap T|\geq 2\\}$. This is always a
complete in $K(G)$. We will prove that if $G$ is a graph with $\Delta(G)\leq
4$, and $G$ is not the octahedron, then $Q_{T}$ is always a necktie, and also
that for any necktie $Q$ there is a triangle $T$ of $G$, such that $Q=Q_{T}$.
In this case, we will say that $T$ is the _center_ of the necktie $Q_{T}$, and
any other element of the necktie that is not the center, will be called an
_ear_.

A graph $G$ is _hereditary Helly_ if all its induced subgraphs are Helly.
Hence any hereditary Helly graph is Helly. The strategy of the proof of the
Main Theorem will be to prove that if $G$ satisfies the hypothesis, then
$K^{2}(G)$ is hereditary Helly. We will use the characterization proved in
[16] as reformulated in [12].

######  Theorem 2.2.

(Theorem 2.1 in [16]) A graph $G$ is hereditary Helly if and only if it is
compatible with the diagram in Figure 1, in the sense that whenever the graph
with the solid edges is a subgraph of $G$, then one of the dashed edges is
induced.

Figure 1: Hajós diagram

##  3 Neckties in low-degree graphs

In what follows, we will call a connected graph $G$ with $\Delta(G)\leq 4$ and
different from the octahedron, a _low degree graph_.

Note that because of the degree condition on $G$, the cliques of $G$ can have
at most five vertices. However, the only connected low degree graph that has a
clique of five vertices is precisely $K_{5}$, which is convergent. Hence, for
our purposes we may assume that all cliques of $G$ have at most four vertices.
Since the graphs that have no neckties are Helly and hence also convergent, we
might as well suppose that $G$ has neckties.

######  Lemma 3.1.

Let $G$ be any graph, and $q_{1},q_{2}$ be cliques in $G$ such that if
$\\{x,y\\}$ is any edge between vertices in $q_{1}\cup q_{2}$, then one of the
vertices $x,y$ is in $q_{1}\cap q_{2}$. Then if $c$ is a complete subgraph
such that $c\subseteq q_{1}\cup q_{2}$, then $c\subseteq q_{1}$ or $c\subseteq
q_{2}$.

###### Proof.

With the given hypothesis, suppose that there is $x\in c$ such that $x\not\in
q_{1}$ and that there is $y\in c$ such that $y\not\in q_{2}$. Then $\\{x,y\\}$
is an edge such that $\\{x,y\\}\cap(q_{1}\cap q_{2})=\emptyset$. ∎

Note that the hypothesis of Lemma 3.1 is satisfied in the case that
$|q_{1}-q_{2}|=1$. Because in that case, if $\\{x\\}=q_{1}-q_{2}$, and there
was an edge from $x$ to the vertex $y\in q_{2}-q_{1}$, then $q_{1}\cup\\{y\\}$
would be a complete subgraph properly containing $q_{1}$.

######  Lemma 3.2.

If $G$ is a graph with $\Delta(G)\leq 4$, then the neckties of $G$ can contain
only triangles.

###### Proof.

Let $Q$ be a necktie in $G$. If $q_{1}\in Q$ was an edge $\\{x,y\\}$, choose
$q_{2}\in Q$ such that $y\not\in q_{2}$ and $q_{3}\in Q$ such that $x\not\in
q_{3}$. Then $q_{1}\cap q_{2}=\\{x\\}$ and $q_{1}\cap q_{3}=\\{y\\}$. Let
$z\in q_{2}\cap q_{3}$. Then $\\{x,y,z\\}$ would be a complete subgraph
properly containing $q_{1}$, which is a contradiction.

Now, suppose $q_{1}\in Q$ is such that $|q_{1}|=4$. If there was
$q^{\prime}\in Q$ such that $|q_{1}\cap q^{\prime}|=1$, then, since by the
previous paragraph, we have $|q^{\prime}|\geq 3$, we would have that if $x\in
q_{1}\cap q^{\prime}$, then $N[x]\supseteq q_{1}\cup q^{\prime}$, and this
last set has at least six elements, against our hypothesis. Suppose now that
there is $q_{2}\in Q$ with $|q_{1}\cap q_{2}|=3$. Then $|q_{2}|=4$. Suppose
that $q_{1}\cap q_{2}=\\{x,y,z\\}$. Then there is $q_{3}\in Q$ such that
$x\not\in q_{3}$. If $q_{3}$ were disjoint to $q_{1}\cap q_{2}$, then
$q_{1}\cup q_{2}$ would be a complete of five vertices. Hence we may assume
$y\in q_{3}$. Then $q_{3}\subseteq N(y)=q_{1}\cup q_{2}$, but by Lemma 3.1
this would imply that either $q_{3}\subseteq q_{1}$ or that $q_{3}\subseteq
q_{2}$, which is a contradiction.

Hence every clique in $Q$ other than $q_{1}$ meets $q_{1}$ in exactly two
elements, and has exactly three elements. Let $q_{2}\in Q$ such that
$q_{2}\neq q_{1}$. If there was $q_{3}\in Q$ such that $q_{3}\cap q_{1}$ is
disjoint to $q_{2}\cap q_{1}$, we would have $q_{1}=(q_{1}\cap
q_{2})\cup(q_{1}\cap q_{3})$, and if $z\in q_{2}\cap q_{3}$, then $z\not\in
q_{1}$, but $q_{1}\cup\\{z\\}$ is a complete subgraph, contradicting our
choice of $q_{1}$. Hence all cliques in $Q$ meet $q_{1}\cap q_{2}$. Suppose
$q_{1}=\\{x,y,u,v\\}$ and $q_{2}=\\{x,y,w\\}$. Let $q_{3}\in Q$ such that
$y\not\in q_{3}$. Then $x\in q_{3}$, and if there was $z^{\prime}\in
q_{3}-(q_{1}\cup q_{2})$, we would have $\\{y,u,v,w,z^{\prime}\\}\subseteq
N(x)$, which is a contradiction. Hence $q_{3}\subseteq q_{1}\cup q_{2}$. By
Lemma 3.1, we would have that $q_{3}\subseteq q_{1}$ or $q_{3}\subseteq
q_{2}$, which is also a contradiction. ∎

######  Lemma 3.3.

If $G$ is a low-degree graph, for any necktie $Q$ in $G$ there is an inner
triangle $T$ of $G$ such that $Q=Q_{T}$, moreover $Q_{T}$ has exactly three
ears. Conversely, if $T$ is an inner triangle, then $Q_{T}$ is indeed a
necktie.

###### Proof.

We adapt the proof of Proposition 10 in [10] to this situation. For $G$ a low-
degree graph, let $Q$ be a necktie of $G$. From Lemma 3.2, we know that $Q$
contains only triangles. Let $T\in Q$. We claim that there must be a triangle
in $Q$ that meets $T$ in only one vertex. Suppose every other triangle in $Q$
meets $T$ at an edge. Let $T_{1}\in Q$, with $T_{1}\neq T$ and suppose
$T=\\{a,b,c\\}$ and $T_{1}=\\{a,b,c^{\prime}\\}$. Now, there must be $T_{2}\in
Q$ such that $b\not\in T_{2}$. But then $T_{2}\cap T=\\{a,c\\}$ and $T_{2}\cap
T_{1}=\\{a,c^{\prime}\\}$, which implies $T_{2}\subseteq T\cup T_{1}$. By
Lemma 3.1, this is not possible.

Let then $T=\\{a,b,c\\}\in Q$, and $T_{1}=\\{a,b^{\prime},c^{\prime}\\}$ with
$T\cap T_{1}=\\{a\\}$. Choose $T_{2}\in Q$ such that $a\not\in T_{2}$. Then
$T_{2}\cap T$ must consist of exactly one vertex, since if $T_{2}\cap
T=\\{b,c\\}$, then $T$ would be properly contained in a complete graph of four
vertices. Similarly, $T_{2}\cap T_{1}$ consists of only one vertex. Without
loss, assume that $T_{2}=\\{a^{\prime},b,c^{\prime}\\}$, with
$a^{\prime}\not\in T\cup T_{1}$. Then $T_{3}=\\{a,b,c^{\prime}\\}$ is a
triangle of $G$. It must be a clique of $G$ because if, for example, was
contained properly in $\\{a,b,c^{\prime},z\\}$, we would have that
$\\{b,b^{\prime},c,c^{\prime},z\\}\subseteq N(a)$, or if, say, we had $z=c$,
then $T$ would be contained in a tetrahedron. Hence $T_{3}$ is an inner
triangle.

We claim that $T_{3}\in Q$. If this were not so, there should be $T_{4}\in Q$
such that $T_{4}\cap T_{3}=\emptyset$, but that meets $T$, $T_{1}$ and
$T_{2}$. We must have then that $T_{4}\cap T=\\{c\\}$, $T_{4}\cap
T_{1}=\\{b^{\prime}\\}$ and $T_{4}\cap T_{2}=\\{a^{\prime}\\}$. This implies
that $T_{4}=\\{a^{\prime},b^{\prime},c\\}$, and that the subgraph of $G$
induced by $\\{a,a^{\prime},b,b^{\prime},c,c^{\prime}\\}$ is an octahedron.
This contradicts our assumption on $G$, and so this proves our claim that
$T_{3}\in Q$.

We have now that $\\{T,T_{1},T_{2},T_{3}\\}\subseteq Q$. Suppose there was a
triangle $T_{4}$ of $G$, with $T_{4}\in Q$, and different from
$T,T_{1},T_{2},T_{3}$. We must have $T_{4}\cap T_{3}\neq\emptyset$, without
loss, assume that $a\in T_{4}\cap T_{3}$. Suppose that $T_{4}=\\{a,r,s\\}$.
But then $T_{4}\subseteq N[a]=\\{a,b,c,b^{\prime},c^{\prime}\\}$. It is
immediate to verify that any choice of $r,s$ among $b,c,b^{\prime},c^{\prime}$
leads to contradict either that $T_{4}$ is different from all of
$T,T_{1},T_{2},T_{3}$, that each of these are cliques, or that $T_{4}\cap
T_{2}\neq\emptyset$. Hence $Q=\\{T,T_{1},T_{2},T_{3}\\}=Q_{T_{3}}$, where
$T,T_{1},T_{2}$ are the ears of $Q_{T_{3}}$.

Now, for the converse, let $T=\\{a,b,c\\}$ be an inner triangle. Each of the
cliques in $Q_{T}$ contains at least two vertices of $T$, so $Q_{T}$ is a
complete in $K(G)$. Suppose that $T_{1}$ and $T_{2}$ are triangles in $G$ such
that $T_{1}\cap T=\\{a,b\\}$ and that $T_{2}\cap T=\\{a,c\\}$. If we had $x\in
T_{1}\cap T_{2}$ with $x\not\in T$, then $T\cup\\{x\\}$ would be a complete of
$G$ that properly contains $T$. This implies that there are at least three
different cliques $q_{1},q_{2},q_{3}$ of $G$ in $Q_{T}$, one corresponding to
each edge of $T$. Suppose that $q_{1}\cap T=\\{a,b\\}$, and that $|q_{1}|=4$.
Then $|N(a)|$ would have five vertices. The same would happen if there was a
$q^{\prime}\in Q_{T}$ with $q^{\prime}\neq q_{1}$ and $q^{\prime}\cap
T=\\{a,b\\}$. This proves that $q_{1},q_{2},q_{3}$ are triangles, and that
$Q_{T}=\\{T,q_{1},q_{2},q_{3}\\}$. If $Q_{T}$ were not a necktie, there would
be a clique $q_{4}$ in $G$ that meets $q_{1},q_{2},q_{3}$ but not $T$. By
considering the degrees of vertices in $q_{4}\cap q_{1}$, $q_{4}\cap q_{2}$
and $q_{4}\cap q_{3}$, we get that $q_{4}$ would have to be a triangle. But
then, in that case, $G$ would be an octahedron. It follows that $Q_{T}$ is a
necktie. ∎

##  4 Forbidden subgraphs

We will apply Theorem 2.2 to $K^{2}(G)$, but we will first state a series of
lemmas to help with the several cases that will arise. We start by extracting
some facts from [10].

######  Lemma 4.1.

([10]) For any graph $G$:

  1. 1.

Two stars $x^{*}$ and $y*$ are adjacent in $K^{2}(G)$ if and only if $x\sim y$
in $G$.

  2. 2.

A star $x^{*}$ and a necktie $Q_{T}$ centered at the triangle $T$ are adjacent
in $K^{2}(G)$ if and only if $x$ is adjacent to two vertices of $T$.

  3. 3.

Two neckties $Q_{T}$, $Q_{T^{\prime}}$ are adjacent in $K^{2}(G)$ if and only
if:

     * •

$|T\cap T^{\prime}|=2$, or

     * •

$|T\cap T^{\prime}|=1$ and if $v\in T\cap T^{\prime}$, there is an edge
(called a _crossbar_) joining a vertex in $T-v$ to a vertex in $T^{\prime}-v$.

######  Lemma 4.2.

Let $G$ be a low-degree graph. If $T$ and $T^{\prime}$ are triangles in $G$,
where $T\cap T^{\prime}=\\{x\\}$ and $T$ is an inner triangle, then $N(x)$
induces a 4-cycle. Moreover, if $T^{\prime}$ is also inner, then none of the
ears of $Q_{T}$ is an inner triangle, and none of the vertices of $T$ besides
$x$ is a normal vertex.

###### Proof.

Suppose that $T=\\{x,e,f\\}$ and $T^{\prime}=\\{x,g,h\\}$. Since the triangle
$T$ is inner, considering the edge $\\{x,e\\}$ there must be $y\in G$ and a
triangle $T_{1}=\\{x,e,y\\}\neq T$. We have that $y\in N(x)=\\{e,f,g,h\\}$.
Since $y\neq e$ because $|T_{1}|=3$ and $y\neq f$ because $T_{1}\neq T$, we
must have that $y=g$ or $y=h$. Without loss, assume $y=g$, hence $e\sim g$.
Now, considering analogously the edge $\\{x,f\\}$, and given that $T$ is a
clique of $G$, we must have $f\sim h$. Since $T$ is a clique, we have that $e$
is not adjacent to $h$, and also that $f$ is not adjacent to $g$. Hence $N(x)$
induces a $4$-cycle. Given that the degree of $x$ is $4$, we must have that
$T^{\prime}$ is a clique. Since $T$ is inner, then there is a vertex $u$ such
that the triangle $\\{u,e,f\\}$ is different from $T$. Besides,
$u\not\in\\{g,h\\}$ because $T$ is a clique.

In the case that $T^{\prime}$ is inner, then analogously there is a vertex
$u^{\prime}$ such that $\\{u^{\prime},g,h\\}$ is different from $T^{\prime}$.
We have that $u\neq u^{\prime}$, otherwise, $G$ would be $4$-regular and an
octahedron. Let us consider the triangle $T_{1}=\\{e,g,x\\}$, which is an ear
in $Q_{T}$. If $T_{1}$ were inner, there would be a vertex $y$ such that
$\\{e,g,y\\}$ is a triangle different from $T_{1}$. But $y\in N(e)\cap
N(g)=\\{x\\}$, which is not possible. Hence $T_{1}$ is not inner, and by
symmetry, $\\{f,h,x\\}$ is not inner either. Now, consider
$T_{2}=\\{e,f,u\\}$, and suppose there is a vertex $z$ such that $\\{e,u,z\\}$
is a triangle different from $T_{2}$. Then $z\in N(e)=\\{u,f,x,g\\}$. None of
these is possible by our assumptions. Hence $T_{2}$ is not inner. Finally,
neither $e^{*}$ nor $f^{*}$ are cliques, since they are properly contained in
$Q_{T}$. ∎

As a corollary to the two previous lemmas, we have that if $T_{1}$ and $T_{2}$
are internal triangles where $T_{1}\cap T_{2}\neq\emptyset$, then
$Q_{T_{1}}\sim Q_{T_{2}}$ in $K^{2}(G)$. Because if $|T_{1}\cap T_{2}|=1$,
then there are (two) crossbars from $T_{1}$ to $T_{2}$. The situation in this
case is pictured in Figure 2.

$x$$u^{\prime}$$u$$g$$e$$f$$h$$T_{2}$$T_{1}$ Figure 2: Case $|T_{1}\cap
T_{2}|=1$

######  Lemma 4.3.

Let $G$ be a low-degree graph, and let $T,T^{\prime}$ be internal triangles
such that $T\cap T^{\prime}=\\{x,y\\}$. Then $N(x)$ induces a $4$-cycle, the
only ear of $Q_{T}$ that is an inner triangle is $T^{\prime}$, and the only
normal vertices of $T$ are $x,y$.

###### Proof.

Suppose that $T=\\{x,y,u\\}$, and $T^{\prime}=\\{x,y,u^{\prime}\\}$.
Considering the edge $\\{x,u\\}$ of the inner triangle $T$, let $x^{\prime}\in
G$ such that $T_{1}=\\{x,u,x^{\prime}\\}\neq T$. Since $T$ is a clique, we
must have $x^{\prime}\neq u^{\prime}$. Applying the Lemma 4.2 to the inner
triangle $T^{\prime}$ and $T_{1}$, we obtain that $N(x)$ is a $4$-cycle, hence
$x^{\prime}\sim u^{\prime}$. Applying the previous steps to the edge
$\\{y,u\\}$ of the triangle $T$, we obtain a vertex $y^{\prime}\in G$ that is
a neighbor of $u,y,u^{\prime}$ so that $N(y)$ is a $4$-cycle. Since $T$ is a
clique, we have $y^{\prime}\neq x^{\prime}$. Now, the triangle $T_{1}$ is an
ear of $Q_{T}$. If $T_{1}$ were inner, there would be a vertex $z$ such that
$\\{z,u,x^{\prime}\\}$ is a triangle different from $T_{1}$. The vertex $z$ is
different from $y^{\prime}$ since $G$ is not an octahedron. Moreover $z\in
N(u)=\\{x,x^{\prime},y,y^{\prime}\\}$, but this contradicts our other
assumptions. Hence $T_{1}$ is not inner. Now, $u$ is not a normal vertex since
$u^{*}$ is contained properly in $Q_{T}$. ∎

The situation of the previous lemma is shown in Figure 3.

$x$$y$$y^{\prime}$$x^{\prime}$$u$$u^{\prime}$$T_{1}$$T_{2}$ Figure 3: Case
$|T_{1}\cap T_{2}|=2$

######  Lemma 4.4.

If $G$ is a low-degree graph, there is no path (induced or not) in $K^{2}(G)$,
that consists of three neckties.

###### Proof.

Let $T_{1}$, $T_{2}$ and $T_{3}$ be three inner triangles in $G$ such that
$Q_{T_{1}}\sim Q_{T_{2}}\sim Q_{T_{3}}$ in $K^{2}(G)$. From $Q_{T_{1}}\sim
Q_{T_{2}}$, we have one of the two situations shown in either Figure 2 or
Figure 3. But in none of those cases it is possible to have an inner triangle
$T_{3}$, different from $T_{1}$, and satisfying $T_{3}\cap
T_{2}\neq\emptyset$. ∎

######  Lemma 4.5.

Let $G$ be a low-degree graph, where $a,b\in G$ are normal vertices and
$T_{1},T_{2}$ are inner triangles. Then $a^{*},b^{*},Q_{T_{1}},Q_{T_{2}}$ do
not induce a diamond in $K^{2}(G)$ of one of the forms shown in Figure 4.

$Q_{T_{2}}$$Q_{T_{1}}$$a^{*}$$b^{*}$$Q_{T_{2}}$$a^{*}$$Q_{T_{1}}$$b^{*}$
Figure 4: Forbidden diamonds

###### Proof.

Consider the case to the left in Figure 4. Since $Q_{T_{1}}\sim Q_{T_{2}}$, we
have $|T_{1}\cap T_{2}|\neq\emptyset$. If $|T_{1}\cap T_{2}|=1$, we have the
situation of Figure 2. Since $b^{*}$ is a neighbor of both $Q_{T_{1}}$ and
$Q_{T_{2}}$, and $b$ is a normal vertex, we have that $b\in T_{1}\cap T_{2}$.
It is immediate to verify that no neighbor of $b$ is a normal vertex. Now, if
$|T_{1}\cap T_{2}|=2$, then again our assumptions on $b$ imply that $b\in
T_{1}\cap T_{2}$, and all neighbors $x$ of $b$ that are normal vertices are
such that $x^{*}$ is a neighbor of both $Q_{T_{1}}$ and $Q_{T_{2}}$.

Now, with respect to the case on the right, since $Q_{T_{1}}$ is not adjacent
to $Q_{T_{2}}$ in $K^{2}(G)$, then $T_{1}\cap T_{2}=\emptyset$. Since $b$ must
be a neighbor to two vertices in $T_{1}$, to two vertices in $T_{2}$ and to
the vertex $a$, and the degree of $b$ is at most four, we have that $a\in
T_{1}\cup T_{2}$. Without loss, assume $a\in T_{1}$. By a similar argument, we
must have $b\in T_{2}$. Let $T_{1}=\\{a,u,v\\}$ and $T_{2}=\\{b,w,r\\}$. Since
$a$ is a neighbor to two vertices in $T_{2}$, without loss we may assume that
$a\sim w$. Applying Lemma 4.2 to the inner triangle $T_{1}$ and the triangle
$T=\\{a,b,w\\}$, we have that $N(a)$ is a $4$-cycle, and without loss, we may
assume $u\sim b$ and $v\sim w$. Similarly, applying the same lemma to $T_{2}$
and the triangle $T^{\prime}=\\{a,b,u\\}$ we have that $u\sim r$. But then $T$
and $T^{\prime}$ are inner triangles, and Lemma 4.3 applies. We have that $T$
is the only ear in $Q_{T^{\prime}}$ that is an inner triangle, which
contradicts that $T_{1}$ is inner. ∎

######  Lemma 4.6.

Let $G$ be a low-degree graph, and let $a,b,x,z\in G$ be normal vertices and
$T$ an inner triangle in $G$ forming the subgraph with the solid edges in
Figure 5. Then one of the dashed edges has to be present.

$b^{*}$$x^{*}$$Q_{T}$$a^{*}$$z^{*}$ Figure 5: Forbidden subgraph

###### Proof.

Suppose there is a subgraph with the solid edges of the form in Figure 5, but
without the dashed edges. Then in $G$ we have that $\\{a,x.z\\}\subseteq
N(b)$. Since $b^{*}\sim Q_{T}$ in $K^{2}(G)$, we have that two neighbors of
$b$ are in $T$, and so, at least one of $\\{a,x,z\\}$ is an element of $T$.
But since $z\not\sim Q_{T}$, we have that $z\not\in T$, and it is not possible
for $a,b$ to be both elements of $T$.

Suppose first that $a\in T$ (and so, $b\not\in T$). Let us write
$T=\\{a,u,v\\}$. Now, $b$ is a neighbor of two elements of $T$, let us say
without loss that $b\sim v$. Applying Lemma 4.2, we must then have that $z\sim
u$. But this contradicts that $z\not\sim Q_{T}$. Consider then the case that
$a\not\in T$ and $x\in T$. Suppose $T=\\{x,u,v\\}$. If we had that
$b\in\\{u,v\\}$, we could assume without loss that $b=v$. Since $a$ is a
neighbor of two elements of $T$, and $a\not\sim x$ by our hypothesis, then
$a\sim u$. Applying Lemma 4.2 to the inner triangle $T$ and the triangle
$\\{b,a,z\\}$, we obtain that $z\sim x$, which again would mean that $z$ is a
neighbor of two elements of $T$. This shows that $b\not\in\\{u,v\\}$. Then
$a^{*}\sim Q_{T}$ in $K^{2}(G)$ implies that $a\sim u$ and $a\sim v$ in $G$.
We also have $b^{*}\sim Q_{T}$ in $K^{2}(G)$, without loss, assume $b\sim v$.
Then the triangle $\\{a,b,v\\}$ is inner, and we are in the situation of
Figure 4.2, which shows that $x$ is not a normal vertex, contradicting our
hypothesis. ∎

######  Lemma 4.7.

Let $G$ be a low-degree graph, and let $a,b,x,z\in G$ be normal vertices and
$T$ an inner triangle in $G$ forming the subgraph with the solid lines in
Figure 6. Then one of the dashed lines has to be present.

$b^{*}$$x^{*}$$c^{*}$$a^{*}$$Q_{T}$ Figure 6: Forbidden subgraph

###### Proof.

Suppose there is a subgraph with the solid edges of the form in Figure 6, but
without the dashed edges. Then in $G$ we have that the normal vertices
$\\{a,c,b,x\\}$ induce a diamond. Since $b^{*}\sim Q_{T}$ and
$\\{a,c,x\\}\subseteq N(b)$, at least one of $\\{a,c,x\\}$ is in the inner
triangle $T$. But since $c^{*}\not\sim Q_{T}$, we have that $c\not\in T$, and
at most one of $a,b$ is in $T$. Consider first the case where $a\in T$, and
let $T=\\{a,u,v\\}$. Since $c^{*}\not\sim Q_{T}$ we must have
$\\{u,v\\}\cap\\{b,c,x\\}=\emptyset$. Applying Lemma 4.2, to the inner
triangle $T$ and the triangle $\\{a,b,c\\}$, we have that $c$ would have to be
adjacent to either of $u$ or $v$, but this contradicts $c^{*}\not\sim Q_{T}$.
So, let us consider the case $a\not\in T$ and $x\in T$. Then $T=\\{x,u,v\\}$
with $\\{u,v\\}\cap\\{a,b,c\\}=\emptyset$. As before, an application of Lemma
4.2 leads to $c\sim u$, or to $c\sim v$ but this is a contradiction. ∎

##  5 Proof of the Main Theorem

######  Theorem 5.1.

Let $G$ be a low-degree graph. If the graph with the solid edges in Figure 7
appears as a subgraph of $K^{2}(G)$, then there is necessarily at least one of
the dotted edges.

$Q_{1}$$Q_{4}$$Q_{2}$$Q_{3}$$Q_{6}$$Q_{5}$ Figure 7: Forbidden subgraph

###### Proof.

Suppose there is a subgraph with the solid edges of the form in Figure 7, but
without the dashed edges. We consider several cases:

  1. 1.

Suppose first that $Q_{1},Q_{2},Q_{3}$ are stars, and set $Q_{i}=a_{i}^{*}$
for $i=1,2,3$. As a subcase, consider when $Q_{4},Q_{5},Q_{6}$ are also stars.
Then there is a subgraph of $G$ isomorphic to the one in Figure 7, whose
vertices are normal vertices. However, then the triangle
$T=\\{a_{1},a_{2},a_{3}\\}$ is inner, and $a_{1}^{*}$ is contained properly in
$Q_{T}$, contradicting that $a_{1}$ is a normal vertex. Hence, this subcase is
not possible. Now, consider the subcase when one of $Q_{4},Q_{5},Q_{6}$ is a
necktie. Without loss, suppose that $Q_{4}$ is a necktie. By Lemma 4.7,
neither $Q_{5}$ nor $Q_{6}$ are stars. Pick then inner triangles
$T_{1},T_{2},T_{3}$ such that $Q_{4}=Q_{T_{3}}$, $Q_{5}=Q_{T_{1}}$ and
$Q_{6}=Q_{T_{2}}$. We claim that one of $T_{1}\cap T_{2}$, $T_{2}\cap T_{3}$,
$T_{1}\cap T_{3}$ must be non-empty. Suppose that $T_{1}\cap T_{3}=\emptyset$
and $T_{2}\cap T_{3}=\emptyset$. Since $a_{1}$ is a neighbor of two vertices
of $T_{2}$ and of two vertices of $T_{3}$, and of $a_{2}$ and of $a_{3}$, we
must have that $a_{2}\in T_{3}$ and $a_{3}\in T_{2}$. Similarly, considering
the neighbors of $a_{2}$, we get that $a_{1}\in T_{3}$ and $a_{3}\in T_{1}$.
This means that $T_{1}\cap T_{2}\neq\emptyset$. This proves our claim, so
without loss, assume that $T_{1}\cap T_{2}\neq\emptyset$. If $|T_{1}\cap
T_{2}|=1$, we are in the situation of Figure 2. In this case, one can verify
that the only normal vertex such that its star is a neighbor in $K^{2}(G)$ of
both $Q_{T_{1}}$ and $Q_{T_{2}}$ is the vertex in $T_{1}\cap T_{2}$, then
$T_{1}\cap T_{2}=\\{a_{3}\\}$. But then none of the neighbors of $a_{3}$ is a
normal vertex. So we are left with the possibility that $|T_{1}\cap T_{2}|=2$,
that is, the situation of Figure 3. But we obtain that this subcase is not
possible either, since, given that $a_{3}$ is a normal vertex with
$a_{3}^{*}\sim Q_{T_{1}}$ and $a_{3}^{*}\sim Q_{T_{2}}$, it must happen that
$a_{3}\in T_{1}\cap T_{2}$. But then $a_{3}$ cannot have two different
neighbors that are normal vertices.

  2. 2.

Suppose now that $Q_{1}$ is a necktie, and $Q_{2},Q_{3}$ are stars.
Considering the graph to the right of Figure 4, we obtain that $Q_{5}$ must be
a star. Considering the graph to the left of Figure 4, we obtain that $Q_{6}$
must also be a star. But by Lemma 4.6, this is not possible.

  3. 3.

Suppose now that $Q_{1},Q_{2}$ are neckties, and $Q_{3}$ is a star. By Lemma
4.4, $Q_{5}$ cannot be a necktie. But by the graph to the left of Figure 4,
$Q_{5}$ cannot be a star either.

  4. 4.

The case when $Q_{1},Q_{2},Q_{3}$ are all neckties, is also impossible by
Lemma 4.4.

This finishes the proof of the Main Theorem. ∎

######  Corollary 5.2.

If $G$ is a connected, divergent graph, that is different from the octahedron,
then $G$ has a vertex with degree at least five.

## References

  * [1] Markus Baumeister and Anna M. Limbach.  Clique dynamics of locally cyclic graphs with $\delta\geq 6$, 2021.  Preprint at arXiv.
  * [2] C. Cedillo and M. A. Pizaña.  Clique-convergence is undecidable for automatic graphs.  Journal of Graph Theory, 96(3):414–437, 2021.
  * [3] F. Escalante.  Über iterierte Clique-Graphen.  Abh. Math. Sem. Univ. Hamburg, 39:59–68, 1973.
  * [4] M. E. Frías-Armenta, F. Larrión, V. Neumann-Lara, and M. A. Pizaña.  Edge contraction and edge removal on iterated clique graphs.  Discrete Appl. Math., 161(10-11):1427–1439, 2013.
  * [5] Frank Harary.  Graph theory.  Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London, 1969.
  * [6] F. Larrión, C. P. de Mello, A. Morgana, V. Neumann-Lara, and M. A. Pizaña.  The clique operator on cographs and serial graphs.  Discrete Math., 282(1-3):183–191, 2004.
  * [7] F. Larrión and V. Neumann-Lara.  Clique divergent graphs with unbounded sequence of diameters.  Discrete Math., 197/198:491–501, 1999.  16th British Combinatorial Conference (London, 1997).
  * [8] F. Larrión and V. Neumann-Lara.  Locally $C_{6}$ graphs are clique divergent.  Discrete Math., 215(1-3):159–170, 2000.
  * [9] F. Larrión, V. Neumann-Lara, and M. A. Pizaña.  On expansive graphs.  European J. Combin., 30(2):372–379, 2009.
  * [10] F. Larrión, V. Neumann-Lara, and M. A. Pizaña.  Whitney triangulations, local girth and iterated clique graphs.  Discrete Math., 258(1-3):123–135, 2002.
  * [11] F. Larrión, V. Neumann-Lara, and M. A. Pizaña.  Graph relations, clique divergence and surface triangulations.  J. Graph Theory, 51(2):110–122, 2006.
  * [12] F. Larrión and M. A. Pizaña.  On hereditary clique-Helly self-clique graphs.  Discrete Appl. Math., 156(7):1157–1167, 2008.
  * [13] F. Larrión, M. A. Pizaña, and R. Villarroel-Flores.  The clique operator on matching and chessboard graphs.  Discrete Math., 309(1):85–93, 2009.
  * [14] Min Chih Lin, Francisco J. Soulignac, and Jayme L. Szwarcfiter.  The clique operator on circular-arc graphs.  Discrete Appl. Math., 158(12):1259–1267, 2010.
  * [15] Victor Neumann-Lara.  On clique-divergent graphs.  Problèmes combinatoires et théorie des graphes, Orsay 1976, Colloq. int. CNRS No. 260, 313-315 (1978)., 1978.
  * [16] Erich Prisner.  Hereditary clique-Helly graphs.  J. Combin. Math. Combin. Comput., 14:216–220, 1993.
  * [17] Erich Prisner.  Graph dynamics, volume 338 of Pitman Research Notes in Mathematics Series.  Longman, Harlow, 1995.