# DiCoM - Diverse Concept Modeling towards Enhancing Generalizability in Chest
X-Ray Studies

Abhijeet Parida1 Daniel Capellán-Martín1,2 Sara Atito3 Muhammad Awais2
María J. Ledesma-Carbayo2 Marius G. Linguraru1,4 Syed Muhammad Anwar1,4

1 Children’s National Hospital, Washington, DC, USA
<EMAIL_ADDRESS>
2 Universidad Politécnica de Madrid & CIBER-BBN, Madrid, Spain
<EMAIL_ADDRESS>
3 CVSSP, University of Surrey, Surrey, UK
<EMAIL_ADDRESS>
4 George Washington University, Washington DC, USA
<EMAIL_ADDRESS>

###### Abstract

Chest X-Ray (CXR) is a widely used clinical imaging modality and has a pivotal
role in the diagnosis and prognosis of various lung and heart related
conditions. Conventional automated clinical diagnostic tool design strategies
relying on radiology reads and supervised learning, entail the cumbersome
requirement of high-quality annotated training data. To address this
challenge, self-supervised pre-training has proven to outperform supervised
pre-training in numerous downstream vision tasks, representing a significant
breakthrough in the field. However, medical imaging pre-training significantly
differs from pre-training with natural images (e.g., ImageNet) due to unique
attributes of clinical images. In this context, we introduce Diverse Concept
Modeling (DiCoM), a novel self-supervised training paradigm that leverages a
student teacher framework for learning diverse concepts and hence effective
representation of the CXR data. Hence, expanding beyond merely modeling a
single primary label within an image, instead, effectively harnessing the
information from all the concepts inherent in the CXR. The pre-trained model
is subsequently fine-tuned to address diverse domain-specific tasks. Our
proposed paradigm consistently demonstrates robust performance across multiple
downstream tasks on multiple datasets, highlighting the success and
generalizability of the pre-training strategy. To establish the efficacy of
our methods we analyze both the power of learned representations and the speed
of convergence (SoC) of our models. For diverse data and tasks, DiCoM is able
to achieve in most cases better results compared to other state-of-the-art
pre-training strategies. This when combined with the higher SoC and
generalization capabilities positions DiCoM to be established as a foundation
model for CXRs, a widely used imaging modality.

##  1 Introduction

Chest X-Rays (CXRs) are the preferred imaging modality for various clinical
diagnostic tasks. This is supported by the fact that acquiring CXR is
relatively cheap and the X-ray facilities are widely available. For pediatric
cases, with CXRs, the exposure to radiation is lesser as compared to a
computed tomography scan. Hence, CXRs are routinely used to triage and
diagnose a variety of clinical conditions in pediatric population [14, 46].
Since the pandemic, CXRs have become the primary radiological screening method
for Coronavirus disease (COVID-19), particularly for symptomatic or COVID-19
positive patients presented to the emergency department, as the Coronavirus
disease manifests in an acute respiratory illness affecting the lungs. This
has resulted in a large number of CXR studies performed in both adult and
pediatric cases in the last few years. In general, with an increasing burden
on healthcare facilities during the pandemic and beyond, CXR has proved very
useful to triage COVID-19 and pneumonia inresource-constrained environments
[2]. The success of this image-based diagnostic modality would be further
enhanced by an expert computer-aided diagnosis system that can effectively
process CXRs for pathology detection, thus managing to mitigate the growing
workload for radiologists.

There are many deep learning methods presented in literature for CXR analyses,
yet very few are clinically adapted. Challenges towards the development and
clinical translation of deep learning methods include the scarcity of quality
labels, limited data for new or rare diseases (particularly for pediatrics),
and lack of generalization for handling imaging data drift from different
clinical sites and devices. Foundation medical image analysis models, similar
to those trained on large-scale domain corpora in natural language processing
[20], could help address the challenges for image-based computer-aided
diagnosis systems. However, for preserving patient privacy, clinical data
needs to be securely stored, limiting availability, and access to large-scale
shared clinical data sets. Further, it is harder to obtain pristine ground
truth labels on clinical data to help with training fully supervised models.
Still the amount of un-annotated digitized clinical data in medical centers is
rapidly increasing. Patient outcomes would greatly benefit from the
development of methods that learn from these large amounts of unused data.

Within current deep learning architectures, vision transformers (ViT) trained
with large-scale data achieve state-of-the-art performance in multiple vision-
related tasks like classification, detection, and semantic segmentation [21,
38]. This success has led to the rapid development of vision foundation models
for a variety of computer vision tasks[7, 35]. For medical imaging, the
attention module in ViT can help identify appropriate features for the
downstream domain-specific tasks, such as pathology classification or image
segmentation, compared to the standard convolutional neural network (CNN)
based architectures. Among these methods, masked image modeling strategies
utilize large unlabeled data to facilitate effective self supervised learning
(SSL) [6, 23, 51], hence providing optimal model weight initialization and
convergence stability for multiple downstream tasks like classification and
segmentation.

Herein, we propose the Diverse Concept Modeling (DiCoM) strategy for domain-
specific self-supervised pre-training using CXR data, thus ascertaining the
feasibility of our proposed methodology for an automated CXR-based diagnosis
and image analysis in the clinical domain. Particularly, we show that the
learned representation is generalizable and successfully transferred to
challenging small-scale and out of distribution unseen pediatric data with a
significant performance in COVID-19 and pneumonia detection. We see
performance gains in challenging cases such as multi-class classification and
in a variety of other tasks related to CXR reads demonstrating the
generlizability of our pre-training strategy.

Our Contributions are summarized as follows-

  * •

We introduce DiCoM, diverse concept modeling strategy for self-supervised pre-
training of deep learning model with a ViT backbone on chest X-Rays.

  * •

We conduct extensive downstream-tuning experiments on CXRs on both seen and
unseen data distributions from public and private sources (to assess the
relevance of the proposed method in practical clinical scenarios) for multi-
class classification, binary classification, and semantic segmentation. We
establish the importance of pre-training on domain data for improved
performance.

  * •

We are the first to study the effort required for the convergence of a large
scale foundation model for clinical data and show that our training strategy
is the most efficient. We also analyze the manifolds to evaluate and establish
efficient representation learning.

  * •

To the best of our knowledge, we are the first to show that self-supervised
pre-training on adult CXR helps learn useful representations for COVID-19 and
multi-class pneumonia detection in pediatric chest scans, traditionally an
underrepresented class in most data sets adding credence to the generalization
of our model for unseen out of distribution data.

Figure 1: Diverse Concept Modeling (DiCoM) framework for self-supervised pre-
training of vision transformers for chest X-ray image analysis.

##  2 Related Works

Earlier self-supervised pre-training methods utilized various pretext tasks,
such as auto-encoding for reconstructing noisy or perturbed images [34],
denoising auto-encoder approaches [47], predicting patch order [36], color
recovery from grayscale images [52], predicting missing regions via image
inpainting [40], predicting rotation angles of images [18], and adversarial
loss for masked patches [45]. Recent methods have shifted towards a
contrastive learning framework [37, 50, 26, 8, 13, 39, 19]. The primary
objective of contrastive learning is to minimize the distance between two
augmented views of the same image while maximizing the distance between views
from different images.

In recent years, driven by the popularity of vision transformers[16], self-
supervised learning approaches have adopted transformer backbones. The concept
of masked image modeling for SSL pre-training has been explored in iGPT [12]
and ViT [16]. These frameworks involve tasks like recovering quantized color
space for patches using GPT and BERT tasks. While CNNs and ViTs in SSL have
demonstrated potential, none have surpassed supervised pre-training, as
exemplified by ViT trained on the JFT-300M Google internally labeled dataset
[16].

Self-supervised pre-training has been gaining appeal in the medical image
domain. Inspired by the UNET architecture [42], a transformer-based model was
introduced for medical image analysis, particularly in segmentation [22].
Employing a self-supervised pre-training strategy, the model demonstrated
state-of-the-art performance on body organ segmentation challenge datasets.
Another application involved a self-supervised contrastive learning strategy
for COVID-19 prognosis [43], outperforming radiologists in predicting
mortality for COVID-19 patients. Additionally, a self-supervised pre-training
approach was applied to magnetic resonance imaging for knee abnormality
classification [3], highlighting the potential of such methods in limited data
scenarios. This work represents a step forward in developing a generalizable
foundational model for CXRs, showcasing the merits and feasibility of the
proposed approach and its potential for improving patient outcomes.

##  3 Self-Supervised Pre-training for Medical Imaging

Self supervised learning is an alternative to supervised learning, operating
on the input data without the need for ground truth labels. The fundamental
idea is to generate supervisory signals from the unstructured data by defining
a pretext task, where a machine learning framework learns the underlying
structure of the data to solve the task. To that end, SSL methods can be
trained using a much larger data that are less affected by human labeling bias
and noise within the data.

Towards this, we introduce Diverse Concept Modeling- DiCoM, a general self-
supervised vision transformer framework for CXRs. In Section 3.1, we briefly
summarise group masked model learning [5, 6] and its adoption to medical
domain. Following, in Section 3.2, we explain our proposed method of self-
learning of data and class tokens conceptualization, with the incorporation of
knowledge distillation [25].

###  3.1 Preliminary

Masked image modeling similar to the Masked Language Modeling (MLM) used in
BERT [15], was proposed in SiT [5] and employed in several recent vision works
[10, 4, 51]. Masked image modeling has different variations and group masked
model learning [5] is one of them which proved effective when dealing with
small datasets.The primary objective of group masked model learning is to
corrupt a “significant” segment of the visual input and restore them through
model learning. The idea is that by restoring the corrupted parts based on the
overall context, the network implicitly grasps the concept of visual
integrity.

Various methods can be employed to corrupt a group of connected patches, such
as replacing randomly selected patches with zeros, introducing noise, or
substituting random patches with patches from other CXRs. In this study, we
opted for simplicity and corrupted the input by replacing randomly selected
groups of tokens with zeros. It’s crucial to highlight that the groups of
corrupted patches are selected randomly, i.e., patches with vital organs or
background are manipulated with equal probability. This allows the network to
generalize to unseen data, as demonstrated by the results for unseen datasets
(Section 4.3.2).

