Accuracy criterion for mean field approximations of Markov processes on hypergraphs

Basic Information

• Paper ID: 2201.02041
• Title: Accuracy criterion for mean field approximations of Markov processes on hypergraphs
• Authors: Dániel Keliger (Budapest University of Technology and Economics), Illés Horváth (MTA-BME Information Systems Research Group)
• Classification: math.PR (Probability Theory)
• Publication Date: October 15, 2025
• Paper Link: https://arxiv.org/abs/2201.02041

Abstract

This paper provides error bounds for the N-intertwined mean field approximation (NIMFA) of locally density-dependent Markov population processes operating on well-distributed underlying network structures. The research demonstrates that NIMFA is accurate when typical vertices have many neighbors. This result provides theoretical justification for the most commonly used approximation methods in epidemiology, statistical physics, and opinion dynamics literature under specific conditions. The paper extends beyond interactions between two individuals and accordingly adopts hypergraph structures.

Research Background and Motivation

1. Problem to be addressed: Exact analysis of stochastic population processes becomes infeasible due to exponential growth of the state space with population size, even for moderately sized populations. Therefore, good approximation methods are needed.
2. Problem importance: Analysis of stochastic population processes is an important topic across multiple disciplines including epidemiology, biology, economics, and computer systems. These processes involve large numbers of interacting individuals (agents) that perform stochastic actions based on the behavior of other individuals.
3. Limitations of existing approaches:
   • Kurtz's classical results assume each individual observes the entire population, which is overly restrictive in practical applications
   • In many real population processes, individuals can only observe a subset of the population
   • Theoretical proofs for NIMFA rely primarily on numerical evidence, lacking rigorous theoretical analysis
4. Research motivation: To provide rigorous error bounds for NIMFA, particularly on well-distributed networks, and to extend to hypergraph structures allowing interactions among more than two individuals.

Core Contributions

1. Provides general error bounds for NIMFA with strong performance on well-distributed networks
2. Extends to hypergraph structures allowing higher-order interactions among more than two individuals
3. Under additional homogeneity assumptions, such as annealed networks or activity-driven networks, proves that error bounds are small
4. Further simplifies NIMFA to other known approximation methods, such as heterogeneous mean field approximation
5. Applies Szemerédi regularity lemma to reduce the number of equations

Methodology Details

Task Definition

Study the accuracy of mean field approximations for locally density-dependent Markov population processes on hypergraphs. Each vertex is in some state from a finite state space S, and can change states in a Markovian manner.

Model Architecture

1. Hypergraph Structure

• Vertex set: N = {1, ..., N}
• Hyperedges: (i, j₁, ..., jₘ), where 1 ≤ m ≤ M, with the first vertex i being special
• Weights: w^(m)_{i,j₁,...,jₘ} describing the joint influence intensity of j₁, ..., jₘ on vertex i

2. Markov Process Definition

The state of each vertex i at time t is represented by indicator variable ξᵢ,ₛ(t). The m-neighborhood is defined as:

$\phi^{(m)}_{i,s}(t) = \sum_{j \in [N]^m} w^{(m)}_{i,j} \xi^{(m)}_{j,s}(t)$

The transition rate function is: qₛₛ'(φᵢ(t)), where φᵢ(t) contains all m-neighborhood information.

3. NIMFA Approximation

NIMFA approximates the original process through the following system:

$\frac{d}{dt}z_i(t) = Q(\zeta_i(t))z_i(t)$

where: $\zeta^{(m)}_{i,s}(t) = \sum_{j \in [N]^m} w^{(m)}_{i,j} z^{(m)}_{j,s}(t)$

Technical Innovations

1. Introduction of auxiliary process: Constructs an auxiliary Markov process ξ̂ᵢ,ₛ(t) whose transition rates use NIMFA's ζᵢ(t) rather than the original φᵢ(t)
2. Coupling technique: Uses the same background Poisson process to couple the original process and auxiliary process
3. Hierarchical error analysis:
   • D^(0)_i(t): Error in indicator variables
   • D^(m)_i(t): Error in m-neighborhoods
   • Establishes recursive relationships via Grönwall inequality

Experimental Setup

Datasets

The paper primarily employs theoretical analysis and numerical verification using the following models:

1. Simplified SIS model: On modified ring graphs connecting the nearest 10 and 100 neighbors
2. Glauert dynamics: Spin systems in statistical physics
3. Voting model: Opinion dynamics model
4. Majority rule model: Community-based opinion update

Evaluation Metrics

