Learning Superpixel Ensemble and Hierarchy Graphs for Melanoma Detection

Asmaa M. Elwer; Muhammad A. Rushdi; Mahmoud H. Annaby

cs.CVApr 4, 2026

Learning Superpixel Ensemble and Hierarchy Graphs for Melanoma Detection

Authors: Asmaa M. Elwer, Muhammad A. Rushdi, Mahmoud H. Annaby

Organizations: Department of Biomedical Engineering and Systems, Faculty of Engineering, Cairo University, Giza 12613, Egypt · School of Information Technology, New Giza University, Giza 12256, Egypt · Department of Mathematics, Faculty of Science, Cairo University, Giza 12613, Egypt

Abstract

Graph signal processing (GSP) is becoming a major tool in biomedical signal and image analysis. In most GSP techniques, graph structures and edge weights have been typically set via statistical and computational methods. More recently, graph structure learning methods offered more reliable and flexible data representations. In this work, we introduce a graph learning approach for melanoma detection in dermoscopic images based on two graph-theoretic representations: superpixel ensemble graphs (SEG) and superpixel hierarchy graphs (SHG). For these two types of graphs, superpixel maps of a skin lesion image are respectively generated at multiple levels without and with parentchild constraints among superpixels at adjacent levels, where each level corresponds to a subgraph with a different number of nodes (20, 40, 60, 80, or 100 nodes). Two edge weight assignment techniques are explored: handcrafted Gaussian weights and learned weights based on optimization methods. The graph nodal signals are assigned based on texture, geometric, and color superpixel features. In addition, the effect of graph edge thresholding is investigated by applying different thresholds (25%, 50%, and 75%) to prune the weakest edges and analyze the impact of pruning on the melanoma detection performance. Experimental evaluation of the proposed method is performed with different classifiers trained and tested on the publicly available ISIC2017 dataset. Data augmentation is applied to alleviate class imbalance by adding more melanoma images from the ISIC archive. The results show that learned superpixel ensemble graphs with textural nodal signals give the highest performance reaching an accuracy of 99.00% and an AUC of 99.59%.

Figures & tables

Panel of Figure 1 — Figure 1: Dermoscopic image samples from the ISIC $2017$ dataset for both melanoma lesions (a, b) and benign lesions (c, d).

Panel of Figure 2 — Figure 2: Superpixel graph construction: (a) a color graph signal with each bar length representing the signal value for the corresponding superpixel, (b) superpixel graph construction with Gaussian-kernel-based handcrafted weights, and (c) superpixel graph construction with majorization-minimization-based learned weights.

Panel of Figure 3 — Figure 3: A hierarchical superpixel image structure with $M=80$ superpixels at the most refined level $K=4$ . (a) Superpixel ensemble graph (SEG) where superpixel maps are independently constructed. (b) Superpixel hierarchy graph (SHG) where every superpixel map results from the immediately more refined one by merging every pair of superpixels.

Figure 4: Block diagram of the proposed melanoma detection system.

Graph level		SVM	KNN	QDA	RF	GB	AB	MLP
Single graph	AC	95.92	96.21	87.17	90.38	97.08	95.63	89.50
(n=20)	Spec	93.77	91.73	98.36	73.77	98.72	98.42	91.75
	Sens	91.82	97.56	81.36	78.28	96.83	92.31	87.78
	AUC	92.33	97.89	95.67	93.29	89.87	98.35	97.27
Single graph	AC	98.04	95.92	87.46	90.67	96.50	96.50	88.92
(n=40)	Spec	98.11	90.30	94.85	99.18	98.36	99.18	98.36

Table 1: Melanoma detection results based on single-level graphs and superpixel ensemble graphs (SEG) with handcrafted weights and geometric signals . For each graph type, the best results are shown in bold. The best overall results are underlined.

Graph level		SVM	KNN	QDA	RF	GB	AB	MLP
Single graph	AC	96.00	97.67	79.59	90.38	98.05	95.63	90.38
(n=20)	Spec	73.77	94.53	96.72	73.77	98.36	100.00	99.18
	Sens	94.12	99.03	72.27	79.64	97.74	91.86	90.05
	AUC	92.92	95.34	97.22	93.31	89.89	94.05	92.73
