IOAH3: Importance-Driven Adaptive Spatial Partitioning

# Importance-Driven Adaptive Spatial Partitioning via Graph-Cut Optimisation over H3 Hierarchical Grids
Source: [https://arxiv.org/html/2606.18280](https://arxiv.org/html/2606.18280)
Ehsaneddin Jalilian GeoSocial Artificial Intelligence, Interdisciplinary Transformation University Austria ehsaneddin\.jalilian@it\-u\.at

###### Abstract

We present IOAH3 \(Importance\-Oriented Adaptive H3 partitioning\), a computational method for constructing data\-driven spatial partitions of geo\-referenced observation domains\. Standard approaches to spatial aggregation adopt fixed areal units, such as administrative boundaries or uniform hexagonal grids at a single resolution, without regard to the informational content of the underlying observations in each region\. This leads to the well\-known modifiable areal unit problem: statistical and inferential results depend on the arbitrary choice of partition, and spatially concentrated phenomena are averaged out in coarse cells that obscure fine\-scale structure\. IOAH3 addresses this by constructing an adaptive partition in three stages: multi\-source feature extraction and importance scoring via principal component analysis over road density, POI density, building density, and terrain roughness signals, with population and flood\-hazard data entering as auxiliary inputs to cell filtering and spatial smoothness; spatial cell selection via Markov Random Field graph\-cut optimisation, which jointly maximises per\-cell importance while enforcing spatial contiguity; and data\-driven hierarchical refinement of high\-importance regions to finer H3 resolution levels, with neighbour\-propagated support to avoid isolated fine\-resolution islands\. The resulting partitions serve as input to spatial inference pipelines and provide a principled resolution of the partition\-sensitivity problem prior to any modelling step\. Code is available at[https://github\.com/EhsaneddinJalilian/IoaH3](https://github.com/EhsaneddinJalilian/IoaH3)\.

## 1Introduction

Spatial inference systems that operate on geo\-referenced data must first aggregate raw observations into discrete areal units before any modelling step can be applied\. The choice of those units is consequential: coarse cells suppress within\-cell variation, fine cells may be data\-sparse, and neither uniform grid nor administrative boundary systems are designed to align with the spatial structure of the phenomenon under study\. This sensitivity, the modifiable areal unit problem \(MAUP\)\(Openshaw,[1984](https://arxiv.org/html/2606.18280#bib.bib5)\), is well\-documented in the spatial statistics literature, yet in practice most GeoAI pipelines adopt a fixed resolution without examination\.

The problem is not merely statistical\. When the areal partition is too coarse relative to the scale at which a spatial phenomenon varies, the aggregation operator irreversibly destroys signal\. No downstream model, however sophisticated, can recover variation that was never present in its input\. This observation motivates a prior step: constructing the partition itself in a principled, data\-driven way that aligns cell boundaries with the spatial structure of the observations\.

IOAH3 is a method for this prior step\. It takes multi\-source raster and vector observations over a geographic domain and produces an adaptive H3 hexagonal partition whose resolution varies spatially according to the estimated importance of each region\. The method combines three independently motivated components: unsupervised importance scoring via PCA over heterogeneous feature signals, spatial cell selection via graph\-cut optimisation over a Markov Random Field \(MRF\) encoding both per\-cell importance and spatial contiguity, and data\-driven hierarchical refinement of selected cells to finer H3 resolution levels with neighbour\-propagated support\.

The remainder of this document is structured as follows\. Section[2](https://arxiv.org/html/2606.18280#S2)provides background on H3 hierarchical grids and MRF graph\-cut optimisation\. Section[3](https://arxiv.org/html/2606.18280#S3)describes the three\-stage IOAH3 pipeline in detail\. Section[4](https://arxiv.org/html/2606.18280#S4)gives implementation and Computational Complexity\. Section[5](https://arxiv.org/html/2606.18280#S5)discusses the method and limitations\.

## 2Background

### 2\.1H3 Hierarchical Hexagonal Grids

H3\(Brodsky,[2018](https://arxiv.org/html/2606.18280#bib.bib4)\)is a hierarchical discrete global grid system that tessellates the Earth’s surface using hexagonal cells at 16 resolution levels\. At resolutionrr, each cell covers approximatelyArA\_\{r\}km2, whereArA\_\{r\}decreases by a factor of roughly 7 with each increment inrr\. Key resolution levels relevant to this work are given in Table[1](https://arxiv.org/html/2606.18280#S2.T1)\.

Table 1:H3 resolution levels used in IOAH3\.H3 cells have the property that each cell at resolutionrris exactly contained within one cell at resolutionr−1r\-1, forming a strict hierarchy\. This makes hierarchical refinement, replacing a coarse cell with its seven child cells at the next resolution, geometrically exact and computationally inexpensive\.

### 2\.2Markov Random Fields and Graph\-Cut Optimisation

A Markov Random Field \(MRF\) over a set of sites𝒱\\mathcal\{V\}with neighbourhood structureℰ\\mathcal\{E\}is a probability model of the form

P​\(𝐱\)∝exp⁡\(−∑i∈𝒱ψi​\(xi\)−λ​∑\(i,j\)∈ℰϕi​j​\(xi,xj\)\),P\(\\mathbf\{x\}\)\\propto\\exp\\\!\\left\(\-\\sum\_\{i\\in\\mathcal\{V\}\}\\psi\_\{i\}\(x\_\{i\}\)\-\\lambda\\sum\_\{\(i,j\)\\in\\mathcal\{E\}\}\\phi\_\{ij\}\(x\_\{i\},x\_\{j\}\)\\right\),\(1\)whereψi\\psi\_\{i\}are unary potentials encoding per\-site preferences andϕi​j\\phi\_\{ij\}are pairwise potentials encoding smoothness over adjacent sites\. For binary labellingsxi∈\{0,1\}x\_\{i\}\\in\\\{0,1\\\}\(included / excluded\) and submodular pairwise terms, the MAP estimate of \([1](https://arxiv.org/html/2606.18280#S2.E1)\) can be computed exactly in polynomial time via the max\-flow / min\-cut duality\(Boykov and Kolmogorov,[2004](https://arxiv.org/html/2606.18280#bib.bib1); Kolmogorov and Zabih,[2004](https://arxiv.org/html/2606.18280#bib.bib2)\)\. The resulting cut minimises a weighted combination of unary dissatisfaction and pairwise discontinuity, producing a labelling that is simultaneously consistent with per\-site importance and spatially coherent\.

## 3Method

### 3\.1Stage 1: Feature Extraction and Importance Scoring

Letℋr\\mathcal\{H\}\_\{r\}denote the set of H3 cells covering the domainΩ\\Omegaat base resolutionrr\. For each cellh∈ℋrh\\in\\mathcal\{H\}\_\{r\}, IOAH3 extracts a feature vector𝐟​\(h\)∈ℝd\\mathbf\{f\}\(h\)\\in\\mathbb\{R\}^\{d\}aggregating the following information sources:

- •Road densityρroad​\(h\)\\rho\_\{\\text\{road\}\}\(h\): count of OSM road segments of class motorway, trunk, primary, secondary, tertiary, unclassified, or residential whose nodes fall withinhh, normalised by cell area\.
- •POI densityρpoi​\(h\)\\rho\_\{\\text\{poi\}\}\(h\): count of OSM point\-of\-interest nodes \(amenity or shop tags\) withinhh, normalised by cell area\.
- •Building densityρbldg​\(h\)\\rho\_\{\\text\{bldg\}\}\(h\): count of OSM building footprint nodes withinhh, normalised by cell area\.
- •Elevation roughnessσz​\(h\)\\sigma\_\{z\}\(h\): mean gradient magnitude withinhh, computed at the native DEM resolution \(10 m Lambert projection\) as‖∇z‖=\(∂z/∂x\)2\+\(∂z/∂y\)2\\\|\\nabla z\\\|=\\sqrt\{\(\\partial z/\\partial x\)^\{2\}\+\(\\partial z/\\partial y\)^\{2\}\}\. The value then is averaged over sampled pixels mapped to each H3 cell\. This captures terrain ruggedness, a stronger predictor of infrastructural and hazard importance than mean elevation\.
- •Population countp​\(h\)p\(h\): total resident population withinhh, aggregated\. Population is not included in the PCA feature set\. It enters the pipeline as: \(i\) a pre\-filtering criterion \(cells with zero population, no infrastructure, and negligible hazard are dropped before PCA\); and \(ii\) an input to the MRF pairwise smoothness weight alongside flood\-hazard probability \(see Section[3\.2](https://arxiv.org/html/2606.18280#S3.SS2)\)\.
- •Flood\-hazard probabilityη​\(h\)\\eta\(h\): mean flood\-hazard probability withinhh, aggregated by mean from a flood\-probability raster\. Like population, hazard does not enter the PCA feature set but serves as a pre\-filtering criterion and as a pairwise smoothness input in Stage 2\.

The first four signals \(road density, POI density, building density, elevation roughness;d=4d=4\) form the PCA feature matrix\. They are standardised to zero mean and unit variance, then reduced to a single importance score via principal component analysis:

s​\(h\)=normalise​\(𝐰⊤​𝐟~​\(h\)\)∈\[0,1\],s\(h\)=\\mathrm\{normalise\}\\\!\\left\(\\mathbf\{w\}^\{\\top\}\\tilde\{\\mathbf\{f\}\}\(h\)\\right\)\\in\[0,1\],\(2\)where𝐰\\mathbf\{w\}is the first principal component loading vector and𝐟~​\(h\)\\tilde\{\\mathbf\{f\}\}\(h\)is the standardised feature vector\. The normalisation mapss​\(h\)s\(h\)to\[0,1\]\[0,1\]by min\-max scaling across all cells\. This score is data\-driven and parameter\-free: no manual weighting of features is required\.

### 3\.2Stage 2: Graph\-Cut Cell Selection

Given the importance scores\{s​\(h\)\}h∈ℋr\\\{s\(h\)\\\}\_\{h\\in\\mathcal\{H\}\_\{r\}\}, IOAH3 constructs an MRF over the H3 grid and solves for the binary labellingℓ:ℋr→\{0,1\}\\ell:\\mathcal\{H\}\_\{r\}\\to\\\{0,1\\\}\(included / excluded\) that minimises

E​\(ℓ\)=∑h∈ℋrψh​\(ℓh\)\+λ​∑\(h,h′\)∈ℰϕh​h′​\(ℓh,ℓh′\),E\(\\ell\)=\\sum\_\{h\\in\\mathcal\{H\}\_\{r\}\}\\psi\_\{h\}\(\\ell\_\{h\}\)\+\\lambda\\sum\_\{\(h,h^\{\\prime\}\)\\in\\mathcal\{E\}\}\\phi\_\{hh^\{\\prime\}\}\(\\ell\_\{h\},\\ell\_\{h^\{\\prime\}\}\),\(3\)
where the unary termψh​\(0\)=1−s​\(h\)\\psi\_\{h\}\(0\)=1\-s\(h\)\(cost of including a low\-importance cell\) andψh​\(1\)=0\\psi\_\{h\}\(1\)=0\(no cost for excluding any cell\)\. The pairwise termϕh​h′​\(ℓh,ℓh′\)=𝟏​\[ℓh≠ℓh′\]⋅wh​h′\\phi\_\{hh^\{\\prime\}\}\(\\ell\_\{h\},\\ell\_\{h^\{\\prime\}\}\)=\\mathbf\{1\}\[\\ell\_\{h\}\\neq\\ell\_\{h^\{\\prime\}\}\]\\cdot w\_\{hh^\{\\prime\}\}, where the smoothness weight is

wh​h′=e−\(\|p​\(h\)−p​\(h′\)\|\+\|η​\(h\)−η​\(h′\)\|\),w\_\{hh^\{\\prime\}\}=e^\{\-\\left\(\|p\(h\)\-p\(h^\{\\prime\}\)\|\+\|\\eta\(h\)\-\\eta\(h^\{\\prime\}\)\|\\right\)\},\(4\)withp​\(h\)p\(h\)the raw population count andη​\(h\)\\eta\(h\)the raw hazard value of cellhh\. Raw \(un\-normalised\) values are used directly; the exponential suppresses the weight when adjacent cells differ strongly in population or hazard, regardless of absolute scale\.ℰ\\mathcal\{E\}is the H3 k\-ring\-1 adjacency graph \(each cell connected to its six hexagonal neighbours\)\.λ=1\.0\\lambda=1\.0controls the smoothness\-importance trade\-off\.

The energy \([3](https://arxiv.org/html/2606.18280#S3.E3)\) is submodular in the pairwise terms \(sincewh​h′≥0w\_\{hh^\{\\prime\}\}\\geq 0\) and is therefore minimised exactly by max\-flow / min\-cut using\(Boykov and Kolmogorov,[2004](https://arxiv.org/html/2606.18280#bib.bib1)\)\.

###### Proposition 1\.

The pairwise term \([4](https://arxiv.org/html/2606.18280#S3.E4)\) is submodular for allwh​h′≥0w\_\{hh^\{\\prime\}\}\\geq 0, and the total energy \([3](https://arxiv.org/html/2606.18280#S3.E3)\) admits an exact minimum\-cut solution\.

###### Proof\.

Submodularity of the termϕh​h′\\phi\_\{hh^\{\\prime\}\}follows directly fromwh​h′≥0w\_\{hh^\{\\prime\}\}\\geq 0and the standard Potts model construction\. The result then follows fromKolmogorov and Zabih \([2004](https://arxiv.org/html/2606.18280#bib.bib2)\), Theorem 1\. ∎

After optimisation, cells withℓh=0\\ell\_\{h\}=0are marked*included*; cells withℓh=1\\ell\_\{h\}=1are marked*excluded*and retained as background context\. An additional connectivity filter removes included cells with fewer than one included neighbour, preventing isolated singleton inclusions\.

### 3\.3Stage 3: Adaptive Hierarchical Refinement

Included cells are refined to finer H3 resolutions based on their importance score\. Letq40,q65,q80q\_\{40\},q\_\{65\},q\_\{80\}denote the 40th, 65th, and 80th percentiles of\{s​\(h\):ℓh=0\}\\\{s\(h\):\\ell\_\{h\}=0\\\}\. The target resolution for cellhhis

r∗​\(h\)=\{rmaxif​s​\(h\)\>q80,9if​q65<s​\(h\)≤q80,r0otherwise,r^\{\*\}\(h\)=\\begin\{cases\}r\_\{\\max\}&\\text\{if \}s\(h\)\>q\_\{80\},\\\\ 9&\\text\{if \}q\_\{65\}<s\(h\)\\leq q\_\{80\},\\\\ r\_\{0\}&\\text\{otherwise\},\\end\{cases\}\(5\)
wherer0=7r\_\{0\}=7is the base resolution andrmax=10r\_\{\\max\}=10is the maximum refinement resolution\.

Critically, refinement is spatially propagated: for every cellhhwithr∗​\(h\)\>r0r^\{\*\}\(h\)\>r\_\{0\}, all H3 k\-ring\-1 neighbours ofhhare also promoted to at leastr∗​\(h\)r^\{\*\}\(h\)\. This ensures contiguous fine\-resolution zones rather than isolated fine cells surrounded by coarse cells, which would create discontinuous partition boundaries\.

Each cellhhwith target resolutionr∗\>r0r^\{\*\}\>r\_\{0\}is replaced by its7r∗−r07^\{r^\{\*\}\-r\_\{0\}\}H3 children at resolutionr∗r^\{\*\}\. Feature values for child cells are sampled from fine\-resolution rasters pre\-loaded once before the refinement loop\. Pseudocode for the full pipeline is given in Algorithm[1](https://arxiv.org/html/2606.18280#alg1)\.

Algorithm 1IOAH3: Importance\-Driven Adaptive H3 Partitioning1:Raster layers

ℛ\\mathcal\{R\}, OSM vector data

𝒱\\mathcal\{V\}, base resolution

r0r\_\{0\}, max resolution

rmaxr\_\{\\max\}
2:Adaptive partition

𝒫\\mathcal\{P\}with per\-cell resolution and features

3:Extract per\-cell features

𝐟​\(h\)\\mathbf\{f\}\(h\)for all

h∈ℋr0h\\in\\mathcal\{H\}\_\{r\_\{0\}\}from

ℛ\\mathcal\{R\}and

𝒱\\mathcal\{V\}
4:Compute importance scores

s​\(h\)←PCA1​\(𝐟​\(h\)\)s\(h\)\\leftarrow\\mathrm\{PCA\}\_\{1\}\(\\mathbf\{f\}\(h\)\)via \([2](https://arxiv.org/html/2606.18280#S3.E2)\)

5:Construct MRF graph

G=\(ℋr0,ℰ\)G=\(\\mathcal\{H\}\_\{r\_\{0\}\},\\mathcal\{E\}\)with unary and pairwise terms per \([3](https://arxiv.org/html/2606.18280#S3.E3)\)–\([4](https://arxiv.org/html/2606.18280#S3.E4)\)

6:Solve

ℓ∗←arg⁡minℓ⁡E​\(ℓ\)\\ell^\{\*\}\\leftarrow\\arg\\min\_\{\\ell\}E\(\\ell\)via max\-flow / min\-cut

7:Connectivity filter:for each

hhwith

ℓh∗=0\\ell^\{\*\}\_\{h\}=0, set

ℓh∗←1\\ell^\{\*\}\_\{h\}\\leftarrow 1if

\|\{h′∈kring1​\(h\):ℓh′∗=0\}\|<1\|\\\{h^\{\\prime\}\\in\\mathrm\{kring1\}\(h\):\\ell^\{\*\}\_\{h^\{\\prime\}\}=0\\\}\|<1
8:Compute quantiles

q40,q65,q80q\_\{40\},q\_\{65\},q\_\{80\}over

\{s​\(h\):ℓh∗=0\}\\\{s\(h\):\\ell^\{\*\}\_\{h\}=0\\\}
9:Compute target resolutions

r∗​\(h\)r^\{\*\}\(h\)per \([5](https://arxiv.org/html/2606.18280#S3.E5)\)

10:Propagate refinement to neighbours:

11:for

hhwith

r∗​\(h\)\>r0r^\{\*\}\(h\)\>r\_\{0\}do

12:for

h′h^\{\\prime\}in k\-ring\-1 neighbours of

hhdo

13:

r∗​\(h′\)←max⁡\(r∗​\(h′\),r∗​\(h\)\)r^\{\*\}\(h^\{\\prime\}\)\\leftarrow\\max\(r^\{\*\}\(h^\{\\prime\}\),r^\{\*\}\(h\)\)
14:endfor

15:endfor

16:Refine:

17:for

hhwith

r∗​\(h\)\>r0r^\{\*\}\(h\)\>r\_\{0\}do

18:Replace

hhwith children

\{c:c∈H3children​\(h,r∗​\(h\)\)\}\\\{c:c\\in\\mathrm\{H3children\}\(h,r^\{\*\}\(h\)\)\\\}
19:Sample feature values for each child from fine rasters

20:endfor

21:returnpartition

𝒫\\mathcal\{P\}with per\-cell resolution, features, and inclusion label

## 4Implementation and Computational Complexity

Letn=\|ℋr0\|n=\|\\mathcal\{H\}\_\{r\_\{0\}\}\|be the number of base\-resolution cells\. Stage 1 runs inO​\(n​d\)O\(nd\)time for feature extraction andO​\(n​d\)O\(nd\)for PCA scoring\. Stage 2 constructs an MRF withnnnodes and at most6​n6nedges \(H3 hexagonal adjacency\), and solves it inO​\(n2​n\)O\(n^\{2\}\\sqrt\{n\}\)worst\-case time via the Boykov\-Kolmogorov max\-flow algorithm, though empirical runtimes are substantially faster on geographic grids\. Stage 3 runs inO​\(n⋅7rmax−r0\)O\(n\\cdot 7^\{r\_\{\\max\}\-r\_\{0\}\}\)in the worst case \(all cells refined to maximum resolution\), but in practice only a small fraction of cells are refined tormaxr\_\{\\max\}\.

## 5Discussion and Limitations

IOAH3 addresses the MAUP sensitivity problem at the partition construction stage, prior to any modelling step\. The graph\-cut formulation is principled in that it admits an exact solution and makes the importance\-smoothness trade\-off explicit through theλ\\lambdaparameter\. The hierarchical H3 structure guarantees that refinement is geometrically consistent and that child\-cell feature values can be sampled directly from the same raster sources\.

Several limitations are worth acknowledging\. First, the PCA importance score is a linear aggregation of the input features; non\-linear importance structure \(for example, interaction between road density and hazard level\) is not captured\. A learned importance function, trained on downstream task performance, would be more expressive but requires labelled data\. Second, the MRF smoothness term is defined over population and hazard signals only; a more general formulation would include all feature signals in the pairwise weights\. Third, the quantile\-based refinement thresholds in \([5](https://arxiv.org/html/2606.18280#S3.E5)\) are fixed at the 40th, 65th, and 80th percentiles; these were chosen empirically and may require adjustment for domains with different importance distributions\.

## 6Conclusion

We have presented IOAH3, a three\-stage method for constructing adaptive spatial partitions of geo\-referenced observation domains over H3 hierarchical grids\. The method combines PCA\-based importance scoring, MRF graph\-cut optimisation for spatially coherent cell selection, and data\-driven hierarchical refinement with neighbour propagation\. The resulting multi\-resolution partitions concentrate fine\-grained cells in regions of high informational importance while maintaining a coarser but complete background partition\. The method is fully automated, parameter\-light, and produces citable, reproducible output suitable as input to downstream spatial inference pipelines\.

## References

- An experimental comparison of min\-cut/max\-flow algorithms for energy minimization in vision\.IEEE Transactions on Pattern Analysis and Machine Intelligence26\(9\),pp\. 1124–1137\.Cited by:[§2\.2](https://arxiv.org/html/2606.18280#S2.SS2.p1.5),[§3\.2](https://arxiv.org/html/2606.18280#S3.SS2.p4.1)\.
- I\. Brodsky \(2018\)H3: Uber’s hexagonal hierarchical spatial index\.Note:Uber Engineering BlogExternal Links:[Link](https://www.uber.com/us/en/blog/h3/)Cited by:[§2\.1](https://arxiv.org/html/2606.18280#S2.SS1.p1.5)\.
- V\. Kolmogorov and R\. Zabih \(2004\)What energy functions can be minimized via graph cuts?\.IEEE Transactions on Pattern Analysis and Machine Intelligence26\(2\),pp\. 147–159\.Cited by:[§2\.2](https://arxiv.org/html/2606.18280#S2.SS2.p1.5),[§3\.2](https://arxiv.org/html/2606.18280#S3.SS2.1.p1.2)\.
- S\. Openshaw \(1984\)The modifiable areal unit problem\.Geo Books,Norwich\.External Links:ISBN 0860941345Cited by:[§1](https://arxiv.org/html/2606.18280#S1.p1.1)\.