# Photonic Accelerators for Image Segmentation in
Autonomous Driving and Defect Detection

Lakshmi Nair*, David Widemann, Brad Turcott,
Nick Moore, Alexandra Wleklinski, Darius Bunandar *Email:
<EMAIL_ADDRESS>Lightmatter Inc.
Boston, Massachusetts, USA  Ioannis Papavasileiou†, Shihu Wang, Eric Logan
<EMAIL_ADDRESS>Corning Inc.
Corning, New York, USA

###### Abstract

Photonic computing promises faster and more energy-efficient deep neural
network (DNN) inference than traditional digital hardware. Advances in
photonic computing can have profound impacts on applications such as
autonomous driving and defect detection that depend on fast, accurate and
energy efficient execution of image segmentation models. In this paper, we
investigate image segmentation on photonic accelerators to explore: a) the
types of image segmentation DNN architectures that are best suited for
photonic accelerators, and b) the throughput and energy efficiency of
executing the different image segmentation models on photonic accelerators,
along with the trade-offs involved therein. Specifically, we demonstrate that
certain segmentation models exhibit negligible loss in accuracy (compared to
digital float32 models) when executed on photonic accelerators, and explore
the empirical reasoning for their robustness. We also discuss techniques for
recovering accuracy in the case of models that do not perform well. Further,
we compare throughput (inferences-per-second) and energy consumption estimates
for different image segmentation workloads on photonic accelerators. We
discuss the challenges and potential optimizations that can help improve the
application of photonic accelerators to such computer vision tasks.

###### Index Terms:

Photonic Computing, Image Segmentation, Deep Learning, Computer Vision

##  I Introduction

Semantic segmentation of imagery is an important computer vision task for
various applications ranging from robotics [1] and autonomous driving [2] to
defect detection during manufacturing processes [3], with an increasing number
of models being released for such tasks even today [4]. Over the past decade,
DNNs for image segmentation have evolved from convolutional neural networks
(CNNs) [5, 6, 7] to transformer-based networks that outperform CNNs on these
tasks [8]. However, the sizes of these DNNs and the amount of computation
required for training such models have outpaced Moore’s law [9]. In order to
address the problems of growing model latency and energy usage, researchers
have turned to the use of photonic computing for quickly and efficiently
performing matrix-vector products (MVPs), which are the primary computations
in DNNs [10, 11]. While existing work has explored the use of FPGA (field-
programmable gate array) based accelerators for autonomous driving, for
achieving low latency [12, 13, 14], recent advances in photonic computing are
yet to be explored in this domain.

Figure 1: The relative mIoU (accuracy), memory, energy cost, and throughput of
five DNN models performing image segmentation on three datasets using a photo-
core (photonic compute unit). Vision transformers, like Swin (maskformer), are
more accurate out-of-the-box at the cost of requiring more energy and memory
than their CNN counterparts.

In this paper, we focus on image segmentation workloads on photonic
accelerators for autonomous driving and defect detection in manufacturing –
two important applications that require fast, accurate and real-time image
segmentation capabilities [15, 16]. For this work, we do not contribute our
own accelerator design. Instead, we focus on the implications of executing
image segmentation workloads on existing photonic devices, by basing our work
on a recently proposed photonic compute core, called the photo-core [17].
While there is some variability among photonic accelerator designs, we believe
that the findings of this work will offer common insights and challenges
associated with executing image segmentation DNNs on photonic accelerators.
Specifically, we make the following contributions: a) we analyze recent image
segmentation DNNs on the photo-core, alongside techniques such as fine-tuning
for accuracy recovery; b) we identify the DNN architectures that achieve good
out-of-the-box (OOB) accuracy compared to float32. We further investigate the
empirical reasons for the accuracy robustness of some architectures over
others, in order to guide the design of future DNNs specialized for photonic
accelerators; c) we investigate the relative throughput and power estimates
for the image segmentation models on the photo-core to characterize the
relative trade-offs for the DNNs on photonic devices. To our knowledge, this
is the first work to investigate image segmentation on photonic accelerators,
with the goal of providing insights for computer vision on photonic hardware.

Figure 2: High-level overview of applying ABFP with the photo-core unit. Input
weights and activations are scaled at per-vector granularity and the quantized
matrices are mutliplied on the photocore. The output result is then amplified,
quantized at the output ADC, and de-quantized for accumulation in digital.

##  II Related Work

###  II-A ML applications on accelerators

Recently, digital machine learning accelerators have attained significant
interest owing to the potential speed benefits that they offer for ML
workloads. Since the primary computational component of DNNs is matrix
multiplication, specialty ASICS such as Nvidia’s Tensor Cores [18] and
Google’s TPU [19] have been developed to accelerate matrix multiplication.
However, the power consumption of these systems has been increasing with each
generation, and their throughput has not improved correspondingly [20]. As a
result, recent approaches have proposed photonic accelerator designs that
demonstrate higher throughput with lower energy profiles, offsetting the
disadvantages of more traditional systems [17, 21, 22]. However, photonic
designs present numerous challenges associated with noisy electro-optical
components (e.g., thermal, shot noise) alongside their reduced precision that
impact the performance of DNNs [23].

Prior work has looked into performing high-speed image classification [24, 25]
and natural language processing (NLP) [26] on photonic accelerators. For image
classification, prior work demonstrated inference speeds of under 570 ps with
high accuracy, for classification of hand-written letters [24]. Their work
used a clock-less processing of data thus eliminating analog-to-digital
conversions to improve throughput and energy efficiency. Further work
demonstrated an integrated metasystem, in contrast to conventional photonics
integrated circuits, for high accuracy and throughput on the MNIST dataset
[25]. For NLP, prior work demonstrated a novel design of photonic extreme
learning machines (PELM) for performing sentiment analysis on the Image Movie
Database [27].

For image segmentation, prior work has looked at performing real-time image
segmentation on an FPGA-based accelerator [12]. They demonstrate low latency
of about 3ms with less than 30% resource usage, while maintaining accuracy on
the Cityscapes dataset. Prior work has also looked at the use of FPGA
accelerator for performing real-time skin segmentation, demonstrating that no
more than 88% of the system resources were used in the process [14]. In the
context of designing more efficient image segmentation models for
accelerators, prior work has developed the Fast Spatial Feature Network
(FSFNet) that achieved high throughput and accuracy on the Cityscapes dataset
[13]. Self-driving and defect detection applications rely heavily on their
capacity to segment images quickly and accurately. Whilst most research
focuses on digital accelerators, we investigate image segmentation on photonic
accelerators.

###  II-B Mitigating Quantization & Analog Noise Error

Similar to fully digital systems, one of the key challenges of executing DNNs
on photonic accelerators stem from the reduced precision supported by the
electro-optical components, such as the analog-to-digital converters (ADCs)
and digital-to-analog converters (DACs) [28]. While using low precision data
types can significantly increase DNN throughput, the model’s accuracy
degradation can be too large to accomplish the task at hand [29]. To address
this, fine-tuning and post-training quantization techniques have been used to
improve the accuracy of models running low precision inference [29].

Most recently, the approach of dynamically scaling vectors, such as VS-Quant
[30] and Adaptive Block Floating Point (ABFP) [28], have emerged as a
potential solution to maintaining accuracy at low precision. Both ABFP and VS-
Quant follow a similar approach, by computing scaling factors (i.e., the
maximum magnitude) over vectors of length $n$, with VS-Quant adding an
additional level of quantization for the scale factors themselves. In this
paper, we explore the use of ABFP in photonic accelerators as a method of
obtaining good out-of-the-box (OOB) performance for image segmentation. We do
not explore the use of a second-level quantization of the scale factors
themselves (we leave the scales in bfloat16), although the second-level
quantization could be utilized in the context of accelerator designs for
further improvements [31].

Among training methods, for both VS-Quant and ABFP, the authors have explored
the use of fine-tuning to further boost model accuracy. For ABFP, the authors
propose using Differential Noise Fine-tuning (DNF) as a faster alternative to
the typical quantization-aware training approach. In the case of image
segmentation models that do not perform well OOB, we explore the use of DNF to
recover model accuracy. Note that in this case, fine-tuning is performed off-
device and the fine-tuned model is deployed on the device for inference only.

###  II-C Defect Detection

Defect detection is used to enhance manufacturing process efficiency, and to
ensure the adherence of parts to specifications. Existing methods for defect
detection include deep learning for image classification [32, 33], object
detection[34], or instance segmentation[35, 36, 37, 38]. Defect detection in
real-time on edge devices has particularly gained significant attention for
its advantages including reduced latency, improved privacy, enhanced
reliability, and efficient bandwidth utilization [39]. Techniques for
deploying defect detection on edge devices include approaches like transfer
learning [40], model compression [41], pruning and quantization [42] and
federated learning [40] to reduce the model complexity and memory usage.
However, prior work has not looked at the deployment of defect detection
models on photonic devices.

##  III Methods

In this section, we discuss the implementation details of the photo-core [17]
that we use as a reference for our experiments. We then describe the two
accuracy recovery methods explored in this work, namely Adaptive Block
Floating Point (ABFP) and Differential Noise Fine-tuning (DNF) [28].

###  III-A Hardware Design

We investigate the performance of image segmentation DNNs on photonic devices,
by evaluating the accuracy, throughput and energy implications of executing
the matrix multiplication operations on the photo-core, while performing all
the non-linear operations (such as activations) in high-precision digital.
Within the photo-core, a weight-stationary approach to computing matrix-vector
products (MVPs) is adopted. The weights and input activations of each layer
are first unfolded into 2D matrices if necessary (e.g., using kn2row [43] for
convolutions). Since the photo-core has a fixed size of $n\times n$, weight
matrices that are bigger/smaller than $n\times n$ are zero-padded to a
multiple of $n$ (called tile size) and then tiled into $n\times n$ sized sub-
matrices. The input vectors are similarly zero-padded and tiled. Each tile or
vector is then loaded onto the photo-core one-by-one. The weight tile is
programmed into a Mach-Zehnder Interferometer array, and the input vector is
encoded into optical signals. The MVP is then performed via photonics, by
modulating the signal strength of the light. The resulting photo-current is
converted to digital, via ADCs. The partial results are digitally accumulated
for the final output (see Figure 2); please refer to [17] for more photo-core
details.

The chosen DAC precision for inputs and weights is 10 bits and 7 bits,
respectively, with an 11-bit ADC at the output. Particularly, we note that the
output of the GEMM operations in the photo-core is quantized at the output
ADCs, which adds to the error caused by input and weight quantization. This
differs from digital devices that retain higher precision in outputs [44]. In
the following sections, we discuss the implications of this with methods to
mitigate its impact in photonic accelerators.

###  III-B Adaptive Block Floating Point (ABFP)

