Rcases $\m@th{##}$$\m@th{##}$ .}

# Spatial Gated Multi-Layer Perceptron for Land Use and Land Cover Mapping

Ali Jamali,* Swalpa Kumar Roy,* , Danfeng Hong, ,
Peter M Atkinson, and Pedram Ghamisi This research was funded by the Institute
of Advanced Research in Artificial Intelligence (IARAI). (Corresponding
author: Pedram Ghamisi)A. Jamali is with the Department of Geography, Simon
Fraser University, British Columbia 8888, Canada (e-mail: alij@sfu.ca).S. K.
Roy is with the Department of Computer Science and Engineering, Alipurduar
Government Engineering and Management College, West Bengal 736206, India
(e-mail: swalpa@cse.jgec.ac.in).D. Hong is with the Aerospace Information
Research Institute, Chinese Academy of Sciences, 100094 Beijing, China.
(e-mail: hongdf@aircas.ac.cn).P. M. Atkinson is with the Faculty of Science
and Technology, Lancaster University, Lancaster, U.K.
<EMAIL_ADDRESS>).P. Ghamisi is with the Helmholtz-Zentrum
Dresden-Rossendorf (HZDR), Helmholtz Institute Freiberg for Resource
Technology, 09599 Freiberg, Germany, and is also with the Institute of
Advanced Research in Artificial Intelligence (IARAI), 1030 Vienna, Austria
(e-mail: p.ghamisi@gmail.com).(* indicates these two authors contributed
equally to the work.)

###### Abstract

Convolutional Neural Networks (CNNs) are models that are utilized extensively
for the hierarchical extraction of features. Vision transformers (ViTs),
through the use of a self-attention mechanism, have recently achieved superior
modeling of global contextual information compared to CNNs. However, to
realize their image classification strength, ViTs require substantial training
datasets. Where the available training data are limited, current advanced
multi-layer perceptrons (MLPs) can provide viable alternatives to both deep
CNNs and ViTs. In this paper, we developed the SGU-MLP, a learning algorithm
that effectively uses both MLPs and spatial gating units (SGUs) for precise
land use land cover (LULC) mapping. Results illustrated the superiority of the
developed SGU-MLP classification algorithm over several CNN and CNN-ViT-based
models, including HybridSN, ResNet, iFormer, EfficientFormer and CoAtNet. The
proposed SGU-MLP algorithm was tested through three experiments in Houston,
USA, Berlin, Germany and Augsburg, Germany. The SGU-MLP classification model
was found to consistently outperform the benchmark CNN and CNN-ViT-based
algorithms. For example, for the Houston experiment, SGU-MLP significantly
outperformed HybridSN, CoAtNet, Efficientformer, iFormer and ResNet by
approximately 15%, 19%, 20%, 21%, and 25%, respectively, in terms of average
accuracy. The code will be made publicly available at
https://github.com/aj1365/SGUMLP

###### Index Terms:

Attention mechanism, image classification, spatial gating unit (SGU), vision
transformers.

##  I Introduction

Land use and land cover (LULC) is one of the most significant indicators of
anthropogenic interaction with the natural environment. Massive growth in LU
because of forest destruction, urbanization and soil erosion has altered the
global landscape and caused greater stress on natural ecosystems across the
world [1]. Modelers’ dominant perception of cities is of a sophisticated
structure with characteristics like occurrence, self-organization and non-
linear relationships. Urbanization and growing urban populations have led to
significant scientific debate since they lead to substantial shifts in
agricultural use and environmental degradation [2]. Analysis of urban growth,
including intense growth in urban sprawl, is essential for understanding its
environmental consequences, as well as promoting the adoption of more
sustainable forms of urban expansion. As a result, it is essential to organize
and structure the process of LULC change in natural ecosystems.

Precise LULC mapping serves as the foundation for non-monetary assessment and
is generally obtained by integrating a machine learning or deep learning
algorithm with imagery from remote sensing. Deep learning models are capable
of extracting adaptively the most important features from data using a data-
driven approach. During the training phase, these models can achieve an
effective parametric configuration by simultaneously training the associated
classification model. This greatly enhances their ability to accurately
represent complex data and avoid ambiguity [3]. Deep learning models have been
progressively used for LULC mapping in recent years [4, 5]. In particular,
Convolutional Neural Networks (CNNs) are widely utilized models for
hierarchical feature extraction. Due to their self-attention system, vision
transformers (ViTs) can model global contextual information more effectively
than CNNs [6], but they require larger training datasets to maximize image
classification accuracy. On the other hand, where fewer training data are
available, current advanced Multi-layer Perceptrons (MLPs) can be used as an
alternative to both deep CNNs and ViTs [7].

In this paper, we develop and propose an SGU-MLP, a deep learning classifier
that employs MLPs and a spatial gating unit (SGU) for accurate LULC modeling.
The SGU concept enables the algorithm to efficiently characterize complex
spatial interactions across input data tokens without the use of positional
information embedding as utilized in popular ViTs. The SGU-MLP model’s final
layer employs a structure entirely composed of multi-layer perceptrons (MLPs),
eliminating the requirement for CNNs or ViTs and, consequently, minimizing the
necessity for extensive training data.

This Letter introduces the SGU-MLP in Section II, illustrates the experiments
and analyses the results in Section III, and highlights the concluding remarks
in Section IV.

Figure 1: Graphical representation of spatial gated multi-layer perceptron
framework for land use and land cover classification. The MLP-Mixer layer
includes two MLPs to extract spatial information. $\odot$ represents channel-
wise concatenation.

##  II Proposed Classification Framework

As illustrated in Fig. 1, the SGU-MLP, is developed for image classification
using a small number of training data. For efficient application of the multi-
scale representation in the classification task, we incorporated a
computationally light and straightforward depth-wise CNN-based architecture.
As presented in Fig. 2, the MLP-Mixer layer of the developed model includes
two different types of layers: (i) MLPs utilized across image patches for
extraction of spatial information and (ii) MLPs utilized individually to
extract per-location features from image inputs. In addition, in each MLP
block, the SGU is utilized to enable the developed algorithm to effectively
learn intricate spatial relationships among the tokens of the input data.

###  II-A Depth-wise Convolution Block (DWC):

The DWC architecture is light and straightforward, and is based on CNNs. With
so many variables and the limited available training data, a higher
probability of overfitting exists during the training process. Hence, to
address overfitting and capture multi-scale feature information, we
incorporated three depth-wise convolutions in parallel. These convolutions
consist of filters with a size of 20 and kernel ($k$) sizes of $1\times{1}$,
$3\times{3}$, and $5\times{5}$, respectively. Feature maps $X$ with a size of
$9\times{9}\times{d}$ are the input for the DWC block that produces output
$D_{Z}$, where $d$ is the number of bands.

$D_{Z}=\sum_{j=1,3,5}\rm{DWConv2D_{(k\times{k})}(\textit{X})}$ (1)

The output maps of the three depth-wise CNNs are added and fed to the MLP-
Mixer blocks.

Figure 2: Graphical representation of MLP-Mixer layer.

###  II-B Spatial gating unit (SGU):

The SGU is designed to extract complex spatial interaction across tokens.
Unlike, the current ViT models, the SGU does not necessitate the use of
positional embedding. In other words, the positional embedding information is
obtained through the use of spatial depth-wise convolutions [8] similar to
inverted bottlenecks employed in MobileNetV2 [9]. Considering the dense layer
of $D$ in the MLP block, as illustrated in Fig. 1, the SGU uses a linear
projection layer that benefits from a contraction operation across the spatial
dimension of the cross-tokens interaction as defined by:

$f_{W,b}(D)=WD+b$ (2)

where $W\in R^{n\times{n}}$ defines a matrix that has a size equal to the
input sequence length, while $n$ and $b$ present the sequence length and
biases of the tokens. It should be highlighted that the spatial projection
matrix of $W$ is not dependent on the input data, contradicting the self-
attention models where $W(D)$ is created dynamically from the $D$. The SGU can
be formulated as:

$S(D)=D\cdot f_{W,b}(D)$ (3)

where element-wise multiplication is represented by $(\cdot)$. The SGU
equation can be improved by dividing $D$ into $D1$ and $D2$ along the channel
dimension. Thus, the SGU can be formulated as:

$S(D)=D1\cdot f_{W,b}(D2)$ (4)

The output map of the DWC block is flattened and fed to the MLP-Mixer layer.
Considering a dense layer of size $256\times{256}$, The $D1$ and $D2$ both
have sizes of $256\times{128}$. The $f_{W,b}(D2)$ has a size of
$256\times{128}$, where the $S(D)$ has a size of $256\times{128}$.

