Surrogate Graph Partitioning for Spatial Prediction

Yuta Shikuri, Hironori FujisawaarXiv 2025 · DOI · arXiv

Introduction

Spatial prediction models, such as Gaussian Processes, are essential for managing natural hazards and assessing insurance risks. However, these models often function as "black boxes," providing high-accuracy predictions without the high-level, interpretable "risk maps" required by regulators and human auditors. This paper proposes a method to bridge this gap by partitioning complex spatial predictions into a small number of contiguous, homogeneous segments.

The Challenge of Spatial Interpretability

Existing surrogate modeling techniques, like decision trees, often fail to respect geographical constraints. They can produce "islands" of risk or fail to capture complex spatial features like coastlines. The goal is to find a surrogate model that groups individual predictions into $m$ spatially contiguous segments that are internally consistent while maintaining high predictive accuracy.

Methodology: Surrogate Graph Partitioning

The authors introduce a Surrogate Graph Partitioning framework that treats spatial data points as vertices in a graph, with edges representing geographical proximity.

Overview of the Surrogate Graph Partitioning workflow, from initial graph representation to prior aggregation and final partitioning.

Mixed-Integer Quadratic Programming (MIQP)

The partitioning problem is formulated as an MIQP, aiming to minimize the variance of predictions within each segment. This formulation allows for mathematically exact solutions, ensuring that the resulting segments are optimal for the given constraints.

Connectivity and Interpretability

To ensure interpretability, the model enforces a "connected graph partitioning" constraint. This prevents the grouping of geographically distant areas solely based on similar predicted values, ensuring that each segment represents a single, continuous region on a map.

Scaling via Prior Aggregation

Solving MIQP for large datasets is computationally expensive. To address this, the authors propose Prior Aggregation. This preprocessing step groups nearby, similar points into "sublabels" before the global optimization phase.

The prior aggregation step groups local nodes into sublabels to reduce the complexity of the global MIQP problem.

Theorem 5.4 in the paper provides a theoretical guarantee that this approximation remains close to the optimal solution, significantly reducing computation time without a major loss in accuracy.

Experimental Evaluation

The method was tested on two significant spatial datasets:

  1. California Housing: Predicting price and income across 20,640 locations.
  2. National Risk Index: Predicting annual loss rates for agriculture and buildings in the Southeastern US (17,754 samples).

The scalability was further tested by resampling $10^5$ prediction points.

Key Results

The Graph + MIQP approach demonstrated clear advantages over traditional tree-based surrogates:

  • Accuracy: In the building risk dataset ($m=3$), the graph-based approach achieved an error rate of 48.6%, compared to 76.1% for the tree-based baseline.
  • Visual Fidelity: The model successfully identified complex spatial structures, such as coastal high-risk zones, which are often obscured by global surrogate models.
  • Efficiency: Prior aggregation enabled the model to process large datasets in under 100 seconds, making the MIQP approach practical for real-world applications.

Conclusion and Future Work

This research provides a robust framework for creating interpretable spatial surrogates. While the current MIQP approach scales well with prior aggregation, future work will focus on narrowing the gap between approximate and optimal solutions and extending the framework to handle even more irregular spatial distributions.

Summary updated

BibTeX
@misc{shikuri2025surrogate,
  author = {Yuta Shikuri and Hironori Fujisawa},
  title = {{Surrogate Graph Partitioning for Spatial Prediction}},
  year = {2025},
  eprint = {2510.07832},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2510.07832},
}
Figure