The inference accuracy of the DNNs on the photo-core is impacted by two key
factors: the presence of analog noise (e.g., shot noise, thermal noise) and
the quantization noise due to the reduced weight and activation precision at
the ADCs. To mitigate this, we explore the use of ABFP [28] for quantizing the
weights and activations to the photo-core. ABFP reduces quantization effects
by scaling vectors of length $n$ in the weight tiles and input vectors. In
addition to per-vector scaling, ABFP also uses an over-amplification factor
(i.e., gain $G$) at the output. The use of over-amplification helps increase
the signal-to-noise ratio in order to mitigate the impact of analog noise. In
our experiments, we analyze this composite framework based on its overall
impact in terms of accuracy, throughput and energy.

Figure 2 shows the workflow of ABFP with the photo-core. Given a weight
matrix, $N_{r}\times N_{c}$, ABFP computes the scale as the maximum values
over each row of the $n\times n$ sub-tile, i.e., one scale per row vector of
length $n$. The scales are stored in bfloat16. Instead of computing the scales
over the entire matrix, the use of per-vector scales, $S^{W}$, for each
$n$-sized row helps mitigate the impact of quantization. Similarly, for the
input vector, the scales, $S^{X}$, are computed as the maximum over vectors of
length $n$. The weight sub-tiles and input vectors are quantized using the
corresponding scales and passed into the photo-core via input and weight DACs.

###  III-C Simulation Details

For this work, we designed a simulator for the photo-core, that captures the
overall architecture shown in Figure 2, while run on NVIDIA A100 GPUs.
Specifically, non-linear operations within the DNNs are computed directly at
higher GPU precision, whereas, MVPs that would occur on the photo-core are
digitally simulated. The photo-core MVP simulation includes modeling
quantization and sources of error that stem from analog noise such as thermal
noise and shot noise. These noise sources affect the overall MVP output, and
is modeled by adding a cumulative noise term to it. The noise is sampled from
a zero-mean normal distribution with a standard deviation that reflects the
effects of the cumulative analog noise. Hence, the effects of analog noise and
quantization are combined in the digital simulation to model the complete
electro-photonic system for DNN inference shown in Figure 2. Within the
simulation, the MVP of the weight tile $W$ and input vector $X$ is given by:

$Y^{q}=Q(W;S^{W},\Delta_{W})*Q(X;S^{X},\Delta_{X})$ (1)

The operator, $Q$, is typical quantization operation defined as:

$Q(X;S^{X},\Delta_{X})=\left\lfloor\frac{X}{S^{X}}\Delta_{X}\right\rceil\\\ $
(2)

Where, $\Delta_{m}=2^{b_{m}-1}-1$ for $b_{m}$ integer bits, and
$\lfloor.\rceil$ represents rounding and then clipping between
$\left[-\Delta_{m},\Delta_{m}\right]$. We use 7-bit weights and 10-bit inputs,
i.e., $b_{W}=7$ and $b_{X}=10$. Eqn (2) represents a typical quantization
operation, where the inputs are first scaled, then rounded and clipped to the
specified range [44]. The resultant partial output for a tile (see Eqn (1)) is
then amplified via the application of gain $G$ (we use $G=4.0$). To simulate
the impact of analog noise, we add a Gaussian noise
$\mathcal{E}\in\mathcal{N}(0,\sigma)$ to the resultant output. The noisy
result is then quantized at the output ADCs and further de-quantized using the
corresponding weight and input scales and converted to bfloat16 as follows:

$Y=Q(Y^{q}G+\mathcal{E};n\Delta_{X}\Delta_{W},\Delta_{Y})\frac{nS^{W}S^{X}}{G\Delta_{Y}}$
(3)

Eqn (3) represents 11-bit output quantization ($b_{Y}=11$), and then de-
quantization to bfloat16. The final output is obtained by bfloat16
accumulation over the partial tile outputs.

###  III-D Differential Noise Fine-tuning (DNF)

For models that do not perform well OOB, we fine-tune them using Differential
Noise Finetuning (DNF) to improve accuracy. In a one-time pre-training step,
DNF computes per-layer noise distributions based on the output differences
between the quantized and float32 models. During training, DNF samples noise
tensors from the pre-computed noise distributions and adds the noise to the
layer outputs of the float32 model. This way, the noise induced perturbations
in the layer outputs enable the models to adapt their weights to quantization
error and noise. In contrast to typical Quantization-Aware Training (QAT), DNF
uses float32 precision in the forward pass, eliminating the need for simulated
quantization operations in the forward pass thus resulting in significant
speed improvements [28].

##  IV Experiments

Figure 3: An example of the Corning manufacturing process that requires precise insertion of the cylindrical part and its extension to a molded plastic pocket. Semantic segmentation is used to identify four object categories: cylindrical part, cylindrical part extension, molded plastic pocket, and cylindrical part holder. Only the four colored and underlined objects are of interest to the inspection process and are being segmented from the image and other parts. Dotted lines indicate occlusion of the cylindrical part from other components. TABLE I:  Experiment results for the models simulated on the photo-core + ABFP (photonic) system with and without DNF. |  | Pixel Accuracy | IoU
---|---|---|---
Model | Dataset | FP32 | Photonic (OOB) | Photonic (+ DNF) | FP32 | Photonic (OOB) | Photonic (+ DNF)
|  |  | [$\%$ of FP32] | [$\%$ of FP32] |  | [$\%$ of FP32] | [$\%$ of FP32]
Mobilenet-dilated-deepsupp | ADE20K | 76.74 | 64.15 [83.6$\%$] | 71.60 [93.3$\%$] | 33.13 | 18.27 [55.2$\%$] | 27.60 [83.3$\%$]
Cityscapes | 94.45 | 86.99 [92.1$\%$] | 94.27 [99.8$\%$] | 74.64 | 50.89 [68.2$\%$] | 73.69 [98.7$\%$]
Corning | 97.30 | 67.80 [69.7$\%$] | 91.42 [93.9$\%$] | 68.76 | 22.00 [32.0$\%$] | 58.28 [84.8$\%$]
Resnet50-ppm-dilated-deepsup | ADE20K | 79.09 | 75.49 [95.4$\%$] | 77.46 [97.9$\%$] | 39.82 | 33.14 [83.2$\%$] | 36.21 [90.9$\%$]
Cityscapes | 93.77 | 74.78 [79.7$\%$] | 93.29 [99.5$\%$] | 72.75 | 55.50 [76.3$\%$] | 69.14 [95.0$\%$]
Corning | 98.03 | 78.07 [79.6$\%$] | 96.79 [98.7$\%$] | 70.51 | 35.05 [49.7$\%$] | 68.27 [96.8$\%$]
HRNetv2 | ADE20K | 81.45 | 80.69 [99.1%] | 80.90 [99.3%] | 43.17 | 41.73 [96.7%] | 42.54 [98.5$\%$]
Cityscapes | 95.41 | 95.25 [99.8%] | 95.28 [99.9%] | 78.97 | 78.29 [99.1%] | 78.49 [99.4%]
Corning | 98.49 | 96.89 [98.4%] | 97.37 [98.9$\%$] | 71.60 | 68.43 [95.6$\%$] | 69.66 [97.3$\%$]
Swin-base Maskformer | ADE20K | 82.88 | 82.15 [99.1$\%$] | 82.37 [99.4%] | 52.85 | 50.88 [96.3$\%$] | 52.27 [98.9%]
Cityscapes | 97.42 | 97.41 [99.9%] | NA | 79.18 | 79.16 [99.9%] | NA
Corning | 98.47 | 98.39 [99.9%] | NA | 71.89 | 71.85 [99.9%] | NA
Swin-large Maskformer | ADE20K | 83.53 | 83.00 [99.4%] | 82.27 [99.7%] | 54.37 | 52.29 [96.2$\%$] | 53.99 [99.3%]
Cityscapes | 97.44 | 97.43 [99.9%] | NA | 80.07 | 79.98 [99.9%] | NA
Corning | 98.52 | 98.39 [99.9%] | NA | 72.23 | 71.93 [99.6%] | NA

We evaluate the performance of image segmentation models for autonomous
driving and defect detection on the photo-core. In particular, we evaluate: a)
accuracy of different image segmentation DNNs and why certain DNNs perform
better than others; b) implications of using the ABFP representation; c)
implications of using over-amplification (gain), in terms of accuracy and
energy consumption; d) throughput and energy comparisons of image segmentation
workloads on the photo-core. We do not make any conclusions about the absolute
energy consumption or throughput of the photo-core, relative to other hardware
architectures. Instead, our work is focused on empirically analyzing and
comparing the DNNs to evaluate their relative strengths on photonic hardware
via the photo-core.

###  IV-A Datasets

We evaluate and fine-tune the image segmentation DNNs for autonomous driving
using the ADE20k [7] and Cityscapes [45] datasets, which comprise images of
city scenes with 150 and 34 object classes, respectively.

For defect detection, the Corning Defect Detection dataset (not public),
consists of RGB imagery from a traditional manufacturing process, involving
the insertion of a cylindrical part into a molded plastic pocket (See example
in Figure 3). The objective of the inspection is to verify that positions of
the part and the equipment fall within the designated process limits. Pixel-
level segmentation facilitates the determination of the relative position of
multiple objects and it enables the identification of instances where outcomes
deviate from desired specifications. In all three datasets, each pixel in an
image is either labeled as one of the classes or as a background pixel.

###  IV-B Models

Five DNNs were chosen based on their sizes and structural nature
(convolutional vs. transformers)111Please see:
https://github.com/CSAILVision/semantic-segmentation-pytorch and
https://huggingface.co/facebook/maskformer-swin-large-ade.
MobileNetv2dilated-c1-deepsup (referred to as mobilenet) is a lightweight CNN
architecture designed for efficient semantic segmentation, featuring depth-
wise separable convolutions and dilated convolutions to reduce computation
costs while maintaining accuracy. ResNet50dilated-ppm-deepsup (referred to as
Resnet50) is a variant of ResNet that utilizes dilated convolutions and
pyramid pooling to capture contextual information. HRNetv2 is a high-
resolution CNN architecture employing multi-resolution fusion to combine
features and capture fine-grained information. Maskformer (referred to as
swin-base or swin-large) uses a Swin-base or Swin-large backbone with a
detection transformer head for instance segmentation tasks, utilizing self-
attention mechanisms [46]. We used model checkpoints that were pre-trained on
the ImageNet dataset, providing a strong initialization for our work.

###  IV-C Accuracy Metrics

We use pixel accuracy and intersection over union (IoU) metrics. Pixel
accuracy is the ratio of the number of correctly predicted pixels, over the
total number of non-background pixels in the image. The Intersection over
Union (IoU) metric measures the overlap between the predicted segmentation
mask and the ground truth mask. IoU is calculated as the ratio of the
intersection of the predicted and ground truth masks, over their union. The
IoU $\in[0,1]$, where 1 indicates a perfect overlap between the predicted and
ground truth masks, and 0 indicates no overlap. We measure the average IoU
across the object classes in the image and then report the mean IoU (mIoU).

##  V Results

###  V-A Accuracy Analysis