###  II-C Multi-layer Perceptron Mixer Block (MLP-Mixer):

In current advanced deep vision architectures, layers combine features in one
or more of the following ways: (1) at a given spatial location, (2) among
various spatial locations, or (3) both simultaneously, with kernel of
$k\times{k}$ convolutions (for $k$ $>$ 1) and pooling operations (2),
incorporated in CNNs. Convolutions with kernel size $1\times{1}$ perform the
operation (1), whereas convolutions with larger kernels accomplish both
operations (1) and (2). Self-attention layers in ViTs and other attention-
based structures include operations (1) and (2), while models based on the
MLPs only perform (1). The objective of the MLP-Mixer architecture is to
distinguish between cross-location (height and width mixing) operations and
per-location (channel-mixing) operations, as presented in Fig. 2 [7]. A series
of non-overlapping patches of images $E$ from the output feature of the DWC
block $D_{Z}$ are the input to the MLP-Mixer that is projected to a given
hidden dimension of $C$, resulting in two-dimensional data of
$\mathbf{M}\in\mathcal{R}^{E\times{d}}$, where $d$ illustrates the image input
band number. Given the input image of size $H\times{W}$, and patches of
$F\times{F}$, the number of patches would be $E=\frac{H\times{W}}{F^{2}}$,
where all resulting patches of images are projected into the same projection
matrix. The MLP-Mixer consists of several identical size layers, where each
layer has two MLP blocks. The first token-mixing (i.e., height and width
mixing) MLP block is applied on the columns of $M$, while the second MLP block
(i.e., channel mixing) is utilized on the rows of the $M$. Two fully connected
layers are in each MLP block, and a non-linearity function is applied
independently to each row of the input image tensors. As such, each MLP-Mixer
can be formulated as:

$U_{\iota,i}=M_{\iota,i}+W_{2}\xi(W_{1}LN(M)_{\iota,i})),i=1,...,B$ (5)
$Y_{j,\iota}=U_{j,\iota}+W_{4}\xi(W_{3}LN(U)_{\iota,i})),j=1,\ldots,E$ (6)

Notably, the MLP-Mixer has a linear computation complexity, which
distinguishes it from vision transformers with quadratic computation
complexity and, consequently, exhibits a high level of computational
efficiency.

###  II-D Spatial Gating Unit Multi-layer Perceptron (SGU-MLP):

Let us consider three data modalities, $X_{1}$, $X_{2}$, and $X_{3}$. From
these datasets, image patches with the size of $9\times{9}$ are extracted and
then concatenated. As seen in Fig. 1, the concatenated layer is fed to the DWC
layer. After being fed into the DWC block, the input images of size
$9\times{9}\times{B}$ result in equal feature maps of size
$9\times{9}\times{B}$, where $B$ represents the number of bands. The resulting
feature map is then flattened and passed on to the MLP-Mixer blocks. The MLP-
Mixer includes four blocks with patch sizes of 4, token dimension of 256, and
channel dimension of 256. As discussed, in each MLP block, before the
activation function (i.e., GELU), the SGU is employed to extract complex
spatial interactions between the tokens. Finally, the last layer of the MLP-
Mixer is a dense layer with a softmax activation function. The size of the
last layer is equal to the number of existing classes in each study area.

##  III Experimental Results

###  III-A Experimental Data

Houston dataset: This dataset was captured over the University of Houston
campus and the neighboring urban area. It consists of a coregistered
hyperspectral and multispectral dataset containing 144 and 8 bands,
respectively, with $349\times{1905}$ pixels. More information can be found at
[10].

Berlin dataset: This dataset has a spatial resolution of $797\times{220}$
pixels and contains 244 spectral bands with wavelengths ranging from 0.4
$\mu$m to 2.5 $\mu$m over Berlin. The Sentinel-1 dual-Pol (VV-VH) single-look
complex (SLC) product represents the SAR data. The processed SAR data have a
satial resolution of $1723\times{476}$ pixels and a 13.89 m GSD. The HS image
is nearest neighbor interpolated, as for the Houston dataset, to provide the
same image size as the SAR data [11].

Augsburg dataset: This scene over the city of Augsburg, Germany includes three
distinct datasets: a spaceborne HS image, a dual-Pol PolSAR image and a DSM
image. The PolSAR data were obtained from the Sentinel-1 platform, and the HS
and DSM data were obtained by DAS-EOC and DLR. All image spatial resolutions
were downscaled to a single 30 m GSD. The scene describes four features from
the dual-Pol (VV-VH) SAR image, 180 spectral bands from 0.4 $\mu$m to 2.5
$\mu$m for the HS image and one DSM image of $332\times{485}$ pixels [12].

###  III-B Classification Results

The classification capability of the developed SGU-MLP was evaluated against
several CNN-based and cutting-edge CNN-ViT algorithms, including HybridSN
[13], ResNet [14], iFormer [15], EfficientFormer [16] and CoAtNet [17]. In the
Augsburg dataset, as seen in Table I, the developed SGU-MLP algorithm
demonstrated superior classification performance with an average accuracy of
66.79% compared to ResNet (43.57%), CoAtNet(49.9%), Efficientformer (52.81%),
iFormer (52.96%) and HybridSN (55.76%). The developed SGU-MLP classifier
significantly increased the classification accuracy of the CNN-ViT-based
algorithms of iFormer, Efficientformer, and CoAtNet by about 21%, 21%, and 25%
in terms of average accuracy, as illustrated in Table I and Fig. 3(g).

In the Berlin study area, the SGU-MLP classifier with an average accuracy of
66.26% considerably increased the classification accuracy of the other CNN-ViT
algorithms iFormer, CoAtNet and Efficientformer by approximately 5%, 9% and
9%, respectively, as shown in Table II and Fig. 4(g). The MLP-SGU achieved F-1
scores of 0.27, 0.41, 0.46, 0.48, 0.67, 0.72, 0.73 and 0.82 for the
recognition of commercial areas, industrial areas, allotment, water, soil, low
plants, forest and residential areas, respectively.

As shown in Table III and Fig. 5(g), with a kappa index of 86.91%, the SGU-MLP
algorithm noticeably surpassed the classification performance of the ResNet
(65.49%), iFormer (68.71%), Efficientformer (69.25%), CoAtNet (70.56%), and
HybridSN (73.59%), respectively, in the Houston pilot site. The developed SGU-
MLP classification model outperformed the other CNN and CNN-ViT-based
algorithms of the HybridSN, CoAtNet, Efficientformer, iFormer, and ResNet by
about 15%, 19%, 20%, 21%, and 25%, respectively, in terms of average accuracy,
as demonstrated in Table III.

TABLE I: Classification results of Augsburg dataset in terms of F-1 score
where $\kappa$ = Kappa index, OA = Overall Accuracy, AA = Average Accuracy,
respectively.

Class | HybridSN | ResNet | iFormer | Efficientformer | CoAtNet | SGU-MLP
---|---|---|---|---|---|---
Forest | 0.88 | 0.83 | 0.91 | 0.88 | 0.85 | 0.94
Residential | 0.89 | 0.83 | 0.89 | 0.9 | 0.87 | 0.95
Industrial | 0.43 | 0.15 | 0.35 | 0.4 | 0.22 | 0.63
Low Plants | 0.87 | 0.88 | 0.88 | 0.88 | 0.98 | 0.96
Allotment | 0.13 | 0.1 | 0.13 | 0.11 | 0.09 | 0.36
Commercial | 0.04 | 0.05 | 0.1 | 0.11 | 0.16 | 0.28
Water | 0.35 | 0.19 | 0.21 | 0.25 | 0.19 | 0.52
OA$\times$100 | 82.28 | 79.07 | 82.82 | 82.72 | 81.32 | 91.82
AA$\times$100 | 55.76 | 43.57 | 52.96 | 52.81 | 49.9 | 66.79
$\kappa\times$100 | 74.85 | 69.34 | 75.37 | 75.24 | 73.12 | 88.22

(a)

(b)

(c)

(d)

(e)

(f)

(g) Figure 3: Classification Maps over the Augsburg dataset using a) Study
image, b) CoAtNet, c) EfficientFormer, d) HybridSN, e) iFormer, f) ResNet, and
g) the SGU-MLP.

Forest  Residential  Industrial  Low plants  Allotment  Water

TABLE II: Classification results of Berlin dataset in terms of F-1 score where
$\kappa$ = Kappa index, OA = Overall Accuracy, AA = Average Accuracy,
respectively.

