# Data-driven Clustering in Ad-hoc Networks based on Community Detection

Shufan Huang  Shanghai Jiao Tong UniversityChina<EMAIL_ADDRESS>,
Yongpeng Wu  Shanghai Jiao Tong UniversityChina<EMAIL_ADDRESS>and
Siyuan Gao  Jiangxi Institute of Metrology & TestingChina<EMAIL_ADDRESS>
(2021)

###### Abstract.

High demands for industrial networks lead to increasingly large sensor
networks. However, the complexity of networks and demands for accurate data
require better stability and communication quality. Conventional clustering
methods for ad-hoc networks are based on topology and connectivity, leading to
unstable clustering results and low communication quality. In this paper, we
focus on two situations: time-evolving networks, and multi-channel ad-hoc
networks. We model ad-hoc networks as graphs and introduce community detection
methods to both situations. Particularly, in time-evolving networks, our
method utilizes the results of community detection to ensure stability. By
using similarity or human-in-the-loop measures, we construct a new weighted
graph for final clustering. In multi-channel networks, we perform allocations
from the results of multiplex community detection. Experiments on real-world
datasets show that our method outperforms baselines in both stability and
quality.

Community detection, Ad-hoc network, Graph clustering

††journalyear: 2021††copyright: acmcopyright††conference: Adjunct Proceedings
of the 2021 ACM International Joint Conference on Pervasive and Ubiquitous
Computing and Proceedings of the 2021 ACM International Symposium on Wearable
Computers; September 21–26, 2021; Virtual, USA††booktitle: Adjunct Proceedings
of the 2021 ACM International Joint Conference on Pervasive and Ubiquitous
Computing and Proceedings of the 2021 ACM International Symposium on Wearable
Computers (UbiComp-ISWC ’21 Adjunct), September 21–26, 2021, Virtual,
USA††price: 15.00††doi: 10.1145/3460418.3480412††isbn:
978-1-4503-8461-2/21/09††ccs: Computer systems organization Sensor
networks††ccs: Human-centered computing Ubiquitous and mobile computing

##  1\. Introduction

The development in the industry led to higher demand on management of energy
consumption data. The number and variety of data require a huge number of
sensors, and the connection between the sensors would be a problem to be
solved. As the number of sensors increases, the network becomes more complex.
In ad-hoc networks, clustering algorithms separate the nodes in ad-hoc
networks into multiple groups and determine the connection between nodes. They
also enable the ad-hoc networks to adjust according to changes of situation.

However, conventional clustering methods in ad-hoc networks are mainly based
on topology and connectivity, such as k-hop and dominant set-based clustering
algorithms (Yu and Chong, 2005). Although clustering algorithms are efficient,
the clustering quality cannot be guaranteed. In sensor networks, the quality
of data affect the subsequent analysis. Thus, new methods should facilitate
further analysis. Furthermore, the conventional clustering is only based on
the current status of the ad-hoc network. Results could be unstable due to the
lack of previous data. Also, in ad-hoc networks with multiple channels,
conventional methods cannot map the sensors to each channel and maximize the
quality of communication at the same time.

In this paper, we propose two methods to solve the clustering of ad-hoc
networks under two different situations by modelling the ad-hoc network as
graphs. In the first situation, behaviors of ad-hoc networks over a period of
time is recorded and time-evolving graphs are constructed. Our objective is to
make use of the historical data in the ad-hoc network to generate a stable and
reliable partition of the graph. The second situation can be depicted as a
multiplex graph, where layers in the graph denote different channels in the
ad-hoc network. By assigning labels for each node in the graph, the nodes can
be clustered and allocated to their optimal channel. Inspired by the social
property in graphs generated from ad-hoc networks, we introduce two methods
based on community detection. The first method is for the time-evolving
graphs, where time series of graphs are treated independently at each
timestamp. Then, we treat the community relationships between nodes in a
period of time as the basis for the reconstruction of the graph. We offer two
options: the first is to calculate an index based on the Jaccard Similarity as
the weight of new edges; the other is to train a classifier with a small scale
of labeled data to output the new weight of the edges. The second method is
for ad-hoc networks with multiple channels, a mapping of nodes can be
established by labeling sensors instead of nodes in the multiplex network.
With the mapping, we further find the optimal way to allocate the sensors to
channels. In summary, this paper made the following contributions:

  * •

We introduce the community structure from social network to model the
structure of the ad-hoc network.

  * •

We propose two methods based on data-driven community detection suitable for
time-evolving ad-hoc networks and multi-channel ad-hoc networks.

  * •

The experiment shows that the proposed methods outperform conventional
clustering algorithms in both stability and communication quality.

The rest of the paper is organized as follows. In Section 2, we review the
related works regarding conventional clustering methods for ad-hoc networks
and community detection methods. Section 3 introduces our key motivation and
models for two situations. In Section 4, we propose our novel methods based on
community detection. In Section 5, we introduce the experimental setup,
analyze the results of different methods and discuss the interesting findings.
Finally, we conclude remarks and future works in section 6.

##  2\. Related Works

###  2.1. Clustering Methods for Ad-hoc Networks

The existing clustering algorithms for ad-hoc networks are mostly unsupervised
algorithms based on graph data, including algorithms based on topology, multi-
hop clustering, and weighted clustering. Some clustering algorithms are
defined based on topology, such as the concept of dominating set (Yu and
Chong, 2005). Commonly used dominating sets includes Connected Dominating Set
(CDS) (Wu and Li, 1999) and Weakly Connected Dominating Set (WCDS) (Han and
Jia, 2007). These algorithms define clusters as dominating sets or dominating
set with weaker definitions. Such algorithms are easy to implement but the
efficiency is restricted since the discovery of dominating set is an NP-hard
problem. In multi-hop clustering, the clusters are generated with the
information of the neighborhood. The cluster heads are selected based on their
own IDs and the IDs of their k-hop neighbors. The nodes communicate with each
other by broadcasting their IDs and decisions of selection, an example of such
clustering methods is the k-CONID (Chen et al., 2002), it is a combination of
multi-hop clustering and identifier neighbor based clustering (Harous;, 2013).
Weighted clustering is the basis of many commonly used clustering algorithms
in ad-hoc networks, such as the Weighted Clustering Algorithm (WCA)
(Chatterjee et al., 2002). The greatest advantage of weighted clustering
algorithms is their flexibility. A weighted combination of attributes such as
node degree, node mobility, transmission range, distance to neighbors is used
to score the nodes. The cluster head is elected by broadcasting the scores
among neighbors.

###  2.2. Community Detection

Community detection is a useful tool in the analysis of large-scale networks.
All the community detection methods are based on the community structure in
the network. The community structure refers to a group of nodes in the graph
whose density is large internally, while the external connections are sparse.
Various community detection algorithms have been proposed with different
objective functions, such as modularity-based algorithms (Louvain) (Blondel et
al., 2008), information entropy-based algorithm map equation (InfoMap)
(Rosvall et al., 2009), connectivity based algorithms (GN) (Newman, 2004),
label propagation algorithms (LPA) (Raghavan et al., 2007), non-negative
matrix factorization (Wang et al., 2011), and methods based on compressed
sensing (Mahyar et al., 2015)(Wang et al., 2018). The community structure
allows the division of large-scale networks and makes the subsequent analysis
easier. For community detection in multilayer graphs, the methods can be
categorized into three types. (Huang et al., 2021) The first is flattening
methods, which collapses the information in a multilayer graph into a single
layer. These methods are commonly used in the multiplex networks, where inter-
layer edges only appears between same nodes. The second is aggregation
methods, which discovers communities in each layer, and then aggregates them
by a certain principle. Direct methods are community algorithms that optimizes
some quality-assessment criteria without flattening, such as Locally Adaptive
Random Transitions(LART) (Kuncheva and Montana, 2015), Label Propagation
Algorithm for the multilayer network (MNLPA) (Alimadadi et al., 2019),
MultiTensor (De Bacco et al., 2017) and InfoMap (Edler et al., 2017).

##  3\. Motivation and Modeling

In this section, we explain the motivation and model to solve the problem of
clustering in ad-hoc networks.

###  3.1. Motivation

Sensor network plays an increasingly important role in monitoring operation
status and data analytics. The most significant feature of ad-hoc networks is
its flexibility and adaptation to changes in the network, such as new nodes
and failure in nodes. Nonetheless, the failure and insertion of sensors are
not-so-common in some industrial applications. Therefore, the demand for ad-
hoc networks changes from robustness to stability and the quality of
communication. Conventional clustering algorithms in ad-hoc networks focus
more on the connectivity and topology of the network, and new algorithms are
needed to ensure the quality of communication. Researches have been conducted
on the _social properties_ of ad-hoc networks (Nguyen et al., 2014; Liaqat et
al., 2019; Daly and Haahr, 2007). In sensor networks, the phenomenon of social
relationships is easy to identify. For example, the sensors monitoring the
same object have a natural tendency to communicate with each other, which
reflects the social property in the network. Therefore, as a useful tool in
analysis in social networks, community detection is also applicable on ad-hoc
networks.

###  3.2. Model

In this paper, we set two different situations.

###### Situation 3.1.

The quality of communication between sensors is given for a period of time, a
method is needed to partition the sensors into smaller clusters.

###### Situation 3.2.

The quality of communication between sensors of different channels is given,
the method is required to give an allocation to maximize the quality of
communication on each channel, and minimize the number of isolated sensors.

We model the ad-hoc network by undirected graphs $G(V,E,W)$, where nodes $v\in
V$ denote sensors, edges $e\in E$ denote communications between the two
sensors, and edge weights $w\in W$ denote communication quality between the
two sensors.

In Situation 3.1, an undirected graph is created for every timestamp to
represent the time-evolving network. In Situation 3.2, each channel is viewed
as a layer of the graph. Since there are multiple channels in the second
situation, the network becomes a multilayer graph. Besides, since there is no
interlayer connection, the graph can be further simplified into a multiplex
graph, where the interlayer connection exists if and only if the two nodes
have the same index in different layers.

In these two situations, we introduce community detection methods to split the
original network into communities in which the nodes are densely connected to
each other. Given an undirected weighted graph $G(V,E,W)$, community detection
algorithms outputs a community assignment $C$, grouping $V$ to corresponding
labels signaling the community. An evaluation method for community assignment
is needed to obtain the best result. The evaluation in Situation 3.1 is
defined as an object function to compute the average modularity(Girvan and
Newman, 2002) $\bar{Q}$ in the time-evolving graphs, which is a modified
version of modularity in multilayer networks.

(1)
$\bar{Q}=\frac{1}{T}\sum^{T}_{t=1}\sum^{c_{j}}_{i=1}(e_{ii}(t)-a_{i}(t)^{2})$

where $e_{ii}$ is the fraction of the edges from one node in group $i$ to
another node in the same group $i$ in the graph at timestamp $t$, $c_{j}$ is
the number of communities at timestamp $j$. $a_{ih}$ is the expected fraction
of edges from one node in group $i$ to another one in the same group in a
randomized network at timestamp $t$. $T$ is the length of time window selected
from the time-evolving graph. Larger modularity indicates stronger community
structure.

