⚡ electrical engineering

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

This paper introduces a unified tensor-based framework for modeling higher-order Markov chains with memory, utilizing even-order paired tensors to analyze steady states and convergence while applying the approach to define memory-driven random walks on hypergraphs for studying higher-order networks.

Original authors: Shaoxuan Cui, Lingfei Wang, Hildeberto Jardon-Kojakhmetov, Karl Henrik Johansson, Ming Cao

Published 2026-04-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Shaoxuan Cui, Lingfei Wang, Hildeberto Jardon-Kojakhmetov, Karl Henrik Johansson, Ming Cao

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to predict the next move in a complex game, like a board game or a video game.

The Old Way (Classical Markov Chains):
Traditionally, mathematicians have used a tool called a "Markov Chain" to predict the future. This tool operates on a simple rule: "The future depends only on the present."
Think of it like a drunk person walking home. If they are currently at the corner of Main and 1st, the only thing that matters for their next step is that they are at Main and 1st. It doesn't matter if they walked there from the park or the grocery store; the past is erased. They just look at where they are right now and pick a direction.

The Problem:
Real life isn't like that.

Memory Matters: In a conversation, what you say next depends on what was said five minutes ago, not just the last word.
Groups Matter: In a social network, a group of three friends might do something together that two friends wouldn't. A simple "pairwise" connection (A talks to B) misses the group dynamic (A, B, and C are in a huddle).

The paper you shared, "Markov Chains and Random Walks with Memory on Hypergraphs," proposes a new, super-powered way to model these complex situations.

Here is the breakdown using simple analogies:

1. The "Hypergraph": The Group Hug

Standard graphs are like a network of handshakes. You shake hands with one person at a time.
Hypergraphs are like group hugs. A single "hyperedge" can connect three, four, or ten people all at once.

Analogy: Imagine a dance floor. A standard graph tracks who is dancing with whom (pairs). A hypergraph tracks the whole dance circle (a group of 5 people moving together).

2. The "Memory": The Movie Script

The authors realized that in these group settings, the order matters.

Analogy: Imagine a relay race.
- No Memory: The runner just knows "I am at the baton."
- With Memory: The runner knows, "I am at the baton, and I just received it from the person who ran the first leg."
- The paper treats the "past sequence" (the history of the race) as a single, solid block. It doesn't just look at the current runner; it looks at the entire team's path so far.

3. The "Tensor": The Multi-Dimensional Spreadsheet

To handle these "group hugs" with "memory," the authors use a mathematical object called a Tensor.

Analogy:
- A Vector is a list (1D).
- A Matrix is a spreadsheet (2D).
- A Tensor is a multi-layered, 3D (or higher) cube of data.
- Think of a Rubik's Cube. A matrix is just one flat face. A tensor is the whole cube. This allows the math to hold information about "Who is with whom" AND "In what order did they arrive?" simultaneously.

4. The "Unfolding": Flattening the Cube

The paper's big trick is "Tensor Unfolding."

Analogy: Imagine you have a complex, 3D puzzle (the memory + group structure). It's hard to solve in 3D. The authors show you how to "unfold" it into a flat 2D sheet (a standard matrix) without losing any information.
Once it's flat, they can use all the standard, powerful math tools we already have to solve it. They call this an "Even-Order Paired Tensor," which is just a fancy way of saying they paired up the "past" with the "future" in a neat, symmetrical package.

5. The "Random Walk": The Explorer

The paper applies this to Random Walks (explorers moving through a network).

The Old Explorer: Walks randomly. If they are at Node A, they pick a neighbor. They forget how they got there.
The New Explorer (Memory Walk): Walks through a "Hypergraph." If they are in a group of 3, they remember the order they entered the group.
- Scenario: If you enter a room through the front door, then the back door, you might leave differently than if you entered through the back then the front.
- The paper shows that this "Memory Explorer" gets stuck in different loops than the "No-Memory Explorer."
- Real-world result: In the paper's example, a group of 5 nodes splits into two separate worlds. A memory-less walker sees one big connected world. A memory-aware walker sees two isolated islands. This changes everything about how we predict where people or information will end up.