To reconstruct the CXRs, we use ViT as a group masked auto-encoder. Analogous
to auto-encoders, the network is trained to reconstruct the input image using
the output tokens of the transformer. ViT processes a sequence of patches by
tokenizing the input CXR $\mathbf{x}\in\mathbb{R}^{H\times W}$, where $H$ and
$W$ represent the height and width of the CXR. The image is then flattened
into $n$ non-overlapping 2D patches, of size $p\times p$ pixels.

To pre-train the ViT, we manipulate the input CXR, $\mathbf{x}$, by randomly
replacing 70% of the image with zeros to obtain $\mathbf{\hat{x}}$. The
reconstructed CXR, $\mathbf{\bar{x}}=D(E(\mathbf{\hat{x}}))$, is generated by
inputting $\mathbf{\hat{x}}$ into the transformer encoder $E(.)$ and
processing the output through a lightweight decoder $D(.)$. The decoder
consists of three fully connected layers: the first two layers have 2048
neurons each, and the final layer has 256 neurons. Each layer is separated by
a GeLU non-linearity. Transposed convolution operations are used to recover
the CXR. Post pre-training, $E(.)$ is retained for downstream tasks and $D(.)$
is discarded. This decision is motivated by the fact that the $D(.)$ only
learns CXR reconstruction, may not contribute significantly to the downstream
tasks. In the reconstruction task, we use $\ell 1$-loss between the original
and the reconstructed image as shown in Equation 1. The loss is specifically
computed for the corrupted pixel, similar to [15, 6].

$\displaystyle\mathcal{L}_{\rm recons}$
$\displaystyle=\sum_{i}^{H}\sum_{j}^{W}\mathbf{M}_{i,j}\times|\mathbf{x}_{i,j}-\mathbf{\bar{x}}_{i,j}|$
(1)

where, $H\times W$ is the resolution of the CXR and $\mathbf{M}$ is a binary
mask, with 1 corresponding to the manipulated pixels and 0 otherwise.

###  3.2 Local and Global Pseudo-Label Learning

The DiCoM framework employs group masked model learning to grasp visual
integrity. To enhance the concept further, we propose leveraging pseudo
labels. Here, ”pseudo” denotes labels from a teacher model during knowledge
distillation. We suggest using self-knowledge distillation to learn local
pseudo labels for individual tokens in the CXR and a global pseudo label for
the entire CXR. Our hypothesis is that by using multiple representations for
an image might result in better representation learning, given the limited
diversity in augmented views of CXRs. Hence we explore the learning of
representation for each of the data tokens through knowledge distillation.

In knowledge distillation, a student network is trained to mimic the output of
a given teacher network, where $\theta$ and $\phi$ are the parameters of the
student and the teacher networks, respectively. We employ an identical network
architecture for both the student and the teacher, with the teacher acting as
a momentum encoder [24] for the student.An exponential moving average of the
student weights is used to update the teacher network, following the rule:
$\phi\leftarrow\lambda\phi+(1-\lambda)\theta$.

In our case, the student network comprises of two components: A ViT backbone,
followed by a projection head. The projection head consists of three fully
connected layers: the first two with 2048 neurons and GeLU non-linearity each,
and the final layer with 256 neurons. The output of the final layer is
$\ell_{2}$ normalized and directly connected to a weight-normalized fully
connected layer with 8192 neurons. It’s important to note that the entire
projection head is shared for both the class token and the data tokens. This
shared configuration facilitates the transfer of semantics acquired in the
class token to the patch tokens.

To generate the pseudo label for the data tokens of the CXR image
$\mathbf{x}$, the image is fed to the teacher network and the output tokens
are passed to the projection head to obtain
$\mathbf{z}_{t}\in\mathbb{R}^{n\times K}$. The masked image $\mathbf{\hat{x}}$
is passed to the student network to obtain
$\mathbf{z}_{s}\in\mathbb{R}^{n\times K}$, where $n$ is the number of tokens
of the ViT and $K$, is the feature size of the final layer ($K=3092$). The
objective is to align the output of the student network with that of the
teacher network, utilizing the Kullback-Leibler(KL) divergence.

To prevent model collapse, an normalization step is introduced to avoid the
model outputs becoming a trivial constant. The teacher’s output goes through a
batch normalization layer without adaptive parameters, using the moving
average and standard deviation of the data, resulting in
$\mathbf{\bar{z}}_{t}$. The output probability distributions are obtained as
follows:

$p_{t}^{(i,j)}=\frac{\exp({\mathbf{\bar{z}}_{t}^{(i,j)}}/{\tau_{t}})}{\sum_{k=1}^{K}\exp({\mathbf{\bar{z}}_{t}^{(i,k)}}/{\tau_{t}})},$
(2)
$p_{s}^{(i,j)}=\frac{\exp({\mathbf{{z}}_{s}^{(i,j)}}/{\tau_{s}})}{\sum_{k=1}^{K}\exp({\mathbf{{z}}_{s}^{(i,k)}}/{\tau_{s}})}$
(3)

where $\mathbf{\bar{z}}_{t}$ and $\mathbf{z}_{s}$ are the class logits for the
teacher and the student. $p_{t}(i,.)$ and $p_{s}(i,.)$ are the probabilities
corresponding to the $i^{\rm th}$ token output by the teacher and the student.
Additionally, $\tau_{t}$ and $\tau_{s}$ are the temperature parameters for the
teacher and the student. The softmax function includes a temperature parameter
that controls the sharpness of the output probabilities. Sharpening is
obtained by using a lower value for the temperature $\tau_{t}$ in the teacher
compared to the student $\tau_{s}$.

Our training objective is to match the output probability of the student
$p_{s}$ with that of teacher $p_{t}$. We use the cross entropy measure for
this task.

$\mathcal{L}_{\rm
l}=\sum_{k}^{N}\left(\sum_{i=1}^{n}T^{k}_{i}\times\sum_{j=1}^{K}-p^{k}_{t}{(i,j)}\log
p^{k}_{s}{(i,j)}\right),$ (4)

where $\mathbf{T}$ is a binary mask with 1 indicates a masked token and 0
otherwise.

The network is trained to assign a class for each token in the image and
distinguish it from other tokens. The idea of local contrastive loss
($\mathcal{L}_{\rm l}$) is similar to image reconstruction not in the pixel
space, rather in the class space.Regarding global contrastive learning, we
follow the same procedure as in the local contrastive learning, but focus on
the class token to learn a global representation for the entire CXR. This task
involves two augmented views. The goal is to match the student’s class token
from the first augmented view, $p_{s,1}(0,.)$, with the teacher’s class token
from the second augmented view, $p_{t,2}(0,.)$, and vice versa. The overall
global contrastive learning loss($\mathcal{L}_{\rm g}$) is:

$\begin{split}\mathcal{L}_{\rm
g}&=\sum_{k}^{N}\sum_{j=1}^{K}-p^{k}_{t,1}{(0,j)}\log p^{k}_{s,2}{(0,j)})\\\
~{}~{}~{}~{}&+\sum_{j=1}^{C}-p^{k}_{t,2}{(0,j)}\log
p^{k}_{s,1}{(0,j)})\end{split}$ (5)

###  3.3 Putting Together the DiCoM Framework

For a CXR, two augmented views are generated and fed into the teacher network.
The masked version of the two views are passed to the student network. The
output data tokens from the student network is used in both the reconstruction
head and the contrastive learning projection head. The reconstruction loss,
$\mathcal{L}_{\rm recons}$, is computed between the reconstructed images and
the original images. Additionally, the local contrastive learning loss,
$\mathcal{L}{\rm l}$, is determined by aligning the output of the data tokens
from the student network with those from the teacher network. Subsequently,
the global contrastive learning loss, $\mathcal{L}{\rm g}$, is calculated by
matching the representation of the two augmented views corresponding to the
class token from both the student and teacher networks. The overall loss,
$\mathcal{L}$:

$\mathcal{L}=\alpha_{1}\mathcal{L}_{\rm recons}+\alpha_{2}\mathcal{L}_{\rm
l}+\alpha_{3}\mathcal{L}_{\rm g},$ (6)

where $\alpha_{1},\alpha_{2}$ & $\alpha_{3}$ are the scaling factors of our
diverse concept objective function, which are set to equal weights for
simplicity in this study. We believe further improvements can be gained by
optimizing the scaling factors or by incorporating uncertainty weighting [31].

Dataset | Sample Size | Classes / clinical conditions | Downstream task | Pre-training | Fine-tuning | Testing
---|---|---|---|---|---|---
COVIDxCXR-3111https://www.kaggle.com/datasets/andyczhao/covidx-cxr2 [48, 41] | 30,384 | COVID-19, Pneumonia, Healthy | Binary Classification | ✓ | ✓ | ✓
CheXpert[27] | 191,229 | 14 radiological observations | Binary Classification | ✓ | ✓ | ✓
ChestXray-14[49] | 112,120 | 14 radiological observations | - | ✓ | ✗ | ✗
SPR X-Ray[33] | 22,449 | Sex (male, female) | - | ✓ | ✗ | ✗
Shenzhen[28] | 662 | Tuberculosis, healthy | Segmentation | ✓ | ✓ | ✓
Montgomery[28] | 138 | Tuberculosis, healthy | Segmentation | ✓ | ✓ | ✓
Belarus[1] | 304 | Tuberculosis, healthy | Segmentation | ✓ | ✓ | ✓
MIMIC-CXR[29, 30] | 240,570 | 14 radiological observations | Binary Classification | ✗ | ✓ | ✓
COVID-PEDs (in-house) | 199 | COVID-19, healthy | Binary Classification | ✗ | ✓ | ✓
Convergence Analysis | ✗ | ✗ | ✓
Guangzhou Medical [32] | 5,856 | Viral pneumonia, bacterial pneumonia, healthy | Multi-class Classification | ✗ | ✓ | ✓
UNIFESP[17] | 2,480 | Chest, wrists, skull, thigh, lower leg, | Representation Learning | ✗ | ✗ | ✓
Knee, elbow, feet, and finger

Table 1: Summary of Datasets used for various tasks and experiments in this
study.

##  4 Experimental Results

###  4.1 Datasets

