# Automatic Classification of Galaxy Morphology: A Rotationally-invariant
supervised Machine-learning method based on the Unsupervised Machine-learning
Data Set

GuanWen Fang Institute of Astronomy and Astrophysics, Anqing Normal
University, Anqing 246133, People’s Republic of China<EMAIL_ADDRESS>Shuo Ba  Shuo Ba and GuanWen Fang contributed equally to this work  School of
Engineering, Dali University, Dali 671003, People’s Republic of China;
<EMAIL_ADDRESS>Yizhou Gu School of Physics and Astronomy, Shanghai
Jiao Tong University, 800 Dongchuan Road, Minhang, Shanghai 200240, People’s
Republic of China<EMAIL_ADDRESS>Zesen Lin CAS Key Laboratory for
Research in Galaxies and Cosmology, Department of Astronomy, University of
Science and Technology of China, Hefei 230026, People’s Republic of China;
<EMAIL_ADDRESS>School of Astronomy and Space Science, University of Science
and Technology of China, Hefei 230026, People’s Republic of China  Department
of Physics, The Chinese University of Hong Kong, Shatin, N.T., Hong Kong
S.A.R., China  Yuejie Hou  School of Engineering, Dali University, Dali
671003, People’s Republic of China<EMAIL_ADDRESS>Chenxin Qin
School of Engineering, Dali University, Dali 671003, People’s Republic of
China<EMAIL_ADDRESS>Chichun Zhou School of Engineering, Dali
University, Dali 671003, People’s Republic of China<EMAIL_ADDRESS>Jun Xu  Institute of Astronomy and Astrophysics, Anqing Normal University,
Anqing 246133, People’s Republic of China<EMAIL_ADDRESS>Yao Dai
Institute of Astronomy and Astrophysics, Anqing Normal University, Anqing
246133, People’s Republic of China<EMAIL_ADDRESS>Jie Song  CAS Key
Laboratory for Research in Galaxies and Cosmology, Department of Astronomy,
University of Science and Technology of China, Hefei 230026, People’s Republic
of China<EMAIL_ADDRESS>School of Astronomy and Space Science, University
of Science and Technology of China, Hefei 230026, People’s Republic of China
Xu Kong CAS Key Laboratory for Research in Galaxies and Cosmology, Department
of Astronomy, University of Science and Technology of China, Hefei 230026,
People’s Republic of China<EMAIL_ADDRESS>School of Astronomy and Space
Science, University of Science and Technology of China, Hefei 230026, People’s
Republic of China

###### Abstract

Classification of galaxy morphology is a challenging but meaningful task for
the enormous amount of data produced by the next-generation telescope. By
introducing the adaptive polar coordinate transformation, we develop a
rotationally invariant supervised machine learning (SML) method that ensures
consistent classifications when rotating galaxy images, which is always
required to be satisfied physically but difficult to achieve algorithmically.
The adaptive polar coordinate transformation, compared with the conventional
method of data augmentation by including additional rotated images in the
training set, is proved to be an effective and efficient method in improving
the robustness of the SML methods. In the previous work, we generated a
catalog of galaxies with well-classified morphologies via our developed
unsupervised machine learning (UML) method. By using this UML-dataset as the
training set, we apply the new method to classify galaxies into five
categories (unclassifiable, irregulars, late-type disks, early-type disks, and
spheroids). In general, the result of our morphological classifications
following the sequence from irregulars to spheroids agrees well with the
expected trends of other galaxy properties, including Sérsic indices,
effective radii, nonparametric statistics, and colors. Thus, we demonstrate
that the rotationally invariant SML method, together with the previously
developed UML method, completes the entire task of automatic classification of
galaxy morphology.

Galaxy structure (622), Astrostatistics techniques (1886), Astronomy data
analysis (1858)

##  1 Introduction

Galaxy morphology is closely related to the formation and assembly history of
the galaxy. For example, as galaxies evolve, structures, such as bulges, bars,
and spiral arms or tidal tails, are formed. Moreover, morphology is related to
color, stellar mass, star formation rate, gas content, and environments (e.g.,
Dressler 1980; Kauffmann et al. 2003; Baldry et al. 2004; Lianou et al. 2019).
Therefore, the classification or quantification of galaxy morphology is
instrumental in understanding galaxy evolution. Besides the model-dependent or
model-independent parameters developed to quantify galaxy morphology or
structural features (Sérsic, 1963; Lotz et al., 2004; Conselice, 2014),
morphological classification of galaxies (Hubble, 1926) is a fundamental
problem and attracts great interests.

A direct way to carry out a certain scheme of the morphological classification
is by visual inspections (e.g., Hubble 1926; de Vaucouleurs 1959; van den
Bergh 1960). For example, volunteers were gathered to identify the
morphological types of galaxies in the Galaxy Zoo project (e.g., Lintott et
al. 2011; Simmons et al. 2017; Walmsley et al. 2022). Besides the visual
inspections, methods based on the multi-dimensional morphological parameter
space are developed, where the boundary of distinctions can be defined by the
empirical cuts (Lotz et al., 2004; Conselice, 2014) or machine learning
algorithms, such as the principal component analysis (Scarlata et al., 2007)
and the support-vector machine (Huertas-Company et al., 2008).

In recent years, deep learning methods are introduced to the morphological
classification of galaxies. Instead of searching the boundaries in the
parameter spaces consisting of manually designed parameters, they directly
extract key features from the two-dimensional images with single or multiple
channels and give the morphological types. For example, the convolutional
neural network (CNN) can directly extract enormous information from raw pixels
hierarchically and is capable of mimicking human perceptions. The supervised
neural networks had been applied to galaxy classification in several imaging
surveys, e.g., Sloan Digital Sky Survey, Dark Energy Survey, and Cosmic
Assembly Near-infrared Deep Extragalactic Legacy Survey at higher redshift
(Dieleman et al., 2015; Huertas-Company et al., 2015; Domínguez Sánchez et
al., 2018, 2019; Barchi et al., 2020; Cheng et al., 2020b, 2021b; Vega-Ferrero
et al., 2021). Beyond the morphological classification, they were also used to
identify galaxies with specific features such as bar structures (Abraham et
al., 2018) or galaxies that might suffer gravitational lensing effect (Li et
al., 2020).

However, the existing solutions of galaxy morphological classification suffer
from the following shortcomings. (1) The supervised deep learning methods
require large pre-labeled data sets as the training sets. Usually, such data
sets are obtained by visual inspections, which are low efficiency, high cost,
and with subjective bias. (2) The CNN-based neural networks have poor
robustness to image rotations (see Cheng et al. 2016, 2018; Cabrera-Vives et
al. 2017; Chen et al. 2018; Reyes et al. 2018; Yao et al. 2019). That is, the
algorithms might misclassify the morphological types of galaxies after
rotating their images. Usually, the conventional solution to this problem is
to perform data augmentation by including additional rotated images in the
training set (e.g., Dieleman et al. 2015), which inevitably consumes a huge
amount of unnecessary computing resources.

The unsupervised techniques that combine a convolutional autoencoder (CAE;
Masci et al. 2011) with clustering methods have been applied in the
classification tasks, such as gravitational lensing detection (Cheng et al.,
2020a) and galaxy morphological classification (Cheng et al., 2021a). The CAE
is used to extract key features of galaxies from the raw images, while
clustering algorithms are responsible for gathering the galaxies with similar
features into a group subsequently. Different clustering algorithms, using
different similarity definitions and techniques, may result in inconsistent
clustering output. To obtain a comprehensive perspective of classifications,
we develop the bagging-based multi-clustering method that clusters galaxies by
the voting of three clustering algorithms (Zhou et al., 2022), rather than
using a single algorithm. To establish a high-quality classification of galaxy
morphology, only the galaxies with consistent voting by the three clustering
algorithms are collected as the “well-classified” dataset (hereafter the UML-
dataset). In Zhou et al. (2022), the application of the proposed UML method to
$47,149$ galaxies with $H<24.5$ in five CANDELS fields resulted in a UML-
dataset containing $24,900$ galaxies ($\sim 53\%$), at the cost of leaving
$22,249$ galaxies ($\sim 47\%$) with disputed labels.

In this work, to handle the remaining $22,249$ galaxies with disputed labels
and complete the entire task of automatic classification of galaxy morphology,
we further propose a rotationally invariant supervised machine learning (SML)
method by using the UML-dataset as the training set. Unlike the conventional
method of data augmentation, we propose a different method (adaptive polar
coordinate transformation; APCT) to consider the rotation invariance of the
CNN model in the pre-processing step, which converts the rotation-invariant
problem into a translation-invariant problem.

The paper is organized as follows. The sample selection and UML-dataset are
described in Section 2. The APCT and other pre-process strategies are
introduced in Section 3. In Section 4, we introduce three typical existing SML
models. The combination of the APCT and the SML algorithms is used directly to
give the morphological types of galaxies. In Section 5, the result of
morphological classification is given. The effectiveness of the proposed
method is evaluated by the t-SNE visualization graphs and galaxy properties as
a function of our classification results from the best model. Finally, a
summary is given in Section 6.