Single graph	AC	97.54	97.19	87.46	90.67	93.38	97.08	88.92
(n=40)	Spec	96.72	93.08	99.18	99.18	99.18	100.00	98.36

Table 2: Melanoma detection results based on single-level graphs and superpixel ensemble graphs (SEG) with handcrafted weights and texture signals . For each graph type, the best results are shown in bold. The best overall results are underlined.

Graph level		SVM	KNN	QDA	RF	GB	AB	MLP
Single graph	AC	96.79	96.79	81.34	90.96	97.96	97.37	90.38
(n=20)	Spec	86.77	91.73	95.52	75.41	97.01	98.67	99.18
	Sens	95.02	98.01	84.55	79.19	97.29	95.93	86.43
	AUC	93.23	89.71	95.33	93.28	91.33	98.51	91.11
Single graph	AC	96.41	97.08	88.34	90.96	97.38	95.92	93.59
(n=40)	Spec	100.00	93.75	91.80	99.18	96.27	99.18	99.18

Table 3: Melanoma detection results based on single-level graphs and superpixel ensemble graphs (SEG) with handcrafted weights and color signals . For each graph type, the best results are shown in bold. The best overall results are underlined.

Graph level		SVM	KNN	QDA	RF	GB	AB	MLP
Single graph	AC	96.21	96.79	95.34	97.96	90.96	96.50	89.50
(n=20)	Spec	95.08	93.13	97.54	100.00	99.18	97.54	98.36
	Sens	97.27	99.01	94.12	97.74	97.29	94.57	95.48
	AUC	98.05	98.48	94.88	98.35	90.02	97.20	98.90
Single graph	AC	98.38	97.08	92.42	98.71	98.54	95.34	91.55
(n=40)	Spec	99.18	93.13	100.00	99.18	99.18	100.00	98.36

Table 4: Melanoma detection results based on single-level graphs and superpixel ensemble graphs (SEG) with learned weights and geometric signals . For each graph type, the best results are shown in bold. The best overall results are underlined.

Graph level		SVM	KNN	QDA	RF	GB	AB	MLP
Single graph	AC	98.23	95.92	87.84	90.35	96.79	96.79	91.25
(n=20)	Spec	93.77	96.06	96.07	89.77	98.78	94.73	98.36
	Sens	95.93	99.52	82.81	92.92	97.29	92.76	90.05
	AUC	95.97	99.32	98.17	91.72	98.94	96.37	99.28
Single graph	AC	97.38	96.79	91.55	90.64	96.21	97.67	93.00
(n=40)	Spec	100.00	93.13	98.36	99.18	97.54	98.36	98.36

Table 5: Melanoma detection results based on single-level graphs and superpixel ensemble graphs (SEG) with learned weights and texture signals . For each graph type, the best results are shown in bold. The best overall results are underlined.

Graph level		SVM	KNN	QDA	RF	GB	AB	MLP
Single graph	AC	97.96	95.92	94.75	97.96	97.67	95.34	92.13
(n=20)	Spec	98.36	90.91	96.72	96.72	98.36	97.54	98.36
	Sens	97.74	99.54	91.86	99.10	97.74	94.57	88.69
	AUC	98.22	95.30	94.89	98.06	91.83	96.89	96.76
Single graph	AC	99.13	97.08	91.84	97.67	97.67	96.50	93.29
(n=40)	Spec	98.00	94.44	98.36	97.54	98.36	98.36	100.00

Table 6: Melanoma detection results based on single-level graphs and superpixel ensemble graphs (SEG) with learned weights and color signals . For each graph type, the best results are shown in bold. The best overall results are underlined.

		Geometric	Texture	Color
	AC	98.12	98.41	99.01
Handcrafted	Spec	98.94	100.00	100.00
weights	Sens	97.37	98.57	99.13
	AUC	98.86	98.97	99.10
	AC	98.71	99.00	99.24
Learned	Spec	99.24	100.00	100.00

Table 7: Summary of melanoma detection results using different multi-level superpixel ensemble graph (SEG) architectures with handcrafted and learned weights. For each weight assignment scheme, the best results are shown in bold. The best overall results are underlined.

