Measuring Spatial Clustering via Metropolis-Hastings Diffusion Distance
Machine Learning
Summary
The authors introduce a new way, called diffusion distance, to measure how different two distributions are on a network or graph by looking at how quickly one changes into the other through a special random process. When comparing a distribution to a uniform one, this measure helps detect spatial clustering and extends traditional methods like Moran's I by considering the whole graph structure instead of just local neighborhoods. They provide mathematical foundations, connect the measure to known concepts like graph spectra and optimal transport, and develop a statistical test to identify clustering in large datasets. Their tests show that diffusion distance can detect subtle spatial patterns better than Moran's I, demonstrated both on simulated data and real urban segregation data in U.S. cities.
Authors
Thomas Weighill, Chidinma Williams
Abstract
We propose a novel measure of the discrepancy between two probability distributions $f$ and $g$ on a graph - which we call the diffusion distance - that measures the rate of convergence of $f$ to $g$ under a graph-constrained Markov chain with stationary distribution $g$. As a default choice for this Markov chain, we use the Metropolis-Hastings transition matrix targeting $g$ with proposals given by a random walk on the graph. Our primary case of interest is when the second distribution $g$ is uniform, in which case the diffusion distance becomes a measure of spatial clustering in $f$. Used in this way, (Metropolis-Hastings) diffusion distance to uniformity extends Moran's $I$-type measures of spatial autocorrelation by incorporating global graph geometry rather than just local patterns. Indeed, Moran's $I$, the most well-known measure of spatial autocorrelation, can be viewed as a one-step heuristic for diffusion distance, so long as specific spatial weights are used. We establish theoretical bounds and a stability result for our measure, connecting it to graph spectra and optimal transport. We then turn our attention to outlining a statistical test for spatial clustering using diffusion distance. Under permutation null models, we derive high-probability bounds on diffusion distance underpinned by exact spectral formulas for convergence of distributions, enabling an efficient statistical test for spatial clustering on large datasets. We empirically compare diffusion distance to Moran's $I$ both as a numerical measure and as a statistical test. We show that diffusion distance exhibits higher power on synthetic data using a stochastic block model. Empirical analysis of Black population distributions for 100 U.S. cities shows that diffusion distance detects subtle differences in urban segregation patterns that Moran's $I$ does not.