Besides modularity, we include Bit Error Rate (BER) to evaluate the quality of
communication. With higher density in the community, the average BER
calculated with the average shortest distance in each connective component in
the graph is also reduced due to the increment in density when modularity is
optimized.

In Situation 3.2, the evaluation objective $L$ is composed of connectivity and
average BER. Connectivity is defined as the number of connected components in
a graph where the inter-community edges are removed. Connectivity is
introduced to ensure that every node can be reached by other nodes in the same
community, and no extra connected components are separated from the network
due to the allocation of channels.

(2) $L(C)=\bar{Q}+\lambda(N_{cc}-N_{community})+\gamma BER$

where $C$ is the final result of community detection, $N_{cc}$ is the number
of connected components in a graph where the inter-community edges are
removed, $N_{communities}$ is the number of communities in the final, and BER
is the average Bit Error Rate between nodes. $\lambda$ and $\gamma$ are
weights to balance the importance of the three factors.

##  4\. Methodology

In this section, we introduce two methods that can be adopted to serve as a
clustering algorithm and give a satisfying result on real-life datasets. The
first method is a combination of community detection results on multiple
timestamps. It facilitates the overall analysis of sensor networks over a
period of time. The second method is to adapt multi-layer community detection
algorithms to the clustering of networks with multiple channels.

###  4.1. Method for Situation 3.1

The first method is to solve the problem of network partition over a period of
time. The main idea is to use the statistic result as the parameter in the
network structure, and reach an overall result by applying the community
detection algorithms. It can be divided into four steps.

####  4.1.1. Graph Construction

Firstly, this method takes the communication data between sensors as input.
The input data is split by timestamp. For each timestamp, the communication
from one sensor to another is unique. The sensors can be viewed as nodes in
the networks, and the communication is treated as undirected edges between
sender and receiver. The network becomes an undirected graph with average
communication data as the weight of corresponding edges.

####  4.1.2. Community Detection

Secondly, community detection algorithms are employed to get the community
structure at the specific timestamp. The community detection algorithm can be
any algorithm that can be employed on the undirected weighted network. In this
paper, we leverage Louvain (Blondel et al., 2008), GN (Newman, 2004), and
InfoMap (Rosvall et al., 2009) to evaluate their performance.

####  4.1.3. Graph Reconstruction

Thirdly, the results generated in the second step are gathered to construct a
new graph containing the information from all timestamps. Here, two options
are provided, the first is to traverse all timestamps to calculate the number
of timestamps where two nodes are in the same community. A variation of
Jaccard Similarity is used to represent how close the relationship is between
two nodes.

(3) $J=\frac{C_{t}(A)\cap C_{t}(B)}{C_{t}(A)\cup C_{t}(B)}$

where $C_{t}$ is the set of community mapping with timestamp, and A,B are two
different nodes in the graph.

Figure 1. Method Overview

The second option is based on a simple extreme learning machine that serves as
a classifier. A binary vector over a time window is recorded for
classification. Zero means that the two nodes are in the same community at the
corresponding timestamp, while one stands for the opposite. If there is no
prior knowledge about the vector, some candidates are proposed and people can
label whether the two nodes are in the same community at the next timestamp.
In the following processing, further manual labeling is not needed, since the
result of community detection in the next timestamp will repeat this process.
In the next step, a new graph is created using the ratio or probability above.
All nodes that appeared in the period of time are included. The edges are non-
directional edges with the ratio of its node pair as weight. The new network
usually contains more edges than the network of any timestamp. The ratio
serves as the similarity between nodes, and the community detection algorithm
can be employed again to get the final result.

####  4.1.4. Node Partition

Since LPA (Raghavan et al., 2007) only requires communication in the
neighborhood, which facilitates its implementation on distributed systems,
including the ad-hoc network, it is applied on the reconstructed graph in Step
4.1.3. The final community splits the final network into smaller parts, thus
the community detection algorithm can be viewed as the clustering algorithm.

###  4.2. Method for Situation 3.2

The second method is to solve the problem of multi-channel partition. For
sensor networks with multiple channels, each sensor can communicate on
different channels. Each channel can be regarded as a layer in the network,
the communications between nodes are denoted as edges on the correspondent
layer. The sensors are represented by multiple nodes on every layer.

####  4.2.1. Community Detection

We reuse graph construction step in Section 4.1.1 but alter the community
detection step to fit the situation of multi-layer. Since there are no
interlayer connections between different nodes, the network can be viewed as
multiplex graphs, where interlayer connections can only be between nodes of
the same sensor. (Kinsley et al., 2020) Conventional partition methods based
on topology may find it hard to fit such situations, but with multi-layer
community detection algorithms, the problem can be solved. Community detection
algorithms can generate a map from the node index to its community. With this
map, every node belongs to a community, and the communities can serve as
partitions because they tend to cluster nodes with the greatest similarity in
the multiplex graph. Thus, we leverage multi-layer community detection
algorithms including LART (Kuncheva and Montana, 2015), MNLPA (Alimadadi et
al., 2019), MultiTensor (De Bacco et al., 2017), and InfoMap (Edler et al.,
2017) to output the community partition.

####  4.2.2. Channel Distribution

With multiplex communities, the next step is to select the channels suitable
for each community. A greedy algorithm is used to solve this problem. The
communities are sorted by the number of nodes, and the larger community has
the priority to choose the most suitable channel for them based on two
requirements. The first one is that if the community is set on the channel,
the increment of connected components is minimized. The second one is that the
communication quality within the community is maximized. For the first $n$
communities, where $n$ is the number of channels, they should be in different
layers. While for the latter communities, in case two requirements collide,
the first one is the priority.

##  5\. Experiment and evaluation

In this section, the result of experiment based on real-life datasets are
presented. We compare different algorithms in Methods for both Situations. For
Situation 3.1, we compare the performance of the method with different
community detection algorithms. In Situation 3.2, we compare the performance
of several multi-layer community detection algorithms.

###  5.1. Dataset and Settings

Table 1 shows the dataset used for Situation 3.1. It includes the data
collected by a sensor network in three periods of time. The dataset used for
Situation 3.2 is from communications between sensors and their quality in
three different channels during the same time period, with 62 timestamps.

(a) Variation

(b) Modularity

(c) Average BER

Figure 2. Evaluation Results for Situation 3.1 Table 1. Dataset for Situation 3.1 Name | Node | Total Edge | Timestamp
---|---|---|---
$F1$ | 62 | 267464 | 391
$F2$ | 27 | 182748 | 1773
$F3$ | 29 | 392880 | 2034

###  5.2. Experiment for Situation 3.1

####  5.2.1. Evaluation Methods

The first evaluation method is based on real-life application. From the
perspective of daily maintenance and data analysis, a stable partition of
network is needed. Thus, we define the _variation_ between the partition in
two adjacent timestamps. The distance is defined with the edit distance
between nodes. The second evaluation method is based on Modularity. Modularity
is a standard to evaluate the result of community detection methods. From the
perspective of community detection, modularity evaluates the density of the
community. We calculate the average _modularity_ in the graphs generated in
Step 4.1.2 to compare the performance of the three algorithms. The third
evaluation method is _Average BER_. We remove the inter-community connections,
and calculate the shortest distance from one node to another. Average BER is
defined as the average distance within all connected components in all graphs
in the time window without inter-community edges. The edge weight is defined
with the original BER instead of the normalized BER in Section 4.1.1.

####  5.2.2. Result Analysis

We compare methods for Situation 3.1 with conventional clustering methods for
ad-hoc networks, including WCDS (Han and Jia, 2007), WCA (Chatterjee et al.,
2002), and K-CONID (Chen et al., 2002). We examine all seven methods for
datasets in Table 5.1. Figure 2(a) shows the great advantage in our method
compared with conventional methods. In the experiment, the time window is
fixed to 2. Later research shows that the smaller the time window is, the more
stable the partition is. Therefore, the variation in our methods is the worst
case among all time windows, but they still outperform the conventional
clustering algorithms. We also test the average modularity on multiple
timestamps in Figure 2(b). Most of our methods outperforms conventional
clustering methods on modularity, since the latter ones concentrate on the
topology and the degree of nodes, while the community detection methods take
advantage of the connectivity and relationships between nodes. However, the
performance of Louvain is not as good as other community detection methods,
since it is a greedy approach. In addition, we notice that Louvain may
generate fake community by splitting one large community into several pieces.
Results for Average BER is shown in Figure 2(c). The advantage of community
detection of our methods is not obvious on this factor. GN reaches the best
result in Average BER, but its difference between InfoMap and LPA is subtle.
Although the GN algorithm performs better on the data results, we noticed an
extremely unbalanced result with a community with only three nodes. Compared
to GN, the other three community detection methods can reach more balanced
results.

Figure 3. The Effect of Time Window on Modularity

Finally, we look into the sensitivity of modularity to the size of time
window. In Figure 3, we show the effect of size of time window on the
modularity result. It is obvious that all community detection algorithms
converge before the size of window reaches 20, which indicates that in real
world application, the size of time window can be controlled without affecting
the performance of community detection.

###  5.3. Experiment for Situation 3.2

Experiment for Situation 3.2 is based on a small dataset with 62 timestamps
and 3 channels. The evaluation is based on the average modularity and the
quality of the partition result.

Table 2. Average BER for Situation 3.2 Methods | LART | MNLPA | MultiTensor | InfoMap
---|---|---|---|---
Average BER | 74.29 | 45.14 | 68.37 | 59.89

Table 2 shows Average BER result for multiplex community detection. Among the
four algorithms, the difference in Average BER is evident. However, in the
result of MultiTensor, there exist multiple isolated components.Although MNLPA
did best in Average BER, the size of communities are not balanced. It gave
only two communities and the difference in size of community is huge. In the
result of LART, there are two isolated nodes who is identified as a community,
which makes the partition meaningless and should not be accepted. To conclude,
InfoMap is the best choice for partitioning in ad-hoc networks with multiple
channels in our dataset.

(a) Multiplex Community Detection Result

(b) Final Allocation by InfoMap

Figure 4. Allocation Result for Example 5.1

###### Example 5.0.

Result Analysis from a real-world dataset in industrial IoT domain: The result
of multilayer community detection is shown in Figure 4(a). Each color
represents a community. It is obvious that the community on three different
layers is identical even if the network structure is different. The result of
the partition is shown in Figure 4(b), the nodes with colors are the result of
the final partition. The two yellow isolated nodes are on layer 3, connected
to the red community. In this example, the greedy algorithm gave the optimal
result.

##  6\. Conclusion

In this paper, we introduce community detection to solve the problem of
partition in complex ad-hoc networks. We propose two methods. One is for a
series of networks, which calculates the result of community detection to
generate similarity and further partition. The other one is for networks with
multiple channels, which takes advantage of multilayer community detection
algorithms to make a partition for sensors instead of nodes. We test our
proposals on real-life datasets and choose the most suitable algorithm. One of
the advantages of our methods is that each component can be flexibly replaced
according to specific application scenarios. This makes our framework more
robust. However, future work is required since the dataset we adopted was
relatively small. The robustness should be tested with larger and more complex
datasets. In addition, future work should be done to take full advantage of
the features of the time series. Further comparisons should also be conducted
to find the optimal algorithm apart from the ones listed in this paper.

