# Dual Clustering-Based Method for Geospatial Knowledge Graph Partitioning
###### Abstract
Local search partitioning algorithms optimize the initial partitioning based on local graph information. These algorithms can be classified into three categories: unit or group movement, label propagation partitioning algorithms, and neighborhood expansion-based partitioning algorithms. Algorithms based on unit or group movement aim to reduce edge cuts by moving units or groups between partitions to optimize the initial partitioning (e.g., KL algorithm [26], FM algorithm [35], and JA-BE-JA-VC algorithm [36]). However, the act of exchanging individual vertices or edges between partitions is prone to getting stuck in local optima [37; 38; 39; 40; 41]. To solve this problem, vertex group movement methods have been further developed [37; 38]. These methods first detect vertex groups at partition boundaries, and then move these vertex groups based on movement gain and partition load to improve partition quality [40; 41]. Label propagation-based partitioning algorithms randomly assign each node a label, and then iteratively update the labels under the constraint of balancing computational load between partitions [42; 43]. The label of a node is updated to the most frequent label among its adjacent vertices. This update process continues until there are no label changes and loads of partitions are balanced [44; 45; 46]. Neighborhood expansion-based partitioning algorithms [27; 47; 48] first select seed points to form a core set, and then iteratively select appropriate vertices from the boundary set to join the core set. The boundary set is iteratively updated until the threshold of computational load is reached. Based on the above reviews, one can find that the aforementioned methods only rely on the graph structure for partitioning and neglect the spatial relationship between entities. In the application of geospatial knowledge graphs (e.g., geographic knowledge recommendation and geographic data analysis), a spatial query is frequently required [49; 50]. In Figure 1, we use a practical example to show the disadvantage of existing non-spatial graph partitioning methods. Different partitions are labeled by the color of nodes (orange and purple). Spatial queries are represented by orange and blue shadows. When a spatial relationship is neglected (Figure 1a), the two spatial queries need to run across partitions. The network communication between partitions will result in the increase in query response time. In contrast, when a spatial relationship is considered to produce partitions (Figure 1b), the two spatial queries can run in a single partition. To improve the efficiency of a spatial query in large-scale geospatial knowledge graphs, spatial relationships between entities must be considered in the partitioning of geospatial knowledge graphs [50; 51]. Existing partitioning methods that disregard spatial relationships may lead to spatially adjacent entities being assigned to different partitions, negatively affecting spatial query performance. To address this issue, we treat the partitioning of geospatial knowledge graphs as a special spatial clustering problem and develop a dual clustering-based method for geospatial knowledge graph partitioning (GKGP-DC). GKGP-DC incorporates the constraints of spatial relationships between entity nodes into the optimization objective of graph partitioning.