TABLE II:  Comparing input activations with and without using ABFP (vs. using per-tensor max). Using ABFP outperforms full tensor max, particularly in cases where outliers are more prominent. | Without ABFP | With ABFP
---|---|---
Model |  | mIoU [% FP32]
---
| mIoU [% FP32]
---
Resnet50 | 6.61 [9.1%] | 55.5 [76.3%]
HRNetv2 | 65.72 [83.2%] | 78.29 [99.1%]

The performance of the image segmentation models in terms of pixel accuracy
and mIoU is shown in Table I. For the Mobilenet and Resnet50 models, we see
that the out-of-the-box (OOB) performance is less than 99% of float32.
However, HRNetv2 and the Maskformer models (Swin-base and Swin-large) perform
well OOB on all datasets, achieving $\simeq 99\%$ of float32. We further see
that in all the cases, the model performances can be improved through the use
of differential noise fine-tuning (DNF). DNF enables the Mobilenet and
Resnet50 models to achieve significant improvements compared to their OOB
performance. Overall, the swin-large maskformer outperforms the other networks
in terms of pixel accuracy and mIoU on all the tested datasets.

Does ABFP help with OOB model performance? Table II displays the results
comparing the accuracy of HRNetv2 and Resnet50, with and without ABFP. The
utilization of ABFP leads to a notable improvement in the final mIoU,
particularly for Resnet50 in comparison to HRNetv2.

Figure 4: Analysis of layer sensitivity. Most of the mIoU drop compared to FP32 mIoU, is accounted for within the first four layers of the models. TABLE III:  Ablation results for running the most sensitive layer of Resnet50 (layer #1) on Cityscapes, by toggling different levels of quantization in the photonic system. As shown, output quantization of the sensitive layer results in almost all of the loss compared to FP32. Quantization | Photonic accuracy | Photonic mIoU
---|---|---
Setting | [% FP32] | [% FP32]
With all quantization | 74.78 [79.75%] | 55.50 [76.29%]
No input quantization | 74.72 [79.68%] | 55.65 [76.49%]
No weight quantization | 74.22 [79.15%] | 55.42 [76.18%]
No output quantization | 93.45 [99.66%] | 71.42 [98.17%]
Figure 5: Normalized distributions (in range $[-1.0,1.0]$) of the outputs of
the most sensitive layers of the different models. HRNetv2 and Swin-base has a
better utilization of the range even for the most sensitive layers, thus
resulting in less accuracy drop compared to FP32, on the photo-core. The $s$,
in the legend, is the scaling factor from the largest activation.

Why do HRNetv2 and Maskformer models have superior OOB results? In Table I, we
noted that some models under-performed others significantly, in spite of using
ABFP. To investigate the reasoning behind this, we performed a layer
sensitivity analysis of the models [44]. During layer sensitivity analysis, a
single layer is quantized at a time, and the model mIoU is evaluated. Layers
that result in a lower mIoU when quantized are considered to be “sensitive” to
loss of precision [44]. In Figure 4, we show the results of the layer
sensitivity analysis for the first four layers of each model in terms of the
drop in mIoU between the float32 model and the model with the specific layers
quantized. We see that most of the drop in mIoU happens within the first few
layers of the models. In particular, layer #1 of Resnet50 and layer #4 of
Mobilenet exhibit increased sensitivity to quantization, i.e., they exhibit
the highest mIoU drop compared to the float32 mIoU. This is consistent with
observations on typical digital hardware [47]. However, for HRNetv2 and Swin-
base, even the most sensitive layers only result in a small drop in mIoU.

To further understand whether the specific layers are sensitive due to input,
weight or output quantization, we perform an ablation study by isolating each
level of quantization as shown in Table III. Specifically, we note that output
quantization results in almost all of the mIoU loss. The additional
quantization at the output ADC introduces a large source of error that impacts
the model performance. Following up on this observation, we visualize the
normalized output distributions of the most sensitive layers of the different
models in Figure 5. We note that the maximum output activation value (denoted
by $s$) varies across the models, and in particular, Mobilenet and Resnet50
models have very high outliers. A range of $\pm$ three standard deviations of
the normalized ResNet distribution utilizes only $23\%$ of the quantization
levels whereas the swin-base model uses approximately $69\%$ of the
quantization levels. This leads to poor range utilization that in turn results
in poor quantization, impacting the performance of Resnet50 and Mobilenet.

Figure 6: Analysis of accuracy vs. tile size $n$ and gain for Swin-base and
large Maskformer. The use of gain helps improve accuracy by increasing the
signal-to-noise ratio. However, beyond a certain point, gain causes saturation
and clipping of activations, resulting in a drop in model accuracy.

How does gain help with OOB performance? To better understand the impact of
the chosen tile size, $n$, and gain, particularly for the models that achieve
99% accuracy OOB (Swin-base and Swin-large Maskformer), we investigate this
relationship in Figure 6. We make the following observations: a) as $n$
reduces, mIoU generally improves, since smaller tile sizes can further
mitigate the impact of outliers which is a key issue as previously described;
b) the use of gain helps improve mIoU until a certain point, since the signal-
to-noise ratio is correspondingly improved; c) beyond a threshold, gain causes
the mIoU to drop due to saturation. Saturation of values (when amplified by
the gain) causes clipping of critical activations thus impacting model
accuracy. Overall, the combination of ABFP + gain with specific choices of
$n$, enable models like Swin-base and large Maskformers to achieve good OOB
results.

###  V-B Energy Usage Analysis

Figure 7: Analysis of the energy consumption of one batch of data for
different tile sizes. Hrnetv2 has lesser consumption than Resnet50 at $n=64$
(denoted by $\blacktriangle$) compared to $n=256$ (denoted by $\star$) due to
a decrease in photocore utilization relative to Resnet50.

The laser power of the photo-core depends on the gain $G$, tile size $n$, and
fixed internal parameters such as MZI loss, laser efficiency and coupling
loss. The key factors of interest in this work are $n$ and $G$, and we analyze
the relative scaling behavior of photo-core energy consumption for the image
segmentation workloads based on the two parameters. This also allows us to
abstract the remaining parameters from our analysis since they are fixed
across the models (MZI loss, laser efficiency etc.). With this form of
abstraction, we can group the internal laser parameters to two sets of
constants, $\alpha$ and $\beta$. Then the photo-core power $P$, can be
summarized in terms of $G$ and $n$:

$P(G,n)=\left(G\alpha^{n}+\beta\right)n$ (4)

The total amount of photo-core energy required for a given DNN inference at a
specified gain and tile size is then $E(G,n)=T*P(G,n)$, where $T$ is the total
time taken to execute the DNN workload (# of MVPs $\times$ time taken for the
photo-core per MVP), plus data transfer costs for the weights to be sent and
loaded onto the photo-core (set to 40ns, 10ns respectively)222Since we focus
primarily on the photocore, we exclude energy analysis of digital aspects such
as quantization, and data transfer costs of inputs.. This abstraction captures
the exponential relation between energy and $n$, and the linear relation
between energy and $G$ (with a slope that is determined by $T$ and $n$).
Empirically, for our system, a gain of 2 increases energy consumption by
$1.4\times$ for $n=64$ and $1.9\times$ for $n=128$, compared to using no
overamp, indicating that the accuracy improvements from Section V-A (Figure 6)
come at an energy cost.

Figure 7 shows how the relative energy consumption scales as a function of
tile sizes for a single batch of data. We keep the other photo-core parameters
fixed, and do not focus on the absolute energy consumption of the models.
Instead, we make the following observations: a) the swin-base and swin-large
maskformers consume $\simeq 2\times$ and $\simeq 4\times$ more energy
respectively, than CNNs; b) the energy consumption reduces up to $n=64,128$.
This is because smaller tile sizes ($<64$) require more MVPs and
correspondingly larger run-times. Beyond $n=128$, the $\alpha$ parameter
begins to dominate for larger tile sizes leading to more energy consumption;
c) the energy consumption of HRNetv2 is less than Resnet50 at $n=64$ (shown as
$\blacktriangle$), but higher at $n=256$ (shown as $\star$). This is due to
the reduced photo-core utilization of HRNetv2 compared to Resnet50, at
$n=256$. Depending on the matrix sizes in these models (that are not divisible
by tile size), larger tile sizes will lead to under-utilized tiles and higher
energy consumption.

###  V-C Throughput Analysis

Figure 8: Analysis of throughput vs. tile size $n$. Smaller tile sizes can
mitigate impact of outliers, but reduce throughput significantly compared to
larger tiles.

Figure 8 shows the throughput for the different DNNs for different tile sizes
and a fixed batch size of 4. We see that: a) swin-base and swin-large
maskformers have lower throughput compared to the CNNs. This highlights a
trade-off with the maskformer models that have better OOB accuracy results,
but lower throughput compared to CNNs; b) although smaller tile sizes offer
accuracy improvements as shown in Section V-A (Figure 6), it results in lower
throughput. Hence, there is an accuracy-vs-throughput trade-off when selecting
the appropriate tile size to use for the image segmentation workloads.

##  VI Discussion

In this work, we presented an analysis of image segmentation workloads for
autonomous driving and defect detection on photonic hardware. We analyzed
different convolutional and transformer models, and a summary of our findings
is captured in Figure 1. We see that while the maskformer models achieve good
OOB accuracy, they are less competitive in terms of throughput and energy
consumption. In contrast, HRNetv2 (particularly with DNF) presents a good
trade-off in terms of energy, throughput and accuracy. Thus, HRNetv2 is a
promising candidate for image segmentation on photonic devices. We highlight
some additional key insights from this work:

  1. 1.

The accuracy of image segmentation on photonic hardware is significantly
impacted by the output quantization. While both ABFP and DNF are promising for
improving accuracy, techniques such as parameterized activations to mitigate
outliers [48], can also be helpful.

  2. 2.

Accuracy degradation mainly occurs due to relatively few layers of each model.
Existing approaches that execute sensitive layers at higher precision while
keeping others lower [44, 49], can be beneficial here. Photonic systems should
consider supporting this hybrid approach with controllable bit-precisions for
sensitive layers.

  3. 3.

There is a complex relationship between the photo-core tile size, gain, and
DNN architectures, influencing the energy and throughput profiles. Photonic
systems may be designed to dynamically adjust internal parameters such as gain
to optimize energy efficiency. DNN architectures can also be re-designed as in
[50], to be optimal for the specific photo-core tile size to improve
throughput.

Drawbacks and future work: While we have looked at hardware parameters like
tile size and gain, we have not analyzed other architectural aspects of the
hardware in-depth, such as wall-plug efficiency of the laser, data storage or
movement, and non-linearities on digital ASICs. We have also not explored
other potential throughput optimizations of attention layers [51] that may
improve Maskformer performance over CNNs. We explore our work in the context
of the photo-core; however, we believe that our findings with ABFP, DNF, tile
sizes and gain will offer insights for future work in algorithmic and hardware
enhancements to photonic accelerators for ML workloads.

##  VII Acknowledgements

The authors would like to thank colleagues Cansu Demirkiran and Alexander
Sludds for their helpful insights and discussions. We also thank our reviewers
for their constructive feedback.

