Improving Subgraph Matching by Combining Algorithms and Graph Neural Networks

Homomorphism is an important structure-preserving mapping between graphs. Given a graph 𝐺 and a pattern 𝑄, the subgraph homomorphism problem is to find a mapping 𝜑 from 𝑄 to 𝐺 such that adjacent vertices of 𝑄 are mapped to adjacent vertices in 𝐺. Unlike the subgraph isomorphic mapping that is injective, homomorphism allows multiple vertices in 𝑄 to map to the same vertex in 𝐺, increasing complexity. We develop HFrame, the first GNN-based framework for subgraph homomorphism, by combining algorithms and machine learning. We show that HFrame is more expressive than the vanilla GNN, i.e., HFrame can distinguish more graph pairs (𝑄, 𝐺) such that 𝑄 is not homomorphic to 𝐺. Moreover, we provide a generalization error bound for HFrame. Using real-life and synthetic graphs, we show that HFrame is up to 101.91× faster than exact matching algorithms, and its average accuracy can reach 0.962. CCS Concepts • Computing methodologies → Neural networks; Model development and analysis.