Graph Learning for Inverse Landscape Genetics

Prathamesh Dharangutte, Christopher Musco

Abstract

The problem of inferring unknown graph edges from numerical data at a graph's nodes appears in many forms across machine learning. We study a version of this problem that arises in the field of landscape genetics, where genetic similarity between organisms living in a heterogeneous landscape is explained by a weighted graph that encodes the ease of dispersal through that landscape. Our main contribution is an efficient algorithm for inverse landscape genetics, which is the task of inferring this graph from measurements of genetic similarity at different locations (graph nodes). Inverse landscape genetics is important in discovering impediments to species dispersal that threaten biodiversity and long-term species survival. In particular, it is widely used to study the effects of climate change and human development. Drawing on influential work that models organism dispersal using graph effective resistances (McRae 2006), we reduce the inverse landscape genetics problem to that of inferring graph edges from noisy measurements of these resistances, which can be obtained from genetic similarity data. Building on the work of Hoskins et al. (2018) on learning edges in social networks, we develop an efficient first-order optimization method for solving this problem. Despite its non-convex nature, experiments on synthetic and real genetic data establish that our method provides fast and reliable convergence, significantly outperforming existing heuristics used in the field.

Introduction

In landscape genetics, understanding how geographic features—such as mountains, rivers, or highways—influence the genetic similarity between populations is vital for conservation. If two groups of a species are genetically similar, they likely share an accessible "path" through the environment; if they are divergent, a barrier likely exists.

Traditionally, ecologists constructed "landscape graphs" manually, assigning resistance values to environmental features based on expert opinion. The Inverse Landscape Genetics problem seeks to automate this: given genetic data, can we learn the environmental parameters that best explain observed gene flow? This is a complex graph learning problem because the relationship between edge weights and genetic similarity is non-convex and computationally expensive to evaluate, often forcing researchers to rely on slow, unreliable local search heuristics.

Methodology

We model the landscape as a weighted, undirected grid graph where edge weights represent the ease of dispersal. To capture biological reality, we utilize effective resistance (from electrical circuit theory) rather than simple shortest paths. This accounts for multiple potential dispersal routes between locations.

Landscape graphs illustrating varying resistance surfaces and the resulting connectivity between nodes A and B.

Our core contribution is a differentiable framework that enables first-order optimization (gradient descent). By differentiating through the Moore-Penrose pseudoinverse of the graph Laplacian, we can compute the gradient of the loss function. To ensure scalability to large-scale graphs (e.g., the 24,000+ node wolverine dataset), we employ the MINRES iterative linear system solver, avoiding the computational bottleneck of direct matrix inversion.

Experimental Results

Synthetic Validation

Experiments on synthetic Alaskan grids demonstrated that gradient descent is significantly more reliable than derivative-free heuristics like Nelder-Mead. The algorithm achieves low parameter recovery error even with sparse sampling, and performance improves consistently as the number of sampled nodes increases.

Parameter recovery error as a function of the number of nodes sampled and noise levels in synthetic experiments.

Real-World Application: North American Wolverine

On genetic data for the North American wolverine (Gulo gulo) in Alaska, our gradient-based method achieved an $R^2$ value of 0.7383, significantly outperforming the Nelder-Mead heuristic (0.6203) and previous expert-designed models (0.68–0.71). The learned parameters were biologically intuitive, identifying open water as a high-resistance barrier and forested areas as corridors for dispersal.

Conclusion

By leveraging first-order optimization and differentiable graph theory, this work provides a powerful tool for ecologists to infer resistance surfaces from sparse genetic data. This capability is essential for predicting the impacts of climate change and habitat fragmentation on biodiversity. Future work will focus on optimizing sampling designs to further enhance the efficiency of landscape genetic studies.

Summary updated

Abstract

The problem of inferring unknown graph edges from numerical data at a graph's nodes appears in many forms across machine learning. We study a version of this problem that arises in the field of \emph{landscape genetics}, where genetic similarity between organisms living in a heterogeneous landscape is explained by a weighted graph that encodes the ease of dispersal through that landscape. Our main contribution is an efficient algorithm for \emph{inverse landscape genetics}, which is the task of inferring this graph from measurements of genetic similarity at different locations (graph nodes). Inverse landscape genetics is important in discovering impediments to species dispersal that threaten biodiversity and long-term species survival. In particular, it is widely used to study the effects of climate change and human development. Drawing on influential work that models organism dispersal using graph \emph{effective resistances} (McRae 2006), we reduce the inverse landscape genetics problem to that of inferring graph edges from noisy measurements of these resistances, which can be obtained from genetic similarity data. Building on the NeurIPS 2018 work of Hoskins et al. 2018 on learning edges in social networks, we develop an efficient first-order optimization method for solving this problem. Despite its non-convex nature, experiments on synthetic and real genetic data establish that our method provides fast and reliable convergence, significantly outperforming existing heuristics used in the field. By providing researchers with a powerful, general purpose algorithmic tool, we hope our work will have a positive impact on accelerating work on landscape genetics.
BibTeX
@inproceedings{dharangutte2021graph,
  author = {Prathamesh Dharangutte and Christopher Musco},
  title = {{Graph Learning for Inverse Landscape Genetics}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i17.17731},
}

Loading related content...

Figure