## References

  * [1] Juana Valeria Hurtado and Abhinav Valada.  Semantic scene segmentation for robotics.  In Deep Learning for Robot Perception and Cognition, pages 279–311. Elsevier, 2022.
  * [2] Senay Cakir, Marcel Gauß, Kai Häppeler, Yassine Ounajjar, Fabian Heinle, and Reiner Marchthaler.  Semantic segmentation for autonomous driving: Model evaluation, dataset generation, perspective comparison, and real-time capability.  arXiv preprint arXiv:2207.12939, 2022.
  * [3] Graham Roberts, Simon Y Haile, Rajat Sainju, Danny J Edwards, Brian Hutchinson, and Yuanyuan Zhu.  Deep learning for semantic segmentation of defects in advanced stem images of steels.  Scientific reports, 9(1):12744, 2019.
  * [4] Alexander Kirillov, Eric Mintun, Nikhila Ravi, Hanzi Mao, Chloe Rolland, Laura Gustafson, Tete Xiao, Spencer Whitehead, Alexander C Berg, Wan-Yen Lo, et al.  Segment anything.  arXiv preprint arXiv:2304.02643, 2023.
  * [5] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition, 2015.
  * [6] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition, 2014\.
  * [7] Bolei Zhou, Hang Zhao, Xavier Puig, Tete Xiao, Sanja Fidler, Adela Barriuso, and Antonio Torralba.  Semantic understanding of scenes through the ade20k dataset.  International Journal on Computer Vision, 2018.
  * [8] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo.  Swin transformer: Hierarchical vision transformer using shifted windows.  type: article.
  * [9] Ai and compute.  Accessed: May 16, 2018.
  * [10] Mitchell A Nahmias, Thomas Ferreira De Lima, Alexander N Tait, Hsuan-Tung Peng, Bhavin J Shastri, and Paul R Prucnal.  Photonic multiply-accumulate operations for neural networks.  IEEE Journal of Selected Topics in Quantum Electronics, 26(1):1–18, 2019.
  * [11] Nicola Peserico, Bhavin J Shastri, and Volker J Sorger.  Integrated photonic tensor processing unit for a matrix multiply: a review.  Journal of Lightwave Technology, 2023.
  * [12] Nicolò Ghielmetti, Vladimir Loncar, Maurizio Pierini, Marcel Roed, Sioni Summers, Thea Aarrestad, Christoffer Petersson, Hampus Linander, Jennifer Ngadiuba, Kelvin Lin, et al.  Real-time semantic segmentation on fpgas for autonomous vehicles with hls4ml.  Machine Learning: Science and Technology, 3(4):045011, 2022.
  * [13] Minjong Kim, Byungjae Park, and Suyoung Chi.  Accelerator-aware fast spatial feature network for real-time semantic segmentation.  IEEE Access, 8:226524–226537, 2020.
  * [14] Bart De Ruijsscher, Georgi N Gaydadjiev, Jeroen Lichtenauer, and Emile Hendriks.  Fpga accelerator for real-time skin segmentation.  In 2006 IEEE/ACM/IFIP Workshop on Embedded Systems for Real Time Multimedia, pages 93–97. IEEE, 2006.
  * [15] Christopher J Holder and Muhammad Shafique.  On efficient real-time semantic segmentation: a survey.  arXiv preprint arXiv:2206.08605, 2022.
  * [16] Panagiotis Stavropoulos, Alexios Papacharalampopoulos, and Dimitris Petridis.  A vision-based system for real-time defect detection: a rubber compound part case study.  Procedia CIRP, 93:1230–1235, 2020.
  * [17] Cansu Demirkiran, Furkan Eris, Gongyu Wang, Jonathan Elmhurst, Nick Moore, Nicholas C. Harris, Ayon Basumallik, Vijay Janapa Reddi, Ajay Joshi, and Darius Bunandar.  An electro-photonic system for accelerating deep neural networks, 2022\.
  * [18] Tesla NVIDIA.  V100 gpu architecture.  The world’s most advanced data center GPU. Version WP-08608-001_v1, 1, 2017.
  * [19] Norman P Jouppi, Cliff Young, Nishant Patil, David Patterson, Gaurav Agrawal, Raminder Bajwa, Sarah Bates, Suresh Bhatia, Nan Boden, Al Borchers, et al.  In-datacenter performance analysis of a tensor processing unit.  In Proceedings of the 44th annual international symposium on computer architecture, pages 1–12, 2017.
  * [20] Hadi Esmaeilzadeh, Emily Blem, Renée St. Amant, Karthikeyan Sankaralingam, and Doug Burger.  Dark silicon and the end of multicore scaling.  In 2011 38th Annual International Symposium on Computer Architecture (ISCA), pages 365–376, 2011.
  * [21] Weichen Liu, Wenyang Liu, Yichen Ye, Qian Lou, Yiyuan Xie, and Lei Jiang.  Holylight: A nanophotonic accelerator for deep learning in data centers.  In 2019 Design, Automation & Test in Europe Conference & Exhibition (DATE), pages 1483–1488. IEEE, 2019.
  * [22] Armin Mehrabian, Yousra Al-Kabani, Volker J Sorger, and Tarek El-Ghazawi.  Pcnna: A photonic convolutional neural network accelerator.  In 2018 31st IEEE International System-on-Chip Conference (SOCC), pages 169–173. IEEE, 2018.
  * [23] Emilio Paolini, Lorenzo De Marinis, Marco Cococcioni, Luca Valcarenghi, Luca Maggiani, and Nicola Andriolli.  Photonic-aware neural networks.  Neural Computing and Applications, 34(18):15589–15601, 2022.
  * [24] Farshid Ashtiani, Alexander J Geers, and Firooz Aflatouni.  An on-chip photonic deep neural network for image classification.  Nature, 606(7914):501–506, 2022.
  * [25] Zi Wang, Lorry Chang, Feifan Wang, Tiantian Li, and Tingyi Gu.  Integrated photonic metasystem for image classifications at telecommunication wavelength.  Nature Communications, 13(1):2131, 2022.
  * [26] Carlo M Valensise, Ivana Grecco, Davide Pierangeli, and Claudio Conti.  Large-scale photonic natural language processing.  Photonics Research, 10(12):2846–2853, 2022.
  * [27] Davide Pierangeli, Giulia Marcucci, and Claudio Conti.  Photonic extreme learning machine by free-space optical propagation.  Photonics Research, 9(8):1446, jul 2021.
  * [28] Ayon Basumallik, Darius Bunandar, Nicholas Dronen, Nicholas Harris, Ludmila Levkova, Calvin McCarter, Lakshmi Nair, David Walter, and David Widemann.  Adaptive block floating-point for analog deep learning hardware.  arXiv preprint arXiv:2205.06287, 2022.
  * [29] Amir Gholami, Sehoon Kim, Zhen Dong, Zhewei Yao, Michael W Mahoney, and Kurt Keutzer.  A survey of quantization methods for efficient neural network inference.  arXiv preprint arXiv:2103.13630, 2021.
  * [30] Steve Dai, Rangha Venkatesan, Mark Ren, Brian Zimmer, William Dally, and Brucek Khailany.  Vs-quant: Per-vector scaled quantization for accurate low-precision neural network inference.  Proceedings of Machine Learning and Systems, 3:873–884, 2021.
  * [31] Ben Keller, Rangharajan Venkatesan, Steve Dai, Stephen G Tell, Brian Zimmer, William J Dally, C Thomas Gray, and Brucek Khailany.  A 17–95.6 tops/w deep learning inference accelerator with per-vector scaled 4-bit quantization for transformers in 5nm.  In 2022 IEEE Symposium on VLSI Technology and Circuits (VLSI Technology and Circuits), pages 16–17. IEEE, 2022.
  * [32] Jingchang Li, Qi Zhou, Longchao Cao, Yanzhi Wang, and Jiexiang Hu.  A convolutional neural network-based multi-sensor fusion approach for in-situ quality monitoring of selective laser melting.  Journal of Manufacturing Systems, 64:429–442, 2022.
  * [33] Javier Villalba-Diez, Daniel Schmidt, Roman Gevers, Joaquín Ordieres-Meré, Martin Buchwitz, and Wanja Wellbrock.  Deep learning for industrial computer vision quality control in the printing industry 4.0.  Sensors, 19(18), 2019.
  * [34] Hafiz Mughees Ahmad and Afshin Rahimi.  Deep learning methods for object detection in smart manufacturing: A survey.  Journal of Manufacturing Systems, 64:181–196, 2022.
  * [35] Jingang Cao, Guotian Yang, and Xiyun Yang.  A pixel-level segmentation convolutional neural network based on deep feature fusion for surface defect detection.  IEEE Transactions on Instrumentation and Measurement, 70:1–12, 2020\.
  * [36] Hüseyin Üzen, Muammer Turkoglu, Muzaffer Aslan, and Davut Hanbay.  Depth-wise squeeze and excitation block-based efficient-unet model for surface defect detection.  The Visual Computer, 39(5):1745–1764, 2023.
  * [37] Hüseyin Üzen, Muammer Türkoğlu, Berrin Yanikoglu, and Davut Hanbay.  Swin-mfinet: Swin transformer based multi-feature integration network for detection of pixel-level surface defects.  Expert Systems with Applications, 209:118269, 2022.
  * [38] Yih-Lon Lin, Yu-Min Chiang, Chia-Ming Liu, and Sih-Wei Huang.  Electrode tab deflection detection for pouch lithium-ion battery using mask r-cnn.  In Intelligent and Transformative Production in Pandemic Times: Proceedings of the 26th International Conference on Production Research, pages 141–149. Springer, 2023.
  * [39] Garima Nain, K.K. Pattanaik, and G.K. Sharma.  Towards edge computing in intelligent manufacturing: Past, present and future.  Journal of Manufacturing Systems, 62:588–611, 2022.
  * [40] I Kevin, Kai Wang, Xiaokang Zhou, Wei Liang, Zheng Yan, and Jinhua She.  Federated transfer learning based cross-domain prediction for smart manufacturing.  IEEE Transactions on Industrial Informatics, 18(6):4088–4096, 2021\.
  * [41] Tejalal Choudhary, Vipul Mishra, Anurag Goswami, and Jagannathan Sarangapani.  A comprehensive survey on model compression and acceleration.  Artificial Intelligence Review, 53:5113–5155, 2020.
  * [42] Tailin Liang, John Glossner, Lei Wang, Shaobo Shi, and Xiaotong Zhang.  Pruning and quantization for deep neural network acceleration: A survey.  Neurocomputing, 461:370–403, 2021.
  * [43] Andrew Anderson, Aravind Vasudevan, Cormac Keane, and David Gregg.  Low-memory gemm-based convolution algorithms for deep neural networks.  arXiv preprint arXiv:1709.03395, 2017.
  * [44] Hao Wu, Patrick Judd, Xiaojie Zhang, Mikhail Isaev, and Paulius Micikevicius.  Integer quantization for deep learning inference: Principles and empirical evaluation.  arXiv preprint arXiv:2004.09602, 2020.
  * [45] Marius Cordts, Mohamed Omran, Sebastian Ramos, Timo Rehfeld, Markus Enzweiler, Rodrigo Benenson, Uwe Franke, Stefan Roth, and Bernt Schiele.  The cityscapes dataset for semantic urban scene understanding, 2016.
  * [46] Bowen Cheng, Alex Schwing, and Alexander Kirillov.  Per-pixel classification is not all you need for semantic segmentation.  Advances in Neural Information Processing Systems, 34:17864–17875, 2021.
  * [47] Vinay Joshi, Manuel Le Gallo, Simon Haefeli, Irem Boybat, Sasidharan Rajalekshmi Nandakumar, Christophe Piveteau, Martino Dazzi, Bipin Rajendran, Abu Sebastian, and Evangelos Eleftheriou.  Accurate deep neural network inference using computational phase-change memory.  Nature communications, 11(1):2473, 2020.
  * [48] Jungwook Choi, Zhuo Wang, Swagath Venkataramani, Pierce I-Jen Chuang, Vijayalakshmi Srinivasan, and Kailash Gopalakrishnan.  Pact: Parameterized clipping activation for quantized neural networks.  arXiv preprint arXiv:1805.06085, 2018.
  * [49] Soroosh Khoram and Jing Li.  Adaptive quantization of neural networks.  In International Conference on Learning Representations, 2018.
  * [50] Barret Zoph and Quoc V. Le.  Neural architecture search with reinforcement learning, 2016.  cite arxiv:1611.01578.
  * [51] Mohammad Shoeybi, Mostofa Patwary, Raul Puri, Patrick LeGresley, Jared Casper, and Bryan Catanzaro.  Megatron-lm: Training multi-billion parameter language models using model parallelism.  arXiv preprint arXiv:1909.08053, 2019.


