Improving Subgraph Matching by Combining Algorithms and Graph Neural Networks

Shuyang Guo; Wenjin Xie; Ping Lu; Ting Deng; Richong Zhang; Jianxin Li; Xiangping Huang; Zhongyi Liu

doi:10.1145/3711896.3737006

Improving Subgraph Matching by Combining Algorithms and Graph Neural Networks

Shuyang Guo
, Wenjin Xie
, Ping Lu^*
, Ting Deng
, Richong Zhang
, Jianxin Li
, Xiangping Huang
, Zhongyi Liu

^*Corresponding author for this work

School of Computer Science and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

Homomorphism is an important structure-preserving mapping between graphs. Given a graph G and a pattern Q, the subgraph homomorphism problem is to find a mapping φ from Q to G such that adjacent vertices of Q are mapped to adjacent vertices in G. Unlike the subgraph isomorphic mapping that is injective, homomorphism allows multiple vertices in Q to map to the same vertex in G, 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 (Q, G) such that Q is not homomorphic to G. 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.

Original language	English
Title of host publication	KDD 2025 - Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining
Publisher	Association for Computing Machinery
Pages	733-744
Number of pages	12
ISBN (Electronic)	9798400714542
DOIs	https://doi.org/10.1145/3711896.3737006
State	Published - 3 Aug 2025
Event	31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2025 - Toronto, Canada Duration: 3 Aug 2025 → 7 Aug 2025

Publication series

Name	Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Volume	2
ISSN (Print)	2154-817X

Conference

Conference	31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2025
Country/Territory	Canada
City	Toronto
Period	3/08/25 → 7/08/25

Keywords

expressive power
generalization bound
graph matching
graph neural network

Access to Document

10.1145/3711896.3737006

Cite this

Guo, S., Xie, W., Lu, P., Deng, T., Zhang, R., Li, J., Huang, X., & Liu, Z. (2025). Improving Subgraph Matching by Combining Algorithms and Graph Neural Networks. In KDD 2025 - Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining (pp. 733-744). (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining; Vol. 2). Association for Computing Machinery . https://doi.org/10.1145/3711896.3737006

Guo, Shuyang ; Xie, Wenjin ; Lu, Ping et al. / Improving Subgraph Matching by Combining Algorithms and Graph Neural Networks. KDD 2025 - Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining. Association for Computing Machinery , 2025. pp. 733-744 (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining).

@inproceedings{5a4cb9521126460098279023563c08b3,

title = "Improving Subgraph Matching by Combining Algorithms and Graph Neural Networks",

abstract = "Homomorphism is an important structure-preserving mapping between graphs. Given a graph G and a pattern Q, the subgraph homomorphism problem is to find a mapping φ from Q to G such that adjacent vertices of Q are mapped to adjacent vertices in G. Unlike the subgraph isomorphic mapping that is injective, homomorphism allows multiple vertices in Q to map to the same vertex in G, 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 (Q, G) such that Q is not homomorphic to G. 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.",

keywords = "expressive power, generalization bound, graph matching, graph neural network",

author = "Shuyang Guo and Wenjin Xie and Ping Lu and Ting Deng and Richong Zhang and Jianxin Li and Xiangping Huang and Zhongyi Liu",

note = "Publisher Copyright: {\textcopyright} 2025 ACM.; 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2025 ; Conference date: 03-08-2025 Through 07-08-2025",

year = "2025",

month = aug,

day = "3",

doi = "10.1145/3711896.3737006",

language = "英语",

series = "Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining",

publisher = "Association for Computing Machinery ",

pages = "733--744",

booktitle = "KDD 2025 - Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining",

address = "美国",

}

Guo, S, Xie, W, Lu, P , Deng, T , Zhang, R, Li, J, Huang, X & Liu, Z 2025, Improving Subgraph Matching by Combining Algorithms and Graph Neural Networks. in KDD 2025 - Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, vol. 2, Association for Computing Machinery , pp. 733-744, 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2025, Toronto, Canada, 3/08/25. https://doi.org/10.1145/3711896.3737006

Improving Subgraph Matching by Combining Algorithms and Graph Neural Networks. / Guo, Shuyang; Xie, Wenjin; Lu, Ping et al.
KDD 2025 - Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining. Association for Computing Machinery , 2025. p. 733-744 (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining; Vol. 2).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Improving Subgraph Matching by Combining Algorithms and Graph Neural Networks

AU - Guo, Shuyang

AU - Xie, Wenjin

AU - Lu, Ping

AU - Deng, Ting

AU - Zhang, Richong

AU - Li, Jianxin

AU - Huang, Xiangping

AU - Liu, Zhongyi

PY - 2025/8/3

Y1 - 2025/8/3

N2 - Homomorphism is an important structure-preserving mapping between graphs. Given a graph G and a pattern Q, the subgraph homomorphism problem is to find a mapping φ from Q to G such that adjacent vertices of Q are mapped to adjacent vertices in G. Unlike the subgraph isomorphic mapping that is injective, homomorphism allows multiple vertices in Q to map to the same vertex in G, 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 (Q, G) such that Q is not homomorphic to G. 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.

AB - Homomorphism is an important structure-preserving mapping between graphs. Given a graph G and a pattern Q, the subgraph homomorphism problem is to find a mapping φ from Q to G such that adjacent vertices of Q are mapped to adjacent vertices in G. Unlike the subgraph isomorphic mapping that is injective, homomorphism allows multiple vertices in Q to map to the same vertex in G, 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 (Q, G) such that Q is not homomorphic to G. 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.

KW - expressive power

KW - generalization bound

KW - graph matching

KW - graph neural network

UR - https://www.scopus.com/pages/publications/105014588561

U2 - 10.1145/3711896.3737006

DO - 10.1145/3711896.3737006

M3 - 会议稿件

AN - SCOPUS:105014588561

T3 - Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

SP - 733

EP - 744

BT - KDD 2025 - Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining

PB - Association for Computing Machinery

T2 - 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2025

Y2 - 3 August 2025 through 7 August 2025

ER -

Guo S, Xie W, Lu P , Deng T , Zhang R, Li J et al. Improving Subgraph Matching by Combining Algorithms and Graph Neural Networks. In KDD 2025 - Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining. Association for Computing Machinery . 2025. p. 733-744. (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining). doi: 10.1145/3711896.3737006

Improving Subgraph Matching by Combining Algorithms and Graph Neural Networks

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this