Class | HybridSN | ResNet | iFormer | Efficientformer | CoAtNet | SGUMLP
---|---|---|---|---|---|---
Forest | 0.71 | 0.64 | 0.69 | 0.73 | 0.65 | 0.73
Residential | 0.8 | 0.81 | 0.82 | 0.81 | 0.76 | 0.82
Industrial | 0.49 | 0.39 | 0.35 | 0.32 | 0.32 | 0.41
Low Plants | 0.59 | 0.35 | 0.72 | 0.7 | 0.59 | 0.72
Soil | 0.65 | 0.72 | 0.7 | 0.67 | 0.75 | 0.67
Allotment | 0.44 | 0.28 | 0.34 | 0.29 | 0.3 | 0.46
Commercial | 0.45 | 0.25 | 0.29 | 0.24 | 0.29 | 0.27
Water | 0.65 | 0.53 | 0.49 | 0.38 | 0.28 | 0.48
OA$\times$100 | 66.81 | 63.7 | 68.6 | 68.17 | 63.14 | 70.79
AA$\times$100 | 62.67 | 58.23 | 62.84 | 60.05 | 60.53 | 66.26
$\kappa\times$100 | 55.84 | 47.61 | 55.28 | 54.32 | 49.21 | 58.06

(a)

(b)

(c)

(d)

(e)

(f)

(g) Figure 4: Classification Maps over the Berlin dataset using a) Study
image, b) CoAtNet, c) EfficientFormer, d) HybridSN, e) iFormer, f) ResNet, and
g) the SGU-MLP.

Forest  Residential  Industrial  Soil  Low plants  Allotment  Water

TABLE III: Classification results of Houston dataset in terms of F-1 score
where $\kappa$ = Kappa index, OA = Overall Accuracy, AA = Average Accuracy,
respectively.

Class | HybridSN | ResNet | iFormer | Efficientformer | CoAtNet | SGUMLP
---|---|---|---|---|---|---
Healthy Grass | 0.85 | 0.88 | 0.86 | 0.89 | 0.9 | 0.89
Stressed Grass | 0.84 | 0.9 | 0.87 | 0.87 | 0.88 | 0.89
Synthetic Grass | 0.84 | 0.78 | 0.5 | 0.58 | 0.72 | 0.97
Tree | 0.87 | 0.89 | 0.92 | 0.91 | 0.93 | 0.94
Soil | 0.96 | 0.94 | 0.93 | 0.95 | 0.85 | 0.99
Water | 0.73 | 0.71 | 0.29 | 0.39 | 0.25 | 0.35
Residential | 0.69 | 0.72 | 0.68 | 0.6 | 0.79 | 0.81
Commercial | 0.69 | 0.39 | 0.68 | 0.56 | 0.6 | 0.83
Road | 0.7 | 0.57 | 0.75 | 0.77 | 0.82 | 0.85
Highway | 0.58 | 0.52 | 0.45 | 0.54 | 0.54 | 0.89
Railway | 0.7 | 0.54 | 0.67 | 0.57 | 0.67 | 0.82
Parking Lot1 | 0.74 | 0.42 | 0.48 | 0.71 | 0.55 | 0.96
Parking Lot2 | 0.94 | 0.61 | 0.72 | 0.78 | 0.58 | 0.9
Tennis Court | 0.84 | 0.77 | 0.74 | 0.73 | 0.56 | 0.99
Running Track | 0.64 | 0.82 | 0.83 | 0.61 | 0.92 | 0.95
OA$\times$100 | 75.62 | 68.16 | 71.03 | 71.66 | 72.67 | 87.91
AA$\times$100 | 76.44 | 71.42 | 72.86 | 70.69 | 75.62 | 89.33
$\kappa\times$100 | 73.59 | 65.49 | 68.71 | 69.25 | 70.56 | 86.91

(a)

(b)

(c)

(d)

(e)

(f)

(g) Figure 5: Classification Maps over the Houston dataset using a) Study
image, b) CoAtNet, c) EfficientFormer, d) HybridSN, e) iFormer, f) ResNet, and
g) the SGU-MLP.

Residential  Allotment  Water  Commercial  Healthy grass  Stressed grass
Synthetic grass  Tree  Road  Highway  Railway  Parking Lot1  Parking Lot2
Tennis court  Running track

###  III-C Ablation study

An ablation study was performed to better understand the contribution and
significance of different parts of the developed SGU-MLP classification
algorithm. As seen in Table IV, the inclusion of the DWC block and SGU block
increased the classification accuracy of the MLP-Mixer model by approximately
4% and 1%, respectively, in terms of average accuracy for the Augsburg
dataset. The highest classification accuracy was achieved by the inclusion of
both the DWC and SGU blocks with an average accuracy of 66.79%, increasing the
classification accuracy of the MLP-Mixer algorithm by about 8%.

In the Berlin dataset, as illustrated in Table V, the inclusion of the SGU
block and DWC block increased the classification accuracy of the MLP-Mixer
algorithm by about 3% and 4%, respectively, in terms of Kappa index. By
incorporating both the DWC and SGU blocks, the highest classification was
attained with a Kappa index of 58.06%. This increased the accuracy of the MLP-
Mixer classifier by approximately 10%.

As demonstrated in Table VI, the inclusion of the DWC block and SGU block
increased the accuracy of the MLP-Mixer algorithm by approximately 1% and 3%,
respectively, in terms of average accuracy for the Houston dataset. By the
inclusion of both the DWC and SGU blocks, the MLP-Mixer’s classification
accuracy was increased by approximately 9% to 89.33%.

TABLE IV: Classification results of Augsburg dataset in terms of F-1 score
where $\kappa$ = Kappa index, OA = Overall Accuracy, AA = Average Accuracy,
respectively.

Class | MLP | SGU + MLP | DWC + MLP | SGUMLP
---|---|---|---|---
Forest | 0.88 | 0.92 | 0.94 | 0.94
Residential | 0.93 | 0.95 | 0.95 | 0.95
Industrial | 0.57 | 0.57 | 0.54 | 0.63
Low Plants | 0.96 | 0.98 | 0.98 | 0.98
Allotment | 0.17 | 0.27 | 0.41 | 0.36
Commercial | 0.19 | 0.26 | 0.25 | 0.28
Water | 0.56 | 0.56 | 0.53 | 0.52
OA$\times$100 | 88.21 | 90.86 | 91.39 | 91.82
AA$\times$100 | 61.41 | 65.83 | 64.42 | 66.79
$\kappa\times$100 | 82.95 | 86.83 | 87.57 | 88.22

TABLE V: Classification results of Augsburg dataset in terms of F-1 score
where $\kappa$ = Kappa index, OA = Overall Accuracy, AA = Average Accuracy,
respectively.

Class | MLP | SGU + MLP | DWC + MLP | SGUMLP
---|---|---|---|---
Forest | 0.71 | 0.74 | 0.70 | 0.73
Residential | 0.78 | 0.80 | 0.81 | 0.82
Industrial | 0.34 | 0.38 | 0.40 | 0.41
Low Plants | 0.61 | 0.70 | 0.66 | 0.72
Soil | 0.66 | 0.70 | 0.70 | 0.67
Allotment | 0.40 | 0.43 | 0.46 | 0.46
Commercial | 0.31 | 0.28 | 0.25 | 0.27
Water | 0.43 | 0.47 | 0.53 | 0.48
OA$\times$100 | 65.47 | 68.96 | 69.11 | 70.79
AA$\times$100 | 64.11 | 66.2 | 65.07 | 66.26
$\kappa\times$100 | 52 | 56.1 | 55.88 | 58.06

TABLE VI: Classification results of Houston dataset in terms of F-1 score
where $\kappa$ = Kappa index, OA = Overall Accuracy, AA = Average Accuracy,
respectively.

Class | MLP | SGU + MLP | DWC + MLP | SGUMLP
---|---|---|---|---
Healthy Grass | 0.89 | 0.90 | 0.90 | 0.90
Stressed Grass | 0.89 | 0.89 | 0.90 | 0.89
Synthetic Grass | 0.69 | 0.96 | 0.97 | 0.97
Tree | 0.90 | 0.93 | 0.92 | 0.94
Soil | 0.95 | 1 | 1 | 0.99
Water | 0.66 | 0.21 | 0.81 | 0.35
Residential | 0.65 | 0.80 | 0.77 | 0.81
Commercial | 0.70 | 0.82 | 0.81 | 0.83
Road | 0.79 | 0.87 | 0.81 | 0.85
Highway | 0.54 | 0.74 | 0.68 | 0.89
Railway | 0.71 | 0.84 | 0.82 | 0.82
Parking Lot1 | 0.76 | 0.96 | 0.95 | 0.96
Parking Lot2 | 0.89 | 0.89 | 0.87 | 0.90
Tennis Court | 0.93 | 1 | 1 | 0.99
Running Track | 0.90 | 0.96 | 0.95 | 0.95
OA$\times$100 | 78.04 | 85.03 | 86.44 | 87.91
AA$\times$100 | 81.26 | 87.03 | 88.12 | 89.33
$\kappa\times$100 | 76.20 | 83.85 | 85.28 | 86.91

