Assignment Flows for Data Labeling on Graphs: Convergence and Stability

• URL: http://arxiv.org/abs/2002.11571v3
• Date: Sun, 21 Nov 2021 23:58:37 GMT
• Title: Assignment Flows for Data Labeling on Graphs: Convergence and Stability
• Authors: Artjom Zern, Alexander Zeilmann, Christoph Schn\"orr
• Abstract summary: This paper establishes conditions on the weight parameters that guarantee convergence of the continuous-time assignment flow to integral assignments (labelings) Several counter-examples illustrate that violating the conditions may entail unfavorable behavior of the assignment flow regarding contextual data classification.
• Score: 69.68068088508505
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The assignment flow recently introduced in the J. Math. Imaging and Vision 58/2 (2017), constitutes a high-dimensional dynamical system that evolves on an elementary statistical manifold and performs contextual labeling (classification) of data given in any metric space. Vertices of a given graph index the data points and define a system of neighborhoods. These neighborhoods together with nonnegative weight parameters define regularization of the evolution of label assignments to data points, through geometric averaging induced by the affine e-connection of information geometry. Regarding evolutionary game dynamics, the assignment flow may be characterized as a large system of replicator equations that are coupled by geometric averaging. This paper establishes conditions on the weight parameters that guarantee convergence of the continuous-time assignment flow to integral assignments (labelings), up to a negligible subset of situations that will not be encountered when working with real data in practice. Furthermore, we classify attractors of the flow and quantify corresponding basins of attraction. This provides convergence guarantees for the assignment flow which are extended to the discrete-time assignment flow that results from applying a Runge-Kutta-Munthe-Kaas scheme for numerical geometric integration of the assignment flow. Several counter-examples illustrate that violating the conditions may entail unfavorable behavior of the assignment flow regarding contextual data classification.

Related papers

• Sigma Flows for Image and Data Labeling and Learning Structured Prediction [2.4699742392289]
  This paper introduces the sigma flow model for the prediction of structured labelings of data observed on Riemannian manifold. The approach combines the Laplace-Beltrami framework for image denoising and enhancement, introduced by Sochen, Kimmel and Malladi about 25 years ago, and the assignment flow approach introduced and studied by the authors.
  arXiv  Detail & Related papers  (2024-08-28T17:04:56Z)
• Building symmetries into data-driven manifold dynamics models for complex flows [0.0]
  We exploit the symmetries of the Navier-Stokes equations to find the manifold where the long-time dynamics live. We apply this framework to two-dimensional Kolmogorov flow in a chaotic bursting regime.
  arXiv  Detail & Related papers  (2023-12-15T22:05:21Z)
• Improving embedding of graphs with missing data by soft manifolds [51.425411400683565]
  The reliability of graph embeddings depends on how much the geometry of the continuous space matches the graph structure. We introduce a new class of manifold, named soft manifold, that can solve this situation. Using soft manifold for graph embedding, we can provide continuous spaces to pursue any task in data analysis over complex datasets.
  arXiv  Detail & Related papers  (2023-11-29T12:48:33Z)
• GAFlow: Incorporating Gaussian Attention into Optical Flow [62.646389181507764]
  We push Gaussian Attention (GA) into the optical flow models to accentuate local properties during representation learning. We introduce a novel Gaussian-Constrained Layer (GCL) which can be easily plugged into existing Transformer blocks. For reliable motion analysis, we provide a new Gaussian-Guided Attention Module (GGAM)
  arXiv  Detail & Related papers  (2023-09-28T07:46:01Z)
• Quantum State Assignment Flows [3.7886425043810905]
  This paper flows for assignment as state spaces representing data associated with layers of an underlying weighted graph. The novel approach for data representation and analysis, including the representation of data across the graph by and entanglementization, is presented.
  arXiv  Detail & Related papers  (2023-06-30T18:29:14Z)
• Data-heterogeneity-aware Mixing for Decentralized Learning [63.83913592085953]
  We characterize the dependence of convergence on the relationship between the mixing weights of the graph and the data heterogeneity across nodes. We propose a metric that quantifies the ability of a graph to mix the current gradients. Motivated by our analysis, we propose an approach that periodically and efficiently optimize the metric.
  arXiv  Detail & Related papers  (2022-04-13T15:54:35Z)
• Hyperbolic Graph Embedding with Enhanced Semi-Implicit Variational Inference [48.63194907060615]
  We build off of semi-implicit graph variational auto-encoders to capture higher-order statistics in a low-dimensional graph latent representation. We incorporate hyperbolic geometry in the latent space through a Poincare embedding to efficiently represent graphs exhibiting hierarchical structure.
  arXiv  Detail & Related papers  (2020-10-31T05:48:34Z)
• Asymptotic Analysis of an Ensemble of Randomly Projected Linear Discriminants [94.46276668068327]
  In [1], an ensemble of randomly projected linear discriminants is used to classify datasets. We develop a consistent estimator of the misclassification probability as an alternative to the computationally-costly cross-validation estimator. We also demonstrate the use of our estimator for tuning the projection dimension on both real and synthetic data.
  arXiv  Detail & Related papers  (2020-04-17T12:47:04Z)
• Nonparametric Continuous Sensor Registration [1.290382979353427]
  This paper develops a new mathematical framework that enables nonparametric joint semantic and geometric representation of continuous functions using data. The joint embedding is modeled by representing the processes in a reproducing kernel Hilbert space. An implementation of this framework for RGB-D cameras outperforms the state-of-the-art robust visual odometry.
  arXiv  Detail & Related papers  (2020-01-08T17:40:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.