We aim to show that the domain-specific representation learned during the
self-supervised pre-training stage using our proposed strategy (DiCoM) is
generalizable and has the potential to solve frequent clinical tasks
(classification and segmentation). To this end, we used a large-scale data
comprising of 357,286 frontal CXR images for self-supervised pre-training,
including pathologies such as COVID-19, pneumonia, tuberculosis, and clinical
signs such as atelectasis, lung opacity, and cardiomegaly, among others. A
brief summary is provided in Table 1. Note that the initial CheXpert dataset
contains a total of 224,316 CXR images (both frontal and lateral), of which
our study uses 191,229 frontal CXR images.

Details including preprocessing steps and splits used for the pre-training,
fine-tuning, and testing stages of the experiments are presented in Appendix
LABEL:sec:dataset.

###  4.2 Evaluation Strategies

Pre-Training: We conducted training of the smaller ViT (ViT-S) model using
several competitive SSL-based pre-training strategies, adhering to their
suggested hyperparameters, for 250 epochs on the chest X-ray pre-training data
(as described in Section 4.1 and Appendix A). The competing strategies
employed for this study include the momentum contrastive method (MOCO-v3
[24]), knowledge distillation method (DINO [11]), group masked methods (MAE
[23] and GMML [6]), and SiT [5].

Downstream Tuning: After the self-supervised pre-training, task-specific
layers for the downstream task are introduced. We hypothesize that the pre-
training from unlabeled CXRs using our proposed strategy (DiCoM) learns
excellent representation for task-specific downstream-tuning of network
weights. We have further established this fact by objectively quantifying the
learned representation (Section 4.6). The fine-tuning for the downstream tasks
is performed in a supervised manner for classification using DEiT [44] and
their suggested hyper-parameters for 100 epochs for a fair comparison. To
study the performance on segmentation and the impact of modification of the
model architecture we use the UNETR framework [22]. The UNETR using different
weights from different pre-trained model are optimized for 200 epochs using
their suggested hyper-parameters for 2D CXR images.

DiCoM Evaluation: To assess various SSL strategies, we adhere to the
guidelines outlined in [9]. In cases where labels for downstream tasks are
available, we conduct both linear probing and fine-tuning. Linear probing
involves appending a linear layer at the end of the frozen backbone to
estimate the quality of the representation of the backbone [9]. Fine-tuning,
on the other hand, involves re-training the entire network, including both the
linear layer and the backbone, to gauge the total discriminative power of the
entire model [23].

Extending our evaluation beyond classification tasks, we further assess SSL
methods using tasks such as lung segmentation. Importantly, we delve into the
evaluation of the speed of convergence (SoC) of downstream tasks in Section
4.7 and explore the power of the learned representations in Section 4.6.

Metrics: To compare different methods, we employ metrics that are agnostic to
any thresholds and insensitive to class imbalances. Therefore, for binary
classification, we utilize the Area Under the Precision-Recall (AUPR) curve,
for segmentation, we use the Dice coefficient (equivalent to F1 score), and
for clustering to quantify learned representations, we rely on the Silhouette
coefficient.

###  4.3 Binary Classification

We conducted various downstream classification tasks to evaluate the efficacy
of DiCoM across multiple datasets.

####  4.3.1 Seen Distribution during Downstream Tuning

We conducted both linear probing and fine-tuning experiments for COVID versus
non-COVID classification on COVIDxCXR-3 data (refer to Table 2). This approach
ensures that our reported results reflect performance on a seen data
distribution, considering that COVIDxCXR-3 served as one of the datasets
employed during the SSL pre-training phase. Our approach exhibits superior
performance compared to alternative methods. Notably, we observe a positive
AUPR difference of $\sim$5.2% and $\sim$0.3% during linear probing and fine-
tuning, respectively. These findings suggest that the knowledge acquired
through the self-supervised pre-training phase using DiCoM is more effectively
transferred when adapting to domain-specific scenarios during the fine-tuning
process.

We conducted both linear probing and fine-tuning experiments on another seen
data distribution Chexpert, using the training and testing data from CheXpert,
adhering to the original data splits. Results are presented in Table 3. Our
findings indicate that, while DiCoM slightly trails behind other methodologies
such as SiT, DINO, or MOCO in certain scenarios, it generally demonstrates
competitive performance on CheXpert. Notably, we observe a performance
improvement of $\sim$1.3% and $\sim$0.5% in AUPR curve through linear probing
and fine-tuning, respectively.

SSL Technique | COVIDxCXR-3 | COVID-PEDs
---|---|---
Linear Probing | Fine-tuning | Linear Probing | Fine-tuning
ACC | AUPR | AUC | ACC | AUPR | AUC | ACC | AUPR | AUC | ACC | AUPR | AUC
No Pre-training | .855 | .948 | .936 | .971 | .997 | .997 | .605 | .681 | .667 | .684 | .820 | .772
MOCO-v3 | .935 | .989 | .986 | .984 |  .999 |  .999 | .658 | .735 | .678 | .737 | .847 | .808
DINO | .978 |  .998 |  .998 | .986 |  .999 |  .999 |  .711 | .811 | .728 | .711 | .832 | .790
MAE | .966 | .997 | .996 | .993 | 1.00 | 1.00 | .684 | .815 | .750 | .816 | .917 | .868
GMML | .926 | .986 | .983 | .986 |  .999 |  .999 | .658 | .775 | .742 |  .789 | .873 | .792
SiT |  .988 | 1.00 | 1.00 |  .992 | 1.00 | 1.00 | .632 |  .821 |  .772 |  .789 | .865 | .808
DiCoM (ours) | .989 | 1.00 | 1.00 | .990 | 1.00 | 1.00 | .763 | .848 | .783 | .711 |  .879 |  .828

Table 2: Binary classification of non-COVID-19 vs. COVID-19 on test sets of
COVIDxCXR-3 (adult, seen) and COVID-PEDs (private data, pediatric, unseen).
The highest scores are in bold, while the second best ones are underlined.
Abbreviations: ACC, accuracy; AUPR, Area Under the Precision-Recall Curve;
AUC, Area Under the Receiver Operating Curve.

SSL Technique | CheXpert | MIMIC-CXR
---|---|---
Linear Probing | Fine-tuning | Linear Probing | Fine-tuning
ACC | AUPR | AUC | ACC | AUPR | AUC | ACC | AUPR | AUC | ACC | AUPR | AUC
No Pre-training | .869 | .956 | .775 | .842 | .982 | .894 | .797 | .895 | .664 | .817 | .911 | .740
MOCO-v3 |  .884 | .983 | .916 | .907 |  .993 |  .962 | .819 | .922 | .750 | .821 | .929 | .777
DINO | .888 |  .990 |  .948 | .896 | .992 | .959 | .822 | .914 | .747 | .828 | .930 | .777
MAE | .849 | .990 | .935 | .884 | .988 | .934 | .829 | .926 | .768 |  .839 | .938 |  .791
GMML | .855 | .983 | .895 | .855 | .993 | .953 | .825 | .918 | .749 | .821 | .933 | .779
SiT | .869 | .992 | .959 |  .900 | .995 | .972 |  .838 | .953 | .817 | .820 |  .939 | .774
DiCoM (ours) | .865 | .969 | .852 | .861 | .987 | .930 | .843 |  .948 |  .802 | .840 | .947 | .807

Table 3: Binary classification of multiple diseases on the test set of
CheXpert (seen) and MIMIC-CXR (unseen) datasets. Original test splits were
used for each of the datasets. Binary classification is disease vs. healthy.
The highest scores are in bold, while the second best ones are underlined.
Abbreviations: ACC, accuracy; AUPR, Area Under the Precision-Recall Curve;
AUC, Area Under the Receiver Operating Curve.

####  4.3.2 Unseen Distribution during Downstream Tuning

We also conducted experiments involving the fine-tuning and linear probing of
each pre-trained model on unseen data to assess the transferability of
knowledge acquired during the pre-training phase, even when dealing with
distribution-shifted data. To this end, the models were tuned and tested on
MIMIC-CXR, maintaining the original splits. We kept MIMIC-CXR data for this
particular experiment and hence was not included in the pre-training stage.
Table 3 presents the results, demonstrating that DiCoM achieves superior
performance on MIMIC-CXR. Specifically, it emerges as the top-performing
approach in fine-tuning and ranks second in linear probing (with AUPR as
ranking metric). When compared to a fully supervised ViT-S model, DiCoM
exhibits a performance improvement of $\sim$5.3% and $\sim$3.6% in AUPR for
linear probing and fine-tuning, respectively.

These results underscore DiCoM’s robust adaptability to unseen data,
showcasing its effectiveness in enhancing model performance in scenarios where
conventional fully supervised approaches would not perform as well.

####  4.3.3 Shifted Distribution during Downstream Tuning

In addition to evaluating the model’s adaptability to unseen data, we
investigated its performance in handling out-of-distribution (OOD) datasets,
i.e., when there is a shift in the data distribution, specifically in the
context of pediatric cases, where radiological signs and disease detection
pose unique challenges in standard clinical practice.

Here, our experiments focused on COVID-PEDs, a relatively small dataset
(approximately 1,000 times smaller than MIMIC-CXR or CheXpert) of pediatric
COVID-19 cases collected in-house. The results, outlined in Table 2, highlight
DiCoM’s consistent high performance in handling task-specific OOD datasets.
Notably, when compared to a fully supervised ViT-S model, DiCoM demonstrates a
performance improvement of 16.7% and 5.9% in AUPR for linear probing and fine-
tuning, respectively, underscoring its efficacy in addressing challenges posed
by distribution-shifted pediatric data.

###  4.4 Multi-class Classification

To further assess the effectiveness of the representation learning using
DiCoM, we conducted experiments on a multi-class classification task using the
Guangzhou pediatric dataset [32]. This dataset not only serves as unseen data,
but also poses an OOD scenario, given its distinct pediatric characteristics.

Results are presented in Table 4. Here, once more, DiCoM showcased exceptional
performance, securing the top score among all SSL techniques during fine-
tuning and ranking second only to DINO in the case of linear probing.
Comparative analysis against a fully supervised ViT-S model revealed notable
performance improvements for DiCoM, with gains of 18.6% and 18.3% in AUPR for
linear probing and fine-tuning, respectively.