##  IV Conclusion

Convolutional Neural Networks (CNNs) are commonly utilized frameworks for
hierarchical feature extraction. At the same time, due to the use of a self-
attention system, vision transformers (ViTs) can achieve better modeling of
global contextual information than CNNs. However, to realize their image
classification capability, ViTs require large training datasets. To overcome
this limitation, we developed the SGU-MLP algorithm based on advanced MLP
models and a spatial gating unit for land use land cover mapping which
demonstrated superior classification accuracy compared to several CNN and CNN-
ViT-based models. For the Houston experiment, for example, with a Kappa index
of 86.91%, the SGU-MLP algorithm significantly outperformed the classification
accuracy of the ResNet (65.49%), iFormer (68.71%), Efficientformer (69.25%),
CoAtNet (70.56%) and HybridSN (73.59%) algorithms. For the Augsburg dataset,
the SGU-MLP algorithm, with an average accuracy of 66.26%, again demonstrated
increased classification accuracy compared to ResNet (43.57%), CoAtNet(49.9%),
Efficientformer (52.81%), iFormer (52.96%) and HybridSN (55.76%).

## References

  * [1] J. Yang, A. Guo, Y. Li, Y. Zhang, and X. Li, “Simulation of landscape spatial layout evolution in rural-urban fringe areas: a case study of ganjingzi district,” _GIScience & Remote Sensing_, vol. 56, no. 3, pp. 388–405, 2019\. [Online]. Available: https://doi.org/10.1080/15481603.2018.1533680
  * [2] D. Haase, A. Haase, N. Kabisch, S. Kabisch, and D. Rink, “Actors and factors in land-use simulation: The challenge of urban shrinkage,” _Environmental Modelling & Software_, vol. 35, pp. 92–103, 2012. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S1364815212000606
  * [3] Y. Fan, X. Ding, J. Wu, J. Ge, and Y. Li, “High spatial-resolution classification of urban surfaces using a deep learning method,” _Building and Environment_ , vol. 200, p. 107949, 2021. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S036013232100353X
  * [4] P. Ghamisi, B. Rasti, N. Yokoya, Q. Wang, B. Hofle, L. Bruzzone, F. Bovolo, M. Chi, K. Anders, R. Gloaguen, P. M. Atkinson, and J. A. Benediktsson, “Multisource and multitemporal data fusion in remote sensing: A comprehensive review of the state of the art,” _IEEE Geoscience and Remote Sensing Magazine_ , vol. 7, no. 1, pp. 6–39, 2019.
  * [5] A. Muhammad, S. Sidrah, R. Swalpa Kumar, H. Danfeng, W. Xin, Y. Jing, M. K. Adil, M. Manuel, D. Salvatore, and C. Jocelyn, “Hyperspectral image classification–traditional to deep models: A survey for future prospects,” _IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing_ , vol. 15, pp. 968–999, 2022.
  * [6] S. K. Roy, A. Deria, D. Hong, B. Rasti, A. Plaza, and J. Chanussot, “Multimodal fusion transformer for remote sensing image classification,” _arXiv preprint arXiv:2203.16952_ , 2022.
  * [7] I. O. Tolstikhin, N. Houlsby, A. Kolesnikov, L. Beyer, X. Zhai, T. Unterthiner, J. Yung, A. Steiner, D. Keysers, J. Uszkoreit, M. Lucic, and A. Dosovitskiy, “Mlp-mixer: An all-mlp architecture for vision,” in _Advances in Neural Information Processing Systems_ , M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, Eds., vol. 34. Curran Associates, Inc., 2021, pp. 24 261–24 272.
  * [8] H. Liu, Z. Dai, D. So, and Q. V. Le, “Pay attention to mlps,” in _Advances in Neural Information Processing Systems_ , M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, Eds., vol. 34. Curran Associates, Inc., 2021, pp. 9204–9215. [Online]. Available: https://proceedings.neurips.cc/paper_files/paper/2021/file/4cc05b35c2f937c5bd9e7d41d3686fff-Paper.pdf
  * [9] M. Sandler, A. Howard, M. Zhu, A. Zhmoginov, and L.-C. Chen, “Mobilenetv2: Inverted residuals and linear bottlenecks,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2018.
  * [10] C. Debes, A. Merentitis, R. Heremans, J. Hahn, N. Frangiadakis, T. van Kasteren, W. Liao, R. Bellens, A. Pižurica, S. Gautama, W. Philips, S. Prasad, Q. Du, and F. Pacifici, “Hyperspectral and lidar data fusion: Outcome of the 2013 grss data fusion contest,” _IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing_ , vol. 7, no. 6, pp. 2405–2418, 2014.
  * [11] A. Okujeni, S. van der Linden, and P. Hostert, “Berlin-urban-gradient dataset 2009 - an enmap preparatory flight campaign,” 2016.
  * [12] D. Hong, J. Hu, J. Yao, J. Chanussot, and X. X. Zhu, “Multimodal remote sensing benchmark datasets for land cover classification with a shared and specific feature learning model,” _ISPRS Journal of Photogrammetry and Remote Sensing_ , vol. 178, pp. 68–80, 2021. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0924271621001362
  * [13] S. K. Roy, G. Krishna, S. R. Dubey, and B. B. Chaudhuri, “Hybridsn: Exploring 3-d–2-d cnn feature hierarchy for hyperspectral image classification,” _IEEE Geoscience and Remote Sensing Letters_ , vol. 17, no. 2, pp. 277–281, 2019.
  * [14] 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 (CVPR)_ , June 2016.
  * [15] H. Zhou, S. Zhang, J. Peng, S. Zhang, J. Li, H. Xiong, and W. Zhang, “Informer: Beyond efficient transformer for long sequence time-series forecasting,” _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 35, no. 12, pp. 11 106–11 115, May 2021. [Online]. Available: https://ojs.aaai.org/index.php/AAAI/article/view/17325
  * [16] Y. Li, G. Yuan, Y. Wen, J. Hu, G. Evangelidis, S. Tulyakov, Y. Wang, and J. Ren, “Efficientformer: Vision transformers at mobilenet speed,” 2022.
  * [17] Z. Dai, H. Liu, Q. Le, and M. Tan, “CoAtNet: Marrying convolution and attention for all data sizes,” in _Advances in Neural Information Processing Systems 34_ , 2021.


# Resolution of Yan’s conjecture on entropy of graphs

Stijn Cambie This author was unemployed when performing this research. E-mail:
<EMAIL_ADDRESS>Matteo Mazzamurro  Department of Computer Science,
University of Warwick, UK. E-mail<EMAIL_ADDRESS>This paper
is partly funded by: EPSRC Centre for Doctoral Training in Urban Science and
Progress (EP/L016400/1), EPSRC DTP (EP/N509796/1).

###### Abstract

The first degree-based entropy of a graph is the Shannon entropy of its degree
sequence normalized by the degree sum. In this paper, we characterize the
connected graphs with given order $n$ and size $m$ that minimize the first
degree-based entropy whenever $n-1\leq m\leq 2n-3,$ thus extending and proving
a conjecture by Yan.

##  1 Introduction

The first-degree based graph entropy and the Shannon entropy of other graph
invariants have attracted significant attention in organic chemistry, as
measures of uniformity of a graph’s structural aspect of interest [7, 1, 5].
Although Shannon entropy is conceptually and computationally simple, its
careful and context-informed normalisation and interpretation poses some
challenges. Determining the range of values the Shannon entropy of a graph
invariant can take is a non-trivial task as it may depend on the presence of
structural constraints on the graph [4]. Solving this issue requires first and
foremost the identification of the measure’s extremal values for graphs
satisfying natural constraints.

