Saved in:
| Main Authors: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2507.20226 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911323667824640 |
|---|---|
| author | Guo, Shuyang Xie, Wenjin Lu, Ping Deng, Ting Zhang, Richong Li, Jianxin Huang, Xiangping Liu, Zhongyi |
| author_facet | Guo, Shuyang Xie, Wenjin Lu, Ping Deng, Ting Zhang, Richong Li, Jianxin Huang, Xiangping Liu, Zhongyi |
| contents | Homomorphism is a key mapping technique between graphs that preserves their structure. Given a graph and a pattern, the subgraph homomorphism problem involves finding a mapping from the pattern to the graph, ensuring that adjacent vertices in the pattern are mapped to adjacent vertices in the graph. Unlike subgraph isomorphism, which requires a one-to-one mapping, homomorphism allows multiple vertices in the pattern to map to the same vertex in the graph, making it more complex. We propose HFrame, the first graph neural network-based framework for subgraph homomorphism, which integrates traditional algorithms with machine learning techniques. We demonstrate that HFrame outperforms standard graph neural networks by being able to distinguish more graph pairs where the pattern is not homomorphic to the graph. Additionally, we provide a generalization error bound for HFrame. Through experiments on both real-world and synthetic graphs, we show that HFrame is up to 101.91 times faster than exact matching algorithms and achieves an average accuracy of 0.962. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_20226 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Improving Subgraph Matching by Combining Algorithms and Graph Neural Networks Guo, Shuyang Xie, Wenjin Lu, Ping Deng, Ting Zhang, Richong Li, Jianxin Huang, Xiangping Liu, Zhongyi Artificial Intelligence Homomorphism is a key mapping technique between graphs that preserves their structure. Given a graph and a pattern, the subgraph homomorphism problem involves finding a mapping from the pattern to the graph, ensuring that adjacent vertices in the pattern are mapped to adjacent vertices in the graph. Unlike subgraph isomorphism, which requires a one-to-one mapping, homomorphism allows multiple vertices in the pattern to map to the same vertex in the graph, making it more complex. We propose HFrame, the first graph neural network-based framework for subgraph homomorphism, which integrates traditional algorithms with machine learning techniques. We demonstrate that HFrame outperforms standard graph neural networks by being able to distinguish more graph pairs where the pattern is not homomorphic to the graph. Additionally, we provide a generalization error bound for HFrame. Through experiments on both real-world and synthetic graphs, we show that HFrame is up to 101.91 times faster than exact matching algorithms and achieves an average accuracy of 0.962. |
| title | Improving Subgraph Matching by Combining Algorithms and Graph Neural Networks |
| topic | Artificial Intelligence |
| url | https://arxiv.org/abs/2507.20226 |