# Non-Binary LDPC Code Design for Energy-Time Entanglement Quantum Key
Distribution

Debarnab Mitra, Lev Tauz, Murat Can Sarihan, Chee Wei Wong, and Lara Dolecek
Department of Electrical and Computer Engineering, University of California,
Los Angeles, USA
email<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>and<EMAIL_ADDRESS>
###### Abstract

In energy-time entanglement Quantum Key Distribution (QKD), two users extract
a shared secret key from the arrival times (discretized as symbols) of
entangled photon pairs. In prior work, Zhou _et al._ proposed a _multi-level
coding_ (MLC) scheme that splits the observed symbols into bit layers and
utilizes binary Low-Density Parity-Check (LDPC) codes for _reconciliation_ of
the symbols. While binary LDPC codes offer low latency for key generation,
splitting the symbols into bits results in a loss of key generation rate due
to error propagation. Additionally, existing LDPC codes do not fully utilize
the properties of the QKD channel to optimize the key rates. In this paper, we
mitigate the above issues by first generalizing the MLC scheme to a non-
binary(NB) MLC scheme that has layers with non-binary symbols and utilizes NB-
LDPC codes. We show the NB-MLC scheme offers flexibility in system design.
Additionally, we show that the NB-MLC scheme with a small symbol size per
layer offers the best trade-off between latency and key rate. We then propose
a framework to jointly optimize the rate and degree profile of the NB-LDPC
codes that is tailored towards the QKD channel resulting in higher key rates
than prior work.

##  I Introduction

Quantum Key Distribution (QKD) provides a physically secure way to share a
secret key between two users, Alice and Bob, over a quantum communication
channel in the presence of an eavesdropper Eve [1, 2, 3]. Energy-time
entanglement QKD (ET-QKD) protocols have been studied extensively in
literature due to their ability to extract multiple bits per generated
entangled photon pairs [3, 4]. At a high level, an ET-QKD protocol consists of
the following steps [5]: i) In the first step, called _generation_ , Alice and
Bob generate _raw keys_ using a quantum channel that are represented as
sequences of symbols. Due to imperfections in the quantum channel, the raw
keys at Alice and Bob may disagree in some positions; ii) In the second step,
called _information reconciliation_ (IR), Alice and Bob communicate over a
public channel (accessible to Eve) to reconcile the raw keys; iii) In the
third step, called _privacy amplification_ (PA), Alice and Bob amplify the
privacy of the reconciled key by accounting for Eve’s knowledge to generate
the final shared secret key. Channel coding is utilized in the IR step to
ensure that Alice and Bob arrive at an identical sequence of symbols. In this
paper, similar to [5], we focus on the IR step of the protocol and assume that
if we communicate $m$ bits during the IR step, then PA results in a loss of
$m$ bits from the length of the reconciled key to get the shared secret key.
The _key rate_ of the system is defined as the average length of the shared
secret key obtained by Alice and Bob after PA.

A promising coding framework proposed to get high key rates is called the
_multi-level coding_ (MLC) scheme [5] that has been considered for works such
as [3, 6]. In the MLC scheme, the sequence of symbols after the generation
step is converted into multiple bit layers and then each bit layer is
sequentially reconciled using binary LDPC codes. Binary LDPC codes have low
complexity and fast decoding algorithms and hence result in low latency and
complexity for key generation. However, the MLC coding scheme suffers from
error propagation where a decoding error in one of the bit layers results in
decoding errors in subsequent bit layers leading to reduced key rates.
Contrary to the MLC scheme with binary LDPC codes, non-binary (NB) LDPC codes
that directly encode the generated symbols do not suffer from error
propagation. Hence, NB-LDPC code can naturally lead to higher key rates.
However, the symbols in the generation step can belong to a Galois field of
size as large as $2^{10}$ and it is known that iterative decoding of NB-LDPC
codes has a very high complexity (log-linear in the field size[7]) leading to
high latency for the key generation. Hence, baseline NB-LDPC codes with large
field sizes are not favorable in QKD applications requiring low latency, such
as in [8, 9].

In addition to the above latency vs. key rate trade-off, the LDPC codes used
previously in the IR step of ET-QKD protocols have not fully utilized the
properties of the ET-QKD channel. For example, [5] used a standard LDPC
ensemble without optimization. Similarly, spatially-coupled (SC) LDPC codes,
irregular repeat accumulate (IRA) codes, SC-IRA codes, and multi-edge-type
(MET) codes have been discussed for the continuous-variable (CV) QKD [10, 11].
However, these works focus on channel models such as binary input additive
white Gaussian noise (BIAWGN) that do not match the ET-QKD channel [12].

A unique property of the ET-QKD problem considered in this paper is that the
key rate of the system is closely dependent on both the rate of the code and
the frame error rate (FER) performance. Fig. 2 shows the FER and key rates
obtained by a random LDPC code for different values of rate. From this graph,
we see that increasing the code rate can improve the key rate even at the cost
of higher FER, a phenomenon we see in both binary and non-binary LDPC codes.
Additionally, the maximum in the key rate occurs for a relatively large value
of FER ($\sim 5$%). While the conventional code design approach is to minimize
the FER to a very small value for a given rate, in this case, the goal is to
jointly optimize both the rate and the FER to achieve the largest key rate.

The degree distribution of an LDPC code is known to affect its FER
performance. Degree distribution optimization techniques for LDPC codes based
on code thresholds (e.g., [13]) optimize the degree distribution for a fixed
rate and hence are not directly applicable to the current ET-QKD problem that
needs a joint rate and FER optimization. Additionally, the optimized degree
distributions are designed for non-QKD channels (e.g., BIAWGN in [13]) and
they do not result in large key rates as we demonstrate in Section V.

Figure 1: QKD system model. The arrival times of photons are discretized using
pulse position modulation. Each frame has $2^{q}$ bins and the spacing between
frames in called binwidth.

Coding RateKey RateFER

Coding RateKey RateFER

Figure 2: Key rate and FER vs. coding rate. Left panel: NB-LDPC code in
$\mathbb{GF}(2^{6})$; Right panel: Binary LDPC code. Maximum in the key rate
occurs at FER around 0.05 in both figures.

In the paper, we mitigate the above issues of latency vs. key rate trade-off
and code design considering the properties of the ET-QKD channel using a two-
pronged approach. Firstly, we generalize the MLC scheme of [5] to a non-binary
MLC scheme by splitting the symbols after the generation step into multiple
layers with non-binary symbols belonging to a smaller Galois field. The NB-MLC
scheme offers a natural trade-off between latency and key rate depending on
the size of the symbols in a layer, allowing flexibility in system design.
Additionally, we demonstrate that the NB-MLC scheme with a small symbol size
per layer results in higher key rates compared to a fully binary scheme [5] as
well as using a fully non-binary scheme without layering. Secondly, we provide
a joint rate and degree distribution optimization (JRDO) framework based on
differential evolution [14] for the construction of the NB-LDPC codes in each
layer of the NB-MLC scheme. The JRDO framework uses the QKD channel
information and we demonstrate that it results in a higher key rate compared
to the LDPC codes used in the MLC scheme [5] and that obtained by utilizing
degree distributions optimized for conventional channels such as the BIAWGN
channel [13]. The rest of this paper is organized as follows. In section II,
we provide the preliminaries and the system model. In section III, we describe
the NB-MLC scheme. In section IV, we provide the JRDO framework. Finally, we
provide simulation results in section V and conclude the paper in section VI.

##  II Preliminaries and System Model

###  II-1 ET-QKD system model

As shown in Fig. 1, in ET-QKD [3], energy-time entangled photon pairs are
generated by a third party in the generation step. Alice and Bob then receive
one photon each out of the pair who then record the arrival times of the
received photons. The raw key information is derived from the arrival times.
In this method, Alice and Bob both synchronize their timelines and then
discretize their time into frames where each frame is further divided into
$2^{q}$ bins of equal size, where $q$ is a positive integer. Alice and Bob
retain only time frames in which they both detect a single photon arrival and
discard all other frames. The photon arrival time in a non-discarded frame is
then converted (discretized) into a symbol in $\mathbb{GF}(2^{q})$ based on
the bin number the received photon occupies within each frame. The discretized
sequences received by Alice and Bob are then divided into blocks each having
$N$ symbols where $N$ is the code length. Let
$\mathbf{X}=\\{X_{1},\ldots,X_{N}\\}$, $X_{i}\in\mathbb{GF}(2^{q})$ and
$\mathbf{Y}=\\{Y_{1},\ldots,Y_{N}\\}$, $Y_{i}\in\mathbb{GF}(2^{q})$ be the
sequences of length $N$ recorded by Alice and Bob, respectively. Due to
imperfections in the generation step (e.g., timing jitters, transmission loss
[5]) $\mathbf{Y}$ is a noisy version of $\mathbf{X}$. We assume the sequences
$\mathbf{X}$ and $\mathbf{Y}$ are memoryless and each $Y_{i}$ is the output of
the ET-QKD channel characterized by transition law $P_{Y|X}$ and input
$X_{i}$.

A simple IR protocol based on NB-LDPC codes in $\mathbb{GF}(2^{q})$ proceeds
as follows. Alice sends Bob $\mathbf{S}=\mathbf{H}\mathbf{X}$ over the public
channel (which is accessible to Eve) where
$\mathbf{H}\in\mathbb{GF}(2^{q})^{M\times N}$ is the parity check matrix of an
NB-LDPC code. Bob decodes $\mathbf{X}$ using the received $\mathbf{S}$ and
side information $\mathbf{Y}$. LDPC decoding using side information is
encountered in the Slepian-Wolf (SW) problem [16]. SW LDPC decoding is very
similar to the sum-product decoder used in conventional decoding of LDPC
channel codes with small differences in the way the log-likelihood messages
are initialized and the CN to VN messages. We refer the reader to [16] for
details about SW LDPC decoding. The goal of the NB-LDPC code is to make the
decoding output equal to $\mathbf{X}$ with high probability while ensuring
that the information leaked to Eve is minimized. Finally, the sequence
$\mathbf{X}$ is the reconciled key that is passed to the PA step. The key rate
$r$ (in bits per photon) of the above scheme (similar to [5]) is given as
follows:

$r=q(1-E)\frac{N-M}{N},$ (1)

where $E$ is the FER incorporated in the decoding of $\mathbf{X}$. Note that
we subtract $M$ in Eqn. (1) since $M$ symbols are sent over the public channel
and hence will be lost due to PA.

###  II-2 ET-QKD channel

In this paper, we use empirical data from a practical ET-QKD system testbed[4]
to estimate the channel transition law $P_{Y|X}$ directly. For interested
readers, authors in [12] have demonstrated a modeling that provides a good
approximation of the ET-QKD channel. Succinctly, the ET-QKD channel is a
mixture of _local_ and a _global_ channel with Gaussian and uniform
distributions. The uniform distribution causes a low SNR in our system
resulting in a high operating FER ($\sim 1-10\%$). Note that the ET-QKD
channel is different from conventional channels such as AWGN, BSC, etc. As
such, codes that have been optimized for these channels are not necessarily
the best ones for the ET-QKD channel as we demonstrate in Section V.

###  II-3 NB-LDPC codes

A NB-LDPC code over $\mathbb{GF}(2^{q})$ is defined by a sparse parity check
matrix $\mathbf{H}\in\mathbb{GF}(2^{q})^{M\times N}$. The matrix $\mathbf{H}$
has a Tanner graph representation comprising of $M$ check nodes (CNs) and $N$
variable nodes (VNs) corresponding to rows and columns of $\mathbf{H}$. A CN
is connected to a VN by an edge if the corresponding entry in $\mathbf{H}$ is
non-zero where the edge is additionally labeled by the non-zero entry. The
interconnection between VNs and CNs of a code is represented by degree
distributions $L(x)=\sum_{d}L_{d}x^{d}$ and $P(x)=\sum_{d}P_{d}x^{d}$, where
$L_{d}$ and $P_{d}$ represent the fraction of nodes connected respectively to
VNs and CNs of degree $d$. The coding rate $R$ of the code is given by
$R=1-\frac{L^{\prime}(1)}{P^{\prime}(1)}$. The FER performance of the code
depends on the degree distributions $L(x)$ and $P(x)$. In this paper, we
optimize the rate $R$ and VN degree distribution $L(x)$. For given $R$ and
$L(x)$, we find a two-element distribution $P(x)$ that results in rate $R$.
Now for the degree distributions $L(x)$ and $P(x)$, parity check matrix
$\mathbf{H}$ is randomly sampled among the ensemble of LDPC codes that match
these degree distributions [15] and label each edge uniformly at random with a
non-zero element of $\mathbb{GF}(2^{q})$. In the next section, we propose the
NB-MLC scheme for IR.

