|Table of Contents|

[1] Qiu Jingyi, Zhang Duxi, Song Aibo, Wang Honglin Zhang Tianbo, et al. Embedding-based approximate query for knowledge graph [J]. Journal of Southeast University (English Edition), 2024, 40 (4): 417-424. [doi:10.3969/j.issn.1003-7985.2024.04.011]
Copy

Embedding-based approximate query for knowledge graph()
基于嵌入的知识图谱近似查询
Share：

Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]

Volumn:
40
Issue:
2024 4
Page:
417-424
Research Field:
Computer Science and Engineering
Publishing date:
2024-12-03

Info

Title:
Embedding-based approximate query for knowledge graph
基于嵌入的知识图谱近似查询
Author(s):
Qiu Jingyi1;  Zhang Duxi2;  Song Aibo1;  Wang Honglin3 Zhang Tianbo1;  Jin Jiahui1;  Fang Xiaolin1;  Li Yaqi1
1 School of Computer Science and Engineering, Southeast University, Nanjing 211189, China
2 Ningbo Power Supply Co., State Grid Zhejiang Electric Power Co., Ltd., Ningbo 315000, China
3 School of Artificial Intelligence, Nanjing University of Information Science and Technology, Nanjing 210044, China
邱敬怡1;  章杜锡2;  宋爱波1;  王红林3;  张添博1;  金嘉晖1;  方效林1;  李雅琦1
1东南大学计算机科学与工程学院, 南京211189; 2国网浙江省电力有限公司宁波供电公司, 宁波 315000; 3南京信息工程大学人工智能学院, 南京 210044
Keywords:
approximate query;  knowledge graph;  embedding;  deep neural network
近似查询;  知识图谱;  嵌入;  深度神经网络
PACS:
TP392
DOI:
10.3969/j.issn.1003-7985.2024.04.011
Abstract:
To solve the low efficiency of approximate queries caused by the large sizes of the knowledge graphs in the real world, an embedding-based approximate query method is proposed. First, the nodes in the query graph are classified according to the degrees of approximation required for different types of nodes. This classification transforms the query problem into three constraints, from which approximate information is extracted. Second, candidates are generated by calculating the similarity between embeddings. Finally, a deep neural network model is designed, incorporating a loss function based on the high-dimensional ellipsoidal diffusion distance. This model identifies the distance between nodes using their embeddings and constructs a score function. k nodes are returned as the query results. The results show that the proposed method can return both exact results and approximate matching results. On datasets DBLP(DataBase systems and Logic Programming)and FUA-S(Flight USA Airports-Sparse), this method exhibits superior performance in terms of precision and recall, returning results in 0.10 and 0.03 s, respectively. This indicates greater efficiency compared to PathSim and other comparative methods.
为解决现实生活中知识图谱规模庞大而导致近似查询效率低下的问题, 提出了一种基于嵌入的知识图谱近似查询方法.首先对查询图中的节点进行分类, 根据不同类型节点所需的近似程度, 将查询问题转化为3个约束条件, 提取近似信息.然后, 通过计算嵌入之间的相似度, 生成候选集.最后, 设计了一个深度神经网络模型和基于高维椭球形扩散距离的损失函数, 根据嵌入判断节点间距离, 并构建打分函数, 返回k个节点作为查询结果.结果表明, 所提方法可以同时返回精确匹配结果和近似匹配结果.该方法在DBLP和FUA-S两个数据集上均获得了最高的准确率和召回率, 且可分别在0.10和0.03 s内返回结果, 效率高于PathSim等对比方法.

References:

