Graph Learning for Inverse Landscape Genetics

Prathamesh Dharangutte, Christopher Musco

Abstract

Landscape genetics aims to understand how physical environments influence species dispersal. Traditionally, this field relied on expert heuristics to assign "resistance" values to landscape features. This paper introduces the first efficient, gradient-based optimization framework for inverse landscape genetics, allowing researchers to learn these environmental parameters directly from genetic similarity data. By modeling dispersal as electrical resistance in a graph, the authors provide a scalable solution that significantly outperforms traditional derivative-free methods in both speed and accuracy.

The Inverse Landscape Genetics Problem

Landscape genetics seeks to quantify how features like elevation, land cover, or human infrastructure facilitate or hinder the movement of organisms. Populations separated by high-resistance barriers diverge genetically, while those connected by low-resistance corridors remain similar.

To model this, researchers use "landscape graphs" where nodes represent geographic locations and edge weights represent the ease of dispersal. The inverse landscape genetics problem asks: can we learn the optimal edge weights—and the underlying environmental parameters that determine them—from observed genetic dissimilarity data? Historically, this was a bottleneck, relying on brute-force searches or local heuristics like the Nelder-Mead algorithm, which scale poorly and often fail to find global optima.

A visualization of a landscape graph where edge weights (thickness) represent the ease of dispersal between locations.

A Differentiable Framework for Dispersal

The authors frame the problem as a graph learning task based on three core pillars:

  1. Effective Resistance: Dispersal is modeled using "effective resistance" ($R_{ij}$), treating the landscape as an electrical circuit. Locations with multiple high-weight paths between them have low resistance, mirroring high genetic similarity.
  2. Differentiable Loss Function: The model minimizes the Frobenius norm between the predicted resistance matrix and the observed genetic dissimilarity matrix (specifically the fixation index, $F_{ST}$).
  3. First-Order Optimization: The primary contribution is a method to compute the gradient of this loss function by differentiating through the Moore-Penrose pseudoinverse of a graph Laplacian. To maintain scalability for large graphs, the authors employ the MINRES iterative solver, avoiding the prohibitive $O(n^3)$ cost of direct matrix inversion.

Empirical Performance and Sample Efficiency

The method was evaluated on both synthetic Alaska grid data and real-world genetic data from North American Wolverines (Gulo gulo). The wolverine dataset involved a massive landscape graph with over 24,000 nodes and 47,000 edges, incorporating 17 different land-cover types.

Key results include:

  • Superior Accuracy: On the wolverine dataset, the gradient-based method achieved an $R^2$ of 0.7383, outperforming both the Nelder-Mead heuristic (0.6203) and previous expert-driven models (0.68–0.71).
  • Sample Efficiency: The model demonstrated remarkable robustness to sparse data. As shown in the experimental results, the algorithm can reliably recover landscape parameters with as few as 25 sampled populations, even in the presence of noise.
Parameter estimation error across discrete, continuous, and combined landscape cases, showing performance as a function of sample size and noise.

Conclusion and Future Work

By bringing modern gradient-based optimization to landscape genetics, this work enables the analysis of much larger and more complex environmental datasets than previously possible. While the loss function remains non-convex, the empirical results show consistent convergence to high-quality solutions. Future research may explore "active learning" strategies to identify the most informative geographic locations for genetic sampling, further enhancing the model's efficiency and predictive power.

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 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 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},
}
Figure