Efficient Distributed Exact Subgraph Matching via GNN-PE: Load Balancing, Cache Optimization, and Query Plan Ranking

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.

• Publication year

  2025

• Venue

  arXiv.org

• Publication date

  2025-11-12

• Fields of study

  Computer Science

• Identifiers
  DOI 10.48550/arXiv.2511.09052arXiv 2511.09052
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding

  2023influential reference
• In-Memory Subgraph Matching: An In-depth Study

  2020cited by this paper
• CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching

  2019cited by this paper
• Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together

  2019cited by this paper
• Distributed Subgraph Matching on Timely Dataflow

  2019cited by this paper
• Efficient Subgraph Matching by Postponing Cartesian Products

  2016cited by this paper
• Turboiso: towards ultrafast and robust subgraph isomorphism search in large graph databases

  2013cited by this paper
• A (sub)graph isomorphism algorithm for matching large graphs

  2004cited by this paper
• A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs

  1998cited by this paper

• No citing papers are available for this paper.