# A CNN-Transformer Deep Learning Model for Real-time Sleep Stage
Classification in an Energy-Constrained Wireless Device

Zongyan Yao  University of Toronto
Toronto, Canada
<EMAIL_ADDRESS>Xilin Liu  University of Toronto
Toronto, Canada
<EMAIL_ADDRESS>
###### Abstract

This paper proposes a deep learning (DL) model for automatic sleep stage
classification based on single-channel EEG data. The DL model features a
convolutional neural network (CNN) and transformers. The model was designed to
run on energy and memory-constrained devices for real-time operation with
local processing. The Fpz-Cz EEG signals from a publicly available Sleep-EDF
dataset are used to train and test the model. Four convolutional filter layers
were used to extract features and reduce the data dimension. Then,
transformers were utilized to learn the time-variant features of the data. To
improve performance, we also implemented a subject specific training before
the inference (i.e., prediction) stage. With the subject specific training,
the F1 score was 0.91, 0.37, 0.84, 0.877, and 0.73 for wake, N1- N3, and rapid
eye movement (REM) stages, respectively. The performance of the model was
comparable to the state-of-the-art works with significantly greater
computational costs. We tested a reduced-sized version of the proposed model
on a low-cost Arduino Nano 33 BLE board and it was fully functional and
accurate. In the future, a fully integrated wireless EEG sensor with edge DL
will be developed for sleep research in pre-clinical and clinical experiments,
such as real-time sleep modulation.

##  I Introduction

Sleep quality and health are closely related; therefore, it is important to
understand one’s sleep quality to improve health condition. A measurement of
sleep quality is the time spent in each sleep stage. There are five sleep
stages, which are wake, N1, N2, N3, and REM, with each stage progressively
deeper sleep. Most of the sleep occurs between stages N1 and N3 [1]. The
clinical evaluation of sleep stages is performed by polysomnogram (PSG), a
procedure that records one’s electroencephalogram (EEG), electrooculogram
(ECG), and other physiological features. Medical professionals will manually
classify their sleep stages over time according to one or more of the features
mentioned above.

Figure 1: An overview of the envisioned wireless device for real-time sleep
stage classification using edge DL. This paper focuses on the development and
deployment of the DL model.

With the development of electronic technology and machine intelligence,
wearable devices, such as smartwatches, can measure user biosignals and
potentially classify their sleep stages. However, the cost of these devices is
high and the performance of sleep stage classification is limited. In
addition, classification often requires the transmission of data to mobile
phones or the cloud, raising concerns about cybersecurity [2, 3]. High-quality
real-time sleep classification and sleep modulation still needs to be
performed in sleep laboratories. There is a need for low-cost at-home sleep
monitoring devices that can perform sleep stage classification on device, and
potentially use the sleep stage to generate auditory stimulation for treating
sleep disorders or enhancing sleep quality [4].

In this paper, we develop a lightweight DL model for running on devices with
restricted energy and memory, such as microcontrollers [5]. There are two main
constraints to the development of the model for hardware. The first constraint
is that the size of the model will be limited by the memory resources
available on the hardware, including the non-volatile Flash memory for model
storage and the random-access memory (RAM) for model computing [6]. The second
constraint is that the computational demand of the model will be limited by
the clock rate, bit width, and computational capabilities (such as floating
point or fixed point) of the device [7]. Key trade-offs are between model
performance and complexity. In this work, we developed a DL model that can run
on a low-power wireless microcontroller, based on a low-cost Arduino Nano 33
BLE development board. Despite its small size, our model achieved performances
comparable to the state-of-the-art during a validation using a publicly
available sleep dataset.

Fig. 1 shows the overall block diagram of the envisioned fully integrated
sleep stage classification device featuring the developed DL model. The device
will be miniature in size and fully self-contained. It can enable a wide range
of sleep research in pre-clinical and clinical studies.

##  II Methods

Figure 2: Architecture of the proposed CNN-Transformer DL model for real-time
sleep stage classification using single channel EEG signal.

###  II-A Dataset

Sleep-EDF Expanded Database (version 1, published in 2013) contains 197 whole-
night Polysomnographic (PSG) sleep recordings [8, 9]. It contains two subsets,
the Sleep Cassette Study (SC) and Sleep Telemetry Study (ST). Data from the
Sleep Telemetry Study was obtained in 1994 to study the effects of temazepam
on sleep. Since we are proposing a model to classify the stages of sleep of
healthy people, we will not use data from this subset. Our experiments will be
performed on the SC subset.

Two 20-hour PSG recordings were taken for 77 subjects between the age of 25
and 101. The first nights of subjects 36 and 52, and the second night of
subject 13 were lost. The PSG recordings contain three channels of EEG
signals, one channel of EOG and chin EMG signals, oronasal airflow, rectal
body temperature, and event marker. To reduce our model’s size, we only use
Fpz-Cz EEG signals as input to our model. The EEG signals were sampled at 100
Hz. Each of the 30-second segments of the signals was labeled by well-trained
sleep experts. There are eight stages, N1, N2, N3, N4, Wake, REM, MOVEMENT,
UNKNOWN). To make our results consistent and comparable with previous studies
[10, 11, 12], we preprocessed the data with the following methods:

  1. 1.

Discarded the segments with UNKNOWN and MOVEMENT labels.

  2. 2.

Combined N4 and N3 together as N3 stage.

  3. 3.

Ignored wake epochs longer than 30 minutes outside of sleep periods.

TABLE I: data distribution

| Wake | N1 | N2 | N3 | REM
---|---|---|---|---|---
# of Segment | 44752 | 15793 | 54682 | 12268 | 20976
Distribution | 30.14% | 10.64% | 36.83% | 8.26% | 14.13%
Total Number | 148471

###  II-B Performance Metrics

We evaluated our model’s performance using per-class Precision (PR), per-class
Recall (RE), per-class F1-score (F1), and overall accuracy (acc). Overall
accuracy is the ratio between the number of correct predictions and the
population. For a category prediction, there are four outcomes: true positive
(TP), false positive (FP), true negative (TN), false negative (FP). Metrics
are defined as:

$PR=\frac{TP}{TP+FP}$ (1) $RE=\frac{TP}{TP+FN}$ (2) $F1=\frac{2TP}{2TP+FN+FP}$
(3)

Overall accuracy is commonly used to measure classification performance.
However, for an imbalanced dataset, precision does not provide adequate
information on classifiers, because it hardly reveals performance in minority
groups [13]. Table I shows the distribution of the dataset. The dataset is
highly imbalanced, so we introduced additional metrics, PR, RE, and F1, to
correctly measure the performance of our model.

###  II-C Proposed Model

Raw EEG data contains time-invariant and time-variant features. Each 30-second
input data segment with 100-Hz sampling frequency, so the input shape is
(3000,1). It is too large to feed it into a transformer unit. Fig. 2 shows our
model’s architecture. A convolutional neural network can extract time-
invariant data and output smaller data. We implemented four sequential
convolutional layers to output features with shape (19,128). Then we use a
transformer unit to learn some time-variant information from the features. Its
attention mechanism learned the contexts on all positions of the time series
data. The two dense layers inside the transformer unit work as an encoder. The
output of the encoder is then added to the input data for additional features.
Finally, to correctly classify sleep scores, we used a dense layer with a
softmax activation function to obtain the most possible categories. We also
tried other models, such as recurrent neural network and auto-encoders.
Experiments showed that our proposed model yielded the best performance.

##  III Experiments

###  III-A Data Preprocessing

Since our model was designed to be deployed on microcontrollers with limited
memory and computation resources, we cannot design a complex data
preprocessing method, so we implemented a simple standarization. The
performance of deep-learning models is highly dependent on the statistical
properties of the input data. If the input data is too small or too large, the
models perform poorly. The EEG data in the Fpz-Cz channel is within the scope
of $10^{-5}$, which is too small for our model. Standarization transforms data
to have a zero mean and a standard deviation of one. For each sample $X$, we
standardized it to $Z$ using

$Z=\frac{X-M}{S}$

where M indicates the mean of the samples and S indicates the standard
deviation of the samples. After standarization, the input data was in the
range of $10^{-1}$ to $10^{1}$, and the model showed the best performance.

###  III-B Basic Training

We used 5-fold cross-validation to train and test our model. There are 77
subjects in total, and each fold contains 16 subjects’ data (one fold has 13
subjects). In each iteration, we selected four folds as training and
validating data, and one fold as testing data. Among the four folds of data,
we randomly sampled 10% for validation. The remaining 90% of data was for
training. We used Adam algorithm for optimization, which is a stochastic
gradient descent method based on adaptive estimation of first-order and
second-order moments. It computes efficiently and requires little memory [14].
We utilized categorical cross-entropy as the loss function and fed our model
with a batch size of 64 samples.

###  III-C Subject-Specific Training

We also performed subject-specific training in the testing stage to further
adapt the patterns of each subject. We randomly selected 10% of the test data
and fed them to our trained model. The remaining 90% of the test data were
used to test our models after subject-specific training.

##  IV Results