In [2], we determined the minimum first degree-based entropy among all graphs
with a given size. Here the extremal graphs are precisely the colex graphs. In
this paper, we do so for connected graphs with given size $m$ and order $n$,
which we call $(n,m)$-graphs, for the case when $n-1\leq m\leq 2m-3$. This
problem was first presented by Yan [9], who conjectured that the degree
sequence of the graph minimising the first-degree based graph entropy when
$m\geq n+9$ is $(n-1,m-n+2,2^{m-n+1},1^{2n-m-3}).$ Here we refine this
conjecture, first of all by noticing that such degree sequence is only
possible when $m\leq 2n-3$, and then showing how, with some adjustments, the
conjecture can be extended to the range $n-1\leq m\leq 2n-3$. We finally
proceed to prove it. The extremal graphs, i.e. the graphs minimizing the
entropy among all $(n,m)$-graphs, are presented in Table 1.

$m=n-1+a$ $0\leq a\leq n-2$ $a\not\in\\{3,5,6\\}$ |  $a$$n-2-a$
---|---
$m=n+2$ |  $n-4$
$m=n+4$ |  $n-5$$5$$n-7$
$m=n+5$ |  $n-5$
Table 1: Overview of extremal $(n,m)$-graphs minimizing the entropy

Let us now start by formally defining the measure of interest. Here the
logarithm will always denote the natural logarithm.

######  Definition 1.

The first degree-based entropy of a graph $G$ with degree sequence
$(d_{i})_{1\leq i\leq n}$ and size $m$ equals

$I(G)=-\sum_{i=1}^{n}\frac{d_{i}}{2m}\log\left(\frac{d_{i}}{2m}\right).$

If we let $f(x)=x\log(x)$ and
$h(G)=\sum_{i}f(d_{i})=\sum_{i}d_{i}\log(d_{i})$, then we have
$I(G)=\log(2m)-\frac{1}{2m}h(G).$ Thus, determining the minimum of $I(G)$ is
equivalent to determining the maximum of $h(G).$

By [9, Theorem 4], we know that the graph maximizing $h(G)$ among all
$(n,m)$-graphs is a threshold graph. This implies in particular that the graph
has a universal vertex $v$ with degree $n-1$. Now $G\backslash v$ is a
$(m-n+1,n-1)$-graph. Taking into account that $d_{G}(u)=d_{G\backslash
v}(u)+1$ for every vertex $u\in V\backslash v,$ we note that it is sufficient
to find the $(m-n+1,n-1)$-graph maximizing $h_{1}(G)$, where $h_{1}(G)$ is
formed by taking into account that the original degrees are larger by one. We
extend this idea towards the setting where there are $c$ universal vertices
initially. Then, we compute the extremal graphs maximizing the related
function $h_{c}(G)$ given only the size (and fixed large order essentially, as
explained in Subsection 1.1). We do so by induction. In Section 2 we compute
the extremal graphs for small size. These are the base cases for the
induction. Then by taking a vertex of minimum degree and relating $h_{c}(G)$
with $h_{c}(G\backslash v)$, we perform the induction in Section 3. Besides a
few exceptions, the extremal graphs turn out to be the star, contrary to the
extremal graphs for $h(G)$ when only the graph size is given, for which the
extremal graphs are colex graphs, see [2]. The precise statement is formulated
in Theorem 7. At the end of the section, in Subsection 3.1, we apply Theorem 7
to characterize the graphs minimizing the entropy among $(n,m)$-graphs when
$n-1\leq m\leq 2n-3$, thus proving an extended version of the conjecture
formulated by Yan [9, Conj. 6].

The main ideas of the proof are given in Section 3. Some necessary tools and
computations are gathered in Subsection 1.1 and Section 4.

###  1.1 Definitions

In this paper, we will express the entropy in terms of other functions and use
help functions in the computations. These are defined here.

######  Definition 2.

For any constant $c\geq 0,$ we define the function
$f_{c}(x)=(x+c)\cdot\log(x+c).$ For a graph $G$ with degree sequence
$(d_{i})_{1\leq i\leq n}$, we define $h_{c}(G)=\sum_{i}f_{c}(d_{i}).$ When
$c=0$, we just write $h(G)$ for $h_{0}(G)=\sum_{i}d_{i}\log(d_{i}).$

When $c\geq 2$, the function $h_{c}(G)$ depends on the number of vertices as
well, since isolated vertices contribute $f_{c}(0)=c\log c>0.$ Thus, we will
compare graphs with a different order by extending the order, i.e. add
isolated vertices in such a way that the graphs have the same order. We could
have defined $h_{c}^{N}(G)=\sum_{i}f_{c}(d_{i})+(N-n)f_{c}(0)$ to do so, but
preferred to keep the notation light.

We remark here that it will be sufficient to focus on connected graphs.

######  Observation 3.

When omitting the isolated vertices, the graph maximizing $h_{c}(G)$ among all
graphs of size $m$ is a connected graph. For this, note that identifying two
vertices in different components with strictly positive degrees $d_{u},d_{v}$
leads to an increase of the value $h_{c}(G)$ since $f_{c}$ is a strictly
convex function, i.e. $f_{c}(d_{u}+d_{v})+f_{c}(0)>f_{c}(d_{u})+f_{c}(d_{v}).$

In some proofs, we will also make use of the following function.

######  Definition 4.

The function $\Delta_{c}$ is defined by
$\Delta_{c}(x)=f_{c}(x)-f_{c}(x-1)=1+\int_{x+c-1}^{x+c}\log t\,\mathrm{d}t$.

Note that $\Delta_{c}$ is a strictly concave, increasing function.

##  2 Extremal graphs for small size

In this section, we compute the extremal graphs maximizing $h_{1}(G)$ for
$m\leq 10$ and for $h_{c}(G)$ with $c\geq 2$ for $m\leq 6.$

######  Lemma 5.

For $m\leq 10$, among all graphs with $m$ edges, we have that $h_{1}(G)$ is
maximized by

$G=\begin{cases}K_{1,m}=S_{m+1}&\mbox{ if }m\not\in\\{3,4,6\\}\\\ K_{3}&\mbox{
if }m=3\\\ K_{4}^{-}=\mathcal{C}(5,3)\mbox{ and }S_{6}&\mbox{ if }m=5\\\
K_{4}&\mbox{ if }m=6.\\\ \end{cases}$

###### Proof.

A computer program can verify this claim. Since $h_{1}(G)$ only depends on the
degree sequence of the graph, for a given $m\leq 10$, it is enough to list all
degree sequences of graphs of size $m$ and then compute $h_{1}$ for each
sequence. To list all degree sequences, it is sufficient to list all integer
partitions of $2m$ and then establish which of these are valid degree
sequences using one of several existing criteria (see, e.g., [8]). For
example, one can use the function `parts()` from the R-package `partitions`
[6] to list all partitions of $2m$ and check which ones are degree sequences
using `is_graphical()` from the R-package `igraph` [3] (see Appendix A). ∎

######  Lemma 6.

For $c\geq 2$ and $m\leq 6$, among all graphs with $m$ edges, we have that
$h_{c}(G)$ is maximized by

$G=\begin{cases}K_{1,m}&\mbox{ if }m\not=3\\\ K_{3}&\mbox{ if }m=3.\\\
\end{cases}$

Here one has to take into account isolated vertices when comparing graphs with
different order.

###### Proof.

For $m\in\\{1,2\\}$ nothing needs to be done, as there is only one connected
graph of size $m.$ When $m=3,$ there are precisely $3$ connected graphs and we
observe that

$h_{c}(P_{4})=2f_{c}(1)+2f_{c}(2)<h_{c}(S_{4})=3f_{c}(1)+f_{c}(3)<h_{c}(K_{3})=3f_{c}(2)+f_{c}(0).$

The first inequality is true due to the strict convexity of the function
$f_{c}.$ The second inequality is true since $\Delta_{c}$ (Definition 4) is
strictly concave and thus $\Delta_{c}(3)+\Delta_{c}(1)<2\Delta_{c}(2).$

By the inequality of Karamata, it is sufficient to consider the degree
sequences of graphs with size $m$ that are not majorized by the degree
sequences of other such graphs. With a simple computer
program111https://github.com/StijnCambie/EntropyGraphs/blob/main/ExtrG_h_c_forsmallm.py,
we verify those.

For $m=4$ and $m=5$, these non-majorized degree sequences are respectively
$\overrightarrow{v^{4}_{1}}=\\{4,1,1,1,1\\},\overrightarrow{v^{4}_{2}}=\\{3,2,2,1,0\\}$
and
$\overrightarrow{v^{5}_{1}}=\\{5,1,1,1,1,1\\},\overrightarrow{v^{5}_{2}}=\\{4,2,2,1,1,0\\},\overrightarrow{v^{5}_{3}}=\\{3,3,2,2,0,0\\}.$
For $m=6$, these degree sequences are
$\overrightarrow{v^{6}_{1}}=\\{6,1,1,1,1,1,1\\},\overrightarrow{v^{6}_{2}}=\\{5,2,2,1,1,1,0\\},\overrightarrow{v^{6}_{3}}=\\{4,3,2,2,1,0,0\\},\overrightarrow{v^{6}_{4}}=\\{3,3,3,3,0,0,0\\}.$

