Assignment Flows for Data Labeling on Graphs: Convergence and Stability

  • 2021-10-12 17:32:23
  • Artjom Zern, Alexander Zeilmann, Christoph Schnörr
  • 0


The assignment flow recently introduced in the J. Math. Imaging and Vision58/2 (2017), constitutes a high-dimensional dynamical system that evolves on anelementary statistical manifold and performs contextual labeling(classification) of data given in any metric space. Vertices of a given graphindex the data points and define a system of neighborhoods. These neighborhoodstogether with nonnegative weight parameters define regularization of theevolution of label assignments to data points, through geometric averaginginduced by the affine e-connection of information geometry. Regardingevolutionary game dynamics, the assignment flow may be characterized as a largesystem of replicator equations that are coupled by geometric averaging. Thispaper establishes conditions on the weight parameters that guaranteeconvergence of the continuous-time assignment flow to integral assignments(labelings), up to a negligible subset of situations that will not beencountered when working with real data in practice. Furthermore, we classifyattractors of the flow and quantify corresponding basins of attraction. Thisprovides convergence guarantees for the assignment flow which are extended tothe discrete-time assignment flow that results from applying aRunge-Kutta-Munthe-Kaas scheme for numerical geometric integration of theassignment flow. Several counter-examples illustrate that violating theconditions may entail unfavorable behavior of the assignment flow regardingcontextual data classification.


Quick Read (beta)

loading the full paper ...