This reaffirms DiCoM’s efficacy in capturing and leveraging meaningful
representations, consistently outperforming fully supervised and other self-
supervised approaches even in complex multi-class classification scenarios.
The superior performance on the Guangzhou pediatric dataset further
underscores the robustness and versatility of DiCoM in diverse medical imaging
tasks adding credence to the generalization capabilities of DiCoM.

SSL Technique | Linear Probing (AUPR) | Fine-tuning (AUPR)
---|---|---
No Pre-training | 0.673 | 0.708
MOCO-v3 | 0.827 | 0.827
DINO | 0.875 |  0.888
MAE | 0.846 | 0.804
GMML | 0.740 | 0.833
SiT | 0.776 | 0.853
DiCoM (ours) |  0.859 | 0.891

Table 4: Multiclass classification accuracy for healthy vs. viral pneumonia
vs. bacterial pneumonia on the test set of the Guangzhou pediatric pneumonia
dataset.

###  4.5 Segmentation: Architecture Shift

In addition to the tasks with vanilla vision transformer architecture, we
explored the performance of the pre-trained weights embedded into alternative
architectures. Specifically, we evaluated the pre-training method in the
context of lung segmentation using the UNETR [22] architecture.

SSL Technique | Shenzhen | Montgomery | Belarus
---|---|---|---
DICE | HD_95 | DICE | HD_95 | DICE | HD_95
No Pretraining | 0.914 | 9.62 | 0.956 | 8.89 | 0.859 | 21.40
MOCO-v3 | 0.917 |  7.50 |  0.964 |  5.64 | 0.873 | 16.51
DINO | 0.956 | 8.20 | 0.958 | 7.24 | 0.866 | 19.43
MAE | 0.960 | 6.97 | 0.966 | 4.90 |  0.877 |  16.19
GMML | 0.952 | 8.30 | 0.955 | 7.23 | 0.837 | 21.84
SiT | 0.957 | 7.80 | 0.952 | 9.31 | 0.868 | 18.61
DiCoM (ours) |  0.958 | 7.90 |  0.964 | 8.06 | 0.885 | 15.97

Table 5: Lung segmentation performance for different pre-trained weights on
various dataset using UNETR[22] for segmentation of lung. Abbreviations:
HD_95, Hausdorff 95% distance.

The segmentation performance is showcased on the test sets of three datasets:
Shenzhen, Montgomery, and Belarus. The segmentation results for these
datasets, characterized by varying sizes, are summarized in Table 5. Across
all datasets, it is evident that the SSL pre-training proves advantageous for
enhancing Dice scores.

In the context of larger datasets (Shenzhen & Montgomery), MAE[23] based pre-
training surpasses other methods in terms of Dice scores, with our proposed
method closely following. However, for smaller dataset like the Belarus TB
dataset, DiCoM outperforms other pre-training strategies. These findings
highlight the efficacy of pre-trained weights for tasks involving changes in
architecture as well. Overall, DiCoM demonstrates superior performance
compared to alternative approaches. A comprehensive qualitative comparison of
lung segmentation by different methods is given in Appendix B.

###  4.6 Learning Representations

In addition to assessing various downstream tasks, we also conducted an
evaluation of the ViT-encoder’s performance as a feature extractor. Our
specific focus was on understanding how well the features learned for CXRs
compared to X-Rays (XRs) from other body parts.

We employed the UNIFESP dataset[17], encompassing CXRs and XRs of non-
intersecting body parts such as wrists, skull, thigh, lower Leg, knee, elbow,
feet, and finger. The goal was to achieve equal representation of both
classes. Our hypothesis was that CXRs would reside on a different manifold
compared to the other XRs. To quantify this hypothesis, we utilized the Rand
Index (a measure of clustering accuracy) and Silhouette Coefficient (a measure
of cluster tightness), assuming the presence of two clusters — one for CXRs
and another for other XRs. The rationale being that a good feature extractor
would exhibit a high Rand Index and Silhouette Coefficient.

SSL Technique | Rand Index | Silhoutte Coefficient
---|---|---
MOCO-v3 | 0.500 | 0.132
DINO | 0.591 | 0.052
MAE | 0.779 | 0.314
GMML | 0.665 | 0.372
SiT | 0.502 | 0.052
DiCoM (ours) |  0.758 |  0.358

Table 6: Clustering metrics to evaluate feature learning of CXRs versus other
X-Rays. Rand index is a measure of accuracy of clustering and silhoutte
coefficient is a measure of tightness of the cluster.

The results in Table 6 reveal that for the Rand Index, MAE outperforms others
with an accuracy of 77.9%, while DiCoM closely follows with 75.8%. Regarding
the proximity of samples within each cluster, the highest performance is
observed in pre-training using GMML, yielding a Silhouette Coefficient of
0.372, and DiCoM comes second with 0.358. When combined effect of both these
metrics (silhoutte coefficient and Rand index) is considered, DiCoM has
learned a more effective representation due to highly accurate closed
clustering of CXRs compared to other methods, establishing itself as a
superior feature extractor for this modality.

The manifold visualizations for each of the methods, complementing the metrics
presented in Table 6, are provided in Appendix LABEL:section:appendix-
manifold.

###  4.7 Downstream Tuning in Low Resource Settings and Clinical Translation

In the majority of medical interventions globally, resources, both in terms of
data and computational power, are often limited. The use of pre-trained
methods proves advantageous in such scenarios, enabling computationally
intensive tasks to be offloaded to large compute clusters located remotely.
Ideally, a clinical site dedicated to a specific task should find it
sufficient to train for a few iterations on a small dataset to achieve optimal
results. This approach enhances the feasibility and efficiency of implementing
medical interventions in environments with limited resources. Moreover, the
need for fewer computational resources leads to models having a reduced carbon
footprint.

Figure 2: Speed of Convergence (SoC) for various methods. Higher SoC indicates
better performance in low resource settings.

To quantify this, we gauge the speed of convergence (SoC) by defining it as
the area under the curve of the maximum AUPR versus epoch curve. SoC serves as
an indicator of how rapidly the model attains maximum performance. To simulate
low data settings, we use the COVID-PEDs dataset. Figure 2 illustrates that
DiCoM exhibits a high SoC score of 0.856. This is 2.3% higher than MOCO-v3,
the nearest competitor, and 11.9% higher than the model without pre-training.
Additionally, it is noteworthy that DiCoM achieves peak performance in 15
epochs, whereas MOCO-v3 requires at least 27 epochs. The accelerated
convergence of DiCoM therefore enhances efficiency, making it suitable and
preferable not only in resource-constrained settings but also environmentally
friendly.

##  5 Discussions

Figure 3: Performance summary of the various pretraining strategies on
different tasks. Higher area is an indicator of better overall performance.
Abbreviations: clf, classification.

Our experimental results described in the preceding section support the claim
that the representation learning achieved with DiCoM leads to superior
performance and generalizability when compared to other pre-training
approaches, including fully supervised ViTs, across various domain-specific
downstream tasks, as illustrated in Figure 3. With area under the curve for
DiCoM of 0.886 (highest among compared methods), our experimental evaluations
affirms that DiCoM excels in generating representations that empowers the ViT
model to achieve top performance on not only large-scale datasets but also for
datasets with diverse characteristics. These include larger seen distributions
during pre-training to smaller unseen out-of-distribution datasets (i.e.,
pediatric data acquired from different devices and conditions). Furthermore,
DiCoM consistently outperforms fully supervised ViT-S models in all
classification tasks, achieving a performance gain of $\sim$18.6%. Our method
also exhibits superior performance in segmentation downstream tasks compared
to alternative approaches, showing generalizibility in shifts of architecture.
In this context, DiCoM achieves a gain of $\sim$4.4% over fully supervised
ViT-S model. Moreover, clustering results combining the Rand index and
silhouette coefficient validate the superior representation learned by DiCoM.
We argue that this clustering superiority could be the reason for its
effectiveness in these diverse downstream tasks. Lastly, SoC results reveal
that DiCoM’s pre-trained weights are helpful for deployment in scenarios with
limited data and computational resources, facilitating robust performance with
a reduced carbon footprint—a valuable attribute in resource-constrained and
environmentally conscious settings.

##  6 Conclusions

Given the importance of CXRs in the current healthcare landscape and the
increased care burden within healthcare facilities, we have proposed DiCoM as
a paradigm that leverages self-supervised pre-training to address domain-
specific downstream tasks related to CXRs. Looking ahead, we plan to enhance
and further extend the generalizibilty of DiCoM paradigm to establish a
foundational model for chest radiography by incorporating even more CXR data
during pre-training such as MIMIC and other public and private repositories,
and including computed tomography scans from chest for volumetric analyses.
Such advances would enhance the model’s capability for detecting additional
lung diseases such as tuberculosis and nodules.