Now we verify that $h_{c}\left(\overrightarrow{d}\right)=\sum_{i}f_{c}(d_{i})$
is always maximized by the first degree sequence.

For $4\leq m\leq 6,$ we have

$h_{c}\left(\overrightarrow{v^{m}_{1}}\right)-h_{c}\left(\overrightarrow{v^{m}_{2}}\right)=\Delta_{c}(m)+\Delta_{c}(1)-2\Delta_{c}(2)\geq\int_{c-1}^{c}\log\left((t+1)(t+4)\right)-\log\left((t+2)^{2}\right)\,\mathrm{d}t>0.$

The last inequality is true since $(t+1)(t+4)>(t+2)^{2}$ whenever $t\geq 1$.

For $m\in\\{5,6\\}$ we analogously have

$\displaystyle
h_{c}\left(\overrightarrow{v^{m}_{1}}\right)-h_{c}\left(\overrightarrow{v^{m}_{3}}\right)$
$\displaystyle=\Delta_{c}(m)+\Delta_{c}(m-1)+2\Delta_{c}(1)-\Delta_{c}(3)-3\Delta_{c}(2)$
$\displaystyle\geq\int_{c-1}^{c}\log\left((t+5)(t+4)(t+1)^{2}\right)-\log\left((t+3)(t+2)^{3}\right)\,\mathrm{d}t$
$\displaystyle>0.$

The last inequality being true since $(t+5)(t+4)(t+1)^{2}>(t+3)(t+2)^{3}$
whenever $t\geq 1$.

For the final case, we have

$\displaystyle
h_{c}\left(\overrightarrow{v^{6}_{1}}\right)-h_{c}\left(\overrightarrow{v^{6}_{4}}\right)$
$\displaystyle=\Delta_{c}(6)+\Delta_{c}(5)+\Delta_{c}(4)+3\Delta_{c}(1)-3\Delta_{c}(3)-3\Delta_{c}(2)$
$\displaystyle=\int_{c-1}^{c}\log\left((t+6)(t+5)(t+4)(t+1)^{3}\right)-\log\left((t+3)^{3}(t+2)^{3}\right)\,\mathrm{d}t$
$\displaystyle>0.$

When $c=2$, this can be computed222It is approximately $0.0629$. For $c\geq
3,$ this is due to $(t+6)(t+5)(t+4)(t+1)^{3}>(t+3)^{3}(t+2)^{3}$ for $t\geq
2.$ Finally, it is also clear that the extremal degree sequences do correspond
with the star $S_{m+1}=K_{1,m}.$ ∎

##  3 Graphs maximizing $h_{c}(G)$ given the size

In this section, we prove the following theorem that gives the precise
characterization of extremal graphs for $h_{c}(G)$ where $c\geq 1$ is an
integer (for $c=0$, this was done in [2]).

######  Theorem 7.

Among all graphs with $m$ edges, we have that $h_{1}(G)$ is maximized by

$G=\begin{cases}K_{1,m}=S_{m+1}&\mbox{ if }m\not\in\\{3,4,6\\}\\\ K_{3}&\mbox{
if }m=3\\\ K_{4}^{-}=\mathcal{C}(5,3)\mbox{ and }S_{6}&\mbox{ if }m=5\\\
K_{4}&\mbox{ if }m=6.\\\ \end{cases}$

For any $c\geq 2$, among all graphs with $m$ edges and $n>m$ vertices, we have
that $h_{c}(G)$ is maximized by

$G=\begin{cases}K_{1,m}&\mbox{ if }m\not=3\\\ K_{3}&\mbox{ if }m=3.\\\
\end{cases}$

###### Proof.

Assume we know the extremal graphs with size at most $m-1.$ By Lemmas 5 and 6,
this has been done for $m\leq 6$ and for $m\leq 10$ when $c=1.$ So we assume
$m\geq 7$, and even $m\geq 11$ if $c=1.$ Let $G$ be an extremal graph with
size $m$ for which the minimum (non-zero) degree is equal to $b.$ The latter
implies that there are at least $b+1$ vertices with degree at least $b$ and
thus $m\geq\binom{b+1}{2}.$ Let $v$ be a vertex with degree $b$ and let
$d_{1},d_{2},\ldots,d_{b}$ be the degrees of the neighbours of $v$.

If $b=1$, we have

$\displaystyle h_{c}(G)$ $\displaystyle=h_{c}(G\backslash
v)+f_{c}(1)-f_{c}(0)+\Delta_{c}(d_{1})$ $\displaystyle\leq
h_{c}(K_{1,m-1})+f_{c}(1)-f_{c}(0)+\Delta_{c}(m)$
$\displaystyle=h_{c}(K_{1,m})$

and equality occurs if and only if $G=K_{1,m}.$

Now assume $b\geq 2.$ Note that $\sum_{i=1}^{b}d_{i}\leq m+\binom{b}{2}$ by
the analog of the handshaking lemma since every edge which is not part of
$G[N(v)]$ can be counted at most once. Since $\Delta_{c}$ is strictly concave,
we have

$\displaystyle h_{c}(G)-h_{c}(G\backslash v)$
$\displaystyle=f_{c}(b)-f_{c}(0)+\sum_{i=1}^{b}\Delta_{c}(d_{i})$
$\displaystyle\leq
f_{c}(b)-f_{c}(0)+b\cdot\Delta_{c}\left(\frac{m+\binom{b}{2}}{b}\right)$
$\displaystyle:=LHS(m,b,c).$

On the other hand, we also have

$\displaystyle h_{c}(K_{1,m})-h_{c}(K_{1,m-b})$
$\displaystyle=f_{c}(m)-f_{c}(m-b)+b\Delta_{c}\left(1\right)$
$\displaystyle:=RHS(m,b,c).$

By computations performed in Section 4, we know that the first is smaller than
the second, i.e. $LHS(m,b,c)<RHS(m,b,c).$ Now $G\backslash v$ has $m-b$ edges,
here $m-b\geq 4$ (for $c\geq 2$) and $m-b\geq 7$ (for $c=1$). Due to Lemmas 5
and 6 we have $h_{c}(G\backslash v)\leq h_{c}(K_{1,m-b}).$

So we conclude that

$\displaystyle h_{c}(G)$ $\displaystyle=h_{c}(G\backslash
v)+f_{c}(b)-f_{c}(0)+\sum_{i=1}^{b}\Delta_{c}(d_{i})$ $\displaystyle\leq
h_{c}(G\backslash
v)+f_{c}(b)-f_{c}(0)+b\cdot\Delta_{c}\left(\frac{m+\binom{b}{2}}{b}\right)$
$\displaystyle<h_{c}(K_{1,m-b})+f_{c}(m)-f_{c}(m-b)+b\Delta_{c}\left(1\right)$
$\displaystyle=h_{c}(K_{1,m}).$

By complete induction, we have the whole characterization. ∎

###  3.1 Proof of Yan’s Conjecture

We now prove an extended version of Yan’s conjecture [9, Conj.6].

######  Theorem 8.

When $n\leq m\leq 2n-3$, the extremal $(n,m)$-graph minimizing the entropy is
such that, deleting its universal vertex, one obtains the $(n-1,m-n+1)$-graph
$G$ described in Theorem 7 for the $c=1$ case, i.e. the graph with
$m^{\prime}=m-n+1$ edges maximizing $h_{1}(G).$ That is, the extremal
$(n,m)$-graph has degree sequence

$\begin{cases}(n-1,m-n+2,2^{m-n+1},1^{2n-m-3})&\mbox{ if }2n-3\geq m\geq
n+6\mbox{ or }m\in\\{n,n+1,n+3\\},\\\ (n-1,4^{4},1^{n-5})&\mbox{ if }m=n+5,\\\
(n-1,4^{2},3^{2},1^{n-5})\mbox{ or }(n-1,6,2^{5},1^{n-7})&\mbox{ if }m=n+4,\\\
(n-1,3^{3},1^{n-4})&\mbox{ if }m=n+2,\\\ (n-1,1^{n-1})&\mbox{ if }m=n-1.\\\
\end{cases}$

These graphs are presented in Table 1.

###### Proof.