Table II and Table III show the confusion table and the performance of our
model, respectively. Since the dataset is imbalanced, the per-class
performance in N1 and REM was expected to be poorer than the majority classes.
The model performed well in the Wake and N2 classes. The state-of-the-art
performances from literature are also similar. From Table VI, all models have
an F1 score per class less than 0.5 in N1 and less than 0.8 in REM. To improve
the performance of our model, we perform a subject-specific training to
further adapt subject-wise patterns. Table IV and Table V show that
performances improved after subject-specific training. Firstly, the overall
accuracy increased from 0.775 to 0.795. Secondly, per-class precision, recall,
and F1 score increased for all classes.

Table VI compares the F1 score of different models from the literature. Since
our proposed model is lightweight and small, it cannot yield the best
performance. However, it still had performance comparable to that of the
state-of-the-art. For the wake stage, we yielded the highest F1-score of 0.91.
For other classes, we were close to the highest. There is no model that could
beat our performances in all classes. Some models performed better on certain
classes.

TABLE II: Confusion matrix before subject-specific training Actual/Predict | Wake | N1 | N2 | N3 | REM
---|---|---|---|---|---
Wake | 0.90 | 0.04 | 0.01 | 0 | 0.04
N1 | 0.20 | 0.26 | 0.31 | 0.01 | 0.21
N2 | 0.01 | 0.04 | 0.82 | 0.07 | 0.06
N3 | 0 | 0 | 0.19 | 0.80 | 0
REM | 0.05 | 0.08 | 0.12 | 0 | 0.74
TABLE III: Performance before subject-specific training | Wake | N1 | N2 | N3 | REM
---|---|---|---|---|---
Precision | 0.90 | 0.26 | 0.72 | 0.80 | 0.74
Recall | 0.89 | 0.42 | 0.81 | 0.70 | 0.64
F1-Score | 0.90 | 0.32 | 0.82 | 0.75 | 0.69
Accuracy | 0.775
TABLE IV: Confusion matrix after subject-specific training Actual/Predict | Wake | N1 | N2 | N3 | REM
---|---|---|---|---|---
Wake | 0.91 | 0.05 | 0.01 | 0 | 0.02
N1 | 0.21 | 0.31 | 0.29 | 0.01 | 0.18
N2 | 0.01 | 0.04 | 0.84 | 0.06 | 0.05
N3 | 0 | 0 |  0.20 | 0.80 | 0
REM | 0.05 | 0.08 | 0.10 | 0 | 0.78
TABLE V: Performance after patient-specific training | Wake | N1 | N2 | N3 | REM
---|---|---|---|---|---
Precision | 0.92 | 0.31 | 0.84 | 0.80 | 0.78
Recall | 0.90 | 0.46 | 0.83 | 0.74 | 0.69
F1-Score | 0.91 | 0.37 | 0.84 | 0.77 | 0.73
Accuracy | 0.795
TABLE VI: F1-Score comparison with state-of-art

Reference | Year | Architecture | F1-Score | Accuracy
---|---|---|---|---
Wake | N1 | N2 | N3 | REM
[15] | 2022 | DSSNet | 0.86 | 0.20 | 0.87 | 0.87 | 0.71 | 0.82
[16] | 2018 | 1-Max-CNN | 0.77 | 0.33 | 0.87 | 0.86 | 0.76 | 0.80
[10] | 2017 | DeepSleepNet | 0.88 | 0.37 | 0.83 | 0.77 | 0.80 | 0.80
[17] | 2019 | SleepEEGNet | 0.91 | 0.44 | 0.82 | 0.73 | 0.76 | 0.80
[18] | 2021 | CNN | 0.91 | 0.42 | 0.77 | 0.66 | 0.69 | N/A
This work | 0.91 | 0.37 | 0.84 | 0.77 | 0.73 | 0.80

##  V Discussion

Our lightweight model was designed for memory-constrained microcontroller
units. It had around 300,000 parameters, and its size was 2 MB. We used an
Arduino Nano 33 BLE board, which integrates a wireless microntroller
(nRF52840, Nordic Semiconductor) with a 64 MHz 32-bit ARM CPU, 1 MB of flash
memory, and 256 KB of SRAM [19]. The deployed model was stored in the flash
memory, so the model was supposed to be less than 1 MB. We planned to add an
external memory unit to the model in the future. To test the availability of
our design in the current stage, we implemented a smaller version of the model
and deployed it on the Arduino board. The model had an accuracy of 68%, but
the microcontroller was fully functional for target classification. To reduce
the size of our model, we also quantized the model in the deployment stage.

We randomly selected 10% of the test data set to perform subject-specific
training. If a dataset is large, the randomly selected data should follow the
distribution of the dataset. In our experiments, the distribution varied as
the dataset was not large enough. The improvement of performance was highly
dependent on the distribution of the selected data. Therefore, we will enforce
the distribution of the subject-specific training data. This means that the
number of selected data in each category is calculated and fixed based on the
test dataset. This method would maximize the benefits of subject-specific
training.

As mentioned previously, the dataset has an imbalanced class distribution,
which significantly affects models’ performance, especially on the minority
categories. There are different methods to mitigate the effect of imbalance
data, such as oversampling and undersampling. Oversampling is used to
duplicate samples in minority classes, while undersampling is used to remove
samples from the majority classes. There are two common ways in training
imbalanced data. Another method we will try in the future is to add weights to
the loss function. The loss function can be weighted differently for different
classes, so that minority classes are learned more.

##  VI Conclusion

In this work, we developed a lightweight DL model for real-time sleep stage
classification using single-channel EEG data. The DL model features CNN and
transformers. We validated the model using the Sleep-EDF dataset and tested it
in a low-power microcontroller. The model achieved performance comparable to
the state-of-the-art works. In the future, we plan to develop a fully
integrated wireless EEG sensor using the model. The developed device can
enable a wide range of sleep research.

## References

  * [1] A. K. Patel, V. Reddy, and J. F. Araujo, “Physiology, sleep stages,” in _StatPearls [Internet]_. StatPearls Publishing, 2022.
  * [2] X. Liu, A. G. Richardson, and J. Van der Spiegel, “An energy-efficient compressed sensing-based encryption scheme for wireless neural recording,” _IEEE Journal on Emerging and Selected Topics in Circuits and Systems_ , vol. 11, no. 2, pp. 405–414, 2021.
  * [3] X. Liu, H. Zhu, T. Qiu, S. Y. Sritharan, D. Ge, S. Yang, M. Zhang, A. G. Richardson, T. H. Lucas, N. Engheta _et al._ , “A fully integrated sensor-brain–machine interface system for restoring somatosensation,” _IEEE Sensors Journal_ , vol. 21, no. 4, pp. 4764–4775, 2020.
  * [4] X. Liu and A. G. Richardson, “A system-on-chip for closed-loop optogenetic sleep modulation,” in _2021 43rd Annual International Conference of the IEEE Engineering in Medicine & Biology Society (EMBC)_. IEEE, 2021, pp. 5678–5681.
  * [5] X. Liu, B. Subei, M. Zhang, A. G. Richardson, T. H. Lucas, and J. Van der Spiegel, “The pennbmbi: A general purpose wireless brain-machine-brain interface system for unrestrained animals,” in _2014 IEEE International Symposium on Circuits and Systems (ISCAS)_. IEEE, 2014, pp. 650–653.
  * [6] X. Liu and A. G. Richardson, “Edge deep learning for neural implants: a case study of seizure detection and prediction,” _Journal of Neural Engineering_ , vol. 18, no. 4, p. 046034, 2021.
  * [7] X. Liu, J. Sacks, M. Zhang, A. G. Richardson, T. H. Lucas, and J. Van der Spiegel, “The virtual trackpad: An electromyography-based, wireless, real-time, low-power, embedded hand-gesture-recognition system using an event-driven artificial neural network,” _IEEE Transactions on Circuits and Systems II: Express Briefs_ , vol. 64, no. 11, pp. 1257–1261, 2016.
  * [8] B. Kemp, A. Zwinderman, B. Tuk, H. Kamphuisen, and J. Oberye, “Analysis of a sleep-dependent neuronal feedback loop: the slow-wave microcontinuity of the eeg,” _IEEE Transactions on Biomedical Engineering_ , vol. 47, no. 9, pp. 1185–1194, 2000.
  * [9] A. L. Goldberger, L. A. Amaral, L. Glass, J. M. Hausdorff, P. C. Ivanov, R. G. Mark, J. E. Mietus, G. B. Moody, C.-K. Peng, and H. E. Stanley, “Physiobank, physiotoolkit, and physionet: components of a new research resource for complex physiologic signals,” _circulation_ , vol. 101, no. 23, pp. e215–e220, 2000.
  * [10] A. Supratak, H. Dong, C. Wu, and Y. Guo, “Deepsleepnet: A model for automatic sleep stage scoring based on raw single-channel eeg,” _IEEE Transactions on Neural Systems and Rehabilitation Engineering_ , vol. 25, no. 11, pp. 1998–2008, 2017.
  * [11] W. Qu, Z. Wang, H. Hong, Z. Chi, D. D. Feng, R. Grunstein, and C. Gordon, “A residual based attention model for eeg based sleep staging,” _IEEE Journal of Biomedical and Health Informatics_ , vol. 24, no. 10, pp. 2833–2843, 2020.
  * [12] N. Goshtasbi, R. Boostani, and S. Sanei, “Sleepfcn: A fully convolutional deep learning framework for sleep stage classification using single-channel electroencephalograms,” _IEEE Transactions on Neural Systems and Rehabilitation Engineering_ , vol. 30, pp. 2088–2096, 2022.
  * [13] H. He and E. A. Garcia, “Learning from imbalanced data,” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 21, no. 9, pp. 1263–1284, 2009.
  * [14] D. P. Kingma, “Adam: A method for stochastic optimization/diederik p,” _Kingma, Jimmy Ba, URL: https://arxiv. org/abs/1412.6980_.
  * [15] S. Chang, Z. Yang, Y. You, and X. Guo, “Dssnet: A deep sequential sleep network for self-supervised representation learning based on single-channel eeg,” _IEEE Signal Processing Letters_ , vol. 29, pp. 2143–2147, 2022.
  * [16] H. Phan, F. Andreotti, N. Cooray, O. Y. Chèn, and M. De Vos, “Dnn filter bank improves 1-max pooling cnn for single-channel eeg automatic sleep stage classification,” in _2018 40th Annual International Conference of the IEEE Engineering in Medicine and Biology Society (EMBC)_ , 2018, pp. 453–456.
  * [17] S. Mousavi, F. Afghah, and U. R. Acharya, “Sleepeegnet: Automated sleep stage scoring with sequence to sequence deep learning approach,” _PloS one_ , vol. 14, no. 5, p. e0216456, 2019.
  * [18] C. A. Ellis, R. L. Miller, and V. D. Calhoun, “A novel local explainability approach for spectral insight into raw eeg-based deep learning classifiers,” in _2021 IEEE 21st International Conference on Bioinformatics and Bioengineering (BIBE)_ , 2021, pp. 1–6.
  * [19] A. Kurniawan, “Iot projects with arduino nano 33 ble sense,” _Berkeley: Apress_ , vol. 129, 2021.


