# Dual Clustering-Based Method for Geospatial Knowledge Graph Partitioning
###### Abstract  
Geospatial knowledge graphs provide critical technology for integrating geographic information and semantic knowledge, which are very useful for geographic data analysis. As the scale of geospatial knowledge graphs continues to grow, the distributed management of geospatial knowledge graphs is becoming an inevitable requirement. Geospatial knowledge graph partitioning is the core technology for the distributed management of geospatial knowledge graphs. To support geographic data analysis, spatial relationships between entities should be considered in the application of geospatial knowledge graphs. However, existing knowledge graph partitioning methods overlook the spatial relationships between entities, resulting in the low efficiency of spatial queries. To address this issue, this study proposes a geospatial knowledge graph partitioning method based on dual clustering which performs two different clustering methods step by step. First, the density peak clustering method (DPC) is used to cluster geographic nodes. The nodes within each cluster are merged into a super-node. Then, we use an efficient graph clustering method (i.e., Leiden) to identify the community structure of the graph. Nodes belonging to the same community are further merged to reduce the size of the graph. Finally, partitioning operations are performed on the compressed graph based on the idea of the Linear-Weighted Deterministic Greedy Policy (LDG). We construct a geospatial knowledge graph based on YAGO3 to evaluate the performance of the proposed graph partitioning method. The experimental results show that the proposed method outperforms ten comparison methods in terms of graph partitioning quality and spatial query efficiency. 2024202024202420242024202420242024202024202420202420242020242024202420242020  
graphs, standalone management methods can no longer meet current demands [5]. Distributed management is becoming an inevitable requirement. The partitioning of geospatial knowledge graphs is an essential task in large-scale knowledge graph management, which partitions a data graph into several subgraphs which are stored on different distributed cluster nodes [6]. Geospatial knowledge graph partitioning provides the foundational support for the distributed storage, management, querying, and reasoning of geospatial knowledge graphs. When executing a distributed query, the query is first decomposed into several subqueries based on the partitioning result. Then, the subqueries are assigned to various cluster nodes to obtain partial solutions. Finally, the results of the subqueries are connected to produce the final solution. The efficiency of query is highly relevant to the partitioning results. The more partitions passed during the query, the slower the query is. Currently, knowledge graph partitioning is generally regarded as a graph partitioning problem. The optimization goals of node/edge partitioning strategies are (i) minimizing the number of cross-partition edges (cut edges) or nodes that have been duplicated in different partitions (replicated node) and (ii) ensuring balanced node or edge counts within each partition [7]. Minimizing the number of cut edges or replicated vertices aims to reduce network communication costs between cluster nodes in a distributed environment. Meanwhile, balancing the number of nodes or edges within each partition prevents the formation of computational hotspots and avoids excessive differences in processing capabilities. The graph partitioning problem is a well-known NP-hard problem [8; 9], and no polynomial-time algorithm has been found to solve it thus far. Therefore, existing work has focused on finding approximate partitioning solutions rather than optimal ones [10; 11]. Currently, according to different graph loading methods, existing graph partitioning algorithms can be categorized into streaming partitioning algorithms and offline partitioning algorithms.