收藏切换
Efficient Subgraph Matching Algorithm with Graph Neural Network
收藏切换
Xin Xue1, 3, Tianchen Zhu1, 3, Qingyun Sun1, 3, Haoyi Zhou2, 3, *, Jianxin Li1, 3
Journal of Computer Research and Development | 2025, 62(3) : 694 - 708
Less
收藏切换
Journal of Computer Research and Development | 2025, 62(3): 694-708
• Artificial Intelligence •
Efficient Subgraph Matching Algorithm with Graph Neural Network
Full
Xin Xue1, 3, Tianchen Zhu1, 3, Qingyun Sun1, 3, Haoyi Zhou2, 3, *, Jianxin Li1, 3
Affiliations
  • 1School of Computer Science and Engineering, Beihang University, Beijing 100191
  • 2School of Software, Beihang University, Beijing 100191
  • 3Beijing Advanced Innovation Center for Big Data and Brain Computing, Beijing 100191
  • born in 2001. PhD candidate. Student member of CCF. Her main research interests include graph neural network and combinatorial optimization problem

    born in 1996. PhD. Member of CCF. His main research interest includes decision-making in time series

    born in 1996. PhD, assistant professor. Member of CCF. Her main research interests include graph machine learning, network big data analysis, and anomaly detection

    born in 1991. PhD, assistant professor. Member of CCF. His main research interests include time-series forecasting, task decision-making, and AI safety

    born in 1979. PhD, professor. Distinguished member of CCF. His main research interests include big data analysis and processing, network big data computing, and scientific computing

About Author:

born in 2001. PhD candidate. Student member of CCF. Her main research interests include graph neural network and combinatorial optimization problem

born in 1996. PhD. Member of CCF. His main research interest includes decision-making in time series

born in 1996. PhD, assistant professor. Member of CCF. Her main research interests include graph machine learning, network big data analysis, and anomaly detection

born in 1991. PhD, assistant professor. Member of CCF. His main research interests include time-series forecasting, task decision-making, and AI safety

born in 1979. PhD, professor. Distinguished member of CCF. His main research interests include big data analysis and processing, network big data computing, and scientific computing

Published: 2025-03-01 doi: 10.7544/issn1000-1239.202330732
Outline
收藏切换

Subgraph matching is an optimization problem in graph, which is to find all matching subgraphs of the query graph in a large target graph. Although subgraph matching is an NP-Hard problem, the problem is common in many fields such as social networks, biochemistry, and cognitive science. Backtracking searching algorithms for subgraph matching have high time complexity, and the pruning strategy is essential to reduce the operating time. However, complex expanding in the existing pruning strategy leads to high complexity of time and space. To balance the efficiency and the effectiveness, only limited neighborhood structure information can be used in conflicting judging, which lets lots of useless states pass the pruning judging and wastes time. An efficient, accurate, and adaptive subgraph matching algorithm is proposed. The algorithm captures the detail structure of the whole graph by graph neural network, builds structure connections, and generates pruning possibilities for all candidate searching states. It replaces complex expanding pruning method with inferring by the neural network model to rapidly estimate the probability of pruning during searching. A data sampling mechanism is designed to alleviate the problem of network training collapse. Experiments show that using our pruning method in traditional backtracking search can improve search efficiency.

subgraph matching  /  graph neural network  /  backtracking algorithm  /  combinatorial optimization  /  attention mechanism
薛欣, 朱天晨, 孙庆赟, 周号益, 李建欣. 融合图神经网络的高效子图匹配算法. 计算机研究与发展, 2025 , 62 (3) : 694 -708 . DOI: 10.7544/issn1000-1239.202330732
Xin Xue, Tianchen Zhu, Qingyun Sun, Haoyi Zhou, Jianxin Li. Efficient Subgraph Matching Algorithm with Graph Neural Network[J]. Journal of Computer Research and Development, 2025 , 62 (3) : 694 -708 . DOI: 10.7544/issn1000-1239.202330732
Year 2025 volume 62 Issue 3
126
60
Cite this Article
BibTeX
Article Info
doi: 10.7544/issn1000-1239.202330732
  • Receive Date:2023-09-12
  • Online Date:2026-11-10
  • Published:2025-03-01
Article Data
Affiliations
History
  • Received:2023-09-12
  • Revised:2024-07-05
  • Accepted:2024-08-09
Affiliations
    1School of Computer Science and Engineering, Beihang University, Beijing 100191
    2School of Software, Beihang University, Beijing 100191
    3Beijing Advanced Innovation Center for Big Data and Brain Computing, Beijing 100191
References
Share
https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/10.7544/issn1000-1239.202330732
Share to
QR

Scan QR to access full text

Cite this article
BibTeX
Citations
表12种不同金属材料的力学参数
科
Family
属数
Number of
genus
种数
Number of
species
占总种数比例
Percentage of
total species (%)
属
Genus
种数
Number of
species
占总种数比例
Percentage of total
species (%)
鹅膏菌科Amanitaceae 2 11 5.26 鹅膏菌属 Amanita 10 4.78
小菇科 Mycenaceae 2 12 5.74 丝盖伞属 Inocybe 5 2.39
多孔菌科 Polyporaceae 8 14 6.70 蜡蘑属 Laccaria 5 2.39
红菇科 Russulaceae 3 23 11.00 小皮伞属 Marasmius 6 2.87
小菇属 Mycena 11 5.26
光柄菇属 Pluteus 5 2.39
红菇属 Russula 17 8.13
栓菌属 Trametes 5 2.39
关闭全屏
  • BibTeX
  • EndNote
  • RefWorks
  • TxT