Research map / Probabilistic and scientific modeling / Dynamical systems
Learning the Topology and Behavior of Discrete Dynamical Systems
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Theoretical study of PAC-learning both topology and threshold interaction functions of discrete synchronous dynamical systems from configuration-successor snapshots: proves NP-hardness in general, efficient learners for perfect matchings, bounded-indegree directed graphs, and partially observed graphs, and tight Natarajan dimension bounds of order n^2.
Problem
Learning both the underlying network topology and the threshold interaction functions of a black-box discrete (synchronous) dynamical system from observed snapshots of its dynamics under the PAC model.
Approach
Extends PAC learning of dynamical systems from known-graph to unknown-graph settings; shows the general problem is NP-hard via a 3SAT reduction to a consistency problem, identifies tractable graph classes with efficient consistent learners, and bounds the Natarajan dimension of the hypothesis class by Theta(n^2).
Key results
- General (Undir, Thresh) SyDS learning is NP-hard via 3SAT reduction, so not efficiently PAC learnable unless NP = RP.
- Efficient PAC learner for perfect-matching graphs with running time O(n^3 q).
- Natarajan dimension of the hypothesis class is at least floor(n^2/4) and at most c*n^2, giving Theta(n^2) tightness.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Learn the topology and threshold interaction functions jointly over general undirected graphs | (Undir, Thresh)-SyDSs · General undirected graphs | efficient PAC learnability | Hurt |
| Restrict the underlying graph to a perfect matching | Threshold SyDSs · Perfect matching graphs | efficient PAC learnability | Helped |
| Restrict the underlying graph to directed graphs with fixed maximum indegree Δ | Threshold SyDSs · Directed graphs with fixed maximum indegree Δ | efficient PAC learnability | Helped |
| Provide the network with at most k missing edges, with at most one missing edge incident on each vertex | Partially observed (Undir, Thresh)-SyDSs · Partially observed network | efficient PAC learnability | Helped |
| Learn both topology and threshold assignments for undirected threshold SyDSs | Undirected threshold SyDS hypothesis class · Undirected threshold SyDS hypothesis class | Natarajan dimension: \geq \lfloor n^2/4 \rfloor; \leq c \cdot n^2 | Mixed |
| Learn topology and threshold assignments jointly | Undirected threshold SyDS hypothesis class · Undirected threshold SyDS hypothesis class | sample complexity: \Theta\left((1 / \epsilon) \cdot (n^2 + \log{}(1/\delta))\right) | Hurt |
Surprising findings
- Learning both topology and behavior is computationally intractable in general, even though learning behavior alone on a known graph is efficient.
Limitations
- Learner only uses positive snapshots (successor pairs), no negative examples.
- General topology learning is NP-hard; tractable results only for restricted graph classes (matchings, bounded indegree, at most one missing edge per vertex).
- Sample complexity bounds are asymptotic and theoretical, with no empirical evaluation.
Experimental setup
Builds on: PAC learning framework Natarajan dimension known-graph learning of threshold SyDS
Closest papers by meaning
- Efficient PAC Learnability of Dynamical Systems Over Multilayer Networks (ICML 2024 · similarity 0.92)
- Let's do the time-warp-attend: Learning topological invariants of dynamical systems (ICLR 2024 · similarity 0.86)
- Learning the Causal Structure of Networked Dynamical Systems under Latent Nodes and Structured Noise (AAAI 2024 · similarity 0.86)
- Benchmarking Structural Inference Methods for Interacting Dynamical Systems with Synthetic Data (NeurIPS 2024 · similarity 0.86)
- Neural Persistence Dynamics (NeurIPS 2024 · similarity 0.86)
- Learning invariant representations of time-homogeneous stochastic dynamical systems (ICLR 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.