###### Abstract

The Erdős–Faber–Lovász Conjecture, posed in 1972, states that if a graph $G$
is the union of $n$ cliques of order $n$ (referred to as defining $n$-cliques)
such that two cliques can share at most one vertex, then the vertices of $G$
can be properly coloured using $n$ colours. Although still open after almost
50 years, it can be easily shown that the conjecture is true when every shared
vertex belongs to exactly two defining $n$-cliques. We here provide a quick
and easy algorithm to colour the vertices of $G$ in this case, and discuss
connections with clique-decompositions and edge-colourings of graphs.

###### keywords:

Erdős–Faber–Lovász Conjecture, chromatic number, clique-decomposition, edge-
colouring

counter-format=(tsk[r]), label-width=4ex

The Erdős–Faber–Lovász Conjecture revisited

John Baptist<EMAIL_ADDRESS>Paul
<EMAIL_ADDRESS>research work disclosed in this publication is
funded by the ENDEAVOUR Scholarship Scheme (Malta). The scholarship may be
part-financed by the European Union – European Social Fund (ESF) under
Operational Programme II – Cohesion Policy 2014–2020, “Investing in human
capital to create more opportunities and promote the well being of
society”.Department of Mathematics, University of Malta, Malta

05C15

##  1 Introduction

For any graph $G$, the _chromatic number_ $\chi(G)$ is the least number of
colours that are required to colour all the vertices of $G$ such that no two
adjacent vertices receive the same colour. In $1972$, Erdős, Faber, and Lovász
posed the following conjecture, whilst at a tea party in Boulder Colorado.

######  Conjecture 1.1 (EFL Conjecture).

[4] If a graph $G$ is the union of $n$ cliques of order $n$, no two of which
share more than one vertex, then $\chi(G)=n$.

For “a proof or disproof” of the conjecture, Paul Erdős initially offered
$50$USD, but then, having seen that the problem is not so trivial and simple
as it seems, he increased his offer to $500$USD. To this day, no complete
solution of this conjecture exists. We refer the reader to [1, 5, 8, 10, 11,
12] for a more thorough introduction to the conjecture and recent results. In
particular, we remark that the fractional version of the EFL Conjecture was
solved by Kahn and Seymour [6] in 1992. Moreover, in January 2021, it was
announced [7] that the conjecture is true for sufficiently large values of
$n$, which to our knowledge, is the best result so far in trying to attack the
EFL Conjecture.

For every positive integer $n$, let $\mathbb{EFL}_{n}$ denote the class of
graphs that are constructed as the union of $n$ cliques $Q_{1},\ldots,Q_{n}$
each of order $n$, such that any two of these $n$ cliques intersect in at most
one vertex. The $n$-cliques $Q_{1},\ldots,Q_{n}$ are referred to as the
_defining_ $n$-cliques, and a vertex which belongs to more than one defining
$n$-clique is said to be _shared_. Conjecture 1.1 is equivalent to saying that
if $G\in\mathbb{EFL}_{n}$, then $\chi(G)=n$. To avoid the trivial case when
$n=1$, we tacitly assume that $n\geq 2$. We also remark that since a graph $G$
belonging to $\mathbb{EFL}_{n}$ contains $n$-cliques, $\chi(G)\geq n$, and so
in order to prove that $\chi(G)=n$ it suffices to provide a proper
$n$-colouring of the vertices of $G$.

Let $\mathcal{G}$ be in $\mathbb{EFL}_{n}$ such that every shared vertex
belongs to exactly two defining $n$-cliques of $\mathcal{G}$. It is known
that, in this case, $\mathcal{G}$ admits a proper $n$-vertex-colouring by
using clique-decompositions and edge-colourings as described in the following
(for a more detailed discussion, the reader is referred to Section 3). In
fact, consider the complete graph $K_{n}$ on $n$ vertices, with each vertex of
$K_{n}$ corresponding to a defining $n$-clique of $\mathcal{G}$ and with every
shared vertex of $\mathcal{G}$ corresponding to an edge of $K_{n}$. By
Vizing’s Theorem, the edges of $K_{n}$ can be properly coloured using at most
$n$ colours, and consequently, the shared vertices of $\mathcal{G}$ can also
be properly coloured using at most $n$ colours. This colouring is then
extended to a proper $n$-colouring of all the vertices of $\mathcal{G}$, as
follows. Every defining $n$-clique of $\mathcal{G}$ contains at most $n-1$
shared vertices, which by the above are all coloured differently. Let
$\mathcal{C}_{i}$ denote the set of colours of the shared vertices belonging
to the defining $n$-clique $Q_{i}$. Since the number of unshared vertices of
$Q_{i}$ is equal to $n-|\mathcal{C}_{i}|$, the unshared vertices of $Q_{i}$
can be assigned mutually different colours from
$\\{\,1,\ldots,n\,\\}-\mathcal{C}_{i}$, yielding a proper $n$-vertex-colouring
of $\mathcal{G}$. Consequently, $\chi(\mathcal{G})=n$, and hence, the EFL
Conjecture holds for this particular instance.

The aim of this note is to present a very simple and straightforward algorithm
that enables the construction of a proper colouring of the vertices of
$\mathcal{G}$ with $n$ colours, when every shared vertex belongs to exactly
two defining $n$-cliques, without having the need to first colour the edges of
the corresponding complete graph $K_{n}$ and then transferring this colouring
to $\mathcal{G}$ (as described above). We first consider the special case when
the number of shared vertices in $\mathcal{G}$ achieves the maximum value
${n\choose 2}$, that is, when every two defining $n$-cliques share a vertex
and every shared vertex belongs to exactly two defining $n$-cliques. Lemma 2.1
gives the algorithm for the case when $n$ is even, and then with the help of
Example 2.3, this is generalised to the case when $n$ is odd (see Proposition
2.4). Finally, in Theorem 2.5, we discuss how this algorithm can be utilised
in the case when the number of shared vertices is less than $\binom{n}{2}$. In
fact, our algorithm properly colours the shared vertices of a graph
$\mathcal{G}\in\mathbb{EFL}_{n}$ (in which every shared vertex belongs to
exactly two defining $n$-cliques) using at most $n$ colours. One can then
extend this colouring to a proper $n$-colouring of all the vertices of
$\mathcal{G}$, as explained above. In Section 3 we discuss a very natural
reformulation of the EFL Conjecture, suggested in [1], in terms of clique-
decompositions and edge-colourings. We end this note by suggesting Problem 3.1
which although we believe is captivating in itself, we think it can shed some
further light on an eventual complete solution of the EFL Conjecture.

Although most of our terminology is standard, we refer the reader to [2] for
further definitions and notation not explicitly stated.

##  2 Main result

For $i$ and $j$ in $\\{\,1,\ldots,n\,\\}$ and $i<j$, if the defining
$n$-cliques $Q_{i}$ and $Q_{j}$ have a shared vertex, then this shared vertex
is denoted by the ordered pair $(i,j)$. Let $\mathcal{G}_{n}$ be the unique
graph in $\mathbb{EFL}_{n}$ having $\binom{n}{2}$ shared vertices, and let
$\mathcal{V}_{n}\subset V(\mathcal{G}_{n})$ be the set of shared vertices of
$\mathcal{G}_{n}$, that is, $|\mathcal{V}_{n}|=\binom{n}{2}$. In this case
every shared vertex belongs to exactly two defining $n$-cliques. We remark
that in what follows the complete residue system used when taking operations
modulo $t$ is $\\{\,1,\ldots,t\,\\}$. We first consider the case when $n$ is
an even integer.

######  Lemma 2.1.

Let $n\geq 2$ be an even integer. The function
$c:\mathcal{V}_{n}\rightarrow\\{\,1,\ldots,n-1\,\\}$, such that

