On the convergence of nonlinear averaging dynamics with three-body interactions on hypergraphs

• URL: http://arxiv.org/abs/2304.07203v2
• Date: Sun, 30 Jun 2024 15:12:45 GMT
• Title: On the convergence of nonlinear averaging dynamics with three-body interactions on hypergraphs
• Authors: Emilio Cruciani, Emanuela L. Giacomelli, Jinyeop Lee,
• Abstract summary: We investigate a discrete-time nonlinear averaging dynamics with three-body interactions on a hypergraph. By assuming random initial states, we prove that the dynamics converges to a multiplicatively-shifted average of the initial states.
• Score: 1.6467744688891353
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Complex networked systems in fields such as physics, biology, and social sciences often involve interactions that extend beyond simple pairwise ones. Hypergraphs serve as powerful modeling tools for describing and analyzing the intricate behaviors of systems with multi-body interactions. Herein, we investigate a discrete-time nonlinear averaging dynamics with three-body interactions: an underlying hypergraph, comprising triples as hyperedges, delineates the structure of these interactions, while the vertices update their states through a weighted, state-dependent average of neighboring pairs' states. This dynamics captures reinforcing group effects, such as peer pressure, and exhibits higher-order dynamical effects resulting from a complex interplay between initial states, hypergraph topology, and nonlinearity of the update. Differently from linear averaging dynamics on graphs with two-body interactions, this model does not converge to the average of the initial states but rather induces a shift. By assuming random initial states and by making some regularity and density assumptions on the hypergraph, we prove that the dynamics converges to a multiplicatively-shifted average of the initial states, with high probability. We further characterize the shift as a function of two parameters describing the initial state and interaction strength, as well as the convergence time as a function of the hypergraph structure.

Related papers

• Similarity Matching Networks: Hebbian Learning and Convergence Over Multiple Time Scales [5.093257685701887]
  We consider and analyze the emphsimilarity matching network for principal subspace projection.<n>By leveraging a multilevel optimization framework, we prove convergence of the dynamics in the offline setting.
  arXiv  Detail & Related papers  (2025-06-06T14:46:22Z)
• How Particle System Theory Enhances Hypergraph Message Passing [30.792540956996444]
  Hypergraphs effectively model higher-order relationships in natural phenomena, capturing complex interactions beyond pairwise connections.<n>We introduce a novel hypergraph message passing framework inspired by interacting particle systems, where hyperedges act as fields inducing shared node dynamics.
  arXiv  Detail & Related papers  (2025-05-24T05:04:25Z)
• Perfect Clustering in Nonuniform Hypergraphs [2.2252684361733293]
  We introduce a hyper-edge-centric model for analyzing hypergraphs, called the interaction hypergraph. We show that a spectral estimate of the interaction latent positions can achieve perfect clustering once enough interactions are observed.
  arXiv  Detail & Related papers  (2025-04-11T21:12:48Z)
• UnityGraph: Unified Learning of Spatio-temporal features for Multi-person Motion Prediction [13.052342503276936]
  Multi-person motion prediction is a complex emerging field with significant real-world applications. We propose a novel graph structure UnityGraph, which treats multi-temporal features as a whole, enhancing model coherence and couplings-temporal features. Our method achieves the state-of-the-art performance, confirming its effectiveness and innovative design.
  arXiv  Detail & Related papers  (2024-11-06T08:05:36Z)
• TimeGraphs: Graph-based Temporal Reasoning [64.18083371645956]
  TimeGraphs is a novel approach that characterizes dynamic interactions as a hierarchical temporal graph. Our approach models the interactions using a compact graph-based representation, enabling adaptive reasoning across diverse time scales. We evaluate TimeGraphs on multiple datasets with complex, dynamic agent interactions, including a football simulator, the Resistance game, and the MOMA human activity dataset.
  arXiv  Detail & Related papers  (2024-01-06T06:26:49Z)