##  2 Sample selection and UML-dataset

In this section, we give a brief introduction to the galaxy sample, which is
in line with Zhou et al. (2022). The sample of $47,149$ galaxies with F160W
$<$ 24.5 mag are selected from the five CANDELS fields, with an additional
criterion being the flag use_phot=1, which means that the object is not a star
and not heavily contaminated. Here we refer to the 3D-HST project (Skelton et
al., 2014; Momcheva et al., 2016) for the full details, from which the H-band
selected catalogs (v4.1.5) and H-band images are taken in this work.

To accomplish a well-classified dataset, a UML method, the combination of the
CAE and the bagging-based multi-clustering method, is proposed in our previous
work (Zhou et al., 2022). It has been applied to $47,149$ galaxies with
$H<24.5$ extracted from five CANDLES fields. In this method, only galaxies
with consistent clustering results from three clustering algorithms were
defined as “well-clustered sample” and then “well classified” into different
morphological types (see Zhou et al. 2022 for more details). As a result,
$24,900$ galaxies ($\sim 53\%$) are well classified, without any pre-labeled
galaxies, yielding the UML-dataset. In this dataset, galaxies are classified
into five categories, including $6,335$ spheroid (SPH), $3,916$ early-type
disk (ETD), $4,333$ late-type disk (LTD), $9,851$ irregular (IRR), and $465$
unclassifiable (UNC) galaxies. It provides enough samples to learn the key
features corresponding to each category. The overview of UML-dataset is
illustrated in Figure 1, including the example stamps, the t-Distributed
Stochastic Neighbor Embedding (t-SNE) visualization, and the counting
distribution of the five categories. The t-SNE is a technique that visualizes
the high dimensional data by giving each data point a location in a two or
three-dimensional map (van der Maaten & Hinton, 2008).

Figure 1: An overview of the UML-dataset. Left: Cutouts of galaxies selected
from different categories, i.e., SPH, ETD, LTD, IRR, and UNC galaxies, are
shown from top to bottom. Right: The t-SNE visualization of 6000 randomly
selected galaxies with different morphologies (top) and the corresponding
counting distribution (bottom) in the UML-dataset are given.

However, the remaining $22,249$ galaxies ($\sim 47\%$; hereafter the UML
remaining dataset) were eliminated in Zhou et al. (2022) due to the disputed
votes from different clustering algorithms. In order to complete the
morphological classification of galaxies, the UML-dataset is considered as the
training set for the downstream SML methods. That is, by training the SML
models on the UML-dataset, we obtain algorithms that can give the
morphological classification for the rest of the sample.

In general, the performances of algorithms are affected by the signal-to-noise
ratios (SNRs) of images and the . SNR is defined as the ratio between the flux
and the corresponding uncertainty in H-band, which are extracted from Skelton
et al. (2014). In this work, we use the astronomical definition of position
angles (PA) to approximately represent the orientation of galaxies for
simplicity. By assuming a single elliptical Sérsic model of light profile
(central symmetric) for galaxies, PA describes the direction of the major axis
of the assumed elliptical profile, which is measured with GALFIT by van der
Wel et al. (2014). As shown in Figure 2, due to the large sample size,
galaxies in the UML-dataset have a relatively uniform PA distribution with
small fluctuation. However, the distribution of image SNRs is not as uniform
as that of PAs and exhibits a peak at $\sim 1000$. Problem arising from this
uneven SNR distribution will be further discussed and be solved in Section
3.2. It is noteworthy that the astronomically defined PA ranging from -90∘ to
$90^{\circ}$ cannot fully constrain the orientations of galaxies due to the
fact that the light profiles and backgrounds of galaxies in observations are
not perfectly central symmetric. Thus, unlike the model profile of galaxies,
the raw image from observation and its rotated image are not exactly the same.
The standard CNN models are not rotation invariant which might recognize them
as different types. If the rotation features are not well learned by the
machine, the algorithm might give different classifications for images of the
same galaxy before and after rotating the image by a certain degree. However,
It is expected that the classification results should not be affected by how
galaxy images are rotated. Instead of feeding in more images in the training
phase by artificially rotating to solve this problem, we propose an APCT in
the pre-process phase as described in Section 3.1.

Figure 2: Distributions of the image SNRs (left) and positional angles (right)
of galaxies in the UML-dataset.

##  3 The APCT and Other Pre-processing Strategies

The pre-processing strategies are also important for the SML algorithms. In
this section, the proposed adaptive polar coordinate transformation and other
pre-processing strategies are introduced.

###  3.1 The APCT

The morphological classification of galaxies should be rotationally invariant,
which means that the result of morphological classification should not change
regardless of how the raw image of one galaxy is rotated. CNN extracts the
local translation-invariant features effectively, which is widely used to
learn the key morphological features of the galaxies. However, the standard
CNN models have poor robustness to rotations of images (see Cheng et al. 2016,
2018; Cabrera-Vives et al. 2017; Chen et al. 2018; Reyes et al. 2018; Yao et
al. 2019). Existing SML algorithms, such as the CNN-based neural networks, are
affected by the rotational angle so that they might not recognize galaxies
with the same morphological type after rotation. The performance of the SML
methods will be affected, especially when the training set has an uneven
distribution of orientations.

Data augmentation and conventional polar coordinate transformation are both
strategies to overcome the problem of rotation invariance. Data augmentation
is a common treatment that generates extra images by rotating the raw images
to make the angles evenly distributed in the training set. Another alternative
is the polar coordinate transformation that transforms the rotation of the raw
images into the translation of the new images, as well as the potential
features. By combining the polar coordinate transformation with the CNN, which
is translation-invariant, one obtains a rotation-invariant algorithm. For
example, the polar coordinate transformation is used to transform circle-like
features in the CT Images of vulnerable plaques into line-like features (Liu
et al., 2019).

Figure 3: Examples of the conventional polar coordinate transformation. It
shows that the conventional polar coordinate transformation can not transform
the rotations of the raw images into perfect translations of the new images.

To yield an efficient data pre-processing method for galaxy images, we adopt
the polar coordinate transformation rather than data augmentation in the pre-
processing phase of our rotationally invariant SML method. However, when the
pixel values in the orthogonal coordinate are assigned to the new pixels in
the polar coordinate, distortion may happen since the images are constructed
by discrete pixels. As also shown in Figure 3, if using the conventional polar
coordinate transformation, rotations of the raw images may not be transformed
into translations of the new images perfectly. Thus, in this section, we
propose the APCT to solve this problem. To help clarification, an overview of
the pre-process phase is shown in Figure 4, while the improvements are
summarized as the following three aspects.

Figure 4: An flow chart of the pre-process phase before feeding the network,
including adaptive polar coordinate transformation, and mirroring.

(1) The conventional polar coordinate transformation uses a fixed polar axis.
In that case, as the raw images rotate, there are horizontal translations in
the transformed images. Different from the conventional polar coordinate
transformation, the proposed APCT uses a polar axis that is invariant under
rotation instead of a fixed one. In this approach, The positions of pixels
with the maximum and minimum flux values in the images are selected as the
brightest and darkest points, respectively. When there is more than one pixel
with the minimum/maximum fluxes, we choose the ones with the smallest distance
to the image centers. The axis from the brightest point to the darkest point
is taken as the polar axis of the polar coordinate system making the polar
axis of the processed images rotationally invariant, as shown in panel a) of
Figure 4.

(2) For images with smaller sizes, such as $28\times 28$, the polar coordinate
transformation will lead to distortions, as shown in Figure 3. We find that
the distortion will be reduced if the images are enlarged. Therefore, to
reduce the distortion caused by the polar coordinate transformation, the raw
images are resized from $28\times 28$ to a larger size, say $56\times 56$,
before the APCT. Once the polar axis is chosen, as shown in panel a) of Figure
4, the axis is rotated counterclockwise at a unit of $0.05$ rad each time. For
each discreet rotation, the axis passes through many pixels of the raw images.
By stacking the pixels along this rotating axis while rotating, one obtains a
new image with a size of $28\times 125$ with $125$ equaling $2\pi/0.05$
rounded, as shown in panels b) and c) of Figure 4. $28$ here is the radius
equaling half of the width or height of the images after the aforementioned
resizing. Pixels along the rotating axis within the coverage of images are
remained, while those outside the coverage or with missing fluxes are set to
be $0$. In the transformation, raw pixels will be re-sampled yielding new
images with larger sizes.

(3) To highlight morphological features, images are mirrored, resulting in
images with a size of $56\times 125$ before feeding to the algorithms, as
shown in panel d) of Figure 4.

