Neural Subgraph Matching
arXiv:2007.03092
Abstract
Subgraph matching is the problem of determining the presence and location(s) of a given query graph in a large target graph. Despite being an NP-complete problem, the subgraph matching problem is crucial in domains ranging from network science and database systems to biochemistry and cognitive science. However, existing techniques based on combinatorial matching and integer programming cannot handle matching problems with both large target and query graphs. Here we propose NeuroMatch, an accurate, efficient, and robust neural approach to subgraph matching. NeuroMatch decomposes query and target graphs into small subgraphs and embeds them using graph neural networks. Trained to capture geometric constraints corresponding to subgraph relations, NeuroMatch then efficiently performs subgraph matching directly in the embedding space. Experiments demonstrate NeuroMatch is 100x faster than existing combinatorial approaches and 18% more accurate than existing approximate subgraph matching methods.
References in corpus (7)
- Inductive Representation Learning on Large Graphs
- Topology of evolving networks: local events and universality
- Graph Matching Networks for Learning the Similarity of Graph Structured Objects
- Deep Graph Matching Consensus
- Retrosynthesis Prediction with Conditional Graph Logic Network
- Convolutional Set Matching for Graph Similarity
- A Fast Projected Fixed-Point Algorithm for Large Graph Matching
Cited by in corpus (9)
- Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting
- Design Space for Graph Neural Networks
- CLARE: A Semi-supervised Community Detection Algorithm
- Can Graph Neural Networks Count Substructures?
- AEDNet: Adaptive Edge-Deleting Network For Subgraph Matching
- Graph Meta Learning via Local Subgraphs
- Logic Embeddings for Complex Query Answering
- Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Results
- Neural PathSim for Inductive Similarity Search in Heterogeneous Information Networks