SkyNet: Solving Skyline Queries with Neural Networks

Skyline computation, aiming at identifying a set of skyline points that are not dominated by any other point, is particularly useful for multi-criteria data analysis and decision making. The long-standing time complexity for computing skyline is $O\left(n \log ^{d-1} n\right)$, where $n$ is the number of points and $d$ is the number of dimensions. This can be prohibitively expensive in high dimensional space. One major challenge for the skyline problem is how to further scale it up with better time cost, especially for high dimensional space. In this paper, we propose the first neural architecture based on graph neural networks to learn skyline patterns (SkyNet). We define three types of skyline graphs to map points into graph structures. Given SkyNet, we can predict the skyline rather than compute the skyline using traditional comparison-based algorithms. To further enhance accuracy, we introduce a new Spatial Graph Attention mechanism (SGAT). SGAT captures deep relative spatial information between points, which is crucial for identifying dominance relationships and predicting the skyline. We also propose space-aware and layer-based loss functions, so that the trained model can better learn the spatial relationship between points. Extensive experiments show that SkyNet and its variants achieve high accuracy, efficiency, and transferability.