A comparison between the conventional polar coordinate transformation and the
APCT is given in Figure 5. It shows that the APCT is almost rotationally
invariant. For example, a simple statistic shows that, for the majority of the
images after the APCT, the mean pixel-value differences before and after the
rotation are smaller than $1$, which is small enough and can be ignored.

Figure 5: A comparison between the conventional and the adaptive polar
coordinate transformation. Our method (i.e., APCT) keeps the resulting images
almost invariant regardless of how the raw images are rotated.

###  3.2 Noise Reduction by Convolutional Autoencoder

The CNNs are sensitive to noises (see Liu et al. 2020; Nazaré et al. 2017),
therefore, the distribution of image SNRs in the training set also affects the
performance of the SML algorithms. For example, if the training set has an
uneven distribution of the SNRs, say most of the samples in the training set
have high SNRs, the algorithm might fail on the test set consisting of samples
with low SNRs. It is because in images with low SNRs, the noises will break
features that are learned by the neural networks leading to
misclassifications. As shown in the left panel of Figure 2, the distribution
of image SNRs of the UML-dataset is not uniform, thus additional procedure in
the image pre-process or the training algorithms, such as enhancing the image
quality of low-SNR images or assigning more weights to low-SNR images in the
training, is required. As an effective implementation method of the former
procedure (i.e., enhancing the poor quality of low-SNR images), noise
reduction is known to be a useful method to overcome the problem arising from
the uneven distribution of SNR (see Nazaré et al. 2017). In this work, we
adopt the CAE method to reduce the noises (Du et al., 2017).

In this approach, the images are encoded by the convolutional and subsampling
layers and decoded by the deconvolutional and upsampling layers generating the
reconstructed images. The parameters of the CAE are trained to minimize the
mean square error of pixels between the input and reconstructed images. We
show some examples of comparisons between the input and reconstructed images
in Figure 6. The reconstructed images not only maintain the main morphological
features but also remove the redundant pixels, and thus reduce the noises.

Figure 6: Comparisons between the input (left) and reconstructed (right)
images in the noise reduction by using the CAE. The reconstructed images not
only maintain the main morphological features but also remove the redundant
pixels, and thus reduce the noises.

The pre-processing strategies of APCT and noise reduction make the SML
algorithms not affected by the distributions of PAs and SNRs of galaxies in
the training set. In other words, by applying the proposed pre-process
strategies, we reduce the dependence of the training set on the galaxy PAs and
image SNRs.

##  4 The SML Models and the Experiment Settings

In order to complete the entire task of automatic morphological classification
of galaxies and, at the same time, give the morphological types for the UML
remaining dataset, we train three widely used SML algorithms on the UML-
dataset. In this section, we give a brief review of the three SML methods and
the experiment settings.

###  4.1 A Brief Review of three SML Models

In this work, we test three SML models, namely the GoogLeNet (see Szegedy et
al. 2015), the DenseNet121 (see Huang et al. 2017), and the attention56
network (see Wang et al. 2017). The one with the best performance on the
validation set will be selected as our fiducial model. Figure 7 gives an
overview of the three neural networks. The brief introductions are described
below.

Figure 7: An overview of the three SML networks.

The GoogLeNet is a deep learning neural network proposed by Christian Szegedy
in 2014 (see Szegedy et al. 2015). The GoogLeNet uses $9$ inception modules
stacked one over the other. In the inception module, convolutions with kernel
sizes of $1\times 1$, $3\times 3$, and $5\times 5$ and max pooling with a
kernel size of $3\times 3$ are applied in a parallel way, making it cover a
bigger area of the images and, at the same time, keep a fine resolution for
small areas.

The DenseNet121 is one of the derivative versions of the densely connected
convolutional network (DenseNet) (see Huang et al. 2017). In a DenseNet, each
layer is connected to every other layer. That is, the outputs of all the
preceding layers are used as inputs of the subsequent layers. Unlike the
resnet, which uses an additive method that merges the previous layer with the
future layer, the DenseNet concatenates the outputs of the previous layers
with the future layers. The number “121” denotes the number of layers in the
neural network.

The attention56 network is one of the derivative versions of the residual
attention network (see Wang et al. 2017). The residual attention network is
built by stacking attention modules. The attention modules can generate
attention-aware features and the attention-aware features from different
modules change adaptively as layers go deeper. Inside each attention module, a
bottom-up top-down feedforward structure is used to unfold the feedforward and
feedback attention process into a single feedforward process (see Wang et al.
2017). The number “56” denotes the number of layers in the neural network.

###  4.2 Experiment Setting

One of the main aims of this work is to train the SML models on the UML-
dataset with $24,900$ galaxies and then label the UML remaining dataset with
$22,249$ galaxies that cannot be well classified by the UML method proposed by
Zhou et al. (2022) in the five CANDELS fields. In principle, all the UML-
dataset should be trained in order to make the algorithms learn all the
information contained in the training set. However, to avoid overfitting, the
UML-dataset should be split into subsamples of training and validation sets
usually with a ratio of $7:3$ or $8:2$. Here, instead of adopting a fixed
ratio, the UML-dataset is randomly split into training and validation sets
containing $22,000$ and $2,900$ galaxies, respectively, as shown in Table 1.
To ensure that there is no overfitting, we repeat the random splitting of the
UML-dataset several times to generate different combinations of the training
and validation sets and perform the training and validation on these sets
respectively. The result indeed shows that there is no overfitting in our
training.

Table 1: The numbers of galaxies in the training and validation sets.  Number of images | SPH | ETD | LTD | IRR | UNC | ALL
---|---|---|---|---|---|---
Training set | $5588$ | $3436$ | $3837$ | $8727$ | $412$ | $22000$
Validation set | $747$ | $480$ | $496$ | $1124$ | $53$ | $2900$

In the training phase of the SML algorithms, the batch size is $32$, the
learning rate for $0.0001$, and the maximum training epoch is $500$.

##  5 Results and Analysis

In this section, we show the result of the proposed rotationally invariant SML
method. The performance is mainly evaluated by the accuracy of the validation
set and the t-SNE visualization on the UML remaining dataset. We will also
demonstrate the effectiveness of the pre-process strategy of the APCT.

###  5.1 Performances of three models

In this section, we show the performances of three SML models. The
morphological labels from the UML-dataset are regarded as the real labels,
whereas the predicted labels are given by the SML methods. The overall
accuracy is calculated by $N_{\rm correct}/N_{\rm total}$ where $N_{\rm
correct}$ is the number of correctly labeled galaxies and $N_{\rm total}$ is
the total number of galaxies. The overall accuracies of the three models on
the validation sets are listed in Table 2. It shows that all three models have
high accuracy ($>90\%$), while the GoogLeNet has the highest accuracy of
$95.1\%$. Table 2 also shows that the overall accuracy of GoogLeNet on the
validation set is improved by $\sim 5.2\%$ after the noise reduction, proving
the effectiveness of noise reduction by the CAE.

Table 2: Overall accuracy of the deep learning models.  Model | Accuracy of the training set | Accuracy of the validation set |
---|---|---|---
GoogLeNet | $100.0\%$ | $95.1\%$ |
GoogLeNet (Without Noise Reduction) | $100.0\%$ | $89.9\%$ |
DenseNet121 | $100.0\%$ | $94.3\%$ |
DenseNet121 (Without Noise Reduction) | $100.0\%$ | $89.9\%$ |
Attention56 | $100.0\%$ | $93.2\%$ |
Attention56 (Without Noise Reduction) | $100.0\%$ | $89.6\%$ |

Figure 8 shows the precision and recall of the predictions. The precision is
defined by $N_{\rm predict-correct}/N_{\rm predict-total}$, where $N_{\rm
predict-total}$ is the total number of this morphological type predicted by
the SML model and the $N_{\rm predict-correct}$ is the number of correct
predictions in line with the labels from the UML-dataset. The recall is
defined by $N_{\rm predict-correct}/N_{\rm real-total}$, where $N_{\rm real-
total}$ is the total number of this morphological type from the UML-dataset.
It shows that although the DenseNet121 model has higher precision in the LTD
category, GoogLeNet performs much better in the other four categories making
it the best model. Therefore, in the following analysis, GoogLeNet is chosen
to be the representative and fiducial SML model.

Figure 8: The precision (top) and the recall (bottom) of each morphological
types in the validation set for the three SML models, i.e., Attention56
(left), DenseNet121 (middle), and GoogLeNet (right).

###  5.2 The Effectiveness of the APCT

In this section, we demonstrate the effectiveness of the APCT. Without loss of
generality, we rotate the images in the validation set at 90°, 180°, and 270°,
respectively, and calculate the overall accuracy for the GoogLeNet model.