• Prediction accuracy of infected individual proportions
• Deviation between NIMFA estimates and simulation results
• Tightness of error bounds

Comparison Methods

• Exact simulation (averaged over 1000 runs)
• Homogeneous mean field approximation (HMFA)
• Heterogeneous mean field approximation (IMFA)

Experimental Results

Main Results

Theorem 2 (Main Result): Assuming initial conditions ξᵢ(0) are independent and satisfy condition (16), then for each t ≥ 0, there exists a constant C = C(t, δₘₐₓ, R) such that:

$\max_i \sup_{0≤τ≤t} P(\xi_i(τ) \neq \hat{\xi}_i(τ)) ≤ \frac{1}{2}D_{max}(t) ≤ C\sqrt{w^*_{max}}$

For the case M = 1, there exist constants C₁, C₂ such that: $\||\tilde{D}(t)\|| ≤ C₁(1+t)\exp(C₂||W+I||t)||\mu||$

Numerical Verification

Figures 2 and 3 show results of the SIS process on modified ring graphs:

• NIMFA accuracy significantly improves as degree increases from 10 to 100
• Simulation results (triangles) align closely with NIMFA estimates (solid lines)
• Validates theoretical predictions: NIMFA is more accurate when vertices have more neighbors

Ablation Studies

The paper analyzes the impact of different network structures on error bounds:

1. Convention 1: wₘₐₓ = 1/d̄, error is small when average degree is large
2. Convention 2: wₘₐₓ = 1/dₘᵢₙ, sensitive to low-degree vertices
3. Regular hypergraphs: Simplifies to HMFA under uniform initial conditions

Related Work

Main Research Directions

1. Kurtz's classical results: Mean field limits of density-dependent Markov chains
2. Epidemic models on networks: SIS, SIR and other models on graphs
3. Mean field approximations: Various dimensionality reduction approximation methods

Relationship to Related Work

• Sridhar and Kar 30,31: More general conditions than this work (only bounded degree vs. doubly stochastic matrices)
• Parasnis et al. 24: Extension to age-structured populations and time-varying networks
• Provides local bounds: Not just global averages, but predictions for individual vertices

Conclusions and Discussion

Main Conclusions

1. When network weights are well-distributed (e.g., vertices typically have large degree), NIMFA provides accurate approximations
2. Error bounds are O(√w*ₘₐₓ + 1/√N)
3. Theory justifies the reasonableness of commonly used approximations in epidemiology, statistical physics, and opinion dynamics

Limitations

1. Sparse graph problem: Error bounds perform poorly for truly sparse graphs (bounded average degree)
2. Upper regularity condition: May be overly restrictive for some applications
3. Network structure requirements: Requires complete network knowledge, typically unavailable in practice

Future Directions

1. Extension to cases with rapidly decaying degree distributions
2. Application of weak versions of Szemerédi lemma for better algorithmic properties
3. Study of coarse-graining performance in preserving network dynamics

In-Depth Evaluation

Strengths

1. Theoretical rigor: Provides the first rigorous error bounds for NIMFA
2. Methodological innovation: Clever construction of auxiliary processes and coupling techniques
3. Broad applicability: Covers epidemiology, statistical physics, opinion dynamics, and other fields
4. Strong extensibility: Extends from graphs to hypergraphs, allowing higher-order interactions

Weaknesses

1. Limited practical applicability: Limited capability in handling sparse networks
2. Stringent conditions: Requires networks to satisfy specific regularity conditions
3. Insufficient numerical verification: Primarily theoretical results with relatively simple numerical experiments

Impact

1. Theoretical contribution: Provides important theoretical foundation for mean field theory of Markov processes on networks
2. Practical value: Guides selection of appropriate approximation methods in practical applications
3. Reproducibility: Clear theoretical results, but requires more numerical verification

Applicable Scenarios

• Modeling epidemic spread on large-scale networks
• Analysis of opinion dynamics on social networks
• Study of phase transitions in statistical physics systems
• Network dynamics problems requiring computational efficiency while maintaining certain accuracy

References

1. Kurtz, T. (1978). Strong approximation theorems for density dependent Markov chains
2. Van Mieghem, P. (2011). The N-intertwined SIS epidemic network model
3. Sridhar, A. & Kar, S. (2021). Mean-field approximation for stochastic population processes in networks
4. Szemerédi, E. (1975). Regular partitions of graphs

This paper provides an important theoretical foundation for mean field approximations of Markov processes on networks. While it has limitations in handling sparse networks, its rigorous mathematical analysis and broad application prospects make it a significant contribution to the field.