pith. sign in

arxiv: 2604.06895 · v1 · submitted 2026-04-08 · 📡 eess.SY · cs.SY

Markov Chains and Random Walks with Memory on Hypergraphs: A Tensor-Based Approach

Shaoxuan Cui , Lingfei Wang , Hildeberto Jardon-Kojakhmetov , Karl Henrik Johansson , Ming Cao This is my paper

Pith reviewed 2026-05-10 18:41 UTC · model grok-4.3

classification 📡 eess.SY cs.SY
keywords Markov chains with memoryhypergraphsrandom walkstensor methodshigher-order networkssteady-state analysisconvergencememory effects
0
0 comments X

The pith

An even-order paired tensor links folded and unfolded dynamics in Markov chains with memory, allowing steady-state and convergence analysis for hypergraph random walks.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper sets out a unified tensor framework to model Markov chains that incorporate memory and higher-order group interactions rather than just pairwise links. It defines an even-order paired tensor that connects two representations of the same dynamics and uses this to derive steady states and convergence behavior. The work then shows how a memory-carrying chain can be reduced to a low-dimensional nonlinear tensor system while retaining its core properties, followed by a complete stability analysis. As a concrete case, random walks on hypergraphs are treated so that memory arises naturally from the hyperedge structure, giving new analysis tools for time-dependent higher-order networks.

Core claim

Our formulation introduces an even-order paired tensor that links folded and unfolded dynamics and characterizes their steady states and convergence. We further show that a Markov chain with memory can be approximated by a low-dimensional nonlinear tensor-based system and then provide a full system analysis. As an application, we define random walks on hypergraphs where memory naturally arises from the hyperedge structure, providing new tools for analyzing higher-order networks with time-dependent effects.

What carries the argument

even-order paired tensor that links folded and unfolded dynamics of a Markov chain with memory

If this is right

  • Steady-state distributions and convergence rates of higher-order Markov chains become computable directly from the spectral properties of the paired tensor.
  • Memory effects can be retained while the state space is reduced to a low-dimensional nonlinear system whose trajectories are easier to analyze.
  • Random walks on hypergraphs acquire explicit memory terms arising from hyperedge incidence, enabling study of time-dependent diffusion on group-structured networks.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same tensor construction could be tested on empirical data from social or biological systems where interactions occur in groups larger than pairs and past states influence future transitions.
  • Because the approximation is low-dimensional, it may support faster numerical integration or control design for large hypergraphs that would otherwise be intractable.
  • The framework suggests a route to compare memory models on hypergraphs with memoryless models on ordinary graphs by examining when the paired tensor reduces to a standard transition matrix.

Load-bearing premise

The even-order paired tensor accurately links folded and unfolded dynamics so that steady states and convergence can be read off from it, and the low-dimensional nonlinear approximation preserves the essential long-term behavior of the original memory-dependent chain.

What would settle it

Numerical simulation of a small hypergraph random walk with explicit memory shows that its empirical stationary distribution or mixing time deviates measurably from the values predicted by the even-order paired tensor and its low-dimensional reduction.

Figures

Figures reproduced from arXiv: 2604.06895 by Hildeberto Jardon-Kojakhmetov, Karl Henrik Johansson, Lingfei Wang, Ming Cao, Shaoxuan Cui.