The accuracy as a function of rotational angles for the GoogLeNet model
applied to the images with and without APCT is presented in Figure 9, which
shows that under the APCT, the overall accuracy is nearly unchanged after
rotations compared to that of the original, rotation-free validation set.
However, the overall accuracy of the models using the raw images after
rotations but without APCT decreases significantly (by about 13%). Given that
the un-rotated validation set is randomly selected from the UML-dataset, there
is little difference in the distributions of angles between the training and
validation sets. Therefore, the un-rotated validation set has a high overall
accuracy without the APCT. However, after rotation, the difference in the
angle distributions between the training and validation sets occurs. As a
result, the overall accuracy decrease obviously from over $95\%$ to about
$83\%$, suggesting that the existing SML methods have poor robustness to
rotations of images.

Figure 9: The accuracy of the GoogLeNet with and without APCT on the
validation sets as a function of rotational angles.

Moreover, Table 3 shows the overall accuracy of the original and rotated
validation sets of the three SML models. It shows that, after rotation, the
accuracy is nearly unchanged (with the largest difference of only 1.5%)
compared to that of the un-rotated validation set regardless of the SML models
considered.

In practical application, the model needs to label galaxies that have never
been met before. The distribution of angles of the new dataset might have a
large difference from that of the training set. Therefore, the SML method with
good robustness to rotations of images is preferred. Figure 9 and Table 3
demonstrate that the APCT is an effective and efficient method to improve the
robustness of the SML methods.

Table 3: The accuracy of three SML models with and without APCT on the validation sets rotated by different angles.  Model | Without rotation | 90° | 180° | 270° |
---|---|---|---|---|---
GoogLeNet | $95.1\%$ | $94.7\%$ | $94.5\%$ | $94.6\%$ |
GoogLeNet(Without APCT) | $96.7\%$ | $82.9\%$ | $83.3\%$ | $83.6\%$ |
DenseNet121 | $94.3\%$ | $93.6\%$ | $93.4\%$ | $93.9\%$ |
DenseNet121(Without APCT) | $97.2\%$ | $82.3\%$ | $82.6\%$ | $83.4\%$ |
Attention56 | $93.2\%$ | $92.0\%$ | $91.7\%$ | $92.9\%$ |
Attention56(Without APCT) | $96.0\%$ | $82.4\%$ | $76.3\%$ | $79.6\%$ |

###  5.3 The t-SNE visualization of the UML remaining dataset

Given that the intrinsic morphological types of the galaxies in the five
CANDELS fields are missing, we can not directly evaluate the performance of
the SML methods by calculating indicators such as overall accuracy. In this
section, we use the t-SNE visualization graph to evaluate the morphological
classification result of the UML remaining dataset. The t-SNE is a useful
method to map the subsamples from a high-dimensional feature space to a
2-dimensional compressed feature space. By using this method, one can check
the classification result intuitively, especially when the real labels are
missing.

The morphological types of the UML remaining dataset with $22,249$ galaxies
are predicted by our SML method. Here, to verify the effectiveness of the
morphological classifications, we randomly select $2,000$ labeled galaxies
from the dataset and give the t-SNE visualization graphs based on the raw
images. Figure 10 shows the t-SNE visualization graphs of the $2,000$ galaxies
labeled by three methods. It shows that the SML models give the labeled
galaxies with clear boundaries that prove the effectiveness of the proposed
method. From the t-SNE visualization graphs, there is no obvious evidence that
one model has an advantage over the other two models.

Figure 10: The t-SNE visualization graphs of $2,000$ randomly selected images
that are labeled by the three SML methods. There is no obvious evidence that
one model has an advantage over the two.

To further evaluate the effectiveness of the proposed rotationally invariant
SML method, we give Figure 11 that shows the t-SNE visualization graphs
between our SML methods with/without the APCT and the SML results of Huertas-
Company et al. (2015). The morphological type of Huertas-Company et al. (2015)
is determined by five parameters, $f_{\rm spheroid}$, $f_{\rm disk}$, $f_{\rm
irr}$, $f_{\rm PS}$ and $f_{\rm Unc}$. The definition is shown as follows:

  1. 1.

Spheroids (SPH): $f_{\rm spheroid}>2/3$, $f_{\rm disk}<2/3$, and $f_{\rm
irr}<0.1$ ;

  2. 2.

Early-type Disks (ETD): $f_{\rm spheroid}>2/3$, $f_{\rm disk}>2/3$, and
$f_{\rm irr}<0.1$ ;

  3. 3.

Late-type Disks (LTD): $f_{\rm spheroid}<2/3$, $f_{\rm disk}>2/3$, and $f_{\rm
irr}<0.1$;

  4. 4.

Irregulars (IRR): $f_{\rm spheroid}<2/3$ and $f_{\rm irr}>0.1$.

  5. 5.

Unclassifiable (UNC): the remaining sources.

Galaxies can be matched by the object ID from the 3D-HST catalogs of Skelton
et al. (2014).

Figure 11: The t-SNE visualization graphs of $2,000$ randomly selected images
that are labeled by different results. Image a) is the results of the
GoogLeNet model with APCT; Image b) is the results of the GoogLeNet model
without APCT; Image c) is the results of Huertas-Company et al. (2015). It
shows that both SML models give the labeled galaxies with clear boundaries in
the t-SNE visualization graphs, proving the effectiveness of the proposed
method.

It shows that the SML models trained on the UML-dataset give the labeled
galaxies with clear boundaries in the t-SNE visualization graphs. Among
$22,249$ galaxies in the UML remaining dataset, $17,793$ of them ($\sim 80\%$)
are labeled consistently by the GoogLeNet with and without APCT. Like the
result shown in Figure 10 where the differences between the three models are
not obvious, in this t-SNE visualization graph (Figure 11) the difference
between the classification result with and without APCT is also not obvious.
One plausible reason for this situation is that the t-SNE graph is not a
quantitative tool and thus not good at distinguishing small differences in
accuracy, like difference $\lesssim 10\%$ (e.g., Figure 9).

Moreover, in Figure 12 we show some galaxies selected from the UML remaining
dataset that are correctly labeled by the rotationally invariant SML model
with APCT but incorrectly labeled by the same model without APCT. These
galaxies are firstly randomly selected from the collections of $4,456$
galaxies that are inconsistently labeled by the GoogLeNet with and without
APCT and then verified by visual inspection. It shows that the proposed
rotationally invariant SML model with APCT has better robustness to
morphological types such as LTD and SPH.

Figure 12: Examples of galaxies that are correctly labeled by the rotationally
invariant SML model with APCT but incorrectly labeled by the same model
without APCT. These galaxies are firstly randomly selected from galaxies with
disputed labels by the SML models with and without APCT and then verified by
visual inspection.

###  5.4 Comparisons with galaxy properties

Similar to our previous work of Zhou et al. (2022), we investigate the
connections of massive galaxies ($M_{*}>10^{10}M_{\odot}$) between our
morphological types and other galaxy properties in Figure 13. The SPH, ETD,
LTD, and IRR categories are represented by red, green, blue, and cyan colors,
respectively. The upper left panel summarizes the distribution of galaxies in
rest-frame $U-V$ v.s. $V-J$ color space. The wedged region defined by Williams
et al. (2009) represents the region dominated by quiescent galaxies and the
rest of the region represents the region where star-forming galaxies reside.
The combination of the Gini coefficient and $M_{20}$ shown in the upper right
panel is useful to demonstrate the disturbance and bulge strength of galaxies
(Lotz et al., 2004; Sazonova et al., 2020). The Gini coefficient can quantify
the uniformity of light distribution. The higher Gini means that fluxes are
more concentrated in the minority of pixels. The $M_{20}$ is the second moment
of the distribution of the brightest 20% of galaxy light, tracing the
substructures in a galaxy. The bottom panels are the distribution of the
Sérsic indices $n$ and effective radii $r_{e}$, respectively. The detailed
definitions of these parameters have been introduced in our previous work of
Zhou et al. (2022).

Figure 13: Relationships between morphological types and other galaxy
properties for massive galaxies in the UML remaining dataset. The upper panels
summarize the distribution of galaxies in rest-frame $U-V$ v.s. $V-J$ color
space and in the $G-M_{20}$ space. The contour levels indicate the 20%, 50%,
and 80% of the corresponding subclass from inner to outskirts. The data points
are 100 galaxies randomly selected from each subclass, where the total numbers
are given in the corner. The bottom panels are the distribution of $n$ and
$r_{e}$, with the median values represented as the upper bricks. The SPH, ETD,
LTD, and IRR categories are represented by red, blue, green, and cyan colors,
respectively.

In general, the galaxy properties agree well with the expected sequence of our
morphological types from IRR to SPH. Following the sequence in Figure 13,
Panel a) shows that galaxies move from the star-forming region to the
quiescent region; Panel b) illustrates galaxies changing from more disturbed
to more concentrated (high Gini coefficient for SPH category); Panel c) shows
that galaxies tend to be more bulge dominated; Panel d) implies that galaxies
become smaller in size. In Zhou et al. (2022) we have demonstrated that the
majority of the UNC sources have very low SNRs (e.g., images in the bottom row
of the left panel of Figure 1). For this reason, we do not carry out a similar
analysis for these UNC sources.

