Subgraph Matching Cardinality Estimation Combining Heuristic and Boosting Method

doi:10.3778/j.issn.1673-9418.2009088

Journal of Frontiers of Computer Science and Technology ›› 2022, Vol. 16 ›› Issue (3): 582-590.DOI: 10.3778/j.issn.1673-9418.2009088

• Artificial Intelligence • Previous Articles Next Articles

Subgraph Matching Cardinality Estimation Combining Heuristic and Boosting Method

HOU Wenzhe, ZHAO Xiang⁺()

Science and Technology on Information Systems Engineering Laboratory, National University of Defense Technology, Changsha 410000, China

Received:2020-09-29 Revised:2021-04-28 Online:2022-03-01 Published:2021-05-07
About author:HOU Wenzhe, born in 1997, M.S. candidate. His research intersts include graph data analysis and natural language processing.
ZHAO Xiang, born in 1986, Ph.D., associate professor, M.S. supervisor. His research interests include data graph and big data analysis.
Supported by:
National Natural Science Foundation of China(61872446);National Natural Science Foundation of China(61902417);National Natural Science Foundation of China(71971212);Natural Science Foundation of Hunan Province(2019JJ20024)

融合启发式和Boosting的子图匹配基数估计方法

侯文哲, 赵翔⁺()

国防科技大学信息系统工程重点实验室,长沙 410000

通讯作者: + E-mail: xiangzhao@nudt.edu.cn
作者简介:侯文哲（1997—）,男,山东泰安人,硕士研究生,主要研究方向为图数据分析、自然语言处理。
赵翔（1986—）,男,浙江金华人,博士,副教授,硕士生导师,主要研究方向为知识图谱技术、大数据分析。
基金资助:
国家自然科学基金(61872446);国家自然科学基金(61902417);国家自然科学基金(71971212);湖南省自然科学基金(2019JJ20024)

Abstract

Abstract:

Attributed to its innate advantage in modeling relational information, graph data have been widely leveraged in various applications including social network, knowledge representation, etc. Compared with traditional relational database systems, primitive operators in graph data management, represented by subgraph matching, still observe space for further optimization. In a fully-fledged graph database system, in order to optimize the schedule of multiple subgraph matching tasks, it usually necessitates accurate estimation of the cost of every task, especially of the cardinality of matching results. However, current methods for cardinality estimation of subgraph matching fail to fully exploit the structural information in the graph, and moreover, it may potentially result in serious error accumulation. In this light, BoostCard is proposed to aggregate the local structural features via representing neighborhood information of nodes. Meanwhile, it utilizes statistical method to predict whether there is an edge between two nodes. And it adopts the Boosting strategy to compensate globally based on the acquired features of nodes. Hence, it can achieve intelligent cardinality estimation of subgraph matching, making itself a widely applicable framework for the task. In comparison with conventional statistic-based methods, BoostCard offers significant performance gain in the cardinality estimation of multi-node subgraph matching over real-life data sets.

Key words: graph data, subgraph matching, cardinality estimation, Boosting learning

摘要：

由于在建模关联信息方面具备天然优势,图数据已在社交网络、知识表示等方面被广泛运用。但是相较于传统的关系型数据库系统,图数据管理中的以子图匹配为代表的一系列基础操作仍有进一步优化的空间。在一个完善的图数据库系统中,为实现多个子图匹配任务的优化调度,往往需要对每个任务的代价,尤其是匹配结果的基数进行准确预估。然而,现有的子图匹配基数预估方法缺乏对图结构信息的充分考量,且在多结点匹配中存在严重的潜在累计误差。BoostCard方法通过对各结点的邻域信息进行表示,来聚合结点的局部结构特征,同时运用统计方法估计不同结点之间连接成边的概率从而实现匹配基数的初步预测。而后在初期获取的结点结构特征的基础上,采用提升学习的思想对预测结果进行全局补偿,可实现智能化的子图匹配基数估计,是一种具有广泛适用性的子图匹配预测框架。通过实验可知,相比于传统的统计方法,BoostCard在真实数据集的子图匹配基数估计,尤其是多结点子图匹配问题上有明显的性能提升。

关键词: 图数据, 子图匹配, 基数估计, 提升学习

CLC Number:

TP391