• Linear Opinion Dynamics Model with Higher-Order Interactions [17.413930396663833]
  We extend the popular Friedkin-Johnsen model for opinion dynamics on graphs to hypergraphs. We show that higher-order interactions play an important role in the opinion dynamics.
  arXiv  Detail & Related papers  (2023-10-09T12:56:11Z)
• SEGNO: Generalizing Equivariant Graph Neural Networks with Physical Inductive Biases [66.61789780666727]
  We show how the second-order continuity can be incorporated into GNNs while maintaining the equivariant property. We also offer theoretical insights into SEGNO, highlighting that it can learn a unique trajectory between adjacent states. Our model yields a significant improvement over the state-of-the-art baselines.
  arXiv  Detail & Related papers  (2023-08-25T07:15:58Z)
• Learning the effective order of a hypergraph dynamical system [4.530678016396476]
  We propose a method to determine the minimum order of a hypergraph necessary to approximate the corresponding dynamics accurately. Specifically, we develop an analytical framework that allows us to determine this order when the type of dynamics is known. We utilize these ideas in conjunction with a hypergraph neural network to directly learn the dynamics itself and the resulting order of the hypergraph from both synthetic and real data sets.
  arXiv  Detail & Related papers  (2023-06-02T09:04:45Z)
• Learning Physical Dynamics with Subequivariant Graph Neural Networks [99.41677381754678]
  Graph Neural Networks (GNNs) have become a prevailing tool for learning physical dynamics. Physical laws abide by symmetry, which is a vital inductive bias accounting for model generalization. Our model achieves on average over 3% enhancement in contact prediction accuracy across 8 scenarios on Physion and 2X lower rollout MSE on RigidFall.
  arXiv  Detail & Related papers  (2022-10-13T10:00:30Z)
• Learning Heterogeneous Interaction Strengths by Trajectory Prediction with Graph Neural Network [0.0]
  We propose the attentive relational inference network (RAIN) to infer continuously weighted interaction graphs without any ground-truth interaction strengths. We show that our RAIN model with the PA mechanism accurately infers continuous interaction strengths for simulated physical systems in an unsupervised manner.
  arXiv  Detail & Related papers  (2022-08-28T09:13:33Z)
• Learning the Evolutionary and Multi-scale Graph Structure for Multivariate Time Series Forecasting [50.901984244738806]
  We show how to model the evolutionary and multi-scale interactions of time series. In particular, we first provide a hierarchical graph structure cooperated with the dilated convolution to capture the scale-specific correlations. A unified neural network is provided to integrate the components above to get the final prediction.
  arXiv  Detail & Related papers  (2022-06-28T08:11:12Z)
• Dynamic Representation Learning with Temporal Point Processes for Higher-Order Interaction Forecasting [8.680676599607123]
  This paper proposes a temporal point process model for hyperedge prediction to address these problems. As far as our knowledge, this is the first work that uses the temporal point process to forecast hyperedges in dynamic networks.
  arXiv  Detail & Related papers  (2021-12-19T14:24:37Z)
• TCL: Transformer-based Dynamic Graph Modelling via Contrastive Learning [87.38675639186405]
  We propose a novel graph neural network approach, called TCL, which deals with the dynamically-evolving graph in a continuous-time fashion. To the best of our knowledge, this is the first attempt to apply contrastive learning to representation learning on dynamic graphs.
  arXiv  Detail & Related papers  (2021-05-17T15:33:25Z)
• Tensor Representations for Action Recognition [54.710267354274194]
  Human actions in sequences are characterized by the complex interplay between spatial features and their temporal dynamics. We propose novel tensor representations for capturing higher-order relationships between visual features for the task of action recognition. We use higher-order tensors and so-called Eigenvalue Power Normalization (NEP) which have been long speculated to perform spectral detection of higher-order occurrences.
  arXiv  Detail & Related papers  (2020-12-28T17:27:18Z)

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.