##  6 Conclusions and outlooks

The main aim of this series of works is to provide an automatic morphological
classification method for galaxies. To accomplish this goal, we implement the
following studies.

(1) In Zhou et al. (2022), a UML method was proposed to build a well-
classified UML-dataset. In that approach, the CAE is used to compress the
dimension of raw image data and, at the same time, extract key morphological
features. The bagging-based multi-clustering method, a voting method, clusters
galaxies with analogous characteristics into one group. By applying this UML
method to galaxies in the five CANDELS fields, we obtain a well-classified
UML-dataset consisting of $24,900$ galaxies that are consistently voted by
different clustering algorithms at the cost of eliminating $22,249$ disputed
galaxies. The UML-dataset is generated without using any pre-labeled galaxies.

(2) In this work, we develop a rotationally invariant SML method as
supplementary. In this approach, an APCT is proposed to improve the robustness
of the SML method to rotations of images. Then, the SML algorithms are trained
on the UML-dataset giving a method that identifies the morphological types of
new galaxies with high confidence. By applying the rotationally invariant SML
method on galaxies in the five CANDELS fields, we give the missing labels for
the remaining $22,249$ disputed galaxies. The result of the proposed method in
the five CANDELS fields, including the t-SNE visualization graphs showing our
morphological classification result and that of Huertas-Company et al. (2015),
the comparison with galaxy properties showing the agreement between the galaxy
properties and the sequence of our morphological types, proves that the
combination of the UML method proposed in the previous work (Zhou et al.,
2022) and the rotationally invariant SML method proposed in the present work
can automatically give the morphological classification of galaxies.

The framework of automatic classification of galaxy morphology developed in
this series of works will be iterated and updated continuously (e.g., Dai et
al., in preparation), and could be used in future deep field surveys that
produce enormous amounts of photometric data, including surveys scheduled by
the forthcoming Chinese Space Station Telescope.

This work is based on observations taken by the 3D-HST Treasury Program (GO
12177 and 12328) with the NASA/ ESA HST, which is operated by the Association
of Universities for Research in Astronomy, Inc., under NASA contract
NAS526555. This work has made use of the Rainbow Cosmological Surveys
Database, which is operated by the Centro de Astrobiología (CAB/INTA),
partnered with the University of California Observatories at Santa Cruz
(UCO/Lick,UCSC). This work is supported by the Strategic Priority Research
Program of Chinese Academy of Sciences (No. XDB 41000000), the National Key
R&D Program of China (2017YFA0402600), and the China Manned Space Project with
No. CMS-CSST-2021-A07. This work is also supported by the National Natural
Science Foundation of China (NSFC; Nos. 11973038, 62106033, 11673004). C.C.Z.
acknowledges the support from Yunnan Youth Basic Research Projects
(202001AU070020). Y.Z.G. acknowledges the support from China Postdoctoral
Science Foundation (2020M681281) and Shanghai Post-doctoral Excellence Program
(2020218). Z.S.L. acknowledges the support from China Postdoctoral Science
Foundation (2021M700137).

## References

  * Abraham et al. (2018) Abraham, S., Aniyan, A. K., Kembhavi, A. K., Philip, N. S., & Vaghmare, K. 2018, MNRAS, 477, 894, doi: 10.1093/mnras/sty627
  * Baldry et al. (2004) Baldry, I. K., Glazebrook, K., Brinkmann, J., et al. 2004, ApJ, 600, 681, doi: 10.1086/380092
  * Barchi et al. (2020) Barchi, P. H., de Carvalho, R. R., Rosa, R. R., et al. 2020, Astronomy and Computing, 30, 100334, doi: 10.1016/j.ascom.2019.100334
  * Cabrera-Vives et al. (2017) Cabrera-Vives, G., Reyes, I., Förster, F., Estévez, P. A., & Maureira, J.-C. 2017, The Astrophysical Journal, 836, 97
  * Chen et al. (2018) Chen, Y., Lyu, Z. X., Kang, X., & Wang, Z. J. 2018, in 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), IEEE, 2111–2115
  * Cheng et al. (2018) Cheng, G., Han, J., Zhou, P., & Xu, D. 2018, IEEE Transactions on Image Processing, 28, 265
  * Cheng et al. (2016) Cheng, G., Zhou, P., & Han, J. 2016, IEEE Transactions on Geoscience and Remote Sensing, 54, 7405
  * Cheng et al. (2021a) Cheng, T.-Y., Huertas-Company, M., Conselice, C. J., et al. 2021a, MNRAS, 503, 4446, doi: 10.1093/mnras/stab734
  * Cheng et al. (2020a) Cheng, T.-Y., Li, N., Conselice, C. J., et al. 2020a, MNRAS, 494, 3750, doi: 10.1093/mnras/staa1015
  * Cheng et al. (2020b) Cheng, T.-Y., Conselice, C. J., Aragón-Salamanca, A., et al. 2020b, MNRAS, 493, 4209, doi: 10.1093/mnras/staa501
  * Cheng et al. (2021b) —. 2021b, MNRAS, 507, 4425, doi: 10.1093/mnras/stab2142
  * Conselice (2014) Conselice, C. J. 2014, ARA&A, 52, 291, doi: 10.1146/annurev-astro-081913-040037
  * de Vaucouleurs (1959) de Vaucouleurs, G. 1959, Handbuch der Physik, 53, 275, doi: 10.1007/978-3-642-45932-0_7
  * Dieleman et al. (2015) Dieleman, S., Willett, K. W., & Dambre, J. 2015, MNRAS, 450, 1441, doi: 10.1093/mnras/stv632
  * Domínguez Sánchez et al. (2018) Domínguez Sánchez, H., Huertas-Company, M., Bernardi, M., Tuccillo, D., & Fischer, J. L. 2018, MNRAS, 476, 3661, doi: 10.1093/mnras/sty338
  * Domínguez Sánchez et al. (2019) Domínguez Sánchez, H., Huertas-Company, M., Bernardi, M., et al. 2019, MNRAS, 484, 93, doi: 10.1093/mnras/sty3497
  * Dressler (1980) Dressler, A. 1980, ApJ, 236, 351, doi: 10.1086/157753
  * Du et al. (2017) Du, B., Xiong, W., Wu, J., et al. 2017, IEEE Transactions on Cybernetics, 47, 1017, doi: 10.1109/TCYB.2016.2536638
  * Huang et al. (2017) Huang, G., Liu, Z., Van Der Maaten, L., & Weinberger, K. Q. 2017, in Proceedings of the IEEE conference on computer vision and pattern recognition, 4700–4708
  * Hubble (1926) Hubble, E. P. 1926, ApJ, 64, 321, doi: 10.1086/143018
  * Huertas-Company et al. (2008) Huertas-Company, M., Rouan, D., Tasca, L., Soucail, G., & Le Fèvre, O. 2008, A&A, 478, 971, doi: 10.1051/0004-6361:20078625
  * Huertas-Company et al. (2015) Huertas-Company, M., Gravet, R., Cabrera-Vives, G., et al. 2015, ApJS, 221, 8, doi: 10.1088/0067-0049/221/1/8
  * Kauffmann et al. (2003) Kauffmann, G., Heckman, T. M., White, S. D. M., et al. 2003, MNRAS, 341, 54, doi: 10.1046/j.1365-8711.2003.06292.x
  * Li et al. (2020) Li, R., Napolitano, N. R., Tortora, C., et al. 2020, ApJ, 899, 30, doi: 10.3847/1538-4357/ab9dfa
  * Lianou et al. (2019) Lianou, S., Barmby, P., Mosenkov, A. A., Lehnert, M., & Karczewski, O. 2019, A&A, 631, A38, doi: 10.1051/0004-6361/201834553
  * Lintott et al. (2011) Lintott, C., Schawinski, K., Bamford, S., et al. 2011, MNRAS, 410, 166, doi: 10.1111/j.1365-2966.2010.17432.x
  * Liu et al. (2019) Liu, R., Zhang, Y., Zheng, Y., et al. 2019, Cardiovascular engineering and technology, 10, 590, doi: 10.1007/s13239-019-00425-2
  * Liu et al. (2020) Liu, Y., Tu, H.-L., Zhou, C.-C., Liua, Y., & Zhang, F.-L. 2020, arXiv preprint arXiv:2005.11679
  * Lotz et al. (2004) Lotz, J. M., Primack, J., & Madau, P. 2004, AJ, 128, 163, doi: 10.1086/421849
  * Masci et al. (2011) Masci, J., Meier, U., Cireşan, D., & Schmidhuber, J. 2011, in International conference on artificial neural networks, Springer, 52–59
  * Momcheva et al. (2016) Momcheva, I. G., Brammer, G. B., van Dokkum, P. G., et al. 2016, ApJS, 225, 27, doi: 10.3847/0067-0049/225/2/27
  * Nazaré et al. (2017) Nazaré, T. S., Costa, G. B., Contato, W. A., & Ponti, M. 2017, in Iberoamerican Congress on Pattern Recognition, Springer, 416–424
  * Reyes et al. (2018) Reyes, E., Estévez, P. A., Reyes, I., et al. 2018, in 2018 International Joint Conference on Neural Networks (IJCNN), IEEE, 1–8
  * Sazonova et al. (2020) Sazonova, E., Alatalo, K., Lotz, J., et al. 2020, ApJ, 899, 85, doi: 10.3847/1538-4357/aba42f
  * Scarlata et al. (2007) Scarlata, C., Carollo, C. M., Lilly, S., et al. 2007, ApJS, 172, 406, doi: 10.1086/516582
  * Sérsic (1963) Sérsic, J. L. 1963, Boletin de la Asociacion Argentina de Astronomia La Plata Argentina, 6, 41
  * Simmons et al. (2017) Simmons, B. D., Lintott, C., Willett, K. W., et al. 2017, MNRAS, 464, 4420, doi: 10.1093/mnras/stw2587
  * Skelton et al. (2014) Skelton, R. E., Whitaker, K. E., Momcheva, I. G., et al. 2014, ApJS, 214, 24, doi: 10.1088/0067-0049/214/2/24
  * Szegedy et al. (2015) Szegedy, C., Liu, W., Jia, Y., et al. 2015, in 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 1–9, doi: 10.1109/CVPR.2015.7298594
  * van den Bergh (1960) van den Bergh, S. 1960, ApJ, 131, 558, doi: 10.1086/146869
  * van der Maaten & Hinton (2008) van der Maaten, L., & Hinton, G. 2008, Journal of Machine Learning Research, 9, 2579.  http://jmlr.org/papers/v9/vandermaaten08a.html
  * van der Wel et al. (2014) van der Wel, A., Franx, M., van Dokkum, P. G., et al. 2014, ApJ, 788, 28, doi: 10.1088/0004-637X/788/1/28
  * Vega-Ferrero et al. (2021) Vega-Ferrero, J., Domínguez Sánchez, H., Bernardi, M., et al. 2021, MNRAS, 506, 1927, doi: 10.1093/mnras/stab594
  * Walmsley et al. (2022) Walmsley, M., Lintott, C., Géron, T., et al. 2022, MNRAS, 509, 3966, doi: 10.1093/mnras/stab2093
  * Wang et al. (2017) Wang, F., Jiang, M., Qian, C., et al. 2017, in Proceedings of the IEEE conference on computer vision and pattern recognition, 3156–3164
  * Williams et al. (2009) Williams, R. J., Quadri, R. F., Franx, M., van Dokkum, P., & Labbé, I. 2009, ApJ, 691, 1879, doi: 10.1088/0004-637X/691/2/1879
  * Yao et al. (2019) Yao, X., Feng, X., Cheng, G., Han, J., & Guo, L. 2019, in IGARSS 2019-2019 IEEE International Geoscience and Remote Sensing Symposium, IEEE, 1382–1385
  * Zhou et al. (2022) Zhou, C., Gu, Y., Fang, G., & Lin, Z. 2022, AJ, 163, 86, doi: 10.3847/1538-3881/ac4245


