Spatial prediction estimates unobserved values from spatially distributed observations. Although flexible predictive models are increasingly available, their practical use remains limited when interpretability is essential. In this study, we formulate a graph partitioning problem to construct a global surrogate model that approximates black-box predictions with simpler representations. Specifically, we select connected subgraphs to minimize within-cluster residuals in vertex-level predictions. Although this formulation can be viewed as a variant of spatial regionalization, it operates on model-based predictions at individual locations rather than predefined areal units. With many locations, this point-level formulation may produce artificial connections between regions, reducing interpretability. We therefore introduce a constraint that excludes such connections while retaining flexible partition boundaries. We theoretically analyze how this constraint affects the resulting partition. We also develop a computational procedure for adjusting partition boundaries. Experimental results show that the proposed method yields spatially coherent partitions with flexible boundaries.
Figures & tables
Figure 1: Overview of the proposed approach. Vertex colors represent the predicted values at individual locations. The locations are partitioned into spatially connected regions to approximate the predictions subject to a constraint defined using sublabels.
Figure 2: Example of a bridge-like connection. Two spatially separated regions of beige vertices are connected through intermediate vertices consisting of one blue vertex and three light-blue vertices. Such a connection may be introduced solely to decrease the objective value, but it does not reflect a spatially coherent regional structure.
Figure 3: Illustration of Definition 3.2 . The left and right panels show two independent graph partitioning instances with m=2 . Each square represents a sublabel group. The dashed line indicates the boundary between the brown–beige partition V1(ω) and the blue–sky-blue partition V2(ω) . White and gray squares represent core and boundary groups, respectively. In the left panel, let S denote the bottom-left gray square. Since G[V1(ω)∖(S∩V1(ω))] is disconnected, this assignment violates the condition of Definition 3.2 .
Figure 4: Example of label reassignment. Let n=8,m=2 , and l=3 . This table illustrates how optimal labels are reassigned for the first and third sublabel groups. For the second sublabel group, no reassignment is performed because its assignment in the optimal partition has only a single label.
Figure 5: Spatial partitions produced by our approach with l=30 . For each target variable, we show the trial with the largest value of ∥f−g([1,…,1]⊤;f)∥2 . The leftmost panel depicts the individual predictions f . The second panel presents the piecewise-constant approximation fσ . The remaining panels give the cluster-wise projection g(ω;f) for the resulting partitions. Colors indicate the levels of the predicted values. Colors are scaled separately for each target variable.
Appendix figures & tables5 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 6: Differences between our approach and MIQCP for l=30 . For each target variable, we show the trial with the largest value of ∥f−g([1,…,1]⊤;f)∥2 . The panels highlight the vertices whose assignments differ between the two methods after matching the cluster labels to minimize the number of differing assignments. Highlighted vertices are outlined in black and colored according to their prediction values, while the remaining vertices are shown in gray. Colors are scaled separately for each target variable.
Figure 7: Greedily refined feasible partitions in Ω0 with l=30 . For each target variable, we show the trial with the largest value of ∥f−g([1,…,1]⊤;f)∥2 . The panels show the cluster-wise projection g(ω;f) for the resulting partitions. Vertices whose assignments differ from those obtained by our approach are outlined in black after matching the cluster labels to minimize the number of differing assignments. Colors indicate the levels of the projected values and are scaled separately for each target variable.
Figure 8: Spatial partitions produced by our approach with l=15 . The figure follows the same layout as Figure 5 .
Figure 9: Differences between our approach and MIQCP for l=15 . The figure follows the same layout as Figure 6 .
Figure 10: Greedily refined feasible partitions in Ω0 with l=15 . The figure follows the same layout as Figure 7 .