Consensus Driven by the Geometric Mean

Herbert Mangesius, Dong Xue, Sandra Hirche

TL;DR

While standard network consensus focuses on finding an arithmetic average, many real-world systems—from chemical reactions to financial models—operate on multiplicative or power-law scales. This paper introduces three novel non-linear consensus protocols driven by the geometric mean, proving they converge exponentially and revealing a deep connection between network averaging, chemical kinetics, and the gradient descent of "free energy."

What Problem Does This Paper Address?

In network theory, "consensus" is the process by which a group of agents reaches a common value through local interactions. Traditionally, this is modeled as a linear system where agents move toward the arithmetic mean of their neighbors.

However, the authors argue that the arithmetic mean isn't always the right tool. In fields like biology (gene expression), finance (compound growth), and power grids, the underlying dynamics are inherently non-linear. In these cases, the geometric mean—which is better suited for data exhibiting power-law relationships—is a more natural "target" for the network to reach. The challenge addressed here is designing and proving the stability of continuous-time protocols that drive a network toward this geometric consensus.

Methods

The authors propose three distinct non-linear protocols, each characterized by a different type of non-linearity in their differential equations:

  1. Polynomial Protocol: Structured similarly to chemical reaction kinetics. It models the rate of change as a balance between "in-flows" and "out-flows" represented by products of states raised to specific weights.
  2. Entropic Protocol: Driven by "negative relative entropy" (or information divergence). It moves agents based on the logarithmic difference between their state and their neighbors.
  3. Scaling-Invariant Protocol: A log-linear update rule that behaves like a standard consensus system but operates in logarithmic coordinates.

To prove these systems work, the authors use a clever mathematical "bridge": they transform these non-linear, time-invariant equations into "virtual" linear time-varying consensus systems. This allows them to apply established stability results from linear theory to prove that these complex non-linear systems will always converge exponentially to a single value.

Datasets

The paper does not use empirical datasets. Instead, it validates the theoretical findings using numerical simulations on synthetic graph structures:

  • Strongly connected balanced digraphs: Where every node has equal incoming and outgoing influence.
  • Non-balanced digraphs: Where influence is weighted unevenly, testing the "weighted" versions of the geometric mean.
  • Complete graphs: Used specifically to study the bounds of the polynomial protocol.

Key Insights and Ideas

  • The "Virtual Graph" Perspective: One of the most powerful ideas in the paper is treating non-linear interactions as a linear system on a "virtual graph" where the edge weights change over time based on the agents' current states.
  • Free Energy Gradient Flows: The authors show that all three protocols are actually performing a form of optimization. They are "gradient flows" of a free energy functional (related to relative entropy). Essentially, the network is "sliding down" an energy surface toward the most efficient state: the geometric mean.
  • Chemical Kinetics Connection: The polynomial protocol bridges the gap between social/robotic consensus and biochemistry. It shows that the way chemicals reach equilibrium in a reaction is mathematically equivalent to a network reaching a geometric mean consensus.
  • Variational Characterization: The paper provides a new way to define the geometric mean: it is the unique solution that minimizes free energy on a manifold where the product of all components remains constant.

Key Results

  • Guaranteed Convergence: The authors prove that for any positive initial conditions, all three protocols achieve global exponential convergence to a consensus state.
  • Analytical Targets:
    • The Entropic Protocol converges exactly to the weighted geometric mean of the initial states.
  • The Scaling-Invariant Protocol converges to the weighted arithmetic mean, but does so via log-linear dynamics.
  • Polynomial Bounds: While the exact consensus value for the polynomial protocol is harder to pin down analytically, numerical results show it is strictly bounded between the arithmetic mean and the "arithmetic-geometric mean" (a value related to elliptic integrals).

Limitations and Future Work

  • Positive Constraints: The protocols require all initial states to be positive ($x > 0$), which is natural for chemical concentrations or stock prices but might limit applications where states can be zero or negative.
  • Polynomial Protocol Complexity: The authors acknowledge they haven't yet analytically derived the exact consensus value for the polynomial protocol, noting it likely involves complex elliptic integrals. This remains a "conjecture" for future proof.
  • Graph Topology: While the paper touches on time-varying graphs, the primary focus is on constant weightings. Extending the variational framework to more radical network switching remains an open area.

Summary updated

Abstract

Consensus networks are usually understood as arithmetic mean driven dynamical averaging systems. In applications, however, network dynamics often describe inherently non-arithmetic and non-linear consensus processes. In this paper, we propose and study three novel consensus protocols driven by geometric mean averaging: a polynomial, an entropic, and a scaling-invariant protocol, where terminology characterizes the particular non-linearity appearing in the respective differential protocol equation. We prove exponential convergence to consensus for positive initial conditions. For the novel protocols we highlight connections to applied network problems: The polynomial consensus system is structured like a system of chemical kinetics on a graph. The entropic consensus system converges to the weighted geometric mean of the initial condition, which is an immediate extension of the (weighted) average consensus problem. We find that all three protocols generate gradient flows of free energy on the simplex of constant mass distribution vectors albeit in different metrics. On this basis, we propose a novel variational characterization of the geometric mean as the solution of a non-linear constrained optimization problem involving free energy as cost function. We illustrate our findings in numerical simulations.
BibTeX
@article{mangesius2018consensus,
  author = {Herbert Mangesius and Dong Xue and Sandra Hirche},
  title = {{Consensus Driven by the Geometric Mean}},
  journal = {IEEE Trans. Control. Netw. Syst.},
  year = {2018},
  doi = {10.1109/tcns.2016.2598665},
}

Loading related content...

Figure