Learning Interaction Kernels for Agent Systems on Riemannian Manifolds

Mauro Maggioni, Jason Miller, Hongda Qiu, Ming ZhongICML 2021

TL;DR

This paper introduces a nonparametric method to learn the hidden interaction rules (kernels) that govern how agents—like cells, robots, or planets—move and interact on curved surfaces (Riemannian manifolds). By exploiting the physical symmetries of these systems, the authors develop an estimator that avoids the "curse of dimensionality," meaning its accuracy depends on the number of observed trajectories rather than the complexity of the state space.

What Problem Does This Paper Address?

In many scientific fields, we observe systems of interacting particles or "agents" that don't move in flat Euclidean space. For example, opinions might evolve on a manifold of beliefs, or robots might be constrained to move on a sphere. To predict these systems or understand their underlying physics, we need to infer the interaction kernel—the function that determines how the distance between two agents translates into a force or influence.

The primary challenge is the curse of dimensionality. If you try to learn the entire velocity field of $N$ agents in $d$ dimensions directly, the amount of data required grows exponentially with $N \times d$. Furthermore, traditional machine learning tools often struggle with the non-linear geometry and constraints inherent to Riemannian manifolds (like the shortest path between points being a geodesic rather than a straight line).

Methods

The authors propose a nonparametric, inverse-problem-based approach. Instead of learning the high-dimensional function $f$ in $\dot{X} = f(X)$, they exploit the fact that for many physical systems, $f$ is composed of pairwise interactions governed by a one-dimensional kernel $\phi(r)$, where $r$ is the Riemannian distance.

Key components of their method include:

  • Geometric Least Squares: They define a loss functional that measures the difference between observed velocities and those predicted by a candidate kernel, integrated over the manifold's geometry.
  • Symmetry Exploitation: By assuming the system is invariant under agent permutation and that interactions are radially symmetric (depending only on distance), they reduce a high-dimensional learning problem to a 1D function estimation problem.
  • Basis Functions: They represent the unknown kernel $\phi$ using a finite-dimensional space, specifically Clamped B-splines, which allows them to turn the learning task into solving a well-conditioned linear system.
  • Geometric Coercivity: They introduce a "coercivity condition" specific to manifolds, which theoretically guarantees that the kernel is actually recoverable from the observed trajectory data.

Datasets

The paper evaluates the method using synthetic trajectory data generated from two classical dynamical systems across two prototypical manifolds:

  1. Manifolds:
    • The 2D Sphere ($\mathbb{S}^2$): A space with constant positive curvature.
  2. The Poincaré Disk ($\mathbb{PD}$): A model of hyperbolic space with constant negative curvature.
  3. Dynamical Systems:
    • Opinion Dynamics (OD): A homogeneous system where agents' "opinions" move toward or away from each other.
  4. Predator-Swarm (PS1): A heterogeneous system involving two types of agents (prey and predators) with different interaction rules.

The training data consisted of $M=500$ trajectories, each with $L=500$ time steps.

Key Insights and Ideas

  • Dimension Independence: The most significant "aha moment" is that the convergence rate of the estimator is $O(M^{-1/3})$ (ignoring log factors), which is the optimal minimax rate for 1D nonparametric regression. Crucially, this rate does not depend on the dimension of the manifold or the number of agents.
  • Transfer Learning: Because the method learns the fundamental interaction law $\phi$ rather than just fitting a specific trajectory, the learned kernel can be "transferred." You can train on a system with 20 agents and use the result to accurately predict a system with 40 agents.
  • Geometry Matters: The choice of manifold significantly changes the "shortest path" (geodesic) and the volume of space, but the framework handles this naturally by using the manifold's metric tensor $g$ and distance $d_M$.

Key Results

The estimator achieved low relative errors across all tests. For Opinion Dynamics on the sphere, the relative error was approximately $1.89 \times 10^{-1}$.

Learned kernels and trajectory predictions for Opinion Dynamics on the Sphere and Poincaré Disk.

The "mean trajectory error" (the distance between the true and predicted paths) remained stable even when testing on entirely new initial conditions not seen during training. The method successfully captured the "support" of the interaction (the range at which agents stop influencing each other) without prior knowledge.

In the Predator-Swarm system, errors for specific interaction types (like prey-prey) were as low as $8.4 \times 10^{-3}$.

Learned interaction kernels for the heterogeneous Predator-Swarm system.

Limitations and Future Work

  • First-Order Assumption: The current work focuses on first-order systems (velocity-based). The authors note that extending this to second-order systems (acceleration/force-based) would require more complex geometric tools like parallel transport to compare vectors at different points on the manifold.
  • Known Geometry: The method assumes the manifold $(M, g)$ is known beforehand. Learning the interaction kernel and the underlying manifold simultaneously remains an open challenge.
  • Local Interactions: The theory assumes interactions are somewhat local (compactly supported kernels) to ensure unique shortest paths (geodesics) exist between agents. Global interactions on highly curved or "holey" manifolds might complicate the weight vector definitions.

Summary updated

BibTeX
@inproceedings{maggioni2021learning,
  author = {Mauro Maggioni and Jason Miller and Hongda Qiu and Ming Zhong},
  title = {{Learning Interaction Kernels for Agent Systems on Riemannian Manifolds}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
}
Figure