[1] Su Y, Yang S Q, Sun H, et al. Exploiting relevance feedback in knowledge graph search[C]// Proceedings of the 21st ACM Knowledge Discovery and Data Mining. Sydney, Australia, 2015: 1135-1144. DOI:10.1145/2783258.2783320.
[2] Suchanek F M, Kasneci G, Weikum G. YAGO: A large ontology from Wikipedia and WordNet[J]. Journal of Web Semantics, 2008, 6(3): 203-217. DOI: 10.1016/j.websem.2008.06.001.
[3] Liu L H, Chen Y Z, Das M, et al. Knowledge graph question answering with ambiguous query[C]// Proceedings of the 32nd International World Wide Web Conferences. Austin, TX, USA, 2023: 2477-2486. DOI: 10.1145/3543507.3583316.
[4] Li H Y, Zhao M, Yu W Q. A multi-attention RNN-based relation linking approach for question answering over knowledge base[J]. Journal of Southeast University(English Version), 2020, 36(4): 385-392. DOI: 10.3969/j.issn.1003-7985.2020.04.003.
[5] Zhou K, Zhao W X, Bian S Q, et al. Improving conversational recommender systems via knowledge graph based semantic fusion[C]// Proceedings of the 26th ACM Knowledge Discovery and Data Mining. Virtual Event, USA, 2020: 1006-1014. DOI: 10.1145/3394486.3403143.
[6] Wei J Q, Han S, Zou L. VISION-KG: Topic-centric visualization system for summarizing knowledge graph[C]// Proceedings of the 13th International Conference on Web Search and Data Mining. Houston, TX, USA, 2020: 857-860. DOI: 10.1145/3336191.3371863.
[7] Arenas M, Cuenca Grau B, Kharlamov E, et al. Faceted search over RDF-based knowledge graphs[J]. Journal of Web Semantics, 2016, 37/38: 55-74. DOI: 10.1016/j.websem.2015.12.002.
[8] Mailis T, Kotidis Y, Nikolopoulos V, et al. An efficient index for RDF query containment[C]//Proceedings of the 2019 International Conference on Management of Data. Amsterdam, the Netherlands, 2019: 1499-1516. DOI: 10.1145/3299869.3319864.
[9] Abdelaziz I, Harbi R, Khayyat Z, et al. A survey and experimental comparison of distributed SPARQL engines for very large RDF data[J]. Proceedings of the VLDB Endowment, 2017, 10(13): 2049-2060. DOI: 10.14778/3151106.3151109.
[10] Zeng J, U L H, Yan X, et al. Fast core-based top-k frequent pattern discovery in knowledge graphs[C]// Proceedings of the 37th IEEE International Conference on Data Engineering. Chania, Greece, 2021: 936-947. DOI: 10.1109/ICDE51399.2021.00086.
[11] Sun Y Z, Han J W, Yan X F, et al. Pathsim: Meta path-based top-k similarity search in heterogeneous information networks[C]// Proceedings of the VLDB Endowment. Seattle, WA, USA, 2011: 992-1003. DOI: 10.14778/3402707.3402736.
[12] Yang S Q, Han F Q, Wu Y H, et al. Fast top-k search in knowledge graphs[C]// Proceedings of the 32nd IEEE International Conference on Data Engineering. Helsinki, Finland, 2016: 990-1001. DOI: 10.1109/ICDE.2016.7498307.
[13] Wang Y X, Khan A, Wu T X, et al. Semantic guided and response times bounded top-k similarity search over knowledge graphs[C]// Proceedings of the 36th IEEE International Conference on Data Engineering. Dallas, TX, USA, 2020: 445-456. DOI: 10.1109/ICDE48307.2020.00045.
[14] Qin Z Y, Bai Y S, Sun Y Z. GHashing: Semantic graph hashing for approximate similarity search in graph databases[C]// Proceedings of the 26th ACM Knowledge Discovery and Data Mining. Virtual Event, USA, 2020: 2062-2072. DOI: 10.1145/3394486.3403257.
[15] Biao Y, Lin G Y, Zhang W G. Adaptive topology learning of camera network across non-overlapping views[J]. Journal of Southeast University(English Version), 2015, 31(1): 61-66. DOI: 10.3969/j.issn.1003-7985.2015.01.011.
[16] Zhao N N, Jiang R. Poisoning attack detection scheme based on data integrity sampling audit algorithm in neural network[J]. Journal of Southeast University(English Version), 2023, 39(3): 314-322. DOI: 10.3969/j.issn.1003-7985.2023.03.012.
[17] Wang Y H, He J Z, Zhang M Z, et al. Concrete crack identification in complex environments based on SSD and pruning neural network[J]. Journal of Southeast University(English Version), 2023, 39(4): 393-399. DOI: 10.3969/j.issn.1003-7985.2023.04.008.
[18] Han M, Kim H, Gu G, et al. Efficient subgraph matching: Harmonizing dynamic programming, adaptive matching order, and failing set together[C]// Proceedings of the 2019 ACM Conference on Management of Data. Amsterdam, the Netherlands, 2019: 1429-1446. DOI: 10.1145/3299869.3319880.
[19] Chen S W. Graph embedding [EB/OL].(2022)[2023-12-08]. https://github.com/shenweichen/GraphEmbedding.
[20] Khan A, Wu Y H, Aggarwal C C, et al. Nema: Fast graph search with label similarity[C]// Proceedings of the VLDB Endowment. Riva del Garda, Italy, 2013: 181-192. DOI: 10.14778/2535569.2448952.
[21] 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 Intelligence, 2004, 26(10): 1367-1372. DOI: 10.1109/TPAMI.2004.75.
[22] Kim H J, Choi Y Y, Park K S, et al. Versatile equivalences: Speeding up subgraph query processing and subgraph matching[C]// Proceedings of the 2021 ACM Conference on Management of Data. Virtual Event, China, 2021: 925-937. DOI: 10.1145/3448016.3457265.

Memo

Memo:
Biographies: Qiu Jingyi(1996—), female, Ph.D. candidate; Song Aibo(corresponding author), male, doctor, professor, absong@seu.edu.cn.
Foundation item: The State Grid Technology Project(No. 5108202340042A-1-1-ZN).
Citation: Qiu Jingyi, Zhang Duxi, Song Aibo, et al.Embedding-based approximate query for knowledge graph[J].Journal of Southeast University(English Edition), 2024, 40(4):417-424.DOI:10.3969/j.issn.1003-7985.2024.04.011.
Last Update: 2024-12-20