Kidney stones are solid crystals made of minerals and salts that form within the kidney, often creating a sharp, hard mass. These stones can block urine flow as they move into the urinary tract, making early detection crucial. Although deep neural Networks (DNNs) have been used to diagnose kidney stones with some success, they still face performance and standardization issues. A new approach combines graph Convolutional Networks (GCNs) with DNNs to address these challenges. This method extracts orb features from images, converts them into graphs, and embeds nodes using a graph Convolutional Network, which includes a message-passing layer and node feature aggregation. The GCN updates node properties, enhancing efficiency and performance when integrated into a deep Network. This approach enables more comprehensive and precise feature extraction from images, improving kidney stone diagnosis. The study highlights GCNs' potential in analyzing medical images for diagnosing kidney stones. The proposed architecture was tested using publicly available CT scan images and demonstrated outstanding accuracy, correctly identifying kidney stones or healthy conditions in 98.6% of cases. It outperformed other advanced techniques, especially in detecting stones of various sizes, including very small ones, proving its effectiveness in medical image analysis.