## AcknowledgementS

The work of Y. Wu is supported in part by the National Key R&D Program of
China under Grant 2018YFB1801102 and National Science Foundation(NSFC) under
Grant 62071289.

## References

  * (1)
  * Alimadadi et al. (2019) Fatemeh Alimadadi, Ehsan Khadangi, and Alireza Bagheri. 2019\.  Community detection in facebook activity networks and presenting a new multilayer label propagation algorithm for community detection.  _International Journal of Modern Physics B_ 33, 10 (2019), 1950089\.  https://doi.org/10.1142/S0217979219500899 arXiv:https://doi.org/10.1142/S0217979219500899
  * Blondel et al. (2008) Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. 2008.  Fast unfolding of communities in large networks.  _Journal of Statistical Mechanics: Theory and Experiment_ 2008, 10 (Oct 2008), P10008.  https://doi.org/10.1088/1742-5468/2008/10/p10008
  * Chatterjee et al. (2002) Mainak Chatterjee, Sajal K. Das, and Damla Turgut. 2002\.  WCA: A Weighted Clustering Algorithm for Mobile Ad Hoc Networks.  _Cluster Computing_ 5, 2 (01 Apr 2002), 193–204.  https://doi.org/10.1023/A:1013941929408
  * Chen et al. (2002) Geng Chen, Fabian Garcia Nocetti, Julio Solano Gonzalez, and Ivan Stojmenovic. 2002.  Connectivity based k-hop clustering in wireless networks. In _Proceedings of the 35th Annual Hawaii International Conference on System Sciences_. IEEE, 2450–2459.
  * Daly and Haahr (2007) Elizabeth M. Daly and Mads Haahr. 2007.  Social Network Analysis for Routing in Disconnected Delay-Tolerant MANETs. In _Proceedings of the 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing_ (Montreal, Quebec, Canada) _(MobiHoc ’07)_. Association for Computing Machinery, New York, NY, USA, 32–40.  https://doi.org/10.1145/1288107.1288113
  * De Bacco et al. (2017) Caterina De Bacco, Eleanor A. Power, Daniel B. Larremore, and Cristopher Moore. 2017.  Community detection, link prediction, and layer interdependence in multilayer networks.  _Phys. Rev. E_ 95 (Apr 2017), 042317.  Issue 4. https://doi.org/10.1103/PhysRevE.95.042317
  * Edler et al. (2017) Daniel Edler, Ludvig Bohlin, and Martin Rosvall. 2017\.  Mapping higher-order network flows in memory and multilayer networks with Infomap.  _CoRR_ abs/1706.04792 (2017).  arXiv:1706.04792 http://arxiv.org/abs/1706.04792
  * Girvan and Newman (2002) M. Girvan and M. E. J. Newman. 2002.  Community structure in social and biological networks.  _Proceedings of the National Academy of Sciences_ 99, 12 (2002), 7821–7826.  https://doi.org/10.1073/pnas.122653799 arXiv:https://www.pnas.org/content/99/12/7821.full.pdf
  * Han and Jia (2007) Bo Han and Weijia Jia. 2007\.  Clustering wireless ad hoc networks with weakly connected dominating set.  _J. Parallel and Distrib. Comput._ 67, 6 (2007), 727–737.  https://doi.org/10.1016/j.jpdc.2007.03.001
  * Harous; (2013) Abdelhak Bentaleb;Abdelhak Boubetra;Saad Harous;. 2013.  Survey of Clustering Schemes in Mobile Ad hoc Networks.  _Communications and Network_ Vol.05No.02 (2013).  https://doi.org/10.4236/cn.2013.52B002
  * Huang et al. (2021) Xinyu Huang, Dongming Chen, Tao Ren, and Dongqi Wang. 2021\.  A survey of community detection methods in multilayer networks.  _Data Mining and Knowledge Discovery_ 35, 1 (01 Jan 2021), 1–45.  https://doi.org/10.1007/s10618-020-00716-6
  * Kinsley et al. (2020) Amy C Kinsley, Gianluigi Rossi, Matthew J Silk, and Kimberly VanderWaal. 2020.  Multilayer and Multiplex Networks: An Introduction to Their Use in Veterinary Epidemiology.  _Frontiers in veterinary science_ 7 (2020), 596.
  * Kuncheva and Montana (2015) Zhana Kuncheva and Giovanni Montana. 2015.  Community detection in multiplex networks using locally adaptive random walks.  _CoRR_ abs/1507.01890 (2015).  arXiv:1507.01890 http://arxiv.org/abs/1507.01890
  * Liaqat et al. (2019) Hannan Bin Liaqat, Amjad Ali, Junaid Qadir, Ali Kashif Bashir, Muhammad Bilal, and Fiaz Majeed. 2019\.  Socially-Aware Congestion Control in Ad-Hoc Networks: Current Status and The Way Forward.  _CoRR_ abs/1903.01617 (2019).  arXiv:1903.01617 http://arxiv.org/abs/1903.01617
  * Mahyar et al. (2015) Hamidreza Mahyar, Hamid R. Rabiee, Ali Movaghar, Elaheh Ghalebi, and Ali Nazemian. 2015.  CS-ComDet: A compressive sensing approach for inter-community detection in social networks. In _2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM)_. 89–96.  https://doi.org/10.1145/2808797.2808856
  * Newman (2004) M. E. J. Newman. 2004\.  Fast algorithm for detecting community structure in networks.  _Phys. Rev. E_ 69 (Jun 2004), 066133.  Issue 6. https://doi.org/10.1103/PhysRevE.69.066133
  * Nguyen et al. (2014) Nam P. Nguyen, Thang N. Dinh, Yilin Shen, and My T. Thai. 2014\.  Dynamic Social Community Detection and Its Applications.  _PLOS ONE_ 9, 4 (04 2014), 1–18.  https://doi.org/10.1371/journal.pone.0091431
  * Raghavan et al. (2007) Usha Nandini Raghavan, Réka Albert, and Soundar Kumara. 2007\.  Near linear time algorithm to detect community structures in large-scale networks.  _Physical Review E_ 76, 3 (Sep 2007).  https://doi.org/10.1103/physreve.76.036106
  * Rosvall et al. (2009) M. Rosvall, D. Axelsson, and C. T. Bergstrom. 2009.  The map equation.  _The European Physical Journal Special Topics_ 178, 1 (Nov 2009), 13–23.  https://doi.org/10.1140/epjst/e2010-01179-1
  * Wang et al. (2011) Fei Wang, Tao Li, Xin Wang, Shenghuo Zhu, and Chris Ding. 2011.  Community discovery using nonnegative matrix factorization.  _Data Mining and Knowledge Discovery_ 22, 3 (2011), 493–521.
  * Wang et al. (2018) Tengjiao Wang, Jingbo Tan, Wenbo Ding, Yanru Zhang, Fang Yang, Jian Song, and Zhu Han. 2018.  Intercommunity Detection Scheme for Social Internet of Things: Compressive Sensing Over Graphs Approach.  _IEEE Internet of Things Journal_ 5, 6 (2018), 4550–4557.  https://doi.org/10.1109/JIOT.2018.2837048
  * Wu and Li (1999) Jie Wu and Hailan Li. 1999\.  On calculating connected dominating set for efficient routing in ad hoc wireless networks. In _Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications_. 7–14.
  * Yu and Chong (2005) J. Y. Yu and P. H.J. Chong. 2005.  A Survey of Clustering Schemes for Mobile Ad Hoc Networks.  _Commun. Surveys Tuts._ 7, 1 (Jan. 2005), 32–48.  https://doi.org/10.1109/COMST.2005.1423333


# Unsupervised Skin Lesion Segmentation via Structural Entropy Minimization
on Multi-Scale Superpixel Graphs