##  III Non-Binary Multi-Level Coding

The NB-MLC scheme offers a tradeoff between key rate $r$ and
latency/complexity of key generation through an integer parameter $a$, $1\leq
a\leq q$. Let $b$ and $r$ be integers such that $q=ab+r$, where
$b=\lfloor\frac{q}{a}\rfloor$ and $r$ is the remainder when $q$ is divided by
$a$. Each symbol $X$ in $\mathbf{X}$ received by Alice is an element of
$\mathbb{GF}(2^{q})$. We split $X$ into $b+1$ symbols $(X_{1},X_{2},\ldots
X_{b+1})$, where $X_{i}\in\mathbb{GF}(2^{a}),1\leq i\leq b$ and
$X_{b+1}\in\mathbb{GF}(2^{r})$ using an injective mapping
$u:\mathbb{GF}(2^{q})\rightarrow\mathbb{GF}(2^{a})^{b}\times\mathbb{GF}(2^{r})$.
Using the above conversion, we split the sequence $\mathbf{X}$ into $b+1$
layers $(\mathbf{X}_{1},\mathbf{X}_{2},\ldots,\mathbf{X}_{b+1})$, where
$\mathbf{X}_{i}\in\mathbb{GF}(2^{a})^{N},1\leq i\leq b$ and
$\mathbf{X}_{b+1}\in\mathbb{GF}(2^{r})^{N}$. Let $\alpha_{i}$ denote the bit
size of the symbols in the $i$th layer. We have $\alpha_{i}=a,1\leq i\leq b$
and $\alpha_{b+1}=r$. For each layer $i$, we use a NB-LDPC code
$\mathbf{H}_{i}$ where
$\mathbf{H}_{i}\in\mathbb{GF}(2^{\alpha_{i}})^{m_{i}\times N}$ for $1\leq
i\leq b+1$. Now, Alice generates a message
$\mathbf{S}=\\{\mathbf{S}_{1},\mathbf{S}_{2},\ldots,\mathbf{S}_{b+1}\\}$ by
setting $\mathbf{S}_{i}=\mathbf{H}_{i}\mathbf{X}_{i}$, $1\leq i\leq b+1$ and
sends it to Bob over the public channel. Using $\mathbf{S}$ and $\mathbf{Y}$,
Bob decodes every layer $\mathbf{X}_{i},1\leq i\leq b+1$ and hence
$\mathbf{X}$ which is the reconciled key.

Let
$\widehat{\mathbf{X}}_{1}^{i-1}:=\\{\widehat{\mathbf{X}}_{1},\widehat{\mathbf{X}}_{2},\ldots,\widehat{\mathbf{X}}_{i-1}\\}$
be the decoding result of layers $1,2,\ldots i-1$. Similar to [5], Bob decodes
layer $\mathbf{X}_{i}$ with received message $\mathbf{S}_{i}$, and side
information $\mathbf{Y}$ and $\widehat{\mathbf{X}}_{1}^{i-1}$ using SW
decoding for NB-LDPC codes [16]. The equivalent channel for the $i$th layer
takes input $\mathbf{X}_{i}$ and outputs
$\\{\mathbf{Y},\mathbf{X}_{1}^{i-1}\\}$ with transition law
$\gamma^{i}:=P(Y=y,X^{i-1}_{1}=x^{i-1}_{1}|X_{i}=x_{i})$. We derive the
transition law $\gamma^{i}$ empirically from our QKD testbed and use it in
Section IV for code optimization.

The size of massage $\mathbf{S}_{i}$ sent by Alice for the reconciliation of
the $i$th layer is $m_{i}$. Let $E_{i}$ be the FER for the $i$th layer. The
key rate of the NB-MLC scheme is obtained by adding the key rates of each
layer (similar to [5]) and is given by

$r=\sum_{i=1}^{b+1}\alpha_{i}(1-E_{i})\frac{N-m_{i}}{N}.$ (2)

The key rate depends on the coding rates $R_{i}=\frac{N-m_{i}}{N}$ of
$\mathbf{H}_{i}$ used in layer $i$. The parameter $a$ in the NB-MLC scheme
affects the key rate as well as the latency and hardware complexity (which
are, respectively, the sum of the decoding latencies and the sum of the
complexities of all the layers). Note that $a=1$ gives us the binary MLC
scheme of [5] and $a=q$ provides a completely non-binary scheme with only one
layer. As $a$ is increased from $1$ to $q$, the complexity monotonically
increases. However, as we demonstrate in Section V, the key rates are not
monotonic in $a$.

Finally, the performance of the system in terms of the key rate and latency
also depends on the mapping $u(X)$ used to split the symbols
$X\in\mathbb{GF}(2^{q})$ into symbols of different layers. For convenience, we
use the following mapping. We first convert $X$ into its binary representation
$X_{b}$. We then split the bits in $X_{b}$ into $b+1$ groups with the $i$th
group having $\alpha_{i}$ bits. We then treat the bits in each group $i$ as a
binary representation and convert them back to a symbol in
$\mathbb{GF}(2^{\alpha_{i}})$. A study on the effects of different mappings on
the key rate and latency is beyond the scope of this paper and is part of
future work. In the next section, we provide the JRDO framework based on
differential evolution to jointly optimize the rate and degree distribution of
the NB-LDPC codes.

##  IV Joint Rate and
Degree Distribution Optimization

In this section, we provide the framework to design parity check matrices
$\mathbf{H}_{i}$, $1\leq i\leq b+1$ for use in the $i$th layer of the NB-MLC
scheme with channel transition probability
$\gamma^{i}:=P(Y=y,X^{i-1}_{1}=x^{i-1}_{1}|X_{i}=x_{i})$. The construction
method is the same for all layers, hence we drop index $i$. In particular, we
design the VN degree distribution $L(x)$ and rate $R$ for $\mathbf{H}$ (see
Section II-3 for how a non-binary $\mathbf{H}$ is generated from $L(x)$ and
$R$). The channel transition probability is $\gamma$.

$a$Key Rate

$a$Latency (in ms)

Latency (in ms)Key Rate

Figure 3: Key rate and latency for different $q$ as the NB-MLC bit size $a$ is
varied. The ET-QKD system has a binwidth of 300ps. Left panel: Key rate vs.
$a$; Middle panel: Latency vs. $a$; Right panel: Key rate vs. latency where
each point on a curve for a particular $q$ represents a different value of $a$
(the values of $a$ are marked on the curves). All curves use LDPC codes
mentioned in Section II-3 with $L(x)=x^{3}$.

Our framework utilizes differential evolution (DE) [14] to find $L(x)$ and
$R$. DE is a popular and effective population-based evolutionary algorithm
that can be used for a maximization (or minimization) of any function $f()$.
The algorithm iteratively improves a candidate solution (that maximizes $f()$)
using an evolutionary process and can explore large design spaces with low
complexity. DE has been extensively used in coding theory literature to design
good irregular LDPC codes for the erasure channel [17], AWGN channel [13],
Rayleigh fading channel [18], etc. The goal in these works is to design degree
distributions that have low FER. This goal is achieved using DE where the
function $f()$ is generally set as some low complexity predictor of the FER
performance of the code such as the threshold obtained by density evolution
[13]. However, as discussed in section I, the goal for us in this paper is to
maximize the key rate and not merely to minimize the FER. Additionally, the
techniques for optimizing the degree distributions using code thresholds work
for a fixed code rate and we have not found any previous work that jointly
optimizes the code rate along with maximizing the threshold.

In this paper, following the expression for key rate in Eqn. (2), we jointly
optimize the degree distribution $L(x)$ and the coding rate $R$ using DE by
setting $f(L(x),R)=(1-E)R$. Here, $E$ is the expected FER of a code ensemble
with degree distribution $L(x)$ and rate $R$ on a channel with transition law
$\gamma$. Note that to be able to optimize the above function using DE
feasibly, the cost of computing the function must be low (since the DE
algorithm evaluates the function $f()$ a certain fixed number of times at
every iteration). However, as discussed in Section II-2, since the FER of the
code is high ($\sim 1-10\%$), the FER $E$ can be easily computed using Monte-
Carlo (MC) simulations with a small number of MC experiments (e.g., 200-300).
The overall JRDO algorithm is provided in Algorithm 1 where the procedures
DiffMutation() and CrossOver() have regular meanings as per [14]. The
contribution in Algorithm 1 is the use of the objective function
$f(L(x),R)=(1-E)R$ and its feasible evaluation using MC simulations owing to
the high FER property of the ET-QKD channel thus making the joint optimization
possible.

Binwidth (in ps)Key Rate

$a$Key Rate

Binwidth (in ps)Key Rate

Figure 4: Left panel: Key rate vs. binwidth for different values of NB-MLC bit
size $a$. The QKD system has $2^{6}$ bins per frame; Middle panel: Key rate
vs. $a$ for different LDPC codes. The QKD system has $2^{5}$ bins per frame
and a binwidth of 300ps; Right panel: Key rate vs. binwidth for different LDPC
codes. The NB-MLC scheme uses $a=3$. The QKD system has $2^{6}$ bins per
frame. Algorithm 1 JRDO: Joint Rate and deg. Dist. optimization

1:Initialize population
$\Pi=\\{(L_{1},R_{1}),\ldots,(L_{N_{pop},R_{N_{pop}}})\\}$

2:for max number of iterations do

3: for $j=1:N_{pop}$ do

4: $(L^{m}_{j},R^{m}_{j})=$DiffMutation$(j,\Pi)$

5: $(L^{c}_{j},R^{c}_{j})=$
CrossOver$\big{(}(L^{m}_{j},R^{m}_{j}),(L_{j},R_{j})\big{)}$

6: Evaluate $f(L^{c}_{j},R^{c}_{j})$ using Monte-Carlo simulations

7: for $j=1:N_{pop}$ do

8: if $f(L^{c}_{j},R^{c}_{j})>f(L_{j},R_{j})$ then

9: Update population: $(L_{j},R_{j})\leftarrow(L^{c}_{j},R^{c}_{j})$

10:Output: $(L,R)$ from $\Pi$ with largest $f(L,R)$

##  V Simulation Results

In this section, we demonstrate the performance of the NB-MLC scheme and the
performance of the codes designed using the JRDO algorithm. We compare the
performance with the MLC scheme of [5] as well as with codes used in [5] and
codes designed for the BIAWGN channel [13]. For the JRDO framework, we
optimize degree distribution $L(x)=\sum_{d=2}^{5}L_{d}$ where we set $L_{1}$
to be zero and a maximum VN degree of 5. For non-JRDO codes, we find and use
the rate that results in the largest key rate (for that particular layer of
the NB-MLC scheme) by exhaustively iterating over the message length $m_{i}$.
The latency of the NB-MLC scheme is calculated as the sum of the decoding
latencies of all the layers in the NB-MLC scheme. We use a code length
$N=2000$ and FFT-based sum-product LDPC decoding (SW version [16]) in our
simulations.

In Fig. 3, we study the effect of the MLC bit size $a$ on