## References

  * [1] Belarus tuberculosis portal.
  * [2] Sherif A Abo-Hedibah, Nehal Tharwat, and Ali H Elmokadem.  Is chest x-ray severity scoring for covid-19 pneumonia reliable?  Polish Journal of Radiology, 86(1):432–439, 2021.
  * [3] Sara Atito, Syed Muhammad Anwar, Muhammad Awais, and Josef Kittler.  Sb-ssl: Slice-based self-supervised transformers for knee abnormality classification from mri.  In Workshop on Medical Image Learning with Limited and Noisy Data, pages 86–95. Springer, 2022.
  * [4] Sara Atito, Muhammad Awais, Ammarah Farooq, Zhenhua Feng, and Josef Kittler.  Mc-ssl0. 0: Towards multi-concept self-supervised learning.  arXiv preprint arXiv:2111.15340, 2021.
  * [5] Sara Atito, Muhammad Awais, and Josef Kittler.  Sit: Self-supervised vision transformer.  arXiv preprint arXiv:2104.03602, 2021.
  * [6] Sara Atito, Muhammad Awais, and Josef Kittler.  Gmml is all you need.  arXiv preprint arXiv:2205.14986, 2022.
  * [7] Bobby Azad, Reza Azad, Sania Eskandari, Afshin Bozorgpour, Amirhossein Kazerouni, Islem Rekik, and Dorit Merhof.  Foundational models in medical imaging: A comprehensive survey and future vision.  arXiv preprint arXiv:2310.18689, 2023.
  * [8] Philip Bachman, R Devon Hjelm, and William Buchwalter.  Learning representations by maximizing mutual information across views.  Advances in neural information processing systems, 32, 2019.
  * [9] Randall Balestriero, Mark Ibrahim, Vlad Sobal, Ari Morcos, Shashank Shekhar, Tom Goldstein, Florian Bordes, Adrien Bardes, Gregoire Mialon, Yuandong Tian, et al.  A cookbook of self-supervised learning.  arXiv preprint arXiv:2304.12210, 2023.
  * [10] Hangbo Bao, Li Dong, and Furu Wei.  Beit: Bert pre-training of image transformers.  arXiv preprint arXiv:2106.08254, 2021.
  * [11] Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin.  Emerging properties in self-supervised vision transformers.  In Proceedings of the IEEE/CVF international conference on computer vision, pages 9650–9660, 2021.
  * [12] Mark Chen, Alec Radford, Rewon Child, Jeffrey Wu, Heewoo Jun, David Luan, and Ilya Sutskever.  Generative pretraining from pixels.  In International conference on machine learning, pages 1691–1703. PMLR, 2020.
  * [13] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton.  A simple framework for contrastive learning of visual representations.  In International conference on machine learning, pages 1597–1607. PMLR, 2020.
  * [14] Karuna M Das, Jamal A Alkoteesh, Jumaa Al Kaabi, Taleb Al Mansoori, Abbey J Winant, Rajvir Singh, Rajesh Paraswani, Rizwan Syed, Elsadeg M Sharif, Ghazala B Balhaj, et al.  Comparison of chest radiography and chest ct for evaluation of pediatric covid-19 pneumonia: Does ct add diagnostic value?  Pediatric Pulmonology, 56(6):1409–1418, 2021.
  * [15] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  arXiv preprint arXiv:1810.04805, 2018.
  * [16] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  arXiv preprint arXiv:2010.11929, 2020.
  * [17] Felipe Kitamura Eduardo Farina.  Unifesp x-ray body part classifier competition, 2022.
  * [18] Spyros Gidaris, Praveer Singh, and Nikos Komodakis.  Unsupervised representation learning by predicting image rotations.  arXiv preprint arXiv:1803.07728, 2018.
  * [19] Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre H Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Daniel Guo, Mohammad Gheshlaghi Azar, et al.  Bootstrap your own latent: A new approach to self-supervised learning.  arXiv preprint arXiv:2006.07733, 2020.
  * [20] Yu Gu, Robert Tinn, Hao Cheng, Michael Lucas, Naoto Usuyama, Xiaodong Liu, Tristan Naumann, Jianfeng Gao, and Hoifung Poon.  Domain-specific language model pretraining for biomedical natural language processing.  ACM Transactions on Computing for Healthcare (HEALTH), 3(1):1–23, 2021.
  * [21] Kai Han, Yunhe Wang, Hanting Chen, Xinghao Chen, Jianyuan Guo, Zhenhua Liu, Yehui Tang, An Xiao, Chunjing Xu, Yixing Xu, et al.  A survey on vision transformer.  IEEE transactions on pattern analysis and machine intelligence, 2022.
  * [22] Ali Hatamizadeh, Yucheng Tang, Vishwesh Nath, Dong Yang, Andriy Myronenko, Bennett Landman, Holger R Roth, and Daguang Xu.  Unetr: Transformers for 3d medical image segmentation.  In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pages 574–584, 2022.
  * [23] Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Dollár, and Ross Girshick.  Masked autoencoders are scalable vision learners.  arXiv preprint arXiv:2111.06377, 2021.
  * [24] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick.  Momentum contrast for unsupervised visual representation learning.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9729–9738, 2020.
  * [25] Geoffrey Hinton, Oriol Vinyals, and Jeff Dean.  Distilling the knowledge in a neural network.  arXiv preprint arXiv:1503.02531, 2015.
  * [26] R Devon Hjelm, Alex Fedorov, Samuel Lavoie-Marchildon, Karan Grewal, Phil Bachman, Adam Trischler, and Yoshua Bengio.  Learning deep representations by mutual information estimation and maximization.  In International Conference on Learning Representations (ICLR), 2019.
  * [27] Jeremy Irvin, Pranav Rajpurkar, Michael Ko, Yifan Yu, Silviana Ciurea-Ilcus, Chris Chute, Henrik Marklund, Behzad Haghgoo, Robyn Ball, Katie Shpanskaya, Jayne Seekins, David A. Mong, Safwan S. Halabi, Jesse K. Sandberg, Ricky Jones, David B. Larson, Curtis P. Langlotz, Bhavik N. Patel, Matthew P. Lungren, and Andrew Y. Ng.  Chexpert: A large chest radiograph dataset with uncertainty labels and expert comparison.  33rd AAAI Conference on Artificial Intelligence, AAAI 2019, 31st Innovative Applications of Artificial Intelligence Conference, IAAI 2019 and the 9th AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, pages 590–597, 1 2019.
  * [28] Stefan Jaeger, Sema Candemir, Sameer Antani, Yì-Xiáng J. Wáng, Pu-Xuan Lu, and George Thoma.  Two public chest x-ray datasets for computer-aided screening of pulmonary diseases.  Quantitative Imaging in Medicine and Surgery, 4:475, 12 2014.
  * [29] A. Johnson, M. Lungren, Y. Peng, Z. Lu, R. Mark, S. Berkowitz, and S. Horng.  MIMIC-CXR-JPG - chest radiographs with structured labels (version 2.0.0), 2019.
  * [30] Alistair E. W. Johnson, Tom J. Pollard, Nathaniel R. Greenbaum, Matthew P. Lungren, Chih ying Deng, Yifan Peng, Zhiyong Lu, Roger G. Mark, Seth J. Berkowitz, and Steven Horng.  MIMIC-CXR-JPG, a large publicly available database of labeled chest radiographs.  arXiv preprint arXiv:1901.07042, 1 2019.
  * [31] Alex Kendall, Yarin Gal, and Roberto Cipolla.  Multi-task learning using uncertainty to weigh losses for scene geometry and semantics.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 7482–7491, 2018.
  * [32] Daniel S. Kermany, Michael Goldbaum, Wenjia Cai, Carolina C.S. Valentim, Huiying Liang, Sally L. Baxter, Alex McKeown, Ge Yang, Xiaokang Wu, Fangbing Yan, Justin Dong, Made K. Prasadha, Jacqueline Pei, Magdalena Ting, Jie Zhu, Christina Li, Sierra Hewett, Jason Dong, Ian Ziyar, Alexander Shi, Runze Zhang, Lianghong Zheng, Rui Hou, William Shi, Xin Fu, Yaou Duan, Viet A.N. Huu, Cindy Wen, Edward D. Zhang, Charlotte L. Zhang, Oulan Li, Xiaobo Wang, Michael A. Singer, Xiaodong Sun, Jie Xu, Ali Tafreshi, M. Anthony Lewis, Huimin Xia, and Kang Zhang.  Identifying medical diagnoses and treatable diseases by image-based deep learning.  Cell, 172:1122–1131.e9, 2 2018.
  * [33] Felipe Kitamura, Lilian Mallagoli, and Paulo Kuriki.  Spr x-ray gender prediction challenge, 2023.
  * [34] Mark A Kramer.  Nonlinear principal component analysis using autoassociative neural networks.  AIChE journal, 37(2):233–243, 1991.
  * [35] DongAo Ma, Jiaxuan Pang, Michael B Gotway, and Jianming Liang.  Foundation ark: Accruing and reusing knowledge for superior and robust performance.  In International Conference on Medical Image Computing and Computer-Assisted Intervention, pages 651–662. Springer, 2023.
  * [36] Mehdi Noroozi and Paolo Favaro.  Unsupervised learning of visual representations by solving jigsaw puzzles.  In European conference on computer vision, pages 69–84. Springer, 2016.
  * [37] Aaron van den Oord, Yazhe Li, and Oriol Vinyals.  Representation learning with contrastive predictive coding.  arXiv preprint arXiv:1807.03748, 2018.
  * [38] Arshi Parvaiz, Muhammad Anwaar Khalid, Rukhsana Zafar, Huma Ameer, Muhammad Ali, and Muhammad Moazam Fraz.  Vision transformers in medical computer vision–a contemplative retrospection.  arXiv preprint arXiv:2203.15269, 2022.
  * [39] Massimiliano Patacchiola and Amos J Storkey.  Self-supervised relational reasoning for representation learning.  In Advances in Neural Information Processing Systems, volume 33, pages 4003–4014, 2020.
  * [40] Deepak Pathak, Philipp Krahenbuhl, Jeff Donahue, Trevor Darrell, and Alexei A Efros.  Context encoders: Feature learning by inpainting.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2536–2544, 2016.
  * [41] Maya Pavlova, Tia Tuinstra, Hossein Aboutalebi, Andy Zhao, Hayden Gunraj, and Alexander Wong.  Covidx cxr-3: A large-scale, open-source benchmark dataset of chest x-ray images for computer-aided covid-19 diagnostics.  arXiv preprint arXiv:2206.03671, 2022.
  * [42] Olaf Ronneberger, Philipp Fischer, and Thomas Brox.  U-net: Convolutional networks for biomedical image segmentation.  In International Conference on Medical image computing and computer-assisted intervention, pages 234–241. Springer, 2015.
  * [43] Anuroop Sriram, Matthew Muckley, Koustuv Sinha, Farah Shamout, Joelle Pineau, Krzysztof J Geras, Lea Azour, Yindalon Aphinyanaphongs, Nafissa Yakubova, and William Moore.  Covid-19 prognosis via self-supervised representation learning and multi-image prediction.  arXiv preprint arXiv:2101.04909, 2021.
  * [44] Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Herve Jegou.  Training data-efficient image transformers & distillation through attention.  In International Conference on Machine Learning, volume 139, pages 10347–10357, July 2021.
  * [45] Trieu H Trinh, Minh-Thang Luong, and Quoc V Le.  Selfie: Self-supervised pretraining for image embedding.  arXiv preprint arXiv:1906.02940, 2019.
  * [46] Irma T. Ugalde, Samuel Prater, Marylou Cardenas-Turanzas, Nipa Sanghani, Donna Mendez, John Peacock, Grace Guvernator, Christine Koerner, and Myron Allukian.  Chest x-ray vs. computed tomography of the chest in pediatric blunt trauma.  Journal of Pediatric Surgery, 56(5):1039–1046, 2021.
  * [47] Pascal Vincent, Hugo Larochelle, Yoshua Bengio, and Pierre-Antoine Manzagol.  Extracting and composing robust features with denoising autoencoders.  In Proceedings of the 25th international conference on Machine learning, pages 1096–1103, 2008.
  * [48] Linda Wang, Zhong Qiu Lin, and Alexander Wong.  Covid-net: a tailored deep convolutional neural network design for detection of covid-19 cases from chest x-ray images.  Scientific Reports, 10(1):19549, Nov 2020.
  * [49] Xiaosong Wang, Yifan Peng, Le Lu, Zhiyong Lu, Mohammadhadi Bagheri, and Ronald M Summers.  Chestx-ray8: Hospital-scale chest x-ray database and benchmarks on weakly-supervised classification and localization of common thorax diseases.  pages 2097–2106, 2017.
  * [50] Zhirong Wu, Yuanjun Xiong, Stella X Yu, and Dahua Lin.  Unsupervised feature learning via non-parametric instance discrimination.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3733–3742, 2018.
  * [51] Zhenda Xie, Zheng Zhang, Yue Cao, Yutong Lin, Jianmin Bao, Zhuliang Yao, Qi Dai, and Han Hu.  Simmim: A simple framework for masked image modeling.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9653–9663, 2022.
  * [52] Richard Zhang, Phillip Isola, and Alexei A Efros.  Colorful image colorization.  In European conference on computer vision, pages 649–666. Springer, 2016.


