Deep Skyline Community Search

Minglang Xie, Jianye Yang, Wenjie Zhang, Shiyu Yang, Xuemin LinEDBT 2025 · OpenReview

Introduction

In modern network analysis, nodes are often associated with multiple numerical attributes. For instance, in a social network, users might have attributes like age, income, and activity level. Finding a "skyline community" involves identifying a group of nodes that are not only tightly connected (forming a $k$-core) but also "dominate" other groups across these attributes. A community is said to dominate another if it is better in at least one dimension and not worse in any other.

Multi-valued graph and its corresponding skyline communities.

Traditional algorithms for skyline community search face a "dimensionally explosive" challenge. Their computational complexity grows exponentially with the number of attributes ($d$), making them impractical for high-dimensional data or massive networks with millions of nodes. Existing tools become agonizingly slow once they encounter five or more attributes due to redundant, recursive calculations.

The DeepSCS Framework

To overcome these limitations, the authors propose DeepSCS (Deep Skyline Community Search). This framework shifts the heavy lifting from expensive recursive searches to an efficient, unsupervised deep learning model. The process is divided into two main phases: Offline Pre-training and Online Search.

The DeepSCS architecture, featuring offline pre-training with SLGCN and online search with the SCIESG solver.

1. Offline Pre-training: SLGCN

The core of the offline phase is the Skyline Learnable Graph Convolutional Network (SLGCN). This model is trained in an unsupervised manner to learn node representations that capture both structural and attribute-based dominance. Two novel loss functions guide this training:

  • Dominance Loss: Forces the model to learn representations where the "skyline" relationship is preserved in the embedding space.
  • Link Loss: Maintains structural cohesion by ensuring that physically connected nodes remain close in the embedding space.

To ensure scalability, the model uses $k$-core decomposition and $k$-hop neighborhood sampling, focusing training on the most cohesive regions of the graph rather than the entire network.

2. Online Search: SCIESG

During the online phase, when a query node is provided, the system utilizes the SCIESG (Skyline Community search with Expected Score Gain) solver. Instead of relying on fixed similarity thresholds common in other unsupervised methods, it uses an Expected Score Gain (ESG) function. This function iteratively adds neighboring nodes to the community only if they provide a significant improvement in quality compared to a random selection, making the search adaptive to local graph density.

Key Insights

A pivotal discovery in this work is the Dimensional Inclusion Property. The authors proved that skyline communities in higher dimensions effectively "cover" those in lower dimensions. This allows a single model trained on high-dimensional data to be used for queries involving any subset of those dimensions, greatly enhancing the model's versatility and efficiency.

Performance and Results

DeepSCS was evaluated on several large-scale real-world datasets, including Flixster (2.5 million nodes) and Delicious. The results demonstrate a significant leap in performance:

  • Massive Speedup: DeepSCS achieved up to a 1,000x speedup over the state-of-the-art SC-CP algorithm on the Delicious dataset with 5 attributes.
  • Scalability: Unlike traditional methods, the running time of DeepSCS remains nearly constant as the number of attributes ($d$) increases.
  • Accuracy: The framework maintains high accuracy, with F1-scores often exceeding 70%, proving that learned embeddings can effectively capture complex dominance relationships.

Conclusion and Future Directions

DeepSCS represents a major step forward in attributed graph mining by successfully applying deep learning to the skyline community search problem. While highly effective, the authors note potential for future work in handling "dimension gaps" (where query dimensions differ significantly from training) and extending the framework to temporal graphs where network structure evolves over time, potentially using Fourier Transforms to represent time-based patterns as attributes.

Summary updated

BibTeX
@inproceedings{xie2025deep,
  author = {Minglang Xie and Jianye Yang and Wenjie Zhang and Shiyu Yang and Xuemin Lin},
  title = {{Deep Skyline Community Search}},
  booktitle = {EDBT},
  year = {2025},
  url = {https://openreview.net/forum?id=lQ2aBwTAxE},
}
Figure