the key rate and latency of the QKD system. Recall that the QKD system has
$2^{q}$ bins per frame implying a total bit size of $q$. From Fig. 3 left
panel, we can see that for all values of $q$, the key rate is non-monotonic in
$a$ and has a maximum when $a$ is strictly between $1$ and $q$. The reason the
key rate is non-monotonic in $a$ is the following. Increasing the value of $a$
makes the NB-MLC scheme use NB-LDPC codes from a larger Galois field which are
stronger resulting in greater FER performance and hence better key rates per
layer. However, due to layering, correct decoding in the earlier layers still
contributes to the overall key rate even if decoding failures exist in the
later layers. This additive effect (due to Eqn. (2)) improves the overall key
rate with more layers (small $a$). Due to the above two effects, the overall
key rate is non-monotonic. In Fig. 3 middle panel, we plot the latency of the
NB-MLC scheme as a function of $a$ for different values of $q$. From the plot,
we see that the latency becomes significantly large as $a$ becomes large
(close to $q$). This trend is because a larger $a$ implies an NB-LDPC code
from a larger Galois field and hence a larger decoding latency. Note that as
$a$ increases, the increase in decoding complexity is sometimes offset by the
decrease in the number of decoding layers in the NB-MLC scheme, and thus
latency is non-monotonic in $a$ (also evident in Fig. 3 right panel). In Fig.
3 right panel, we plot the key rate vs. latency achieved due to different
values of $a$ in the NB-MLC scheme. From the figure, it is clear that the best
trade-off is obtained for a small value of $a$ (3 or 4). Increasing $a$
further results in higher latency at no increase in key rates.

In Fig. 4 left panel, we compare the key rates across different values of
binwidths in a QKD system with $q=6$. We compare the key rates for $a=1,3$,
and $6$. Similar to Fig. 3, we can again see that across all binwidths, $a=3$
has a higher key rate compared to $a=1$ (MLC scheme of [5] with binary LDPC
codes) and $a=6$ (a scheme with complete NB-LDPC codes and no layering).
Overall, the NB-MLC scheme with a small value of $a>1$ results in the best
system performance.

In Fig. 4 middle and right panels, we compare the key rates obtained by
different code constructions. The diamond marked curves correspond to LDPC
codes used in [5]. As per [5], these LDPC codes are randomly constructed such
that each VN has a constant degree of 3. Note that there is no limitation on
the CN degree distribution in [5]. However, the LDPC codes considered in this
paper (see Section II-3) have a two-element CN degree distribution. The
triangle marked curves correspond to the degree distribution provided in [13,
Table I] with a maximum VN degree 5. Note that this degree distribution is
optimized for the BIAWGN channel. The circle marked curves correspond to LDPC
codes with regular VN degree distribution $L(x)=3$ (similar to [5]) but with a
two-element CN degree distribution. Finally, the square marked curves
correspond to degree distributions obtained using the JRDO algorithm. From the
figures, we make the following observations. The key rates for the diamond
marked curves are worse compared to the circle marked curves. This trend
suggests that it is better to use a two-element CN degree distribution (as
done in our paper). The key rates for the triangle marked curves (BIAWGN
optimized degree distribution) are worse compared to using regular LDPC codes
with VN degree 3 (circle marked curves). This trend demonstrates that codes
optimized for non-QKD channels do not perform well when used for the QKD
channel. Finally, in Fig. 4 middle and right panels, we see that JRDO-LDPC
codes (square marked curves) result in the largest key rates which is because
the JRDO-LDPC codes are optimized for the QKD channel. In Fig. 4 right panel,
we additionally plot the key rates achieved using the techniques of [5] i.e.,
MLC scheme ($a=1$) and VN degree 3 regular LDPC codes and no limitation on CN
degree distribution (plus marked curve). We see that our techniques (square
marked curve) provide around 40% improvement in key rates compared to [5].

##  VI Conclusion

In this paper, we considered the problem of information reconciliation in ET-
QKD and proposed a generalization of the multi-level coding (MLC) scheme of
[5] called NB-MLC that uses NB-LDPC codes. We showed that the NB-MLC scheme
offers flexibility in system design in terms of key rate and latency, and the
NB-MLC scheme with a small bit size per layer results in the best trade-off
between key rate and latency. Finally, we proposed a framework based on
different evolution called JRDO that jointly optimizes the rate and degree
distribution for the LDPC codes used in the NB-MLC scheme. JRDO-LDPC codes are
optimized for the ET-QKD channel and result in a significant improvement in
the key rates compared to LDPC codes used in prior work. Ongoing research is
focused on optimizing the edge weight distributions (along with JRDO) to
further improve the key rates.

## Acknowledgement

The authors acknowledge the NSF grant QuIC-TAQS no. 2137984 and NSF grant
EFRI-ACQUIRE no. 1741707.

## References

  * [1] C. H. Bennett and G. Brassard, “Quantum cryptography: Public key distribution and coin tossing," _IEEE International Conference on Computers, Systems, and Signal Processing_ , 1984.
  * [2] H.-K. Lo, M. Curty, and K. Tamaki, “Secure quantum key distribution," _Nature Photonics_ , vol. 8, no. 8, 2014.
  * [3] T. Zhong, _et al._ , “Photon-efficient quantum key distribution using time-energy entanglement with high-dimensional encoding," _New Journal of Physics_ , vol. 17, no. 2, 2015.
  * [4] K.-C. Chang, _et al._ , “648 Hilbert-space dimensionality in a biphoton frequency comb: entanglement of formation and schmidt mode decomposition," _npj Quantum Information_ , vol. 7, no. 1, 2021.
  * [5] H. Zhou, L. Wang, and G. Wornell, “Layered schemes for large-alphabet secret key distribution," _IEEE Inf. Theory and App. Workshop_ , Feb. 2013.
  * [6] C. Lee, _et al._ , “Large-alphabet encoding for higher-rate quantum key distribution," _Optics express_ , vol. 27, no. 13, 2019.
  * [7] M. C. Davey and D. MacKay, “Low density parity check codes over GF(q)," _IEEE Communication Letters_ , vol. 2, 1998.
  * [8] J. Martinez-Mateo, D. Elkouss, and V. Martin, “Key reconciliation for high performance quantum key distribution," _Scientific Rep._ , vol. 3, 2013.
  * [9] S. Wehner, D. Elkouss, and R. Hanson, “Quantum internet: A vision for the road ahead,’ _Science_ , vol. 362, no. 6412, 2018.
  * [10] X.-Q. Jiang, _et al._ , “High-speed reconciliation for CVQKD based on spatially coupled LDPC codes," _IEEE Photon. J._ , vol. 10, no. 4, 2018.
  * [11] S. J. Johnson, V. A. Chandrasetty, and A. M. Lance, “Repeat-accumulate codes for reconciliation in continuous-variable quantum key distribution," _IEEE Australian Communications Theory Workshop_ , pp. 18–23, 2016.
  * [12] S. Yang, _et al._ , “Efficient information reconciliation for energy-time entanglement quantum key distribution" _IEEE Asilomar Conference on Signals, Systems, and Computers_ , Nov. 2019.
  * [13] T. J. Richardson, M. A. Shokrollahi, and R. L.Urbanke, “Design of capacity-approaching irregular low-density parity-check codes," _IEEE Transactions on Information Theory_ , vol. 47, no. 2, 2001.
  * [14] R. Storn and K. Price, “Differential evolution-A simple and efficient heuristic for global optimization over continuous spaces," _J. Global Optim._ , vol. 11, no. 4, 1997.
  * [15] T. Richardson, and R. Urbanke, “Modern coding theory," _Cambridge: Cambridge University Press_ , 2008.
  * [16] E. Dupraz, V. Savin and M. Kieffer, “Density Evolution for the Design of Non-Binary Low Density Parity Check Codes for Slepian-Wolf Coding," _IEEE Transactions on Communications_ , vol. 63, no. 1, 2015.
  * [17] A. Shokrollahi and R. Storn, “Design of efficient erasure codes with differential evolution," _IEEE Int. Symp. on Inf. Theory_ , Jun. 2000.
  * [18] J. Hou, P. H. Siegel, and L. B. Milstein, “Performance analysis and code optimization of low density parity-check codes on Rayleigh fading channels," _IEEE J. on Sel. Areas in Commun._ , vol. 19, no. 5, 2001.


$f^{\xi,y_{1}}(s_{n})+f^{\xi,y_{2}}(s_{n})=0$. Inequality (5.3) implies
$s_{n+1}<s_{n}<s_{n-1}$ for all $n>N$, and one can define the open sets

$\displaystyle S_{n}$
$\displaystyle:=\left\\{s\in(s_{n+1},s_{n-1})\,:\,f^{\xi,y_{1}}(s)+f^{\xi,y_{2}}(s)<0\right\\},$
$\displaystyle U_{n}$ $\displaystyle:=\left\\{\tau
g_{\xi,y_{1}}(s)+(1-\tau)g_{\xi,y_{2}}(s)\,:\,\tau\in(0,1),\,s\in
S_{n}\right\\}.$

For each $n>N$, the set $U_{n}$ is contained in the interior
$\textrm{int}\,R_{n}$ of the closed rectangle

$R_{n}:=\Big{\\{}x+s\xi+t(x-y_{1})\,:\,s_{n+1}\leq s\leq s_{n-1},\,\inf_{s\in
S_{n}}\left\\{f^{\xi,y_{1}}(s)\right\\}\leq t\leq-\inf_{s\in
S_{n}}\left\\{f^{\xi,y_{2}}(s)\right\\}\Big{\\}}.$

By definition $s_{n}\in S_{n}$ for all $n>N$, from which it follows that
$x_{n}\notin\partial V$ for any open $V\subset E_{\varepsilon}^{c}\cap
R_{n}^{c}$. On the other hand $x_{n}\in\partial U$ for all $n\in\mathbb{N}$
which implies $U\subset\textrm{int}\,R_{n}$ for all $n\in\mathbb{N}$, since
$U$ is connected and $\partial R_{n}\cap E_{\varepsilon}^{c}=\varnothing$ by
definition. However, given that $x\in\partial U\cap R_{n}^{c}$, this leads to
the contradiction $U\subset R_{n}\cap R_{n}^{c}$ for all $n>N$. ∎

Lemmas 5.4 and 5.6 below state that the sets of one-sided shallow
singularities (S4) and chain singularities (S6) are both at most countably
infinite. The argument in both cases rests on the fact that for any finite sum
$M:=\sum_{x\in A}m_{x}<\infty$ of non-negative real numbers $m_{x}$ indexed by
a (potentially uncountable) set $A$, the index subset $A_{0}:=\\{x\in
A\,:\,m_{x}>0\\}$ corresponding to the positive elements in the sum is at most
countably infinite.222This follows from the observation that the set
$A_{n}:=\\{x\in A\,:\,m_{x}>1/n\\}$ is finite for each $n\in\mathbb{N}$ and
hence $A_{0}:=\\{x\in A\,:\,m_{x}>0\\}=\bigcup_{n\in\mathbb{N}}A_{n}$ is
countable as a countable union of finite sets. In the case of shallow
singularities, the numbers being summed will represent lengths (one-
dimensional Hausdorff measures) $m_{x}:=\mathcal{H}^{1}(I_{x})$ of boundary
segments $I_{x}\subset\partial E_{\varepsilon}$, and in the case of chain
singularities they will stand for surface areas
$m_{x}:=\mathcal{H}^{2}(A_{x})$ of open subsets
$A_{x}\subset\mathrm{int}\,E_{\varepsilon}$. In each case, these numbers will
be strictly positive by definition for every $x$, implying that the underlying
index sets—corresponding to the sets of singularities in question—are
themselves at most countably infinite.

######  Lemma 5.4 (Number of one-sided shallow singularities).

For a compact set $E\subset\mathbb{R}^{2}$, the number of one-sided shallow
singularities (S4) on $\partial E_{\varepsilon}$ is at most countably
infinite.

###### Proof.