By [9, Theorem 4], we know that the extremal $(n,m)$-graph is a threshold
graph. This implies in particular that it has a universal vertex $v$ with
degree $n-1$. Now $G^{\prime}=G\backslash v$ is a $(m-n+1,n-1)$-graph. Taking
into account that $d_{G}(u)=d_{G^{\prime}}(u)+1$ for every vertex $u\in
V\backslash v,$ we note that

$h(G)=f(n-1)+h_{1}(G^{\prime}).$

Now since $m-n+1\leq n-2,$ we note that the extremal structure for
$G^{\prime}$ is determined in Theorem 7 and the conclusion is immediate. ∎

##  4 Computational claims

In this section, we prove that

$LHS(m,b,c)=f_{c}(b)-f_{c}(0)+b\cdot\left(f_{c}\left(\frac{m+\binom{b}{2}}{b}\right)-f_{c}\left(\frac{m+\binom{b}{2}}{b}-1\right)\right)$

and

$RHS(m,b,c)=f_{c}(m)-f_{c}(m-b)+b\cdot(f_{c}(1)-f_{c}(0))$

satisfy $LHS(m,b,c)<RHS(m,b,c)$ for every $b\geq 2$ and $m\geq\binom{b+1}{2}$
whenever $m\geq 7$ and $c\geq 1$, or $m\geq 4$ and $c\geq 2.$

We do this by means of the following claims. In Claim 9, we prove that for
fixed $b$ and $c$, it is sufficient to prove it for the smallest $m$ in the
range. After that, it is proven in the cases for which $m=\binom{b+1}{2}$ in
Claim 10 and for the remaining cases in Claim 11.

The proofs are mainly computational and there are alternative computations
that lead to the same conclusion.

######  Claim 9.

Fix $b\geq 2$ and $c\geq 1.$ Then $RHS(m,b,c)-LHS(m,b,c)$ is an increasing
function in $m.$

###### Proof.

We want to prove that the derivative of this quantity with respect to $m$ is
positive. To compute the derivative, taking into account the chain rule and
$\frac{d}{dx}f_{c}(x)=\log(x+c)+1$, we have that

$\frac{d}{dm}\left(RHS(m,b,c)-LHS(m,b,c)\right)=\log\left(\frac{m+c}{m-b+c}\right)-\log\left(\frac{m+\binom{b}{2}+bc}{m+\binom{b}{2}+bc-b}\right)>0.$

The inequality now follows the fact whenever $0<b<y<z$, we have
$\frac{y}{y-b}>\frac{z}{z-b}$. Here it is enough to take $y=m+c$ and
$z=m+\binom{b}{2}+bc$. ∎

######  Claim 10.

Fix $b\geq 2$ and $c\geq 1.$ Let

$LL(b,c)=(b+1)f_{c}(b)-f_{c}(0)-bf_{c}(b-1)$

and

$RL(b,c)=f_{c}\left(\binom{b+1}{2}\right)-f_{c}\left(\binom{b}{2}\right)+b\cdot\left(f_{c}(1)-f_{c}(0)\right).$

Then

$LL(b,c)<RL(b,c)$

if $c=1$ and $b\geq 4$, or $c\geq 2$ and $b\geq 3.$

###### Proof.

The cases $1\leq c\leq 3$ can be verified directly using the formulae: solving
numerically the resulting inequalities in the variable $b$, one finds that the
inequality holds as long as $b>3.24$, $b>2.53$, and $b>2.34$ for $c=1$, $c=2$,
and $c=3$, respectively. A proof that $RL(b,c)-LL(b,c)$ is increasing in $b$,
has been put in Appendix B, where an alternative strategy for the verification
of this claim has been given.

For $c\geq 4$ and $b\geq 3$, write

$\displaystyle RL(b,c)$
$\displaystyle=f_{c}\left(\binom{b}{2}+b\right)-f_{c}\left(\binom{b}{2}\right)+b\Delta_{c}(1)$
$\displaystyle=\sum_{i=1}^{b}\left[f_{c}\left(\binom{b}{2}+i\right)-f_{c}\left(\binom{b}{2}+i-1\right)\right]+b\Delta_{c}(1)$
$\displaystyle=\sum_{i=1}^{b}\Delta_{c}\left(\binom{b}{2}+i\right)+b\Delta_{c}(1),$

and

$\displaystyle LL(b,c)$
$\displaystyle=b\left(f_{c}(b)-f_{c}(b-1)\right)+f_{c}(b)-f_{c}(0)$
$\displaystyle=b\Delta_{c}(b)+f_{c}(b)-f_{c}(0)$
$\displaystyle=b\Delta_{c}(b)+\sum_{i=1}^{b}\left[f_{c}(i)-f_{c}(i-1)\right]$
$\displaystyle=b\Delta_{c}(b)+\sum_{i=1}^{b}\Delta_{c}(i).$

Then

$\displaystyle RL(b,c)-LL(b,c)$
$\displaystyle=\sum_{i=1}^{b}\left[\Delta_{c}\left(\binom{b}{2}+i\right)-\Delta_{c}(i)\right]-b\left(\Delta_{c}(b)-\Delta_{c}(1)\right)$
$\displaystyle>b\left[\Delta_{c}\left(\binom{b}{2}+b\right)-\Delta_{c}(b)\right]-b\left(\Delta_{c}(b)-\Delta_{c}(1)\right)$
(1)
$\displaystyle=b\left[\Delta_{c}\left(\binom{b+1}{2}\right)+\Delta_{c}(1)-2\Delta_{c}(b)\right]$

where inequality (1) follows from $b\geq 2$ and the strict concavity of
$\Delta_{c}(x)$. Then, by definition 4,

$RL(b,c)-LL(b,c)\geq
b\int_{c-1}^{c}\left(\log\left(t+\binom{b+1}{2}\right)+\log(t+1)-2\log(t+b)\right)\,\mathrm{d}t\\\
$

For the integral to be positive, it is enough that, for $c-1<t<c$,

$\left(t+\binom{b+1}{2}\right)(t+1)-(t+b)^{2}>0,$

which is equivalent to

$t(b-2)(b-1)>b(b-1).$ (2)

Now, since $b\geq 3$, inequality (2) holds if and only if $t>\frac{b}{b-2}$.
Furthermore, $b\geq 3$ also implies $\frac{b}{b-2}\leq 3$. But $c\geq 4$ so
$t>c-1=3\geq\frac{b}{b-2}$. Therefore $RL(b,c)>LL(b,c)$ for $c\geq 4$ and
$b\geq 3$ as well. ∎

######  Claim 11.

It is true that $LHS(7,3,1)<RHS(7,3,1)$ and $LHS(7,2,1)<RHS(7,2,1).$
For any $c\geq 2$, it is true that $LHS(4,2,c)<RHS(4,2,c).$

###### Proof.

The values $RHS(7,3,1)-LHS(7,3,1)$ and $RHS(7,2,1)-LHS(7,2,1)$ are
approximately $0.18$ and $0.36$ respectively and thus $LHS(7,3,1)<RHS(7,3,1)$
and $LHS(7,2,1)<RHS(7,2,1).$ The second inequality is equivalent to

$\Delta_{c}(4)+\Delta_{c}(3)+\Delta_{c}(1)>2\Delta_{c}(2.5)+\Delta_{c}(2).$

This is true for every $c\geq 2$ since

$\displaystyle\int_{c-1}^{c}\log\left((t+4)(t+3)(t+1)\right)\,\mathrm{d}t>\int_{c-1}^{c}\log\left(\left(t+\frac{5}{2}\right)^{2}(t+2)\right)\,\mathrm{d}t,$

as $(t+4)(t+3)(t+1)>\left(t+\frac{5}{2}\right)^{2}(t+2)$ for every $t\geq 1.$
∎

