Static and Dynamic Approaches to Computing Barycenters of Probability Measures on Graphs

Researchers David Gentile and James M. Murphy have published a significant paper introducing a novel method for computing barycenters—essentially weighted averages—of probability measures that exist on graph structures. This addresses a key limitation where classical optimal transport theory, a popular framework for comparing and averaging probability distributions, becomes mathematically degenerate when applied directly to data constrained by a graph's topology. Their work is crucial for machine learning and computer vision applications where data naturally resides on networks, such as social networks, biological interaction graphs, or 3D mesh models.

The core of their approach is a dynamic formulation of the optimal transport problem, which induces a Riemannian geometric structure on the space of probability measures (the simplex). They numerically approximate the necessary exponential mappings and geodesic curves between data points on the graph. Using this geometry, they perform "intrinsic gradient descent" to synthesize new barycenters by iteratively moving data along approximated geodesics toward an average. For analysis, they frame the problem as a quadratic program based on distances between target and reference measures. The authors compare their dynamic, geometry-based method against a more common static approach that uses entropic regularization, presenting numerical experiments across 17 figures to validate that their framework provides a more coherent and effective tool for processing signals on graphs.