Write $W$ for the set of one-sided shallow singularities on $\partial
E_{\varepsilon}$, and consider some $x\in W$. By definition of a one-sided
shallow singularity, there exists a
$\xi\in\Xi_{x}^{\mathrm{ext}}(E_{\varepsilon})$ and $\delta>0$ for which
$J_{x}:=U_{\delta}(x,\xi)\cap\partial
E_{\varepsilon}\subset\mathrm{Unp_{\varepsilon}}(E)$. Due to Proposition 3.5
there exists a local boundary representation $\mathcal{G}(x)$ and some some
$r(x)>0$ for which $J_{x}=g_{\xi,y}([0,r(x)])$, where
$\Pi_{E}^{\mathrm{ext}}(x)=\\{y\\}$ and $g_{\xi,y}\in\mathcal{G}(x)$,
satisfies

$g_{\xi,y}(s)=x+s\xi+f^{\xi,y}(s)(x-y)$

for some continuous $f:[0,\varepsilon/2]\to\mathbb{R}$. In particular, the
open subsegment $I_{x}:=g_{\xi,y}((0,r(x)/2))\subset J_{x}$ contains only
smooth points and has a positive, finite length
$r(x)/2<\mathcal{H}^{1}(I_{x})<\infty$. This follows for instance from the
fact that $g_{\xi,y}$ satisfies $|s-w|\leq\left\lVert
g_{\xi,y}(s)-g_{\xi,y}(w)\right\rVert\leq 2|s-w|/\sqrt{3}$ for all
$s,w\in(0,r(x)/2)$ (see Proposition 3.6) and since the increase of the
Hausdorff measure under a Lipschitz map is bounded by the Lipschitz constant
(see for instance [1, Proposition 2.49]). If $z\neq x$ is another one-sided
shallow singularity, the corresponding segment $I_{z}$ satisfies $I_{z}\cap
I_{x}=\varnothing$ by definition. Hence, the collection $I:=\bigcup_{x\in
W}I_{x}\subset\partial E_{\varepsilon}$ has finite length

(5.5) $\mathcal{H}^{1}(I)=\sum_{x\in
W}\mathcal{H}^{1}(I_{x})<\mathcal{H}^{1}(E_{\varepsilon})<\infty.$

The last inequality in (5.5) was established already by Erdős in [11, Section
6]. According to the counting argument preceding the statement of the result,
inequality (5.5) implies that the set $W$ can be at most countably infinite. ∎

The following example demonstrates that the set of two-sided shallow
singularities (S5) can be dense and have positive Hausdorff measure on the
boundary $\partial E_{\varepsilon}$. The idea is to construct a suitably
jagged function on the interval $[0,1]$ (say) and interpret its graph as a
subset of the boundary $\partial E_{\varepsilon}$ of a corresponding set
$E\subset\mathbb{R}^{2}$.

######  Example 5.5 (Dense, positive measure set of shallow singularities).

Consider a bounded, increasing function $\alpha:[0,1]\to\mathbb{R}$ that is
discontinuous at every rational number $q\in\mathbb{Q}\cap[0,1]$ but
continuous at every irrational number $p\in[0,1]\setminus\mathbb{Q}$.333One
way to construct such a function is to write
$\mathbb{Q}\cap[0,1]=\big{\\{}q_{n}\,:\,n\in\mathbb{N}\big{\\}}$, define
$N(x):=\\{n\,:\,q_{n}\leq x\\}$, take any positive summable sequence
$(a_{n})_{n=1}^{\infty}$, and set $\alpha(x):=\sum_{n\in N(x)}a_{n}$ for all
$x\in[0,1]$. This way $\alpha$ is increasing on $[0,1]$, has a jump of
amplitude $a_{n}$ at each rational $x=q_{n}$, is continuous at every
$x\in[0,1]\setminus\mathbb{Q}$, and satisfies
$\alpha(1)=\sum_{n=1}^{\infty}a_{n}<\infty$. As an almost everywhere
continuous bounded function, every such $\alpha$ is Riemann-integrable, and
its monotonicity implies that the integral function
$I_{\alpha}(x):=\int_{0}^{x}\alpha(s)ds$ is convex. Most significantly for our
example, $I_{\alpha}$ has a well-defined derivative at every irrational
$p\in[0,1]\setminus\mathbb{Q}$, but not at any rational
$q\in\mathbb{Q}\cap[0,1]$.

For any $\varepsilon>0$, one may thus interpret the graph
$G:=\big{\\{}(s,I_{\alpha}(s))\,:\,s\in[0,1]\big{\\}}$ as a subset of an
boundary $\partial E_{\varepsilon}$ as follows. Since the one-sided
derivatives

$D^{\pm}I_{\alpha}(s):=\lim_{h\to\pm
0}\frac{I_{\alpha}(s+h)-I_{\alpha}(s)}{h}$

exist at every $s\in[0,1]$, one can define for each $x(s):=(s,I_{\alpha}(s))$
the corresponding contributors $y^{-}(s),y^{+}(s)\in\Pi_{E}(x(s))$ by setting
$y^{\pm}(s):=\big{(}s+a^{\pm}(s),\,I_{\alpha}(s)-b^{\pm}(s)\big{)}$, where for
each $s\in[0,1]$

$a^{\pm}(s):=\frac{\varepsilon
D^{\pm}I_{\alpha}(s)}{\sqrt{1+\big{[}D^{\pm}I_{\alpha}(s)\big{]}^{2}}}\qquad\textrm{and}\qquad
b^{\pm}(s):=\frac{\varepsilon}{\sqrt{1+\big{[}D^{\pm}I_{\alpha}(s)\big{]}^{2}}}.$

A direct computation shows that $D^{\pm}I_{\alpha}(s)=b^{\pm}(s)/a^{\pm}(s)$
and $\left\lVert x(s)-y^{\pm}(s)\right\rVert=\varepsilon$ for all $s\in[0,1]$.
Furthermore, the convexity of $I_{\alpha}$ implies that for each $y^{\pm}(s)$
the ball $\overline{B_{\varepsilon}(y^{\pm}(s))}$ intersects $G$ only at the
corresponding $x(s)$, which implies that $G\subset\partial E_{\varepsilon}$
for the set $E:=\\{y^{\pm}(s)\,:\,s\in[0,1]\\}$.

By construction, $y^{+}(p)=y^{-}(p)$ for the irrational
$p\in[0,1]\setminus\mathbb{Q}$, whereas $y^{+}(q)>y^{-}(q)$ for all rational
$q\in\mathbb{Q}\cap[0,1]$. Hence $x(q)$ is a wedge for each rational $q$ while
$x(p)\in\mathrm{Unp_{\varepsilon}}(E)$ for every irrational $p$, which implies
that the points $x(p)$ are in fact two-sided shallow singularities (S5). Due
to the continuity of $I_{\alpha}$, these points form a dense set on $G$. Given
that $I_{\alpha}$ is convex and absolutely continuous as an integral function,
and the derivative $\alpha$ is bounded, $I_{\alpha}$ is in fact Lipschitz
continuous with some Lipschitz constant $K$. It then follows from the basic
properties of Hausdorff measure (see for instance [1, Proposition 2.49]) and
the rectifiability of $\partial E_{\varepsilon}$ (see [27, Proposition 2.3]
and [12, Corollary 3.3]) that
$\mathcal{H}^{1}([0,1])\leq\mathcal{H}^{1}(G)<\infty$ and the set
$P:=\big{\\{}(p,I_{\alpha}(p))\,:\,p\in[0,1]\setminus\mathbb{Q}\big{\\}}$ of
two-sided singularities has full measure on $G$.

######  Lemma 5.6 (Number of one-sided chain singularities).

For a compact set $E\subset\mathbb{R}^{2}$, the number of one-sided chain
singularities (S6) on $\partial E_{\varepsilon}$ is at most countably
infinite.

###### Proof.

Write $C$ for the set of one-sided chain singularities on $\partial
E_{\varepsilon}$. We argue that there exists a collection $\\{A_{x}\\}_{x\in
C}$ of pair-wise disjoint open sets
$A_{x}\subset\textrm{int}\,E_{\varepsilon}$, indexed by $C$. The result then
follows from the counting argument discussed in the lead-up to Lemma 5.4
above.

For each $x\in C$, the set of outward directions is a singleton
$\Xi_{x}(E_{\varepsilon})=\\{\xi\\}$. Let $x\in C$ and let $\mathcal{G}(x)$ be
a local boundary representation at $x$ so that for $i\in\\{1,2\\}$ and
$g_{\xi,y_{i}}\in\mathcal{G}(x)$

$g_{\xi,y_{i}}(s)=x+s\xi+f^{\xi,y_{i}}(s)(x-y_{i})$

for some continuous functions $f^{\xi,y_{i}}:[0,\varepsilon/2]\to\mathbb{R}$.
It follows from the definition of one-sided chain singularities that the
extremal contributors $y_{1},y_{2}\in\Pi_{E}^{\mathrm{ext}}(x)$ satisfy
$y_{1}-x=-(y_{2}-x)$ for all $x\in C$. Since
$-\xi\notin\Xi_{x}(E_{\varepsilon})$, there are two possibilities:

  * (i)

there exists some non-extremal contributor $y\in\Pi_{E}(x)$ for which $\langle
y-x,\xi\rangle<0$, or else

  * (ii)

there exists some $\delta_{0}\in\mathbb{R}_{+}$ such that for all
$\delta<\delta_{0}$,

$\overline{B_{\varepsilon}(E\cap
U_{\delta}(y_{1},-\xi))}\cap\overline{B_{\varepsilon}(E\cap
U_{\delta}(y_{2},-\xi))}\setminus\\{x\\}\neq\varnothing$

(see Proposition 3.1 for clarification). In both cases there exists some
$p(x)<0$ for which

(5.6)
$Q(x):=\big{\\{}x+s\xi+t(x-y_{1})\,:\,p(x)<s<0,\,-\varepsilon/2<t<\varepsilon/2\big{\\}}\subset\mathrm{int}\,E_{\varepsilon}.$

One can then define $A_{x}:=U_{p(x)/3}(x,-\xi)$. Note that for all $x\in C$
the set $A_{x}$ is open and has a positive surface area
$\mathcal{H}^{2}(A_{x})>0$. Furthermore, $A_{x}\subset
Q(x)\subset\textrm{int}\,E_{\varepsilon}$ and it follows from the construction
that if $z\neq x$ is any other one-sided chain singularity, its distance from
$x$ satisfies $|z-x|\geq p(x)$, implying $A_{x}\cap A_{z}=\varnothing$. The
sets $A_{x}$ are thus pair-wise disjoint, open and contained in some bounded
ball $B_{R}(0)$ due to the compactness of $E_{\varepsilon}$. Hence the sum
$\sum_{x\in C}\mathcal{H}^{2}(A_{x})$ of their surface areas is finite, from
which the result follows by the counting argument discussed in the lead-up to
Lemma 5.4. ∎

####  5.1.1. Proof of Theorem 2

We conclude this section with the proof of Theorem 2, which combines Lemmas
5.2–5.4 and 5.6 into one statement.

######  Theorem 2 (Countable sets of singularities).

For a compact set $E\subset\mathbb{R}^{2}$, the number of wedges (S1), sharp
singularities (S2, S3 and S8) and one-sided shallow singularities (S4) and
chain singularities (S6) on $\partial E_{\varepsilon}$ is at most countably
infinite.

###### Proof.

Consider the collection $\\{U_{i}\\}_{i\in I}$ of the connected components of
$E_{\varepsilon}^{c}$. Since $E$ is assumed to be compact, $E\subset B_{R}(0)$
for some $R>0$. It follows that all but one (denote this by $U_{j}$) of the
connected components $U_{i}$ are bounded, so that

$\bigcup_{i\in I\setminus\\{j\\}}U_{i}\subset B_{R}(0).$

Following the counting argument presented immediately before the statement of
Lemma 5.4, this implies that the index set $I$ is at most countably infinite.
By definition every sharp singularity (S2, S3, S8) $x\in\partial
E_{\varepsilon}$ satisfies $x\in\bigcup_{i\in I}\partial U_{i}$. It follows
then from Lemma 5.3 that the set of sharp singularities on $\partial
E_{\varepsilon}$ is countable as a countable union of finite sets. Finally,
Lemmas 5.2, 5.4 and 5.6 guarantee that the number of wedges (S1) and one-sided
shallow (S4) and chain (S6) singularities (respectively) are at most countably
infinite, and the proof is complete. ∎