6. The "Nonlinear Laplacian": The Shortcut

Finally, the authors found a way to simplify the math even further.

Analogy: Simulating a whole crowd of people moving with memory is computationally heavy (like simulating every single grain of sand in an hourglass).
They derived a "Nonlinear Laplacian" model. This is like a weather forecast model. Instead of tracking every single air molecule, it tracks the "pressure" and "temperature" of the whole system.
They proved that for large systems, this simplified "weather model" gives almost the exact same answer as the complex "grain-by-grain" simulation, but it's much faster to calculate.

Why Does This Matter?

This framework helps us understand complex systems better:

Social Media: How does a rumor spread? Does it matter if it was heard from a friend, then a celebrity, then a news site? (Yes, and this math captures that).
Biology: How do proteins react? It's not just two molecules bumping; it's a chain of events.
Traffic: How does a traffic jam form? It depends on the sequence of cars, not just the car in front of you.

In a nutshell: The authors built a new mathematical "lens" that lets us see the past and the groups simultaneously. They turned a messy, high-dimensional problem into a clean, solvable puzzle, showing us that when we ignore memory and group dynamics, we are often looking at a distorted version of reality.

1. Problem Statement

Classical Markov chains and random walks on graphs rely on two restrictive assumptions:

Pairwise Interactions: Transitions depend only on the current state (memoryless) and interactions between two nodes.
Memorylessness: The next state is independent of the history of past states.

Many real-world complex systems violate these assumptions. Examples include biochemical pathways (multi-molecule reactions), neuronal firing patterns (temporal motifs), and information diffusion in social networks (group-wise interactions with temporal correlations). Neglecting higher-order structures and memory effects leads to inaccurate characterizations of diffusion, ranking, and control processes.

Existing literature addresses these issues separately:

Markov chains with memory exist but often use algebraically cumbersome tensor formulations that are difficult to unfold for memory depths greater than two.
Hypergraph-based random walks capture group interactions but typically remain memoryless.

The Gap: There is no unified framework that simultaneously models higher-order group interactions (hypergraphs) and memory effects (dependence on past state sequences) in a mathematically tractable way.

2. Methodology

The authors propose a unified tensor-based framework that bridges higher-order Markov chains with memory and random walks on directed hypergraphs.

A. Mathematical Foundations

Even-Order Paired Tensors: The core innovation is the use of $2N$ -th order tensors where indices are arranged in $N$ pairs $(i_n, j_n)$ . This structure allows the representation of systems with multiple interacting components and memory.
Einstein Product: The authors utilize the Einstein product ( $*$ ) to generalize matrix multiplication to higher-order tensors. This operation preserves the structure required for memory transitions.
Tensor Unfolding: A mapping function $\phi(\cdot)$ transforms the high-order paired tensor into a standard matrix. This allows the application of classical linear algebra techniques (like the Perron-Frobenius theorem) to analyze higher-order dynamics.

B. Modeling Memory as Hypergraph Transitions

The authors conceptualize a memory-driven transition as motion through a directed hyperedge:

Tail: The ordered sequence of past states $(i_2, \dots, i_m)$ represents the "tail" of the hyperedge.
Head: The next state $i_1$ represents the "head."
Transition Tensor: A transition tensor $P$ encodes probabilities $p_{i_1 i_2 \dots i_m}$ . By lifting this to an even-order paired tensor $\tilde{P}$ , the update rule for the joint probability distribution $\Pi_t$ becomes a linear iteration:
$\Pi_{t+1} = \tilde{P} * \Pi_t$
Upon unfolding, this becomes $\phi(\Pi_{t+1}) = \phi(\tilde{P})\phi(\Pi_t)$ , a standard linear system.

