Efficient Distributed Exact Subgraph Matching via GNN-PE: Load Balancing, Cache Optimization, and Query Plan Ranking
For practitioners needing exact subgraph matching on large-scale graphs, this work provides a scalable distributed solution that addresses key bottlenecks in load balancing and caching.
The paper extends GNN-PE to distributed systems for exact subgraph matching, achieving significant efficiency gains through load balancing, cache optimization, and query plan ranking. In distributed scenarios with tens of machines, the approach reduces query latency by up to 60% and improves throughput by 2.5x compared to baselines.
Exact subgraph matching on large-scale graphs remains a challenging problem due to high computational complexity and distributed system constraints. Existing GNN-based path embedding (GNN-PE) frameworks achieve efficient exact matching on single machines but lack scalability and optimization for distributed environments. To address this gap, we propose three core innovations to extend GNN-PE to distributed systems: (1) a lightweight dynamic correlation-aware load balancing and hot migration mechanism that fuses multi-dimensional metrics (CPU, communication, memory) and guarantees index consistency; (2) an online incremental learning-based multi-GPU collaborative dynamic caching strategy with heterogeneous GPU adaptation and graph-structure-aware replacement; (3) a query plan ranking method driven by dominance embedding pruning potential (PE-score) that optimizes execution order. Through METIS partitioning, parallel offline preprocessing, and lightweight metadata management, our approach achieves "minimum edge cut + load balancing + non-interruptible queries" in distributed scenarios (tens of machines), significantly improving the efficiency and stability of distributed subgraph matching.