$\displaystyle=v_{1}-2-\frac{e_{1}-1}{m_{2}(H_{1})}$ $\displaystyle=0.$

where the second equality follows from $m_{2}(H_{1},H_{2})=m_{2}(H_{1})$ (see
Proposition 1.7) and the last equality follows from $H_{1}$ being (strictly)
$2$-balanced.  $\square$

As in Case 1, when we have a degenerate iteration $i$, the structure of
$F_{i+1}$ depends not just on $F_{i}$ but also on the structure of
$G^{\prime}$. Indeed, if $F_{i}$ is extended by a copy $L$ of $H_{2}$ in line
4 of Extend, then $L$ could intersect $F_{i}$ in a multitude of ways.
Moreover, there may be several copies of $H_{2}$ that satisfy the condition in
line 2 of Extend. One could say the same for graphs added in line 6 of Extend.
Thus, as in Case 1, degenerate iterations cause us difficulties since they
enlarge the family of graphs algorithm Grow-Alt can return. However, we will
show that at most a constant number of degenerate iterations can happen before
algorithm Grow-Alt terminates, allowing us to bound from above sufficiently
well the number of non-isomorphic graphs Grow-Alt can return. Pivotal in
proving this is the following claim, analogous to Claim 6.3.

######  Claim 7.3.

There exists a constant $\kappa=\kappa(H_{1},H_{2})>0$ such that if iteration
$i$ of the while-loop in procedure Grow is degenerate then we have

$\lambda(F_{i+1})\leq\lambda(F_{i})-\kappa.$

Compared to the proof of Claim 6.3, the proof of Claim 7.3 is relatively
straightforward.

Proof.  Let $F:=F_{i}$ be the graph before the operation in line 15 (of Grow-
Alt) is carried out and let $F^{\prime}:=F_{i+1}$ be the output from line 15.
We aim to show there exists a constant $\kappa=\kappa(H_{1},H_{2})>0$ such
that

$\lambda(F)-\lambda(F^{\prime})=v(F)-v(F^{\prime})-\frac{e(F)-e(F^{\prime})}{m_{2}(H_{1},H_{2})}\geq\kappa$

whether Extend attached a graph $L\in\mathcal{L}_{G^{\prime}}$ or
$R\in\mathcal{R}_{G^{\prime}}$ to $F$. We need only consider the case when
$L\in\mathcal{L}_{G^{\prime}}$ is the graph added by Extend in this non-
degenerate iteration $i$ of the while-loop, as the proof of the
$R\in\mathcal{R}_{G^{\prime}}$ case is identical. Let
$V_{L^{\prime}}:=V(F)\cap V(L)$ and $E_{L^{\prime}}:=E(F)\cap E(L)$ and set
$v_{L^{\prime}}:=|V_{L^{\prime}}|$ and $e_{L^{\prime}}:=|E_{L^{\prime}}|$. Let
${L^{\prime}}$ be the graph on vertex set $V_{L^{\prime}}$ and edge set
$E_{L^{\prime}}$. By Claim 7.1, we have $e(F^{\prime})>e(F)$, hence
${L^{\prime}}$ is a proper subgraph of $H_{2}$. Also, observe that since
iteration $i$ was degenerate, we must have that $v_{L^{\prime}}\geq 3$. Let
$F_{\hat{L}}$ be the graph produced by a non-degenerate iteration at $e$ with
a copy $\hat{L}$ of $H_{2}$, that is, $F_{\hat{L}}:=F\cup\hat{L}$ and
$V(F)\cap V(\hat{L})=e$. Our strategy is to compare $F^{\prime}$ with
$F_{\hat{L}}$. By Claim 7.2, $\lambda(F)=\lambda(F_{\hat{L}})$. Thus, since
$m_{2}(H_{1},H_{2})=m_{2}(H_{2})$, we have

(28)
$\lambda(F)-\lambda(F^{\prime})=\lambda(F_{\hat{L}})-\lambda(F^{\prime})=v_{2}-2-(v_{2}-v_{L^{\prime}})-\frac{(e_{2}-1)-(e_{2}-e_{L^{\prime}})}{m_{2}(H_{1},H_{2})}=v_{L^{\prime}}-2-\frac{e_{L^{\prime}}-1}{m_{2}(H_{1},H_{2})}.$

If $e_{L^{\prime}}=1$, then since $v_{L^{\prime}}\geq 3$ we have
$\lambda(F)-\lambda(F^{\prime})\geq 1$. So assume $e_{L^{\prime}}\geq 2$.
Since $H_{2}$ is _strictly_ $2$-balanced and $L^{\prime}$ is a proper subgraph
of $H_{2}$ with $e_{L^{\prime}}\geq 2$ (that is, $L^{\prime}$ is not an edge),
we have that

(29) $\frac{v_{L^{\prime}}-2}{e_{L^{\prime}}-1}>\frac{1}{m_{2}(H_{2})}.$

Using (28), (29) and that $e_{L^{\prime}}\geq 2$ and
$m_{2}(H_{1},H_{2})=m_{2}(H)$, we have

$\lambda(F)-\lambda(F^{\prime})=(e_{L^{\prime}}-1)\left(\frac{v_{L^{\prime}}-2}{e_{L^{\prime}}-1}-\frac{1}{m_{2}(H_{2})}\right)>0.$

Letting
$\delta:=\frac{1}{2}\min\left\\{(e_{L^{\prime}}-1)\left(\frac{v_{L^{\prime}}-2}{e_{L^{\prime}}-1}-\frac{1}{m_{2}(H_{2})}\right):L^{\prime}\subset
H_{2},e_{L^{\prime}}\geq 2\right\\}$, we take

$\kappa:=\min\\{1,\delta\\}.$

$\square$

Together, Claims 7.2 and 7.3 yield the following claim (analogous to Claim
6.4).

######  Claim 7.4.

There exists a constant $q_{2}=q_{2}(H_{1},H_{2})$ such that algorithm Grow-
Alt performs at most $q_{2}$ degenerate iterations before it terminates,
regardless of the input instance $G^{\prime}$.

Proof.  Analogous to the proof of Claim 6.4.  $\square$

For $0\leq d\leq t\leq\lceil\ln(n)\rceil$, let
$\mathcal{F}_{\textsc{Alt}}(t,d)$ denote a family of representatives for the
isomorphism classes of all graphs $F_{t}$ that algorithm Grow-Alt can possibly
generate after exactly $t$ iterations of the while-loop with exactly $d$ of
those $t$ iterations being degenerate. Let
$f_{\textsc{Alt}}(t,d):=|\mathcal{F}_{\textsc{Alt}}(t,d)|$.

######  Claim 7.5.

There exist constants $C_{0}=C_{0}(H_{1},H_{2})$ and $A=A(H_{1},H_{2})$ such
that

$f_{\textsc{Alt}}(t,d)\leq\lceil\ln(n)\rceil^{(C_{0}+1)d}\cdot A^{t-d}$

for $n$ sufficiently large.

Proof.  Analogous to the proof of Claim 6.5.  $\square$

Let $\mathcal{F}_{\textsc{Alt}}=\mathcal{F}_{\textsc{Alt}}(H_{1},H_{2},n)$ be
a family of representatives for the isomorphism classes of _all_ graphs that
can be outputted by Grow-Alt (whether Grow-Alt enters the while-loop or not).
Note that the proof of the following claim requires Conjecture 1.8 to be true;
in particular, we need that $\hat{\mathcal{A}}$ is finite when
$m_{2}(H_{1})=m_{2}(H_{2})$.

######  Claim 7.6.

There exists a constant $b=b(H_{1},H_{2})>0$ such that for all $p\leq
bn^{-1/m_{2}(H_{1},H_{2})}$, $G_{n,p}$ does not contain any graph from
$\mathcal{F}_{\textsc{Alt}}(H_{1},H_{2},n)$ a.a.s.

Proof.  Analogous to the proof of Claim 6.6.  $\square$

Proof of Lemma 5.5: Case 2. Suppose that the call to Asym-Edge-Col$(G)$ gets
stuck for some graph $G$, and consider $G^{\prime}\subseteq G$ at this moment.
Then Grow-Alt$(G^{\prime})$ returns a copy of a graph
$F\in\mathcal{F}_{\textsc{Alt}}(H_{1},H_{2},n)$ that is contained in
$G^{\prime}\subseteq G$. By Claim 7.6, this event a.a.s. does not occur in
$G=G_{n,p}$ with $p$ as claimed. Thus Asym-Edge-Col does not get stuck a.a.s.
and, by Lemma 5.3, finds a valid edge-colouring for $H_{1}$ and $H_{2}$ of
$G_{n,p}$ with $p\leq bn^{-1/m_{2}(H_{1},H_{2})}$ a.a.s.∎

