# Efficient PAC Learnability of Dynamical Systems Over Multilayer Networks

arXiv: https://arxiv.org/abs/2405.06884 · HTML: https://mlsanity.com/paper/2405.06884/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 65 references that are in the map.
- First posted on arXiv 11 May 2024.

## Builds on (most cited first, 19 of 19)

- [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017)
- [Networks beyond pairwise interactions: structure and dynamics](https://mlsanity.com/paper/2006.01764/) (2020)
- [Multilayer Networks](https://mlsanity.com/paper/1309.7233/) (2013)
- [Epidemic processes in complex networks](https://mlsanity.com/paper/1408.2701/) (2014)
- [The structure and dynamics of multilayer networks](https://mlsanity.com/paper/1407.0742/) (2014)
- [Online Influence Maximization under Linear Threshold Model](https://mlsanity.com/paper/2011.06378/) (2020)
- [Estimating Diffusion Network Structures: Recovery Conditions, Sample Complexity & Soft-thresholding Algorithm](https://mlsanity.com/paper/1405.2936/) (2014)
- [Learning Mixtures of Linear Dynamical Systems](https://mlsanity.com/paper/2201.11211/) (2022)
- [Inferring Graphs from Cascades: A Sparse Recovery Framework](https://mlsanity.com/paper/1505.05663/) (2015)
- [Combinatorial Analysis of Multiple Networks](https://mlsanity.com/paper/1303.4986/) (2013)
- [Network Inference and Influence Maximization from Samples](https://mlsanity.com/paper/2106.03403/) (2021)
- [Trace Complexity of Network Inference](https://mlsanity.com/paper/1308.2954/) (2013)
- [Spreading processes in Multilayer Networks](https://mlsanity.com/paper/1405.4329/) (2014)
- [Reconstructing parameters of spreading models from partial observations](https://mlsanity.com/paper/1608.08698/) (2016)
- [Learning Influence Functions from Incomplete Observations](https://mlsanity.com/paper/1611.02305/) (2016)
- [Characterizing interactions in online social networks during exceptional events](https://mlsanity.com/paper/1506.09115/) (2015)
- [Prediction-Centric Learning of Independent Cascade Dynamics from Partial Observations](https://mlsanity.com/paper/2007.06557/) (2020)
- [Diffusion Source Identification on Networks with Statistical Confidence](https://mlsanity.com/paper/2106.04800/) (2021)
- [Network Diffusions via Neural Mean-Field Dynamics](https://mlsanity.com/paper/2006.09449/) (2020)

## Abstract (arXiv)

Networked dynamical systems are widely used as formal models of real-world cascading phenomena, such as the spread of diseases and information. Prior research has addressed the problem of learning the behavior of an unknown dynamical system when the underlying network has a single layer. In this work, we study the learnability of dynamical systems over multilayer networks, which are more realistic and challenging. First, we present an efficient PAC learning algorithm with provable guarantees to show that the learner only requires a small number of training examples to infer an unknown system. We further provide a tight analysis of the Natarajan dimension which measures the model complexity. Asymptotically, our bound on the Nararajan dimension is tight for almost all multilayer graphs. The techniques and insights from our work provide the theoretical foundations for future investigations of learning problems for multilayer dynamical systems.