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

Yu Wang, Hui Wang, Jiake Ge, Xin WangarXiv 2025 · DOI · arXiv

Abstract

Exact subgraph matching is a computationally intensive NP-complete problem vital for various domains, including social network analysis and bioinformatics. While Graph Neural Network-based Path Embedding (GNN-PE) has significantly accelerated matching on single machines, its transition to distributed environments introduces critical bottlenecks such as load imbalance, high communication overhead, and inefficient hardware utilization. This paper presents a distributed GNN-PE framework that addresses these challenges through three primary innovations: a multi-dimensional dynamic load balancer, a collaborative multi-GPU caching strategy, and a pruning-aware query plan ranking system. Our evaluation on large-scale datasets demonstrates that this approach achieves up to two orders of magnitude improvement in query latency and a 2-3x increase in throughput compared to existing distributed baselines.

Introduction

Finding all instances of a query graph within a massive data graph—exact subgraph matching—remains a significant challenge in large-scale graph processing. Recent advancements have leveraged GNNs to create embeddings that prune irrelevant search spaces, yet scaling these methods to distributed clusters often results in performance degradation. Distributed systems frequently encounter "hotspots" where specific machines are overwhelmed, while others remain idle. Furthermore, the network latency incurred by verifying potential matches across shards often becomes the primary performance bottleneck. This work transforms GNN-PE into a robust, cluster-ready system by optimizing resource allocation and minimizing inter-node communication.

Methodology

The proposed system introduces a suite of optimizations designed for heterogeneous distributed environments. To facilitate a clear understanding of the system's components, the following table summarizes the key symbols and notations used throughout our framework.

Table 1: Summary of symbols and notations used in the distributed GNN-PE framework.

Lightweight Dynamic Load Balancing

Traditional load balancers often rely solely on CPU metrics, which fails to capture the complexity of distributed graph queries. Our system monitors a multi-dimensional load ($Load(C_k)$) that incorporates CPU utilization ($U_{cpu}$), memory occupancy ($Mem$), and cross-shard communication frequency ($Comm$). By fusing these metrics, the system can identify true bottlenecks. When a machine becomes a hotspot, the system migrates graph shards ($S_i$) to underutilized nodes in less than 50ms. Data integrity during these rapid migrations is maintained via CRC32 checksums, ensuring continuous query processing without downtime.

Multi-GPU Collaborative Caching

To maximize hardware efficiency, we implement a hybrid CPU-GPU storage architecture. An online incremental learning model, AW-ResNet, calculates a cache value ($V(p)$) for graph paths based on access frequency and contribution to successful matches. This allows the system to prioritize high-value data in fast GPU memory. Furthermore, the system exploits hardware heterogeneity by assigning complex model inference to high-performance GPUs (e.g., H100) while delegating data preprocessing to mid-range GPUs (e.g., RTX 3090).

PE-Score Driven Query Plan Ranking

Communication overhead is minimized by prioritizing query paths with the highest "pruning potential." We utilize an XGBoost-based model to calculate a PE-score ($PE-score(p)$) for each candidate path. This score predicts the effectiveness of a path in eliminating invalid candidates early in the matching process. By executing high-pruning paths first, the system significantly reduces the volume of data that must be transmitted across the network for verification.

Experimental Evaluation

Datasets and Setup

The framework was evaluated using several diverse large-scale datasets:

  • DBLP: A computer science bibliography graph.
  • Youtube: A social network graph.
  • US Patents: A citation network exhibiting high (99.5%) pruning potential.
  • Newman-Watts-Strogatz: Synthetic graphs used to analyze performance across varying graph topologies.

Experiments were conducted on clusters of up to 50 worker machines ($n \le 50$), handling graphs with up to 1 million vertices and hundreds of shards ($m$).

Key Results and Insights

  • Performance Gains: The distributed GNN-PE framework outperformed baseline methods by 1-2 orders of magnitude in query latency and achieved a 2-3x improvement in overall throughput.
  • Communication Efficiency: The PE-score ranking mechanism successfully reduced cross-shard data transfers by 60-70%, effectively mitigating network congestion.
  • Resource Utilization: By treating hardware heterogeneity as a tiered pipeline, GPU utilization was improved to over 85%, a significant increase from the <60% typical of static placement strategies.
  • System Stability: The dynamic load balancer maintained a cluster load standard deviation ($\sigma$) of under 10%, preventing the long-tail latency spikes that often plague distributed systems.

Conclusion

This work demonstrates that efficient distributed subgraph matching requires a holistic approach that considers communication as a primary load factor and treats pruning potential as a first-class citizen in query optimization. While currently optimized for static graphs, future research will extend these techniques to dynamic graphs with real-time updates and further optimize for ultra-low-latency edge computing environments.

Summary updated

BibTeX
@misc{wang2025efficient,
  author = {Yu Wang and Hui Wang and Jiake Ge and Xin Wang},
  title = {{Efficient Distributed Exact Subgraph Matching via GNN-PE: Load Balancing, Cache Optimization, and Query Plan Ranking}},
  year = {2025},
  eprint = {2511.09052},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2511.09052},
}
Figure