##  8\. Proof of Theorem 1.10

Since $H_{1}$ and $H_{2}$ are regular graphs, let $\ell_{1}$ be the degree of
every vertex in $H_{1}$ and $\ell_{2}$ be the degree of every vertex in
$H_{2}$. We begin using an approach employed in [10] and [14]. Let $A$ be a
$2$-connected graph such that $A\in\mathcal{C}^{*}(H_{1},H_{2})$ if
$m_{2}(H_{1})>m_{2}(H_{2})$ and $A\in\mathcal{C}(H_{1},H_{2})$ if
$m_{2}(H_{1})=m_{2}(H_{2})$. In both cases, $A\in\mathcal{C}(H_{1},H_{2})$.
Then, since every vertex is contained in a copy of $H_{1}$ and a copy of
$H_{2}$ whose edge-sets intersect in exactly one edge, we must have that
$\delta(A)\geq\ell_{1}+\ell_{2}-1$. Hence

(30) $d(A)=\frac{e_{A}}{v_{A}}\geq\frac{\ell_{1}+\ell_{2}-1}{2}.$

We aim to show $d(A)>m_{2}(H_{1},H_{2})+\varepsilon$ for some
$\varepsilon=\varepsilon(H_{1},H_{2})>0$. Indeed, if there exists
$\varepsilon=\varepsilon(H_{1},H_{2})>0$ such that for all such graphs $A$ we
have $d(A)>m_{2}(H_{1},H_{2})+\varepsilon$ then
$\hat{\mathcal{A}}(H_{1},H_{2},\varepsilon)=\emptyset$, and so Conjecture 1.8
holds trivially for $H_{1}$ and $H_{2}$.

Since $m_{2}(H_{1})\geq m_{2}(H_{2})>1$, we have that $H_{1}$ and $H_{2}$
cannot be matchings. Hence $\ell_{1},\ell_{2}\geq 2$. Also, observe that

(31)
$m_{2}(H_{1},H_{2})=\frac{e_{1}}{v_{1}-2+\frac{1}{m_{2}(H_{2})}}=\frac{\frac{v_{1}\ell_{1}}{2}}{v_{1}-2+\frac{v_{2}-2}{\frac{v_{2}\ell_{2}}{2}-1}}=\frac{v_{1}\ell_{1}}{2v_{1}-4+\frac{4v_{2}-8}{v_{2}\ell_{2}-2}}.$

Furthermore,

(32) $\displaystyle\frac{\ell_{1}+\ell_{2}-1}{2}>m_{2}(H_{1},H_{2})$
$\displaystyle\iff$
$\displaystyle\ell_{1}+\ell_{2}-1>\frac{v_{1}v_{2}\ell_{1}\ell_{2}-2v_{1}\ell_{1}}{2v_{1}v_{2}\ell_{2}-4v_{2}\ell_{2}-4v_{1}+4v_{2}}$
$\displaystyle\iff$
$\displaystyle\ell_{1}+\ell_{2}-1>\frac{2v_{1}v_{2}\ell_{1}\ell_{2}-4v_{1}\ell_{1}}{2v_{1}v_{2}\ell_{2}-4v_{2}\ell_{2}-4v_{1}+4v_{2}}$
$\displaystyle\iff$ $\displaystyle
0<v_{1}v_{2}\ell_{2}(\ell_{2}-1)-2v_{1}(\ell_{2}-1)-2v_{2}\ell_{1}(\ell_{2}-1)-2v_{2}(\ell_{2}-1)^{2}$
$\displaystyle\iff$ $\displaystyle
0<v_{1}v_{2}\ell_{2}-2v_{1}-2v_{2}\ell_{1}-2v_{2}\ell_{2}+2v_{2},$

where in the last implication we used that $\ell_{2}\geq 2$.

Let
$f(v_{1},v_{2},\ell_{1},\ell_{2}):=v_{1}v_{2}\ell_{2}-2v_{1}-2v_{2}\ell_{1}-2v_{2}\ell_{2}+2v_{2}$.
Observe that $\ell_{1}\leq v_{1}-1$. Hence
$-2v_{2}\ell_{1}\geq-2v_{1}v_{2}+2v_{2}$ and we have

$f(v_{1},v_{2},\ell_{1},\ell_{2})\geq
v_{1}v_{2}(\ell_{2}-2)-2v_{1}+4v_{2}-2v_{2}\ell_{2}.$

Let
$g(v_{1},v_{2},\ell_{2}):=v_{1}v_{2}(\ell_{2}-2)-2v_{1}+4v_{2}-2v_{2}\ell_{2}$
so $f(v_{1},v_{2},\ell_{1},\ell_{2})\geq g(v_{1},v_{2},\ell_{2})$. Observe
that, since $\ell_{1},\ell_{2}\geq 2$, we have that $v_{1},v_{2}\geq 3$. If
$\ell_{2}=2$, then $g(v_{1},v_{2},2)=-2v_{1}<0$. However, if $\ell_{2}\geq 3$,
then since $v_{1},v_{2}\geq 3$, we have that

$\frac{dg}{dv_{1}}=v_{2}(\ell_{2}-2)-2>0;$
$\frac{dg}{dv_{2}}=v_{1}(\ell_{2}-2)+4-2\ell_{2}=(v_{1}-2)(\ell_{2}-2)>0;$
$\frac{dg}{d\ell_{2}}=v_{1}v_{2}-2v_{2}=v_{2}(v_{1}-2)>0.$

Further,

$g(4,5,3)=20-8+20-30=2>0.$

Thus, for all $v_{1}\geq 4,v_{2}\geq 5,\ell_{2}\geq 3$, we have that

$f(v_{1},v_{2},\ell_{1},\ell_{2})\geq g(v_{1},v_{2},\ell_{2})\geq
g(4,5,3)=2>0.$

Hence, by (30)-(32), we have that there exists a constant
$\varepsilon:=\varepsilon(H_{1},H_{2})>0$ such that

$d(A)>m_{2}(H_{1},H_{2})+\varepsilon.$

Thus we only have left the cases when $v_{1}=3$, $v_{2}\leq 4$ or
$\ell_{2}=2$.

######  Case 1.

$\ell_{2}=2$.

Then $H_{2}$ is a cycle and

$f(v_{1},v_{2},\ell_{1},2)=2v_{1}v_{2}-2v_{1}-2v_{2}\ell_{1}-2v_{2}.$

Observe that $\ell_{1}\leq v_{1}-2$, as otherwise $H_{1}$ is a clique,
contradicting that $(H_{1},H_{2})$ is not a pair of a clique and a cycle. Thus
$-\ell_{1}\geq-(v_{1}-2)$. Then, since we excluded considering when $H_{2}$ is
a cycle and $H_{1}$ is a graph with $v_{1}=|V(H_{1})|\geq|V(H_{2})|=v_{2}$, we
have that $v_{2}>v_{1}$, and so

$f(v_{1},v_{2},\ell_{1},2)\geq 2(v_{2}-v_{1})\geq 2>0.$

Hence by (30)-(32), we have that there exists a constant
$\varepsilon:=\varepsilon(H_{1},H_{2})>0$ such that
$d(A)>m_{2}(H_{1},H_{2})+\varepsilon$.

######  Case 2.

$v_{1}=3$.

Then $H_{1}=K_{3}$ and $\ell_{1}=2$. Thus

$f(3,v_{2},2,\ell_{2})=v_{2}(\ell_{2}-2)-6.$

We can assume $\ell_{2}\geq 3$, as otherwise we are in Case 1. Observe that we
cannot have that $v_{2}=6$ and $\ell_{2}\geq 3$. Indeed, when $\ell_{2}=3$,
one can check that the only strictly $2$-balanced $3$-regular graph on 6
vertices is $K_{3,3}$. But then $(H_{1},H_{2})=(K_{3},K_{3,3})$, which is a
pair of graphs we excluded from consideration.

When $\ell_{2}\geq 4$, we have that $m_{2}(H_{2})>m_{2}(H_{1})$, contradicting
that our choice of $H_{1}$ and $H_{2}$ meet the criteria in Conjecture 1.8. If
$v_{2}\leq 5$, then since also $\ell_{2}\geq 3$ we must have that $H_{2}$ is a
copy of $K_{4}$ or $K_{5}$.191919There exists no graph with both odd
regularity and odd order. But then $m_{2}(H_{2})>m_{2}(H_{1})$.

Hence $v_{2}\geq 7$ and $\ell_{2}\geq 3$. Thus $f(3,v_{2},2,\ell_{2})>0$ and,
as before, we conclude that there exists a constant
$\varepsilon:=\varepsilon(H_{1},H_{2})>0$ such that
$d(A)>m_{2}(H_{1},H_{2})+\varepsilon.$

######  Case 3.

$v_{2}\leq 4$.

Still assuming $\ell_{2}\geq 3$, we have that $H_{2}=K_{4}$, $v_{2}=4$ and
$\ell_{2}=3$. If $v_{1}\geq\ell_{1}+2$, then

$f(v_{1},4,\ell_{1},3)=10v_{1}-8(\ell_{1}+2)\geq 2(\ell_{1}+2)>0.$

If $v_{1}=\ell_{1}+1$, then $H_{1}$ is a clique. Since $H_{1}$ and $H_{2}$
meet the criteria in Conjecture 1.8, we must have that $v_{1}\geq 5$.
Therefore

$f(v_{1},4,\ell_{1},3)=10v_{1}-8(\ell_{1}+2)=2v_{1}-8\geq 2>0.$

Then, as before, there exists a constant
$\varepsilon:=\varepsilon(H_{1},H_{2})>0$ such that
$d(A)>m_{2}(H_{1},H_{2})+\varepsilon$, as desired.

##  9\. Concluding remarks

