Spatial prediction refers to the estimation of unobserved values from spatially distributed observations. Although recent advances have improved the capacity to model diverse observation types, adoption in practice remains limited in industries that demand interpretability. To mitigate this gap, surrogate models that explain black-box predictors provide a promising path toward interpretable decision making. In this study, we propose a graph partitioning problem to construct spatial segments that minimize the sum of within-segment variances of individual predictions. The assignment of data points to segments can be formulated as a mixed-integer quadratic programming problem. While this formulation potentially enables the identification of exact segments, its computational complexity becomes prohibitive as the number of data points increases. Motivated by this challenge, we develop an approximation scheme that leverages the structural properties of graph partitioning. Experimental results demonstrate the computational efficiency of this approximation in identifying spatial segments.
Figures & tables
Figure 1: Overview of our approach. Data points are grouped through graph partitioning, which is formulated as an MIQP problem. This formulation is approximated, with a performance guarantee, by aggregating nearby data points in advance. The color at each vertex represents the magnitude of the individual predictions. The dashed boxes in the middle figure indicate the aggregation units.
Figure 2: Example of constraint 4.1 . Let V be the collection of vertex sets that induce connected subgraphs whose vertices share the same color. Without imposing the constraint characterized by V , the beige vertex sets remain connected via one blue and three light blue vertices. However, once a blue or light blue vertex set in V is removed, this connection is broken.
Figure 3: Example of prior aggregation. Let n=8,m=2 , and l=3 . The upper table, which corresponds to assumption 5.2 , illustrates how labels are reassigned for the first and third groups of data points sharing the same sublabel. For the second group, no replacement is performed because its assignment in the optimal solution has only a single label. The lower table shows the relationship between the entries of η and η~ .
Figure 4: Examples of violations of assumption 5.7 and assumption 5.8 . Each square represents a group of data points that share the same sublabel. Gray regions highlight the violation of the assumptions. Unconnected vertices in the original undirected graph violate assumption 5.7 . Additionally, assumption 5.8 is violated when the removal of vertices in the gray square with multiple labels causes a connected component in the optimal solution to become disconnected.
Figure 5: Spatial segments obtained through connected graph partitioning using the MIQP formulation. For each target variable, the result of the trial with the largest total sum of squares is displayed. The leftmost panel presents individual predictions η from Gaussian process regression. The second panel displays approximate predictions η~ from the prior aggregation. The remaining panels show segmentations with m∈{2,3,4} clusters. Colors indicate the levels of the predicted values.