# On the number of edges of separated multigraphs

Jacob Fox Stanford University, Stanford, CA. Supported by a Packard Fellowship
and by NSF award DMS-1855635. Email<EMAIL_ADDRESS>János Pach Rényi
Institute, Budapest and MIPT, Moscow. Supported by NKFIH grants K-176529,
KKP-133864, Austrian Science Fund Z 342-N31, Ministry of Education and Science
of the Russian Federation MegaGrant No. 075-15-2019-1926, ERC Advanced Grant
“GeoScape.” Email<EMAIL_ADDRESS>Andrew Suk Department of Mathematics,
University of California at San Diego, La Jolla, CA, 92093 USA. Supported an
NSF CAREER award, NSF award DMS-1952786, and an Alfred Sloan Fellowship.
Email<EMAIL_ADDRESS>
###### Abstract

We prove that the number of edges of a multigraph $G$ with $n$ vertices is at
most $O(n^{2}\log n)$, provided that any two edges cross at most once,
parallel edges are noncrossing, and the lens enclosed by every pair of
parallel edges in $G$ contains at least one vertex. As a consequence, we prove
the following extension of the Crossing Lemma of Ajtai, Chvátal, Newborn,
Szemerédi and Leighton, if $G$ has $e\geq 4n$ edges, in any drawing of $G$
with the above property, the number of crossings is
$\Omega\left(\frac{e^{3}}{n^{2}\log(e/n)}\right)$. This answers a question of
Kaufmann et al. and is tight up to the logarithmic factor.

##  1 Introduction

A _topological graph_ is a graph drawn in the plane such that its vertices are
represented by points, and the edges are represented by simple continuous arcs
connecting the corresponding pairs of points. In notation and terminology, we
do not distinguish between the vertices and the points representing them and
the edges and the arcs representing them. The edges are allowed to intersect,
but they cannot pass through any vertex other than their endpoints. If two
edges share an interior point, then they must properly _cross_ at that point,
i.e., one edge passes from one side of the other edge to its other side.

A multigraph is a graph in which two vertices can be joined by several edges.
Two edges that join the same pair of vertices are called parallel.

According to the crossing lemma of Ajtai, Chvátal, Newborn, Szemerédi [1] and
Leighton [6], every topological graph $G$ with $n$ vertices and $e>4n$ edges
has at least $c\frac{e^{3}}{n^{2}}$ edge crossings, where $c>0$ is an absolute
constant. In notation, we have

$\mbox{\rm cr}(G)\geq c\cdot\frac{e^{3}}{n^{2}}.$ (1)

In a seminal paper which was an important step towards the solution of Erdős’s
famous problem on distinct distances [4], Székely [14] generalized the
crossing lemma to multigraphs: for every topological multigraph $G$ with $n$
vertices and $e>4n$ edges, in which the multiplicity of every edge is at most
$m$, we have

$\mbox{\rm cr}(G)\geq c\frac{e^{3}}{mn^{2}}.$ (2)

As the maximum multiplicity $m$ increases, (2) gets weaker. However, as was
shown in [11] and [5], under certain special conditions on the multigraphs,
the inequality (1) remains true, independently of $m$. Some related results
were established in [12]. In all of these papers, one of the key elements of
the argument was to find an analogue of Euler’s theorem for the corresponding
classes of “nearly planar” multigraphs.

Throughout this paper, we consider only single-crossing topological
multigraphs, i.e., we assume that any two edges cross at most once. Hence, two
edges that share an endpoint may also have a common interior point. Two edges
are said to be _independent_ if they do not share an endpoint, and they are
called _disjoint_ if they are independent and do not cross.

######  Definition 1.1.

A multigraph $G$ is called separated if no two parallel edges of $G$ cross,
and the “lens” enclosed by them has at least one vertex in its interior.

It was conjectured in [5] that any separated single-crossing topological
multigraph with $n$ vertices has at most $O(n^{2})$ edges. The aim of this
note is to verify this conjecture apart from a logarithmic factor.

######  Theorem 1.2.

The number of edges of a separated single-crossing topological multigraph $G$
on $n$ vertices satisfies $|E(G)|\leq 64n^{2}\log n.$

Note that in a separated multigraph, any pair of vertices can be connected by
at most $n-1$ edges. This immediately implies the bound $|E(G)|\leq{n\choose
2}(n-1)=O(n^{3})$.

If we plug in Theorem 1.2 into the machinery of [11] and [5], a routine
calculation gives the following.

######  Corollary 1.3.

Every separated single-crossing topological multigraph on $n$ vertices and
$e\geq 4n$ edges has at least $10^{-25}\frac{e^{3}}{n^{2}\log(e/n)}$
crossings.

For simplicity, we will assume that a multigraph does not have _loops_. It is
easy to see that Theorem 1 also holds for topological multigraphs with loops,
assuming that each loop contains a vertex.

Theorem 1.2 does not remain true if we replace the assumption that $G$ is
single-crossing by the weaker one that any two edges cross at most twice. To
see this, let the vertices of $G$ lie on the $x$-axis: set
$V(G)=\\{1,2,\ldots,n\\}$. Let each edge consist of a semicircle in the upper
half-plane and a semicircle below it that meet at a point of the $x$-axis.
More precisely, for any pair of integers $i,j\in V(G)$ with $i<j$, and for any
$k$ with $i\leq k<j,$ pick a distinct point $p_{ikj}$ in the open interval
$(k,k+1)$. Let $\gamma_{ikj}$ be the union of two semicircles centered at the
$x$-axis: an upper semicircle connecting $i$ to $p_{ikj}$ and a lower one
connecting $p_{ikj}$ to $j$. Let $E(G)$ consist of all arcs $\gamma_{ikj}$
over all triples $i\leq k<j.$ Observe that any two edges of $G$ cross at most
twice: once above the $x$-axis and once below it. No two parallel edges,
$\gamma_{ihj}$ and $\gamma_{ikj}$ with $h<k$, cross each other, and the region
enclosed by them contains the vertex $k\in V(G)$. Therefore, $G$ is a
separated topological multigraph with $\sum_{i,j(i<j)}(j-i)=\Omega(n^{3})$.