In [14], the value of $\varepsilon$ was set at $0.01$ for _every_ pair of
cliques, that is, the value of $\varepsilon$ did not depend explicitly on the
graphs $H_{1}$ and $H_{2}$. It would be interesting to know if there exists a
single value of $\varepsilon$ satisfying Conjecture 1.8 for _all_ suitable
pairs of graphs $H_{1}$ and $H_{2}$.

Let us discuss why we use Grow-Alt when $m_{2}(H_{1})=m_{2}(H_{2})$ instead of
Grow. The main reason is that when attaching a copy of $H_{1}$ precisely at an
edge202020That is, $e_{1}-1$ edges and $v_{1}-2$ vertices are added. of
$F_{i}$ to create $F_{i+1}$ \- for some iteration $i$ during Grow or Grow-Alt
\- we have $\lambda(F_{i})=\lambda(F_{i+1})$ if $m_{2}(H_{1})=m_{2}(H_{2})$
and $\lambda(F_{i})>\lambda(F_{i+1})$ if $m_{2}(H_{1})>m_{2}(H_{2})$. We would
say that iteration $i$ was a non-degenerate iteration if
$m_{2}(H_{1})=m_{2}(H_{2})$ and a degenerate iteration if
$m_{2}(H_{1})>m_{2}(H_{2})$. That is, if we were to use Grow instead of Grow-
Alt then the number of possible non-degenerate iterations would depend on the
size of $F_{i}$ and grow too quickly.

Connected to this observation is why for $A\in\hat{\mathcal{A}}$ we take
$A\in\mathcal{C}$ when $m_{2}(H_{1})=m_{2}(H_{2})$, rather than
$A\in\mathcal{C}^{*}$.212121As mentioned at the end of Section 1.4.3. In the
proof of Claim 7.1, we need to conclude that $F_{i}$ is not in
$\hat{\mathcal{A}}$ in order to conclude Eligible-Edge-Alt is always
successful. As part of concluding this, we need that $F_{i}\in\mathcal{C}$,
which we get by assuming for a contradiction that there is no edge in $F_{i}$
eligible for extension in Grow-Alt. Hence, if for all $A\in\hat{\mathcal{A}}$
one sets $A\in\mathcal{C}^{*}$ when $m_{2}(H_{1})=m_{2}(H_{2})$, then one
needs to conclude that $F_{i}\in\mathcal{C}^{*}$. This means that we must
assume for a contradiction that for every edge $e\in E(F_{i})$ there exists
$L\in L_{F_{i}}^{*}$ such that $e\in E(L)$. Such an argument then requires us
to change from using Eligible-Edge-Alt to Eligible-Edge in Grow-Alt in order
to arrive at the correct contradiction in the proof. But now
Extend$(F_{i},e,G^{\prime})$ in Grow-Alt may fail to add an edge as it is
possible that every $L\in\mathcal{L}_{G^{\prime}}^{*}$ containing $e$ has its
copies of $H_{1}$ and $H_{2}$ intersecting at $e$ both contained fully in
$F_{i}$, that is, we cannot guarantee that in every iteration $i$ of the
while-loop of Grow-Alt that $e(F_{i+1})>e(F_{i})$.

In order to overcome this we would need to replace procedure Extend with a
procedure similar to procedure Extend-L, which is used in Grow. If we used
Extend-L, then the copy $L$ of $H_{1}$ could be fully contained in $F_{i}$ and
one of its copies $R^{\prime}$ of $H_{2}$ appended to it could contain
precisely one edge of $F_{i}$ and two vertices of $F_{i}$, with every other
appended copy of $H_{2}$ fully contained in $F_{i}$. This would then have to
be considered a non-degenerate iteration for Grow-Alt as
$\lambda(F_{i})=\lambda(F_{i+1})$. But, importantly,
Extend-L$(F_{i},e,G^{\prime})$ depends on the structure of $G^{\prime}$, not
on the structure of $F_{i}$. Thus $R^{\prime}$ could be attached at a number
of edges of $F_{i}$. This would increase the number of possible non-degenerate
iterations too much.

What procedure similar to Extend-L do we choose then? One possibility would be
to attach a copy $L$ of $H_{2}$ with copies of $H_{1}$ appended to _every one_
of its edges $e^{\prime}$, but this procedure runs into the same problem as
Extend-L. Overall, this discussion shows how difficult - and maybe impossible
- it would be to prove the $m_{2}(H_{1})=m_{2}(H_{2})$ case of Lemma 5.5 while
stipulating that when $A\in\hat{\mathcal{A}}$ we have $A\in\mathcal{C}^{*}$.

Also, in [14], Marciniszyn, Skokan, Spöhel and Steger note that they do not
know whether $\mathcal{C}^{*}(H_{1},H_{2})=\mathcal{C}(H_{1},H_{2})$ or not
for any pair of cliques. The author is unaware if this has been resolved for
any pair of graphs. According with the definition of $\hat{\mathcal{A}}$,
perhaps it is the case that
$\mathcal{C}^{*}(H_{1},H_{2})=\mathcal{C}(H_{1},H_{2})$ whenever
$m_{2}(H_{1})=m_{2}(H_{2})$?

Note that our method in this paper does not completely extend to when
$m_{2}(H_{2})=1$. Indeed, in this case $H_{2}$ is a forest and so not
$2$-connected, a property which is specifically used in the proofs of Claims
6.1, 6.6, 7.1 and 7.6. In the proofs of Claims 6.1 and 7.1 we require that
$F_{i}$ is $2$-connected for each $i>0$. However, if the last iteration of the
while-loop of either Grow or Grow-Alt was non-degenerate when constructing
$F_{i}$, then $F_{i}$ is certainly not $2$-connected if $H_{2}$ is a tree. A
similar problem occurs at the beginning of the proofs of Claims 6.6 and 7.6 if
$T\cong H_{2}$.

##  10\. Acknowledgements

The author is grateful to Andrew Treglown for suggesting working on the
$0$-statement of the Kohayakawa-Kreuter Conjecture and to Robert Hancock and
Andrew Treglown for providing many helpful comments on a draft of this paper.
The author also thanks the referee for their comments and suggestions.

## References

  * [1] F. Chung and R. Graham, Erdős on graphs, AK Peters, Wellesley, MA, 1998 (His legacy of unsolved problems).
  * [2] J. Folkman, Graphs with monochromatic complete subgraphs in every edge coloring, _SIAM J. Appl. Math._ 18 (1970), 19-24.
  * [3] P. Frankl and V. Rödl, Large triangle-free subgraphs in graphs without $K_{4}$, _Graphs Combin._ 2(2) (1986), 135–144.
  * [4] E. Friedgut and M. Krivelevich, Sharp thresholds for certain Ramsey properties of random graphs, _Random Structures Algorithms_ 17(1) (2000), 1-19.
  * [5] E. Friedgut, V. Rödl, A. Ruciński and P. Tetali, A sharp threshold for random graphs with a monochromatic triangle in every edge coloring, _Mem. Amer. Math. Soc._ 179(845) (2006), vi+66.
  * [6] L. Gugelmann, R. Nenadov, Y. Person, N. Škorić, A. Steger and H. Thomas, Symmetric and asymmetric Ramsey properties in random hypergraphs, _Forum Math. Sigma_ 5(e28) (2017), 47 pages.
  * [7] R. Hancock, K. Staden and A. Treglown, Independent sets in hypergraphs and Ramsey properties of graphs and the integers, _SIAM J. Discrete Math._ 33 (2019), 153-188.
  * [8] S. Janson, T. Łuczak and A. Ruciński, Random Graphs, _Wiley-Interscience Series in Discrete Mathematics and Optimization (Wiley-Interscience, 2000)_.
  * [9] J.H. Kim, The Ramsey number $R(3,t)$ has order of magnitude $t^{2}/\log t$, _Random Structures Algorithms_ 7 (1995), 173-207.
  * [10] Y. Kohayakawa and B. Kreuter, Threshold functions for asymmetric Ramsey properties involving cycles, _Random Structures Algorithms_ 11 (1997), 245-276.
  * [11] Y. Kohayakawa, M. Schacht and R. Spöhel, Upper bounds on probability thresholds for asymmetric Ramsey properties, _Random Structures Algorithms_ 44(1) (2014), 1-28.
  * [12] A. Liebenau, L. Mattos, W. Mendonça and J. Skokan, Asymmetric Ramsey properties of random graphs for cliques and cycles, arXiv:2010.11933.
  * [13] T. Łuczak, A. Ruciński and B. Voigt, Ramsey properties of random graphs, _J. Combin. Theory Ser. B_ 56 (1992), 55-68.
  * [14] M. Marciniszyn, J. Skokan, R. Spöhel and A. Steger, Asymmetric Ramsey properties of random graphs involving cliques, _Random Structures Algorithms_ 34(4) (2009), 419-453.
  * [15] F. Mousset, R. Nenadov and W. Samotij, Towards the Kohayakawa–Kreuter conjecture on asymmetric Ramsey properties, _Combin. Probab. Comput._ 29(6) (2020), 943-955.
  * [16] R. Nenadov and A. Steger, A short proof of the random Ramsey theorem, _Combin. Probab. Comput._ 25(1) (2016), 130-144.
  * [17] J. Nešetřil and V. Rödl, The Ramsey property for graphs with forbidden complete subgraphs, _J. Combin. Theory Ser. B_ 20 (1976), 243-249.
  * [18] F.P. Ramsey, On a problem of formal logic, _Proc. Lon. Math. Soc._ 30 (1930), 264-286.
  * [19] V. Rödl and A. Ruciński, Lower bounds on probability thresholds for Ramsey properties, _Combinatorics, Paul Erdos is eighty, Vol. 1, Bolyai Soc. Math. Stud., János Bolyai Math. Soc., Budapest_ (1993), 317-346.
  * [20] V. Rödl and A. Ruciński, Random graphs with monochromatic triangles in every edge coloring, _Random Structures Algorithms_ 5(2) (1994), 253-270.
  * [21] V. Rödl and A. Ruciński, Threshold functions for Ramsey properties, _J. Amer. Math. Soc._ 8 (1995), 917-942.
  * [22] M. Schacht and F. Schulenburg, Sharp thresholds for Ramsey properties of strictly balanced nearly bipartite graphs, _Random Structures Algorithms_ 52(1) (2018), 3-40.