Embedding-based approximate query for knowledge graph

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.

Keywords

approximate query / knowledge graph / embedding / deep neural network

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.

Funding

The State Grid Technology Project(5108202340042A-1-1-ZN)