The proof of Theorem 1.2 is presented in the next section, and the proof of
Corollary 1.3 can be found in the subsequent section.

All logarithms used in the sequel are of base 2. We omit all floor and ceiling
signs wherever they are not crucially important.

##  2 Proof of Theorem 1.2

We will need the following simple lemma.

######  Lemma 2.1.

Let $G$ be a single-crossing topological graph on $n$ vertices with no
parallel edges, in which every pair of independent edges cross. Then we have
$|E(G)|\leq 4n$.

###### Proof.

Let $V(G)=A\cup B$ be a bipartition of the vertex set such that at least half
of the edges of $G$ run between $A$ and $B$. Denote the corresponding
bipartite graph by $G(A,B)$. Any pair of independent edges of $G(A,B)$ cross
once, that is, an odd number of times. Assume without loss of generality that
$A$ and $B$ are separated by a horizontal line. By “flipping” one of the half-
planes bounded by this line from left to right, we obtain a drawing of
$G(A,B)$, in which any pair of independent edges cross an even number of
times. According to the Hanani-Tutte theorem [15, 13], this implies that
$G(A,B)$ is a planar graph. Any bipartite planar graph on $n\geq 3$ vertices
has at most $2n-4$ edges. Therefore, $|E(G)|\leq 2|E(G(A,B))|\leq 4n-8.$ ∎

###### Proof of Theorem 1.2.

Let $G=(V,E)$ be a separated single-crossing topological multigraph on $n$
vertices. If two vertices, $u$ and $v$, are joined by $j>1$ parallel edges,
then they cut the plane into $j$ pieces, one of which is unbounded. The
bounded pieces are called lenses. Each lens is bounded by two adjacent edges
joining a pair of vertices. Let $L$ denote the set of lenses determined by
$G$.

If $|L|\leq{|E(G)|\over 2}$, then keeping only one edge between every pair of
adjacent vertices, we obtain a simple graph $G^{\prime}$ whose number of edges
satisfies

${|E(G)|\over 2}\leq|E(G^{\prime})|\leq{n\choose 2}.$

This implies that $|E(G)|<n^{2},$ and we are done.

From now on, we can and will assume that

$|L|\geq{|E(G)|\over 2}.$ (3)

For any lens $\ell\in L$, let $|\ell|$ denote the number of vertices in the
interior of $\ell$. For $t=\log n$, we partition $L$ into $t$ parts,
$L_{1}\cup L_{2}\cup\cdots\cup L_{t}$, where $\ell\in L_{i}$ if and only of
$2^{i-1}\leq|\ell|<2^{i}$. By the pigeonhole principle, there is an integer
$k,1\leq k\leq t,$ such that

$|L_{k}|\geq{|L|\over\log n}.$ (4)

Fix an integer $k$ with the above property, and let $d_{k}(v)$ denote the
number of lenses in $L_{k}$ that contain vertex $v$ in its interior. Then we
have

$\sum\limits_{v\in V}d_{k}(v)=\sum\limits_{\ell\in
L_{k}}|\ell|\geq|L_{k}|2^{k-1}.$

Hence, there is a vertex $v\in V$ that lies in the interior of at least
$|L_{k}|{2^{k-1}\over n}$ lenses from $L_{k}$. Assume without loss of
generality that $v$ is located at the origin $o$, and let $L^{o}$ denote the
set of lenses in $L_{k}$ which contain the origin. Hence, we have

$|L^{o}|\geq|L_{k}|\cdot{2^{k-1}\over n}.$

Combining this with (3) and (4), we obtain

$|L^{o}|\geq\frac{|E(G)|}{n\log n}\cdot 2^{k-2}.$ (5)

Let $G^{o}$ denote the subgraph of $G$ consisting of all vertices and the
edges that bound a lens in $L^{o}$. Any two vertices of $G^{o}$ are connected
by 0 or 2 edges of $G^{o}$.

Now we use the idea of the probabilistic proof of the crossing lemma; see [8].
Let $W$ be a random subset of $V$ in which each vertex is picked independently
with probability $p=2^{-k}$. Let $G^{o}[W]$ be the subgraph of $G^{o}$ induced
by $W$. Let $L^{o}(W)$ denote the set of empty lenses in $G^{o}[W]$ (that is,
the set of lenses with empty interiors). For the expected values of $|W|$ and
$|L^{o}(W)|$, we have

$\mathbb{E}[|W|]=pn$

and

$\mathbb{E}[|L^{o}(W)|]\geq p^{2}(1-p)^{2^{k}}|L^{o}|.$

By linearity of expectation, there is a subset $W^{\prime}$ of $V$ such that

$|L^{o}(W^{\prime})|-4|W^{\prime}|\geq\mathbb{E}[|L^{o}(W)|]-4\mathbb{E}[|W|]\geq
p^{2}(1-p)^{2^{k}}|L^{o}|-4pn.$ (6)

For each lens in $\ell\in L^{o}(W^{\prime})$, we arbitrarily pick one of the
two edges enclosing $\ell$, and denote the resulting simple topological graph
by $G^{\prime}$. We now make the following observation.

######  Lemma 2.2.

Any two independent edges of $G^{\prime}$ cross each other.

###### Proof.

Suppose, for contradiction, that $G^{\prime}$ has two independent edges, $e$
and $e^{\prime}$, which do not cross. Let $\ell$ and $\ell^{\prime}$ be the
corresponding empty lenses in $G^{o}[W^{\prime}]$. Since the interiors of
$\ell$ and $\ell^{\prime}$ are empty, neither of them can contain an endpoint
of the other. Both of these lenses contain the origin $o$, which implies that
they cannot be disjoint. Therefore, both sides of $\ell$ must cross both sides
of $\ell^{\prime}$, contradicting the choice of $e$ and $e^{\prime}$. Here, we
used the assumption that $G$ and, hence, $G^{\prime}$ are single-crossing. ∎

In view of Lemma 2.2, we can apply Lemma 2.1 to $G^{\prime}$. We obtain
$|E(G^{\prime})|=|L^{o}(W^{\prime})|\leq 4|W^{\prime}|$ and hence by (6) we
have $p^{2}(1-p)^{2^{k}}|L^{o}|\leq 4pn$. It follows that

$|L^{o}|\leq 4p^{-1}(1-p)^{-2^{k}}n.$

Substituting $p=2^{-k}$, we get

$|L^{o}|\leq 16\cdot 2^{k}n.$

Comparing this with (5), we conclude that

$|E(G)|\leq 64n^{2}\log n.$

This completes the proof of Theorem 1.2. ∎

##  3 Proof of Corollary 1.3

The _bisection width_ of a graph is defined as the minimum number of edges
whose deletion separates the graph into parts each containing at most a
fraction $4/5$ of the vertices. For our purposes, the constant $4/5$ is not so
important, and any positive constant less than $1$ will do. A bound on the
bisection width of a graph in terms of the crossing number and the degree
sequence of the graph was established by Pach, Shahrokhi, and Szegedy [9]
through an application of the Lipton-Tarjan separator theorem [7]. It was
applied to obtain a new proof and various generalizations of the crossing
lemma [10], [3], [5].

The proof of Corollary 1.3 follows the same general strategy as the new proof
of the crossing lemma in [10], although, importantly, we need to work with a
topological variant of the bisection width, introduced in [11]. Given a
separated single-crossing topological graph $G=(V,E)$, let $b(G)$ denote the
minimum number of edges we need to delete from $G$ so that there is a vertex
partition $V=V_{1}\cup V_{2}$ such that

(i) $|V_{1}|,|V_{2}|\leq 4|V(G)|/5$,

(ii) there is no remaining edge between $V_{1}$ and $V_{2}$, and

(iii) for $i=1,2$, the subgraph $G_{i}\subset G[V_{i}]$ formed by the
remaining edges of $G[V_{i}]$ is a separated single-crossing topological
graph.

Our proof of Corollary 1.3 is based on the following statement.

######  Lemma 3.1.

Let $G$ be a separated single-crossing topological graph on $n$ vertices with
degree sequence $d_{1},\ldots,d_{n}$ and $c(G)$ crossings. Then

$b(G)\leq 22\sqrt{c(G)+\sum_{i=1}^{n}d_{i}^{2}+n}.$

$\Box$

Lemma 3.1 was proved in [11], in the special case where no two edges of $G$
incident to the same vertex cross each other. The argument in [11] goes
through to the general case without any change. In fact, it also remains valid
for other “drawing styles” (see [5], Theorem 2).

###### Proof of Corollary 1.3.