## References

  * [1] D. Bonchev.  Information Theoretic Indices for Characterization of Chemical Structures.  Research Studies Press, Chichester, 1983.
  * [2] S. Cambie and M. Mazzamurro.  Minimum entropy of graphs with given size.  arXiv e-prints, page arXiv:2204.08251, Apr. 2022.
  * [3] G. Csardi and T. Nepusz.  The igraph software package for complex network research.  InterJournal, Complex Systems:1695, 2006.  https://igraph.org.
  * [4] M. Dehmer and V. Kraus.  On extremal properties of graph entropies.  MATCH Commun. Math. Comput. Chem, 68(3):889–912, 2012.
  * [5] M. Dehmer, K. Varmuza, S. Borgert, and F. Emmert-Streib.  On entropy-based molecular descriptors: Statistical analysis of real and synthetic chemical structures.  Journal of chemical information and modeling, 49(7):1655–1663, 2009\.
  * [6] R. K. S. Hankin and P. Egeler.  partitions: Additive Partitions of Integers, 2021.  R package version 1.10-4, https://CRAN.R-project.org/package=partitions.
  * [7] A. Mowshowitz.  Entropy and the complexity of graphs: I. an index of the relative complexity of a graph.  The bulletin of mathematical biophysics, 30(1):175–204, 1968.
  * [8] G. Sierksma and H. Hoogeveen.  Seven criteria for integer sequences being graphic.  Journal of Graph theory, 15(2):223–231, 1991.
  * [9] J. Yan.  Topological structure of extremal graphs on the first degree–based graph entropies.  MATCH Commun. Math. Comput. Chem., 85(2):275–284, 2021.

##  Appendix A Codes

The following R code can be used to prove Lemma 5.

⬇

#load necessary packages

library(partitions)

library(igraph)

#define function h_c

h_c <- function(x,c){

#avoid issues with log(0)

if(c==0){

x[x==0] <- 1

}

ans <- sum((x+c)*log(x+c))

return(ans)

}

#allow tolerance in the comparison to account for machine precision

tol<-1e-6

#initialize empty list of degree sequences

h_c_max <- list()

for(m in 3:10){

#find partitions of 2m

parts_m <- as.matrix(parts(2*m))

#select partitions that are valid degree sequences

is_graphical_m <- apply(parts_m,MARGIN=2,is_graphical)

graphical_parts_m <- as.matrix(parts_m[,is_graphical_m])

#find which degree sequence(s) maximize(s) h_c

h_c_m <- apply(graphical_parts_m,MARGIN=2,h_c,c=1)

h_c_m_max <- graphical_parts_m[,which((max(h_c_m)-h_c_m)<tol)]

#add the degree sequence(s) maximizing h_c_m to the list

h_c_max <- append(h_c_max,list(h_c_m_max))

}

##  Appendix B Precise verification of Claim 10

For easy reference, we restate Claim 10 here.

######  Claim 12.

Fix $b\geq 2$ and $c\geq 1.$ Let

$LL(b,c)=(b+1)f_{c}(b)-f_{c}(0)-bf_{c}(b-1)$

and

$RL(b,c)=f_{c}\left(\binom{b+1}{2}\right)-f_{c}\left(\binom{b}{2}\right)+b\cdot\left(f_{c}(1)-f_{c}(0)\right).$

Then

$LL(b,c)<RL(b,c)$

if $c=1$ and $b\geq 4$, or $c\geq 2$ and $b\geq 3.$

###### Proof.

We first prove that the derivative of this quantity with respect to $b$ is
positive. We have

$\displaystyle\frac{d}{db}RL(b,c)=$
$\displaystyle\frac{2b+1}{2}\left(\log\left(\binom{b+1}{2}+c\right)+1\right)$
$\displaystyle-\frac{2b-1}{2}\left(\log\left(\binom{b}{2}+c\right)+1\right)+f_{c}(1)-f_{c}(0)$
$\displaystyle\frac{d}{db}LL(b,c)=$
$\displaystyle(b+1)\left(\log\left(b+c\right)+1\right)$
$\displaystyle-b\left(\log\left(b+c-1\right)+1\right)+f_{c}(b)-f_{c}(b-1)$

Combining these two expression, we can write

$\frac{d}{db}\left(RL(b,c)-LL(b,c)\right)=J_{1}(b,c)+J_{2}(b,c)+J_{3}(b,c),$
(3)

where

$\displaystyle J_{1}(b,c)=$
$\displaystyle\frac{2b-1}{2}\left(\log\left(\binom{b+1}{2}+c\right)-\log\left(\binom{b}{2}+c\right)-2\log\left(b+c\right)+2\log\left(b+c-1\right)\right),$
$\displaystyle J_{2}(b,c)=$ $\displaystyle
c\left(\log(c+1)-\log(c)-\log(b+c)+\log(b+c-1)\right),$ $\displaystyle
J_{3}(b,c)=$
$\displaystyle\log\left(\binom{b+1}{2}+c\right)+\log(c+1)-2\log(b+c).$

It is sufficient to prove that $J_{i}(b,c)\geq 0$ for $i\in\\{1,2,3\\}$ for
the above conditions on $b$ and $c$.

By expanding the binomial coefficient, we rewrite $J_{1}(b,c)$ as

$J_{1}(b,c)=\frac{2b-1}{2}\log\left(\frac{(b^{2}+b+2c)(b+c-1)^{2}}{(b^{2}-b+2c)(b+c)^{2}}\right).$

Then $J_{1}(b,c)>0$ if and only if $g(b,c)>0$, where

$g(b,c)=(b^{2}+b+2c)(b+c-1)^{2}-(b^{2}-b+2c)(b+c)^{2}.$

This can be simplified as

$g(b,c)=2(b-3)bc+2(b-2)c^{2}+b+2c-b^{2}.$

Hence we can see that, whenever $b\geq 3$,

$\frac{\partial}{\partial c}g(b,c)=4(b-2)c+2(b-3)b+2>0,$

and so $g(b,c)$ is a strictly increasing function in $c$ whenever $b\geq 3$.

For $c=1$ we have that ${g(b,1)=b^{2}-3b-2>0}$ for $b\geq 4$. Similarly, for
$c=2$, we get ${g(b,2)=3b^{2}-3b-12>0}$ for $b\geq 3$. Thus $g(b,c)>0$ (and
hence $J_{1}(b,c)>0$) for $c=1$ and $b\geq 4$, and for $c\geq 2$ and $b\geq
3$.

Analogous arguments apply to $J_{2}$ and $J_{3}$.

$J_{2}(b,c)>0$ since
$\log\left(1+\frac{1}{c}\right)>\log\left(1+\frac{1}{b+c-1}\right)$ when
$b-1>0$.

For $J_{3}(b,c)$ note that

$2\left(\binom{b+1}{2}+c\right)(c+1)-2(b+c)^{2}=(bc-2c-b)(b-1),$

which is non-negative whenever $b,c\geq 3$.

Combining these results and substituting in equation (3), we have
${\frac{d}{db}\left(RL(b,c)-LL(b,c)\right)>0}$ for $c\geq 3$.

For the remaining cases, consider the sum $J_{2}(b,c)+J_{3}(b,c)$. When $c=1,$

$J_{2}(b,1)+J_{3}(b,1)=\log\left(\frac{2b(b^{2}+b+2)}{(b+1)^{3}}\right).$

Now,

$2b(b^{2}+b+2)-(b+1)^{3}=(b-1)(b^{2}+1),$

which is positive for $b>1$. Similarly,

$J_{2}(b,2)+J_{3}(b,2)=\log\left(\frac{27(b^{2}+b+4)(b^{2}+2b+1)}{8(b^{2}+4b+4)^{2}}\right),$

and

$27(b^{2}+b+4)(b^{2}+2b+1)-8(b^{2}+4b+4)^{2}=(b-1)(19b^{3}+36b^{2}+33b+20),$

which is positive for $b>1$.

Hence $J_{2}(b,c)+J_{3}(b,c)>0$ when $b\geq 2$ and $c=1$ or $c=2$. Combining
with the results for $J_{1}(b,c)$, and substituting in equation (3), we
conclude that ${\frac{d}{db}\left(RL(b,c)-LL(b,c)\right)>0}$ for $c=1$ and
$b\geq 4$, and $c=2$ and $b\geq 3$ as well.

Since the derivative is positive in all cases, it is sufficient to prove that
$RL(4,1)>LL(4,1)$ and $RL(3,c)>LL(3,c).$ The first one can be verified
directly, a computation shows that $RL(4,1)-LL(4,1)\sim 0.245$ and thus
$RL(4,1)>LL(4,1)$. The second inequality, $RL(3,c)>LL(3,c)$, is equivalent to

$\Delta_{c}(6)+\Delta_{c}(5)+\Delta_{c}(4)+2\Delta_{c}(1)>4\Delta_{c}(3)+\Delta_{c}(2).$

This is true for every $c\geq 2$ since

$\displaystyle\int_{c-1}^{c}\log\left((t+6)(t+5)(t+4)(t+1)^{2}\right)\,\mathrm{d}t>\int_{c-1}^{c}\log\left((t+3)^{4}(t+2)\right)\,\mathrm{d}t,$

as $(t+6)(t+5)(t+4)(t+1)^{2}>(t+3)^{4}(t+2)$ for every $t\geq 1.$ ∎