###  5.2. Chain Singularities Form a Totally Disconnected Set

We conclude the paper by showing that the set $\mathcal{C}(\partial
E_{\varepsilon})$ of chain singularities (types S6–S8) is closed and totally
disconnected. This implies that $\mathcal{C}(\partial E_{\varepsilon})$ is
nowhere dense, meaning that it is small in the topological sense, even though
it may have a positive one-dimensional Hausdorff measure on the boundary.

Before presenting the proof of the above result, we provide a concrete example
of a set $E\subset\mathbb{R}^{2}$ and $\varepsilon>0$ for which the one-
dimensional Hausdorff measure of the set of chain-chain singularities on
$\partial E_{\varepsilon}$ is positive. Essentially, we analyse [27, Example
2.2] from the geometric point of view.

######  Example 5.7 (A set of chain singularities with positive measure).

Let $C\subset[0,1]$ be a 'fat' Cantor set (a Cantor set with positive one-
dimensional Hausdorff measure) and consider the set
$E:=\big{\\{}(s,t)\in\mathbb{R}^{2}\,:\,s\in C,\,t\in\\{0,1\\}\big{\\}}$. The
Cantor set is obtained by removing from the interval $[0,1]$ a certain
countable collection $\mathcal{I}:=\\{I_{n}\,:\,n\in\mathbb{N}\\}$ of open
subintervals. By construction $C$ is totally disconnected and thus contains no
intervals itself, and since it is uncountable, most of the points $s\in C$ do
not lie on the boundary of any of the removed intervals. Denote the collection
of these points by $C^{*}:=C\setminus\bigcup_{n\in\mathbb{N}}\partial I_{n}$.
By construction, every $s\in C^{*}$ is however an accumulation point of
$\bigcup_{n\in\mathbb{N}}I_{n}$. Since the sets $I_{n}$ are open, it is clear
that for $\varepsilon=1/2$ the sets $V_{n}:=\\{(s,1/2)\,:\,s\in I_{n}\\}$
satisfy $V_{n}\subset E_{\varepsilon}^{c}$ for all $n\in\mathbb{N}$. Thus, for
every point $x\in A:=\\{(s,1/2)\,:\,s\in C^{*}\\}\subset\partial
E_{\varepsilon}$ there exists a sequence $(w_{m})_{m=1}^{\infty}\subset
E_{\varepsilon}^{c}$, where $w_{m}=(s_{m},1/2)\in V_{m}$ for some $s_{m}\in
I_{n(m)}$, and $s_{m}\to s$ as $m\to\infty$. We can also assume that
$I_{n(m)}\neq I_{n(m^{\prime})}$ whenever $m\neq m^{\prime}$. For the
connected components $W_{m}\supset V_{m}$ of $E_{\varepsilon}^{c}$ this
implies $W_{m}\neq W_{m^{\prime}}$ whenever $m\neq m^{\prime}$. It is easy to
see that condition (ii) in Proposition 4.5 thus holds true for all $x\in A$ so
that $A\subset\mathcal{C}(\partial E_{\varepsilon})$. Hence
$\mathcal{H}^{1}(\mathcal{C}(\partial
E_{\varepsilon}))\geq\mathcal{H}^{1}(A)=\mathcal{H}^{1}(C^{*})>0$ due to the
translation invariance of Hausdorff measure.

####  5.2.1. Proof of Theorem 3

The proof of our third main result builds on many of the results presented in
the previous sections. To show that the set of chain singularities is closed,
we combine Proposition 3.9 regarding the connectedness of the complement
$E_{\varepsilon}^{c}$ near wedges and $x\in\mathrm{Unp_{\varepsilon}}(E)$ with
the characterisation of chain singularities provided by Proposition 4.5. The
second part of the proof also makes use of the basic results established in
Section 2.2.

######  Theorem 3 (The set of chain singularities is closed and totally
disconnected).

For any compact set $E\subset\mathbb{R}^{2}$ and $\varepsilon>0$, the set
$\mathcal{C}(\partial E_{\varepsilon})$ of chain singularities is closed and
totally disconnected.

###### Proof.

We begin by showing that the complement $\partial
E_{\varepsilon}\setminus\mathcal{C}(\partial E_{\varepsilon})$ is open. To
this end, consider some $x\in\partial
E_{\varepsilon}\setminus\mathcal{C}(\partial E_{\varepsilon})$. If $x$ is a
wedge (S1) or if $x\in\mathrm{Unp_{\varepsilon}}(E)$, Proposition 3.9 implies
that there exists some neighbourhood $B_{r}(x)$ and a connected subset
$V_{x}\subset E_{\varepsilon}^{c}$ for which

(5.7) $B_{r}(x)\cap E_{\varepsilon}^{c}=B_{r}(x)\cap V_{x}.$

One the other hand, Proposition 4.5 states that each chain singularity
$x\in\mathcal{C}(\partial E_{\varepsilon})$ is associated with a sequence
$(V_{n})_{n=1}^{\infty}\subset E_{\varepsilon}^{c}$ of disjoint connected
components of the complement $E_{\varepsilon}^{c}$, for which
$\mathrm{dist}_{H}(x,V_{n})\to 0$ as $n\to\infty$. Equation (5.7) hence
implies that $B_{r}(x)\cap\mathcal{C}(\partial E_{\varepsilon})=\varnothing$.
Similarly, for a sharp singularity (type S2) or a sharp-sharp singularity
(type S3), Proposition 4.2 implies the existence of a neighbourhood $B_{r}(x)$
for which $B_{r}(x)\cap\mathcal{C}(\partial E_{\varepsilon})=\varnothing$.
Hence $\partial E_{\varepsilon}\setminus\mathcal{C}(\partial E_{\varepsilon})$
is open on the boundary.

To demonstrate that $\mathcal{C}(\partial E_{\varepsilon})$ is totally
disconnected, we show that for any two chain singularities
$x,z\in\mathcal{C}(\partial E_{\varepsilon})$ there exist disjoint open sets
$A_{x},A_{z}\subset\mathbb{R}^{2}$ for which $x\in A_{x},z\in A_{z}$ and
$\mathcal{C}(\partial E_{\varepsilon})\subset(A_{x}\cup A_{z})\cap\partial
E_{\varepsilon}$. More specifically, we will consider for each
$x\in\mathcal{C}(\partial E_{\varepsilon})$ and $s_{1}\leq 0\leq s_{2}$ the
sets

(5.8)
$A_{x,\xi}(s_{1},s_{2}):=\big{\\{}x+s\xi+t(x-y_{1})\,:\,s_{1}<s<s_{2},\,\,-\varepsilon/2<t<\varepsilon/2\big{\\}}$

and show that for each $z\in\mathcal{C}(\partial
E_{\varepsilon})\setminus\\{x\\}$ there exist
$\xi\in\Xi_{x}^{\mathrm{ext}}(E_{\varepsilon})$ and $s_{1}<0<s_{2}$ for which
$\partial A_{x,\xi}(s_{1},s_{2})\cap\mathcal{C}(\partial
E_{\varepsilon})=\varnothing$ and $z\notin A_{x,\xi}(s_{1},s_{2})$.

Given that $x$ is a chain singularity, Proposition 4.2 implies that for $r>0$
the boundary region $\partial E_{\varepsilon}\cap U_{r}(x,\xi)$ exhibits
'chain-type' geometry near $x$ for at least one extremal outward direction
$\xi\in\Xi_{x}^{\mathrm{ext}}(E_{\varepsilon})$. We begin by assuming that
$\xi$ is such a direction, and consider the corresponding sets
$A_{x,\xi}(0,s)$ for $s>0$. Writing $R(z):=\left\lVert z-x\right\rVert$, our
aim is to find some $s<R(z)/2$ for which $\partial
A_{x,\xi}(0,s)\cap\mathcal{C}(\partial E_{\varepsilon})=\\{x\\}$. To this end,
let $\mathcal{G}(x)$ be a local boundary representation at $x$ and let
$f^{\xi,y_{1}},f^{\xi,y_{2}}:[0,\varepsilon/2]\to\mathbb{R}$ be the continuous
functions for which

$g_{\xi,y_{i}}(s)=x+s\xi+f^{\xi,y_{i}}(s)(x-y_{i})$

for every $g_{\xi,y_{i}}\in\mathcal{G}(x)$, $i\in\\{1,2\\}$ and all
$s\in[0,\varepsilon/2]$. As argued in the proof of Proposition 4.2 (ii), there
exist sequences $(s_{n})_{n=1}^{\infty}\subset\mathbb{R}_{+}$ and
$(p_{n})_{n=1}^{\infty}\subset\mathbb{R}_{+}$ for which

  * •

$p_{n}<s_{n}\leq p_{n-1}<s_{n-1}$ for all $n\in\mathbb{N}$,

  * •

$f^{\xi,y_{1}}(s)+f^{\xi,y_{2}}(s)=0$ for all
$s\in(s_{n})_{n=1}^{\infty}\cup(p_{n})_{n=1}^{\infty}$, and

  * •

$f^{\xi,y_{1}}(s)+f^{\xi,y_{2}}(s)<0$ for all $s\in(p_{n},s_{n})$ and
$n\in\mathbb{N}$.

It follows that the open set

$V_{n}:=\big{\\{}\tau
g_{\xi,y_{1}}(s)+(1-\tau)g_{\xi,y_{2}}(s)\,:\,\tau\in(0,1),\,s\in(p_{n},s_{n})\big{\\}}$

is a connected component of the complement $E_{\varepsilon}^{c}$ for all
$n\in\mathbb{N}$. Consequently there exists some $N\in\mathbb{N}$ for which
$\mathrm{dist}_{H}(V_{n},x)<R(z)/2$ whenever $n\geq N$. The definition of the
sets $V_{n}$ implies that for each $n\geq N$, the boundary point
$x_{n}^{(1)}:=g_{\xi,y_{1}}\big{(}\frac{p_{n}+s_{n}}{2}\big{)}\in\partial
V_{n}\subset\partial E_{\varepsilon}$ has an outward direction aligned with
the vector

$\eta_{n}^{(1)}:=g_{\xi,y_{2}}\left(\frac{p_{n}+s_{n}}{2}\right)-g_{\xi,y_{1}}\left(\frac{p_{n}+s_{n}}{2}\right)=-\left(f^{\xi,y_{1}}\left(\frac{p_{n}+s_{n}}{2}\right)+f^{\xi,y_{2}}\left(\frac{p_{n}+s_{n}}{2}\right)\right)(x-y_{1})$

(the reader is encouraged to compare this with equation (4.3) in the proof of
Proposition 4.2), and the analogous expression (obtained by replacing the
roles of $y_{1}$ and $y_{2}$) holds true for $x_{n}^{(2)}$ and
$\eta_{n}^{(2)}$ defined similarly. We claim that there exists some $n\geq N$,
for which $x_{n}^{(i)}\notin\mathcal{C}(\partial E_{\varepsilon})$ for
$i\in\\{1,2\\}$. Assume this were not the case. Then it follows from the
definition of chain-singularities and Proposition 2.12 that for at least one
$i\in\\{1,2\\}$ we have
$\eta_{n}^{(i)}\in\Xi_{x_{n}^{(i)}}^{\mathrm{ext}}(E_{\varepsilon})$ for
infinitely many $n\geq N$. By virtue of the definition of the sets $V_{n}$ as
regions between the graphs $g_{\xi,y_{i}}$, and since $x_{n}^{(i)}\in\partial
V_{n}\subset\partial E_{\varepsilon}$ for all $n\in\mathbb{N}$, it follows
from Proposition 2.14 that
$\xi=\lim_{n\to\infty}\big{(}x_{n}^{(i)}-x\big{)}\big{/}\big{\|}x_{n}^{(i)}-x\big{\|}$
for $i\in\\{1,2\\}$. But then, due to Lemma 2.13 (ii)(b), we have