Guangjie Zeng1, Hao Peng1#, Angsheng Li12, Zhiwei Liu3, Chunyang Liu4, Philip
S. Yu5, Lifang He6 #Corresponding author. 1State Key Laboratory of Software
Development Environment, Beihang University, Beijing, China;
2Zhongguancun Laboratory, Beijing, China; 3Salesforce AI Research, California,
USA;
4Didi Chuxing, Beijing, China; 5University of Illinois Chicago, Illinois, USA;
6Lehigh University, Pennsylvania, USA.
{zengguangjie, penghao<EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Skin lesion segmentation is a fundamental task in dermoscopic image analysis.
The complex features of pixels in the lesion region impede the lesion
segmentation accuracy, and existing deep learning-based methods often lack
interpretability to this problem. In this work, we propose a novel
unsupervised Skin Lesion sEgmentation framework based on structural entropy
and isolation forest outlier Detection, namely SLED. Specifically, skin
lesions are segmented by minimizing the structural entropy of a superpixel
graph constructed from the dermoscopic image. Then, we characterize the
consistency of healthy skin features and devise a novel multi-scale
segmentation mechanism by outlier detection, which enhances the segmentation
accuracy by leveraging the superpixel features from multiple scales. We
conduct experiments on four skin lesion benchmarks and compare SLED with nine
representative unsupervised segmentation methods. Experimental results
demonstrate the superiority of the proposed framework. Additionally, some case
studies are analyzed to demonstrate the effectiveness of SLED.

###### Index Terms:

skin lesion segmentation, structural entropy, medical image analysis

##  I Introduction

Skin lesion segmentation of dermoscopic images is essential for skin cancer
diagnosis [1]. Accurate segmentation of skin lesions from the surrounding skin
is challenging because skin lesions, especially melanoma ones, vary in color,
texture, shape, size, and location. Moreover, low contrast between the lesion
and healthy skin, changing illumination, and the existence of artifacts like
hairs, blood vessels, and color calibration charts make this task even harder.

A large amount of unsupervised skin lesion segmentation methods have been
proposed by researchers in recent years, including thresholding-based methods
[2], region-based methods [3], saliency-based methods [4], and clustering-
based methods [5]. They segment skin lesions without labeled datasets,
relieving medical experts from the laborious work of data labeling. However,
the fine-grained characteristics of lesion skins and healthy skins are under-
explored. Figure 1 illustrates examples of skin lesions from the PH2 dataset
[6]. On the one hand, the features like color and texture of pixels within the
lesion regions are diverse, and the lesion region can be further divided into
some unspecified number of sub-regions as shown in Figures 1(b) and 1(d).
Ignoring the diversity in a fine-grained level of those pixels leads to sub-
optimal segmentation results. On the other hand, the features of pixels in
healthy skin are generally consistent, which is one of the most important
prior information for skin lesion segmentation. Existing methods fail to fully
and effectively utilize this prior, thus being unable to accurately segment
the margin between the lesion region and healthy skin.

Figure 1:  Examples of skin lesion dermoscopic images. (a) Example lesion 1;
(b) The segmentation regions of (a), which contains two sub-regions; (c)
Example lesion 2; (d) The segmentation regions of (c), which contains four
sub-regions.

Regarding the diversity of pixel features in the lesion region, some works
directly segment the dermoscopic image into two regions, i.e., the lesion
region and healthy skin [2, 3]. They ignore the fine-grained level distinction
within the lesion region, which can lead to inaccurate segmentation of pixels
at lesion borders. Other works segment dermoscopic images into a proper number
of regions [5], and then classify regions into the lesion region and healthy
skin. Though being better at distinguishing the fine-grained features, they
require a pre-defined number of sub-regions, which lacks generalization
ability to new scenarios. Regarding the consistent healthy skin prior, RSSLS
[7] utilizes reconstruction error-based saliency to segment skin lesions. With
the detected background, i.e., the healthy skin, the whole image is
reconstructed based on the background, forming the saliency map. However, the
background detection process is complex and imprecise, inducing noise into the
segmentation procedure.

In this work, we propose a novel unsupervised Skin Lesion sEgmentation
framework via structural entropy (SE) and outlier Detection, namely SLED,
which adaptively determines the number of segments by SE minimization, and
utilizes the consistent healthy skin prior through isolation forest outlier
detection. The basic idea is that we take image segmentation as the graph
partition problem where graphs are constructed to incorporate both color
features and spatial position of pixels (or superpixels). First, we segment
the dermoscopic image into a proper number of regions by minimizing the SE of
a graph constructed from the image without the need to know the number of sub-
regions a priori, which is critical as shown in Figure 1 the number of sub-
regions of a lesion is unknown and unpredictable. The nodes of the graph are
pre-segmented superpixels and edge weights are the similarity between
superpixels. Modules in the graph partition obtained by SE minimization
represent the regions. Second, we distinguish these regions into the lesion
region and healthy skin by maximizing the between-class variance, forming a
single-scale segmentation. Third, we integrate single-scale segmentation
results from different superpixel scales into multi-scale segmentation. To
achieve this integration, we train isolation forest models using superpixels
in the healthy skin regions from single-scale segmentation results and
generate a multi-scale outlier score map by combining outlier scores from
different scales. The consistency of pixel features in healthy skin helps
isolation forest models to distinguish the lesion region from healthy skin
with higher outlier scores. Thresholding on the multi-scale score map gives
the multi-scale segmentation. Source code is available on
Github111https://github.com/SELGroup/SLED.

We comprehensively evaluate our framework with state-of-the-art unsupervised
segmentation methods and several clustering-based methods on four popular skin
lesion segmentation datasets. The results show that our framework is more
accurate in skin lesion segmentation. We also test the performance of several
outlier detection methods, finding that isolation forest best models healthy
skin in dermoscopic images. The main contributions of this paper are
summarized as follows: (1) An unsupervised skin lesion segmentation framework
guided by iteratively refined structural entropy is proposed, which adaptively
determines the number of segments in the segmentation process. (2) We
characterize the fact that features in healthy skin are consistent and devise
a novel multi-scale segmentation mechanism via isolation forest outlier
detection method. (3) Comprehensive experiments on four popular skin lesion
segmentation datasets demonstrate that our framework achieves new state-of-
the-art performance among unsupervised skin lesion segmentation methods.

##  II Related Work

###  II-A Unsupervised Skin Lesion Segmentation

Compared to supervised methods, unsupervised skin lesion segmentation methods
avoid the laborious work of lesion labeling, and have attracted great interest
in recent years. Here we briefly review existing unsupervised skin lesion
segmentation methods, including thresholding-based, region-based, saliency-
based, and clustering-based approaches.

Histogram thresholding is a simple yet effective way for skin lesion
segmentation. The thresholding histograms are constructed in different ways,
such as principle component analysis (PCA) on color bands [8] and carefully
chosen color bands [2]. More specialized thresholding techniques are also
designed for skin lesion segmentation, including weighted thresholding [9] and
adaptive thresholding [10]. Region-based methods iteratively merge image
regions until the desired lesion region is found. In [3], a simple region
merging method that merges superpixels into two regions, i.e., the lesion
region and healthy skin, is proposed. In [11], a superpixel region labeling
method via continuity classification for skin lesion segmentation is proposed.
Saliency detection-based methods treat skin lesions in dermoscopic images as
the salient object. They construct a saliency map by assigning each pixel a
saliency score, and segment the lesion region by thresholding on the saliency
map. The saliency scores are defined by reconstruction errors [7], color and
brightness prior [12], color channel volume[4] in unsupervised manners, or
lists of regional contrast and regional property in a supervised manner [13].
Clustering-based methods group pixels or superpixels into regions and then
classify them to find the skin lesion. Ahn et al.[5] proposed a spatial guided
self-supervised clustering network (SGSCN) for skin lesion and liver tumor
segmentation that iteratively determines the number of segments. Zhang et
al.[14] proposed a deep hyperspherical clustering method based on the theory
of belief functions to achieve unsupervised skin lesion segmentation. In the
single-scale segmentation step of our framework, we group superpixels by
minimizing SE and classify regions by maximizing the between-class variance.

###  II-B Unsupervised Image Segmentation

Apart from methods specifically designed for skin lesion segmentation, there
exist a large number of unsupervised image segmentation methods for more
general usage. Classical image segmentation methods group pixels into
meaningful regions. Representative methods include $K$-means and spectral
clustering [15]. More recent works utilize the power of deep learning such as
convolutional neural networks (CNNs) to learn vision features. Kanezaki et al.
[16] proposed a CNN-based model to group spatially continuous pixels of
similar features to facilitate unsupervised natural image segmentation. In
order to perform the segmentation of the target region, there are several
other research lines in unsupervised image segmentation related to skin lesion
segmentation, which focuses on different scenarios. The first line is
unsupervised salient object detection, which aims at localizing and segmenting
salient objects simultaneously without manual annotations. Yan et al. [17]
pointed out the unreliability of usually used noisy labels generated by
traditional unsupervised salient object detection methods and proposed
unsupervised domain adaptive salient object detection which learns from
synthetic labels with higher quality. Zhou et al. [18] proposed a texture-
guided saliency distilling unsupervised salient object detection model through
a confidence-aware saliency distilling strategy that assigns scores to samples
based on confidence, and a boundary-aware texture matching strategy which
refines boundaries by matching textures. The second line is unsupervised
foreground extraction, which aims for a binary partition of an image with a
foreground containing identifiable objects and a background with remaining
regions. Yu et al. [19] presented deep region competition (DRC) to solve the
foreground extraction problem by reconciling energy-based prior with
generative image modeling in the form of mixture of experts. Ding et al. [20]
pointed out two kinds of trivial solutions in the image compositional
generation process when performing foreground extraction, and solved trivial
solutions with the proposed ComGAN model. For the task of skin lesion
segmentation, lesions can be taken as salient objects or image foregrounds, so
both methods belonging to these two research lines can be used to tackle the
task of skin lesion segmentation.

###  II-C Structural Entropy

SE [21] is first proposed to measure the complexity of the hierarchical
structure of graphs through associated encoding trees, which is naturally a
node clustering method. As the SE of a graph $G$ is the minimum overall number
of bits required to determine the codewords of the graph nodes, it measures
the uncertainty embedded in $G$. SE has been successfully applied in the field
of bioinformatics [22], reinforcement learning [23, 24], and graph neural
networks [25, 26, 27]. In this work, we use the two-dimensional SE, i.e., SE
of a graph by a partition, to perform skin lesion segmentation. Without
confusion, SE in the following sections means two-dimensional SE.

Let $G=(V,E,\mathbf{W})$ be an undirected weighted graph, where
$V=\\{v_{1},...,v_{N}\\}$ is the node set, $E$ is the edge set, and
$\mathbf{W}\in\mathbb{R}^{N\times N}$ is the edge weight matrix. A graph
partition $\mathcal{P}$ defined on $G$ can be formulated as
$\mathcal{P}=\\{X_{1},X_{2},...,X_{L}\\}$, where $X_{i}$ is the $i$-th module
containing a subset nodes of $V$. Given a graph $G$ and its graph partition
$\mathcal{P}$, the SE of $G$ given by $\mathcal{P}$ is defined as:

$\displaystyle\mathcal{H}^{\mathcal{P}}(G)=-\sum_{X\in\mathcal{P}}\sum_{v_{i}\in
X}\frac{g_{i}}{vol(G)}{\rm log_{2}}\frac{d_{i}}{vol(X)}$ (1)
$\displaystyle-\sum_{X\in\mathcal{P}}\frac{cut(X)}{vol(G)}{\rm
log_{2}}\frac{vol(X)}{vol(G)},$

where $d_{i}$ is the degree of node $v_{i}$, $g_{i}$ is the weight sum of
edges connecting $v_{i}$ and other nodes, $vol(X)$ and $vol(G)$ are volumes,
i.e., the sum of the node degrees, in module $X$ and graph $G$, respectively,
and $cut(X)$ is the cut of $X$, i.e., the weight sum of edges between nodes in
and not in module $X$.

##  III Methodology

In this section, we present SLED, a novel unsupervised skin lesion
segmentation framework based on SE and outlier detection. The overview of SLED
is depicted in Figure 2. SLED composes of three components: superpixel graph
construction, SE guided segmentation, and multi-scale segmentation mechanism
by outlier detection. Different scale superpixels are grouped by SE to form
single-scale segmentation results, which are then integrated by the outlier
detection-based multi-scale mechanism to generate the final segmentation.

Figure 2: Overview of SLED.

###  III-A Basic Notations

In this paper, superpixel graphs are constructed from images to perform
segmentation, so some notations refer to elements both in graphs and images.
In particular, $v$ denotes both a graph node and a superpixel, $\mathcal{P}$
denotes both a graph partition and an image segmentation, and $X$ and $Y$
denote both modules in graph partition and regions in images. We list some
important notations in Table I.

TABLE I: Definition of notations. Symbol | Domain | Description
---|---|---
$G$ | - | Superpixel graph
$V,E,\mathbf{W}$ | - | Node set, edge set, edge weight matrix
$v$ | - | graph node/superpixel
$\mathcal{P}$ | - | Graph partition (image segmentation)
$L$ | $\mathbb{Z}$ | Number of modules/regions
$X,Y$ | - | Modules in graph partition (regions in images)
$\mathcal{H}^{\mathcal{P}}(G)$ | - | SE of $G$ given by $\mathcal{P}$
$cut(X)$ | $\mathbb{R}$ | Cut of $X$
|  | (weight sum of edges connected to nodes in $X$)
$vol(X)$ | $\mathbb{R}$ | Volume of $X$ (degree sum of nodes in $X$)
$\sigma^{2}_{B}$ | $\mathbb{Z}$ | Between class variance of regions
$o$ | $\mathbb{R}$ | Outlier score of a superpixel
$O$ | $\mathbb{Z}^{N\times N}$ | Outlier score map
$\epsilon$ | $\mathbb{N}$ | superpixel scale

###  III-B Superpixel Graph Construction

Graph-based segmentation methods [15, 28] integrate the information of both
color features and spatial position of pixels (or superpixels) in the
procedure of graph construction. This gives graph-based methods the ability to
segment images accurately and keep the spatial continuity of segments in the
meantime. Among the graph-based methods, SE-based methods give a high-quality
graph partition by SE minimization. Furthermore, SE-based methods adaptively
determine the number of modules in the partition, which are segments
corresponding to sub-regions in images in the case of skin lesion
segmentation. This gives SE-based methods the advantage of accurate
segmentation of pixels at lesion borders.

We construct a graph $G=(V,E,\mathbf{W})$ based on the image, where the nodes
in $V=\\{v_{1},...,v_{N}\\}$ correspond to superpixels of image segmented by
SLIC algorithm [29], the edges in $E$ connect spatially close superpixels, and
the weight matrix $\mathbf{W}$ measures the similarities among superpixels. To
utilize the spatial information of superpixels, we only connect the nodes
whose spatial distance is smaller than a threshold $r$. For nodes $v_{i}$ and
$v_{j}$ with edge connected, the similarity weight $\mathbf{W}_{i,j}$ is
computed as follows:

$\mathbf{W}_{i,j}={\rm
exp}\left(\frac{-d(v_{i},v_{j})^{2}}{\sigma_{i}\sigma_{j}}\right),$ (2)

where $d(v_{i},v_{j})$ is the mean color distance between $v_{i}$ and $v_{j}$,
$\sigma_{i}$ and $\sigma_{j}$ are the local scaling parameters for nodes [30].
We then sparsify this graph into a $K$-nearest neighbor graph by retaining $K$
most significant edges for each node, which avoids the complex dense graphs
for subsequent SE minimization.

Figure 3: Illustration of SE guided segmentation.

###  III-C Structural Entropy Guided Segmentation

After superpixel graphs construction, images are segmented into regions
through SE minimization on these graphs. The procedure of SE guided
segmentation is depicted in Figure 3. We aim to partition the graph into
several modules by SE minimization. Since nodes in modules represent the
superpixels of the image, those modules thus represent homogeneous regions of
the image. As such, we can simply classify those regions to be either lesion
regions or healthy skin regions to predict accurate lesion boundaries.

We minimize the SE of $G$ to obtain a high-quality graph partition
$\mathcal{P}=\\{X_{1},X_{2},...,X_{L}\\}$. Greedily applying the merging
operator [21] on the encoding tree gives the SE minimized encoding tree and
corresponding graph partition with adaptively determined $L$ modules. However,
the partition result by greedy merging can be sub-optimum. We propose the
iteratively refined structural entropy for better results. It composes a
merging stage and a refinement stage, as illustrated in Algorithm 1. In the
merging stage, we merge nodes to maximize the decreasing amount of SE to
obtain the encoding tree with multiple modules. And then in the refinement
stage, we greedily adjust nodes into different modules to achieve better SE
scores.

Algorithm 1 Iteratively refined structural entropy

0: A graph $G=(V,E,\mathbf{W})$

0: Encoding tree $\mathcal{T}$ and corresponding partition $\mathcal{P}$

1: Initialize $\mathcal{T}$ containing all graph nodes as tree leaves

2: // Merging stage

3: repeat

4: Merge a chosen module pair $(X,Y)$ into $X\cup Y$ condition on
$argmax_{X,Y}\\{\Delta\mathcal{H}^{\mathcal{M}}_{X,Y}\\}$ via Eq. (3)

5: Update $\Delta\mathcal{H}^{\mathcal{M}}$ for node pairs connected to $X$ or
$Y$

6: until $\Delta\mathcal{H}^{\mathcal{M}}<0$ for all module pairs

7: // Refinement stage

8: repeat

9: for each node $v_{i}\in V$ do

10: Remove node $v_{i}$ from the original module $X$

11: Insert node $v_{i}$ into a chosen module $Y$ condition on
$argmax_{Y}\\{\Delta\mathcal{H}^{\mathcal{R}}_{X,v_{i}}-\Delta\mathcal{H}^{\mathcal{I}}_{Y,v_{i}}\\}$
via Eqs. (4) and (5)

12: Update the cut and the volume of each module

13: end for

14: until $\mathcal{H}^{\mathcal{P}}(G)$ converges

In the merging stage, we apply the merging operator on the initial encoding
tree which contains all graph nodes as tree leaves to obtain the encoding tree
by merging. For an encoding tree $\mathcal{T}$ with modules $X$ and $Y$
contained, the decrease amount of SE after merging $X$ and $Y$ is given by:

$\begin{split}\Delta\mathcal{H}_{X,Y}^{\mathcal{M}}=\frac{1}{vol(G)}[\left(vol(X)-cut(X)\right){\rm
log_{2}}\,vol(X)\\\ +\left(vol(Y)-cut(Y)\right){\rm log_{2}}\,vol(Y)\\\
-\left(vol(X\cup Y)-cut(X\cup Y)\right){\rm log_{2}}\,vol(X\cup Y)\\\
+\left(cut(X)+cut(Y)-cut(X\cup Y)\right){\rm log_{2}}\,vol(G)],\end{split}$
(3)

where $\mathcal{M}$ denotes modules $\mathcal{M}$erging, $X\cup Y$ is a module
merged from $X$ and $Y$, containing nodes from either $X$ or $Y$, $vol(X)$ and
$vol(G)$ are the volume of $X$ and $G$, and $cut(X)$ is the cut of $X$, as
defined in Section II-C. Merging operator merges $X$ and $Y$ into $X\cup Y$ if
$\Delta\mathcal{H}_{X,Y}^{\mathcal{M}}>0$.

In the refinement stage, we iteratively refine the encoding tree from the
merging stage to obtain the encoding tree by refinement. For graph node
$v_{i}$, the decrease amount of SE by removing $v_{i}$ from the original
module $X$ is given by:

$\begin{split}\Delta\mathcal{H}_{X,v_{i}}^{\mathcal{R}}=\frac{vol(X)-cut(X)}{vol(G)}{\rm
log_{2}}\frac{vol(X)}{vol(G)}\\\
-\frac{vol(X\backslash\\{v_{i}\\})-cut(X\backslash\\{v_{i}\\})}{vol(G)}{\rm
log_{2}}\frac{vol(X\backslash\\{v_{i}\\})}{vol(G)},\end{split}$ (4)

where $\mathcal{R}$ denotes node $\mathcal{R}$emoving,
$X\backslash\\{v_{i}\\}$ means removing node $v_{i}$ from module $X$, and the
increase amount of SE by inserting node $v_{i}$ into another module $Y$ is
given by:

$\begin{split}\Delta\mathcal{H}_{Y,v_{i}}^{\mathcal{I}}=-\frac{vol(Y)-cut(Y)}{vol(G)}{\rm
log_{2}}\frac{vol(Y)}{vol(G)}\\\
+\frac{vol(Y\cup\\{v_{i}\\})-cut(Y\cup\\{v_{i}\\})}{vol(G)}{\rm
log_{2}}\frac{vol(Y\cup\\{v_{i}\\})}{vol(G)},\end{split}$ (5)

where $\mathcal{I}$ denotes node $\mathcal{I}$nserting, $Y\cup\\{v_{i}\\}$
denotes inserting node $i$ into module $Y$. It should be noted that the
constructed graph $G$ contains no self-loop, thus $g_{i}=d_{i}$ for graph node
$v_{i}$. In each iteration, we remove nodes from the original modules and find
modules that minimize SE the most.

In the merging stage, the merging operator is performed iff
$\Delta\mathcal{H}^{\mathcal{M}}_{X,Y}>0$, so $\mathcal{H}^{\mathcal{P}}(G)$
decreases after each merging iteration and converges when no such module pair
exists. In the refinement stage, node $v_{i}$ transfers from module $X$ to a
module $Y$ with largest
$\Delta\mathcal{H}^{\mathcal{R}}_{X,v_{i}}-\Delta\mathcal{H}^{\mathcal{I}}_{Y,v_{i}}$
in each iteration, so $\mathcal{H}^{\mathcal{P}}(G)$ decreases or stays
constant after each refinement iteration, and converges when no improvement
can be made.

The time complexity of the merging stage is $O(N{\rm log}^{2}N)$ [21]. In the
refinement stage, calculating $\Delta\mathcal{H}_{X,v_{i}}^{\mathcal{R}}$ and
$\Delta\mathcal{H}_{Y,v_{i}}^{\mathcal{I}}$ for each node $v_{i}$ and every
possible module $Y$ take time of $O(NL)$ for each iteration. Also, updating
the cut and the volume of each module take time of $O(NL)$ for each iteration.
Thus, the total time complexity of Algorithm 1 is $O(N{\rm log}^{2}N+NLT)$,
where $N$, $L$, and $T$ denote the number of nodes, modules, and iterations,
respectively.

Homogeneous Regions Bisection. Hereafter, we classify those segmented regions
into the lesion region and healthy skin. We adopt the between-class variance
maximization method, which is a widely used criterion in skin lesion
segmentation [2]. Specifically, we choose a color channel $c$ from the image,
obtain a gray image, and use the intensity of the gray image to classify the
regions into classes $C_{0}$ and $C_{1}$. To better separate the regions, the
channel $c$ is chosen from the RGB channels with maximum $\sigma^{2}_{B}$
after bisection. For each region $X_{i}$, the occurrence probability
$\omega_{X_{i}}$ and the mean intensity $\mu_{X_{i}}$ are represented as:

$\omega_{X_{i}}=\frac{\|X_{i}\|}{M},$ (6)

and

$\mu_{X_{i}}=\frac{\sum_{\text{pixel}_{j}\in X_{i}}I_{j}}{\|X_{i}\|},$ (7)

respectively, where $I_{j}$ is the intensity of pixel $j$, $\|X_{i}\|$ is the
number of pixels in region $X_{i}$, and $M$ is the total number of pixels in
the image. The between-class variance of regions is given by:

$\begin{split}\sigma^{2}_{B}&=\omega_{0}(\mu_{0}-\mu_{T})^{2}+\omega_{1}(\mu_{1}-\mu_{T})^{2},\\\
\end{split}$ (8)

where $\omega_{k}$ is the occurrence probability of class $C_{k}$ defined as:

$\omega_{k}=\sum_{X_{i}\in C_{i}}\omega_{X_{i}},$ (9)

$\mu_{k}$ is the mean intensity of class $C_{k}$ defined as:

$\mu_{k}=\sum_{X_{i}\in C_{k}}\omega_{X_{i}}\mu_{X_{i}},$ (10)

and $\mu_{T}$ is the total mean intensity of $C_{0}$ and $C_{1}$, defined as:

$\mu_{T}=\sum_{X_{i}\in C_{0,1}}\omega_{X_{i}}\mu_{X_{i}}.$ (11)

In practice, we arrange $\mu_{X_{i}}$ in ascending order and separate those
regions into two classes, i.e., $C_{0}=\\{X_{i}\mid\mu_{X_{i}}\leq\tau\\}$ and
$C_{1}=\\{X_{i}\mid\mu_{X_{i}}>\tau\\}$ using a threshold $\tau$ which gives
the greatest $\sigma^{2}_{B}$. The darker class $C_{0}$ is the lesion region.

###  III-D Multi-Scale Segmentation Mechanism

Due to the complex condition of different dermoscopic images, mis-segmentation
may occur in SE-guided segmentation. We develop a multi-scale superpixel-based
segmentation mechanism to improve the segmentation accuracy. In fact, we
observed features of pixels in healthy skin are consistent. Thus, we view
superpixels in healthy skin as normal, while those in the lesion region are
outliers. Hence, we can distinguish healthy and lesion regions by the outlier
detection method. Intuitively, a higher outlier score of a superpixel reflects
a higher possibility to be a lesion region.

Outlier Detection by Isolation Forest. Isolation Forest (iForest) [31] detects
outliers by building an ensemble of binary trees that separate training data
points called iTrees. The susceptibility of data points to being outliers is
measured by the average traversal path length on iTrees. The average traversal
path length-based outlier scores of iForest are well-graded. These graded
scores help mis-segmented superpixels to be reclassified correctly in the
following binary segmentation procedure by thresholding.

Given a dermoscopic image segmentation with lesion region and healthy skin, we
train an iForest model containing a collection of iTrees using superpixels
$\\{s_{i},i=1,...,K\\}$ in the healthy skin whose attributes are the average
RGB colors. With this ensemble of iTrees, the average path lengths $h(s_{i})$
of all superpixels $\\{s_{i},i=1,...,N\\}$ are counted, and the outlier score
$o$ of an superpixel $s_{i}$ is calculated as:

$o(v_{i},\psi)=2^{-\frac{E(h(s_{i}))}{c(\psi)}},$ (12)

where $E(h(s_{i}))$ is the average of $h(s_{i})$ from the collection of
iTrees, $\psi$ is the number of superpixels in healthy skin, and $c(\psi)$ is
the normalization term. The outlier scores of all superpixels are obtained
from the iTrees, forming a score map $O$ at the size of the image.

Multi-Scale Integration. We integrate the outlier scores from different
superpixel scales and form the multi-scale score map. The weighted score of
pixel $j$ being an outlier is defined as:

$O(j)=\frac{\sum_{\epsilon\in\gamma}\left(w^{\epsilon}O^{\epsilon}(j)\right)}{\sum_{\epsilon\in\gamma}(w^{\epsilon})},$
(13)

where $O^{\epsilon}(j)$ is the score of pixel $j$ at scale $\epsilon$,
$\gamma$ is the number of different scales, and $w^{\epsilon}$ is the weight
of scale $\epsilon$. We use the $\sigma^{2}_{B}$ in Eq. (8) to indicate the
confidence of single-scale segmentation where larger $\sigma^{2}_{B}$ should
be associated with larger weights. Specifically, the weight of a scale
$\epsilon$ is defined as:

$w^{\epsilon}={\rm\exp}\\{\frac{\sigma^{2}_{B}(\epsilon)-\min_{\epsilon\in\gamma}\sigma^{2}_{B}(\epsilon)}{\min_{\epsilon\in\gamma}\sigma^{2}_{B}(\epsilon)}\\},$
(14)

where $\sigma^{2}_{B}(\epsilon)$ is the between-class variance of scale
$\epsilon$.

The binary segmentation result is obtained by applying GHT thresholding [32]
on the multi-scale score map. We also perform hole filling to avoid small
holes in the lesion part. Following [9], we compute the region score of every
connected component which increase with region size and proximity to the image
center. This is achieved by filtering each connected component with a two-
dimensional Gaussian filter. The connected component with the largest region
score is selected as the final lesion region.

##  IV Experiments and Results

TABLE II: Comparison of unsupervised skin lesion segmentation methods. Bold: the best performance on each metric, underline: the second best performance. | ISIC 2016 | ISIC 2017 | ISIC 2018
---|---|---|---
Method% | AC$\uparrow$ | SE$\uparrow$ | SP$\uparrow$ | DI$\uparrow$ | JA$\uparrow$ | AC$\uparrow$ | SE$\uparrow$ | SP$\uparrow$ | DI$\uparrow$ | JA$\uparrow$ | AC$\uparrow$ | SE$\uparrow$ | SP$\uparrow$ | DI$\uparrow$ | JA$\uparrow$
UDASOD | 71.15 | 45.44 | 76.57 | 34.50 | 27.96 | 59.07 | 60.07 | 55.99 | 31.19 | 23.70 | 67.87 | 35.92 | 79.60 | 24.51 | 18.86
Sp. Merging | 86.67 | 67.13 | 95.39 | 69.97 | 61.06 | 79.89 | 59.16 | 88.72 | 54.66 | 46.02 | 84.53 | 69.82 | 92.79 | 70.11 | 60.89
DRC | 83.78 | 68.51 | 97.11 | 66.84 | 53.32 | 83.77 | 70.35 | 95.58 | 59.11 | 45.40 | 83.85 | 70.00 | 97.00 | 68.71 | 56.05
Saliency-CCE | 85.91 | 74.72 | 95.70 | 72.18 | 60.64 | 83.87 | 74.07 | 92.98 | 61.77 | 49.53 | 85.51 | 77.44 | 94.34 | 72.85 | 61.91
A2S-v2 | 87.51 | 82.64 | 93.85 | 75.52 | 65.67 | 82.85 | 68.65 | 92.80 | 61.35 | 51.10 | 86.22 | 72.13 | 97.35 | 75.01 | 65.94
SpecWRSC | 84.83 | 65.95 | 92.69 | 68.76 | 58.05 | 83.03 | 68.21 | 89.96 | 61.01 | 50.52 | 81.20 | 69.39 | 86.34 | 68.97 | 58.41
NCut | 85.24 | 64.86 | 93.54 | 68.78 | 58.14 | 83.79 | 67.12 | 90.90 | 62.13 | 51.84 | 82.48 | 68.12 | 88.31 | 69.11 | 58.78
$K$-means | 89.24 | 69.88 | 95.76 | 76.13 | 66.37 | 84.90 | 70.77 | 90.64 | 67.78 | 58.11 | 83.70 | 71.73 | 88.09 | 71.46 | 61.57
SGSCN | 86.61 | 63.36 | 96.59 | 71.08 | 60.24 | 85.13 | 54.98 | 95.56 | 59.95 | 50.04 | 82.30 | 71.17 | 87.36 | 70.97 | 61.81
SLEDSS | 90.69 | 77.85 | 97.23 | 81.61 | 72.21 | 86.96 | 75.98 | 92.98 | 70.62 | 60.56 | 86.22 | 79.77 | 90.52 | 76.81 | 67.98
SLEDMS | 91.82 | 80.83 | 97.72 | 84.33 | 76.02 | 88.81 | 77.96 | 94.61 | 73.90 | 64.45 | 86.93 | 80.12 | 91.84 | 77.68 | 69.35
Improvement | 4.31 | - | 0.61 | 8.81 | 10.35 | 3.68 | 3.89 | - | 12.13 | 13.35 | 0.71 | 2.68 | - | 2.67 | 3.41

In this section, we first describe our experimental setup, including datasets,
evaluation metrics, baselines, and implementation details of SLED. Next, we
quantitatively evaluate SLED on four datasets to verify the effectiveness of
SLED. Besides, we perform ablation studies and case studies to analyze SLED in
detail. At last, we evaluate the efficiency of SLED. All experiments are
conducted to answer the following questions:

  * •

Q1: Does SLED outperform state-of-the-art baselines regarding skin lesion
segmentation?

  * •

Q2: Dose our outlier detection-based multi-scale segmentation mechanism
effectively utilize the consistent healthy skin prior?

  * •

Q3: Is SLED sensitive to major parameters?

  * •

Q4: Is SLED efficient enough for skin lesion segmentation compared to
baselines?

###  IV-A Experimental Setup

Datasets. We evaluate SLED on four public benchmark datasets: ISIC 2016 [33],
ISIC 2017 [34], ISIC 2018 [35], and PH2 [6]. The first three datasets are
provided by the International Skin Imaging Collaboration (ISIC) archive from
the “Skin Lesion Analysis toward Melanoma Detection” challenge hosted by the
International Symposium on Biomedical Imaging (ISBI) in 2016, 2017, and 2018
respectively. We evaluate the performance of different methods on the test
sets, which contain 379, 600, and 1000 RGB dermoscopic images respectively at
the resolution ranging from 1022 $\times$ 767 to 4288 $\times$ 2848, along
with their corresponding ground truth. The PH2 dataset is another frequently
used benchmark, especially for unsupervised skin lesion segmentation. It
contains a total of 200 RGB dermoscopic images at the resolution of 768
$\times$ 560 pixels, along with their pixel-level lesion ground truth
annotated by expert dermatologists.

Evaluation Metrics and Baselines. We adopt five metrics used in ISIC
challenges for evaluating all compared methods, which are pixel-level accuracy
(AC), pixel-level sensitivity (SE), pixel-level specificity (SP), Dice
Coefficient (DI), and Jaccard Index (JA), as defined in [33]. We compare SLED
with a variety of baseline methods including unsupervised skin lesion
segmentation methods, an unsupervised foreground extraction method,
unsupervised salient object detection methods, and several clustering methods.
For unsupervised skin lesion segmentation methods, we consider superpixel
merging (Sp. Merging [3]), saliency map thresholding (Saliency-CCE), and deep
learning-based clustering (SGSCN [5]). For the unsupervised foreground
extraction method, we consider Deep Region Competition (DRC [19]), where skin
lesions are taken as foreground. For unsupervised salient object detection
methods, we consider Unsupervised Domain Adaptive Salient Object Detection
(UDASOD [17]) and texture-guided saliency distilling (A2S-v2 [18]), where skin
lesions are taken as salient objects. For clustering methods, we consider
normalized cut (NCut [15]), $K$-means, and hierarchical clustering (SpecWRSC
[36]). The number of segments of $K$-means, NCut, and SpecWRSC is set to be
three, which has been reported to perform well for skin lesion segmentation
[5]. To achieve a fair comparison, we perform the same preprocessing,
homogeneous region bisection, and postprocessing method for clustering-based
methods as SLED. The details of important methods are as follows:

  * •

Sp. Merging [3] segments skin lesions by greedily merging superpixels using
the distance of the mean color of each superpixel as the criterion.

  * •

Saliency-CCE [4] utilizes a hand-crafted color feature extractor called color
channel volume to obtain the saliency map of skin lesions and binarize this
map through adaptive thresholding to obtain lesion masks.

  * •

SGSCN [5] is a spatial guided self-supervised clustering network that groups
pixels that are spatially close and have consistent features.

  * •

DRC [19] is an unsupervised foreground extraction approach by reconciling
energy-based prior with generative image modeling in the form of Mixture of
Experts.

  * •

UDASOD [17] is an unsupervised domain adaptive salient object detection method
which learns saliency from synthetic but clean labels.

  * •

A2S-v2 [18] is an unsupervised salient object detection method with a
confidence-aware saliency distilling strategy and a boundary-aware texture
matching strategy.

  * •

SpecWRSC [36] is an efficient hierarchical clustering algorithm running in
nearly-linear time in the input size of the input graph. We choose the largest
$K$ modules from the hierarchical clustering tree to obtain $K$ clusters.

Implementation Details. For all datasets, images are resized into $768\times
560$ pixels, artifacts in dermoscopic images are removed using existing
methods, including hairs [37], dark corners [38], and color charts [13]. Color
constancy [39] is also performed on images to cope with illumination problems.
We set the parameters of superpixel graph construction empirically, with the
spatial distance threshold $r$ of 0.3 times image height and width, the local
scaling parameter $\sigma$ of 30, and retained edge number $K$ of 50. To
evaluate the effectiveness of the multi-scale mechanism in SLED framework, we
report both the results of single-scale SLED (SLEDSS) and multi-scale SLED
(SLEDMS), corresponding to SLED without and with the multi-scale mechanism. In
the reported results, we empirically set the number of superpixels of SLEDSS
to be 400. The segmentation results of SLEDMS integrate the results of SLEDSS
with superpixel numbers from 200 to 700 at increments of 50. All the
experiments are conducted on a server with two Intel(R) 2.30 GHz CPUs and 500
GB RAM.

###  IV-B Quantitative Results (Q1)

Table II shows the results of unsupervised skin lesion segmentation methods on
three ISIC datasets. Compared to state-of-the-art methods, SLEDMS and SLEDSS
achieve the best and second-best performance on three metrics including AC,
DI, and JA on both three datasets. SLEDMS witnesses improvements from 0.61% to
13.35% on these three metrics, as shown in the last row of Table II. Since SE
and SP are a pair of metrics to measure how well methods can identify true
positives and true negatives respectively, SLEDMS failed to achieve the best
performance on both metrics. However, SLEDMS achieves the best performance on
at least one metric on both three datasets and achieves quite well performance
on the other metric, demonstrating the superiority of SLEDMS on this pair of
metrics. Both SLEDSS and SLEDMS achieve better performance than all other
clustering-based methods, which thanks to their ability to adaptively
determine the number of segments of SE. We can also see that SLEDMS achieves
better performance than SLEDSS on all metrics, which proves the effectiveness
of our outlier detection-based multi-scale mechanism.

We also evaluate SLED on the popular PH2 dataset, as shown in Table III.
SLEDMS and SLEDSS achieve the best and second-best performance on four metrics
and achieve quite high SP scores comparable to baseline methods. Improvements
of SLEDMS on this dataset range from 1.20% to 3.35% on four metrics, as shown
in the last row of Table III. Through quantitative comparison with nine
baselines on four datasets, SLED is proven to achieve new state-of-the-art
performance among unsupervised skin lesion segmentation methods.

TABLE III: Comparison of unsupervised skin lesion segmentation methods on PH2 dataset.  Method% | AC$\uparrow$ | SE$\uparrow$ | SP$\uparrow$ | DI$\uparrow$ | JA$\uparrow$
---|---|---|---|---|---
UDASOD | 63.18 | 48.22 | 68.03 | 31.56 | 23.68
Sp. Merging | 89.10 | 79.63 | 96.00 | 82.83 | 73.97
DRC | 82.63 | 69.18 | 97.65 | 72.41 | 59.76
Saliency-CCE | 84.62 | 78.90 | 93.77 | 76.79 | 65.62
A2S-v2 | 85.66 | 87.56 | 91.37 | 78.21 | 67.15
SpecWRSC | 85.96 | 79.08 | 89.74 | 78.12 | 68.54
NCut | 88.15 | 76.16 | 94.94 | 80.17 | 70.51
$K$-means | 91.64 | 83.82 | 95.03 | 86.14 | 77.78
SGSCN | 91.80 | 84.26 | 93.82 | 87.89 | 80.15
SLEDSS | 92.00 | 89.35 | 94.76 | 88.02 | 80.11
SLEDMS | 93.00 | 89.97 | 96.37 | 90.34 | 83.50
Improvement | 1.20 | 2.41 | - | 2.45 | 3.35
Figure 4: Performance of SLEDSS with different number of superpixels (blue) and SLEDMS (orange) on the ISIC 2016 dataset. Figure 5: Parameter sensitivity experiments for threshold $r$ on the ISIC 2016 dataset. TABLE IV: Performance of SLED on the ISIC 2016 dataset using different outlier detection methods. Method% | AC$\uparrow$ | SE$\uparrow$ | SP$\uparrow$ | DI$\uparrow$ | JA$\uparrow$
---|---|---|---|---|---
SLEDEcod | 75.58 | 24.51 | 99.51 | 33.36 | 23.77
SLEDK-NN | 84.80 | 47.94 | 99.78 | 60.07 | 47.72
SLEDOCSVM | 91.34 | 79.52 | 97.48 | 82.59 | 74.13
SLED${}_{\textit{i}Forest}$ | 91.82 | 80.83 | 97.72 | 84.33 | 76.02
Figure 6: Visual comparison of outlier score maps from different outlier
detection methods. (a) Dermoscopic images; (b) Ground truth; (c) Detected
healthy skin by SLEDSS; (d)-(g) Outlier score maps from healthy skin by (d)
Ecod [40], (e) $K$-NN [41], (f) OCSVM [42], and (g) iForest [31] respectively.

###  IV-C Ablation Study (Q2, Q3)

Sensitivity Analysis. We analyze the sensitivity of parameters involved in
SLED. One important parameter is the superpixel number $N$. A larger value of
$N$ reduces the risk of over-merge but impeded the efficiency of SLED. We
explore the performance of SLEDSS with different values of $N$ as shown in
Figure 4. The performance of SLEDSS is slightly fluctuating but generally
stable when $N>100$, indicating that SLEDSS adapts well among a wide range
value of $N$. SLEDMS outperforms any SLEDSS results in four out of five
metrics by integrating segmentation of SLEDSS at different superpixel scales,
demonstrating the effectiveness of the multi-scale segmentation mechanism.

Another important parameter is the spatial distance threshold $r$, which is
used to balance the importance of color features and the spatial position of
superpixels in the graph construction. A larger value of $r$ means greater
importance of the color feature. Figure 5 shows the sensitivity of $r$ to
SLED. It can be observed that the performance of SLED is poor when $r=0.1$ and
gets stable when $r$ is larger. SLEDSS witnesses a small drop in performance
when $r$ is larger than 0.3, but this drop can be eliminated by the multi-
scale segmentation mechanism of SLEDMS.

Outlier Detection Methods. The proposed multi-scale segmentation mechanism is
a general approach, which can be implemented by many unsupervised outlier
detection methods. To find the method that best models healthy skin, we
utilize different outlier detection methods to implement several variants of
SLED , including SLEDEcod (Ecod [40]), SLEDK-NN ($K$-Nearest Neighbors [41]),
SLED OCSVM (OCSVM [42]), and SLED ${}_{\textit{i}Forest}$ (Isolation Forest
[31]). Table IV presents the performance of these variants. SLED
${}_{\textit{i}Forest}$ achieves best performance in all metrics, which
indicates that iForest models healthy skin better. SLED OCSVM ranks second
with comparable performance.

Figure 6 illustrates examples of outlier score maps using different outlier
detection methods. Both Ecod and $K$-NN fail to distinguish the lesion region
and healthy skin. OCSVM distinguishes the lesion region but fails to reflect
the diverse pixel feature in the lesion region, as shown in the second and
third rows. Visually the outlier score maps of iForest better reflect the
features of the lesion region by giving different superpixels graded scores.
When the detected healthy skin by SLEDSS is not accurate, as shown by the last
row, all methods fail to give a good score map. However, the score map of
iForest still reflects the lesion region. In all, iForest best models healthy
skin, and best fits our framework.

###  IV-D Case Study

Figure 7: Comparison of segmentation results. (a) Dermoscopic images; (b)
Ground truth; (c) UDASOD (d) Sp. Merging; (e) DRC; (f) Saliency-CCE; (g)
A2S-v2; (h) SpecWRSC; (i) NCut; (j) $K$-means; (k) SGSCN; (l) SLEDSS; (m)
SLEDMS.

Qualitative Comparison. Figure 7 gives a qualitative comparison of different
segmentation methods. Variations of lesions in color, texture, shape, size,
and location impede lesion segmentation accuracy. Low contrast between lesions
and healthy skin (shown by 2nd and 3rd rows) and changing illumination (shown
by 4th row) are the other two challenges. Furthermore, many lesions show
diverse features and can be divided into several sub-regions, misleading some
methods to take less prominent parts of lesions as healthy skin. Both K-means,
NCut, and SpecWRSC suffer from the problem of fixed segments number, leading
to poor segmentation results in some cases. Compared to other methods
including SLEDSS, SLEDMS gives more accurate lesion boundaries.

Examples of Outlier Score Maps. Figure 8 shows several examples of outlier
score maps. The multi-scale mechanism helps reduce the mis-segmentation of
SLEDSS, as shown in the second and third rows. In these two rows, the
segmented lesion regions by SLEDSS are smaller than the ground truths, leading
to inaccurate single-scale score maps. Multi-scale score maps however better
distinguish lesion regions by integrating different single-scale score maps,
leading to more accurate segmentation results of SLEDMS. It should also be
noted that when the features of pixels in healthy skin are not consistent, the
proposed multi-scale mechanism induces noises. For example, the image in the
last row has inconsistent backgrounds due to the influence of light
illumination, and the segmentation result of SLEDMS is worse than SLEDSS.

Figure 8: Visualization of outlier score maps. (a) Dermoscopic images; (b)
Ground truth; (c) Segmentation results of SLEDSS; (d) Single-scale outlier
score maps from (c); (e) Multi-scale outlier score maps; (f) Segmentation
results of SLEDMS from (e). TABLE V: Time usage of methods on PH2 dataset.

Method |  UDASOD |  Sp. Merging |  DRC |  Saliency-CCE |  A2S-v2 |  SpecWRSC |  NCut |  $K$-means |  SGSCN |  SLEDSS |  SLEDMS
---|---|---|---|---|---|---|---|---|---|---|---
Time (min) | 1 | 60 | 292 | 18 | 1 | 25 | 24 | 22 | 396 | 25 | 51

###  IV-E Efficiency (Q4)

We test the efficiency of different methods on the PH2 dataset as shown in
Table V. The running time of SLEDSS is comparable to Saliency-CCE, NCut, and
$K$-means. By calculating the segmentation of SLEDSS with different scales in
parallel, the running time of SLEDMS is comparable to Sp. Merging, and less
than DRC and SGSCN. Although UDASOD and A2S-v2 consume the least running time,
they both require tremendous model training time. In all, SLED is quite
efficient.

##  V Conclusion

In this paper, we have presented SLED, a novel unsupervised skin lesion
segmentation framework. To address the challenges of diverse pixel features
within the lesion region and the consistency of pixel features in healthy
skin, we introduce two key components in our framework: SE guided segmentation
and a multi-scale mechanism utilizing isolation forest outlier detection. Our
extensive experimental evaluations on four widely used skin lesion
segmentation benchmarks confirm the superiority of SLED over existing methods
in terms of effectiveness and efficiency. We believe that SLED holds great
potential for improving dermatological diagnosis and aiding in early disease
detection.

## Acknowledgement

This work is supported by the National Key R&D Program of China through grant
2021YFB1714800, NSFC through grant 61932002, S&T Program of Hebei through
grant 20310101D, Natural Science Foundation of Beijing Municipality through
grant 4222030, CCF-DiDi GAIA Collaborative Research Funds for Young Scholars,
and the Fundamental Research Funds for the Central Universities. Philip S. Yu
is supported by NSF under grant III-2106758.

## References

  * [1] Y. Yuan, M. Chao, and Y.-C. Lo, “Automatic skin lesion segmentation using deep fully convolutional networks with jaccard distance,” _IEEE transactions on medical imaging_ , vol. 36, no. 9, pp. 1876–1886, 2017.
  * [2] M. R. Guarracino and L. Maddalena, “Sdi+: A novel algorithm for segmenting dermoscopic images,” _IEEE journal of biomedical and health informatics_ , vol. 23, no. 2, pp. 481–488, 2018.
  * [3] D. Patiño, J. Avendaño, and J. W. Branch, “Automatic skin lesion segmentation on dermoscopic images by the means of superpixel merging,” in _International Conference on Medical Image Computing and Computer-Assisted Intervention_. Springer, 2018, pp. 728–736.
  * [4] X. Zhou, T. Tong, Z. Zhong, H. Fan, and Z. Li, “Saliency-cce: Exploiting colour contextual extractor and saliency-based biomedical image segmentation,” _Computers in Biology and Medicine_ , p. 106551, 2023.
  * [5] E. Ahn, D. Feng, and J. Kim, “A spatial guided self-supervised clustering network for medical image segmentation,” in _International Conference on Medical Image Computing and Computer-Assisted Intervention_. Springer, 2021, pp. 379–388.
  * [6] T. Mendonça, P. M. Ferreira, J. S. Marques, A. R. Marcal, and J. Rozeira, “Ph 2-a dermoscopic image database for research and benchmarking,” in _2013 35th annual international conference of the IEEE engineering in medicine and biology society (EMBC)_. IEEE, 2013, pp. 5437–5440.
  * [7] E. Ahn, J. Kim, L. Bi, A. Kumar, C. Li, M. Fulham, and D. D. Feng, “Saliency-based lesion segmentation via background detection in dermoscopic images,” _IEEE journal of biomedical and health informatics_ , vol. 21, no. 6, pp. 1685–1693, 2017.
  * [8] F. Peruch, F. Bogo, M. Bonazza, V.-M. Cappelleri, and E. Peserico, “Simpler, faster, more accurate melanocytic lesion segmentation through meds,” _IEEE Transactions on Biomedical Engineering_ , vol. 61, no. 2, pp. 557–565, 2013.
  * [9] M. Zortea, E. Flores, and J. Scharcanski, “A simple weighted thresholding method for the segmentation of pigmented skin lesions in macroscopic images,” _Pattern Recognition_ , vol. 64, pp. 92–104, 2017.
  * [10] D. N. Thanh, U. Erkan, V. S. Prasath, V. Kumar, and N. N. Hien, “A skin lesion segmentation method for dermoscopic images based on adaptive thresholding with normalization of color models,” in _2019 6th International Conference on Electrical and Electronics Engineering (ICEEE)_. IEEE, 2019, pp. 116–120.
  * [11] F. Navarro, M. Escudero-Vinolo, and J. Bescós, “Accurate segmentation and registration of skin lesion images to evaluate lesion change,” _IEEE journal of biomedical and health informatics_ , vol. 23, no. 2, pp. 501–508, 2018\.
  * [12] H. Fan, F. Xie, Y. Li, Z. Jiang, and J. Liu, “Automatic segmentation of dermoscopy images using saliency combined with otsu threshold,” _Computers in biology and medicine_ , vol. 85, pp. 75–85, 2017.
  * [13] M. Jahanifar, N. Z. Tajeddin, B. M. Asl, and A. Gooya, “Supervised saliency map driven segmentation of lesions in dermoscopic images,” _IEEE journal of biomedical and health informatics_ , vol. 23, no. 2, pp. 509–518, 2018\.
  * [14] Z. Zhang, S. Ye, Z. Liu, H. Wang, and W. Ding, “Deep hyperspherical clustering for skin lesion medical image segmentation,” _IEEE Journal of Biomedical and Health Informatics_ , 2023.
  * [15] J. Shi and J. Malik, “Normalized cuts and image segmentation,” _IEEE Transactions on pattern analysis and machine intelligence_ , vol. 22, no. 8, pp. 888–905, 2000.
  * [16] W. Kim, A. Kanezaki, and M. Tanaka, “Unsupervised learning of image segmentation based on differentiable feature clustering,” _IEEE Transactions on Image Processing_ , vol. 29, pp. 8055–8068, 2020.
  * [17] P. Yan, Z. Wu, M. Liu, K. Zeng, L. Lin, and G. Li, “Unsupervised domain adaptive salient object detection through uncertainty-aware pseudo-label learning,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 36, no. 3, 2022, pp. 3000–3008.
  * [18] H. Zhou, B. Qiao, L. Yang, J. Lai, and X. Xie, “Texture-guided saliency distilling for unsupervised salient object detection,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2023, pp. 7257–7267.
  * [19] P. Yu, S. Xie, X. Ma, Y. Zhu, Y. N. Wu, and S.-C. Zhu, “Unsupervised foreground extraction via deep region competition,” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 14 264–14 279, 2021.
  * [20] R. Ding, K. Guo, X. Zhu, Z. Wu, and L. Wang, “Comgan: unsupervised disentanglement and segmentation via image composition,” _Advances in neural information processing systems_ , vol. 35, pp. 4638–4651, 2022.
  * [21] A. Li and Y. Pan, “Structural information and dynamical complexity of networks,” _IEEE Transactions on Information Theory_ , vol. 62, no. 6, pp. 3290–3339, 2016.
  * [22] A. Li, X. Yin, B. Xu, D. Wang, J. Han, Y. Wei, Y. Deng, Y. Xiong, and Z. Zhang, “Decoding topologically associating domains with ultra-low resolution hi-c data by graph structural entropy,” _Nature communications_ , vol. 9, no. 1, p. 3265, 2018.
  * [23] X. Zeng, H. Peng, and A. Li, “Effective and stable role-based multi-agent collaboration by structural information principles,” in _Proceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence_ , 2023, pp. 11 772–11 780.
  * [24] X. Zeng, H. Peng, A. Li, C. Liu, L. He, and P. S. Yu, “Hierarchical state abstraction based on structural information principles,” in _Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence_ , 2023, pp. 4549–4557.
  * [25] J. Wu, X. Chen, K. Xu, and S. Li, “Structural entropy guided graph hierarchical pooling,” in _International Conference on Machine Learning_. PMLR, 2022, pp. 24 017–24 030.
  * [26] D. Zou, H. Peng, X. Huang, R. Yang, J. Li, J. Wu, C. Liu, and P. S. Yu, “Se-gsl: A general and effective graph structure learning framework through structural entropy optimization,” in _Proceedings of the ACM Web Conference 2023_ , 2023, pp. 499–510.
  * [27] Z. Yang, G. Zhang, J. Wu, J. Yang, Q. Z. Sheng, H. Peng, A. Li, S. Xue, and J. Su, “Minimum entropy principle guided graph neural networks,” in _Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining_ , 2023, pp. 114–122.
  * [28] P. F. Felzenszwalb and D. P. Huttenlocher, “Efficient graph-based image segmentation,” _International journal of computer vision_ , vol. 59, no. 2, pp. 167–181, 2004.
  * [29] R. Achanta, A. Shaji, K. Smith, A. Lucchi, P. Fua, and S. Süsstrunk, “Slic superpixels compared to state-of-the-art superpixel methods,” _IEEE transactions on pattern analysis and machine intelligence_ , vol. 34, no. 11, pp. 2274–2282, 2012.
  * [30] L. Zelnik-Manor and P. Perona, “Self-tuning spectral clustering,” _Advances in neural information processing systems_ , vol. 17, 2004.
  * [31] F. T. Liu, K. M. Ting, and Z.-H. Zhou, “Isolation-based anomaly detection,” _ACM Transactions on Knowledge Discovery from Data (TKDD)_ , vol. 6, no. 1, pp. 1–39, 2012.
  * [32] J. T. Barron, “A generalization of otsu’s method and minimum error thresholding,” in _European Conference on Computer Vision_. Springer, 2020, pp. 455–470.
  * [33] D. Gutman, N. C. Codella, E. Celebi, B. Helba, M. Marchetti, N. Mishra, and A. Halpern, “Skin lesion analysis toward melanoma detection: A challenge at the international symposium on biomedical imaging (isbi) 2016, hosted by the international skin imaging collaboration (isic),” _arXiv preprint arXiv:1605.01397_ , 2016.
  * [34] N. C. Codella, D. Gutman, M. E. Celebi, B. Helba, M. A. Marchetti, S. W. Dusza, A. Kalloo, K. Liopyris, N. Mishra, H. Kittler _et al._ , “Skin lesion analysis toward melanoma detection: A challenge at the 2017 international symposium on biomedical imaging (isbi), hosted by the international skin imaging collaboration (isic),” in _2018 IEEE 15th international symposium on biomedical imaging (ISBI 2018)_. IEEE, 2018, pp. 168–172.
  * [35] N. Codella, V. Rotemberg, P. Tschandl, M. E. Celebi, S. Dusza, D. Gutman, B. Helba, A. Kalloo, K. Liopyris, M. Marchetti _et al._ , “Skin lesion analysis toward melanoma detection 2018: A challenge hosted by the international skin imaging collaboration (isic),” _arXiv preprint arXiv:1902.03368_ , 2019.
  * [36] S. Laenen, B.-A. Manghiuc, and H. Sun, “Nearly-optimal hierarchical clustering for well-clustered graphs,” _arXiv preprint arXiv:2306.09950_ , 2023.
  * [37] T. Lee, V. Ng, R. Gallagher, A. Coldman, and D. McLean, “Dullrazor®: A software approach to hair removal from images,” _Computers in biology and medicine_ , vol. 27, no. 6, pp. 533–543, 1997.
  * [38] S. W. Pewton and M. H. Yap, “Dark corner on skin lesion image dataset: Does it matter?” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops_ , 2022, pp. 4831–4839.
  * [39] G. D. Finlayson and E. Trezzi, “Shades of gray and colour constancy,” in _Color and Imaging Conference_ , vol. 2004, no. 1. Society for Imaging Science and Technology, 2004, pp. 37–41.
  * [40] Z. Li, Y. Zhao, X. Hu, N. Botta, C. Ionescu, and G. Chen, “Ecod: Unsupervised outlier detection using empirical cumulative distribution functions,” _IEEE Transactions on Knowledge and Data Engineering_ , 2022.
  * [41] F. Angiulli and C. Pizzuti, “Fast outlier detection in high dimensional spaces,” in _European conference on principles of data mining and knowledge discovery_. Springer, 2002, pp. 15–27.
  * [42] B. Schölkopf, J. C. Platt, J. Shawe-Taylor, A. J. Smola, and R. C. Williamson, “Estimating the support of a high-dimensional distribution,” _Neural computation_ , vol. 13, no. 7, pp. 1443–1471, 2001.