Efficient Distributed Exact Subgraph Matching via GNN-PE: Load Balancing, Cache Optimization, and Query Plan Ranking
Yu Wang, Hui Wang, Jiake Ge, Xin Wang
由于高计算复杂性和分布式系统限制,在大规模图形上精确匹配子图仍然是一个具有挑战性的问题。 现有的基于 GNN 的路径嵌入 (GNN-PE) 框架在单台计算机上实现了高效的精确匹配,但缺乏分布式环境的可扩展性和优化。 为了解决这一差距,我们提出了三个核心创新,将GNN-PE扩展到分布式系统:(1)一个轻量级的动态相关性感知负载平衡和热迁移机制,融合了多维指标(CPU,通信,内存)并保证了指数一致性;(2)一种基于在线增量学习的多GPU协作动态缓存策略,具有异构GPU适应和图形结构感知替换;(3)由支配性嵌入修剪潜力驱动的查询计划排名方法。 通过METIS分区、并行离线预处理和轻量级元数据管理,我们的方法实现了分布式场景(机器的微量边缘切位+负载平衡+不间断查询),显著提高了分布式子图匹配的效率和稳定性。
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 mech...