Figure 1
Figure 1. Figure 1: Left: original hypergraph E = {{1, 2, 3}, {3, 4, 5}}, where all hyperedges are undirected. For example, {1, 2, 3} denotes composition of all ordered tails and heads induced by 1, 2, 3. Right: the corresponding projected graph, obtained by replacing each hyperedge with a complete pairwise subgraph. All edges and hyperedges are equally weighted. as an equality iff a = b. Thus V˙ ≡ 0 iff for all i1, i2, I wit… view at source ↗
Figure 2
Figure 2. Figure 2: Comparison between the unfolded higher-order [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
read the original abstract

Many complex systems exhibit interactions that depend not only on pairwise connections, but also group structures and memory effects. To capture such effects, we develop a unified tensor framework for modeling higher-order Markov chains with memory. Our formulation introduces an even-order paired tensor that links folded and unfolded dynamics and characterizes their steady states and convergence. We further show that a Markov chain with memory can be approximated by a low-dimensional nonlinear tensor-based system and then provide a full system analysis. As an application, we define random walks on hypergraphs where memory naturally arises from the hyperedge structure, providing new tools for analyzing higher-order networks with time-dependent effects.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper develops a unified tensor framework for higher-order Markov chains with memory. It introduces an even-order paired tensor linking folded and unfolded dynamics to characterize steady states and convergence, shows that Markov chains with memory can be approximated by low-dimensional nonlinear tensor-based systems, provides a full system analysis, and applies the approach to random walks on hypergraphs where memory arises naturally from hyperedge structure.

Significance. If the tensor construction and approximation hold with rigorous support, the work could provide useful new tools for modeling memory effects in higher-order networks and hypergraphs. The emphasis on full system analysis and the paired-tensor linkage between dynamics are potentially valuable contributions to tensor methods in network science.

major comments (2)
  1. Abstract: the central claim that a Markov chain with memory can be approximated by a low-dimensional nonlinear tensor-based system without loss of essential properties is load-bearing but unsupported by any derivation, error bound, or verification in the provided text; this assumption requires explicit construction of the approximation and analysis of its fidelity to be credible.
  2. Abstract: the even-order paired tensor is asserted to link folded and unfolded dynamics and characterize steady states and convergence, yet no definition, construction, or proof is supplied; without these the characterization claim cannot be assessed and remains a potential circularity risk if the tensor is defined in terms of the quantities it is meant to characterize.
minor comments (1)
  1. The abstract would benefit from a brief statement of the tensor order, the precise meaning of 'folded' and 'unfolded' dynamics, and at least one concrete example or bound to make the claims more accessible.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and constructive comments, which help clarify the presentation of our central contributions. We address each major comment below and have revised the manuscript to provide the requested explicit constructions, derivations, and analyses.

read point-by-point responses

  1. Referee: Abstract: the central claim that a Markov chain with memory can be approximated by a low-dimensional nonlinear tensor-based system without loss of essential properties is load-bearing but unsupported by any derivation, error bound, or verification in the provided text; this assumption requires explicit construction of the approximation and analysis of its fidelity to be credible.

    Authors: We agree that the abstract claim is central and requires explicit support. While the manuscript body sketches the approximation via tensor unfolding in Section 3, we acknowledge the need for a self-contained derivation and fidelity analysis. In the revised version, we have added a detailed construction of the low-dimensional nonlinear system using higher-order singular value decomposition for truncation, together with an error bound in the Frobenius norm that quantifies the deviation in transition probabilities. We have also included a numerical verification on a small hypergraph example confirming that steady-state distributions and convergence rates are preserved within the derived bound. These changes directly address the concern about essential properties. revision: yes

  2. Referee: Abstract: the even-order paired tensor is asserted to link folded and unfolded dynamics and characterize steady states and convergence, yet no definition, construction, or proof is supplied; without these the characterization claim cannot be assessed and remains a potential circularity risk if the tensor is defined in terms of the quantities it is meant to characterize.

    Authors: We appreciate the referee highlighting the risk of circularity and the absence of explicit details. The paired tensor is constructed in the manuscript from the memory transition tensor and its adjoint without presupposing steady states, but the presentation was insufficiently detailed. In the revision, we have inserted a dedicated subsection with the precise definition (as the even-order tensor formed by pairing the unfolded transition operator with its folded counterpart), the step-by-step construction from the hypergraph incidence structure, and a self-contained proof (via the spectral radius and fixed-point theorem) that the linkage to steady states and convergence follows directly from the tensor's eigenvalue equation. This grounds the characterization in the transition probabilities alone. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The abstract and available claims describe a constructive tensor framework for higher-order Markov chains and random walks on hypergraphs, introducing an even-order paired tensor to link folded/unfolded dynamics and a low-dimensional approximation. No specific equations, derivations, or self-citations are supplied that would allow any claimed prediction, steady-state characterization, or convergence result to reduce by construction to fitted parameters, self-definitions, or prior author work. The modeling steps appear as independent definitions and analyses rather than tautological reductions, making the derivation self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 1 invented entities

The abstract provides insufficient detail to identify specific free parameters, axioms, or invented entities. The 'even-order paired tensor' appears to be a new mathematical construct introduced by the authors for linking dynamics.

invented entities (1)
  • even-order paired tensor no independent evidence
    purpose: Links folded and unfolded dynamics in higher-order Markov chains with memory to characterize steady states and convergence
    Introduced in the abstract as the core of the formulation; no independent evidence or external validation mentioned.

pith-pipeline@v0.9.0 · 5417 in / 1278 out tokens · 42978 ms · 2026-05-10T18:41:48.928185+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages

  1. [1]

    J. R. Norris,Markov chains. Cambridge university press, 1998, no. 2

    work page 1998

  2. [2]

    D. A. Levin and Y . Peres,Markov chains and mixing times. American Mathematical Soc., 2017, vol. 107

    work page 2017

  3. [3]

    The physics of higher-order interactions in complex systems,

    F. Battiston, E. Amico, A. Barrat, G. Bianconi, G. Ferraz de Arruda, B. Franceschiello, I. Iacopini, S. K ´efi, V . Latora, Y . Morenoet al., “The physics of higher-order interactions in complex systems,”Nature physics, vol. 17, no. 10, pp. 1093–1098, 2021

    work page 2021

  4. [4]

    Alon,An introduction to systems biology: design principles of biological circuits

    U. Alon,An introduction to systems biology: design principles of biological circuits. Chapman and Hall/CRC, 2019

    work page 2019

  5. [5]

    Two’s company, three (or more) is a simplex: Algebraic-topological tools for understanding higher-order structure in neural data,

    C. Giusti, R. Ghrist, and D. S. Bassett, “Two’s company, three (or more) is a simplex: Algebraic-topological tools for understanding higher-order structure in neural data,”Journal of computational neu- roscience, vol. 41, no. 1, pp. 1–14, 2016

    work page 2016

  6. [6]

    An sis diffusion process with direct and indirect spreading on a hypergraph,

    S. Cui, F. Liu, L. Liang, H. Jard ´on-Kojakhmetov, and M. Cao, “An sis diffusion process with direct and indirect spreading on a hypergraph,” Automatica, vol. 177, p. 112319, 2025

    work page 2025

  7. [7]

    On metzler positive systems on hypergraphs,

    S. Cui, G. Zhang, H. Jard ´on-Kojakhmetov, and M. Cao, “On metzler positive systems on hypergraphs,”IEEE Transactions on Control of Network Systems, 2025

    work page 2025

  8. [8]

    Temporal networks as a modeling frame- work,

    P. Holme and J. Saram ¨aki, “Temporal networks as a modeling frame- work,” inTemporal networks. Springer, 2013, pp. 1–14

    work page 2013

  9. [9]

    Visual analytics for temporal hypergraph model explo- ration,

    M. T. Fischer, D. Arya, D. Streeb, D. Seebacher, D. A. Keim, and M. Worring, “Visual analytics for temporal hypergraph model explo- ration,”IEEE Transactions on Visualization and Computer Graphics, vol. 27, no. 2, pp. 550–560, 2020

    work page 2020

  10. [10]

    From networks to optimal higher-order models of complex systems,

    R. Lambiotte, M. Rosvall, and I. Scholtes, “From networks to optimal higher-order models of complex systems,”Nature physics, vol. 15, no. 4, pp. 313–320, 2019

    work page 2019

  11. [11]

    Markov chains with memory, tensor for- mulation, and the dynamics of power iteration,

    S.-J. Wu and M. T. Chu, “Markov chains with memory, tensor for- mulation, and the dynamics of power iteration,”Applied Mathematics and Computation, vol. 303, pp. 226–239, 2017

    work page 2017

  12. [12]

    Random walks on hypergraphs,

    T. Carletti, F. Battiston, G. Cencetti, and D. Fanelli, “Random walks on hypergraphs,”Physical review E, vol. 101, no. 2, p. 022308, 2020

    work page 2020

  13. [13]

    Hypergraph ran- dom walks, laplacians, and clustering,

    K. Hayashi, S. G. Aksoy, C. H. Park, and H. Park, “Hypergraph ran- dom walks, laplacians, and clustering,” inProceedings of the 29th acm international conference on information & knowledge management, 2020, pp. 495–504

    work page 2020

  14. [14]

    Higher- order laplacian dynamics on hypergraphs with cooperative and antago- nistic interactions,

    S. Cui, C. Zhang, B. Jiang, H. J. Kojakhmetov, and M. Cao, “Higher- order laplacian dynamics on hypergraphs with cooperative and antag- onistic interactions,”arXiv preprint arXiv:2502.08276, 2025

    work page arXiv 2025

  15. [15]

    Analysis of higher-order lotka-volterra models: Application of s- tensors and the polynomial complementarity problem,

    S. Cui, Q. Zhao, G. Zhang, H. Jardon-Kojakhmetov, and M. Cao, “Analysis of higher-order lotka-volterra models: Application of s- tensors and the polynomial complementarity problem,”IEEE Trans- actions on Automatic Control, 2025

    work page 2025

  16. [16]

    Multilinear control systems theory,

    C. Chen, A. Surana, A. M. Bloch, and I. Rajapakse, “Multilinear control systems theory,”SIAM Journal on Control and Optimization, vol. 59, no. 1, pp. 749–776, 2021

    work page 2021

  17. [17]

    Algebraic riccati tensor equations with applications in multilinear control systems,

    Y . Wang, Y . Wei, G. Zhang, and S. Y . Chang, “Algebraic riccati tensor equations with applications in multilinear control systems,” arXiv preprint arXiv:2402.13491, 2024

    work page arXiv 2024

  18. [18]

    Eigenvalues of a real supersymmetric tensor,

    L. Qi, “Eigenvalues of a real supersymmetric tensor,”Journal of Symbolic Computation, vol. 40, no. 6, pp. 1302–1324, 2005

    work page 2005

  19. [19]

    Bullo,Lectures on Network Systems, 1.6 ed

    F. Bullo,Lectures on Network Systems, 1.6 ed. Kindle Direct Pub- lishing, 2022. [Online]. Available: http://motion.me.ucsb.edu/book-lns

    work page 2022

  20. [20]

    What are higher-order networks?

    C. Bick, E. Gross, H. A. Harrington, and M. T. Schaub, “What are higher-order networks?”SIAM Review, vol. 65, no. 3, pp. 686–731, 2023

    work page 2023

  21. [21]

    Directed hyper- graphs and applications,

    G. Gallo, G. Longo, S. Pallottino, and S. Nguyen, “Directed hyper- graphs and applications,”Discrete applied mathematics, vol. 42, no. 2-3, pp. 177–201, 1993

    work page 1993

  22. [22]

    Topics in propagation of chaos,

    A.-S. Sznitman, “Topics in propagation of chaos,” inEcole d’ ´et´e de probabilit´es de Saint-Flour XIX—1989. Springer, 2006, pp. 165–251

    work page 1989

  23. [23]

    Random walks and commu- nity detection in hypergraphs,

    T. Carletti, D. Fanelli, and R. Lambiotte, “Random walks and commu- nity detection in hypergraphs,”Journal of Physics: Complexity, vol. 2, no. 1, p. 015011, 2021

    work page 2021