Graph level		SVM	KNN	QDA	RF	GB	AB	MLP
Single graph	AC	97.95	94.31	93.46	97.65	96.71	93.56	92.68
(n=5)	Spec	98.95	88.27	98.25	97.87	97.11	98.65	98.13
	Sens	97.17	94.80.0	97.21	97.64	94.24	88.82	98.74
	AUC	96.51	97.97	97.06	94.87	95.94	97.75	97.01
Single graph	AC	98.23	96.41	73.05	98.2	97.60	95.51	94.01
(n=10)	Spec	97.9	92.31	98.62	90.91	90.91	98.00	97.2

Table 8: Melanoma detection results based on single-level graphs and superpixel hierarchy graphs (SHG) with learned weights and geometric signals . For each graph type, the best results are shown in bold. The best overall results are underlined.

Graph level		SVM	KNN	QDA	RF	GB	AB	MLP
Single graph	AC	96.33	95.75	93.78	93.24	96.53	93.63	94.45
(n=5)	Spec	91.44	91.02	98.65	93.14	92.89	96.69	98.21
	Sens	93.56	91.72	96.96	94.42	93.9	89.81	97.99
	AUC	92.73	97.61	95.33	96.99	97.38	98.74	97.11
Single graph	AC	94.98	96.72	94.85	93.63	90.54	93.24	89.38
(n=10)	Spec	97.02	92.92	98.33	97.10	96.89	93.09	98.21

Table 9: Melanoma detection results based on single-level graphs and superpixel hierarchy graphs (SHG) with learned weights and texture signals . For each graph type, the best results are shown in bold. The best overall results are underlined.

Graph level		SVM	KNN	QDA	RF	GB	AB	MLP
Single graph	AC	97.86	93.13	95.46	96.02	96.77	93.41	95.41
(n=5)	Spec	98.73	95.76	97.97	97.00	98.57	98.66	98.98
	Sens	98.33	97.98	90.65	97.85	94.50	95.65	98.80
	AUC	94.99	96.63	97.49	97.01	95.00	96.93	96.41
Single graph	AC	96.86	92.29	92.93	98.02	96.49	93.69	89.69
(n=10)	Spec	99.66	94.29	98.31	93.90	97.32	97.66	98.85

Table 10: Melanoma detection results based on single-level graphs and superpixel hierarchy graphs (SHG) with learned weights and color signals . For each graph type, the best results are shown in bold. The best overall results are underlined.

Figure 5: Areas under the ROC curve (AUCs) for seven different classifiers trained on features of single-level graphs and superpixel ensemble graphs (SEG): (a) geometric graph signals and handcrafted weights, (b) texture graph signals and handcrafted weights, (c) color graph signals and handcrafted weights, (d) geometric graph signals and learned weights, (e) texture graph signals and learned weights, (f) color graph signals and learned weights.

Figure 6: Distribution of selected features across five graph levels and conventional features used for superpixel ensemble graphs (SEG) constructed with handcrafted and learned weights: (a) geometric graph signals with handcrafted weights, (b) texture graph signals with handcrafted weights, (c) color graph signals with handcrafted weights, (d) geometric graph signals with learned weights, (e) texture graph signals with learned weights, (f) color graph signals with learned weights.

Pruning threshold ( $\tau\%$ )		SVM	KNN	QDA	RF	GB	AB	MLP
	AC	98.70	98.05	96.42	99.24	98.70	96.1039	94.80
$\tau$ =0%	Spec	95.40	93.54	100.00	98.97	99.51	98.06	91.30
	Sens	97.69	100.00	95.02	99.55	98.19	95.02	90.47
	AUC	97.94	98.24	98.87	92.38	99.31	99.07	94.90
	AC	92.57	93.86	89.66	97.85	95.11	90.44	87.71
$\tau$ =25%	Spec	85.83	87.30	93.87	97.21	87.78	91.61	91.67

Table 11: Melanoma detection results for thresholded superpixel ensemble graphs (SEG) with learned weights and color signals. Graphs are pruned with three thresolds (

\tau\%=25\%,50\%,75\%

). For each threshold, the best results are shown in bold. The best overall results are underlined.