$c\big{(}(i,j)\big{)}\equiv\left\\{\begin{array}[]{rl}i+j\pmod{n-1}&$if
$j<n,\\\ 2i\pmod{n-1}&$if $j=n,\end{array}\right.$

is a proper $(n-1)$-colouring of the vertices in $\mathcal{V}_{n}$.

######  Proof 2.2.

Let $(i,j)$ and $(k,\ell)$ be two adjacent vertices. It suffices to show that
$c\big{(}(i,j)\big{)}\neq c\big{(}(k,\ell)\big{)}$. For contradiction, we
suppose that $c\big{(}(i,j)\big{)}=c\big{(}(k,\ell)\big{)}$. We first note
that exactly one of $i$ and $j$ has to be equal to exactly one of $k$ and
$\ell$. There are five cases that need to be considered.

Case 1. $i=k$ and either $j<\ell<n$ or $\ell<j<n$.

Notwithstanding whether $j<\ell<n$ or $\ell<j<n$, we have $i+j\equiv
k+\ell\equiv i+\ell\pmod{n-1}$, implying that $j\equiv\ell\pmod{n-1}$, a
contradiction. $\blacksquare$

Case 2. $j=\ell<n$ and either $i<k$ or $k<i$.

Notwithstanding whether $i<k$ or $k<i$, we have $i+j\equiv k+\ell\equiv
k+j\pmod{n-1}$, implying that $i\equiv k\pmod{n-1}$, a contradiction.
$\blacksquare$

Case 3. Either $j=k$ or $i=\ell$.

Without loss of generality, let $j=k$. Then, $i<\ell\leq n$ and $j<n$.
Assuming first that $\ell<n$, we get that $i+j\equiv k+\ell\equiv
j+\ell\pmod{n-1}$, implying that $i\equiv j\pmod{n-1}$, a contradiction. Thus,
$\ell=n$, and $i+j\equiv 2k\equiv 2j\pmod{n-1}$, implying that $i\equiv
j\pmod{n-1}$, a contradiction once again. $\blacksquare$

Case 4. $j=\ell=n$ and either $i<k$ or $k<i$.

Notwithstanding whether $i<k$ or $k<i$, we have $2i\equiv 2k\pmod{n-1}$, and
since $n$ is even, this implies that $i\equiv k\pmod{n-1}$, a contradiction.
$\blacksquare$

Case 5. $i=k$ and either $j<\ell=n$ or $\ell<j=n$.

Without loss of generality, let $j<\ell=n$. Then, $i+j\equiv 2k\equiv
2i\pmod{n-1}$, implying that $j\equiv i\pmod{n-1}$, a contradiction.
$\blacksquare$

Hence $c$ is a proper $(n-1)$-colouring of the shared vertices of
$\mathcal{G}_{n}$.

Since every defining $n$-clique of $\mathcal{G}_{n}$ contains $n-1$ shared
vertices, it can be easily seen that the proper $(n-1)$-vertex-colouring given
in Lemma 2.1 can be extended to a proper $n$-vertex-colouring of
$\mathcal{G}_{n}$, by assigning a unique new colour to all the vertices in
$V(\mathcal{G}_{n})-\mathcal{V}_{n}$, implying that $\chi(\mathcal{G}_{n})=n$.

######  Example 2.3.

Here, we use the colouring explained in Lemma 2.1 to obtain a proper
$9$-colouring of the shared vertices of $\mathcal{G}_{10}$. Note that addition
is taken modulo $9$.

_Colours_
---
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
(1,9) | (5,6) | (1,2) | (1,3) | (1,4) | (1,5) | (1,6) | (1,7) | (1,8)
(2,8) | (2,9) | (3,9) | (4,9) | (2,3) | (2,4) | (2,5) | (2,6) | (2,7)
(3,7) | (3,8) | (4,8) | (5,8) | (5,9) | (6,9) | (3,4) | (3,5) | (3,6)
(4,6) | (4,7) | (5,7) | (6,7) | (6,8) | (7,8) | (7,9) | (8,9) | (4,5)
(5,10) | (1,10) | (6,10) | (2,10) | (7,10) | (3,10) | (8,10) | (4,10) | (9,10)
Table 1: A proper $9$-colouring of the shared vertices in $\mathcal{G}_{10}$

Colour $10$ is then given to the vertices in
$V(\mathcal{G}_{10})-\mathcal{V}_{10}$.

Note that if we remove the shared vertices marked bold, the above table
reduces to a proper $9$-colouring of the shared vertices of $\mathcal{G}_{9}$.
In fact, let $n\geq 3$ be an odd integer. The above idea can be used for a
proper $n$-colouring of the shared vertices of $\mathcal{G}_{n}$. More
precisely, by the algorithm given in Lemma 2.1, we know that the colouring

$c\big{(}(i,j)\big{)}\equiv\left\\{\begin{array}[]{rl}(i+j)\pmod{n}&$if
$j<n+1,\\\ 2i\pmod{n}&$if $j=n+1,\end{array}\right.$

provides a proper $n$-colouring of the shared vertices of $\mathcal{G}_{n+1}$,
since $n+1$ is even. Restricting the above colouring to those shared vertices
$(i,j)$ for which $j\leq n$, we get that $c\big{(}(i,j)\big{)}\equiv
i+j\pmod{n}$ is a proper $n$-colouring of the shared vertices of
$\mathcal{G}_{n}$. As before, this gives a proper $n$-colouring of the
vertices in $\mathcal{G}_{n}$, implying that $\chi(\mathcal{G}_{n})=n$. The
next proposition follows immediately from the above arguments.

######  Proposition 2.4.

If $n$ is even, then

$c\big{(}(i,j)\big{)}\equiv\left\\{\begin{array}[]{rl}i+j\pmod{n-1}&$if
$j<n\\\ 2i\pmod{n-1}&$if $j=n,\end{array}\right.$

is a proper $(n-1)$-colouring of the shared vertices of $\mathcal{G}_{n}$.
Otherwise, if $n$ is odd, $c\big{(}(i,j)\big{)}\equiv i+j\pmod{n}$ is a proper
$n$-colouring of the shared vertices of $\mathcal{G}_{n}$. ∎

Now, let $\mathcal{G}\in\mathbb{EFL}_{n}$ for some integer $n$, such that
every shared vertex belongs to exactly two defining $n$-cliques. Let
$\mathcal{V}$ be the set of all the shared vertices of $\mathcal{G}$. Then,
$\mathcal{V}\subseteq\mathcal{V}_{n}$, and so $|\mathcal{V}|\leq\binom{n}{2}$.
Consider the case when $|\mathcal{V}|<\binom{n}{2}$. The colouring $c$ given
in Proposition 2.4 is also a proper colouring of the shared vertices of
$\mathcal{G}$ using at most $n$ colours, since every shared vertex of
$\mathcal{G}$ corresponds to a shared vertex of $\mathcal{G}_{n}$. Hence, the
algorithm described in Proposition 2.4 can be used to provide a proper
colouring of the shared vertices of $\mathcal{G}$ using at most $n$ colours.
As before, this can then be extended to a proper $n$-colouring of all the
vertices of $\mathcal{G}$. We can thus summarise the above results in the
following theorem.

######  Theorem 2.5.

Let $\mathcal{G}\in\mathbb{EFL}_{n}$ such that every shared vertex of
$\mathcal{G}$ belongs to exactly two defining $n$-cliques of $\mathcal{G}$.

  1. (i)

If $n$ is even, then

$c\big{(}(i,j)\big{)}\equiv\left\\{\begin{array}[]{rl}i+j\pmod{n-1}&$if
$j<n\\\ 2i\pmod{n-1}&$if $j=n.\end{array}\right.$

is a proper $(n-1)$-colouring of the shared vertices of $\mathcal{G}$.

  2. (ii)

If $n$ is odd, then $c\big{(}(i,j)\big{)}\equiv i+j\pmod{n}$ is a proper
$n$-colouring of the shared vertices of $\mathcal{G}$.

  3. (iii)

$\chi(\mathcal{G})=n$.

##  3 Clique-decompositions and edge-colourings

We would like to end this note by recalling that, as also indicated above in
Section 1, the EFL Conjecture can be restated in a very simple and intuitive
way in terms of clique-decompositions and edge-colourings of the complete
graph. As far as we know this re-statement of the EFL Conjecture was first
suggested in [1]. Let $H$ be a simple graph on $n$ vertices. A _clique-
decomposition_ of $H$ is a collection
$\mathcal{D}=\\{\,D_{1},\ldots,D_{k}\,\\}$ of subgraphs of $H$, such that each
$D_{i}$ is a clique, and each edge of $H$ belongs to exactly one clique from
$\mathcal{D}$. We denote a clique-decomposition $\mathcal{D}$ of a graph $H$
as $(H,\mathcal{D})$. A _$n$ -colouring of $(H,\mathcal{D})$_ is an assignment
of $n$ colours to the elements of $\mathcal{D}$ such that if $V(D_{i})\cap
V(D_{j})\neq\emptyset$, for some $i\neq j$, then the colours of $D_{i}$ and
$D_{j}$ are distinct. One can easily visualise this as an edge-colouring (not
necessarily proper) of $H$ in which the edges in each $D_{i}$ are
monochromatic, and if for some $i\neq j$, $V(D_{i})\cap
V(D_{j})\neq\emptyset$, then the edges of $D_{i}$ have a different colour than
the edges of $D_{j}$.

Let $G\in\mathbb{EFL}_{n}$ (not necessarily with every shared vertex belonging
to exactly two defining $n$-cliques), and let $H$ be the graph on $n$
vertices, say $v_{1},\ldots,v_{n}$, with edge-set $\\{\,v_{i}v_{j}\mid
V(Q_{i})\cap V(Q_{j})\neq\emptyset,\textrm{ for }i\neq j\,\\}$. We consider
the following clique-decomposition of $H$. Let $\\{\,u_{1},\ldots,u_{k}\,\\}$
be the set of shared vertices of $G$, and, for every
$t\in\\{\,1,\ldots,k\,\\}$, let $\mathcal{I}_{t}$ be the set of indices of all
the defining $n$-cliques containing $u_{t}$. Furthermore, for each
$t\in\\{\,1,\ldots,k\,\\}$, we let $D_{t}$ be the subgraph of $H$ induced by
the vertices $\\{\,v_{i}\mid i\in\mathcal{I}_{t}\,\\}$. Consequently, the set
$\mathcal{D}=\\{\,D_{1},\ldots,D_{k}\,\\}$ is a clique-decomposition of $H$.
If there exists a $n$-colouring of $(H,\mathcal{D})$, then there exists a
vertex colouring of the shared vertices of $G$ using $n$ colours, implying
that $\chi(G)=n$.

In general, one can deduce that every graph in $\mathbb{EFL}_{n}$ gives rise
to a simple graph on $n$ vertices with a clique-decomposition, and by a
similar argument, every simple graph on $n$ vertices with a clique-
decomposition corresponds to some graph in $\mathbb{EFL}_{n}$. The case
considered in Section 2 corresponds to the case when every clique in
$\mathcal{D}$ is a $2$-clique. Moreover, as in the previous section, if one
can show that for every possible clique-decomposition $\mathcal{D}$ of
$K_{n}$, $(K_{n},\mathcal{D})$ admits a $n$-colouring, then the EFL Conjecture
would be true. Although a proof of the conjecture for all sufficiently large
values of $n$ was recently announced [7], we still believe that such a problem
deserves to be studied further and solved for the other instances as well, as
this could give insights into related areas such as clique-decompositions and
edge-colourings of graphs, which have been already studied such as in [3, 9].
In this sense, we suggest the following problem which we think could be a
possible way forward.

######  Problem 3.1.

Let $\mathcal{D}$ be a clique-decomposition of $K_{n}$, such that every clique
in $\mathcal{D}$ is either a 2-clique or a $r$-clique, for some fixed
$r\in\\{\,3,\ldots,n-1\,\\}$. Determine whether $(K_{n},\mathcal{D})$ has a
$n$-colouring, and, if in the affirmative, whether an efficient algorithm to
find such a $n$-colouring exists.

## References

  * [1] G. Araujo-Pardo and A. Vázquez-Ávila: A note on Erdős–Faber–Lovász Conjecture and edge coloring of complete graphs, Ars Comb. 129 (2016), 287–298.
  * [2] J.A. Bondy and U.S.R. Murty: Graph Theory, Grad. Texts in Math. 244, Springer-Verlag London, 2008.
  * [3] S. Ehard and E. Mohr: Rainbow triangles and cliques in edge-colored graphs, Eur. J. Comb. 84 (2020), 103037.
  * [4] P. Erdős: On the combinatorial problems which I would most like to see solved, Combinatorica 1(1) (1981), 25–42.
  * [5] S.M. Hegde and S. Dara: Further results on Erdős–Faber–Lovász conjecture, AKCE Int. J. Graphs Comb. (2019), https://doi.org/10.1016/j.akcej.2019.03.003.
  * [6] J. Kahn and P.D. Seymour: A fractional version of the Erdős–Faber–Lovász conjecture, Combinatorica 12(2) (1992), 155–160.
  * [7] D.Y. Kang, T. Kelly, D. Kühn, A. Methuku and D. Osthus: A proof of the Erdős–Faber–Lovász conjecture, 2021, https://arxiv.org/abs/2101.04698.
  * [8] H. Klein and M. Margra: A remark on the conjecture of Erdős, Faber and Lovász, J. Geom. 88 (2008), 116–119.
  * [9] H. Liu, O. Pikhurko and T. Sousa: Monochromatic Clique Decompositions of Graphs, J. Graph Theory 80(4) (2015), 287–298.
  * [10] D. Romero and A. Sánchez-Arroyo: Adding evidence to the Erdős–Faber–Lovász conjecture, Ars Combin. 85 (2007), 71–84.
  * [11] D. Romero and A. Sánchez-Arroyo: The Erdős–Faber–Lovász conjecture is true for $n\leq 12$, Discrete Math. Algorithms Appl. 6(3) (2014), 1450039.
  * [12] A. Sánchez-Arroyo: The Erdős–Faber–Lovász conjecture for dense hypergraphs, Discrete Math. 308 (2008), 991–992.