Optimizing skyline queries in large-scale uncertain graph using graph neural networks and reinforcement learning

Abstract

Skyline queries play a critical role in multi-criteria decision-making by identifying data points that are not dominated by others, thus offering optimal choices to users. These queries are particularly valuable in transportation management, logistics, route optimization, and decision support systems. However, existing skyline query processing algorithms exhibit limited effectiveness when applied to large-scale and uncertain graph datasets, due to their reliance on exhaustive dominance comparisons, and sensitivity to uncertainty, which collectively result in incompatibility when applied in real-world graph environments. To address these challenges, this research proposes a novel skyline query processing framework that integrates Graph Neural Networks (GNNs) with Reinforcement Learning (RL), enabling effective representation learning over uncertain graph structures and adaptive skyline selection, a solution to ensure compatibility, and also test the potential scalability of the framework. As part of the contribution, large-scale uncertain graph datasets are systematically constructed with controlled size, density, and uncertainty levels to enable rigorous evaluation and scalability analysis. The proposed method is evaluated using 10-fold cross-validation, and performance is measured using accuracy, precision, recall, F1-score, and ROC-AUC. Experimental results demonstrate that while baseline skyline algorithms achieve acceptable accuracy, they suffer from significantly lower precision and recall, leading to suboptimal identification of skyline points. In contrast, the proposed GNN-RL framework achieves an accuracy of 98.97% alongside recall and F1-score above 98%, demonstrating strong robustness in uncertain graph settings. Furthermore, scalability experiments across varying dataset sizes confirm the suitability of the proposed approach for large-scale skyline query processing. This research contributes both theoretically and practically to intelligent data analytics and supports the United Nations Sustainable Development Goal (SDG) No. 9 which promotes resilient infrastructure, sustainable industrialization, and innovation through the development of scalable and intelligent data-driven technologies.