HOU Wenzhe, ZHAO Xiang. Subgraph Matching Cardinality Estimation Combining Heuristic and Boosting Method[J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(3): 582-590.

侯文哲, 赵翔. 融合启发式和Boosting的子图匹配基数估计方法[J]. 计算机科学与探索, 2022, 16(3): 582-590.

Figures/Tables 7

Fig.1 Sample of exact subisomorphism

Fig.2 Structural information acquirement

Fig.3 Loss function

Table 1 Estimated r 2 values

方法	Yeast				Human				Random
方法	$n = 2$	$n = 3$	$n = 4$	$n = 5$	$n = 2$	$n = 3$	$n = 4$	$n = 5$	$n = 2$	$n = 3$	$n = 4$	$n = 5$
STAT	0.922	0.392	—	—	0.681	—	—	—	0.924	—	—	—
BoostCard	0.900	0.800	0.663	0.422	0.205	0.175	0.135	0.110	0.895	0.737	0.448	—

Table 1 Estimated r 2 values

方法	Yeast				Human				Random
方法	$n = 2$	$n = 3$	$n = 4$	$n = 5$	$n = 2$	$n = 3$	$n = 4$	$n = 5$	$n = 2$	$n = 3$	$n = 4$	$n = 5$
STAT	0.922	0.392	—	—	0.681	—	—	—	0.924	—	—	—
BoostCard	0.900	0.800	0.663	0.422	0.205	0.175	0.135	0.110	0.895	0.737	0.448	—

Fig.4 Estimation of mean-square error

Table 2 Accuracy of estimation compensation

$δ$	Human		Facebook
$δ$	$n = 2$	$n = 5$	$n = 2$	$n = 5$
0.25	0.851	0.818	0.799	0.762
0.50	0.878	0.856	0.827	0.787
0.75	0.912	0.904	0.856	0.794

Table 2 Accuracy of estimation compensation

$δ$	Human		Facebook
$δ$	$n = 2$	$n = 5$	$n = 2$	$n = 5$
0.25	0.851	0.818	0.799	0.762
0.50	0.878	0.856	0.827	0.787
0.75	0.912	0.904	0.856	0.794

Fig.5 Accuracy and recall of estimation compensation

References 18

[1]	KIPF A, KIPF T, RADKE B, et al. Learned cardinalities: esti-mating correlated joins with deep learning[C]// Proceedings of the 9th Biennial Conference on Innovative Data Systems Research, Asilomar, Jan 13-16, 2019: 1-8.
[2]	KOŁACZKOWSKI P, RYBIŃSKI H. Automatic index selec-tion in RDBMS by exploring query execution plan space[M]// RAS Z W, DARDZINSKA A. Berlin, Heidelberg: Springer, 2009.
[3]	SUN J, LI G L. An end-to-end learning-based cost estimator[J]. Proceedings of the VLDB Endowment, 2019, 13(3): 307-319. DOI URL
[4]	MADUKO A, ANYANWU K, SHETH A P, et al. Graph sum-maries for subgraph frequency estimation[C]// LNCS 5021: Proceedings of the 5th European Semantic Web Conference on Semantic Web: Research and Applications, Tenerife, Jun 1-5, 2008. Berlin, Heidelberg: Springer, 2008: 508-523.
[5]	PARADIES M, VASILYEVA E, MOCAN A, et al. Robust cardinality estimation for subgraph isomorphism queries on property graphs[C]// LNCS 9579: Proceedings of the Biome-dical Data Management and Graph Online Querying, Waiko-loa, Aug 31-Sep 4, 2015. Cham: Springer, 2015: 184-198.
[6]	于静, 刘燕兵, 张宇, 等. 大规模图数据匹配技术综述[J]. 计算机研究与发展, 2015, 52(2): 391-409.
	YU J, LIU Y B, ZHANG Y, et al. Survey on large-scale graph pattern matching[J]. Journal of Computer Research and Development, 2015, 52(2): 391-409.
[7]	ULLMANN J R. An algorithm for subgraph isomorphism[J]. Journal of the ACM, 1976, 23(1): 31-42. DOI URL
[8]	CORDELLA L P, FOGGIA P, SANSONE C, et al. A (sub) graph isomorphism algorithm for matching large graphs[J]. IEEE Transactions on Pattern Analysis and Machine Intelli-gence, 2004, 26(10): 1367-1372.
[9]	ZOU L, CHEN L, YU J X, et al. A novel spectral coding in a large graph database[C]// Proceedings of the 11th Interna-tional Conference on Extending Database Technology, Nantes, Mar 25-29, 2008. New York: ACM, 2008: 181-192.
[10]	ZHAO P X, YU J X, YU P S. Graph indexing: tree + delta <= graph[C]// Proceedings of the 33rd International Conference on Very Large Data Bases, Vienna, Sep 23-27, 2007. New York: ACM, 2007: 938-949.
[11]	SHANG H C, ZHANG Y, LIN X M, et al. Taming verifica-tion hardness: an efficient algorithm for testing subgraph isomorphism[J]. Proceedings of the VLDB Endowment, 2008, 1(1): 364-375. DOI URL
[12]	SHASHA D E, WANG J T L, GIUGNO R. Algorithmics and applications of tree and graph searching[C]// Proceedings of the 21st ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Madison, Jun 3-5, 2002. New York: ACM, 2002: 39-52.
[13]	ZHANG S J, LI S R, YANG J. GADDI: distance index based subgraph matching in biological networks[C]// Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, Saint Peter-sburg, Mar 24-26, 2009. New York: ACM, 2009: 192-203.
[14]	YAN X F, YU P S, HAN J W. Graph indexing: a frequent structure-based approach[C]// Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data, Paris, Jun 13-18, 2004. New York: ACM, 2004: 335-346.
[15]	STOCKER M, SEABORNE A, BERNSTEIN A, et al. SPARQL basic graph pattern optimization using selectivity estimation[C]// Proceedings of the 17th International Conference on World Wide Web, Beijing, Apr 21-25, 2008. New York: ACM, 2008: 595-604.
[16]	NEUMANN T, MOERKOTTE G. Characteristic sets: accu-rate cardinality estimation for RDF queries with multiple joins[C]// Proceedings of the 27th International Conference on Data Engineering, Hannover, Apr 11-16, 2011. Washington: IEEE Computer Society, 2011: 984-994.
[17]	MARCUS R C, PAPAEMMANOUIL O. Plan-structured deep neural network models for query performance prediction[J]. Proceedings of the VLDB Endowment, 2019, 12(11): 2150-8097.
[18]	XIROGIANNOPOULOS K, KHURANA U, DESHPANDE A. GraphGen: exploring interesting graphs in relational data[J]. Proceedings of the VLDB Endowment, 2015, 8(12): 2032-2035. DOI URL

Subgraph Matching Cardinality Estimation Combining Heuristic and Boosting Method

融合启发式和Boosting的子图匹配基数估计方法

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 7

References 18

Related Articles 8

Recommended Articles

Metrics

[1]	HU Zisong, WANG Lizhen, Vanha Tran, ZHOU Lihua. Mining Spatial Prevalent Co-location Patterns Based on Graph Databases [J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(4): 806-821.
[2]	LI Penghui, ZHAI Zhengli, FENG Shu. Research Progress of Adversarial Defenses on Graphs [J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(12): 2292-2303.
[3]	ZHANG Xiaolin, YUAN Haochen, LI Zhuolin, ZHANG Huanxiang, LIU Jiao. Subgraph Matching Oriented Privacy Preserving Method for Social Network [J]. Journal of Frontiers of Computer Science and Technology, 2019, 13(9): 1504-1515.
[4]	LOU Yunkai, WANG Chaokun. Optimization Approach to Subgraph Matching Algorithms Using Community Structure Information [J]. Journal of Frontiers of Computer Science and Technology, 2019, 13(1): 1-22.
[5]	XU Jia, ZHANG Qianzhen, ZHAO Xiang, LV Pin, LI Taoshen. Incremental Pattern Matching Algorithm for Dynamic Graph Based on Structure Decomposition [J]. Journal of Frontiers of Computer Science and Technology, 2018, 12(8): 1214-1224.
[6]	LI Wenpeng, WANG Jianbin, LIN Zeqi, ZHAO Junfeng, ZOU Yanzhen, XIE Bing. Software Knowledge Graph Building Method for Open Source Project [J]. Journal of Frontiers of Computer Science and Technology, 2017, 11(6): 851-862.
[7]	WANG Hongxu, WU Bin, LIU Yang. Parallel Graph Data Analysis System Based on Spark [J]. Journal of Frontiers of Computer Science and Technology, 2015, 9(9): 1066-1074.
[8]	WANG Nan, WANG Bin, LI Xiaohua, YANG Xiaochun. Subgraph Queries over Dynamic Graph Data [J]. Journal of Frontiers of Computer Science and Technology, 2014, 8(2): 139-149.