$0=\left\langle\frac{x-y_{i}}{\varepsilon},\,\xi\right\rangle=\lim_{n\to\infty}\big{\langle}\eta_{n}^{(i)},\xi\big{\rangle}=1,$

which is impossible. Thus, there exists some $n\in\mathbb{N}$ for which
$x_{n}^{(i)}\notin\mathcal{C}(\partial E_{\varepsilon})$ for $i\in\\{1,2\\}$,
which in turn implies that $\partial
A_{x,\xi}\big{(}0,(p_{n}+s_{n})/2\big{)}\cap\mathcal{C}(\partial
E_{\varepsilon})=\\{x\\}$, since

$\partial A_{x,\xi}\left(0,\frac{p_{n}+s_{n}}{2}\right)\cap\partial
E_{\varepsilon}=\big{\\{}x,x_{n}^{(1)},x_{n}^{(2)}\big{\\}}.$

In the remainder of the proof we consider one by one the cases of one-sided
chain (S6), chain-chain (S7) and sharp-chain (S8) singularities, and identify
the sets $A_{x}$ and $A_{z}$ mentioned in the beginning of the proof.

(i) Assume $x$ is a one-sided chain singularity (S6), so that
$\Xi_{x}^{\mathrm{ext}}(E_{\varepsilon})=\\{\xi\\}$ for some $\xi\in S^{1}$.
By the argument presented above, there exists some $0<s_{2}<R(z)/2$ for which
$\partial A_{x,\xi}\big{(}0,s_{2}\big{)}\cap\mathcal{C}(\partial
E_{\varepsilon})=\\{x\\}$. On the other hand, according to the reasoning
presented in the proof of Lemma 5.6, the set

$Q_{p}(x):=\big{\\{}x+s\xi+t(x-y_{1})\,:\,p<s<0,\,-\varepsilon/2<t<\varepsilon/2\big{\\}}$

satisfies $Q_{p}(x)\subset\mathrm{int}\,E_{\varepsilon}$ for some $p<0$ (see
equation (5.6)). By setting $s_{1}:=-\mathrm{min}\big{\\{}p,R(z)/2\big{\\}}$
it follows then that $\partial A_{x,\xi}(s_{1},s_{2})\cap\mathcal{C}(\partial
E_{\varepsilon})=\varnothing$ and we may define
$A_{x}:=A_{x,\xi}(s_{1},s_{2})$ and
$A_{z}:=\big{(}\mathbb{R}^{2}\setminus\overline{A_{x}}\big{)}$.

(ii) Assume then that $x$ is a chain-chain singularity (S7) with
$\Xi_{x}^{\mathrm{ext}}(E_{\varepsilon})=\\{\xi,-\xi\\}$ for some $\xi\in
S^{1}$. Since now both of the extremal outward directions $\xi$ and $-\xi$ are
associated with 'chain'-type geometry, one can again utilise the argument
above in order to choose for $\xi_{1}:=\xi$ and $\xi_{2}:=-\xi$ the
corresponding $s_{1},s_{2}>0$ for which $\partial
A_{x,\xi_{i}}\big{(}0,s_{i}\big{)}\cap\mathcal{C}(\partial
E_{\varepsilon})=\\{x\\}$ and $s_{i}<R(z)/2$ for $i\in\\{1,2\\}$. By setting
$s_{3}=\mathrm{min}\\{s_{1},s_{2}\\}$ we may define
$A_{x}:=A_{x,\xi}(-s_{3},s_{3})$ and
$A_{z}:=\big{(}\mathbb{R}^{2}\setminus\overline{A_{x}}\big{)}$.

(iii) Finally, assume that $x$ is a sharp-chain singularity (S8) with
$\Xi_{x}^{\mathrm{ext}}(E_{\varepsilon})=\\{\xi,-\xi\\}$ for some $\xi\in
S^{1}$. We may assume that $\xi$ is associated with 'chain'-type geometry, so
that once again we have $\partial
A_{x,\xi}\big{(}0,s_{2}\big{)}\cap\mathcal{C}(\partial
E_{\varepsilon})=\\{x\\}$ for some $0<s_{2}<R(z)/2$ due to the arguments
presented above. For the direction $-\xi$, Proposition 4.2 (i) implies that
there exists some $r>0$ for which

$E_{\varepsilon}^{c}\cap U_{r}(x,-\xi)=V\cap
U_{r}(x,-\xi)=\bigcup_{0<s<r}x+s\big{(}\alpha(s),\beta(s)\big{)}_{S^{1}},$

where $V$ is the unique connected component of $E_{\varepsilon}^{c}$
intersecting $U_{r}(x,-\xi)$, $\alpha(s),\beta(s)\in S^{1}$ for all
$s\in(0,r)$ and $\alpha(s),\beta(s)\to-\xi$ as $s\to 0$. It follows then from
the definition of chain singularity that
$U_{r}(x,-\xi)\cap\mathcal{C}(\partial E_{\varepsilon})=\varnothing$. By
setting $s_{1}=-\mathrm{min}\\{r/2,\varepsilon/2,R(z)/2\\}$ we may thus define
$A_{x}:=A_{x,\xi}(s_{1},s_{2})$ and
$A_{z}:=\big{(}\mathbb{R}^{2}\setminus\overline{A_{x}}\big{)}$ and the proof
is complete. ∎

The set $\mathcal{I}$ of inaccessible singularities (types S6 and S7) inherits
the properties of being totally disconnected and nowhere dense, but it may
generally fail to be closed. Since the set $\mathcal{C}(\partial
E_{\varepsilon})$ on the other hand is compact and separable as a subset of
$\mathbb{R}^{2}$, it follows from the Cantor-Bendixson Theorem (see [19, Thm.
6.4]) that whenever the cardinality of the chain-chain singularities (type S7)
is uncountable, the set $\mathcal{C}(\partial E_{\varepsilon})$ can be written
as a disjoint union $\mathcal{C}(\partial E_{\varepsilon})=C\cup P$, where $C$
is homeomorphic to the Cantor set and $P$ is countable. For further
information on totally disconnected spaces, see [19].

## Acknowledgements

This project has received funding from the European Union's Horizon 2020
research and innovation Programme under the Marie Skłodowska-Curie grant
agreement no. 643073. The authors express their gratitude to Gabriel Fuhrman,
Vadim Kulikov, Tuomas Orponen, Sebastian van Strien and Dmitry Turaev for many
useful discussions and valuable comments regarding earlier versions of this
article.

## References

  * [1] L. Ambrosio, N. Fusco, and D. Pallara, _Functions of Bounded Variation and Free Discontinuity Problems_ , Oxford University Press, 2000\.
  * [2] J.-P. Aubin and H. Frankowska, _Set-Valued Analysis_ , Birkhäuser, Boston, 1990.
  * [3] F. Bigolin and G. H. Greco, _Geometric characterizations of ${C}^{1}$-manifolds in euclidean spaces by tangent cones_, J. Math. Anal. Appl. 396 (2012), 145–163.
  * [4] A. Blokh, M. Misiurewicz, and L. Oversteegen, _Sets of constant distance from a compact set in 2-manifolds with a geodesic metric_ , Proc. Amer. Math. Soc. 137 (2009), no. 2, 733–743.
  * [5] G. Bouligand, _Sur les surfaces dépourvues de points hyperlimites_ , Ann. Soc. Polon. Math. 9 (1930), 32–41.
  * [6] by same author, _Introduction á la géométrie infinitésimale directe_ , Gauthier-Villars, 1932.
  * [7] M. Brown, _Sets of constant distance from a planar set_ , Michigan Math. J. 19 (1972), 321–323.
  * [8] F. H. Clarke, _Generalized gradients and applications_ , Trans. Am. Math. Soc. 205 (1975), 247–262.
  * [9] F. Colonius and W. Kliemann, _The Dynamics of Control_ , Birkhäuser, Boston, 2000.
  * [10] M. D. Donsker and S. R. S. Varadhan, _Asymptotics for the Wiener Sausage_ , Comm. Pure and Appl. Math. 28 (1975), 525–565.
  * [11] P. Erdős, _Some remarks on the measurability of certain sets_ , Bull. Amer. Math. Soc. 51 (1945), no. 10, 728–731.
  * [12] K. J. Falconer, _The geometry of fractal sets_ , Cambridge University Press, 1985.
  * [13] H. Federer, _Curvature measures_ , Trans. Amer. Math. Soc. 93 (1959), 418–491.
  * [14] S. Ferry, _When $\varepsilon$-boundaries are manifolds_, Fund. Math. 90 (1976), 199–210.
  * [15] J.H.G. Fu, _Tubular neighborhoods in Euclidian spaces_ , Duke Mathematical Journal 52 (1985), no. 4, 1025–1046.
  * [16] Y. Hamana, _On the expected volume of the Wiener sausage_ , J. Math. Soc. Japan 62 (2010), no. 1, 1113–1136.
  * [17] A. Kac and J. M. Luttinger, _Bose-Einstein condensation in the presence of impurities_ , J. Math. Phys. 14 (1973), 1626–1628.
  * [18] A. Käenmäki, J. Lehrbäck, and M. Vuorinen, _Dimensions, Whitney covers, and tubular neighborhoods_ , Indiana Univ. Math. J. 62 (2013), no. 6, 1861–1889.
  * [19] A.S. Kechris, _Classical descriptive set theory_ , Graduate Texts in Mathematics, pp. 31–32, 35–36, Springer-Verlag, 1995.
  * [20] B. Klartag, _Eldan's Stochastic Localization and Tubular Neighborhoods of Complex-Analytic Sets_ , The Journal of Geometric Analysis 28 (2018), 2008–2018.
  * [21] J.S.W. Lamb, M. Rasmussen, and C. Rodrigues, _Topological bifurcations of minimal invariant sets for set-valued dynamical systems_ , Proceedings of the American Mathematical Society 143 (2015), no. 9, 3927–3937.
  * [22] S. Nekovar and G. Pruessner, _A Field-Theoretic Approach to the Wiener Sausage_ , Journal of Statistical Physics 163 (2016), 604–641.
  * [23] I. Ya. Oleksiv and N. I. Pesin, _Finiteness of the Hausdorff measure of level sets of bounded subsets in Euclidian space_ , Mat. Zametki 37 (1985), 422–431, (in Russian).
  * [24] A. Przeworski, _An upper bound on density for packings of collars about hyperplanes in $\mathbb{H}^{n}$_, Geom. Dedicata 163 (2013), 193–213.
  * [25] J. Rataj, E. Spodarev, and D. Meschenmoser, _Approximations of the Wiener Sausage and Its Curvature Measures_ , The Annals of Applied Probability 19 (2009), no. 5, 1840–1859.
  * [26] J. Rataj and E. Spodarev V. Schmidt, _On the Expected Surface Area of the Wiener Sausage_ , Mathematische Nachrichten 282 (2009), no. 4, 591–603.
  * [27] J. Rataj and S. Winter, _On volume and surface area of parallel sets_ , Indiana University Mathematics Journal 59 (2010), no. 5, 1661–1685.
  * [28] J. Rataj and L. Zajíček, _Properties of distance functions on convex surfaces and applications_ , Czech. Math. J. 61 (2011), 247–269.
  * [29] by same author, _Smallness of the critical values of distance functions in two-dimensional euclidean and riemannian spaces_ , Mathematika 66 (2020), 297–324.
  * [30] R. T. Rockafellar, _Clarke's tangent cones and the boundaries of closed sets in $\mathbb{R}^{n}$_, Nonlinear Analysis: Theory, Methods and Applications 3 (1979), no. 1, 145–154.
  * [31] R. T. Rockafellar and R. J.-B. Wets, _Variational analysis_ , Springer-Verlag, 1998.
  * [32] F. Spitzer, _Electrostatic Capacity, Heat Flow, and Brownian Motion_ , Z. Wahrscheinlichkeitstheorie 3 (1964), 110–121.
  * [33] L.L. Stachó, _On the volume function of parallel sets_ , Acta Sci. Math. 38 (1976), 365–374.


