Charting the Design Space of Neural Graph Representations for Subgraph Matching
Vaibhav Raj Indradyumna Roy Ashwin Ramachandran Soumen Chakrabarti Abir De
Subgraph matching is vital in knowledge graph (KG) question answering, molecule design, scene graph, code and circuit search, etc.
Neural methods have shown promising results for subgraph matching.
Our study of recent systems suggests refactoring them into a unified design space for graph matching networks.
Existing methods occupy only a few isolated patches in this space, which remains largely uncharted.
We undertake the first comprehensive exploration of this space, featuring such axes as attention-based vs. soft permutation-based interaction between query and corpus graphs, aligning nodes vs. edges, and the form of the final scoring network that integrates neural representations of the graphs.
Our extensive experiments reveal that judicious and hitherto-unexplored combinations of choices in this space lead to large performance benefits.
Beyond better performance, our study uncovers valuable insights and establishes general design principles for neural graph representation and interaction, which may be of wider interest.
Graph Retrieval, Graph Neural Networks, Subgraph Matching
We propose a unified framework for graph matching networks and experiment with various alternatives for each design axis to obtain state-of-the-art results on the subgraph isomorphism task.