C. Continuous-Time Extension and Approximation

Continuous-Time Formulation: The framework is extended to continuous-time using a flow rate tensor $R$ and a diagonal outflow operator $D$ , forming a rate tensor $\tilde{Q} = \tilde{R} - \tilde{D}$ . The dynamics follow the Kolmogorov forward equation: $\frac{d}{dt}\Pi(t) = \tilde{Q} * \Pi(t)$ .
Low-Dimensional Nonlinear Reduction: To avoid the exponential state space explosion ( $n^{m-1}$ ), the authors apply a mean-field closure (assuming independence of components, $\Pi \approx x^{\otimes (m-1)}$ ). This reduces the system to a nonlinear differential equation:
$\dot{x} = R x^{m-1} - F x^{m-1} = L x^{m-1}$
where $L$ is a higher-order Laplacian tensor. This transforms the problem into finding an H-eigenvalue of the Laplacian.

3. Key Contributions

Unified Tensor Formulation: Proposed an even-order paired tensor formulation for Markov chains with arbitrary finite memory depth $m$ . This provides an explicit, constructive procedure for tensor unfolding for any $m \geq 2$ , overcoming limitations of previous works restricted to $m=2$ .
Theoretical Analysis of Convergence:
- Proved the existence and uniqueness of stationary distributions for discrete-time memory chains using the Perron-Frobenius theorem for U-irreducible tensors.
- Established global convergence for the continuous-time nonlinear Laplacian system under a higher-order detailed-balance condition and strong connectivity of the interaction graph.
Memory-Aware Hypergraph Random Walks: Defined a new class of random walks on directed hypergraphs where hyperedges encode ordered memory transitions. This framework captures dynamics that cannot be collapsed into memoryless projected graphs.

4. Key Results

Stationary Distributions: For discrete-time chains, the steady state is the marginal sum of the dominant U-eigentensor of the transition tensor. The convergence rate is determined by the second-largest U-eigenvalue.
Nonlinear Dynamics: The continuous-time approximation yields a nonlinear system where the stationary state corresponds to a zero H-eigenvalue of the Laplacian tensor.
Detailed Balance & Stability: If the transition tensor satisfies a higher-order detailed-balance condition ( $r_{i_1 i_2 I} x^*_{i_2} = r_{i_2 i_1 I} x^*_{i_1}$ ) and the interaction graph is strongly connected, the system globally converges to a unique equilibrium (up to a scaling factor).
Hypergraph Case Study:
- Applied to a hypergraph with two disjoint hyperedges $\{1,2,3\}$ and $\{3,4,5\}$ .
- Result: Unlike memoryless random walks (which would merge these into a single irreducible component on a projected graph), the memory-based walk splits the system into two closed communicating classes. The stationary distribution depends on the initial condition, revealing behavior inaccessible to classical approaches.
- Simulation: Numerical simulations ( $n=6, m=5$ ) showed that the nonlinear Laplacian approximation closely matches the exact unfolded dynamics in both transient evolution and steady-state distribution.

5. Significance

Theoretical Unification: This work successfully unifies two distinct fields (memory-dependent processes and hypergraph theory) under a single tensor algebraic framework.
Computational Tractability: By utilizing tensor unfolding and mean-field approximations, the framework makes the analysis of high-dimensional memory systems feasible, reducing complexity from exponential to polynomial (for the nonlinear approximation).
New Insights into Complex Systems: The framework reveals that memory fundamentally alters diffusion and connectivity. Systems that appear connected in a projected (memoryless) view may actually be fragmented when memory is accounted for.
Broad Applicability: The tools developed are applicable to diverse fields including neuroscience (temporal motifs), chemistry (reaction pathways), and social network analysis (group dynamics), providing rigorous tools for studying time-dependent higher-order effects.

In conclusion, the paper provides a rigorous mathematical foundation for modeling complex systems where history and group structure matter, offering both exact tensor-based analysis and efficient nonlinear approximations.