Let $G$ be a separated single-crossing topological graph on $n$ vertices with
$e$ edges, degree sequence $d_{1},\ldots,d_{n}$, and $c(G)$ crossings. Similar
to (Corollary 2.2 of [11]), we have $c(G)\geq e-3n$ through an application of
Euler’s polyhedral formula. This bound is sufficient for $e<10^{12}n$. We may
therefore assume $e\geq 10^{12}n$.

Let $\Delta:=\lceil 2e/n\rceil$. By locally splitting each vertex of $G$ whose
degree is larger than $\Delta$ into vertices of degree $\Delta$, with possibly
one additional vertex of degree less than $\Delta$, we obtain another
separated single-crossing topological graph $G^{\prime}$ with $e$ edges,
$c(G)$ crossings, and with at most $2n$ vertices of maximum degree at most
$\Delta:=\lceil 2e/n\rceil$. Denoting the number of vertices of $G^{\prime}$
by $n^{\prime}$, we have $n\leq n^{\prime}\leq 2n$.

Let $k=10^{-10}\frac{e^{2}}{n^{2}\log(e/n)}$. Note that $k\geq\Delta$, as
$e\geq 10^{12}n$.

Let $\mathcal{F}_{0}=\\{G^{\prime}\\}$. We consider a process where at step
$i=1,2,\ldots$ we create a family $\mathcal{F}_{i}$ of vertex-disjoint
subgraphs of $G^{\prime}$, each of which is a separated single-crossing
topological graph. Throughout the process, we maintain the property, true for
$i=0$, that each member $H\in\mathcal{F}_{i}$ either satisfies $c(H)\geq
ke(H)$ or has at most $(4/5)^{i}n^{\prime}$ vertices. Assume that this
property is satisfied at step $i$. At step $i+1$, we construct
$\mathcal{F}_{i+1}$ from $\mathcal{F}_{i}$, as follows. For each
$H\in\mathcal{F}_{i}$, if $c(H)\geq ke(H)$ or $H$ has at most
$(4/5)^{i+1}n^{\prime}$ vertices, then place $H$ in $\mathcal{F}_{i+1}$.
Otherwise, we have $c(H)<ke(H)$ and the number of vertices of $H$ is at least
$(4/5)^{i+1}n^{\prime}$ and at most $(4/5)^{i}n^{\prime}$. In this case, we
apply Lemma 3.1 to $H$: by deleting $b(H)$ edges from $H$, we obtain two
vertex-disjoint separated single-crossing topological subgraphs, $H_{1}$ and
$H_{2}$, each of which has at most $\frac{4}{5}v(H)$ vertices. We place
$H_{1}$ and $H_{2}$ in $\mathcal{F}_{i+1}$. Obviously, the resulting family
$\mathcal{F}_{i+1}$ has the desired property.

Next, we bound the number of edges that were deleted from the members of
$\mathcal{F}_{i}$ to obtain $\mathcal{F}_{i+1}$. For each
$H\in\mathcal{F}_{i}$ which does not belong to $\mathcal{F}_{i+1}$, we have
$c(H)<ke(H)$. It follows from Lemma 3.1 that the number of edges we deleted
from $H$ to obtain $H_{1}$ and $H_{2}$ is at most

$b(H)\leq 22\sqrt{c(H)+\Delta e(H)+v(H)}\leq 22\sqrt{ke(H)+\Delta
e(H)+v(H)}\leq 40\left(\sqrt{ke(H)}+\sqrt{v(H)}\right).$

Since each $H\in\mathcal{F}_{i}$ which does not belong to $\mathcal{F}_{i+1}$
has at least $(4/5)^{i+1}n^{\prime}$ vertices, the number of $H$ with this
property is at most $n^{\prime}/\left((4/5)^{i}n^{\prime}\right)=(5/4)^{i+1}$.
As the sum of $e(H)$ with $H\in\mathcal{F}_{i}$ is at most $e$, we obtain
$\sum_{H\in\mathcal{F}_{i}\setminus\mathcal{F}_{i+1}}\sqrt{e(H)}\leq\sqrt{(5/4)^{i+1}}\sqrt{e}$.
Similarly,
$\sum_{H\in\mathcal{F}_{i}\setminus\mathcal{F}_{i+1}}\sqrt{v(H)}\leq\sqrt{(5/4)^{i+1}}\sqrt{n^{\prime}}$.
Hence, in going from $\mathcal{F}_{i}$ to $\mathcal{F}_{i+1}$, at most
$40(5/4)^{(i+1)/2}\left(\sqrt{ke}+\sqrt{n}\right)$ edges were deleted, in
total.

We stop at the last step $i_{0}$ such that $(5/4)^{i_{0}/2}\leq
10^{-3}(e/k)^{1/2}$. In total, in getting from step $0$ to step $i_{0}$, the
number of edges we have deleted is at most

$\sum_{i=0}^{i_{0}-1}40(5/4)^{(i+1)/2}\left(\sqrt{ke}+\sqrt{n}\right)\leq
500(5/4)^{i_{0}/2}\sqrt{ke}\leq e/2.$

Hence, the members of $\mathcal{F}_{i_{0}}$ contain, in total, at least $e/2$
edges. On the other hand, each graph $H\in\mathcal{F}_{i_{0}}$ either
satisfies $c(H)\geq ke(H)$ or has at most $v:=(4/5)^{i_{0}}n^{\prime}\leq
3\cdot 10^{6}kn/e$ vertices. By Theorem 1.2, each graph $H$ of the latter type
has at most $64v^{2}\log v$ edges. In total, the number of edges in all
members $H$ in $\mathcal{F}_{i_{0}}$ of the latter type is at most
$64n^{\prime}v\log v\leq 2\cdot 10^{9}kn^{2}e^{-1}\log(n/e)=e/5$. Hence, there
are at least $e/2-e/5=3e/10$ edges of $G^{\prime}$ which are in graphs $H$ in
$\mathcal{F}_{i_{0}}$ with $c(H)\geq ke(H)$. Therefore, in these subgraphs
altogether we have at least $k(3e/10)\geq
10^{-11}\frac{e^{3}}{n^{2}\log(e/n)}$ crossings. All of them are distinct
crossings in the original graph $G$, which completes the proof. ∎

## References

  * [1] M. Ajtai, V. Chvátal, M. N. Newborn, and E. Szemerédi: Crossing-free subgraphs, in: Theory and Practice of Combinatorics, North-Holland Mathematics Studies 60, North-Holland, Amsterdam, 9–12, 1982.
  * [2] N. Alon, P. Seymour, and R. Thomas: Planar separators, SIAM J. Discrete Math. 7 (1994), no. 2, 184–193.
  * [3] D. Bokal, É. Czabarka, L. Székely, and I. Vrt’o: General lower bounds for the minor crossing number of graphs, Discrete Comput. Geom. 44 (2010), no. 2, 463–483.
  * [4] L. Guth and N. H. Katz: On the Erdős distinct distances problem in the plane, Ann. of Math. 181 (2015), no. 1, 155–190.
  * [5] M. Kaufmann, J. Pach, G. Tóth, and T. Ueckerdt: The number of crossings in multigraphs with no empty lens, J. Graph Algorithms Appl. 25 (2021), no. 1, 383–396.
  * [6] T. Leighton: Complexity Issues in VLSI, Foundations of Computing Series, MIT Press, Cambridge, 1983.
  * [7] R. J. Lipton and R. E. Tarjan, A separator theorem for planar graphs, SIAM J. Appl. Math. 36 (1979), no. 2, 177–189.
  * [8] J. Matoušek: Lectures on Discrete Geometry. Graduate Texts in Mathematics 212, Springer-Verlag, New York, 2002.
  * [9] J. Pach, F. Shahrokhi, and M. Szegedy: Applications of the crossing number, Algorithmica 16 (1996), no. 1, 111–117.
  * [10] J. Pach, J. Spencer, and G. Tóth: New bounds on crossing numbers, Discrete Comput. Geom. 24 (2000), no. 4, 623–644.
  * [11] J. Pach and G. Tóth: A crossing lemma for multigraphs, Discrete Comput. Geom. 63 (2020), no. 4, 918–933.
  * [12] J. Pach, G. Tardos, and G. Tóth: Crossings between non-homotopic edges, in: Graph Drawing and Network Visualization, Lecture Notes in Comput. Sci. 12590, Springer-Verlag, Cham, 2020, 359–371.
  * [13] M. Schaefer: Toward a theory of planarity: Hanani-Tutte and planarity variants, J. Graph Algorithms Appl. bf 17 (2013), no. 4, 367–440.
  * [14] L. A. Székely: Crossing numbers and hard Erdős problems in discrete geometry, Combin. Probab. Comput. 6 (1997), no. 3, 353–358.
  * [15] W. T. Tutte: Toward a theory of crossing numbers, J. Combinatorial Theory 8 (1970), 45–53.