# Explainable Multimodal Sentiment Analysis on Bengali Memes

Kazi Toufique Elahi, Tasnuva Binte Rahman, Shakil Shahriar, Samir Sarker,
Sajib Kumar Saha Joy, Faisal Muhammad Shah  Department of Computer Science and
Engineering
Ahsanullah University of Science and Technology
Dhaka 1208, Bangladesh
Email: {ktoufiquee, tasnuvabinterahmansrishti, shakilshahriararnob,
<EMAIL_ADDRESS>
{joy.cse<EMAIL_ADDRESS>
###### Abstract

Memes have become a distinctive and effective form of communication in the
digital era, attracting online communities and cutting across cultural
barriers. Even though memes are frequently linked with humor, they have an
amazing capacity to convey a wide range of emotions, including happiness,
sarcasm, frustration, and more. Understanding and interpreting the sentiment
underlying memes has become crucial in the age of information. Previous
research has explored text-based, image-based, and multimodal approaches,
leading to the development of models like CAPSAN and PromptHate for detecting
various meme categories. However, the study of low-resource languages like
Bengali memes remains scarce, with limited availability of publicly accessible
datasets. A recent contribution includes the introduction of the MemoSen
dataset. However, the achieved accuracy is notably low, and the dataset
suffers from imbalanced distribution. In this study, we employed a multimodal
approach using ResNet50 and BanglishBERT and achieved a satisfactory result of
0.71 weighted F1-score, performed comparison with unimodal approaches, and
interpreted behaviors of the models using explainable artificial intelligence
(XAI) techniques.

###### Index Terms:

Sentiment Analysis, Memes, Multimodal, Deep Learning, Explainable AI.

##  I Introduction

The usage of social media platforms (i.e. Facebook, Twitter, Instagram) has
increased dramatically due to the substantial evolution of the Internet and
various Web 2.0 applications [1]. These social media platforms contain
people’s opinions and conversations on various topics like politics, games,
entertainment, and so on. Sentiment analysis on these has always been a
popular topic for NLP researchers. However, the nature of data found on these
platforms has evolved over time. It has transformed from being solely text-
based to encompass a combination of text, images, audio, and videos. One such
content is memes. Memes are a popular form of communication amongst the
younger generation. It is a type of content that is context-based and might be
in the form of images, text, or both. Memes are entertaining, critical,
sarcastic, and may even be political [2]. Movies, politics, TV shows,
religion, and social culture are all common sources of Internet memes [3]. As
it can be expressed in a lot of ways and can express a wide range of emotions,
understanding and interpreting the sentiment behind memes is of utmost
relevance in this age.

Several research studies have been conducted to better understand the
sentiment underlying memes. Various datasets specifically curated for memes,
such as Facebook Hateful Memes (FHM) [4], Harmful Meme Dataset (HarM) [5], and
Memotion [6], are available publicly. These datasets have served as a
foundation for several significant researches. For instance, Alluri et al. [3]
introduced the CAPSEN model with an accuracy of 60.25% (Memotion). Similarly,
Cao et al. [7] introduced a prompt-based model PromptHate with an accuracy of
84.47% (FHM) and 72.98% (HarM).

However, it is essential to highlight that most of these studies are focused
on datasets in the English language. As Bengali is a low-resource language,
the availability of datasets for memes in the Bengali language is scarce, and
research in this domain is even rarer. Nonetheless, a recent study conducted
by Hossain et al. [1] addressed this gap by introducing the MemoSen dataset,
comprising a collection of Bengali memes for sentiment analysis. While their
comprehensive analysis of the dataset yielded a weighted F1 score of 0.643, it
remains a far cry from the scores achieved in sentiment analysis of memes in
other languages. Additionally, the dataset suffers from an inherent imbalance
in its distribution.

Due to the limited availability of research on sentiment analysis of Bengali
memes, we aim to address this gap by conducting research on the MemoSEN
dataset. Initially, we implemented different models using solely text inputs
and image inputs that attained the highest F1-score of 0.66 and 0.70
respectively. Afterward, we combined both text and image inputs to create a
multimodal approach that achieved an F1-score of 0.71. In summary, we have
achieved the following:

  * •

Reached a desirable accuracy by implementing a multimodal approach on the
MemoSEN dataset.

  * •

Evaluated the performance of our approach by performing a comparative analysis
against the performance of other models.

  * •

Leveraged Explainable AI (XAI) to provide an explanation of the implemented
models.

##  II Related Works

Numerous studies have been conducted on sentiment analysis of memes, employing
both unimodal and multimodal approaches. A short description of studies that
achieved exemplary performance is listed in this section.

Hossain et al.[1] introduced MemoSen, one of the largest publicly available
multiclass sentiment classification datasets for Bengali memes. Their
ResNet50+BiLSTM-based model achieved the highest 0.635 weighted F1-score
showing that the multimodal approach performed better than the unimodal
approach. The same authors created another multimodal hateful meme dataset
named MUTE [8] more recently, which contains 4158 memes with Bengali and code-
mix captions, categorized into Hate and Non-hate classes. For benchmarking
purposes, VGG16, VGG19, and ResNet50 models were employed for visual data.
Whereas CNN+BiLSTM, BiLSTM+Attention, M-BERT, Bangla-BERT, and Cross-Lingual
Representation Learner (XLM-R) were implemented for textual data. The highest
weighted F1-Score of 0.672 was achieved by a multimodal approach using
VGG16+BanglaBERT. Noticeably, the model faced trouble in correctly labeling
the same words in different textual formats (code-mixed, code-switched).
Additionally, the model is confused by the disparity between some memes’
visual and textual content.

Karim et al. [9] achieved a maximum F1-score of 0.83 for hate speech detection
on Bengali memes implementing XLM-RoBERTa+DenseNet-161. Their limitations
included limited training data and the need for explanations regarding the
model’s predictions. Jannat et al.[10] achieved the highest F1-score of 0.68
using BiLSTM+VGG19 for binary sentiment classification in Bengali memes. CNN,
BiLSTM, and BiLSTM-CNN were implemented to perform text classification. VGG16,
VGG19, and InceptionV3 had been employed for visual data. BiLSTM and VGG19
came out to be the best performers individually. Sun et al. [11] proposed
TIMF, a model based on CNN+BiLSTM and TensorFusion, and performed benchmark
analysis on multiple datasets.

Alluri et al.[12] addressed the class imbalance in the Memotion dataset using
the Synthetic Minority Over-sampling Technique (SMOTE) and introduced IMGTXT
(ViT+RoBERTa), IMGSEN(ViT+SBERT RoBERTa), and CAPSEN(Generated captions +
Textual data using SBERT) models. The IMGSEN model outperformed other models
in humor and motivation categories with F1-scores of 63.30 and 55.09, while
the CAPSEN model excelled in sarcasm and overall sentiment with F1-scores of
61.33 and 57.79. It was suggested that the high dimensionality of data
contributed to lower accuracy in IMGTXT. Additionally, it was mentioned that
the CAPSEN model can be improved as it was only trained on Flickr8k [13].

Hasan et al.[14] achieved the highest F1-score of 49% using a CNN+VGG16-based
multimodal model in their study on the detection of troll memes. Their model
struggled to identify non-troll memes in particular, most likely due to the
overlapping nature of memes across all classes. Pramanik et al.[5] contributed
to the prospect of harmful meme detection with their approach of using
VisualBERT pre-trained on COCO [15], achieving the highest F1-score of 80.13%,
leading by almost 9% to their unimodal pre-trained approach of ConcatBERT.
They also conducted a human evaluation to justify their result and the
VisualBERT performed best there as well with an almost 66% F1 score. Ullah et
al.[16] in their overview of multimodal sentiment analysis mentioned the
detection of hidden emotions, exploring more feature points of the face, and
fusing analysis results from multiple modalities as the difficulties mostly
needed to be handled regarding the subject.

##  III Dataset Overview

In this study, the MemoSEN[1] dataset is utilized as the primary data source.
Presently, the MemoSEN dataset comprises a total of 4372 images, each
accompanied by its respective caption. It is worth mentioning that among these
images, 17 do not have any associated captions. The memes within this dataset
are categorized into three distinct groups: Neutral, Positive, and Negative.

(a) Neutral

(b) Positive

(c) Negative

Figure 1: Example meme from each class

An example from each class is visualized in Figure 1. Through observation, it
can be seen that the people who made this dataset labeled neutral to self-
criticizing memes in general, most of the neutral memes are generally self-
loathing, self-humor, or self-criticization.

TABLE I: Dataset Statistics | Neutral | Positive | Negative
---|---|---|---
Train (70%) | 204 | 944 | 1909
Validation (10%) | 29 | 135 | 273
Test (20%) | 58 | 270 | 546
Total | 291 | 1349 | 2728

For our study, we stratified and split the dataset into train, validation, and
test sets. The distribution of memes across the three categories is shown in
Table I. It is evident from the figure that the number of instances in the
neutral class is significantly lower compared to both the positive and
negative classes. This indicates that the dataset is imbalanced.

TABLE II: Bengali and English Caption Count Language | Caption Count |  |  |
---|---|---|---|---
Bengali | 2511 |  |  |
English | 451 |  |  |
Bengali + English | 1389 |  |  |
No Caption | 17 |  |  |

The MemoSEN dataset contains captions of multiple language, including Bengali,
English, and a combination of both languages. Statistics of caption language
is shown in Table II.

Figure 2: Length-Frequency distribution of Captions

Figure 3: Word Cloud

Captions in this dataset vary in length. The longest caption comprises 121
words, whereas the shortest contains just 1 word. On average, captions consist
of approximately 19 words. The length-frequency distribution over the dataset
is visualized in Figure 2. Also, a word cloud is shown in Figure 3 as an
addition to data analysis to visually represent the top 200 frequently used
words taken from the captions.

##  IV Methodology

Figure 4: Methodology

The methodology followed in the study is depicted in Figure 4. An in-depth
description of the steps is provided in this section.

###  IV-A Dataset Preparation

In the dataset, we encountered instances where some of the image path entries
did not correspond to valid image files. As a result, we decided to remove
those entries from the dataset.

###  IV-B Data Preprocessing

The dataset consists of multimodal data, including both images and texts. To
ensure clarity and meaningful information, preprocessing steps were applied to
both modalities. For the preprocessing, the following steps were performed:

  * •

Normalizing: Punctuations and characters in the captions that have multiple
unicode representations were normalized using a normalizer module [17] to
reduce data sparsity.

  * •

Resizing: Images were resized to a resolution of 224x224 pixels to ensure
consistency in image shape.

###  IV-C Classification

For classification, we employed visual, textual, and multimodal approaches
individually. The models that were used are listed as follows:

  * •

Visual/Image-based Approach: We used ResNet50 [18], MobileNet v3 [19], and
DenseNet161 [20] to classify the memes with only the images as input. All of
these models were initilized with ImageNet1k [21] weights and then trained on
MemoSen dataset.

  * •

Textual/Text-based Approach: As the captions include both Bengali and English
words, this presents a challenge where state-of-the-art BERT models trained on
a single language will perform poorly for downstream tasks. For proper
classification based on textual data, a multilingual BERT was necessary. For
this reason, we employed BanglishBERT [22], an ELECTRA discriminator model
pre-trained with the Replaced Token Detection (RTD) objective on large amounts
of Bengali and English corpora. Additionally, we employed BiLSTM for a
performance comparison with BanglishBERT.

  * •

Multimodal Approach: For the multimodal approach, we tried combinations of
BanglishBERT + ResNet50 and BanglishBert + DenseNet161. First, each models
were used to extract features. The features were then passed through two
different linear layers each containing 20 neurons. The output of the linear
layers was concatenated and passed through another linear layer with 3
neurons.

###  IV-D Evaluation:

We evaluated all of our approaches with accuracy, precision, recall, and
f1-score. As the dataset is imbalanced, weighted scores were used.

##  V Experimental Result

TABLE III: Performance Comparison of Visual, Textual and Multimodal Approaches |  | Accuracy | Precision | Recall |  F1-Score
---|---|---|---|---|---
Visual |  ResNet50 | 0.72 | 0.67 | 0.72 |  0.69
MobileNet v3 (Large) | 0.71 | 0.66 | 0.71 |  0.67
DenseNet161 | 0.73 | 0.69 | 0.73 |  0.70
Textual |  BiLSTM | 0.62 | 0.39 | 0.62 |  0.48
BanglishBERT | 0.66 | 0.66 | 0.66 |  0.66
Visual + Textual |  BanglishBERT \+ DenseNet161 | 0.73 | 0.68 | 0.73 |  0.70
Banglish BERT \+ ResNet50 | 0.74 | 0.69 | 0.74 |  0.71

Table III shows the weighted scores of all the models we have tested. As we
can see, the visual approaches outperform the textual approaches in every
case, since the lowest F1-score achieved by MobileNet v3 is 0.67, whereas the
highest F1-score in the textual approaches was achieved by BanglishBERT with
only 0.66. The best result overall is obtained by combining the visual and
textual approaches of BanglishBERT and ResNet50, which achieved a 0.71
weighted F1-score. This implementation outperforms the previously attained
highest F1-Score of 0.635 with ResNet50+BiLSTM, as reported by Hossain et al.
[1].

Figure 5: Train and Validation Loss vs Accuracy Curve of Multimodal
BanglishBERT + ResNet50

For a better understanding of the training process, the train and validation
loss vs. accuracy graph of our multimodal approach is visualized in Figure 5.
To minimize bias and variance of the model, different hyperparameters were
tested. The best result was achieved using a batch size of 32 and the AdamW
optimizer with a learning rate of 0.00001, betas of (0.9, 0.9999), an epsilon
value of 1e-9, and a weight decay of 0.08.

(a) True Label: Neutral, Textual: Negative,
Visual: Negative, Multimodal: Negative

(b) True Label: Negative, Textual: Negative,
Visual: Negative, Multimodal: Negative

(c) True Label: Positive, Textual: Positive,
Visual: Positive, Multimodal: Positive

(d) True Label: Positive, Textual: Negative,
Visual: Negative, Multimodal: Negative

(e) True Label: Negative, Textual: Negative,
Visual: Negative, Multimodal: Negative

(f) True Label: Negative, Textual: Positive,
Visual: Negative, Multimodal: Positive

Figure 6: XAI implemented example of memes

(a) DenseNet161

(b) BanglishBERT

(c) BanglishBERT + ResNet50

Figure 7: Confusion Matrix of highest performing models

Figure 7 illustrates the confusion matrix of the best-performing models of
Visual, Textual, and Multimodal approaches. A striking observation is that
none of the models could accurately classify neutral memes. Both the Visual
and Multimodal approaches failed to correctly identify any neutral memes,
while the Textual approach only managed to classify six neutral memes
correctly. This suggests that neutral memes are more challenging to detect
than positive or negative memes and require more sophisticated methods to
capture their subtleties.

##  VI Result Analysis

To understand how these models make their decisions, we applied the LIME
algorithm to both DenseNet161 and BanglishBERT. Figure 6 visualizes six memes
on which LIME was applied. The examples are organized in the following order:
the original meme on the left, the result of LIME on image input on the right,
and the result of LIME on captions below them. For image data, green-marked
areas support the decision of the model, and red-marked areas contribute
against that decision. Similarly, for textual data, orange tokens contribute
to positive, green tokens contribute to negative, and blue tokens contribute
to neutral sentiment. The intensity of color represents the importance of the
marked token.

From the examples of Figure 6, it can be seen that DenseNet161 focuses mostly
on people’s faces, which is not enough to understand the underlying sentiment
of the memes. For proper sentiment prediction, captions are also necessary.
For this reason, multimodal achieves the highest score as it uses both caption
and image as its input. However, DenseNet161 was able to reach a very close
score (0.70 F1-Score) compared to BanglishBERT (0.66 F1-Score) which implies
that memes on the dataset rely more on images for sentimental context.

Our results reveal a common trend among all the models: none of them were able
to accurately classify neutral memes. Possible reasons for this anomaly are
the following:

  1. 1.

The number of neutral memes in the dataset is relatively low, with only 291
instances.

  2. 2.

Visually similar meme templates are used across all classes of memes, and due
to the imbalanced nature of the dataset, the model may shift its focus toward
other classes.

  3. 3.

Textual tokens used in neutral memes are also common in other classes.

As evidence to support our second hypothesis, the LIME algorithm was
implemented on neutral (Figure 7a) and negative (Figure 7b) memes that share
the same visual template. It can be observed that, in both cases, the model
focuses on the upper portion of the person’s head, which is expected since the
images are identical. However, the nature of this meme is defined by its
caption, in which the visual model falls short.

Moreover, in the text data, as illustrated in Figure 7a, the majority of the
highlighted tokens are associated with the negative class, supporting our
third hypothesis.

##  VII Conclusion

This study presents a comprehensive analysis of the performance of various
models, using both text and image-based inputs, for Bengali meme
classification. However, none of the models were able to accurately classify
neutral memes, resulting in poor performance scores. To further advance this
study, more data could be added to balance the dataset, and state-of-the-art
VisualBERT-based models could be implemented. Our contribution to this study
includes a thorough analysis of meme classification using unimodal (Image,
Text) and multimodal (Image + Text) approaches, reaching a satisfactory
performance with the multimodal approach, as well as an in-depth explanation
of anomalies through the implementation of LIME.

## References

  * [1] E. Hossain, O. Sharif, and M. M. Hoque, “Memosen: A multimodal dataset for sentiment analysis of memes,” in _Proceedings of the Thirteenth Language Resources and Evaluation Conference_ , 2022, pp. 1542–1554.
  * [2] E. Asmawati, A. Saikhu, and D. Siahaan, “Sentiment analysis of text memes: A comparison among supervised machine learning methods,” in _2022 9th International Conference on Electrical Engineering, Computer Science and Informatics (EECSI)_. IEEE, 2022, pp. 349–354.
  * [3] N. V. Alluri and N. D. Krishna, “Multi modal analysis of memes for sentiment extraction,” in _2021 Sixth International Conference on Image Information Processing (ICIIP)_ , vol. 6. IEEE, 2021, pp. 213–217.
  * [4] D. Kiela, H. Firooz, A. Mohan, V. Goswami, A. Singh, P. Ringshia, and D. Testuggine, “The hateful memes challenge: Detecting hate speech in multimodal memes,” _Advances in neural information processing systems_ , vol. 33, pp. 2611–2624, 2020.
  * [5] S. Pramanick, D. Dimitrov, R. Mukherjee, S. Sharma, M. S. Akhtar, P. Nakov, and T. Chakraborty, “Detecting harmful memes and their targets,” _arXiv preprint arXiv:2110.00413_ , 2021.
  * [6] C. Sharma, W. Paka, Scott, D. Bhageria, A. Das, S. Poria, T. Chakraborty, and B. Gambäck, “Task Report: Memotion Analysis 1.0 @SemEval 2020: The Visuo-Lingual Metaphor!” in _Proceedings of the 14th International Workshop on Semantic Evaluation (SemEval-2020)_. Barcelona, Spain: Association for Computational Linguistics, Sep 2020.
  * [7] R. Cao, R. K.-W. Lee, W.-H. Chong, and J. Jiang, “Prompting for multimodal hateful meme classification,” _arXiv preprint arXiv:2302.04156_ , 2023.
  * [8] E. Hossain, O. Sharif, and M. M. Hoque, “Mute: A multimodal dataset for detecting hateful memes,” in _Proceedings of the 2nd Conference of the Asia-Pacific Chapter of the Association for Computational Linguistics and the 12th International Joint Conference on Natural Language Processing: Student Research Workshop_ , 2022, pp. 32–39.
  * [9] M. R. Karim, S. K. Dey, T. Islam, M. Shajalal, and B. R. Chakravarthi, “Multimodal hate speech detection from bengali memes and texts,” in _International Conference on Speech and Language Technologies for Low-resource Languages_. Springer, 2022, pp. 293–308.
  * [10] N. Jannat, A. Das, O. Sharif, and M. M. Hoque, “An empirical framework for identifying sentiment from multimodal memes using fusion approach,” in _2022 25th International Conference on Computer and Information Technology (ICCIT)_. IEEE, 2022, pp. 791–796.
  * [11] J. Sun, H. Yin, Y. Tian, J. Wu, L. Shen, and L. Chen, “Two-level multimodal fusion for sentiment analysis in public security,” _Security and Communication Networks_ , vol. 2021, pp. 1–10, 2021.
  * [12] N. Varma Alluri and N. Dheeraj Krishna, “Multimodal analysis of memes for sentiment extraction,” _arXiv e-prints_ , pp. arXiv–2112, 2021.
  * [13] M. Hodosh, P. Young, and J. Hockenmaier, “Framing image description as a ranking task: Data, models and evaluation metrics,” _Journal of Artificial Intelligence Research_ , vol. 47, pp. 853–899, 2013.
  * [14] M. Hasan, N. Jannat, E. Hossain, O. Sharif, and M. M. Hoque, “Cuet-nlp@ dravidianlangtech-acl2022: Investigating deep learning techniques to detect multimodal troll memes,” in _Proceedings of the Second Workshop on Speech and Language Technologies for Dravidian Languages_ , 2022, pp. 170–176.
  * [15] T.-Y. Lin, M. Maire, S. Belongie, J. Hays, P. Perona, D. Ramanan, P. Dollár, and C. L. Zitnick, “Microsoft coco: Common objects in context,” in _Computer Vision–ECCV 2014: 13th European Conference, Zurich, Switzerland, September 6-12, 2014, Proceedings, Part V 13_. Springer, 2014, pp. 740–755.
  * [16] M. A. Ullah, M. M. Islam, N. B. Azman, and Z. M. Zaki, “An overview of multimodal sentiment analysis research: Opportunities and difficulties,” in _2017 IEEE International Conference on Imaging, Vision & Pattern Recognition (icIVPR)_. IEEE, 2017, pp. 1–6.
  * [17] T. Hasan, A. Bhattacharjee, K. Samin, M. Hasan, M. Basak, M. S. Rahman, and R. Shahriyar, “Not low-resource anymore: Aligner ensembling, batch filtering, and new datasets for Bengali-English machine translation,” in _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_. Online: Association for Computational Linguistics, Nov. 2020, pp. 2612–2623. [Online]. Available: https://www.aclweb.org/anthology/2020.emnlp-main.207
  * [18] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 770–778.
  * [19] A. Howard, M. Sandler, G. Chu, L.-C. Chen, B. Chen, M. Tan, W. Wang, Y. Zhu, R. Pang, V. Vasudevan _et al._ , “Searching for mobilenetv3,” in _Proceedings of the IEEE/CVF international conference on computer vision_ , 2019, pp. 1314–1324.
  * [20] G. Huang, Z. Liu, L. Van Der Maaten, and K. Q. Weinberger, “Densely connected convolutional networks,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2017, pp. 4700–4708.
  * [21] O. Russakovsky, J. Deng, H. Su, J. Krause, S. Satheesh, S. Ma, Z. Huang, A. Karpathy, A. Khosla, M. Bernstein, A. C. Berg, and L. Fei-Fei, “ImageNet Large Scale Visual Recognition Challenge,” _International Journal of Computer Vision (IJCV)_ , vol. 115, no. 3, pp. 211–252, 2015.
  * [22] A. Bhattacharjee, T. Hasan, K. Mubasshir, M. S. Islam, W. A. Uddin, A. Iqbal, M. S. Rahman, and R. Shahriyar, “Banglabert: Lagnuage model pretraining and benchmarks for low-resource language understanding evaluation in bangla,” in _Findings of the North American Chapter of the Association for Computational Linguistics: NAACL 2022_ , july 2022. [Online]. Available: https://arxiv.org/abs/2101.00204