GNN-based Anchor Embedding for Efficient Subgraph Retrieval

Several recent works utilize deep learning (DL) techniques for subgraph retrieval via matching, yet most only return approximate isomorphism relations between queries and data graphs--failing to retrieve all exact matching locations, a critical demand for structured graph retrieval in information retrieval. Unlike these DL-based approximate methods, we propose a learning-based framework for subgraph retrieval, called the graph neural network (GNN)-based anchor embedding framework (GNN-AE), which can efficiently retrieve all exact matching locations. In contrast to most traditional exact subgraph matching methods, which create auxiliary structures online for each query, our method has two core optimizations: (1) We construct offline, one-time-only efficient embedding indices for small feature subgraphs (namely, anchored subgraphs and anchored paths) in the data graph and obtain candidates for the query on these indexed feature subgraphs, trading space for time to reduce online query latency; (2) We leverage GNNs to perform graph isomorphism tests on indexed feature subgraphs and generate low-conflict embeddings for these feature subgraphs, yielding a high-quality, compact set of candidates that further enhances query efficiency. Beyond these core optimizations, we develop a parallel matching growth algorithm and design a cost-based DFS query strategy to retrieve all matching locations. Extensive experiments on both real and synthetic datasets validate the efficiency and effectiveness of our GNN-AE for exact subgraph retrieval.