Author	Year	Dataset	Features	Best classifiers	AUC	AC	SP	SN
Chatterjee et al. [ 48 ]	$2019$	ISIC $2017$	Regional spatial and spectral features using statistical feature extraction and cross-spectrum analysis	SVM	–	$98.52\%$	$98.83\%$	$98.76\%$

Mahbod et al. [ 49 ]	$2019$	ISIC $2017$	Ensembles of deep features from multiple pre-trained and fine-tuned DNNs at multiple layers	SVM	$0.87$	–	–	–

Annaby et al. [ 12 ]	$2020$	ISIC $2017+250$ ISIC melanoma images	Superpixel graph features using Gaussian-kernel weighted edges	Random forests	$0.99$	$97.50\%$	$95.10\%$	$100.00\%$

Table 12: Performance comparison of different automated melanoma detection methods. The performance metrics for each classifier are the area under the ROC curve (AUC), the accuracy (AC), the specificity (SP) and the sensitivity (SN).

Skin Lesion Classification

Skin lesion classification uses medical images and clinical context to identify lesion types and estimate malignancy, supporting diagnosis and triage.

See all 53 papers

Geometry-Aware Superpixel Graph Transformer with Metadata for Skin Lesion Classification
Jun 18, 2026Muhammad Azeem, Tanveer Hussain, Amr Ahmed +1Skin Lesion Classification Graph Representation Learning
Edge Hill University, Ormskirk, Lancashire, L39 4QP, United Kingdom
Hierarchical Multi-Scale Graph Learning with Knowledge-Guided Attention for Whole-Slide Image Survival Analysis
Feb 26, 2026Bin Xu, Yufei Zhou, Boling Song +6Cancer Survival Prediction Whole-Slide Image Analysis
Nanjing University of Information Science and Technology, Nanjing, China · Case Western Reserve University, Cleveland, OH, USA · Georgia Institute of Technology and Emory University, Atlanta, GA, USA +4
Synthetic Melanoma Image Generation and Evaluation Using Generative Adversarial Networks
Mar 13, 2026Pei-Yu Lin, Yidan Shen, Neville Mathew +6Medical Image Synthesis Synthetic Data Evaluation
Department of Engineering Technology, University of Houston, Sugar Land, TX 77479, USA · Department of Electrical and Computer Engineering, University of Houston, Houston, TX 77204, USA · Department of Information Science Technology, University of Houston, Sugar Land, TX 77479, USA +5

Jun 18, 2026J/K move · Enter open · S save

Geometry-Aware Superpixel Graph Transformer with Metadata for Skin Lesion Classification

Muhammad Azeem, Tanveer Hussain, Amr Ahmed, Ardhendu Behera

Edge Hill University, Ormskirk, Lancashire, L39 4QP, United Kingdom

Skin Lesion Classification Graph Representation Learning Multimodal Classification Medical Image Classification Graph Transformer

Open paper AskPDF arXiv

Automated skin cancer classification from dermoscopic images remains challenging due to heterogeneous lesion structure, strong intra-class variability, and subtle visual differences between benign and malignant cases. Existing CNN/ViT pipelines typically rely on global or patch-level features and often combine patient metadata via late fusion, which limits spatially grounded multimodal reasoning. We present a novel region-based graph learning framework that explicitly models lesions as graphs of spatially coherent superpixel regions represented as frozen CNN features. To capture fine-grained lesion arrangements, we encode inter-regional geometry as edge attributes and introduce a dedicated metadata context node connected to all regions, providing structured integration of demographic/clinical variables within the same relational space. Node representations are updated using our edge-aware graph transformer followed by attention-driven propagation, and a final graph-level embedding for benign-malignant classification. Experiments on four public benchmarks demonstrate that explicit region-level relational modeling and graph-native multimodal fusion yield consistent gains over the state-of-the-art. Consequently, we establish a new graph-centric perspective in which CNN features are modeled as relational nodes and improved through contextual integration, yielding more expressive and robust classifications.

Abstract

Skin Lesion Classification

Explore similar work

Geometry-Aware Superpixel Graph Transformer with Metadata for Skin Lesion Classification

Hierarchical Multi-Scale Graph Learning with Knowledge-Guided Attention for Whole-Slide Image Survival Analysis

Synthetic Melanoma Image Generation and Evaluation Using Generative Adversarial Networks