Early diagnosis of skin cancer is crucial for improving treatment outcomes, increasing survival rates, and enhancing overall patient prognosis. An automated method utilizing clinical markers focused on cancer lesions can significantly improve the cancer diagnosis process. This study aims to leverage significant lesion markers identified by dermatologists using a Graph Neural Network (GNN), LesionGraph-Net, to enhance performance and analyze the complex relationships among biomarkers. The region of interest (ROI) from skin cancer images is segmented using K-means clustering, and biomarkers from skin lesions are extracted using computerized features. Among them, seven key features are identified based on feature selection methods. A graph is constructed from these features using the Pearson correlation formula, with the edge weight threshold determined through experiments at 0.2. LesionGraph-Net is then employed to identify the cancer, and its performance is compared to image-based transfer learning models and feature-based approaches, including GCN, 1D CNN, and various machine learning models. Our proposed model exhibits strong performance, achieving an accuracy of 98.62% and an F1 score of 98.43%. Compared to other methods, the proposed model consistently outperforms both image and feature-based approaches, underscoring the effectiveness of graph-based analysis in diagnosing skin cancer. The study highlights the benefits of integrating automated systems that incorporate significant clinical biomarkers. The retrieved clinical indications align with computerized features, aiding early diagnosis and cancer analysis for dermatologists. The study indicates that GNN-based models outperform conventional methods in identifying cancer, highlighting their potential for clinical trials.