# Dual Clustering-Based Method for Geospatial Knowledge Graph Partitioning
###### Abstract
Streaming graph partitioning algorithms load edges or nodes into a data stream according to certain rules (such as random-order, depth-first, or breadth-first traversal) and partition only one node or one edge at a time [12]. The hash partitioning method is the simplest streaming graph partitioning technique. It calculates a hash value based on the reading order or globally unique ID of vertices or edges and assigns vertices or edges with equal hash values to the same partition. Hash-based graph partitioning is nearly a random partitioning method, which leads to significant communication costs [13]. [PERSON] et al. (2014) proposed the DBH (Degree-Based Hashing) algorithm, which improves upon the hash algorithm by prioritizing the partitioning of higher-degree vertices to enhance partitioning quality [14]. Degree-Based Hashing (DBH) is a hashing method that takes edges as input. For the nodes of an edge, it leverages the degree information of two nodes. Then, DBH replicates the node with a higher degree and assigns the edge according to the hash value of the node with a lower degree. However, the partitioning algorithms mentioned above do not consider historical partitioning information and have a certain level of randomness, resulting in a large number of cut edges or replicated vertices. This disadvantage leads to substantial communication costs. To solve this problem, many scholars have taken historical partitioning information into account. These algorithms establish a scoring function between the current data and each previously partitioned subgraph. When a new edge or vertex is loaded into the data stream, the partition is assigned based on the scoring function (e.g., Greedy algorithm [15], FENNEL (streaming edge-cut neural network for efficient graph partitioning) algorithm [16], HDRF (High-Degree Replicated First) algorithm [17] and Skewness-aware Vertex-cut Partitioner [18]). For instance, HDRF is an improved method of DBH. Instead of using the degrees of the nodes, HDRF constructs a score function based on the number of subgraph neighbors in the historical partition and computational load. The input edge will be assigned to the partition with the highest score. However, the above traditional streaming partitioning algorithms neglect the global structure of the graph and may fall into local optima. Researchers have introduced sliding window or buffer techniques to alleviate these limitations. These methods first load the data into a window or buffer to increase the number of candidate nodes/edges in one assignment, and then choose the best node/edge from the candidates for assignment to a partition [19; 20; 21; 22; 23]. Streaming graph partitioning algorithms are usually efficient, typically requiring only a single pass over the graph data to complete the partitioning. However, it is hard to capture the global structures of graphs with streaming partitioning algorithms, which usually lead to low-quality partitions [21]. Offline partitioning algorithms load the complete graph data into memory before partitioning. These algorithms can be further categorized into global and local search partitioning algorithms. Global search partitioning algorithms directly consider the global information of the entire graph to produce a partition. For instance, spectral partitioning methods calculate the eigenvector corresponding to the second-smallest eigenvalue of the graph's Laplacian matrix and recursively bisect the graph until the partitioning goal is achieved [24]. The time complexity of spectral partitioning is too high to partition large-scale graphs. Multilevel partitioning algorithms [25; 26; 27; 28; 29; 30; 31] were further proposed to address this problem. Multilevel partitioning algorithms first coarsen a large graph into a smaller graph. Then, they apply a partitioning strategy (such as spectral partitioning [32], KL algorithm [33], or Greedy Graph Growth algorithm [34]) to the small graph. Finally, the partition is projected back onto the original large graph with further refinement.