Random walks on simplicial complexes

• URL: http://arxiv.org/abs/2404.08803v2
• Date: Tue, 7 May 2024 14:31:13 GMT
• Title: Random walks on simplicial complexes
• Authors: Thomas Bonis, Laurent Decreusefond, Viet Chi Tran, Zhihan Iris Zhang,
• Abstract summary: We show that the generator of our Markov chain is the upper Laplacian defined in the context of algebraic topology for discrete structure. We study the diffusive limits when the simplicial complexes under scrutiny are a sequence of ever refining triangulations of the flat torus.
• Score: 0.9937132009954994
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The notion of Laplacian of a graph can be generalized to simplicial complexes and hypergraphs, and contains information on the topology of these structures. Even for a graph, the consideration of associated simplicial complexes is interesting to understand its shape. Whereas the Laplacian of a graph has a simple probabilistic interpretation as the generator of a continuous time Markov chain on the graph, things are not so direct when considering simplicial complexes. We define here new Markov chains on simplicial complexes. For a given order~$k$, the state space is the set of $k$-cycles that are chains of $k$-simplexes with null boundary. This new framework is a natural generalization of the canonical Markov chains on graphs. We show that the generator of our Markov chain is the upper Laplacian defined in the context of algebraic topology for discrete structure. We establish several key properties of this new process: in particular, when the number of vertices is finite, the Markov chain is positive recurrent. This result is not trivial, since the cycles can loop over themselves an unbounded number of times. We study the diffusive limits when the simplicial complexes under scrutiny are a sequence of ever refining triangulations of the flat torus. Using the analogy between singular and Hodge homologies, we express this limit as valued in the set of currents. The proof of tightness and the identification of the limiting martingale problem make use of the flat norm and carefully controls of the error terms in the convergence of the generator. Uniqueness of the solution to the martingale problem is left open. An application to hole detection is carried.

Related papers

• Disentangled Representation Learning with the Gromov-Monge Gap [65.73194652234848]
  Learning disentangled representations from unlabelled data is a fundamental challenge in machine learning. We introduce a novel approach to disentangled representation learning based on quadratic optimal transport. We demonstrate the effectiveness of our approach for quantifying disentanglement across four standard benchmarks.
  arXiv  Detail & Related papers  (2024-07-10T16:51:32Z)
• Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
  We show that PCA becomes computationally hard at a critical value of the signal's magnitude. We define a new set of objects, which provide an explicit, near-orthogonal basis for invariants of a given degree. It also lets us analyze a new problem of distinguishing between different ensembles.
  arXiv  Detail & Related papers  (2024-04-29T14:33:24Z)
• Path convergence of Markov chains on large graphs [3.693375843298262]
  We show that as the size of a graph goes to infinity, the random trajectories of the processes converge to deterministic curves on the space of measure-valued graphons. A novel feature of this approach is that it provides a precise exponential convergence rate for the Metropolis chain in a certain limiting regime.
  arXiv  Detail & Related papers  (2023-08-18T00:13:59Z)
• Self-Repellent Random Walks on General Graphs -- Achieving Minimal Sampling Variance via Nonlinear Markov Chains [11.3631620309434]
  We consider random walks on discrete state spaces, such as general undirected graphs, where the random walkers are designed to approximate a target quantity over the network topology via sampling and neighborhood exploration. Given any Markov chain corresponding to a target probability distribution, we design a self-repellent random walk (SRRW) which is less likely to transition to nodes that were highly visited in the past, and more likely to transition to seldom visited nodes. For a class of SRRWs parameterized by a positive real alpha, we prove that the empirical distribution of the process converges almost surely to the the target (
  arXiv  Detail & Related papers  (2023-05-08T23:59:09Z)
• Connes implies Tsirelson: a simple proof [91.3755431537592]
  We show that the Connes embedding problem implies the synchronous Tsirelson conjecture. We also give a different construction of Connes' algebra $mathcalRomega$ appearing in the Connes embedding problem.
  arXiv  Detail & Related papers  (2022-09-16T13:59:42Z)
• Counting Markov Equivalent Directed Acyclic Graphs Consistent with Background Knowledge [0.0]
  We consider the more general problem of counting the number of acyclic graphs in a Markov equivalence class when the directions of some of the edges are also fixed. In particular, our algorithm does emphnot depend upon the number of additional edges provided as input.
  arXiv  Detail & Related papers  (2022-06-14T10:45:43Z)
• Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov Random Fields [51.07460861448716]
  This paper presents a convex-analytic framework to learn from data. We show that a triangular convexity decomposition is guaranteed by a transform of the corresponding to its upper part.
  arXiv  Detail & Related papers  (2021-09-17T17:46:12Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
  arXiv  Detail & Related papers  (2021-05-03T16:36:27Z)
• Inverse problems in quantum graphs and accidental degeneracy [0.0]
  The direct spectral problem and the inverse spectral problem are written in terms of simple equations containing information on the topology of a quantum graph. The inverse problem is shown to beener, and some low dimensional examples are explicitly solved.
  arXiv  Detail & Related papers  (2021-03-30T23:52:58Z)
• Building manifolds from quantum codes [0.0]
  We construct the first examples of power law $mathbbZ$ systolic freedom. We give an efficient randomized algorithm to construct a weakly fundamental cycle basis for a graph. We use this result to trivialize the fundamental group of the manifold we construct.
  arXiv  Detail & Related papers  (2020-12-03T20:36:50Z)
• Shannon Entropy Rate of Hidden Markov Processes [77.34726150561087]
  We show how to calculate entropy rates for hidden Markov chains. We also show how this method gives the minimal set of infinite predictive features. A sequel addresses the challenge's second part on structure.
  arXiv  Detail & Related papers  (2020-08-29T00:48:17Z)

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.